4.Scan

Scan conversion

Problem

How to generate filled polygons (by determining which pixel positions are inside the polygon)

Concepts

Spatial coherence
Span coherence
Edge coherence

Scan - conversion of rectangles

For ( y from y₀ to y_n )
   For ( x from x₀ to x_n )
      Write Pixel (x, y, val)

Scan - conversion of rectangles

For ( y from y₀ to y_n )
   For ( x from x₀ to x_n )
      Write Pixel (x, y, val)

Scan - conversion of rectangles

For ( y from y₀ to y_n )
   For ( x from x₀ to x_n )
      Write Pixel (x, y, val)

Scan - convert arbitrary polygon

vertices: (4, 1) , (7, 13) , (11 , 2)

Scan - convert arbitrary polygon

vertices: (4, 1) , (7, 13) , (11 , 2)

    Intersect scanline w/pgon edges => span extrema

Scan - convert arbitrary polygon

vertices: (4, 1) , (7, 13) , (11 , 2)

    Intersect scanline w/pgon edges => span extrema
    Fill between pairs of span extrema

Scan - convert arbitrary polygon

vertices: (4, 1) , (7, 13) , (11 , 2)

For each nonempty scanline
    Intersect scanline w/pgon edges => span extrema
    Fill between pairs of span extrema

Scan - convert arbitrary polygon

vertices: (4, 1) , (7, 13) , (11 , 2)

For each nonempty scanline
    Intersect scanline w/pgon edges => span extrema
    Fill between pairs of span extrema

Scan-Conversion: scanlines with vertices

4 intersections w/ scanline 6
at x = 1, 6, 6, 12 1/7

Scan-Conversion: scanlines with vertices

4 intersections w/ scanline 6
at x = 1, 6, 6, 12 1/7
=>
Local extrema work as is
(counted twice)

Scan-Conversion: scanlines with vertices

3 intersections w/scanline 5
at x = 1, 1, 11 5/7

Scan-Conversion: scanlines with vertices

3 intersections w/scanline 5
at x = 1, 1, 11 5/7
==>
Count continuing edges once
(shorten lower edge)
now x=1, 11 5/7

Scan-Conversion: scanlines with vertices

4 intersections w/ scanline 1
at x = 5, 5, 10, 10

Scan-Conversion: scanlines with vertices

4 intersections w/ scanline 1
at x = 5, 5, 10, 10
=>
Don't count vertices of horizontal edges.
Now x = 5, 10

Scan-line Rasterization Algorithm

1.	Bucket sort edges into sorted edge table
2.	Initialize y & active edge table y = first non- empty scanline AET = SET [y]
3,	Repeat until AET and SET are empty Fill pixels between pairs of x intercepts in AET Remove exhausted edges Y++ Update x intercepts Resort table (AET) Add entering edges

Sorted edge table:

all edges sorted by min y
holds:

max y
init x
inverse slope

Active edge table:

edges intersecting current scanline
holds:

max y
current x
inverse slope

Scan - conversion

Scanlines with vertices (4,1), (1,11), (9,5), (12,8), (12,1)

Scan - conversion

Scanlines with vertices (4,1), (1,11), (9,5), (12,8), (12,1)

bucket sort edges into sorted edge table

sort on minY: 1
store:

max Y: 11
min X: 4
1/m : (Xmax - Xmin) / (Ymax - Ymin) = (1 - 4) / (11 - 1) = -3 / 10

Scan - conversion

Scanlines with vertices (4,1), (1,11), (9,5), (12,8), (12,1)

bucket sort edges into sorted edge table
initialize active edge list to first non empty scanline

Scan - conversion

Scanlines with vertices (4,1), (1,11), (9,5), (12,8), (12,1)

bucket sort edges into sorted edge table
initialize active edge list to first non empty scanline
for each non empty scanline

Scan - conversion

Scanlines with vertices (4,1), (1,11), (9,5), (12,8), (12,1)

