A* Pathfinding Project  4.0.9
The A* Pathfinding Project for Unity 3D
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Properties Events Macros Groups Pages
Voxelize Class Reference

Voxelizer for recast graphs. More...

Detailed Description

Voxelizer for recast graphs.

In comments: units wu are World Units, vx are Voxels

A* Pro Feature:
This is an A* Pathfinding Project Pro feature only. This function/class/variable might not exist in the Free version of the A* Pathfinding Project or the functionality might be limited
The Pro version can be bought here

Public Member Functions

 Voxelize (float ch, float cs, float walkableClimb, float walkableHeight, float maxSlope, float maxEdgeLength)
 
ushort[] BoxBlur (ushort[] src, ushort[] dst)
 
void BuildCompactField ()
 
void BuildContours (float maxError, int maxEdgeLength, VoxelContourSet cset, int buildFlags)
 
void BuildDistanceField ()
 
void BuildPolyMesh (VoxelContourSet cset, int nvp, out VoxelMesh mesh)
 Builds a polygon mesh from a contour set.
 
void BuildRegions ()
 
void BuildVoxelConnections ()
 
int CalcAreaOfPolygon2D (int[] verts, int nverts)
 
ushort CalculateDistanceField (ushort[] src)
 
Vector3 CompactSpanToVector (int x, int z, int i)
 
void DebugDrawCompactSpans ()
 
void DebugDrawSpans ()
 
void ErodeVoxels (int radius)
 
void ErodeWalkableArea (int radius)
 
ushort[] ExpandRegions (int maxIterations, uint level, ushort[] srcReg, ushort[] srcDist, ushort[] dstReg, ushort[] dstDist, List< int > stack)
 
void FilterLedges (uint voxelWalkableHeight, int voxelWalkableClimb, float cs, float ch)
 
void FilterLowHeightSpans (uint voxelWalkableHeight, float cs, float ch)
 
void FilterSmallRegions (ushort[] reg, int minRegionSize, int maxRegions)
 Filters out or merges small regions.
 
bool FloodRegion (int x, int z, int i, uint level, ushort r, ushort[] srcReg, ushort[] srcDist, List< int > stack)
 
int GetCornerHeight (int x, int z, int i, int dir, ref bool isBorderVertex)
 
void Init ()
 
void MarkRectWithRegion (int minx, int maxx, int minz, int maxz, ushort region, ushort[] srcReg)
 
void RemoveDegenerateSegments (List< int > simplified)
 
void SimplifyContour (List< int > verts, List< int > simplified, float maxError, int maxEdgeLenght, int buildFlags)
 
void VectorToIndex (Vector3 p, out int x, out int z)
 
void VoxelizeInput (Pathfinding.Util.GraphTransform graphTransform, Bounds graphSpaceBounds)
 
Vector3 VoxelToWorld (int x, int y, int z)
 Convert from voxel coordinates to world coordinates.
 
Int3 VoxelToWorldInt3 (Int3 voxelPosition)
 Convert from voxel coordinates to world coordinates.
 
void WalkContour (int x, int z, int i, ushort[] flags, List< int > verts)
 

Static Public Member Functions

static int Area2 (int a, int b, int c, int[] verts)
 
static bool Collinear (int a, int b, int c, int[] verts)
 
static bool Diagonal (int i, int j, int n, int[] verts, int[] indices)
 Returns T iff (v_i, v_j) is a proper internal diagonal of P.
 
static bool Ileft (int a, int b, int c, int[] va, int[] vb, int[] vc)
 
static bool InCone (int i, int j, int n, int[] verts, int[] indices)
 
static bool IntersectProp (int a, int b, int c, int d, int[] verts)
 
static bool Left (int a, int b, int c, int[] verts)
 Returns true iff c is strictly to the left of the directed line through a to b.
 
static bool LeftOn (int a, int b, int c, int[] verts)
 
static bool MergeContours (ref VoxelContour ca, ref VoxelContour cb, int ia, int ib)
 
static int Next (int i, int n)
 (i+1) % n assuming 0 <= i < n
 
static int Prev (int i, int n)
 (i-1+n) % n assuming 0 <= i < n
 
static bool Xorb (bool x, bool y)
 

Public Attributes

int borderSize = 0
 The size of the non-navigable border around the heightfield.
 
readonly float cellHeight = 0.1F
 The y-axis cell size to use for fields.
 
