TrinityCore
dtNavMesh Class Reference

#include <DetourNavMesh.h>

Public Member Functions

 dtNavMesh ()
 
 ~dtNavMesh ()
 
Initialization and Tile Management
dtStatus init (const dtNavMeshParams *params)
 
dtStatus init (unsigned char *data, const int dataSize, const int flags)
 
const dtNavMeshParamsgetParams () const
 The navigation mesh initialization params. More...
 
dtStatus addTile (unsigned char *data, int dataSize, int flags, dtTileRef lastRef, dtTileRef *result)
 
dtStatus removeTile (dtTileRef ref, unsigned char **data, int *dataSize)
 
Query Functions
void calcTileLoc (const float *pos, int *tx, int *ty) const
 
const dtMeshTilegetTileAt (const int x, const int y, const int layer) const
 
int getTilesAt (const int x, const int y, dtMeshTile const **tiles, const int maxTiles) const
 
dtTileRef getTileRefAt (int x, int y, int layer) const
 
dtTileRef getTileRef (const dtMeshTile *tile) const
 
const dtMeshTilegetTileByRef (dtTileRef ref) const
 
int getMaxTiles () const
 
const dtMeshTilegetTile (int i) const
 
dtStatus getTileAndPolyByRef (const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
 
void getTileAndPolyByRefUnsafe (const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
 
bool isValidPolyRef (dtPolyRef ref) const
 
dtPolyRef getPolyRefBase (const dtMeshTile *tile) const
 
dtStatus getOffMeshConnectionPolyEndPoints (dtPolyRef prevRef, dtPolyRef polyRef, float *startPos, float *endPos) const
 
const dtOffMeshConnectiongetOffMeshConnectionByRef (dtPolyRef ref) const
 
State Management

These functions do not effect dtTileRef or dtPolyRef's.

dtStatus setPolyFlags (dtPolyRef ref, unsigned short flags)
 
dtStatus getPolyFlags (dtPolyRef ref, unsigned short *resultFlags) const
 
dtStatus setPolyArea (dtPolyRef ref, unsigned char area)
 
dtStatus getPolyArea (dtPolyRef ref, unsigned char *resultArea) const
 
int getTileStateSize (const dtMeshTile *tile) const
 
dtStatus storeTileState (const dtMeshTile *tile, unsigned char *data, const int maxDataSize) const
 
dtStatus restoreTileState (dtMeshTile *tile, const unsigned char *data, const int maxDataSize)
 
Encoding and Decoding

These functions are generally meant for internal use only.

dtPolyRef encodePolyId (unsigned int salt, unsigned int it, unsigned int ip) const
 
void decodePolyId (dtPolyRef ref, unsigned int &salt, unsigned int &it, unsigned int &ip) const
 
unsigned int decodePolyIdSalt (dtPolyRef ref) const
 
unsigned int decodePolyIdTile (dtPolyRef ref) const
 
unsigned int decodePolyIdPoly (dtPolyRef ref) const
 

Private Member Functions

 dtNavMesh (const dtNavMesh &)
 
dtNavMeshoperator= (const dtNavMesh &)
 
dtMeshTilegetTile (int i)
 Returns pointer to tile in the tile array. More...
 
int getTilesAt (const int x, const int y, dtMeshTile **tiles, const int maxTiles) const
 Returns neighbour tile based on side. More...
 
int getNeighbourTilesAt (const int x, const int y, const int side, dtMeshTile **tiles, const int maxTiles) const
 Returns neighbour tile based on side. More...
 
int findConnectingPolys (const float *va, const float *vb, const dtMeshTile *tile, int side, dtPolyRef *con, float *conarea, int maxcon) const
 Returns all polygons in neighbour tile based on portal defined by the segment. More...
 
void connectIntLinks (dtMeshTile *tile)
 Builds internal polygons links for a tile. More...
 
void baseOffMeshLinks (dtMeshTile *tile)
 Builds internal polygons links for a tile. More...
 
void connectExtLinks (dtMeshTile *tile, dtMeshTile *target, int side)
 Builds external polygon links for a tile. More...
 
void connectExtOffMeshLinks (dtMeshTile *tile, dtMeshTile *target, int side)
 Builds external polygon links for a tile. More...
 
void unconnectLinks (dtMeshTile *tile, dtMeshTile *target)
 Removes external links at specified side. More...
 
int queryPolygonsInTile (const dtMeshTile *tile, const float *qmin, const float *qmax, dtPolyRef *polys, const int maxPolys) const
 Queries polygons within a tile. More...
 
dtPolyRef findNearestPolyInTile (const dtMeshTile *tile, const float *center, const float *halfExtents, float *nearestPt) const
 Find nearest polygon within a tile. More...
 
void closestPointOnPoly (dtPolyRef ref, const float *pos, float *closest, bool *posOverPoly) const
 Returns closest point on polygon. More...
 

Private Attributes

dtNavMeshParams m_params
 Current initialization params. TODO: do not store this info twice. More...
 
float m_orig [3]
 Origin of the tile (0,0) More...
 
float m_tileWidth
 
float m_tileHeight
 Dimensions of each tile. More...
 
int m_maxTiles
 Max number of tiles. More...
 
int m_tileLutSize
 Tile hash lookup size (must be pot). More...
 
int m_tileLutMask
 Tile hash lookup mask. More...
 
dtMeshTile ** m_posLookup
 Tile hash lookup. More...
 
dtMeshTilem_nextFree
 Freelist of tiles. More...
 
dtMeshTilem_tiles
 List of tiles. More...
 

Detailed Description

A navigation mesh based on tiles of convex polygons.

The navigation mesh consists of one or more tiles defining three primary types of structural data:

A polygon mesh which defines most of the navigation graph. (See rcPolyMesh for its structure.) A detail mesh used for determining surface height on the polygon mesh. (See rcPolyMeshDetail for its structure.) Off-mesh connections, which define custom point-to-point edges within the navigation graph.

The general build process is as follows:

  1. Create rcPolyMesh and rcPolyMeshDetail data using the Recast build pipeline.
  2. Optionally, create off-mesh connection data.
  3. Combine the source data into a dtNavMeshCreateParams structure.
  4. Create a tile data array using dtCreateNavMeshData().
  5. Allocate at dtNavMesh object and initialize it. (For single tile navigation meshes, the tile data is loaded during this step.)
  6. For multi-tile navigation meshes, load the tile data using dtNavMesh::addTile().

Notes:

  • This class is usually used in conjunction with the dtNavMeshQuery class for pathfinding.
  • Technically, all navigation meshes are tiled. A 'solo' mesh is simply a navigation mesh initialized to have only a single tile.
  • This class does not implement any asynchronous methods. So the dtStatus result of all methods will always contain either a success or failure flag.
See also
dtNavMeshQuery, dtCreateNavMeshData, dtNavMeshCreateParams, dtAllocNavMesh, dtFreeNavMesh

Constructor & Destructor Documentation

◆ dtNavMesh() [1/2]

dtNavMesh::dtNavMesh ( )
188  :
189  m_tileWidth(0),
190  m_tileHeight(0),
191  m_maxTiles(0),
192  m_tileLutSize(0),
193  m_tileLutMask(0),
194  m_posLookup(0),
195  m_nextFree(0),
196  m_tiles(0)
197 {
198 #ifndef DT_POLYREF64
199  m_saltBits = 0;
200  m_tileBits = 0;
201  m_polyBits = 0;
202 #endif
203  memset(&m_params, 0, sizeof(dtNavMeshParams));
204  m_orig[0] = 0;
205  m_orig[1] = 0;
206  m_orig[2] = 0;
207 }
dtMeshTile ** m_posLookup
Tile hash lookup.
Definition: DetourNavMesh.h:661
dtNavMeshParams m_params
Current initialization params. TODO: do not store this info twice.
Definition: DetourNavMesh.h:654
float m_tileHeight
Dimensions of each tile.
Definition: DetourNavMesh.h:656
int m_maxTiles
Max number of tiles.
Definition: DetourNavMesh.h:657
float m_orig[3]
Origin of the tile (0,0)
Definition: DetourNavMesh.h:655
float m_tileWidth
Definition: DetourNavMesh.h:656
int m_tileLutMask
Tile hash lookup mask.
Definition: DetourNavMesh.h:659
dtMeshTile * m_tiles
List of tiles.
Definition: DetourNavMesh.h:663
int m_tileLutSize
Tile hash lookup size (must be pot).
Definition: DetourNavMesh.h:658
dtMeshTile * m_nextFree
Freelist of tiles.
Definition: DetourNavMesh.h:662
Definition: DetourNavMesh.h:324

◆ ~dtNavMesh()

dtNavMesh::~dtNavMesh ( )
210 {
211  for (int i = 0; i < m_maxTiles; ++i)
212  {
214  {
215  dtFree(m_tiles[i].data);
216  m_tiles[i].data = 0;
217  m_tiles[i].dataSize = 0;
218  }
219  }
221  dtFree(m_tiles);
222 }
The navigation mesh owns the tile memory and is responsible for freeing it.
Definition: DetourNavMesh.h:114
dtMeshTile ** m_posLookup
Tile hash lookup.
Definition: DetourNavMesh.h:661
constexpr auto data(C &c)
Definition: advstd.h:96
int m_maxTiles
Max number of tiles.
Definition: DetourNavMesh.h:657
dtMeshTile * m_tiles
List of tiles.
Definition: DetourNavMesh.h:663
int dataSize
Size of the tile data.
Definition: DetourNavMesh.h:312
unsigned char * data
The tile data. (Not directly accessed under normal situations.)
Definition: DetourNavMesh.h:311
uint8 flags
Definition: DisableMgr.cpp:47
void dtFree(void *ptr)
Definition: DetourAlloc.cpp:46
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ dtNavMesh() [2/2]

dtNavMesh::dtNavMesh ( const dtNavMesh )
private

Member Function Documentation

◆ addTile()

dtStatus dtNavMesh::addTile ( unsigned char *  data,
int  dataSize,
int  flags,
dtTileRef  lastRef,
dtTileRef result 
)

Adds a tile to the navigation mesh.

Parameters
[in]dataData for the new tile mesh. (See: dtCreateNavMeshData)
[in]dataSizeData size of the new tile mesh.
[in]flagsTile flags. (See: dtTileFlags)
[in]lastRefThe desired reference for the tile. (When reloading a tile.) [opt] [Default: 0]
[out]resultThe tile reference. (If the tile was succesfully added.) [opt]
Returns
The status flags for the operation.

The add operation will fail if the data is in the wrong format, the allocated tile space is full, or there is a tile already at the specified reference.

The lastRef parameter is used to restore a tile with the same tile reference it had previously used. In this case the dtPolyRef's for the tile will be restored to the same values they were before the tile was removed.

The nav mesh assumes exclusive access to the data passed and will make changes to the dynamic portion of the data. For that reason the data should not be reused in other nav meshes until the tile has been successfully removed from this nav mesh.

See also
dtCreateNavMeshData, removeTile
848 {
849  // Make sure the data is in right format.
850  dtMeshHeader* header = (dtMeshHeader*)data;
851  if (header->magic != DT_NAVMESH_MAGIC)
852  return DT_FAILURE | DT_WRONG_MAGIC;
853  if (header->version != DT_NAVMESH_VERSION)
854  return DT_FAILURE | DT_WRONG_VERSION;
855 
856  // Make sure the location is free.
857  if (getTileAt(header->x, header->y, header->layer))
858  return DT_FAILURE;
859 
860  // Allocate a tile.
861  dtMeshTile* tile = 0;
862  if (!lastRef)
863  {
864  if (m_nextFree)
865  {
866  tile = m_nextFree;
867  m_nextFree = tile->next;
868  tile->next = 0;
869  }
870  }
871  else
872  {
873  // Try to relocate the tile to specific index with same salt.
874  int tileIndex = (int)decodePolyIdTile((dtPolyRef)lastRef);
875  if (tileIndex >= m_maxTiles)
876  return DT_FAILURE | DT_OUT_OF_MEMORY;
877  // Try to find the specific tile id from the free list.
878  dtMeshTile* target = &m_tiles[tileIndex];
879  dtMeshTile* prev = 0;
880  tile = m_nextFree;
881  while (tile && tile != target)
882  {
883  prev = tile;
884  tile = tile->next;
885  }
886  // Could not find the correct location.
887  if (tile != target)
888  return DT_FAILURE | DT_OUT_OF_MEMORY;
889  // Remove from freelist
890  if (!prev)
891  m_nextFree = tile->next;
892  else
893  prev->next = tile->next;
894 
895  // Restore salt.
896  tile->salt = decodePolyIdSalt((dtPolyRef)lastRef);
897  }
898 
899  // Make sure we could allocate a tile.
900  if (!tile)
901  return DT_FAILURE | DT_OUT_OF_MEMORY;
902 
903  // Insert tile into the position lut.
904  int h = computeTileHash(header->x, header->y, m_tileLutMask);
905  tile->next = m_posLookup[h];
906  m_posLookup[h] = tile;
907 
908  // Patch header pointers.
909  const int headerSize = dtAlign4(sizeof(dtMeshHeader));
910  const int vertsSize = dtAlign4(sizeof(float)*3*header->vertCount);
911  const int polysSize = dtAlign4(sizeof(dtPoly)*header->polyCount);
912  const int linksSize = dtAlign4(sizeof(dtLink)*(header->maxLinkCount));
913  const int detailMeshesSize = dtAlign4(sizeof(dtPolyDetail)*header->detailMeshCount);
914  const int detailVertsSize = dtAlign4(sizeof(float)*3*header->detailVertCount);
915  const int detailTrisSize = dtAlign4(sizeof(unsigned char)*4*header->detailTriCount);
916  const int bvtreeSize = dtAlign4(sizeof(dtBVNode)*header->bvNodeCount);
917  const int offMeshLinksSize = dtAlign4(sizeof(dtOffMeshConnection)*header->offMeshConCount);
918 
919  unsigned char* d = data + headerSize;
920  tile->verts = dtGetThenAdvanceBufferPointer<float>(d, vertsSize);
921  tile->polys = dtGetThenAdvanceBufferPointer<dtPoly>(d, polysSize);
922  tile->links = dtGetThenAdvanceBufferPointer<dtLink>(d, linksSize);
923  tile->detailMeshes = dtGetThenAdvanceBufferPointer<dtPolyDetail>(d, detailMeshesSize);
924  tile->detailVerts = dtGetThenAdvanceBufferPointer<float>(d, detailVertsSize);
925  tile->detailTris = dtGetThenAdvanceBufferPointer<unsigned char>(d, detailTrisSize);
926  tile->bvTree = dtGetThenAdvanceBufferPointer<dtBVNode>(d, bvtreeSize);
927  tile->offMeshCons = dtGetThenAdvanceBufferPointer<dtOffMeshConnection>(d, offMeshLinksSize);
928 
929  // If there are no items in the bvtree, reset the tree pointer.
930  if (!bvtreeSize)
931  tile->bvTree = 0;
932 
933  // Build links freelist
934  tile->linksFreeList = 0;
935  tile->links[header->maxLinkCount-1].next = DT_NULL_LINK;
936  for (int i = 0; i < header->maxLinkCount-1; ++i)
937  tile->links[i].next = i+1;
938 
939  // Init tile.
940  tile->header = header;
941  tile->data = data;
942  tile->dataSize = dataSize;
943  tile->flags = flags;
944 
945  connectIntLinks(tile);
946 
947  // Base off-mesh connections to their starting polygons and connect connections inside the tile.
948  baseOffMeshLinks(tile);
949  connectExtOffMeshLinks(tile, tile, -1);
950 
951  // Create connections with neighbour tiles.
952  static const int MAX_NEIS = 32;
953  dtMeshTile* neis[MAX_NEIS];
954  int nneis;
955 
956  // Connect with layers in current tile.
957  nneis = getTilesAt(header->x, header->y, neis, MAX_NEIS);
958  for (int j = 0; j < nneis; ++j)
959  {
960  if (neis[j] == tile)
961  continue;
962 
963  connectExtLinks(tile, neis[j], -1);
964  connectExtLinks(neis[j], tile, -1);
965  connectExtOffMeshLinks(tile, neis[j], -1);
966  connectExtOffMeshLinks(neis[j], tile, -1);
967  }
968 
969  // Connect with neighbour tiles.
970  for (int i = 0; i < 8; ++i)
971  {
972  nneis = getNeighbourTilesAt(header->x, header->y, i, neis, MAX_NEIS);
973  for (int j = 0; j < nneis; ++j)
974  {
975  connectExtLinks(tile, neis[j], i);
976  connectExtLinks(neis[j], tile, dtOppositeTile(i));
977  connectExtOffMeshLinks(tile, neis[j], i);
978  connectExtOffMeshLinks(neis[j], tile, dtOppositeTile(i));
979  }
980  }
981 
982  if (result)
983  *result = getTileRef(tile);
984 
985  return DT_SUCCESS;
986 }
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:293
static const unsigned int DT_WRONG_VERSION
Definition: DetourStatus.h:32
dtMeshTile ** m_posLookup
Tile hash lookup.
Definition: DetourNavMesh.h:661
void connectIntLinks(dtMeshTile *tile)
Builds internal polygons links for a tile.
Definition: DetourNavMesh.cpp:524
Defines the location of detail sub-mesh data within a dtMeshTile.
Definition: DetourNavMesh.h:198
constexpr auto data(C &c)
Definition: advstd.h:96
dtOffMeshConnection * offMeshCons
The tile off-mesh connections. [Size: dtMeshHeader::offMeshConCount].
Definition: DetourNavMesh.h:309
void baseOffMeshLinks(dtMeshTile *tile)
Builds internal polygons links for a tile.
Definition: DetourNavMesh.cpp:561
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
unsigned int decodePolyIdSalt(dtPolyRef ref) const
Definition: DetourNavMesh.h:565
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
int m_maxTiles
Max number of tiles.
Definition: DetourNavMesh.h:657
int offMeshConCount
The number of off-mesh connections.
Definition: DetourNavMesh.h:274
dtBVNode * bvTree
Definition: DetourNavMesh.h:307
int detailMeshCount
The number of sub-meshes in the detail mesh.
Definition: DetourNavMesh.h:267
static const unsigned int DT_WRONG_MAGIC
Definition: DetourStatus.h:31
int m_tileLutMask
Tile hash lookup mask.
Definition: DetourNavMesh.h:659
Definition: DetourNavMesh.h:222
int layer
The layer of the tile within the dtNavMesh tile grid. (x, y, layer)
Definition: DetourNavMesh.h:262
int flags
Tile flags. (See: dtTileFlags)
Definition: DetourNavMesh.h:313
Definition: DetourNavMesh.h:256
dtMeshTile * m_tiles
List of tiles.
Definition: DetourNavMesh.h:663
dtMeshTile * next
The next free tile, or the next tile in the spatial grid.
Definition: DetourNavMesh.h:314
dtTileRef getTileRef(const dtMeshTile *tile) const
Definition: DetourNavMesh.cpp:1266
int getTilesAt(const int x, const int y, dtMeshTile const **tiles, const int maxTiles) const
Definition: DetourNavMesh.cpp:1051
Definition: DetourNavMesh.h:162
int polyCount
The number of polygons in the tile.
Definition: DetourNavMesh.h:264
int bvNodeCount
The number of bounding volume nodes. (Zero if bounding volumes are disabled.)
Definition: DetourNavMesh.h:273
int x
The x-position of the tile within the dtNavMesh tile grid. (x, y, layer)
Definition: DetourNavMesh.h:260
unsigned int linksFreeList
Index to the next free link.
Definition: DetourNavMesh.h:292
unsigned int salt
Counter describing modifications to the tile.
Definition: DetourNavMesh.h:290
int version
Tile data format version number.
Definition: DetourNavMesh.h:259
int detailVertCount
The number of unique vertices in the detail mesh. (In addition to the polygon vertices.)
Definition: DetourNavMesh.h:270
int maxLinkCount
The number of allocated links.
Definition: DetourNavMesh.h:266
int getNeighbourTilesAt(const int x, const int y, const int side, dtMeshTile **tiles, const int maxTiles) const
Returns neighbour tile based on side.
Definition: DetourNavMesh.cpp:1007
float * verts
The tile vertices. [Size: dtMeshHeader::vertCount].
Definition: DetourNavMesh.h:295
dtLink * links
The tile links. [Size: dtMeshHeader::maxLinkCount].
Definition: DetourNavMesh.h:296
int dataSize
Size of the tile data.
Definition: DetourNavMesh.h:312
const dtMeshTile * getTileAt(const int x, const int y, const int layer) const
Definition: DetourNavMesh.cpp:988
float * detailVerts
The detail mesh&#39;s unique vertices. [(x, y, z) * dtMeshHeader::detailVertCount].
Definition: DetourNavMesh.h:300
void connectExtOffMeshLinks(dtMeshTile *tile, dtMeshTile *target, int side)
Builds external polygon links for a tile.
Definition: DetourNavMesh.cpp:454
unsigned char * detailTris
The detail mesh&#39;s triangles. [(vertA, vertB, vertC) * dtMeshHeader::detailTriCount].
Definition: DetourNavMesh.h:303
dtMeshTile * m_nextFree
Freelist of tiles.
Definition: DetourNavMesh.h:662
dtPolyDetail * detailMeshes
The tile&#39;s detail sub-meshes. [Size: dtMeshHeader::detailMeshCount].
Definition: DetourNavMesh.h:297
void connectExtLinks(dtMeshTile *tile, dtMeshTile *target, int side)
Builds external polygon links for a tile.
Definition: DetourNavMesh.cpp:387
int magic
Tile magic number. (Used to identify the data format.)
Definition: DetourNavMesh.h:258
int dtAlign4(int x)
Definition: DetourCommon.h:442
unsigned int decodePolyIdTile(dtPolyRef ref) const
Definition: DetourNavMesh.h:580
int detailTriCount
The number of triangles in the detail mesh.
Definition: DetourNavMesh.h:272
unsigned char * data
The tile data. (Not directly accessed under normal situations.)
Definition: DetourNavMesh.h:311
int prev(int i, int n)
Definition: RecastContour.cpp:468
int computeTileHash(int x, int y, const int mask)
Definition: DetourNavMesh.cpp:114
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:294
int dtOppositeTile(int side)
Definition: DetourCommon.h:444
static const int DT_NAVMESH_MAGIC
A magic number used to detect compatibility of navigation tile data.
Definition: DetourNavMesh.h:82
uint8 flags
Definition: DisableMgr.cpp:47
Definition: DetourNavMesh.h:288
int y
The y-position of the tile within the dtNavMesh tile grid. (x, y, layer)
Definition: DetourNavMesh.h:261
static const int DT_NAVMESH_VERSION
A version number used to detect compatibility of navigation tile data.
Definition: DetourNavMesh.h:85
int vertCount
The number of vertices in the tile.
Definition: DetourNavMesh.h:265
Definition: DetourNavMesh.h:231
static const unsigned int DT_OUT_OF_MEMORY
Definition: DetourStatus.h:33
static const unsigned int DT_NULL_LINK
A value that indicates the entity does not link to anything.
Definition: DetourNavMesh.h:100
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ baseOffMeshLinks()

void dtNavMesh::baseOffMeshLinks ( dtMeshTile tile)
private

Builds internal polygons links for a tile.

562 {
563  if (!tile) return;
564 
565  dtPolyRef base = getPolyRefBase(tile);
566 
567  // Base off-mesh connection start points.
568  for (int i = 0; i < tile->header->offMeshConCount; ++i)
569  {
570  dtOffMeshConnection* con = &tile->offMeshCons[i];
571  dtPoly* poly = &tile->polys[con->poly];
572 
573  const float halfExtents[3] = { con->rad, tile->header->walkableClimb, con->rad };
574 
575  // Find polygon to connect to.
576  const float* p = &con->pos[0]; // First vertex
577  float nearestPt[3];
578  dtPolyRef ref = findNearestPolyInTile(tile, p, halfExtents, nearestPt);
579  if (!ref) continue;
580  // findNearestPoly may return too optimistic results, further check to make sure.
581  if (dtSqr(nearestPt[0]-p[0])+dtSqr(nearestPt[2]-p[2]) > dtSqr(con->rad))
582  continue;
583  // Make sure the location is on current mesh.
584  float* v = &tile->verts[poly->verts[0]*3];
585  dtVcopy(v, nearestPt);
586 
587  // Link off-mesh connection to target poly.
588  unsigned int idx = allocLink(tile);
589  if (idx != DT_NULL_LINK)
590  {
591  dtLink* link = &tile->links[idx];
592  link->ref = ref;
593  link->edge = (unsigned char)0;
594  link->side = 0xff;
595  link->bmin = link->bmax = 0;
596  // Add to linked list.
597  link->next = poly->firstLink;
598  poly->firstLink = idx;
599  }
600 
601  // Start end-point is always connect back to off-mesh connection.
602  unsigned int tidx = allocLink(tile);
603  if (tidx != DT_NULL_LINK)
604  {
605  const unsigned short landPolyIdx = (unsigned short)decodePolyIdPoly(ref);
606  dtPoly* landPoly = &tile->polys[landPolyIdx];
607  dtLink* link = &tile->links[tidx];
608  link->ref = base | (dtPolyRef)(con->poly);
609  link->edge = 0xff;
610  link->side = 0xff;
611  link->bmin = link->bmax = 0;
612  // Add to linked list.
613  link->next = landPoly->firstLink;
614  landPoly->firstLink = tidx;
615  }
616  }
617 }
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:293
unsigned short poly
The polygon reference of the connection within the tile.
Definition: DetourNavMesh.h:240
float walkableClimb
The maximum climb height of the agents using the tile.
Definition: DetourNavMesh.h:278
dtPolyRef findNearestPolyInTile(const dtMeshTile *tile, const float *center, const float *halfExtents, float *nearestPt) const
Find nearest polygon within a tile.
Definition: DetourNavMesh.cpp:698
dtOffMeshConnection * offMeshCons
The tile off-mesh connections. [Size: dtMeshHeader::offMeshConCount].
Definition: DetourNavMesh.h:309
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
int offMeshConCount
The number of off-mesh connections.
Definition: DetourNavMesh.h:274
unsigned short verts[DT_VERTS_PER_POLYGON]
Definition: DetourNavMesh.h:169
unsigned int decodePolyIdPoly(dtPolyRef ref) const
Definition: DetourNavMesh.h:595
Definition: DetourNavMesh.h:162
float rad
The radius of the endpoints. [Limit: >= 0].
Definition: DetourNavMesh.h:237
unsigned int allocLink(dtMeshTile *tile)
Definition: DetourNavMesh.cpp:122
float * verts
The tile vertices. [Size: dtMeshHeader::vertCount].
Definition: DetourNavMesh.h:295
dtLink * links
The tile links. [Size: dtMeshHeader::maxLinkCount].
Definition: DetourNavMesh.h:296
dtPolyRef getPolyRefBase(const dtMeshTile *tile) const
Definition: DetourNavMesh.cpp:1287
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:191
T dtSqr(T a)
Definition: DetourCommon.h:68
unsigned int firstLink
Index to first link in linked list. (Or DT_NULL_LINK if there is no link.)
Definition: DetourNavMesh.h:165
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:294
float pos[6]
The endpoints of the connection. [(ax, ay, az, bx, by, bz)].
Definition: DetourNavMesh.h:234
Definition: DetourNavMesh.h:231
static const unsigned int DT_NULL_LINK
A value that indicates the entity does not link to anything.
Definition: DetourNavMesh.h:100
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ calcTileLoc()

void dtNavMesh::calcTileLoc ( const float *  pos,
int *  tx,
int *  ty 
) const

Calculates the tile grid location for the specified world position.

Parameters
[in]posThe world position for the query. [(x, y, z)]
[out]txThe tile's x-location. (x, y)
[out]tyThe tile's y-location. (x, y)
1123 {
1124  *tx = (int)floorf((pos[0]-m_orig[0]) / m_tileWidth);
1125  *ty = (int)floorf((pos[2]-m_orig[2]) / m_tileHeight);
1126 }
float m_tileHeight
Dimensions of each tile.
Definition: DetourNavMesh.h:656
float m_orig[3]
Origin of the tile (0,0)
Definition: DetourNavMesh.h:655
float m_tileWidth
Definition: DetourNavMesh.h:656
+ Here is the caller graph for this function:

◆ closestPointOnPoly()

void dtNavMesh::closestPointOnPoly ( dtPolyRef  ref,
const float *  pos,
float *  closest,
bool posOverPoly 
) const
private

Returns closest point on polygon.

620 {
621  const dtMeshTile* tile = 0;
622  const dtPoly* poly = 0;
623  getTileAndPolyByRefUnsafe(ref, &tile, &poly);
624 
625  // Off-mesh connections don't have detail polygons.
627  {
628  const float* v0 = &tile->verts[poly->verts[0]*3];
629  const float* v1 = &tile->verts[poly->verts[1]*3];
630  const float d0 = dtVdist(pos, v0);
631  const float d1 = dtVdist(pos, v1);
632  const float u = d0 / (d0+d1);
633  dtVlerp(closest, v0, v1, u);
634  if (posOverPoly)
635  *posOverPoly = false;
636  return;
637  }
638 
639  const unsigned int ip = (unsigned int)(poly - tile->polys);
640  const dtPolyDetail* pd = &tile->detailMeshes[ip];
641 
642  // Clamp point to be inside the polygon.
643  float verts[DT_VERTS_PER_POLYGON*3];
644  float edged[DT_VERTS_PER_POLYGON];
645  float edget[DT_VERTS_PER_POLYGON];
646  const int nv = poly->vertCount;
647  for (int i = 0; i < nv; ++i)
648  dtVcopy(&verts[i*3], &tile->verts[poly->verts[i]*3]);
649 
650  dtVcopy(closest, pos);
651  if (!dtDistancePtPolyEdgesSqr(pos, verts, nv, edged, edget))
652  {
653  // Point is outside the polygon, dtClamp to nearest edge.
654  float dmin = edged[0];
655  int imin = 0;
656  for (int i = 1; i < nv; ++i)
657  {
658  if (edged[i] < dmin)
659  {
660  dmin = edged[i];
661  imin = i;
662  }
663  }
664  const float* va = &verts[imin*3];
665  const float* vb = &verts[((imin+1)%nv)*3];
666  dtVlerp(closest, va, vb, edget[imin]);
667 
668  if (posOverPoly)
669  *posOverPoly = false;
670  }
671  else
672  {
673  if (posOverPoly)
674  *posOverPoly = true;
675  }
676 
677  // Find height at the location.
678  for (int j = 0; j < pd->triCount; ++j)
679  {
680  const unsigned char* t = &tile->detailTris[(pd->triBase+j)*4];
681  const float* v[3];
682  for (int k = 0; k < 3; ++k)
683  {
684  if (t[k] < poly->vertCount)
685  v[k] = &tile->verts[poly->verts[t[k]]*3];
686  else
687  v[k] = &tile->detailVerts[(pd->vertBase+(t[k]-poly->vertCount))*3];
688  }
689  float h;
690  if (dtClosestHeightPointTriangle(closest, v[0], v[1], v[2], h))
691  {
692  closest[1] = h;
693  break;
694  }
695  }
696 }
unsigned char getType() const
Gets the polygon type. (See: dtPolyTypes)
Definition: DetourNavMesh.h:194
Defines the location of detail sub-mesh data within a dtMeshTile.
Definition: DetourNavMesh.h:198
void dtVlerp(float *dest, const float *v1, const float *v2, const float t)
Definition: DetourCommon.h:118
float dtVdist(const float *v1, const float *v2)
Definition: DetourCommon.h:218
unsigned char triCount
The number of triangles in the sub-mesh.
Definition: DetourNavMesh.h:203
unsigned short verts[DT_VERTS_PER_POLYGON]
Definition: DetourNavMesh.h:169
unsigned int vertBase
The offset of the vertices in the dtMeshTile::detailVerts array.
Definition: DetourNavMesh.h:200
Definition: DetourNavMesh.h:162
void getTileAndPolyByRefUnsafe(const dtPolyRef ref, const dtMeshTile **tile, const dtPoly **poly) const
Definition: DetourNavMesh.cpp:1146
bool dtClosestHeightPointTriangle(const float *p, const float *a, const float *b, const float *c, float &h)
Definition: DetourCommon.cpp:204
float * verts
The tile vertices. [Size: dtMeshHeader::vertCount].
Definition: DetourNavMesh.h:295
float * detailVerts
The detail mesh&#39;s unique vertices. [(x, y, z) * dtMeshHeader::detailVertCount].
Definition: DetourNavMesh.h:300
unsigned char * detailTris
The detail mesh&#39;s triangles. [(vertA, vertB, vertC) * dtMeshHeader::detailTriCount].
Definition: DetourNavMesh.h:303
dtPolyDetail * detailMeshes
The tile&#39;s detail sub-meshes. [Size: dtMeshHeader::detailMeshCount].
Definition: DetourNavMesh.h:297
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:191
The polygon is an off-mesh connection consisting of two vertices.
Definition: DetourNavMesh.h:156
unsigned char vertCount
The number of vertices in the polygon.
Definition: DetourNavMesh.h:178
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:294
unsigned int triBase
The offset of the triangles in the dtMeshTile::detailTris array.
Definition: DetourNavMesh.h:201
Definition: DetourNavMesh.h:288
bool dtDistancePtPolyEdgesSqr(const float *pt, const float *verts, const int nverts, float *ed, float *et)
Definition: DetourCommon.cpp:255
static const int DT_VERTS_PER_POLYGON
Definition: DetourNavMesh.h:73
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ connectExtLinks()

void dtNavMesh::connectExtLinks ( dtMeshTile tile,
dtMeshTile target,
int  side 
)
private

Builds external polygon links for a tile.

388 {
389  if (!tile) return;
390 
391  // Connect border links.
392  for (int i = 0; i < tile->header->polyCount; ++i)
393  {
394  dtPoly* poly = &tile->polys[i];
395 
396  // Create new links.
397 // unsigned short m = DT_EXT_LINK | (unsigned short)side;
398 
399  const int nv = poly->vertCount;
400  for (int j = 0; j < nv; ++j)
401  {
402  // Skip non-portal edges.
403  if ((poly->neis[j] & DT_EXT_LINK) == 0)
404  continue;
405 
406  const int dir = (int)(poly->neis[j] & 0xff);
407  if (side != -1 && dir != side)
408  continue;
409 
410  // Create new links
411  const float* va = &tile->verts[poly->verts[j]*3];
412  const float* vb = &tile->verts[poly->verts[(j+1) % nv]*3];
413  dtPolyRef nei[4];
414  float neia[4*2];
415  int nnei = findConnectingPolys(va,vb, target, dtOppositeTile(dir), nei,neia,4);
416  for (int k = 0; k < nnei; ++k)
417  {
418  unsigned int idx = allocLink(tile);
419  if (idx != DT_NULL_LINK)
420  {
421  dtLink* link = &tile->links[idx];
422  link->ref = nei[k];
423  link->edge = (unsigned char)j;
424  link->side = (unsigned char)dir;
425 
426  link->next = poly->firstLink;
427  poly->firstLink = idx;
428 
429  // Compress portal limits to a byte value.
430  if (dir == 0 || dir == 4)
431  {
432  float tmin = (neia[k*2+0]-va[2]) / (vb[2]-va[2]);
433  float tmax = (neia[k*2+1]-va[2]) / (vb[2]-va[2]);
434  if (tmin > tmax)
435  dtSwap(tmin,tmax);
436  link->bmin = (unsigned char)(dtClamp(tmin, 0.0f, 1.0f)*255.0f);
437  link->bmax = (unsigned char)(dtClamp(tmax, 0.0f, 1.0f)*255.0f);
438  }
439  else if (dir == 2 || dir == 6)
440  {
441  float tmin = (neia[k*2+0]-va[0]) / (vb[0]-va[0]);
442  float tmax = (neia[k*2+1]-va[0]) / (vb[0]-va[0]);
443  if (tmin > tmax)
444  dtSwap(tmin,tmax);
445  link->bmin = (unsigned char)(dtClamp(tmin, 0.0f, 1.0f)*255.0f);
446  link->bmax = (unsigned char)(dtClamp(tmax, 0.0f, 1.0f)*255.0f);
447  }
448  }
449  }
450  }
451  }
452 }
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:293
int findConnectingPolys(const float *va, const float *vb, const dtMeshTile *tile, int side, dtPolyRef *con, float *conarea, int maxcon) const
Returns all polygons in neighbour tile based on portal defined by the segment.
Definition: DetourNavMesh.cpp:300
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
unsigned short verts[DT_VERTS_PER_POLYGON]
Definition: DetourNavMesh.h:169
unsigned short neis[DT_VERTS_PER_POLYGON]
Packed data representing neighbor polygons references and flags for each edge.
Definition: DetourNavMesh.h:172
Definition: DetourNavMesh.h:162
int polyCount
The number of polygons in the tile.
Definition: DetourNavMesh.h:264
unsigned int allocLink(dtMeshTile *tile)
Definition: DetourNavMesh.cpp:122
T dtClamp(T v, T mn, T mx)
Definition: DetourCommon.h:75
float * verts
The tile vertices. [Size: dtMeshHeader::vertCount].
Definition: DetourNavMesh.h:295
dtLink * links
The tile links. [Size: dtMeshHeader::maxLinkCount].
Definition: DetourNavMesh.h:296
static const unsigned short DT_EXT_LINK
Definition: DetourNavMesh.h:97
void dtSwap(T &a, T &b)
Definition: DetourCommon.h:46
unsigned int firstLink
Index to first link in linked list. (Or DT_NULL_LINK if there is no link.)
Definition: DetourNavMesh.h:165
unsigned char vertCount
The number of vertices in the polygon.
Definition: DetourNavMesh.h:178
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:294
int dtOppositeTile(int side)
Definition: DetourCommon.h:444
static const unsigned int DT_NULL_LINK
A value that indicates the entity does not link to anything.
Definition: DetourNavMesh.h:100
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ connectExtOffMeshLinks()

void dtNavMesh::connectExtOffMeshLinks ( dtMeshTile tile,
dtMeshTile target,
int  side 
)
private

Builds external polygon links for a tile.

455 {
456  if (!tile) return;
457 
458  // Connect off-mesh links.
459  // We are interested on links which land from target tile to this tile.
460  const unsigned char oppositeSide = (side == -1) ? 0xff : (unsigned char)dtOppositeTile(side);
461 
462  for (int i = 0; i < target->header->offMeshConCount; ++i)
463  {
464  dtOffMeshConnection* targetCon = &target->offMeshCons[i];
465  if (targetCon->side != oppositeSide)
466  continue;
467 
468  dtPoly* targetPoly = &target->polys[targetCon->poly];
469  // Skip off-mesh connections which start location could not be connected at all.
470  if (targetPoly->firstLink == DT_NULL_LINK)
471  continue;
472 
473  const float halfExtents[3] = { targetCon->rad, target->header->walkableClimb, targetCon->rad };
474 
475  // Find polygon to connect to.
476  const float* p = &targetCon->pos[3];
477  float nearestPt[3];
478  dtPolyRef ref = findNearestPolyInTile(tile, p, halfExtents, nearestPt);
479  if (!ref)
480  continue;
481  // findNearestPoly may return too optimistic results, further check to make sure.
482  if (dtSqr(nearestPt[0]-p[0])+dtSqr(nearestPt[2]-p[2]) > dtSqr(targetCon->rad))
483  continue;
484  // Make sure the location is on current mesh.
485  float* v = &target->verts[targetPoly->verts[1]*3];
486  dtVcopy(v, nearestPt);
487 
488  // Link off-mesh connection to target poly.
489  unsigned int idx = allocLink(target);
490  if (idx != DT_NULL_LINK)
491  {
492  dtLink* link = &target->links[idx];
493  link->ref = ref;
494  link->edge = (unsigned char)1;
495  link->side = oppositeSide;
496  link->bmin = link->bmax = 0;
497  // Add to linked list.
498  link->next = targetPoly->firstLink;
499  targetPoly->firstLink = idx;
500  }
501 
502  // Link target poly to off-mesh connection.
503  if (targetCon->flags & DT_OFFMESH_CON_BIDIR)
504  {
505  unsigned int tidx = allocLink(tile);
506  if (tidx != DT_NULL_LINK)
507  {
508  const unsigned short landPolyIdx = (unsigned short)decodePolyIdPoly(ref);
509  dtPoly* landPoly = &tile->polys[landPolyIdx];
510  dtLink* link = &tile->links[tidx];
511  link->ref = getPolyRefBase(target) | (dtPolyRef)(targetCon->poly);
512  link->edge = 0xff;
513  link->side = (unsigned char)(side == -1 ? 0xff : side);
514  link->bmin = link->bmax = 0;
515  // Add to linked list.
516  link->next = landPoly->firstLink;
517  landPoly->firstLink = tidx;
518  }
519  }
520  }
521 
522 }
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:293
unsigned short poly
The polygon reference of the connection within the tile.
Definition: DetourNavMesh.h:240
unsigned char side
End point side.
Definition: DetourNavMesh.h:248
float walkableClimb
The maximum climb height of the agents using the tile.
Definition: DetourNavMesh.h:278
dtPolyRef findNearestPolyInTile(const dtMeshTile *tile, const float *center, const float *halfExtents, float *nearestPt) const
Find nearest polygon within a tile.
Definition: DetourNavMesh.cpp:698
dtOffMeshConnection * offMeshCons
The tile off-mesh connections. [Size: dtMeshHeader::offMeshConCount].
Definition: DetourNavMesh.h:309
unsigned char flags
Definition: DetourNavMesh.h:245
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
int offMeshConCount
The number of off-mesh connections.
Definition: DetourNavMesh.h:274
static const unsigned int DT_OFFMESH_CON_BIDIR
A flag that indicates that an off-mesh connection can be traversed in both directions. (Is bidirectional.)
Definition: DetourNavMesh.h:103
unsigned short verts[DT_VERTS_PER_POLYGON]
Definition: DetourNavMesh.h:169
unsigned int decodePolyIdPoly(dtPolyRef ref) const
Definition: DetourNavMesh.h:595
Definition: DetourNavMesh.h:162
float rad
The radius of the endpoints. [Limit: >= 0].
Definition: DetourNavMesh.h:237
unsigned int allocLink(dtMeshTile *tile)
Definition: DetourNavMesh.cpp:122
float * verts
The tile vertices. [Size: dtMeshHeader::vertCount].
Definition: DetourNavMesh.h:295
dtLink * links
The tile links. [Size: dtMeshHeader::maxLinkCount].
Definition: DetourNavMesh.h:296
dtPolyRef getPolyRefBase(const dtMeshTile *tile) const
Definition: DetourNavMesh.cpp:1287
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:191
T dtSqr(T a)
Definition: DetourCommon.h:68
unsigned int firstLink
Index to first link in linked list. (Or DT_NULL_LINK if there is no link.)
Definition: DetourNavMesh.h:165
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:294
int dtOppositeTile(int side)
Definition: DetourCommon.h:444
float pos[6]
The endpoints of the connection. [(ax, ay, az, bx, by, bz)].
Definition: DetourNavMesh.h:234
Definition: DetourNavMesh.h:231
static const unsigned int DT_NULL_LINK
A value that indicates the entity does not link to anything.
Definition: DetourNavMesh.h:100
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ connectIntLinks()

void dtNavMesh::connectIntLinks ( dtMeshTile tile)
private

Builds internal polygons links for a tile.

525 {
526  if (!tile) return;
527 
528  dtPolyRef base = getPolyRefBase(tile);
529 
530  for (int i = 0; i < tile->header->polyCount; ++i)
531  {
532  dtPoly* poly = &tile->polys[i];
533  poly->firstLink = DT_NULL_LINK;
534 
536  continue;
537 
538  // Build edge links backwards so that the links will be
539  // in the linked list from lowest index to highest.
540  for (int j = poly->vertCount-1; j >= 0; --j)
541  {
542  // Skip hard and non-internal edges.
543  if (poly->neis[j] == 0 || (poly->neis[j] & DT_EXT_LINK)) continue;
544 
545  unsigned int idx = allocLink(tile);
546  if (idx != DT_NULL_LINK)
547  {
548  dtLink* link = &tile->links[idx];
549  link->ref = base | (dtPolyRef)(poly->neis[j]-1);
550  link->edge = (unsigned char)j;
551  link->side = 0xff;
552  link->bmin = link->bmax = 0;
553  // Add to linked list.
554  link->next = poly->firstLink;
555  poly->firstLink = idx;
556  }
557  }
558  }
559 }
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:293
unsigned char getType() const
Gets the polygon type. (See: dtPolyTypes)
Definition: DetourNavMesh.h:194
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
unsigned short neis[DT_VERTS_PER_POLYGON]
Packed data representing neighbor polygons references and flags for each edge.
Definition: DetourNavMesh.h:172
Definition: DetourNavMesh.h:162
int polyCount
The number of polygons in the tile.
Definition: DetourNavMesh.h:264
unsigned int allocLink(dtMeshTile *tile)
Definition: DetourNavMesh.cpp:122
dtLink * links
The tile links. [Size: dtMeshHeader::maxLinkCount].
Definition: DetourNavMesh.h:296
dtPolyRef getPolyRefBase(const dtMeshTile *tile) const
Definition: DetourNavMesh.cpp:1287
static const unsigned short DT_EXT_LINK
Definition: DetourNavMesh.h:97
The polygon is an off-mesh connection consisting of two vertices.
Definition: DetourNavMesh.h:156
unsigned int firstLink
Index to first link in linked list. (Or DT_NULL_LINK if there is no link.)
Definition: DetourNavMesh.h:165
unsigned char vertCount
The number of vertices in the polygon.
Definition: DetourNavMesh.h:178
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:294
static const unsigned int DT_NULL_LINK
A value that indicates the entity does not link to anything.
Definition: DetourNavMesh.h:100
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ decodePolyId()

void dtNavMesh::decodePolyId ( dtPolyRef  ref,
unsigned int &  salt,
unsigned int &  it,
unsigned int &  ip 
) const
inline

Decodes a standard polygon reference.

Note
This function is generally meant for internal use only.
Parameters
[in]refThe polygon reference to decode.
[out]saltThe tile's salt value.
[out]itThe index of the tile.
[out]ipThe index of the polygon within the tile.
See also
encodePolyId
543  {
544 #ifdef DT_POLYREF64
545  const dtPolyRef saltMask = ((dtPolyRef)1<<DT_SALT_BITS)-1;
546  const dtPolyRef tileMask = ((dtPolyRef)1<<DT_TILE_BITS)-1;
547  const dtPolyRef polyMask = ((dtPolyRef)1<<DT_POLY_BITS)-1;
548  salt = (unsigned int)((ref >> (DT_POLY_BITS+DT_TILE_BITS)) & saltMask);
549  it = (unsigned int)((ref >> DT_POLY_BITS) & tileMask);
550  ip = (unsigned int)(ref & polyMask);
551 #else
552  const dtPolyRef saltMask = ((dtPolyRef)1<<m_saltBits)-1;
553  const dtPolyRef tileMask = ((dtPolyRef)1<<m_tileBits)-1;
554  const dtPolyRef polyMask = ((dtPolyRef)1<<m_polyBits)-1;
555  salt = (unsigned int)((ref >> (m_polyBits+m_tileBits)) & saltMask);
556  it = (unsigned int)((ref >> m_polyBits) & tileMask);
557  ip = (unsigned int)(ref & polyMask);
558 #endif
559  }
static const unsigned int DT_SALT_BITS
Definition: DetourNavMesh.h:55
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
static const unsigned int DT_TILE_BITS
Definition: DetourNavMesh.h:56
static const unsigned int DT_POLY_BITS
Definition: DetourNavMesh.h:57
+ Here is the caller graph for this function:

◆ decodePolyIdPoly()

unsigned int dtNavMesh::decodePolyIdPoly ( dtPolyRef  ref) const
inline

Extracts the polygon's index (within its tile) from the specified polygon reference.

Note
This function is generally meant for internal use only.
Parameters
[in]refThe polygon reference.
See also
encodePolyId
596  {
597 #ifdef DT_POLYREF64
598  const dtPolyRef polyMask = ((dtPolyRef)1<<DT_POLY_BITS)-1;
599  return (unsigned int)(ref & polyMask);
600 #else
601  const dtPolyRef polyMask = ((dtPolyRef)1<<m_polyBits)-1;
602  return (unsigned int)(ref & polyMask);
603 #endif
604  }
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
static const unsigned int DT_POLY_BITS
Definition: DetourNavMesh.h:57
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ decodePolyIdSalt()

unsigned int dtNavMesh::decodePolyIdSalt ( dtPolyRef  ref) const
inline

Extracts a tile's salt value from the specified polygon reference.

Note
This function is generally meant for internal use only.
Parameters
[in]refThe polygon reference.
See also
encodePolyId
566  {
567 #ifdef DT_POLYREF64
568  const dtPolyRef saltMask = ((dtPolyRef)1<<DT_SALT_BITS)-1;
569  return (unsigned int)((ref >> (DT_POLY_BITS+DT_TILE_BITS)) & saltMask);
570 #else
571  const dtPolyRef saltMask = ((dtPolyRef)1<<m_saltBits)-1;
572  return (unsigned int)((ref >> (m_polyBits+m_tileBits)) & saltMask);
573 #endif
574  }
static const unsigned int DT_SALT_BITS
Definition: DetourNavMesh.h:55
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
static const unsigned int DT_TILE_BITS
Definition: DetourNavMesh.h:56
static const unsigned int DT_POLY_BITS
Definition: DetourNavMesh.h:57
+ Here is the caller graph for this function:

◆ decodePolyIdTile()

unsigned int dtNavMesh::decodePolyIdTile ( dtPolyRef  ref) const
inline

Extracts the tile's index from the specified polygon reference.

Note
This function is generally meant for internal use only.
Parameters
[in]refThe polygon reference.
See also
encodePolyId
581  {
582 #ifdef DT_POLYREF64
583  const dtPolyRef tileMask = ((dtPolyRef)1<<DT_TILE_BITS)-1;
584  return (unsigned int)((ref >> DT_POLY_BITS) & tileMask);
585 #else
586  const dtPolyRef tileMask = ((dtPolyRef)1<<m_tileBits)-1;
587  return (unsigned int)((ref >> m_polyBits) & tileMask);
588 #endif
589  }
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
static const unsigned int DT_TILE_BITS
Definition: DetourNavMesh.h:56
static const unsigned int DT_POLY_BITS
Definition: DetourNavMesh.h:57
+ Here is the caller graph for this function:

◆ encodePolyId()

dtPolyRef dtNavMesh::encodePolyId ( unsigned int  salt,
unsigned int  it,
unsigned int  ip 
) const
inline

Derives a standard polygon reference.

Note
This function is generally meant for internal use only.
Parameters
[in]saltThe tile's salt value.
[in]itThe index of the tile.
[in]ipThe index of the polygon within the tile.
527  {
528 #ifdef DT_POLYREF64
529  return ((dtPolyRef)salt << (DT_POLY_BITS+DT_TILE_BITS)) | ((dtPolyRef)it << DT_POLY_BITS) | (dtPolyRef)ip;
530 #else
531  return ((dtPolyRef)salt << (m_polyBits+m_tileBits)) | ((dtPolyRef)it << m_polyBits) | (dtPolyRef)ip;
532 #endif
533  }
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
static const unsigned int DT_TILE_BITS
Definition: DetourNavMesh.h:56
static const unsigned int DT_POLY_BITS
Definition: DetourNavMesh.h:57
+ Here is the caller graph for this function:

◆ findConnectingPolys()

int dtNavMesh::findConnectingPolys ( const float *  va,
const float *  vb,
const dtMeshTile tile,
int  side,
dtPolyRef con,
float *  conarea,
int  maxcon 
) const
private

Returns all polygons in neighbour tile based on portal defined by the segment.

303 {
304  if (!tile) return 0;
305 
306  float amin[2], amax[2];
307  calcSlabEndPoints(va, vb, amin, amax, side);
308  const float apos = getSlabCoord(va, side);
309 
310  // Remove links pointing to 'side' and compact the links array.
311  float bmin[2], bmax[2];
312  unsigned short m = DT_EXT_LINK | (unsigned short)side;
313  int n = 0;
314 
315  dtPolyRef base = getPolyRefBase(tile);
316 
317  for (int i = 0; i < tile->header->polyCount; ++i)
318  {
319  dtPoly* poly = &tile->polys[i];
320  const int nv = poly->vertCount;
321  for (int j = 0; j < nv; ++j)
322  {
323  // Skip edges which do not point to the right side.
324  if (poly->neis[j] != m) continue;
325 
326  const float* vc = &tile->verts[poly->verts[j]*3];
327  const float* vd = &tile->verts[poly->verts[(j+1) % nv]*3];
328  const float bpos = getSlabCoord(vc, side);
329 
330  // Segments are not close enough.
331  if (dtAbs(apos-bpos) > 0.01f)
332  continue;
333 
334  // Check if the segments touch.
335  calcSlabEndPoints(vc,vd, bmin,bmax, side);
336 
337  if (!overlapSlabs(amin,amax, bmin,bmax, 0.01f, tile->header->walkableClimb)) continue;
338 
339  // Add return value.
340  if (n < maxcon)
341  {
342  conarea[n*2+0] = dtMax(amin[0], bmin[0]);
343  conarea[n*2+1] = dtMin(amax[0], bmax[0]);
344  con[n] = base | (dtPolyRef)i;
345  n++;
346  }
347  break;
348  }
349  }
350  return n;
351 }
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:293
float walkableClimb
The maximum climb height of the agents using the tile.
Definition: DetourNavMesh.h:278
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
static float getSlabCoord(const float *va, const int side)
Definition: DetourNavMesh.cpp:67
unsigned short verts[DT_VERTS_PER_POLYGON]
Definition: DetourNavMesh.h:169
static void calcSlabEndPoints(const float *va, const float *vb, float *bmin, float *bmax, const int side)
Definition: DetourNavMesh.cpp:76
unsigned short neis[DT_VERTS_PER_POLYGON]
Packed data representing neighbor polygons references and flags for each edge.
Definition: DetourNavMesh.h:172
T dtAbs(T a)
Definition: DetourCommon.h:63
Definition: DetourNavMesh.h:162
int polyCount
The number of polygons in the tile.
Definition: DetourNavMesh.h:264
T dtMax(T a, T b)
Definition: DetourCommon.h:58
bool overlapSlabs(const float *amin, const float *amax, const float *bmin, const float *bmax, const float px, const float py)
Definition: DetourNavMesh.cpp:31
float * verts
The tile vertices. [Size: dtMeshHeader::vertCount].
Definition: DetourNavMesh.h:295
dtPolyRef getPolyRefBase(const dtMeshTile *tile) const
Definition: DetourNavMesh.cpp:1287
static const unsigned short DT_EXT_LINK
Definition: DetourNavMesh.h:97
T dtMin(T a, T b)
Definition: DetourCommon.h:52
unsigned char vertCount
The number of vertices in the polygon.
Definition: DetourNavMesh.h:178
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:294
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ findNearestPolyInTile()

dtPolyRef dtNavMesh::findNearestPolyInTile ( const dtMeshTile tile,
const float *  center,
const float *  halfExtents,
float *  nearestPt 
) const
private

Find nearest polygon within a tile.

701 {
702  float bmin[3], bmax[3];
703  dtVsub(bmin, center, halfExtents);
704  dtVadd(bmax, center, halfExtents);
705 
706  // Get nearby polygons from proximity grid.
707  dtPolyRef polys[128];
708  int polyCount = queryPolygonsInTile(tile, bmin, bmax, polys, 128);
709 
710  // Find nearest polygon amongst the nearby polygons.
711  dtPolyRef nearest = 0;
712  float nearestDistanceSqr = FLT_MAX;
713  for (int i = 0; i < polyCount; ++i)
714  {
715  dtPolyRef ref = polys[i];
716  float closestPtPoly[3];
717  float diff[3];
718  bool posOverPoly = false;
719  float d;
720  closestPointOnPoly(ref, center, closestPtPoly, &posOverPoly);
721 
722  // If a point is directly over a polygon and closer than
723  // climb height, favor that instead of straight line nearest point.
724  dtVsub(diff, center, closestPtPoly);
725  if (posOverPoly)
726  {
727  d = dtAbs(diff[1]) - tile->header->walkableClimb;
728  d = d > 0 ? d*d : 0;
729  }
730  else
731  {
732  d = dtVlenSqr(diff);
733  }
734 
735  if (d < nearestDistanceSqr)
736  {
737  dtVcopy(nearestPt, closestPtPoly);
738  nearestDistanceSqr = d;
739  nearest = ref;
740  }
741  }
742 
743  return nearest;
744 }
float dtVlenSqr(const float *v)
Definition: DetourCommon.h:209
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:293
float walkableClimb
The maximum climb height of the agents using the tile.
Definition: DetourNavMesh.h:278
void closestPointOnPoly(dtPolyRef ref, const float *pos, float *closest, bool *posOverPoly) const
Returns closest point on polygon.
Definition: DetourNavMesh.cpp:619
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
void dtVadd(float *dest, const float *v1, const float *v2)
Definition: DetourCommon.h:129
T dtAbs(T a)
Definition: DetourCommon.h:63
int queryPolygonsInTile(const dtMeshTile *tile, const float *qmin, const float *qmax, dtPolyRef *polys, const int maxPolys) const
Queries polygons within a tile.
Definition: DetourNavMesh.cpp:746
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:191
void dtVsub(float *dest, const float *v1, const float *v2)
Definition: DetourCommon.h:140
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ getMaxTiles()

int dtNavMesh::getMaxTiles ( ) const

The maximum number of tiles supported by the navigation mesh.

Returns
The maximum number of tiles supported by the navigation mesh.
1108 {
1109  return m_maxTiles;
1110 }
int m_maxTiles
Max number of tiles.
Definition: DetourNavMesh.h:657
+ Here is the caller graph for this function:

◆ getNeighbourTilesAt()

int dtNavMesh::getNeighbourTilesAt ( const int  x,
const int  y,
const int  side,
dtMeshTile **  tiles,
const int  maxTiles 
) const
private

Returns neighbour tile based on side.

1008 {
1009  int nx = x, ny = y;
1010  switch (side)
1011  {
1012  case 0: nx++; break;
1013  case 1: nx++; ny++; break;
1014  case 2: ny++; break;
1015  case 3: nx--; ny++; break;
1016  case 4: nx--; break;
1017  case 5: nx--; ny--; break;
1018  case 6: ny--; break;
1019  case 7: nx++; ny--; break;
1020  };
1021 
1022  return getTilesAt(nx, ny, tiles, maxTiles);
1023 }
int getTilesAt(const int x, const int y, dtMeshTile const **tiles, const int maxTiles) const
Definition: DetourNavMesh.cpp:1051
G3D::int16 y
Definition: Vector2int16.h:38
G3D::int16 x
Definition: Vector2int16.h:37
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ getOffMeshConnectionByRef()

const dtOffMeshConnection * dtNavMesh::getOffMeshConnectionByRef ( dtPolyRef  ref) const

Gets the specified off-mesh connection.

Parameters
[in]refThe polygon reference of the off-mesh connection.
Returns
The specified off-mesh connection, or null if the polygon reference is not valid.
1434 {
1435  unsigned int salt, it, ip;
1436 
1437  if (!ref)
1438  return 0;
1439 
1440  // Get current polygon
1441  decodePolyId(ref, salt, it, ip);
1442  if (it >= (unsigned int)m_maxTiles) return 0;
1443  if (m_tiles[it].salt != salt || m_tiles[it].header == 0) return 0;
1444  const dtMeshTile* tile = &m_tiles[it];
1445  if (ip >= (unsigned int)tile->header->polyCount) return 0;
1446  const dtPoly* poly = &tile->polys[ip];
1447 
1448  // Make sure that the current poly is indeed off-mesh link.
1449  if (poly->getType() != DT_POLYTYPE_OFFMESH_CONNECTION)
1450  return 0;
1451 
1452  const unsigned int idx = ip - tile->header->offMeshBase;
1453  dtAssert(idx < (unsigned int)tile->header->offMeshConCount);
1454  return &tile->offMeshCons[idx];
1455 }
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:293
#define dtAssert(expression)
Definition: DetourAssert.h:47
unsigned char getType() const
Gets the polygon type. (See: dtPolyTypes)
Definition: DetourNavMesh.h:194
dtOffMeshConnection * offMeshCons
The tile off-mesh connections. [Size: dtMeshHeader::offMeshConCount].
Definition: DetourNavMesh.h:309
int m_maxTiles
Max number of tiles.
Definition: DetourNavMesh.h:657
int offMeshConCount
The number of off-mesh connections.
Definition: DetourNavMesh.h:274
int offMeshBase
The index of the first polygon which is an off-mesh connection.
Definition: DetourNavMesh.h:275
dtMeshTile * m_tiles
List of tiles.
Definition: DetourNavMesh.h:663
Definition: DetourNavMesh.h:162
int polyCount
The number of polygons in the tile.
Definition: DetourNavMesh.h:264
The polygon is an off-mesh connection consisting of two vertices.
Definition: DetourNavMesh.h:156
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:294
Definition: DetourNavMesh.h:288
void decodePolyId(dtPolyRef ref, unsigned int &salt, unsigned int &it, unsigned int &ip) const
Definition: DetourNavMesh.h:542
+ Here is the call graph for this function:

◆ getOffMeshConnectionPolyEndPoints()

dtStatus dtNavMesh::getOffMeshConnectionPolyEndPoints ( dtPolyRef  prevRef,
dtPolyRef  polyRef,
float *  startPos,
float *  endPos 
) const

Gets the endpoints for an off-mesh connection, ordered by "direction of travel".

Parameters
[in]prevRefThe reference of the polygon before the connection.
[in]polyRefThe reference of the off-mesh connection polygon.
[out]startPosThe start position of the off-mesh connection. [(x, y, z)]
[out]endPosThe end position of the off-mesh connection. [(x, y, z)]
Returns
The status flags for the operation.

Off-mesh connections are stored in the navigation mesh as special 2-vertex polygons with a single edge. At least one of the vertices is expected to be inside a normal polygon. So an off-mesh connection is "entered" from a normal polygon at one of its endpoints. This is the polygon identified by the prevRef parameter.

1391 {
1392  unsigned int salt, it, ip;
1393 
1394  if (!polyRef)
1395  return DT_FAILURE;
1396 
1397  // Get current polygon
1398  decodePolyId(polyRef, salt, it, ip);
1399  if (it >= (unsigned int)m_maxTiles) return DT_FAILURE | DT_INVALID_PARAM;
1400  if (m_tiles[it].salt != salt || m_tiles[it].header == 0) return DT_FAILURE | DT_INVALID_PARAM;
1401  const dtMeshTile* tile = &m_tiles[it];
1402  if (ip >= (unsigned int)tile->header->polyCount) return DT_FAILURE | DT_INVALID_PARAM;
1403  const dtPoly* poly = &tile->polys[ip];
1404 
1405  // Make sure that the current poly is indeed off-mesh link.
1406  if (poly->getType() != DT_POLYTYPE_OFFMESH_CONNECTION)
1407  return DT_FAILURE;
1408 
1409  // Figure out which way to hand out the vertices.
1410  int idx0 = 0, idx1 = 1;
1411 
1412  // Find link that points to first vertex.
1413  for (unsigned int i = poly->firstLink; i != DT_NULL_LINK; i = tile->links[i].next)
1414  {
1415  if (tile->links[i].edge == 0)
1416  {
1417  if (tile->links[i].ref != prevRef)
1418  {
1419  idx0 = 1;
1420  idx1 = 0;
1421  }
1422  break;
1423  }
1424  }
1425 
1426  dtVcopy(startPos, &tile->verts[poly->verts[idx0]*3]);
1427  dtVcopy(endPos, &tile->verts[poly->verts[idx1]*3]);
1428 
1429  return DT_SUCCESS;
1430 }
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:293
unsigned char getType() const
Gets the polygon type. (See: dtPolyTypes)
Definition: DetourNavMesh.h:194
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
int m_maxTiles
Max number of tiles.
Definition: DetourNavMesh.h:657
unsigned short verts[DT_VERTS_PER_POLYGON]
Definition: DetourNavMesh.h:169
dtMeshTile * m_tiles
List of tiles.
Definition: DetourNavMesh.h:663
Definition: DetourNavMesh.h:162
int polyCount
The number of polygons in the tile.
Definition: DetourNavMesh.h:264
float * verts
The tile vertices. [Size: dtMeshHeader::vertCount].
Definition: DetourNavMesh.h:295
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
dtLink * links
The tile links. [Size: dtMeshHeader::maxLinkCount].
Definition: DetourNavMesh.h:296
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:191
The polygon is an off-mesh connection consisting of two vertices.
Definition: DetourNavMesh.h:156
unsigned int firstLink
Index to first link in linked list. (Or DT_NULL_LINK if there is no link.)
Definition: DetourNavMesh.h:165
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:294
Definition: DetourNavMesh.h:288
void decodePolyId(dtPolyRef ref, unsigned int &salt, unsigned int &it, unsigned int &ip) const
Definition: DetourNavMesh.h:542
static const unsigned int DT_NULL_LINK
A value that indicates the entity does not link to anything.
Definition: DetourNavMesh.h:100
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ getParams()

const dtNavMeshParams * dtNavMesh::getParams ( ) const

The navigation mesh initialization params.

Note
The parameters are created automatically when the single tile initialization is performed.
295 {
296  return &m_params;
297 }
dtNavMeshParams m_params
Current initialization params. TODO: do not store this info twice.
Definition: DetourNavMesh.h:654
+ Here is the caller graph for this function:

◆ getPolyArea()

dtStatus dtNavMesh::getPolyArea ( dtPolyRef  ref,
unsigned char *  resultArea 
) const

Gets the user defined area for the specified polygon.

Parameters
[in]refThe polygon reference.
[out]resultAreaThe area id for the polygon.
Returns
The status flags for the operation.
1508 {
1509  if (!ref) return DT_FAILURE;
1510  unsigned int salt, it, ip;
1511  decodePolyId(ref, salt, it, ip);
1512  if (it >= (unsigned int)m_maxTiles) return DT_FAILURE | DT_INVALID_PARAM;
1513  if (m_tiles[it].salt != salt || m_tiles[it].header == 0) return DT_FAILURE | DT_INVALID_PARAM;
1514  const dtMeshTile* tile = &m_tiles[it];
1515  if (ip >= (unsigned int)tile->header->polyCount) return DT_FAILURE | DT_INVALID_PARAM;
1516  const dtPoly* poly = &tile->polys[ip];
1517 
1518  *resultArea = poly->getArea();
1519 
1520  return DT_SUCCESS;
1521 }
unsigned char getArea() const
Gets the user defined area id.
Definition: DetourNavMesh.h:191
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:293
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
int m_maxTiles
Max number of tiles.
Definition: DetourNavMesh.h:657
dtMeshTile * m_tiles
List of tiles.
Definition: DetourNavMesh.h:663
Definition: DetourNavMesh.h:162
int polyCount
The number of polygons in the tile.
Definition: DetourNavMesh.h:264
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:294
Definition: DetourNavMesh.h:288
void decodePolyId(dtPolyRef ref, unsigned int &salt, unsigned int &it, unsigned int &ip) const
Definition: DetourNavMesh.h:542
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:

◆ getPolyFlags()

dtStatus dtNavMesh::getPolyFlags ( dtPolyRef  ref,
unsigned short *  resultFlags 
) const

Gets the user defined flags for the specified polygon.

Parameters
[in]refThe polygon reference.
[out]resultFlagsThe polygon flags.
Returns
The status flags for the operation.
1476 {
1477  if (!ref) return DT_FAILURE;
1478  unsigned int salt, it, ip;
1479  decodePolyId(ref, salt, it, ip);
1480  if (it >= (unsigned int)m_maxTiles) return DT_FAILURE | DT_INVALID_PARAM;
1481  if (m_tiles[it].salt != salt || m_tiles[it].header == 0) return DT_FAILURE | DT_INVALID_PARAM;
1482  const dtMeshTile* tile = &m_tiles[it];
1483  if (ip >= (unsigned int)tile->header->polyCount) return DT_FAILURE | DT_INVALID_PARAM;
1484  const dtPoly* poly = &tile->polys[ip];
1485 
1486  *resultFlags = poly->flags;
1487 
1488  return DT_SUCCESS;
1489 }
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:293
unsigned short flags
The user defined polygon flags.
Definition: DetourNavMesh.h:175
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
int m_maxTiles
Max number of tiles.
Definition: DetourNavMesh.h:657
dtMeshTile * m_tiles
List of tiles.
Definition: DetourNavMesh.h:663
Definition: DetourNavMesh.h:162
int polyCount
The number of polygons in the tile.
Definition: DetourNavMesh.h:264
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:294
Definition: DetourNavMesh.h:288
void decodePolyId(dtPolyRef ref, unsigned int &salt, unsigned int &it, unsigned int &ip) const
Definition: DetourNavMesh.h:542
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:

◆ getPolyRefBase()

dtPolyRef dtNavMesh::getPolyRefBase ( const dtMeshTile tile) const

Gets the polygon reference for the tile's base polygon.

Parameters
[in]tileThe tile.
Returns
The polygon reference for the base polygon in the specified tile.

Example use case:

const dtPolyRef base = navmesh->getPolyRefBase(tile);
for (int i = 0; i < tile->header->polyCount; ++i)
{
const dtPoly* p = &tile->polys[i];
const dtPolyRef ref = base | (dtPolyRef)i;
// Use the reference to access the polygon data.
}
1288 {
1289  if (!tile) return 0;
1290  const unsigned int it = (unsigned int)(tile - m_tiles);
1291  return encodePolyId(tile->salt, it, 0);
1292 }
dtPolyRef encodePolyId(unsigned int salt, unsigned int it, unsigned int ip) const
Definition: DetourNavMesh.h:526
dtMeshTile * m_tiles
List of tiles.
Definition: DetourNavMesh.h:663
unsigned int salt
Counter describing modifications to the tile.
Definition: DetourNavMesh.h:290
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ getTile() [1/2]

const dtMeshTile * dtNavMesh::getTile ( int  i) const

Gets the tile at the specified index.

Parameters
[in]iThe tile index. [Limit: 0 >= index < getMaxTiles()]
Returns
The tile at the specified index.
1118 {
1119  return &m_tiles[i];
1120 }
dtMeshTile * m_tiles
List of tiles.
Definition: DetourNavMesh.h:663
+ Here is the caller graph for this function:

◆ getTile() [2/2]

dtMeshTile * dtNavMesh::getTile ( int  i)
private

Returns pointer to tile in the tile array.

1113 {
1114  return &m_tiles[i];
1115 }
dtMeshTile * m_tiles
List of tiles.
Definition: DetourNavMesh.h:663

◆ getTileAndPolyByRef()

dtStatus dtNavMesh::getTileAndPolyByRef ( const dtPolyRef  ref,
const dtMeshTile **  tile,
const dtPoly **  poly 
) const

Gets the tile and polygon for the specified polygon reference.

Parameters
[in]refThe reference for the a polygon.
[out]tileThe tile containing the polygon.
[out]polyThe polygon.
Returns
The status flags for the operation.
1129 {
1130  if (!ref) return DT_FAILURE;
1131  unsigned int salt, it, ip;
1132  decodePolyId(ref, salt, it, ip);
1133  if (it >= (unsigned int)m_maxTiles) return DT_FAILURE | DT_INVALID_PARAM;
1134  if (m_tiles[it].salt != salt || m_tiles[it].header == 0) return DT_FAILURE | DT_INVALID_PARAM;
1135  if (ip >= (unsigned int)m_tiles[it].header->polyCount) return DT_FAILURE | DT_INVALID_PARAM;
1136  *tile = &m_tiles[it];
1137  *poly = &m_tiles[it].polys[ip];
1138  return DT_SUCCESS;
1139 }
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
int m_maxTiles
Max number of tiles.
Definition: DetourNavMesh.h:657
dtMeshTile * m_tiles
List of tiles.
Definition: DetourNavMesh.h:663
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:294
void decodePolyId(dtPolyRef ref, unsigned int &salt, unsigned int &it, unsigned int &ip) const
Definition: DetourNavMesh.h:542
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ getTileAndPolyByRefUnsafe()

void dtNavMesh::getTileAndPolyByRefUnsafe ( const dtPolyRef  ref,
const dtMeshTile **  tile,
const dtPoly **  poly 
) const

Returns the tile and polygon for the specified polygon reference.

Parameters
[in]refA known valid reference for a polygon.
[out]tileThe tile containing the polygon.
[out]polyThe polygon.
Warning
Only use this function if it is known that the provided polygon reference is valid. This function is faster than getTileAndPolyByRef, but it does not validate the reference.
1147 {
1148  unsigned int salt, it, ip;
1149  decodePolyId(ref, salt, it, ip);
1150  *tile = &m_tiles[it];
1151  *poly = &m_tiles[it].polys[ip];
1152 }
dtMeshTile * m_tiles
List of tiles.
Definition: DetourNavMesh.h:663
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:294
void decodePolyId(dtPolyRef ref, unsigned int &salt, unsigned int &it, unsigned int &ip) const
Definition: DetourNavMesh.h:542
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ getTileAt()

const dtMeshTile * dtNavMesh::getTileAt ( const int  x,
const int  y,
const int  layer 
) const

Gets the tile at the specified grid location.

Parameters
[in]xThe tile's x-location. (x, y, layer)
[in]yThe tile's y-location. (x, y, layer)
[in]layerThe tile's layer. (x, y, layer)
Returns
The tile, or null if the tile does not exist.
989 {
990  // Find tile based on hash.
991  int h = computeTileHash(x,y,m_tileLutMask);
992  dtMeshTile* tile = m_posLookup[h];
993  while (tile)
994  {
995  if (tile->header &&
996  tile->header->x == x &&
997  tile->header->y == y &&
998  tile->header->layer == layer)
999  {
1000  return tile;
1001  }
1002  tile = tile->next;
1003  }
1004  return 0;
1005 }
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:293
dtMeshTile ** m_posLookup
Tile hash lookup.
Definition: DetourNavMesh.h:661
int m_tileLutMask
Tile hash lookup mask.
Definition: DetourNavMesh.h:659
int layer
The layer of the tile within the dtNavMesh tile grid. (x, y, layer)
Definition: DetourNavMesh.h:262
dtMeshTile * next
The next free tile, or the next tile in the spatial grid.
Definition: DetourNavMesh.h:314
int x
The x-position of the tile within the dtNavMesh tile grid. (x, y, layer)
Definition: DetourNavMesh.h:260
G3D::int16 y
Definition: Vector2int16.h:38
int computeTileHash(int x, int y, const int mask)
Definition: DetourNavMesh.cpp:114
G3D::int16 x
Definition: Vector2int16.h:37
Definition: DetourNavMesh.h:288
int y
The y-position of the tile within the dtNavMesh tile grid. (x, y, layer)
Definition: DetourNavMesh.h:261
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ getTileByRef()

const dtMeshTile * dtNavMesh::getTileByRef ( dtTileRef  ref) const

Gets the tile for the specified tile reference.

Parameters
[in]refThe tile reference of the tile to retrieve.
Returns
The tile for the specified reference, or null if the reference is invalid.
1094 {
1095  if (!ref)
1096  return 0;
1097  unsigned int tileIndex = decodePolyIdTile((dtPolyRef)ref);
1098  unsigned int tileSalt = decodePolyIdSalt((dtPolyRef)ref);
1099  if ((int)tileIndex >= m_maxTiles)
1100  return 0;
1101  const dtMeshTile* tile = &m_tiles[tileIndex];
1102  if (tile->salt != tileSalt)
1103  return 0;
1104  return tile;
1105 }
unsigned int decodePolyIdSalt(dtPolyRef ref) const
Definition: DetourNavMesh.h:565
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
int m_maxTiles
Max number of tiles.
Definition: DetourNavMesh.h:657
dtMeshTile * m_tiles
List of tiles.
Definition: DetourNavMesh.h:663
unsigned int salt
Counter describing modifications to the tile.
Definition: DetourNavMesh.h:290
unsigned int decodePolyIdTile(dtPolyRef ref) const
Definition: DetourNavMesh.h:580
Definition: DetourNavMesh.h:288
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ getTileRef()

dtTileRef dtNavMesh::getTileRef ( const dtMeshTile tile) const

Gets the tile reference for the specified tile.

Parameters
[in]tileThe tile.
Returns
The tile reference of the tile.
1267 {
1268  if (!tile) return 0;
1269  const unsigned int it = (unsigned int)(tile - m_tiles);
1270  return (dtTileRef)encodePolyId(tile->salt, it, 0);
1271 }
uint64_d dtTileRef
Definition: DetourNavMesh.h:66
dtPolyRef encodePolyId(unsigned int salt, unsigned int it, unsigned int ip) const
Definition: DetourNavMesh.h:526
dtMeshTile * m_tiles
List of tiles.
Definition: DetourNavMesh.h:663
unsigned int salt
Counter describing modifications to the tile.
Definition: DetourNavMesh.h:290
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ getTileRefAt()

dtTileRef dtNavMesh::getTileRefAt ( int  x,
int  y,
int  layer 
) const

Gets the tile reference for the tile at specified grid location.

Parameters
[in]xThe tile's x-location. (x, y, layer)
[in]yThe tile's y-location. (x, y, layer)
[in]layerThe tile's layer. (x, y, layer)
Returns
The tile reference of the tile, or 0 if there is none.
1075 {
1076  // Find tile based on hash.
1077  int h = computeTileHash(x,y,m_tileLutMask);
1078  dtMeshTile* tile = m_posLookup[h];
1079  while (tile)
1080  {
1081  if (tile->header &&
1082  tile->header->x == x &&
1083  tile->header->y == y &&
1084  tile->header->layer == layer)
1085  {
1086  return getTileRef(tile);
1087  }
1088  tile = tile->next;
1089  }
1090  return 0;
1091 }
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:293
dtMeshTile ** m_posLookup
Tile hash lookup.
Definition: DetourNavMesh.h:661
int m_tileLutMask
Tile hash lookup mask.
Definition: DetourNavMesh.h:659
int layer
The layer of the tile within the dtNavMesh tile grid. (x, y, layer)
Definition: DetourNavMesh.h:262
dtMeshTile * next
The next free tile, or the next tile in the spatial grid.
Definition: DetourNavMesh.h:314
dtTileRef getTileRef(const dtMeshTile *tile) const
Definition: DetourNavMesh.cpp:1266
int x
The x-position of the tile within the dtNavMesh tile grid. (x, y, layer)
Definition: DetourNavMesh.h:260
G3D::int16 y
Definition: Vector2int16.h:38
int computeTileHash(int x, int y, const int mask)
Definition: DetourNavMesh.cpp:114
G3D::int16 x
Definition: Vector2int16.h:37
Definition: DetourNavMesh.h:288
int y
The y-position of the tile within the dtNavMesh tile grid. (x, y, layer)
Definition: DetourNavMesh.h:261
+ Here is the call graph for this function:

◆ getTilesAt() [1/2]

int dtNavMesh::getTilesAt ( const int  x,
const int  y,
dtMeshTile const **  tiles,
const int  maxTiles 
) const

Gets all tiles at the specified grid location. (All layers.)

Parameters
[in]xThe tile's x-location. (x, y)
[in]yThe tile's y-location. (x, y)
[out]tilesA pointer to an array of tiles that will hold the result.
[in]maxTilesThe maximum tiles the tiles parameter can hold.
Returns
The number of tiles returned in the tiles array.

This function will not fail if the tiles array is too small to hold the entire result set. It will simply fill the array to capacity.

1052 {
1053  int n = 0;
1054 
1055  // Find tile based on hash.
1056  int h = computeTileHash(x,y,m_tileLutMask);
1057  dtMeshTile* tile = m_posLookup[h];
1058  while (tile)
1059  {
1060  if (tile->header &&
1061  tile->header->x == x &&
1062  tile->header->y == y)
1063  {
1064  if (n < maxTiles)
1065  tiles[n++] = tile;
1066  }
1067  tile = tile->next;
1068  }
1069 
1070  return n;
1071 }
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:293
dtMeshTile ** m_posLookup
Tile hash lookup.
Definition: DetourNavMesh.h:661
int m_tileLutMask
Tile hash lookup mask.
Definition: DetourNavMesh.h:659
dtMeshTile * next
The next free tile, or the next tile in the spatial grid.
Definition: DetourNavMesh.h:314
int x
The x-position of the tile within the dtNavMesh tile grid. (x, y, layer)
Definition: DetourNavMesh.h:260
G3D::int16 y
Definition: Vector2int16.h:38
int computeTileHash(int x, int y, const int mask)
Definition: DetourNavMesh.cpp:114
G3D::int16 x
Definition: Vector2int16.h:37
Definition: DetourNavMesh.h:288
int y
The y-position of the tile within the dtNavMesh tile grid. (x, y, layer)
Definition: DetourNavMesh.h:261
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ getTilesAt() [2/2]

int dtNavMesh::getTilesAt ( const int  x,
const int  y,
dtMeshTile **  tiles,
const int  maxTiles 
) const
private

Returns neighbour tile based on side.

1026 {
1027  int n = 0;
1028 
1029  // Find tile based on hash.
1030  int h = computeTileHash(x,y,m_tileLutMask);
1031  dtMeshTile* tile = m_posLookup[h];
1032  while (tile)
1033  {
1034  if (tile->header &&
1035  tile->header->x == x &&
1036  tile->header->y == y)
1037  {
1038  if (n < maxTiles)
1039  tiles[n++] = tile;
1040  }
1041  tile = tile->next;
1042  }
1043 
1044  return n;
1045 }
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:293
dtMeshTile ** m_posLookup
Tile hash lookup.
Definition: DetourNavMesh.h:661
int m_tileLutMask
Tile hash lookup mask.
Definition: DetourNavMesh.h:659
dtMeshTile * next
The next free tile, or the next tile in the spatial grid.
Definition: DetourNavMesh.h:314
int x
The x-position of the tile within the dtNavMesh tile grid. (x, y, layer)
Definition: DetourNavMesh.h:260
G3D::int16 y
Definition: Vector2int16.h:38
int computeTileHash(int x, int y, const int mask)
Definition: DetourNavMesh.cpp:114
G3D::int16 x
Definition: Vector2int16.h:37
Definition: DetourNavMesh.h:288
int y
The y-position of the tile within the dtNavMesh tile grid. (x, y, layer)
Definition: DetourNavMesh.h:261
+ Here is the call graph for this function:

◆ getTileStateSize()

int dtNavMesh::getTileStateSize ( const dtMeshTile tile) const

Gets the size of the buffer required by storeTileState to store the specified tile's state.

Parameters
[in]tileThe tile.
Returns
The size of the buffer required to store the state.
See also
storeTileState
1309 {
1310  if (!tile) return 0;
1311  const int headerSize = dtAlign4(sizeof(dtTileState));
1312  const int polyStateSize = dtAlign4(sizeof(dtPolyState) * tile->header->polyCount);
1313  return headerSize + polyStateSize;
1314 }
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:293
Definition: DetourNavMesh.cpp:1294
int polyCount
The number of polygons in the tile.
Definition: DetourNavMesh.h:264
int dtAlign4(int x)
Definition: DetourCommon.h:442
Definition: DetourNavMesh.cpp:1301
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ init() [1/2]

dtStatus dtNavMesh::init ( const dtNavMeshParams params)

Initializes the navigation mesh for tiled use.

Parameters
[in]paramsInitialization parameters.
Returns
The status flags for the operation.
225 {
226  memcpy(&m_params, params, sizeof(dtNavMeshParams));
227  dtVcopy(m_orig, params->orig);
228  m_tileWidth = params->tileWidth;
229  m_tileHeight = params->tileHeight;
230 
231  // Init tiles
232  m_maxTiles = params->maxTiles;
233  m_tileLutSize = dtNextPow2(params->maxTiles/4);
234  if (!m_tileLutSize) m_tileLutSize = 1;
236 
238  if (!m_tiles)
239  return DT_FAILURE | DT_OUT_OF_MEMORY;
241  if (!m_posLookup)
242  return DT_FAILURE | DT_OUT_OF_MEMORY;
243  memset(m_tiles, 0, sizeof(dtMeshTile)*m_maxTiles);
244  memset(m_posLookup, 0, sizeof(dtMeshTile*)*m_tileLutSize);
245  m_nextFree = 0;
246  for (int i = m_maxTiles-1; i >= 0; --i)
247  {
248  m_tiles[i].salt = 1;
249  m_tiles[i].next = m_nextFree;
250  m_nextFree = &m_tiles[i];
251  }
252 
253  // Init ID generator values.
254 #ifndef DT_POLYREF64
255  m_tileBits = dtIlog2(dtNextPow2((unsigned int)params->maxTiles));
256  m_polyBits = dtIlog2(dtNextPow2((unsigned int)params->maxPolys));
257  // Only allow 31 salt bits, since the salt mask is calculated using 32bit uint and it will overflow.
258  m_saltBits = dtMin((unsigned int)31, 32 - m_tileBits - m_polyBits);
259 
260  if (m_saltBits < 10)
261  return DT_FAILURE | DT_INVALID_PARAM;
262 #endif
263 
264  return DT_SUCCESS;
265 }
dtMeshTile ** m_posLookup
Tile hash lookup.
Definition: DetourNavMesh.h:661
float orig[3]
The world space origin of the navigation mesh&#39;s tile space. [(x, y, z)].
Definition: DetourNavMesh.h:326
dtNavMeshParams m_params
Current initialization params. TODO: do not store this info twice.
Definition: DetourNavMesh.h:654
void * dtAlloc(size_t size, dtAllocHint hint)
Definition: DetourAlloc.cpp:41
float m_tileHeight
Dimensions of each tile.
Definition: DetourNavMesh.h:656
Memory persist after a function call.
Definition: DetourAlloc.h:28
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
int m_maxTiles
Max number of tiles.
Definition: DetourNavMesh.h:657
float m_orig[3]
Origin of the tile (0,0)
Definition: DetourNavMesh.h:655
float m_tileWidth
Definition: DetourNavMesh.h:656
int m_tileLutMask
Tile hash lookup mask.
Definition: DetourNavMesh.h:659
dtMeshTile * m_tiles
List of tiles.
Definition: DetourNavMesh.h:663
dtMeshTile * next
The next free tile, or the next tile in the spatial grid.
Definition: DetourNavMesh.h:314
unsigned int salt
Counter describing modifications to the tile.
Definition: DetourNavMesh.h:290
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
int m_tileLutSize
Tile hash lookup size (must be pot).
Definition: DetourNavMesh.h:658
unsigned int dtNextPow2(unsigned int v)
Definition: DetourCommon.h:418
dtMeshTile * m_nextFree
Freelist of tiles.
Definition: DetourNavMesh.h:662
int maxPolys
The maximum number of polygons each tile can contain.
Definition: DetourNavMesh.h:330
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:191
T dtMin(T a, T b)
Definition: DetourCommon.h:52
float tileWidth
The width of each tile. (Along the x-axis.)
Definition: DetourNavMesh.h:327
Definition: DetourNavMesh.h:324
float tileHeight
The height of each tile. (Along the z-axis.)
Definition: DetourNavMesh.h:328
Definition: DetourNavMesh.h:288
int maxTiles
The maximum number of tiles the navigation mesh can contain.
Definition: DetourNavMesh.h:329
unsigned int dtIlog2(unsigned int v)
Definition: DetourCommon.h:430
static const unsigned int DT_OUT_OF_MEMORY
Definition: DetourStatus.h:33
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ init() [2/2]

dtStatus dtNavMesh::init ( unsigned char *  data,
const int  dataSize,
const int  flags 
)

Initializes the navigation mesh for single tile use.

Parameters
[in]dataData of the new tile. (See: dtCreateNavMeshData)
[in]dataSizeThe data size of the new tile.
[in]flagsThe tile flags. (See: dtTileFlags)
Returns
The status flags for the operation.
See also
dtCreateNavMeshData
268 {
269  // Make sure the data is in right format.
270  dtMeshHeader* header = (dtMeshHeader*)data;
271  if (header->magic != DT_NAVMESH_MAGIC)
272  return DT_FAILURE | DT_WRONG_MAGIC;
273  if (header->version != DT_NAVMESH_VERSION)
274  return DT_FAILURE | DT_WRONG_VERSION;
275 
277  dtVcopy(params.orig, header->bmin);
278  params.tileWidth = header->bmax[0] - header->bmin[0];
279  params.tileHeight = header->bmax[2] - header->bmin[2];
280  params.maxTiles = 1;
281  params.maxPolys = header->polyCount;
282 
283  dtStatus status = init(&params);
284  if (dtStatusFailed(status))
285  return status;
286 
287  return addTile(data, dataSize, flags, 0, 0);
288 }
static const unsigned int DT_WRONG_VERSION
Definition: DetourStatus.h:32
dtStatus init(const dtNavMeshParams *params)
Definition: DetourNavMesh.cpp:224
float orig[3]
The world space origin of the navigation mesh&#39;s tile space. [(x, y, z)].
Definition: DetourNavMesh.h:326
constexpr auto data(C &c)
Definition: advstd.h:96
dtStatus addTile(unsigned char *data, int dataSize, int flags, dtTileRef lastRef, dtTileRef *result)
Definition: DetourNavMesh.cpp:846
float bmax[3]
The maximum bounds of the tile&#39;s AABB. [(x, y, z)].
Definition: DetourNavMesh.h:280
unsigned int dtStatus
Definition: DetourStatus.h:22
static const unsigned int DT_WRONG_MAGIC
Definition: DetourStatus.h:31
Definition: DetourNavMesh.h:256
int polyCount
The number of polygons in the tile.
Definition: DetourNavMesh.h:264
float bmin[3]
The minimum bounds of the tile&#39;s AABB. [(x, y, z)].
Definition: DetourNavMesh.h:279
int version
Tile data format version number.
Definition: DetourNavMesh.h:259
bool dtStatusFailed(dtStatus status)
Definition: DetourStatus.h:47
int maxPolys
The maximum number of polygons each tile can contain.
Definition: DetourNavMesh.h:330
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:191
int magic
Tile magic number. (Used to identify the data format.)
Definition: DetourNavMesh.h:258
float tileWidth
The width of each tile. (Along the x-axis.)
Definition: DetourNavMesh.h:327
Definition: DetourNavMesh.h:324
float tileHeight
The height of each tile. (Along the z-axis.)
Definition: DetourNavMesh.h:328
static const int DT_NAVMESH_MAGIC
A magic number used to detect compatibility of navigation tile data.
Definition: DetourNavMesh.h:82
uint8 flags
Definition: DisableMgr.cpp:47
int maxTiles
The maximum number of tiles the navigation mesh can contain.
Definition: DetourNavMesh.h:329
std::unordered_set< uint32 > params[2]
Definition: DisableMgr.cpp:48
static const int DT_NAVMESH_VERSION
A version number used to detect compatibility of navigation tile data.
Definition: DetourNavMesh.h:85
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:

◆ isValidPolyRef()

bool dtNavMesh::isValidPolyRef ( dtPolyRef  ref) const

Checks the validity of a polygon reference.

Parameters
[in]refThe polygon reference to check.
Returns
True if polygon reference is valid for the navigation mesh.
1155 {
1156  if (!ref) return false;
1157  unsigned int salt, it, ip;
1158  decodePolyId(ref, salt, it, ip);
1159  if (it >= (unsigned int)m_maxTiles) return false;
1160  if (m_tiles[it].salt != salt || m_tiles[it].header == 0) return false;
1161  if (ip >= (unsigned int)m_tiles[it].header->polyCount) return false;
1162  return true;
1163 }
int m_maxTiles
Max number of tiles.
Definition: DetourNavMesh.h:657
dtMeshTile * m_tiles
List of tiles.
Definition: DetourNavMesh.h:663
void decodePolyId(dtPolyRef ref, unsigned int &salt, unsigned int &it, unsigned int &ip) const
Definition: DetourNavMesh.h:542
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ operator=()

dtNavMesh& dtNavMesh::operator= ( const dtNavMesh )
private

◆ queryPolygonsInTile()

int dtNavMesh::queryPolygonsInTile ( const dtMeshTile tile,
const float *  qmin,
const float *  qmax,
dtPolyRef polys,
const int  maxPolys 
) const
private

Queries polygons within a tile.

748 {
749  if (tile->bvTree)
750  {
751  const dtBVNode* node = &tile->bvTree[0];
752  const dtBVNode* end = &tile->bvTree[tile->header->bvNodeCount];
753  const float* tbmin = tile->header->bmin;
754  const float* tbmax = tile->header->bmax;
755  const float qfac = tile->header->bvQuantFactor;
756 
757  // Calculate quantized box
758  unsigned short bmin[3], bmax[3];
759  // dtClamp query box to world box.
760  float minx = dtClamp(qmin[0], tbmin[0], tbmax[0]) - tbmin[0];
761  float miny = dtClamp(qmin[1], tbmin[1], tbmax[1]) - tbmin[1];
762  float minz = dtClamp(qmin[2], tbmin[2], tbmax[2]) - tbmin[2];
763  float maxx = dtClamp(qmax[0], tbmin[0], tbmax[0]) - tbmin[0];
764  float maxy = dtClamp(qmax[1], tbmin[1], tbmax[1]) - tbmin[1];
765  float maxz = dtClamp(qmax[2], tbmin[2], tbmax[2]) - tbmin[2];
766  // Quantize
767  bmin[0] = (unsigned short)(qfac * minx) & 0xfffe;
768  bmin[1] = (unsigned short)(qfac * miny) & 0xfffe;
769  bmin[2] = (unsigned short)(qfac * minz) & 0xfffe;
770  bmax[0] = (unsigned short)(qfac * maxx + 1) | 1;
771  bmax[1] = (unsigned short)(qfac * maxy + 1) | 1;
772  bmax[2] = (unsigned short)(qfac * maxz + 1) | 1;
773 
774  // Traverse tree
775  dtPolyRef base = getPolyRefBase(tile);
776  int n = 0;
777  while (node < end)
778  {
779  const bool overlap = dtOverlapQuantBounds(bmin, bmax, node->bmin, node->bmax);
780  const bool isLeafNode = node->i >= 0;
781 
782  if (isLeafNode && overlap)
783  {
784  if (n < maxPolys)
785  polys[n++] = base | (dtPolyRef)node->i;
786  }
787 
788  if (overlap || isLeafNode)
789  node++;
790  else
791  {
792  const int escapeIndex = -node->i;
793  node += escapeIndex;
794  }
795  }
796 
797  return n;
798  }
799  else
800  {
801  float bmin[3], bmax[3];
802  int n = 0;
803  dtPolyRef base = getPolyRefBase(tile);
804  for (int i = 0; i < tile->header->polyCount; ++i)
805  {
806  dtPoly* p = &tile->polys[i];
807  // Do not return off-mesh connection polygons.
809  continue;
810  // Calc polygon bounds.
811  const float* v = &tile->verts[p->verts[0]*3];
812  dtVcopy(bmin, v);
813  dtVcopy(bmax, v);
814  for (int j = 1; j < p->vertCount; ++j)
815  {
816  v = &tile->verts[p->verts[j]*3];
817  dtVmin(bmin, v);
818  dtVmax(bmax, v);
819  }
820  if (dtOverlapBounds(qmin,qmax, bmin,bmax))
821  {
822  if (n < maxPolys)
823  polys[n++] = base | (dtPolyRef)i;
824  }
825  }
826  return n;
827  }
828 }
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:293
unsigned short bmax[3]
Maximum bounds of the node&#39;s AABB. [(x, y, z)].
Definition: DetourNavMesh.h:225
unsigned char getType() const
Gets the polygon type. (See: dtPolyTypes)
Definition: DetourNavMesh.h:194
void dtVmin(float *mn, const float *v)
Definition: DetourCommon.h:161
float bvQuantFactor
The bounding volume quantization factor.
Definition: DetourNavMesh.h:283
void dtVmax(float *mx, const float *v)
Definition: DetourCommon.h:171
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
dtBVNode * bvTree
Definition: DetourNavMesh.h:307
float bmax[3]
The maximum bounds of the tile&#39;s AABB. [(x, y, z)].
Definition: DetourNavMesh.h:280
unsigned short verts[DT_VERTS_PER_POLYGON]
Definition: DetourNavMesh.h:169
int i
The node&#39;s index. (Negative for escape sequence.)
Definition: DetourNavMesh.h:226
Definition: DetourNavMesh.h:222
unsigned short bmin[3]
Minimum bounds of the node&#39;s AABB. [(x, y, z)].
Definition: DetourNavMesh.h:224
bool dtOverlapQuantBounds(const unsigned short amin[3], const unsigned short amax[3], const unsigned short bmin[3], const unsigned short bmax[3])
Definition: DetourCommon.h:333
Definition: DetourNavMesh.h:162
int polyCount
The number of polygons in the tile.
Definition: DetourNavMesh.h:264
int bvNodeCount
The number of bounding volume nodes. (Zero if bounding volumes are disabled.)
Definition: DetourNavMesh.h:273
float bmin[3]
The minimum bounds of the tile&#39;s AABB. [(x, y, z)].
Definition: DetourNavMesh.h:279
T dtClamp(T v, T mn, T mx)
Definition: DetourCommon.h:75
float * verts
The tile vertices. [Size: dtMeshHeader::vertCount].
Definition: DetourNavMesh.h:295
iterator end()
Definition: GridRefManager.h:36
dtPolyRef getPolyRefBase(const dtMeshTile *tile) const
Definition: DetourNavMesh.cpp:1287
void dtVcopy(float *dest, const float *a)
Definition: DetourCommon.h:191
The polygon is an off-mesh connection consisting of two vertices.
Definition: DetourNavMesh.h:156
unsigned char vertCount
The number of vertices in the polygon.
Definition: DetourNavMesh.h:178
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:294
bool dtOverlapBounds(const float *amin, const float *amax, const float *bmin, const float *bmax)
Definition: DetourCommon.h:350
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ removeTile()

dtStatus dtNavMesh::removeTile ( dtTileRef  ref,
unsigned char **  data,
int *  dataSize 
)

Removes the specified tile from the navigation mesh.

Parameters
[in]refThe reference of the tile to remove.
[out]dataData associated with deleted tile.
[out]dataSizeSize of the data associated with deleted tile.
Returns
The status flags for the operation.

This function returns the data for the tile so that, if desired, it can be added back to the navigation mesh at a later point.

See also
addTile
1172 {
1173  if (!ref)
1174  return DT_FAILURE | DT_INVALID_PARAM;
1175  unsigned int tileIndex = decodePolyIdTile((dtPolyRef)ref);
1176  unsigned int tileSalt = decodePolyIdSalt((dtPolyRef)ref);
1177  if ((int)tileIndex >= m_maxTiles)
1178  return DT_FAILURE | DT_INVALID_PARAM;
1179  dtMeshTile* tile = &m_tiles[tileIndex];
1180  if (tile->salt != tileSalt)
1181  return DT_FAILURE | DT_INVALID_PARAM;
1182 
1183  // Remove tile from hash lookup.
1184  int h = computeTileHash(tile->header->x,tile->header->y,m_tileLutMask);
1185  dtMeshTile* prev = 0;
1186  dtMeshTile* cur = m_posLookup[h];
1187  while (cur)
1188  {
1189  if (cur == tile)
1190  {
1191  if (prev)
1192  prev->next = cur->next;
1193  else
1194  m_posLookup[h] = cur->next;
1195  break;
1196  }
1197  prev = cur;
1198  cur = cur->next;
1199  }
1200 
1201  // Remove connections to neighbour tiles.
1202  static const int MAX_NEIS = 32;
1203  dtMeshTile* neis[MAX_NEIS];
1204  int nneis;
1205 
1206  // Disconnect from other layers in current tile.
1207  nneis = getTilesAt(tile->header->x, tile->header->y, neis, MAX_NEIS);
1208  for (int j = 0; j < nneis; ++j)
1209  {
1210  if (neis[j] == tile) continue;
1211  unconnectLinks(neis[j], tile);
1212  }
1213 
1214  // Disconnect from neighbour tiles.
1215  for (int i = 0; i < 8; ++i)
1216  {
1217  nneis = getNeighbourTilesAt(tile->header->x, tile->header->y, i, neis, MAX_NEIS);
1218  for (int j = 0; j < nneis; ++j)
1219  unconnectLinks(neis[j], tile);
1220  }
1221 
1222  // Reset tile.
1223  if (tile->flags & DT_TILE_FREE_DATA)
1224  {
1225  // Owns data
1226  dtFree(tile->data);
1227  tile->data = 0;
1228  tile->dataSize = 0;
1229  if (data) *data = 0;
1230  if (dataSize) *dataSize = 0;
1231  }
1232  else
1233  {
1234  if (data) *data = tile->data;
1235  if (dataSize) *dataSize = tile->dataSize;
1236  }
1237 
1238  tile->header = 0;
1239  tile->flags = 0;
1240  tile->linksFreeList = 0;
1241  tile->polys = 0;
1242  tile->verts = 0;
1243  tile->links = 0;
1244  tile->detailMeshes = 0;
1245  tile->detailVerts = 0;
1246  tile->detailTris = 0;
1247  tile->bvTree = 0;
1248  tile->offMeshCons = 0;
1249 
1250  // Update salt, salt should never be zero.
1251 #ifdef DT_POLYREF64
1252  tile->salt = (tile->salt+1) & ((1<<DT_SALT_BITS)-1);
1253 #else
1254  tile->salt = (tile->salt+1) & ((1<<m_saltBits)-1);
1255 #endif
1256  if (tile->salt == 0)
1257  tile->salt++;
1258 
1259  // Add to free list.
1260  tile->next = m_nextFree;
1261  m_nextFree = tile;
1262 
1263  return DT_SUCCESS;
1264 }
The navigation mesh owns the tile memory and is responsible for freeing it.
Definition: DetourNavMesh.h:114
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:293
static const unsigned int DT_SALT_BITS
Definition: DetourNavMesh.h:55
dtMeshTile ** m_posLookup
Tile hash lookup.
Definition: DetourNavMesh.h:661
constexpr auto data(C &c)
Definition: advstd.h:96
dtOffMeshConnection * offMeshCons
The tile off-mesh connections. [Size: dtMeshHeader::offMeshConCount].
Definition: DetourNavMesh.h:309
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
unsigned int decodePolyIdSalt(dtPolyRef ref) const
Definition: DetourNavMesh.h:565
uint64_d dtPolyRef
Definition: DetourNavMesh.h:58
int m_maxTiles
Max number of tiles.
Definition: DetourNavMesh.h:657
dtBVNode * bvTree
Definition: DetourNavMesh.h:307
int m_tileLutMask
Tile hash lookup mask.
Definition: DetourNavMesh.h:659
int flags
Tile flags. (See: dtTileFlags)
Definition: DetourNavMesh.h:313
dtMeshTile * m_tiles
List of tiles.
Definition: DetourNavMesh.h:663
dtMeshTile * next
The next free tile, or the next tile in the spatial grid.
Definition: DetourNavMesh.h:314
int getTilesAt(const int x, const int y, dtMeshTile const **tiles, const int maxTiles) const
Definition: DetourNavMesh.cpp:1051
int x
The x-position of the tile within the dtNavMesh tile grid. (x, y, layer)
Definition: DetourNavMesh.h:260
unsigned int linksFreeList
Index to the next free link.
Definition: DetourNavMesh.h:292
unsigned int salt
Counter describing modifications to the tile.
Definition: DetourNavMesh.h:290
int getNeighbourTilesAt(const int x, const int y, const int side, dtMeshTile **tiles, const int maxTiles) const
Returns neighbour tile based on side.
Definition: DetourNavMesh.cpp:1007
float * verts
The tile vertices. [Size: dtMeshHeader::vertCount].
Definition: DetourNavMesh.h:295
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
dtLink * links
The tile links. [Size: dtMeshHeader::maxLinkCount].
Definition: DetourNavMesh.h:296
int dataSize
Size of the tile data.
Definition: DetourNavMesh.h:312
float * detailVerts
The detail mesh&#39;s unique vertices. [(x, y, z) * dtMeshHeader::detailVertCount].
Definition: DetourNavMesh.h:300
unsigned char * detailTris
The detail mesh&#39;s triangles. [(vertA, vertB, vertC) * dtMeshHeader::detailTriCount].
Definition: DetourNavMesh.h:303
dtMeshTile * m_nextFree
Freelist of tiles.
Definition: DetourNavMesh.h:662
dtPolyDetail * detailMeshes
The tile&#39;s detail sub-meshes. [Size: dtMeshHeader::detailMeshCount].
Definition: DetourNavMesh.h:297
unsigned int decodePolyIdTile(dtPolyRef ref) const
Definition: DetourNavMesh.h:580
unsigned char * data
The tile data. (Not directly accessed under normal situations.)
Definition: DetourNavMesh.h:311
int prev(int i, int n)
Definition: RecastContour.cpp:468
int computeTileHash(int x, int y, const int mask)
Definition: DetourNavMesh.cpp:114
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:294
Definition: DetourNavMesh.h:288
int y
The y-position of the tile within the dtNavMesh tile grid. (x, y, layer)
Definition: DetourNavMesh.h:261
void unconnectLinks(dtMeshTile *tile, dtMeshTile *target)
Removes external links at specified side.
Definition: DetourNavMesh.cpp:353
void dtFree(void *ptr)
Definition: DetourAlloc.cpp:46
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ restoreTileState()

dtStatus dtNavMesh::restoreTileState ( dtMeshTile tile,
const unsigned char *  data,
const int  maxDataSize 
)

Restores the state of the tile.

Parameters
[in]tileThe tile.
[in]dataThe new state. (Obtained from storeTileState.)
[in]maxDataSizeThe size of the state within the data buffer.
Returns
The status flags for the operation.

Tile state includes non-structural data such as polygon flags, area ids, etc.

Note
This function does not impact the tile's dtTileRef and dtPolyRef's.
See also
storeTileState
1354 {
1355  // Make sure there is enough space to store the state.
1356  const int sizeReq = getTileStateSize(tile);
1357  if (maxDataSize < sizeReq)
1358  return DT_FAILURE | DT_INVALID_PARAM;
1359 
1360  const dtTileState* tileState = dtGetThenAdvanceBufferPointer<const dtTileState>(data, dtAlign4(sizeof(dtTileState)));
1361  const dtPolyState* polyStates = dtGetThenAdvanceBufferPointer<const dtPolyState>(data, dtAlign4(sizeof(dtPolyState) * tile->header->polyCount));
1362 
1363  // Check that the restore is possible.
1364  if (tileState->magic != DT_NAVMESH_STATE_MAGIC)
1365  return DT_FAILURE | DT_WRONG_MAGIC;
1366  if (tileState->version != DT_NAVMESH_STATE_VERSION)
1367  return DT_FAILURE | DT_WRONG_VERSION;
1368  if (tileState->ref != getTileRef(tile))
1369  return DT_FAILURE | DT_INVALID_PARAM;
1370 
1371  // Restore per poly state.
1372  for (int i = 0; i < tile->header->polyCount; ++i)
1373  {
1374  dtPoly* p = &tile->polys[i];
1375  const dtPolyState* s = &polyStates[i];
1376  p->flags = s->flags;
1377  p->setArea(s->area);
1378  }
1379 
1380  return DT_SUCCESS;
1381 }
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:293
static const unsigned int DT_WRONG_VERSION
Definition: DetourStatus.h:32
unsigned short flags
The user defined polygon flags.
Definition: DetourNavMesh.h:175
static const int DT_NAVMESH_STATE_VERSION
A version number used to detect compatibility of navigation tile states.
Definition: DetourNavMesh.h:91
constexpr auto data(C &c)
Definition: advstd.h:96
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
void setArea(unsigned char a)
Sets the user defined area id. [Limit: < DT_MAX_AREAS].
Definition: DetourNavMesh.h:185
static const unsigned int DT_WRONG_MAGIC
Definition: DetourStatus.h:31
Definition: DetourNavMesh.cpp:1294
dtTileRef getTileRef(const dtMeshTile *tile) const
Definition: DetourNavMesh.cpp:1266
Definition: DetourNavMesh.h:162
int polyCount
The number of polygons in the tile.
Definition: DetourNavMesh.h:264
int magic
Definition: DetourNavMesh.cpp:1296
dtTileRef ref
Definition: DetourNavMesh.cpp:1298
unsigned short flags
Definition: DetourNavMesh.cpp:1303
int getTileStateSize(const dtMeshTile *tile) const
Definition: DetourNavMesh.cpp:1308
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
int dtAlign4(int x)
Definition: DetourCommon.h:442
int version
Definition: DetourNavMesh.cpp:1297
static const int DT_NAVMESH_STATE_MAGIC
A magic number used to detect the compatibility of navigation tile states.
Definition: DetourNavMesh.h:88
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:294
unsigned char area
Definition: DetourNavMesh.cpp:1304
Definition: DetourNavMesh.cpp:1301
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:

◆ setPolyArea()

dtStatus dtNavMesh::setPolyArea ( dtPolyRef  ref,
unsigned char  area 
)

Sets the user defined area for the specified polygon.

Parameters
[in]refThe polygon reference.
[in]areaThe new area id for the polygon. [Limit: < DT_MAX_AREAS]
Returns
The status flags for the operation.
1492 {
1493  if (!ref) return DT_FAILURE;
1494  unsigned int salt, it, ip;
1495  decodePolyId(ref, salt, it, ip);
1496  if (it >= (unsigned int)m_maxTiles) return DT_FAILURE | DT_INVALID_PARAM;
1497  if (m_tiles[it].salt != salt || m_tiles[it].header == 0) return DT_FAILURE | DT_INVALID_PARAM;
1498  dtMeshTile* tile = &m_tiles[it];
1499  if (ip >= (unsigned int)tile->header->polyCount) return DT_FAILURE | DT_INVALID_PARAM;
1500  dtPoly* poly = &tile->polys[ip];
1501 
1502  poly->setArea(area);
1503 
1504  return DT_SUCCESS;
1505 }
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:293
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
void setArea(unsigned char a)
Sets the user defined area id. [Limit: < DT_MAX_AREAS].
Definition: DetourNavMesh.h:185
int m_maxTiles
Max number of tiles.
Definition: DetourNavMesh.h:657
dtMeshTile * m_tiles
List of tiles.
Definition: DetourNavMesh.h:663
Definition: DetourNavMesh.h:162
int polyCount
The number of polygons in the tile.
Definition: DetourNavMesh.h:264
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:294
Definition: DetourNavMesh.h:288
void decodePolyId(dtPolyRef ref, unsigned int &salt, unsigned int &it, unsigned int &ip) const
Definition: DetourNavMesh.h:542
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:

◆ setPolyFlags()

dtStatus dtNavMesh::setPolyFlags ( dtPolyRef  ref,
unsigned short  flags 
)

Sets the user defined flags for the specified polygon.

Parameters
[in]refThe polygon reference.
[in]flagsThe new flags for the polygon.
Returns
The status flags for the operation.
1459 {
1460  if (!ref) return DT_FAILURE;
1461  unsigned int salt, it, ip;
1462  decodePolyId(ref, salt, it, ip);
1463  if (it >= (unsigned int)m_maxTiles) return DT_FAILURE | DT_INVALID_PARAM;
1464  if (m_tiles[it].salt != salt || m_tiles[it].header == 0) return DT_FAILURE | DT_INVALID_PARAM;
1465  dtMeshTile* tile = &m_tiles[it];
1466  if (ip >= (unsigned int)tile->header->polyCount) return DT_FAILURE | DT_INVALID_PARAM;
1467  dtPoly* poly = &tile->polys[ip];
1468 
1469  // Change flags.
1470  poly->flags = flags;
1471 
1472  return DT_SUCCESS;
1473 }
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:293
unsigned short flags
The user defined polygon flags.
Definition: DetourNavMesh.h:175
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
int m_maxTiles
Max number of tiles.
Definition: DetourNavMesh.h:657
dtMeshTile * m_tiles
List of tiles.
Definition: DetourNavMesh.h:663
Definition: DetourNavMesh.h:162
int polyCount
The number of polygons in the tile.
Definition: DetourNavMesh.h:264
static const unsigned int DT_INVALID_PARAM
Definition: DetourStatus.h:34
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:294
uint8 flags
Definition: DisableMgr.cpp:47
Definition: DetourNavMesh.h:288
void decodePolyId(dtPolyRef ref, unsigned int &salt, unsigned int &it, unsigned int &ip) const
Definition: DetourNavMesh.h:542
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:

◆ storeTileState()

dtStatus dtNavMesh::storeTileState ( const dtMeshTile tile,
unsigned char *  data,
const int  maxDataSize 
) const

Stores the non-structural state of the tile in the specified buffer. (Flags, area ids, etc.)

Parameters
[in]tileThe tile.
[out]dataThe buffer to store the tile's state in.
[in]maxDataSizeThe size of the data buffer. [Limit: >= getTileStateSize]
Returns
The status flags for the operation.

Tile state includes non-structural data such as polygon flags, area ids, etc.

Note
The state data is only valid until the tile reference changes.
See also
getTileStateSize, restoreTileState
1322 {
1323  // Make sure there is enough space to store the state.
1324  const int sizeReq = getTileStateSize(tile);
1325  if (maxDataSize < sizeReq)
1327 
1328  dtTileState* tileState = dtGetThenAdvanceBufferPointer<dtTileState>(data, dtAlign4(sizeof(dtTileState)));
1329  dtPolyState* polyStates = dtGetThenAdvanceBufferPointer<dtPolyState>(data, dtAlign4(sizeof(dtPolyState) * tile->header->polyCount));
1330 
1331  // Store tile state.
1332  tileState->magic = DT_NAVMESH_STATE_MAGIC;
1333  tileState->version = DT_NAVMESH_STATE_VERSION;
1334  tileState->ref = getTileRef(tile);
1335 
1336  // Store per poly state.
1337  for (int i = 0; i < tile->header->polyCount; ++i)
1338  {
1339  const dtPoly* p = &tile->polys[i];
1340  dtPolyState* s = &polyStates[i];
1341  s->flags = p->flags;
1342  s->area = p->getArea();
1343  }
1344 
1345  return DT_SUCCESS;
1346 }
unsigned char getArea() const
Gets the user defined area id.
Definition: DetourNavMesh.h:191
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:293
unsigned short flags
The user defined polygon flags.
Definition: DetourNavMesh.h:175
static const int DT_NAVMESH_STATE_VERSION
A version number used to detect compatibility of navigation tile states.
Definition: DetourNavMesh.h:91
constexpr auto data(C &c)
Definition: advstd.h:96
static const unsigned int DT_SUCCESS
Definition: DetourStatus.h:26
static const unsigned int DT_BUFFER_TOO_SMALL
Definition: DetourStatus.h:35
Definition: DetourNavMesh.cpp:1294
dtTileRef getTileRef(const dtMeshTile *tile) const
Definition: DetourNavMesh.cpp:1266
Definition: DetourNavMesh.h:162
int polyCount
The number of polygons in the tile.
Definition: DetourNavMesh.h:264
int magic
Definition: DetourNavMesh.cpp:1296
dtTileRef ref
Definition: DetourNavMesh.cpp:1298
unsigned short flags
Definition: DetourNavMesh.cpp:1303
int getTileStateSize(const dtMeshTile *tile) const
Definition: DetourNavMesh.cpp:1308
int dtAlign4(int x)
Definition: DetourCommon.h:442
int version
Definition: DetourNavMesh.cpp:1297
static const int DT_NAVMESH_STATE_MAGIC
A magic number used to detect the compatibility of navigation tile states.
Definition: DetourNavMesh.h:88
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:294
unsigned char area
Definition: DetourNavMesh.cpp:1304
Definition: DetourNavMesh.cpp:1301
static const unsigned int DT_FAILURE
Definition: DetourStatus.h:25
+ Here is the call graph for this function:

◆ unconnectLinks()

void dtNavMesh::unconnectLinks ( dtMeshTile tile,
dtMeshTile target 
)
private

Removes external links at specified side.

354 {
355  if (!tile || !target) return;
356 
357  const unsigned int targetNum = decodePolyIdTile(getTileRef(target));
358 
359  for (int i = 0; i < tile->header->polyCount; ++i)
360  {
361  dtPoly* poly = &tile->polys[i];
362  unsigned int j = poly->firstLink;
363  unsigned int pj = DT_NULL_LINK;
364  while (j != DT_NULL_LINK)
365  {
366  if (decodePolyIdTile(tile->links[j].ref) == targetNum)
367  {
368  // Remove link.
369  unsigned int nj = tile->links[j].next;
370  if (pj == DT_NULL_LINK)
371  poly->firstLink = nj;
372  else
373  tile->links[pj].next = nj;
374  freeLink(tile, j);
375  j = nj;
376  }
377  else
378  {
379  // Advance
380  pj = j;
381  j = tile->links[j].next;
382  }
383  }
384  }
385 }
dtMeshHeader * header
The tile header.
Definition: DetourNavMesh.h:293
dtTileRef getTileRef(const dtMeshTile *tile) const
Definition: DetourNavMesh.cpp:1266
Definition: DetourNavMesh.h:162
int polyCount
The number of polygons in the tile.
Definition: DetourNavMesh.h:264
void freeLink(dtMeshTile *tile, unsigned int link)
Definition: DetourNavMesh.cpp:131
dtLink * links
The tile links. [Size: dtMeshHeader::maxLinkCount].
Definition: DetourNavMesh.h:296
unsigned int decodePolyIdTile(dtPolyRef ref) const
Definition: DetourNavMesh.h:580
unsigned int firstLink
Index to first link in linked list. (Or DT_NULL_LINK if there is no link.)
Definition: DetourNavMesh.h:165
dtPoly * polys
The tile polygons. [Size: dtMeshHeader::polyCount].
Definition: DetourNavMesh.h:294
static const unsigned int DT_NULL_LINK
A value that indicates the entity does not link to anything.
Definition: DetourNavMesh.h:100
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

Member Data Documentation

◆ m_maxTiles

int dtNavMesh::m_maxTiles
private

Max number of tiles.

◆ m_nextFree

dtMeshTile* dtNavMesh::m_nextFree
private

Freelist of tiles.

◆ m_orig

float dtNavMesh::m_orig[3]
private

Origin of the tile (0,0)

◆ m_params

dtNavMeshParams dtNavMesh::m_params
private

Current initialization params. TODO: do not store this info twice.

◆ m_posLookup

dtMeshTile** dtNavMesh::m_posLookup
private

Tile hash lookup.

◆ m_tileHeight

float dtNavMesh::m_tileHeight
private

Dimensions of each tile.

◆ m_tileLutMask

int dtNavMesh::m_tileLutMask
private

Tile hash lookup mask.

◆ m_tileLutSize

int dtNavMesh::m_tileLutSize
private

Tile hash lookup size (must be pot).

◆ m_tiles

dtMeshTile* dtNavMesh::m_tiles
private

List of tiles.

◆ m_tileWidth

float dtNavMesh::m_tileWidth
private

The documentation for this class was generated from the following files: