DetourNavMeshBuilder.cpp File Reference

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <float.h>
#include "DetourNavMesh.h"
#include "DetourCommon.h"
#include "DetourMath.h"
#include "DetourNavMeshBuilder.h"
#include "DetourAlloc.h"
#include "DetourAssert.h"

Include dependency graph for DetourNavMeshBuilder.cpp:

Classes
struct	BVItem

Functions
static int	compareItemX (const void *va, const void *vb)
static int	compareItemY (const void *va, const void *vb)
static int	compareItemZ (const void *va, const void *vb)
static void	calcExtends (BVItem *items, const int, const int imin, const int imax, unsigned short *bmin, unsigned short *bmax)
int	longestAxis (unsigned short x, unsigned short y, unsigned short z)
static void	subdivide (BVItem *items, int nitems, int imin, int imax, int &curNode, dtBVNode *nodes)
static int	createBVTree (const unsigned short *verts, const int, const unsigned short *polys, const int npolys, const int nvp, const float cs, const float ch, const int, dtBVNode *nodes)
static unsigned char	classifyOffMeshPoint (const float *pt, const float *bmin, const float *bmax)
bool	dtCreateNavMeshData (dtNavMeshCreateParams *params, unsigned char **outData, int *outDataSize)
bool	dtNavMeshHeaderSwapEndian (unsigned char *data, const int)
bool	dtNavMeshDataSwapEndian (unsigned char *data, const int)

Variables
static unsigned short	MESH_NULL_IDX = 0xffff

Function Documentation

static void calcExtends ( BVItem *  items, const int  , const int  imin, const int  imax, unsigned short *  bmin, unsigned short *  bmax  )

static

{
 bmin[0] = items[imin].bmin[0];
 bmin[1] = items[imin].bmin[1];
 bmin[2] = items[imin].bmin[2];
 
 bmax[0] = items[imin].bmax[0];
 bmax[1] = items[imin].bmax[1];
 bmax[2] = items[imin].bmax[2];
 
 for (int i = imin+1; i < imax; ++i)
 {
 const BVItem& it = items[i];
 if (it.bmin[0] < bmin[0]) bmin[0] = it.bmin[0];
 if (it.bmin[1] < bmin[1]) bmin[1] = it.bmin[1];
 if (it.bmin[2] < bmin[2]) bmin[2] = it.bmin[2];
 
 if (it.bmax[0] > bmax[0]) bmax[0] = it.bmax[0];
 if (it.bmax[1] > bmax[1]) bmax[1] = it.bmax[1];
 if (it.bmax[2] > bmax[2]) bmax[2] = it.bmax[2];
 }
}

Here is the caller graph for this function:

static unsigned char classifyOffMeshPoint ( const float *  pt, const float *  bmin, const float *  bmax  )

static

{
 static const unsigned char XP = 1<<0;
 static const unsigned char ZP = 1<<1;
 static const unsigned char XM = 1<<2;
 static const unsigned char ZM = 1<<3; 

 unsigned char outcode = 0; 
 outcode |= (pt[0] >= bmax[0]) ? XP : 0;
 outcode |= (pt[2] >= bmax[2]) ? ZP : 0;
 outcode |= (pt[0] < bmin[0]) ? XM : 0;
 outcode |= (pt[2] < bmin[2]) ? ZM : 0;

 switch (outcode)
 {
 case XP: return 0;
 case XP|ZP: return 1;
 case ZP: return 2;
 case XM|ZP: return 3;
 case XM: return 4;
 case XM|ZM: return 5;
 case ZM: return 6;
 case XP|ZM: return 7;
 };

 return 0xff; 
}

Here is the caller graph for this function:

static int compareItemX ( const void *  va, const void *  vb  )

static

{
 const BVItem* a = (const BVItem*)va;
 const BVItem* b = (const BVItem*)vb;
 if (a->bmin[0] < b->bmin[0])
 return -1;
 if (a->bmin[0] > b->bmin[0])
 return 1;
 return 0;
}

Here is the caller graph for this function:

static int compareItemY ( const void *  va, const void *  vb  )

static

{
 const BVItem* a = (const BVItem*)va;
 const BVItem* b = (const BVItem*)vb;
 if (a->bmin[1] < b->bmin[1])
 return -1;
 if (a->bmin[1] > b->bmin[1])
 return 1;
 return 0;
}

Here is the caller graph for this function:

static int compareItemZ ( const void *  va, const void *  vb  )

static

{
 const BVItem* a = (const BVItem*)va;
 const BVItem* b = (const BVItem*)vb;
 if (a->bmin[2] < b->bmin[2])
 return -1;
 if (a->bmin[2] > b->bmin[2])
 return 1;
 return 0;
}

Here is the caller graph for this function:

static int createBVTree ( const unsigned short *  verts, const int  , const unsigned short *  polys, const int  npolys, const int  nvp, const float  cs, const float  ch, const int  , dtBVNode *  nodes  )

static

