Advancing Front Triangulation

I was supposed to finish the tower defence game for mobiles but then I saw this:

Low Poly Sheep

I was so impressed what people could do with so few polygons and I thought it would be fun to code something low poly. Low poly art seems to be kind of trendy now as well. Retro from the 90’s when demos & games had to minimise the number of polygons for performance reasons. Anyways, the polygons are flat shaded, meaning, one triangle has the same color. To obtain this we can just set each vertex normal in a triangle to the same. It also seems like many artworks added ambient occlusion to their pieces, this gives some more depth to the world. Anyways, I started out by trying to create a sheep in Blender (first time for me) and throwing it into a low poly world.

Starting in 2.5d

I generated the trees and clouds by adding faces to a icosahedrons. The ground was generated from random points heighten by 2d Simplex Noise and a Delaunay triangulation (used jshull). It looked like this, crappy but with potential:

Moving to 3d

This was all experimental and inspiring. The triangulation worked in 2d but not 3d so I became curious of how to do this in proper 3d. My first attempt was to find a Delaunay triangulator for 3d, it turned out to be harder than I though. I learnt that the nice properties of 2d Delaunay didn’t transfer easily to 3d. So I though it would try some different other ways.

First I tried marching cubes triangulation, but I was not very happy with the result so I moved on.

Second I tried Surface Nets, it generates quads and has problems with sharp edges and looked something like this on Simplex Noise:

:

After reading more about this I found out that many are using Dual Marching Cubes. So I decided to try that by adapting Jmonkeys port from Ogre3d. The implementation builds an Octree that narrows down the features in the model. The result was encouraging:

However you could still spot traces of the cubes and there were some quirks (memory usage, not always connecting Octs properly and a general unsatisfaction with not have written the code:) )

Advancing Front

So for fun I decided to give it a shot. After some thinking I decided to do it by traversing the surface and build triangles as I went along. I later found out that this approach is called “Advancing Front”. Advancing Front generally generates high quality meshes and are pretty efficient. A downside is that it doesn’t find unconnected meshes, you will have to find that by random sampling and following gradients. The upside to the downside is that you don’t have to look at huge empty or solid spaces (like marching cubes).

It requires a gradient or surface normal to be calculated so we know how to move along the surface. I made it for implicit surfaces where solid > 0 and empty <= 0. E.g. SimplexNoise(x,y,z) = density [-1 – 1]

Anyways the method roughly works like this:

1. Find a surface point, A

2. Create and edge between A and another nearby point, B

3. Push the edge on a Queue

4. While Queue is not empty

4.1 Pop edge, from the edge midpoint move along the surface (within error margin)

4.2 Snap new surface point to previous nearby surface point, if any

4.3 Create a new triangle and push new edges to Queue

That is a very simplified overview, 4.3 either generates 0,1 or 2 edges. 0 if it’s closing a triangle with 3 common edges, 1 if it’s closing a triangle with 2 common edges and 2 if it generates a completely new triangle.

There are still some quirks left but at least I now know exactly what the code does 🙂 I am very happy with the quality of the generated meshes. Also I feel confident that it’s/can be made memory/cpu friendly.

I might do a little video later!

I don’t knwo what I will do with this though, but I might try to add physics to it. Generating a nav mesh is simple too, but I should really finish some old projects….

Here is a follow up post.