PDA

View Full Version : All points inside polygon using rasterization



GreenAlien
02-27-2012, 11:14 AM
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.

1) 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.

tonyo_au
02-28-2012, 11:46 PM
I am not sure if I understand what you are trying to do; but have you looked at MSAA (coverage) rendering. A fragment that is completely inside the polygon will have all its samples set. A fragment which is on the edge will have some set and some not; in fact I believe it is possible to find exactly which past of the fragment are inside from the sample indices presented to the fragment shader.

Dark Photon
02-29-2012, 05:52 PM
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...so that every pixel ("fragment") whose center is inside or on the polygon boundary gets lit.
Agree with the other poster -- hard to tell exactly what your constraints and limitations on here. Assuming this isn't homework and you're actually going to use the GPU to do this...

Render hole polys into stencil buffer. Render parent poly with stencil test set to exclude holes. Let the GPU handle clipping, rasterization, masking hole texels, and such.

Not sure, but I don't think you want precisely what you're proposing because that might cause some pixels to be set twice for the two tris on either side of a shared edge case, depending on where the edge is.