TrinityCore
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
Recast.h File Reference
+ This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

class  rcContext
 
struct  rcConfig
 
struct  rcSpan
 
struct  rcSpanPool
 
struct  rcHeightfield
 
struct  rcCompactCell
 Provides information on the content of a cell column in a compact heightfield. More...
 
struct  rcCompactSpan
 Represents a span of unobstructed space within a compact heightfield. More...
 
struct  rcCompactHeightfield
 
struct  rcHeightfieldLayer
 
struct  rcHeightfieldLayerSet
 
struct  rcContour
 Represents a simple, non-overlapping contour in field space. More...
 
struct  rcContourSet
 
struct  rcPolyMesh
 
struct  rcPolyMeshDetail
 

Enumerations

enum  rcLogCategory { RC_LOG_PROGRESS = 1, RC_LOG_WARNING, RC_LOG_ERROR }
 
enum  rcTimerLabel {
  RC_TIMER_TOTAL, RC_TIMER_TEMP, RC_TIMER_RASTERIZE_TRIANGLES, RC_TIMER_BUILD_COMPACTHEIGHTFIELD,
  RC_TIMER_BUILD_CONTOURS, RC_TIMER_BUILD_CONTOURS_TRACE, RC_TIMER_BUILD_CONTOURS_SIMPLIFY, RC_TIMER_FILTER_BORDER,
  RC_TIMER_FILTER_WALKABLE, RC_TIMER_MEDIAN_AREA, RC_TIMER_FILTER_LOW_OBSTACLES, RC_TIMER_BUILD_POLYMESH,
  RC_TIMER_MERGE_POLYMESH, RC_TIMER_ERODE_AREA, RC_TIMER_MARK_BOX_AREA, RC_TIMER_MARK_CYLINDER_AREA,
  RC_TIMER_MARK_CONVEXPOLY_AREA, RC_TIMER_BUILD_DISTANCEFIELD, RC_TIMER_BUILD_DISTANCEFIELD_DIST, RC_TIMER_BUILD_DISTANCEFIELD_BLUR,
  RC_TIMER_BUILD_REGIONS, RC_TIMER_BUILD_REGIONS_WATERSHED, RC_TIMER_BUILD_REGIONS_EXPAND, RC_TIMER_BUILD_REGIONS_FLOOD,
  RC_TIMER_BUILD_REGIONS_FILTER, RC_TIMER_BUILD_LAYERS, RC_TIMER_BUILD_POLYMESHDETAIL, RC_TIMER_MERGE_POLYMESHDETAIL,
  RC_MAX_TIMERS
}
 
enum  rcBuildContoursFlags { RC_CONTOUR_TESS_WALL_EDGES = 0x01, RC_CONTOUR_TESS_AREA_EDGES = 0x02 }
 

Functions

Allocation Functions

Functions used to allocate and de-allocate Recast objects.

See also
rcAllocSetCustom
rcHeightfieldrcAllocHeightfield ()
 
void rcFreeHeightField (rcHeightfield *hf)
 
rcCompactHeightfieldrcAllocCompactHeightfield ()
 
void rcFreeCompactHeightfield (rcCompactHeightfield *chf)
 
rcHeightfieldLayerSetrcAllocHeightfieldLayerSet ()
 
void rcFreeHeightfieldLayerSet (rcHeightfieldLayerSet *lset)
 
rcContourSetrcAllocContourSet ()
 
void rcFreeContourSet (rcContourSet *cset)
 
rcPolyMeshrcAllocPolyMesh ()
 
void rcFreePolyMesh (rcPolyMesh *pmesh)
 
rcPolyMeshDetailrcAllocPolyMeshDetail ()
 
void rcFreePolyMeshDetail (rcPolyMeshDetail *dmesh)
 
General helper functions
template<class T >
void rcIgnoreUnused (const T &)
 
template<class T >
void rcSwap (T &a, T &b)
 
template<class T >
rcMin (T a, T b)
 
template<class T >
rcMax (T a, T b)
 
template<class T >
rcAbs (T a)
 
template<class T >
rcSqr (T a)
 
template<class T >
rcClamp (T v, T mn, T mx)
 
float rcSqrt (float x)
 
Vector helper functions.
void rcVcross (float *dest, const float *v1, const float *v2)
 
float rcVdot (const float *v1, const float *v2)
 
void rcVmad (float *dest, const float *v1, const float *v2, const float s)
 
void rcVadd (float *dest, const float *v1, const float *v2)
 
void rcVsub (float *dest, const float *v1, const float *v2)
 
void rcVmin (float *mn, const float *v)
 
void rcVmax (float *mx, const float *v)
 
void rcVcopy (float *dest, const float *v)
 
float rcVdist (const float *v1, const float *v2)
 
float rcVdistSqr (const float *v1, const float *v2)
 
void rcVnormalize (float *v)
 
Heightfield Functions
See also
rcHeightfield
void rcCalcBounds (const float *verts, int nv, float *bmin, float *bmax)
 
void rcCalcGridSize (const float *bmin, const float *bmax, float cs, int *w, int *h)
 
bool rcCreateHeightfield (rcContext *ctx, rcHeightfield &hf, int width, int height, const float *bmin, const float *bmax, float cs, float ch)
 
void rcMarkWalkableTriangles (rcContext *ctx, const float walkableSlopeAngle, const float *verts, int nv, const int *tris, int nt, unsigned char *areas)
 
void rcClearUnwalkableTriangles (rcContext *ctx, const float walkableSlopeAngle, const float *verts, int nv, const int *tris, int nt, unsigned char *areas)
 
void rcAddSpan (rcContext *ctx, rcHeightfield &hf, const int x, const int y, const unsigned short smin, const unsigned short smax, const unsigned char area, const int flagMergeThr)
 
void rcRasterizeTriangle (rcContext *ctx, const float *v0, const float *v1, const float *v2, const unsigned char area, rcHeightfield &solid, const int flagMergeThr=1)
 
void rcRasterizeTriangles (rcContext *ctx, const float *verts, const int nv, const int *tris, const unsigned char *areas, const int nt, rcHeightfield &solid, const int flagMergeThr=1)
 
void rcRasterizeTriangles (rcContext *ctx, const float *verts, const int nv, const unsigned short *tris, const unsigned char *areas, const int nt, rcHeightfield &solid, const int flagMergeThr=1)
 
void rcRasterizeTriangles (rcContext *ctx, const float *verts, const unsigned char *areas, const int nt, rcHeightfield &solid, const int flagMergeThr=1)
 
void rcFilterLowHangingWalkableObstacles (rcContext *ctx, const int walkableClimb, rcHeightfield &solid)
 
void rcFilterLedgeSpans (rcContext *ctx, const int walkableHeight, const int walkableClimb, rcHeightfield &solid)
 
void rcFilterWalkableLowHeightSpans (rcContext *ctx, int walkableHeight, rcHeightfield &solid)
 
int rcGetHeightFieldSpanCount (rcContext *ctx, rcHeightfield &hf)
 
Compact Heightfield Functions
bool rcBuildCompactHeightfield (rcContext *ctx, const int walkableHeight, const int walkableClimb, rcHeightfield &hf, rcCompactHeightfield &chf)
 
bool rcErodeWalkableArea (rcContext *ctx, int radius, rcCompactHeightfield &chf)
 
bool rcMedianFilterWalkableArea (rcContext *ctx, rcCompactHeightfield &chf)
 
void rcMarkBoxArea (rcContext *ctx, const float *bmin, const float *bmax, unsigned char areaId, rcCompactHeightfield &chf)
 
void rcMarkConvexPolyArea (rcContext *ctx, const float *verts, const int nverts, const float hmin, const float hmax, unsigned char areaId, rcCompactHeightfield &chf)
 
int rcOffsetPoly (const float *verts, const int nverts, const float offset, float *outVerts, const int maxOutVerts)
 
void rcMarkCylinderArea (rcContext *ctx, const float *pos, const float r, const float h, unsigned char areaId, rcCompactHeightfield &chf)
 
bool rcBuildDistanceField (rcContext *ctx, rcCompactHeightfield &chf)
 
bool rcBuildRegions (rcContext *ctx, rcCompactHeightfield &chf, const int borderSize, const int minRegionArea, const int mergeRegionArea)
 
bool rcBuildLayerRegions (rcContext *ctx, rcCompactHeightfield &chf, const int borderSize, const int minRegionArea)
 
bool rcBuildRegionsMonotone (rcContext *ctx, rcCompactHeightfield &chf, const int borderSize, const int minRegionArea, const int mergeRegionArea)
 
void rcSetCon (rcCompactSpan &s, int dir, int i)
 
int rcGetCon (const rcCompactSpan &s, int dir)
 
int rcGetDirOffsetX (int dir)
 
int rcGetDirOffsetY (int dir)
 
Layer, Contour, Polymesh, and Detail Mesh Functions
bool rcBuildHeightfieldLayers (rcContext *ctx, rcCompactHeightfield &chf, const int borderSize, const int walkableHeight, rcHeightfieldLayerSet &lset)
 
bool rcBuildContours (rcContext *ctx, rcCompactHeightfield &chf, const float maxError, const int maxEdgeLen, rcContourSet &cset, const int buildFlags=RC_CONTOUR_TESS_WALL_EDGES)
 
bool rcBuildPolyMesh (rcContext *ctx, rcContourSet &cset, const int nvp, rcPolyMesh &mesh)
 
bool rcMergePolyMeshes (rcContext *ctx, rcPolyMesh **meshes, const int nmeshes, rcPolyMesh &mesh)
 
bool rcBuildPolyMeshDetail (rcContext *ctx, const rcPolyMesh &mesh, const rcCompactHeightfield &chf, const float sampleDist, const float sampleMaxError, rcPolyMeshDetail &dmesh)
 
bool rcCopyPolyMesh (rcContext *ctx, const rcPolyMesh &src, rcPolyMesh &dst)
 
bool rcMergePolyMeshDetails (rcContext *ctx, rcPolyMeshDetail **meshes, const int nmeshes, rcPolyMeshDetail &mesh)
 

Variables

static const float RC_PI = 3.14159265f
 The value of PI used by Recast. More...
 
static const int RC_SPAN_HEIGHT_BITS = 16
 Defines the number of bits allocated to rcSpan::smin and rcSpan::smax. More...
 
static const int RC_SPAN_MAX_HEIGHT = (1<<RC_SPAN_HEIGHT_BITS)-1
 Defines the maximum value for rcSpan::smin and rcSpan::smax. More...
 
static const int RC_SPANS_PER_POOL = 2048
 
static const unsigned short RC_BORDER_REG = 0x8000
 
static const int RC_BORDER_VERTEX = 0x10000
 
static const int RC_AREA_BORDER = 0x20000
 
static const int RC_CONTOUR_REG_MASK = 0xffff
 
static const unsigned short RC_MESH_NULL_IDX = 0xffff
 
static const unsigned char RC_NULL_AREA = 0
 
static const unsigned char RC_WALKABLE_AREA = 63
 
static const int RC_NOT_CONNECTED = 0x3f
 

Enumeration Type Documentation

Contour build flags.

See also
rcBuildContours
Enumerator
RC_CONTOUR_TESS_WALL_EDGES 

Tessellate solid (impassable) edges during contour simplification.

RC_CONTOUR_TESS_AREA_EDGES 

Tessellate edges between areas during contour simplification.

519 {
522 };
Tessellate edges between areas during contour simplification.
Definition: Recast.h:521
Tessellate solid (impassable) edges during contour simplification.
Definition: Recast.h:520

Recast log categories.

See also
rcContext
Enumerator
RC_LOG_PROGRESS 

A progress log entry.

RC_LOG_WARNING 

A warning log entry.

RC_LOG_ERROR 

An error log entry.

28 {
29  RC_LOG_PROGRESS = 1,
31  RC_LOG_ERROR,
32 };
An error log entry.
Definition: Recast.h:31
A progress log entry.
Definition: Recast.h:29
A warning log entry.
Definition: Recast.h:30

Recast performance timer categories.

See also
rcContext
Enumerator
RC_TIMER_TOTAL 

The user defined total time of the build.

RC_TIMER_TEMP 

A user defined build time.

RC_TIMER_RASTERIZE_TRIANGLES 

The time to rasterize the triangles. (See: rcRasterizeTriangle)

RC_TIMER_BUILD_COMPACTHEIGHTFIELD 

The time to build the compact heightfield. (See: rcBuildCompactHeightfield)

RC_TIMER_BUILD_CONTOURS 

The total time to build the contours. (See: rcBuildContours)

RC_TIMER_BUILD_CONTOURS_TRACE 

The time to trace the boundaries of the contours. (See: rcBuildContours)

RC_TIMER_BUILD_CONTOURS_SIMPLIFY 

The time to simplify the contours. (See: rcBuildContours)

RC_TIMER_FILTER_BORDER 

The time to filter ledge spans. (See: rcFilterLedgeSpans)

RC_TIMER_FILTER_WALKABLE 

The time to filter low height spans. (See: rcFilterWalkableLowHeightSpans)

RC_TIMER_MEDIAN_AREA 

The time to apply the median filter. (See: rcMedianFilterWalkableArea)

RC_TIMER_FILTER_LOW_OBSTACLES 

The time to filter low obstacles. (See: rcFilterLowHangingWalkableObstacles)

RC_TIMER_BUILD_POLYMESH 

The time to build the polygon mesh. (See: rcBuildPolyMesh)

RC_TIMER_MERGE_POLYMESH 

The time to merge polygon meshes. (See: rcMergePolyMeshes)

RC_TIMER_ERODE_AREA 

The time to erode the walkable area. (See: rcErodeWalkableArea)

RC_TIMER_MARK_BOX_AREA 

The time to mark a box area. (See: rcMarkBoxArea)

RC_TIMER_MARK_CYLINDER_AREA 

The time to mark a cylinder area. (See: rcMarkCylinderArea)

RC_TIMER_MARK_CONVEXPOLY_AREA 

The time to mark a convex polygon area. (See: rcMarkConvexPolyArea)

RC_TIMER_BUILD_DISTANCEFIELD 

The total time to build the distance field. (See: rcBuildDistanceField)

RC_TIMER_BUILD_DISTANCEFIELD_DIST 

The time to build the distances of the distance field. (See: rcBuildDistanceField)

RC_TIMER_BUILD_DISTANCEFIELD_BLUR 

The time to blur the distance field. (See: rcBuildDistanceField)

RC_TIMER_BUILD_REGIONS 

The total time to build the regions. (See: rcBuildRegions, rcBuildRegionsMonotone)

RC_TIMER_BUILD_REGIONS_WATERSHED 

The total time to apply the watershed algorithm. (See: rcBuildRegions)

RC_TIMER_BUILD_REGIONS_EXPAND 

The time to expand regions while applying the watershed algorithm. (See: rcBuildRegions)

RC_TIMER_BUILD_REGIONS_FLOOD 

The time to flood regions while applying the watershed algorithm. (See: rcBuildRegions)

RC_TIMER_BUILD_REGIONS_FILTER 

The time to filter out small regions. (See: rcBuildRegions, rcBuildRegionsMonotone)

RC_TIMER_BUILD_LAYERS 

The time to build heightfield layers. (See: rcBuildHeightfieldLayers)

RC_TIMER_BUILD_POLYMESHDETAIL 

The time to build the polygon mesh detail. (See: rcBuildPolyMeshDetail)

RC_TIMER_MERGE_POLYMESHDETAIL 

The time to merge polygon mesh details. (See: rcMergePolyMeshDetails)

RC_MAX_TIMERS 

The maximum number of timers. (Used for iterating timers.)

37 {
96 };
The maximum number of timers. (Used for iterating timers.)
Definition: Recast.h:95
The total time to build the contours. (See: rcBuildContours)
Definition: Recast.h:47
The time to build the distances of the distance field. (See: rcBuildDistanceField) ...
Definition: Recast.h:75
The user defined total time of the build.
Definition: Recast.h:39
The time to rasterize the triangles. (See: rcRasterizeTriangle)
Definition: Recast.h:43
The time to merge polygon meshes. (See: rcMergePolyMeshes)
Definition: Recast.h:63
The time to build the polygon mesh detail. (See: rcBuildPolyMeshDetail)
Definition: Recast.h:91
The time to trace the boundaries of the contours. (See: rcBuildContours)
Definition: Recast.h:49
The time to mark a box area. (See: rcMarkBoxArea)
Definition: Recast.h:67
The time to blur the distance field. (See: rcBuildDistanceField)
Definition: Recast.h:77
The time to build heightfield layers. (See: rcBuildHeightfieldLayers)
Definition: Recast.h:89
The total time to apply the watershed algorithm. (See: rcBuildRegions)
Definition: Recast.h:81
The total time to build the distance field. (See: rcBuildDistanceField)
Definition: Recast.h:73
The time to filter low height spans. (See: rcFilterWalkableLowHeightSpans)
Definition: Recast.h:55
The time to erode the walkable area. (See: rcErodeWalkableArea)
Definition: Recast.h:65
The time to build the compact heightfield. (See: rcBuildCompactHeightfield)
Definition: Recast.h:45
The total time to build the regions. (See: rcBuildRegions, rcBuildRegionsMonotone) ...
Definition: Recast.h:79
The time to flood regions while applying the watershed algorithm. (See: rcBuildRegions) ...
Definition: Recast.h:85
A user defined build time.
Definition: Recast.h:41
The time to expand regions while applying the watershed algorithm. (See: rcBuildRegions) ...
Definition: Recast.h:83
The time to merge polygon mesh details. (See: rcMergePolyMeshDetails)
Definition: Recast.h:93
The time to build the polygon mesh. (See: rcBuildPolyMesh)
Definition: Recast.h:61
The time to apply the median filter. (See: rcMedianFilterWalkableArea)
Definition: Recast.h:57
The time to mark a cylinder area. (See: rcMarkCylinderArea)
Definition: Recast.h:69
The time to filter ledge spans. (See: rcFilterLedgeSpans)
Definition: Recast.h:53
The time to mark a convex polygon area. (See: rcMarkConvexPolyArea)
Definition: Recast.h:71
The time to filter out small regions. (See: rcBuildRegions, rcBuildRegionsMonotone) ...
Definition: Recast.h:87
The time to simplify the contours. (See: rcBuildContours)
Definition: Recast.h:51
The time to filter low obstacles. (See: rcFilterLowHangingWalkableObstacles)
Definition: Recast.h:59

Function Documentation

template<class T >
T rcAbs ( a)
inline

Returns the absolute value.

Parameters
[in]aThe value.
Returns
The absolute value of the specified value.
577 { return a < 0 ? -a : a; }

+ Here is the caller graph for this function:

void rcAddSpan ( rcContext ,
rcHeightfield hf,
const int  x,
const int  y,
const unsigned short  smin,
const unsigned short  smax,
const unsigned char  area,
const int  flagMergeThr 
)

Adds a span to the specified heightfield.

Parameters
[in,out]ctxThe build context to use during the operation.
[in,out]hfAn initialized heightfield.
[in]xThe width index where the span is to be added. [Limits: 0 <= value < rcHeightfield::width]
[in]yThe height index where the span is to be added. [Limits: 0 <= value < rcHeightfield::height]
[in]sminThe minimum height of the span. [Limit: < smax] [Units: vx]
[in]smaxThe maximum height of the span. [Limit: <= RC_SPAN_MAX_HEIGHT] [Units: vx]
[in]areaThe area id of the span. [Limit: <= RC_WALKABLE_AREA)
[in]flagMergeThrThe merge theshold. [Limit: >= 0] [Units: vx]

The span addition can be set to favor flags. If the span is merged to another span and the new smax is within flagMergeThr units from the existing span, the span flags are merged.

See also
rcHeightfield, rcSpan.
167 {
168 // rcAssert(ctx);
169  addSpan(hf, x,y, smin, smax, area, flagMergeThr);
170 }
G3D::int16 y
Definition: Vector2int16.h:38
static void addSpan(rcHeightfield &hf, const int x, const int y, const unsigned short smin, const unsigned short smax, const unsigned char area, const int flagMergeThr)
Definition: RecastRasterization.cpp:85
G3D::int16 x
Definition: Vector2int16.h:37

+ Here is the call graph for this function:

rcCompactHeightfield* rcAllocCompactHeightfield ( )

Allocates a compact heightfield object using the Recast allocator.

Returns
A compact heightfield that is ready for initialization, or null on failure.
See also
rcBuildCompactHeightfield, rcFreeCompactHeightfield
96 {
98  memset(chf, 0, sizeof(rcCompactHeightfield));
99  return chf;
100 }
Definition: Recast.h:305
void * rcAlloc(int size, rcAllocHint hint)
Definition: RecastAlloc.cpp:44
Memory will persist after a function call.
Definition: RecastAlloc.h:26

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

rcContourSet* rcAllocContourSet ( )

Allocates a contour set object using the Recast allocator.

Returns
A contour set that is ready for initialization, or null on failure.
See also
rcBuildContours, rcFreeContourSet
135 {
137  memset(cset, 0, sizeof(rcContourSet));
138  return cset;
139 }
Definition: Recast.h:368
void * rcAlloc(int size, rcAllocHint hint)
Definition: RecastAlloc.cpp:44
Memory will persist after a function call.
Definition: RecastAlloc.h:26

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

rcHeightfield* rcAllocHeightfield ( )

Allocates a heightfield object using the Recast allocator.

Returns
A heightfield that is ready for initialization, or null on failure.
See also
rcCreateHeightfield, rcFreeHeightField
74 {
76  memset(hf, 0, sizeof(rcHeightfield));
77  return hf;
78 }
Definition: Recast.h:274
void * rcAlloc(int size, rcAllocHint hint)
Definition: RecastAlloc.cpp:44
Memory will persist after a function call.
Definition: RecastAlloc.h:26

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

rcHeightfieldLayerSet* rcAllocHeightfieldLayerSet ( )

Allocates a heightfield layer set using the Recast allocator.

