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

[Zachary Pincus]

Hello,

Thanks for the suggestion. Unfortunately, Bresenham-based line- and  
polygon-conversion algorithms (such as in  
itk::PolyLineMask2DImageFilter) can't guarantee that any pixel center  
inside the geometric polygon will be drawn and that every center  
outside the polygon will not. This error is minor except at the edges  
of polygons, which unfortunately make up a large fraction of the  
polygons I'm using (which represent rather small objects).

I will still try to find some reference code somewhere for polygon  
scan conversion and port that to ITK, but that will have to be a back- 
burner project.

One other thing I should mention, based on reading the emails you  
referred to. It seemed like in that case, your use of the polygon  
rasterizer was as an intermediate in the creation of a distance map  
from the polygon. Now, obviously this is slower (at least two  
iterations through the image instead of one) and less precise than  
some miraculous method which would take a geometric polygon and  
output a subpixel-accurate distance map. In case either of these  
problems has been affecting you, I have just recently found out that  
this miraculous method does exist, and there is C++ code available  
for the same!

http://www.acm.caltech.edu/~seanm/projects/cpt/cpt.html

Zach



On Feb 6, 2006, at 9:04 AM, Frank Miller wrote:

> 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
> 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())
>      {
> _______________________________________________
> Insight-users mailing list
> Insight-users at itk.org
> http://www.itk.org/mailman/listinfo/insight-users