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
rcHeightfield *	rcAllocHeightfield ()
void	rcFreeHeightField (rcHeightfield *hf)
rcCompactHeightfield *	rcAllocCompactHeightfield ()
void	rcFreeCompactHeightfield (rcCompactHeightfield *chf)
rcHeightfieldLayerSet *	rcAllocHeightfieldLayerSet ()
void	rcFreeHeightfieldLayerSet (rcHeightfieldLayerSet *lset)
rcContourSet *	rcAllocContourSet ()
void	rcFreeContourSet (rcContourSet *cset)
rcPolyMesh *	rcAllocPolyMesh ()
void	rcFreePolyMesh (rcPolyMesh *pmesh)
rcPolyMeshDetail *	rcAllocPolyMeshDetail ()
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 >
T	rcMin (T a, T b)
template<class T >
T	rcMax (T a, T b)
template<class T >
T	rcAbs (T a)
template<class T >
T	rcSqr (T a)
template<class T >
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
See also rcCompactHeightfield
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
See also rcHeightfieldLayer, rcContourSet, rcPolyMesh, rcPolyMeshDetail
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

enum rcBuildContoursFlags

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.

{
 RC_CONTOUR_TESS_WALL_EDGES = 0x01, 
 RC_CONTOUR_TESS_AREA_EDGES = 0x02, 
};

enum rcLogCategory

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.

{
 RC_LOG_PROGRESS = 1, 
 RC_LOG_WARNING, 
 RC_LOG_ERROR, 
};

enum rcTimerLabel

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

{
 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
};

Function Documentation

template<class T >

T rcAbs ( T  a )

inline

Returns the absolute value.

Parameters

[in]

a

The value.

Returns

The absolute value of the specified value.

{ 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]	ctx	The build context to use during the operation.
[in,out]	hf	An initialized heightfield.
[in]	x	The width index where the span is to be added. [Limits: 0 <= value < rcHeightfield::width]
[in]	y	The height index where the span is to be added. [Limits: 0 <= value < rcHeightfield::height]
[in]	smin	The minimum height of the span. [Limit: < smax] [Units: vx]
[in]	smax	The maximum height of the span. [Limit: <= RC_SPAN_MAX_HEIGHT] [Units: vx]
[in]	area	The area id of the span. [Limit: <= RC_WALKABLE_AREA)
[in]	flagMergeThr	The 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.

{
// rcAssert(ctx);
 addSpan(hf, x,y, smin, smax, area, flagMergeThr);
}

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

{
 rcCompactHeightfield* chf = (rcCompactHeightfield*)rcAlloc(sizeof(rcCompactHeightfield), RC_ALLOC_PERM);
 memset(chf, 0, sizeof(rcCompactHeightfield));
 return chf;
}

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

{
 rcContourSet* cset = (rcContourSet*)rcAlloc(sizeof(rcContourSet), RC_ALLOC_PERM);
 memset(cset, 0, sizeof(rcContourSet));
 return cset;
}

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

{
 rcHeightfield* hf = (rcHeightfield*)rcAlloc(sizeof(rcHeightfield), RC_ALLOC_PERM);
 memset(hf, 0, sizeof(rcHeightfield));
 return hf;
}

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

{
 rcHeightfieldLayerSet* lset = (rcHeightfieldLayerSet*)rcAlloc(sizeof(rcHeightfieldLayerSet), RC_ALLOC_PERM);
 memset(lset, 0, sizeof(rcHeightfieldLayerSet));
 return lset;
}

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

{
 rcPolyMesh* pmesh = (rcPolyMesh*)rcAlloc(sizeof(rcPolyMesh), RC_ALLOC_PERM);
 memset(pmesh, 0, sizeof(rcPolyMesh));
 return pmesh;
}

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

{
 rcPolyMeshDetail* dmesh = (rcPolyMeshDetail*)rcAlloc(sizeof(rcPolyMeshDetail), RC_ALLOC_PERM);
 memset(dmesh, 0, sizeof(rcPolyMeshDetail));
 return dmesh;
}

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]	ctx	The build context to use during the operation.
[in]	walkableHeight	Minimum floor to 'ceiling' height that will still allow the floor area to be considered walkable. [Limit: >= 3] [Units: vx]
[in]	walkableClimb	Maximum ledge height that is considered to still be traversable. [Limit: >=0] [Units: vx]
[in]	hf	The heightfield to be compacted.
[out]	chf	The 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

{
 rcAssert(ctx);
 
 ctx->startTimer(RC_TIMER_BUILD_COMPACTHEIGHTFIELD);
 
 const int w = hf.width;
 const int h = hf.height;
 const int spanCount = rcGetHeightFieldSpanCount(ctx, hf);

 // Fill in header.
 chf.width = w;
 chf.height = h;
 chf.spanCount = spanCount;
 chf.walkableHeight = walkableHeight;
 chf.walkableClimb = walkableClimb;
 chf.maxRegions = 0;
 rcVcopy(chf.bmin, hf.bmin);
 rcVcopy(chf.bmax, hf.bmax);
 chf.bmax[1] += walkableHeight*hf.ch;
 chf.cs = hf.cs;
 chf.ch = hf.ch;
 chf.cells = (rcCompactCell*)rcAlloc(sizeof(rcCompactCell)*w*h, RC_ALLOC_PERM);
 if (!chf.cells)
 {
 ctx->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Out of memory 'chf.cells' (%d)", w*h);
 return false;
 }
 memset(chf.cells, 0, sizeof(rcCompactCell)*w*h);
 chf.spans = (rcCompactSpan*)rcAlloc(sizeof(rcCompactSpan)*spanCount, RC_ALLOC_PERM);
 if (!chf.spans)
 {
 ctx->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Out of memory 'chf.spans' (%d)", spanCount);
 return false;
 }
 memset(chf.spans, 0, sizeof(rcCompactSpan)*spanCount);
 chf.areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*spanCount, RC_ALLOC_PERM);
 if (!chf.areas)
 {
 ctx->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Out of memory 'chf.areas' (%d)", spanCount);
 return false;
 }
 memset(chf.areas, RC_NULL_AREA, sizeof(unsigned char)*spanCount);
 
 const int MAX_HEIGHT = 0xffff;
 
 // Fill in cells and spans.
 int idx = 0;
 for (int y = 0; y < h; ++y)
 {
 for (int x = 0; x < w; ++x)
 {
 const rcSpan* s = hf.spans[x + y*w];
 // If there are no spans at this cell, just leave the data to index=0, count=0.
 if (!s) continue;
 rcCompactCell& c = chf.cells[x+y*w];
 c.index = idx;
 c.count = 0;
 while (s)
 {
 if (s->area != RC_NULL_AREA)
 {
 const int bot = (int)s->smax;
 const int top = s->next ? (int)s->next->smin : MAX_HEIGHT;
 chf.spans[idx].y = (unsigned short)rcClamp(bot, 0, 0xffff);
 chf.spans[idx].h = (unsigned char)rcClamp(top - bot, 0, 0xff);
 chf.areas[idx] = s->area;
 idx++;
 c.count++;
 }
 s = s->next;
 }
 }
 }

 // Find neighbour connections.
 const int MAX_LAYERS = RC_NOT_CONNECTED-1;
 int tooHighNeighbour = 0;
 for (int y = 0; y < h; ++y)
 {
 for (int x = 0; x < w; ++x)
 {
 const rcCompactCell& c = chf.cells[x+y*w];
 for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
 {
 rcCompactSpan& s = chf.spans[i];
 
 for (int dir = 0; dir < 4; ++dir)
 {
 rcSetCon(s, dir, RC_NOT_CONNECTED);
 const int nx = x + rcGetDirOffsetX(dir);
 const int ny = y + rcGetDirOffsetY(dir);
 // First check that the neighbour cell is in bounds.
 if (nx < 0 || ny < 0 || nx >= w || ny >= h)
 continue;
 
 // Iterate over all neighbour spans and check if any of the is
 // accessible from current cell.
 const rcCompactCell& nc = chf.cells[nx+ny*w];
 for (int k = (int)nc.index, nk = (int)(nc.index+nc.count); k < nk; ++k)
 {
 const rcCompactSpan& ns = chf.spans[k];
 const int bot = rcMax(s.y, ns.y);
 const int top = rcMin(s.y+s.h, ns.y+ns.h);

 // Check that the gap between the spans is walkable,
 // and that the climb height between the gaps is not too high.
 if ((top - bot) >= walkableHeight && rcAbs((int)ns.y - (int)s.y) <= walkableClimb)
 {
 // Mark direction as walkable.
 const int lidx = k - (int)nc.index;
 if (lidx < 0 || lidx > MAX_LAYERS)
 {
 tooHighNeighbour = rcMax(tooHighNeighbour, lidx);
 continue;
 }
 rcSetCon(s, dir, lidx);
 break;
 }
 }
 
 }
 }
 }
 }
 
 if (tooHighNeighbour > MAX_LAYERS)
 {
 ctx->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Heightfield has too many layers %d (max: %d)",
 tooHighNeighbour, MAX_LAYERS);
 }
 
 ctx->stopTimer(RC_TIMER_BUILD_COMPACTHEIGHTFIELD);
 
 return true;
}

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]	ctx	The build context to use during the operation.
[in]	chf	A fully built compact heightfield.
[in]	maxError	The maximum distance a simplfied contour's border edges should deviate the original raw contour. [Limit: >=0] [Units: wu]
[in]	maxEdgeLen	The maximum allowed length for contour edges along the border of the mesh. [Limit: >=0] [Units: vx]
[out]	cset	The resulting contour set. (Must be pre-allocated.)
[in]	buildFlags	The 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

{
    rcAssert(ctx);
    
    const int w = chf.width;
    const int h = chf.height;
    const int borderSize = chf.borderSize;
    
    ctx->startTimer(RC_TIMER_BUILD_CONTOURS);
    
    rcVcopy(cset.bmin, chf.bmin);
    rcVcopy(cset.bmax, chf.bmax);
    if (borderSize > 0)
    {
        // If the heightfield was build with bordersize, remove the offset.
        const float pad = borderSize*chf.cs;
        cset.bmin[0] += pad;
        cset.bmin[2] += pad;
        cset.bmax[0] -= pad;
        cset.bmax[2] -= pad;
    }
    cset.cs = chf.cs;
    cset.ch = chf.ch;
    cset.width = chf.width - chf.borderSize*2;
    cset.height = chf.height - chf.borderSize*2;
    cset.borderSize = chf.borderSize;
    
    int maxContours = rcMax((int)chf.maxRegions, 8);
    cset.conts = (rcContour*)rcAlloc(sizeof(rcContour)*maxContours, RC_ALLOC_PERM);
    if (!cset.conts)
        return false;
    cset.nconts = 0;
    
    rcScopedDelete<unsigned char> flags = (unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP);
    if (!flags)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'flags' (%d).", chf.spanCount);
        return false;
    }
    
    ctx->startTimer(RC_TIMER_BUILD_CONTOURS_TRACE);
    
    // Mark boundaries.
    for (int y = 0; y < h; ++y)
    {
        for (int x = 0; x < w; ++x)
        {
            const rcCompactCell& c = chf.cells[x+y*w];
            for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
            {
                unsigned char res = 0;
                const rcCompactSpan& s = chf.spans[i];
                if (!chf.spans[i].reg || (chf.spans[i].reg & RC_BORDER_REG))
                {
                    flags[i] = 0;
                    continue;
                }
                for (int dir = 0; dir < 4; ++dir)
                {
                    unsigned short r = 0;
                    if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
                    {
                        const int ax = x + rcGetDirOffsetX(dir);
                        const int ay = y + rcGetDirOffsetY(dir);
                        const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);
                        r = chf.spans[ai].reg;
                    }
                    if (r == chf.spans[i].reg)
                        res |= (1 << dir);
                }
                flags[i] = res ^ 0xf; // Inverse, mark non connected edges.
            }
        }
    }
    
    ctx->stopTimer(RC_TIMER_BUILD_CONTOURS_TRACE);
    
    rcIntArray verts(256);
    rcIntArray simplified(64);
    
    for (int y = 0; y < h; ++y)
    {
        for (int x = 0; x < w; ++x)
        {
            const rcCompactCell& c = chf.cells[x+y*w];
            for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
            {
                if (flags[i] == 0 || flags[i] == 0xf)
                {
                    flags[i] = 0;
                    continue;
                }
                const unsigned short reg = chf.spans[i].reg;
                if (!reg || (reg & RC_BORDER_REG))
                    continue;
                const unsigned char area = chf.areas[i];
                
                verts.resize(0);
                simplified.resize(0);
                
                ctx->startTimer(RC_TIMER_BUILD_CONTOURS_TRACE);
                walkContour(x, y, i, chf, flags, verts);
                ctx->stopTimer(RC_TIMER_BUILD_CONTOURS_TRACE);
                
                ctx->startTimer(RC_TIMER_BUILD_CONTOURS_SIMPLIFY);
                simplifyContour(verts, simplified, maxError, maxEdgeLen, buildFlags);
                removeDegenerateSegments(simplified);
                ctx->stopTimer(RC_TIMER_BUILD_CONTOURS_SIMPLIFY);
                
                
                // Store region->contour remap info.
                // Create contour.
                if (simplified.size()/4 >= 3)
                {
                    if (cset.nconts >= maxContours)
                    {
                        // Allocate more contours.
                        // This happens when a region has holes.
                        const int oldMax = maxContours;
                        maxContours *= 2;
                        rcContour* newConts = (rcContour*)rcAlloc(sizeof(rcContour)*maxContours, RC_ALLOC_PERM);
                        for (int j = 0; j < cset.nconts; ++j)
                        {
                            newConts[j] = cset.conts[j];
                            // Reset source pointers to prevent data deletion.
                            cset.conts[j].verts = 0;
                            cset.conts[j].rverts = 0;
                        }
                        rcFree(cset.conts);
                        cset.conts = newConts;
                        
                        ctx->log(RC_LOG_WARNING, "rcBuildContours: Expanding max contours from %d to %d.", oldMax, maxContours);
                    }
                    
                    rcContour* cont = &cset.conts[cset.nconts++];
                    
                    cont->nverts = simplified.size()/4;
                    cont->verts = (int*)rcAlloc(sizeof(int)*cont->nverts*4, RC_ALLOC_PERM);
                    if (!cont->verts)
                    {
                        ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'verts' (%d).", cont->nverts);
                        return false;
                    }
                    memcpy(cont->verts, &simplified[0], sizeof(int)*cont->nverts*4);
                    if (borderSize > 0)
                    {
                        // If the heightfield was build with bordersize, remove the offset.
                        for (int j = 0; j < cont->nverts; ++j)
                        {
                            int* v = &cont->verts[j*4];
                            v[0] -= borderSize;
                            v[2] -= borderSize;
                        }
                    }
                    
                    cont->nrverts = verts.size()/4;
                    cont->rverts = (int*)rcAlloc(sizeof(int)*cont->nrverts*4, RC_ALLOC_PERM);
                    if (!cont->rverts)
                    {
                        ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'rverts' (%d).", cont->nrverts);
                        return false;
                    }
                    memcpy(cont->rverts, &verts[0], sizeof(int)*cont->nrverts*4);
                    if (borderSize > 0)
                    {
                        // If the heightfield was build with bordersize, remove the offset.
                        for (int j = 0; j < cont->nrverts; ++j)
                        {
                            int* v = &cont->rverts[j*4];
                            v[0] -= borderSize;
                            v[2] -= borderSize;
                        }
                    }
                    
                    cont->reg = reg;
                    cont->area = area;
                }
            }
        }
    }
    
    // Merge holes if needed.
    if (cset.nconts > 0)
    {
        // Calculate winding of all polygons.
        rcScopedDelete<char> winding = (char*)rcAlloc(sizeof(char)*cset.nconts, RC_ALLOC_TEMP);
        if (!winding)
        {
            ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'hole' (%d).", cset.nconts);
            return false;
        }
        int nholes = 0;
        for (int i = 0; i < cset.nconts; ++i)
        {
            rcContour& cont = cset.conts[i];
            // If the contour is wound backwards, it is a hole.
            winding[i] = calcAreaOfPolygon2D(cont.verts, cont.nverts) < 0 ? -1 : 1;
            if (winding[i] < 0)
                nholes++;
        }
        
        if (nholes > 0)
        {
            // Collect outline contour and holes contours per region.
            // We assume that there is one outline and multiple holes.
            const int nregions = chf.maxRegions+1;
            rcScopedDelete<rcContourRegion> regions = (rcContourRegion*)rcAlloc(sizeof(rcContourRegion)*nregions, RC_ALLOC_TEMP);
            if (!regions)
            {
                ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'regions' (%d).", nregions);
                return false;
            }
            memset(regions, 0, sizeof(rcContourRegion)*nregions);
            
            rcScopedDelete<rcContourHole> holes = (rcContourHole*)rcAlloc(sizeof(rcContourHole)*cset.nconts, RC_ALLOC_TEMP);
            if (!holes)
            {
                ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'holes' (%d).", cset.nconts);
                return false;
            }
            memset(holes, 0, sizeof(rcContourHole)*cset.nconts);
            
            for (int i = 0; i < cset.nconts; ++i)
            {
                rcContour& cont = cset.conts[i];
                // Positively would contours are outlines, negative holes.
                if (winding[i] > 0)
                {
                    if (regions[cont.reg].outline)
                        ctx->log(RC_LOG_ERROR, "rcBuildContours: Multiple outlines for region %d.", cont.reg);
                    regions[cont.reg].outline = &cont;
                }
                else
                {
                    regions[cont.reg].nholes++;
                }
            }
            int index = 0;
            for (int i = 0; i < nregions; i++)
            {
                if (regions[i].nholes > 0)
                {
                    regions[i].holes = &holes[index];
                    index += regions[i].nholes;
                    regions[i].nholes = 0;
                }
            }
            for (int i = 0; i < cset.nconts; ++i)
            {
                rcContour& cont = cset.conts[i];
                rcContourRegion& reg = regions[cont.reg];
                if (winding[i] < 0)
                    reg.holes[reg.nholes++].contour = &cont;
            }
            
            // Finally merge each regions holes into the outline.
            for (int i = 0; i < nregions; i++)
            {
                rcContourRegion& reg = regions[i];
                if (!reg.nholes) continue;
                
                if (reg.outline)
                {
                    mergeRegionHoles(ctx, reg);
                }
                else
                {
                    // The region does not have an outline.
                    // This can happen if the contour becaomes selfoverlapping because of
                    // too aggressive simplification settings.
                    ctx->log(RC_LOG_ERROR, "rcBuildContours: Bad outline for region %d, contour simplification is likely too aggressive.", i);
                }
            }
        }
        
    }
    
    ctx->stopTimer(RC_TIMER_BUILD_CONTOURS);
    
    return true;
}

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]	ctx	The build context to use during the operation.
[in,out]	chf	A 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