{
 // Build tree
 BVItem* items = (BVItem*)dtAlloc(sizeof(BVItem)*npolys, DT_ALLOC_TEMP);
 for (int i = 0; i < npolys; i++)
 {
 BVItem& it = items[i];
 it.i = i;
 // Calc polygon bounds.
 const unsigned short* p = &polys[i*nvp*2];
 it.bmin[0] = it.bmax[0] = verts[p[0]*3+0];
 it.bmin[1] = it.bmax[1] = verts[p[0]*3+1];
 it.bmin[2] = it.bmax[2] = verts[p[0]*3+2];
 
 for (int j = 1; j < nvp; ++j)
 {
 if (p[j] == MESH_NULL_IDX) break;
 unsigned short x = verts[p[j]*3+0];
 unsigned short y = verts[p[j]*3+1];
 unsigned short z = verts[p[j]*3+2];
 
 if (x < it.bmin[0]) it.bmin[0] = x;
 if (y < it.bmin[1]) it.bmin[1] = y;
 if (z < it.bmin[2]) it.bmin[2] = z;
 
 if (x > it.bmax[0]) it.bmax[0] = x;
 if (y > it.bmax[1]) it.bmax[1] = y;
 if (z > it.bmax[2]) it.bmax[2] = z;
 }
 // Remap y
 it.bmin[1] = (unsigned short)dtMathFloorf((float)it.bmin[1]*ch/cs);
 it.bmax[1] = (unsigned short)dtMathCeilf((float)it.bmax[1]*ch/cs);
 }
 
 int curNode = 0;
 subdivide(items, npolys, 0, npolys, curNode, nodes);
 
 dtFree(items);
 
 return curNode;
}

Here is the call graph for this function:

Here is the caller graph for this function:

bool dtNavMeshDataSwapEndian	(	unsigned char *	data,
		const int
	)

Warning

This function assumes that the header is in the correct endianess already. Call dtNavMeshHeaderSwapEndian() first on the data if the data is expected to be in wrong endianess to start with. Call dtNavMeshHeaderSwapEndian() after the data has been swapped if converting from native to foreign endianess.

{
 // Make sure the data is in right format.
 dtMeshHeader* header = (dtMeshHeader*)data;
 if (header->magic != DT_NAVMESH_MAGIC)
 return false;
 if (header->version != DT_NAVMESH_VERSION)
 return false;
 
 // Patch header pointers.
 const int headerSize = dtAlign4(sizeof(dtMeshHeader));
 const int vertsSize = dtAlign4(sizeof(float)*3*header->vertCount);
 const int polysSize = dtAlign4(sizeof(dtPoly)*header->polyCount);
 const int linksSize = dtAlign4(sizeof(dtLink)*(header->maxLinkCount));
 const int detailMeshesSize = dtAlign4(sizeof(dtPolyDetail)*header->detailMeshCount);
 const int detailVertsSize = dtAlign4(sizeof(float)*3*header->detailVertCount);
 const int detailTrisSize = dtAlign4(sizeof(unsigned char)*4*header->detailTriCount);
 const int bvtreeSize = dtAlign4(sizeof(dtBVNode)*header->bvNodeCount);
 const int offMeshLinksSize = dtAlign4(sizeof(dtOffMeshConnection)*header->offMeshConCount);
 
 unsigned char* d = data + headerSize;
 float* verts = (float*)d; d += vertsSize;
 dtPoly* polys = (dtPoly*)d; d += polysSize;
 /*dtLink* links = (dtLink*)d;*/ d += linksSize;
 dtPolyDetail* detailMeshes = (dtPolyDetail*)d; d += detailMeshesSize;
 float* detailVerts = (float*)d; d += detailVertsSize;
 /*unsigned char* detailTris = (unsigned char*)d;*/ d += detailTrisSize;
 dtBVNode* bvTree = (dtBVNode*)d; d += bvtreeSize;
 dtOffMeshConnection* offMeshCons = (dtOffMeshConnection*)d; d += offMeshLinksSize;
 
 // Vertices
 for (int i = 0; i < header->vertCount*3; ++i)
 {
 dtSwapEndian(&verts[i]);
 }

 // Polys
 for (int i = 0; i < header->polyCount; ++i)
 {
 dtPoly* p = &polys[i];
 // poly->firstLink is update when tile is added, no need to swap.
 for (int j = 0; j < DT_VERTS_PER_POLYGON; ++j)
 {
 dtSwapEndian(&p->verts[j]);
 dtSwapEndian(&p->neis[j]);
 }
 dtSwapEndian(&p->flags);
 }

 // Links are rebuild when tile is added, no need to swap.

 // Detail meshes
 for (int i = 0; i < header->detailMeshCount; ++i)
 {
 dtPolyDetail* pd = &detailMeshes[i];
 dtSwapEndian(&pd->vertBase);
 dtSwapEndian(&pd->triBase);
 }
 
 // Detail verts
 for (int i = 0; i < header->detailVertCount*3; ++i)
 {
 dtSwapEndian(&detailVerts[i]);
 }

 // BV-tree
 for (int i = 0; i < header->bvNodeCount; ++i)
 {
 dtBVNode* node = &bvTree[i];
 for (int j = 0; j < 3; ++j)
 {
 dtSwapEndian(&node->bmin[j]);
 dtSwapEndian(&node->bmax[j]);
 }
 dtSwapEndian(&node->i);
 }

 // Off-mesh Connections.
 for (int i = 0; i < header->offMeshConCount; ++i)
 {
 dtOffMeshConnection* con = &offMeshCons[i];
 for (int j = 0; j < 6; ++j)
 dtSwapEndian(&con->pos[j]);
 dtSwapEndian(&con->rad);
 dtSwapEndian(&con->poly);
 }
 
 return true;
}