Returns
A heightfield layer set that is ready for initialization, or null on failure.
See also
rcBuildHeightfieldLayers, rcFreeHeightfieldLayerSet
114 {
116  memset(lset, 0, sizeof(rcHeightfieldLayerSet));
117  return lset;
118 }
Definition: Recast.h:349
void * rcAlloc(int size, rcAllocHint hint)
Definition: RecastAlloc.cpp:44
Memory will persist after a function call.
Definition: RecastAlloc.h:26

+ Here is the call graph for this function:

rcPolyMesh* rcAllocPolyMesh ( )

Allocates a polygon mesh object using the Recast allocator.

Returns
A polygon mesh that is ready for initialization, or null on failure.
See also
rcBuildPolyMesh, rcFreePolyMesh
154 {
156  memset(pmesh, 0, sizeof(rcPolyMesh));
157  return pmesh;
158 }
void * rcAlloc(int size, rcAllocHint hint)
Definition: RecastAlloc.cpp:44
Definition: Recast.h:383
Memory will persist after a function call.
Definition: RecastAlloc.h:26

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

rcPolyMeshDetail* rcAllocPolyMeshDetail ( )

Allocates a detail mesh object using the Recast allocator.

Returns
A detail mesh that is ready for initialization, or null on failure.
See also
rcBuildPolyMeshDetail, rcFreePolyMeshDetail
172 {
174  memset(dmesh, 0, sizeof(rcPolyMeshDetail));
175  return dmesh;
176 }
void * rcAlloc(int size, rcAllocHint hint)
Definition: RecastAlloc.cpp:44
Memory will persist after a function call.
Definition: RecastAlloc.h:26
Definition: Recast.h:404

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

bool rcBuildCompactHeightfield ( rcContext ctx,
const int  walkableHeight,
const int  walkableClimb,
rcHeightfield hf,
rcCompactHeightfield chf 
)

Builds a compact heightfield representing open space, from a heightfield representing solid space.

Parameters
[in,out]ctxThe build context to use during the operation.
[in]walkableHeightMinimum floor to 'ceiling' height that will still allow the floor area to be considered walkable. [Limit: >= 3] [Units: vx]
[in]walkableClimbMaximum ledge height that is considered to still be traversable. [Limit: >=0] [Units: vx]
[in]hfThe heightfield to be compacted.
[out]chfThe resulting compact heightfield. (Must be pre-allocated.)
Returns
True if the operation completed successfully.

This is just the beginning of the process of fully building a compact heightfield. Various filters may be applied, then the distance field and regions built. E.g: rcBuildDistanceField and rcBuildRegions

See the rcConfig documentation for more information on the configuration parameters.

See also
rcAllocCompactHeightfield, rcHeightfield, rcCompactHeightfield, rcConfig
329 {
330  rcAssert(ctx);
331 
333 
334  const int w = hf.width;
335  const int h = hf.height;
336  const int spanCount = rcGetHeightFieldSpanCount(ctx, hf);
337 
338  // Fill in header.
339  chf.width = w;
340  chf.height = h;
341  chf.spanCount = spanCount;
342  chf.walkableHeight = walkableHeight;
343  chf.walkableClimb = walkableClimb;
344  chf.maxRegions = 0;
345  rcVcopy(chf.bmin, hf.bmin);
346  rcVcopy(chf.bmax, hf.bmax);
347  chf.bmax[1] += walkableHeight*hf.ch;
348  chf.cs = hf.cs;
349  chf.ch = hf.ch;
350  chf.cells = (rcCompactCell*)rcAlloc(sizeof(rcCompactCell)*w*h, RC_ALLOC_PERM);
351  if (!chf.cells)
352  {
353  ctx->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Out of memory 'chf.cells' (%d)", w*h);
354  return false;
355  }
356  memset(chf.cells, 0, sizeof(rcCompactCell)*w*h);
357  chf.spans = (rcCompactSpan*)rcAlloc(sizeof(rcCompactSpan)*spanCount, RC_ALLOC_PERM);
358  if (!chf.spans)
359  {
360  ctx->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Out of memory 'chf.spans' (%d)", spanCount);
361  return false;
362  }
363  memset(chf.spans, 0, sizeof(rcCompactSpan)*spanCount);
364  chf.areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*spanCount, RC_ALLOC_PERM);
365  if (!chf.areas)
366  {
367  ctx->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Out of memory 'chf.areas' (%d)", spanCount);
368  return false;
369  }
370  memset(chf.areas, RC_NULL_AREA, sizeof(unsigned char)*spanCount);
371 
372  const int MAX_HEIGHT = 0xffff;
373 
374  // Fill in cells and spans.
375  int idx = 0;
376  for (int y = 0; y < h; ++y)
377  {
378  for (int x = 0; x < w; ++x)
379  {
380  const rcSpan* s = hf.spans[x + y*w];
381  // If there are no spans at this cell, just leave the data to index=0, count=0.
382  if (!s) continue;
383  rcCompactCell& c = chf.cells[x+y*w];
384  c.index = idx;
385  c.count = 0;
386  while (s)
387  {
388  if (s->area != RC_NULL_AREA)
389  {
390  const int bot = (int)s->smax;
391  const int top = s->next ? (int)s->next->smin : MAX_HEIGHT;
392  chf.spans[idx].y = (unsigned short)rcClamp(bot, 0, 0xffff);
393  chf.spans[idx].h = (unsigned char)rcClamp(top - bot, 0, 0xff);
394  chf.areas[idx] = s->area;
395  idx++;
396  c.count++;
397  }
398  s = s->next;
399  }
400  }
401  }
402 
403  // Find neighbour connections.
404  const int MAX_LAYERS = RC_NOT_CONNECTED-1;
405  int tooHighNeighbour = 0;
406  for (int y = 0; y < h; ++y)
407  {
408  for (int x = 0; x < w; ++x)
409  {
410  const rcCompactCell& c = chf.cells[x+y*w];
411  for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
412  {
413  rcCompactSpan& s = chf.spans[i];
414 
415  for (int dir = 0; dir < 4; ++dir)
416  {
417  rcSetCon(s, dir, RC_NOT_CONNECTED);
418  const int nx = x + rcGetDirOffsetX(dir);
419  const int ny = y + rcGetDirOffsetY(dir);
420  // First check that the neighbour cell is in bounds.
421  if (nx < 0 || ny < 0 || nx >= w || ny >= h)
422  continue;
423 
424  // Iterate over all neighbour spans and check if any of the is
425  // accessible from current cell.
426  const rcCompactCell& nc = chf.cells[nx+ny*w];
427  for (int k = (int)nc.index, nk = (int)(nc.index+nc.count); k < nk; ++k)
428  {
429  const rcCompactSpan& ns = chf.spans[k];
430  const int bot = rcMax(s.y, ns.y);
431  const int top = rcMin(s.y+s.h, ns.y+ns.h);
432 
433  // Check that the gap between the spans is walkable,
434  // and that the climb height between the gaps is not too high.
435  if ((top - bot) >= walkableHeight && rcAbs((int)ns.y - (int)s.y) <= walkableClimb)
436  {
437  // Mark direction as walkable.
438  const int lidx = k - (int)nc.index;
439  if (lidx < 0 || lidx > MAX_LAYERS)
440  {
441  tooHighNeighbour = rcMax(tooHighNeighbour, lidx);
442  continue;
443  }
444  rcSetCon(s, dir, lidx);
445  break;
446  }
447  }
448 
449  }
450  }
451  }
452  }
453 
454  if (tooHighNeighbour > MAX_LAYERS)
455  {
456  ctx->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Heightfield has too many layers %d (max: %d)",
457  tooHighNeighbour, MAX_LAYERS);
458  }
459 
461 
462  return true;
463 }
int height
The height of the heightfield. (Along the z-axis in cell units.)
Definition: Recast.h:308
#define rcAssert
Definition: RecastAssert.h:30
int width
The width of the heightfield. (Along the x-axis in cell units.)
Definition: Recast.h:276
T rcAbs(T a)
Definition: Recast.h:577
unsigned short maxRegions
The maximum region id of any span within the field.
Definition: Recast.h:314
Represents a span of unobstructed space within a compact heightfield.
Definition: Recast.h:295
static const int RC_NOT_CONNECTED
Definition: Recast.h:547
float ch
The height of each cell. (The minimum increment along the y-axis.)
Definition: Recast.h:281
unsigned char area
The area id assigned to the span.
Definition: Recast.h:260
rcCompactCell * cells
Array of cells. [Size: width*height].
Definition: Recast.h:319
int rcGetDirOffsetY(int dir)
Definition: Recast.h:1048
unsigned short y
The lower extent of the span. (Measured from the heightfield's base.)
Definition: Recast.h:297
rcCompactSpan * spans
Array of spans. [Size: spanCount].
Definition: Recast.h:320
T rcMin(T a, T b)
Definition: Recast.h:566
unsigned int h
The height of the span. (Measured from y.)
Definition: Recast.h:300
unsigned int index
Index to the first span in the column.
Definition: Recast.h:290
Definition: Recast.h:256
float bmax[3]
The maximum bounds in world space. [(x, y, z)].
Definition: Recast.h:279
Provides information on the content of a cell column in a compact heightfield.
Definition: Recast.h:288
void rcSetCon(rcCompactSpan &s, int dir, int i)
Definition: Recast.h:1016
unsigned int count
Number of spans in the column.
Definition: Recast.h:291
An error log entry.
Definition: Recast.h:31
void * rcAlloc(int size, rcAllocHint hint)
Definition: RecastAlloc.cpp:44
int rcGetDirOffsetX(int dir)
Definition: Recast.h:1038
float cs
The size of each cell. (On the xz-plane.)
Definition: Recast.h:280
unsigned char * areas
Array containing area id data. [Size: spanCount].
Definition: Recast.h:322
G3D::int16 y
Definition: Vector2int16.h:38
float bmax[3]
The maximum bounds in world space. [(x, y, z)].
Definition: Recast.h:316
int width
The width of the heightfield. (Along the x-axis in cell units.)
Definition: Recast.h:307
The time to build the compact heightfield. (See: rcBuildCompactHeightfield)
Definition: Recast.h:45
unsigned int smin
The lower limit of the span. [Limit: < smax].
Definition: Recast.h:258
void rcVcopy(float *dest, const float *v)
Definition: Recast.h:677
void startTimer(const rcTimerLabel label)
Definition: Recast.h:131
int spanCount
The number of spans in the heightfield.
Definition: Recast.h:309
int walkableHeight
The walkable height used during the build of the field. (See: rcConfig::walkableHeight) ...
Definition: Recast.h:310
Memory will persist after a function call.
Definition: RecastAlloc.h:26
T rcClamp(T v, T mn, T mx)
Definition: Recast.h:589
unsigned int smax
The upper limit of the span. [Limit: <= RC_SPAN_MAX_HEIGHT].
Definition: Recast.h:259
float cs
The size of each cell. (On the xz-plane.)
Definition: Recast.h:317
rcSpan * next
The next span higher up in column.
Definition: Recast.h:261
float bmin[3]
The minimum bounds in world space. [(x, y, z)].
Definition: Recast.h:278
float ch
The height of each cell. (The minimum increment along the y-axis.)
Definition: Recast.h:318
static const unsigned char RC_NULL_AREA
Definition: Recast.h:538
T rcMax(T a, T b)
Definition: Recast.h:572
void log(const rcLogCategory category, const char *format,...)
Definition: Recast.cpp:55
G3D::int16 x
Definition: Vector2int16.h:37
int height
The height of the heightfield. (Along the z-axis in cell units.)
Definition: Recast.h:277
void stopTimer(const rcTimerLabel label)
Definition: Recast.h:135
int walkableClimb
The walkable climb used during the build of the field. (See: rcConfig::walkableClimb) ...
Definition: Recast.h:311
#define MAX_HEIGHT
Definition: Map.h:247
rcSpan ** spans
Heightfield of spans (width*height).
Definition: Recast.h:282
float bmin[3]
The minimum bounds in world space. [(x, y, z)].
Definition: Recast.h:315
int rcGetHeightFieldSpanCount(rcContext *ctx, rcHeightfield &hf)
Definition: Recast.cpp:297

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

bool rcBuildContours ( rcContext ctx,
rcCompactHeightfield chf,
const float  maxError,
const int  maxEdgeLen,
rcContourSet cset,
const int  buildFlags 
)

Builds a contour set from the region outlines in the provided compact heightfield.

Parameters
[in,out]ctxThe build context to use during the operation.
[in]chfA fully built compact heightfield.
[in]maxErrorThe maximum distance a simplfied contour's border edges should deviate the original raw contour. [Limit: >=0] [Units: wu]
[in]maxEdgeLenThe maximum allowed length for contour edges along the border of the mesh. [Limit: >=0] [Units: vx]
[out]csetThe resulting contour set. (Must be pre-allocated.)
[in]buildFlagsThe build flags. (See: rcBuildContoursFlags)
Returns
True if the operation completed successfully.

The raw contours will match the region outlines exactly. The maxError and maxEdgeLen parameters control how closely the simplified contours will match the raw contours.

Simplified contours are generated such that the vertices for portals between areas match up. (They are considered mandatory vertices.)

Setting maxEdgeLength to zero will disabled the edge length feature.

See the rcConfig documentation for more information on the configuration parameters.

See also
rcAllocContourSet, rcCompactHeightfield, rcContourSet, rcConfig
827 {
828  rcAssert(ctx);
829 
830  const int w = chf.width;
831  const int h = chf.height;
832  const int borderSize = chf.borderSize;
833 
835 
836  rcVcopy(cset.bmin, chf.bmin);
837  rcVcopy(cset.bmax, chf.bmax);
838  if (borderSize > 0)
839  {
840  // If the heightfield was build with bordersize, remove the offset.
841  const float pad = borderSize*chf.cs;
842  cset.bmin[0] += pad;
843  cset.bmin[2] += pad;
844  cset.bmax[0] -= pad;
845  cset.bmax[2] -= pad;
846  }
847  cset.cs = chf.cs;
848  cset.ch = chf.ch;
849  cset.width = chf.width - chf.borderSize*2;
850  cset.height = chf.height - chf.borderSize*2;
851  cset.borderSize = chf.borderSize;
852 
853  int maxContours = rcMax((int)chf.maxRegions, 8);
854  cset.conts = (rcContour*)rcAlloc(sizeof(rcContour)*maxContours, RC_ALLOC_PERM);
855  if (!cset.conts)
856  return false;
857  cset.nconts = 0;
858 
859  rcScopedDelete<unsigned char> flags = (unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP);
860  if (!flags)
861  {
862  ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'flags' (%d).", chf.spanCount);
863  return false;
864  }
865 
867 
868  // Mark boundaries.
869  for (int y = 0; y < h; ++y)
870  {
871  for (int x = 0; x < w; ++x)
872  {
873  const rcCompactCell& c = chf.cells[x+y*w];
874  for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
875  {
876  unsigned char res = 0;
877  const rcCompactSpan& s = chf.spans[i];
878  if (!chf.spans[i].reg || (chf.spans[i].reg & RC_BORDER_REG))
879  {
880  flags[i] = 0;
881  continue;
882  }
883  for (int dir = 0; dir < 4; ++dir)
884  {
885  unsigned short r = 0;
886  if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
887  {
888  const int ax = x + rcGetDirOffsetX(dir);
889  const int ay = y + rcGetDirOffsetY(dir);
890  const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);
891  r = chf.spans[ai].reg;
892  }
893  if (r == chf.spans[i].reg)
894  res |= (1 << dir);
895  }
896  flags[i] = res ^ 0xf; // Inverse, mark non connected edges.
897  }
898  }
899  }
900 
902 
903  rcIntArray verts(256);
904  rcIntArray simplified(64);
905 
906  for (int y = 0; y < h; ++y)
907  {
908  for (int x = 0; x < w; ++x)
909  {
910  const rcCompactCell& c = chf.cells[x+y*w];
911  for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
912  {
913  if (flags[i] == 0 || flags[i] == 0xf)
914  {
915  flags[i] = 0;
916  continue;
917  }
918  const unsigned short reg = chf.spans[i].reg;
919  if (!reg || (reg & RC_BORDER_REG))
920  continue;
921  const unsigned char area = chf.areas[i];
922 
923  verts.resize(0);
924  simplified.resize(0);
925 
927  walkContour(x, y, i, chf, flags, verts);
929 
931  simplifyContour(verts, simplified, maxError, maxEdgeLen, buildFlags);
932  removeDegenerateSegments(simplified);
934 
935 
936  // Store region->contour remap info.
937  // Create contour.
938  if (simplified.size()/4 >= 3)
939  {
940  if (cset.nconts >= maxContours)
941  {
942  // Allocate more contours.
943  // This happens when a region has holes.
944  const int oldMax = maxContours;
945  maxContours *= 2;
946  rcContour* newConts = (rcContour*)rcAlloc(sizeof(rcContour)*maxContours, RC_ALLOC_PERM);
947  for (int j = 0; j < cset.nconts; ++j)
948  {
949  newConts[j] = cset.conts[j];
950  // Reset source pointers to prevent data deletion.
951  cset.conts[j].verts = 0;
952  cset.conts[j].rverts = 0;
953  }
954  rcFree(cset.conts);
955  cset.conts = newConts;
956 
957  ctx->log(RC_LOG_WARNING, "rcBuildContours: Expanding max contours from %d to %d.", oldMax, maxContours);
958  }
959 
960  rcContour* cont = &cset.conts[cset.nconts++];
961 
962  cont->nverts = simplified.size()/4;
963  cont->verts = (int*)rcAlloc(sizeof(int)*cont->nverts*4, RC_ALLOC_PERM);
964  if (!cont->verts)
965  {
966  ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'verts' (%d).", cont->nverts);
967  return false;
968  }
969  memcpy(cont->verts, &simplified[0], sizeof(int)*cont->nverts*4);
970  if (borderSize > 0)
971  {
972  // If the heightfield was build with bordersize, remove the offset.
973  for (int j = 0; j < cont->nverts; ++j)
974  {
975  int* v = &cont->verts[j*4];
976  v[0] -= borderSize;
977  v[2] -= borderSize;
978  }
979  }
980 
981  cont->nrverts = verts.size()/4;
982  cont->rverts = (int*)rcAlloc(sizeof(int)*cont->nrverts*4, RC_ALLOC_PERM);
983  if (!cont->rverts)
984  {
985  ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'rverts' (%d).", cont->nrverts);
986  return false;
987  }
988  memcpy(cont->rverts, &verts[0], sizeof(int)*cont->nrverts*4);
989  if (borderSize > 0)
990  {
991  // If the heightfield was build with bordersize, remove the offset.
992  for (int j = 0; j < cont->nrverts; ++j)
993  {
994  int* v = &cont->rverts[j*4];
995  v[0] -= borderSize;
996  v[2] -= borderSize;
997  }
998  }
999 
1000  cont->reg = reg;
1001  cont->area = area;
1002  }
1003  }
1004  }
1005  }
1006 
1007  // Merge holes if needed.
1008  if (cset.nconts > 0)
1009  {
1010  // Calculate winding of all polygons.
1011  rcScopedDelete<char> winding = (char*)rcAlloc(sizeof(char)*cset.nconts, RC_ALLOC_TEMP);
1012  if (!winding)
1013  {
1014  ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'hole' (%d).", cset.nconts);
1015  return false;
1016  }
1017  int nholes = 0;
1018  for (int i = 0; i < cset.nconts; ++i)
1019  {
1020  rcContour& cont = cset.conts[i];
1021  // If the contour is wound backwards, it is a hole.
1022  winding[i] = calcAreaOfPolygon2D(cont.verts, cont.nverts) < 0 ? -1 : 1;
1023  if (winding[i] < 0)
1024  nholes++;
1025  }
1026 
1027  if (nholes > 0)
1028  {
1029  // Collect outline contour and holes contours per region.
1030  // We assume that there is one outline and multiple holes.
1031  const int nregions = chf.maxRegions+1;
1033  if (!regions)
1034  {
1035  ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'regions' (%d).", nregions);
1036  return false;
1037  }
1038  memset(regions, 0, sizeof(rcContourRegion)*nregions);
1039 
1041  if (!holes)
1042  {
1043  ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'holes' (%d).", cset.nconts);
1044  return false;
1045  }
1046  memset(holes, 0, sizeof(rcContourHole)*cset.nconts);
1047 
1048  for (int i = 0; i < cset.nconts; ++i)
1049  {
1050  rcContour& cont = cset.conts[i];
1051  // Positively would contours are outlines, negative holes.
1052  if (winding[i] > 0)
1053  {
1054  if (regions[cont.reg].outline)
1055  ctx->log(RC_LOG_ERROR, "rcBuildContours: Multiple outlines for region %d.", cont.reg);
1056  regions[cont.reg].outline = &cont;
1057  }
1058  else
1059  {
1060  regions[cont.reg].nholes++;
1061  }
1062  }
1063  int index = 0;
1064  for (int i = 0; i < nregions; i++)
1065  {
1066  if (regions[i].nholes > 0)
1067  {
1068  regions[i].holes = &holes[index];
1069  index += regions[i].nholes;
1070  regions[i].nholes = 0;
1071  }
1072  }
1073  for (int i = 0; i < cset.nconts; ++i)
1074  {
1075  rcContour& cont = cset.conts[i];
1076  rcContourRegion& reg = regions[cont.reg];
1077  if (winding[i] < 0)
1078  reg.holes[reg.nholes++].contour = &cont;
1079  }
1080 
1081  // Finally merge each regions holes into the outline.
1082  for (int i = 0; i < nregions; i++)
1083  {
1084  rcContourRegion& reg = regions[i];
1085  if (!reg.nholes) continue;
1086 
1087  if (reg.outline)
1088  {
1089  mergeRegionHoles(ctx, reg);
1090  }
1091  else
1092  {
1093  // The region does not have an outline.
1094  // This can happen if the contour becaomes selfoverlapping because of
1095  // too aggressive simplification settings.
1096  ctx->log(RC_LOG_ERROR, "rcBuildContours: Bad outline for region %d, contour simplification is likely too aggressive.", i);
1097  }
1098  }
1099  }
1100 
1101  }
1102 
1104 
1105  return true;
1106 }
float bmin[3]
The minimum bounds in world space. [(x, y, z)].
Definition: Recast.h:372
int height
The height of the heightfield. (Along the z-axis in cell units.)
Definition: Recast.h:308
#define rcAssert
Definition: RecastAssert.h:30
The total time to build the contours. (See: rcBuildContours)
Definition: Recast.h:47
static void simplifyContour(rcIntArray &points, rcIntArray &simplified, const float maxError, const int maxEdgeLen, const int buildFlags)
Definition: RecastContour.cpp:210
int borderSize
The AABB border size used during the build of the field. (See: rcConfig::borderSize) ...
Definition: Recast.h:312
unsigned short maxRegions
The maximum region id of any span within the field.
Definition: Recast.h:314
Represents a span of unobstructed space within a compact heightfield.
Definition: Recast.h:295
int nrverts
The number of vertices in the raw contour.
Definition: Recast.h:361
static int calcAreaOfPolygon2D(const int *verts, const int nverts)
Definition: RecastContour.cpp:454
IntFormatSpec< int, AlignTypeSpec< TYPE_CODE >, Char > pad(int value, unsigned width, Char fill= ' ')
static const int RC_NOT_CONNECTED
Definition: Recast.h:547
unsigned short reg
The id of the region the span belongs to. (Or zero if not in a region.)
Definition: Recast.h:298
int nverts
The number of vertices in the simplified contour.
Definition: Recast.h:359
rcCompactCell * cells
Array of cells. [Size: width*height].
Definition: Recast.h:319
int rcGetDirOffsetY(int dir)
Definition: Recast.h:1048
rcCompactSpan * spans
Array of spans. [Size: spanCount].
Definition: Recast.h:320
int * rverts
Raw contour vertex and connection data. [Size: 4 * nrverts].
Definition: Recast.h:360
int rcGetCon(const rcCompactSpan &s, int dir)
Definition: Recast.h:1028
unsigned int index
Index to the first span in the column.
Definition: Recast.h:290
rcContour * conts
An array of the contours in the set. [Size: nconts].
Definition: Recast.h:370
int height
The height of the set. (Along the z-axis in cell units.)
Definition: Recast.h:377
Provides information on the content of a cell column in a compact heightfield.
Definition: Recast.h:288
The time to trace the boundaries of the contours. (See: rcBuildContours)
Definition: Recast.h:49
int nconts
The number of contours in the set.
Definition: Recast.h:371
int * verts
Simplified contour vertex and connection data. [Size: 4 * nverts].
Definition: Recast.h:358
static void walkContour(int x, int y, int i, rcCompactHeightfield &chf, unsigned char *flags, rcIntArray &points)
Definition: RecastContour.cpp:104
Represents a simple, non-overlapping contour in field space.
Definition: Recast.h:356
unsigned int count
Number of spans in the column.
Definition: Recast.h:291
An error log entry.
Definition: Recast.h:31
Definition: RecastAlloc.h:105
static void removeDegenerateSegments(rcIntArray &simplified)
Definition: RecastContour.cpp:580
void rcFree(void *ptr)
Definition: RecastAlloc.cpp:55
unsigned char area
The area id of the contour.
Definition: Recast.h:363
void * rcAlloc(int size, rcAllocHint hint)
Definition: RecastAlloc.cpp:44
int rcGetDirOffsetX(int dir)
Definition: Recast.h:1038
rcContour * contour
Definition: RecastContour.cpp:652
unsigned char * areas
Array containing area id data. [Size: spanCount].
Definition: Recast.h:322
float bmax[3]
The maximum bounds in world space. [(x, y, z)].
Definition: Recast.h:373
G3D::int16 y
Definition: Vector2int16.h:38
float bmax[3]
The maximum bounds in world space. [(x, y, z)].
Definition: Recast.h:316
int width
The width of the heightfield. (Along the x-axis in cell units.)
Definition: Recast.h:307
uint8 holes[ADT_CELLS_PER_GRID][ADT_CELLS_PER_GRID][8]
Definition: System.cpp:444
unsigned short reg
The region id of the contour.
Definition: Recast.h:362
void rcVcopy(float *dest, const float *v)
Definition: Recast.h:677
float cs
The size of each cell. (On the xz-plane.)
Definition: Recast.h:374
Definition: RecastContour.cpp:656
void startTimer(const rcTimerLabel label)
Definition: Recast.h:131
int spanCount
The number of spans in the heightfield.
Definition: Recast.h:309
Memory will persist after a function call.
Definition: RecastAlloc.h:26
rcContourHole * holes
Definition: RecastContour.cpp:659
float cs
The size of each cell. (On the xz-plane.)
Definition: Recast.h:317
Definition: RecastContour.cpp:650
int width
The width of the set. (Along the x-axis in cell units.)
Definition: Recast.h:376
float ch
The height of each cell. (The minimum increment along the y-axis.)
Definition: Recast.h:318
Memory used temporarily within a function.
Definition: RecastAlloc.h:27
T rcMax(T a, T b)
Definition: Recast.h:572
void log(const rcLogCategory category, const char *format,...)
Definition: Recast.cpp:55
uint8 flags
Definition: DisableMgr.cpp:44
int borderSize
The AABB border size used to generate the source data from which the contours were derived...
Definition: Recast.h:378
float ch
The height of each cell. (The minimum increment along the y-axis.)
Definition: Recast.h:375
G3D::int16 x
Definition: Vector2int16.h:37
void stopTimer(const rcTimerLabel label)
Definition: Recast.h:135
int nholes
Definition: RecastContour.cpp:660
rcContour * outline
Definition: RecastContour.cpp:658
static const unsigned short RC_BORDER_REG
Definition: Recast.h:498
A warning log entry.
Definition: Recast.h:30
A simple dynamic array of integers.
Definition: RecastAlloc.h:61
The time to simplify the contours. (See: rcBuildContours)
Definition: Recast.h:51
float bmin[3]
The minimum bounds in world space. [(x, y, z)].
Definition: Recast.h:315
static void mergeRegionHoles(rcContext *ctx, rcContourRegion &region)
Definition: RecastContour.cpp:722

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

