🔒 Locked

Issues with Triangulation

Started by RonHiler Sep 7, 2006 at 3:24 PM 5 replies 3.5k views

Original Post

Sep 7, 2006 at 3:24 PM

So I'm nearing a point with my engine that I have to start thinking about generalized polygon triangulation. This involves input from the designers, so I have no preset rules on what the polygon looks like. I've been doing my homework (and am still doing it), and I can see this is no trivial subject! As far as I can tell, triangulating a polygon with n verts is trivial as long as A) there are no holes B) it's planar, and C) it doesn't self-intersect. If these hold true, triangulating a polygon (either convex or concave) is pretty simple stuff. Unfortunately, if I want a robust tesselator, I also have to deal with those three cases. A) For the holes issue, there seems to be a fair bit of literature out there on dealing with them in a pretty robust manner. I'm not so worried about holes. I'll probably regret saying that later, but at least right now it seems like I can handle holes. B) Dealing with non-planar polygons. I've not managed to dig up *anything* on dealing with this issue. If you ignore it, you could really badly distort the original shape (which is certainly not the desired result). It seems to me that you could run the polygon through some sort of "preprocessor" and break it up along major "folds" in the polygon such that the subpolys are all now planar (within a certain tolerance) before you move into the tesselation stage. Is that how y'all would handle it? Any other suggestions? C) Dealing with self-intersecting polygons (i.e. the "Bowtie"). I've seen that some algorithms try to deal with self-intersections, but most just throw up their hands and say they aren't supported. Triangulating a self-intersecting polygon seems horrendously complicated. Forgive me if this seems overly naive, but wouldn't it be much easier to once again run the poly through a preprocessor and check for these self intersections (just a chord-chord intersection check)? If found you split the poly in two (drop a vertex at the intersection point. Do that recursively, and you can eliminate this issue altogether. Couldn't you? In summary, the way I'm considering dealing with these issues is: A) For each object in the scene B) For each face on the object C) Check for self-intersections, if found, split the face into two faces. Select one face for further checking, add the other to the "todo" list (from B on). Do this recursively until no self-intersections remain. D) Check for face planarity, within a certain tolerance. If not within tolerance, split the face in two along the best fold (how to do this???). Select one face for further checking, add the other to the "todo" list (from B on). Do this recursively until face is planer within the tolerance level. E) Triangulate the resulting face, with support for holes via the usual sorts of triangulation algorithms. NOTE: This doesn't need to happen in realtime by any means! Triangulation is happening in the design phase, by the time the objects get to the user, they will long since have been converted to triangles, heh. Any comments? Am I being completely naive on this whole approach? Thanks, Ron

TheAdmiral

Sep 7, 2006 at 3:57 PM

Sounds like you have a good grasp on how to tackle these issues. Just to complete the set, the first problem can be fixed using the same principle as for the other two: If a polygon has one hole, you can split it into two that have no holes. You addressed the other two just fine.

So indeed, the idea is to iteratively search for problem points (any subset satisfying one of the three criteria), narrow the search (further find the smallest such subset), split the polygon into two (making a note to join the results back together after triangulation is complete), repeating until you have a set of simply-connected, direct, planar polygons. From here, your task should be straightforward.

Something else to consider is that you can eliminate case C with a triangulation prepass. Since no triangle can exhibit the bowtie property, you won't need to bother with it if the polygon is comprised entirely of triangles.

As I'm sure you're aware, a triangulation any primitive, other than the triangle, is not unique. So you'll want to try and pick the 'best' partition. A term I encountered when playing with Blender is 'beauty triangulation' (what a wonderful name), whereby a n-gon is broken into triangles in such a way that the mean-square interior angle sum is minimised (or at least that's how I'd imagine the algorithm to work). This results in the triangulation with maximal regularity, so no 'long thin' triangles are generated unless they are unavoidable. Determining such a beauty partition of a quad is simple. To extend the method to higher order primitives, I think a simple divide-and-conquer algorithm would perform excellently.

Let us know how you get on.

Regards
Admiral

RonHiler

Author

RonHiler

Sep 7, 2006 at 4:35 PM

Thank you Admiral. It's good to know I'm not completely off base. I'm still doing research on the issue, so it may be a little while, but I will definitely let you know how it goes.

