COMP175: Computer Graphics
Lecture 5
Rasterization:
Raster-Based Fill Algorithms
Review
Region filling: The process of coloring in a region of an image
Requirements:
1. A digital representation of a closed shape
2. A test for determining if a point is inside or outside of the shape
3. A rule or procedure for determining the colors of each point
inside the shape
Review
Seed Fill Algorithms
Start will an interior seed point
and grow
Pixel-based descriptions
Boundary fill
Flood fill
Raster-Based Filling
Fill the interior one raster scan
line at a time
Geometric descriptions
Even-odd parity rule
Non-zero winding number rule
Raster-based filling of polygons
Polygon: A sequence of vertices connected by edges
Assume that vertices have been rasterized
Raster-based filling of polygons
For each scan line
Determine points where the scan line intersects the polygon
Raster-based filling of polygons
For each scan line
Determine points where the scan line intersects the polygon
Set pixels between intersection points (using a fill rule)
Even-odd parity rule: set pixels between pairs of intersections
Non-zero winding rule: set pixels according to the winding number
Efficient raster-based fill algorithms
We will consider three implementations:
X-intersection array algorithm
Edge list algorithm
Pinedas algorithm
X-intersection Array Algorithm
X-intersection array algorithm
Basic approach:
1. Create a 2D array of x-intersections.
2. Compute the x-intersections between each edge and the
scan lines of the array.
3. For each scan line, sort the x-intersections left to right.
4. For each scan line, render spans of pixels between pairs of
x-intersections.
X-intersection array algorithm
A two pass approach
First consider each edge of the polygon (object order)
Determine x-intersections
Then consider each scan line (image order)
Fill interior spans
1. Create a 2D array of x-intersections
MxN array: Large enough to hold all possible x-intersections for
each scan line intersecting the polygon
M = the number of scan lines
N = the maximum number of x-intersections for any scan line
Scan line
j0+M-1
x0
x1
x2
j0+M-1
j0+3
j0+3
j0+2
j0+2
j0+1
j0+1
j0
Polygon and scan lines
j0
x-intersection array
xN-1
2. Insert x-intersections into the array
For each edge
a. Determine the x-intersections between the edge and each scan line
b. Place the x-intersection into the edge crossings array
Scan line
j0+M-1
x04
x03
x02
e0 x01
x00
Intersections for edge e0
x1
x2
xN-1
j0+M-1
j0+3
j0+3
j0+2
j0+2
j0+1
j0+1
j0
x0
j0
x04
x03
x02
x01
x00
Add x-intersections for edge e0
2. Insert x-intersections into the array
For each edge
a. Determine the x-intersections between the edge and each scan line
b. Place the x-intersection into the edge crossings array
e1 x
12
x10
x13
Scan line
j0+M-1
x11
j0+3
j0+3
j0+2
j0+2
j0+1
j0+1
j0
Intersections for edge e1
j0+M-1
j0
x0
x1
x2
xN-1
x12
x12
x11
x10
x04
x03
x02
x01
x00
Add x-intersections for edge e1
2. Insert x-intersections into the array
For each edge
a. Determine the x-intersections between the edge and each scan line
b. Place the x-intersection into the edge crossings array
x20
x21
x22
e2
x23
x24
Scan line
j0+M-1
j0+3
j0+3
j0+2
j0+2
j0+1
j0+1
j0
Intersections for edge e2
j0+M-1
j0
x0
x1
x13
x12
x11
x10
x04
x03
x02
x01
x00
x20
x21
x22
x23
x24
x2
xN-1
Add x-intersections for edge e2
2. Insert x-intersections into the array
For each edge
a. Determine the x-intersections between the edge and each scan line
b. Place the x-intersection into the edge crossings array
Scan line
j0+M-1
j0+M-1
x71
x70
e7
Intersections for edge e7
j0+3
j0+3
j0+2
j0+2
j0+1
j0+1
j0
j0
x0
x1
x13
x12
x11
x10
x03
x02
x02
x01
x00
x20 x42
x21 x41
x22 x40
x23 x51
x24 x50
x65
x66
x70
x71
x2
xN-1
x60
x61
x62
x63
x64
Add x-intersections for edge e7
3. Sort the x-intersections
For each row, sort the x-intersections from left to right
Scan line
j0+M-1
j0+M-1
j0+3
j0+3
j0+2
j0+2
j0+1
j0+1
j0
j0
x0
x1
x13
x12
x11
x10
x03
x02
x02
x01
x00
x20 x42
x21 x41
x22 x40
x23 x51
x24 x50
x65
x66
x70
x71
x2
x60
x61
x62
x63
x64
xN-1
4. Render interior spans
Using even-odd parity rule, fill pixels in each row between pairs of
intersection points
Scan line
j0+M-1
j0+M-1
x01
x00
x71
x70
j0+3
j0+3
j0+2
j0+2
j0+1
j0+1
j0
First two spans from x-intersection array
j0
x0
x1
x13
x12
x11
x10
x03
x02
x02
x01
x00
x20 x42
x21 x41
x22 x40
x23 x51
x24 x50
x65
x66
x70
x71
x2
x60
x61
x62
x63
x64
Final x-intersection array
xN-1
Exercise
Fill this polygon using the non-zero winding rule
For each edge, compute the x-intersections
Also store Winding Number Increment (WNI = +1 or -1)
Scan
line
j=8
x07
e0
e3
x14
j=3
j=0
x07
WNI
x37
-1
+1
x15
j=4
j=1
WNI
x16
j=5
j=2
j=7
j=6
e1
x13
x22
e2
x21
x12
1
0
x11
x20
x10
Final x-intersection array
WNI
Exercise
Fill this polygon using the non-zero winding rule
For each edge, compute the x-intersections
Also store Winding Number Increment (WNI = +1 or -1)
Scan
line
j=8
x07
e0
j=7
j=6
e3
x16
j=5
x15
j=4
x14
j=3
j=2
j=1
j=0
e1
x13
x22
e2
x21
x12
x11
x20
x10
x
WNI
x07
x16
x15
x14
x13
x12
x11
x10
x
WNI
x37
-1
+1
x36
-1
+1
x35
-1
+1
x34
-1
+1
x33
-1
+1
x22
-1
+1
x21
-1
-1
x20
+1
+1
Final x-intersection array
WNI
Exercise
Sort edge intersections from left to right
Scan
line
j=8
x07
e0
j=7
j=6
e3
x16
j=5
x15
j=4
x14
j=3
j=2
j=1
j=0
e1
x13
x22
e2
x21
x12
x11
x20
x10
x
WNI
x07
x16
x15
x34
x33
x22
x21
x20
x
WNI
x37
-1
+1
x36
-1
+1
x35
-1
+1
x14
+1
-1
x13
+1
-1
x12
+1
-1
x11
+1
+1
x10
-1
-1
Final x-intersection array
WNI
Exercise
For each scan line, fill pixels according to the winding number
Scan
line
j=8
x07
e0
j=7
j=6
e3
x16
j=5
x15
j=4
x14
j=3
j=2
j=1
j=0
e1
x13
x22
e2
x21
x12
x11
x20
x10
x
WNI
x07
x16
x15
x34
x33
x22
x21
x20
x
WNI
x37
-1
+1
x36
-1
+1
x35
-1
+1
x14
+1
-1
x13
+1
-1
x12
+1
-1
x11
+1
+1
x10
-1
-1
Final x-intersection array
WNI
Memory considerations
A large x-intersection array is needed for
General or concave polygons (M could be large)
High resolution images (N large)
Convex polygon
A maximum of two x-intersections per scan line
M = 2
Sorting is easy
Concave polygon
Subdivide to convex polygons
Digital Differential Analyzer (DDA)
To compute x-intersections efficiently, use DDA:
1. Sample an edge once for each row it crosses.
+
+
+
+
+
+
+
Digital Differential Analyzer (DDA)
To compute x-intersections efficiently, use DDA:
1. Sample an edge once for each row it crosses.
2. Order vertices from bottom to top.
(x1, y1)
+
+
+
+
+
+
+
(x0, y0)
Digital Differential Analyzer (DDA)
To compute x-intersections efficiently, use DDA:
1. Sample an edge once for each row it crosses.
2. Order vertices from bottom to top.
3. Determine the change in x-intersection between rows.
mInv = dx/dy = (x1 x0) / (y1 y0)
+
+
dy
+
+
+
+
dx
Digital Differential Analyzer (DDA)
To compute x-intersections efficiently, use DDA:
1. Sample an edge once for each row it crosses.
2. Order vertices from bottom to top.
3. Determine the change in x-intersection between rows.
4. Determine the first intersection point (x, j0)
+
mInv = dx/dy = (x1 x0) / (y1 y0)
j0 = y0
(int)y0 + 1
+
+
x = x0 + mInv * (j0 y0)
+
+
j0
, if y0 is an integer
, otherwise
(x, j0)
+
Digital Differential Analyzer (DDA)
To compute x-intersections efficiently, use DDA:
if (y0 is an integer)
j = y0
else
j = int(y0) + 1
mInv = (x1 x0) / (y1 y0)
x = x0 + mInv * (j y0)
while (j <= y1) {
xIntercept = x
j=j+1
x = x + mInv
}
Limitations of x-intersection array
A two-pass approach
1. Determine and sort the x-intersections (process each edge)
2. Render the spans (process each scan line)
Can we do it in one pass?
For each scan line, determine the x-intersections in left to right order and fill
spans as we go -> Edge List Algorithm
Edge List Algorithm
Edge list algorithm
Basic approach:
1. Create a global list of all polygon edges.
Pre-process edges to facilitate incremental updates of x-intersections
between scan lines.
Order edges from bottom-left to top-right.
2. Create an active edge list.
Keeps track of edges that intersect the current scan line.
Order active edges left to right.
3. Process each scan line.
a. Determine x-intersections of active edges in left to right order.
b. Fill spans between appropriate x-intersections using a fill rule.
c. Update active edge list.
1. Create a global list of polygon edges
Order edges from bottom-left to top-right.
Global Edge List
e8
Edge
e7
e6
e5
e3
e4
e0
e1
e2
e0
e1
e2
Edge data (dx/dy, j0, x, y1)
2. Create an active edge list
List edges that cross the current scan line.
Order active edges from left to right.
Active Edge List
e8
Edge
e7
e6
e5
e3
Current scan line
e4
e0
e1
e2
a0
a1
a2
a3
Index into the global edge list
4 (index to edge e4)
5
6
3
3. Process each scan line
a. Determine x-intersections of active edges in left to right order.
b. Fill spans between appropriate x-intersections using a fill rule.
c. Update active edge list and move to the next scan line.
Next scan line
Current scan line
a0
a1
a2
a3
An example
Create a global edge list:
e5
e1
e2
e4
e3
e0
e7
General polygon
e6
An example
Create a global edge list:
Pre-process each edge for fast intersection computation
Pre-compute the data needed:
mInv = dx/dy, j0, x(j0), y1, and the edges winding number increment,
if using the non-zero winding rule
Store pre-processed data in the global edge list
(x2,y2)
e1
e2
(x1,y1)
(x5,y5)
e5
e4
e3
(x4,y4)
e6
(x3,y3)
e0
(x0,y0)
(x6,y6)
(x7,y7)
e7
General polygon
Edge
e0
e1
e2
e3
e4
e5
e6
e7
Edge data
mInv0, j00, x(j0)0, y10,
mInv1, j01, x(j0)1, y11,
mInv2, j02, x(j0)2, y12,
mInv3, j03, x(j0)3, y13,
mInv4, j04, x(j0)4, y14,
mInv5, j05, x(j0)5, y15,
mInv6, j06, x(j0)6, y16,
mInv7, j07, x(j0)7, y17,
The global edge list has one entry for
each edge. This list is initially unsorted.
An example
Create a global edge list:
Pre-process each edge for fast intersection computation
Pre-compute the data needed:
mInv = dx/dy, j0, x(j0), y1, and the edges winding number increment,
if using the non-zero winding rule
Store pre-processed data in the global edge list
Sort the global edge list according to each edges bottom vertex
(x2,y2)
e1
e2
(x1,y1)
(x5,y5)
e5
e4
e3
(x4,y4)
e6
(x3,y3)
e0
(x0,y0)
(x6,y6)
(x7,y7)
e7
General polygon
Edge
e0
e7
e6
e2
e3
e1
e4
e5
Edge data
mInv0, j00, x(j0)0, y10,
mInv7, j07, x(j0)7, y17,
mInv6, j06, x(j0)6, y16,
mInv2, j02, x(j0)2, y12,
mInv4, j04, x(j0)4, y14,
mInv1, j01, x(j0)1, y11,
mInv3, j03, x(j0)3, y13,
mInv5, j05, x(j0)5, y15,
Sorted global edge list
An example
Keeps track of which edges are intersected by the current scan line
Initialize the active edge list with edges intersected by the lowest scan line
Active edges are sorted from left to right
(x2,y2)
e1
e2
(x1,y1)
(x5,y5)
e5
(x6,y6)
e4
e3
(x4,y4)
e6
(x3,y3)
e0
(x0,y0)
(x7,y7)
e7
General polygon
Edge
e0
e7
e6
e2
e3
e1
e4
e5
Edge data
mInv0, j00, x(j0)0, y10,
mInv7, j07, x(j0)7, y17,
Edge
a0
a1
Edge in global list
e0
e7
mInv6, j06, x(j0)6, y16,
mInv2, j02, x(j0)2, y12,
mInv4, j04, x(j0)4, y14,
mInv1, j01, x(j0)1, y11,
mInv3, j03, x(j0)3, y13,
mInv5, j05, x(j0)5, y15,
Sorted global edge list
Active edge list
for scan line j
An example
Process each scan line
Determine the x-intersections for each active edge using DDA
Set pixels in the spans between pairs of x-intersections using the fill rule
(even-odd parity rule or non-zero winding rule)
(x2,y2)
e1
e2
(x1,y1)
(x5,y5)
e5
(x6,y6)
e4
e3
(x4,y4)
e6
(x3,y3)
e0
(x0,y0)
(x7,y7)
e7
General polygon
Edge
e0
e7
e6
e2
e3
e1
e4
e5
Edge data
mInv0, j00, x(j0)0, y10,
mInv7, j07, x(j0)7, y17,
Edge
a0
a1
Edge in global list
e0
e7
mInv6, j06, x(j0)6, y16,
mInv2, j02, x(j0)2, y12,
mInv4, j04, x(j0)4, y14,
mInv1, j01, x(j0)1, y11,
mInv3, j03, x(j0)3, y13,
mInv5, j05, x(j0)5, y15,
Sorted global edge list
Active edge list
for scan line j
An example
Update the active edge list
Remove edges whose top vertex is on or below the next scan line
Add edges from the global edge list whose bottom vertex lies between this
scan line and the next scan line or on the next scan line
Re-sort the edges in the active edge list from left to right
(x2,y2)
e1
e2
(x1,y1)
(x5,y5)
e5
e4
e3
(x4,y4)
e6
(x3,y3)
e0
(x0,y0)
(x6,y6)
(x7,y7)
e7
General polygon
j+1
j
Edge
e0
e7
e6
e2
e3
e1
e4
e5
Edge data
mInv0, j00, x(j0)0, y10,
mInv7, j07, x(j0)7, y17,
Edge
a0
a1
Edge in global list
e0
e6
mInv6, j06, x(j0)6, y16,
mInv2, j02, x(j0)2, y12,
mInv4, j04, x(j0)4, y14,
mInv1, j01, x(j0)1, y11,
mInv3, j03, x(j0)3, y13,
mInv5, j05, x(j0)5, y15,
Sorted global edge list
Active edge list
for scan line j+1
An example
Update the active edge list
Remove edges whose top vertex is on or below the next scan line
Add edges from the global edge list whose bottom vertex lies between this
scan line and the next scan line or on the next scan line
Re-sort the edges in the active edge list from left to right
(x2,y2)
e1
e2
(x1,y1)
(x5,y5)
e5
e4
e3
(x4,y4)
e6
j+2
(x3,y3)
e0
(x0,y0)
(x6,y6)
(x7,y7)
e7
General polygon
j+1
Edge
e0
e7
e6
e2
e3
e1
e4
e5
Edge data
mInv0, j00, x(j0)0, y10,
mInv7, j07, x(j0)7, y17,
mInv6, j06, x(j0)6, y16,
mInv2, j02, x(j0)2, y12,
Edge
a0
a1
a2
a3
Edge in global list
e0
e2
e3
e6
mInv4, j04, x(j0)4, y14,
mInv1, j01, x(j0)1, y11,
mInv3, j03, x(j0)3, y13,
mInv5, j05, x(j0)5, y15,
Sorted global edge list
Active edge list
for scan line j+2
Horizontal edges
If a horizontal edge lies between scan lines
It does not intersect any scan line
If it lies on a scan line
The even odd parity and the winding number
will not change along the edge
The vertices of edges connected to the
horizontal edge will determine the parity and
the winding number
Horizontal edges can be safely ignored
Shared vertices
If the scan line intersects a shared vertex
The edge crossing could be counted more than once
Yields incorrect, inconsistent even-odd parity and winding numbers
P
P
Scan line pierces the outline
=> Should count one crossing
Scan line grazes the outline
=> Should count 0 or 2 crossings
Shared vertices
One approach:
Ensure that the scan line does not intersect a vertex
Preprocess: Add a small y-offset to a vertex if it falls on a scan line
P1
P0
Shared vertices
Another approach:
Use a convention to include/exclude vertices
Include the bottom vertex of each edge if it falls on a scan line
Do not include the top vertex of each edge if it falls on a scan line
Do not include the top vertex
Do not include the top vertex
Include the bottom vertex
Include the bottom vertex
Shared vertices
Another approach:
Use a convention to include/exclude vertices
Include the bottom vertex of each edge if it falls on a scan line
Do not include the top vertex of each edge if it falls on a scan line
Include the bottom
vertex of edge e1
e1
Do not include the
top vertex of edge e0
e0
Counts 1 crossing when the scan line pierces
the polygon at a shared vertex.
Shared vertices
Another approach:
Use a convention to include/exclude vertices
Include the bottom vertex of each edge if it falls on a scan line
Do not include the top vertex of each edge if it falls on a scan line
Do not include the
top vertex of edge e2
e2
Do not include the top
vertex of edge e3
e3
Counts 0 crossings when the scan line grazes
the polygon at a shared top vertex.
Shared vertices
Another approach:
Use a convention to include/exclude vertices
Include the bottom vertex of each edge if it falls on a scan line
Do not include the top vertex of each edge if it falls on a scan line
e0
Include the bottom
vertex of edge e0
e4
Include the bottom
vertex of edge e4
Counts 2 crossings when the scan line grazes
the polygon at a shared bottom vertex.
Sliver polygons
So thin that some scan lines have only one pixel or no pixels
No simple solution
Avoid long thin triangles
Want triangles with a good aspect ratio
Example of an aliasing problem
(more on these next week)
Implementing edge lists
Recall the basic algorithm:
1. Create a global edge list.
2. Create an active edge list.
3. Process each scan line.
a. Determine x-intersections of active edges in left to right order.
b. Fill spans between appropriate x-intersections using a fill rule.
c. Update active edge list.
What information is required?
To create the global edge list:
Vertices ordered from bottom to top (ignore horizontal edges)
Data required to compute intersections between edges and scan lines
Data for the fill rule
(4,5.5)
e2
(0,4.5)
e1
e3
e0
(2,2)
(0,0.5)
e4
(4,0.5)
Edge
(x0, y0)( x1, y1)
e0
(0, 0.5)
(0, 4.5)
e1
(2, 2)
(0, 4.5)
e2
(2, 2)
(0, 5.5)
e3
(4, 0.5)
(4, 5.5)
e4
Vertices are listed bottom to top
What information is required?
To create the active edge list:
Which edges are active for a given scan line
How to update the active edge list for the next scan line
(4,5.5)
e0
e2
(0,4.5)
e1
e1
e2
e3
e0
(2,2)
(0,0.5)
Active Edges
e4
(4,0.5)
e3
What information is required?
To determine x-intersections for current scan line:
Data for determining the x-intersection for each scan line
e.g., if using DDA, need previous x-intersection and dx/dy
(4,5.5)
e2
(0,4.5)
e1
j
e0
j-1
+
(0,0.5)
+
+(2,2)
e4
+e3
+
(4,0.5)
Previous x
dx/dy
e0
e1
-2/2.5
e2
2/3.5
e3
What information is required?
To fill spans between x-intersections:
X-intersections for each active edge, ordered left to right
Even-odd parity bit or winding number
Edge direction if using non-zero winding rule
(i.e., the winding number increment, +1 or -1)
What information is required?
To update the active edge list:
Test to determine when to remove an edge
Compare next scan line with max height of each edge
For a closed polygon, always add a new edge when an old edge is
removed (until the last edge has been processed)
New edges should be initialized in the pre-processing step so that it
doesnt have to be done here
Data for updating x-intersections of each active edge
Data structures
EdgeData: For each edge,
j0 = bottom-most scan line
intersected by the edge
j1 = top-most scan line intersected
by the edge
x = the value of the x-intersection
with the current scan line, initialized
to x(j0)
dx = the change in the value of the
x-intersection for the next scan line
dir = the direction of the edge (1 if
the original edge is upward, -1 if the
original edge is downward)
j1
j0
x = x(j0)
dx
Data structures
EdgeData: For each edge,
j0 = bottom-most scan line
intersected by the edge
j1 = top-most scan line intersected
by the edge
x = the value of the x-intersection
with the current scan line, initialized
to x(j0)
dx = the change in the value of the
x-intersection for the next scan line
dir = the direction of the edge (1 if
the original edge is upward, -1 if the
original edge is downward)
j1
j0
x = x(j0)
dx
Compute the line data
if (y0 is an integer) j0 = y0
else j0 = (int) y0 + 1
if (y1 is an integer) j1 = y1 1
else j1 = (int) y1
dx = (x1 x0) / (y1 y0)
x = x0 + dx * (j0 y0)
dir = 1
Data structures
typedef struct {
int j0;
//Bottom-most scan line intersecting edge
int j1;
//Top-most scan line intersecting edge
float x;
//x-intersection with current scan line
float dx; //Displacement of x-intersect for next scan line
float dir; //1 if edge is upward, -1 if edge is downward
} EdgeData;
Global edge list
Allocate an array big enough to hold all the edge data
EdgeData *global = (edgeData *) malloc(nEdges * sizeof(EdgeData));
(4.5,5.5)
j=5
j=4
Edge
e2
(0,4.5)
e0
e1
j=3
e3
e0
j=2
(2,2.00001)
e1
e2
e3
j=1
j=0
Data (j0, j1, x, dx, dir)
e4
(0,0.5)
e4
(4.5,0.5)
Global edge list
Global edge list
Compute the data for each edge and insert it in the global edge list
(4.5,5.5)
j=5
j=4
Edge
e2
(0,4.5)
e1
j=3
e3
e0
j=2
(2,2.00001)
j=1
j=0
(0,0.5)
e4
Data (j0, j1, x, dx, dir)
e0
1, 4, 0, 0, 1
e1
3, 4, 1.2, -0.8, -1
e2
3, 5, 2.71, 0.71, 1
e3
1, 5, 4.5, 0, -1
e4
1, 0, 0, 0, 0
(4.5,0.5)
Global edge list
Global edge list
Compute the data for each edge and insert it in the global edge list
Note that we can ignore horizontal edges (j1 = j0)
(4.5,5.5)
j=5
j=4
Edge
e2
(0,4.5)
e1
j=3
e3
e0
j=2
(2,2.00001)
j=1
j=0
(0,0.5)
e4
Data (j0, j1, x, dx, dir)
e0
1, 4, 0, 0, 1
e1
3, 4, 1.2, -0.8, -1
e2
3, 5, 2.71, 0.71, 1
e3
1, 5, 4.5, 0, -1
e4
1, 0, 0, 0, 0
(4.5,0.5)
Global edge list
Global edge list
Order the edges in the global edge list bottom-to-top, left-to-right
Use a standard sorting method, e.g., insertion sort
(4.5,5.5)
j=5
j=4
Edge
e2
(0,4.5)
e1
j=3
e3
e0
j=2
(2,2.00001)
Data (j0, j1, x, dx, dir)
e0
1, 4, 0, 0, 1
e1
3, 4, 1.2, -0.8, -1
e2
3, 5, 2.71, 0.71, 1
e3
1, 5, 4.5, 0, -1
j=1
j=0
(0,0.5)
e4
(4.5,0.5)
Global edge list
Sorting the global edge list
Start at the head of the list
Search remaining elements in the list for smallest j0 (if two edges have
equal j0, choose the one with the smallest x-intersection)
Swap the current edge with the one with the smallest j0
Start at the next edge in the list, search the remaining elements and
swap, continuing until the last edge of the list is reached
Edge
Data (j0, j1, x, dx, dir)
e0
1, 4, 0, 0, 1
e1
3, 4, 1.2, -0.8, -1
e2
3, 5, 2.71, 0.71, 1
e3
1, 5, 4.5, 0, -1
Global edge list
Sorting the global edge list
Start at the head of the list
Search remaining elements in the list for smallest j0 (if two edges have
equal j0, choose the one with the smallest x-intersection)
Swap the current edge with the one with the smallest j0
Start at the next edge in the list, search the remaining elements and
swap, continuing until the last edge of the list is reached
Edge
e0 is the lowest, leftmost edge:
no swap is needed
Data (j0, j1, x, dx, dir)
e0
1, 4, 0, 0, 1
e1
3, 4, 1.2, -0.8, -1
e2
3, 5, 2.71, 0.71, 1
e3
1, 5, 4.5, 0, -1
Global edge list
Sorting the global edge list
Start at the head of the list
Search remaining elements in the list for smallest j0 (if two edges have
equal j0, choose the one with the smallest x-intersection)
Swap the current edge with the one with the smallest j0
Start at the next edge in the list, search the remaining elements and
swap, continuing until the last edge of the list is reached
Edge
e3 is the next lowest, leftmost edge:
swap with current edge
Data (j0, j1, x, dx, dir)
e0
1, 4, 0, 0, 1
e1
3, 4, 1.2, -0.8, -1
e2
3, 5, 2.71, 0.71, 1
e3
1, 5, 4.5, 0, -1
Global edge list
Sorting the global edge list
Start at the head of the list
Search remaining elements in the list for smallest j0 (if two edges have
equal j0, choose the one with the smallest x-intersection)
Swap the current edge with the one with the smallest j0
Start at the next edge in the list, search the remaining elements and
swap, continuing until the last edge of the list is reached
Edge
e3 is the next lowest, leftmost edge:
swap with current edge
Data (j0, j1, x, dx, dir)
e0
1, 4, 0, 0, 1
e3
1, 5, 4.5, 0, -1
e2
3, 5, 2.71, 0.71, 1
e1
3, 4, 1.2, -0.8, -1
Global edge list
Sorting the global edge list
Start at the head of the list
Search remaining elements in the list for smallest j0 (if two edges have
equal j0, choose the one with the smallest x-intersection)
Swap the current edge with the one with the smallest j0
Start at the next edge in the list, search the remaining elements and
swap, continuing until the last edge of the list is reached
Edge
e1 is the next lowest, leftmost edge:
swap with current edge
Data (j0, j1, x, dx, dir)
e0
1, 4, 0, 0, 1
e3
1, 5, 4.5, 0, -1
e2
3, 5, 2.71, 0.71, 1
e1
3, 4, 1.2, -0.8, -1
Global edge list
Sorting the global edge list
Start at the head of the list
Search remaining elements in the list for smallest j0 (if two edges have
equal j0, choose the one with the smallest x-intersection)
Swap the current edge with the one with the smallest j0
Start at the next edge in the list, search the remaining elements and
swap, continuing until the last edge of the list is reached
Edge
e1 is the next lowest, leftmost edge:
swap with current edge
Data (j0, j1, x, dx, dir)
e0
1, 4, 0, 0, 1
e3
1, 5, 4.5, 0, -1
e1
3, 4, 1.2, -0.8, -1
e2
3, 5, 2.71, 0.71, 1
Global edge list
Sorting the global edge list
Start at the head of the list
Search remaining elements in the list for smallest j0 (if two edges have
equal j0, choose the one with the smallest x-intersection)
Swap the current edge with the one with the smallest j0
Start at the next edge in the list, search the remaining elements and
swap, continuing until the last edge of the list is reached
Edge
Last edge: sort is complete
Data (j0, j1, x, dx, dir)
e0
1, 4, 0, 0, 1
e3
1, 5, 4.5, 0, -1
e1
3, 4, 1.2, -0.8, -1
e2
3, 5, 2.71, 0.71, 1
Global edge list
Global edge list
Now have a sorted global edge list
(4.5,5.5)
j=5
j=4
Edge
e2
(0,4.5)
e1
j=3
e3
e0
j=2
(2,2.00001)
Data (j0, j1, x, dx, dir)
e0
1, 4, 0, 0, 1
e3
1, 5, 4.5, 0, -1
e1
3, 4, 1.2, -0.8, -1
e2
3, 5, 2.71, 0.71, 1
j=1
j=0
(0,0.5)
e4
(4.5,0.5)
Global edge list
Active edge list
Keeps track of which edges in the global edge list are intersected
by the current scan line
Use to fill spans between x-intersections in the current scan line
Must update the active list with each new scan line
Active edge list
There are several ways to implement it
Could use linked lists:
Keep a linked list of edge indices
Each element in the linked list contains an index to the corresponding edge
in the global edge array and pointer to the next and previous active edges
To update the active edge list, update the pointers
typedef struct {
int edgeIdx;
_ActiveEdge *prev;
_ActiveEdge *next;
} ActiveEdge;
// Edge index in the global edge array
// Pointer to previous active edge
// Pointer to next active edge
Active edge list
There are several ways to implement it
Could use an active edge array
int nActive;
//# active edges
int *active = (int) malloc (nEdges * sizeof(int)); //Edge indices
Initialize the active list with indices of edges that intersect the first scan line
Update the active list with each new scan line
Remove edges if j1 is below the new scan line
Update x for each edge remaining in the active edge list
Add edges whose j0 falls between the previous and the new scan line
Sort edges in the active edge list from left to right (e.g., insertion sort)
Exercise
A. Fill in the active edge table with
the ordered active edges at each
scan line
B. Use non-zero winding to determine
which ranges of x values are
inside the polygon
Edge
Data (j0, j1, x, dx, dir)
e0
1, 4, 0, 0, 1
e3
1, 5, 4.5, 0, -1
e1
3, 4, 1.2, -0.8, -1
e2
3, 5, 2.71, 0.71, 1
Global edge list
(4.5,5.5)
j=5
e2
(0,4.5)
j=4
Scan line
e1
j=1
j=3
e3
e0
j=2
0, 3
2
3
(2,2.00001)
j=1
j=0
Edge index
(0,0.5)
e4
(4.5,0.5)
Active edge list
Summary
Raster-based filling of polygons
X-intersection array algorithm
Improve efficiency with DDA
Edge list algorithm
Special considerations: horizontal edges, shared vertices, slivers
Implementation with active edge array
Both approaches find limits of interior spans, fill pixels between the limits
74
Next time
Coloring and texturing polygons
Third polygon filling approach: Pinedas algorithm
Uses coherence of square tiles rather than rows of pixels
Computes color/texture interpolation
75
