Detour

Classes
struct	dtPoly
struct	dtMeshHeader
struct	dtMeshTile
struct	dtNavMeshParams
class	dtNavMesh
struct	dtNavMeshCreateParams
class	dtQueryFilter
struct	dtRaycastHit
class	dtNavMeshQuery
struct	dtNavMeshQuery::dtQueryData

Typedefs
typedef uint64_d	dtPolyRef
typedef uint64_d	dtTileRef

Functions
dtNavMesh *	dtAllocNavMesh ()
void	dtFreeNavMesh (dtNavMesh *navmesh)
bool	dtCreateNavMeshData (dtNavMeshCreateParams *params, unsigned char **outData, int *outDataSize)
dtNavMeshQuery *	dtAllocNavMeshQuery ()
void	dtFreeNavMeshQuery (dtNavMeshQuery *query)

Variables
static const int	DT_VERTS_PER_POLYGON = 6
static const int	DT_MAX_AREAS = 64

Detailed Description

Members in this module are used to create, manipulate, and query navigation meshes.

Note

This is a summary list of members. Use the index or search feature to find minor members.

Members in this module are wrappers around the standard math library

Typedef Documentation

dtPolyRef

A handle to a polygon within a navigation mesh tile.

Polygon references are subject to the same invalidate/preserve/restore rules that apply to dtTileRef's. If the dtTileRef for the polygon's tile changes, the polygon reference becomes invalid.

Changing a polygon's flags, area id, etc. does not impact its polygon reference.

dtTileRef

A handle to a tile within a navigation mesh.

The following changes will invalidate a tile reference:

• The referenced tile has been removed from the navigation mesh.
• The navigation mesh has been initialized using a different set of dtNavMeshParams.

A tile reference is preserved/restored if the tile is added to a navigation mesh initialized with the original dtNavMeshParams and is added at the original reference location. (E.g. The lastRef parameter is used with dtNavMesh::addTile.)

Basically, if the storage structure of a tile changes, its associated tile reference changes.

Function Documentation

dtNavMesh* dtAllocNavMesh

(

)

Allocates a navigation mesh object using the Detour allocator.

Returns

A navigation mesh that is ready for initialization, or null on failure.

{
 void* mem = dtAlloc(sizeof(dtNavMesh), DT_ALLOC_PERM);
 if (!mem) return 0;
 return new(mem) dtNavMesh;
}

Here is the call graph for this function:

Here is the caller graph for this function:

dtNavMeshQuery* dtAllocNavMeshQuery

(

)

Allocates a query object using the Detour allocator.

Returns

An allocated query object, or null on failure.

{
 void* mem = dtAlloc(sizeof(dtNavMeshQuery), DT_ALLOC_PERM);
 if (!mem) return 0;
 return new(mem) dtNavMeshQuery;
}

Here is the call graph for this function:

Here is the caller graph for this function:

bool dtCreateNavMeshData	(	dtNavMeshCreateParams *	params,
		unsigned char **	outData,
		int *	outDataSize
	)

Builds navigation mesh tile data from the provided tile creation data.

Parameters

[in]	params	Tile creation data.
[out]	outData	The resulting tile data.
[out]	outDataSize	The size of the tile data array.

Returns

True if the tile data was successfully created.

The output data array is allocated using the detour allocator (dtAlloc()). The method used to free the memory will be determined by how the tile is added to the navigation mesh.

See also

dtNavMesh, dtNavMesh::addTile()

