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.