{
    rcAssert(ctx);
    
    ctx->startTimer(RC_TIMER_BUILD_DISTANCEFIELD);
    
    if (chf.dist)
    {
        rcFree(chf.dist);
        chf.dist = 0;
    }
    
    unsigned short* src = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP);
    if (!src)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildDistanceField: Out of memory 'src' (%d).", chf.spanCount);
        return false;
    }
    unsigned short* dst = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP);
    if (!dst)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildDistanceField: Out of memory 'dst' (%d).", chf.spanCount);
        rcFree(src);
        return false;
    }
    
    unsigned short maxDist = 0;

    ctx->startTimer(RC_TIMER_BUILD_DISTANCEFIELD_DIST);
    
    calculateDistanceField(chf, src, maxDist);
    chf.maxDistance = maxDist;
    
    ctx->stopTimer(RC_TIMER_BUILD_DISTANCEFIELD_DIST);
    
    ctx->startTimer(RC_TIMER_BUILD_DISTANCEFIELD_BLUR);
    
    // Blur
    if (boxBlur(chf, 1, src, dst) != src)
        rcSwap(src, dst);
    
    // Store distance.
    chf.dist = src;
    
    ctx->stopTimer(RC_TIMER_BUILD_DISTANCEFIELD_BLUR);

    ctx->stopTimer(RC_TIMER_BUILD_DISTANCEFIELD);
    
    rcFree(dst);
    
    return true;
}

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]	ctx	The build context to use during the operation.
[in]	chf	A fully built compact heightfield.
[in]	borderSize	The size of the non-navigable border around the heightfield. [Limit: >=0] [Units: vx]
[in]	walkableHeight	Minimum floor to 'ceiling' height that will still allow the floor area to be considered walkable. [Limit: >= 3] [Units: vx]
[out]	lset	The 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

{
    rcAssert(ctx);
    
    ctx->startTimer(RC_TIMER_BUILD_LAYERS);
    
    const int w = chf.width;
    const int h = chf.height;
    
    rcScopedDelete<unsigned char> srcReg = (unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP);
    if (!srcReg)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'srcReg' (%d).", chf.spanCount);
        return false;
    }
    memset(srcReg,0xff,sizeof(unsigned char)*chf.spanCount);
    
    const int nsweeps = chf.width;
    rcScopedDelete<rcLayerSweepSpan> sweeps = (rcLayerSweepSpan*)rcAlloc(sizeof(rcLayerSweepSpan)*nsweeps, RC_ALLOC_TEMP);
    if (!sweeps)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'sweeps' (%d).", nsweeps);
        return false;
    }
    
    
    // Partition walkable area into monotone regions.
    int prevCount[256];
    unsigned char regId = 0;

    for (int y = borderSize; y < h-borderSize; ++y)
    {
        memset(prevCount,0,sizeof(int)*regId);
        unsigned char sweepId = 0;
        
        for (int x = borderSize; x < w-borderSize; ++x)
        {
            const rcCompactCell& c = chf.cells[x+y*w];
            
            for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
            {
                const rcCompactSpan& s = chf.spans[i];
                if (chf.areas[i] == RC_NULL_AREA) continue;

                unsigned char sid = 0xff;

                // -x
                if (rcGetCon(s, 0) != RC_NOT_CONNECTED)
                {
                    const int ax = x + rcGetDirOffsetX(0);
                    const int ay = y + rcGetDirOffsetY(0);
                    const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 0);
                    if (chf.areas[ai] != RC_NULL_AREA && srcReg[ai] != 0xff)
                        sid = srcReg[ai];
                }
                
                if (sid == 0xff)
                {
                    sid = sweepId++;
                    sweeps[sid].nei = 0xff;
                    sweeps[sid].ns = 0;
                }
                
                // -y
                if (rcGetCon(s,3) != RC_NOT_CONNECTED)
                {
                    const int ax = x + rcGetDirOffsetX(3);
                    const int ay = y + rcGetDirOffsetY(3);
                    const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 3);
                    const unsigned char nr = srcReg[ai];
                    if (nr != 0xff)
                    {
                        // Set neighbour when first valid neighbour is encoutered.
                        if (sweeps[sid].ns == 0)
                            sweeps[sid].nei = nr;
                        
                        if (sweeps[sid].nei == nr)
                        {
                            // Update existing neighbour
                            sweeps[sid].ns++;
                            prevCount[nr]++;
                        }
                        else
                        {
                            // This is hit if there is nore than one neighbour.
                            // Invalidate the neighbour.
                            sweeps[sid].nei = 0xff;
                        }
                    }
                }
                
                srcReg[i] = sid;
            }
        }
        
        // Create unique ID.
        for (int i = 0; i < sweepId; ++i)
        {
            // If the neighbour is set and there is only one continuous connection to it,
            // the sweep will be merged with the previous one, else new region is created.
            if (sweeps[i].nei != 0xff && prevCount[sweeps[i].nei] == (int)sweeps[i].ns)
            {
                sweeps[i].id = sweeps[i].nei;
            }
            else
            {
                if (regId == 255)
                {
                    ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Region ID overflow.");
                    return false;
                }
                sweeps[i].id = regId++;
            }
        }
        
        // Remap local sweep ids to region ids.
        for (int x = borderSize; x < w-borderSize; ++x)
        {
            const rcCompactCell& c = chf.cells[x+y*w];
            for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
            {
                if (srcReg[i] != 0xff)
                    srcReg[i] = sweeps[srcReg[i]].id;
            }
        }
    }

    // Allocate and init layer regions.
    const int nregs = (int)regId;
    rcScopedDelete<rcLayerRegion> regs = (rcLayerRegion*)rcAlloc(sizeof(rcLayerRegion)*nregs, RC_ALLOC_TEMP);
    if (!regs)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'regs' (%d).", nregs);
        return false;
    }
    memset(regs, 0, sizeof(rcLayerRegion)*nregs);
    for (int i = 0; i < nregs; ++i)
    {
        regs[i].layerId = 0xff;
        regs[i].ymin = 0xffff;
        regs[i].ymax = 0;
    }
    
    // Find region neighbours and overlapping regions.
    for (int y = 0; y < h; ++y)
    {
        for (int x = 0; x < w; ++x)
        {
            const rcCompactCell& c = chf.cells[x+y*w];
            
            unsigned char lregs[RC_MAX_LAYERS];
            int nlregs = 0;
            
            for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
            {
                const rcCompactSpan& s = chf.spans[i];
                const unsigned char ri = srcReg[i];
                if (ri == 0xff) continue;
                
                regs[ri].ymin = rcMin(regs[ri].ymin, s.y);
                regs[ri].ymax = rcMax(regs[ri].ymax, s.y);
                
                // Collect all region layers.
                if (nlregs < RC_MAX_LAYERS)
                    lregs[nlregs++] = ri;
                
                // Update neighbours
                for (int dir = 0; dir < 4; ++dir)
                {
                    if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
                    {
                        const int ax = x + rcGetDirOffsetX(dir);
                        const int ay = y + rcGetDirOffsetY(dir);
                        const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);
                        const unsigned char rai = srcReg[ai];
                        if (rai != 0xff && rai != ri)
                            addUnique(regs[ri].neis, regs[ri].nneis, rai);
                    }
                }
                
            }
            
            // Update overlapping regions.
            for (int i = 0; i < nlregs-1; ++i)
            {
                for (int j = i+1; j < nlregs; ++j)
                {
                    if (lregs[i] != lregs[j])
                    {
                        rcLayerRegion& ri = regs[lregs[i]];
                        rcLayerRegion& rj = regs[lregs[j]];
                        addUnique(ri.layers, ri.nlayers, lregs[j]);
                        addUnique(rj.layers, rj.nlayers, lregs[i]);
                    }
                }
            }
            
        }
    }
    
    // Create 2D layers from regions.
    unsigned char layerId = 0;
    
    static const int MAX_STACK = 64;
    unsigned char stack[MAX_STACK];
    int nstack = 0;
    
    for (int i = 0; i < nregs; ++i)
    {
        rcLayerRegion& root = regs[i];
        // Skip already visited.
        if (root.layerId != 0xff)
            continue;

        // Start search.
        root.layerId = layerId;
        root.base = 1;
        
        nstack = 0;
        stack[nstack++] = (unsigned char)i;
        
        while (nstack)
        {
            // Pop front
            rcLayerRegion& reg = regs[stack[0]];
            nstack--;
            for (int j = 0; j < nstack; ++j)
                stack[j] = stack[j+1];
            
            const int nneis = (int)reg.nneis;
            for (int j = 0; j < nneis; ++j)
            {
                const unsigned char nei = reg.neis[j];
                rcLayerRegion& regn = regs[nei];
                // Skip already visited.
                if (regn.layerId != 0xff)
                    continue;
                // Skip if the neighbour is overlapping root region.
                if (contains(root.layers, root.nlayers, nei))
                    continue;
                // Skip if the height range would become too large.
                const int ymin = rcMin(root.ymin, regn.ymin);
                const int ymax = rcMax(root.ymax, regn.ymax);
                if ((ymax - ymin) >= 255)
                     continue;

                if (nstack < MAX_STACK)
                {
                    // Deepen
                    stack[nstack++] = (unsigned char)nei;
                    
                    // Mark layer id
                    regn.layerId = layerId;
                    // Merge current layers to root.
                    for (int k = 0; k < regn.nlayers; ++k)
                        addUnique(root.layers, root.nlayers, regn.layers[k]);
                    root.ymin = rcMin(root.ymin, regn.ymin);
                    root.ymax = rcMax(root.ymax, regn.ymax);
                }
            }
        }
        
        layerId++;
    }
    
    // Merge non-overlapping regions that are close in height.
    const unsigned short mergeHeight = (unsigned short)walkableHeight * 4;
    
    for (int i = 0; i < nregs; ++i)
    {
        rcLayerRegion& ri = regs[i];
        if (!ri.base) continue;
        
        unsigned char newId = ri.layerId;
        
        for (;;)
        {
            unsigned char oldId = 0xff;
            
            for (int j = 0; j < nregs; ++j)
            {
                if (i == j) continue;
                rcLayerRegion& rj = regs[j];
                if (!rj.base) continue;
                
                // Skip if the regions are not close to each other.
                if (!overlapRange(ri.ymin,ri.ymax+mergeHeight, rj.ymin,rj.ymax+mergeHeight))
                    continue;
                // Skip if the height range would become too large.
                const int ymin = rcMin(ri.ymin, rj.ymin);
                const int ymax = rcMax(ri.ymax, rj.ymax);
                if ((ymax - ymin) >= 255)
                  continue;
                          
                // Make sure that there is no overlap when merging 'ri' and 'rj'.
                bool overlap = false;
                // Iterate over all regions which have the same layerId as 'rj'
                for (int k = 0; k < nregs; ++k)
                {
                    if (regs[k].layerId != rj.layerId)
                        continue;
                    // Check if region 'k' is overlapping region 'ri'
                    // Index to 'regs' is the same as region id.
                    if (contains(ri.layers,ri.nlayers, (unsigned char)k))
                    {
                        overlap = true;
                        break;
                    }
                }
                // Cannot merge of regions overlap.
                if (overlap)
                    continue;
                
                // Can merge i and j.
                oldId = rj.layerId;
                break;
            }
            
            // Could not find anything to merge with, stop.
            if (oldId == 0xff)
                break;
            
            // Merge
            for (int j = 0; j < nregs; ++j)
            {
                rcLayerRegion& rj = regs[j];
                if (rj.layerId == oldId)
                {
                    rj.base = 0;
                    // Remap layerIds.
                    rj.layerId = newId;
                    // Add overlaid layers from 'rj' to 'ri'.
                    for (int k = 0; k < rj.nlayers; ++k)
                        addUnique(ri.layers, ri.nlayers, rj.layers[k]);
                    // Update height bounds.
                    ri.ymin = rcMin(ri.ymin, rj.ymin);
                    ri.ymax = rcMax(ri.ymax, rj.ymax);
                }
            }
        }
    }
    
    // Compact layerIds
    unsigned char remap[256];
    memset(remap, 0, 256);

    // Find number of unique layers.
    layerId = 0;
    for (int i = 0; i < nregs; ++i)
        remap[regs[i].layerId] = 1;
    for (int i = 0; i < 256; ++i)
    {
        if (remap[i])
            remap[i] = layerId++;
        else
            remap[i] = 0xff;
    }
    // Remap ids.
    for (int i = 0; i < nregs; ++i)
        regs[i].layerId = remap[regs[i].layerId];
    
    // No layers, return empty.
    if (layerId == 0)
    {
        ctx->stopTimer(RC_TIMER_BUILD_LAYERS);
        return true;
    }
    
    // Create layers.
    rcAssert(lset.layers == 0);
    
    const int lw = w - borderSize*2;
    const int lh = h - borderSize*2;

    // Build contracted bbox for layers.
    float bmin[3], bmax[3];
    rcVcopy(bmin, chf.bmin);
    rcVcopy(bmax, chf.bmax);
    bmin[0] += borderSize*chf.cs;
    bmin[2] += borderSize*chf.cs;
    bmax[0] -= borderSize*chf.cs;
    bmax[2] -= borderSize*chf.cs;
    
    lset.nlayers = (int)layerId;
    
    lset.layers = (rcHeightfieldLayer*)rcAlloc(sizeof(rcHeightfieldLayer)*lset.nlayers, RC_ALLOC_PERM);
    if (!lset.layers)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'layers' (%d).", lset.nlayers);
        return false;
    }
    memset(lset.layers, 0, sizeof(rcHeightfieldLayer)*lset.nlayers);

    
    // Store layers.
    for (int i = 0; i < lset.nlayers; ++i)
    {
        unsigned char curId = (unsigned char)i;

        rcHeightfieldLayer* layer = &lset.layers[i];

        const int gridSize = sizeof(unsigned char)*lw*lh;

        layer->heights = (unsigned char*)rcAlloc(gridSize, RC_ALLOC_PERM);
        if (!layer->heights)
        {
            ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'heights' (%d).", gridSize);
            return false;
        }
        memset(layer->heights, 0xff, gridSize);

        layer->areas = (unsigned char*)rcAlloc(gridSize, RC_ALLOC_PERM);
        if (!layer->areas)
        {
            ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'areas' (%d).", gridSize);
            return false;
        }
        memset(layer->areas, 0, gridSize);

        layer->cons = (unsigned char*)rcAlloc(gridSize, RC_ALLOC_PERM);
        if (!layer->cons)
        {
            ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'cons' (%d).", gridSize);
            return false;
        }
        memset(layer->cons, 0, gridSize);
        
        // Find layer height bounds.
        int hmin = 0, hmax = 0;
        for (int j = 0; j < nregs; ++j)
        {
            if (regs[j].base && regs[j].layerId == curId)
            {
                hmin = (int)regs[j].ymin;
                hmax = (int)regs[j].ymax;
            }
        }

        layer->width = lw;
        layer->height = lh;
        layer->cs = chf.cs;
        layer->ch = chf.ch;
        
        // Adjust the bbox to fit the heightfield.
        rcVcopy(layer->bmin, bmin);
        rcVcopy(layer->bmax, bmax);
        layer->bmin[1] = bmin[1] + hmin*chf.ch;
        layer->bmax[1] = bmin[1] + hmax*chf.ch;
        layer->hmin = hmin;
        layer->hmax = hmax;

        // Update usable data region.
        layer->minx = layer->width;
        layer->maxx = 0;
        layer->miny = layer->height;
        layer->maxy = 0;
        
        // Copy height and area from compact heightfield. 
        for (int y = 0; y < lh; ++y)
        {
            for (int x = 0; x < lw; ++x)
            {
                const int cx = borderSize+x;
                const int cy = borderSize+y;
                const rcCompactCell& c = chf.cells[cx+cy*w];
                for (int j = (int)c.index, nj = (int)(c.index+c.count); j < nj; ++j)
                {
                    const rcCompactSpan& s = chf.spans[j];
                    // Skip unassigned regions.
                    if (srcReg[j] == 0xff)
                        continue;
                    // Skip of does nto belong to current layer.
                    unsigned char lid = regs[srcReg[j]].layerId;
                    if (lid != curId)
                        continue;
                    
                    // Update data bounds.
                    layer->minx = rcMin(layer->minx, x);
                    layer->maxx = rcMax(layer->maxx, x);
                    layer->miny = rcMin(layer->miny, y);
                    layer->maxy = rcMax(layer->maxy, y);
                    
                    // Store height and area type.
                    const int idx = x+y*lw;
                    layer->heights[idx] = (unsigned char)(s.y - hmin);
                    layer->areas[idx] = chf.areas[j];
                    
                    // Check connection.
                    unsigned char portal = 0;
                    unsigned char con = 0;
                    for (int dir = 0; dir < 4; ++dir)
                    {
                        if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
                        {
                            const int ax = cx + rcGetDirOffsetX(dir);
                            const int ay = cy + rcGetDirOffsetY(dir);
                            const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);
                            unsigned char alid = srcReg[ai] != 0xff ? regs[srcReg[ai]].layerId : 0xff;
                            // Portal mask
                            if (chf.areas[ai] != RC_NULL_AREA && lid != alid)
                            {
                                portal |= (unsigned char)(1<<dir);
                                // Update height so that it matches on both sides of the portal.
                                const rcCompactSpan& as = chf.spans[ai];
                                if (as.y > hmin)
                                    layer->heights[idx] = rcMax(layer->heights[idx], (unsigned char)(as.y - hmin));
                            }
                            // Valid connection mask
                            if (chf.areas[ai] != RC_NULL_AREA && lid == alid)
                            {
                                const int nx = ax - borderSize;
                                const int ny = ay - borderSize;
                                if (nx >= 0 && ny >= 0 && nx < lw && ny < lh)
                                    con |= (unsigned char)(1<<dir);
                            }
                        }
                    }
                    
                    layer->cons[idx] = (portal << 4) | con;
                }
            }
        }
        
        if (layer->minx > layer->maxx)
            layer->minx = layer->maxx = 0;
        if (layer->miny > layer->maxy)
            layer->miny = layer->maxy = 0;
    }
    
    ctx->stopTimer(RC_TIMER_BUILD_LAYERS);
    
    return true;
}

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]	ctx	The build context to use during the operation.
[in,out]	chf	A populated compact heightfield.
[in]	borderSize	The size of the non-navigable border around the heightfield. [Limit: >=0] [Units: vx]
[in]	minRegionArea	The minimum number of cells allowed to form isolated island areas. [Limit: >=0] [Units: vx].

