We have encountered some problems with the polygon scan iterator when it
is used in the mode that includes points on the boundary of the polygon.
In this case, and for the first and last scan lines, the method for
getting the horizontal pixel spans is not valid and only works by
chance. I wish to fix this problem, but there is an issue of the
"correct" behavior for a polygon pixel scan. There seem to be a number
of different interpretations of "inside" and "on" for pixels:
1) Pixels are treated as infinitesimal points on an integer grid where
"inside" means a discrete pixel point is strictly inside the polygon
border. The case of "on" the polygon boarder means that a pixel point
is not "in" but is within one horizontal pixel distance and/or within
one vertical pixel distance from the polygon border.
2) Pixels are treated as square tiles with unit area. In this case the
entire tile must be inside the polygon border to be in. An inside tile
edge or corner can just touch the boundary and still be considered
inside. The case of a tile "on" the boundary means that the polygon
boundary intersects the tile in some finite interval. Intersections
that intersect a tile corner or lie on the edge of a tile are considered
3) Beyond these two cases there is also the notion of a "partition"
where a set of adjacent polygons with a common border should not claim
the same pixel twice. This situation can arise, for example, for a
triangular mesh and the need to extract pixels for mapping texture onto
the triangles. Neither of the definitions in 1) and 2) respect the
I am writing to seek the vxl community consensus on which set inclusion
definitions should be observed by the polygon and triangle scan
iterators. Currently, there is neither consistency nor correctness.
Professor of Engineering(Research)
Barus and Holley
184 Hope Street
I think a scan iterator should
A. iterate over all integer coordinates strictly contained within the shape;
B. not necessarily iterate over all the boundary points; and
C. iterate such that the iteration over the union of two shapes yields
exactly the same bag of points as the union of iterations over the two
shapes. (Bag to make sure points aren't repeated.)
This yields to something similar to the common scan conversion
routines in graphics. Coordinates are then treated as points and not
areas. The concept of a "point on the border" is well-defined, but not
trivial. (C) implies a partitioning.
I think the frustrations about a point being on the boundary comes
often comes from not posing the problem correctly, in the following
sense. Suppose you have a rectange (0,0)-(5,5) defining a region, and
you want all the pixels in that rectangle. You want the points (0,x),
(x,0), (x,5) and (5,x) to be included in the bag. Then, given the
conditions above, simply define your region as
(-0.5,-0.5)-(5.5,5.5). Boundary pixel issue solved. (Or, if you don't
want the boundary, define the region as (0.5,0.5)-(4.5,4.5).)
I think the graphics scan conversion meaning works well. In the cases
it doesn't seem to, I think begin explicit about what you want from
the boundary solves the problems.
A nice thing about using this definition of scan conversion is that
the graphics community has already developed fast and robust
algorithms that handle all the corner cases.