## Re: [Vxl-maintainers] Polygon Scan Iterator

 Re: [Vxl-maintainers] Polygon Scan Iterator From: Amitha Perera - 2006-03-13 21:01:56 ```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. Amitha. ```

 [Vxl-maintainers] Polygon Scan Iterator From: Joseph L Mundy - 2006-03-09 22:51:13 Attachments: Message as HTML ```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 outside. 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 partition constraint. 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. Joe o----o----o----o----o----o----o----o Professor of Engineering(Research) Room 351 Barus and Holley 184 Hope Street Providence, RI 401-863-2655 ```
 Re: [Vxl-maintainers] Polygon Scan Iterator From: Amitha Perera - 2006-03-13 21:01:56 ```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. Amitha. ```