Triangulation algorithm for video games

Hi,

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.

tri1

 

 

 

 

 

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:

tri10   tri9   tri7

 

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.

 

tri11

 

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 :

tri6 For example, this is the edge of the point 5, so Array[5] = D5

tri3 Calculate all these edges length

 

tri4 Here is the smallest : the edge of the point 6

tri5 Remove this point of your array and recompute the edge length of point 5 and 7 (no need to recompute all).

tri6 Restart to find the smallest edge length and remove it…

tri7 When you have finished, your triangulation is done

 

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.

ZeroKcm

5 thoughts on “Triangulation algorithm for video games

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *