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.

Recast Settings Uncovered

Some folks have been wondering what is the meaning behind some of the Recast generation settings. Here's a quick primer how to derive the correct values.

First you should decide the size of your character "capsule". For example if you are using meters as units in your game world, a good size of human sized character might be r=0.4, h=2.0.

Next the voxelization cell size cs will be derived from that. Usually good value for cs is r/2 or r/3. In ourdoor environments, r/2 might be enough, indoors you sometimes what the extra precision and you might choose to use r/3 or smaller.

The voxelization cell height ch is defined separately in order to allow greater precision in height tests. Good starting point for ch is cs/2. If you get small holes where there are discontinuities in the height (steps), you may want to decrease cell height.

Next up is the character definition values. First up is walkableHeight, which defines the height of the agent in voxels, that is ceil(h/ch).

The walkableClimb defines how high steps the character can climb. In most levels I have encountered so far, this means almost weist height! Lazy level designers. If you use down projection+capsule for NPC collision detection you may derive a good value from that representation. Again this value is in voxels, remember to use ch instead of cs, ceil(maxClimb/ch).

The parameter walkableRadius defines the agent radius in voxels, ceil(r/cs). If this value is greater than zero, the navmesh will be shrunken my the agent radius. The shrinking is done in voxel representation, so some precision is lost there. This step allows simpler checks at runtime. If you want to have tight fit navmesh, use zero radius.

The parameter walkableSlopeAngle is used before voxelization to check if the slope of a triangle is too high and those polygons will be given non-walkable flag. You may tweak the triangle flags yourself too, for example if you wish to make certain objects or materials non-walkable. The parameter is in radians.

In certain cases really long outer edges may decrease the triangulation results. Sometimes this can be remedied by just tesselating the long edges. The parameter maxEdgeLen defines the max
edge length in voxel coordinates. A good value for maxEdgeLen is something like walkableRadius*8. A good way to tweak this value is to first set it really high and see if your data creates long edges. If so, then try to find as bif value as possible which happen to create those few extra vertices which makes the tesselation better.

When the rasterized areas are converted back to vectorized representation the maxSimplificationError describes how loosely the simplification is done (the simplification is Douglas-Peucker, so this value describes the max deviation in voxels). Good values are between
1.1-1.5 (1.3 usually yield good results). If the value is less, some strair-casing starts to appear at the edges and if it is more than that, the simplification starts to cut some corners.

Watershed partitioning is really prone to noise in the input distance field. In order to get nicer ares, the ares are merged and small isolated areas are removed after the water shed partitioning. The parameter minRegionSize describes the minimum isolated region size that is still kept. A region is removed if the regionVoxelCount < minRegionSize*minRegionSize.

The triangulation process greatly benefits from small local data. The parameter mergeRegionSize controls how large regions can be still merged. If regionVoxelCount > mergeRegionSize*mergeRegionSize the region is not allowed to be merged with another region anymore.

Yeah, I know these last two values are a bit weirdly defined. If you are using tiled preprocess with relatively small tile size, the merge value can be really high. If you have followed the above steps, then I'd recommend using the demo values for minRegionSize and mergeRegionSize. If you see small patched missing here and there, you could lower the minRegionSize.

I hope this helps a bit adopting Recast and Detour!

Height Detail Mesh Progress

I made some good progress over the weekend. I rewrote the code a couple of times and now it starts to be acceptable. I changed my crappy vertex insertion code to actual Delaunay triangulation code and the meshes looks far better now, and the speed is about the same.

The height detail mesh is not as accurate as the rest of the Recast functionality. But it gives great height approximation. If you want to make the character to follow terrain accurately, I'd recommend to use the navmesh height as starting point, add some offset and do a ray/sphere cast.

Now I have spent more time integrating the code to rest of the system and doing small rewrites here and there in order to move the data around easier. I'm currently working on the Detour side, making sure all the required functionality is there. Next up is smooth path tessellation so that it conforms the detail mesh and support for tile preprocess as well as tile navmesh. One little feature and a lot of support coding.

I have been recently neglecting to reply to project related emails which require longer replies. I try to arrange some time soon to make it happen. So if you are waiting for a reply, don't panic, I try to answer soon :)

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.

Recast and Detour Discussion

I just added a Google group for Recast and Detour questions, feedback and other discussion. You are of course welcome to comment on the blog topics here too.

http://groups.google.com/group/recastnavigation

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.

Navmesh Height Accuracy

I have spent some time recently to research different methods to improve the height accuracy of the navigation meshes. I had four ideas how I wanted to approach problem:

1. Subdivide the navmesh polygons to better conform the underlying terrain
2. Use subdivision based displacement mapping per navmesh poly
3. Use method similar to texture mapping per polygon
   
4. User callback function

Option number one would not require any changes to the run-time part, but it would cost both memory as well as performance, since the A* node count would increase.

Option two was my number one choice for a long time. The idea would be to have some sort of subdivision scheme which is easy to reproduce at runtime and store deltas per subdivision. In the end I rejected this since I could not find proper subdivision scheme that would work on polygons and slivers too.

The texture mapping approach would store a small heightmap texture per polygon or per couple of polygons much like lightmappers do. The additional awesomeness about this feature is that it would allow to embed other kinds of gameplay related information into the navmesh, such as how stealth the current location is, or stance value for the character, etc.

Some path finding solutions use the user callback mechanism and I might add that to Detour at some point too. The rationale behind that solution is that the height data can take a lot of memory and is often already stored somewhere.

After some failed prototypes with the tesselation approach I tried out the texture mapping and it seemed to work better, but not without its own set of problems. The image above shows first the raw navigation mesh and below is the texture mapped version.

The heigthfield texel size in the picture is roughly the width of the thin polygons on the bridge. The image shows less than a quater of the level, and the textures for that level take 128.3 kB. It should be possible to trim that number using some simple compression and omitting textures which are not really used.

If you have good pointers to simple texture compression schemes which allow fast random lookup, let me know! Bonus points for anything that allows fast bilerp too.

I have tried to make the textures so that the height is slight over estimation. That should make it easier to trace a perfect ground alignment. It is possible to later on add different downsampling schemes if necessary.

Currently there is a small texture stored per polygon. First I wanted to store a texture per region, but that turned out to be more complicated than I expected. When the texel size increases there starts to be more and more problems. Since the regions are non-convex, something like U-shaped staircase can create a lot of problems if you try to own sample it.

There are still some similar problems with the per polygon textures, but they reasonable to fix.

The next update of Recast and Detour will include the height texture feature. Hopefully out soonish. The code will be laid out so that the textures are optional.