diff options
Diffstat (limited to 'extern/recastnavigation/Detour')
12 files changed, 0 insertions, 4174 deletions
diff --git a/extern/recastnavigation/Detour/Include/DetourCommon.h b/extern/recastnavigation/Detour/Include/DetourCommon.h deleted file mode 100644 index d824efc06e4..00000000000 --- a/extern/recastnavigation/Detour/Include/DetourCommon.h +++ /dev/null @@ -1,167 +0,0 @@ -// -// Copyright (c) 2009 Mikko Mononen memon@inside.org -// -// This software is provided 'as-is', without any express or implied -// warranty. In no event will the authors be held liable for any damages -// arising from the use of this software. -// Permission is granted to anyone to use this software for any purpose, -// including commercial applications, and to alter it and redistribute it -// freely, subject to the following restrictions: -// 1. The origin of this software must not be misrepresented; you must not -// claim that you wrote the original software. If you use this software -// in a product, an acknowledgment in the product documentation would be -// appreciated but is not required. -// 2. Altered source versions must be plainly marked as such, and must not be -// misrepresented as being the original software. -// 3. This notice may not be removed or altered from any source distribution. -// - -#ifndef DETOURCOMMON_H -#define DETOURCOMMON_H - -////////////////////////////////////////////////////////////////////////////////////////// - -template<class T> inline void swap(T& a, T& b) { T t = a; a = b; b = t; } -template<class T> inline T min(T a, T b) { return a < b ? a : b; } -template<class T> inline T max(T a, T b) { return a > b ? a : b; } -template<class T> inline T abs(T a) { return a < 0 ? -a : a; } -template<class T> inline T sqr(T a) { return a*a; } -template<class T> inline T clamp(T v, T mn, T mx) { return v < mn ? mn : (v > mx ? mx : v); } - -inline void vcross(float* dest, const float* v1, const float* v2) -{ - dest[0] = v1[1]*v2[2] - v1[2]*v2[1]; - dest[1] = v1[2]*v2[0] - v1[0]*v2[2]; - dest[2] = v1[0]*v2[1] - v1[1]*v2[0]; -} - -inline float vdot(const float* v1, const float* v2) -{ - return v1[0]*v2[0] + v1[1]*v2[1] + v1[2]*v2[2]; -} - -inline void vmad(float* dest, const float* v1, const float* v2, const float s) -{ - dest[0] = v1[0]+v2[0]*s; - dest[1] = v1[1]+v2[1]*s; - dest[2] = v1[2]+v2[2]*s; -} - -inline void vadd(float* dest, const float* v1, const float* v2) -{ - dest[0] = v1[0]+v2[0]; - dest[1] = v1[1]+v2[1]; - dest[2] = v1[2]+v2[2]; -} - -inline void vsub(float* dest, const float* v1, const float* v2) -{ - dest[0] = v1[0]-v2[0]; - dest[1] = v1[1]-v2[1]; - dest[2] = v1[2]-v2[2]; -} - -inline void vmin(float* mn, const float* v) -{ - mn[0] = min(mn[0], v[0]); - mn[1] = min(mn[1], v[1]); - mn[2] = min(mn[2], v[2]); -} - -inline void vmax(float* mx, const float* v) -{ - mx[0] = max(mx[0], v[0]); - mx[1] = max(mx[1], v[1]); - mx[2] = max(mx[2], v[2]); -} - -inline void vcopy(float* dest, const float* a) -{ - dest[0] = a[0]; - dest[1] = a[1]; - dest[2] = a[2]; -} - -inline float vdist(const float* v1, const float* v2) -{ - float dx = v2[0] - v1[0]; - float dy = v2[1] - v1[1]; - float dz = v2[2] - v1[2]; - return sqrtf(dx*dx + dy*dy + dz*dz); -} - -inline float vdistSqr(const float* v1, const float* v2) -{ - float dx = v2[0] - v1[0]; - float dy = v2[1] - v1[1]; - float dz = v2[2] - v1[2]; - return dx*dx + dy*dy + dz*dz; -} - -inline void vnormalize(float* v) -{ - float d = 1.0f / sqrtf(sqr(v[0]) + sqr(v[1]) + sqr(v[2])); - v[0] *= d; - v[1] *= d; - v[2] *= d; -} - -inline bool vequal(const float* p0, const float* p1) -{ - static const float thr = sqr(1.0f/16384.0f); - const float d = vdistSqr(p0, p1); - return d < thr; -} - -inline int nextPow2(int v) -{ - v--; - v |= v >> 1; - v |= v >> 2; - v |= v >> 4; - v |= v >> 8; - v |= v >> 16; - v++; - return v; -} - -inline float vdot2D(const float* u, const float* v) -{ - return u[0]*v[0] + u[2]*v[2]; -} - -inline float vperp2D(const float* u, const float* v) -{ - return u[2]*v[0] - u[0]*v[2]; -} - -inline float triArea2D(const float* a, const float* b, const float* c) -{ - return ((b[0]*a[2] - a[0]*b[2]) + (c[0]*b[2] - b[0]*c[2]) + (a[0]*c[2] - c[0]*a[2])) * 0.5f; -} - -inline bool checkOverlapBox(const unsigned short amin[3], const unsigned short amax[3], - const unsigned short bmin[3], const unsigned short bmax[3]) -{ - bool overlap = true; - overlap = (amin[0] > bmax[0] || amax[0] < bmin[0]) ? false : overlap; - overlap = (amin[1] > bmax[1] || amax[1] < bmin[1]) ? false : overlap; - overlap = (amin[2] > bmax[2] || amax[2] < bmin[2]) ? false : overlap; - return overlap; -} - -void closestPtPointTriangle(float* closest, const float* p, - const float* a, const float* b, const float* c); - -bool closestHeightPointTriangle(const float* p, const float* a, const float* b, const float* c, float& h); - -bool intersectSegmentPoly2D(const float* p0, const float* p1, - const float* verts, int nverts, - float& tmin, float& tmax, - int& segMin, int& segMax); - -float distancePtSegSqr2D(const float* pt, const float* p, const float* q, float& t); - -void calcPolyCenter(float* tc, const unsigned short* idx, int nidx, const float* verts); - -#endif // DETOURCOMMON_H
\ No newline at end of file diff --git a/extern/recastnavigation/Detour/Include/DetourNode.h b/extern/recastnavigation/Detour/Include/DetourNode.h deleted file mode 100644 index 316d5bf4cf6..00000000000 --- a/extern/recastnavigation/Detour/Include/DetourNode.h +++ /dev/null @@ -1,149 +0,0 @@ -// -// Copyright (c) 2009 Mikko Mononen memon@inside.org -// -// This software is provided 'as-is', without any express or implied -// warranty. In no event will the authors be held liable for any damages -// arising from the use of this software. -// Permission is granted to anyone to use this software for any purpose, -// including commercial applications, and to alter it and redistribute it -// freely, subject to the following restrictions: -// 1. The origin of this software must not be misrepresented; you must not -// claim that you wrote the original software. If you use this software -// in a product, an acknowledgment in the product documentation would be -// appreciated but is not required. -// 2. Altered source versions must be plainly marked as such, and must not be -// misrepresented as being the original software. -// 3. This notice may not be removed or altered from any source distribution. -// - -#ifndef DETOURNODE_H -#define DETOURNODE_H - -enum dtNodeFlags -{ - DT_NODE_OPEN = 0x01, - DT_NODE_CLOSED = 0x02, -}; - -struct dtNode -{ - float cost; - float total; - unsigned int id; - unsigned int pidx : 30; - unsigned int flags : 2; -}; - -class dtNodePool -{ -public: - dtNodePool(int maxNodes, int hashSize); - ~dtNodePool(); - inline void operator=(const dtNodePool&) {} - void clear(); - dtNode* getNode(unsigned int id); - const dtNode* findNode(unsigned int id) const; - - inline unsigned int getNodeIdx(const dtNode* node) const - { - if (!node) return 0; - return (unsigned int)(node - m_nodes)+1; - } - - inline dtNode* getNodeAtIdx(unsigned int idx) - { - if (!idx) return 0; - return &m_nodes[idx-1]; - } - - inline int getMemUsed() const - { - return sizeof(*this) + - sizeof(dtNode)*m_maxNodes + - sizeof(unsigned short)*m_maxNodes + - sizeof(unsigned short)*m_hashSize; - } - -private: - inline unsigned int hashint(unsigned int a) const - { - a += ~(a<<15); - a ^= (a>>10); - a += (a<<3); - a ^= (a>>6); - a += ~(a<<11); - a ^= (a>>16); - return a; - } - - dtNode* m_nodes; - unsigned short* m_first; - unsigned short* m_next; - const int m_maxNodes; - const int m_hashSize; - int m_nodeCount; -}; - -class dtNodeQueue -{ -public: - dtNodeQueue(int n); - ~dtNodeQueue(); - inline void operator=(dtNodeQueue&) {} - - inline void clear() - { - m_size = 0; - } - - inline dtNode* top() - { - return m_heap[0]; - } - - inline dtNode* pop() - { - dtNode* result = m_heap[0]; - m_size--; - trickleDown(0, m_heap[m_size]); - return result; - } - - inline void push(dtNode* node) - { - m_size++; - bubbleUp(m_size-1, node); - } - - inline void modify(dtNode* node) - { - for (int i = 0; i < m_size; ++i) - { - if (m_heap[i] == node) - { - bubbleUp(i, node); - return; - } - } - } - - inline bool empty() const { return m_size == 0; } - - inline int getMemUsed() const - { - return sizeof(*this) + - sizeof(dtNode*)*(m_capacity+1); - } - - -private: - void bubbleUp(int i, dtNode* node); - void trickleDown(int i, dtNode* node); - - dtNode** m_heap; - const int m_capacity; - int m_size; -}; - - -#endif // DETOURNODE_H
\ No newline at end of file diff --git a/extern/recastnavigation/Detour/Include/DetourStatNavMesh.h b/extern/recastnavigation/Detour/Include/DetourStatNavMesh.h deleted file mode 100644 index 5a3e04a2074..00000000000 --- a/extern/recastnavigation/Detour/Include/DetourStatNavMesh.h +++ /dev/null @@ -1,234 +0,0 @@ -// -// Copyright (c) 2009 Mikko Mononen memon@inside.org -// -// This software is provided 'as-is', without any express or implied -// warranty. In no event will the authors be held liable for any damages -// arising from the use of this software. -// Permission is granted to anyone to use this software for any purpose, -// including commercial applications, and to alter it and redistribute it -// freely, subject to the following restrictions: -// 1. The origin of this software must not be misrepresented; you must not -// claim that you wrote the original software. If you use this software -// in a product, an acknowledgment in the product documentation would be -// appreciated but is not required. -// 2. Altered source versions must be plainly marked as such, and must not be -// misrepresented as being the original software. -// 3. This notice may not be removed or altered from any source distribution. -// - -#ifndef DETOURSTATNAVMESH_H -#define DETOURSTATNAVMESH_H - -// Reference to navigation polygon. -typedef unsigned short dtStatPolyRef; - -// Maximum number of vertices per navigation polygon. -static const int DT_STAT_VERTS_PER_POLYGON = 6; - -// Structure holding the navigation polygon data. -struct dtStatPoly -{ - unsigned short v[DT_STAT_VERTS_PER_POLYGON]; // Indices to vertices of the poly. - dtStatPolyRef n[DT_STAT_VERTS_PER_POLYGON]; // Refs to neighbours of the poly. - unsigned char nv; // Number of vertices. - unsigned char flags; // Flags (not used). -}; - -struct dtStatPolyDetail -{ - unsigned short vbase; // Offset to detail vertex array. - unsigned short nverts; // Number of vertices in the detail mesh. - unsigned short tbase; // Offset to detail triangle array. - unsigned short ntris; // Number of triangles. -}; - -const int DT_STAT_NAVMESH_MAGIC = (('N'<<24) | ('A'<<16) | ('V'<<8) | 'M'); -const int DT_STAT_NAVMESH_VERSION = 3; - -struct dtStatBVNode -{ - unsigned short bmin[3], bmax[3]; - int i; -}; - -struct dtStatNavMeshHeader -{ - int magic; - int version; - int npolys; - int nverts; - int nnodes; - int ndmeshes; - int ndverts; - int ndtris; - float cs; - float bmin[3], bmax[3]; - dtStatPoly* polys; - float* verts; - dtStatBVNode* bvtree; - dtStatPolyDetail* dmeshes; - float* dverts; - unsigned char* dtris; -}; - -class dtStatNavMesh -{ -public: - - dtStatNavMesh(); - ~dtStatNavMesh(); - - // Initializes the navmesh with data. - // Params: - // data - (in) Pointer to navmesh data. - // dataSize - (in) size of the navmesh data. - // ownsData - (in) Flag indicating if the navmesh should own and delete the data. - bool init(unsigned char* data, int dataSize, bool ownsData); - - // Finds the nearest navigation polygon around the center location. - // Params: - // center - (in) The center of the search box. - // extents - (in) The extents of the search box. - // Returns: Reference identifier for the polygon, or 0 if no polygons found. - dtStatPolyRef findNearestPoly(const float* center, const float* extents); - - // Returns polygons which touch the query box. - // Params: - // center - (in) the center of the search box. - // extents - (in) the extents of the search box. - // polys - (out) array holding the search result. - // maxPolys - (in) The max number of polygons the polys array can hold. - // Returns: Number of polygons in search result array. - int queryPolygons(const float* center, const float* extents, - dtStatPolyRef* polys, const int maxPolys); - - // Finds path from start polygon to end polygon. - // If target polygon canno be reached through the navigation graph, - // the last node on the array is nearest node to the end polygon. - // Params: - // startRef - (in) ref to path start polygon. - // endRef - (in) ref to path end polygon. - // path - (out) array holding the search result. - // maxPathSize - (in) The max number of polygons the path array can hold. - // Returns: Number of polygons in search result array. - int findPath(dtStatPolyRef startRef, dtStatPolyRef endRef, - const float* startPos, const float* endPos, - dtStatPolyRef* path, const int maxPathSize); - - // Finds a straight path from start to end locations within the corridor - // described by the path polygons. - // Start and end locations will be clamped on the corridor. - // Params: - // startPos - (in) Path start location. - // endPos - (in) Path end location. - // path - (in) Array of connected polygons describing the corridor. - // pathSize - (in) Number of polygons in path array. - // straightPath - (out) Points describing the straight path. - // maxStraightPathSize - (in) The max number of points the straight path array can hold. - // Returns: Number of points in the path. - int findStraightPath(const float* startPos, const float* endPos, - const dtStatPolyRef* path, const int pathSize, - float* straightPath, const int maxStraightPathSize); - - // Finds intersection againts walls starting from start pos. - // Params: - // startRef - (in) ref to the polygon where the start lies. - // startPos - (in) start position of the query. - // endPos - (in) end position of the query. - // t - (out) hit parameter along the segment, 0 if no hit. - // endRef - (out) ref to the last polygon which was processed. - // Returns: Number of polygons in path or 0 if failed. - int raycast(dtStatPolyRef startRef, const float* startPos, const float* endPos, - float& t, dtStatPolyRef* path, const int pathSize); - - // Returns distance to nearest wall from the specified location. - // Params: - // centerRef - (in) ref to the polygon where the center lies. - // centerPos - (in) center if the query circle. - // maxRadius - (in) max search radius. - // hitPos - (out) location of the nearest hit. - // hitNormal - (out) normal of the nearest hit. - // Returns: Distance to nearest wall from the test location. - float findDistanceToWall(dtStatPolyRef centerRef, const float* centerPos, float maxRadius, - float* hitPos, float* hitNormal); - - // Finds polygons found along the navigation graph which touch the specified circle. - // Params: - // centerRef - (in) ref to the polygon where the center lies. - // centerPos - (in) center if the query circle - // radius - (in) radius of the query circle - // resultRef - (out, opt) refs to the polygons touched by the circle. - // resultParent - (out, opt) parent of each result polygon. - // resultCost - (out, opt) search cost at each result polygon. - // maxResult - (int) maximum capacity of search results. - // Returns: Number of results. - int findPolysAround(dtStatPolyRef centerRef, const float* centerPos, float radius, - dtStatPolyRef* resultRef, dtStatPolyRef* resultParent, float* resultCost, - const int maxResult); - - // Returns closest point on navigation polygon. - // Params: - // ref - (in) ref to the polygon. - // pos - (in) the point to check. - // closest - (out) closest point. - // Returns: true if closest point found. - bool closestPointToPoly(dtStatPolyRef ref, const float* pos, float* closest) const; - - // Returns height of the polygon at specified location. - // Params: - // ref - (in) ref to the polygon. - // pos - (in) the point where to locate the height. - // height - (out) height at the location. - // Returns: true if oer polygon. - bool getPolyHeight(dtStatPolyRef ref, const float* pos, float* height) const; - - // Returns pointer to a polygon based on ref. - const dtStatPoly* getPolyByRef(dtStatPolyRef ref) const; - // Returns polygon index based on ref, or -1 if failed. - int getPolyIndexByRef(dtStatPolyRef ref) const; - // Returns number of navigation polygons. - inline int getPolyCount() const { return m_header ? m_header->npolys : 0; } - // Rerturns pointer to specified navigation polygon. - inline const dtStatPoly* getPoly(int i) const { return &m_header->polys[i]; } - // Returns number of vertices. - inline int getVertexCount() const { return m_header ? m_header->nverts : 0; } - // Returns pointer to specified vertex. - inline const float* getVertex(int i) const { return &m_header->verts[i*3]; } - // Returns number of navigation polygons details. - inline int getPolyDetailCount() const { return m_header ? m_header->ndmeshes : 0; } - // Rerturns pointer to specified navigation polygon detail. - const dtStatPolyDetail* getPolyDetail(int i) const { return &m_header->dmeshes[i]; } - // Returns pointer to specified vertex. - inline const float* getDetailVertex(int i) const { return &m_header->dverts[i*3]; } - // Returns pointer to specified vertex. - inline const unsigned char* getDetailTri(int i) const { return &m_header->dtris[i*4]; } - - bool isInClosedList(dtStatPolyRef ref) const; - - int getMemUsed() const; - - inline unsigned char* getData() const { return m_data; } - inline int getDataSize() const { return m_dataSize; } - inline const dtStatNavMeshHeader* getHeader() const { return m_header; } - inline const dtStatBVNode* getBvTreeNodes() const { return m_header ? m_header->bvtree : 0; } - inline int getBvTreeNodeCount() const { return m_header ? m_header->nnodes : 0; } - -private: - - // Copies the locations of vertices of a polygon to an array. - int getPolyVerts(dtStatPolyRef ref, float* verts) const; - // Returns portal points between two polygons. - bool getPortalPoints(dtStatPolyRef from, dtStatPolyRef to, float* left, float* right) const; - // Returns edge mid point between two polygons. - bool getEdgeMidPoint(dtStatPolyRef from, dtStatPolyRef to, float* mid) const; - - unsigned char* m_data; - int m_dataSize; - - dtStatNavMeshHeader* m_header; - - class dtNodePool* m_nodePool; - class dtNodeQueue* m_openList; -}; - -#endif // DETOURSTATNAVMESH_H diff --git a/extern/recastnavigation/Detour/Include/DetourStatNavMeshBuilder.h b/extern/recastnavigation/Detour/Include/DetourStatNavMeshBuilder.h deleted file mode 100644 index 03c79c429e7..00000000000 --- a/extern/recastnavigation/Detour/Include/DetourStatNavMeshBuilder.h +++ /dev/null @@ -1,33 +0,0 @@ -// -// Copyright (c) 2009 Mikko Mononen memon@inside.org -// -// This software is provided 'as-is', without any express or implied -// warranty. In no event will the authors be held liable for any damages -// arising from the use of this software. -// Permission is granted to anyone to use this software for any purpose, -// including commercial applications, and to alter it and redistribute it -// freely, subject to the following restrictions: -// 1. The origin of this software must not be misrepresented; you must not -// claim that you wrote the original software. If you use this software -// in a product, an acknowledgment in the product documentation would be -// appreciated but is not required. -// 2. Altered source versions must be plainly marked as such, and must not be -// misrepresented as being the original software. -// 3. This notice may not be removed or altered from any source distribution. -// - -#ifndef DETOURSTATNAVMESHBUILDER_H -#define DETOURSTATNAVMESHBUILDER_H - -bool dtCreateNavMeshData(const unsigned short* verts, const int nverts, - const unsigned short* polys, const int npolys, const int nvp, - const float* bmin, const float* bmax, float cs, float ch, - const unsigned short* dmeshes, const float* dverts, const int ndverts, - const unsigned char* dtris, const int ndtris, - unsigned char** outData, int* outDataSize); - -int createBVTree(const unsigned short* verts, const int nverts, - const unsigned short* polys, const int npolys, const int nvp, - float cs, float ch, int nnodes, dtStatBVNode* nodes); - -#endif // DETOURSTATNAVMESHBUILDER_H
\ No newline at end of file diff --git a/extern/recastnavigation/Detour/Include/DetourTileNavMesh.h b/extern/recastnavigation/Detour/Include/DetourTileNavMesh.h deleted file mode 100644 index 50ccdd118e8..00000000000 --- a/extern/recastnavigation/Detour/Include/DetourTileNavMesh.h +++ /dev/null @@ -1,315 +0,0 @@ -// -// Copyright (c) 2009 Mikko Mononen memon@inside.org -// -// This software is provided 'as-is', without any express or implied -// warranty. In no event will the authors be held liable for any damages -// arising from the use of this software. -// Permission is granted to anyone to use this software for any purpose, -// including commercial applications, and to alter it and redistribute it -// freely, subject to the following restrictions: -// 1. The origin of this software must not be misrepresented; you must not -// claim that you wrote the original software. If you use this software -// in a product, an acknowledgment in the product documentation would be -// appreciated but is not required. -// 2. Altered source versions must be plainly marked as such, and must not be -// misrepresented as being the original software. -// 3. This notice may not be removed or altered from any source distribution. -// - -#ifndef DETOURTILENAVMESH_H -#define DETOURTILENAVMESH_H - -// Reference to navigation polygon. -typedef unsigned int dtTilePolyRef; - -// The bits used in the poly ref. -static const int DT_TILE_REF_SALT_BITS = 12; -static const int DT_TILE_REF_TILE_BITS = 12; -static const int DT_TILE_REF_POLY_BITS = 8; -static const int DT_TILE_REF_SALT_MASK = (1<<DT_TILE_REF_SALT_BITS)-1; -static const int DT_TILE_REF_TILE_MASK = (1<<DT_TILE_REF_TILE_BITS)-1; -static const int DT_TILE_REF_POLY_MASK = (1<<DT_TILE_REF_POLY_BITS)-1; - -// Maximum number of vertices per navigation polygon. -static const int DT_TILE_VERTS_PER_POLYGON = 6; - -static const int DT_MAX_TILES = 1 << DT_TILE_REF_TILE_BITS; -static const int DT_MAX_POLYGONS = 1 << DT_TILE_REF_POLY_BITS; - -static const int DT_TILE_NAVMESH_MAGIC = (('N'<<24) | ('A'<<16) | ('V'<<8) | 'T'); -static const int DT_TILE_NAVMESH_VERSION = 2; - -// Structure holding the navigation polygon data. -struct dtTilePoly -{ - unsigned short v[DT_TILE_VERTS_PER_POLYGON]; // Indices to vertices of the poly. - unsigned short n[DT_TILE_VERTS_PER_POLYGON]; // Refs to neighbours of the poly. - unsigned short links; // Base index to header 'links' array. - unsigned char nlinks; // Number of links for - unsigned char nv; // Number of vertices. - unsigned char flags; // Flags (not used). -}; - -struct dtTilePolyDetail -{ - unsigned short vbase; // Offset to detail vertex array. - unsigned short nverts; // Number of vertices in the detail mesh. - unsigned short tbase; // Offset to detail triangle array. - unsigned short ntris; // Number of triangles. -}; - -// Stucture holding a link to another polygon. -struct dtTileLink -{ - dtTilePolyRef ref; // Neighbour reference. - unsigned short p; // Index to polygon which owns this link. - unsigned char e; // Index to polygon edge which owns this link. - unsigned char side; // If boundary link, defines on which side the link is. - unsigned char bmin, bmax; // If boundary link, defines the sub edge area. -}; - -struct dtTileHeader -{ - int magic; // Magic number, used to identify the data. - int version; // Data version number. - int npolys; // Number of polygons in the tile. - int nverts; // Number of vertices in the tile. - int nlinks; // Number of links in the tile (will be updated when tile is added). - int maxlinks; // Number of allocated links. - int ndmeshes; - int ndverts; - int ndtris; - float bmin[3], bmax[3]; // Bounding box of the tile. - dtTilePoly* polys; // Pointer to the polygons (will be updated when tile is added). - float* verts; // Pointer to the vertices (will be updated when tile added). - dtTileLink* links; // Pointer to the links (will be updated when tile added). - dtTilePolyDetail* dmeshes; - float* dverts; - unsigned char* dtris; -}; - -struct dtTile -{ - int salt; // Counter describing modifications to the tile. - int x,y; // Grid location of the tile. - dtTileHeader* header; // Pointer to tile header. - unsigned char* data; // Pointer to tile data. - int dataSize; // Size of the tile data. - bool ownsData; // Flag indicating of the navmesh should release the data. - dtTile* next; // Next free tile or, next tile in spatial grid. -}; - -// Encodes a tile id. -inline dtTilePolyRef dtEncodeTileId(unsigned int salt, unsigned int it, unsigned int ip) -{ - return (salt << (DT_TILE_REF_POLY_BITS+DT_TILE_REF_TILE_BITS)) | ((it+1) << DT_TILE_REF_POLY_BITS) | ip; -} - -// Decodes a tile id. -inline void dtDecodeTileId(dtTilePolyRef ref, unsigned int& salt, unsigned int& it, unsigned int& ip) -{ - salt = (ref >> (DT_TILE_REF_POLY_BITS+DT_TILE_REF_TILE_BITS)) & DT_TILE_REF_SALT_MASK; - it = ((ref >> DT_TILE_REF_POLY_BITS) & DT_TILE_REF_TILE_MASK) - 1; - ip = ref & DT_TILE_REF_POLY_MASK; -} - -static const int DT_TILE_LOOKUP_SIZE = DT_MAX_TILES/4; - -class dtTiledNavMesh -{ -public: - dtTiledNavMesh(); - ~dtTiledNavMesh(); - - // Initializes the nav mesh. - // Params: - // orig - (in) origin of the nav mesh tile space. - // tileSiz - (in) size of a tile. - // portalheight - (in) height of the portal region between tiles. - // Returns: True if succeed, else false. - bool init(const float* orig, float tileSize, float portalHeight); - - // Adds new tile into the navmesh. - // The add will fail if the data is in wrong format, - // there is not enough tiles left, or if there is a tile already at the location. - // Params: - // x,y - (in) Location of the new tile. - // data - (in) Data of the new tile mesh. - // dataSize - (in) Data size of the new tile mesh. - // ownsData - (in) Flag indicating if the navmesh should own and delete the data. - // Returns: True if tile was added, else false. - bool addTileAt(int x, int y, unsigned char* data, int dataSize, bool ownsData); - - // Removes tile at specified location. - // Params: - // x,y - (in) Location of the tile to remove. - // data - (out) Data associated with deleted tile. - // dataSize - (out) Size of the data associated with deleted tile. - // Returns: True if remove suceed, else false. - bool removeTileAt(int x, int y, unsigned char** data, int* dataSize); - - // Returns pointer to tile at specified location. - // Params: - // x,y - (in) Location of the tile to get. - // Returns: pointer to tile if tile exists or 0 tile does not exists. - dtTile* getTileAt(int x, int y); - - // Returns pointer to tile in the tile array. - // Params: - // i - (in) Index to the tile to retrieve, must be in range [0,DT_MAX_TILES[ - // Returns: Pointer to specified tile. - dtTile* getTile(int i); - const dtTile* getTile(int i) const; - - // Finds the nearest navigation polygon around the center location. - // Params: - // center - (in) The center of the search box. - // extents - (in) The extents of the search box. - // Returns: Reference identifier for the polygon, or 0 if no polygons found. - dtTilePolyRef findNearestPoly(const float* center, const float* extents); - - // Returns polygons which touch the query box. - // Params: - // center - (in) the center of the search box. - // extents - (in) the extents of the search box. - // polys - (out) array holding the search result. - // maxPolys - (in) The max number of polygons the polys array can hold. - // Returns: Number of polygons in search result array. - int queryPolygons(const float* center, const float* extents, - dtTilePolyRef* polys, const int maxPolys); - - // Finds path from start polygon to end polygon. - // If target polygon canno be reached through the navigation graph, - // the last node on the array is nearest node to the end polygon. - // Params: - // startRef - (in) ref to path start polygon. - // endRef - (in) ref to path end polygon. - // path - (out) array holding the search result. - // maxPathSize - (in) The max number of polygons the path array can hold. - // Returns: Number of polygons in search result array. - int findPath(dtTilePolyRef startRef, dtTilePolyRef endRef, - const float* startPos, const float* endPos, - dtTilePolyRef* path, const int maxPathSize); - - // Finds a straight path from start to end locations within the corridor - // described by the path polygons. - // Start and end locations will be clamped on the corridor. - // Params: - // startPos - (in) Path start location. - // endPos - (in) Path end location. - // path - (in) Array of connected polygons describing the corridor. - // pathSize - (in) Number of polygons in path array. - // straightPath - (out) Points describing the straight path. - // maxStraightPathSize - (in) The max number of points the straight path array can hold. - // Returns: Number of points in the path. - int findStraightPath(const float* startPos, const float* endPos, - const dtTilePolyRef* path, const int pathSize, - float* straightPath, const int maxStraightPathSize); - - // Finds intersection againts walls starting from start pos. - // Params: - // startRef - (in) ref to the polygon where the start lies. - // startPos - (in) start position of the query. - // endPos - (in) end position of the query. - // t - (out) hit parameter along the segment, 0 if no hit. - // endRef - (out) ref to the last polygon which was processed. - // Returns: Number of polygons in path or 0 if failed. - int raycast(dtTilePolyRef startRef, const float* startPos, const float* endPos, - float& t, dtTilePolyRef* path, const int pathSize); - - // Returns distance to nearest wall from the specified location. - // Params: - // centerRef - (in) ref to the polygon where the center lies. - // centerPos - (in) center if the query circle. - // maxRadius - (in) max search radius. - // hitPos - (out) location of the nearest hit. - // hitNormal - (out) normal of the nearest hit. - // Returns: Distance to nearest wall from the test location. - float findDistanceToWall(dtTilePolyRef centerRef, const float* centerPos, float maxRadius, - float* hitPos, float* hitNormal); - - // Finds polygons found along the navigation graph which touch the specified circle. - // Params: - // centerRef - (in) ref to the polygon where the center lies. - // centerPos - (in) center if the query circle - // radius - (in) radius of the query circle - // resultRef - (out, opt) refs to the polygons touched by the circle. - // resultParent - (out, opt) parent of each result polygon. - // resultCost - (out, opt) search cost at each result polygon. - // maxResult - (int) maximum capacity of search results. - // Returns: Number of results. - int findPolysAround(dtTilePolyRef centerRef, const float* centerPos, float radius, - dtTilePolyRef* resultRef, dtTilePolyRef* resultParent, float* resultCost, - const int maxResult); - - // Returns closest point on navigation polygon. - // Params: - // ref - (in) ref to the polygon. - // pos - (in) the point to check. - // closest - (out) closest point. - // Returns: true if closest point found. - bool closestPointToPoly(dtTilePolyRef ref, const float* pos, float* closest) const; - - // Returns height of the polygon at specified location. - // Params: - // ref - (in) ref to the polygon. - // pos - (in) the point where to locate the height. - // height - (out) height at the location. - // Returns: true if over polygon. - bool getPolyHeight(dtTilePolyRef ref, const float* pos, float* height) const; - - // Returns pointer to a polygon based on ref. - const dtTilePoly* getPolyByRef(dtTilePolyRef ref) const; - - // Returns pointer to a polygon vertices based on ref. - const float* getPolyVertsByRef(dtTilePolyRef ref) const; - - // Returns pointer to a polygon link based on ref. - const dtTileLink* getPolyLinksByRef(dtTilePolyRef ref) const; - -private: - - // Returns base id for the tile. - dtTilePolyRef getTileId(dtTile* tile); - // Returns neighbour tile based on side. - dtTile* getNeighbourTileAt(int x, int y, int side); - // Returns all polygons in neighbour tile based on portal defined by the segment. - int findConnectingPolys(const float* va, const float* vb, - dtTile* tile, int side, - dtTilePolyRef* con, float* conarea, int maxcon); - // Builds internal polygons links for a tile. - void buildIntLinks(dtTile* tile); - // Builds external polygon links for a tile. - void buildExtLinks(dtTile* tile, dtTile* target, int side); - // Removes external links at specified side. - void removeExtLinks(dtTile* tile, int side); - // Queries polygons within a tile. - int queryTilePolygons(dtTile* tile, const float* qmin, const float* qmax, - dtTilePolyRef* polys, const int maxPolys); - - float getCost(dtTilePolyRef prev, dtTilePolyRef from, dtTilePolyRef to) const; - float getFirstCost(const float* pos, dtTilePolyRef from, dtTilePolyRef to) const; - float getLastCost(dtTilePolyRef from, dtTilePolyRef to, const float* pos) const; - float getHeuristic(const float* from, const float* to) const; - - // Returns portal points between two polygons. - bool getPortalPoints(dtTilePolyRef from, dtTilePolyRef to, float* left, float* right) const; - // Returns edge mid point between two polygons. - bool getEdgeMidPoint(dtTilePolyRef from, dtTilePolyRef to, float* mid) const; - - float m_orig[3]; - float m_tileSize; - float m_portalHeight; - - dtTile* m_posLookup[DT_TILE_LOOKUP_SIZE]; - dtTile* m_nextFree; - dtTile m_tiles[DT_MAX_TILES]; - - dtTileLink* m_tmpLinks; - int m_ntmpLinks; - - class dtNodePool* m_nodePool; - class dtNodeQueue* m_openList; -}; - -#endif // DETOURTILENAVMESH_H diff --git a/extern/recastnavigation/Detour/Include/DetourTileNavMeshBuilder.h b/extern/recastnavigation/Detour/Include/DetourTileNavMeshBuilder.h deleted file mode 100644 index 643dec1edb1..00000000000 --- a/extern/recastnavigation/Detour/Include/DetourTileNavMeshBuilder.h +++ /dev/null @@ -1,29 +0,0 @@ -// -// Copyright (c) 2009 Mikko Mononen memon@inside.org -// -// This software is provided 'as-is', without any express or implied -// warranty. In no event will the authors be held liable for any damages -// arising from the use of this software. -// Permission is granted to anyone to use this software for any purpose, -// including commercial applications, and to alter it and redistribute it -// freely, subject to the following restrictions: -// 1. The origin of this software must not be misrepresented; you must not -// claim that you wrote the original software. If you use this software -// in a product, an acknowledgment in the product documentation would be -// appreciated but is not required. -// 2. Altered source versions must be plainly marked as such, and must not be -// misrepresented as being the original software. -// 3. This notice may not be removed or altered from any source distribution. -// - -#ifndef DETOURTILEDNAVMESHBUILDER_H -#define DETOURTILEDNAVMESHBUILDER_H - -bool dtCreateNavMeshTileData(const unsigned short* verts, const int nverts, - const unsigned short* polys, const int npolys, const int nvp, - const unsigned short* dmeshes, const float* dverts, const int ndverts, - const unsigned char* dtris, const int ndtris, - const float* bmin, const float* bmax, float cs, float ch, int tileSize, int walkableClimb, - unsigned char** outData, int* outDataSize); - -#endif // DETOURTILEDNAVMESHBUILDER_H
\ No newline at end of file diff --git a/extern/recastnavigation/Detour/Source/DetourCommon.cpp b/extern/recastnavigation/Detour/Source/DetourCommon.cpp deleted file mode 100644 index e55ce5e6351..00000000000 --- a/extern/recastnavigation/Detour/Source/DetourCommon.cpp +++ /dev/null @@ -1,244 +0,0 @@ -// -// Copyright (c) 2009 Mikko Mononen memon@inside.org -// -// This software is provided 'as-is', without any express or implied -// warranty. In no event will the authors be held liable for any damages -// arising from the use of this software. -// Permission is granted to anyone to use this software for any purpose, -// including commercial applications, and to alter it and redistribute it -// freely, subject to the following restrictions: -// 1. The origin of this software must not be misrepresented; you must not -// claim that you wrote the original software. If you use this software -// in a product, an acknowledgment in the product documentation would be -// appreciated but is not required. -// 2. Altered source versions must be plainly marked as such, and must not be -// misrepresented as being the original software. -// 3. This notice may not be removed or altered from any source distribution. -// - -#include <math.h> -#include "DetourCommon.h" - -void closestPtPointTriangle(float* closest, const float* p, - const float* a, const float* b, const float* c) -{ - // Check if P in vertex region outside A - float ab[3], ac[3], ap[3]; - vsub(ab, b, a); - vsub(ac, c, a); - vsub(ap, p, a); - float d1 = vdot(ab, ap); - float d2 = vdot(ac, ap); - if (d1 <= 0.0f && d2 <= 0.0f) - { - // barycentric coordinates (1,0,0) - vcopy(closest, a); - return; - } - - // Check if P in vertex region outside B - float bp[3]; - vsub(bp, p, b); - float d3 = vdot(ab, bp); - float d4 = vdot(ac, bp); - if (d3 >= 0.0f && d4 <= d3) - { - // barycentric coordinates (0,1,0) - vcopy(closest, b); - return; - } - - // Check if P in edge region of AB, if so return projection of P onto AB - float vc = d1*d4 - d3*d2; - if (vc <= 0.0f && d1 >= 0.0f && d3 <= 0.0f) - { - // barycentric coordinates (1-v,v,0) - float v = d1 / (d1 - d3); - closest[0] = a[0] + v * ab[0]; - closest[1] = a[1] + v * ab[1]; - closest[2] = a[2] + v * ab[2]; - return; - } - - // Check if P in vertex region outside C - float cp[3]; - vsub(cp, p, c); - float d5 = vdot(ab, cp); - float d6 = vdot(ac, cp); - if (d6 >= 0.0f && d5 <= d6) - { - // barycentric coordinates (0,0,1) - vcopy(closest, c); - return; - } - - // Check if P in edge region of AC, if so return projection of P onto AC - float vb = d5*d2 - d1*d6; - if (vb <= 0.0f && d2 >= 0.0f && d6 <= 0.0f) - { - // barycentric coordinates (1-w,0,w) - float w = d2 / (d2 - d6); - closest[0] = a[0] + w * ac[0]; - closest[1] = a[1] + w * ac[1]; - closest[2] = a[2] + w * ac[2]; - return; - } - - // Check if P in edge region of BC, if so return projection of P onto BC - float va = d3*d6 - d5*d4; - if (va <= 0.0f && (d4 - d3) >= 0.0f && (d5 - d6) >= 0.0f) - { - // barycentric coordinates (0,1-w,w) - float w = (d4 - d3) / ((d4 - d3) + (d5 - d6)); - closest[0] = b[0] + w * (c[0] - b[0]); - closest[1] = b[1] + w * (c[1] - b[1]); - closest[2] = b[2] + w * (c[2] - b[2]); - return; - } - - // P inside face region. Compute Q through its barycentric coordinates (u,v,w) - float denom = 1.0f / (va + vb + vc); - float v = vb * denom; - float w = vc * denom; - closest[0] = a[0] + ab[0] * v + ac[0] * w; - closest[1] = a[1] + ab[1] * v + ac[1] * w; - closest[2] = a[2] + ab[2] * v + ac[2] * w; -} - -bool intersectSegmentPoly2D(const float* p0, const float* p1, - const float* verts, int nverts, - float& tmin, float& tmax, - int& segMin, int& segMax) -{ - static const float EPS = 0.00000001f; - - tmin = 0; - tmax = 1; - segMin = -1; - segMax = -1; - - float dir[3]; - vsub(dir, p1, p0); - - for (int i = 0, j = nverts-1; i < nverts; j=i++) - { - float edge[3], diff[3]; - vsub(edge, &verts[i*3], &verts[j*3]); - vsub(diff, p0, &verts[j*3]); - float n = vperp2D(edge, diff); - float d = -vperp2D(edge, dir); - if (fabs(d) < EPS) - { - // S is nearly parallel to this edge - if (n < 0) - return false; - else - continue; - } - float t = n / d; - if (d < 0) - { - // segment S is entering across this edge - if (t > tmin) - { - tmin = t; - segMin = j; - // S enters after leaving polygon - if (tmin > tmax) - return false; - } - } - else - { - // segment S is leaving across this edge - if (t < tmax) - { - tmax = t; - segMax = j; - // S leaves before entering polygon - if (tmax < tmin) - return false; - } - } - } - - return true; -} - -float distancePtSegSqr2D(const float* pt, const float* p, const float* q, float& t) -{ - float pqx = q[0] - p[0]; - float pqz = q[2] - p[2]; - float dx = pt[0] - p[0]; - float dz = pt[2] - p[2]; - float d = pqx*pqx + pqz*pqz; - t = pqx*dx + pqz*dz; - if (d > 0) - t /= d; - if (t < 0) - t = 0; - else if (t > 1) - t = 1; - - dx = p[0] + t*pqx - pt[0]; - dz = p[2] + t*pqz - pt[2]; - - return dx*dx + dz*dz; -} - -void calcPolyCenter(float* tc, const unsigned short* idx, int nidx, const float* verts) -{ - tc[0] = 0.0f; - tc[1] = 0.0f; - tc[2] = 0.0f; - for (int j = 0; j < nidx; ++j) - { - const float* v = &verts[idx[j]*3]; - tc[0] += v[0]; - tc[1] += v[1]; - tc[2] += v[2]; - } - const float s = 1.0f / nidx; - tc[0] *= s; - tc[1] *= s; - tc[2] *= s; -} - -inline float vdot2(const float* a, const float* b) -{ - return a[0]*b[0] + a[2]*b[2]; -} - -#include <stdio.h> - -bool closestHeightPointTriangle(const float* p, const float* a, const float* b, const float* c, float& h) -{ - float v0[3], v1[3], v2[3]; - vsub(v0, c,a); - vsub(v1, b,a); - vsub(v2, p,a); - - const float dot00 = vdot2(v0, v0); - const float dot01 = vdot2(v0, v1); - const float dot02 = vdot2(v0, v2); - const float dot11 = vdot2(v1, v1); - const float dot12 = vdot2(v1, v2); - - // Compute barycentric coordinates - float invDenom = 1.0f / (dot00 * dot11 - dot01 * dot01); - float u = (dot11 * dot02 - dot01 * dot12) * invDenom; - float v = (dot00 * dot12 - dot01 * dot02) * invDenom; - - // The (sloppy) epsilon is needed to allow to get height of points which - // are interpolated along the edges of the triangles. - static const float EPS = 1e-4f; - - // If point lies inside the triangle, return interpolated ycoord. - if (u >= -EPS && v >= -EPS && (u+v) <= 1+EPS) - { - h = a[1] + v0[1]*u + v1[1]*v; - return true; - } - - return false; -} diff --git a/extern/recastnavigation/Detour/Source/DetourNode.cpp b/extern/recastnavigation/Detour/Source/DetourNode.cpp deleted file mode 100644 index 1a2305fcede..00000000000 --- a/extern/recastnavigation/Detour/Source/DetourNode.cpp +++ /dev/null @@ -1,140 +0,0 @@ -// -// Copyright (c) 2009 Mikko Mononen memon@inside.org -// -// This software is provided 'as-is', without any express or implied -// warranty. In no event will the authors be held liable for any damages -// arising from the use of this software. -// Permission is granted to anyone to use this software for any purpose, -// including commercial applications, and to alter it and redistribute it -// freely, subject to the following restrictions: -// 1. The origin of this software must not be misrepresented; you must not -// claim that you wrote the original software. If you use this software -// in a product, an acknowledgment in the product documentation would be -// appreciated but is not required. -// 2. Altered source versions must be plainly marked as such, and must not be -// misrepresented as being the original software. -// 3. This notice may not be removed or altered from any source distribution. -// - -#include "DetourNode.h" -#include <string.h> - -////////////////////////////////////////////////////////////////////////////////////////// -dtNodePool::dtNodePool(int maxNodes, int hashSize) : - - m_nodes(0), - m_first(0), - m_next(0), - m_maxNodes(maxNodes), - m_hashSize(hashSize), - m_nodeCount(0) -{ - m_nodes = new dtNode[m_maxNodes]; - m_next = new unsigned short[m_maxNodes]; - m_first = new unsigned short[hashSize]; - memset(m_first, 0xff, sizeof(unsigned short)*m_hashSize); - memset(m_next, 0xff, sizeof(unsigned short)*m_maxNodes); -} - -dtNodePool::~dtNodePool() -{ - delete [] m_nodes; - delete [] m_next; - delete [] m_first; -} - -void dtNodePool::clear() -{ - memset(m_first, 0xff, sizeof(unsigned short)*m_hashSize); - m_nodeCount = 0; -} - -const dtNode* dtNodePool::findNode(unsigned int id) const -{ - unsigned int bucket = hashint(id) & (m_hashSize-1); - unsigned short i = m_first[bucket]; - while (i != 0xffff) - { - if (m_nodes[i].id == id) - return &m_nodes[i]; - i = m_next[i]; - } - return 0; -} - -dtNode* dtNodePool::getNode(unsigned int id) -{ - unsigned int bucket = hashint(id) & (m_hashSize-1); - unsigned short i = m_first[bucket]; - dtNode* node = 0; - while (i != 0xffff) - { - if (m_nodes[i].id == id) - return &m_nodes[i]; - i = m_next[i]; - } - - if (m_nodeCount >= m_maxNodes) - return 0; - - i = (unsigned short)m_nodeCount; - m_nodeCount++; - - // Init node - node = &m_nodes[i]; - node->pidx = 0; - node->cost = 0; - node->total = 0; - node->id = id; - node->flags = 0; - - m_next[i] = m_first[bucket]; - m_first[bucket] = i; - - return node; -} - - -////////////////////////////////////////////////////////////////////////////////////////// -dtNodeQueue::dtNodeQueue(int n) : - m_heap(0), - m_capacity(n), - m_size(0) -{ - m_heap = new dtNode*[m_capacity+1]; -} - -dtNodeQueue::~dtNodeQueue() -{ - delete [] m_heap; -} - -void dtNodeQueue::bubbleUp(int i, dtNode* node) -{ - int parent = (i-1)/2; - // note: (index > 0) means there is a parent - while ((i > 0) && (m_heap[parent]->total > node->total)) - { - m_heap[i] = m_heap[parent]; - i = parent; - parent = (i-1)/2; - } - m_heap[i] = node; -} - -void dtNodeQueue::trickleDown(int i, dtNode* node) -{ - int child = (i*2)+1; - while (child < m_size) - { - if (((child+1) < m_size) && - (m_heap[child]->total > m_heap[child+1]->total)) - { - child++; - } - m_heap[i] = m_heap[child]; - i = child; - child = (i*2)+1; - } - bubbleUp(i, node); -} diff --git a/extern/recastnavigation/Detour/Source/DetourStatNavMesh.cpp b/extern/recastnavigation/Detour/Source/DetourStatNavMesh.cpp deleted file mode 100644 index a02211816a2..00000000000 --- a/extern/recastnavigation/Detour/Source/DetourStatNavMesh.cpp +++ /dev/null @@ -1,876 +0,0 @@ -// -// Copyright (c) 2009 Mikko Mononen memon@inside.org -// -// This software is provided 'as-is', without any express or implied -// warranty. In no event will the authors be held liable for any damages -// arising from the use of this software. -// Permission is granted to anyone to use this software for any purpose, -// including commercial applications, and to alter it and redistribute it -// freely, subject to the following restrictions: -// 1. The origin of this software must not be misrepresented; you must not -// claim that you wrote the original software. If you use this software -// in a product, an acknowledgment in the product documentation would be -// appreciated but is not required. -// 2. Altered source versions must be plainly marked as such, and must not be -// misrepresented as being the original software. -// 3. This notice may not be removed or altered from any source distribution. -// - -#include <math.h> -#include <float.h> -#include <string.h> -#include <stdio.h> -#include "DetourStatNavMesh.h" -#include "DetourNode.h" -#include "DetourCommon.h" - - -////////////////////////////////////////////////////////////////////////////////////////// -dtStatNavMesh::dtStatNavMesh() : - m_data(0), - m_dataSize(0), - m_header(0), - m_nodePool(0), - m_openList(0) -{ -} - -dtStatNavMesh::~dtStatNavMesh() -{ - delete m_nodePool; - delete m_openList; - if (m_data) - delete [] m_data; -} - -bool dtStatNavMesh::init(unsigned char* data, int dataSize, bool ownsData) -{ - dtStatNavMeshHeader* header = (dtStatNavMeshHeader*)data; - - if (header->magic != DT_STAT_NAVMESH_MAGIC) - return false; - if (header->version != DT_STAT_NAVMESH_VERSION) - return false; - - const int headerSize = sizeof(dtStatNavMeshHeader); - const int vertsSize = sizeof(float)*3*header->nverts; - const int polysSize = sizeof(dtStatPoly)*header->npolys; - const int nodesSize = sizeof(dtStatBVNode)*header->npolys*2; - const int detailMeshesSize = sizeof(dtStatPolyDetail)*header->ndmeshes; - const int detailVertsSize = sizeof(float)*3*header->ndverts; - const int detailTrisSize = sizeof(unsigned char)*4*header->ndtris; - - - unsigned char* d = data + headerSize; - header->verts = (float*)d; d += vertsSize; - header->polys = (dtStatPoly*)d; d += polysSize; - header->bvtree = (dtStatBVNode*)d; d += nodesSize; - header->dmeshes = (dtStatPolyDetail*)d; d += detailMeshesSize; - header->dverts = (float*)d; d += detailVertsSize; - header->dtris = (unsigned char*)d; d += detailTrisSize; - - m_nodePool = new dtNodePool(2048, 256); - if (!m_nodePool) - return false; - - m_openList = new dtNodeQueue(2048); - if (!m_openList) - return false; - - if (ownsData) - { - m_data = data; - m_dataSize = dataSize; - } - - m_header = header; - - return true; -} - -const dtStatPoly* dtStatNavMesh::getPolyByRef(dtStatPolyRef ref) const -{ - if (!m_header || ref == 0 || (int)ref > m_header->npolys) return 0; - return &m_header->polys[ref-1]; -} - -int dtStatNavMesh::getPolyIndexByRef(dtStatPolyRef ref) const -{ - if (!m_header || ref == 0 || (int)ref > m_header->npolys) return -1; - return (int)ref-1; -} - -int dtStatNavMesh::findPath(dtStatPolyRef startRef, dtStatPolyRef endRef, - const float* startPos, const float* endPos, - dtStatPolyRef* path, const int maxPathSize) -{ - if (!m_header) return 0; - - if (!startRef || !endRef) - return 0; - - if (!maxPathSize) - return 0; - - if (startRef == endRef) - { - path[0] = startRef; - return 1; - } - - m_nodePool->clear(); - m_openList->clear(); - - static const float H_SCALE = 1.1f; // Heuristic scale. - - dtNode* startNode = m_nodePool->getNode(startRef); - startNode->pidx = 0; - startNode->cost = 0; - startNode->total = vdist(startPos, endPos) * H_SCALE; - startNode->id = startRef; - startNode->flags = DT_NODE_OPEN; - m_openList->push(startNode); - - dtNode* lastBestNode = startNode; - float lastBestNodeCost = startNode->total; - while (!m_openList->empty()) - { - dtNode* bestNode = m_openList->pop(); - - if (bestNode->id == endRef) - { - lastBestNode = bestNode; - break; - } - - const dtStatPoly* poly = getPoly(bestNode->id-1); - for (int i = 0; i < (int)poly->nv; ++i) - { - dtStatPolyRef neighbour = poly->n[i]; - if (neighbour) - { - // Skip parent node. - if (bestNode->pidx && m_nodePool->getNodeAtIdx(bestNode->pidx)->id == neighbour) - continue; - - dtNode* parent = bestNode; - dtNode newNode; - newNode.pidx = m_nodePool->getNodeIdx(parent); - newNode.id = neighbour; - - // Calculate cost. - float p0[3], p1[3]; - if (!parent->pidx) - vcopy(p0, startPos); - else - getEdgeMidPoint(m_nodePool->getNodeAtIdx(parent->pidx)->id, parent->id, p0); - getEdgeMidPoint(parent->id, newNode.id, p1); - newNode.cost = parent->cost + vdist(p0,p1); - // Special case for last node. - if (newNode.id == endRef) - newNode.cost += vdist(p1, endPos); - - // Heuristic - const float h = vdist(p1,endPos)*H_SCALE; - newNode.total = newNode.cost + h; - - dtNode* actualNode = m_nodePool->getNode(newNode.id); - if (!actualNode) - continue; - - if (!((actualNode->flags & DT_NODE_OPEN) && newNode.total > actualNode->total) && - !((actualNode->flags & DT_NODE_CLOSED) && newNode.total > actualNode->total)) - { - actualNode->flags &= ~DT_NODE_CLOSED; - actualNode->pidx = newNode.pidx; - actualNode->cost = newNode.cost; - actualNode->total = newNode.total; - - if (h < lastBestNodeCost) - { - lastBestNodeCost = h; - lastBestNode = actualNode; - } - - if (actualNode->flags & DT_NODE_OPEN) - { - m_openList->modify(actualNode); - } - else - { - actualNode->flags |= DT_NODE_OPEN; - m_openList->push(actualNode); - } - } - } - } - bestNode->flags |= DT_NODE_CLOSED; - } - - // Reverse the path. - dtNode* prev = 0; - dtNode* node = lastBestNode; - do - { - dtNode* next = m_nodePool->getNodeAtIdx(node->pidx); - node->pidx = m_nodePool->getNodeIdx(prev); - prev = node; - node = next; - } - while (node); - - // Store path - node = prev; - int n = 0; - do - { - path[n++] = node->id; - node = m_nodePool->getNodeAtIdx(node->pidx); - } - while (node && n < maxPathSize); - - return n; -} - -bool dtStatNavMesh::closestPointToPoly(dtStatPolyRef ref, const float* pos, float* closest) const -{ - int idx = getPolyIndexByRef(ref); - if (idx == -1) - return false; - - float closestDistSqr = FLT_MAX; - const dtStatPoly* p = getPoly(idx); - const dtStatPolyDetail* pd = getPolyDetail(idx); - - for (int j = 0; j < pd->ntris; ++j) - { - const unsigned char* t = getDetailTri(pd->tbase+j); - const float* v[3]; - for (int k = 0; k < 3; ++k) - { - if (t[k] < p->nv) - v[k] = getVertex(p->v[t[k]]); - else - v[k] = getDetailVertex(pd->vbase+(t[k]-p->nv)); - } - float pt[3]; - closestPtPointTriangle(pt, pos, v[0], v[1], v[2]); - float d = vdistSqr(pos, pt); - if (d < closestDistSqr) - { - vcopy(closest, pt); - closestDistSqr = d; - } - } - - return true; -} - -bool dtStatNavMesh::getPolyHeight(dtStatPolyRef ref, const float* pos, float* height) const -{ - int idx = getPolyIndexByRef(ref); - if (idx == -1) - return false; - - const dtStatPoly* p = getPoly(idx); - const dtStatPolyDetail* pd = getPolyDetail(idx); - - for (int i = 0; i < pd->ntris; ++i) - { - const unsigned char* t = getDetailTri(pd->tbase+i); - const float* v[3]; - for (int j = 0; j < 3; ++j) - { - if (t[j] < p->nv) - v[j] = getVertex(p->v[t[j]]); - else - v[j] = getDetailVertex(pd->vbase+(t[j]-p->nv)); - } - float h; - if (closestHeightPointTriangle(pos, v[0], v[1], v[2], h)) - { - if (height) - *height = h; - return true; - } - } - - return false; -} - -int dtStatNavMesh::findStraightPath(const float* startPos, const float* endPos, - const dtStatPolyRef* path, const int pathSize, - float* straightPath, const int maxStraightPathSize) -{ - if (!m_header) return 0; - - if (!maxStraightPathSize) - return 0; - - if (!path[0]) - return 0; - - int straightPathSize = 0; - - float closestStartPos[3]; - if (!closestPointToPoly(path[0], startPos, closestStartPos)) - return 0; - - // Add start point. - vcopy(&straightPath[straightPathSize*3], closestStartPos); - straightPathSize++; - if (straightPathSize >= maxStraightPathSize) - return straightPathSize; - - float closestEndPos[3]; - if (!closestPointToPoly(path[pathSize-1], endPos, closestEndPos)) - return 0; - - float portalApex[3], portalLeft[3], portalRight[3]; - - if (pathSize > 1) - { - vcopy(portalApex, closestStartPos); - vcopy(portalLeft, portalApex); - vcopy(portalRight, portalApex); - int apexIndex = 0; - int leftIndex = 0; - int rightIndex = 0; - - for (int i = 0; i < pathSize; ++i) - { - float left[3], right[3]; - if (i < pathSize-1) - { - // Next portal. - getPortalPoints(path[i], path[i+1], left, right); - } - else - { - // End of the path. - vcopy(left, closestEndPos); - vcopy(right, closestEndPos); - } - - // Right vertex. - if (vequal(portalApex, portalRight)) - { - vcopy(portalRight, right); - rightIndex = i; - } - else - { - if (triArea2D(portalApex, portalRight, right) <= 0.0f) - { - if (triArea2D(portalApex, portalLeft, right) > 0.0f) - { - vcopy(portalRight, right); - rightIndex = i; - } - else - { - vcopy(portalApex, portalLeft); - apexIndex = leftIndex; - - if (!vequal(&straightPath[(straightPathSize-1)*3], portalApex)) - { - vcopy(&straightPath[straightPathSize*3], portalApex); - straightPathSize++; - if (straightPathSize >= maxStraightPathSize) - return straightPathSize; - } - - vcopy(portalLeft, portalApex); - vcopy(portalRight, portalApex); - leftIndex = apexIndex; - rightIndex = apexIndex; - - // Restart - i = apexIndex; - - continue; - } - } - } - - // Left vertex. - if (vequal(portalApex, portalLeft)) - { - vcopy(portalLeft, left); - leftIndex = i; - } - else - { - if (triArea2D(portalApex, portalLeft, left) >= 0.0f) - { - if (triArea2D(portalApex, portalRight, left) < 0.0f) - { - vcopy(portalLeft, left); - leftIndex = i; - } - else - { - vcopy(portalApex, portalRight); - apexIndex = rightIndex; - - if (!vequal(&straightPath[(straightPathSize-1)*3], portalApex)) - { - vcopy(&straightPath[straightPathSize*3], portalApex); - straightPathSize++; - if (straightPathSize >= maxStraightPathSize) - return straightPathSize; - } - - vcopy(portalLeft, portalApex); - vcopy(portalRight, portalApex); - leftIndex = apexIndex; - rightIndex = apexIndex; - - // Restart - i = apexIndex; - - continue; - } - } - } - } - } - - // Add end point. - vcopy(&straightPath[straightPathSize*3], closestEndPos); - straightPathSize++; - - return straightPathSize; -} - -int dtStatNavMesh::getPolyVerts(dtStatPolyRef ref, float* verts) const -{ - if (!m_header) return 0; - const dtStatPoly* poly = getPolyByRef(ref); - if (!poly) return 0; - float* v = verts; - for (int i = 0; i < (int)poly->nv; ++i) - { - const float* cv = &m_header->verts[poly->v[i]*3]; - *v++ = cv[0]; - *v++ = cv[1]; - *v++ = cv[2]; - } - return (int)poly->nv; -} - -int dtStatNavMesh::raycast(dtStatPolyRef centerRef, const float* startPos, const float* endPos, - float& t, dtStatPolyRef* path, const int pathSize) -{ - if (!m_header) return 0; - if (!centerRef) return 0; - - /* dtStatPolyRef prevRef = centerRef; */ /* UNUSED */ - dtStatPolyRef curRef = centerRef; - t = 0; - - float verts[DT_STAT_VERTS_PER_POLYGON*3]; - int n = 0; - - while (curRef) - { - // Cast ray against current polygon. - int nv = getPolyVerts(curRef, verts); - if (nv < 3) - { - // Hit bad polygon, report hit. - return n; - } - - float tmin, tmax; - int segMin, segMax; - if (!intersectSegmentPoly2D(startPos, endPos, verts, nv, tmin, tmax, segMin, segMax)) - { - // Could not a polygon, keep the old t and report hit. - return n; - } - // Keep track of furthest t so far. - if (tmax > t) - t = tmax; - - if (n < pathSize) - path[n++] = curRef; - - // Check the neighbour of this polygon. - const dtStatPoly* poly = getPolyByRef(curRef); - dtStatPolyRef nextRef = poly->n[segMax]; - if (!nextRef) - { - // No neighbour, we hit a wall. - return n; - } - - // No hit, advance to neighbour polygon. - /* prevRef = curRef; */ /* UNUSED */ - curRef = nextRef; - } - - return n; -} - - -float dtStatNavMesh::findDistanceToWall(dtStatPolyRef centerRef, const float* centerPos, float maxRadius, - float* hitPos, float* hitNormal) -{ - if (!m_header) return 0; - if (!centerRef) return 0; - - m_nodePool->clear(); - m_openList->clear(); - - dtNode* startNode = m_nodePool->getNode(centerRef); - startNode->pidx = 0; - startNode->cost = 0; - startNode->total = 0; - startNode->id = centerRef; - startNode->flags = DT_NODE_OPEN; - m_openList->push(startNode); - - float radiusSqr = sqr(maxRadius); - - hitNormal[0] = 1; - hitNormal[1] = 0; - hitNormal[2] = 0; - - while (!m_openList->empty()) - { - dtNode* bestNode = m_openList->pop(); - const dtStatPoly* poly = getPoly(bestNode->id-1); - - // Hit test walls. - for (int i = 0, j = (int)poly->nv-1; i < (int)poly->nv; j = i++) - { - // Skip non-solid edges. - if (poly->n[j]) continue; - - // Calc distance to the edge. - const float* vj = getVertex(poly->v[j]); - const float* vi = getVertex(poly->v[i]); - float tseg; - float distSqr = distancePtSegSqr2D(centerPos, vj, vi, tseg); - - // Edge is too far, skip. - if (distSqr > radiusSqr) - continue; - - // Hit wall, update radius. - radiusSqr = distSqr; - // Calculate hit pos. - hitPos[0] = vj[0] + (vi[0] - vj[0])*tseg; - hitPos[1] = vj[1] + (vi[1] - vj[1])*tseg; - hitPos[2] = vj[2] + (vi[2] - vj[2])*tseg; - } - - // Check to see if the circle expands to one of the neighbours and expand. - for (int i = 0, j = (int)poly->nv-1; i < (int)poly->nv; j = i++) - { - // Skip solid edges. - if (!poly->n[j]) continue; - - // Expand to neighbour if not visited yet. - dtStatPolyRef neighbour = poly->n[j]; - - // Skip parent node. - if (bestNode->pidx && m_nodePool->getNodeAtIdx(bestNode->pidx)->id == neighbour) - continue; - - // Calc distance to the edge. - const float* vj = getVertex(poly->v[j]); - const float* vi = getVertex(poly->v[i]); - float tseg; - float distSqr = distancePtSegSqr2D(centerPos, vj, vi, tseg); - - // Edge is too far, skip. - if (distSqr > radiusSqr) - continue; - - dtNode* parent = bestNode; - dtNode newNode; - newNode.pidx = m_nodePool->getNodeIdx(parent); - newNode.id = neighbour; - - // Cost - float p0[3], p1[3]; - if (!parent->pidx) - vcopy(p0, centerPos); - else - getEdgeMidPoint(m_nodePool->getNodeAtIdx(parent->pidx)->id, parent->id, p0); - getEdgeMidPoint(parent->id, newNode.id, p1); - newNode.total = parent->total + vdist(p0,p1); - - dtNode* actualNode = m_nodePool->getNode(newNode.id); - if (!actualNode) - continue; - - if (!((actualNode->flags & DT_NODE_OPEN) && newNode.total > actualNode->total) && - !((actualNode->flags & DT_NODE_CLOSED) && newNode.total > actualNode->total)) - { - actualNode->flags &= ~DT_NODE_CLOSED; - actualNode->pidx = newNode.pidx; - actualNode->total = newNode.total; - - if (actualNode->flags & DT_NODE_OPEN) - { - m_openList->modify(actualNode); - } - else - { - actualNode->flags |= DT_NODE_OPEN; - m_openList->push(actualNode); - } - } - } - bestNode->flags |= DT_NODE_CLOSED; - } - - // Calc hit normal. - vsub(hitNormal, centerPos, hitPos); - vnormalize(hitNormal); - - return sqrtf(radiusSqr); -} - -int dtStatNavMesh::findPolysAround(dtStatPolyRef centerRef, const float* centerPos, float radius, - dtStatPolyRef* resultRef, dtStatPolyRef* resultParent, float* resultCost, - const int maxResult) -{ - if (!m_header) return 0; - if (!centerRef) return 0; - - m_nodePool->clear(); - m_openList->clear(); - - dtNode* startNode = m_nodePool->getNode(centerRef); - startNode->pidx = 0; - startNode->cost = 0; - startNode->total = 0; - startNode->id = centerRef; - startNode->flags = DT_NODE_OPEN; - m_openList->push(startNode); - - int n = 0; - if (n < maxResult) - { - if (resultRef) - resultRef[n] = startNode->id; - if (resultParent) - resultParent[n] = 0; - if (resultCost) - resultCost[n] = 0; - ++n; - } - - const float radiusSqr = sqr(radius); - - while (!m_openList->empty()) - { - dtNode* bestNode = m_openList->pop(); - const dtStatPoly* poly = getPoly(bestNode->id-1); - for (unsigned i = 0, j = (int)poly->nv-1; i < (int)poly->nv; j=i++) - { - dtStatPolyRef neighbour = poly->n[j]; - - if (neighbour) - { - // Skip parent node. - if (bestNode->pidx && m_nodePool->getNodeAtIdx(bestNode->pidx)->id == neighbour) - continue; - - // Calc distance to the edge. - const float* vj = getVertex(poly->v[j]); - const float* vi = getVertex(poly->v[i]); - float tseg; - float distSqr = distancePtSegSqr2D(centerPos, vj, vi, tseg); - - // If the circle is not touching the next polygon, skip it. - if (distSqr > radiusSqr) - continue; - - dtNode* parent = bestNode; - dtNode newNode; - newNode.pidx = m_nodePool->getNodeIdx(parent); - newNode.id = neighbour; - - // Cost - float p0[3], p1[3]; - if (!parent->pidx) - vcopy(p0, centerPos); - else - getEdgeMidPoint(m_nodePool->getNodeAtIdx(parent->pidx)->id, parent->id, p0); - getEdgeMidPoint(parent->id, newNode.id, p1); - newNode.total = parent->total + vdist(p0,p1); - - dtNode* actualNode = m_nodePool->getNode(newNode.id); - if (!actualNode) - continue; - - if (!((actualNode->flags & DT_NODE_OPEN) && newNode.total > actualNode->total) && - !((actualNode->flags & DT_NODE_CLOSED) && newNode.total > actualNode->total)) - { - actualNode->flags &= ~DT_NODE_CLOSED; - actualNode->pidx = newNode.pidx; - actualNode->total = newNode.total; - - if (actualNode->flags & DT_NODE_OPEN) - { - m_openList->modify(actualNode); - } - else - { - if (n < maxResult) - { - if (resultRef) - resultRef[n] = actualNode->id; - if (resultParent) - resultParent[n] = m_nodePool->getNodeAtIdx(actualNode->pidx)->id; - if (resultCost) - resultCost[n] = actualNode->total; - ++n; - } - actualNode->flags |= DT_NODE_OPEN; - m_openList->push(actualNode); - } - } - } - } - bestNode->flags |= DT_NODE_CLOSED; - - } - - return n; -} - -// Returns polygons which are withing certain radius from the query location. -int dtStatNavMesh::queryPolygons(const float* center, const float* extents, - dtStatPolyRef* polys, const int maxIds) -{ - if (!m_header) return 0; - - const dtStatBVNode* node = &m_header->bvtree[0]; - const dtStatBVNode* end = &m_header->bvtree[m_header->nnodes]; - - // Calculate quantized box - const float ics = 1.0f / m_header->cs; - unsigned short bmin[3], bmax[3]; - // Clamp query box to world box. - float minx = clamp(center[0] - extents[0], m_header->bmin[0], m_header->bmax[0]) - m_header->bmin[0]; - float miny = clamp(center[1] - extents[1], m_header->bmin[1], m_header->bmax[1]) - m_header->bmin[1]; - float minz = clamp(center[2] - extents[2], m_header->bmin[2], m_header->bmax[2]) - m_header->bmin[2]; - float maxx = clamp(center[0] + extents[0], m_header->bmin[0], m_header->bmax[0]) - m_header->bmin[0]; - float maxy = clamp(center[1] + extents[1], m_header->bmin[1], m_header->bmax[1]) - m_header->bmin[1]; - float maxz = clamp(center[2] + extents[2], m_header->bmin[2], m_header->bmax[2]) - m_header->bmin[2]; - // Quantize - bmin[0] = (unsigned short)(ics * minx) & 0xfffe; - bmin[1] = (unsigned short)(ics * miny) & 0xfffe; - bmin[2] = (unsigned short)(ics * minz) & 0xfffe; - bmax[0] = (unsigned short)(ics * maxx + 1) | 1; - bmax[1] = (unsigned short)(ics * maxy + 1) | 1; - bmax[2] = (unsigned short)(ics * maxz + 1) | 1; - - // Traverse tree - int n = 0; - while (node < end) - { - bool overlap = checkOverlapBox(bmin, bmax, node->bmin, node->bmax); - bool isLeafNode = node->i >= 0; - - if (isLeafNode && overlap) - { - if (n < maxIds) - { - polys[n] = (dtStatPolyRef)node->i; - n++; - } - } - - if (overlap || isLeafNode) - node++; - else - { - const int escapeIndex = -node->i; - node += escapeIndex; - } - } - - return n; -} - -dtStatPolyRef dtStatNavMesh::findNearestPoly(const float* center, const float* extents) -{ - if (!m_header) return 0; - - // Get nearby polygons from proximity grid. - dtStatPolyRef polys[128]; - int npolys = queryPolygons(center, extents, polys, 128); - - // Find nearest polygon amongst the nearby polygons. - dtStatPolyRef nearest = 0; - float nearestDistanceSqr = FLT_MAX; - for (int i = 0; i < npolys; ++i) - { - dtStatPolyRef ref = polys[i]; - float closest[3]; - if (!closestPointToPoly(ref, center, closest)) - continue; - float d = vdistSqr(center, closest); - if (d < nearestDistanceSqr) - { - nearestDistanceSqr = d; - nearest = ref; - } - } - - return nearest; -} - -bool dtStatNavMesh::getPortalPoints(dtStatPolyRef from, dtStatPolyRef to, float* left, float* right) const -{ - const dtStatPoly* fromPoly = getPolyByRef(from); - if (!fromPoly) - return false; - - // Find common edge between the polygons and returns the segment end points. - for (unsigned i = 0, j = (int)fromPoly->nv - 1; i < (int)fromPoly->nv; j = i++) - { - unsigned short neighbour = fromPoly->n[j]; - if (neighbour == to) - { - vcopy(left, getVertex(fromPoly->v[j])); - vcopy(right, getVertex(fromPoly->v[i])); - return true; - } - } - - return false; -} - -bool dtStatNavMesh::getEdgeMidPoint(dtStatPolyRef from, dtStatPolyRef to, float* mid) const -{ - float left[3], right[3]; - if (!getPortalPoints(from, to, left,right)) return false; - mid[0] = (left[0]+right[0])*0.5f; - mid[1] = (left[1]+right[1])*0.5f; - mid[2] = (left[2]+right[2])*0.5f; - return true; -} - -bool dtStatNavMesh::isInClosedList(dtStatPolyRef ref) const -{ - if (!m_nodePool) return false; - const dtNode* node = m_nodePool->findNode(ref); - return node && node->flags & DT_NODE_CLOSED; -} - -int dtStatNavMesh::getMemUsed() const -{ - if (!m_nodePool || ! m_openList) - return 0; - return sizeof(*this) + m_dataSize + - m_nodePool->getMemUsed() + - m_openList->getMemUsed(); -} diff --git a/extern/recastnavigation/Detour/Source/DetourStatNavMeshBuilder.cpp b/extern/recastnavigation/Detour/Source/DetourStatNavMeshBuilder.cpp deleted file mode 100644 index 2ca455fb53d..00000000000 --- a/extern/recastnavigation/Detour/Source/DetourStatNavMeshBuilder.cpp +++ /dev/null @@ -1,346 +0,0 @@ -// -// Copyright (c) 2009 Mikko Mononen memon@inside.org -// -// This software is provided 'as-is', without any express or implied -// warranty. In no event will the authors be held liable for any damages -// arising from the use of this software. -// Permission is granted to anyone to use this software for any purpose, -// including commercial applications, and to alter it and redistribute it -// freely, subject to the following restrictions: -// 1. The origin of this software must not be misrepresented; you must not -// claim that you wrote the original software. If you use this software -// in a product, an acknowledgment in the product documentation would be -// appreciated but is not required. -// 2. Altered source versions must be plainly marked as such, and must not be -// misrepresented as being the original software. -// 3. This notice may not be removed or altered from any source distribution. -// - -#include <math.h> -#include <stdlib.h> -#include <string.h> -#include "DetourStatNavMesh.h" - -struct BVItem -{ - unsigned short bmin[3]; - unsigned short bmax[3]; - int i; -}; - -static int compareItemX(const void* va, const void* vb) -{ - const BVItem* a = (const BVItem*)va; - const BVItem* b = (const BVItem*)vb; - if (a->bmin[0] < b->bmin[0]) - return -1; - if (a->bmin[0] > b->bmin[0]) - return 1; - return 0; -} - -static int compareItemY(const void* va, const void* vb) -{ - const BVItem* a = (const BVItem*)va; - const BVItem* b = (const BVItem*)vb; - if (a->bmin[1] < b->bmin[1]) - return -1; - if (a->bmin[1] > b->bmin[1]) - return 1; - return 0; -} - -static int compareItemZ(const void* va, const void* vb) -{ - const BVItem* a = (const BVItem*)va; - const BVItem* b = (const BVItem*)vb; - if (a->bmin[2] < b->bmin[2]) - return -1; - if (a->bmin[2] > b->bmin[2]) - return 1; - return 0; -} - -static void calcExtends(BVItem* items, int nitems, int imin, int imax, - unsigned short* bmin, unsigned short* bmax) -{ - bmin[0] = items[imin].bmin[0]; - bmin[1] = items[imin].bmin[1]; - bmin[2] = items[imin].bmin[2]; - - bmax[0] = items[imin].bmax[0]; - bmax[1] = items[imin].bmax[1]; - bmax[2] = items[imin].bmax[2]; - - for (int i = imin+1; i < imax; ++i) - { - const BVItem& it = items[i]; - if (it.bmin[0] < bmin[0]) bmin[0] = it.bmin[0]; - if (it.bmin[1] < bmin[1]) bmin[1] = it.bmin[1]; - if (it.bmin[2] < bmin[2]) bmin[2] = it.bmin[2]; - - if (it.bmax[0] > bmax[0]) bmax[0] = it.bmax[0]; - if (it.bmax[1] > bmax[1]) bmax[1] = it.bmax[1]; - if (it.bmax[2] > bmax[2]) bmax[2] = it.bmax[2]; - } -} - -inline int longestAxis(unsigned short x, unsigned short y, unsigned short z) -{ - int axis = 0; - unsigned short maxVal = x; - if (y > maxVal) - { - axis = 1; - maxVal = y; - } - if (z > maxVal) - { - axis = 2; - maxVal = z; - } - return axis; -} - -static void subdivide(BVItem* items, int nitems, int imin, int imax, int& curNode, dtStatBVNode* nodes) -{ - int inum = imax - imin; - int icur = curNode; - - dtStatBVNode& node = nodes[curNode++]; - - if (inum == 1) - { - // Leaf - node.bmin[0] = items[imin].bmin[0]; - node.bmin[1] = items[imin].bmin[1]; - node.bmin[2] = items[imin].bmin[2]; - - node.bmax[0] = items[imin].bmax[0]; - node.bmax[1] = items[imin].bmax[1]; - node.bmax[2] = items[imin].bmax[2]; - - node.i = items[imin].i; - } - else - { - // Split - calcExtends(items, nitems, imin, imax, node.bmin, node.bmax); - - int axis = longestAxis(node.bmax[0] - node.bmin[0], - node.bmax[1] - node.bmin[1], - node.bmax[2] - node.bmin[2]); - - if (axis == 0) - { - // Sort along x-axis - qsort(items+imin, inum, sizeof(BVItem), compareItemX); - } - else if (axis == 1) - { - // Sort along y-axis - qsort(items+imin, inum, sizeof(BVItem), compareItemY); - } - else - { - // Sort along z-axis - qsort(items+imin, inum, sizeof(BVItem), compareItemZ); - } - - int isplit = imin+inum/2; - - // Left - subdivide(items, nitems, imin, isplit, curNode, nodes); - // Right - subdivide(items, nitems, isplit, imax, curNode, nodes); - - int iescape = curNode - icur; - // Negative index means escape. - node.i = -iescape; - } -} - -/*static*/ int createBVTree(const unsigned short* verts, const int nverts, - const unsigned short* polys, const int npolys, const int nvp, - float cs, float ch, - int nnodes, dtStatBVNode* nodes) -{ - // Build tree - BVItem* items = new BVItem[npolys]; - for (int i = 0; i < npolys; i++) - { - BVItem& it = items[i]; - it.i = i+1; - // Calc polygon bounds. - const unsigned short* p = &polys[i*nvp*2]; - it.bmin[0] = it.bmax[0] = verts[p[0]*3+0]; - it.bmin[1] = it.bmax[1] = verts[p[0]*3+1]; - it.bmin[2] = it.bmax[2] = verts[p[0]*3+2]; - - for (int j = 1; j < nvp; ++j) - { - if (p[j] == 0xffff) break; - unsigned short x = verts[p[j]*3+0]; - unsigned short y = verts[p[j]*3+1]; - unsigned short z = verts[p[j]*3+2]; - - if (x < it.bmin[0]) it.bmin[0] = x; - if (y < it.bmin[1]) it.bmin[1] = y; - if (z < it.bmin[2]) it.bmin[2] = z; - - if (x > it.bmax[0]) it.bmax[0] = x; - if (y > it.bmax[1]) it.bmax[1] = y; - if (z > it.bmax[2]) it.bmax[2] = z; - } - // Remap y - it.bmin[1] = (unsigned short)floorf((float)it.bmin[1]*ch/cs); - it.bmax[1] = (unsigned short)ceilf((float)it.bmax[1]*ch/cs); - } - - int curNode = 0; - subdivide(items, npolys, 0, npolys, curNode, nodes); - - delete [] items; - - return curNode; -} - - -bool dtCreateNavMeshData(const unsigned short* verts, const int nverts, - const unsigned short* polys, const int npolys, const int nvp, - const float* bmin, const float* bmax, float cs, float ch, - const unsigned short* dmeshes, const float* dverts, const int ndverts, - const unsigned char* dtris, const int ndtris, - unsigned char** outData, int* outDataSize) -{ - if (nvp > DT_STAT_VERTS_PER_POLYGON) - return false; - if (nverts >= 0xffff) - return false; - - if (!nverts) - return false; - if (!npolys) - return false; - if (!dmeshes || !dverts || ! dtris) - return false; - - // Find unique detail vertices. - int uniqueDetailVerts = 0; - if (dmeshes) - { - for (int i = 0; i < npolys; ++i) - { - const unsigned short* p = &polys[i*nvp*2]; - int ndv = dmeshes[i*4+1]; - int nv = 0; - for (int j = 0; j < nvp; ++j) - { - if (p[j] == 0xffff) break; - nv++; - } - ndv -= nv; - uniqueDetailVerts += ndv; - } - } - - // Calculate data size - const int headerSize = sizeof(dtStatNavMeshHeader); - const int vertsSize = sizeof(float)*3*nverts; - const int polysSize = sizeof(dtStatPoly)*npolys; - const int nodesSize = sizeof(dtStatBVNode)*npolys*2; - const int detailMeshesSize = sizeof(dtStatPolyDetail)*npolys; - const int detailVertsSize = sizeof(float)*3*uniqueDetailVerts; - const int detailTrisSize = sizeof(unsigned char)*4*ndtris; - - const int dataSize = headerSize + vertsSize + polysSize + nodesSize + - detailMeshesSize + detailVertsSize + detailTrisSize; - unsigned char* data = new unsigned char[dataSize]; - if (!data) - return false; - memset(data, 0, dataSize); - - unsigned char* d = data; - dtStatNavMeshHeader* header = (dtStatNavMeshHeader*)d; d += headerSize; - float* navVerts = (float*)d; d += vertsSize; - dtStatPoly* navPolys = (dtStatPoly*)d; d += polysSize; - dtStatBVNode* navNodes = (dtStatBVNode*)d; d += nodesSize; - dtStatPolyDetail* navDMeshes = (dtStatPolyDetail*)d; d += detailMeshesSize; - float* navDVerts = (float*)d; d += detailVertsSize; - unsigned char* navDTris = (unsigned char*)d; d += detailTrisSize; - - // Store header - header->magic = DT_STAT_NAVMESH_MAGIC; - header->version = DT_STAT_NAVMESH_VERSION; - header->npolys = npolys; - header->nverts = nverts; - header->cs = cs; - header->bmin[0] = bmin[0]; - header->bmin[1] = bmin[1]; - header->bmin[2] = bmin[2]; - header->bmax[0] = bmax[0]; - header->bmax[1] = bmax[1]; - header->bmax[2] = bmax[2]; - header->ndmeshes = dmeshes ? npolys : 0; - header->ndverts = dmeshes ? uniqueDetailVerts : 0; - header->ndtris = dmeshes ? ndtris : 0; - - // Store vertices - for (int i = 0; i < nverts; ++i) - { - const unsigned short* iv = &verts[i*3]; - float* v = &navVerts[i*3]; - v[0] = bmin[0] + iv[0] * cs; - v[1] = bmin[1] + iv[1] * ch; - v[2] = bmin[2] + iv[2] * cs; - } - - // Store polygons - const unsigned short* src = polys; - for (int i = 0; i < npolys; ++i) - { - dtStatPoly* p = &navPolys[i]; - p->nv = 0; - for (int j = 0; j < nvp; ++j) - { - if (src[j] == 0xffff) break; - p->v[j] = src[j]; - p->n[j] = src[nvp+j]+1; - p->nv++; - } - src += nvp*2; - } - - header->nnodes = createBVTree(verts, nverts, polys, npolys, nvp, - cs, ch, npolys*2, navNodes); - - - // Store detail meshes and vertices. - // The nav polygon vertices are stored as the first vertices on each mesh. - // We compress the mesh data by skipping them and using the navmesh coordinates. - unsigned short vbase = 0; - for (int i = 0; i < npolys; ++i) - { - dtStatPolyDetail& dtl = navDMeshes[i]; - const int vb = dmeshes[i*4+0]; - const int ndv = dmeshes[i*4+1]; - const int nv = navPolys[i].nv; - dtl.vbase = vbase; - dtl.nverts = ndv-nv; - dtl.tbase = dmeshes[i*4+2]; - dtl.ntris = dmeshes[i*4+3]; - // Copy vertices except the first 'nv' verts which are equal to nav poly verts. - if (ndv-nv) - { - memcpy(&navDVerts[vbase*3], &dverts[(vb+nv)*3], sizeof(float)*3*(ndv-nv)); - vbase += ndv-nv; - } - } - // Store triangles. - memcpy(navDTris, dtris, sizeof(unsigned char)*4*ndtris); - - *outData = data; - *outDataSize = dataSize; - - return true; -} diff --git a/extern/recastnavigation/Detour/Source/DetourTileNavMesh.cpp b/extern/recastnavigation/Detour/Source/DetourTileNavMesh.cpp deleted file mode 100644 index 0813c7755cc..00000000000 --- a/extern/recastnavigation/Detour/Source/DetourTileNavMesh.cpp +++ /dev/null @@ -1,1428 +0,0 @@ -// -// Copyright (c) 2009 Mikko Mononen memon@inside.org -// -// This software is provided 'as-is', without any express or implied -// warranty. In no event will the authors be held liable for any damages -// arising from the use of this software. -// Permission is granted to anyone to use this software for any purpose, -// including commercial applications, and to alter it and redistribute it -// freely, subject to the following restrictions: -// 1. The origin of this software must not be misrepresented; you must not -// claim that you wrote the original software. If you use this software -// in a product, an acknowledgment in the product documentation would be -// appreciated but is not required. -// 2. Altered source versions must be plainly marked as such, and must not be -// misrepresented as being the original software. -// 3. This notice may not be removed or altered from any source distribution. -// - -#include <math.h> -#include <float.h> -#include <string.h> -#include <stdio.h> -#include "DetourTileNavMesh.h" -#include "DetourNode.h" -#include "DetourCommon.h" - - -inline int opposite(int side) { return (side+2) & 0x3; } - -inline bool overlapBoxes(const float* amin, const float* amax, - const float* bmin, const float* bmax) -{ - bool overlap = true; - overlap = (amin[0] > bmax[0] || amax[0] < bmin[0]) ? false : overlap; - overlap = (amin[1] > bmax[1] || amax[1] < bmin[1]) ? false : overlap; - overlap = (amin[2] > bmax[2] || amax[2] < bmin[2]) ? false : overlap; - return overlap; -} - -inline bool overlapRects(const float* amin, const float* amax, - const float* bmin, const float* bmax) -{ - bool overlap = true; - overlap = (amin[0] > bmax[0] || amax[0] < bmin[0]) ? false : overlap; - overlap = (amin[1] > bmax[1] || amax[1] < bmin[1]) ? false : overlap; - return overlap; -} - -static void calcRect(const float* va, const float* vb, - float* bmin, float* bmax, - int side, float padx, float pady) -{ - if ((side&1) == 0) - { - bmin[0] = min(va[2],vb[2]) + padx; - bmin[1] = min(va[1],vb[1]) - pady; - bmax[0] = max(va[2],vb[2]) - padx; - bmax[1] = max(va[1],vb[1]) + pady; - } - else - { - bmin[0] = min(va[0],vb[0]) + padx; - bmin[1] = min(va[1],vb[1]) - pady; - bmax[0] = max(va[0],vb[0]) - padx; - bmax[1] = max(va[1],vb[1]) + pady; - } -} - -inline int computeTileHash(int x, int y) -{ - const unsigned int h1 = 0x8da6b343; // Large multiplicative constants; - const unsigned int h2 = 0xd8163841; // here arbitrarily chosen primes - unsigned int n = h1 * x + h2 * y; - return (int)(n & (DT_TILE_LOOKUP_SIZE-1)); -} - -////////////////////////////////////////////////////////////////////////////////////////// -dtTiledNavMesh::dtTiledNavMesh() : - m_tileSize(0), - m_portalHeight(0), - m_nextFree(0), - m_tmpLinks(0), - m_ntmpLinks(0), - m_nodePool(0), - m_openList(0) -{ -} - -dtTiledNavMesh::~dtTiledNavMesh() -{ - for (int i = 0; i < DT_MAX_TILES; ++i) - { - if (m_tiles[i].data && m_tiles[i].dataSize < 0) - { - delete [] m_tiles[i].data; - m_tiles[i].data = 0; - m_tiles[i].dataSize = 0; - } - } - delete [] m_tmpLinks; - delete m_nodePool; - delete m_openList; -} - -bool dtTiledNavMesh::init(const float* orig, float tileSize, float portalHeight) -{ - vcopy(m_orig, orig); - m_tileSize = tileSize; - m_portalHeight = portalHeight; - - // Init tiles - memset(m_tiles, 0, sizeof(dtTile)*DT_MAX_TILES); - memset(m_posLookup, 0, sizeof(dtTile*)*DT_TILE_LOOKUP_SIZE); - m_nextFree = 0; - for (int i = DT_MAX_TILES-1; i >= 0; --i) - { - m_tiles[i].next = m_nextFree; - m_nextFree = &m_tiles[i]; - } - - if (!m_nodePool) - { - m_nodePool = new dtNodePool(2048, 256); - if (!m_nodePool) - return false; - } - - if (!m_openList) - { - m_openList = new dtNodeQueue(2048); - if (!m_openList) - return false; - } - - return true; -} - -////////////////////////////////////////////////////////////////////////////////////////// -int dtTiledNavMesh::findConnectingPolys(const float* va, const float* vb, - dtTile* tile, int side, - dtTilePolyRef* con, float* conarea, int maxcon) -{ - if (!tile) return 0; - dtTileHeader* h = tile->header; - - float amin[2], amax[2]; - calcRect(va,vb, amin,amax, side, 0.01f, m_portalHeight); - - // Remove links pointing to 'side' and compact the links array. - float bmin[2], bmax[2]; - unsigned short m = 0x8000 | (unsigned short)side; - int n = 0; - - dtTilePolyRef base = getTileId(tile); - - for (int i = 0; i < h->npolys; ++i) - { - dtTilePoly* poly = &h->polys[i]; - for (int j = 0; j < poly->nv; ++j) - { - // Skip edges which do not point to the right side. - if (poly->n[j] != m) continue; - // Check if the segments touch. - const float* vc = &h->verts[poly->v[j]*3]; - const float* vd = &h->verts[poly->v[(j+1) % (int)poly->nv]*3]; - calcRect(vc,vd, bmin,bmax, side, 0.01f, m_portalHeight); - if (!overlapRects(amin,amax, bmin,bmax)) continue; - // Add return value. - if (n < maxcon) - { - conarea[n*2+0] = max(amin[0], bmin[0]); - conarea[n*2+1] = min(amax[0], bmax[0]); - con[n] = base | (unsigned int)i; - n++; - } - break; - } - } - return n; -} - -void dtTiledNavMesh::removeExtLinks(dtTile* tile, int side) -{ - if (!tile) return; - dtTileHeader* h = tile->header; - - // Remove links pointing to 'side' and compact the links array. - dtTileLink* pool = m_tmpLinks; - int nlinks = 0; - for (int i = 0; i < h->npolys; ++i) - { - dtTilePoly* poly = &h->polys[i]; - int plinks = nlinks; - int nplinks = 0; - for (int j = 0; j < poly->nlinks; ++j) - { - dtTileLink* link = &h->links[poly->links+j]; - if ((int)link->side != side) - { - if (nlinks < h->maxlinks) - { - dtTileLink* dst = &pool[nlinks++]; - memcpy(dst, link, sizeof(dtTileLink)); - nplinks++; - } - } - } - poly->links = plinks; - poly->nlinks = nplinks; - } - h->nlinks = nlinks; - if (h->nlinks) - memcpy(h->links, m_tmpLinks, sizeof(dtTileLink)*nlinks); -} - -void dtTiledNavMesh::buildExtLinks(dtTile* tile, dtTile* target, int side) -{ - if (!tile) return; - dtTileHeader* h = tile->header; - - // Remove links pointing to 'side' and compact the links array. - dtTileLink* pool = m_tmpLinks; - int nlinks = 0; - for (int i = 0; i < h->npolys; ++i) - { - dtTilePoly* poly = &h->polys[i]; - int plinks = nlinks; - int nplinks = 0; - // Copy internal and other external links. - for (int j = 0; j < poly->nlinks; ++j) - { - dtTileLink* link = &h->links[poly->links+j]; - if ((int)link->side != side) - { - if (nlinks < h->maxlinks) - { - dtTileLink* dst = &pool[nlinks++]; - memcpy(dst, link, sizeof(dtTileLink)); - nplinks++; - } - } - } - // Create new links. - unsigned short m = 0x8000 | (unsigned short)side; - for (int j = 0; j < poly->nv; ++j) - { - // Skip edges which do not point to the right side. - if (poly->n[j] != m) continue; - - // Create new links - const float* va = &h->verts[poly->v[j]*3]; - const float* vb = &h->verts[poly->v[(j+1)%(int)poly->nv]*3]; - dtTilePolyRef nei[4]; - float neia[4*2]; - int nnei = findConnectingPolys(va,vb, target, opposite(side), nei,neia,4); - for (int k = 0; k < nnei; ++k) - { - if (nlinks < h->maxlinks) - { - dtTileLink* link = &pool[nlinks++]; - link->ref = nei[k]; - link->p = (unsigned short)i; - link->e = (unsigned char)j; - link->side = (unsigned char)side; - - // Compress portal limits to a byte value. - if (side == 0 || side == 2) - { - const float lmin = min(va[2], vb[2]); - const float lmax = max(va[2], vb[2]); - link->bmin = (unsigned char)(clamp((neia[k*2+0]-lmin)/(lmax-lmin), 0.0f, 1.0f)*255.0f); - link->bmax = (unsigned char)(clamp((neia[k*2+1]-lmin)/(lmax-lmin), 0.0f, 1.0f)*255.0f); - } - else - { - const float lmin = min(va[0], vb[0]); - const float lmax = max(va[0], vb[0]); - link->bmin = (unsigned char)(clamp((neia[k*2+0]-lmin)/(lmax-lmin), 0.0f, 1.0f)*255.0f); - link->bmax = (unsigned char)(clamp((neia[k*2+1]-lmin)/(lmax-lmin), 0.0f, 1.0f)*255.0f); - } - nplinks++; - } - } - } - - poly->links = plinks; - poly->nlinks = nplinks; - } - h->nlinks = nlinks; - if (h->nlinks) - memcpy(h->links, m_tmpLinks, sizeof(dtTileLink)*nlinks); -} - -void dtTiledNavMesh::buildIntLinks(dtTile* tile) -{ - if (!tile) return; - dtTileHeader* h = tile->header; - - dtTilePolyRef base = getTileId(tile); - dtTileLink* pool = h->links; - int nlinks = 0; - for (int i = 0; i < h->npolys; ++i) - { - dtTilePoly* poly = &h->polys[i]; - poly->links = nlinks; - poly->nlinks = 0; - for (int j = 0; j < poly->nv; ++j) - { - // Skip hard and non-internal edges. - if (poly->n[j] == 0 || (poly->n[j] & 0x8000)) continue; - - if (nlinks < h->maxlinks) - { - dtTileLink* link = &pool[nlinks++]; - link->ref = base | (unsigned int)(poly->n[j]-1); - link->p = (unsigned short)i; - link->e = (unsigned char)j; - link->side = 0xff; - link->bmin = link->bmax = 0; - poly->nlinks++; - } - } - } - h->nlinks = nlinks; -} - -bool dtTiledNavMesh::addTileAt(int x, int y, unsigned char* data, int dataSize, bool ownsData) -{ - if (getTileAt(x,y)) - return false; - // Make sure there is enough space for new tile. - if (!m_nextFree) - return false; - // Make sure the data is in right format. - dtTileHeader* header = (dtTileHeader*)data; - if (header->magic != DT_TILE_NAVMESH_MAGIC) - return false; - if (header->version != DT_TILE_NAVMESH_VERSION) - return false; - - // Make sure the tmp link array is large enough. - if (header->maxlinks > m_ntmpLinks) - { - m_ntmpLinks = header->maxlinks; - delete [] m_tmpLinks; - m_tmpLinks = 0; - m_tmpLinks = new dtTileLink[m_ntmpLinks]; - } - if (!m_tmpLinks) - return false; - - // Allocate a tile. - dtTile* tile = m_nextFree; - m_nextFree = tile->next; - tile->next = 0; - - // Insert tile into the position lut. - int h = computeTileHash(x,y); - tile->next = m_posLookup[h]; - m_posLookup[h] = tile; - - // Patch header pointers. - const int headerSize = sizeof(dtTileHeader); - const int vertsSize = sizeof(float)*3*header->nverts; - const int polysSize = sizeof(dtTilePoly)*header->npolys; - const int linksSize = sizeof(dtTileLink)*(header->maxlinks); - const int detailMeshesSize = sizeof(dtTilePolyDetail)*header->ndmeshes; - const int detailVertsSize = sizeof(float)*3*header->ndverts; - const int detailTrisSize = sizeof(unsigned char)*4*header->ndtris; - - unsigned char* d = data + headerSize; - header->verts = (float*)d; d += vertsSize; - header->polys = (dtTilePoly*)d; d += polysSize; - header->links = (dtTileLink*)d; d += linksSize; - header->dmeshes = (dtTilePolyDetail*)d; d += detailMeshesSize; - header->dverts = (float*)d; d += detailVertsSize; - header->dtris = (unsigned char*)d; d += detailTrisSize; - - // Init tile. - tile->header = header; - tile->x = x; - tile->y = y; - tile->data = data; - tile->dataSize = dataSize; - tile->ownsData = ownsData; - - buildIntLinks(tile); - - // Create connections connections. - for (int i = 0; i < 4; ++i) - { - dtTile* nei = getNeighbourTileAt(x,y,i); - if (nei) - { - buildExtLinks(tile, nei, i); - buildExtLinks(nei, tile, opposite(i)); - } - } - - return true; -} - -dtTile* dtTiledNavMesh::getTileAt(int x, int y) -{ - // Find tile based on hash. - int h = computeTileHash(x,y); - dtTile* tile = m_posLookup[h]; - while (tile) - { - if (tile->x == x && tile->y == y) - return tile; - tile = tile->next; - } - return 0; -} - -dtTile* dtTiledNavMesh::getTile(int i) -{ - return &m_tiles[i]; -} - -const dtTile* dtTiledNavMesh::getTile(int i) const -{ - return &m_tiles[i]; -} - -dtTile* dtTiledNavMesh::getNeighbourTileAt(int x, int y, int side) -{ - switch (side) - { - case 0: x++; break; - case 1: y++; break; - case 2: x--; break; - case 3: y--; break; - }; - return getTileAt(x,y); -} - -bool dtTiledNavMesh::removeTileAt(int x, int y, unsigned char** data, int* dataSize) -{ - // Remove tile from hash lookup. - int h = computeTileHash(x,y); - dtTile* prev = 0; - dtTile* tile = m_posLookup[h]; - while (tile) - { - if (tile->x == x && tile->y == y) - { - if (prev) - prev->next = tile->next; - else - m_posLookup[h] = tile->next; - break; - } - prev = tile; - tile = tile->next; - } - if (!tile) - return false; - - // Remove connections to neighbour tiles. - for (int i = 0; i < 4; ++i) - { - dtTile* nei = getNeighbourTileAt(x,y,i); - if (!nei) continue; - removeExtLinks(nei, opposite(i)); - } - - - // Reset tile. - if (tile->ownsData) - { - // Owns data - delete [] tile->data; - tile->data = 0; - tile->dataSize = 0; - if (data) *data = 0; - if (dataSize) *dataSize = 0; - } - else - { - if (data) *data = tile->data; - if (dataSize) *dataSize = tile->dataSize; - } - tile->header = 0; - tile->x = tile->y = 0; - tile->salt++; - - // Add to free list. - tile->next = m_nextFree; - m_nextFree = tile; - - return true; -} - - - -bool dtTiledNavMesh::closestPointToPoly(dtTilePolyRef ref, const float* pos, float* closest) const -{ - unsigned int salt, it, ip; - dtDecodeTileId(ref, salt, it, ip); - if (it >= DT_MAX_TILES) return false; - if (m_tiles[it].salt != salt || m_tiles[it].header == 0) return false; - const dtTileHeader* header = m_tiles[it].header; - - if (ip >= (unsigned int)header->npolys) return false; - const dtTilePoly* poly = &header->polys[ip]; - - float closestDistSqr = FLT_MAX; - const dtTilePolyDetail* pd = &header->dmeshes[ip]; - - for (int j = 0; j < pd->ntris; ++j) - { - const unsigned char* t = &header->dtris[(pd->tbase+j)*4]; - const float* v[3]; - for (int k = 0; k < 3; ++k) - { - if (t[k] < poly->nv) - v[k] = &header->verts[poly->v[t[k]]*3]; - else - v[k] = &header->dverts[(pd->vbase+(t[k]-poly->nv))*3]; - } - float pt[3]; - closestPtPointTriangle(pt, pos, v[0], v[1], v[2]); - float d = vdistSqr(pos, pt); - if (d < closestDistSqr) - { - vcopy(closest, pt); - closestDistSqr = d; - } - } - - return true; -} - -bool dtTiledNavMesh::getPolyHeight(dtTilePolyRef ref, const float* pos, float* height) const -{ - unsigned int salt, it, ip; - dtDecodeTileId(ref, salt, it, ip); - if (it >= DT_MAX_TILES) return false; - if (m_tiles[it].salt != salt || m_tiles[it].header == 0) return false; - const dtTileHeader* header = m_tiles[it].header; - - if (ip >= (unsigned int)header->npolys) return false; - const dtTilePoly* poly = &header->polys[ip]; - - const dtTilePolyDetail* pd = &header->dmeshes[ip]; - for (int j = 0; j < pd->ntris; ++j) - { - const unsigned char* t = &header->dtris[(pd->tbase+j)*4]; - const float* v[3]; - for (int k = 0; k < 3; ++k) - { - if (t[k] < poly->nv) - v[k] = &header->verts[poly->v[t[k]]*3]; - else - v[k] = &header->dverts[(pd->vbase+(t[k]-poly->nv))*3]; - } - float h; - if (closestHeightPointTriangle(pos, v[0], v[1], v[2], h)) - { - if (height) - *height = h; - return true; - } - } - - return false; -} - - -dtTilePolyRef dtTiledNavMesh::findNearestPoly(const float* center, const float* extents) -{ - // Get nearby polygons from proximity grid. - dtTilePolyRef polys[128]; - int npolys = queryPolygons(center, extents, polys, 128); - - // Find nearest polygon amongst the nearby polygons. - dtTilePolyRef nearest = 0; - float nearestDistanceSqr = FLT_MAX; - for (int i = 0; i < npolys; ++i) - { - dtTilePolyRef ref = polys[i]; - float closest[3]; - if (!closestPointToPoly(ref, center, closest)) - continue; - float d = vdistSqr(center, closest); - if (d < nearestDistanceSqr) - { - nearestDistanceSqr = d; - nearest = ref; - } - } - - return nearest; -} - -dtTilePolyRef dtTiledNavMesh::getTileId(dtTile* tile) -{ - if (!tile) return 0; - const unsigned int it = tile - m_tiles; - return dtEncodeTileId(tile->salt, it, 0); -} - -int dtTiledNavMesh::queryTilePolygons(dtTile* tile, - const float* qmin, const float* qmax, - dtTilePolyRef* polys, const int maxPolys) -{ - float bmin[3], bmax[3]; - const dtTileHeader* header = tile->header; - int n = 0; - dtTilePolyRef base = getTileId(tile); - for (int i = 0; i < header->npolys; ++i) - { - // Calc polygon bounds. - dtTilePoly* p = &header->polys[i]; - const float* v = &header->verts[p->v[0]*3]; - vcopy(bmin, v); - vcopy(bmax, v); - for (int j = 1; j < p->nv; ++j) - { - v = &header->verts[p->v[j]*3]; - vmin(bmin, v); - vmax(bmax, v); - } - if (overlapBoxes(qmin,qmax, bmin,bmax)) - { - if (n < maxPolys) - polys[n++] = base | (dtTilePolyRef)i; - } - } - return n; -} - -int dtTiledNavMesh::queryPolygons(const float* center, const float* extents, - dtTilePolyRef* polys, const int maxPolys) -{ - float bmin[3], bmax[3]; - bmin[0] = center[0] - extents[0]; - bmin[1] = center[1] - extents[1]; - bmin[2] = center[2] - extents[2]; - - bmax[0] = center[0] + extents[0]; - bmax[1] = center[1] + extents[1]; - bmax[2] = center[2] + extents[2]; - - // Find tiles the query touches. - const int minx = (int)floorf((bmin[0]-m_orig[0]) / m_tileSize); - const int maxx = (int)ceilf((bmax[0]-m_orig[0]) / m_tileSize); - - const int miny = (int)floorf((bmin[2]-m_orig[2]) / m_tileSize); - const int maxy = (int)ceilf((bmax[2]-m_orig[2]) / m_tileSize); - - int n = 0; - for (int y = miny; y < maxy; ++y) - { - for (int x = minx; x < maxx; ++x) - { - dtTile* tile = getTileAt(x,y); - if (!tile) continue; - n += queryTilePolygons(tile, bmin, bmax, polys+n, maxPolys-n); - if (n >= maxPolys) return n; - } - } - - return n; -} - -int dtTiledNavMesh::findPath(dtTilePolyRef startRef, dtTilePolyRef endRef, - const float* startPos, const float* endPos, - dtTilePolyRef* path, const int maxPathSize) -{ - if (!startRef || !endRef) - return 0; - - if (!maxPathSize) - return 0; - - if (!getPolyByRef(startRef) || !getPolyByRef(endRef)) - return 0; - - if (startRef == endRef) - { - path[0] = startRef; - return 1; - } - - if (!m_nodePool || !m_openList) - return 0; - - m_nodePool->clear(); - m_openList->clear(); - - static const float H_SCALE = 1.1f; // Heuristic scale. - - dtNode* startNode = m_nodePool->getNode(startRef); - startNode->pidx = 0; - startNode->cost = 0; - startNode->total = vdist(startPos, endPos) * H_SCALE; - startNode->id = startRef; - startNode->flags = DT_NODE_OPEN; - m_openList->push(startNode); - - dtNode* lastBestNode = startNode; - float lastBestNodeCost = startNode->total; - while (!m_openList->empty()) - { - dtNode* bestNode = m_openList->pop(); - - if (bestNode->id == endRef) - { - lastBestNode = bestNode; - break; - } - - // Get poly and tile. - unsigned int salt, it, ip; - dtDecodeTileId(bestNode->id, salt, it, ip); - // The API input has been cheked already, skip checking internal data. - const dtTileHeader* header = m_tiles[it].header; - const dtTilePoly* poly = &header->polys[ip]; - - for (int i = 0; i < poly->nlinks; ++i) - { - dtTilePolyRef neighbour = header->links[poly->links+i].ref; - if (neighbour) - { - // Skip parent node. - if (bestNode->pidx && m_nodePool->getNodeAtIdx(bestNode->pidx)->id == neighbour) - continue; - - dtNode* parent = bestNode; - dtNode newNode; - newNode.pidx = m_nodePool->getNodeIdx(parent); - newNode.id = neighbour; - - // Calculate cost. - float p0[3], p1[3]; - if (!parent->pidx) - vcopy(p0, startPos); - else - getEdgeMidPoint(m_nodePool->getNodeAtIdx(parent->pidx)->id, parent->id, p0); - getEdgeMidPoint(parent->id, newNode.id, p1); - newNode.cost = parent->cost + vdist(p0,p1); - // Special case for last node. - if (newNode.id == endRef) - newNode.cost += vdist(p1, endPos); - - // Heuristic - const float h = vdist(p1,endPos)*H_SCALE; - newNode.total = newNode.cost + h; - - dtNode* actualNode = m_nodePool->getNode(newNode.id); - if (!actualNode) - continue; - - if (!((actualNode->flags & DT_NODE_OPEN) && newNode.total > actualNode->total) && - !((actualNode->flags & DT_NODE_CLOSED) && newNode.total > actualNode->total)) - { - actualNode->flags &= DT_NODE_CLOSED; - actualNode->pidx = newNode.pidx; - actualNode->cost = newNode.cost; - actualNode->total = newNode.total; - - if (h < lastBestNodeCost) - { - lastBestNodeCost = h; - lastBestNode = actualNode; - } - - if (actualNode->flags & DT_NODE_OPEN) - { - m_openList->modify(actualNode); - } - else - { - actualNode->flags |= DT_NODE_OPEN; - m_openList->push(actualNode); - } - } - } - } - bestNode->flags |= DT_NODE_CLOSED; - } - - // Reverse the path. - dtNode* prev = 0; - dtNode* node = lastBestNode; - do - { - dtNode* next = m_nodePool->getNodeAtIdx(node->pidx); - node->pidx = m_nodePool->getNodeIdx(prev); - prev = node; - node = next; - } - while (node); - - // Store path - node = prev; - int n = 0; - do - { - path[n++] = node->id; - node = m_nodePool->getNodeAtIdx(node->pidx); - } - while (node && n < maxPathSize); - - return n; -} - -int dtTiledNavMesh::findStraightPath(const float* startPos, const float* endPos, - const dtTilePolyRef* path, const int pathSize, - float* straightPath, const int maxStraightPathSize) -{ - if (!maxStraightPathSize) - return 0; - - if (!path[0]) - return 0; - - int straightPathSize = 0; - - float closestStartPos[3]; - if (!closestPointToPoly(path[0], startPos, closestStartPos)) - return 0; - - // Add start point. - vcopy(&straightPath[straightPathSize*3], closestStartPos); - straightPathSize++; - if (straightPathSize >= maxStraightPathSize) - return straightPathSize; - - float closestEndPos[3]; - if (!closestPointToPoly(path[pathSize-1], endPos, closestEndPos)) - return 0; - - float portalApex[3], portalLeft[3], portalRight[3]; - - if (pathSize > 1) - { - vcopy(portalApex, closestStartPos); - vcopy(portalLeft, portalApex); - vcopy(portalRight, portalApex); - int apexIndex = 0; - int leftIndex = 0; - int rightIndex = 0; - - for (int i = 0; i < pathSize; ++i) - { - float left[3], right[3]; - if (i < pathSize-1) - { - // Next portal. - if (!getPortalPoints(path[i], path[i+1], left, right)) - { - if (!closestPointToPoly(path[i], endPos, closestEndPos)) - return 0; - vcopy(&straightPath[straightPathSize*3], closestEndPos); - straightPathSize++; - return straightPathSize; - } - } - else - { - // End of the path. - vcopy(left, closestEndPos); - vcopy(right, closestEndPos); - } - - // Right vertex. - if (vequal(portalApex, portalRight)) - { - vcopy(portalRight, right); - rightIndex = i; - } - else - { - if (triArea2D(portalApex, portalRight, right) <= 0.0f) - { - if (triArea2D(portalApex, portalLeft, right) > 0.0f) - { - vcopy(portalRight, right); - rightIndex = i; - } - else - { - vcopy(portalApex, portalLeft); - apexIndex = leftIndex; - - if (!vequal(&straightPath[(straightPathSize-1)*3], portalApex)) - { - vcopy(&straightPath[straightPathSize*3], portalApex); - straightPathSize++; - if (straightPathSize >= maxStraightPathSize) - return straightPathSize; - } - - vcopy(portalLeft, portalApex); - vcopy(portalRight, portalApex); - leftIndex = apexIndex; - rightIndex = apexIndex; - - // Restart - i = apexIndex; - - continue; - } - } - } - - // Left vertex. - if (vequal(portalApex, portalLeft)) - { - vcopy(portalLeft, left); - leftIndex = i; - } - else - { - if (triArea2D(portalApex, portalLeft, left) >= 0.0f) - { - if (triArea2D(portalApex, portalRight, left) < 0.0f) - { - vcopy(portalLeft, left); - leftIndex = i; - } - else - { - vcopy(portalApex, portalRight); - apexIndex = rightIndex; - - if (!vequal(&straightPath[(straightPathSize-1)*3], portalApex)) - { - vcopy(&straightPath[straightPathSize*3], portalApex); - straightPathSize++; - if (straightPathSize >= maxStraightPathSize) - return straightPathSize; - } - - vcopy(portalLeft, portalApex); - vcopy(portalRight, portalApex); - leftIndex = apexIndex; - rightIndex = apexIndex; - - // Restart - i = apexIndex; - - continue; - } - } - } - } - } - - // Add end point. - vcopy(&straightPath[straightPathSize*3], closestEndPos); - straightPathSize++; - - return straightPathSize; -} - -// Returns portal points between two polygons. -bool dtTiledNavMesh::getPortalPoints(dtTilePolyRef from, dtTilePolyRef to, float* left, float* right) const -{ - unsigned int salt, it, ip; - dtDecodeTileId(from, salt, it, ip); - if (it >= DT_MAX_TILES) return false; - if (m_tiles[it].salt != salt || m_tiles[it].header == 0) return false; - if (ip >= (unsigned int)m_tiles[it].header->npolys) return false; - const dtTileHeader* fromHeader = m_tiles[it].header; - const dtTilePoly* fromPoly = &fromHeader->polys[ip]; - - for (int i = 0; i < fromPoly->nlinks; ++i) - { - const dtTileLink* link = &fromHeader->links[fromPoly->links+i]; - if (link->ref == to) - { - // Find portal vertices. - const int v0 = fromPoly->v[link->e]; - const int v1 = fromPoly->v[(link->e+1) % fromPoly->nv]; - vcopy(left, &fromHeader->verts[v0*3]); - vcopy(right, &fromHeader->verts[v1*3]); - // If the link is at tile boundary, clamp the vertices to - // the link width. - if (link->side == 0 || link->side == 2) - { - // Unpack portal limits. - const float smin = min(left[2],right[2]); - const float smax = max(left[2],right[2]); - const float s = (smax-smin) / 255.0f; - const float lmin = smin + link->bmin*s; - const float lmax = smin + link->bmax*s; - left[2] = max(left[2],lmin); - left[2] = min(left[2],lmax); - right[2] = max(right[2],lmin); - right[2] = min(right[2],lmax); - } - else if (link->side == 1 || link->side == 3) - { - // Unpack portal limits. - const float smin = min(left[0],right[0]); - const float smax = max(left[0],right[0]); - const float s = (smax-smin) / 255.0f; - const float lmin = smin + link->bmin*s; - const float lmax = smin + link->bmax*s; - left[0] = max(left[0],lmin); - left[0] = min(left[0],lmax); - right[0] = max(right[0],lmin); - right[0] = min(right[0],lmax); - } - return true; - } - } - return false; -} - -// Returns edge mid point between two polygons. -bool dtTiledNavMesh::getEdgeMidPoint(dtTilePolyRef from, dtTilePolyRef to, float* mid) const -{ - float left[3], right[3]; - if (!getPortalPoints(from, to, left,right)) return false; - mid[0] = (left[0]+right[0])*0.5f; - mid[1] = (left[1]+right[1])*0.5f; - mid[2] = (left[2]+right[2])*0.5f; - return true; -} - -int dtTiledNavMesh::raycast(dtTilePolyRef centerRef, const float* startPos, const float* endPos, - float& t, dtTilePolyRef* path, const int pathSize) -{ - t = 0; - - if (!centerRef || !getPolyByRef(centerRef)) - return 0; - - dtTilePolyRef curRef = centerRef; - float verts[DT_TILE_VERTS_PER_POLYGON*3]; - int n = 0; - - while (curRef) - { - // Cast ray against current polygon. - - // The API input has been cheked already, skip checking internal data. - unsigned int salt, it, ip; - dtDecodeTileId(curRef, salt, it, ip); - const dtTileHeader* header = m_tiles[it].header; - const dtTilePoly* poly = &header->polys[ip]; - - // Collect vertices. - int nv = 0; - for (int i = 0; i < (int)poly->nv; ++i) - { - vcopy(&verts[nv*3], &header->verts[poly->v[i]*3]); - nv++; - } - if (nv < 3) - { - // Hit bad polygon, report hit. - return n; - } - - float tmin, tmax; - int segMin, segMax; - if (!intersectSegmentPoly2D(startPos, endPos, verts, nv, tmin, tmax, segMin, segMax)) - { - // Could not hit the polygon, keep the old t and report hit. - return n; - } - // Keep track of furthest t so far. - if (tmax > t) - t = tmax; - - if (n < pathSize) - path[n++] = curRef; - - // Follow neighbours. - dtTilePolyRef nextRef = 0; - for (int i = 0; i < poly->nlinks; ++i) - { - const dtTileLink* link = &header->links[poly->links+i]; - if ((int)link->e == segMax) - { - // If the link is internal, just return the ref. - if (link->side == 0xff) - { - nextRef = link->ref; - break; - } - - // If the link is at tile boundary, - const int v0 = poly->v[link->e]; - const int v1 = poly->v[(link->e+1) % poly->nv]; - const float* left = &header->verts[v0*3]; - const float* right = &header->verts[v1*3]; - - // Check that the intersection lies inside the link portal. - if (link->side == 0 || link->side == 2) - { - // Calculate link size. - const float smin = min(left[2],right[2]); - const float smax = max(left[2],right[2]); - const float s = (smax-smin) / 255.0f; - const float lmin = smin + link->bmin*s; - const float lmax = smin + link->bmax*s; - // Find Z intersection. - float z = startPos[2] + (endPos[2]-startPos[2])*tmax; - if (z >= lmin && z <= lmax) - { - nextRef = link->ref; - break; - } - } - else if (link->side == 1 || link->side == 3) - { - // Calculate link size. - const float smin = min(left[0],right[0]); - const float smax = max(left[0],right[0]); - const float s = (smax-smin) / 255.0f; - const float lmin = smin + link->bmin*s; - const float lmax = smin + link->bmax*s; - // Find X intersection. - float x = startPos[0] + (endPos[0]-startPos[0])*tmax; - if (x >= lmin && x <= lmax) - { - nextRef = link->ref; - break; - } - } - } - } - - if (!nextRef) - { - // No neighbour, we hit a wall. - return n; - } - - // No hit, advance to neighbour polygon. - curRef = nextRef; - } - - return n; -} - -int dtTiledNavMesh::findPolysAround(dtTilePolyRef centerRef, const float* centerPos, float radius, - dtTilePolyRef* resultRef, dtTilePolyRef* resultParent, float* resultCost, - const int maxResult) -{ - if (!centerRef) return 0; - if (!getPolyByRef(centerRef)) return 0; - if (!m_nodePool || !m_openList) return 0; - - m_nodePool->clear(); - m_openList->clear(); - - dtNode* startNode = m_nodePool->getNode(centerRef); - startNode->pidx = 0; - startNode->cost = 0; - startNode->total = 0; - startNode->id = centerRef; - startNode->flags = DT_NODE_OPEN; - m_openList->push(startNode); - - int n = 0; - if (n < maxResult) - { - if (resultRef) - resultRef[n] = startNode->id; - if (resultParent) - resultParent[n] = 0; - if (resultCost) - resultCost[n] = 0; - ++n; - } - - const float radiusSqr = sqr(radius); - - while (!m_openList->empty()) - { - dtNode* bestNode = m_openList->pop(); - - // Get poly and tile. - unsigned int salt, it, ip; - dtDecodeTileId(bestNode->id, salt, it, ip); - // The API input has been cheked already, skip checking internal data. - const dtTileHeader* header = m_tiles[it].header; - const dtTilePoly* poly = &header->polys[ip]; - - for (int i = 0; i < poly->nlinks; ++i) - { - const dtTileLink* link = &header->links[poly->links+i]; - dtTilePolyRef neighbour = link->ref; - if (neighbour) - { - // Skip parent node. - if (bestNode->pidx && m_nodePool->getNodeAtIdx(bestNode->pidx)->id == neighbour) - continue; - - // Calc distance to the edge. - const float* va = &header->verts[poly->v[link->e]*3]; - const float* vb = &header->verts[poly->v[(link->e+1)%poly->nv]*3]; - float tseg; - float distSqr = distancePtSegSqr2D(centerPos, va, vb, tseg); - - // If the circle is not touching the next polygon, skip it. - if (distSqr > radiusSqr) - continue; - - dtNode* parent = bestNode; - dtNode newNode; - newNode.pidx = m_nodePool->getNodeIdx(parent); - newNode.id = neighbour; - - // Cost - float p0[3], p1[3]; - if (!parent->pidx) - vcopy(p0, centerPos); - else - getEdgeMidPoint(m_nodePool->getNodeAtIdx(parent->pidx)->id, parent->id, p0); - getEdgeMidPoint(parent->id, newNode.id, p1); - newNode.total = parent->total + vdist(p0,p1); - - dtNode* actualNode = m_nodePool->getNode(newNode.id); - if (!actualNode) - continue; - - if (!((actualNode->flags & DT_NODE_OPEN) && newNode.total > actualNode->total) && - !((actualNode->flags & DT_NODE_CLOSED) && newNode.total > actualNode->total)) - { - actualNode->flags &= ~DT_NODE_CLOSED; - actualNode->pidx = newNode.pidx; - actualNode->total = newNode.total; - - if (actualNode->flags & DT_NODE_OPEN) - { - m_openList->modify(actualNode); - } - else - { - if (n < maxResult) - { - if (resultRef) - resultRef[n] = actualNode->id; - if (resultParent) - resultParent[n] = m_nodePool->getNodeAtIdx(actualNode->pidx)->id; - if (resultCost) - resultCost[n] = actualNode->total; - ++n; - } - actualNode->flags = DT_NODE_OPEN; - m_openList->push(actualNode); - } - } - } - } - } - - return n; -} - -float dtTiledNavMesh::findDistanceToWall(dtTilePolyRef centerRef, const float* centerPos, float maxRadius, - float* hitPos, float* hitNormal) -{ - if (!centerRef) return 0; - if (!getPolyByRef(centerRef)) return 0; - if (!m_nodePool || !m_openList) return 0; - - m_nodePool->clear(); - m_openList->clear(); - - dtNode* startNode = m_nodePool->getNode(centerRef); - startNode->pidx = 0; - startNode->cost = 0; - startNode->total = 0; - startNode->id = centerRef; - startNode->flags = DT_NODE_OPEN; - m_openList->push(startNode); - - float radiusSqr = sqr(maxRadius); - - while (!m_openList->empty()) - { - dtNode* bestNode = m_openList->pop(); - - // Get poly and tile. - unsigned int salt, it, ip; - dtDecodeTileId(bestNode->id, salt, it, ip); - // The API input has been cheked already, skip checking internal data. - const dtTileHeader* header = m_tiles[it].header; - const dtTilePoly* poly = &header->polys[ip]; - - // Hit test walls. - for (int i = 0, j = (int)poly->nv-1; i < (int)poly->nv; j = i++) - { - // Skip non-solid edges. - if (poly->n[j] & 0x8000) - { - // Tile border. - bool solid = true; - for (int i = 0; i < poly->nlinks; ++i) - { - const dtTileLink* link = &header->links[poly->links+i]; - if (link->e == j && link->ref != 0) - { - solid = false; - break; - } - } - if (!solid) continue; - } - else if (poly->n[j]) - { - // Internal edge - continue; - } - - // Calc distance to the edge. - const float* vj = &header->verts[poly->v[j]*3]; - const float* vi = &header->verts[poly->v[i]*3]; - float tseg; - float distSqr = distancePtSegSqr2D(centerPos, vj, vi, tseg); - - // Edge is too far, skip. - if (distSqr > radiusSqr) - continue; - - // Hit wall, update radius. - radiusSqr = distSqr; - // Calculate hit pos. - hitPos[0] = vj[0] + (vi[0] - vj[0])*tseg; - hitPos[1] = vj[1] + (vi[1] - vj[1])*tseg; - hitPos[2] = vj[2] + (vi[2] - vj[2])*tseg; - } - - for (int i = 0; i < poly->nlinks; ++i) - { - const dtTileLink* link = &header->links[poly->links+i]; - dtTilePolyRef neighbour = link->ref; - if (neighbour) - { - // Skip parent node. - if (bestNode->pidx && m_nodePool->getNodeAtIdx(bestNode->pidx)->id == neighbour) - continue; - - // Calc distance to the edge. - const float* va = &header->verts[poly->v[link->e]*3]; - const float* vb = &header->verts[poly->v[(link->e+1)%poly->nv]*3]; - float tseg; - float distSqr = distancePtSegSqr2D(centerPos, va, vb, tseg); - - // If the circle is not touching the next polygon, skip it. - if (distSqr > radiusSqr) - continue; - - dtNode* parent = bestNode; - dtNode newNode; - newNode.pidx = m_nodePool->getNodeIdx(parent); - newNode.id = neighbour; - - float p0[3], p1[3]; - if (!parent->pidx) - vcopy(p0, centerPos); - else - getEdgeMidPoint(m_nodePool->getNodeAtIdx(parent->pidx)->id, parent->id, p0); - getEdgeMidPoint(parent->id, newNode.id, p1); - newNode.total = parent->total + vdist(p0,p1); - - dtNode* actualNode = m_nodePool->getNode(newNode.id); - if (!actualNode) - continue; - - if (!((actualNode->flags & DT_NODE_OPEN) && newNode.total > actualNode->total) && - !((actualNode->flags & DT_NODE_CLOSED) && newNode.total > actualNode->total)) - { - actualNode->flags &= ~DT_NODE_CLOSED; - actualNode->pidx = newNode.pidx; - actualNode->total = newNode.total; - - if (actualNode->flags & DT_NODE_OPEN) - { - m_openList->modify(actualNode); - } - else - { - actualNode->flags = DT_NODE_OPEN; - m_openList->push(actualNode); - } - } - } - } - } - - // Calc hit normal. - vsub(hitNormal, centerPos, hitPos); - vnormalize(hitNormal); - - return sqrtf(radiusSqr); -} - -const dtTilePoly* dtTiledNavMesh::getPolyByRef(dtTilePolyRef ref) const -{ - unsigned int salt, it, ip; - dtDecodeTileId(ref, salt, it, ip); - if (it >= DT_MAX_TILES) return 0; - if (m_tiles[it].salt != salt || m_tiles[it].header == 0) return 0; - if (ip >= (unsigned int)m_tiles[it].header->npolys) return 0; - return &m_tiles[it].header->polys[ip]; -} - -const float* dtTiledNavMesh::getPolyVertsByRef(dtTilePolyRef ref) const -{ - unsigned int salt, it, ip; - dtDecodeTileId(ref, salt, it, ip); - if (it >= DT_MAX_TILES) return 0; - if (m_tiles[it].salt != salt || m_tiles[it].header == 0) return 0; - if (ip >= (unsigned int)m_tiles[it].header->npolys) return 0; - return m_tiles[it].header->verts; -} - -const dtTileLink* dtTiledNavMesh::getPolyLinksByRef(dtTilePolyRef ref) const -{ - unsigned int salt, it, ip; - dtDecodeTileId(ref, salt, it, ip); - if (it >= DT_MAX_TILES) return 0; - if (m_tiles[it].salt != salt || m_tiles[it].header == 0) return 0; - if (ip >= (unsigned int)m_tiles[it].header->npolys) return 0; - return m_tiles[it].header->links; -} diff --git a/extern/recastnavigation/Detour/Source/DetourTileNavMeshBuilder.cpp b/extern/recastnavigation/Detour/Source/DetourTileNavMeshBuilder.cpp deleted file mode 100644 index 95dd34b04f6..00000000000 --- a/extern/recastnavigation/Detour/Source/DetourTileNavMeshBuilder.cpp +++ /dev/null @@ -1,213 +0,0 @@ -// -// Copyright (c) 2009 Mikko Mononen memon@inside.org -// -// This software is provided 'as-is', without any express or implied -// warranty. In no event will the authors be held liable for any damages -// arising from the use of this software. -// Permission is granted to anyone to use this software for any purpose, -// including commercial applications, and to alter it and redistribute it -// freely, subject to the following restrictions: -// 1. The origin of this software must not be misrepresented; you must not -// claim that you wrote the original software. If you use this software -// in a product, an acknowledgment in the product documentation would be -// appreciated but is not required. -// 2. Altered source versions must be plainly marked as such, and must not be -// misrepresented as being the original software. -// 3. This notice may not be removed or altered from any source distribution. -// - -#include <math.h> -#include <stdio.h> -#include <stdlib.h> -#include <string.h> -#include "DetourTileNavMesh.h" -#include "DetourCommon.h" - -bool dtCreateNavMeshTileData(const unsigned short* verts, const int nverts, - const unsigned short* polys, const int npolys, const int nvp, - const unsigned short* dmeshes, const float* dverts, const int ndverts, - const unsigned char* dtris, const int ndtris, - const float* bmin, const float* bmax, float cs, float ch, int tileSize, int walkableClimb, - unsigned char** outData, int* outDataSize) -{ - if (nvp != DT_TILE_VERTS_PER_POLYGON) - return false; - if (nverts >= 0xffff) - return false; - - if (!nverts) - return false; - if (!npolys) - return false; - if (!dmeshes || !dverts || ! dtris) - return false; - - // Find portal edges which are at tile borders. - int nedges = 0; - int nportals = 0; - for (int i = 0; i < npolys; ++i) - { - const unsigned short* p = &polys[i*2*nvp]; - for (int j = 0; j < nvp; ++j) - { - if (p[j] == 0xffff) break; - int nj = j+1; - if (nj >= nvp || p[nj] == 0xffff) nj = 0; - const unsigned short* va = &verts[p[j]*3]; - const unsigned short* vb = &verts[p[nj]*3]; - - nedges++; - - if (va[0] == tileSize && vb[0] == tileSize) - nportals++; // x+ - else if (va[2] == tileSize && vb[2] == tileSize) - nportals++; // z+ - else if (va[0] == 0 && vb[0] == 0) - nportals++; // x- - else if (va[2] == 0 && vb[2] == 0) - nportals++; // z- - } - } - - const int maxLinks = nedges + nportals*2; - - - // Find unique detail vertices. - int uniqueDetailVerts = 0; - if (dmeshes) - { - for (int i = 0; i < npolys; ++i) - { - const unsigned short* p = &polys[i*nvp*2]; - int ndv = dmeshes[i*4+1]; - int nv = 0; - for (int j = 0; j < nvp; ++j) - { - if (p[j] == 0xffff) break; - nv++; - } - ndv -= nv; - uniqueDetailVerts += ndv; - } - } - - // Calculate data size - const int headerSize = sizeof(dtTileHeader); - const int vertsSize = sizeof(float)*3*nverts; - const int polysSize = sizeof(dtTilePoly)*npolys; - const int linksSize = sizeof(dtTileLink)*maxLinks; - const int detailMeshesSize = sizeof(dtTilePolyDetail)*npolys; - const int detailVertsSize = sizeof(float)*3*uniqueDetailVerts; - const int detailTrisSize = sizeof(unsigned char)*4*ndtris; - - const int dataSize = headerSize + vertsSize + polysSize + linksSize + - detailMeshesSize + detailVertsSize + detailTrisSize; - unsigned char* data = new unsigned char[dataSize]; - if (!data) - return false; - memset(data, 0, dataSize); - - unsigned char* d = data; - dtTileHeader* header = (dtTileHeader*)d; d += headerSize; - float* navVerts = (float*)d; d += vertsSize; - dtTilePoly* navPolys = (dtTilePoly*)d; d += polysSize; - d += linksSize; - dtTilePolyDetail* navDMeshes = (dtTilePolyDetail*)d; d += detailMeshesSize; - float* navDVerts = (float*)d; d += detailVertsSize; - unsigned char* navDTris = (unsigned char*)d; d += detailTrisSize; - - - // Store header - header->magic = DT_TILE_NAVMESH_MAGIC; - header->version = DT_TILE_NAVMESH_VERSION; - header->npolys = npolys; - header->nverts = nverts; - header->maxlinks = maxLinks; - header->bmin[0] = bmin[0]; - header->bmin[1] = bmin[1]; - header->bmin[2] = bmin[2]; - header->bmax[0] = bmax[0]; - header->bmax[1] = bmax[1]; - header->bmax[2] = bmax[2]; - header->ndmeshes = npolys; - header->ndverts = uniqueDetailVerts; - header->ndtris = ndtris; - - // Store vertices - for (int i = 0; i < nverts; ++i) - { - const unsigned short* iv = &verts[i*3]; - float* v = &navVerts[i*3]; - v[0] = bmin[0] + iv[0] * cs; - v[1] = bmin[1] + iv[1] * ch; - v[2] = bmin[2] + iv[2] * cs; - } - - // Store polygons - const unsigned short* src = polys; - for (int i = 0; i < npolys; ++i) - { - dtTilePoly* p = &navPolys[i]; - p->nv = 0; - for (int j = 0; j < nvp; ++j) - { - if (src[j] == 0xffff) break; - p->v[j] = src[j]; - p->n[j] = (src[nvp+j]+1) & 0xffff; - p->nv++; - } - src += nvp*2; - } - - // Store portal edges. - for (int i = 0; i < npolys; ++i) - { - dtTilePoly* poly = &navPolys[i]; - for (int j = 0; j < poly->nv; ++j) - { - int nj = j+1; - if (nj >= poly->nv) nj = 0; - - const unsigned short* va = &verts[poly->v[j]*3]; - const unsigned short* vb = &verts[poly->v[nj]*3]; - - if (va[0] == tileSize && vb[0] == tileSize) // x+ - poly->n[j] = 0x8000 | 0; - else if (va[2] == tileSize && vb[2] == tileSize) // z+ - poly->n[j] = 0x8000 | 1; - else if (va[0] == 0 && vb[0] == 0) // x- - poly->n[j] = 0x8000 | 2; - else if (va[2] == 0 && vb[2] == 0) // z- - poly->n[j] = 0x8000 | 3; - } - } - - // Store detail meshes and vertices. - // The nav polygon vertices are stored as the first vertices on each mesh. - // We compress the mesh data by skipping them and using the navmesh coordinates. - unsigned short vbase = 0; - for (int i = 0; i < npolys; ++i) - { - dtTilePolyDetail& dtl = navDMeshes[i]; - const int vb = dmeshes[i*4+0]; - const int ndv = dmeshes[i*4+1]; - const int nv = navPolys[i].nv; - dtl.vbase = vbase; - dtl.nverts = ndv-nv; - dtl.tbase = dmeshes[i*4+2]; - dtl.ntris = dmeshes[i*4+3]; - // Copy vertices except the first 'nv' verts which are equal to nav poly verts. - if (ndv-nv) - { - memcpy(&navDVerts[vbase*3], &dverts[(vb+nv)*3], sizeof(float)*3*(ndv-nv)); - vbase += ndv-nv; - } - } - // Store triangles. - memcpy(navDTris, dtris, sizeof(unsigned char)*4*ndtris); - - *outData = data; - *outDataSize = dataSize; - - return true; -} |