blog games developers documentation portfolio gallery

Documentation:

Simplification process

SimpleLOD does not use any of the known libraries nor any of the known methods for mesh simplification. We're kind of stubborn and are proud of that :-) We think there are plenty of ways to decimate a mesh when you use common sense.

So let's go through the process that SimpleLOD uses.

Meshes are evaluated per triangle and as a starting point we assume that all triangles can be merged. Each triangle starts with a weight of 0. So when we would leave it at that, every mesh would end up as 1 triangle.

In the process we build up those weights and if they exceed a certain level, the triangle is left alone. This maximum weight value is passed as a parameter to the function Mesh LODMaker.MakeLODMesh(Mesh original Mesh, float maxWeight);

Here's how we build up those weights:
First we loop through the vertices searching for doubles. When a vertex has a twin brother in the exact same location, this usually means it should stay in place (think of a cube with 6 sides, each side 4 corners = 24 vertices in triplets). The weight of the vertex is increased when the normals are different (think of the cube again, each of the 3 vertices in one corner have a different normal) and when the uv coordinates are different. This last fact is very important, because merging 2 identical vertices that have different uv coordinates would result in weird texturing on the mesh and you would notice it immediately.

A triangle has 3 corners, numbered 0, 1, 2. When a triangle is merged with an adjacent triangle, it is flattened. There are 6 ways to do this. Move corner 0 -> 1, 1 -> 2, 2 -> 0, or in the opposite direction move corner 1 -> 0, 2 -> 1, 0 -> 2. Flattening a triangle will cause the adjacent triangle to grow.

After the vertices we loop through the triangles and add weights to each of the 6 flattening options per triangle:

0. Add the vertex weights to each transformation pair for each corner

1. Area of the triangle using the normalized mesh.
The bigger the area of a triangle the less likely it is to be flattened. This weight is the same for all 6 options

2. Length of the sides
Again we use the length of the sides of the normalized mesh. The longer a side the more impact it will have to flatten it along that side. This will give different weights to 3 pairs of flattening options.

3. Normals of 3 corners
When the normals of all 3 corners are equal, flattening the triangle wil probably not have too much effect on the shape of the mesh. But when they differ and the triangle is flattened, the mesh will become less smooth. So the bigger the difference between the normals the bigger the weight. This will again give different weight to 3 pairs of flattening options.

4. Total angle of adjacent triangles per corner
Most triangle corners are shared with other triangles. The total angle of these triangles is computed. When it is 360 degrees, the triangle corner is somewhere in the middle of a surface (there are other possibilities, but we keep it simple). When it is 180 degrees, the triangle corner leis at the side of the surface. By adding weights to the corners when they differ from 360 degrees, we prevent making dents in the sides of a mesh and prevent chopping of corners.

5. Total angle of adjacent triangles per corner before and after flattening
Since it is so important not to deform the mesh, we also compute the total angle of the corners of the triangle that share the same corner after we would have flattened our triangle. When the total angle before and after differs, a weight is added again.

6. Projected movement on normal
When we project the movement of a triangle corner on its normal, we can measure how much the mesh would be deformed by the flattening operation. The longer the projected vector, the more weight is added

7. Changing the total area
When we flatten a triangle by moving one corner towards the other and it is inside a flat surface, the total area of all adjacent triangles will remain the same. But when we do this on a curved surface or when the triangle corner lies on an edge of the mesh, the total area will change. The more it would change, the more weight we add.

8. Stretching the UV map
We do the same for the UV map. When we flatten a triangle by moving one corner towards the other and it is inside a flat surface that is UV mapped evenly, the total UV area of all adjacent triangles will remain the same. But when the UV map is not so regular or when the surface is not flat, the total UV area will change. The more it would change by any of the 6 operations, the more weight we add.

Compare weights
We are now ready with adding weights to the 6 flattening options. The option with the smallest weight that is below the maxWeight will be executed. This will also change all adjacent triangles.

Each individual triangle has now been flattened, has grown (due to the flattening of its neighbor) or has been left unchanged. We delete all triangles that are flat, delete all vertices that are unused and build a new mesh.





follow us