readonly float cellSize = 0.2F
 The xz-plane cell size to use for fields.
 
VoxelContourSet countourSet
 
int depth
 Depth in voxels.
 
Bounds forcedBounds
 The world AABB to rasterize.
 
List< RasterizationMeshinputMeshes
 
float maxEdgeLength = 20
 The maximum allowed length for contour edges along the border of the mesh.
 
float maxSlope = 30
 The maximum slope that is considered walkable.
 
int minRegionSize = 100
 
RecastGraph.RelevantGraphSurfaceMode relevantGraphSurfaceMode
 
VoxelArea voxelArea
 
readonly int voxelWalkableClimb
 Maximum ledge height that is considered to still be traversable.
 
readonly uint voxelWalkableHeight
 Minimum floor to 'ceiling' height that will still allow the floor area to be considered walkable.
 
int width
 Width in voxels.
 

Properties

Pathfinding.Util.GraphTransform transformVoxel2Graph [get, set]
 Transform from voxel space to graph space.
 

Private Member Functions

Vector3 ConvertPosition (int x, int z, int i)
 
Vector3 ConvertPosWithoutOffset (int x, int y, int z)
 
void DrawLine (int a, int b, int[] indices, int[] verts, Color color)
 
void FloodOnes (List< Int3 > st1, ushort[] regs, uint level, ushort reg)
 
void GetClosestIndices (int[] vertsa, int nvertsa, int[] vertsb, int nvertsb, ref int ia, ref int ib)
 
int Triangulate (int n, int[] verts, ref int[] indices, ref int[] tris)
 

Static Private Member Functions

static bool Between (int a, int b, int c, int[] verts)
 
static bool Diagonalie (int i, int j, int n, int[] verts, int[] indices)
 Returns T iff (v_i, v_j) is a proper internal *or* external diagonal of P, *ignoring edges incident to v_i and v_j*.
 
static bool Intersect (int a, int b, int c, int d, int[] verts)
 
static void ReleaseContours (VoxelContourSet cset)
 Releases contents of a contour set to caches.
 
static int union_find_find (int[] arr, int x)
 Find method in the UnionFind data structure.
 
static void union_find_union (int[] arr, int a, int b)
 Join method in the UnionFind data structure.
 
static bool Vequal (int a, int b, int[] verts)
 

Private Attributes

readonly Vector3 cellScale
 
VoxelPolygonClipper clipper
 Utility for clipping polygons to rectangles.
 
Pathfinding.Util.GraphTransform transform
 Transform from voxel space to world space.
 
Vector3 voxelOffset = Vector3.zero
 