bool rcBuildDistanceField ( rcContext ctx,
rcCompactHeightfield chf 
)

Builds the distance field for the specified compact heightfield.

Parameters
[in,out]ctxThe build context to use during the operation.
[in,out]chfA populated compact heightfield.
Returns
True if the operation completed successfully.

This is usually the second to the last step in creating a fully built compact heightfield. This step is required before regions are built using rcBuildRegions or rcBuildRegionsMonotone.

After this step, the distance data is available via the rcCompactHeightfield::maxDistance and rcCompactHeightfield::dist fields.

See also
rcCompactHeightfield, rcBuildRegions, rcBuildRegionsMonotone
1257 {
1258  rcAssert(ctx);
1259 
1261 
1262  if (chf.dist)
1263  {
1264  rcFree(chf.dist);
1265  chf.dist = 0;
1266  }
1267 
1268  unsigned short* src = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP);
1269  if (!src)
1270  {
1271  ctx->log(RC_LOG_ERROR, "rcBuildDistanceField: Out of memory 'src' (%d).", chf.spanCount);
1272  return false;
1273  }
1274  unsigned short* dst = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP);
1275  if (!dst)
1276  {
1277  ctx->log(RC_LOG_ERROR, "rcBuildDistanceField: Out of memory 'dst' (%d).", chf.spanCount);
1278  rcFree(src);
1279  return false;
1280  }
1281 
1282  unsigned short maxDist = 0;
1283 
1285 
1286  calculateDistanceField(chf, src, maxDist);
1287  chf.maxDistance = maxDist;
1288 
1290 
1292 
1293  // Blur
1294  if (boxBlur(chf, 1, src, dst) != src)
1295  rcSwap(src, dst);
1296 
1297  // Store distance.
1298  chf.dist = src;
1299 
1301 
1303 
1304  rcFree(dst);
1305 
1306  return true;
1307 }
#define rcAssert
Definition: RecastAssert.h:30
The time to build the distances of the distance field. (See: rcBuildDistanceField) ...
Definition: Recast.h:75
unsigned short * dist
Array containing border distance data. [Size: spanCount].
Definition: Recast.h:321
void rcSwap(T &a, T &b)
Definition: Recast.h:560
An error log entry.
Definition: Recast.h:31
The time to blur the distance field. (See: rcBuildDistanceField)
Definition: Recast.h:77
void rcFree(void *ptr)
Definition: RecastAlloc.cpp:55
void * rcAlloc(int size, rcAllocHint hint)
Definition: RecastAlloc.cpp:44
The total time to build the distance field. (See: rcBuildDistanceField)
Definition: Recast.h:73
static void calculateDistanceField(rcCompactHeightfield &chf, unsigned short *src, unsigned short &maxDist)
Definition: RecastRegion.cpp:31
void startTimer(const rcTimerLabel label)
Definition: Recast.h:131
int spanCount
The number of spans in the heightfield.
Definition: Recast.h:309
unsigned short maxDistance
The maximum distance value of any span within the field.
Definition: Recast.h:313
Memory used temporarily within a function.
Definition: RecastAlloc.h:27
void log(const rcLogCategory category, const char *format,...)
Definition: Recast.cpp:55
void stopTimer(const rcTimerLabel label)
Definition: Recast.h:135
static unsigned short * boxBlur(rcCompactHeightfield &chf, int thr, unsigned short *src, unsigned short *dst)
Definition: RecastRegion.cpp:184

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

bool rcBuildHeightfieldLayers ( rcContext ctx,
rcCompactHeightfield chf,
const int  borderSize,
const int  walkableHeight,
rcHeightfieldLayerSet lset 
)

Builds a layer set from the specified compact heightfield.

Parameters
[in,out]ctxThe build context to use during the operation.
[in]chfA fully built compact heightfield.
[in]borderSizeThe size of the non-navigable border around the heightfield. [Limit: >=0] [Units: vx]
[in]walkableHeightMinimum floor to 'ceiling' height that will still allow the floor area to be considered walkable. [Limit: >= 3] [Units: vx]
[out]lsetThe resulting layer set. (Must be pre-allocated.)
Returns
True if the operation completed successfully.

See the rcConfig documentation for more information on the configuration parameters.