{
 if (params->nvp > DT_VERTS_PER_POLYGON)
 return false;
 if (params->vertCount >= 0xffff)
 return false;
 if (!params->vertCount || !params->verts)
 return false;
 if (!params->polyCount || !params->polys)
 return false;

 const int nvp = params->nvp;
 
 // Classify off-mesh connection points. We store only the connections
 // whose start point is inside the tile.
 unsigned char* offMeshConClass = 0;
 int storedOffMeshConCount = 0;
 int offMeshConLinkCount = 0;
 
 if (params->offMeshConCount > 0)
 {
 offMeshConClass = (unsigned char*)dtAlloc(sizeof(unsigned char)*params->offMeshConCount*2, DT_ALLOC_TEMP);
 if (!offMeshConClass)
 return false;

 // Find tight heigh bounds, used for culling out off-mesh start locations.
 float hmin = FLT_MAX;
 float hmax = -FLT_MAX;
 
 if (params->detailVerts && params->detailVertsCount)
 {
 for (int i = 0; i < params->detailVertsCount; ++i)
 {
 const float h = params->detailVerts[i*3+1];
 hmin = dtMin(hmin,h);
 hmax = dtMax(hmax,h);
 }
 }
 else
 {
 for (int i = 0; i < params->vertCount; ++i)
 {
 const unsigned short* iv = &params->verts[i*3];
 const float h = params->bmin[1] + iv[1] * params->ch;
 hmin = dtMin(hmin,h);
 hmax = dtMax(hmax,h);
 }
 }
 hmin -= params->walkableClimb;
 hmax += params->walkableClimb;
 float bmin[3], bmax[3];
 dtVcopy(bmin, params->bmin);
 dtVcopy(bmax, params->bmax);
 bmin[1] = hmin;
 bmax[1] = hmax;

 for (int i = 0; i < params->offMeshConCount; ++i)
 {
 const float* p0 = &params->offMeshConVerts[(i*2+0)*3];
 const float* p1 = &params->offMeshConVerts[(i*2+1)*3];
 offMeshConClass[i*2+0] = classifyOffMeshPoint(p0, bmin, bmax);
 offMeshConClass[i*2+1] = classifyOffMeshPoint(p1, bmin, bmax);

 // Zero out off-mesh start positions which are not even potentially touching the mesh.
 if (offMeshConClass[i*2+0] == 0xff)
 {
 if (p0[1] < bmin[1] || p0[1] > bmax[1])
 offMeshConClass[i*2+0] = 0;
 }

 // Cound how many links should be allocated for off-mesh connections.
 if (offMeshConClass[i*2+0] == 0xff)
 offMeshConLinkCount++;
 if (offMeshConClass[i*2+1] == 0xff)
 offMeshConLinkCount++;

 if (offMeshConClass[i*2+0] == 0xff)
 storedOffMeshConCount++;
 }
 }
 
 // Off-mesh connectionss are stored as polygons, adjust values.
 const int totPolyCount = params->polyCount + storedOffMeshConCount;
 const int totVertCount = params->vertCount + storedOffMeshConCount*2;
 
 // Find portal edges which are at tile borders.
 int edgeCount = 0;
 int portalCount = 0;
 for (int i = 0; i < params->polyCount; ++i)
 {
 const unsigned short* p = &params->polys[i*2*nvp];
 for (int j = 0; j < nvp; ++j)
 {
 if (p[j] == MESH_NULL_IDX) break;
 edgeCount++;
 
 if (p[nvp+j] & 0x8000)
 {
 unsigned short dir = p[nvp+j] & 0xf;
 if (dir != 0xf)
 portalCount++;
 }
 }
 }

 const int maxLinkCount = edgeCount + portalCount*2 + offMeshConLinkCount*2;
 
 // Find unique detail vertices.
 int uniqueDetailVertCount = 0;
 int detailTriCount = 0;
 if (params->detailMeshes)
 {
 // Has detail mesh, count unique detail vertex count and use input detail tri count.
 detailTriCount = params->detailTriCount;
 for (int i = 0; i < params->polyCount; ++i)
 {
 const unsigned short* p = &params->polys[i*nvp*2];
 int ndv = params->detailMeshes[i*4+1];
 int nv = 0;
 for (int j = 0; j < nvp; ++j)
 {
 if (p[j] == MESH_NULL_IDX) break;
 nv++;
 }
 ndv -= nv;
 uniqueDetailVertCount += ndv;
 }
 }
 else
 {
 // No input detail mesh, build detail mesh from nav polys.
 uniqueDetailVertCount = 0; // No extra detail verts.
 detailTriCount = 0;
 for (int i = 0; i < params->polyCount; ++i)
 {
 const unsigned short* p = &params->polys[i*nvp*2];
 int nv = 0;
 for (int j = 0; j < nvp; ++j)
 {
 if (p[j] == MESH_NULL_IDX) break;
 nv++;
 }
 detailTriCount += nv-2;
 }
 }
 
 // Calculate data size
 const int headerSize = dtAlign4(sizeof(dtMeshHeader));
 const int vertsSize = dtAlign4(sizeof(float)*3*totVertCount);
 const int polysSize = dtAlign4(sizeof(dtPoly)*totPolyCount);
 const int linksSize = dtAlign4(sizeof(dtLink)*maxLinkCount);
 const int detailMeshesSize = dtAlign4(sizeof(dtPolyDetail)*params->polyCount);
 const int detailVertsSize = dtAlign4(sizeof(float)*3*uniqueDetailVertCount);
 const int detailTrisSize = dtAlign4(sizeof(unsigned char)*4*detailTriCount);
 const int bvTreeSize = params->buildBvTree ? dtAlign4(sizeof(dtBVNode)*params->polyCount*2) : 0;
 const int offMeshConsSize = dtAlign4(sizeof(dtOffMeshConnection)*storedOffMeshConCount);
 
 const int dataSize = headerSize + vertsSize + polysSize + linksSize +
 detailMeshesSize + detailVertsSize + detailTrisSize +
 bvTreeSize + offMeshConsSize;
 
 unsigned char* data = (unsigned char*)dtAlloc(sizeof(unsigned char)*dataSize, DT_ALLOC_PERM);
 if (!data)
 {
 dtFree(offMeshConClass);
 return false;
 }
 memset(data, 0, dataSize);
 
 unsigned char* d = data;
 dtMeshHeader* header = (dtMeshHeader*)d; d += headerSize;
 float* navVerts = (float*)d; d += vertsSize;
 dtPoly* navPolys = (dtPoly*)d; d += polysSize;
 d += linksSize;
 dtPolyDetail* navDMeshes = (dtPolyDetail*)d; d += detailMeshesSize;
 float* navDVerts = (float*)d; d += detailVertsSize;
 unsigned char* navDTris = (unsigned char*)d; d += detailTrisSize;
 dtBVNode* navBvtree = (dtBVNode*)d; d += bvTreeSize;
 dtOffMeshConnection* offMeshCons = (dtOffMeshConnection*)d; d += offMeshConsSize;
 
 
 // Store header
 header->magic = DT_NAVMESH_MAGIC;
 header->version = DT_NAVMESH_VERSION;
 header->x = params->tileX;
 header->y = params->tileY;
 header->layer = params->tileLayer;
 header->userId = params->userId;
 header->polyCount = totPolyCount;
 header->vertCount = totVertCount;
 header->maxLinkCount = maxLinkCount;
 dtVcopy(header->bmin, params->bmin);
 dtVcopy(header->bmax, params->bmax);
 header->detailMeshCount = params->polyCount;
 header->detailVertCount = uniqueDetailVertCount;
 header->detailTriCount = detailTriCount;
 header->bvQuantFactor = 1.0f / params->cs;
 header->offMeshBase = params->polyCount;
 header->walkableHeight = params->walkableHeight;
 header->walkableRadius = params->walkableRadius;
 header->walkableClimb = params->walkableClimb;
 header->offMeshConCount = storedOffMeshConCount;
 header->bvNodeCount = params->buildBvTree ? params->polyCount*2 : 0;
 
 const int offMeshVertsBase = params->vertCount;
 const int offMeshPolyBase = params->polyCount;
 
 // Store vertices
 // Mesh vertices
 for (int i = 0; i < params->vertCount; ++i)
 {
 const unsigned short* iv = &params->verts[i*3];
 float* v = &navVerts[i*3];
 v[0] = params->bmin[0] + iv[0] * params->cs;
 v[1] = params->bmin[1] + iv[1] * params->ch;
 v[2] = params->bmin[2] + iv[2] * params->cs;
 }
 // Off-mesh link vertices.
 int n = 0;
 for (int i = 0; i < params->offMeshConCount; ++i)
 {
 // Only store connections which start from this tile.
 if (offMeshConClass[i*2+0] == 0xff)
 {
 const float* linkv = &params->offMeshConVerts[i*2*3];
 float* v = &navVerts[(offMeshVertsBase + n*2)*3];
 dtVcopy(&v[0], &linkv[0]);
 dtVcopy(&v[3], &linkv[3]);
 n++;
 }
 }
 
 // Store polygons
 // Mesh polys
 const unsigned short* src = params->polys;
 for (int i = 0; i < params->polyCount; ++i)
 {
 dtPoly* p = &navPolys[i];
 p->vertCount = 0;
 p->flags = params->polyFlags[i];
 p->setArea(params->polyAreas[i]);
 p->setType(DT_POLYTYPE_GROUND);
 for (int j = 0; j < nvp; ++j)
 {
 if (src[j] == MESH_NULL_IDX) break;
 p->verts[j] = src[j];
 if (src[nvp+j] & 0x8000)
 {
 // Border or portal edge.
 unsigned short dir = src[nvp+j] & 0xf;
 if (dir == 0xf) // Border
 p->neis[j] = 0;
 else if (dir == 0) // Portal x-
 p->neis[j] = DT_EXT_LINK | 4;
 else if (dir == 1) // Portal z+
 p->neis[j] = DT_EXT_LINK | 2;
 else if (dir == 2) // Portal x+
 p->neis[j] = DT_EXT_LINK | 0;
 else if (dir == 3) // Portal z-
 p->neis[j] = DT_EXT_LINK | 6;
 }
 else
 {
 // Normal connection
 p->neis[j] = src[nvp+j]+1;
 }
 
 p->vertCount++;
 }
 src += nvp*2;
 }
 // Off-mesh connection vertices.
 n = 0;
 for (int i = 0; i < params->offMeshConCount; ++i)
 {
 // Only store connections which start from this tile.
 if (offMeshConClass[i*2+0] == 0xff)
 {
 dtPoly* p = &navPolys[offMeshPolyBase+n];
 p->vertCount = 2;
 p->verts[0] = (unsigned short)(offMeshVertsBase + n*2+0);
 p->verts[1] = (unsigned short)(offMeshVertsBase + n*2+1);
 p->flags = params->offMeshConFlags[i];
 p->setArea(params->offMeshConAreas[i]);
 p->setType(DT_POLYTYPE_OFFMESH_CONNECTION);
 n++;
 }
 }

 // Store detail meshes and vertices.
 // The nav polygon vertices are stored as the first vertices on each mesh.
 // We compress the mesh data by skipping them and using the navmesh coordinates.
 if (params->detailMeshes)
 {
 unsigned short vbase = 0;
 for (int i = 0; i < params->polyCount; ++i)
 {
 dtPolyDetail& dtl = navDMeshes[i];
 const int vb = (int)params->detailMeshes[i*4+0];
 const int ndv = (int)params->detailMeshes[i*4+1];
 const int nv = navPolys[i].vertCount;
 dtl.vertBase = (unsigned int)vbase;
 dtl.vertCount = (unsigned char)(ndv-nv);
 dtl.triBase = (unsigned int)params->detailMeshes[i*4+2];
 dtl.triCount = (unsigned char)params->detailMeshes[i*4+3];
 // Copy vertices except the first 'nv' verts which are equal to nav poly verts.
 if (ndv-nv)
 {
 memcpy(&navDVerts[vbase*3], &params->detailVerts[(vb+nv)*3], sizeof(float)*3*(ndv-nv));
 vbase += (unsigned short)(ndv-nv);
 }
 }
 // Store triangles.
 memcpy(navDTris, params->detailTris, sizeof(unsigned char)*4*params->detailTriCount);
 }
 else
 {
 // Create dummy detail mesh by triangulating polys.
 int tbase = 0;
 for (int i = 0; i < params->polyCount; ++i)
 {
 dtPolyDetail& dtl = navDMeshes[i];
 const int nv = navPolys[i].vertCount;
 dtl.vertBase = 0;
 dtl.vertCount = 0;
 dtl.triBase = (unsigned int)tbase;
 dtl.triCount = (unsigned char)(nv-2);
 // Triangulate polygon (local indices).
 for (int j = 2; j < nv; ++j)
 {
 unsigned char* t = &navDTris[tbase*4];
 t[0] = 0;
 t[1] = (unsigned char)(j-1);
 t[2] = (unsigned char)j;
 // Bit for each edge that belongs to poly boundary.
 t[3] = (1<<2);
 if (j == 2) t[3] |= (1<<0);
 if (j == nv-1) t[3] |= (1<<4);
 tbase++;
 }
 }
 }

 // Store and create BVtree.
 // TODO: take detail mesh into account! use byte per bbox extent?
 if (params->buildBvTree)
 {
 createBVTree(params->verts, params->vertCount, params->polys, params->polyCount,
 nvp, params->cs, params->ch, params->polyCount*2, navBvtree);
 }
 
 // Store Off-Mesh connections.
 n = 0;
 for (int i = 0; i < params->offMeshConCount; ++i)
 {
 // Only store connections which start from this tile.
 if (offMeshConClass[i*2+0] == 0xff)
 {
 dtOffMeshConnection* con = &offMeshCons[n];
 con->poly = (unsigned short)(offMeshPolyBase + n);
 // Copy connection end-points.
 const float* endPts = &params->offMeshConVerts[i*2*3];
 dtVcopy(&con->pos[0], &endPts[0]);
 dtVcopy(&con->pos[3], &endPts[3]);
 con->rad = params->offMeshConRad[i];
 con->flags = params->offMeshConDir[i] ? DT_OFFMESH_CON_BIDIR : 0;
 con->side = offMeshConClass[i*2+1];
 if (params->offMeshConUserID)
 con->userId = params->offMeshConUserID[i];
 n++;
 }
 }
 
 dtFree(offMeshConClass);
 
 *outData = data;
 *outDataSize = dataSize;
 
 return true;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void dtFreeNavMesh

(

dtNavMesh *

navmesh

)

Frees the specified navigation mesh object using the Detour allocator.

Parameters

[in]

navmesh

A navigation mesh allocated using dtAllocNavMesh

This function will only free the memory for tiles with the DT_TILE_FREE_DATA flag set.

{
    if (!navmesh) return;
    navmesh->~dtNavMesh();
    dtFree(navmesh);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void dtFreeNavMeshQuery

(

dtNavMeshQuery *

query

)

Frees the specified query object using the Detour allocator.

Parameters

[in]

query

A query object allocated using dtAllocNavMeshQuery

{
    if (!navmesh) return;
    navmesh->~dtNavMeshQuery();
    dtFree(navmesh);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

const int DT_MAX_AREAS = 64

static

The maximum number of user defined area ids.

const int DT_VERTS_PER_POLYGON = 6

static

The maximum number of vertices per navigation polygon.