A* Pathfinding Project  4.1.9
The A* Pathfinding Project for Unity 3D
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. More...
 
void BuildRegions ()
 
void BuildVoxelConnections ()
 
int CalcAreaOfPolygon2D (int[] verts, int nverts)
 
ushort CalculateDistanceField (ushort[] src)
 
Vector3 CompactSpanToVector (int x, int z, int i)
 
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. More...
 
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. More...
 
Int3 VoxelToWorldInt3 (Int3 voxelPosition)
 Convert from voxel coordinates to world coordinates. More...
 
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. More...
 
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. More...
 
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 More...
 
static int Prev (int i, int n)
 (i-1+n) % n assuming 0 <= i < n More...
 
static bool Xorb (bool x, bool y)
 

Public Attributes

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

Properties

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

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*. More...
 
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. More...
 
static int union_find_find (int[] arr, int x)
 Find method in the UnionFind data structure. More...
 
static void union_find_union (int[] arr, int a, int b)
 Join method in the UnionFind data structure. More...
 
static bool Vequal (int a, int b, int[] verts)
 

Private Attributes

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

Constants @{

const uint NotConnected = 0x3f
 
const int RC_CONTOUR_TESS_WALL_EDGES = 1 << 0
 Tessellate wall edges. More...
 
const int RC_CONTOUR_TESS_AREA_EDGES = 1 << 1
 Tessellate edges between areas. More...
 
const int RC_CONTOUR_TESS_TILE_EDGES = 1 << 2
 Tessellate edges at the border of the tile. More...
 
const int MaxLayers = 65535
 Unmotivated variable, but let's clamp the layers at 65535. More...
 
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. More...
 
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. More...
 
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. More...
 

Constructor & Destructor Documentation

◆ Voxelize()

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

Member Function Documentation

◆ Area2()

static int Area2 ( int  a,
int  b,
int  c,
int []  verts 
)
static

◆ Between()

static bool Between ( int  a,
int  b,
int  c,
int []  verts 
)
staticprivate

◆ BoxBlur()

ushort [] BoxBlur ( ushort []  src,
ushort []  dst 
)

◆ BuildCompactField()

void BuildCompactField ( )

◆ BuildContours()

void BuildContours ( float  maxError,
int  maxEdgeLength,
VoxelContourSet  cset,
int  buildFlags 
)

◆ BuildDistanceField()

void BuildDistanceField ( )

◆ BuildPolyMesh()

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.

◆ BuildRegions()

void BuildRegions ( )

◆ BuildVoxelConnections()

void BuildVoxelConnections ( )

◆ CalcAreaOfPolygon2D()

int CalcAreaOfPolygon2D ( int []  verts,
int  nverts 
)

◆ CalculateDistanceField()

ushort CalculateDistanceField ( ushort []  src)

◆ Collinear()

static bool Collinear ( int  a,
int  b,
int  c,
int []  verts 
)
static

◆ CompactSpanToVector()

Vector3 CompactSpanToVector ( int  x,
int  z,
int  i 
)

◆ ConvertPosition()

Vector3 ConvertPosition ( int  x,
int  z,
int  i 
)
private

◆ ConvertPosWithoutOffset()

Vector3 ConvertPosWithoutOffset ( int  x,
int  y,
int  z 
)
private

◆ DebugDrawSpans()

void DebugDrawSpans ( )

◆ Diagonal()

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.

◆ Diagonalie()

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*.

◆ DrawLine()

void DrawLine ( int  a,
int  b,
int []  indices,
int []  verts,
Color  color 
)
private

◆ ErodeVoxels()

void ErodeVoxels ( int  radius)
Todo:
Complete the ErodeVoxels function translation

◆ ErodeWalkableArea()

void ErodeWalkableArea ( int  radius)

◆ ExpandRegions()

ushort [] ExpandRegions ( int  maxIterations,
uint  level,
ushort []  srcReg,
ushort []  srcDist,
ushort []  dstReg,
ushort []  dstDist,
List< int >  stack 
)

◆ FilterLedges()

void FilterLedges ( uint  voxelWalkableHeight,
int  voxelWalkableClimb,
float  cs,
float  ch 
)

◆ FilterLowHeightSpans()

void FilterLowHeightSpans ( uint  voxelWalkableHeight,
float  cs,
float  ch 
)

◆ FilterSmallRegions()

void FilterSmallRegions ( ushort []  reg,
int  minRegionSize,
int  maxRegions 
)

Filters out or merges small regions.

◆ FloodOnes()

void FloodOnes ( List< Int3 st1,
ushort []  regs,
uint  level,
ushort  reg 
)
private

◆ FloodRegion()

bool FloodRegion ( int  x,
int  z,
int  i,
uint  level,
ushort  r,
ushort []  srcReg,
ushort []  srcDist,
List< int >  stack 
)

◆ GetClosestIndices()

void GetClosestIndices ( int []  vertsa,
int  nvertsa,
int []  vertsb,
int  nvertsb,
ref int  ia,
ref int  ib 
)
private

◆ GetCornerHeight()

int GetCornerHeight ( int  x,
int  z,
int  i,
int  dir,
ref bool  isBorderVertex 
)

◆ Ileft()

static bool Ileft ( int  a,
int  b,
int  c,
int []  va,
int []  vb,
int []  vc 
)
static

◆ InCone()

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

◆ Init()

void Init ( )

◆ Intersect()

static bool Intersect ( int  a,
int  b,
int  c,
int  d,
int []  verts 
)
staticprivate

◆ IntersectProp()

static bool IntersectProp ( int  a,
int  b,
int  c,
int  d,
int []  verts 
)
static

◆ Left()

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.

◆ LeftOn()

static bool LeftOn ( int  a,
int  b,
int  c,
int []  verts 
)
static

◆ MarkRectWithRegion()

void MarkRectWithRegion ( int  minx,
int  maxx,
int  minz,
int  maxz,
ushort  region,
ushort []  srcReg 
)

◆ MergeContours()

static bool MergeContours ( ref VoxelContour  ca,
ref VoxelContour  cb,
int  ia,
int  ib 
)
static

◆ Next()

static int Next ( int  i,
int  n 
)
static

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

◆ Prev()

static int Prev ( int  i,
int  n 
)
static

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

◆ ReleaseContours()

static void ReleaseContours ( VoxelContourSet  cset)
staticprivate

Releases contents of a contour set to caches.

◆ RemoveDegenerateSegments()

void RemoveDegenerateSegments ( List< int >  simplified)

◆ SimplifyContour()

void SimplifyContour ( List< int >  verts,
List< int >  simplified,
float  maxError,
int  maxEdgeLenght,
int  buildFlags 
)

◆ Triangulate()

int Triangulate ( int  n,
int []  verts,
ref int []  indices,
ref int []  tris 
)
private

◆ union_find_find()

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

◆ union_find_union()

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

◆ VectorToIndex()

void VectorToIndex ( Vector3  p,
out int  x,
out int  z 
)

◆ Vequal()

static bool Vequal ( int  a,
int  b,
int []  verts 
)
staticprivate

◆ VoxelizeInput()

void VoxelizeInput ( Pathfinding.Util.GraphTransform  graphTransform,
Bounds  graphSpaceBounds 
)

◆ VoxelToWorld()

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.

◆ VoxelToWorldInt3()

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.

◆ WalkContour()

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

◆ Xorb()

static bool Xorb ( bool  x,
bool  y 
)
static

Member Data Documentation

◆ BorderReg

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.

◆ borderSize

int borderSize = 0

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

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

◆ cellHeight

readonly float cellHeight = 0.1F

The y-axis cell size to use for fields.

[Limit: > 0] [Units: wu]

◆ cellScale

readonly Vector3 cellScale
private

◆ cellSize

readonly float cellSize = 0.2F

The xz-plane cell size to use for fields.

[Limit: > 0] [Units: wu]

◆ clipper

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

◆ ContourRegMask

const int ContourRegMask = 0xffff
private

Mask used with contours to extract region id.

◆ countourSet

VoxelContourSet countourSet

◆ depth

int depth

Depth in voxels.

Must match the forcedBounds

◆ forcedBounds

Bounds forcedBounds

The world AABB to rasterize.

◆ inputMeshes

List<RasterizationMesh> inputMeshes

◆ maxEdgeLength

float maxEdgeLength = 20

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

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

◆ MaxLayers

const int MaxLayers = 65535
private

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

◆ MaxRegions

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

◆ maxSlope

float maxSlope = 30

The maximum slope that is considered walkable.

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

◆ minRegionSize

int minRegionSize = 100

◆ NotConnected

const uint NotConnected = 0x3f

◆ RC_AREA_BORDER

const int RC_AREA_BORDER = 0x20000
private

◆ RC_BORDER_VERTEX

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.

◆ RC_CONTOUR_TESS_AREA_EDGES

const int RC_CONTOUR_TESS_AREA_EDGES = 1 << 1

Tessellate edges between areas.

◆ RC_CONTOUR_TESS_TILE_EDGES

const int RC_CONTOUR_TESS_TILE_EDGES = 1 << 2

Tessellate edges at the border of the tile.

◆ RC_CONTOUR_TESS_WALL_EDGES

const int RC_CONTOUR_TESS_WALL_EDGES = 1 << 0

Tessellate wall edges.

◆ relevantGraphSurfaceMode

RecastGraph.RelevantGraphSurfaceMode relevantGraphSurfaceMode

◆ transform

Transform from voxel space to world space.

◆ UnwalkableArea

const int UnwalkableArea = 0
private

◆ VERTEX_BUCKET_COUNT

const int VERTEX_BUCKET_COUNT = 1<<12
private

◆ voxelArea

VoxelArea voxelArea

◆ voxelOffset

Vector3 voxelOffset = Vector3.zero
private

◆ voxelWalkableClimb

readonly int voxelWalkableClimb

Maximum ledge height that is considered to still be traversable.

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

◆ voxelWalkableHeight

readonly uint voxelWalkableHeight

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

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

◆ width

int width

Width in voxels.

Must match the forcedBounds

Property Documentation

◆ transformVoxel2Graph

Pathfinding.Util.GraphTransform transformVoxel2Graph
getprivate set

Transform from voxel space to graph space.


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