Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


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.

  • You cannot reply to this topic
6 replies to this topic

#1 Dave Blake   Members   -  Reputation: 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:
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?

Sponsor:

#2 szecs   Members   -  Reputation: 2176

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.

#3 haegarr   Crossbones+   -  Reputation: 4437

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.

#4 Dave Blake   Members   -  Reputation: 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
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

clippedlune03.jpg

#5 szecs   Members   -  Reputation: 2176

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?

#6 haegarr   Crossbones+   -  Reputation: 4437

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.

#7 lotusf1   Members   -  Reputation: 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.



PARTNERS