BSP and Voxel Based Processing Methods

The PathEngine 3D content processing supports two basic content processing methods, based on two different intermediate data representations for 3D obstructed space in the scene being processed.

BSP combination

The 'bsp' processing method (default) constructs an exact polygonal representation (in the form of a binary space partition) of the extruded and combined scene geometry.

The original scene data is first extruded downwards, by pathfinding agent height.
These extruded volumes are combined into a single connected volumetric representation, with ground surfaces then generated from the upper faces in this representation.

A basic scene with a floor and floating archway.

The objects in this scene extruded polygonally by agent height.

The ground surfaces generated after boolean combination.

Extruding the source volumes has the effect of cutting holes out of the resulting ground wherever overhead obstacles are lower than the required clearance.

Voxel representation

The 'voxels' processing method, in contrast, renders the scene geometry to an intermediate 3D voxel grid.

As with the BSP method, the scene is extruded by agent height.
(This is performed within the voxel representation before further processing.)

Connectivity is then determined between adjacent voxels, based on the maximum step height value supplied, and a ground mesh result built from this voxel connectivity.

A voxel representation of the above scene.

Voxel representation after extrusion.

Voxel processing can be turned on by supplying a 'voxels' value for the 'method' 3D processing option.
A voxel size should then also be specified, with the 'voxelSize' option.

Because of aliasing artifacts caused by the intermediate voxel representation, the 'optimiseWithThreshold' 3D processing should generally also be set, with a threshold value at least equal to the voxel size being applied.

Choosing a processing method

Choice of processing method basically comes down, in most cases, to a tradeoff between fidelity of pathfinding ground mesh and things like memory and time constraints.

(It's certainly possible for the BSP processing method to run faster than the voxel method, for example in a very large environment, with simple and sparsely placed polygonal obstructions, but, in most real world situations voxel processing works out a lot faster.)

The main advantage of BSP 3D processing is then the lack of aliasing to a voxel grid.

With voxel based approaches, if you have something like a doorway, the actual mesh width at this doorway can vary by a factor on the order of the voxel size being used, and so this is then something that needs to be taken into account if you want to guarantee passability for pathfinding agents.

Apart from issues at obstruction boundaries the BSP 3D processing also provides a much more exact ground representation.

(Being able to quickly get hold of a Z values for agent rendering position is nice, but is something that can potentially be handled by other engine components if required. More importantly, perhaps, is the ability to convert things like content position markers to pathfinding configuration space, absolutely robustly. when you have large numbers of positions to work with, and don't want these to sometimes be assigned to the wrong piece of pathfinding ground then the quality of ground representation can become an important issue.)

On the other hand, the extra precision comes at a cost, and having really fast processing times, without needing to do stuff like simplifying geometry or marking stuff up as solid objects, can just be much more convenient, particularly if you are working with very large amounts of content.

Both processes are very robust, operate on exactly the same source data representation, and spit out exactly the same run-time mesh format, so it is possible to some extent to switch between the approaches without changing either the input content data, or to run-time pathfinding code.

Both processes can be split across horizontal 'source tiles', and individual tile pieces processed in parallel and updated only when there are changes to local content.