Pathfinding Through Forests

Forests can cause problems for a straightforward points-of-visibility pathfinding system. The problem is that forests generally have a very large number of points of visibility, with relatively open visibility between those points. It can become costly to represent the visibility graph for connections between these points.
This applies to any 'forest-like' environments, where a large number of small obstructions are scattered around in an external space.

To a human, the problem of finding a shortest path through a forest is a straightforward one. (Assuming that there is no dense undergrowth!)
The point is that obstacles like trees are not relevant over large distances.
If a tree blocks the path to a target then you just walk around it.

PathEngine provides a similar solution to this problem. Small convex obstacles can be automatically identified and split off from the rest of the geometry.
Pathfinding is first performed against the base geometry. The resulting path is then modified to go around any small convex obstacles that are crossed

Small convex obstacles are detected after obstacles are expanded and combined. This way, groups of trees that clump together into larger obstructions are correctly included with the base geometry.
The small convex boundaries are stored in a separate partitioning of the ground mesh.

A ground mesh with lots of trees and rocks. Yellow lines show obstruction boundaries that got split off with the small convex optimisation.

To enable this optimisation you need to pass an attribute into iMesh::generateUnobstructedSpaceFor().
The attribute both enables the optimisation and specifies a maximum circumference for the small convex obstacles.
The following code snippet shows how this can be done:

const char* attributes[3];
attributes[0] = "splitWithCircumferenceBelow";
attributes[1] = "2000";
attributes[2] = 0;
mesh->generateUnobstructedSpaceFor(shape, true, attributes); 

Wrapping non convex obstacles

Starting from release 5.30, it is now possible to apply the small convex optimisation to regions which are non-convex, but which can be wrapped by convex hulls that are not obstructed by other boundaries, and that meet the split constraints.
(But note that the circumference constraint, in this case, applied to the actual wrapped region, as opposed to the wrapping hull, so this gives you some control over the amount of detail that gets hidden from the pathfinding with this optimisation.)

To enable this extension, pass the "smallConvex_WrapNonConvex" unobstructed space generation, with value "true".

A ground mesh with non convex regions split off using the "smallConvex_WrapNonConvex" option.
Again, yellow lines show obstruction boundaries that got split off with the small convex optimisation. These regions are excluded from core 'pathfind space' and do not affect things like pathfinding graph complexity.

Range constraint

In addition to the circumference constraint it is now also possible to specify a range constraint with the "smallConvexMaxRange" attribute.

Path quality implications

You should be aware that path results are not guaranteed to be geometrically shortest paths in all cases, when this optimisation is turned on.
(In practice, however, and with reasonable values chosen for the split option, this is generally not an issue.)

Other related optimisations

Note that this optimisation is separate from, and complementary to PathEngine's Unobstructed Space Optimisation, and so both of these optimisations can potentially be used together where even more significant speedup are desired.