Rough Fringes

I though I'd start this time with something else than a boring screenshot. This is how it looks like over here right now. I'm still hoping that I could reclaim my snot producing organ back to its more purposeful function. Getting much better, though. Should be back in the regular action next week (so less blog posts ;).


Holes in the Navmesh

There has been one bug popping every now and then, which is pretty nasty to fix. The problem is input geometry that has short steep slopes, usually in form of bevels or some sort of decorative geometry. The result is that those polygons will create one or two voxel holes around the edges and as a result you get holes in the navmesh. Over conservatism not for the win in this case.

When Recast processes the input geometry to voxels and detect walkable areas, it uses two criteria, surface slope and step height. Step height is there to allow to climb over sharp features of the input geometry and slope is used to detect contiguous "flat-ish" regions.

There are two ways to detect slopes from input geometry. Firstly, you could detect the angle of the input polygons and mark the ones with steep slopes and non-walkable, secondly, you could run a filter over portion of a voxelized region and detect the slope from that.

The second option is more flexible, but too costly and from my past experiments I noticed that it is quite prone to noise in the input resulting other kinds of unwanted holes in the mesh. The first option is considerable faster and it is the methods used in Recast.


The Current State of Affairs

I made following test case to highlight this problem. All the obstacles but F have such height that the agent should be able to walk over them. Obstacle A is simple box with beveled edges. Obstacles B-E are the same shape, B is twice the size of the others, C is on ground, D is above to ground but still low enough for the agent to walk over, and E is two obstacles stacked on top of each other.


And here's the resulting mesh. Not very nice to look at. The other two images show first the voxels, and then the input geometry. The red polygons in the input mesh are considered too steep slopes. The dark red voxels mark non-walkable areas.



And here's a close up of three of the culprits. The problem is that because of the voxelization, sometimes the whole voxel can belong to a polygon which is marked as non-walkable.


There is already some code which tries to favor walkable surfaces over non-walkable if they are really close to walkable ones. The very first solution to fix the problem in hand would be to extend that.

Instead if really small distance--previous the threshold was 1 voxel--we could increase the favoring distance up to step height of the agent. The resulting mesh after the change is as follows.


A bit better. Some cases got fixed completely. Obstacles which are not directly connected to a walkable ground still have problems. The next step is to go through all the voxels and check if there is a walkable surface just below it at max step height from the current voxel surface. This fixes pretty much all the remaining problems. The filtering can be done by calling rcFilterLowHangingWalkableObstacles()



Filtering Neighbours

There are certain cases where this procedure can try to cut corners too much. Even without the new additions, the step height check sometimes produces too optimistic situations. The problem so far has been that the step height only tests between to neighbours.

If there are many voxels next to each other which all require large steps, then the algorithm could walk steep ledges. If this information were to come from sloped polygons, the neighbours would have been marked as non-walkable.

So I also added a fix for this case, since it is more likely to happen with the newly added code. The magic happens in rcFilterLedgeSpans() and it marks voxels which have step requiring neighbours at opposite directions as non-walkable. Finding neighbours of rcHeightfield is really costly, so I combined this function to another filter which already requires neighbours.

Below is an example of a case that this new test fixes. The corner at the middle of the edge comes from the fact that the character can stand closer to the base of the pedestal up to the peek than at the downhill where the bottom part of the base becomes wall too.