Returns

True if the operation completed successfully.

{
    rcAssert(ctx);
    
    ctx->startTimer(RC_TIMER_BUILD_REGIONS);
    
    const int w = chf.width;
    const int h = chf.height;
    unsigned short id = 1;
    
    rcScopedDelete<unsigned short> srcReg = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP);
    if (!srcReg)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'src' (%d).", chf.spanCount);
        return false;
    }
    memset(srcReg,0,sizeof(unsigned short)*chf.spanCount);
    
    const int nsweeps = rcMax(chf.width,chf.height);
    rcScopedDelete<rcSweepSpan> sweeps = (rcSweepSpan*)rcAlloc(sizeof(rcSweepSpan)*nsweeps, RC_ALLOC_TEMP);
    if (!sweeps)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'sweeps' (%d).", nsweeps);
        return false;
    }
    
    
    // Mark border regions.
    if (borderSize > 0)
    {
        // Make sure border will not overflow.
        const int bw = rcMin(w, borderSize);
        const int bh = rcMin(h, borderSize);
        // Paint regions
        paintRectRegion(0, bw, 0, h, id|RC_BORDER_REG, chf, srcReg); id++;
        paintRectRegion(w-bw, w, 0, h, id|RC_BORDER_REG, chf, srcReg); id++;
        paintRectRegion(0, w, 0, bh, id|RC_BORDER_REG, chf, srcReg); id++;
        paintRectRegion(0, w, h-bh, h, id|RC_BORDER_REG, chf, srcReg); id++;
        
        chf.borderSize = borderSize;
    }
    
    rcIntArray prev(256);
    
    // Sweep one line at a time.
    for (int y = borderSize; y < h-borderSize; ++y)
    {
        // Collect spans from this row.
        prev.resize(id+1);
        memset(&prev[0],0,sizeof(int)*id);
        unsigned short rid = 1;
        
        for (int x = borderSize; x < w-borderSize; ++x)
        {
            const rcCompactCell& c = chf.cells[x+y*w];
            
            for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
            {
                const rcCompactSpan& s = chf.spans[i];
                if (chf.areas[i] == RC_NULL_AREA) continue;
                
                // -x
                unsigned short previd = 0;
                if (rcGetCon(s, 0) != RC_NOT_CONNECTED)
                {
                    const int ax = x + rcGetDirOffsetX(0);
                    const int ay = y + rcGetDirOffsetY(0);
                    const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 0);
                    if ((srcReg[ai] & RC_BORDER_REG) == 0 && chf.areas[i] == chf.areas[ai])
                        previd = srcReg[ai];
                }
                
                if (!previd)
                {
                    previd = rid++;
                    sweeps[previd].rid = previd;
                    sweeps[previd].ns = 0;
                    sweeps[previd].nei = 0;
                }
                
                // -y
                if (rcGetCon(s,3) != RC_NOT_CONNECTED)
                {
                    const int ax = x + rcGetDirOffsetX(3);
                    const int ay = y + rcGetDirOffsetY(3);
                    const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 3);
                    if (srcReg[ai] && (srcReg[ai] & RC_BORDER_REG) == 0 && chf.areas[i] == chf.areas[ai])
                    {
                        unsigned short nr = srcReg[ai];
                        if (!sweeps[previd].nei || sweeps[previd].nei == nr)
                        {
                            sweeps[previd].nei = nr;
                            sweeps[previd].ns++;
                            prev[nr]++;
                        }
                        else
                        {
                            sweeps[previd].nei = RC_NULL_NEI;
                        }
                    }
                }
                
                srcReg[i] = previd;
            }
        }
        
        // Create unique ID.
        for (int i = 1; i < rid; ++i)
        {
            if (sweeps[i].nei != RC_NULL_NEI && sweeps[i].nei != 0 &&
                prev[sweeps[i].nei] == (int)sweeps[i].ns)
            {
                sweeps[i].id = sweeps[i].nei;
            }
            else
            {
                sweeps[i].id = id++;
            }
        }
        
        // Remap IDs
        for (int x = borderSize; x < w-borderSize; ++x)
        {
            const rcCompactCell& c = chf.cells[x+y*w];
            
            for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
            {
                if (srcReg[i] > 0 && srcReg[i] < rid)
                    srcReg[i] = sweeps[srcReg[i]].id;
            }
        }
    }
    
    
    ctx->startTimer(RC_TIMER_BUILD_REGIONS_FILTER);
    
    // Merge monotone regions to layers and remove small regions.
    rcIntArray overlaps;
    chf.maxRegions = id;
    if (!mergeAndFilterLayerRegions(ctx, minRegionArea, chf.maxRegions, chf, srcReg, overlaps))
        return false;
    
    ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FILTER);
    
    
    // Store the result out.
    for (int i = 0; i < chf.spanCount; ++i)
        chf.spans[i].reg = srcReg[i];
    
    ctx->stopTimer(RC_TIMER_BUILD_REGIONS);
    
    return true;
}

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]	ctx	The build context to use during the operation.
[in]	cset	A fully built contour set.
[in]	nvp	The maximum number of vertices allowed for polygons generated during the contour to polygon conversion process. [Limit: >= 3]
[out]	mesh	The 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

{
    rcAssert(ctx);
    
    ctx->startTimer(RC_TIMER_BUILD_POLYMESH);

    rcVcopy(mesh.bmin, cset.bmin);
    rcVcopy(mesh.bmax, cset.bmax);
    mesh.cs = cset.cs;
    mesh.ch = cset.ch;
    mesh.borderSize = cset.borderSize;
    
    int maxVertices = 0;
    int maxTris = 0;
    int maxVertsPerCont = 0;
    for (int i = 0; i < cset.nconts; ++i)
    {
        // Skip null contours.
        if (cset.conts[i].nverts < 3) continue;
        maxVertices += cset.conts[i].nverts;
        maxTris += cset.conts[i].nverts - 2;
        maxVertsPerCont = rcMax(maxVertsPerCont, cset.conts[i].nverts);
    }
    
    if (maxVertices >= 0xfffe)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Too many vertices %d.", maxVertices);
        return false;
    }
        
    rcScopedDelete<unsigned char> vflags = (unsigned char*)rcAlloc(sizeof(unsigned char)*maxVertices, RC_ALLOC_TEMP);
    if (!vflags)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'vflags' (%d).", maxVertices);
        return false;
    }
    memset(vflags, 0, maxVertices);
    
    mesh.verts = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxVertices*3, RC_ALLOC_PERM);
    if (!mesh.verts)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.verts' (%d).", maxVertices);
        return false;
    }
    mesh.polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxTris*nvp*2, RC_ALLOC_PERM);
    if (!mesh.polys)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.polys' (%d).", maxTris*nvp*2);
        return false;
    }
    mesh.regs = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxTris, RC_ALLOC_PERM);
    if (!mesh.regs)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.regs' (%d).", maxTris);
        return false;
    }
    mesh.areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*maxTris, RC_ALLOC_PERM);
    if (!mesh.areas)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.areas' (%d).", maxTris);
        return false;
    }
    
    mesh.nverts = 0;
    mesh.npolys = 0;
    mesh.nvp = nvp;
    mesh.maxpolys = maxTris;
    
    memset(mesh.verts, 0, sizeof(unsigned short)*maxVertices*3);
    memset(mesh.polys, 0xff, sizeof(unsigned short)*maxTris*nvp*2);
    memset(mesh.regs, 0, sizeof(unsigned short)*maxTris);
    memset(mesh.areas, 0, sizeof(unsigned char)*maxTris);
    
    rcScopedDelete<int> nextVert = (int*)rcAlloc(sizeof(int)*maxVertices, RC_ALLOC_TEMP);
    if (!nextVert)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'nextVert' (%d).", maxVertices);
        return false;
    }
    memset(nextVert, 0, sizeof(int)*maxVertices);
    
    rcScopedDelete<int> firstVert = (int*)rcAlloc(sizeof(int)*VERTEX_BUCKET_COUNT, RC_ALLOC_TEMP);
    if (!firstVert)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'firstVert' (%d).", VERTEX_BUCKET_COUNT);
        return false;
    }
    for (int i = 0; i < VERTEX_BUCKET_COUNT; ++i)
        firstVert[i] = -1;
    
    rcScopedDelete<int> indices = (int*)rcAlloc(sizeof(int)*maxVertsPerCont, RC_ALLOC_TEMP);
    if (!indices)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'indices' (%d).", maxVertsPerCont);
        return false;
    }
    rcScopedDelete<int> tris = (int*)rcAlloc(sizeof(int)*maxVertsPerCont*3, RC_ALLOC_TEMP);
    if (!tris)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'tris' (%d).", maxVertsPerCont*3);
        return false;
    }
    rcScopedDelete<unsigned short> polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*(maxVertsPerCont+1)*nvp, RC_ALLOC_TEMP);
    if (!polys)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'polys' (%d).", maxVertsPerCont*nvp);
        return false;
    }
    unsigned short* tmpPoly = &polys[maxVertsPerCont*nvp];

    for (int i = 0; i < cset.nconts; ++i)
    {
        rcContour& cont = cset.conts[i];
        
        // Skip null contours.
        if (cont.nverts < 3)
            continue;
        
        // Triangulate contour
        for (int j = 0; j < cont.nverts; ++j)
            indices[j] = j;
            
        int ntris = triangulate(cont.nverts, cont.verts, &indices[0], &tris[0]);
        if (ntris <= 0)
        {
            // Bad triangulation, should not happen.
/*          printf("\tconst float bmin[3] = {%ff,%ff,%ff};\n", cset.bmin[0], cset.bmin[1], cset.bmin[2]);
            printf("\tconst float cs = %ff;\n", cset.cs);
            printf("\tconst float ch = %ff;\n", cset.ch);
            printf("\tconst int verts[] = {\n");
            for (int k = 0; k < cont.nverts; ++k)
            {
                const int* v = &cont.verts[k*4];
                printf("\t\t%d,%d,%d,%d,\n", v[0], v[1], v[2], v[3]);
            }
            printf("\t};\n\tconst int nverts = sizeof(verts)/(sizeof(int)*4);\n");*/
            ctx->log(RC_LOG_WARNING, "rcBuildPolyMesh: Bad triangulation Contour %d.", i);
            ntris = -ntris;
        }
                
        // Add and merge vertices.
        for (int j = 0; j < cont.nverts; ++j)
        {
            const int* v = &cont.verts[j*4];
            indices[j] = addVertex((unsigned short)v[0], (unsigned short)v[1], (unsigned short)v[2],
                                   mesh.verts, firstVert, nextVert, mesh.nverts);
            if (v[3] & RC_BORDER_VERTEX)
            {
                // This vertex should be removed.
                vflags[indices[j]] = 1;
            }
        }

        // Build initial polygons.
        int npolys = 0;
        memset(polys, 0xff, maxVertsPerCont*nvp*sizeof(unsigned short));
        for (int j = 0; j < ntris; ++j)
        {
            int* t = &tris[j*3];
            if (t[0] != t[1] && t[0] != t[2] && t[1] != t[2])
            {
                polys[npolys*nvp+0] = (unsigned short)indices[t[0]];
                polys[npolys*nvp+1] = (unsigned short)indices[t[1]];
                polys[npolys*nvp+2] = (unsigned short)indices[t[2]];
                npolys++;
            }
        }
        if (!npolys)
            continue;
        
        // Merge polygons.
        if (nvp > 3)
        {
            for(;;)
            {
                // Find best polygons to merge.
                int bestMergeVal = 0;
                int bestPa = 0, bestPb = 0, bestEa = 0, bestEb = 0;
                
                for (int j = 0; j < npolys-1; ++j)
                {
                    unsigned short* pj = &polys[j*nvp];
                    for (int k = j+1; k < npolys; ++k)
                    {
                        unsigned short* pk = &polys[k*nvp];
                        int ea, eb;
                        int v = getPolyMergeValue(pj, pk, mesh.verts, ea, eb, nvp);
                        if (v > bestMergeVal)
                        {
                            bestMergeVal = v;
                            bestPa = j;
                            bestPb = k;
                            bestEa = ea;
                            bestEb = eb;
                        }
                    }
                }
                
                if (bestMergeVal > 0)
                {
                    // Found best, merge.
                    unsigned short* pa = &polys[bestPa*nvp];
                    unsigned short* pb = &polys[bestPb*nvp];
                    mergePolys(pa, pb, bestEa, bestEb, tmpPoly, nvp);
                    unsigned short* lastPoly = &polys[(npolys-1)*nvp];
                    if (pb != lastPoly)
                        memcpy(pb, lastPoly, sizeof(unsigned short)*nvp);
                    npolys--;
                }
                else
                {
                    // Could not merge any polygons, stop.
                    break;
                }
            }
        }
        
        // Store polygons.
        for (int j = 0; j < npolys; ++j)
        {
            unsigned short* p = &mesh.polys[mesh.npolys*nvp*2];
            unsigned short* q = &polys[j*nvp];
            for (int k = 0; k < nvp; ++k)
                p[k] = q[k];
            mesh.regs[mesh.npolys] = cont.reg;
            mesh.areas[mesh.npolys] = cont.area;
            mesh.npolys++;
            if (mesh.npolys > maxTris)
            {
                ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Too many polygons %d (max:%d).", mesh.npolys, maxTris);
                return false;
            }
        }
    }
    
    
    // Remove edge vertices.
    for (int i = 0; i < mesh.nverts; ++i)
    {
        if (vflags[i])
        {
            if (!canRemoveVertex(ctx, mesh, (unsigned short)i))
                continue;
            if (!removeVertex(ctx, mesh, (unsigned short)i, maxTris))
            {
                // Failed to remove vertex
                ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Failed to remove edge vertex %d.", i);
                return false;
            }
            // Remove vertex
            // Note: mesh.nverts is already decremented inside removeVertex()!
            // Fixup vertex flags
            for (int j = i; j < mesh.nverts; ++j)
                vflags[j] = vflags[j+1];
            --i;
        }
    }
    
    // Calculate adjacency.
    if (!buildMeshAdjacency(mesh.polys, mesh.npolys, mesh.nverts, nvp))
    {
        ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Adjacency failed.");
        return false;
    }
    
    // Find portal edges
    if (mesh.borderSize > 0)
    {
        const int w = cset.width;
        const int h = cset.height;
        for (int i = 0; i < mesh.npolys; ++i)
        {
            unsigned short* p = &mesh.polys[i*2*nvp];
            for (int j = 0; j < nvp; ++j)
            {
                if (p[j] == RC_MESH_NULL_IDX) break;
                // Skip connected edges.
                if (p[nvp+j] != RC_MESH_NULL_IDX)
                    continue;
                int nj = j+1;
                if (nj >= nvp || p[nj] == RC_MESH_NULL_IDX) nj = 0;
                const unsigned short* va = &mesh.verts[p[j]*3];
                const unsigned short* vb = &mesh.verts[p[nj]*3];

                if ((int)va[0] == 0 && (int)vb[0] == 0)
                    p[nvp+j] = 0x8000 | 0;
                else if ((int)va[2] == h && (int)vb[2] == h)
                    p[nvp+j] = 0x8000 | 1;
                else if ((int)va[0] == w && (int)vb[0] == w)
                    p[nvp+j] = 0x8000 | 2;
                else if ((int)va[2] == 0 && (int)vb[2] == 0)
                    p[nvp+j] = 0x8000 | 3;
            }
        }
    }

    // Just allocate the mesh flags array. The user is resposible to fill it.
    mesh.flags = (unsigned short*)rcAlloc(sizeof(unsigned short)*mesh.npolys, RC_ALLOC_PERM);
    if (!mesh.flags)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.flags' (%d).", mesh.npolys);
        return false;
    }
    memset(mesh.flags, 0, sizeof(unsigned short) * mesh.npolys);
    
    if (mesh.nverts > 0xffff)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: The resulting mesh has too many vertices %d (max %d). Data can be corrupted.", mesh.nverts, 0xffff);
    }
    if (mesh.npolys > 0xffff)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: The resulting mesh has too many polygons %d (max %d). Data can be corrupted.", mesh.npolys, 0xffff);
    }
    
    ctx->stopTimer(RC_TIMER_BUILD_POLYMESH);
    
    return true;
}

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]	ctx	The build context to use during the operation.
[in]	mesh	A fully built polygon mesh.
[in]	chf	The compact heightfield used to build the polygon mesh.
[in]	sampleDist	Sets the distance to use when samping the heightfield. [Limit: >=0] [Units: wu]
[in]	sampleMaxError	The maximum distance the detail mesh surface should deviate from heightfield data. [Limit: >=0] [Units: wu]
[out]	dmesh	The 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

{
    rcAssert(ctx);
    
    ctx->startTimer(RC_TIMER_BUILD_POLYMESHDETAIL);
    
    if (mesh.nverts == 0 || mesh.npolys == 0)
        return true;
    
    const int nvp = mesh.nvp;
    const float cs = mesh.cs;
    const float ch = mesh.ch;
    const float* orig = mesh.bmin;
    const int borderSize = mesh.borderSize;
    
    rcIntArray edges(64);
    rcIntArray tris(512);
    rcIntArray stack(512);
    rcIntArray samples(512);
    float verts[256*3];
    rcHeightPatch hp;
    int nPolyVerts = 0;
    int maxhw = 0, maxhh = 0;
    
    rcScopedDelete<int> bounds = (int*)rcAlloc(sizeof(int)*mesh.npolys*4, RC_ALLOC_TEMP);
    if (!bounds)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'bounds' (%d).", mesh.npolys*4);
        return false;
    }
    rcScopedDelete<float> poly = (float*)rcAlloc(sizeof(float)*nvp*3, RC_ALLOC_TEMP);
    if (!poly)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'poly' (%d).", nvp*3);
        return false;
    }
    
    // Find max size for a polygon area.
    for (int i = 0; i < mesh.npolys; ++i)
    {
        const unsigned short* p = &mesh.polys[i*nvp*2];
        int& xmin = bounds[i*4+0];
        int& xmax = bounds[i*4+1];
        int& ymin = bounds[i*4+2];
        int& ymax = bounds[i*4+3];
        xmin = chf.width;
        xmax = 0;
        ymin = chf.height;
        ymax = 0;
        for (int j = 0; j < nvp; ++j)
        {
            if(p[j] == RC_MESH_NULL_IDX) break;
            const unsigned short* v = &mesh.verts[p[j]*3];
            xmin = rcMin(xmin, (int)v[0]);
            xmax = rcMax(xmax, (int)v[0]);
            ymin = rcMin(ymin, (int)v[2]);
            ymax = rcMax(ymax, (int)v[2]);
            nPolyVerts++;
        }
        xmin = rcMax(0,xmin-1);
        xmax = rcMin(chf.width,xmax+1);
        ymin = rcMax(0,ymin-1);
        ymax = rcMin(chf.height,ymax+1);
        if (xmin >= xmax || ymin >= ymax) continue;
        maxhw = rcMax(maxhw, xmax-xmin);
        maxhh = rcMax(maxhh, ymax-ymin);
    }
    
    hp.data = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxhw*maxhh, RC_ALLOC_TEMP);
    if (!hp.data)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'hp.data' (%d).", maxhw*maxhh);
        return false;
    }
    
    dmesh.nmeshes = mesh.npolys;
    dmesh.nverts = 0;
    dmesh.ntris = 0;
    dmesh.meshes = (unsigned int*)rcAlloc(sizeof(unsigned int)*dmesh.nmeshes*4, RC_ALLOC_PERM);
    if (!dmesh.meshes)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.meshes' (%d).", dmesh.nmeshes*4);
        return false;
    }
    
    int vcap = nPolyVerts+nPolyVerts/2;
    int tcap = vcap*2;
    
    dmesh.nverts = 0;
    dmesh.verts = (float*)rcAlloc(sizeof(float)*vcap*3, RC_ALLOC_PERM);
    if (!dmesh.verts)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.verts' (%d).", vcap*3);
        return false;
    }
    dmesh.ntris = 0;
    dmesh.tris = (unsigned char*)rcAlloc(sizeof(unsigned char)*tcap*4, RC_ALLOC_PERM);
    if (!dmesh.tris)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.tris' (%d).", tcap*4);
        return false;
    }
    
    for (int i = 0; i < mesh.npolys; ++i)
    {
        const unsigned short* p = &mesh.polys[i*nvp*2];
        
        // Store polygon vertices for processing.
        int npoly = 0;
        for (int j = 0; j < nvp; ++j)
        {
            if(p[j] == RC_MESH_NULL_IDX) break;
            const unsigned short* v = &mesh.verts[p[j]*3];
            poly[j*3+0] = v[0]*cs;
            poly[j*3+1] = v[1]*ch;
            poly[j*3+2] = v[2]*cs;
            npoly++;
        }
        
        // Get the height data from the area of the polygon.
        hp.xmin = bounds[i*4+0];
        hp.ymin = bounds[i*4+2];
        hp.width = bounds[i*4+1]-bounds[i*4+0];
        hp.height = bounds[i*4+3]-bounds[i*4+2];
        getHeightData(chf, p, npoly, mesh.verts, borderSize, hp, stack, mesh.regs[i]);
        
        // Build detail mesh.
        int nverts = 0;
        if (!buildPolyDetail(ctx, poly, npoly,
                             sampleDist, sampleMaxError,
                             chf, hp, verts, nverts, tris,
                             edges, samples))
        {
            return false;
        }
        
        // Move detail verts to world space.
        for (int j = 0; j < nverts; ++j)
        {
            verts[j*3+0] += orig[0];
            verts[j*3+1] += orig[1] + chf.ch; // Is this offset necessary?
            verts[j*3+2] += orig[2];
        }
        // Offset poly too, will be used to flag checking.
        for (int j = 0; j < npoly; ++j)
        {
            poly[j*3+0] += orig[0];
            poly[j*3+1] += orig[1];
            poly[j*3+2] += orig[2];
        }
        
        // Store detail submesh.
        const int ntris = tris.size()/4;
        
        dmesh.meshes[i*4+0] = (unsigned int)dmesh.nverts;
        dmesh.meshes[i*4+1] = (unsigned int)nverts;
        dmesh.meshes[i*4+2] = (unsigned int)dmesh.ntris;
        dmesh.meshes[i*4+3] = (unsigned int)ntris;
        
        // Store vertices, allocate more memory if necessary.
        if (dmesh.nverts+nverts > vcap)
        {
            while (dmesh.nverts+nverts > vcap)
                vcap += 256;
            
            float* newv = (float*)rcAlloc(sizeof(float)*vcap*3, RC_ALLOC_PERM);
            if (!newv)
            {
                ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'newv' (%d).", vcap*3);
                return false;
            }
            if (dmesh.nverts)
                memcpy(newv, dmesh.verts, sizeof(float)*3*dmesh.nverts);
            rcFree(dmesh.verts);
            dmesh.verts = newv;
        }
        for (int j = 0; j < nverts; ++j)
        {
            dmesh.verts[dmesh.nverts*3+0] = verts[j*3+0];
            dmesh.verts[dmesh.nverts*3+1] = verts[j*3+1];
            dmesh.verts[dmesh.nverts*3+2] = verts[j*3+2];
            dmesh.nverts++;
        }
        
        // Store triangles, allocate more memory if necessary.
        if (dmesh.ntris+ntris > tcap)
        {
            while (dmesh.ntris+ntris > tcap)
                tcap += 256;
            unsigned char* newt = (unsigned char*)rcAlloc(sizeof(unsigned char)*tcap*4, RC_ALLOC_PERM);
            if (!newt)
            {
                ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'newt' (%d).", tcap*4);
                return false;
            }
            if (dmesh.ntris)
                memcpy(newt, dmesh.tris, sizeof(unsigned char)*4*dmesh.ntris);
            rcFree(dmesh.tris);
            dmesh.tris = newt;
        }
        for (int j = 0; j < ntris; ++j)
        {
            const int* t = &tris[j*4];
            dmesh.tris[dmesh.ntris*4+0] = (unsigned char)t[0];
            dmesh.tris[dmesh.ntris*4+1] = (unsigned char)t[1];
            dmesh.tris[dmesh.ntris*4+2] = (unsigned char)t[2];
            dmesh.tris[dmesh.ntris*4+3] = getTriFlags(&verts[t[0]*3], &verts[t[1]*3], &verts[t[2]*3], poly, npoly);
            dmesh.ntris++;
        }
    }
    
    ctx->stopTimer(RC_TIMER_BUILD_POLYMESHDETAIL);
    
    return true;
}

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]	ctx	The build context to use during the operation.
[in,out]	chf	A populated compact heightfield.
[in]	borderSize	The size of the non-navigable border around the heightfield. [Limit: >=0] [Units: vx]
[in]	minRegionArea	The minimum number of cells allowed to form isolated island areas. [Limit: >=0] [Units: vx].
[in]	mergeRegionArea	Any 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

{
    rcAssert(ctx);
    
    ctx->startTimer(RC_TIMER_BUILD_REGIONS);
    
    const int w = chf.width;
    const int h = chf.height;
    
    rcScopedDelete<unsigned short> buf = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount*4, RC_ALLOC_TEMP);
    if (!buf)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildRegions: Out of memory 'tmp' (%d).", chf.spanCount*4);
        return false;
    }
    
    ctx->startTimer(RC_TIMER_BUILD_REGIONS_WATERSHED);

    const int LOG_NB_STACKS = 3;
    const int NB_STACKS = 1 << LOG_NB_STACKS;
    rcIntArray lvlStacks[NB_STACKS];
    for (int i=0; i<NB_STACKS; ++i)
        lvlStacks[i].resize(1024);

    rcIntArray stack(1024);
    rcIntArray visited(1024);
    
    unsigned short* srcReg = buf;
    unsigned short* srcDist = buf+chf.spanCount;
    unsigned short* dstReg = buf+chf.spanCount*2;
    unsigned short* dstDist = buf+chf.spanCount*3;
    
    memset(srcReg, 0, sizeof(unsigned short)*chf.spanCount);
    memset(srcDist, 0, sizeof(unsigned short)*chf.spanCount);
    
    unsigned short regionId = 1;
    unsigned short level = (chf.maxDistance+1) & ~1;

    // TODO: Figure better formula, expandIters defines how much the 
    // watershed "overflows" and simplifies the regions. Tying it to
    // agent radius was usually good indication how greedy it could be.
//  const int expandIters = 4 + walkableRadius * 2;
    const int expandIters = 8;

    if (borderSize > 0)
    {
        // Make sure border will not overflow.
        const int bw = rcMin(w, borderSize);
        const int bh = rcMin(h, borderSize);
        // Paint regions
        paintRectRegion(0, bw, 0, h, regionId|RC_BORDER_REG, chf, srcReg); regionId++;
        paintRectRegion(w-bw, w, 0, h, regionId|RC_BORDER_REG, chf, srcReg); regionId++;
        paintRectRegion(0, w, 0, bh, regionId|RC_BORDER_REG, chf, srcReg); regionId++;
        paintRectRegion(0, w, h-bh, h, regionId|RC_BORDER_REG, chf, srcReg); regionId++;

        chf.borderSize = borderSize;
    }
    
    int sId = -1;
    while (level > 0)
    {
        level = level >= 2 ? level-2 : 0;
        sId = (sId+1) & (NB_STACKS-1);

//      ctx->startTimer(RC_TIMER_DIVIDE_TO_LEVELS);

        if (sId == 0)
            sortCellsByLevel(level, chf, srcReg, NB_STACKS, lvlStacks, 1);
        else 
            appendStacks(lvlStacks[sId-1], lvlStacks[sId], srcReg); // copy left overs from last level

//      ctx->stopTimer(RC_TIMER_DIVIDE_TO_LEVELS);

        ctx->startTimer(RC_TIMER_BUILD_REGIONS_EXPAND);
        
        // Expand current regions until no empty connected cells found.
        if (expandRegions(expandIters, level, chf, srcReg, srcDist, dstReg, dstDist, lvlStacks[sId], false) != srcReg)
        {
            rcSwap(srcReg, dstReg);
            rcSwap(srcDist, dstDist);
        }
        
        ctx->stopTimer(RC_TIMER_BUILD_REGIONS_EXPAND);
        
        ctx->startTimer(RC_TIMER_BUILD_REGIONS_FLOOD);
        
        // Mark new regions with IDs.
        for (int j=0; j<lvlStacks[sId].size(); j+=3)
        {
            int x = lvlStacks[sId][j];
            int y = lvlStacks[sId][j+1];
            int i = lvlStacks[sId][j+2];
            if (i >= 0 && srcReg[i] == 0)
            {
                if (floodRegion(x, y, i, level, regionId, chf, srcReg, srcDist, stack))
                    regionId++;
            }
        }
        
        ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FLOOD);
    }
    
    // Expand current regions until no empty connected cells found.
    if (expandRegions(expandIters*8, 0, chf, srcReg, srcDist, dstReg, dstDist, stack, true) != srcReg)
    {
        rcSwap(srcReg, dstReg);
        rcSwap(srcDist, dstDist);
    }
    
    ctx->stopTimer(RC_TIMER_BUILD_REGIONS_WATERSHED);
    
    ctx->startTimer(RC_TIMER_BUILD_REGIONS_FILTER);
    
    // Merge regions and filter out smalle regions.
    rcIntArray overlaps;
    chf.maxRegions = regionId;
    if (!mergeAndFilterRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg, overlaps))
        return false;

    // If overlapping regions were found during merging, split those regions.
    if (overlaps.size() > 0)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildRegions: %d overlapping regions.", overlaps.size());
    }

    ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FILTER);
        
    // Write the result out.
    for (int i = 0; i < chf.spanCount; ++i)
        chf.spans[i].reg = srcReg[i];
    
    ctx->stopTimer(RC_TIMER_BUILD_REGIONS);
    
    return true;
}

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]	ctx	The build context to use during the operation.
[in,out]	chf	A populated compact heightfield.
[in]	borderSize	The size of the non-navigable border around the heightfield. [Limit: >=0] [Units: vx]
[in]	minRegionArea	The minimum number of cells allowed to form isolated island areas. [Limit: >=0] [Units: vx].
[in]	mergeRegionArea	Any 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

{
    rcAssert(ctx);
    
    ctx->startTimer(RC_TIMER_BUILD_REGIONS);
    
    const int w = chf.width;
    const int h = chf.height;
    unsigned short id = 1;
    
    rcScopedDelete<unsigned short> srcReg = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP);
    if (!srcReg)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'src' (%d).", chf.spanCount);
        return false;
    }
    memset(srcReg,0,sizeof(unsigned short)*chf.spanCount);

    const int nsweeps = rcMax(chf.width,chf.height);
    rcScopedDelete<rcSweepSpan> sweeps = (rcSweepSpan*)rcAlloc(sizeof(rcSweepSpan)*nsweeps, RC_ALLOC_TEMP);
    if (!sweeps)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'sweeps' (%d).", nsweeps);
        return false;
    }
    
    
    // Mark border regions.
    if (borderSize > 0)
    {
        // Make sure border will not overflow.
        const int bw = rcMin(w, borderSize);
        const int bh = rcMin(h, borderSize);
        // Paint regions
        paintRectRegion(0, bw, 0, h, id|RC_BORDER_REG, chf, srcReg); id++;
        paintRectRegion(w-bw, w, 0, h, id|RC_BORDER_REG, chf, srcReg); id++;
        paintRectRegion(0, w, 0, bh, id|RC_BORDER_REG, chf, srcReg); id++;
        paintRectRegion(0, w, h-bh, h, id|RC_BORDER_REG, chf, srcReg); id++;
        
        chf.borderSize = borderSize;
    }
    
    rcIntArray prev(256);

    // Sweep one line at a time.
    for (int y = borderSize; y < h-borderSize; ++y)
    {
        // Collect spans from this row.
        prev.resize(id+1);
        memset(&prev[0],0,sizeof(int)*id);
        unsigned short rid = 1;
        
        for (int x = borderSize; x < w-borderSize; ++x)
        {
            const rcCompactCell& c = chf.cells[x+y*w];
            
            for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
            {
                const rcCompactSpan& s = chf.spans[i];
                if (chf.areas[i] == RC_NULL_AREA) continue;
                
                // -x
                unsigned short previd = 0;
                if (rcGetCon(s, 0) != RC_NOT_CONNECTED)
                {
                    const int ax = x + rcGetDirOffsetX(0);
                    const int ay = y + rcGetDirOffsetY(0);
                    const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 0);
                    if ((srcReg[ai] & RC_BORDER_REG) == 0 && chf.areas[i] == chf.areas[ai])
                        previd = srcReg[ai];
                }
                
                if (!previd)
                {
                    previd = rid++;
                    sweeps[previd].rid = previd;
                    sweeps[previd].ns = 0;
                    sweeps[previd].nei = 0;
                }

                // -y
                if (rcGetCon(s,3) != RC_NOT_CONNECTED)
                {
                    const int ax = x + rcGetDirOffsetX(3);
                    const int ay = y + rcGetDirOffsetY(3);
                    const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 3);
                    if (srcReg[ai] && (srcReg[ai] & RC_BORDER_REG) == 0 && chf.areas[i] == chf.areas[ai])
                    {
                        unsigned short nr = srcReg[ai];
                        if (!sweeps[previd].nei || sweeps[previd].nei == nr)
                        {
                            sweeps[previd].nei = nr;
                            sweeps[previd].ns++;
                            prev[nr]++;
                        }
                        else
                        {
                            sweeps[previd].nei = RC_NULL_NEI;
                        }
                    }
                }

                srcReg[i] = previd;
            }
        }
        
        // Create unique ID.
        for (int i = 1; i < rid; ++i)
        {
            if (sweeps[i].nei != RC_NULL_NEI && sweeps[i].nei != 0 &&
                prev[sweeps[i].nei] == (int)sweeps[i].ns)
            {
                sweeps[i].id = sweeps[i].nei;
            }
            else
            {
                sweeps[i].id = id++;
            }
        }
        
        // Remap IDs
        for (int x = borderSize; x < w-borderSize; ++x)
        {
            const rcCompactCell& c = chf.cells[x+y*w];
            
            for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
            {
                if (srcReg[i] > 0 && srcReg[i] < rid)
                    srcReg[i] = sweeps[srcReg[i]].id;
            }
        }
    }


    ctx->startTimer(RC_TIMER_BUILD_REGIONS_FILTER);

    // Merge regions and filter out small regions.
    rcIntArray overlaps;
    chf.maxRegions = id;
    if (!mergeAndFilterRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg, overlaps))
        return false;

    // Monotone partitioning does not generate overlapping regions.
    
    ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FILTER);
    
    // Store the result out.
    for (int i = 0; i < chf.spanCount; ++i)
        chf.spans[i].reg = srcReg[i];
    
    ctx->stopTimer(RC_TIMER_BUILD_REGIONS);

    return true;
}

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]	verts	An array of vertices. [(x, y, z) * nv]
[in]	nv	The number of vertices in the verts array.
[out]	bmin	The minimum bounds of the AABB. [(x, y, z)] [Units: wu]
[out]	bmax	The maximum bounds of the AABB. [(x, y, z)] [Units: wu]

{
    // Calculate bounding box.
    rcVcopy(bmin, verts);
    rcVcopy(bmax, verts);
    for (int i = 1; i < nv; ++i)
    {
        const float* v = &verts[i*3];
        rcVmin(bmin, v);
        rcVmax(bmax, v);
    }
}

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]	bmin	The minimum bounds of the AABB. [(x, y, z)] [Units: wu]
[in]	bmax	The maximum bounds of the AABB. [(x, y, z)] [Units: wu]
[in]	cs	The xz-plane cell size. [Limit: > 0] [Units: wu]
[out]	w	The width along the x-axis. [Limit: >= 0] [Units: vx]
[out]	h	The height along the z-axis. [Limit: >= 0] [Units: vx]

{
    *w = (int)((bmax[0] - bmin[0])/cs+0.5f);
    *h = (int)((bmax[2] - bmin[2])/cs+0.5f);
}

Here is the caller graph for this function:

template<class T >

T rcClamp ( T  v, T  mn, T  mx  )

inline

Clamps the value to the specified range.

Parameters

[in]	v	The value to clamp.
[in]	mn	The minimum permitted return value.
[in]	mx	The maximum permitted return value.

Returns

The value, clamped to the specified range.

{ 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]	ctx	The build context to use during the operation.
[in]	walkableSlopeAngle	The maximum slope that is considered walkable. [Limits: 0 <= value < 90] [Units: Degrees]
[in]	verts	The vertices. [(x, y, z) * nv]
[in]	nv	The number of vertices.
[in]	tris	The triangle vertex indices. [(vertA, vertB, vertC) * nt]
[in]	nt	The number of triangles.
[out]	areas	The 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

{
    rcIgnoreUnused(ctx);
    
    const float walkableThr = cosf(walkableSlopeAngle/180.0f*RC_PI);
    
    float norm[3];
    
    for (int i = 0; i < nt; ++i)
    {
        const int* tri = &tris[i*3];
        calcTriNormal(&verts[tri[0]*3], &verts[tri[1]*3], &verts[tri[2]*3], norm);
        // Check if the face is walkable.
        if (norm[1] <= walkableThr)
            areas[i] = RC_NULL_AREA;
    }
}

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]	ctx	The build context to use during the operation.
[in]	src	The source mesh to copy from.
[out]	dst	The resulting detail mesh. (Must be pre-allocated, must be empty mesh.)

Returns

True if the operation completed successfully.

{
    rcAssert(ctx);
    
    // Destination must be empty.
    rcAssert(dst.verts == 0);
    rcAssert(dst.polys == 0);
    rcAssert(dst.regs == 0);
    rcAssert(dst.areas == 0);
    rcAssert(dst.flags == 0);
    
    dst.nverts = src.nverts;
    dst.npolys = src.npolys;
    dst.maxpolys = src.npolys;
    dst.nvp = src.nvp;
    rcVcopy(dst.bmin, src.bmin);
    rcVcopy(dst.bmax, src.bmax);
    dst.cs = src.cs;
    dst.ch = src.ch;
    dst.borderSize = src.borderSize;
    
    dst.verts = (unsigned short*)rcAlloc(sizeof(unsigned short)*src.nverts*3, RC_ALLOC_PERM);
    if (!dst.verts)
    {
        ctx->log(RC_LOG_ERROR, "rcCopyPolyMesh: Out of memory 'dst.verts' (%d).", src.nverts*3);
        return false;
    }
    memcpy(dst.verts, src.verts, sizeof(unsigned short)*src.nverts*3);
    
    dst.polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*src.npolys*2*src.nvp, RC_ALLOC_PERM);
    if (!dst.polys)
    {
        ctx->log(RC_LOG_ERROR, "rcCopyPolyMesh: Out of memory 'dst.polys' (%d).", src.npolys*2*src.nvp);
        return false;
    }
    memcpy(dst.polys, src.polys, sizeof(unsigned short)*src.npolys*2*src.nvp);
    
    dst.regs = (unsigned short*)rcAlloc(sizeof(unsigned short)*src.npolys, RC_ALLOC_PERM);
    if (!dst.regs)
    {
        ctx->log(RC_LOG_ERROR, "rcCopyPolyMesh: Out of memory 'dst.regs' (%d).", src.npolys);
        return false;
    }
    memcpy(dst.regs, src.regs, sizeof(unsigned short)*src.npolys);
    
    dst.areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*src.npolys, RC_ALLOC_PERM);
    if (!dst.areas)
    {
        ctx->log(RC_LOG_ERROR, "rcCopyPolyMesh: Out of memory 'dst.areas' (%d).", src.npolys);
        return false;
    }
    memcpy(dst.areas, src.areas, sizeof(unsigned char)*src.npolys);
    
    dst.flags = (unsigned short*)rcAlloc(sizeof(unsigned short)*src.npolys, RC_ALLOC_PERM);
    if (!dst.flags)
    {
        ctx->log(RC_LOG_ERROR, "rcCopyPolyMesh: Out of memory 'dst.flags' (%d).", src.npolys);
        return false;
    }
    memcpy(dst.flags, src.flags, sizeof(unsigned short)*src.npolys);
    
    return true;
}

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]	ctx	The build context to use during the operation.
[in,out]	hf	The allocated heightfield to initialize.
[in]	width	The width of the field along the x-axis. [Limit: >= 0] [Units: vx]
[in]	height	The height of the field along the z-axis. [Limit: >= 0] [Units: vx]
[in]	bmin	The minimum bounds of the field's AABB. [(x, y, z)] [Units: wu]
[in]	bmax	The maximum bounds of the field's AABB. [(x, y, z)] [Units: wu]
[in]	cs	The xz-plane cell size to use for the field. [Limit: > 0] [Units: wu]
[in]	ch	The 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

{
    rcIgnoreUnused(ctx);
    
    hf.width = width;
    hf.height = height;
    rcVcopy(hf.bmin, bmin);
    rcVcopy(hf.bmax, bmax);
    hf.cs = cs;
    hf.ch = ch;
    hf.spans = (rcSpan**)rcAlloc(sizeof(rcSpan*)*hf.width*hf.height, RC_ALLOC_PERM);
    if (!hf.spans)
        return false;
    memset(hf.spans, 0, sizeof(rcSpan*)*hf.width*hf.height);
    return true;
}

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]	ctx	The build context to use during the operation.
[in]	radius	The radius of erosion. [Limits: 0 < value < 255] [Units: vx]
[in,out]	chf	The 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

{
    rcAssert(ctx);
    
    const int w = chf.width;
    const int h = chf.height;
    
    ctx->startTimer(RC_TIMER_ERODE_AREA);
    
    unsigned char* dist = (unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP);
    if (!dist)
    {
        ctx->log(RC_LOG_ERROR, "erodeWalkableArea: Out of memory 'dist' (%d).", chf.spanCount);
        return false;
    }
    
    // Init distance.
    memset(dist, 0xff, sizeof(unsigned char)*chf.spanCount);
    
    // Mark boundary cells.
    for (int y = 0; y < h; ++y)
    {
        for (int x = 0; x < w; ++x)
        {
            const rcCompactCell& c = chf.cells[x+y*w];
            for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
            {
                if (chf.areas[i] == RC_NULL_AREA)
                {
                    dist[i] = 0;
                }
                else
                {
                    const rcCompactSpan& s = chf.spans[i];
                    int nc = 0;
                    for (int dir = 0; dir < 4; ++dir)
                    {
                        if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
                        {
                            const int nx = x + rcGetDirOffsetX(dir);
                            const int ny = y + rcGetDirOffsetY(dir);
                            const int nidx = (int)chf.cells[nx+ny*w].index + rcGetCon(s, dir);
                            if (chf.areas[nidx] != RC_NULL_AREA)
                            {
                                nc++;
                            }
                        }
                    }
                    // At least one missing neighbour.
                    if (nc != 4)
                        dist[i] = 0;
                }
            }
        }
    }
    
    unsigned char nd;
    
    // Pass 1
    for (int y = 0; y < h; ++y)
    {
        for (int x = 0; x < w; ++x)
        {
            const rcCompactCell& c = chf.cells[x+y*w];
            for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
            {
                const rcCompactSpan& s = chf.spans[i];
                
                if (rcGetCon(s, 0) != RC_NOT_CONNECTED)
                {
                    // (-1,0)
                    const int ax = x + rcGetDirOffsetX(0);
                    const int ay = y + rcGetDirOffsetY(0);
                    const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 0);
                    const rcCompactSpan& as = chf.spans[ai];
                    nd = (unsigned char)rcMin((int)dist[ai]+2, 255);
                    if (nd < dist[i])
                        dist[i] = nd;
                    
                    // (-1,-1)
                    if (rcGetCon(as, 3) != RC_NOT_CONNECTED)
                    {
                        const int aax = ax + rcGetDirOffsetX(3);
                        const int aay = ay + rcGetDirOffsetY(3);
                        const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 3);
                        nd = (unsigned char)rcMin((int)dist[aai]+3, 255);
                        if (nd < dist[i])
                            dist[i] = nd;
                    }
                }
                if (rcGetCon(s, 3) != RC_NOT_CONNECTED)
                {
                    // (0,-1)
                    const int ax = x + rcGetDirOffsetX(3);
                    const int ay = y + rcGetDirOffsetY(3);
                    const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 3);
                    const rcCompactSpan& as = chf.spans[ai];
                    nd = (unsigned char)rcMin((int)dist[ai]+2, 255);
                    if (nd < dist[i])
                        dist[i] = nd;
                    
                    // (1,-1)
                    if (rcGetCon(as, 2) != RC_NOT_CONNECTED)
                    {
                        const int aax = ax + rcGetDirOffsetX(2);
                        const int aay = ay + rcGetDirOffsetY(2);
                        const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 2);
                        nd = (unsigned char)rcMin((int)dist[aai]+3, 255);
                        if (nd < dist[i])
                            dist[i] = nd;
                    }
                }
            }
        }
    }
    
    // Pass 2
    for (int y = h-1; y >= 0; --y)
    {
        for (int x = w-1; x >= 0; --x)
        {
            const rcCompactCell& c = chf.cells[x+y*w];
            for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
            {
                const rcCompactSpan& s = chf.spans[i];
                
                if (rcGetCon(s, 2) != RC_NOT_CONNECTED)
                {
                    // (1,0)
                    const int ax = x + rcGetDirOffsetX(2);
                    const int ay = y + rcGetDirOffsetY(2);
                    const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 2);
                    const rcCompactSpan& as = chf.spans[ai];
                    nd = (unsigned char)rcMin((int)dist[ai]+2, 255);
                    if (nd < dist[i])
                        dist[i] = nd;
                    
                    // (1,1)
                    if (rcGetCon(as, 1) != RC_NOT_CONNECTED)
                    {
                        const int aax = ax + rcGetDirOffsetX(1);
                        const int aay = ay + rcGetDirOffsetY(1);
                        const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 1);
                        nd = (unsigned char)rcMin((int)dist[aai]+3, 255);
                        if (nd < dist[i])
                            dist[i] = nd;
                    }
                }
                if (rcGetCon(s, 1) != RC_NOT_CONNECTED)
                {
                    // (0,1)
                    const int ax = x + rcGetDirOffsetX(1);
                    const int ay = y + rcGetDirOffsetY(1);
                    const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 1);
                    const rcCompactSpan& as = chf.spans[ai];
                    nd = (unsigned char)rcMin((int)dist[ai]+2, 255);
                    if (nd < dist[i])
                        dist[i] = nd;
                    
                    // (-1,1)
                    if (rcGetCon(as, 0) != RC_NOT_CONNECTED)
                    {
                        const int aax = ax + rcGetDirOffsetX(0);
                        const int aay = ay + rcGetDirOffsetY(0);
                        const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 0);
                        nd = (unsigned char)rcMin((int)dist[aai]+3, 255);
                        if (nd < dist[i])
                            dist[i] = nd;
                    }
                }
            }
        }
    }
    
    const unsigned char thr = (unsigned char)(radius*2);
    for (int i = 0; i < chf.spanCount; ++i)
        if (dist[i] < thr)
            chf.areas[i] = RC_NULL_AREA;
    
    rcFree(dist);
    
    ctx->stopTimer(RC_TIMER_ERODE_AREA);
    
    return true;
}

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]	ctx	The build context to use during the operation.
[in]	walkableHeight	Minimum floor to 'ceiling' height that will still allow the floor area to be considered walkable. [Limit: >= 3] [Units: vx]
[in]	walkableClimb	Maximum ledge height that is considered to still be traversable. [Limit: >=0] [Units: vx]
[in,out]	solid	A 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

