Scan converting triangles

Problem of scan converting triangles. Now that we have converted our general polygon into a set of triangles, we can look at the problem of scan converting the triangle.

Start with top Scan Line: For each scan line, find intersection points with triangle, turn on pixels inside triangle. Note that there will be two intersection points for each scan line, so, one side of the triangle will not be intersected by any given scan line. If we keep track of the Ytop value for the edges, then only those edges for which Ytop <= current scan line may have intersections, e.g., for scan line 1 the only edges are ab and ac, not cb. we need to keep track of edges which can no longer be intersected by the current scan line, e.g., ac for scan line 2.

We could keep the bottom Y value for each edge and compare against the current scan line. Instead, we will keep the length (delta Y) of each polyline. We will decrement this each time we move down a polyline and the edge can no longer be intersected when delta Y = 0.

We need to keep the bottom Y value for the triangle to know when we are done. We also need to compute the intersection of each scan line with the edges. We could perform a brute force computation, i.e., for each scan line compute using:

y = const (scan line)
y = mx + b (poly side)

but it is better to use coherence property (related properties), i.e., compute the intersection using the intersection value from the previous scan line.

Now:

m = (yi+1 - yi) / (xi+1 - xi)
yi+1 = yi 1 { +1 for IBM CGA, ega, vga since 0,0 is upper left; -1 if 0,0 lower left}

For IBM CGA, EGA, VGA, and many other graphics boards:

yi+1 - yi = 1
m = 1 / (xi+1 - xi) => xi+1 = xi + 1/m

So can find 1st pair x, y then use above to find intersections with other scan lines.

Data Structure: each entry in edge list contains

ytop = value of top y
dy = length of y
xint = intial x value
x_change_per_scan_line (1/m)

Top Level Algorithm:

  1. Create Edge List (Note: if we find any horizontal edges then we can draw them)
  2. Repeat
    Find x-intersections
    Draw-lines

 

Solid Polygon menu
HyperGraph Table of Contents.
HyperGraph Home page.

Last changed May 13, 1998, G. Scott Owen, owen@siggraph.org