Navmesh Height Accuracy pt. 3

Third time the charm, I guess.

Whilst the subdivision based method worked well, I was not too happy about the memory usage and how complicated the data ended up being. So inspired by the blog comments I thought I will give simple detail trimesh a try. The idea is that there is tiny trimesh per polygon which is only used for the height calculations.

The naive proto code to calculate the detail mesh is about 10x slower than just the subdivision. Gladly there are plenty of opportunities to optimize it. The above mesh took about 16ms to calculate. The memory consumption is 26kB for the above scene versus 42kB with the subdivision data. There are some room for optimization there too. Some of the vertex data is not shared for example.

I'm not still 100% happy about the detail mesh generation process. My first approach was to initially create dense trimesh using the subdivision method I presented earlier and then simplify the mesh. Deleting vertices from a trimesh is always painful process, and while I got it working OK, deciding which vertices to remove was not so simple task. I wanted something simple, but the code started to look like full blown mesh decimation library, so I ditched the idea. In addition to the complexity of the implementation, there were seams at the borders of the polygons.

My second approach was to insert vertices instead of removing them. The approach is somewhat similar to Fast Polygonal Approximation of Terrains and Height Fields, just a bit simpler and a hint more brute force. First I tesselate and simplify the edges of the nav polygon to make sure the detail meshes match at the boundaries and then the resulting polygon is triangualted. Then I calculate a set of samples and insert them as vertices into the mesh, starting from the most distant sample, until all the samples are within certain error distance to the mesh.

I hope this solution will be the final one. Need more testing to see if the detail meshes align correctly and work in all cases. And I thought this problem was the easiest one on my todo list.