See also
rcAllocHeightfieldLayerSet, rcCompactHeightfield, rcHeightfieldLayerSet, rcConfig
87 {
88  rcAssert(ctx);
89 
91 
92  const int w = chf.width;
93  const int h = chf.height;
94 
95  rcScopedDelete<unsigned char> srcReg = (unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP);
96  if (!srcReg)
97  {
98  ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'srcReg' (%d).", chf.spanCount);
99  return false;
100  }
101  memset(srcReg,0xff,sizeof(unsigned char)*chf.spanCount);
102 
103  const int nsweeps = chf.width;
105  if (!sweeps)
106  {
107  ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'sweeps' (%d).", nsweeps);
108  return false;
109  }
110 
111 
112  // Partition walkable area into monotone regions.
113  int prevCount[256];
114  unsigned char regId = 0;
115 
116  for (int y = borderSize; y < h-borderSize; ++y)
117  {
118  memset(prevCount,0,sizeof(int)*regId);
119  unsigned char sweepId = 0;
120 
121  for (int x = borderSize; x < w-borderSize; ++x)
122  {
123  const rcCompactCell& c = chf.cells[x+y*w];
124 
125  for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
126  {
127  const rcCompactSpan& s = chf.spans[i];
128  if (chf.areas[i] == RC_NULL_AREA) continue;
129 
130  unsigned char sid = 0xff;
131 
132  // -x
133  if (rcGetCon(s, 0) != RC_NOT_CONNECTED)
134  {
135  const int ax = x + rcGetDirOffsetX(0);
136  const int ay = y + rcGetDirOffsetY(0);
137  const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 0);
138  if (chf.areas[ai] != RC_NULL_AREA && srcReg[ai] != 0xff)
139  sid = srcReg[ai];
140  }
141 
142  if (sid == 0xff)
143  {
144  sid = sweepId++;
145  sweeps[sid].nei = 0xff;
146  sweeps[sid].ns = 0;
147  }
148 
149  // -y
150  if (rcGetCon(s,3) != RC_NOT_CONNECTED)
151  {
152  const int ax = x + rcGetDirOffsetX(3);
153  const int ay = y + rcGetDirOffsetY(3);
154  const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 3);
155  const unsigned char nr = srcReg[ai];
156  if (nr != 0xff)
157  {
158  // Set neighbour when first valid neighbour is encoutered.
159  if (sweeps[sid].ns == 0)
160  sweeps[sid].nei = nr;
161 
162  if (sweeps[sid].nei == nr)
163  {
164  // Update existing neighbour
165  sweeps[sid].ns++;
166  prevCount[nr]++;
167  }
168  else
169  {
170  // This is hit if there is nore than one neighbour.
171  // Invalidate the neighbour.
172  sweeps[sid].nei = 0xff;
173  }
174  }
175  }
176 
177  srcReg[i] = sid;
178  }
179  }
180 
181  // Create unique ID.
182  for (int i = 0; i < sweepId; ++i)
183  {
184  // If the neighbour is set and there is only one continuous connection to it,
185  // the sweep will be merged with the previous one, else new region is created.
186  if (sweeps[i].nei != 0xff && prevCount[sweeps[i].nei] == (int)sweeps[i].ns)
187  {
188  sweeps[i].id = sweeps[i].nei;
189  }
190  else
191  {
192  if (regId == 255)
193  {
194  ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Region ID overflow.");
195  return false;
196  }
197  sweeps[i].id = regId++;
198  }
199  }
200 
201  // Remap local sweep ids to region ids.
202  for (int x = borderSize; x < w-borderSize; ++x)
203  {
204  const rcCompactCell& c = chf.cells[x+y*w];
205  for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
206  {
207  if (srcReg[i] != 0xff)
208  srcReg[i] = sweeps[srcReg[i]].id;
209  }
210  }
211  }
212 
213  // Allocate and init layer regions.
214  const int nregs = (int)regId;
216  if (!regs)
217  {
218  ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'regs' (%d).", nregs);
219  return false;
220  }
221  memset(regs, 0, sizeof(rcLayerRegion)*nregs);
222  for (int i = 0; i < nregs; ++i)
223  {
224  regs[i].layerId = 0xff;
225  regs[i].ymin = 0xffff;
226  regs[i].ymax = 0;
227  }
228 
229  // Find region neighbours and overlapping regions.
230  for (int y = 0; y < h; ++y)
231  {
232  for (int x = 0; x < w; ++x)
233  {
234  const rcCompactCell& c = chf.cells[x+y*w];
235 
236  unsigned char lregs[RC_MAX_LAYERS];
237  int nlregs = 0;
238 
239  for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
240  {
241  const rcCompactSpan& s = chf.spans[i];
242  const unsigned char ri = srcReg[i];
243  if (ri == 0xff) continue;
244 
245  regs[ri].ymin = rcMin(regs[ri].ymin, s.y);
246  regs[ri].ymax = rcMax(regs[ri].ymax, s.y);
247 
248  // Collect all region layers.
249  if (nlregs < RC_MAX_LAYERS)
250  lregs[nlregs++] = ri;
251 
252  // Update neighbours
253  for (int dir = 0; dir < 4; ++dir)
254  {
255  if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
256  {
257  const int ax = x + rcGetDirOffsetX(dir);
258  const int ay = y + rcGetDirOffsetY(dir);
259  const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);
260  const unsigned char rai = srcReg[ai];
261  if (rai != 0xff && rai != ri)
262  addUnique(regs[ri].neis, regs[ri].nneis, rai);
263  }
264  }
265 
266  }
267 
268  // Update overlapping regions.
269  for (int i = 0; i < nlregs-1; ++i)
270  {
271  for (int j = i+1; j < nlregs; ++j)
272  {
273  if (lregs[i] != lregs[j])
274  {
275  rcLayerRegion& ri = regs[lregs[i]];
276  rcLayerRegion& rj = regs[lregs[j]];
277  addUnique(ri.layers, ri.nlayers, lregs[j]);
278  addUnique(rj.layers, rj.nlayers, lregs[i]);
279  }
280  }
281  }
282 
283  }
284  }
285 
286  // Create 2D layers from regions.
287  unsigned char layerId = 0;
288 
289  static const int MAX_STACK = 64;
290  unsigned char stack[MAX_STACK];
291  int nstack = 0;
292 
293  for (int i = 0; i < nregs; ++i)
294  {
295  rcLayerRegion& root = regs[i];
296  // Skip already visited.
297  if (root.layerId != 0xff)
298  continue;
299 
300  // Start search.
301  root.layerId = layerId;
302  root.base = 1;
303 
304  nstack = 0;
305  stack[nstack++] = (unsigned char)i;
306 
307  while (nstack)
308  {
309  // Pop front
310  rcLayerRegion& reg = regs[stack[0]];
311  nstack--;
312  for (int j = 0; j < nstack; ++j)
313  stack[j] = stack[j+1];
314 
315  const int nneis = (int)reg.nneis;
316  for (int j = 0; j < nneis; ++j)
317  {
318  const unsigned char nei = reg.neis[j];
319  rcLayerRegion& regn = regs[nei];
320  // Skip already visited.
321  if (regn.layerId != 0xff)
322  continue;
323  // Skip if the neighbour is overlapping root region.
324  if (contains(root.layers, root.nlayers, nei))
325  continue;
326  // Skip if the height range would become too large.
327  const int ymin = rcMin(root.ymin, regn.ymin);
328  const int ymax = rcMax(root.ymax, regn.ymax);
329  if ((ymax - ymin) >= 255)
330  continue;
331 
332  if (nstack < MAX_STACK)
333  {
334  // Deepen
335  stack[nstack++] = (unsigned char)nei;
336 
337  // Mark layer id
338  regn.layerId = layerId;
339  // Merge current layers to root.
340  for (int k = 0; k < regn.nlayers; ++k)
341  addUnique(root.layers, root.nlayers, regn.layers[k]);
342  root.ymin = rcMin(root.ymin, regn.ymin);
343  root.ymax = rcMax(root.ymax, regn.ymax);
344  }
345  }
346  }
347 
348  layerId++;
349  }
350 
351  // Merge non-overlapping regions that are close in height.
352  const unsigned short mergeHeight = (unsigned short)walkableHeight * 4;
353 
354  for (int i = 0; i < nregs; ++i)
355  {
356  rcLayerRegion& ri = regs[i];
357  if (!ri.base) continue;
358 
359  unsigned char newId = ri.layerId;
360 
361  for (;;)
362  {
363  unsigned char oldId = 0xff;
364 
365  for (int j = 0; j < nregs; ++j)
366  {
367  if (i == j) continue;
368  rcLayerRegion& rj = regs[j];
369  if (!rj.base) continue;
370 
371  // Skip if the regions are not close to each other.
372  if (!overlapRange(ri.ymin,ri.ymax+mergeHeight, rj.ymin,rj.ymax+mergeHeight))
373  continue;
374  // Skip if the height range would become too large.
375  const int ymin = rcMin(ri.ymin, rj.ymin);
376  const int ymax = rcMax(ri.ymax, rj.ymax);
377  if ((ymax - ymin) >= 255)
378  continue;
379 
380  // Make sure that there is no overlap when merging 'ri' and 'rj'.
381  bool overlap = false;
382  // Iterate over all regions which have the same layerId as 'rj'
383  for (int k = 0; k < nregs; ++k)
384  {
385  if (regs[k].layerId != rj.layerId)
386  continue;
387  // Check if region 'k' is overlapping region 'ri'
388  // Index to 'regs' is the same as region id.
389  if (contains(ri.layers,ri.nlayers, (unsigned char)k))
390  {
391  overlap = true;
392  break;
393  }
394  }
395  // Cannot merge of regions overlap.
396  if (overlap)
397  continue;
398 
399  // Can merge i and j.
400  oldId = rj.layerId;
401  break;
402  }
403 
404  // Could not find anything to merge with, stop.
405  if (oldId == 0xff)
406  break;
407 
408  // Merge
409  for (int j = 0; j < nregs; ++j)
410  {
411  rcLayerRegion& rj = regs[j];
412  if (rj.layerId == oldId)
413  {
414  rj.base = 0;
415  // Remap layerIds.
416  rj.layerId = newId;
417  // Add overlaid layers from 'rj' to 'ri'.
418  for (int k = 0; k < rj.nlayers; ++k)
419  addUnique(ri.layers, ri.nlayers, rj.layers[k]);
420  // Update height bounds.
421  ri.ymin = rcMin(ri.ymin, rj.ymin);
422  ri.ymax = rcMax(ri.ymax, rj.ymax);
423  }
424  }
425  }
426  }
427 
428  // Compact layerIds
429  unsigned char remap[256];
430  memset(remap, 0, 256);
431 
432  // Find number of unique layers.
433  layerId = 0;
434  for (int i = 0; i < nregs; ++i)
435  remap[regs[i].layerId] = 1;
436  for (int i = 0; i < 256; ++i)
437  {
438  if (remap[i])
439  remap[i] = layerId++;
440  else
441  remap[i] = 0xff;
442  }
443  // Remap ids.
444  for (int i = 0; i < nregs; ++i)
445  regs[i].layerId = remap[regs[i].layerId];
446 
447  // No layers, return empty.
448  if (layerId == 0)
449  {
451  return true;
452  }
453 
454  // Create layers.
455  rcAssert(lset.layers == 0);
456 
457  const int lw = w - borderSize*2;
458  const int lh = h - borderSize*2;
459 
460  // Build contracted bbox for layers.
461  float bmin[3], bmax[3];
462  rcVcopy(bmin, chf.bmin);
463  rcVcopy(bmax, chf.bmax);
464  bmin[0] += borderSize*chf.cs;
465  bmin[2] += borderSize*chf.cs;
466  bmax[0] -= borderSize*chf.cs;
467  bmax[2] -= borderSize*chf.cs;
468 
469  lset.nlayers = (int)layerId;
470 
472  if (!lset.layers)
473  {
474  ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'layers' (%d).", lset.nlayers);
475  return false;
476  }
477  memset(lset.layers, 0, sizeof(rcHeightfieldLayer)*lset.nlayers);
478 
479 
480  // Store layers.
481  for (int i = 0; i < lset.nlayers; ++i)
482  {
483  unsigned char curId = (unsigned char)i;
484 
485  rcHeightfieldLayer* layer = &lset.layers[i];
486 
487  const int gridSize = sizeof(unsigned char)*lw*lh;
488 
489  layer->heights = (unsigned char*)rcAlloc(gridSize, RC_ALLOC_PERM);
490  if (!layer->heights)
491  {
492  ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'heights' (%d).", gridSize);
493  return false;
494  }
495  memset(layer->heights, 0xff, gridSize);
496 
497  layer->areas = (unsigned char*)rcAlloc(gridSize, RC_ALLOC_PERM);
498  if (!layer->areas)
499  {
500  ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'areas' (%d).", gridSize);
501  return false;
502  }
503  memset(layer->areas, 0, gridSize);
504 
505  layer->cons = (unsigned char*)rcAlloc(gridSize, RC_ALLOC_PERM);
506  if (!layer->cons)
507  {
508  ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'cons' (%d).", gridSize);
509  return false;
510  }
511  memset(layer->cons, 0, gridSize);
512 
513  // Find layer height bounds.
514  int hmin = 0, hmax = 0;
515  for (int j = 0; j < nregs; ++j)
516  {
517  if (regs[j].base && regs[j].layerId == curId)
518  {
519  hmin = (int)regs[j].ymin;
520  hmax = (int)regs[j].ymax;
521  }
522  }
523 
524  layer->width = lw;
525  layer->height = lh;
526  layer->cs = chf.cs;
527  layer->ch = chf.ch;
528 
529  // Adjust the bbox to fit the heightfield.
530  rcVcopy(layer->bmin, bmin);
531  rcVcopy(layer->bmax, bmax);
532  layer->bmin[1] = bmin[1] + hmin*chf.ch;
533  layer->bmax[1] = bmin[1] + hmax*chf.ch;
534  layer->hmin = hmin;
535  layer->hmax = hmax;
536 
537  // Update usable data region.
538  layer->minx = layer->width;
539  layer->maxx = 0;
540  layer->miny = layer->height;
541  layer->maxy = 0;
542 
543  // Copy height and area from compact heightfield.
544  for (int y = 0; y < lh; ++y)
545  {
546  for (int x = 0; x < lw; ++x)
547  {
548  const int cx = borderSize+x;
549  const int cy = borderSize+y;
550  const rcCompactCell& c = chf.cells[cx+cy*w];
551  for (int j = (int)c.index, nj = (int)(c.index+c.count); j < nj; ++j)
552  {
553  const rcCompactSpan& s = chf.spans[j];
554  // Skip unassigned regions.
555  if (srcReg[j] == 0xff)
556  continue;
557  // Skip of does nto belong to current layer.
558  unsigned char lid = regs[srcReg[j]].layerId;
559  if (lid != curId)
560  continue;
561 
562  // Update data bounds.
563  layer->minx = rcMin(layer->minx, x);
564  layer->maxx = rcMax(layer->maxx, x);
565  layer->miny = rcMin(layer->miny, y);
566  layer->maxy = rcMax(layer->maxy, y);
567 
568  // Store height and area type.
569  const int idx = x+y*lw;
570  layer->heights[idx] = (unsigned char)(s.y - hmin);
571  layer->areas[idx] = chf.areas[j];
572 
573  // Check connection.
574  unsigned char portal = 0;
575  unsigned char con = 0;
576  for (int dir = 0; dir < 4; ++dir)
577  {
578  if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
579  {
580  const int ax = cx + rcGetDirOffsetX(dir);
581  const int ay = cy + rcGetDirOffsetY(dir);
582  const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);
583  unsigned char alid = srcReg[ai] != 0xff ? regs[srcReg[ai]].layerId : 0xff;
584  // Portal mask
585  if (chf.areas[ai] != RC_NULL_AREA && lid != alid)
586  {
587  portal |= (unsigned char)(1<<dir);
588  // Update height so that it matches on both sides of the portal.
589  const rcCompactSpan& as = chf.spans[ai];
590  if (as.y > hmin)
591  layer->heights[idx] = rcMax(layer->heights[idx], (unsigned char)(as.y - hmin));
592  }
593  // Valid connection mask
594  if (chf.areas[ai] != RC_NULL_AREA && lid == alid)
595  {
596  const int nx = ax - borderSize;
597  const int ny = ay - borderSize;
598  if (nx >= 0 && ny >= 0 && nx < lw && ny < lh)
599  con |= (unsigned char)(1<<dir);
600  }
601  }
602  }
603 
604  layer->cons[idx] = (portal << 4) | con;
605  }
606  }
607  }
608 
609  if (layer->minx > layer->maxx)
610  layer->minx = layer->maxx = 0;
611  if (layer->miny > layer->maxy)
612  layer->miny = layer->maxy = 0;
613  }
614 
616 
617  return true;
618 }
rcHeightfieldLayer * layers
The layers in the set. [Size: nlayers].
Definition: Recast.h:351
int height
The height of the heightfield. (Along the z-axis in cell units.)
Definition: Recast.h:308
#define rcAssert
Definition: RecastAssert.h:30
Definition: RecastLayers.cpp:33
static void addUnique(unsigned char *a, unsigned char &an, unsigned char v)
Definition: RecastLayers.cpp:45
Represents a span of unobstructed space within a compact heightfield.
Definition: Recast.h:295
int hmax
The maximum height bounds of usable data. (Along the y-axis.)
Definition: Recast.h:340
unsigned char neis[RC_MAX_NEIS]
Definition: RecastLayers.cpp:36
static const int RC_NOT_CONNECTED
Definition: Recast.h:547
unsigned char * heights
The heightfield. [Size: width * height].
Definition: Recast.h:341
rcCompactCell * cells
Array of cells. [Size: width*height].
Definition: Recast.h:319
int rcGetDirOffsetY(int dir)
Definition: Recast.h:1048
unsigned short y
The lower extent of the span. (Measured from the heightfield's base.)
Definition: Recast.h:297
rcCompactSpan * spans
Array of spans. [Size: spanCount].
Definition: Recast.h:320
T rcMin(T a, T b)
Definition: Recast.h:566
int rcGetCon(const rcCompactSpan &s, int dir)
Definition: Recast.h:1028
unsigned int index
Index to the first span in the column.
Definition: Recast.h:290
unsigned short ymin
Definition: RecastLayers.cpp:37
Provides information on the content of a cell column in a compact heightfield.
Definition: Recast.h:288
Definition: RecastLayers.cpp:72
unsigned char * areas
Area ids. [Size: Same as heights].
Definition: Recast.h:342
unsigned int count
Number of spans in the column.
Definition: Recast.h:291
An error log entry.
Definition: Recast.h:31
Definition: RecastAlloc.h:105
int height
The height of the heightfield. (Along the z-axis in cell units.)
Definition: Recast.h:334
static bool contains(const unsigned char *a, const unsigned char an, const unsigned char v)
Definition: RecastLayers.cpp:55
static const int RC_MAX_LAYERS
Definition: RecastLayers.cpp:30
The time to build heightfield layers. (See: rcBuildHeightfieldLayers)
Definition: Recast.h:89
float bmin[3]
The minimum bounds in world space. [(x, y, z)].
Definition: Recast.h:329
int maxx
The maximum x-bounds of usable data.
Definition: Recast.h:336
unsigned char layers[RC_MAX_LAYERS]
Definition: RecastLayers.cpp:35
void * rcAlloc(int size, rcAllocHint hint)
Definition: RecastAlloc.cpp:44
int rcGetDirOffsetX(int dir)
Definition: Recast.h:1038
int minx
The minimum x-bounds of usable data.
Definition: Recast.h:335
unsigned char nlayers
Definition: RecastLayers.cpp:39
unsigned char * areas
Array containing area id data. [Size: spanCount].
Definition: Recast.h:322
float ch
The height of each cell. (The minimum increment along the y-axis.)
Definition: Recast.h:332
G3D::int16 y
Definition: Vector2int16.h:38
float bmax[3]
The maximum bounds in world space. [(x, y, z)].
Definition: Recast.h:316
int width
The width of the heightfield. (Along the x-axis in cell units.)
Definition: Recast.h:307
void rcVcopy(float *dest, const float *v)
Definition: Recast.h:677
void startTimer(const rcTimerLabel label)
Definition: Recast.h:131
int spanCount
The number of spans in the heightfield.
Definition: Recast.h:309
unsigned char * cons
Packed neighbor connection information. [Size: Same as heights].
Definition: Recast.h:343
int maxy
The maximum y-bounds of usable data. (Along the z-axis.)
Definition: Recast.h:338
Memory will persist after a function call.
Definition: RecastAlloc.h:26
float cs
The size of each cell. (On the xz-plane.)
Definition: Recast.h:317
float ch
The height of each cell. (The minimum increment along the y-axis.)
Definition: Recast.h:318
static const unsigned char RC_NULL_AREA
Definition: Recast.h:538
int nlayers
The number of layers in the set.
Definition: Recast.h:352
Memory used temporarily within a function.
Definition: RecastAlloc.h:27
T rcMax(T a, T b)
Definition: Recast.h:572
void log(const rcLogCategory category, const char *format,...)
Definition: Recast.cpp:55
unsigned char layerId
Definition: RecastLayers.cpp:38
unsigned short ymax
Definition: RecastLayers.cpp:37
G3D::int16 x
Definition: Vector2int16.h:37
int width
The width of the heightfield. (Along the x-axis in cell units.)
Definition: Recast.h:333
void stopTimer(const rcTimerLabel label)
Definition: Recast.h:135
unsigned char nneis
Definition: RecastLayers.cpp:40
float bmax[3]
The maximum bounds in world space. [(x, y, z)].
Definition: Recast.h:330
unsigned char base
Definition: RecastLayers.cpp:41
int hmin
The minimum height bounds of usable data. (Along the y-axis.)
Definition: Recast.h:339
float cs
The size of each cell. (On the xz-plane.)
Definition: Recast.h:331
Definition: Recast.h:327
float bmin[3]
The minimum bounds in world space. [(x, y, z)].
Definition: Recast.h:315
bool overlapRange(const unsigned short amin, const unsigned short amax, const unsigned short bmin, const unsigned short bmax)
Definition: RecastLayers.cpp:64
int miny
The minimum y-bounds of usable data. (Along the z-axis.)
Definition: Recast.h:337

+ Here is the call graph for this function:

bool rcBuildLayerRegions ( rcContext ctx,
rcCompactHeightfield chf,
const int  borderSize,
const int  minRegionArea 
)

Builds region data for the heightfield by partitioning the heightfield in non-overlapping layers.

Parameters
[in,out]ctxThe build context to use during the operation.
[in,out]chfA populated compact heightfield.
[in]borderSizeThe size of the non-navigable border around the heightfield. [Limit: >=0] [Units: vx]
[in]minRegionAreaThe minimum number of cells allowed to form isolated island areas. [Limit: >=0] [Units: vx].
Returns
True if the operation completed successfully.
1672 {
1673  rcAssert(ctx);
1674 
1676 
1677  const int w = chf.width;
1678  const int h = chf.height;
1679  unsigned short id = 1;
1680 
1681  rcScopedDelete<unsigned short> srcReg = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP);
1682  if (!srcReg)
1683  {
1684  ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'src' (%d).", chf.spanCount);
1685  return false;
1686  }
1687  memset(srcReg,0,sizeof(unsigned short)*chf.spanCount);
1688 
1689  const int nsweeps = rcMax(chf.width,chf.height);
1691  if (!sweeps)
1692  {
1693  ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'sweeps' (%d).", nsweeps);
1694  return false;
1695  }
1696 
1697 
1698  // Mark border regions.
1699  if (borderSize > 0)
1700  {
1701  // Make sure border will not overflow.
1702  const int bw = rcMin(w, borderSize);
1703  const int bh = rcMin(h, borderSize);
1704  // Paint regions
1705  paintRectRegion(0, bw, 0, h, id|RC_BORDER_REG, chf, srcReg); id++;
1706  paintRectRegion(w-bw, w, 0, h, id|RC_BORDER_REG, chf, srcReg); id++;
1707  paintRectRegion(0, w, 0, bh, id|RC_BORDER_REG, chf, srcReg); id++;
1708  paintRectRegion(0, w, h-bh, h, id|RC_BORDER_REG, chf, srcReg); id++;
1709 
1710  chf.borderSize = borderSize;
1711  }
1712 
1713  rcIntArray prev(256);
1714 
1715  // Sweep one line at a time.
1716  for (int y = borderSize; y < h-borderSize; ++y)
1717  {
1718  // Collect spans from this row.
1719  prev.resize(id+1);
1720  memset(&prev[0],0,sizeof(int)*id);
1721  unsigned short rid = 1;
1722 
1723  for (int x = borderSize; x < w-borderSize; ++x)
1724  {
1725  const rcCompactCell& c = chf.cells[x+y*w];
1726 
1727  for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
1728  {
1729  const rcCompactSpan& s = chf.spans[i];
1730  if (chf.areas[i] == RC_NULL_AREA) continue;
1731 
1732  // -x
1733  unsigned short previd = 0;
1734  if (rcGetCon(s, 0) != RC_NOT_CONNECTED)
1735  {
1736  const int ax = x + rcGetDirOffsetX(0);
1737  const int ay = y + rcGetDirOffsetY(0);
1738  const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 0);
1739  if ((srcReg[ai] & RC_BORDER_REG) == 0 && chf.areas[i] == chf.areas[ai])
1740  previd = srcReg[ai];
1741  }
1742 
1743  if (!previd)
1744  {
1745  previd = rid++;
1746  sweeps[previd].rid = previd;
1747  sweeps[previd].ns = 0;
1748  sweeps[previd].nei = 0;
1749  }
1750 
1751  // -y
1752  if (rcGetCon(s,3) != RC_NOT_CONNECTED)
1753  {
1754  const int ax = x + rcGetDirOffsetX(3);
1755  const int ay = y + rcGetDirOffsetY(3);
1756  const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 3);
1757  if (srcReg[ai] && (srcReg[ai] & RC_BORDER_REG) == 0 && chf.areas[i] == chf.areas[ai])
1758  {
1759  unsigned short nr = srcReg[ai];
1760  if (!sweeps[previd].nei || sweeps[previd].nei == nr)
1761  {
1762  sweeps[previd].nei = nr;
1763  sweeps[previd].ns++;
1764  prev[nr]++;
1765  }
1766  else
1767  {
1768  sweeps[previd].nei = RC_NULL_NEI;
1769  }
1770  }
1771  }
1772 
1773  srcReg[i] = previd;
1774  }
1775  }
1776 
1777  // Create unique ID.
1778  for (int i = 1; i < rid; ++i)
1779  {
1780  if (sweeps[i].nei != RC_NULL_NEI && sweeps[i].nei != 0 &&
1781  prev[sweeps[i].nei] == (int)sweeps[i].ns)
1782  {
1783  sweeps[i].id = sweeps[i].nei;
1784  }
1785  else
1786  {
1787  sweeps[i].id = id++;
1788  }
1789  }
1790 
1791  // Remap IDs
1792  for (int x = borderSize; x < w-borderSize; ++x)
1793  {
1794  const rcCompactCell& c = chf.cells[x+y*w];
1795 
1796  for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
1797  {
1798  if (srcReg[i] > 0 && srcReg[i] < rid)
1799  srcReg[i] = sweeps[srcReg[i]].id;
1800  }
1801  }
1802  }
1803 
1804 
1806 
1807  // Merge monotone regions to layers and remove small regions.
1808  rcIntArray overlaps;
1809  chf.maxRegions = id;
1810  if (!mergeAndFilterLayerRegions(ctx, minRegionArea, chf.maxRegions, chf, srcReg, overlaps))
1811  return false;
1812 
1814 
1815 
1816  // Store the result out.
1817  for (int i = 0; i < chf.spanCount; ++i)
1818  chf.spans[i].reg = srcReg[i];
1819 
1821 
1822  return true;
1823 }
int height
The height of the heightfield. (Along the z-axis in cell units.)
Definition: Recast.h:308
#define rcAssert
Definition: RecastAssert.h:30
int borderSize
The AABB border size used during the build of the field. (See: rcConfig::borderSize) ...
Definition: Recast.h:312
unsigned short maxRegions
The maximum region id of any span within the field.
Definition: Recast.h:314
Represents a span of unobstructed space within a compact heightfield.
Definition: Recast.h:295
static const unsigned short RC_NULL_NEI
Definition: RecastRegion.cpp:1328
static const int RC_NOT_CONNECTED
Definition: Recast.h:547
unsigned short reg
The id of the region the span belongs to. (Or zero if not in a region.)
Definition: Recast.h:298
rcCompactCell * cells
Array of cells. [Size: width*height].
Definition: Recast.h:319
int rcGetDirOffsetY(int dir)
Definition: Recast.h:1048
rcCompactSpan * spans
Array of spans. [Size: spanCount].
Definition: Recast.h:320
T rcMin(T a, T b)
Definition: Recast.h:566
int rcGetCon(const rcCompactSpan &s, int dir)
Definition: Recast.h:1028
unsigned int index
Index to the first span in the column.
Definition: Recast.h:290
Provides information on the content of a cell column in a compact heightfield.
Definition: Recast.h:288
unsigned int count
Number of spans in the column.
Definition: Recast.h:291
An error log entry.
Definition: Recast.h:31
Definition: RecastAlloc.h:105
static bool mergeAndFilterLayerRegions(rcContext *ctx, int minRegionArea, unsigned short &maxRegionId, rcCompactHeightfield &chf, unsigned short *srcReg, rcIntArray &)
Definition: RecastRegion.cpp:1041
void * rcAlloc(int size, rcAllocHint hint)
Definition: RecastAlloc.cpp:44
int rcGetDirOffsetX(int dir)
Definition: Recast.h:1038
unsigned char * areas
Array containing area id data. [Size: spanCount].
Definition: Recast.h:322
Definition: RecastRegion.cpp:1330
G3D::int16 y
Definition: Vector2int16.h:38
int width
The width of the heightfield. (Along the x-axis in cell units.)
Definition: Recast.h:307
The total time to build the regions. (See: rcBuildRegions, rcBuildRegionsMonotone) ...
Definition: Recast.h:79
void startTimer(const rcTimerLabel label)
Definition: Recast.h:131
int spanCount
The number of spans in the heightfield.
Definition: Recast.h:309
static void paintRectRegion(int minx, int maxx, int miny, int maxy, unsigned short regId, rcCompactHeightfield &chf, unsigned short *srcReg)
Definition: RecastRegion.cpp:1309
int prev(int i, int n)
Definition: RecastContour.cpp:468
static const unsigned char RC_NULL_AREA
Definition: Recast.h:538
Memory used temporarily within a function.
Definition: RecastAlloc.h:27
T rcMax(T a, T b)
Definition: Recast.h:572
void log(const rcLogCategory category, const char *format,...)
Definition: Recast.cpp:55
G3D::int16 x
Definition: Vector2int16.h:37
void stopTimer(const rcTimerLabel label)
Definition: Recast.h:135
static const unsigned short RC_BORDER_REG
Definition: Recast.h:498
A simple dynamic array of integers.
Definition: RecastAlloc.h:61
The time to filter out small regions. (See: rcBuildRegions, rcBuildRegionsMonotone) ...
Definition: Recast.h:87

+ Here is the call graph for this function:

bool rcBuildPolyMesh ( rcContext ctx,
rcContourSet cset,
const int  nvp,
rcPolyMesh mesh 
)

Builds a polygon mesh from the provided contours.

