• Create Account

## Polygon Triangulation For Regular Mesh

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

6 replies to this topic

### #1Dave Blake  Members

122
Like
0Likes
Like

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?

### #2szecs  Members

2822
Like
1Likes
Like

Posted 09 March 2011 - 07:14 AM

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

### #3haegarr  Members

7188
Like
0Likes
Like

Posted 09 March 2011 - 08:12 AM

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.

### #4Dave Blake  Members

122
Like
0Likes
Like

Posted 09 March 2011 - 09:33 AM

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.

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

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

### #5szecs  Members

2822
Like
0Likes
Like

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?

### #6haegarr  Members

7188
Like
1Likes
Like

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.

### #7lotusf1  Members

137
Like
1Likes
Like

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.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.