rcFilterLowHangingWalkableObstacles Study

[liubai01]

This docs summarizes the discussion in my reading group over rcFilterLowHangingWalkableObstacles.
The purpose of this post is to figure out that:

• What is filtering low hangs ?
• Why we need filtering low hangs ?

What is filtering low hangs?

Intuitively, rcFilterLowHangingWalkableObstacles would like to make those surfaces "climbable from ground" to be marked as walkable, controlled by a parameter called climbable distance. Even if those 'artifacts' over ground looks like unwalkable to some degree (a weird-shape sharp stone, etc.) since they could be easily leaped over, the area could be still viewed as walkable.

The rasterization (voxelization) is the first step in Recast Navmesh.

• Depending on slope angle of input triangles, the voxels are marked as walkable and unwalkable initially.
• Unity above uses a vivid figure to show the configurable max slope angle

rcFilterLowHangingWalkableObstacles is the very first step after voxelization in Recast.

The general idea is that: if one voxel is walkable, then the voxel above it in climbable distance (user-defined as a parameter) should also be set to walkable.

• This step enlarges walkable surface.

Source code:

rcSpan* previousSpan = NULL;
bool previousWasWalkable = false;
unsigned char previousArea = RC_NULL_AREA;

for (rcSpan* span = heightfield.spans[x + z * xSize]; span != NULL; previousSpan = span, span = span->next)
{
    const bool walkable = span->area != RC_NULL_AREA;
    // If current span is not walkable, but there is walkable
    // span just below it, mark the span above it walkable too.
    if (!walkable && previousWasWalkable)
    {
        if (rcAbs((int)span->smax - (int)previousSpan->smax) <= walkableClimb)
        {
            span->area = previousArea;
        }
    }
    // Copy walkable flag so that it cannot propagate
    // past multiple non-walkable objects.
    previousWasWalkable = walkable;
    previousArea = span->area;
}

Here is an example that turns a small hanging plane into walkable after rcFilterLowHangingWalkableObstacles .

Why we need filtering low hanging ?

Base Motivation: Filter out high-frequency noise over a walkable plane.

The rasterization could be viewed as removing voxel-wise wrinkles (cell size & cell height) over a walkable-surface.

For obstacles in a larger scale (stones on the ground) but is still climbable for agents, some techniques are adopted.

At rasterization, Addspan would only propagate walkable flag over spans in a column if

• spans are continuous (overlap)
  • (span is an intermediate structure when rasterizing triangles that represents continuous voxels in a column)
• addSpan merges span when the difference of max heights of two spans is smaller than a threshold (climbable distance)

rcFilterLowHangingWalkableObstacles is a complementary step of addSpan to deal with region of mesh intersections. It propagates flags when spans are not continuous (like cases at left in figure above).

What if we skip that step? See the ablation experiment below.

The partial voxels of that slope is still marked as walkable due to addSpan. But the higher ones fail, since there is room underneath it, which shows that rcFilterLowHangingWalkableObstacles is necessary in some cases.

Reference

1. Order of triangles to rasterization matters #232

[memononen]

Excellent summary, here's my blog post from around the time the feature was implemented for further reference: https://digestingduck.blogspot.com/2010/01/rough-fringes.html

[grahamboree]

This is awesome. I'd love to add it to the official documentation!