Parameters
[in,out]ctxThe build context to use during the operation.
[in]csetA fully built contour set.
[in]nvpThe maximum number of vertices allowed for polygons generated during the contour to polygon conversion process. [Limit: >= 3]
[out]meshThe resulting polygon mesh. (Must be re-allocated.)
Returns
True if the operation completed successfully.
Note
If the mesh data is to be used to construct a Detour navigation mesh, then the upper limit must be retricted to <= DT_VERTS_PER_POLYGON.
See also
rcAllocPolyMesh, rcContourSet, rcPolyMesh, rcConfig
983 {
984  rcAssert(ctx);
985 
987 
988  rcVcopy(mesh.bmin, cset.bmin);
989  rcVcopy(mesh.bmax, cset.bmax);
990  mesh.cs = cset.cs;
991  mesh.ch = cset.ch;
992  mesh.borderSize = cset.borderSize;
993 
994  int maxVertices = 0;
995  int maxTris = 0;
996  int maxVertsPerCont = 0;
997  for (int i = 0; i < cset.nconts; ++i)
998  {
999  // Skip null contours.
1000  if (cset.conts[i].nverts < 3) continue;
1001  maxVertices += cset.conts[i].nverts;
1002  maxTris += cset.conts[i].nverts - 2;
1003  maxVertsPerCont = rcMax(maxVertsPerCont, cset.conts[i].nverts);
1004  }
1005 
1006  if (maxVertices >= 0xfffe)
1007  {
1008  ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Too many vertices %d.", maxVertices);
1009  return false;
1010  }
1011 
1012  rcScopedDelete<unsigned char> vflags = (unsigned char*)rcAlloc(sizeof(unsigned char)*maxVertices, RC_ALLOC_TEMP);
1013  if (!vflags)
1014  {
1015  ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'vflags' (%d).", maxVertices);
1016  return false;
1017  }
1018  memset(vflags, 0, maxVertices);
1019 
1020  mesh.verts = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxVertices*3, RC_ALLOC_PERM);
1021  if (!mesh.verts)
1022  {
1023  ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.verts' (%d).", maxVertices);
1024  return false;
1025  }
1026  mesh.polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxTris*nvp*2, RC_ALLOC_PERM);
1027  if (!mesh.polys)
1028  {
1029  ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.polys' (%d).", maxTris*nvp*2);
1030  return false;
1031  }
1032  mesh.regs = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxTris, RC_ALLOC_PERM);
1033  if (!mesh.regs)
1034  {
1035  ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.regs' (%d).", maxTris);
1036  return false;
1037  }
1038  mesh.areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*maxTris, RC_ALLOC_PERM);
1039  if (!mesh.areas)
1040  {
1041  ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.areas' (%d).", maxTris);
1042  return false;
1043  }
1044 
1045  mesh.nverts = 0;
1046  mesh.npolys = 0;
1047  mesh.nvp = nvp;
1048  mesh.maxpolys = maxTris;
1049 
1050  memset(mesh.verts, 0, sizeof(unsigned short)*maxVertices*3);
1051  memset(mesh.polys, 0xff, sizeof(unsigned short)*maxTris*nvp*2);
1052  memset(mesh.regs, 0, sizeof(unsigned short)*maxTris);
1053  memset(mesh.areas, 0, sizeof(unsigned char)*maxTris);
1054 
1055  rcScopedDelete<int> nextVert = (int*)rcAlloc(sizeof(int)*maxVertices, RC_ALLOC_TEMP);
1056  if (!nextVert)
1057  {
1058  ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'nextVert' (%d).", maxVertices);
1059  return false;
1060  }
1061  memset(nextVert, 0, sizeof(int)*maxVertices);
1062 
1063  rcScopedDelete<int> firstVert = (int*)rcAlloc(sizeof(int)*VERTEX_BUCKET_COUNT, RC_ALLOC_TEMP);
1064  if (!firstVert)
1065  {
1066  ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'firstVert' (%d).", VERTEX_BUCKET_COUNT);
1067  return false;
1068  }
1069  for (int i = 0; i < VERTEX_BUCKET_COUNT; ++i)
1070  firstVert[i] = -1;
1071 
1072  rcScopedDelete<int> indices = (int*)rcAlloc(sizeof(int)*maxVertsPerCont, RC_ALLOC_TEMP);
1073  if (!indices)
1074  {
1075  ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'indices' (%d).", maxVertsPerCont);
1076  return false;
1077  }
1078  rcScopedDelete<int> tris = (int*)rcAlloc(sizeof(int)*maxVertsPerCont*3, RC_ALLOC_TEMP);
1079  if (!tris)
1080  {
1081  ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'tris' (%d).", maxVertsPerCont*3);
1082  return false;
1083  }
1084  rcScopedDelete<unsigned short> polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*(maxVertsPerCont+1)*nvp, RC_ALLOC_TEMP);
1085  if (!polys)
1086  {
1087  ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'polys' (%d).", maxVertsPerCont*nvp);
1088  return false;
1089  }
1090  unsigned short* tmpPoly = &polys[maxVertsPerCont*nvp];
1091 
1092  for (int i = 0; i < cset.nconts; ++i)
1093  {
1094  rcContour& cont = cset.conts[i];
1095 
1096  // Skip null contours.
1097  if (cont.nverts < 3)
1098  continue;
1099 
1100  // Triangulate contour
1101  for (int j = 0; j < cont.nverts; ++j)
1102  indices[j] = j;
1103 
1104  int ntris = triangulate(cont.nverts, cont.verts, &indices[0], &tris[0]);
1105  if (ntris <= 0)
1106  {
1107  // Bad triangulation, should not happen.
1108 /* printf("\tconst float bmin[3] = {%ff,%ff,%ff};\n", cset.bmin[0], cset.bmin[1], cset.bmin[2]);
1109  printf("\tconst float cs = %ff;\n", cset.cs);
1110  printf("\tconst float ch = %ff;\n", cset.ch);
1111  printf("\tconst int verts[] = {\n");
1112  for (int k = 0; k < cont.nverts; ++k)
1113  {
1114  const int* v = &cont.verts[k*4];
1115  printf("\t\t%d,%d,%d,%d,\n", v[0], v[1], v[2], v[3]);
1116  }
1117  printf("\t};\n\tconst int nverts = sizeof(verts)/(sizeof(int)*4);\n");*/
1118  ctx->log(RC_LOG_WARNING, "rcBuildPolyMesh: Bad triangulation Contour %d.", i);
1119  ntris = -ntris;
1120  }
1121 
1122  // Add and merge vertices.
1123  for (int j = 0; j < cont.nverts; ++j)
1124  {
1125  const int* v = &cont.verts[j*4];
1126  indices[j] = addVertex((unsigned short)v[0], (unsigned short)v[1], (unsigned short)v[2],
1127  mesh.verts, firstVert, nextVert, mesh.nverts);
1128  if (v[3] & RC_BORDER_VERTEX)
1129  {
1130  // This vertex should be removed.
1131  vflags[indices[j]] = 1;
1132  }
1133  }
1134 
1135  // Build initial polygons.
1136  int npolys = 0;
1137  memset(polys, 0xff, maxVertsPerCont*nvp*sizeof(unsigned short));
1138  for (int j = 0; j < ntris; ++j)
1139  {
1140  int* t = &tris[j*3];
1141  if (t[0] != t[1] && t[0] != t[2] && t[1] != t[2])
1142  {
1143  polys[npolys*nvp+0] = (unsigned short)indices[t[0]];
1144  polys[npolys*nvp+1] = (unsigned short)indices[t[1]];
1145  polys[npolys*nvp+2] = (unsigned short)indices[t[2]];
1146  npolys++;
1147  }
1148  }
1149  if (!npolys)
1150  continue;
1151 
1152  // Merge polygons.
1153  if (nvp > 3)
1154  {
1155  for(;;)
1156  {
1157  // Find best polygons to merge.
1158  int bestMergeVal = 0;
1159  int bestPa = 0, bestPb = 0, bestEa = 0, bestEb = 0;
1160 
1161  for (int j = 0; j < npolys-1; ++j)
1162  {
1163  unsigned short* pj = &polys[j*nvp];
1164  for (int k = j+1; k < npolys; ++k)
1165  {
1166  unsigned short* pk = &polys[k*nvp];
1167  int ea, eb;
1168  int v = getPolyMergeValue(pj, pk, mesh.verts, ea, eb, nvp);
1169  if (v > bestMergeVal)
1170  {
1171  bestMergeVal = v;
1172  bestPa = j;
1173  bestPb = k;
1174  bestEa = ea;
1175  bestEb = eb;
1176  }
1177  }
1178  }
1179 
1180  if (bestMergeVal > 0)
1181  {
1182  // Found best, merge.
1183  unsigned short* pa = &polys[bestPa*nvp];
1184  unsigned short* pb = &polys[bestPb*nvp];
1185  mergePolys(pa, pb, bestEa, bestEb, tmpPoly, nvp);
1186  unsigned short* lastPoly = &polys[(npolys-1)*nvp];
1187  if (pb != lastPoly)
1188  memcpy(pb, lastPoly, sizeof(unsigned short)*nvp);
1189  npolys--;
1190  }
1191  else
1192  {
1193  // Could not merge any polygons, stop.
1194  break;
1195  }
1196  }
1197  }
1198 
1199  // Store polygons.
1200  for (int j = 0; j < npolys; ++j)
1201  {
1202  unsigned short* p = &mesh.polys[mesh.npolys*nvp*2];
1203  unsigned short* q = &polys[j*nvp];
1204  for (int k = 0; k < nvp; ++k)
1205  p[k] = q[k];
1206  mesh.regs[mesh.npolys] = cont.reg;
1207  mesh.areas[mesh.npolys] = cont.area;
1208  mesh.npolys++;
1209  if (mesh.npolys > maxTris)
1210  {
1211  ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Too many polygons %d (max:%d).", mesh.npolys, maxTris);
1212  return false;
1213  }
1214  }
1215  }
1216 
1217 
1218  // Remove edge vertices.
1219  for (int i = 0; i < mesh.nverts; ++i)
1220  {
1221  if (vflags[i])
1222  {
1223  if (!canRemoveVertex(ctx, mesh, (unsigned short)i))
1224  continue;
1225  if (!removeVertex(ctx, mesh, (unsigned short)i, maxTris))
1226  {
1227  // Failed to remove vertex
1228  ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Failed to remove edge vertex %d.", i);
1229  return false;
1230  }
1231  // Remove vertex
1232  // Note: mesh.nverts is already decremented inside removeVertex()!
1233  // Fixup vertex flags
1234  for (int j = i; j < mesh.nverts; ++j)
1235  vflags[j] = vflags[j+1];
1236  --i;
1237  }
1238  }
1239 
1240  // Calculate adjacency.
1241  if (!buildMeshAdjacency(mesh.polys, mesh.npolys, mesh.nverts, nvp))
1242  {
1243  ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Adjacency failed.");
1244  return false;
1245  }
1246 
1247  // Find portal edges
1248  if (mesh.borderSize > 0)
1249  {
1250  const int w = cset.width;
1251  const int h = cset.height;
1252  for (int i = 0; i < mesh.npolys; ++i)
1253  {
1254  unsigned short* p = &mesh.polys[i*2*nvp];
1255  for (int j = 0; j < nvp; ++j)
1256  {
1257  if (p[j] == RC_MESH_NULL_IDX) break;
1258  // Skip connected edges.
1259  if (p[nvp+j] != RC_MESH_NULL_IDX)
1260  continue;
1261  int nj = j+1;
1262  if (nj >= nvp || p[nj] == RC_MESH_NULL_IDX) nj = 0;
1263  const unsigned short* va = &mesh.verts[p[j]*3];
1264  const unsigned short* vb = &mesh.verts[p[nj]*3];
1265 
1266  if ((int)va[0] == 0 && (int)vb[0] == 0)
1267  p[nvp+j] = 0x8000 | 0;
1268  else if ((int)va[2] == h && (int)vb[2] == h)
1269  p[nvp+j] = 0x8000 | 1;
1270  else if ((int)va[0] == w && (int)vb[0] == w)
1271  p[nvp+j] = 0x8000 | 2;
1272  else if ((int)va[2] == 0 && (int)vb[2] == 0)
1273  p[nvp+j] = 0x8000 | 3;
1274  }
1275  }
1276  }
1277 
1278  // Just allocate the mesh flags array. The user is resposible to fill it.
1279  mesh.flags = (unsigned short*)rcAlloc(sizeof(unsigned short)*mesh.npolys, RC_ALLOC_PERM);
1280  if (!mesh.flags)
1281  {
1282  ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.flags' (%d).", mesh.npolys);
1283  return false;
1284  }
1285  memset(mesh.flags, 0, sizeof(unsigned short) * mesh.npolys);
1286 
1287  if (mesh.nverts > 0xffff)
1288  {
1289  ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: The resulting mesh has too many vertices %d (max %d). Data can be corrupted.", mesh.nverts, 0xffff);
1290  }
1291  if (mesh.npolys > 0xffff)
1292  {
1293  ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: The resulting mesh has too many polygons %d (max %d). Data can be corrupted.", mesh.npolys, 0xffff);
1294  }
1295 
1297 
1298  return true;
1299 }
unsigned char * areas
The area id assigned to each polygon. [Length: maxpolys].
Definition: Recast.h:389
float bmin[3]
The minimum bounds in world space. [(x, y, z)].
Definition: Recast.h:372
#define rcAssert
Definition: RecastAssert.h:30
int nverts
The number of vertices.
Definition: Recast.h:390
static void mergePolys(unsigned short *pa, unsigned short *pb, int ea, int eb, unsigned short *tmp, const int nvp)
Definition: RecastMesh.cpp:531
int nverts
The number of vertices in the simplified contour.
Definition: Recast.h:359
unsigned short * verts
The mesh vertices. [Form: (x, y, z) * nverts].
Definition: Recast.h:385
float ch
The height of each cell. (The minimum increment along the y-axis.)
Definition: Recast.h:397
float bmax[3]
The maximum bounds in world space. [(x, y, z)].
Definition: Recast.h:395
rcContour * conts
An array of the contours in the set. [Size: nconts].
Definition: Recast.h:370
Definition: BnetFileGenerator.h:49
float cs
The size of each cell. (On the xz-plane.)
Definition: Recast.h:396
int height
The height of the set. (Along the z-axis in cell units.)
Definition: Recast.h:377
static bool canRemoveVertex(rcContext *ctx, rcPolyMesh &mesh, const unsigned short rem)
Definition: RecastMesh.cpp:564
int nconts
The number of contours in the set.
Definition: Recast.h:371
int * verts
Simplified contour vertex and connection data. [Size: 4 * nverts].
Definition: Recast.h:358
static unsigned short addVertex(unsigned short x, unsigned short y, unsigned short z, unsigned short *verts, int *firstVert, int *nextVert, int &nv)
Definition: RecastMesh.cpp:137
Represents a simple, non-overlapping contour in field space.
Definition: Recast.h:356
An error log entry.
Definition: Recast.h:31
Definition: RecastAlloc.h:105
static int triangulate(int n, const int *verts, int *indices, int *tris)
Definition: RecastMesh.cpp:339
unsigned char area
The area id of the contour.
Definition: Recast.h:363
void * rcAlloc(int size, rcAllocHint hint)
Definition: RecastAlloc.cpp:44
static bool removeVertex(rcContext *ctx, rcPolyMesh &mesh, const unsigned short rem, const int maxTris)
Definition: RecastMesh.cpp:666
static const unsigned short RC_MESH_NULL_IDX
Definition: Recast.h:533
static const int RC_BORDER_VERTEX
Definition: Recast.h:507
float bmax[3]
The maximum bounds in world space. [(x, y, z)].
Definition: Recast.h:373
unsigned short reg
The region id of the contour.
Definition: Recast.h:362
static int getPolyMergeValue(unsigned short *pa, unsigned short *pb, const unsigned short *verts, int &ea, int &eb, const int nvp)
Definition: RecastMesh.cpp:467
void rcVcopy(float *dest, const float *v)
Definition: Recast.h:677
float cs
The size of each cell. (On the xz-plane.)
Definition: Recast.h:374
void startTimer(const rcTimerLabel label)
Definition: Recast.h:131
static bool buildMeshAdjacency(unsigned short *polys, const int npolys, const int nverts, const int vertsPerPoly)
Definition: RecastMesh.cpp:34
Memory will persist after a function call.
Definition: RecastAlloc.h:26
unsigned short * flags
The user defined flags for each polygon. [Length: maxpolys].
Definition: Recast.h:388
int width
The width of the set. (Along the x-axis in cell units.)
Definition: Recast.h:376
The time to build the polygon mesh. (See: rcBuildPolyMesh)
Definition: Recast.h:61
int borderSize
The AABB border size used to generate the source data from which the mesh was derived.
Definition: Recast.h:398
Memory used temporarily within a function.
Definition: RecastAlloc.h:27
T rcMax(T a, T b)
Definition: Recast.h:572
void log(const rcLogCategory category, const char *format,...)
Definition: Recast.cpp:55
static const int VERTEX_BUCKET_COUNT
Definition: RecastMesh.cpp:126
int borderSize
The AABB border size used to generate the source data from which the contours were derived...
Definition: Recast.h:378
float ch
The height of each cell. (The minimum increment along the y-axis.)
Definition: Recast.h:375
int npolys
The number of polygons.
Definition: Recast.h:391
void stopTimer(const rcTimerLabel label)
Definition: Recast.h:135
int maxpolys
The number of allocated polygons.
Definition: Recast.h:392
unsigned short * regs
The region id assigned to each polygon. [Length: maxpolys].
Definition: Recast.h:387
A warning log entry.
Definition: Recast.h:30
float bmin[3]
The minimum bounds in world space. [(x, y, z)].
Definition: Recast.h:394
int nvp
The maximum number of vertices per polygon.
Definition: Recast.h:393
unsigned short * polys
Polygon and neighbor data. [Length: maxpolys * 2 * nvp].
Definition: Recast.h:386

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

bool rcBuildPolyMeshDetail ( rcContext ctx,
const rcPolyMesh mesh,
const rcCompactHeightfield chf,
const float  sampleDist,
const float  sampleMaxError,
rcPolyMeshDetail dmesh 
)

Builds a detail mesh from the provided polygon mesh.

Parameters
[in,out]ctxThe build context to use during the operation.
[in]meshA fully built polygon mesh.
[in]chfThe compact heightfield used to build the polygon mesh.
[in]sampleDistSets the distance to use when samping the heightfield. [Limit: >=0] [Units: wu]
[in]sampleMaxErrorThe maximum distance the detail mesh surface should deviate from heightfield data. [Limit: >=0] [Units: wu]
[out]dmeshThe resulting detail mesh. (Must be pre-allocated.)
Returns
True if the operation completed successfully.

See the rcConfig documentation for more information on the configuration parameters.