bucket sort edges into sorted edge table
initialize active edge list to first non empty scanline
for each non empty scanline
   fill between pairs (x=4,12)

Scan - conversion

Scanlines with vertices (4,1), (1,11), (9,5), (12,8), (12,1)

bucket sort edges into sorted edge table
initialize active edge list to first non empty scanline
for each non empty scanline
   fill between pairs (x=4,12)
   remove exhausted edges
   update intersection points
   resort table
   add entering edges

Scan - conversion

Scanlines with vertices (4,1), (1,11), (9,5), (12,8), (12,1)

bucket sort edges into sorted edge table
initialize active edge list to first non empty scanline
for each non empty scanline
   fill between pairs (x=3 1/10,12)
   remove exhausted edges
   update intersection points

Scan - conversion

Scanlines with vertices (4,1), (1,11), (9,5), (12,8), (12,1)

bucket sort edges into sorted edge table
initialize active edge list to first non empty scanline
for each non empty scanline
   fill between pairs (x=3 1/10,12)
   remove exhausted edges
   update intersection points
   resort table
   add entering edges

Scan - conversion

Scanlines with vertices (4,1), (1,11), (9,5), (12,8), (12,1)

bucket sort edges into sorted edge table
initialize active edge list to first non empty scanline
for each non empty scanline
   fill between pairs (x=3 1/10,12)
   remove exhausted edges
   update intersection points
   resort table
   add entering edges

Scan - conversion

Scanlines with vertices (4,1), (1,11), (9,5), (12,8), (12,1)

bucket sort edges into sorted edge table
initialize active edge list to first non empty scanline
for each non empty scanline
   fill between pairs (x=3 1/10,12)
   remove exhausted edges
   update intersection points
   resort table
   add entering edges

Scan-conversion: efficiency improvements

1. exploit coherence

   x(k + 1) = x(k) + 1/m

Triangle with verts:
(1,1) (5,14), (11,8)

	X-intercepts	Fill X
y=1	1, 1	1

Scan-conversion: efficiency improvements

1. exploit coherence

   x(k + 1) = x(k) + 1/m

Triangle with verts:
(1,1) (5,14), (11,8)

	X-intercepts	Fill X
y=1	1, 1	1
y=2	1+ 4/13, 1+10/7 = 1 4/13, 2 3/7	2

Scan-conversion: efficiency improvements

1. exploit coherence

   x(k + 1) = x(k) + 1/m

Triangle with verts:
(1,1) (5,14), (11,8)

	X-intercepts	Fill X
y=1	1, 1	1
y=2	1+ 4/13, 1+10/7 = 1 4/13, 2 3/7	2
y=3	1 4/13 + 4/13, 2 3/7 + 10/7 = 1 8/13, 3 6/7	2, 3

Scan-conversion: efficiency improvements

1. exploit coherence

   x(k + 1) = x(k) + 1/m

Triangle with verts:
(1,1) (5,14), (11,8)

	X-intercepts	Fill X
y=1	1, 1	1
y=2	1+ 4/13, 1+10/7 = 1 4/13, 2 3/7	2
y=3	1 4/13 + 4/13, 2 3/7 + 10/7 = 1 8/13, 3 6/7	2, 3
y=4	1 12/13, 5 2/7	2, 3, 4, 5

Scan-conversion: efficiency improvements

1. exploit coherence

   x(k + 1) = x(k) + 1/m

Triangle with verts:
(1,1) (5,14), (11,8)

	X-intercepts	Fill X
y=1	1, 1	1
y=2	1+ 4/13, 1+10/7 = 1 4/13, 2 3/7	2
y=3	1 4/13 + 4/13, 2 3/7 + 10/7 = 1 8/13, 3 6/7	2, 3
y=4	1 12/13, 5 2/7	2, 3, 4, 5
y=5	2 3/13, 6 5/7	3, 4, 5, 6

