**1**

# Polygon Triangulation For Regular Mesh

Started by Dave Blake, Mar 09 2011 07:11 AM

6 replies to this topic

###
#1
Members - Reputation: **122**

Posted 09 March 2011 - 07:11 AM

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:

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?

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:

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?

###
#4
Members - Reputation: **122**

Posted 09 March 2011 - 09:33 AM

Thanks for such speedy replies.

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

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

Yes ear clipping will divide my polygons into triangles, but notAs far as I know, ear clipping works with any kind of 2D shapes. And it definitely works with the shapes you have.

**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

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

###
#5
Members - Reputation: **2665**

Posted 09 March 2011 - 10:57 AM

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?

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?

###
#6
Crossbones+ - Reputation: **6995**

Posted 09 March 2011 - 11:21 AM

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.

###
#7
Members - Reputation: **137**

Posted 10 March 2011 - 06:32 AM

In this book, http://www.amazon.co...99760230&sr=8-2, there is an article about subdividing both uniform and non uniform surfaces. The authors website is at http://www.geometrictools.com/ which may help.