PathEngine home previous: Shape Validationnext: Unobstructed Space Optimisation
Contents, Programmers Guide, Applying the SDK, Preprocess Generation

Preprocess Generation

PathEngine is able to perform fast queries against large environments by generating various kinds of preprocess data structures corresponding to those environments.
Generating and managing preprocess is therefore an important aspect of using PathEngine.

At the core of the PathEngine preprocess generation is the creation of 'agent unobstructed space', a set of expanded and combined boundaries for the obstructions in an environment.

expanded and combined boundaries
Expanded and combined boundaries for part of the Thainesford mesh

The image shows expanded boundaries in an around a couple of buildings in a corner of the town in the 'Thainesford' mesh (included with the SDK).
As described previously, obstructions are defined by both the external edges of the ground mesh and also by shapes pinned to the surface of the ground mesh.
The white lines in the image show the base obstruction shapes. Expanded boundaries are generated for each obstruction shape, and for the external edges of the mesh.
Where these expanded boundaries overlap one another, they are combined together.

As described previously (in The PathEngine Movement Model), these expanded boundaries enable collision queries for an agent to be performed internally as point queries at the agent origin (or line queries for a moving agent).

Levels of preprocess generation

Different levels of preprocess can then be generated, for a given agent shape, depending on the exact types of queries required against that agent shape.

The base unobstructed space is required in order for agents to perform collision queries (see Collision Queries, later on in this section).
Additional preprocess can then be added in to enable connected region queries, or pathfinding queries (see Connectivity Queries and Pathfinding Queries, later on in this section.)

Preprocess is per agent shape

Because these expanded boundaries are specific to an agent shape, preprocess must be generated for each shape that will be used by agents requiring collision or pathfinding queries.

Planning shape usage

Depending on the environments used, the memory footprint for preprocess can get quite large, so it is a good idea to plan how shapes will be used by different types of agents so as to reduce the number of total shapes requiring preprocess generation.

Preprocess is not required for placing obstacles (either statically or dynamically) as long as those obstacles don't need to test for collision against other obstacles.

Objects that need to test collision against other obstacles but that do not need to plan movement around obstacles generally require collision preprocess.

Obstacles that need to plan paths around other obstacles require full pathfind preprocess.


For detailed reference about preprocess generation refer to iMesh::generateUnobstructedSpaceFor(), in the API Reference section.

Documentation for PathEngine release 6.03 - Copyright © 2002-2021 PathEnginenext: Unobstructed Space Optimisation