[Insight-users] Polygon rasterizer (aka scanline conversion)
Karthik.Krishnan at kitware.com
Mon Feb 6 14:33:57 EST 2006
I've been doing similar things in VTK, using
filter to rasterize contours, and I've been pretty happy with the
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).
Zachary Pincus wrote:
> 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!
> On Feb 6, 2006, at 9:04 AM, Frank Miller wrote:
>> 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
>> "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,
>> 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.
>>> 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.
>>> Insight-users mailing list
>>> Insight-users at itk.org
>> diff -Naur PolygonScanConversion/
>> itkPolygonScanConversionConstIterator.txx NewPolygonScanConversion/
>> 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;
>> - m_activeEdgeList.erase(deleteIt);
>> + m_activeEdgeList.erase( deleteIt );
>> if (line->IsAtLast())
>> Insight-users mailing list
>> Insight-users at itk.org
> Insight-users mailing list
> Insight-users at itk.org
More information about the Insight-users