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

Karthik Krishnan Karthik.Krishnan at kitware.com
Mon Feb 6 14:33:57 EST 2006


I've been doing similar things in VTK, using
http://www.vtk.org/doc/nightly/html/classvtkPolyDataToImageStencil.html
filter to rasterize contours, and I've been pretty happy with the 
performance.

See 
http://public.kitware.com/cgi-bin/viewcvs.cgi/Examples/GUI/Tcl/ImageTracerWidget.tcl?rev=1.8.4.2&view=markup 

for an example.

This filter uses OBBTrees to accelerate computation of in/out status of 
a point. (Sure OBBTrees are an overkill if all you need to do is 
rasterize closed planar vtkPolylines, nevertheless, its very fast, so 
I've had no complaints).

-karthik

Zachary Pincus wrote:

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


More information about the Insight-users mailing list