Sunday, August 9, 2009

Navmesh Height Accuracy pt. 2

The heightmap texture idea turned out to be a lot more complicated than I expected. It works fine with dense texture data, but totally breaks when you have lower resolution textures. The grand idea was to use bilinear interpolation to find the height at given location inside the polygon.

The silly thing with that kind of interpolation is that it needs samples outside the polygon too, and figuring out those samples becomes more and more complicated the lower the resolution of the texture map. It is very easy to fill in extra samples using dilation, but making sure that the interpolated samples match at the polygon boundaries turned out too difficult a task.

Above is a picture which show a common problem case. On left you can see the original navmesh. On right you can see what happens when the mesh is tesselated and vertex heights are sampled from the height map. A lot of discontinuities there and on certain locations height is just plain wrong. The way the interpolation breaks is a bit different at different resolutions.

No matter what kind of data I tried to put into the texture and how I tried to sample the texture, there always seems to be stupid corner cases where the technique just fails.

The texture idea is definitely tempting, maybe it can be used for something else later on.

After all, the main rule of thumb for this kind of auxiliary data is that every bit of data should give a bit better result, not vice versa.

Now that I was not happy with the texture approach, I though I will give another go at the tesselation idea. The problem with that technique initially was that I could not find any tesselation algorithm which would work well with arbitrary convex polygons. Simple edge midpoint and polygon centroid subdivision schemes would be trivial to implement, but they are exceptionally horrible with sliver polygons.

The main properties of the tessellation algorithm I was looking for are as follows:
  1. It should work with arbitrary convex polygons
  2. It should create relatively uniform tesselation
  3. The tesselation at the borders of the polygons should match given same tesselation threshold
  4. The resulting aux data that will create same tesselation at runtime should be as small as possible
I have tried to solve this problem earlier, but I never really came up with good solution with slivers. So that was the first thing I tried to solve. Below is a image which shows different stages of the subdivision process I came up with. I might have reinvented the wheel, but I have not seen similar technique earlier.

The basic idea behind the subdivision scheme is that you split the polygon from the mid point of the longest edge of the polygon to the opposite side of the polygon. The split point on the opposite side is either the start, midpoint or end of the edge depending which one is closest to point which is boundaryLength/2 away from the split start point along the polygon boundary. Then the process recurses on both sides of the polygons.

Once all the edges of the polygons are less than the tesselation threshold, then the polygon is split along the shortest diagonal until the result is a triangle. Take a look at the code for more details.

This is how it looks when applied to the problem case of the heightfield texture at different resolutions. Now any added data will improve the result!

Here's the example case from previous post with the tesselation technique.

The subdivision method also allows quick point location within the tesselated polygons. Since the polygon is always subdivided using a single plane, it is possible to only tesselate that side on which the sample point lies and as the final result is a triangle it is triavial to find the correct height.

My idea is to precalculate the subdivision "stack" and store the split indices and height offsets per iteration. I'm still playing around how to store this data in a compact way. 32bits per iteration should be enough.

And as an added bonus (I love added bonuses!), it is possible to implement this method as a filter to the poly mesh too before it is passed to the pathfinder, so those who need more finely tesselated navmeshes can benefit from the tesselation technique too.


  1. Hey great work!
    "32 bits per iteration" means 3 chars and a float scaling factor at each navigation-node?

    I still don't think the extra data is that much after the a lot of sub polygons are merged together (with an given error tolerance).
    Have you tested it?

  2. The compact subdivision data for the larger level example takes 126kB, where the texture version of the same scene took around 128kB. Some scenes require a little less data. Generating the tesselation is really fast. I could not speed up the point location as much I hoped.

    I'm not too thrilled on writing a mesh simplification code, but I think I will give your idea a try. The subdivision data is quite tricky, and I would not mind having much simpler data at slight extra cost.

  3. Are you going to check in the current version as trunk? I have some ideas about the mesh simplification.

  4. - about my dynamic navmeshes with Recast

  5. I personally prefer callback approach. But reacast merge navmesh polygons ... if it will be possible to dont merge voxels with different callback, it will be ideal case imho. Tesselation will slow down A*. For example, on heightmap without obstacles we need only one polygon per tile, but with tesselation it will be very dense mesh. Or you want to have to data sets, one for A*, second for query height?

  6. Yakov, the tesselation will be available as separate detail mesh for height queries or you can also tesselate the navigation mesh. Usually (especially for games) it is better to have the detail mesh for height only in order to have better performance as you said, but in certain cases you may want to associate some extra data per polygon and more finely tesselated navmesh might be more useful.

    I will add support for both as it is not really a big deal to implement them.

  7. looks like best solution.. callbacks needs additional trace to collision geometry, maybe it will slow with complex dynamic environment