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

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

## 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 on other sites
This is probably what you are looking for: Polygon Partitioning.

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

1. 1
2. 2
Rutin
19
3. 3
khawk
18
4. 4
5. 5
A4L
11

• 9
• 12
• 16
• 26
• 10
• ### Forum Statistics

• Total Topics
633768
• Total Posts
3013753
×