See also
rcAllocPolyMeshDetail, rcPolyMesh, rcCompactHeightfield, rcPolyMeshDetail, rcConfig
1120 {
1121  rcAssert(ctx);
1122 
1124 
1125  if (mesh.nverts == 0 || mesh.npolys == 0)
1126  return true;
1127 
1128  const int nvp = mesh.nvp;
1129  const float cs = mesh.cs;
1130  const float ch = mesh.ch;
1131  const float* orig = mesh.bmin;
1132  const int borderSize = mesh.borderSize;
1133 
1134  rcIntArray edges(64);
1135  rcIntArray tris(512);
1136  rcIntArray stack(512);
1137  rcIntArray samples(512);
1138  float verts[256*3];
1139  rcHeightPatch hp;
1140  int nPolyVerts = 0;
1141  int maxhw = 0, maxhh = 0;
1142 
1143  rcScopedDelete<int> bounds = (int*)rcAlloc(sizeof(int)*mesh.npolys*4, RC_ALLOC_TEMP);
1144  if (!bounds)
1145  {
1146  ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'bounds' (%d).", mesh.npolys*4);
1147  return false;
1148  }
1149  rcScopedDelete<float> poly = (float*)rcAlloc(sizeof(float)*nvp*3, RC_ALLOC_TEMP);
1150  if (!poly)
1151  {
1152  ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'poly' (%d).", nvp*3);
1153  return false;
1154  }
1155 
1156  // Find max size for a polygon area.
1157  for (int i = 0; i < mesh.npolys; ++i)
1158  {
1159  const unsigned short* p = &mesh.polys[i*nvp*2];
1160  int& xmin = bounds[i*4+0];
1161  int& xmax = bounds[i*4+1];
1162  int& ymin = bounds[i*4+2];
1163  int& ymax = bounds[i*4+3];
1164  xmin = chf.width;
1165  xmax = 0;
1166  ymin = chf.height;
1167  ymax = 0;
1168  for (int j = 0; j < nvp; ++j)
1169  {
1170  if(p[j] == RC_MESH_NULL_IDX) break;
1171  const unsigned short* v = &mesh.verts[p[j]*3];
1172  xmin = rcMin(xmin, (int)v[0]);
1173  xmax = rcMax(xmax, (int)v[0]);
1174  ymin = rcMin(ymin, (int)v[2]);
1175  ymax = rcMax(ymax, (int)v[2]);
1176  nPolyVerts++;
1177  }
1178  xmin = rcMax(0,xmin-1);
1179  xmax = rcMin(chf.width,xmax+1);
1180  ymin = rcMax(0,ymin-1);
1181  ymax = rcMin(chf.height,ymax+1);
1182  if (xmin >= xmax || ymin >= ymax) continue;
1183  maxhw = rcMax(maxhw, xmax-xmin);
1184  maxhh = rcMax(maxhh, ymax-ymin);
1185  }
1186 
1187  hp.data = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxhw*maxhh, RC_ALLOC_TEMP);
1188  if (!hp.data)
1189  {
1190  ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'hp.data' (%d).", maxhw*maxhh);
1191  return false;
1192  }
1193 
1194  dmesh.nmeshes = mesh.npolys;
1195  dmesh.nverts = 0;
1196  dmesh.ntris = 0;
1197  dmesh.meshes = (unsigned int*)rcAlloc(sizeof(unsigned int)*dmesh.nmeshes*4, RC_ALLOC_PERM);
1198  if (!dmesh.meshes)
1199  {
1200  ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.meshes' (%d).", dmesh.nmeshes*4);
1201  return false;
1202  }
1203 
1204  int vcap = nPolyVerts+nPolyVerts/2;
1205  int tcap = vcap*2;
1206 
1207  dmesh.nverts = 0;
1208  dmesh.verts = (float*)rcAlloc(sizeof(float)*vcap*3, RC_ALLOC_PERM);
1209  if (!dmesh.verts)
1210  {
1211  ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.verts' (%d).", vcap*3);
1212  return false;
1213  }
1214  dmesh.ntris = 0;
1215  dmesh.tris = (unsigned char*)rcAlloc(sizeof(unsigned char)*tcap*4, RC_ALLOC_PERM);
1216  if (!dmesh.tris)
1217  {
1218  ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.tris' (%d).", tcap*4);
1219  return false;
1220  }
1221 
1222  for (int i = 0; i < mesh.npolys; ++i)
1223  {
1224  const unsigned short* p = &mesh.polys[i*nvp*2];
1225 
1226  // Store polygon vertices for processing.
1227  int npoly = 0;
1228  for (int j = 0; j < nvp; ++j)
1229  {
1230  if(p[j] == RC_MESH_NULL_IDX) break;
1231  const unsigned short* v = &mesh.verts[p[j]*3];
1232  poly[j*3+0] = v[0]*cs;
1233  poly[j*3+1] = v[1]*ch;
1234  poly[j*3+2] = v[2]*cs;
1235  npoly++;
1236  }
1237 
1238  // Get the height data from the area of the polygon.
1239  hp.xmin = bounds[i*4+0];
1240  hp.ymin = bounds[i*4+2];
1241  hp.width = bounds[i*4+1]-bounds[i*4+0];
1242  hp.height = bounds[i*4+3]-bounds[i*4+2];
1243  getHeightData(chf, p, npoly, mesh.verts, borderSize, hp, stack, mesh.regs[i]);
1244 
1245  // Build detail mesh.
1246  int nverts = 0;
1247  if (!buildPolyDetail(ctx, poly, npoly,
1248  sampleDist, sampleMaxError,
1249  chf, hp, verts, nverts, tris,
1250  edges, samples))
1251  {
1252  return false;
1253  }
1254 
1255  // Move detail verts to world space.
1256  for (int j = 0; j < nverts; ++j)
1257  {
1258  verts[j*3+0] += orig[0];
1259  verts[j*3+1] += orig[1] + chf.ch; // Is this offset necessary?
1260  verts[j*3+2] += orig[2];
1261  }
1262  // Offset poly too, will be used to flag checking.
1263  for (int j = 0; j < npoly; ++j)
1264  {
1265  poly[j*3+0] += orig[0];
1266  poly[j*3+1] += orig[1];
1267  poly[j*3+2] += orig[2];
1268  }
1269 
1270  // Store detail submesh.
1271  const int ntris = tris.size()/4;
1272 
1273  dmesh.meshes[i*4+0] = (unsigned int)dmesh.nverts;
1274  dmesh.meshes[i*4+1] = (unsigned int)nverts;
1275  dmesh.meshes[i*4+2] = (unsigned int)dmesh.ntris;
1276  dmesh.meshes[i*4+3] = (unsigned int)ntris;
1277 
1278  // Store vertices, allocate more memory if necessary.
1279  if (dmesh.nverts+nverts > vcap)
1280  {
1281  while (dmesh.nverts+nverts > vcap)
1282  vcap += 256;
1283 
1284  float* newv = (float*)rcAlloc(sizeof(float)*vcap*3, RC_ALLOC_PERM);
1285  if (!newv)
1286  {
1287  ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'newv' (%d).", vcap*3);
1288  return false;
1289  }
1290  if (dmesh.nverts)
1291  memcpy(newv, dmesh.verts, sizeof(float)*3*dmesh.nverts);
1292  rcFree(dmesh.verts);
1293  dmesh.verts = newv;
1294  }
1295  for (int j = 0; j < nverts; ++j)
1296  {
1297  dmesh.verts[dmesh.nverts*3+0] = verts[j*3+0];
1298  dmesh.verts[dmesh.nverts*3+1] = verts[j*3+1];
1299  dmesh.verts[dmesh.nverts*3+2] = verts[j*3+2];
1300  dmesh.nverts++;
1301  }
1302 
1303  // Store triangles, allocate more memory if necessary.
1304  if (dmesh.ntris+ntris > tcap)
1305  {
1306  while (dmesh.ntris+ntris > tcap)
1307  tcap += 256;
1308  unsigned char* newt = (unsigned char*)rcAlloc(sizeof(unsigned char)*tcap*4, RC_ALLOC_PERM);
1309  if (!newt)
1310  {
1311  ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'newt' (%d).", tcap*4);
1312  return false;
1313  }
1314  if (dmesh.ntris)
1315  memcpy(newt, dmesh.tris, sizeof(unsigned char)*4*dmesh.ntris);
1316  rcFree(dmesh.tris);
1317  dmesh.tris = newt;
1318  }
1319  for (int j = 0; j < ntris; ++j)
1320  {
1321  const int* t = &tris[j*4];
1322  dmesh.tris[dmesh.ntris*4+0] = (unsigned char)t[0];
1323  dmesh.tris[dmesh.ntris*4+1] = (unsigned char)t[1];
1324  dmesh.tris[dmesh.ntris*4+2] = (unsigned char)t[2];
1325  dmesh.tris[dmesh.ntris*4+3] = getTriFlags(&verts[t[0]*3], &verts[t[1]*3], &verts[t[2]*3], poly, npoly);
1326  dmesh.ntris++;
1327  }
1328  }
1329 
1331 
1332  return true;
1333 }
int xmin
Definition: RecastMeshDetail.cpp:37
int height
The height of the heightfield. (Along the z-axis in cell units.)
Definition: Recast.h:308
#define rcAssert
Definition: RecastAssert.h:30
int nverts
The number of vertices.
Definition: Recast.h:390
int ntris
The number of triangles in tris.
Definition: Recast.h:411
unsigned short * verts
The mesh vertices. [Form: (x, y, z) * nverts].
Definition: Recast.h:385
float * verts
The mesh vertices. [Size: 3*nverts].
Definition: Recast.h:407
T rcMin(T a, T b)
Definition: Recast.h:566
float ch
The height of each cell. (The minimum increment along the y-axis.)
Definition: Recast.h:397
float cs
The size of each cell. (On the xz-plane.)
Definition: Recast.h:396
The time to build the polygon mesh detail. (See: rcBuildPolyMeshDetail)
Definition: Recast.h:91
int nmeshes
The number of sub-meshes defined by meshes.
Definition: Recast.h:409
An error log entry.
Definition: Recast.h:31
Definition: RecastAlloc.h:105
static bool buildPolyDetail(rcContext *ctx, const float *in, const int nin, const float sampleDist, const float sampleMaxError, const rcCompactHeightfield &chf, const rcHeightPatch &hp, float *verts, int &nverts, rcIntArray &tris, rcIntArray &edges, rcIntArray &samples)
Definition: RecastMeshDetail.cpp:591
static void getHeightData(const rcCompactHeightfield &chf, const unsigned short *poly, const int npoly, const unsigned short *verts, const int bs, rcHeightPatch &hp, rcIntArray &stack, int region)
Definition: RecastMeshDetail.cpp:976
void rcFree(void *ptr)
Definition: RecastAlloc.cpp:55
unsigned char * tris
The mesh triangles. [Size: 4*ntris].
Definition: Recast.h:408
void * rcAlloc(int size, rcAllocHint hint)
Definition: RecastAlloc.cpp:44
static const unsigned short RC_MESH_NULL_IDX
Definition: Recast.h:533
int height
Definition: RecastMeshDetail.cpp:37
int width
Definition: RecastMeshDetail.cpp:37
int width
The width of the heightfield. (Along the x-axis in cell units.)
Definition: Recast.h:307
static unsigned char getTriFlags(const float *va, const float *vb, const float *vc, const float *vpoly, const int npoly)
Definition: RecastMeshDetail.cpp:1102
void startTimer(const rcTimerLabel label)
Definition: Recast.h:131
Memory will persist after a function call.
Definition: RecastAlloc.h:26
unsigned short * data
Definition: RecastMeshDetail.cpp:36
int ymin
Definition: RecastMeshDetail.cpp:37
int borderSize
The AABB border size used to generate the source data from which the mesh was derived.
Definition: Recast.h:398
float ch
The height of each cell. (The minimum increment along the y-axis.)
Definition: Recast.h:318
Memory used temporarily within a function.
Definition: RecastAlloc.h:27
T rcMax(T a, T b)
Definition: Recast.h:572
void log(const rcLogCategory category, const char *format,...)
Definition: Recast.cpp:55
unsigned int * meshes
The sub-mesh data. [Size: 4*nmeshes].
Definition: Recast.h:406
int npolys
The number of polygons.
Definition: Recast.h:391
void stopTimer(const rcTimerLabel label)
Definition: Recast.h:135
unsigned short * regs
The region id assigned to each polygon. [Length: maxpolys].
Definition: Recast.h:387
int nverts
The number of vertices in verts.
Definition: Recast.h:410
float bmin[3]
The minimum bounds in world space. [(x, y, z)].
Definition: Recast.h:394
A simple dynamic array of integers.
Definition: RecastAlloc.h:61
int nvp
The maximum number of vertices per polygon.
Definition: Recast.h:393
unsigned short * polys
Polygon and neighbor data. [Length: maxpolys * 2 * nvp].
Definition: Recast.h:386
Definition: RecastMeshDetail.cpp:32

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

bool rcBuildRegions ( rcContext ctx,
rcCompactHeightfield chf,
const int  borderSize,
const int  minRegionArea,
const int  mergeRegionArea 
)

Builds region data for the heightfield using watershed partitioning.

Parameters
[in,out]ctxThe build context to use during the operation.
[in,out]chfA populated compact heightfield.
[in]borderSizeThe size of the non-navigable border around the heightfield. [Limit: >=0] [Units: vx]
[in]minRegionAreaThe minimum number of cells allowed to form isolated island areas. [Limit: >=0] [Units: vx].
[in]mergeRegionAreaAny regions with a span count smaller than this value will, if possible, be merged with larger regions. [Limit: >=0] [Units: vx]
Returns
True if the operation completed successfully.

Non-null regions will consist of connected, non-overlapping walkable spans that form a single contour. Contours will form simple polygons.

If multiple regions form an area that is smaller than minRegionArea, then all spans will be re-assigned to the zero (null) region.

Watershed partitioning can result in smaller than necessary regions, especially in diagonal corridors. mergeRegionArea helps reduce unecessarily small regions.

See the rcConfig documentation for more information on the configuration parameters.

The region data will be available via the rcCompactHeightfield::maxRegions and rcCompactSpan::reg fields.

Warning
The distance field must be created using rcBuildDistanceField before attempting to build regions.
See also
rcCompactHeightfield, rcCompactSpan, rcBuildDistanceField, rcBuildRegionsMonotone, rcConfig
1534 {
1535  rcAssert(ctx);
1536 
1538 
1539  const int w = chf.width;
1540  const int h = chf.height;
1541 
1542  rcScopedDelete<unsigned short> buf = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount*4, RC_ALLOC_TEMP);
1543  if (!buf)
1544  {
1545  ctx->log(RC_LOG_ERROR, "rcBuildRegions: Out of memory 'tmp' (%d).", chf.spanCount*4);
1546  return false;
1547  }
1548 
1550 
1551  const int LOG_NB_STACKS = 3;
1552  const int NB_STACKS = 1 << LOG_NB_STACKS;
1553  rcIntArray lvlStacks[NB_STACKS];
1554  for (int i=0; i<NB_STACKS; ++i)
1555  lvlStacks[i].resize(1024);
1556 
1557  rcIntArray stack(1024);
1558  rcIntArray visited(1024);
1559 
1560  unsigned short* srcReg = buf;
1561  unsigned short* srcDist = buf+chf.spanCount;
1562  unsigned short* dstReg = buf+chf.spanCount*2;
1563  unsigned short* dstDist = buf+chf.spanCount*3;
1564 
1565  memset(srcReg, 0, sizeof(unsigned short)*chf.spanCount);
1566  memset(srcDist, 0, sizeof(unsigned short)*chf.spanCount);
1567 
1568  unsigned short regionId = 1;
1569  unsigned short level = (chf.maxDistance+1) & ~1;
1570 
1571  // TODO: Figure better formula, expandIters defines how much the
1572  // watershed "overflows" and simplifies the regions. Tying it to
1573  // agent radius was usually good indication how greedy it could be.
1574 // const int expandIters = 4 + walkableRadius * 2;
1575  const int expandIters = 8;
1576 
1577  if (borderSize > 0)
1578  {
1579  // Make sure border will not overflow.
1580  const int bw = rcMin(w, borderSize);
1581  const int bh = rcMin(h, borderSize);
1582  // Paint regions
1583  paintRectRegion(0, bw, 0, h, regionId|RC_BORDER_REG, chf, srcReg); regionId++;
1584  paintRectRegion(w-bw, w, 0, h, regionId|RC_BORDER_REG, chf, srcReg); regionId++;
1585  paintRectRegion(0, w, 0, bh, regionId|RC_BORDER_REG, chf, srcReg); regionId++;
1586  paintRectRegion(0, w, h-bh, h, regionId|RC_BORDER_REG, chf, srcReg); regionId++;
1587 
1588  chf.borderSize = borderSize;
1589  }
1590 
1591  int sId = -1;
1592  while (level > 0)
1593  {
1594  level = level >= 2 ? level-2 : 0;
1595  sId = (sId+1) & (NB_STACKS-1);
1596 
1597 // ctx->startTimer(RC_TIMER_DIVIDE_TO_LEVELS);
1598 
1599  if (sId == 0)
1600  sortCellsByLevel(level, chf, srcReg, NB_STACKS, lvlStacks, 1);
1601  else
1602  appendStacks(lvlStacks[sId-1], lvlStacks[sId], srcReg); // copy left overs from last level
1603 
1604 // ctx->stopTimer(RC_TIMER_DIVIDE_TO_LEVELS);
1605 
1607 
1608  // Expand current regions until no empty connected cells found.
1609  if (expandRegions(expandIters, level, chf, srcReg, srcDist, dstReg, dstDist, lvlStacks[sId], false) != srcReg)
1610  {
1611  rcSwap(srcReg, dstReg);
1612  rcSwap(srcDist, dstDist);
1613  }
1614 
1616 
1618 
1619  // Mark new regions with IDs.
1620  for (int j=0; j<lvlStacks[sId].size(); j+=3)
1621  {
1622  int x = lvlStacks[sId][j];
1623  int y = lvlStacks[sId][j+1];
1624  int i = lvlStacks[sId][j+2];
1625  if (i >= 0 && srcReg[i] == 0)
1626  {
1627  if (floodRegion(x, y, i, level, regionId, chf, srcReg, srcDist, stack))
1628  regionId++;
1629  }
1630  }
1631 
1633  }
1634 
1635  // Expand current regions until no empty connected cells found.
1636  if (expandRegions(expandIters*8, 0, chf, srcReg, srcDist, dstReg, dstDist, stack, true) != srcReg)
1637  {
1638  rcSwap(srcReg, dstReg);
1639  rcSwap(srcDist, dstDist);
1640  }
1641 
1643 
1645 
1646  // Merge regions and filter out smalle regions.
1647  rcIntArray overlaps;
1648  chf.maxRegions = regionId;
1649  if (!mergeAndFilterRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg, overlaps))
1650  return false;
1651 
1652  // If overlapping regions were found during merging, split those regions.
1653  if (overlaps.size() > 0)
1654  {
1655  ctx->log(RC_LOG_ERROR, "rcBuildRegions: %d overlapping regions.", overlaps.size());
1656  }
1657 
1659 
1660  // Write the result out.
1661  for (int i = 0; i < chf.spanCount; ++i)
1662  chf.spans[i].reg = srcReg[i];
1663 
1665 
1666  return true;
1667 }
int height
The height of the heightfield. (Along the z-axis in cell units.)
Definition: Recast.h:308
#define rcAssert
Definition: RecastAssert.h:30
int borderSize
The AABB border size used during the build of the field. (See: rcConfig::borderSize) ...
Definition: Recast.h:312
unsigned short maxRegions
The maximum region id of any span within the field.
Definition: Recast.h:314
void rcSwap(T &a, T &b)
Definition: Recast.h:560
unsigned short reg
The id of the region the span belongs to. (Or zero if not in a region.)
Definition: Recast.h:298
static bool floodRegion(int x, int y, int i, unsigned short level, unsigned short r, rcCompactHeightfield &chf, unsigned short *srcReg, unsigned short *srcDist, rcIntArray &stack)
Definition: RecastRegion.cpp:244
int size() const
The current size of the integer array.
Definition: RecastAlloc.h:100
rcCompactSpan * spans
Array of spans. [Size: spanCount].
Definition: Recast.h:320
T rcMin(T a, T b)
Definition: Recast.h:566
An error log entry.
Definition: Recast.h:31
Definition: RecastAlloc.h:105
static bool mergeAndFilterRegions(rcContext *ctx, int minRegionArea, int mergeRegionSize, unsigned short &maxRegionId, rcCompactHeightfield &chf, unsigned short *srcReg, rcIntArray &overlaps)
Definition: RecastRegion.cpp:780
void * rcAlloc(int size, rcAllocHint hint)
Definition: RecastAlloc.cpp:44
The total time to apply the watershed algorithm. (See: rcBuildRegions)
Definition: Recast.h:81
G3D::int16 y
Definition: Vector2int16.h:38
int width
The width of the heightfield. (Along the x-axis in cell units.)
Definition: Recast.h:307
The total time to build the regions. (See: rcBuildRegions, rcBuildRegionsMonotone) ...
Definition: Recast.h:79
void startTimer(const rcTimerLabel label)
Definition: Recast.h:131
static unsigned short * expandRegions(int maxIter, unsigned short level, rcCompactHeightfield &chf, unsigned short *srcReg, unsigned short *srcDist, unsigned short *dstReg, unsigned short *dstDist, rcIntArray &stack, bool fillStack)
Definition: RecastRegion.cpp:346
int spanCount
The number of spans in the heightfield.
Definition: Recast.h:309
static void paintRectRegion(int minx, int maxx, int miny, int maxy, unsigned short regId, rcCompactHeightfield &chf, unsigned short *srcReg)
Definition: RecastRegion.cpp:1309
The time to flood regions while applying the watershed algorithm. (See: rcBuildRegions) ...
Definition: Recast.h:85
The time to expand regions while applying the watershed algorithm. (See: rcBuildRegions) ...
Definition: Recast.h:83
static void sortCellsByLevel(unsigned short startLevel, rcCompactHeightfield &chf, unsigned short *srcReg, unsigned int nbStacks, rcIntArray *stacks, unsigned short loglevelsPerStack)
Definition: RecastRegion.cpp:459
unsigned short maxDistance
The maximum distance value of any span within the field.
Definition: Recast.h:313
Memory used temporarily within a function.
Definition: RecastAlloc.h:27
void log(const rcLogCategory category, const char *format,...)
Definition: Recast.cpp:55
G3D::int16 x
Definition: Vector2int16.h:37
void stopTimer(const rcTimerLabel label)
Definition: Recast.h:135
static const unsigned short RC_BORDER_REG
Definition: Recast.h:498
A simple dynamic array of integers.
Definition: RecastAlloc.h:61
The time to filter out small regions. (See: rcBuildRegions, rcBuildRegionsMonotone) ...
Definition: Recast.h:87
static void appendStacks(rcIntArray &srcStack, rcIntArray &dstStack, unsigned short *srcReg)
Definition: RecastRegion.cpp:499

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

bool rcBuildRegionsMonotone ( rcContext ctx,
rcCompactHeightfield chf,
const int  borderSize,
const int  minRegionArea,
const int  mergeRegionArea 
)

Builds region data for the heightfield using simple monotone partitioning.

Parameters
[in,out]ctxThe build context to use during the operation.
[in,out]chfA populated compact heightfield.
[in]borderSizeThe size of the non-navigable border around the heightfield. [Limit: >=0] [Units: vx]
[in]minRegionAreaThe minimum number of cells allowed to form isolated island areas. [Limit: >=0] [Units: vx].
[in]mergeRegionAreaAny regions with a span count smaller than this value will, if possible, be merged with larger regions. [Limit: >=0] [Units: vx]
Returns
True if the operation completed successfully.

Non-null regions will consist of connected, non-overlapping walkable spans that form a single contour. Contours will form simple polygons.

If multiple regions form an area that is smaller than minRegionArea, then all spans will be re-assigned to the zero (null) region.

Partitioning can result in smaller than necessary regions. mergeRegionArea helps reduce unecessarily small regions.

See the rcConfig documentation for more information on the configuration parameters.

The region data will be available via the rcCompactHeightfield::maxRegions and rcCompactSpan::reg fields.

