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

This is probably what you are looking for: Polygon Partitioning.

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

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).

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