Scribd
Upload
8 views12 pages

Scan Line Polygon Fill Algorithm Guide

This document discusses scan conversion, which is the last step in the graphics pipeline that takes graphical primitives like lines and polygons and converts them into pixels on the screen. It focuses on filling polygons using a scan line algorithm, which works by iterating through each scan line, tracking the edges that intersect that line, and using an active edge table and even-odd rule to determine which pixels should be filled. It also describes how to handle special cases like vertical edges and calculates pixel colors using bilinear interpolation between vertex colors.

Uploaded by

Saransh kumar
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
8 views12 pages

Scan Line Polygon Fill Algorithm Guide

This document discusses scan conversion, which is the last step in the graphics pipeline that takes graphical primitives like lines and polygons and converts them into pixels on the screen. It focuses on filling polygons using a scan line algorithm, which works by iterating through each scan line, tracking the edges that intersect that line, and using an active edge table and even-odd rule to determine which pixels should be filled. It also describes how to handle special cases like vertical edges and calculates pixel colors using bilinear interpolation between vertex colors.

Uploaded by

Saransh kumar
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd

Scan Conversion

Scan Conversion
Last step in the graphics pipeline
Efficiency is a central issue
Common primitives
Lines (done last class)
Polygons (fill polygons, today)
Circles

Hardware implementations
preferable

Filling Polygons:
Scan Line Algorithm
14
12
10
8
6
4
2
0
0

10

12

14

Filling Polygons:
Special Cases
14
12
10

ymax xmin

1
slope

Edge Table (ET) Entry

4
2
0
0

10

12

14

Scan Line Polygon Fill


Algorithm
14

12

10

11

10

7
6

0
0

10

12

14
0

13

Scan Line

AB
3

6/4

FA

12

CD
12

DE

-5/2

EF

-5/2

BC
5

6/4

AET
AET at scanline y=8
AET at Scanline y =9

ET Record format : (Ymax, Xmin, 1/m)


AET Records format: (Ymax, Xcurrent, 1/m)

Scan Line Polygon Fill:


The Algorithm

Set y to smallest y coordinate that has an entry in ET

Initialize the active edge table (AET) to empty

Repeat until the ET and AET are both empty:


Move from ET bucket at y to AET those edges whose ymin = y. (entering edges)
Remove from AET those edges for which y = ymax.
Sort AET on x

Fill in desired pixels on scan line using even-odd parity from AET

Increment y by one (next scan line)


For each edge in the AET, update x by adding x/y

What color to fill?


Recall Shading in OpenGL: Smooth Shading

Requested by:
glShadeModel(GL_SMOOTH);
Lighting calculations will be done at each vertex
using the material properties, and the vectors v and l
calculated for that vertex.
Bilinear interpolation is used to determine color
values in the interior of the polygon.

Bilinear Interpolation

CA

Cq

Cp

CB

Cp = ?
Cq= ?
Ck = ?

Xa Ya, Xb, Yb, Xk, Yk


Need to calculate Xp,
Xq.
Cp, Cq, Xp, Xq can all
use incremental
methods
Rate of color change!!

Using Incremental Methods


Cx
Cx+1 = Cx + (Cp Cq)/(Xq-Xp)

You might also like