Does anyone know how to draw concave polygons quickly?

Does anyone know how to draw concave polygons quickly? I mean that I just have a list of vertexes, but I don’t know if it is a simple polygon or not. And perhaps there are one or more holes in it. You know, OpenGL could not do it automatically. Could you tell me what shall I do? GlUT or other ways?

A good quick and dirty way to draw concave polygons is to use the stencil buffer as follows. Assume no depth testing for this simple example.

Clear the stencil buffer to zero (you can get away with using only the LSB).

Disable color writes (ColorMask with all FALSE). Enable stencil test with an ALWAYS function. Set the stencil op to INCR.

Render the polygon outline as a TRIANGLE_FAN. Once this is done, the stencil buffer will contain the number of triangles that cover each pixel. Pixels with covered by an odd number of triangles are inside the concave polygon; others are outside.

Now in the second pass, turn on color writes. Set the stencil test to EQUAL to 1 with a mask of 1 (testing the LSB). Pixels with an even number of hits will fail; odd ones will pass. Set the stencil op to ZERO on a pass, so the odd pixels are set back to zero (even).

Render the triangle fan again. The stencil buffer will be zeroed out during the second pass, so you can draw more concave polygons without clearing the stencil buffer again.


Thanks for your replay. Could you give me a example?
I am thinking about this problem:
First I can check the polygon’s vertexs, make sure that it is concave or convex. if it is a simple polygon, draw it directly. If it is a complex one, draw it by GLUT. there are not so many concave polygons or with one or more holes I think. So it would be faster. Do you think so? But how to judge it is concave or not fastest?
Thanks for you help!