Warning
The distance field must be created using rcBuildDistanceField before attempting to build regions.
See also
rcCompactHeightfield, rcCompactSpan, rcBuildDistanceField, rcBuildRegionsMonotone, rcConfig
1359 {
1360  rcAssert(ctx);
1361 
1363 
1364  const int w = chf.width;
1365  const int h = chf.height;
1366  unsigned short id = 1;
1367 
1368  rcScopedDelete<unsigned short> srcReg = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP);
1369  if (!srcReg)
1370  {
1371  ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'src' (%d).", chf.spanCount);
1372  return false;
1373  }
1374  memset(srcReg,0,sizeof(unsigned short)*chf.spanCount);
1375 
1376  const int nsweeps = rcMax(chf.width,chf.height);
1378  if (!sweeps)
1379  {
1380  ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'sweeps' (%d).", nsweeps);
1381  return false;
1382  }
1383 
1384 
1385  // Mark border regions.
1386  if (borderSize > 0)
1387  {
1388  // Make sure border will not overflow.
1389  const int bw = rcMin(w, borderSize);
1390  const int bh = rcMin(h, borderSize);
1391  // Paint regions
1392  paintRectRegion(0, bw, 0, h, id|RC_BORDER_REG, chf, srcReg); id++;
1393  paintRectRegion(w-bw, w, 0, h, id|RC_BORDER_REG, chf, srcReg); id++;
1394  paintRectRegion(0, w, 0, bh, id|RC_BORDER_REG, chf, srcReg); id++;
1395  paintRectRegion(0, w, h-bh, h, id|RC_BORDER_REG, chf, srcReg); id++;
1396 
1397  chf.borderSize = borderSize;
1398  }
1399 
1400  rcIntArray prev(256);
1401 
1402  // Sweep one line at a time.
1403  for (int y = borderSize; y < h-borderSize; ++y)
1404  {
1405  // Collect spans from this row.
1406  prev.resize(id+1);
1407  memset(&prev[0],0,sizeof(int)*id);
1408  unsigned short rid = 1;
1409 
1410  for (int x = borderSize; x < w-borderSize; ++x)
1411  {
1412  const rcCompactCell& c = chf.cells[x+y*w];
1413 
1414  for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
1415  {
1416  const rcCompactSpan& s = chf.spans[i];
1417  if (chf.areas[i] == RC_NULL_AREA) continue;
1418 
1419  // -x
1420  unsigned short previd = 0;
1421  if (rcGetCon(s, 0) != RC_NOT_CONNECTED)
1422  {
1423  const int ax = x + rcGetDirOffsetX(0);
1424  const int ay = y + rcGetDirOffsetY(0);
1425  const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 0);
1426  if ((srcReg[ai] & RC_BORDER_REG) == 0 && chf.areas[i] == chf.areas[ai])
1427  previd = srcReg[ai];
1428  }
1429 
1430  if (!previd)
1431  {
1432  previd = rid++;
1433  sweeps[previd].rid = previd;
1434  sweeps[previd].ns = 0;
1435  sweeps[previd].nei = 0;
1436  }
1437 
1438  // -y
1439  if (rcGetCon(s,3) != RC_NOT_CONNECTED)
1440  {
1441  const int ax = x + rcGetDirOffsetX(3);
1442  const int ay = y + rcGetDirOffsetY(3);
1443  const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 3);
1444  if (srcReg[ai] && (srcReg[ai] & RC_BORDER_REG) == 0 && chf.areas[i] == chf.areas[ai])
1445  {
1446  unsigned short nr = srcReg[ai];
1447  if (!sweeps[previd].nei || sweeps[previd].nei == nr)
1448  {
1449  sweeps[previd].nei = nr;
1450  sweeps[previd].ns++;
1451  prev[nr]++;
1452  }
1453  else
1454  {
1455  sweeps[previd].nei = RC_NULL_NEI;
1456  }
1457  }
1458  }
1459 
1460  srcReg[i] = previd;
1461  }
1462  }
1463 
1464  // Create unique ID.
1465  for (int i = 1; i < rid; ++i)
1466  {
1467  if (sweeps[i].nei != RC_NULL_NEI && sweeps[i].nei != 0 &&
1468  prev[sweeps[i].nei] == (int)sweeps[i].ns)
1469  {
1470  sweeps[i].id = sweeps[i].nei;
1471  }
1472  else
1473  {
1474  sweeps[i].id = id++;
1475  }
1476  }
1477 
1478  // Remap IDs
1479  for (int x = borderSize; x < w-borderSize; ++x)
1480  {
1481  const rcCompactCell& c = chf.cells[x+y*w];
1482 
1483  for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
1484  {
1485  if (srcReg[i] > 0 && srcReg[i] < rid)
1486  srcReg[i] = sweeps[srcReg[i]].id;
1487  }
1488  }
1489  }
1490 
1491 
1493 
1494  // Merge regions and filter out small regions.
1495  rcIntArray overlaps;
1496  chf.maxRegions = id;
1497  if (!mergeAndFilterRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg, overlaps))
1498  return false;
1499 
1500  // Monotone partitioning does not generate overlapping regions.
1501 
1503 
1504  // Store the result out.
1505  for (int i = 0; i < chf.spanCount; ++i)
1506  chf.spans[i].reg = srcReg[i];
1507 
1509 
1510  return true;
1511 }
int height
The height of the heightfield. (Along the z-axis in cell units.)
Definition: Recast.h:308
#define rcAssert
Definition: RecastAssert.h:30
int borderSize
The AABB border size used during the build of the field. (See: rcConfig::borderSize) ...
Definition: Recast.h:312
unsigned short maxRegions
The maximum region id of any span within the field.
Definition: Recast.h:314
Represents a span of unobstructed space within a compact heightfield.
Definition: Recast.h:295
static const unsigned short RC_NULL_NEI
Definition: RecastRegion.cpp:1328
static const int RC_NOT_CONNECTED
Definition: Recast.h:547
unsigned short reg
The id of the region the span belongs to. (Or zero if not in a region.)
Definition: Recast.h:298
rcCompactCell * cells
Array of cells. [Size: width*height].
Definition: Recast.h:319
int rcGetDirOffsetY(int dir)
Definition: Recast.h:1048
rcCompactSpan * spans
Array of spans. [Size: spanCount].
Definition: Recast.h:320
T rcMin(T a, T b)
Definition: Recast.h:566
int rcGetCon(const rcCompactSpan &s, int dir)
Definition: Recast.h:1028
unsigned int index
Index to the first span in the column.
Definition: Recast.h:290
Provides information on the content of a cell column in a compact heightfield.
Definition: Recast.h:288
unsigned int count
Number of spans in the column.
Definition: Recast.h:291
An error log entry.
Definition: Recast.h:31
Definition: RecastAlloc.h:105
static bool mergeAndFilterRegions(rcContext *ctx, int minRegionArea, int mergeRegionSize, unsigned short &maxRegionId, rcCompactHeightfield &chf, unsigned short *srcReg, rcIntArray &overlaps)
Definition: RecastRegion.cpp:780
void * rcAlloc(int size, rcAllocHint hint)
Definition: RecastAlloc.cpp:44
int rcGetDirOffsetX(int dir)
Definition: Recast.h:1038
unsigned char * areas
Array containing area id data. [Size: spanCount].
Definition: Recast.h:322
Definition: RecastRegion.cpp:1330
G3D::int16 y
Definition: Vector2int16.h:38
int width
The width of the heightfield. (Along the x-axis in cell units.)
Definition: Recast.h:307
The total time to build the regions. (See: rcBuildRegions, rcBuildRegionsMonotone) ...
Definition: Recast.h:79
void startTimer(const rcTimerLabel label)
Definition: Recast.h:131
int spanCount
The number of spans in the heightfield.
Definition: Recast.h:309
static void paintRectRegion(int minx, int maxx, int miny, int maxy, unsigned short regId, rcCompactHeightfield &chf, unsigned short *srcReg)
Definition: RecastRegion.cpp:1309
int prev(int i, int n)
Definition: RecastContour.cpp:468
static const unsigned char RC_NULL_AREA
Definition: Recast.h:538
Memory used temporarily within a function.
Definition: RecastAlloc.h:27
T rcMax(T a, T b)
Definition: Recast.h:572
void log(const rcLogCategory category, const char *format,...)
Definition: Recast.cpp:55
G3D::int16 x
Definition: Vector2int16.h:37
void stopTimer(const rcTimerLabel label)
Definition: Recast.h:135
static const unsigned short RC_BORDER_REG
Definition: Recast.h:498
A simple dynamic array of integers.
Definition: RecastAlloc.h:61
The time to filter out small regions. (See: rcBuildRegions, rcBuildRegionsMonotone) ...
Definition: Recast.h:87

+ Here is the call graph for this function:

void rcCalcBounds ( const float *  verts,
int  nv,
float *  bmin,
float *  bmax 
)

Calculates the bounding box of an array of vertices.

Parameters
[in]vertsAn array of vertices. [(x, y, z) * nv]
[in]nvThe number of vertices in the verts array.
[out]bminThe minimum bounds of the AABB. [(x, y, z)] [Units: wu]
[out]bmaxThe maximum bounds of the AABB. [(x, y, z)] [Units: wu]
188 {
189  // Calculate bounding box.
190  rcVcopy(bmin, verts);
191  rcVcopy(bmax, verts);
192  for (int i = 1; i < nv; ++i)
193  {
194  const float* v = &verts[i*3];
195  rcVmin(bmin, v);
196  rcVmax(bmax, v);
197  }
198 }
void rcVmin(float *mn, const float *v)
Definition: Recast.h:657
void rcVcopy(float *dest, const float *v)
Definition: Recast.h:677
void rcVmax(float *mx, const float *v)
Definition: Recast.h:667

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void rcCalcGridSize ( const float *  bmin,
const float *  bmax,
float  cs,
int *  w,
int *  h 
)

Calculates the grid size based on the bounding box and grid cell size.

Parameters
[in]bminThe minimum bounds of the AABB. [(x, y, z)] [Units: wu]
[in]bmaxThe maximum bounds of the AABB. [(x, y, z)] [Units: wu]
[in]csThe xz-plane cell size. [Limit: > 0] [Units: wu]
[out]wThe width along the x-axis. [Limit: >= 0] [Units: vx]
[out]hThe height along the z-axis. [Limit: >= 0] [Units: vx]
201 {
202  *w = (int)((bmax[0] - bmin[0])/cs+0.5f);
203  *h = (int)((bmax[2] - bmin[2])/cs+0.5f);
204 }

+ Here is the caller graph for this function:

template<class T >
T rcClamp ( v,
mn,
mx 
)
inline

Clamps the value to the specified range.

Parameters
[in]vThe value to clamp.
[in]mnThe minimum permitted return value.
[in]mxThe maximum permitted return value.
Returns
The value, clamped to the specified range.
589 { return v < mn ? mn : (v > mx ? mx : v); }

+ Here is the caller graph for this function:

void rcClearUnwalkableTriangles ( rcContext ctx,
const float  walkableSlopeAngle,
const float *  verts,
int  ,
const int *  tris,
int  nt,
unsigned char *  areas 
)

Sets the area id of all triangles with a slope greater than or equal to the specified value to RC_NULL_AREA.

Parameters
[in,out]ctxThe build context to use during the operation.
[in]walkableSlopeAngleThe maximum slope that is considered walkable. [Limits: 0 <= value < 90] [Units: Degrees]
[in]vertsThe vertices. [(x, y, z) * nv]
[in]nvThe number of vertices.
[in]trisThe triangle vertex indices. [(vertA, vertB, vertC) * nt]
[in]ntThe number of triangles.
[out]areasThe triangle area ids. [Length: >= nt]

Only sets the area id's for the unwalkable triangles. Does not alter the area id's for walkable triangles.

See the rcConfig documentation for more information on the configuration parameters.

See also
rcHeightfield, rcClearUnwalkableTriangles, rcRasterizeTriangles
280 {
281  rcIgnoreUnused(ctx);
282 
283  const float walkableThr = cosf(walkableSlopeAngle/180.0f*RC_PI);
284 
285  float norm[3];
286 
287  for (int i = 0; i < nt; ++i)
288  {
289  const int* tri = &tris[i*3];
290  calcTriNormal(&verts[tri[0]*3], &verts[tri[1]*3], &verts[tri[2]*3], norm);
291  // Check if the face is walkable.
292  if (norm[1] <= walkableThr)
293  areas[i] = RC_NULL_AREA;
294  }
295 }
static void calcTriNormal(const float *v0, const float *v1, const float *v2, float *norm)
Definition: Recast.cpp:230
static const float RC_PI
The value of PI used by Recast.
Definition: Recast.h:23
static const unsigned char RC_NULL_AREA
Definition: Recast.h:538
void rcIgnoreUnused(const T &)
Definition: Recast.h:555

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

bool rcCopyPolyMesh ( rcContext ctx,
const rcPolyMesh src,
rcPolyMesh dst 
)

Copies the poly mesh data from src to dst.

Parameters
[in,out]ctxThe build context to use during the operation.
[in]srcThe source mesh to copy from.
[out]dstThe resulting detail mesh. (Must be pre-allocated, must be empty mesh.)
Returns
True if the operation completed successfully.
1483 {
1484  rcAssert(ctx);
1485 
1486  // Destination must be empty.
1487  rcAssert(dst.verts == 0);
1488  rcAssert(dst.polys == 0);
1489  rcAssert(dst.regs == 0);
1490  rcAssert(dst.areas == 0);
1491  rcAssert(dst.flags == 0);
1492 
1493  dst.nverts = src.nverts;
1494  dst.npolys = src.npolys;
1495  dst.maxpolys = src.npolys;
1496  dst.nvp = src.nvp;
1497  rcVcopy(dst.bmin, src.bmin);
1498  rcVcopy(dst.bmax, src.bmax);
1499  dst.cs = src.cs;
1500  dst.ch = src.ch;
1501  dst.borderSize = src.borderSize;
1502 
1503  dst.verts = (unsigned short*)rcAlloc(sizeof(unsigned short)*src.nverts*3, RC_ALLOC_PERM);
1504  if (!dst.verts)
1505  {
1506  ctx->log(RC_LOG_ERROR, "rcCopyPolyMesh: Out of memory 'dst.verts' (%d).", src.nverts*3);
1507  return false;
1508  }
1509  memcpy(dst.verts, src.verts, sizeof(unsigned short)*src.nverts*3);
1510 
1511  dst.polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*src.npolys*2*src.nvp, RC_ALLOC_PERM);
1512  if (!dst.polys)
1513  {
1514  ctx->log(RC_LOG_ERROR, "rcCopyPolyMesh: Out of memory 'dst.polys' (%d).", src.npolys*2*src.nvp);
1515  return false;
1516  }
1517  memcpy(dst.polys, src.polys, sizeof(unsigned short)*src.npolys*2*src.nvp);
1518 
1519  dst.regs = (unsigned short*)rcAlloc(sizeof(unsigned short)*src.npolys, RC_ALLOC_PERM);
1520  if (!dst.regs)
1521  {
1522  ctx->log(RC_LOG_ERROR, "rcCopyPolyMesh: Out of memory 'dst.regs' (%d).", src.npolys);
1523  return false;
1524  }
1525  memcpy(dst.regs, src.regs, sizeof(unsigned short)*src.npolys);
1526 
1527  dst.areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*src.npolys, RC_ALLOC_PERM);
1528  if (!dst.areas)
1529  {
1530  ctx->log(RC_LOG_ERROR, "rcCopyPolyMesh: Out of memory 'dst.areas' (%d).", src.npolys);
1531  return false;
1532  }
1533  memcpy(dst.areas, src.areas, sizeof(unsigned char)*src.npolys);
1534 
1535  dst.flags = (unsigned short*)rcAlloc(sizeof(unsigned short)*src.npolys, RC_ALLOC_PERM);
1536  if (!dst.flags)
1537  {
1538  ctx->log(RC_LOG_ERROR, "rcCopyPolyMesh: Out of memory 'dst.flags' (%d).", src.npolys);
1539  return false;
1540  }
1541  memcpy(dst.flags, src.flags, sizeof(unsigned short)*src.npolys);
1542 
1543  return true;
1544 }
unsigned char * areas
The area id assigned to each polygon. [Length: maxpolys].
Definition: Recast.h:389
#define rcAssert
Definition: RecastAssert.h:30
int nverts
The number of vertices.
Definition: Recast.h:390
unsigned short * verts
The mesh vertices. [Form: (x, y, z) * nverts].
Definition: Recast.h:385
float ch
The height of each cell. (The minimum increment along the y-axis.)
Definition: Recast.h:397
float bmax[3]
The maximum bounds in world space. [(x, y, z)].
Definition: Recast.h:395
float cs
The size of each cell. (On the xz-plane.)
Definition: Recast.h:396
An error log entry.
Definition: Recast.h:31
void * rcAlloc(int size, rcAllocHint hint)
Definition: RecastAlloc.cpp:44
void rcVcopy(float *dest, const float *v)
Definition: Recast.h:677
Memory will persist after a function call.
Definition: RecastAlloc.h:26
unsigned short * flags
The user defined flags for each polygon. [Length: maxpolys].
Definition: Recast.h:388
int borderSize
The AABB border size used to generate the source data from which the mesh was derived.
Definition: Recast.h:398
void log(const rcLogCategory category, const char *format,...)
Definition: Recast.cpp:55
int npolys
The number of polygons.
Definition: Recast.h:391
int maxpolys
The number of allocated polygons.
Definition: Recast.h:392
unsigned short * regs
The region id assigned to each polygon. [Length: maxpolys].
Definition: Recast.h:387
float bmin[3]
The minimum bounds in world space. [(x, y, z)].
Definition: Recast.h:394
int nvp
The maximum number of vertices per polygon.
Definition: Recast.h:393
unsigned short * polys
Polygon and neighbor data. [Length: maxpolys * 2 * nvp].
Definition: Recast.h:386

+ Here is the call graph for this function:

bool rcCreateHeightfield ( rcContext ctx,
rcHeightfield hf,
int  width,
int  height,
const float *  bmin,
const float *  bmax,
float  cs,
float  ch 
)

Initializes a new heightfield.

Parameters
[in,out]ctxThe build context to use during the operation.
[in,out]hfThe allocated heightfield to initialize.
[in]widthThe width of the field along the x-axis. [Limit: >= 0] [Units: vx]
[in]heightThe height of the field along the z-axis. [Limit: >= 0] [Units: vx]
[in]bminThe minimum bounds of the field's AABB. [(x, y, z)] [Units: wu]
[in]bmaxThe maximum bounds of the field's AABB. [(x, y, z)] [Units: wu]
[in]csThe xz-plane cell size to use for the field. [Limit: > 0] [Units: wu]
[in]chThe y-axis cell size to use for field. [Limit: > 0] [Units: wu]

See the rcConfig documentation for more information on the configuration parameters.

See also
rcAllocHeightfield, rcHeightfield
214 {
215  rcIgnoreUnused(ctx);
216 
217  hf.width = width;
218  hf.height = height;
219  rcVcopy(hf.bmin, bmin);
220  rcVcopy(hf.bmax, bmax);
221  hf.cs = cs;
222  hf.ch = ch;
223  hf.spans = (rcSpan**)rcAlloc(sizeof(rcSpan*)*hf.width*hf.height, RC_ALLOC_PERM);
224  if (!hf.spans)
225  return false;
226  memset(hf.spans, 0, sizeof(rcSpan*)*hf.width*hf.height);
227  return true;
228 }
int width
The width of the heightfield. (Along the x-axis in cell units.)
Definition: Recast.h:276
float ch
The height of each cell. (The minimum increment along the y-axis.)
Definition: Recast.h:281
Definition: Recast.h:256
float bmax[3]
The maximum bounds in world space. [(x, y, z)].
Definition: Recast.h:279
void * rcAlloc(int size, rcAllocHint hint)
Definition: RecastAlloc.cpp:44
float cs
The size of each cell. (On the xz-plane.)
Definition: Recast.h:280
void rcVcopy(float *dest, const float *v)
Definition: Recast.h:677
Memory will persist after a function call.
Definition: RecastAlloc.h:26
float bmin[3]
The minimum bounds in world space. [(x, y, z)].
Definition: Recast.h:278
int height
The height of the heightfield. (Along the z-axis in cell units.)
Definition: Recast.h:277
void rcIgnoreUnused(const T &)
Definition: Recast.h:555
rcSpan ** spans
Heightfield of spans (width*height).
Definition: Recast.h:282

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

bool rcErodeWalkableArea ( rcContext ctx,
int  radius,
rcCompactHeightfield chf 
)

Erodes the walkable area within the heightfield by the specified radius.

Parameters
[in,out]ctxThe build context to use during the operation.
[in]radiusThe radius of erosion. [Limits: 0 < value < 255] [Units: vx]
[in,out]chfThe populated compact heightfield to erode.
Returns
True if the operation completed successfully.

Basically, any spans that are closer to a boundary or obstruction than the specified radius are marked as unwalkable.

This method is usually called immediately after the heightfield has been built.

