# Polygon Triangulation For Regular Mesh

This topic is 2505 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I'm looking for a fast and efficient method for covering a 2D (sometimes concave) shape with a fairly regular triangular mesh. I know that the problem of triangulation of a simple (non-intersecting, no holes) polygon has been addressed before (with varied degrees of complexity) e.g. ear-clipping, Seidel's algorithm or Delaunay, but these approaches result in vastly different size triangles and are not all applicable to concave shapes. I am hoping that there could be a more simple solution for the restricted shapes I am particularly interested rather than considering a generic polygon.

The shapes I need to tessellate with triangles are the result of a rectangle clipping a "lune" (think cresent or gibeous moon shapes). Something like these:
[attachment=1602:examplepolys.jpg]
These are mostly either a kind of rounded rectangle (with corners concave or convex), or triangle with a curved (convex or concave) side, although the entire lune could need to be covered with a mesh. Approximating the curves with line segments, is there some kind of appoach with strips of triangles I can take?

Any suggestions?

##### Share on other sites
As far as I know, ear clipping works with any kind of 2D shapes. And it definitely works with the shapes you have.

##### Share on other sites
You may look [url="http://www.geometrictools.com/SampleFoundation/Triangulation/Triangulation.html"]here[/url] and check out Dave's article and code snippet about ear-clipping (supports holes and nesting as well). Or look at Seidel's trapezoid approach, e.g. described [url="http://www.gamedev.net/page/resources/_/reference/programming/math-and-physics/polygons/fast-polygon-triangulation-based-on-seidels-al-r408"]here[/url].

##### Share on other sites
Thanks for such speedy replies.

[quote]As far as I know, ear clipping works with any kind of 2D shapes. And it definitely works with the shapes you have.[/quote] Yes ear clipping will divide my polygons into triangles, but not [b]similarly sized triangles[/b]. Just as ear clipping applied to a rectangle would not generate a nice triangluar mesh (just two triangles), it does not regularly triangulate a near rounded rectangle. Similarly with Seidel's algorithm.

Perhaps I am missing something, or not explaining myself clearly?
If I apply Seidel's algorithm to one of my clipped gibbeous lunes I get a triangulation like this
[attachment=1603:clippedlune02.jpg]
Whereas for a regular mesh what I need to do is cover this region with lots of mostly the same small triangle, with variations to allow for the line segments approximating the curved edges. What I have in mind is to split the shape into trapeziums and fill each with a strip of regular triangles, but I can't quite get my head around it.
End result wanted something like this

[attachment=1604:clippedlune03.jpg]

##### Share on other sites
Ah, I see. Try to look into tessellation.
Or maybe you could think about an own algorithm. Sorry, that's not very specific.... I'd add those extra vertices on a grid, chose what's valid, and make some marching algorithm. Okay, that's not very specific either....

By the way, what's your problem with the uneven triangulation? Vertex colors? Lighting? Physics?

##### Share on other sites
Perhaps this way: Think of an infinite mesh (build from the regular triangles) that is cut by a polyline. Insert new vertices wherever a polyline segment crosses a mesh edge. Make a new face from the original triangle and the polyline segments inside. Then you'll get a couple of inner ready-to-use triangles, and some small polygons at the inside of the polyline. The latter can be converted using one of the aforementioned algorithms.

##### Share on other sites
In this book, [url="http://www.amazon.com/Game-Engine-Design-Second-Interactive/dp/0122290631/ref=sr_1_2?ie=UTF8&qid=1299760230&sr=8-2"]http://www.amazon.co...99760230&sr=8-2[/url], there is an article about subdividing both uniform and non uniform surfaces. The authors website is at [url="http://www.geometrictools.com/"]http://www.geometrictools.com/[/url] which may help.