{
    rcAssert(ctx);
    
    ctx->startTimer(RC_TIMER_FILTER_BORDER);

    const int w = solid.width;
    const int h = solid.height;
    const int MAX_HEIGHT = 0xffff;
    
    // Mark border spans.
    for (int y = 0; y < h; ++y)
    {
        for (int x = 0; x < w; ++x)
        {
            for (rcSpan* s = solid.spans[x + y*w]; s; s = s->next)
            {
                // Skip non walkable spans.
                if (s->area == RC_NULL_AREA)
                    continue;
                
                const int bot = (int)(s->smax);
                const int top = s->next ? (int)(s->next->smin) : MAX_HEIGHT;
                
                // Find neighbours minimum height.
                int minh = MAX_HEIGHT;

                // Min and max height of accessible neighbours.
                int asmin = s->smax;
                int asmax = s->smax;

                for (int dir = 0; dir < 4; ++dir)
                {
                    int dx = x + rcGetDirOffsetX(dir);
                    int dy = y + rcGetDirOffsetY(dir);
                    // Skip neighbours which are out of bounds.
                    if (dx < 0 || dy < 0 || dx >= w || dy >= h)
                    {
                        minh = rcMin(minh, -walkableClimb - bot);
                        continue;
                    }

                    // From minus infinity to the first span.
                    rcSpan* ns = solid.spans[dx + dy*w];
                    int nbot = -walkableClimb;
                    int ntop = ns ? (int)ns->smin : MAX_HEIGHT;
                    // Skip neightbour if the gap between the spans is too small.
                    if (rcMin(top,ntop) - rcMax(bot,nbot) > walkableHeight)
                        minh = rcMin(minh, nbot - bot);
                    
                    // Rest of the spans.
                    for (ns = solid.spans[dx + dy*w]; ns; ns = ns->next)
                    {
                        nbot = (int)ns->smax;
                        ntop = ns->next ? (int)ns->next->smin : MAX_HEIGHT;
                        // Skip neightbour if the gap between the spans is too small.
                        if (rcMin(top,ntop) - rcMax(bot,nbot) > walkableHeight)
                        {
                            minh = rcMin(minh, nbot - bot);
                        
                            // Find min/max accessible neighbour height. 
                            if (rcAbs(nbot - bot) <= walkableClimb)
                            {
                                if (nbot < asmin) asmin = nbot;
                                if (nbot > asmax) asmax = nbot;
                            }
                            
                        }
                    }
                }
                
                // The current span is close to a ledge if the drop to any
                // neighbour span is less than the walkableClimb.
                if (minh < -walkableClimb)
                    s->area = RC_NULL_AREA;
                    
                // If the difference between all neighbours is too large,
                // we are at steep slope, mark the span as ledge.
                if ((asmax - asmin) > walkableClimb)
                {
                    s->area = RC_NULL_AREA;
                }
            }
        }
    }
    
    ctx->stopTimer(RC_TIMER_FILTER_BORDER);
}   

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]	ctx	The build context to use during the operation.
[in]	walkableClimb	Maximum ledge height that is considered to still be traversable. [Limit: >=0] [Units: vx]
[in,out]	solid	A 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

{
    rcAssert(ctx);

    ctx->startTimer(RC_TIMER_FILTER_LOW_OBSTACLES);
    
    const int w = solid.width;
    const int h = solid.height;
    
    for (int y = 0; y < h; ++y)
    {
        for (int x = 0; x < w; ++x)
        {
            rcSpan* ps = 0;
            bool previousWalkable = false;
            unsigned char previousArea = RC_NULL_AREA;
            
            for (rcSpan* s = solid.spans[x + y*w]; s; ps = s, s = s->next)
            {
                const bool walkable = s->area != RC_NULL_AREA;
                // If current span is not walkable, but there is walkable
                // span just below it, mark the span above it walkable too.
                if (!walkable && previousWalkable)
                {
                    if (rcAbs((int)s->smax - (int)ps->smax) <= walkableClimb)
                        s->area = previousArea;
                }
                // Copy walkable flag so that it cannot propagate
                // past multiple non-walkable objects.
                previousWalkable = walkable;
                previousArea = s->area;
            }
        }
    }

    ctx->stopTimer(RC_TIMER_FILTER_LOW_OBSTACLES);
}

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]	ctx	The build context to use during the operation.
[in]	walkableHeight	Minimum floor to 'ceiling' height that will still allow the floor area to be considered walkable. [Limit: >= 3] [Units: vx]
[in,out]	solid	A 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

{
    rcAssert(ctx);
    
    ctx->startTimer(RC_TIMER_FILTER_WALKABLE);
    
    const int w = solid.width;
    const int h = solid.height;
    const int MAX_HEIGHT = 0xffff;
    
    // Remove walkable flag from spans which do not have enough
    // space above them for the agent to stand there.
    for (int y = 0; y < h; ++y)
    {
        for (int x = 0; x < w; ++x)
        {
            for (rcSpan* s = solid.spans[x + y*w]; s; s = s->next)
            {
                const int bot = (int)(s->smax);
                const int top = s->next ? (int)(s->next->smin) : MAX_HEIGHT;
                if ((top - bot) <= walkableHeight)
                    s->area = RC_NULL_AREA;
            }
        }
    }
    
    ctx->stopTimer(RC_TIMER_FILTER_WALKABLE);
}

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]

chf

A compact heightfield allocated using rcAllocCompactHeightfield

See also

rcAllocCompactHeightfield

{
    if (!chf) return;
    rcFree(chf->cells);
    rcFree(chf->spans);
    rcFree(chf->dist);
    rcFree(chf->areas);
    rcFree(chf);
}

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]

cset

A contour set allocated using rcAllocContourSet

See also

rcAllocContourSet

{
    if (!cset) return;
    for (int i = 0; i < cset->nconts; ++i)
    {
        rcFree(cset->conts[i].verts);
        rcFree(cset->conts[i].rverts);
    }
    rcFree(cset->conts);
    rcFree(cset);
}

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]

hf

A heightfield allocated using rcAllocHeightfield

See also

rcAllocHeightfield

{
    if (!hf) return;
    // Delete span array.
    rcFree(hf->spans);
    // Delete span pools.
    while (hf->pools)
    {
        rcSpanPool* next = hf->pools->next;
        rcFree(hf->pools);
        hf->pools = next;
    }
    rcFree(hf);
}

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]

lset

A heightfield layer set allocated using rcAllocHeightfieldLayerSet

See also

rcAllocHeightfieldLayerSet

{
    if (!lset) return;
    for (int i = 0; i < lset->nlayers; ++i)
    {
        rcFree(lset->layers[i].heights);
        rcFree(lset->layers[i].areas);
        rcFree(lset->layers[i].cons);
    }
    rcFree(lset->layers);
    rcFree(lset);
}

Here is the call graph for this function:

void rcFreePolyMesh

(

rcPolyMesh *

pmesh

)

Frees the specified polygon mesh using the Recast allocator.

Parameters

[in]

pmesh

A polygon mesh allocated using rcAllocPolyMesh

See also

rcAllocPolyMesh

{
    if (!pmesh) return;
    rcFree(pmesh->verts);
    rcFree(pmesh->polys);
    rcFree(pmesh->regs);
    rcFree(pmesh->flags);
    rcFree(pmesh->areas);
    rcFree(pmesh);
}

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]

dmesh

A detail mesh allocated using rcAllocPolyMeshDetail

See also

rcAllocPolyMeshDetail

{
    if (!dmesh) return;
    rcFree(dmesh->meshes);
    rcFree(dmesh->verts);
    rcFree(dmesh->tris);
    rcFree(dmesh);
}

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]	s	The span to check.
[in]	dir	The 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.

{
    const unsigned int shift = (unsigned int)dir*6;
    return (s.con >> shift) & 0x3f;
}

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]

dir

The direction. [Limits: 0 <= value < 4]

Returns

The width offset to apply to the current cell position to move in the direction.

{
    const int offset[4] = { -1, 0, 1, 0, };
    return offset[dir&0x03];
}

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]

dir

The direction. [Limits: 0 <= value < 4]

Returns

The height offset to apply to the current cell position to move in the direction.

{
    const int offset[4] = { 0, 1, 0, -1 };
    return offset[dir&0x03];
}

Here is the caller graph for this function:

int rcGetHeightFieldSpanCount	(	rcContext *	ctx,
		rcHeightfield &	hf
	)

Returns the number of spans contained in the specified heightfield.

Parameters

[in,out]	ctx	The build context to use during the operation.
[in]	hf	An initialized heightfield.

Returns

The number of spans in the heightfield.

{
    rcIgnoreUnused(ctx);
    
    const int w = hf.width;
    const int h = hf.height;
    int spanCount = 0;
    for (int y = 0; y < h; ++y)
    {
        for (int x = 0; x < w; ++x)
        {
            for (rcSpan* s = hf.spans[x + y*w]; s; s = s->next)
            {
                if (s->area != RC_NULL_AREA)
                    spanCount++;
            }
        }
    }
    return spanCount;
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T >

void rcIgnoreUnused

(

const T &

)

Used to ignore a function parameter. VS complains about unused parameters and this silences the warning.

Parameters

[in]

_

Unused parameter

{ }

Here is the caller graph for this function:

void rcMarkBoxArea	(	rcContext *	ctx,
		const float *	bmin,
		const float *	bmax,
		unsigned char	areaId,
		rcCompactHeightfield &	chf
	)

Applies an area id to all spans within the specified bounding box. (AABB)

Parameters

[in,out]	ctx	The build context to use during the operation.
[in]	bmin	The minimum of the bounding box. [(x, y, z)]
[in]	bmax	The maximum of the bounding box. [(x, y, z)]
[in]	areaId	The area id to apply. [Limit: <= RC_WALKABLE_AREA]
[in,out]	chf	A populated compact heightfield.

The value of spacial parameters are in world units.

See also

rcCompactHeightfield, rcMedianFilterWalkableArea

{
    rcAssert(ctx);
    
    ctx->startTimer(RC_TIMER_MARK_BOX_AREA);

    int minx = (int)((bmin[0]-chf.bmin[0])/chf.cs);
    int miny = (int)((bmin[1]-chf.bmin[1])/chf.ch);
    int minz = (int)((bmin[2]-chf.bmin[2])/chf.cs);
    int maxx = (int)((bmax[0]-chf.bmin[0])/chf.cs);
    int maxy = (int)((bmax[1]-chf.bmin[1])/chf.ch);
    int maxz = (int)((bmax[2]-chf.bmin[2])/chf.cs);
    
    if (maxx < 0) return;
    if (minx >= chf.width) return;
    if (maxz < 0) return;
    if (minz >= chf.height) return;

    if (minx < 0) minx = 0;
    if (maxx >= chf.width) maxx = chf.width-1;
    if (minz < 0) minz = 0;
    if (maxz >= chf.height) maxz = chf.height-1;    
    
    for (int z = minz; z <= maxz; ++z)
    {
        for (int x = minx; x <= maxx; ++x)
        {
            const rcCompactCell& c = chf.cells[x+z*chf.width];
            for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
            {
                rcCompactSpan& s = chf.spans[i];
                if ((int)s.y >= miny && (int)s.y <= maxy)
                {
                    if (chf.areas[i] != RC_NULL_AREA)
                        chf.areas[i] = areaId;
                }
            }
        }
    }

    ctx->stopTimer(RC_TIMER_MARK_BOX_AREA);

}

Here is the call graph for this function:

void rcMarkConvexPolyArea	(	rcContext *	ctx,
		const float *	verts,
		const int	nverts,
		const float	hmin,
		const float	hmax,
		unsigned char	areaId,
		rcCompactHeightfield &	chf
	)

Applies the area id to the all spans within the specified convex polygon.

Parameters

[in,out]	ctx	The build context to use during the operation.
[in]	verts	The vertices of the polygon [Fomr: (x, y, z) * nverts]
[in]	nverts	The number of vertices in the polygon.
[in]	hmin	The height of the base of the polygon.
[in]	hmax	The height of the top of the polygon.
[in]	areaId	The area id to apply. [Limit: <= RC_WALKABLE_AREA]
[in,out]	chf	A populated compact heightfield.

The value of spacial parameters are in world units.

The y-values of the polygon vertices are ignored. So the polygon is effectively projected onto the xz-plane at hmin, then extruded to hmax.

See also

rcCompactHeightfield, rcMedianFilterWalkableArea

{
    rcAssert(ctx);
    
    ctx->startTimer(RC_TIMER_MARK_CONVEXPOLY_AREA);

    float bmin[3], bmax[3];
    rcVcopy(bmin, verts);
    rcVcopy(bmax, verts);
    for (int i = 1; i < nverts; ++i)
    {
        rcVmin(bmin, &verts[i*3]);
        rcVmax(bmax, &verts[i*3]);
    }
    bmin[1] = hmin;
    bmax[1] = hmax;

    int minx = (int)((bmin[0]-chf.bmin[0])/chf.cs);
    int miny = (int)((bmin[1]-chf.bmin[1])/chf.ch);
    int minz = (int)((bmin[2]-chf.bmin[2])/chf.cs);
    int maxx = (int)((bmax[0]-chf.bmin[0])/chf.cs);
    int maxy = (int)((bmax[1]-chf.bmin[1])/chf.ch);
    int maxz = (int)((bmax[2]-chf.bmin[2])/chf.cs);
    
    if (maxx < 0) return;
    if (minx >= chf.width) return;
    if (maxz < 0) return;
    if (minz >= chf.height) return;
    
    if (minx < 0) minx = 0;
    if (maxx >= chf.width) maxx = chf.width-1;
    if (minz < 0) minz = 0;
    if (maxz >= chf.height) maxz = chf.height-1;    
    
    
    // TODO: Optimize.
    for (int z = minz; z <= maxz; ++z)
    {
        for (int x = minx; x <= maxx; ++x)
        {
            const rcCompactCell& c = chf.cells[x+z*chf.width];
            for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
            {
                rcCompactSpan& s = chf.spans[i];
                if (chf.areas[i] == RC_NULL_AREA)
                    continue;
                if ((int)s.y >= miny && (int)s.y <= maxy)
                {
                    float p[3];
                    p[0] = chf.bmin[0] + (x+0.5f)*chf.cs; 
                    p[1] = 0;
                    p[2] = chf.bmin[2] + (z+0.5f)*chf.cs; 

                    if (pointInPoly(nverts, verts, p))
                    {
                        chf.areas[i] = areaId;
                    }
                }
            }
        }
    }

    ctx->stopTimer(RC_TIMER_MARK_CONVEXPOLY_AREA);
}

Here is the call graph for this function:

void rcMarkCylinderArea	(	rcContext *	ctx,
		const float *	pos,
		const float	r,
		const float	h,
		unsigned char	areaId,
		rcCompactHeightfield &	chf
	)

Applies the area id to all spans within the specified cylinder.

Parameters

[in,out]	ctx	The build context to use during the operation.
[in]	pos	The center of the base of the cylinder. [Form: (x, y, z)]
[in]	r	The radius of the cylinder.
[in]	h	The height of the cylinder.
[in]	areaId	The area id to apply. [Limit: <= RC_WALKABLE_AREA]
[in,out]	chf	A populated compact heightfield.

The value of spacial parameters are in world units.

See also

rcCompactHeightfield, rcMedianFilterWalkableArea

{
    rcAssert(ctx);
    
    ctx->startTimer(RC_TIMER_MARK_CYLINDER_AREA);
    
    float bmin[3], bmax[3];
    bmin[0] = pos[0] - r;
    bmin[1] = pos[1];
    bmin[2] = pos[2] - r;
    bmax[0] = pos[0] + r;
    bmax[1] = pos[1] + h;
    bmax[2] = pos[2] + r;
    const float r2 = r*r;
    
    int minx = (int)((bmin[0]-chf.bmin[0])/chf.cs);
    int miny = (int)((bmin[1]-chf.bmin[1])/chf.ch);
    int minz = (int)((bmin[2]-chf.bmin[2])/chf.cs);
    int maxx = (int)((bmax[0]-chf.bmin[0])/chf.cs);
    int maxy = (int)((bmax[1]-chf.bmin[1])/chf.ch);
    int maxz = (int)((bmax[2]-chf.bmin[2])/chf.cs);
    
    if (maxx < 0) return;
    if (minx >= chf.width) return;
    if (maxz < 0) return;
    if (minz >= chf.height) return;
    
    if (minx < 0) minx = 0;
    if (maxx >= chf.width) maxx = chf.width-1;
    if (minz < 0) minz = 0;
    if (maxz >= chf.height) maxz = chf.height-1;    
    
    
    for (int z = minz; z <= maxz; ++z)
    {
        for (int x = minx; x <= maxx; ++x)
        {
            const rcCompactCell& c = chf.cells[x+z*chf.width];
            for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
            {
                rcCompactSpan& s = chf.spans[i];
                
                if (chf.areas[i] == RC_NULL_AREA)
                    continue;
                
                if ((int)s.y >= miny && (int)s.y <= maxy)
                {
                    const float sx = chf.bmin[0] + (x+0.5f)*chf.cs; 
                    const float sz = chf.bmin[2] + (z+0.5f)*chf.cs; 
                    const float dx = sx - pos[0];
                    const float dz = sz - pos[2];
                    
                    if (dx*dx + dz*dz < r2)
                    {
                        chf.areas[i] = areaId;
                    }
                }
            }
        }
    }
    
    ctx->stopTimer(RC_TIMER_MARK_CYLINDER_AREA);
}

Here is the call graph for this function:

void rcMarkWalkableTriangles	(	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 below the specified value to RC_WALKABLE_AREA.

Parameters

[in,out]	ctx	The build context to use during the operation.
[in]	walkableSlopeAngle	The maximum slope that is considered walkable. [Limits: 0 <= value < 90] [Units: Degrees]
[in]	verts	The vertices. [(x, y, z) * nv]
[in]	nv	The number of vertices.
[in]	tris	The triangle vertex indices. [(vertA, vertB, vertC) * nt]
[in]	nt	The number of triangles.
[out]	areas	The triangle area ids. [Length: >= nt]

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

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

See also

rcHeightfield, rcClearUnwalkableTriangles, rcRasterizeTriangles

{
    rcIgnoreUnused(ctx);
    
    const float walkableThr = cosf(walkableSlopeAngle/180.0f*RC_PI);

    float norm[3];
    
    for (int i = 0; i < nt; ++i)
    {
        const int* tri = &tris[i*3];
        calcTriNormal(&verts[tri[0]*3], &verts[tri[1]*3], &verts[tri[2]*3], norm);
        // Check if the face is walkable.
        if (norm[1] > walkableThr)
            areas[i] = RC_WALKABLE_AREA;
    }
}

Here is the call graph for this function:

template<class T >

T rcMax ( T  a, T  b  )

inline

Returns the maximum of two values.

Parameters

[in]	a	Value A
[in]	b	Value B

Returns

The maximum of the two values.

{ return a > b ? a : b; }

Here is the caller graph for this function:

bool rcMedianFilterWalkableArea	(	rcContext *	ctx,
		rcCompactHeightfield &	chf
	)

Applies a median filter to walkable area types (based on area id), removing noise.

Parameters

[in,out]	ctx	The build context to use during the operation.
[in,out]	chf	A populated compact heightfield.

Returns

True if the operation completed successfully.

This filter is usually applied after applying area id's using functions such as rcMarkBoxArea, rcMarkConvexPolyArea, and rcMarkCylinderArea.

See also

rcCompactHeightfield

{
    rcAssert(ctx);
    
    const int w = chf.width;
    const int h = chf.height;
    
    ctx->startTimer(RC_TIMER_MEDIAN_AREA);
    
    unsigned char* areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP);
    if (!areas)
    {
        ctx->log(RC_LOG_ERROR, "medianFilterWalkableArea: Out of memory 'areas' (%d).", chf.spanCount);
        return false;
    }
    
    // Init distance.
    memset(areas, 0xff, sizeof(unsigned char)*chf.spanCount);
    
    for (int y = 0; y < h; ++y)
    {
        for (int x = 0; x < w; ++x)
        {
            const rcCompactCell& c = chf.cells[x+y*w];
            for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
            {
                const rcCompactSpan& s = chf.spans[i];
                if (chf.areas[i] == RC_NULL_AREA)
                {
                    areas[i] = chf.areas[i];
                    continue;
                }
                
                unsigned char nei[9];
                for (int j = 0; j < 9; ++j)
                    nei[j] = chf.areas[i];
                
                for (int dir = 0; dir < 4; ++dir)
                {
                    if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
                    {
                        const int ax = x + rcGetDirOffsetX(dir);
                        const int ay = y + rcGetDirOffsetY(dir);
                        const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);
                        if (chf.areas[ai] != RC_NULL_AREA)
                            nei[dir*2+0] = chf.areas[ai];
                        
                        const rcCompactSpan& as = chf.spans[ai];
                        const int dir2 = (dir+1) & 0x3;
                        if (rcGetCon(as, dir2) != RC_NOT_CONNECTED)
                        {
                            const int ax2 = ax + rcGetDirOffsetX(dir2);
                            const int ay2 = ay + rcGetDirOffsetY(dir2);
                            const int ai2 = (int)chf.cells[ax2+ay2*w].index + rcGetCon(as, dir2);
                            if (chf.areas[ai2] != RC_NULL_AREA)
                                nei[dir*2+1] = chf.areas[ai2];
                        }
                    }
                }
                insertSort(nei, 9);
                areas[i] = nei[4];
            }
        }
    }
    
    memcpy(chf.areas, areas, sizeof(unsigned char)*chf.spanCount);
    
    rcFree(areas);

    ctx->stopTimer(RC_TIMER_MEDIAN_AREA);
    
    return true;
}

