Today, I want to present you my Triangulation algorithm.
There is solutions on Internet, so Why? Because, I cannot find best suited solution I need. Maybe I didn’t dig enough, but clearly, my solution works 🙂
It is actually used in Alone In The Dark and Test Drive Unlimited games on PS3, XBOX360 and PC…
Ok, what is a Triangulation algorithm?
Well, in my case, I have a plane shape with multiple points and I want to draw this shape in a 3D game.
Condition: alls points must be in the final shape.
Our graphics cards only know how to draw triangles. So I need to make Triangles, but how?
As you see, there is a lot’s of solutions:
What is the worst, the best?
I have a personal advice: in a 3D games, there is always little visuals artifacts on the triangle’s edges… Edges are difficult to keep clean. So my solution decreases the edge length.
Here, edges length is = D1 + D2 + D3 + D4
Here is my algorithm:
Put all the external edges length in an array indexed by the number of point :
My algorithm is very fast and very simple… The result of Delaunay’s Triangulation is better for optimizing surfaces, but mine is better for edge length.
For concave polygon, you just need to set an infinite edge length when the point is inside. Let me know in comment if you need more about it.
That’s all for today.