Here is the call graph for this function:

bool dtNavMeshHeaderSwapEndian	(	unsigned char *	data,
		const int	dataSize
	)

Swaps the endianess of the tile data's header (dtMeshHeader).

Parameters

[in,out]	data	The tile data array.
[in]	dataSize	The size of the data array.

{
 dtMeshHeader* header = (dtMeshHeader*)data;
 
 int swappedMagic = DT_NAVMESH_MAGIC;
 int swappedVersion = DT_NAVMESH_VERSION;
 dtSwapEndian(&swappedMagic);
 dtSwapEndian(&swappedVersion);
 
 if ((header->magic != DT_NAVMESH_MAGIC || header->version != DT_NAVMESH_VERSION) &&
 (header->magic != swappedMagic || header->version != swappedVersion))
 {
 return false;
 }
 
 dtSwapEndian(&header->magic);
 dtSwapEndian(&header->version);
 dtSwapEndian(&header->x);
 dtSwapEndian(&header->y);
 dtSwapEndian(&header->layer);
 dtSwapEndian(&header->userId);
 dtSwapEndian(&header->polyCount);
 dtSwapEndian(&header->vertCount);
 dtSwapEndian(&header->maxLinkCount);
 dtSwapEndian(&header->detailMeshCount);
 dtSwapEndian(&header->detailVertCount);
 dtSwapEndian(&header->detailTriCount);
 dtSwapEndian(&header->bvNodeCount);
 dtSwapEndian(&header->offMeshConCount);
 dtSwapEndian(&header->offMeshBase);
 dtSwapEndian(&header->walkableHeight);
 dtSwapEndian(&header->walkableRadius);
 dtSwapEndian(&header->walkableClimb);
 dtSwapEndian(&header->bmin[0]);
 dtSwapEndian(&header->bmin[1]);
 dtSwapEndian(&header->bmin[2]);
 dtSwapEndian(&header->bmax[0]);
 dtSwapEndian(&header->bmax[1]);
 dtSwapEndian(&header->bmax[2]);
 dtSwapEndian(&header->bvQuantFactor);

 // Freelist index and pointers are updated when tile is added, no need to swap.

 return true;
}

Here is the call graph for this function:

int longestAxis ( unsigned short  x, unsigned short  y, unsigned short  z  )

inline

{
 int axis = 0;
 unsigned short maxVal = x;
 if (y > maxVal)
 {
 axis = 1;
 maxVal = y;
 }
 if (z > maxVal)
 {
 axis = 2;
 maxVal = z;
 }
 return axis;
}

Here is the caller graph for this function:

static void subdivide ( BVItem *  items, int  nitems, int  imin, int  imax, int &  curNode, dtBVNode *  nodes  )

static

{
 int inum = imax - imin;
 int icur = curNode;
 
 dtBVNode& node = nodes[curNode++];
 
 if (inum == 1)
 {
 // Leaf
 node.bmin[0] = items[imin].bmin[0];
 node.bmin[1] = items[imin].bmin[1];
 node.bmin[2] = items[imin].bmin[2];
 
 node.bmax[0] = items[imin].bmax[0];
 node.bmax[1] = items[imin].bmax[1];
 node.bmax[2] = items[imin].bmax[2];
 
 node.i = items[imin].i;
 }
 else
 {
 // Split
 calcExtends(items, nitems, imin, imax, node.bmin, node.bmax);
 
 int axis = longestAxis(node.bmax[0] - node.bmin[0],
 node.bmax[1] - node.bmin[1],
 node.bmax[2] - node.bmin[2]);
 
 if (axis == 0)
 {
 // Sort along x-axis
 qsort(items+imin, inum, sizeof(BVItem), compareItemX);
 }
 else if (axis == 1)
 {
 // Sort along y-axis
 qsort(items+imin, inum, sizeof(BVItem), compareItemY);
 }
 else
 {
 // Sort along z-axis
 qsort(items+imin, inum, sizeof(BVItem), compareItemZ);
 }
 
 int isplit = imin+inum/2;
 
 // Left
 subdivide(items, nitems, imin, isplit, curNode, nodes);
 // Right
 subdivide(items, nitems, isplit, imax, curNode, nodes);
 
 int iescape = curNode - icur;
 // Negative index means escape.
 node.i = -iescape;
 }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

unsigned short MESH_NULL_IDX = 0xffff

static