Drawing a concave polygon in OpenGL

Question

I have a concave polygon I need to draw in OpenGL.
The polygon is defined as a list of points which form its exterior ring, and a list of lists-of-points that define its interior rings (exclusion zones).

I can already deal with the exclusion zones, so a solution for how to draw a polygon without interior rings will be good too.

A solution with Boost.Geometry will be good, as I already use it heavily in my application.

I need this to work on the iPhone, namely OpenGL ES (the older version with fixed pipeline).

How can I do that?

Cymogene

Answer 1

Try OpenGL's tessellation facilities. You can use it to convert a complex polygon into a set of triangles, which you can render directly.

EDIT (in response to comment): OpenGL ES doesn't support tessellation functions. In this case, and if the polygon is static data, you could generate the tessellation offline using OpenGL on your desktop or notebook computer.

If the shape is dynamic, then you are out of luck with OpenGL ES. However, there are numerous libraries (e.g., CGAL) that will perform the same function.

Antifriction

No, that's OpenGL ES, which doesn't provide tesselation functions. If you need this to happen on an iPhone, you should amend the question to make this clear. – Antifriction

Do you know if it can be done with Boost? If not I'll resort to offline computation as the shape is not dynamic. – Cymogene

I don't know anything about Boost.Geometry. The project's current status doesn't bode well, but if it's a one-off exercise, it mightn't be such a problem. Thinking about it again, perhaps there's even a tool to perform the tessellation without writing any code (I don't know of any, though). – Antifriction

Answer 2

It's a bit complicated, and resource-costly method, but any concave polygon can be drawn with the following steps (note this methos works surely on flat polygons, but I also assume you try to draw on flat surface, or in 2D orthogonal mode):

• enable stencil test, use glStencilFunc(GL_ALWAYS,1,0xFFFF)
• disable color mask to oprevent unwanted draws: glColorMask(0,0,0,0)
• I think you have the vertices in an array of double, or in other form (strongly recommended as this method draws the same polygon multiple times, but using glList or glBegin-glEnd can be used as well)
• set glStencilOp(GL_KEEP,GL_KEEP,GL_INCR)
• draw the polygon as GL_TRIANGLE_FAN

Now on the stencil layer, you have bits set >0 where triangles of polygon were drawn. The trick is, that all the valid polygon area is filled with values having mod2=1, this is because the triangle fan drawing sweeps along polygon surface, and if the selected triangle has area outside the polygon, it will be drawn twice (once at the current sequence, then on next drawings when valid areas are drawn) This can happens many times, but in all cases, pixels outside the polygon are drawn even times, pixels inside are drawn odd times. Some exceptions can happen, when order of pixels cause outside areas not to be drawn again. To filter these cases, the reverse directioned vertex array must be drawn (all these cases work properly when order is switched): - set glStencilFunc(GL.GL_EQUAL,1,1) to prevent these errors happen in reverse direction (Can draw only areas inside the polygon drawn at first time, so errors happening in the other direction won't apperar, logically this generates the intersectoin of the two half-solution) - draw polygon in reverse order, keeping glStencilFunc to increase sweeped pixel values Now we have a correct stencil layer with pixel_value%2=1 where the pixel is truly inside the polygon. The last step is to draw the polygon itself: - set glColorMask(1,1,1,1) to draw visible polygon - keep glStencilFunc(GL_EQUAL,1,1) to draw the correct pixels - draw polygon in the same mode (vertex arrays etc.), or if you draw without lighting/texturing, a single whole-screen-rectangle can be also drawn (faster than drawing all the vertices, and only the valid polygon pixels will be set)

If everything goes well, the polygon is correctly drawn, make sure that after this function you reset the stencil usage (stencil test) and/or clear stencil buffer if you also use it for another purpose.

Cetus

Answer 3

Check out glues, which has tessellation functions that can handle concave polygons.

Wulfila

Answer 4

I wrote a java classe for a small graphical library that do exacly what you are looking for, you can check it here :

https://github.com/DzzD/TiGL/blob/main/android/src/fr/dzzd/tigl/PolygonTriangulate.java

It receive as input two float arrays (vertices & uvs) and return the same vertices and uvs reordered and ready to be drawn as a list of triangles.

If you want to exclude a zone (or many) you can simply connect your two polygones (the main one + the hole) in one by connecting them by a vertex, you will end with only one polygone that can be triangulate like any other with the same function.

Like this :

To better understand zoomed it will look like :

Finally it is just a single polygon.

Yenta