Recast.cpp File Reference

#include <float.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>
#include "Recast.h"
#include "RecastAlloc.h"
#include "RecastAssert.h"

Include dependency graph for Recast.cpp:

Macros
#define	_USE_MATH_DEFINES

Functions
float	rcSqrt (float x)
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)
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)
static void	calcTriNormal (const float *v0, const float *v1, const float *v2, float *norm)
void	rcMarkWalkableTriangles (rcContext *ctx, const float walkableSlopeAngle, const float *verts, int, const int *tris, int nt, unsigned char *areas)
void	rcClearUnwalkableTriangles (rcContext *ctx, const float walkableSlopeAngle, const float *verts, int, const int *tris, int nt, unsigned char *areas)
int	rcGetHeightFieldSpanCount (rcContext *ctx, rcHeightfield &hf)
bool	rcBuildCompactHeightfield (rcContext *ctx, const int walkableHeight, const int walkableClimb, rcHeightfield &hf, rcCompactHeightfield &chf)

Macro Definition Documentation

#define _USE_MATH_DEFINES

Function Documentation

static void calcTriNormal ( const float *  v0, const float *  v1, const float *  v2, float *  norm  )

static

{
 float e0[3], e1[3];
 rcVsub(e0, v1, v0);
 rcVsub(e1, v2, v0);
 rcVcross(norm, e0, e1);
 rcVnormalize(norm);
}

Here is the call graph for this function:

Here is the caller 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
	)

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:

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:

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

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 rcCreateHeightfield	(	rcContext *	ctx,
		rcHeightfield &	hf,
		int	width,
		int	height,
		const float *	bmin,
		const float *	bmax,
		float	cs,
		float	ch
	)

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:

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 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:

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

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:

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: