You will need an active edge list, which contains a list of all polygon edges intersected by the current scanline. You will also need an in/out flag for each polygon on the scanline. The flags are toggled on/of as you cross an edge for a polygon.
The rules are drawing for each pixel along a scanline are;
- no polygon flags are 'in', then draw background
- only one polygon flag is 'in', the draw the colour of that polygon
- two or more polygon flags are 'in', use you plane equation to find out which is closest at that pixel position.
- as we move onto the next pixel check the AEL (see below) to see if we are crossing an edge. if so toggle the appropriate flag.
An important component in the data structure needed for this algorithm is the edge node. Each edge in the polygon is represented by an edge node. An edge node contains the following information;
- yupper , the y co-ordinate of the upper end-point of the edge.
- ylower , the y co-ordinate of the lower end-point of the edge.
- xint , initially the x co-ordinate of the lower end-point of the edge. As the algorithm progresses, this field will store the x co-ordinate of the point of intersection of the scan-line.
- ym , the reciprocal of the slope of the line ( 1/m ).
- link to the polygon which own the edge.
When constructing an edge node for the edges, the following must be taken into account;
- Horizontal Edges are ignored (an edge node is not generated for these), these edges will be drawn when the adjacent edges are processed.
- If two edges share a vertex AND the vertex is an upper end point for one edge and a lower end point for another edge, the yupper of the lower edge must be reduced by 1. this is to allow the in/out toggle to work correctly.
In the above image the very top scanline intersects to edges at the top of the triangle. the two edges cause it to toggle from "out" to "in" to "out", which is correct.
However, the second line also intersects two edges and is toggled "out" which is incorrect. The solution is to lower the y-int of the lower edge in this case. Now teh scan line only intersects one edge at the vertex.
This adjustment will not have any effect on the shape of the triangle as the xint will be used to determine where to start drawing. The effect of lowering the vertex is to cause it to be removed one scanline earlier than it would otherwise. All this assuming you are scanning from bottom to top.
Most implementations maintain an Active edge list (AEL), a list of edges. which contains all the edges intersected by the current scan line. The AEL needs to be maintained as we move from on scan-line y to the next scan-line (y+1) ;
- Add any edges whose ylower is equal to y .
- Colour the pixels along the scanline as described above
- One or both of the edges in the AEL will no longer be intersected by (y+1) . Remove the edges from the AEL, where yupper is equal to y .
- The intersection point of the scan line with the remaining edges will change for the new scan-line. xint is updated to xint+ym . Note that xint must be stored as a real number to avoid round-off errors.
- increment y (to the next scan line)
- Repeat until the last scanline is drawn.