Here is the call graph for this function:

bool rcMergePolyMeshDetails	(	rcContext *	ctx,
		rcPolyMeshDetail **	meshes,
		const int	nmeshes,
		rcPolyMeshDetail &	mesh
	)

Merges multiple detail meshes into a single detail mesh.

Parameters

[in,out]	ctx	The build context to use during the operation.
[in]	meshes	An array of detail meshes to merge. [Size: nmeshes]
[in]	nmeshes	The number of detail meshes in the meshes array.
[out]	mesh	The resulting detail mesh. (Must be pre-allocated.)

Returns

True if the operation completed successfully.

See also

rcAllocPolyMeshDetail, rcPolyMeshDetail

{
    rcAssert(ctx);
    
    ctx->startTimer(RC_TIMER_MERGE_POLYMESHDETAIL);
    
    int maxVerts = 0;
    int maxTris = 0;
    int maxMeshes = 0;
    
    for (int i = 0; i < nmeshes; ++i)
    {
        if (!meshes[i]) continue;
        maxVerts += meshes[i]->nverts;
        maxTris += meshes[i]->ntris;
        maxMeshes += meshes[i]->nmeshes;
    }
    
    mesh.nmeshes = 0;
    mesh.meshes = (unsigned int*)rcAlloc(sizeof(unsigned int)*maxMeshes*4, RC_ALLOC_PERM);
    if (!mesh.meshes)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'pmdtl.meshes' (%d).", maxMeshes*4);
        return false;
    }
    
    mesh.ntris = 0;
    mesh.tris = (unsigned char*)rcAlloc(sizeof(unsigned char)*maxTris*4, RC_ALLOC_PERM);
    if (!mesh.tris)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.tris' (%d).", maxTris*4);
        return false;
    }
    
    mesh.nverts = 0;
    mesh.verts = (float*)rcAlloc(sizeof(float)*maxVerts*3, RC_ALLOC_PERM);
    if (!mesh.verts)
    {
        ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.verts' (%d).", maxVerts*3);
        return false;
    }
    
    // Merge datas.
    for (int i = 0; i < nmeshes; ++i)
    {
        rcPolyMeshDetail* dm = meshes[i];
        if (!dm) continue;
        for (int j = 0; j < dm->nmeshes; ++j)
        {
            unsigned int* dst = &mesh.meshes[mesh.nmeshes*4];
            unsigned int* src = &dm->meshes[j*4];
            dst[0] = (unsigned int)mesh.nverts+src[0];
            dst[1] = src[1];
            dst[2] = (unsigned int)mesh.ntris+src[2];
            dst[3] = src[3];
            mesh.nmeshes++;
        }
        
        for (int k = 0; k < dm->nverts; ++k)
        {
            rcVcopy(&mesh.verts[mesh.nverts*3], &dm->verts[k*3]);
            mesh.nverts++;
        }
        for (int k = 0; k < dm->ntris; ++k)
        {
            mesh.tris[mesh.ntris*4+0] = dm->tris[k*4+0];
            mesh.tris[mesh.ntris*4+1] = dm->tris[k*4+1];
            mesh.tris[mesh.ntris*4+2] = dm->tris[k*4+2];
            mesh.tris[mesh.ntris*4+3] = dm->tris[k*4+3];
            mesh.ntris++;
        }
    }
    
    ctx->stopTimer(RC_TIMER_MERGE_POLYMESHDETAIL);
    
    return true;
}

Here is the call graph for this function:

Here is the caller graph for this function:

bool rcMergePolyMeshes	(	rcContext *	ctx,
		rcPolyMesh **	meshes,
		const int	nmeshes,
		rcPolyMesh &	mesh
	)

Merges multiple polygon meshes into a single mesh.

Parameters

[in,out]	ctx	The build context to use during the operation.
[in]	meshes	An array of polygon meshes to merge. [Size: nmeshes]
[in]	nmeshes	The number of polygon meshes in the meshes array.
[in]	mesh	The resulting polygon mesh. (Must be pre-allocated.)

Returns

True if the operation completed successfully.

See also

rcAllocPolyMesh, rcPolyMesh

{
    rcAssert(ctx);
    
    if (!nmeshes || !meshes)
        return true;

    ctx->startTimer(RC_TIMER_MERGE_POLYMESH);

    mesh.nvp = meshes[0]->nvp;
    mesh.cs = meshes[0]->cs;
    mesh.ch = meshes[0]->ch;
    rcVcopy(mesh.bmin, meshes[0]->bmin);
    rcVcopy(mesh.bmax, meshes[0]->bmax);

    int maxVerts = 0;
    int maxPolys = 0;
    int maxVertsPerMesh = 0;
    for (int i = 0; i < nmeshes; ++i)
    {
        rcVmin(mesh.bmin, meshes[i]->bmin);
        rcVmax(mesh.bmax, meshes[i]->bmax);
        maxVertsPerMesh = rcMax(maxVertsPerMesh, meshes[i]->nverts);
        maxVerts += meshes[i]->nverts;
        maxPolys += meshes[i]->npolys;
    }
    
    mesh.nverts = 0;
    mesh.verts = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxVerts*3, RC_ALLOC_PERM);
    if (!mesh.verts)
    {
        ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'mesh.verts' (%d).", maxVerts*3);
        return false;
    }

    mesh.npolys = 0;
    mesh.polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxPolys*2*mesh.nvp, RC_ALLOC_PERM);
    if (!mesh.polys)
    {
        ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'mesh.polys' (%d).", maxPolys*2*mesh.nvp);
        return false;
    }
    memset(mesh.polys, 0xff, sizeof(unsigned short)*maxPolys*2*mesh.nvp);

    mesh.regs = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxPolys, RC_ALLOC_PERM);
    if (!mesh.regs)
    {
        ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'mesh.regs' (%d).", maxPolys);
        return false;
    }
    memset(mesh.regs, 0, sizeof(unsigned short)*maxPolys);

    mesh.areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*maxPolys, RC_ALLOC_PERM);
    if (!mesh.areas)
    {
        ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'mesh.areas' (%d).", maxPolys);
        return false;
    }
    memset(mesh.areas, 0, sizeof(unsigned char)*maxPolys);

    mesh.flags = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxPolys, RC_ALLOC_PERM);
    if (!mesh.flags)
    {
        ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'mesh.flags' (%d).", maxPolys);
        return false;
    }
    memset(mesh.flags, 0, sizeof(unsigned short)*maxPolys);
    
    rcScopedDelete<int> nextVert = (int*)rcAlloc(sizeof(int)*maxVerts, RC_ALLOC_TEMP);
    if (!nextVert)
    {
        ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'nextVert' (%d).", maxVerts);
        return false;
    }
    memset(nextVert, 0, sizeof(int)*maxVerts);
    
    rcScopedDelete<int> firstVert = (int*)rcAlloc(sizeof(int)*VERTEX_BUCKET_COUNT, RC_ALLOC_TEMP);
    if (!firstVert)
    {
        ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'firstVert' (%d).", VERTEX_BUCKET_COUNT);
        return false;
    }
    for (int i = 0; i < VERTEX_BUCKET_COUNT; ++i)
        firstVert[i] = -1;

    rcScopedDelete<unsigned short> vremap = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxVertsPerMesh, RC_ALLOC_PERM);
    if (!vremap)
    {
        ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'vremap' (%d).", maxVertsPerMesh);
        return false;
    }
    memset(vremap, 0, sizeof(unsigned short)*maxVertsPerMesh);
    
    for (int i = 0; i < nmeshes; ++i)
    {
        const rcPolyMesh* pmesh = meshes[i];
        
        const unsigned short ox = (unsigned short)floorf((pmesh->bmin[0]-mesh.bmin[0])/mesh.cs+0.5f);
        const unsigned short oz = (unsigned short)floorf((pmesh->bmin[2]-mesh.bmin[2])/mesh.cs+0.5f);
        
        bool isMinX = (ox == 0);
        bool isMinZ = (oz == 0);
        bool isMaxX = ((unsigned short)floorf((mesh.bmax[0] - pmesh->bmax[0]) / mesh.cs + 0.5f)) == 0;
        bool isMaxZ = ((unsigned short)floorf((mesh.bmax[2] - pmesh->bmax[2]) / mesh.cs + 0.5f)) == 0;
        bool isOnBorder = (isMinX || isMinZ || isMaxX || isMaxZ);

        for (int j = 0; j < pmesh->nverts; ++j)
        {
            unsigned short* v = &pmesh->verts[j*3];
            vremap[j] = addVertex(v[0]+ox, v[1], v[2]+oz,
                                  mesh.verts, firstVert, nextVert, mesh.nverts);
        }
        
        for (int j = 0; j < pmesh->npolys; ++j)
        {
            unsigned short* tgt = &mesh.polys[mesh.npolys*2*mesh.nvp];
            unsigned short* src = &pmesh->polys[j*2*mesh.nvp];
            mesh.regs[mesh.npolys] = pmesh->regs[j];
            mesh.areas[mesh.npolys] = pmesh->areas[j];
            mesh.flags[mesh.npolys] = pmesh->flags[j];
            mesh.npolys++;
            for (int k = 0; k < mesh.nvp; ++k)
            {
                if (src[k] == RC_MESH_NULL_IDX) break;
                tgt[k] = vremap[src[k]];
            }

            if (isOnBorder)
            {
                for (int k = mesh.nvp; k < mesh.nvp * 2; ++k)
                {
                    if (src[k] & 0x8000 && src[k] != 0xffff)
                    {
                        unsigned short dir = src[k] & 0xf;
                        switch (dir)
                        {
                            case 0: // Portal x-
                                if (isMinX)
                                    tgt[k] = src[k];
                                break;
                            case 1: // Portal z+
                                if (isMaxZ)
                                    tgt[k] = src[k];
                                break;
                            case 2: // Portal x+
                                if (isMaxX)
                                    tgt[k] = src[k];
                                break;
                            case 3: // Portal z-
                                if (isMinZ)
                                    tgt[k] = src[k];
                                break;
                        }
                    }
                }
            }
        }
    }

    // Calculate adjacency.
    if (!buildMeshAdjacency(mesh.polys, mesh.npolys, mesh.nverts, mesh.nvp))
    {
        ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Adjacency failed.");
        return false;
    }

    if (mesh.nverts > 0xffff)
    {
        ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: The resulting mesh has too many vertices %d (max %d). Data can be corrupted.", mesh.nverts, 0xffff);
    }
    if (mesh.npolys > 0xffff)
    {
        ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: The resulting mesh has too many polygons %d (max %d). Data can be corrupted.", mesh.npolys, 0xffff);
    }
    
    ctx->stopTimer(RC_TIMER_MERGE_POLYMESH);
    
    return true;
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T >

T rcMin ( T  a, T  b  )

inline

Returns the minimum of two values.

Parameters

[in]	a	Value A
[in]	b	Value B

Returns

The minimum of the two values.

{ return a < b ? a : b; }

Here is the caller graph for this function:

int rcOffsetPoly	(	const float *	verts,
		const int	nverts,
		const float	offset,
		float *	outVerts,
		const int	maxOutVerts
	)

Helper function to offset voncex polygons for rcMarkConvexPolyArea.

Parameters

[in]	verts	The vertices of the polygon [Form: (x, y, z) * nverts]
[in]	nverts	The number of vertices in the polygon.
[out]	outVerts	The offset vertices (should hold up to 2 * nverts) [Form: (x, y, z) * return value]
[in]	maxOutVerts	The max number of vertices that can be stored to outVerts.

Returns

Number of vertices in the offset polygon or 0 if too few vertices in outVerts.

