Sign in to follow this  

How can I create a triangle list from a set of points (polygon) a.k.a Tesselation ?

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I'm trying to make my own 2d engine and I like to add some capability to draw a polygon from a set of points or linestrip. I use DX and it seems like a simple task, divide the 2D polygon into triangles and render it.. Let's say I don't wanna know about the tex coordinate yet, I just wanna be able to render a 2D polygon on the screen (not just quad guys), how can I create a triangle list from those polygon points ? Creating a triangle fan is the easiest one but it may cause overlapped triangles. I've been googling for awhile with no result since probably I don't know what keyword to use. can someone help me with this ? [Edited by - yanuart on February 11, 2005 12:55:55 PM]

Share this post


Link to post
Share on other sites
In my graphics class I used the Ear Cutting algorithm. Here's a page that gives a description of it:

http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/applet1.html

Basically the idea is that you go around the polygon and take 3 points at a time, determine if those points make an "ear". Meaning that the triangle formed my those three points is contained by the polygon.

One way to determine if the triangle is an ear is to take the three vectors a->b, b->c and c->a and do the cross product of these vectors. This will give you a vector normal to the triangle. If the triangle's normal is in the same direction as the normal for the polygon, it's an ear. If it's in the opposite direction it's not. It's critical that you do the cross products in the correct order.

If you need to calculate the normal of the polygon, you can do the same trick buf all the way around the polygon. You take the vector from each point to the next one, and do the cross product all the way around.

I've found that when comparing the vectors, you often want to leave a certain amount of fudge factor in there, because the calculations may not come out EXACTLY the same. But it's ok because it should either point one direction or 180 degrees from that direction.

Now if you've determined that you have an ear, you add those three points to your triangle list, then you remove the center point from the polygon. You repeat this process until you just have 3 points left.

Hope this helps,

No Operation

Share this post


Link to post
Share on other sites
Ear cutting is O(n²), which might be too slow, if you want to process large polygons. Horizontal decomposition according to Seidel's algorithm is O(n log n), which is better (source is available on the linked page). Of course, it won't really matter for very simple shapes.

Both algorithms assume non-overlapping polygons. If you want to triangulate pretty much any kind of polygonal input, including overlapping and intersecting shapes, then check out Fast Industrial-Strength Triangulation by Martin Held (warning, it's pretty complex).

Share this post


Link to post
Share on other sites
well I decided to use gluTesselate function from GLUT lib to do triangulation :D.. it's easier that way but I'll check out those algorithms you gave me.. it'll be a nice thing to read at spare times

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this