Hello,

I’m writing research paper on software rasterization algorithms and at one point I gave example of triangle rasterization algorithm.

The algorithm is really basic. If the triangle is flat top or flat bottom it’s possible to determine the minimum and the maximum x values for each scan line using the equation of line for the edges. Then for each scan line fill the pixels between minimum x and maximum x values.
If the triangle is of other kind it’s possible to split it to flat top and flat bottom triangles (finding the fourth vertex) and draw it using the previous algorithm.

I need to cite a reference for this algorithm. I saw it in some book in the ‘90s and I can’t just write it without a reference. The problem is that I can’t remember where I saw it.
I already tried to look at “Computer Graphics: Principles and Practice” but the only similar algorithm there is the polygon rasterization algorithm, which is over engineered for this kind of problem, same with "Computer Graphics: C Version".
I also tried to look at “Black Art of 3D Game Programming”, which have similar algorithm but the algorithm that I saw was in another book and slightly different.

Anyone know a book with this kind of algorithm?
Any help is appreciated.

Thanks.

Michael Abrash's Graphics Programming Black Book might be another reference, but polygons too IIRC.

Note that rendering polygons is much more efficient than triangles due to less edges to setup - if there is enough planar stuff around.

Later there was a SIMD approach which does a bounding rect per triangle and then evaluating 3 side of edge tests in parallel per pixel. I remember a guy named Nicolas Capens who wrote an article about this, might be another good reference.

IIRC "Tricks of the 3D Game Programming Gurus-Advanced 3D Graphics and Rasterization" by Andre laMothe has that algorithm.

For a different method of rasterization look here: http://forum.devmaster.net/t/advanced-rasterization/6145