[Insight-users] Polygon rasterizer (aka scanline conversion)

[Zachary Pincus]

Hello folks,

Having just finished writing a filter to turn images into closed  
parametric paths, I decided to turn my attention to the opposite  
problem: rasterizing (or "scanline converting") a polygon represented  
as a PolyLineParametricPath.

ITK does contain such an algorithm: PolyLineMask2DImageFilter.  
However, this  method only operates at pixel precision . This means  
that it cannot guarantee that if a pixel center is inside the  
geometric polygon, that pixel will be "on" in the rasterized polygon  
and ditto for the outside/off case. Large contours will be distorted  
at the edges, and small contours can be completely changed or not  
even drawn.

The PolyLineMask2DImageFilter is good at what it does: quickly  
rasterizing an approximation of a large polygon. However, I'm  
interested in getting a filter working which will provide precise  
scanline conversion. Looking over the commonly-used algorithm to do  
this, I realize that implementing it from scratch will be completely  
unpleasant -- too many edge cases. So I hope to find a good polygon  
rasterizer to port to ITK. Does anyone know of a simple reference  
implementation? (No antialiasing necessary.) Perhaps somewhere in VTK  
is a polygon rasterizer that could be ported to ITK with little effort?

Any suggestions would be helpful.

Zach

PS. Here's an overview of the "standard" scanline conversion  
algorithm. There are just too many corner cases (ha! literally!) for  
this to sound like fun to implement from scratch.
http://www.dgp.toronto.edu/~ah/csc418/fall_2001/notes/scanconv.html