Scan-conversion: efficiency improvements

1. exploit coherence

   x(k + 1) = x(k) + 1/m

2. integer calculations

Triangle with verts:
(1,1) (5,14), (11,8)

	X-intercepts	Fill X
y=1	1, 1	1
y=2	1+ 4/13, 1+10/7 = 1 4/13, 2 3/7	2
y=3	1 4/13 + 4/13, 2 3/7 + 10/7 = 1 8/13, 3 6/7	2, 3
y=4	1 12/13, 5 2/7	2, 3, 4, 5
y=5	2 3/13, 6 5/7	3, 4, 5, 6

X - intercepts	Counters
1,1	13,7

Scan-conversion: efficiency improvements

1. exploit coherence

   x(k + 1) = x(k) + 1/m

2. integer calculations

Triangle with verts:
(1,1) (5,14), (11,8)

	X-intercepts	Fill X
y=1	1, 1	1
y=2	1+ 4/13, 1+10/7 = 1 4/13, 2 3/7	2
y=3	1 4/13 + 4/13, 2 3/7 + 10/7 = 1 8/13, 3 6/7	2, 3
y=4	1 12/13, 5 2/7	2, 3, 4, 5
y=5	2 3/13, 6 5/7	3, 4, 5, 6

X - intercepts	Counters
1,1	13,7
2,2	17,17

Scan-conversion: efficiency improvements

1. exploit coherence

   x(k + 1) = x(k) + 1/m

2. integer calculations

Triangle with verts:
(1,1) (5,14), (11,8)

	X-intercepts	Fill X
y=1	1, 1	1
y=2	1+ 4/13, 1+10/7 = 1 4/13, 2 3/7	2
y=3	1 4/13 + 4/13, 2 3/7 + 10/7 = 1 8/13, 3 6/7	2, 3
y=4	1 12/13, 5 2/7	2, 3, 4, 5
y=5	2 3/13, 6 5/7	3, 4, 5, 6

X - intercepts	Counters
1,1	13,7
2,2	4,3
2,3	8,13

Scan-conversion: efficiency improvements

1. exploit coherence

   x(k + 1) = x(k) + 1/m

2. integer calculations

Triangle with verts:
(1,1) (5,14), (11,8)

	X-intercepts	Fill X
y=1	1, 1	1
y=2	1+ 4/13, 1+10/7 = 1 4/13, 2 3/7	2
y=3	1 4/13 + 4/13, 2 3/7 + 10/7 = 1 8/13, 3 6/7	2, 3
y=4	1 12/13, 5 2/7	2, 3, 4, 5
y=5	2 3/13, 6 5/7	3, 4, 5, 6

X - intercepts	Counters
1,1	13,7
2,2	4,3
2,3	8,6
2,5	12,16

Fill variants

Fill between pairs:

    for ( x = x1; x < x2; x++ )
	framebuffer [ x, y ] = c

Fill variants : Patterned fill

Fill between pairs:

    for ( x = x1; x < x2; x++ )
       if ( ( x + y ) % 2 )
          framebuffer [ x, y ] = c1
       else
          framebuffer [ x, y ] = c1

Fill variants : Color Wash

From red to blue

Fill between pairs:

    for ( x = x1; x < x2; x++ )
       framebuffer [ x, y ] = C0 + dC * ( x1 - x )

For efficiency carry C and dC in AET
and calculate color incrementally

Fill variants : Vertex Colors

Red, Green and Blue

Interpolate colors along edges
then interpolate across scanlines

Fill between pairs:

    for ( x = x1; x < x2; x++ )
       framebuffer [ x, y ] = Cy1x1 + 
         [(x - x1) / (x2 - x1) * (Cy1x2 - Cy1x1)]
                      dCx

For efficiency carry Cy and dCy in AET
calculate dCx at beginning of scanline

Made by dynaPage 0.2