Consider the concave polygon 1234567 shown in Figure 14-2. Imagine that it’s drawn as a series of triangles: 123, 134, 145, 156, and 167, all of which are shown in the figure. The heavier line represents the original polygon boundary. Drawing all these triangles divides the buffer into nine regions A, B, C, …, I, where region I is outside all the triangles.
Figure 14-2 Concave Polygon
In the text of the figure, each of the region names is followed by a list of the triangles that cover it. Regions A, D, and F make up the original polygon; note that these three regions are covered by an odd number of triangles. Every other region is covered by an even number of triangles (possibly zero). Thus, to render the inside of the concave polygon, you need to render only regions that are enclosed by odd numbers of triangles. This can be done using the stencil buffer, with a two-pass algorithm.
First, clear the stencil buffer and disable writing into the color buffer. Next, draw each of the triangles in turn, using the GL_INVERT function in the stencil buffer. (For best performance, use triangle fans.) This flips the value between zero and a nonzero value every time a triangle that covers a pixel is drawn. After all the triangles are drawn, if a pixel is covered an even number of times, the value in the stencil buffers is zero; otherwise, it’s nonzero. Finally, draw a large polygon over the whole region (or redraw the triangles), but allow drawing only where the stencil buffer is nonzero.
Note: There’s a slight generalization of the preceding technique, where you don’t need to start with a polygon vertex. In the 1234567 example, let P be any point on or off the polygon. Draw the triangles: P12, P23, P34, P45, P56, P67, and P71. Regions covered by odd numbers of triangles are inside; other regions are outside. This is a generalization in that if P happens to be one of the polygon’s edges, one of the triangles is empty.
This technique can be used to fill both nonsimple polygons (polygons whose edges cross each other) and polygons with holes. The following example illustrates how to handle a complicated polygon with two regions, one four-sided and one five-sided. Assume further that there’s a triangular hole and a four-sided hole (it doesn’t matter in which regions the holes lie). Let the two regions be abed and efghi, and let the holes be jkl and mnop.
