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:

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.