Scan Line Algorithm

Intro

The Scan-Line algorithm is a general purpose algorithm for filling polygons, both convex and not convex. The algorithm can be implemented in integer arithmetic avoiding the real number system(floats).

Originally fast graphics was done in integers so it was important to write the algorithms to work in the integer domain. Now hardware solutions let the work be done in real numbers (floats and doubles).

These are two very different domains from algorithms perspectives. One is about the continuous variable, the other the discrete variable.

An AET (Active Edge Table) on the y-axis holds buckets of lines. A current line exists and iterates through y with lines dying of and new ones added.

Definitions

Let the y-axis be indexed in integers corresponding to the horizontal scan lines 0 from bottom to N-1 on top.
Let the y-axis contain a list of line objects.
A line object is completely described by its y-axis index (the minimum y value of the line) and { ymax, dx, x }.
dx is actually the gradient of the line inverted.
The line has the special property that x + dx is the new endpoint for the horizontal line incrementing upwards in y.
Let the x-axis be ordered on the lower end point, then if equal the negative to positive gradient.

The consequences of ordering the x-axis this way is that two successive points counting from the start describe a line segment to be displayed. This is a cool algorithm.

Algorithm

have current scan-line v
copy the scan line with index=0 to v
draw the scan line v
index = 0 .. N-1
remove dead points from v
increment each line in v
++index
Merge y[index] with v. Preserve a valid ordering.
draw the current line v

Example

Solving In The Integer Domain

Apparently after consulting my friend mathematics doesn't have a name for solving something in the integer field as opposed to solving in R. So whats called incremental arithmetic by the computer scientists has no recognizable maths name. (Is this a case of mathematics thats not defined yet is not mathematics?).

Let me elaborate on this diversion. We use complex numbers to solve some problem in R. Going from a higher dimension to a lower one. For incremental arithmetic we are solving in the lower dimension for the higher one.

So calling it incremental arithmetic is a massive understatement. You are really solving a problem in the integer domain - a huge place.

Now for the topic - the scan line algorithm is implemented in the integer domain with incremental arithmetic. (don't call me a hypocrite, I need people to talk to).

For the purposes of the Scan-Line Algorithm this is separated out and the algorithm is fleshed out in the real domain. This is a common thing to do as its best to communicate ideas in the simplest domain.

Acknowledgments

Example from RMIT CS1186 tutorial 3, 2004.

"Computer Graphics - Principles and Practice", second edition, Foley, van Dam, Feiner, Hughes. Page 97+, the Scan-Line Algorithm