Constants @{

const uint NotConnected = 0x3f
 
const int RC_CONTOUR_TESS_WALL_EDGES = 1 << 0
 Tessellate wall edges.
 
const int RC_CONTOUR_TESS_AREA_EDGES = 1 << 1
 Tessellate edges between areas.
 
const int RC_CONTOUR_TESS_TILE_EDGES = 1 << 2
 Tessellate edges at the border of the tile.
 
const int MaxLayers = 65535
 Unmotivated variable, but let's clamp the layers at 65535.
 
const int MaxRegions = 500
 
const int UnwalkableArea = 0
 
const ushort BorderReg = 0x8000
 If heightfield region ID has the following bit set, the region is on border area and excluded from many calculations.
 
const int RC_BORDER_VERTEX = 0x10000
 If contour region ID has the following bit set, the vertex will be later removed in order to match the segments and vertices at tile boundaries.
 
const int RC_AREA_BORDER = 0x20000
 
const int VERTEX_BUCKET_COUNT = 1<<12
 
const int ContourRegMask = 0xffff
 Mask used with contours to extract region id.
 

Constructor & Destructor Documentation

Voxelize ( float  ch,
float  cs,
float  walkableClimb,
float  walkableHeight,
float  maxSlope,
float  maxEdgeLength 
)

Member Function Documentation

static int Area2 ( int  a,
int  b,
int  c,
int[]  verts 
)
static
static bool Between ( int  a,
int  b,
int  c,
int[]  verts 
)
staticprivate
ushort [] BoxBlur ( ushort[]  src,
ushort[]  dst 
)
void BuildCompactField ( )
void BuildContours ( float  maxError,
int  maxEdgeLength,
VoxelContourSet  cset,
int  buildFlags 
)
void BuildDistanceField ( )
void BuildPolyMesh ( VoxelContourSet  cset,
int  nvp,
out VoxelMesh  mesh 
)

Builds a polygon mesh from a contour set.

Parameters
csetcontour set to build a mesh from.
nvpMaximum allowed vertices per polygon.
Warning
Currently locked to 3.
Parameters
meshResults will be written to this mesh.
void BuildRegions ( )
void BuildVoxelConnections ( )
int CalcAreaOfPolygon2D ( int[]  verts,
int  nverts 
)
ushort CalculateDistanceField ( ushort[]  src)
static bool Collinear ( int  a,
int  b,
int  c,
int[]  verts 
)
static
Vector3 CompactSpanToVector ( int  x,
int  z,
int  i 
)
Vector3 ConvertPosition ( int  x,
int  z,
int  i 
)
private
Vector3 ConvertPosWithoutOffset ( int  x,
int  y,
int  z 
)
private
void DebugDrawCompactSpans ( )
void DebugDrawSpans ( )
static bool Diagonal ( int  i,
int  j,
int  n,
int[]  verts,
int[]  indices 
)
static

Returns T iff (v_i, v_j) is a proper internal diagonal of P.

static bool Diagonalie ( int  i,
int  j,
int  n,
int[]  verts,
int[]  indices 
)
staticprivate

Returns T iff (v_i, v_j) is a proper internal *or* external diagonal of P, *ignoring edges incident to v_i and v_j*.

void DrawLine ( int  a,
int  b,
int[]  indices,
int[]  verts,
Color  color 
)
private
void ErodeVoxels ( int  radius)
Todo:
Complete the ErodeVoxels function translation
void ErodeWalkableArea ( int  radius)
ushort [] ExpandRegions ( int  maxIterations,
uint  level,
ushort[]  srcReg,
ushort[]  srcDist,
ushort[]  dstReg,
ushort[]  dstDist,
List< int >  stack 
)
void FilterLedges ( uint  voxelWalkableHeight,
int  voxelWalkableClimb,
float  cs,
float  ch 
)
void FilterLowHeightSpans ( uint  voxelWalkableHeight,
float  cs,
float  ch 
)
void FilterSmallRegions ( ushort[]  reg,
int  minRegionSize,
int  maxRegions 
)

Filters out or merges small regions.

void FloodOnes ( List< Int3 st1,
ushort[]  regs,
uint  level,
ushort  reg 
)
private
bool FloodRegion ( int  x,
int  z,
int  i,
uint  level,
ushort  r,
ushort[]  srcReg,
ushort[]  srcDist,
List< int >  stack 
)
void GetClosestIndices ( int[]  vertsa,
int  nvertsa,
int[]  vertsb,
int  nvertsb,
ref int  ia,
ref int  ib 
)
private
int GetCornerHeight ( int  x,
int  z,
int  i,
int  dir,
ref bool  isBorderVertex 
)
static bool Ileft ( int  a,
int  b,
int  c,
int[]  va,
int[]  vb,
int[]  vc 
)
static
static bool InCone ( int  i,
int  j,
int  n,
int[]  verts,
int[]  indices 
)
static
void Init ( )
static bool Intersect ( int  a,
int  b,
int  c,
int  d,
int[]  verts 
)
staticprivate
static bool IntersectProp ( int  a,
int  b,
int  c,
int  d,
int[]  verts 
)
static
static bool Left ( int  a,
int  b,
int  c,
int[]  verts 
)
static

Returns true iff c is strictly to the left of the directed line through a to b.

static bool LeftOn ( int  a,
int  b,
int  c,
int[]  verts 
)
static
void MarkRectWithRegion ( int  minx,
int  maxx,
int  minz,
int  maxz,
ushort  region,
ushort[]  srcReg 
)
static bool MergeContours ( ref VoxelContour  ca,
ref VoxelContour  cb,
int  ia,
int  ib 
)
static
static int Next ( int  i,
int  n 
)
static

(i+1) % n assuming 0 <= i < n

static int Prev ( int  i,
int  n 
)
static

(i-1+n) % n assuming 0 <= i < n

static void ReleaseContours ( VoxelContourSet  cset)
staticprivate

Releases contents of a contour set to caches.

void RemoveDegenerateSegments ( List< int >  simplified)
void SimplifyContour ( List< int >  verts,
List< int >  simplified,
float  maxError,
int  maxEdgeLenght,
int  buildFlags 
)
int Triangulate ( int  n,
int[]  verts,
ref int[]  indices,
ref int[]  tris 
)
private
static int union_find_find ( int[]  arr,
int  x 
)
staticprivate

Find method in the UnionFind data structure.

See Also
https://en.wikipedia.org/wiki/Disjoint-set_data_structure
static void union_find_union ( int[]  arr,
int  a,
int  b 
)
staticprivate

Join method in the UnionFind data structure.

See Also
https://en.wikipedia.org/wiki/Disjoint-set_data_structure
void VectorToIndex ( Vector3  p,
out int  x,
out int  z 
)
static bool Vequal ( int  a,
int  b,
int[]  verts 
)
staticprivate
void VoxelizeInput ( Pathfinding.Util.GraphTransform  graphTransform,
Bounds  graphSpaceBounds 
)
Vector3 VoxelToWorld ( int  x,
int  y,
int  z 
)

Convert from voxel coordinates to world coordinates.

(0,0,0) in voxel coordinates is a bottom corner of the bounding box. (1,0,0) is one voxel in the +X direction of that.

Int3 VoxelToWorldInt3 ( Int3  voxelPosition)

Convert from voxel coordinates to world coordinates.

(0,0,0) in voxel coordinates is a bottom corner of the bounding box. (1,0,0) is one voxel in the +X direction of that.

void WalkContour ( int  x,
int  z,
int  i,
ushort[]  flags,
List< int >  verts 
)
static bool Xorb ( bool  x,
bool  y 
)
static

Member Data Documentation

const ushort BorderReg = 0x8000
private

If heightfield region ID has the following bit set, the region is on border area and excluded from many calculations.

int borderSize = 0

The size of the non-navigable border around the heightfield.

[Limit: >=0] [Units: vx]

readonly float cellHeight = 0.1F

The y-axis cell size to use for fields.

[Limit: > 0] [Units: wu]

readonly Vector3 cellScale
private
readonly float cellSize = 0.2F

The xz-plane cell size to use for fields.

[Limit: > 0] [Units: wu]

VoxelPolygonClipper clipper
private

Utility for clipping polygons to rectangles.

Implemented as a struct and not a bunch of static methods because it needs some buffer arrays that are best cached to avoid excessive allocations

const int ContourRegMask = 0xffff
private

Mask used with contours to extract region id.

VoxelContourSet countourSet
int depth

Depth in voxels.

Must match the forcedBounds

Bounds forcedBounds

The world AABB to rasterize.

List<RasterizationMesh> inputMeshes
float maxEdgeLength = 20

The maximum allowed length for contour edges along the border of the mesh.

[Limit: >= 0] [Units: vx]

const int MaxLayers = 65535
private

Unmotivated variable, but let's clamp the layers at 65535.

const int MaxRegions = 500
private
Todo:
: Check up on this variable
float maxSlope = 30

The maximum slope that is considered walkable.

[Limits: 0 <= value < 90] [Units: Degrees]

int minRegionSize = 100
const uint NotConnected = 0x3f
const int RC_AREA_BORDER = 0x20000
private
const int RC_BORDER_VERTEX = 0x10000
private

If contour region ID has the following bit set, the vertex will be later removed in order to match the segments and vertices at tile boundaries.

const int RC_CONTOUR_TESS_AREA_EDGES = 1 << 1

Tessellate edges between areas.

const int RC_CONTOUR_TESS_TILE_EDGES = 1 << 2

Tessellate edges at the border of the tile.

const int RC_CONTOUR_TESS_WALL_EDGES = 1 << 0

Tessellate wall edges.

RecastGraph.RelevantGraphSurfaceMode relevantGraphSurfaceMode

Transform from voxel space to world space.

const int UnwalkableArea = 0
private
const int VERTEX_BUCKET_COUNT = 1<<12
private
VoxelArea voxelArea
Vector3 voxelOffset = Vector3.zero
private
readonly int voxelWalkableClimb

Maximum ledge height that is considered to still be traversable.

[Limit: >=0] [Units: vx]

readonly uint voxelWalkableHeight

Minimum floor to 'ceiling' height that will still allow the floor area to be considered walkable.

[Limit: >= 3] [Units: vx]

int width

Width in voxels.

Must match the forcedBounds

Property Documentation

Pathfinding.Util.GraphTransform transformVoxel2Graph
getset

Transform from voxel space to graph space.


The documentation for this class was generated from the following files: