# Polygon Triangulation For Regular Mesh

This topic is 2833 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 here 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 here.

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

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 similarly sized triangles. 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.

1. 1
2. 2
3. 3
Rutin
15
4. 4
khawk
13
5. 5
frob
12

• 9
• 9
• 11
• 11
• 23
• ### Forum Statistics

• Total Topics
633663
• Total Posts
3013236
×