{
    const float MITER_LIMIT = 1.20f;

    int n = 0;

    for (int i = 0; i < nverts; i++)
    {
        const int a = (i+nverts-1) % nverts;
        const int b = i;
        const int c = (i+1) % nverts;
        const float* va = &verts[a*3];
        const float* vb = &verts[b*3];
        const float* vc = &verts[c*3];
        float dx0 = vb[0] - va[0];
        float dy0 = vb[2] - va[2];
        float d0 = dx0*dx0 + dy0*dy0;
        if (d0 > 1e-6f)
        {
            d0 = 1.0f/rcSqrt(d0);
            dx0 *= d0;
            dy0 *= d0;
        }
        float dx1 = vc[0] - vb[0];
        float dy1 = vc[2] - vb[2];
        float d1 = dx1*dx1 + dy1*dy1;
        if (d1 > 1e-6f)
        {
            d1 = 1.0f/rcSqrt(d1);
            dx1 *= d1;
            dy1 *= d1;
        }
        const float dlx0 = -dy0;
        const float dly0 = dx0;
        const float dlx1 = -dy1;
        const float dly1 = dx1;
        float cross = dx1*dy0 - dx0*dy1;
        float dmx = (dlx0 + dlx1) * 0.5f;
        float dmy = (dly0 + dly1) * 0.5f;
        float dmr2 = dmx*dmx + dmy*dmy;
        bool bevel = dmr2 * MITER_LIMIT*MITER_LIMIT < 1.0f;
        if (dmr2 > 1e-6f)
        {
            const float scale = 1.0f / dmr2;
            dmx *= scale;
            dmy *= scale;
        }

        if (bevel && cross < 0.0f)
        {
            if (n+2 >= maxOutVerts)
                return 0;
            float d = (1.0f - (dx0*dx1 + dy0*dy1))*0.5f;
            outVerts[n*3+0] = vb[0] + (-dlx0+dx0*d)*offset;
            outVerts[n*3+1] = vb[1];
            outVerts[n*3+2] = vb[2] + (-dly0+dy0*d)*offset;
            n++;
            outVerts[n*3+0] = vb[0] + (-dlx1-dx1*d)*offset;
            outVerts[n*3+1] = vb[1];
            outVerts[n*3+2] = vb[2] + (-dly1-dy1*d)*offset;
            n++;
        }
        else
        {
            if (n+1 >= maxOutVerts)
                return 0;
            outVerts[n*3+0] = vb[0] - dmx*offset;
            outVerts[n*3+1] = vb[1];
            outVerts[n*3+2] = vb[2] - dmy*offset;
            n++;
        }
    }
    
    return n;
}

Here is the call graph for this function:

void rcRasterizeTriangle	(	rcContext *	ctx,
		const float *	v0,
		const float *	v1,
		const float *	v2,
		const unsigned char	area,
		rcHeightfield &	solid,
		const int	flagMergeThr
	)

Rasterizes a triangle into the specified heightfield.

Parameters

[in,out]	ctx	The build context to use during the operation.
[in]	v0	Triangle vertex 0 [(x, y, z)]
[in]	v1	Triangle vertex 1 [(x, y, z)]
[in]	v2	Triangle vertex 2 [(x, y, z)]
[in]	area	The area id of the triangle. [Limit: <= RC_WALKABLE_AREA]
[in,out]	solid	An initialized heightfield.
[in]	flagMergeThr	The distance where the walkable flag is favored over the non-walkable flag. [Limit: >= 0] [Units: vx]

No spans will be added if the triangle does not overlap the heightfield grid.

See also

rcHeightfield

{
    rcAssert(ctx);

    ctx->startTimer(RC_TIMER_RASTERIZE_TRIANGLES);

    const float ics = 1.0f/solid.cs;
    const float ich = 1.0f/solid.ch;
    rasterizeTri(v0, v1, v2, area, solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr);

    ctx->stopTimer(RC_TIMER_RASTERIZE_TRIANGLES);
}

Here is the call graph for this function:

void rcRasterizeTriangles	(	rcContext *	ctx,
		const float *	verts,
		const int	,
		const int *	tris,
		const unsigned char *	areas,
		const int	nt,
		rcHeightfield &	solid,
		const int	flagMergeThr
	)

Rasterizes an indexed triangle mesh into the specified heightfield.

Parameters

[in,out]	ctx	The build context to use during the operation.
[in]	verts	The vertices. [(x, y, z) * nv]
[in]	nv	The number of vertices.
[in]	tris	The triangle indices. [(vertA, vertB, vertC) * nt]
[in]	areas	The area id's of the triangles. [Limit: <= RC_WALKABLE_AREA] [Size: nt]
[in]	nt	The number of triangles.
[in,out]	solid	An initialized heightfield.
[in]	flagMergeThr	The distance where the walkable flag is favored over the non-walkable flag. [Limit: >= 0] [Units: vx]

Spans will only be added for triangles that overlap the heightfield grid.

See also

rcHeightfield

{
    rcAssert(ctx);

    ctx->startTimer(RC_TIMER_RASTERIZE_TRIANGLES);
    
    const float ics = 1.0f/solid.cs;
    const float ich = 1.0f/solid.ch;
    // Rasterize triangles.
    for (int i = 0; i < nt; ++i)
    {
        const float* v0 = &verts[tris[i*3+0]*3];
        const float* v1 = &verts[tris[i*3+1]*3];
        const float* v2 = &verts[tris[i*3+2]*3];
        // Rasterize.
        rasterizeTri(v0, v1, v2, areas[i], solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr);
    }
    
    ctx->stopTimer(RC_TIMER_RASTERIZE_TRIANGLES);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void rcRasterizeTriangles	(	rcContext *	ctx,
		const float *	verts,
		const int	,
		const unsigned short *	tris,
		const unsigned char *	areas,
		const int	nt,
		rcHeightfield &	solid,
		const int	flagMergeThr
	)

Rasterizes an indexed triangle mesh into the specified heightfield.

Parameters

[in,out]	ctx	The build context to use during the operation.
[in]	verts	The vertices. [(x, y, z) * nv]
[in]	nv	The number of vertices.
[in]	tris	The triangle indices. [(vertA, vertB, vertC) * nt]
[in]	areas	The area id's of the triangles. [Limit: <= RC_WALKABLE_AREA] [Size: nt]
[in]	nt	The number of triangles.
[in,out]	solid	An initialized heightfield.
[in]	flagMergeThr	The distance where the walkable flag is favored over the non-walkable flag. [Limit: >= 0] [Units: vx]

Spans will only be added for triangles that overlap the heightfield grid.

See also

rcHeightfield

{
    rcAssert(ctx);

    ctx->startTimer(RC_TIMER_RASTERIZE_TRIANGLES);
    
    const float ics = 1.0f/solid.cs;
    const float ich = 1.0f/solid.ch;
    // Rasterize triangles.
    for (int i = 0; i < nt; ++i)
    {
        const float* v0 = &verts[tris[i*3+0]*3];
        const float* v1 = &verts[tris[i*3+1]*3];
        const float* v2 = &verts[tris[i*3+2]*3];
        // Rasterize.
        rasterizeTri(v0, v1, v2, areas[i], solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr);
    }
    
    ctx->stopTimer(RC_TIMER_RASTERIZE_TRIANGLES);
}

Here is the call graph for this function:

void rcRasterizeTriangles	(	rcContext *	ctx,
		const float *	verts,
		const unsigned char *	areas,
		const int	nt,
		rcHeightfield &	solid,
		const int	flagMergeThr
	)

Rasterizes triangles into the specified heightfield.

Parameters

[in,out]	ctx	The build context to use during the operation.
[in]	verts	The triangle vertices. [(ax, ay, az, bx, by, bz, cx, by, cx) * nt]
[in]	areas	The area id's of the triangles. [Limit: <= RC_WALKABLE_AREA] [Size: nt]
[in]	nt	The number of triangles.
[in,out]	solid	An initialized heightfield.
[in]	flagMergeThr	The distance where the walkable flag is favored over the non-walkable flag. [Limit: >= 0] [Units: vx]

Spans will only be added for triangles that overlap the heightfield grid.

See also

rcHeightfield

{
    rcAssert(ctx);
    
    ctx->startTimer(RC_TIMER_RASTERIZE_TRIANGLES);
    
    const float ics = 1.0f/solid.cs;
    const float ich = 1.0f/solid.ch;
    // Rasterize triangles.
    for (int i = 0; i < nt; ++i)
    {
        const float* v0 = &verts[(i*3+0)*3];
        const float* v1 = &verts[(i*3+1)*3];
        const float* v2 = &verts[(i*3+2)*3];
        // Rasterize.
        rasterizeTri(v0, v1, v2, areas[i], solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr);
    }
    
    ctx->stopTimer(RC_TIMER_RASTERIZE_TRIANGLES);
}

Here is the call graph for this function:

void rcSetCon ( rcCompactSpan &  s, int  dir, int  i  )

inline

Sets the neighbor connection data for the specified direction.

Parameters

[in]	s	The span to update.
[in]	dir	The direction to set. [Limits: 0 <= value < 4]
[in]	i	The index of the neighbor span.

{
    const unsigned int shift = (unsigned int)dir*6;
    unsigned int con = s.con;
    s.con = (con & ~(0x3f << shift)) | (((unsigned int)i & 0x3f) << shift);
}

Here is the caller graph for this function:

template<class T >

T rcSqr ( T  a )

inline

Returns the square of the value.

Parameters

[in]

a

The value.

Returns

The square of the value.

{ return a*a; }

Here is the caller graph for this function:

float rcSqrt

(

float

x

)

Returns the square root of the value.

Parameters

[in]

x

The value.

Returns

The square root of the vlaue.

{
    return sqrtf(x);
}

Here is the caller graph for this function:

template<class T >

void rcSwap ( T &  a, T &  b  )

inline

Swaps the values of the two parameters.

Parameters

[in,out]	a	Value A
[in,out]	b	Value B

{ T t = a; a = b; b = t; }

Here is the caller graph for this function:

void rcVadd ( float *  dest, const float *  v1, const float *  v2  )

inline

Performs a vector addition. (v1 + v2)

Parameters

[out]	dest	The result vector. [(x, y, z)]
[in]	v1	The base vector. [(x, y, z)]
[in]	v2	The vector to add to v1. [(x, y, z)]

{
    dest[0] = v1[0]+v2[0];
    dest[1] = v1[1]+v2[1];
    dest[2] = v1[2]+v2[2];
}

Here is the caller graph for this function:

void rcVcopy ( float *  dest, const float *  v  )

inline

Performs a vector copy.

Parameters

[out]	dest	The result. [(x, y, z)]
[in]	v	The vector to copy. [(x, y, z)]

{
    dest[0] = v[0];
    dest[1] = v[1];
    dest[2] = v[2];
}

Here is the caller graph for this function:

void rcVcross ( float *  dest, const float *  v1, const float *  v2  )

inline

Derives the cross product of two vectors. (v1 x v2)

Parameters

[out]	dest	The cross product. [(x, y, z)]
[in]	v1	A Vector [(x, y, z)]
[in]	v2	A vector [(x, y, z)]

{
    dest[0] = v1[1]*v2[2] - v1[2]*v2[1];
    dest[1] = v1[2]*v2[0] - v1[0]*v2[2];
    dest[2] = v1[0]*v2[1] - v1[1]*v2[0];
}

Here is the caller graph for this function:

float rcVdist ( const float *  v1, const float *  v2  )

inline

Returns the distance between two points.

Parameters

[in]	v1	A point. [(x, y, z)]
[in]	v2	A point. [(x, y, z)]

Returns

The distance between the two points.

{
    float dx = v2[0] - v1[0];
    float dy = v2[1] - v1[1];
    float dz = v2[2] - v1[2];
    return rcSqrt(dx*dx + dy*dy + dz*dz);
}

Here is the call graph for this function:

float rcVdistSqr ( const float *  v1, const float *  v2  )

inline

Returns the square of the distance between two points.

Parameters

[in]	v1	A point. [(x, y, z)]
[in]	v2	A point. [(x, y, z)]

Returns

The square of the distance between the two points.

{
    float dx = v2[0] - v1[0];
    float dy = v2[1] - v1[1];
    float dz = v2[2] - v1[2];
    return dx*dx + dy*dy + dz*dz;
}

float rcVdot ( const float *  v1, const float *  v2  )

inline

Derives the dot product of two vectors. (v1 . v2)

Parameters

[in]	v1	A Vector [(x, y, z)]
[in]	v2	A vector [(x, y, z)]

Returns

The dot product.

{
    return v1[0]*v2[0] + v1[1]*v2[1] + v1[2]*v2[2];
}

void rcVmad ( float *  dest, const float *  v1, const float *  v2, const float  s  )

inline

Performs a scaled vector addition. (v1 + (v2 * s))

Parameters

[out]	dest	The result vector. [(x, y, z)]
[in]	v1	The base vector. [(x, y, z)]
[in]	v2	The vector to scale and add to v1. [(x, y, z)]
[in]	s	The amount to scale v2 by before adding to v1.

{
    dest[0] = v1[0]+v2[0]*s;
    dest[1] = v1[1]+v2[1]*s;
    dest[2] = v1[2]+v2[2]*s;
}

void rcVmax ( float *  mx, const float *  v  )

inline

Selects the maximum value of each element from the specified vectors.

Parameters

[in,out]	mx	A vector. (Will be updated with the result.) [(x, y, z)]
[in]	v	A vector. [(x, y, z)]

{
    mx[0] = rcMax(mx[0], v[0]);
    mx[1] = rcMax(mx[1], v[1]);
    mx[2] = rcMax(mx[2], v[2]);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void rcVmin ( float *  mn, const float *  v  )

inline

Selects the minimum value of each element from the specified vectors.

Parameters

[in,out]	mn	A vector. (Will be updated with the result.) [(x, y, z)]
[in]	v	A vector. [(x, y, z)]

{
    mn[0] = rcMin(mn[0], v[0]);
    mn[1] = rcMin(mn[1], v[1]);
    mn[2] = rcMin(mn[2], v[2]);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void rcVnormalize ( float *  v )

inline

Normalizes the vector.

Parameters

[in,out]

v

The vector to normalize. [(x, y, z)]

{
    float d = 1.0f / rcSqrt(rcSqr(v[0]) + rcSqr(v[1]) + rcSqr(v[2]));
    v[0] *= d;
    v[1] *= d;
    v[2] *= d;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void rcVsub ( float *  dest, const float *  v1, const float *  v2  )

inline

Performs a vector subtraction. (v1 - v2)

Parameters

[out]	dest	The result vector. [(x, y, z)]
[in]	v1	The base vector. [(x, y, z)]
[in]	v2	The vector to subtract from v1. [(x, y, z)]

{
    dest[0] = v1[0]-v2[0];
    dest[1] = v1[1]-v2[1];
    dest[2] = v1[2]-v2[2];
}

Here is the caller graph for this function:

Variable Documentation

const int RC_AREA_BORDER = 0x20000

static

Area border flag. If a region ID has this bit set, then the associated element lies on the border of an area. (Used during the region and contour build process.)

See also

rcCompactSpan::reg, rcContour::verts, rcContour::rverts

const unsigned short RC_BORDER_REG = 0x8000

static

Heighfield border flag. If a heightfield region ID has this bit set, then the region is a border region and its spans are considered unwalkable. (Used during the region and contour build process.)

See also

rcCompactSpan::reg

const int RC_BORDER_VERTEX = 0x10000

static

Border vertex flag. If a region ID has this bit set, then the associated element lies on a tile border. If a contour vertex's region ID has this bit set, the vertex will later be removed in order to match the segments and vertices at tile boundaries. (Used during the build process.)

See also

rcCompactSpan::reg, rcContour::verts, rcContour::rverts

const int RC_CONTOUR_REG_MASK = 0xffff

static

Applied to the region id field of contour vertices in order to extract the region id. The region id field of a vertex may have several flags applied to it. So the fields value can't be used directly.

See also

rcContour::verts, rcContour::rverts

const unsigned short RC_MESH_NULL_IDX = 0xffff

static

An value which indicates an invalid index within a mesh.

Note

This does not necessarily indicate an error.

See also

rcPolyMesh::polys

const int RC_NOT_CONNECTED = 0x3f

static

The value returned by rcGetCon if the specified direction is not connected to another span. (Has no neighbor.)

const unsigned char RC_NULL_AREA = 0

static

Represents the null area. When a data element is given this value it is considered to no longer be assigned to a usable area. (E.g. It is unwalkable.)

const float RC_PI = 3.14159265f

static

The value of PI used by Recast.

const int RC_SPAN_HEIGHT_BITS = 16

static

Defines the number of bits allocated to rcSpan::smin and rcSpan::smax.

const int RC_SPAN_MAX_HEIGHT = (1<<RC_SPAN_HEIGHT_BITS)-1

static

Defines the maximum value for rcSpan::smin and rcSpan::smax.

const int RC_SPANS_PER_POOL = 2048

static

The number of spans allocated per span spool.

See also

rcSpanPool

const unsigned char RC_WALKABLE_AREA = 63

static

The default area id used to indicate a walkable polygon. This is also the maximum allowed area id, and the only non-null area id recognized by some steps in the build process.