need a good triangulation algorithm...

I had the same probelm when i was writing an occluder fusion function for my engine, even though i''ve discarded the most complex, i''ve come with a simple method, first you should know how to clip triangles , now, suppes you have like in your picture above a black box and a red box, first triangulate normally the black box , that''s to say divide it int two triangles, then triangulate the red box, now you have 2 ''black'' triangles and two ''red'' triangles, clip the black against the red and store the intermediate polygon, and for the last step , triagulate further the resulting polygons into triangles, they are always convex, i hope it helps.

v71''s idea is interesting.

Another approach is to triangulate the entire thing, ignoring holes. Obviously, the hole (or holes) will be filled in here. Then in a separate pass remove any triangles that have an edge that passes through the hole. I believe (without thinking too hard), its fairly easy to determine triangles that need to go away. Here''s the rule. If all of the points on a triangle lie on the boundary or interior of the hole, then discard the triangle. In your case, there are no points in the interior of the hole, then you only have to discard triangles that have all of their points on the boundary of the hole.

If you have multiple holes, then you should consider this a multiple pass approach. Treat each hole separately, and remove triangles that belong to each individual hole.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

The result you showed in your original post looks like it could be produced by BSP algorithms. Basically, you break the thing into three y subdivisions, then break the middle y subdivision into three x subdivisions. You end up with five rectangles, one of which is empty and four of which are full. Simply split each into two tris.

The BSP approach obviously only works if all your line segments are perpendicular.

quote:

---

Original post by Sneftel
The BSP approach obviously only works if all your line segments are perpendicular.

---

I don''t see that this limitation exists. You can represent any arbitrary polytope with a BSP tree. The tree represents topology, not geometry. You have to build the tree based on geometry, though, and the geometry is surely simpler if things are perpendicular. And when there are concave things, its even more difficult.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.