Scanline algorithm for polygons /| (2,4) | y = 2x / | | / | y = -2x+8 fig. 1 | (0,0) /__ | (3,2) __________________ | y = 2/3x __________________ Keep | fig. 2 ____________/|____ It | ___________/x|____ Simple | __________/xx|____ Stupid | _________/xxx|____ | ________/xxxx|____ K.I.S.S. | _______/xxxxx|____ | __________________ | ------------------------------------------------------------------------------------------------------------ Edge Table ref. fig. 2 | Active Edge Table ref. fig. 2 | Delta X / Delta Y, X, Ymax |(y=0) |1/2| 0 | 4 | ---> | 3/2| 0 | 2 | Draw (0,0) Y = 2 ---> |-1/2| 0 | 4 | |(y=1) |1/2|1/2| 4 | ---> | 3/2|3/2| 2 | Draw (1,1) & Draw (2,1) Y = 0 ---> | 1/2| 0 | 4 | ---> |3/2| 0 | 2 | |(y=2) |1/2| 1 | 4 | ---> |-1/2| 3 | 4 | Draw (1,2) & Draw (2,2) & Draw (3,2) |(y=3) |1/2|3/2| 4 | ---> |-1/2|5/2| 4 | Draw (2,3) & Draw (3,3) |(y=4) ------------------------------------------------------------------------------------------------------------------------------------ Star Example (7,15) | | | | | | | | . | | | | | | | Edge Table | | | | | | | | | | | | | | | y = 0 |1/3| 2 | 15| ---> |6/5| 2 | 10| ---> |-6/5| 12| 10| ---> |-1/3| 12| 15| | | | | | | | | | | | | | | |----------------------------------------------------------------------------------- | | | | | | | | | | | | | | | Active Edge Table | | | | | | | | | | | | | | | (y=0) |1/3| 2 | 15| ---> | 6/5| 2 | 10| ---> |-6/5| 12| 10| ---> |-1/3| 12| 15| (0,10)| . | | | | | | | | | | | | | . |(14,10) Draw (2,0) | Draw (12,0) | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | (y=1) | 2+(1/3) | ---> | 3+(1/5) | ---> | 10+(4/5) | ---> | 11+(2/3) | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | (y=2) | 2+(2/3) | ---> | 4+(2/5) | ---> | 9+(3/5) | ---> | 11+(1/3) | | | | | | | | | | | | | | | | | | | |(.)|(.)|(.)|(.)|(.)|(.)|(.)|(.)| | | | (y=3) | 3 | ---> | 5+(3/5) | ---> | 8+(2/5) | ---> | 11 | | | | |(.)|(.)|(.)| | |(.)|(.)|(.)| | | | | | | |(.)|(.)| | | | |(.)|(.)| | | | (y=4) | 3+(1/3) | ---> | 6+(4/5) | ---> | 7+(1/5) | ---> | 10+(2/3) | | | |(.)|(.)| | | | | | |(.)|(.)| | | <--SWAP--> | . | |(.)| | | | | | | | |(.)| | | (y=5) | 3+(2/3) | ---> |-6/5| 6 | 10| ---> | 6/5| 8 | 10| ---> | 10+(1/3) | (0,0) (2,0) (12,0)