Slicing up geometry to create triangles When rendering object onto a screen, one must often cut up their objects into quads and triangles to allow the computer to process them and finally draw them onto a screen.
I am trying to slice up a given piece of geometry and end up with solely triangles. Since I am trying to incorporate something like this into a program, I am trying to find a general algorithm. I couldn't find any existing algorithms for this, so I had a go at it myself:

The problem I'm having with this is that I sometimes end up with a gap in my shape, and at the third step I don't know how to find the correct vertex to start at.
Some "rules":


*

*The object can have any number of vertices (although realistically speaking a limit of ~20 would suffice)

*The order of the vertices is known. This means the perimeter of the object is also known.

*The collection of triangles after applying the algorithm should have the same area and perimeter as the piece of geometry at the beginning. (So the collection of triangles should be the same shape)
The question is: is there a known algorithm for cutting up a single, closed shape into triangles (or quads)?
I don't know if this question is truly appropriate for the math exchange, but I hope someone here has done this before, or knows how to as I'm stuck.

This is called polygon triangulation. There are simple algorithms to solve it. I have some C code, in fact.