Wasting Time

Sep 7, 2006 at 11:34 PM

Some folks insist that the definition for "polygon" means that the vertices are coplanar. I do not. For example, you have spherical triangles/polygons. The "edges" are great-circle arcs. On a general manifold, you can extend the definition of polygon so that the "edges" are geodesic curves.

In many practical situations, the problem is not that you have a nonplanar manifold--it is that you have numerical errors that make it appear as if the vertices are not coplanar. In this case, use a least-squares method to fit your points with a plane, and then project the points onto that plane. This leads you back to the 2D problem of polygons in the plane. If the problem is that the vertices are on some manifold that is unknown, you have ambiguity. There are classic examples of closed polylines in 3D that have multiple triangulations, none of them looking similar. In this case, you have to go back to the source of the polylines and figure out how to interpret them (i.e., figure out what manifold they were created on).

That said, assume you have resolved the "nonplanar polygon" issue and have to deal only with planar points.

1. To deal with self intersections, compute all edge-edge intersections. Subdivide the edges to accommodate this; that is, you introduce new vertices and subdivide edges to obtain a graph of vertices and edges. Within this graph, two edges can only intersect at a vertex (no self intersections).

2. Compute the minimal (minimum) cycle basis. This gives you a collection of simple polygons. They may, however be nested.

3. Create a hierarchy of simple polygons. The root polygon is the outer-most polygon which encloses all others. Children of the root are inner polygons; that is, these are holes in the outer-most polygon. The inner polygons themselves may contain hierarchies of simple polygons.

4. Once you have a hierarchy, you can use triangulation methods that handle polygons with holes. Decomposition into horizonal trapezoids is one such method (see Graphics Gems 5). You can also make ear-clipping methods work, but this requires taking an outer-inner pair of polygons and identifying a pair of mutually visible vertices, one from the inner and one from the outer. Insert two edges to connect these. In the end, you have "cut" the polygon with hole and obtained a simple polygon for which two edges are coincident. Ear-clipping will still work on this, but you have to duplicate vertices for the shared edge.

5. Regarding TheAdmiral's comment about "beauty triangulation". The classical approach to obtaining a triangulation without "needle-like triangles" is Delaunay triangulation. Such a triangulation has the property that you have maximized the minimum angle in each triangle. Once you have a triangulation for a simple polygon (or for a polygon with holes that has been converted to a simple polygon), it is not too difficult to do edge swapping to satisfy the maximized minimum angle constraint.

As much as a lot of the concepts appear simple to "visualize" and draw pictures, the devil is in the details. Robust implementations take a lot of time to get right.

RonHiler

Author

RonHiler

Sep 8, 2006 at 9:46 AM

Quote:
Original post by Wasting Time
Some folks insist that the definition for "polygon" means that the vertices are coplanar. I do not. For example, you have spherical triangles/polygons. The "edges" are great-circle arcs. On a general manifold, you can extend the definition of polygon so that the "edges" are geodesic curves.

Exactly. I apologize if anyone was confused by my terminology. I've given the designers the ability to move around individual verts independently in 3D space, and as soon as you do that, you introduce the possibility of non-planar faces (or what I was calling polygons).

Quote:

In many practical situations, the problem is not that you have a nonplanar manifold--it is that you have numerical errors that make it appear as if the vertices are not coplanar. In this case, use a least-squares method to fit your points with a plane, and then project the points onto that plane.

This is actually where I'm most tenuous in this whole discussion. ISTM that you cannot introduce chords just *anywhere* on a non-planar face. Doing so could create a "seam" on the surface of the face, which is undesirable from the standpoint of the modeller. This is why I was thinking I ought to split non-planar faces into parts that *are* planar (or at least close enough) prior to adding new chords. However, figuring out exactly where to split a face is an algorithm I haven't yet come up with.

Quote:
1. To deal with self intersections, compute all edge-edge intersections. Subdivide the edges to accommodate this; that is, you introduce new vertices and subdivide edges to obtain a graph of vertices and edges. Within this graph, two edges can only intersect at a vertex (no self intersections).

Aye, exactly what I was thinking too. I think we're all on the same page with this one :)

