[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