POLYFILL -
SCAN CONVERSION
of a POLYGON
Pixels are not at the center of the grid,
but at the intersection of two orthogonal
scan lines
sca es (o
(on the
eggrid
d intersection
e sec o popoints).
s)
SCAN CONVERSION - POLYFILL
SCANLINE POLYFILL ALGORITHM
Steps (conceptual):
• Find minimum enclosed rectangle
• No.
No of scanlines = Ymax – Ymin + 1
• For each scanline do
• Obtain intersection points of scanline
with polygon edges.
• Sort intersections from left to right
• Form pairs of intersections from the list§
• Fill within pairs
• Intersection points are updated for each
sca
scanline
e
• Stop
p when scanline has reached Ymax
§ - Intersections at vertices require
special handling
Check if a point is
within a Polygon?
Look left or right,
right and
count the number of
intersection points of the
scanline with the edges of
the Polygon.
If the number is ODD,
point is Inside
p
else Outside
Two different cases of
scanlines passing through
the vertex of a polygon
Case - I
Add one more
i t
intersection:
ti
3 ->
>4
Case - II
Add one more
intersection:
5 -> 6;
Do nott add
D dd
intersection,
keep 4;
HOW ??
What is the difference between the intersection
of the scanlines Y and Y’, with the vertices?
Y
Y’
For Y,, the edges
g at the vertex are on the
same side of the scanline.
Whereas for Y’
Y’, the edges are on
either/both sides of the vertex.
In this case, we require additional processing.
Vertex counting
g in a scanline
Y
Y’
• Traverse along the polygon boundary
clockwise (or counter- clockwise) and
• Ob
Observe th relative
the l ti change
h in
i Y-value
Y l off
the edges on either side of the vertex (i.e. as
we move from one edge to another).
another)
Vertex counting
in a scanline Y
Y’
Check the condition:
If end-point Y values of two consecutive
edges monotonically increase or decrease,
count the middle vertex as a single intersection
point for the scanline passing through it.
Else the shared vertex represents a local
maximum (or minimum) on the polygon
b
boundary.
d I
Increment t the
th intersection
i t ti count.
t
If the vertex is a local extrema, consider
(or add) two intersections for the scan line
corresponding to such a shared vertex.
Must avoid this
to happen in cases,
such as:
To implement the above:
While processing non-horizontal edges
(generally) along a polygon boundary in any
order, check to determine the condition of
monotonically changing (increasing or
decreasing) endpoint Y values.
If so:
Before
Before After
processing After
processing processing
processing
To implement the above:
Shorten the lower edge to ensure only one
intersection point at the vertex.
vertex
Before
f
processing Before After
After
processing
i
processing processing
Scanline PolyFill Algorithm
(revisited, in brief)
Intersect scanline with polygon edges
edges.
Fill between pairs of intersections
Basic Structure:
For y = Ymin to Ymax
1) intersect scanline with each edge
2) sort intersections by increasing X
3) fill pairwise (int0 -> int1, int2 -> int3, ...)
4) Update intersections for next scanline
This is the basic structure,, but we are
going to handle some special cases to make
sure it works correctlyy and fast.
Two important
p features of scanline-based
polygon filling are:
• scanline coherence - values don't change
much from one scanline to the next - the
coverage (or visibility) of a face on one
scanline typically differs little from the
previous one.
• edge
d coherence
h - edges
d iintersected
dbby
scanline “i” are typically intersected by
scanline
li “i+1”.
“i+1”
(Xk+1, Yk+1)
(
(Yk+1 = Yk + 1)
L
(Yk) Slope of the line L
(Xk, Yk)
( (polygon edge) is:
Yk +1 − Yk
If, Yk+1 = Yk + 1; m=
X k +1 − X k
Then, Xk+1 = Xk + 1/m
Thus the intersection for the next scanline
is obtained as:
Xk+1
k = round (Xk + 1/m)
1/m), where m = ΔY/ΔX.
ΔY/ΔX
How to implement this using integer arithmetic ?
Take an example: m = ΔY/ΔX = 7/3.
7/3
Set Counter, C=0
and counter-increment, ΔC = ΔX = 3;
For the next three scan lines,
successive values of C are : 3,
3 6,
6 9.
9
Thus only at 3rd scanline C >= ΔY.
ΔY
Then, Xk is incremented by 1 only at 3rd
Then
scanline and set as: C C – ΔY = 9 – 7 = 2.
Repeat the above step(s) till Yk reaches Ymax .
After 2 more scanlines: 2 + 3 + 3 = 8; 8 – 7 = 1;
After 2 more scanlines: 1 + 3 + 3 = 7;
Data Structure Used (typical example):
SET (Sorted Edge table):
Contains all information necessary to
process the
h scanlines
li efficiently.
ffi i l
SET is
i typically
t i ll built
b ilt using
i a bucket
b k t sort,
t
with a many buckets as there are scan lines.
All edges are sorted by their Ymin
coordinate with a separate Y bucket for each
coordinate,
scanline.
Within each bucket, edges sorted by
increasing X of Ymin point.
point
Only non-horizontal edges are stored. Store
these edges at the scanline position in the SET.
Edge
g structure
(sample record for each scanline):
(Ymax, Xmin, ΔX/ΔY, pointer to next edge)
AEL (Active edge List):
Contains all edges crossed by a scanline
at the current stage of iteration.
This is a list of edges that are active for
this scanline, sorted by increasing X
intersections.
Also called: Active Edge Table (AET).
D
11
F
9
7 E
C
5
A
3
1
2 4 6 8 10 12
B
Bucket-sorted Edge
g Table
11 λ for Polygon
10 λ
9 λ
EF DE
8 λ −5 6
7 9 7 2 11 7
4 λ
6 λ CD
5
4 λ 11 13 0 λ FA
3 9 2 0 λ
2 λ AB BC
1 −5 6
0 λ
3 7 2 5 7 4 λ
1
ymax xmin m
AB BC
AB: 1 −5 6
m = ΔY/ΔX = - (2/5).
3 7 2 5 7 4 λ
Set Counter
Counter, C=0; and
counter-increment, ΔC = min (
(ΔX, ΔY)
)=2(
(= ΔY);
)
Update for AB (-ve m), when YK = 2; Y = 1:
For the next three left (-ve) vertical (Y) scan lines,
successive values of C are : 2, 4, 6; X = 7 - 3 = 4;
Thus only
y at 3rd iteration: C >= ΔX.
Then, Y is incremented byy 1 only
y at 3rd scanline
and set: C C – ΔX = 6 – 5 = 1; Y = 1 + 1 = 2;
Stop as Y = YK. 2 −5
3 4 2
AB
AB BC
BC: 1 −5 6
m = ΔY/ΔX = (4/6).
3 7 2 5 7 4 λ
Set Counter , C=0; and
counter-increment, ΔC = min (
(ΔX, ΔY)
)=4(
(= ΔY);
)
Update for BC (+ve m), when YK = 2; Y = 1:
For the next two right vertical (Y) scan lines,
successive values of C are : 4, 8; X = 7 + 2 = 9;
Thus only at 2nd iteration: C >= ΔX.
Then,, Y is incremented by
y 1 onlyy at 2nd scanline
and set : C C – ΔX = 8 – 6 = 2; Y = 1 + 1 = 2;
Stop
p as Y = YK.
BC 6
5 9 4
2
AB BC
−5 6
3 4 2 5 9 4 λ
2
AB BC
AB:
−5 6
m = ΔY/ΔX = - (2/5).
3 4 2 5 9 4 λ
Counter (from earlier iteration),
iteration) C = 1 ; and
counter-increment, ΔC = min (
(ΔX, ΔY)
)=2(
(= ΔY);
)
Update for AB (-ve m), when YK = 3; Y = 2:
For the next two left (
(-ve)
ve) vertical (Y) scan lines,
successive values
Do youof C are
need all: this
3, 5;??X = 4 - 2 = 2;
Thus only at 2nd iteration: C >= ΔX.
Then, Y is incremented by 1 only at 2nd scanline
and set: C C – ΔX = 5 – 5 = 0; Y = 2 + 1 = 3;
Stop as Y = YK. 3 −5
3 2 2
AB: To go out of AEL, after use, as Ymax = YK.
AB BC
BC: 2 −5 6
m = ΔY/ΔX = (4/6).
3 4 2 5 9 4 λ
Counter (from earlier iteration) , C = 2 ; and
counter-increment, ΔC = min (
(ΔX, ΔY)
)=4(
(= ΔY);
)
Update for BC (+ve m), when YK = 3; Y = 2:
For the next right vertical (Y) scan line, the
successive value of C is : 6; X = 9 + 1 = 10;
Thus only at 1st iteration: C >= ΔX.
Then,, Y is incremented byy 1 only
y at 1st scanline
and set : C C – ΔX = 6 – 6 = 0; Y = 2 + 1 = 3;
Stop as Y = YK = ??. BC −6
5 10 4
3
AB BC
−5 6
3 2 2 5 10 4 λ << - Is this OK ??
After post-processing (update from SET) at 3rd scanline:
3
FA BC
6
9 2 0 5 10 4 λ
Home task:
Complete the next two sets of iterations
lf till you gett :
yourself,
5
FA BC
6
9 2 0 5 ** 4 λ
** = 10 + 3 = 13, why ??
After post-processing
post processing (update from SET) at 5th scanline:
5
FA CD
9 2 0 11 13 0 λ
D
11
F
9
7 E
C
5
A
3
1
2 4 6 8 10 12
B
Status of AET at Scanline 8
AET
Pointer FA EF
9 2 0 9 4
−5
2
ymax x 1
m
DE CD
6
11 9 4 11 13 0 λ
AET Status of AET at Scanline 9
Pointer FA EF
9 2 0 9 2
−5
2
ymax x 1
m
DE CD
6
11 10 4 11 13 0 λ
AET Status off AET at Scanline
li 10
Pointer DE CD
6
11 11
4 11 13 0 λ
Precautions:
Intersection has an integer Y coordinate
If thi
this point
i t is
i the
th Ymin off th
the edge's
d '
endpoints, count it.
If the edge is horizontal and on the
scanline, don't count it.
During iteration process with each
scanline,, the AET is updated.
p
For each scanline the AET keeps p track of
the set of edges it has to intersect and stores
the intersection points in it. The sorting of the
entries is w.r.t the X-intersection values.
Have a re-look at it.
Processing Steps:
• Sett Y to
S t smallest
ll t Y in
i SET entry
t (first
(fi t non-
empty bucket)
• Initialize AET to be empty
• Repeat until both AET and SET are empty
(i) Move from SET bucket Y to AET,
AET those
edges whose Ymin = Y.
(ii) Sort AET on X (simple, as SET is
pre-sorted
pre sorted anyway).
(iii) Fill pixels in scanline Y using pairs of X-
coordns. from AET.
(iv) Increment scanline by 1.
( ) Remove from
(v) f AET those
h entries
i ffor which
hi h
Y = Ymax (edges not involved).
(vi) For each non-vertical edge in AET, update
X for new Y
Y.
END LOOP
END-LOOP
The algorithm:
g
scan-fill(polygon)
Construct the Edge table (ET)
Ymin = min (all Y in the ET)
AET = null
ll
f
for Y = Ymin to
t Ymax
Me ge so t ET[Y] into AET by
Merge-sort b X value
al e
Fill between pairs of X in AET
AET.
for each edge in AET
if edge
edge.Y
Ymax = Y
remove edge
g from AET
else
edge.X = edge.X + dx/dy
endif
sort AET by X value
end scan_fill
HORIZONTAL EDGES
F E
B C
What
at about vertex
e te pprocessing
ocess g oon bot
both s
sides
des o
of a horizontal
o o ta edge ?
Problem with HORIZONTAL EDGES
G F
I
H
E
B C
Wh d
What do you d
do to fill till
ill vertex D – odd
dd number
b off iintersections
i
Problem with HORIZONTAL EDGES
Problem with
adjacent polygons: G F
(the LOC problem )
I H
E
B C
Think of the background surrounding polygon,
producing the same problem at the edges.
Problem with HORIZONTAL EDGES
Problem with
adjacent polygons:
(the LOC problem ) G F
I
H
E
Adjust finishing
B C
Problem with HORIZONTAL EDGES
Problem with
adjacent polygons:
(the LOC problem ) G F
I
H
E
B C
End of Lectures on
POLYFILL -
SCAN CONVERSION
of a POLYGON