Quote:
2. Compute the minimal (minimum) cycle basis. This gives you a collection of simple polygons. They may, however be nested.

Errr, you lost me. What's a cycle basis? The minimum distance from vert A to vert A along the face chords that is > 0?

Quote:
3. Create a hierarchy of simple polygons.

Sure.

Quote:

4. Once you have a hierarchy, you can use triangulation methods that handle polygons with holes. Decomposition into horizonal trapezoids is one such method (see Graphics Gems 5). You can also make ear-clipping methods work, but this requires taking an outer-inner pair of polygons and identifying a pair of mutually visible vertices, one from the inner and one from the outer. Insert two edges to connect these. In the end, you have "cut" the polygon with hole and obtained a simple polygon for which two edges are coincident. Ear-clipping will still work on this, but you have to duplicate vertices for the shared edge.

Yeah, I've read the article in Gems 5. I've noticed it has gotten quite a bit of flack for not being very robust (not to mention the code it hard to follow, but that's my own issue, heh). However, I don't think it would choke on the simple polygons that remain presuming the aforementioned issues have been taken care of beforehand (i.e. we feed it only simple coplanar polygons). I could be wrong though. I have yet to analyze that code in great detail. But, yeah, that's the way I was leaning (that's based on Seidel right?). Ear clipping seems a bit too problematic, although perhaps I'm mistaken about that.

Quote:
5. Regarding TheAdmiral's comment about "beauty triangulation". The classical approach to obtaining a triangulation without "needle-like triangles" is Delaunay triangulation. Such a triangulation has the property that you have maximized the minimum angle in each triangle. Once you have a triangulation for a simple polygon (or for a polygon with holes that has been converted to a simple polygon), it is not too difficult to do edge swapping to satisfy the maximized minimum angle constraint.

Ah, that makes sense. I've run across that term (Delaunay) in my research, but hadn't yet figured out exaclty what it meant, thanks for the definition ;) Sounds like I'll need a post-processing step.

Quote:
As much as a lot of the concepts appear simple to "visualize" and draw pictures, the devil is in the details. Robust implementations take a lot of time to get right.

Indeed. This is one step in the engine coding that I've been dreading :)

Wasting Time

Sep 8, 2006 at 2:44 PM

I think you are going to make your programming life miserable by insisting that you must have general-purpose algorithms that can handle arbitrary data. The modeling packages I know of do not spit out point clouds or polygon soup--they spit out triangle strips, meshes, and fans. This means you already know how the vertices are connected to form polygons. In fact, in most cases you get triangles, so there is no triangulating to do and your problem is solved without even having to program.

That said, just a bit more about the problem and how much abstraction you need to formulate a solution to the problem. To keep things abstract, let's assume that (1) you do have the adjacency information for the vertices and polygons, (2) all the computing is done with exact arithmetic, and (3)the amount of computation time is not of concern.

Suppose you have a mesh of polygons such that (1) the polygons are not necessarily triangles and (2) the polygons do not all lie in the same plane. The first goal is to partition the set of polygons into subsets, each subset consisting of coplanar polygons. You can iterate over the polygons and compute the distinct set of planes you must work with. Then iterate over the planes. For each plane, iterate over the polygons and create a set of polygons that lie in that plane.

Now process each set of coplanar polygons. You have the adjacency information, so you can build a graph of vertices and edges. At this time you can worry about whether the artists have generated polygons that overlap, in which case you can subdivide the edges as I described in my previous post, and then build the graph so that edges only intersect at vertices.

From the graph, you need to determine the polygons to be triangulated. I had mentioned "minimal cycle basis". See The Minimal Cycle Basis for a Planar Graph.

Once you have the polygons, you then need to determine if (and how) they are nested and build tree structures to represent the nesting. Then triangulate. You said "Ear clipping seems a bit too problematic". I do not know what you mean by this. If you can get it to work, then it works. There is the asymptotic order to worry about, but I'd get something working first and then worry about performance later (by swapping in a faster triangulator). For a discussion of ear clipping for polygons with holes and trees of polygons, see
Triangulation by Ear Clipping.

RonHiler

Author

RonHiler

Sep 8, 2006 at 3:42 PM

Cool, thanks. I'll read those over. You can always count on Dr. Eberly to write good articles, huh? :)

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.