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

[Frank Miller]

Zachary,

I might have a solution for you.

I was working on a similar problem a while ago.  I was just learning ITK 
and was not aware of the PolyLineMask2DImageFilter but in my search for 
such a filter, I came across this solution.

http://public.kitware.com/pipermail/insight-users/2005-June/013614.html

I am not sure that this iterator attains the sub-pixel precision you are 
looking for but I suspect that it does or could be made to do so.

I had some trouble with this code at first but I made a few changes and 
it seems to work fine now. I have attached a path file that can be used 
on the code in the above link. You should know, however, that I have not 
taken the time to understand the changes that I made. I just hacked on 
it until it worked. Depending on you application, you might want to be 
more scrupulous.

Note: When you download the code from the link, change the extension to 
.tar.gz

If speed is not an issue, you might try what Jim suggested in this post.

http://public.kitware.com/pipermail/insight-users/2005-October/015297.html

"A brute force way to do what you want is to construct a 
PolygonSpatialObject and use a SpatialObjectToImageFilter to generate 
the initial implicit function."

I have not tried this.

Good luck,

Frank

Zachary Pincus wrote:
> 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
> _______________________________________________
> Insight-users mailing list
> Insight-users at itk.org
> http://www.itk.org/mailman/listinfo/insight-users
-------------- next part --------------
diff -Naur PolygonScanConversion/itkPolygonScanConversionConstIterator.txx NewPolygonScanConversion/itkPolygonScanConversionConstIterator.txx
--- PolygonScanConversion/itkPolygonScanConversionConstIterator.txx	2005-06-15 07:40:50.000000000 -0400
+++ NewPolygonScanConversion/itkPolygonScanConversionConstIterator.txx	2006-02-06 10:44:25.000000000 -0500
@@ -21,7 +21,7 @@
     IndexType firstIndex = *(vertices.begin());
     for (typename IndexListType::const_iterator it = vertices.begin(); it != vertices.end(); ++it)
     {
-      for (int i=0; i < ImageIteratorDimension; ++i)
+      for ( unsigned int i=0; i < ImageIteratorDimension; ++i)
       {
         if ((*it)[i] != firstIndex[i])
         {
@@ -314,16 +314,16 @@
   // Update the active edges and move them to a temporary storage to keep
   // them sorted after the update.
   EdgeListType temporaryActiveEdgeList;
-  EdgeListType::const_iterator it = m_activeEdgeList.begin();
+  EdgeListType::iterator it = m_activeEdgeList.begin();
   while (it != m_activeEdgeList.end())
   {
     Linear2DIndexInterpolator *line = *it;
 
     // Remove the line from the list of active edges. If it is still active
     // after it has been updated, it will be inserted again.
-    EdgeListType::const_iterator deleteIt = it;
+    EdgeListType::iterator deleteIt = it;
     ++it;
-    m_activeEdgeList.erase(deleteIt);
+    m_activeEdgeList.erase( deleteIt );
 
     if (line->IsAtLast())
     {