#340 GeneralPolygons with holes are sometimes corrupted.

[Adam Buchbinder]

Render the attached RIB. The result should be two Sierpinski-looking things. The right figure is several small black triangles atop a white triangle; the left figure is a white triangle with
holes cut in it. The left figure renders improperly.

I believe that the RIB's geometry is correct, as it renders correctly in BMRT and 3Delight. The model was adapted from the examples to "Renderman for Beginners", at http://smartcg.com/tech/cg/books/RfB/download/contents/Ch04_GeomPrim/Fig_4.19/index.html.

I'm running aqsis version 1.5.0 (revision 2522) on Ubuntu Hardy.

[Adam Buchbinder]

RIB triggering the bug.

[Adam Buchbinder]

Scene as rendered by r2522.

[Chris Foster]

I spent some time today looking at why this happens, and it seems that the aqsis algorithm for triangulating polygons with holes is incorrect. AFICT, aqsis does the following to triangulate a general polygon:

1. Create a polygon containing only the boundary.
2. For each hole, insert the hole and add a zero-width slit to join the hole to the outer polygon boundary.
3. Perform the ear-cutting algorithm to successively chop off triangles, removing a vertex at each step.

Unfortunately step 2 seems to have some fundamental problems because holes are added independently of one another. In particular, if the first hole creates a slit which happens to intersect the second hole when it's added later, then the algorithm fails.

If the hole additions are reordered, the problem can be made to go away. In the case of the sierpinski approximation this corresponds to adding the middle hole second rather than first. However, I don't think this can be made into a scalable algorithm; I think we'll need to do something different.

[Chris Foster]

I've decided to discard hope for the ear-clipping triangulation algorithm, since it seems inherently unable to deal with holes...

Some research reveals that there's a lot of triangulation algorithms out there, but few are designed (or described) with holes in mind. The following paper does describe an algorithm which is fast in most circumstances, deals with holes, and appears to be reasonably easy to implement:

"A fast polygon triangulation algorithm based on uniform plane subdivision"
by Marko Lamot and Borut Zalik, Computers & Graphics 27 (2003) 239­253

One option would be to reimplement CqPolygonGeneral2D using this algorithm.