See also
rcCompactHeightfield, rcBuildCompactHeightfield, rcConfig::walkableRadius
38 {
39  rcAssert(ctx);
40 
41  const int w = chf.width;
42  const int h = chf.height;
43 
45 
46  unsigned char* dist = (unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP);
47  if (!dist)
48  {
49  ctx->log(RC_LOG_ERROR, "erodeWalkableArea: Out of memory 'dist' (%d).", chf.spanCount);
50  return false;
51  }
52 
53  // Init distance.
54  memset(dist, 0xff, sizeof(unsigned char)*chf.spanCount);
55 
56  // Mark boundary cells.
57  for (int y = 0; y < h; ++y)
58  {
59  for (int x = 0; x < w; ++x)
60  {
61  const rcCompactCell& c = chf.cells[x+y*w];
62  for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
63  {
64  if (chf.areas[i] == RC_NULL_AREA)
65  {
66  dist[i] = 0;
67  }
68  else
69  {
70  const rcCompactSpan& s = chf.spans[i];
71  int nc = 0;
72  for (int dir = 0; dir < 4; ++dir)
73  {
74  if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
75  {
76  const int nx = x + rcGetDirOffsetX(dir);
77  const int ny = y + rcGetDirOffsetY(dir);
78  const int nidx = (int)chf.cells[nx+ny*w].index + rcGetCon(s, dir);
79  if (chf.areas[nidx] != RC_NULL_AREA)
80  {
81  nc++;
82  }
83  }
84  }
85  // At least one missing neighbour.
86  if (nc != 4)
87  dist[i] = 0;
88  }
89  }
90  }
91  }
92 
93  unsigned char nd;
94 
95  // Pass 1
96  for (int y = 0; y < h; ++y)
97  {
98  for (int x = 0; x < w; ++x)
99  {
100  const rcCompactCell& c = chf.cells[x+y*w];
101  for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
102  {
103  const rcCompactSpan& s = chf.spans[i];
104 
105  if (rcGetCon(s, 0) != RC_NOT_CONNECTED)
106  {
107  // (-1,0)
108  const int ax = x + rcGetDirOffsetX(0);
109  const int ay = y + rcGetDirOffsetY(0);
110  const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 0);
111  const rcCompactSpan& as = chf.spans[ai];
112  nd = (unsigned char)rcMin((int)dist[ai]+2, 255);
113  if (nd < dist[i])
114  dist[i] = nd;
115 
116  // (-1,-1)
117  if (rcGetCon(as, 3) != RC_NOT_CONNECTED)
118  {
119  const int aax = ax + rcGetDirOffsetX(3);
120  const int aay = ay + rcGetDirOffsetY(3);
121  const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 3);
122  nd = (unsigned char)rcMin((int)dist[aai]+3, 255);
123  if (nd < dist[i])
124  dist[i] = nd;
125  }
126  }
127  if (rcGetCon(s, 3) != RC_NOT_CONNECTED)
128  {
129  // (0,-1)
130  const int ax = x + rcGetDirOffsetX(3);
131  const int ay = y + rcGetDirOffsetY(3);
132  const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 3);
133  const rcCompactSpan& as = chf.spans[ai];
134  nd = (unsigned char)rcMin((int)dist[ai]+2, 255);
135  if (nd < dist[i])
136  dist[i] = nd;
137 
138  // (1,-1)
139  if (rcGetCon(as, 2) != RC_NOT_CONNECTED)
140  {
141  const int aax = ax + rcGetDirOffsetX(2);
142  const int aay = ay + rcGetDirOffsetY(2);
143  const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 2);
144  nd = (unsigned char)rcMin((int)dist[aai]+3, 255);
145  if (nd < dist[i])
146  dist[i] = nd;
147  }
148  }
149  }
150  }
151  }
152 
153  // Pass 2
154  for (int y = h-1; y >= 0; --y)
155  {
156  for (int x = w-1; x >= 0; --x)
157  {
158  const rcCompactCell& c = chf.cells[x+y*w];
159  for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
160  {
161  const rcCompactSpan& s = chf.spans[i];
162 
163  if (rcGetCon(s, 2) != RC_NOT_CONNECTED)
164  {
165  // (1,0)
166  const int ax = x + rcGetDirOffsetX(2);
167  const int ay = y + rcGetDirOffsetY(2);
168  const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 2);
169  const rcCompactSpan& as = chf.spans[ai];
170  nd = (unsigned char)rcMin((int)dist[ai]+2, 255);
171  if (nd < dist[i])
172  dist[i] = nd;
173 
174  // (1,1)
175  if (rcGetCon(as, 1) != RC_NOT_CONNECTED)
176  {
177  const int aax = ax + rcGetDirOffsetX(1);
178  const int aay = ay + rcGetDirOffsetY(1);
179  const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 1);
180  nd = (unsigned char)rcMin((int)dist[aai]+3, 255);
181  if (nd < dist[i])
182  dist[i] = nd;
183  }
184  }
185  if (rcGetCon(s, 1) != RC_NOT_CONNECTED)
186  {
187  // (0,1)
188  const int ax = x + rcGetDirOffsetX(1);
189  const int ay = y + rcGetDirOffsetY(1);
190  const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 1);
191  const rcCompactSpan& as = chf.spans[ai];
192  nd = (unsigned char)rcMin((int)dist[ai]+2, 255);
193  if (nd < dist[i])
194  dist[i] = nd;
195 
196  // (-1,1)
197  if (rcGetCon(as, 0) != RC_NOT_CONNECTED)
198  {
199  const int aax = ax + rcGetDirOffsetX(0);
200  const int aay = ay + rcGetDirOffsetY(0);
201  const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 0);
202  nd = (unsigned char)rcMin((int)dist[aai]+3, 255);
203  if (nd < dist[i])
204  dist[i] = nd;
205  }
206  }
207  }
208  }
209  }
210 
211  const unsigned char thr = (unsigned char)(radius*2);
212  for (int i = 0; i < chf.spanCount; ++i)
213  if (dist[i] < thr)
214  chf.areas[i] = RC_NULL_AREA;
215 
216  rcFree(dist);
217 
219 
220  return true;
221 }
int height
The height of the heightfield. (Along the z-axis in cell units.)
Definition: Recast.h:308
#define rcAssert
Definition: RecastAssert.h:30
Represents a span of unobstructed space within a compact heightfield.
Definition: Recast.h:295
static const int RC_NOT_CONNECTED
Definition: Recast.h:547
rcCompactCell * cells
Array of cells. [Size: width*height].
Definition: Recast.h:319
int rcGetDirOffsetY(int dir)
Definition: Recast.h:1048
rcCompactSpan * spans
Array of spans. [Size: spanCount].
Definition: Recast.h:320
T rcMin(T a, T b)
Definition: Recast.h:566
int rcGetCon(const rcCompactSpan &s, int dir)
Definition: Recast.h:1028
unsigned int index
Index to the first span in the column.
Definition: Recast.h:290
Provides information on the content of a cell column in a compact heightfield.
Definition: Recast.h:288
unsigned int count
Number of spans in the column.
Definition: Recast.h:291
An error log entry.
Definition: Recast.h:31
void rcFree(void *ptr)
Definition: RecastAlloc.cpp:55
void * rcAlloc(int size, rcAllocHint hint)
Definition: RecastAlloc.cpp:44
int rcGetDirOffsetX(int dir)
Definition: Recast.h:1038
The time to erode the walkable area. (See: rcErodeWalkableArea)
Definition: Recast.h:65
unsigned char * areas
Array containing area id data. [Size: spanCount].
Definition: Recast.h:322
G3D::int16 y
Definition: Vector2int16.h:38
int width
The width of the heightfield. (Along the x-axis in cell units.)
Definition: Recast.h:307
void startTimer(const rcTimerLabel label)
Definition: Recast.h:131
int spanCount
The number of spans in the heightfield.
Definition: Recast.h:309
static const unsigned char RC_NULL_AREA
Definition: Recast.h:538
Memory used temporarily within a function.
Definition: RecastAlloc.h:27
void log(const rcLogCategory category, const char *format,...)
Definition: Recast.cpp:55
G3D::int16 x
Definition: Vector2int16.h:37
void stopTimer(const rcTimerLabel label)
Definition: Recast.h:135

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void rcFilterLedgeSpans ( rcContext ctx,
const int  walkableHeight,
const int  walkableClimb,
rcHeightfield solid 
)

Marks spans that are ledges as not-walkable.

Parameters
[in,out]ctxThe build context to use during the operation.
[in]walkableHeightMinimum floor to 'ceiling' height that will still allow the floor area to be considered walkable. [Limit: >= 3] [Units: vx]
[in]walkableClimbMaximum ledge height that is considered to still be traversable. [Limit: >=0] [Units: vx]
[in,out]solidA fully built heightfield. (All spans have been added.)

A ledge is a span with one or more neighbors whose maximum is further away than walkableClimb from the current span's maximum. This method removes the impact of the overestimation of conservative voxelization so the resulting mesh will not have regions hanging in the air over ledges.

A span is a ledge if: rcAbs(currentSpan.smax - neighborSpan.smax) > walkableClimb

See also
rcHeightfield, rcConfig
86 {
87  rcAssert(ctx);
88 
90 
91  const int w = solid.width;
92  const int h = solid.height;
93  const int MAX_HEIGHT = 0xffff;
94 
95  // Mark border spans.
96  for (int y = 0; y < h; ++y)
97  {
98  for (int x = 0; x < w; ++x)
99  {
100  for (rcSpan* s = solid.spans[x + y*w]; s; s = s->next)
101  {
102  // Skip non walkable spans.
103  if (s->area == RC_NULL_AREA)
104  continue;
105 
106  const int bot = (int)(s->smax);
107  const int top = s->next ? (int)(s->next->smin) : MAX_HEIGHT;
108 
109  // Find neighbours minimum height.
110  int minh = MAX_HEIGHT;
111 
112  // Min and max height of accessible neighbours.
113  int asmin = s->smax;
114  int asmax = s->smax;
115 
116  for (int dir = 0; dir < 4; ++dir)
117  {
118  int dx = x + rcGetDirOffsetX(dir);
119  int dy = y + rcGetDirOffsetY(dir);
120  // Skip neighbours which are out of bounds.
121  if (dx < 0 || dy < 0 || dx >= w || dy >= h)
122  {
123  minh = rcMin(minh, -walkableClimb - bot);
124  continue;
125  }
126 
127  // From minus infinity to the first span.
128  rcSpan* ns = solid.spans[dx + dy*w];
129  int nbot = -walkableClimb;
130  int ntop = ns ? (int)ns->smin : MAX_HEIGHT;
131  // Skip neightbour if the gap between the spans is too small.
132  if (rcMin(top,ntop) - rcMax(bot,nbot) > walkableHeight)
133  minh = rcMin(minh, nbot - bot);
134 
135  // Rest of the spans.
136  for (ns = solid.spans[dx + dy*w]; ns; ns = ns->next)
137  {
138  nbot = (int)ns->smax;
139  ntop = ns->next ? (int)ns->next->smin : MAX_HEIGHT;
140  // Skip neightbour if the gap between the spans is too small.
141  if (rcMin(top,ntop) - rcMax(bot,nbot) > walkableHeight)
142  {
143  minh = rcMin(minh, nbot - bot);
144 
145  // Find min/max accessible neighbour height.
146  if (rcAbs(nbot - bot) <= walkableClimb)
147  {
148  if (nbot < asmin) asmin = nbot;
149  if (nbot > asmax) asmax = nbot;
150  }
151 
152  }
153  }
154  }
155 
156  // The current span is close to a ledge if the drop to any
157  // neighbour span is less than the walkableClimb.
158  if (minh < -walkableClimb)
159  s->area = RC_NULL_AREA;
160 
161  // If the difference between all neighbours is too large,
162  // we are at steep slope, mark the span as ledge.
163  if ((asmax - asmin) > walkableClimb)
164  {
165  s->area = RC_NULL_AREA;
166  }
167  }
168  }
169  }
170 
172 }
#define rcAssert
Definition: RecastAssert.h:30
int width
The width of the heightfield. (Along the x-axis in cell units.)
Definition: Recast.h:276
T rcAbs(T a)
Definition: Recast.h:577
int rcGetDirOffsetY(int dir)
Definition: Recast.h:1048
T rcMin(T a, T b)
Definition: Recast.h:566
Definition: Recast.h:256
int rcGetDirOffsetX(int dir)
Definition: Recast.h:1038
G3D::int16 y
Definition: Vector2int16.h:38
unsigned int smin
The lower limit of the span. [Limit: < smax].
Definition: Recast.h:258
void startTimer(const rcTimerLabel label)
Definition: Recast.h:131
unsigned int smax
The upper limit of the span. [Limit: <= RC_SPAN_MAX_HEIGHT].
Definition: Recast.h:259
rcSpan * next
The next span higher up in column.
Definition: Recast.h:261
static const unsigned char RC_NULL_AREA
Definition: Recast.h:538
T rcMax(T a, T b)
Definition: Recast.h:572
G3D::int16 x
Definition: Vector2int16.h:37
int height
The height of the heightfield. (Along the z-axis in cell units.)
Definition: Recast.h:277
void stopTimer(const rcTimerLabel label)
Definition: Recast.h:135
#define MAX_HEIGHT
Definition: Map.h:247
The time to filter ledge spans. (See: rcFilterLedgeSpans)
Definition: Recast.h:53
rcSpan ** spans
Heightfield of spans (width*height).
Definition: Recast.h:282

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void rcFilterLowHangingWalkableObstacles ( rcContext ctx,
const int  walkableClimb,
rcHeightfield solid 
)

Marks non-walkable spans as walkable if their maximum is within walkableClimp of a walkable neihbor.

Parameters
[in,out]ctxThe build context to use during the operation.
[in]walkableClimbMaximum ledge height that is considered to still be traversable. [Limit: >=0] [Units: vx]
[in,out]solidA fully built heightfield. (All spans have been added.)

Allows the formation of walkable regions that will flow over low lying objects such as curbs, and up structures such as stairways.

Two neighboring spans are walkable if: rcAbs(currentSpan.smax - neighborSpan.smax) < waklableClimb

Warning
Will override the effect of rcFilterLedgeSpans. So if both filters are used, call rcFilterLedgeSpans after calling this filter.
See also
rcHeightfield, rcConfig
37 {
38  rcAssert(ctx);
39 
41 
42  const int w = solid.width;
43  const int h = solid.height;
44 
45  for (int y = 0; y < h; ++y)
46  {
47  for (int x = 0; x < w; ++x)
48  {
49  rcSpan* ps = 0;
50  bool previousWalkable = false;
51  unsigned char previousArea = RC_NULL_AREA;
52 
53  for (rcSpan* s = solid.spans[x + y*w]; s; ps = s, s = s->next)
54  {
55  const bool walkable = s->area != RC_NULL_AREA;
56  // If current span is not walkable, but there is walkable
57  // span just below it, mark the span above it walkable too.
58  if (!walkable && previousWalkable)
59  {
60  if (rcAbs((int)s->smax - (int)ps->smax) <= walkableClimb)
61  s->area = previousArea;
62  }
63  // Copy walkable flag so that it cannot propagate
64  // past multiple non-walkable objects.
65  previousWalkable = walkable;
66  previousArea = s->area;
67  }
68  }
69  }
70 
72 }
#define rcAssert
Definition: RecastAssert.h:30
int width
The width of the heightfield. (Along the x-axis in cell units.)
Definition: Recast.h:276
T rcAbs(T a)
Definition: Recast.h:577
Definition: Recast.h:256
G3D::int16 y
Definition: Vector2int16.h:38
void startTimer(const rcTimerLabel label)
Definition: Recast.h:131
unsigned int smax
The upper limit of the span. [Limit: <= RC_SPAN_MAX_HEIGHT].
Definition: Recast.h:259
rcSpan * next
The next span higher up in column.
Definition: Recast.h:261
static const unsigned char RC_NULL_AREA
Definition: Recast.h:538
G3D::int16 x
Definition: Vector2int16.h:37
int height
The height of the heightfield. (Along the z-axis in cell units.)
Definition: Recast.h:277
void stopTimer(const rcTimerLabel label)
Definition: Recast.h:135
rcSpan ** spans
Heightfield of spans (width*height).
Definition: Recast.h:282
The time to filter low obstacles. (See: rcFilterLowHangingWalkableObstacles)
Definition: Recast.h:59

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void rcFilterWalkableLowHeightSpans ( rcContext ctx,
int  walkableHeight,
rcHeightfield solid 
)

Marks walkable spans as not walkable if the clearence above the span is less than the specified height.

Parameters
[in,out]ctxThe build context to use during the operation.
[in]walkableHeightMinimum floor to 'ceiling' height that will still allow the floor area to be considered walkable. [Limit: >= 3] [Units: vx]
[in,out]solidA fully built heightfield. (All spans have been added.)

For this filter, the clearance above the span is the distance from the span's maximum to the next higher span's minimum. (Same grid column.)

See also
rcHeightfield, rcConfig
181 {
182  rcAssert(ctx);
183 
185 
186  const int w = solid.width;
187  const int h = solid.height;
188  const int MAX_HEIGHT = 0xffff;
189 
190  // Remove walkable flag from spans which do not have enough
191  // space above them for the agent to stand there.
192  for (int y = 0; y < h; ++y)
193  {
194  for (int x = 0; x < w; ++x)
195  {
196  for (rcSpan* s = solid.spans[x + y*w]; s; s = s->next)
197  {
198  const int bot = (int)(s->smax);
199  const int top = s->next ? (int)(s->next->smin) : MAX_HEIGHT;
200  if ((top - bot) <= walkableHeight)
201  s->area = RC_NULL_AREA;
202  }
203  }
204  }
205 
207 }
#define rcAssert
Definition: RecastAssert.h:30
int width
The width of the heightfield. (Along the x-axis in cell units.)
Definition: Recast.h:276
Definition: Recast.h:256
The time to filter low height spans. (See: rcFilterWalkableLowHeightSpans)
Definition: Recast.h:55
G3D::int16 y
Definition: Vector2int16.h:38
void startTimer(const rcTimerLabel label)
Definition: Recast.h:131
rcSpan * next
The next span higher up in column.
Definition: Recast.h:261
static const unsigned char RC_NULL_AREA
Definition: Recast.h:538
G3D::int16 x
Definition: Vector2int16.h:37
int height
The height of the heightfield. (Along the z-axis in cell units.)
Definition: Recast.h:277
void stopTimer(const rcTimerLabel label)
Definition: Recast.h:135
#define MAX_HEIGHT
Definition: Map.h:247
rcSpan ** spans
Heightfield of spans (width*height).
Definition: Recast.h:282

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void rcFreeCompactHeightfield ( rcCompactHeightfield chf)

Frees the specified compact heightfield object using the Recast allocator.

Parameters
[in]chfA compact heightfield allocated using rcAllocCompactHeightfield
See also
rcAllocCompactHeightfield
103 {
104  if (!chf) return;
105  rcFree(chf->cells);
106  rcFree(chf->spans);
107  rcFree(chf->dist);
108  rcFree(chf->areas);
109  rcFree(chf);
110 }
unsigned short * dist
Array containing border distance data. [Size: spanCount].
Definition: Recast.h:321
rcCompactCell * cells
Array of cells. [Size: width*height].
Definition: Recast.h:319
rcCompactSpan * spans
Array of spans. [Size: spanCount].
Definition: Recast.h:320
void rcFree(void *ptr)
Definition: RecastAlloc.cpp:55
unsigned char * areas
Array containing area id data. [Size: spanCount].
Definition: Recast.h:322

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void rcFreeContourSet ( rcContourSet cset)

Frees the specified contour set using the Recast allocator.

Parameters
[in]csetA contour set allocated using rcAllocContourSet
See also
rcAllocContourSet
142 {
143  if (!cset) return;
144  for (int i = 0; i < cset->nconts; ++i)
145  {
146  rcFree(cset->conts[i].verts);
147  rcFree(cset->conts[i].rverts);
148  }
149  rcFree(cset->conts);
150  rcFree(cset);
151 }
int * rverts
Raw contour vertex and connection data. [Size: 4 * nrverts].
Definition: Recast.h:360
rcContour * conts
An array of the contours in the set. [Size: nconts].
Definition: Recast.h:370
int nconts
The number of contours in the set.
Definition: Recast.h:371
int * verts
Simplified contour vertex and connection data. [Size: 4 * nverts].
Definition: Recast.h:358
void rcFree(void *ptr)
Definition: RecastAlloc.cpp:55

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void rcFreeHeightField ( rcHeightfield hf)

Frees the specified heightfield object using the Recast allocator.

Parameters
[in]hfA heightfield allocated using rcAllocHeightfield
See also
rcAllocHeightfield
81 {
82  if (!hf) return;
83  // Delete span array.
84  rcFree(hf->spans);
85  // Delete span pools.
86  while (hf->pools)
87  {
88  rcSpanPool* next = hf->pools->next;
89  rcFree(hf->pools);
90  hf->pools = next;
91  }
92  rcFree(hf);
93 }
int next(int i, int n)
Definition: RecastContour.cpp:469
void rcFree(void *ptr)
Definition: RecastAlloc.cpp:55
Definition: Recast.h:266
rcSpanPool * next
The next span pool.
Definition: Recast.h:268
rcSpanPool * pools
Linked list of span pools.
Definition: Recast.h:283
rcSpan ** spans
Heightfield of spans (width*height).
Definition: Recast.h:282

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void rcFreeHeightfieldLayerSet ( rcHeightfieldLayerSet lset)

Frees the specified heightfield layer set using the Recast allocator.

Parameters
[in]lsetA heightfield layer set allocated using rcAllocHeightfieldLayerSet
See also
rcAllocHeightfieldLayerSet
121 {
122  if (!lset) return;
123  for (int i = 0; i < lset->nlayers; ++i)
124  {
125  rcFree(lset->layers[i].heights);
126  rcFree(lset->layers[i].areas);
127  rcFree(lset->layers[i].cons);
128  }
129  rcFree(lset->layers);
130  rcFree(lset);
131 }
rcHeightfieldLayer * layers
The layers in the set. [Size: nlayers].
Definition: Recast.h:351
unsigned char * heights
The heightfield. [Size: width * height].
Definition: Recast.h:341
unsigned char * areas
Area ids. [Size: Same as heights].
Definition: Recast.h:342
void rcFree(void *ptr)
Definition: RecastAlloc.cpp:55
unsigned char * cons
Packed neighbor connection information. [Size: Same as heights].
Definition: Recast.h:343
int nlayers
The number of layers in the set.
Definition: Recast.h:352

+ Here is the call graph for this function:

void rcFreePolyMesh ( rcPolyMesh pmesh)

Frees the specified polygon mesh using the Recast allocator.

Parameters
[in]pmeshA polygon mesh allocated using rcAllocPolyMesh
See also
rcAllocPolyMesh
161 {
162  if (!pmesh) return;
163  rcFree(pmesh->verts);
164  rcFree(pmesh->polys);
165  rcFree(pmesh->regs);
166  rcFree(pmesh->flags);
167  rcFree(pmesh->areas);
168  rcFree(pmesh);
169 }
unsigned char * areas
The area id assigned to each polygon. [Length: maxpolys].
Definition: Recast.h:389
unsigned short * verts
The mesh vertices. [Form: (x, y, z) * nverts].
Definition: Recast.h:385
void rcFree(void *ptr)
Definition: RecastAlloc.cpp:55
unsigned short * flags
The user defined flags for each polygon. [Length: maxpolys].
Definition: Recast.h:388
unsigned short * regs
The region id assigned to each polygon. [Length: maxpolys].
Definition: Recast.h:387
unsigned short * polys
Polygon and neighbor data. [Length: maxpolys * 2 * nvp].
Definition: Recast.h:386

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void rcFreePolyMeshDetail ( rcPolyMeshDetail dmesh)

Frees the specified detail mesh using the Recast allocator.

Parameters
[in]dmeshA detail mesh allocated using rcAllocPolyMeshDetail
See also
rcAllocPolyMeshDetail
179 {
180  if (!dmesh) return;
181  rcFree(dmesh->meshes);
182  rcFree(dmesh->verts);
183  rcFree(dmesh->tris);
184  rcFree(dmesh);
185 }
float * verts
The mesh vertices. [Size: 3*nverts].
Definition: Recast.h:407
void rcFree(void *ptr)
Definition: RecastAlloc.cpp:55
unsigned char * tris
The mesh triangles. [Size: 4*ntris].
Definition: Recast.h:408
unsigned int * meshes
The sub-mesh data. [Size: 4*nmeshes].
Definition: Recast.h:406

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

int rcGetCon ( const rcCompactSpan s,
int  dir 
)
inline

Gets neighbor connection data for the specified direction.

Parameters
[in]sThe span to check.
[in]dirThe direction to check. [Limits: 0 <= value < 4]
Returns
The neighbor connection data for the specified direction, or RC_NOT_CONNECTED if there is no connection.
1029 {
1030  const unsigned int shift = (unsigned int)dir*6;
1031  return (s.con >> shift) & 0x3f;
1032 }
unsigned int con
Packed neighbor connection data.
Definition: Recast.h:299

+ Here is the caller graph for this function:

int rcGetDirOffsetX ( int  dir)
inline

Gets the standard width (x-axis) offset for the specified direction.

Parameters
[in]dirThe direction. [Limits: 0 <= value < 4]
Returns
The width offset to apply to the current cell position to move in the direction.
1039 {
1040  const int offset[4] = { -1, 0, 1, 0, };
1041  return offset[dir&0x03];
1042 }

+ Here is the caller graph for this function:

int rcGetDirOffsetY ( int  dir)
inline

Gets the standard height (z-axis) offset for the specified direction.

Parameters
[in]dirThe direction. [Limits: 0 <= value < 4]
Returns
The height offset to apply to the current cell position to move in the direction.
1049 {
1050  const int offset[4] = { 0, 1, 0, -1 };
1051  return offset[dir&0x03];
1052 }

+ Here is the caller graph for