Problem: ScanLine Filling Algorithm

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Hi,
I am trying to fill a polygon using scanLine filling algorithm. At scanline 4, it is not filling correctly. The polygon is attached in the image file. My work is given below:
All Edge Table
0 (1,1)
1 (5,1)
2 (5, 3)
3 (8, 3)
4 (8, 8)
5 (4, 8)
6 (4, 4)
7 (1, 4)
Global Edge Table
Index Ymin Ymax Xval 1/m
0 1 1 1 infinity
1 1 3 5 0
2 3 3 5 infinity
3 3 8 8 0
4 8 8 4 infinity
5 4 8 4 0
6 4 4 1 infinity
7 1 4 1 0
Global Edge Table
Index Ymin Ymax Xval 1/m
0 1 3 5 0
1 3 8 8 0 (X)
2 4 8 4 0 (X)
3 1 4 1 0
ScanLine=1, choose all edges where Ymin=1
Active Edge Table

Index Ymax Xval 1/m
0 3 5 0
1 4 1 0
Reordering (Xvalues are not sorted):
Index Ymax Xval 1/m
0 4 1 0
1 3 5 0
Filling:
Scanline =1, At x=1, Parity is odd so fill all points from x=1 to x=5. Parity becomes odd so stop filling.
(The web document says until x=5 which is also wrong)
Update the x-values. No change.
Index Ymax Xval 1/m
0 4 1 0
1 3 5 0
ScanLine=2, At x=1, Parity is odd so fill all points from x=1 to x=5. Parity becomes odd so stop filling.
(As discussed earlier, the web document says until x=5 which is also wrong).
Since Ymax for edge indexed 1 is 3 which is the next scanLine, we would remove this edge from Active Edge Table:
Index Ymax Xval 1/m
0 4 1 0
1 8 8 0 //Adding remining edges marked as (X) in global edge table
2 8 4 0
Reordering :



Index Ymax Xval 1/m
0 4 1 0
1 8 4 0
2 8 8 0
ScanLine=3, At x=1, parity is odd, so fill all points from x=1 to x=4. Parity is still odd so filling will continue upto x=8. Since next scanline is equal to 4 which is the Ymax value at index=0 so we would remove it from Active Edge Table.
Index Ymax Xval 1/m
0 8 4 0
1 8 8 0
ScanLine=4, At x=4, parity is odd so fill all points from x=4 to x=8. Parity becomes odd no filling.
PROBLEM: We are not filling points fromx=1 to x=3??



The problem is that we are not filling the points from x=1 to x=3 when scanline=4. I have also attached a text file, if there is problem in formatting of tables. Somebody plz guide me.

Zulfi.
 

Attachments

Top