The math in Gamedev is simple. Triangulation and Triangle.Net in Unity
Hello! My name is Grisha, and I am the founder of CGDevs. Mathematics is a very cool tool when developing games. But if we say, in principle, it's difficult to do without understanding vectors and matrices , then triangulation algorithms are not so necessary thing, but with the help of them a sufficiently large number of interesting problems are solved. Today I would like to talk about a rather important tool in computational geometry, such as triangulation and their application in the gaming industry. In addition, I wrote a port and a few wrappers of the great Triangle.Net library for Unity. If interested - welcome under cat. Link to githab is attached.
In general, triangulation is a partition of a geometric object into triangles. This concept in itself is quite simple. The basic example of triangulation in the case of game engines is the mesh. Strictly speaking, a mesh can consist not only of triangles, but in game engines, for a variety of reasons, it is meshes consisting of triangles that are taken.
Triangulations are different, but one of the most popular types of triangulations is Delaunay triangulation. This type of triangulation is distinguished by the property that in the circle described around each triangle, there are only the vertices of this triangle.
In general, outside the gaming industry, a large number of problems are solved using triangulations. In game dev, the first task that comes to mind is the navigation mesh. Navmesh is a data structure that determines which space a player can walk. It allows you to avoid such complex computational problems as determining collisions with a part of the environment.
The second interesting problem solved with the help of the Delaunay triangulation in a game dev is the generation of terranes and objects represented as a set of points. The main advantage of Delaunay triangulation in this case is that, based on its properties, it allows you to avoid very sharp triangles that will interfere with and create artifacts on the tyrrain.
In addition, using the Delaunay triangulation with constraints and algorithms such as Chew's second algorithm and Ruppert's algorithm, it is possible to generate grids even better for tirrains and generate good grids for another application - the finite element method.
The finite element method itself is one of the methods by which applied physics problems are solved. In geymdev it allows you to solve many problems associated with the simulation of deformation, fluid simulations and another used for specials. effects. Usually for recording effects in animation, since for real-time the method has too high computational complexity. An important detail when using the method is that the error of the method depends on the angles of the triangles in the grid. If there are very sharp corners in the grid, the method gives a huge error; for this reason, the algorithms listed above are needed.
And of course, procedural meshes generation in general. As an example in the githab project there is a scene with the ability to draw meshes. Some physical puzzles use this application as a basic mechanic. But in addition, triangulation algorithms allow using procedural generation to solve problems such as procedural destructibility and so on.
In addition to gamedev, triangulation is used in networks, computer vision, various analytical algorithms, as well as in some problems of computational geometry, as the union and exclusion of polygons from each other (which is often useful in tasks arising in the development of games)
Perhaps one of the easiest triangulation algorithms. Gives not the best grid and has a large computational complexity O (n ^ 2) in the worst case.
Read more about it in this article.
An algorithm that generates a Delaunay triangulation on a set of points. In general, as with most Delone algorithms, when correctly implemented, the algorithmic complexity is O (n log n), where n is the number of vertices. But in some cases it can occupy O (n ^ 2).
The downside to Ear Clipping is that this algorithm builds a convex triangulation and in the basic implementation does not imply holes in the resulting grid.
Chew's second algorithm and Ruppert's algorithm are algorithms that allow you to impose restrictions on the Delaunay triangulation and set the minimum angle of a triangle in the grid. An important detail of the algorithms is that they can go into an infinite loop and are guaranteed to give a result at angles between approximately 20.7 degrees and 29 degrees. The ability to set the minimum angle is important when solving the tasks described above.
Chew's second algorithm is implemented in the free package www.cs.cmu.edu/~quake/triangle.html and its port on .Net archive.codeplex.com/?p=triangle
Well, since with the help of triangulations, you can solve so many cool tasks, then at the holidays I wanted to implement my own wrapper for Unity so that I always have a handy tool at hand. In this implementation, the triangulation algorithm works on average for O (n), and at worst, for O (n * log n), where n is the number of vertices. For example, when testing for 1k vertices, the units randomly scattered across the square in the editor on the Intel Core i7-8700 built the grid in an average of 7.56 seconds.
The main differences from the original library in the presence of methods extensions sharpened under Unity, as well as replacing double with float in the entire library (+ a couple of specific operators for cast) Double in a unit does not make much sense. If we consider physical simulations, then I would use a separate application on the plus library, and the result of the calculations was already given to Unity purely for visualization. And also renamed the Mesh type to TriangleNetMesh, so as not to knock off the Mesh from Unity. Yes, they are already in different namespaces, but nevertheless I think the newbies would be a little bewildered by the fact that we get another with the help of one Mesh.
The essence of the library is that you first have to define a so-called polygon. Then, on its basis, generate a mesh. In order for this to work with unit data structures, several extension methods have been introduced.
To demonstrate and use examples, a special demo scene was made with the ability to draw meshes. With it and the library port can be found in the github project.
Thanks for attention! I hope that the port and the article will be useful to someone and it became a little clearer why we need triangulation and knowledge of mathematics in general. I will try to continue to disclose the use and methods of solving various mathematical problems in game dev. In the computational geometry itself there is still a lot of interesting, but in addition there are many other interesting sections of higher mathematics.
What is triangulation?
In general, triangulation is a partition of a geometric object into triangles. This concept in itself is quite simple. The basic example of triangulation in the case of game engines is the mesh. Strictly speaking, a mesh can consist not only of triangles, but in game engines, for a variety of reasons, it is meshes consisting of triangles that are taken.
Triangulations are different, but one of the most popular types of triangulations is Delaunay triangulation. This type of triangulation is distinguished by the property that in the circle described around each triangle, there are only the vertices of this triangle.
What are they needed for?
In general, outside the gaming industry, a large number of problems are solved using triangulations. In game dev, the first task that comes to mind is the navigation mesh. Navmesh is a data structure that determines which space a player can walk. It allows you to avoid such complex computational problems as determining collisions with a part of the environment.
The second interesting problem solved with the help of the Delaunay triangulation in a game dev is the generation of terranes and objects represented as a set of points. The main advantage of Delaunay triangulation in this case is that, based on its properties, it allows you to avoid very sharp triangles that will interfere with and create artifacts on the tyrrain.
In addition, using the Delaunay triangulation with constraints and algorithms such as Chew's second algorithm and Ruppert's algorithm, it is possible to generate grids even better for tirrains and generate good grids for another application - the finite element method.
The finite element method itself is one of the methods by which applied physics problems are solved. In geymdev it allows you to solve many problems associated with the simulation of deformation, fluid simulations and another used for specials. effects. Usually for recording effects in animation, since for real-time the method has too high computational complexity. An important detail when using the method is that the error of the method depends on the angles of the triangles in the grid. If there are very sharp corners in the grid, the method gives a huge error; for this reason, the algorithms listed above are needed.
And of course, procedural meshes generation in general. As an example in the githab project there is a scene with the ability to draw meshes. Some physical puzzles use this application as a basic mechanic. But in addition, triangulation algorithms allow using procedural generation to solve problems such as procedural destructibility and so on.
In addition to gamedev, triangulation is used in networks, computer vision, various analytical algorithms, as well as in some problems of computational geometry, as the union and exclusion of polygons from each other (which is often useful in tasks arising in the development of games)
Ear Clipping with Holes
Perhaps one of the easiest triangulation algorithms. Gives not the best grid and has a large computational complexity O (n ^ 2) in the worst case.
Read more about it in this article.
Bowyer – Watson algorithm
An algorithm that generates a Delaunay triangulation on a set of points. In general, as with most Delone algorithms, when correctly implemented, the algorithmic complexity is O (n log n), where n is the number of vertices. But in some cases it can occupy O (n ^ 2).
The downside to Ear Clipping is that this algorithm builds a convex triangulation and in the basic implementation does not imply holes in the resulting grid.
Delaunay refinement processing
Chew's second algorithm and Ruppert's algorithm are algorithms that allow you to impose restrictions on the Delaunay triangulation and set the minimum angle of a triangle in the grid. An important detail of the algorithms is that they can go into an infinite loop and are guaranteed to give a result at angles between approximately 20.7 degrees and 29 degrees. The ability to set the minimum angle is important when solving the tasks described above.
Chew's second algorithm is implemented in the free package www.cs.cmu.edu/~quake/triangle.html and its port on .Net archive.codeplex.com/?p=triangle
Triangle.Net for Unity
Well, since with the help of triangulations, you can solve so many cool tasks, then at the holidays I wanted to implement my own wrapper for Unity so that I always have a handy tool at hand. In this implementation, the triangulation algorithm works on average for O (n), and at worst, for O (n * log n), where n is the number of vertices. For example, when testing for 1k vertices, the units randomly scattered across the square in the editor on the Intel Core i7-8700 built the grid in an average of 7.56 seconds.
The main differences from the original library in the presence of methods extensions sharpened under Unity, as well as replacing double with float in the entire library (+ a couple of specific operators for cast) Double in a unit does not make much sense. If we consider physical simulations, then I would use a separate application on the plus library, and the result of the calculations was already given to Unity purely for visualization. And also renamed the Mesh type to TriangleNetMesh, so as not to knock off the Mesh from Unity. Yes, they are already in different namespaces, but nevertheless I think the newbies would be a little bewildered by the fact that we get another with the help of one Mesh.
The essence of the library is that you first have to define a so-called polygon. Then, on its basis, generate a mesh. In order for this to work with unit data structures, several extension methods have been introduced.
Usage example
publicvoidGenerateMesh()
{
if(_CurrentState != MeshDrawerState.Nothing) return;
Polygon poly = new Polygon();
poly.Add(_Contour);
foreach (var hole in _Holes)
{
poly.Add(hole, true);
}
var triangleNetMesh = (TriangleNetMesh) poly.Triangulate();
GameObject go = new GameObject("Generated mesh");
var mf = go.AddComponent<MeshFilter>();
var mesh = triangleNetMesh.GenerateUnityMesh();
mesh.uv = GenerateUv(mesh.vertices);
mf.mesh = mesh;
var mr = go.AddComponent<MeshRenderer>();
mr.sharedMaterial = _MeshMaterial;
var collider = go.AddComponent<PolygonCollider2D>();
collider.points = _Contour.ToArray();
var rb = go.AddComponent<Rigidbody2D>();
rb.mass = triangleNetMesh.Triangles.Sum(tris => tris.Area);
Clear();
}
To demonstrate and use examples, a special demo scene was made with the ability to draw meshes. With it and the library port can be found in the github project.
Thanks for attention! I hope that the port and the article will be useful to someone and it became a little clearer why we need triangulation and knowledge of mathematics in general. I will try to continue to disclose the use and methods of solving various mathematical problems in game dev. In the computational geometry itself there is still a lot of interesting, but in addition there are many other interesting sections of higher mathematics.