Thursday, August 20, 2009

Navmesh Height Accuracy pt. 5

So fitting the detail mesh into the tiled preprocess was not as painless as I hoped. The problem is that the detail mesh requires the edges of the polygons to align perfectly as well as it requires the heightfield present to pull the date from.

While the tiled process has all kinds of good properties, one thing that was quite complicated to get right was how to handle T-junctions between the tiles. The region partitioning system can create extra vertices along the tile edges. Just imagine open field, with one obstacle. Most of the tiles will be just one region, whilst the tile which has the obstacle will be split into several regions. That extra region would create T-junctions along the tile edges.

The way I handled this earlier was just that first I rasterized all the tiles, one at a time, and stored the region contours, which is just little amount of data per tile. After all tiles had been processed, I would post process all the neighbor contours so that they equal vertices along the tile edges. After that, I would build a the polygon mesh from the contours.

That was all fine back them. But now, the detail mesh generation requires the heightfield and matching contours to be present at the same time. And keeping the heighfield in memory is not an option since there just is not enough of it in some cases.

Well, the past day or two I have been working slightly different approach to the per tile generation. We will see how it will turn out. I have had quite a few dead ends recently, so I'm prepared that it will fail :) The idea is that first I will detect the extra vertices along the tile edges and then I would remove them from the polymesh and then generate the detail mesh. Since there are minimum number of vertices per tile edge, there is no T-junctions. That way I do not need to fix up the contours in second pass and all is good again.

It took me a while to come up with this solution, even if it sounds like the best thing to do. I guess I'm just subconsciously trying to dodge every solution which requires adding or removing a vertex from triangle mesh and keeping the resulting mesh still valid.

I don't want to make a quad-edge mesh thing-a-magic just for few vertices that needs to be removed and the code to handle vertex removing and triangle patching on simple flat mesh structures is just pain it the arse. If someone has good pointers how to remove a vertex from 2D trimesh and keep the remainder of the mesh in good shape (no overlaps, etc), let me know.

Adding the detail mesh has been quite a journey. There has been many more detours on the way than I expected. It's been awesome ride, nonetheless.


  1. having navigation mesh always "on" actual surface will be enough for me ))

  2. hm, it's impossible. maybe just trace from upper point....

  3. Yeah, it is. But the height detail mesh will give you better estimate where the surface will be. I deally I would like to guarantee a certain threshold, but a couple of things in the current version does not allow that.

    Yet, I think that if you need to do more precise traces using physics geom, you can use the detail mesh + agent climb (or half agent height) as starting point and you should get good results.