org.critterai.nmgen
Class NavmeshGenerator

java.lang.Object
  extended by org.critterai.nmgen.NavmeshGenerator

public final class NavmeshGenerator
extends Object

Used to generate static triangle meshes representing the traversable surfaces of arbitrary source geometry.

When the build operation is provided with source geometry, several meshes are generated which represent the traversable (walkable) surfaces of the source geometry. A large number of configuration options are used to adjust the final result.

See Also:
Project Home, Process Overview, Configuration Options

Constructor Summary
NavmeshGenerator(float cellSize, float cellHeight, float minTraversableHeight, float maxTraversableStep, float maxTraversableSlope, boolean clipLedges, float traversableAreaBorderSize, int smoothingThreshold, boolean useConservativeExpansion, int minUnconnectedRegionSize, int mergeRegionSize, float maxEdgeLength, float edgeMaxDeviation, int maxVertsPerPoly, float contourSampleDistance, float contourMaxDeviation)
          Constructor
 
Method Summary
 TriangleMesh build(float[] vertices, int[] indices, IntermediateData outIntermediateData)
          Build a navigation mesh from the source geometry.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

NavmeshGenerator

public NavmeshGenerator(float cellSize,
                        float cellHeight,
                        float minTraversableHeight,
                        float maxTraversableStep,
                        float maxTraversableSlope,
                        boolean clipLedges,
                        float traversableAreaBorderSize,
                        int smoothingThreshold,
                        boolean useConservativeExpansion,
                        int minUnconnectedRegionSize,
                        int mergeRegionSize,
                        float maxEdgeLength,
                        float edgeMaxDeviation,
                        int maxVertsPerPoly,
                        float contourSampleDistance,
                        float contourMaxDeviation)
                 throws IllegalArgumentException
Constructor

Parameters:
cellSize - The width and depth resolution used when sampling the source mesh.

Constraints: > 0

cellHeight - The height resolution used when sampling the source mesh.

Constraints: > 0

minTraversableHeight - Represents the minimum floor to ceiling height that will still allow the floor area to be considered walkable.

Permits detection of overhangs in the geometry which make the geometry below become unwalkable.

Constraints: > 0

maxTraversableStep - Represents the maximum ledge height that is considered to still be walkable.

Prevents minor deviations in height from improperly showing as obstructions. Permits detection of stair-like structures, curbs, etc.

Constraints: >= 0

maxTraversableSlope - The maximum slope that is considered walkable. (Degrees)

Constraints: 0 <= value <= 85

clipLedges - Indicates whether ledges should be marked as unwalkable.

A ledge is a normally walkable voxel that has one or more accessible neighbors with a an un-steppable drop from voxel top to voxel top.

E.g. If an agent using the navmesh were to travel down from the ledge voxel to its neighbor voxel, it would result in the maximum traversable step distance being violated. The agent cannot legally "step down" from a ledge to its neighbor.

traversableAreaBorderSize - Represents the closest any part of the navmesh can get to an obstruction in the source mesh.

Usually set to the maximum bounding radius of entities utilizing the navmesh for navigation decisions.

Constraints: >= 0

smoothingThreshold - The amount of smoothing to be performed when generating the distance field.

This value impacts region formation and border detection. A higher value results in generally larger regions and larger border sizes. A value of zero will disable smoothing.

Constraints: 0 <= value <= 4

useConservativeExpansion - Applies extra algorithms to regions to help prevent poorly formed regions from forming.

If the navigation mesh is missing sections that should be present, then enabling this feature will likely fix the problem

Enabling this feature significantly increased processing cost.

minUnconnectedRegionSize - The minimum region size for unconnected (island) regions. (Voxels)

Any generated regions that are not connected to any other region and are smaller than this size will be culled before final navmesh generation. I.e. No longer considered walkable.

Constraints: > 0

mergeRegionSize - Any regions smaller than this size will, if possible, be merged with larger regions. (Voxels)

Helps reduce the number of unnecessarily small regions that can be formed. This is especially an issue in diagonal path regions where inherent faults in the region generation algorithm can result in unnecessarily small regions.

If a region cannot be legally merged with a neighbor region, then it will be left alone.

Constraints: >= 0

maxEdgeLength - The maximum length of polygon edges that represent the border of the navmesh.

More vertices will be added to navmesh border edges if this value is exceeded for a particular edge. In certain cases this will reduce the number of thin, long triangles in the navmesh.

A value of zero will disable this feature.

Constraints: >= 0

edgeMaxDeviation - The maximum distance the edge of the navmesh may deviate from the source geometry.

Setting this lower will result in the navmesh edges following the geometry contour more accurately at the expense of an increased triangle count.

Setting the value to zero is not recommended since it can result in a large increase in the number of triangles in the final navmesh at a high processing cost.

Constraints: >= 0

maxVertsPerPoly - The maximum number of vertices per polygon for polygons generated during the voxel to polygon conversion stage.

Higher values reduce performance, but can also result in better formed triangles in the navmesh. A value of around 6 is generally adequate with diminishing returns for values higher than 6.

Contraints: >= 3

contourSampleDistance - Sets the sampling distance to use when matching the navmesh to the surface of the original geometry.

Impacts how well the final mesh conforms to the original geometry's surface contour. Higher values result in a navmesh which conforms more closely to the original geometry's surface at the cost of a higher final triangle count and higher processing cost.

Setting this argument to zero will disable this functionality.

Constraints: >= 0

contourMaxDeviation - The maximum distance the surface of the navmesh may deviate from the surface of the original geometry.

The accuracy of the algorithm which uses this value is impacted by the value of the contour sample distance argument.

The value of this argument has no meaning if the contour sample distance argument is set to zero.

Setting the value to zero is not recommended since it can result in a large increase in the number of triangles in the final navmesh at a high processing cost.

Constraints: >= 0

Throws:
IllegalArgumentException - If there are any unresolvable argument errors. (Most argument errors are avoided through value clamping and other auto-correction methods.)
See Also:
Detailed parameter information.
Method Detail

build

public TriangleMesh build(float[] vertices,
                          int[] indices,
                          IntermediateData outIntermediateData)
Build a navigation mesh from the source geometry.

Parameters:
vertices - The source geometry vertices in the form (x, y, z)
indices - The triangle mesh vertices in the form (vertA, vertB, vertC), wrapped clockwise.
outIntermediateData - If non-null, the intermediate build results will be added to this object. If the build fails, the object will contain all intermediate results which were successfully generated.
Returns:
The generated navigation mesh, or null if generation failed.
See Also:
Process Overview


Project Home and Source Code

Copyright 2010 Stephen Pratt. All rights reserved. Use is subject to license terms.