Hi,
my aim is to rasterize, in one single color a polygon (generally, non-convex, not self-intersecting, with holes, tessellated to convex polygons using GLU, if that matters; yes, I know its obsolete) onto a completely black background so that every pixel (“fragment”) whose center is inside or on the polygon boundary gets lit. The original problem is to find all points on a regular lattice inside of a polygon.
- I understand OpenGL considers [1] the coordinates [x + 0.5, y + 0.5] the center of the [x,y] pixel (doesn’t really matter whether lower-left-most or otherwise)
2a) I assume polygon vertices are pixel centers. As far as I can tell [2], polygons get rasterized in a similar fashion, with the pixel whose centers are exactly on the polygon’s boundary defined to belong to the polygon “if they’re on the top or left edges” ([4,*]. As far as I can deduce, this also has as the consequence that the pixel centers on horizontal bottom edges are considered out
2b) and I’m not entirely sure about vertices with two edges going up, each to a different side (sort of a V shape, with the vertex with a degree of 2 being the vertex in question), as those belong to both a left edge and a right edge (the Active Edge Algorithm [3] suggests they probably do not belong to the polygon).
How do I, given 1, 2a, 2b, find all the pixels whose centers are inside? I thought I might draw a polyline to include the bottom/right edges, but that seems to be even more under-defined for my purposes. I could offset the polygon slightly to bottom/right (much less than a pixel) and render it again, which would solve the bottom/right edges problem (unrealistically assuming infinite precision), and render the vertices for the “V shapes” as single points or treat them separately. But I thought maybe there’s a more elegant/accurate(in real life) solution.
Any comments on the proposed method, as well as any other ideas (preferably OpenGL based) are welcome.
Disclaimer: I know OpenGL wasn’t designed for solving this exact problem, but I’m trying to make it do it. I know it’s not right and might be implementation dependent, but please accept this is the thing I want to try/explore at the moment.
[1] https://www.opengl.org/registry/specs/ARB/fragment_coord_conventions.txt , “OpenGL assumes a lower-left origin for window coordinates and assumes pixel centers are located at half-pixel coordinates. This means the XY location (0.5,0.5) corresponds to the lower-left-most pixel in a window.”
[2] http://chrishecker.com/images/9/97/Gdmtex2.pdf (“raster blaster” headline)
[3] http://ezekiel.vancouver.wsu.edu/~cs442/lectures/raster/polyfill/poly.pdf
[4] http://www.opengl.org/documentation/specs/version1.1/glspec1.1/node54.html, “Fragment centers that lie inside of this polygon are produced by rasterization. Special treatment is given to a fragment whose center lies on a polygon boundary edge. In such a case we require that if two polygons lie on either side of a common edge (with identical endpoints) on which a fragment center lies, then exactly one of the polygons results in the production of the fragment during rasterization.”
[*] Any info on whether any implementation actually do a bottom/right rule instead top/left (or some other, more intricate, thing)? If bottom/right and top/left are the only ones, I could detect the situation and flip. FOR THE SAKE OF DISCUSSION, I ASSUME TOP/LEFT.