diff options
| author | jackpoz <giacomopoz@gmail.com> | 2016-08-17 12:50:43 +0200 |
|---|---|---|
| committer | joschiwald <joschiwald.trinity@gmail.com> | 2017-02-12 15:41:19 +0100 |
| commit | e5ba8f1e4d771a0921b1be0dc1e66a2263b26a44 (patch) | |
| tree | 296d92398e9f0f2bf4d9ba87dd84e20b7a7a2b07 /dep/recastnavigation | |
| parent | a2acd445fe738ba4b4c8283d13ec8b6029ec9037 (diff) | |
Core/MMAPs: Update recast
Update recast to https://github.com/recastnavigation/recastnavigation/commit/64385e9ed0822427bca5814d03a3f4c4d7a6db9f
(cherry picked from commit 1d7013e0e2758b1468a488dd17e3f5c5ce5f265d)
# Conflicts:
# dep/PackageList.txt
Diffstat (limited to 'dep/recastnavigation')
26 files changed, 1329 insertions, 1083 deletions
diff --git a/dep/recastnavigation/Detour/Include/DetourAlloc.h b/dep/recastnavigation/Detour/Include/DetourAlloc.h index e814b62a716..f87b454acb6 100644 --- a/dep/recastnavigation/Detour/Include/DetourAlloc.h +++ b/dep/recastnavigation/Detour/Include/DetourAlloc.h @@ -19,6 +19,8 @@ #ifndef DETOURALLOCATOR_H #define DETOURALLOCATOR_H +#include <stddef.h> + /// Provides hint values to the memory allocator on how long the /// memory is expected to be used. enum dtAllocHint @@ -32,7 +34,7 @@ enum dtAllocHint // @param[in] rcAllocHint A hint to the allocator on how long the memory is expected to be in use. // @return A pointer to the beginning of the allocated memory block, or null if the allocation failed. /// @see dtAllocSetCustom -typedef void* (dtAllocFunc)(int size, dtAllocHint hint); +typedef void* (dtAllocFunc)(size_t size, dtAllocHint hint); /// A memory deallocation function. /// @param[in] ptr A pointer to a memory block previously allocated using #dtAllocFunc. @@ -49,7 +51,7 @@ void dtAllocSetCustom(dtAllocFunc *allocFunc, dtFreeFunc *freeFunc); /// @param[in] hint A hint to the allocator on how long the memory is expected to be in use. /// @return A pointer to the beginning of the allocated memory block, or null if the allocation failed. /// @see dtFree -void* dtAlloc(int size, dtAllocHint hint); +void* dtAlloc(size_t size, dtAllocHint hint); /// Deallocates a memory block. /// @param[in] ptr A pointer to a memory block previously allocated using #dtAlloc. diff --git a/dep/recastnavigation/Detour/Include/DetourCommon.h b/dep/recastnavigation/Detour/Include/DetourCommon.h index 2afba0d780b..739858cd9ad 100644 --- a/dep/recastnavigation/Detour/Include/DetourCommon.h +++ b/dep/recastnavigation/Detour/Include/DetourCommon.h @@ -20,6 +20,7 @@ #define DETOURCOMMON_H #include "DetourMath.h" +#include <stddef.h> /** @defgroup detour Detour @@ -482,6 +483,23 @@ inline void dtSwapEndian(float* v) void dtRandomPointInConvexPoly(const float* pts, const int npts, float* areas, const float s, const float t, float* out); +template<typename TypeToRetrieveAs> +TypeToRetrieveAs* dtGetThenAdvanceBufferPointer(const unsigned char*& buffer, const size_t distanceToAdvance) +{ + TypeToRetrieveAs* returnPointer = reinterpret_cast<TypeToRetrieveAs*>(buffer); + buffer += distanceToAdvance; + return returnPointer; +} + +template<typename TypeToRetrieveAs> +TypeToRetrieveAs* dtGetThenAdvanceBufferPointer(unsigned char*& buffer, const size_t distanceToAdvance) +{ + TypeToRetrieveAs* returnPointer = reinterpret_cast<TypeToRetrieveAs*>(buffer); + buffer += distanceToAdvance; + return returnPointer; +} + + /// @} #endif // DETOURCOMMON_H diff --git a/dep/recastnavigation/Detour/Include/DetourNavMesh.h b/dep/recastnavigation/Detour/Include/DetourNavMesh.h index 782ddbc2edd..f50f705a2c5 100644 --- a/dep/recastnavigation/Detour/Include/DetourNavMesh.h +++ b/dep/recastnavigation/Detour/Include/DetourNavMesh.h @@ -22,8 +22,15 @@ #include "DetourAlloc.h" #include "DetourStatus.h" - -// Edited by TC +// Undefine (or define in a build cofnig) the following line to use 64bit polyref. +// Generally not needed, useful for very large worlds. +// Note: tiles build using 32bit refs are not compatible with 64bit refs! +#define DT_POLYREF64 1 + +#ifdef DT_POLYREF64 +// TODO: figure out a multiplatform version of uint64_t +// - maybe: https://code.google.com/p/msinttypes/ +// - or: http://www.azillionmonkeys.com/qed/pstdint.h #if defined(WIN32) && !defined(__MINGW32__) /// Do not rename back to uint64. Otherwise mac complains about typedef redefinition typedef unsigned __int64 uint64_d; @@ -37,20 +44,29 @@ typedef unsigned __int64 uint64_d; /// Do not rename back to uint64. Otherwise mac complains about typedef redefinition typedef uint64_t uint64_d; #endif +#endif // Note: If you want to use 64-bit refs, change the types of both dtPolyRef & dtTileRef. // It is also recommended that you change dtHashRef() to a proper 64-bit hash. -// Edited by TC -// We cannot have over 31 bits for either tile nor poly -// without changing polyCount to use 64bits too. /// A handle to a polygon within a navigation mesh tile. /// @ingroup detour -typedef uint64_d dtPolyRef; // Edited by TC +#ifdef DT_POLYREF64 +static const unsigned int DT_SALT_BITS = 12; +static const unsigned int DT_TILE_BITS = 21; +static const unsigned int DT_POLY_BITS = 31; +typedef uint64_d dtPolyRef; +#else +typedef unsigned int dtPolyRef; +#endif /// A handle to a tile within a navigation mesh. /// @ingroup detour -typedef uint64_d dtTileRef; // Edited by TC +#ifdef DT_POLYREF64 +typedef uint64_d dtTileRef; +#else +typedef unsigned int dtTileRef; +#endif /// The maximum number of vertices per navigation polygon. /// @ingroup detour @@ -90,12 +106,6 @@ static const unsigned int DT_OFFMESH_CON_BIDIR = 1; /// @ingroup detour static const int DT_MAX_AREAS = 64; -static const int STATIC_SALT_BITS = 12; -static const int STATIC_TILE_BITS = 21; -static const int STATIC_POLY_BITS = 31; -// we cannot have over 31 bits for either tile nor poly -// without changing polyCount to use 64bits too. - /// Tile flags used for various functions and fields. /// For an example, see dtNavMesh::addTile(). enum dtTileFlags @@ -120,11 +130,10 @@ enum dtStraightPathOptions }; -/// Options for dtNavMeshQuery::findPath +/// Options for dtNavMeshQuery::initSlicedFindPath and updateSlicedFindPath enum dtFindPathOptions { - DT_FINDPATH_LOW_QUALITY_FAR = 0x01, ///< [provisional] trade quality for performance far from the origin. The idea is that by then a new query will be issued - DT_FINDPATH_ANY_ANGLE = 0x02, ///< use raycasts during pathfind to "shortcut" (raycast still consider costs) + DT_FINDPATH_ANY_ANGLE = 0x02, ///< use raycasts during pathfind to "shortcut" (raycast still consider costs) }; /// Options for dtNavMeshQuery::raycast @@ -148,7 +157,7 @@ enum dtPolyTypes }; -/// Defines a polyogn within a dtMeshTile object. +/// Defines a polygon within a dtMeshTile object. /// @ingroup detour struct dtPoly { @@ -303,6 +312,9 @@ struct dtMeshTile int dataSize; ///< Size of the tile data. int flags; ///< Tile flags. (See: #dtTileFlags) dtMeshTile* next; ///< The next free tile, or the next tile in the spatial grid. +private: + dtMeshTile(const dtMeshTile&); + dtMeshTile& operator=(const dtMeshTile&); }; /// Configuration parameters used to define multi-tile navigation meshes. @@ -513,7 +525,11 @@ public: /// @param[in] ip The index of the polygon within the tile. inline dtPolyRef encodePolyId(unsigned int salt, unsigned int it, unsigned int ip) const { +#ifdef DT_POLYREF64 + return ((dtPolyRef)salt << (DT_POLY_BITS+DT_TILE_BITS)) | ((dtPolyRef)it << DT_POLY_BITS) | (dtPolyRef)ip; +#else return ((dtPolyRef)salt << (m_polyBits+m_tileBits)) | ((dtPolyRef)it << m_polyBits) | (dtPolyRef)ip; +#endif } /// Decodes a standard polygon reference. @@ -525,12 +541,21 @@ public: /// @see #encodePolyId inline void decodePolyId(dtPolyRef ref, unsigned int& salt, unsigned int& it, unsigned int& ip) const { +#ifdef DT_POLYREF64 + const dtPolyRef saltMask = ((dtPolyRef)1<<DT_SALT_BITS)-1; + const dtPolyRef tileMask = ((dtPolyRef)1<<DT_TILE_BITS)-1; + const dtPolyRef polyMask = ((dtPolyRef)1<<DT_POLY_BITS)-1; + salt = (unsigned int)((ref >> (DT_POLY_BITS+DT_TILE_BITS)) & saltMask); + it = (unsigned int)((ref >> DT_POLY_BITS) & tileMask); + ip = (unsigned int)(ref & polyMask); +#else const dtPolyRef saltMask = ((dtPolyRef)1<<m_saltBits)-1; const dtPolyRef tileMask = ((dtPolyRef)1<<m_tileBits)-1; const dtPolyRef polyMask = ((dtPolyRef)1<<m_polyBits)-1; salt = (unsigned int)((ref >> (m_polyBits+m_tileBits)) & saltMask); it = (unsigned int)((ref >> m_polyBits) & tileMask); ip = (unsigned int)(ref & polyMask); +#endif } /// Extracts a tile's salt value from the specified polygon reference. @@ -539,8 +564,13 @@ public: /// @see #encodePolyId inline unsigned int decodePolyIdSalt(dtPolyRef ref) const { +#ifdef DT_POLYREF64 + const dtPolyRef saltMask = ((dtPolyRef)1<<DT_SALT_BITS)-1; + return (unsigned int)((ref >> (DT_POLY_BITS+DT_TILE_BITS)) & saltMask); +#else const dtPolyRef saltMask = ((dtPolyRef)1<<m_saltBits)-1; return (unsigned int)((ref >> (m_polyBits+m_tileBits)) & saltMask); +#endif } /// Extracts the tile's index from the specified polygon reference. @@ -549,8 +579,13 @@ public: /// @see #encodePolyId inline unsigned int decodePolyIdTile(dtPolyRef ref) const { +#ifdef DT_POLYREF64 + const dtPolyRef tileMask = ((dtPolyRef)1<<DT_TILE_BITS)-1; + return (unsigned int)((ref >> DT_POLY_BITS) & tileMask); +#else const dtPolyRef tileMask = ((dtPolyRef)1<<m_tileBits)-1; return (unsigned int)((ref >> m_polyBits) & tileMask); +#endif } /// Extracts the polygon's index (within its tile) from the specified polygon reference. @@ -559,13 +594,21 @@ public: /// @see #encodePolyId inline unsigned int decodePolyIdPoly(dtPolyRef ref) const { +#ifdef DT_POLYREF64 + const dtPolyRef polyMask = ((dtPolyRef)1<<DT_POLY_BITS)-1; + return (unsigned int)(ref & polyMask); +#else const dtPolyRef polyMask = ((dtPolyRef)1<<m_polyBits)-1; return (unsigned int)(ref & polyMask); +#endif } /// @} private: + // Explicitly disabled copy constructor and copy assignment operator. + dtNavMesh(const dtNavMesh&); + dtNavMesh& operator=(const dtNavMesh&); /// Returns pointer to tile in the tile array. dtMeshTile* getTile(int i); @@ -594,7 +637,7 @@ private: void connectExtOffMeshLinks(dtMeshTile* tile, dtMeshTile* target, int side); /// Removes external links at specified side. - void unconnectExtLinks(dtMeshTile* tile, dtMeshTile* target); + void unconnectLinks(dtMeshTile* tile, dtMeshTile* target); // TODO: These methods are duplicates from dtNavMeshQuery, but are needed for off-mesh connection finding. @@ -619,9 +662,11 @@ private: dtMeshTile* m_nextFree; ///< Freelist of tiles. dtMeshTile* m_tiles; ///< List of tiles. +#ifndef DT_POLYREF64 unsigned int m_saltBits; ///< Number of salt bits in the tile ID. unsigned int m_tileBits; ///< Number of tile bits in the tile ID. unsigned int m_polyBits; ///< Number of poly bits in the tile ID. +#endif }; /// Allocates a navigation mesh object using the Detour allocator. diff --git a/dep/recastnavigation/Detour/Include/DetourNavMeshBuilder.h b/dep/recastnavigation/Detour/Include/DetourNavMeshBuilder.h index c80d1717630..9425a7a7893 100644 --- a/dep/recastnavigation/Detour/Include/DetourNavMeshBuilder.h +++ b/dep/recastnavigation/Detour/Include/DetourNavMeshBuilder.h @@ -145,4 +145,5 @@ function. @see dtCreateNavMeshData -*/
\ No newline at end of file +*/ + diff --git a/dep/recastnavigation/Detour/Include/DetourNavMeshQuery.h b/dep/recastnavigation/Detour/Include/DetourNavMeshQuery.h index c7b360dcdc6..61541e83dfe 100644 --- a/dep/recastnavigation/Detour/Include/DetourNavMeshQuery.h +++ b/dep/recastnavigation/Detour/Include/DetourNavMeshQuery.h @@ -131,6 +131,9 @@ struct dtRaycastHit /// hitNormal The normal of the nearest wall hit. [(x, y, z)] float hitNormal[3]; + + /// The index of the edge on the final polygon where the wall was hit. + int hitEdgeIndex; /// Pointer to an array of reference ids of the visited polygons. [opt] dtPolyRef* path; @@ -145,7 +148,18 @@ struct dtRaycastHit float pathCost; }; +/// Provides custom polygon query behavior. +/// Used by dtNavMeshQuery::queryPolygons. +/// @ingroup detour +class dtPolyQuery +{ +public: + virtual ~dtPolyQuery() { } + /// Called for each batch of unique polygons touched by the search area in dtNavMeshQuery::queryPolygons. + /// This can be called multiple times for a single query. + virtual void process(const dtMeshTile* tile, dtPoly** polys, dtPolyRef* refs, int count) = 0; +}; /// Provides the ability to perform pathfinding related queries against /// a navigation mesh. @@ -158,7 +172,7 @@ public: /// Initializes the query object. /// @param[in] nav Pointer to the dtNavMesh object to use for all queries. - /// @param[in] maxNodes Maximum number of search nodes. [Limits: 0 < value <= 65536] + /// @param[in] maxNodes Maximum number of search nodes. [Limits: 0 < value <= 65535] /// @returns The status flags for the query. dtStatus init(const dtNavMesh* nav, const int maxNodes); @@ -179,7 +193,7 @@ public: const float* startPos, const float* endPos, const dtQueryFilter* filter, dtPolyRef* path, int* pathCount, const int maxPath) const; - + /// Finds the straight path from the start to the end position within the polygon corridor. /// @param[in] startPos Path start position. [(x, y, z)] /// @param[in] endPos Path end position. [(x, y, z)] @@ -282,6 +296,20 @@ public: dtPolyRef* resultRef, dtPolyRef* resultParent, float* resultCost, int* resultCount, const int maxResult) const; + /// Gets a path from the explored nodes in the previous search. + /// @param[in] endRef The reference id of the end polygon. + /// @param[out] path An ordered list of polygon references representing the path. (Start to end.) + /// [(polyRef) * @p pathCount] + /// @param[out] pathCount The number of polygons returned in the @p path array. + /// @param[in] maxPath The maximum number of polygons the @p path array can hold. [Limit: >= 0] + /// @returns The status flags. Returns DT_FAILURE | DT_INVALID_PARAM if any parameter is wrong, or if + /// @p endRef was not explored in the previous search. Returns DT_SUCCESS | DT_BUFFER_TOO_SMALL + /// if @p path cannot contain the entire path. In this case it is filled to capacity with a partial path. + /// Otherwise returns DT_SUCCESS. + /// @remarks The result of this function depends on the state of the query object. For that reason it should only + /// be used immediately after one of the two Dijkstra searches, findPolysAroundCircle or findPolysAroundShape. + dtStatus getPathFromDijkstraSearch(dtPolyRef endRef, dtPolyRef* path, int* pathCount, int maxPath) const; + /// @} /// @name Local Query Functions ///@{ @@ -309,6 +337,14 @@ public: const dtQueryFilter* filter, dtPolyRef* polys, int* polyCount, const int maxPolys) const; + /// Finds polygons that overlap the search box. + /// @param[in] center The center of the search box. [(x, y, z)] + /// @param[in] extents The search distance along each axis. [(x, y, z)] + /// @param[in] filter The polygon filter to apply to the query. + /// @param[in] query The query. Polygons found will be batched together and passed to this query. + dtStatus queryPolygons(const float* center, const float* extents, + const dtQueryFilter* filter, dtPolyQuery* query) const; + /// Finds the non-overlapping navigation polygons in the local neighbourhood around the center position. /// @param[in] startRef The reference id of the polygon where the search starts. /// @param[in] centerPos The center of the query circle. [(x, y, z)] @@ -472,13 +508,13 @@ public: /// @} private: + // Explicitly disabled copy constructor and copy assignment operator + dtNavMeshQuery(const dtNavMeshQuery&); + dtNavMeshQuery& operator=(const dtNavMeshQuery&); - /// Returns neighbour tile based on side. - dtMeshTile* getNeighbourTileAt(int x, int y, int side) const; - /// Queries polygons within a tile. - int queryPolygonsInTile(const dtMeshTile* tile, const float* qmin, const float* qmax, const dtQueryFilter* filter, - dtPolyRef* polys, const int maxPolys) const; + void queryPolygonsInTile(const dtMeshTile* tile, const float* qmin, const float* qmax, + const dtQueryFilter* filter, dtPolyQuery* query) const; /// Returns portal points between two polygons. dtStatus getPortalPoints(dtPolyRef from, dtPolyRef to, float* left, float* right, @@ -502,6 +538,9 @@ private: dtStatus appendPortals(const int startIdx, const int endIdx, const float* endPos, const dtPolyRef* path, float* straightPath, unsigned char* straightPathFlags, dtPolyRef* straightPathRefs, int* straightPathCount, const int maxStraightPath, const int options) const; + + // Gets the path leading to the specified end node. + dtStatus getPathToNode(struct dtNode* endNode, dtPolyRef* path, int* pathCount, int maxPath) const; const dtNavMesh* m_nav; ///< Pointer to navmesh data. diff --git a/dep/recastnavigation/Detour/Include/DetourNode.h b/dep/recastnavigation/Detour/Include/DetourNode.h index 6fefdc8e0f3..db097470800 100644 --- a/dep/recastnavigation/Detour/Include/DetourNode.h +++ b/dep/recastnavigation/Detour/Include/DetourNode.h @@ -31,28 +31,26 @@ enum dtNodeFlags typedef unsigned short dtNodeIndex; static const dtNodeIndex DT_NULL_IDX = (dtNodeIndex)~0; +static const int DT_NODE_PARENT_BITS = 24; +static const int DT_NODE_STATE_BITS = 2; struct dtNode { - float pos[3]; ///< Position of the node. - float cost; ///< Cost from previous node to current node. - float total; ///< Cost up to the node. - unsigned int pidx : 24; ///< Index to parent node. - unsigned int state : 2; ///< extra state information. A polyRef can have multiple nodes with different extra info. see DT_MAX_STATES_PER_NODE - unsigned int flags : 3; ///< Node flags. A combination of dtNodeFlags. - dtPolyRef id; ///< Polygon ref the node corresponds to. + float pos[3]; ///< Position of the node. + float cost; ///< Cost from previous node to current node. + float total; ///< Cost up to the node. + unsigned int pidx : DT_NODE_PARENT_BITS; ///< Index to parent node. + unsigned int state : DT_NODE_STATE_BITS; ///< extra state information. A polyRef can have multiple nodes with different extra info. see DT_MAX_STATES_PER_NODE + unsigned int flags : 3; ///< Node flags. A combination of dtNodeFlags. + dtPolyRef id; ///< Polygon ref the node corresponds to. }; - -static const int DT_MAX_STATES_PER_NODE = 4; // number of extra states per node. See dtNode::state - - +static const int DT_MAX_STATES_PER_NODE = 1 << DT_NODE_STATE_BITS; // number of extra states per node. See dtNode::state class dtNodePool { public: dtNodePool(int maxNodes, int hashSize); ~dtNodePool(); - inline void operator=(const dtNodePool&) {} void clear(); // Get a dtNode by ref and extra state information. If there is none then - allocate @@ -64,19 +62,19 @@ public: inline unsigned int getNodeIdx(const dtNode* node) const { if (!node) return 0; - return (unsigned int)(node - m_nodes)+1; + return (unsigned int)(node - m_nodes) + 1; } inline dtNode* getNodeAtIdx(unsigned int idx) { if (!idx) return 0; - return &m_nodes[idx-1]; + return &m_nodes[idx - 1]; } inline const dtNode* getNodeAtIdx(unsigned int idx) const { if (!idx) return 0; - return &m_nodes[idx-1]; + return &m_nodes[idx - 1]; } inline int getMemUsed() const @@ -95,6 +93,9 @@ public: inline int getNodeCount() const { return m_nodeCount; } private: + // Explicitly disabled copy constructor and copy assignment operator. + dtNodePool(const dtNodePool&); + dtNodePool& operator=(const dtNodePool&); dtNode* m_nodes; dtNodeIndex* m_first; @@ -109,17 +110,10 @@ class dtNodeQueue public: dtNodeQueue(int n); ~dtNodeQueue(); - inline void operator=(dtNodeQueue&) {} - inline void clear() - { - m_size = 0; - } + inline void clear() { m_size = 0; } - inline dtNode* top() - { - return m_heap[0]; - } + inline dtNode* top() { return m_heap[0]; } inline dtNode* pop() { @@ -152,12 +146,16 @@ public: inline int getMemUsed() const { return sizeof(*this) + - sizeof(dtNode*)*(m_capacity+1); + sizeof(dtNode*) * (m_capacity + 1); } inline int getCapacity() const { return m_capacity; } private: + // Explicitly disabled copy constructor and copy assignment operator. + dtNodeQueue(const dtNodeQueue&); + dtNodeQueue& operator=(const dtNodeQueue&); + void bubbleUp(int i, dtNode* node); void trickleDown(int i, dtNode* node); diff --git a/dep/recastnavigation/Detour/Source/DetourAlloc.cpp b/dep/recastnavigation/Detour/Source/DetourAlloc.cpp index 5f671df5bdb..d9ad1fc0139 100644 --- a/dep/recastnavigation/Detour/Source/DetourAlloc.cpp +++ b/dep/recastnavigation/Detour/Source/DetourAlloc.cpp @@ -19,7 +19,7 @@ #include <stdlib.h> #include "DetourAlloc.h" -static void *dtAllocDefault(int size, dtAllocHint) +static void *dtAllocDefault(size_t size, dtAllocHint) { return malloc(size); } @@ -38,7 +38,7 @@ void dtAllocSetCustom(dtAllocFunc *allocFunc, dtFreeFunc *freeFunc) sFreeFunc = freeFunc ? freeFunc : dtFreeDefault; } -void* dtAlloc(int size, dtAllocHint hint) +void* dtAlloc(size_t size, dtAllocHint hint) { return sAllocFunc(size, hint); } diff --git a/dep/recastnavigation/Detour/Source/DetourNavMesh.cpp b/dep/recastnavigation/Detour/Source/DetourNavMesh.cpp index e8a679bb5d1..f70fa04729a 100644 --- a/dep/recastnavigation/Detour/Source/DetourNavMesh.cpp +++ b/dep/recastnavigation/Detour/Source/DetourNavMesh.cpp @@ -193,11 +193,13 @@ dtNavMesh::dtNavMesh() : m_tileLutMask(0), m_posLookup(0), m_nextFree(0), - m_tiles(0), - m_saltBits(0), - m_tileBits(0), - m_polyBits(0) + m_tiles(0) { +#ifndef DT_POLYREF64 + m_saltBits = 0; + m_tileBits = 0; + m_polyBits = 0; +#endif memset(&m_params, 0, sizeof(dtNavMeshParams)); m_orig[0] = 0; m_orig[1] = 0; @@ -248,11 +250,17 @@ dtStatus dtNavMesh::init(const dtNavMeshParams* params) m_nextFree = &m_tiles[i]; } - // Edited by TC - m_tileBits = STATIC_TILE_BITS; - m_polyBits = STATIC_POLY_BITS; - m_saltBits = STATIC_SALT_BITS; - + // Init ID generator values. +#ifndef DT_POLYREF64 + m_tileBits = dtIlog2(dtNextPow2((unsigned int)params->maxTiles)); + m_polyBits = dtIlog2(dtNextPow2((unsigned int)params->maxPolys)); + // Only allow 31 salt bits, since the salt mask is calculated using 32bit uint and it will overflow. + m_saltBits = dtMin((unsigned int)31, 32 - m_tileBits - m_polyBits); + + if (m_saltBits < 10) + return DT_FAILURE | DT_INVALID_PARAM; +#endif + return DT_SUCCESS; } @@ -296,7 +304,7 @@ int dtNavMesh::findConnectingPolys(const float* va, const float* vb, if (!tile) return 0; float amin[2], amax[2]; - calcSlabEndPoints(va,vb, amin,amax, side); + calcSlabEndPoints(va, vb, amin, amax, side); const float apos = getSlabCoord(va, side); // Remove links pointing to 'side' and compact the links array. @@ -342,7 +350,7 @@ int dtNavMesh::findConnectingPolys(const float* va, const float* vb, return n; } -void dtNavMesh::unconnectExtLinks(dtMeshTile* tile, dtMeshTile* target) +void dtNavMesh::unconnectLinks(dtMeshTile* tile, dtMeshTile* target) { if (!tile || !target) return; @@ -355,10 +363,9 @@ void dtNavMesh::unconnectExtLinks(dtMeshTile* tile, dtMeshTile* target) unsigned int pj = DT_NULL_LINK; while (j != DT_NULL_LINK) { - if (tile->links[j].side != 0xff && - decodePolyIdTile(tile->links[j].ref) == targetNum) + if (decodePolyIdTile(tile->links[j].ref) == targetNum) { - // Revove link. + // Remove link. unsigned int nj = tile->links[j].next; if (pj == DT_NULL_LINK) poly->firstLink = nj; @@ -644,9 +651,9 @@ void dtNavMesh::closestPointOnPoly(dtPolyRef ref, const float* pos, float* close if (!dtDistancePtPolyEdgesSqr(pos, verts, nv, edged, edget)) { // Point is outside the polygon, dtClamp to nearest edge. - float dmin = FLT_MAX; - int imin = -1; - for (int i = 0; i < nv; ++i) + float dmin = edged[0]; + int imin = 0; + for (int i = 1; i < nv; ++i) { if (edged[i] < dmin) { @@ -830,6 +837,11 @@ int dtNavMesh::queryPolygonsInTile(const dtMeshTile* tile, const float* qmin, co /// tile will be restored to the same values they were before the tile was /// removed. /// +/// The nav mesh assumes exclusive access to the data passed and will make +/// changes to the dynamic portion of the data. For that reason the data +/// should not be reused in other nav meshes until the tile has been successfully +/// removed from this nav mesh. +/// /// @see dtCreateNavMeshData, #removeTile dtStatus dtNavMesh::addTile(unsigned char* data, int dataSize, int flags, dtTileRef lastRef, dtTileRef* result) @@ -905,14 +917,14 @@ dtStatus dtNavMesh::addTile(unsigned char* data, int dataSize, int flags, const int offMeshLinksSize = dtAlign4(sizeof(dtOffMeshConnection)*header->offMeshConCount); unsigned char* d = data + headerSize; - tile->verts = (float*)d; d += vertsSize; - tile->polys = (dtPoly*)d; d += polysSize; - tile->links = (dtLink*)d; d += linksSize; - tile->detailMeshes = (dtPolyDetail*)d; d += detailMeshesSize; - tile->detailVerts = (float*)d; d += detailVertsSize; - tile->detailTris = (unsigned char*)d; d += detailTrisSize; - tile->bvTree = (dtBVNode*)d; d += bvtreeSize; - tile->offMeshCons = (dtOffMeshConnection*)d; d += offMeshLinksSize; + tile->verts = dtGetThenAdvanceBufferPointer<float>(d, vertsSize); + tile->polys = dtGetThenAdvanceBufferPointer<dtPoly>(d, polysSize); + tile->links = dtGetThenAdvanceBufferPointer<dtLink>(d, linksSize); + tile->detailMeshes = dtGetThenAdvanceBufferPointer<dtPolyDetail>(d, detailMeshesSize); + tile->detailVerts = dtGetThenAdvanceBufferPointer<float>(d, detailVertsSize); + tile->detailTris = dtGetThenAdvanceBufferPointer<unsigned char>(d, detailTrisSize); + tile->bvTree = dtGetThenAdvanceBufferPointer<dtBVNode>(d, bvtreeSize); + tile->offMeshCons = dtGetThenAdvanceBufferPointer<dtOffMeshConnection>(d, offMeshLinksSize); // If there are no items in the bvtree, reset the tree pointer. if (!bvtreeSize) @@ -931,7 +943,10 @@ dtStatus dtNavMesh::addTile(unsigned char* data, int dataSize, int flags, tile->flags = flags; connectIntLinks(tile); + + // Base off-mesh connections to their starting polygons and connect connections inside the tile. baseOffMeshLinks(tile); + connectExtOffMeshLinks(tile, tile, -1); // Create connections with neighbour tiles. static const int MAX_NEIS = 32; @@ -942,11 +957,11 @@ dtStatus dtNavMesh::addTile(unsigned char* data, int dataSize, int flags, nneis = getTilesAt(header->x, header->y, neis, MAX_NEIS); for (int j = 0; j < nneis; ++j) { - if (neis[j] != tile) - { - connectExtLinks(tile, neis[j], -1); - connectExtLinks(neis[j], tile, -1); - } + if (neis[j] == tile) + continue; + + connectExtLinks(tile, neis[j], -1); + connectExtLinks(neis[j], tile, -1); connectExtOffMeshLinks(tile, neis[j], -1); connectExtOffMeshLinks(neis[j], tile, -1); } @@ -1184,25 +1199,24 @@ dtStatus dtNavMesh::removeTile(dtTileRef ref, unsigned char** data, int* dataSiz } // Remove connections to neighbour tiles. - // Create connections with neighbour tiles. static const int MAX_NEIS = 32; dtMeshTile* neis[MAX_NEIS]; int nneis; - // Connect with layers in current tile. + // Disconnect from other layers in current tile. nneis = getTilesAt(tile->header->x, tile->header->y, neis, MAX_NEIS); for (int j = 0; j < nneis; ++j) { if (neis[j] == tile) continue; - unconnectExtLinks(neis[j], tile); + unconnectLinks(neis[j], tile); } - // Connect with neighbour tiles. + // Disconnect from neighbour tiles. for (int i = 0; i < 8; ++i) { nneis = getNeighbourTilesAt(tile->header->x, tile->header->y, i, neis, MAX_NEIS); for (int j = 0; j < nneis; ++j) - unconnectExtLinks(neis[j], tile); + unconnectLinks(neis[j], tile); } // Reset tile. @@ -1234,7 +1248,11 @@ dtStatus dtNavMesh::removeTile(dtTileRef ref, unsigned char** data, int* dataSiz tile->offMeshCons = 0; // Update salt, salt should never be zero. +#ifdef DT_POLYREF64 + tile->salt = (tile->salt+1) & ((1<<DT_SALT_BITS)-1); +#else tile->salt = (tile->salt+1) & ((1<<m_saltBits)-1); +#endif if (tile->salt == 0) tile->salt++; @@ -1307,8 +1325,8 @@ dtStatus dtNavMesh::storeTileState(const dtMeshTile* tile, unsigned char* data, if (maxDataSize < sizeReq) return DT_FAILURE | DT_BUFFER_TOO_SMALL; - dtTileState* tileState = (dtTileState*)data; data += dtAlign4(sizeof(dtTileState)); - dtPolyState* polyStates = (dtPolyState*)data; data += dtAlign4(sizeof(dtPolyState) * tile->header->polyCount); + dtTileState* tileState = dtGetThenAdvanceBufferPointer<dtTileState>(data, dtAlign4(sizeof(dtTileState))); + dtPolyState* polyStates = dtGetThenAdvanceBufferPointer<dtPolyState>(data, dtAlign4(sizeof(dtPolyState) * tile->header->polyCount)); // Store tile state. tileState->magic = DT_NAVMESH_STATE_MAGIC; @@ -1339,8 +1357,8 @@ dtStatus dtNavMesh::restoreTileState(dtMeshTile* tile, const unsigned char* data if (maxDataSize < sizeReq) return DT_FAILURE | DT_INVALID_PARAM; - const dtTileState* tileState = (const dtTileState*)data; data += dtAlign4(sizeof(dtTileState)); - const dtPolyState* polyStates = (const dtPolyState*)data; data += dtAlign4(sizeof(dtPolyState) * tile->header->polyCount); + const dtTileState* tileState = dtGetThenAdvanceBufferPointer<const dtTileState>(data, dtAlign4(sizeof(dtTileState))); + const dtPolyState* polyStates = dtGetThenAdvanceBufferPointer<const dtPolyState>(data, dtAlign4(sizeof(dtPolyState) * tile->header->polyCount)); // Check that the restore is possible. if (tileState->magic != DT_NAVMESH_STATE_MAGIC) diff --git a/dep/recastnavigation/Detour/Source/DetourNavMeshBuilder.cpp b/dep/recastnavigation/Detour/Source/DetourNavMeshBuilder.cpp index 1bf271bed7a..965e6cdc5c5 100644 --- a/dep/recastnavigation/Detour/Source/DetourNavMeshBuilder.cpp +++ b/dep/recastnavigation/Detour/Source/DetourNavMeshBuilder.cpp @@ -106,7 +106,6 @@ inline int longestAxis(unsigned short x, unsigned short y, unsigned short z) if (z > maxVal) { axis = 2; - maxVal = z; } return axis; } @@ -421,15 +420,16 @@ bool dtCreateNavMeshData(dtNavMeshCreateParams* params, unsigned char** outData, memset(data, 0, dataSize); unsigned char* d = data; - dtMeshHeader* header = (dtMeshHeader*)d; d += headerSize; - float* navVerts = (float*)d; d += vertsSize; - dtPoly* navPolys = (dtPoly*)d; d += polysSize; - d += linksSize; - dtPolyDetail* navDMeshes = (dtPolyDetail*)d; d += detailMeshesSize; - float* navDVerts = (float*)d; d += detailVertsSize; - unsigned char* navDTris = (unsigned char*)d; d += detailTrisSize; - dtBVNode* navBvtree = (dtBVNode*)d; d += bvTreeSize; - dtOffMeshConnection* offMeshCons = (dtOffMeshConnection*)d; d += offMeshConsSize; + + dtMeshHeader* header = dtGetThenAdvanceBufferPointer<dtMeshHeader>(d, headerSize); + float* navVerts = dtGetThenAdvanceBufferPointer<float>(d, vertsSize); + dtPoly* navPolys = dtGetThenAdvanceBufferPointer<dtPoly>(d, polysSize); + d += linksSize; // Ignore links; just leave enough space for them. They'll be created on load. + dtPolyDetail* navDMeshes = dtGetThenAdvanceBufferPointer<dtPolyDetail>(d, detailMeshesSize); + float* navDVerts = dtGetThenAdvanceBufferPointer<float>(d, detailVertsSize); + unsigned char* navDTris = dtGetThenAdvanceBufferPointer<unsigned char>(d, detailTrisSize); + dtBVNode* navBvtree = dtGetThenAdvanceBufferPointer<dtBVNode>(d, bvTreeSize); + dtOffMeshConnection* offMeshCons = dtGetThenAdvanceBufferPointer<dtOffMeshConnection>(d, offMeshConsSize); // Store header @@ -705,14 +705,16 @@ bool dtNavMeshDataSwapEndian(unsigned char* data, const int /*dataSize*/) const int offMeshLinksSize = dtAlign4(sizeof(dtOffMeshConnection)*header->offMeshConCount); unsigned char* d = data + headerSize; - float* verts = (float*)d; d += vertsSize; - dtPoly* polys = (dtPoly*)d; d += polysSize; - /*dtLink* links = (dtLink*)d;*/ d += linksSize; - dtPolyDetail* detailMeshes = (dtPolyDetail*)d; d += detailMeshesSize; - float* detailVerts = (float*)d; d += detailVertsSize; - /*unsigned char* detailTris = (unsigned char*)d;*/ d += detailTrisSize; - dtBVNode* bvTree = (dtBVNode*)d; d += bvtreeSize; - dtOffMeshConnection* offMeshCons = (dtOffMeshConnection*)d; d += offMeshLinksSize; + float* verts = dtGetThenAdvanceBufferPointer<float>(d, vertsSize); + dtPoly* polys = dtGetThenAdvanceBufferPointer<dtPoly>(d, polysSize); + d += linksSize; // Ignore links; they technically should be endian-swapped but all their data is overwritten on load anyway. + //dtLink* links = dtGetThenAdvanceBufferPointer<dtLink>(d, linksSize); + dtPolyDetail* detailMeshes = dtGetThenAdvanceBufferPointer<dtPolyDetail>(d, detailMeshesSize); + float* detailVerts = dtGetThenAdvanceBufferPointer<float>(d, detailVertsSize); + d += detailTrisSize; // Ignore detail tris; single bytes can't be endian-swapped. + //unsigned char* detailTris = dtGetThenAdvanceBufferPointer<unsigned char>(d, detailTrisSize); + dtBVNode* bvTree = dtGetThenAdvanceBufferPointer<dtBVNode>(d, bvtreeSize); + dtOffMeshConnection* offMeshCons = dtGetThenAdvanceBufferPointer<dtOffMeshConnection>(d, offMeshLinksSize); // Vertices for (int i = 0; i < header->vertCount*3; ++i) diff --git a/dep/recastnavigation/Detour/Source/DetourNavMeshQuery.cpp b/dep/recastnavigation/Detour/Source/DetourNavMeshQuery.cpp index fbf3724e85b..a263106dc1c 100644 --- a/dep/recastnavigation/Detour/Source/DetourNavMeshQuery.cpp +++ b/dep/recastnavigation/Detour/Source/DetourNavMeshQuery.cpp @@ -100,7 +100,6 @@ inline float dtQueryFilter::getCost(const float* pa, const float* pb, } #endif -// Edited by TC static const float H_SCALE = 2.0f; // Search heuristic scale. @@ -166,6 +165,9 @@ dtNavMeshQuery::~dtNavMeshQuery() /// This function can be used multiple times. dtStatus dtNavMeshQuery::init(const dtNavMesh* nav, const int maxNodes) { + if (maxNodes > DT_NULL_IDX || maxNodes > (1 << DT_NODE_PARENT_BITS) - 1) + return DT_FAILURE | DT_INVALID_PARAM; + m_nav = nav; if (!m_nodePool || m_nodePool->getMaxNodes() < maxNodes) @@ -196,7 +198,6 @@ dtStatus dtNavMeshQuery::init(const dtNavMesh* nav, const int maxNodes) m_tinyNodePool->clear(); } - // TODO: check the open list size too. if (!m_openList || m_openList->getCapacity() < maxNodes) { if (m_openList) @@ -541,9 +542,9 @@ dtStatus dtNavMeshQuery::closestPointOnPoly(dtPolyRef ref, const float* pos, flo if (!dtDistancePtPolyEdgesSqr(pos, verts, nv, edged, edget)) { // Point is outside the polygon, dtClamp to nearest edge. - float dmin = FLT_MAX; - int imin = -1; - for (int i = 0; i < nv; ++i) + float dmin = edged[0]; + int imin = 0; + for (int i = 1; i < nv; ++i) { if (edged[i] < dmin) { @@ -627,9 +628,9 @@ dtStatus dtNavMeshQuery::closestPointOnPolyBoundary(dtPolyRef ref, const float* else { // Point is outside the polygon, dtClamp to nearest edge. - float dmin = FLT_MAX; - int imin = -1; - for (int i = 0; i < nv; ++i) + float dmin = edged[0]; + int imin = 0; + for (int i = 1; i < nv; ++i) { if (edged[i] < dmin) { @@ -698,78 +699,98 @@ dtStatus dtNavMeshQuery::getPolyHeight(dtPolyRef ref, const float* pos, float* h return DT_FAILURE | DT_INVALID_PARAM; } +class dtFindNearestPolyQuery : public dtPolyQuery +{ + const dtNavMeshQuery* m_query; + const float* m_center; + float m_nearestDistanceSqr; + dtPolyRef m_nearestRef; + float m_nearestPoint[3]; + +public: + dtFindNearestPolyQuery(const dtNavMeshQuery* query, const float* center) + : m_query(query), m_center(center), m_nearestDistanceSqr(FLT_MAX), m_nearestRef(0), m_nearestPoint() + { + } + + dtPolyRef nearestRef() const { return m_nearestRef; } + const float* nearestPoint() const { return m_nearestPoint; } + + void process(const dtMeshTile* tile, dtPoly** polys, dtPolyRef* refs, int count) + { + dtIgnoreUnused(polys); + + for (int i = 0; i < count; ++i) + { + dtPolyRef ref = refs[i]; + float closestPtPoly[3]; + float diff[3]; + bool posOverPoly = false; + float d; + m_query->closestPointOnPoly(ref, m_center, closestPtPoly, &posOverPoly); + + // If a point is directly over a polygon and closer than + // climb height, favor that instead of straight line nearest point. + dtVsub(diff, m_center, closestPtPoly); + if (posOverPoly) + { + d = dtAbs(diff[1]) - tile->header->walkableClimb; + d = d > 0 ? d*d : 0; + } + else + { + d = dtVlenSqr(diff); + } + + if (d < m_nearestDistanceSqr) + { + dtVcopy(m_nearestPoint, closestPtPoly); + + m_nearestDistanceSqr = d; + m_nearestRef = ref; + } + } + } +}; + /// @par /// /// @note If the search box does not intersect any polygons the search will /// return #DT_SUCCESS, but @p nearestRef will be zero. So if in doubt, check /// @p nearestRef before using @p nearestPt. /// -/// @warning This function is not suitable for large area searches. If the search -/// extents overlaps more than MAX_SEARCH (128) polygons it may return an invalid result. -/// dtStatus dtNavMeshQuery::findNearestPoly(const float* center, const float* extents, const dtQueryFilter* filter, dtPolyRef* nearestRef, float* nearestPt) const { dtAssert(m_nav); - *nearestRef = 0; - - // Get nearby polygons from proximity grid. - const int MAX_SEARCH = 128; - dtPolyRef polys[MAX_SEARCH]; - int polyCount = 0; - if (dtStatusFailed(queryPolygons(center, extents, filter, polys, &polyCount, MAX_SEARCH))) + if (!nearestRef) return DT_FAILURE | DT_INVALID_PARAM; - // Find nearest polygon amongst the nearby polygons. - dtPolyRef nearest = 0; - float nearestDistanceSqr = FLT_MAX; - for (int i = 0; i < polyCount; ++i) - { - dtPolyRef ref = polys[i]; - float closestPtPoly[3]; - float diff[3]; - bool posOverPoly = false; - float d = 0; - closestPointOnPoly(ref, center, closestPtPoly, &posOverPoly); - - // If a point is directly over a polygon and closer than - // climb height, favor that instead of straight line nearest point. - dtVsub(diff, center, closestPtPoly); - if (posOverPoly) - { - const dtMeshTile* tile = 0; - const dtPoly* poly = 0; - m_nav->getTileAndPolyByRefUnsafe(polys[i], &tile, &poly); - d = dtAbs(diff[1]) - tile->header->walkableClimb; - d = d > 0 ? d*d : 0; - } - else - { - d = dtVlenSqr(diff); - } - - if (d < nearestDistanceSqr) - { - if (nearestPt) - dtVcopy(nearestPt, closestPtPoly); - nearestDistanceSqr = d; - nearest = ref; - } - } - - if (nearestRef) - *nearestRef = nearest; + dtFindNearestPolyQuery query(this, center); + + dtStatus status = queryPolygons(center, extents, filter, &query); + if (dtStatusFailed(status)) + return status; + + *nearestRef = query.nearestRef(); + // Only override nearestPt if we actually found a poly so the nearest point + // is valid. + if (nearestPt && *nearestRef) + dtVcopy(nearestPt, query.nearestPoint()); return DT_SUCCESS; } -int dtNavMeshQuery::queryPolygonsInTile(const dtMeshTile* tile, const float* qmin, const float* qmax, - const dtQueryFilter* filter, - dtPolyRef* polys, const int maxPolys) const +void dtNavMeshQuery::queryPolygonsInTile(const dtMeshTile* tile, const float* qmin, const float* qmax, + const dtQueryFilter* filter, dtPolyQuery* query) const { dtAssert(m_nav); + static const int batchSize = 32; + dtPolyRef polyRefs[batchSize]; + dtPoly* polys[batchSize]; + int n = 0; if (tile->bvTree) { @@ -778,7 +799,7 @@ int dtNavMeshQuery::queryPolygonsInTile(const dtMeshTile* tile, const float* qmi const float* tbmin = tile->header->bmin; const float* tbmax = tile->header->bmax; const float qfac = tile->header->bvQuantFactor; - + // Calculate quantized box unsigned short bmin[3], bmax[3]; // dtClamp query box to world box. @@ -795,25 +816,34 @@ int dtNavMeshQuery::queryPolygonsInTile(const dtMeshTile* tile, const float* qmi bmax[0] = (unsigned short)(qfac * maxx + 1) | 1; bmax[1] = (unsigned short)(qfac * maxy + 1) | 1; bmax[2] = (unsigned short)(qfac * maxz + 1) | 1; - + // Traverse tree const dtPolyRef base = m_nav->getPolyRefBase(tile); - int n = 0; while (node < end) { const bool overlap = dtOverlapQuantBounds(bmin, bmax, node->bmin, node->bmax); const bool isLeafNode = node->i >= 0; - + if (isLeafNode && overlap) { dtPolyRef ref = base | (dtPolyRef)node->i; if (filter->passFilter(ref, tile, &tile->polys[node->i])) { - if (n < maxPolys) - polys[n++] = ref; + polyRefs[n] = ref; + polys[n] = &tile->polys[node->i]; + + if (n == batchSize - 1) + { + query->process(tile, polys, polyRefs, batchSize); + n = 0; + } + else + { + n++; + } } } - + if (overlap || isLeafNode) node++; else @@ -822,17 +852,14 @@ int dtNavMeshQuery::queryPolygonsInTile(const dtMeshTile* tile, const float* qmi node += escapeIndex; } } - - return n; } else { float bmin[3], bmax[3]; - int n = 0; const dtPolyRef base = m_nav->getPolyRefBase(tile); for (int i = 0; i < tile->header->polyCount; ++i) { - const dtPoly* p = &tile->polys[i]; + dtPoly* p = &tile->polys[i]; // Do not return off-mesh connection polygons. if (p->getType() == DT_POLYTYPE_OFFMESH_CONNECTION) continue; @@ -850,16 +877,63 @@ int dtNavMeshQuery::queryPolygonsInTile(const dtMeshTile* tile, const float* qmi dtVmin(bmin, v); dtVmax(bmax, v); } - if (dtOverlapBounds(qmin,qmax, bmin,bmax)) + if (dtOverlapBounds(qmin, qmax, bmin, bmax)) { - if (n < maxPolys) - polys[n++] = ref; + polyRefs[n] = ref; + polys[n] = p; + + if (n == batchSize - 1) + { + query->process(tile, polys, polyRefs, batchSize); + n = 0; + } + else + { + n++; + } } } - return n; } + + // Process the last polygons that didn't make a full batch. + if (n > 0) + query->process(tile, polys, polyRefs, n); } +class dtCollectPolysQuery : public dtPolyQuery +{ + dtPolyRef* m_polys; + const int m_maxPolys; + int m_numCollected; + bool m_overflow; + +public: + dtCollectPolysQuery(dtPolyRef* polys, const int maxPolys) + : m_polys(polys), m_maxPolys(maxPolys), m_numCollected(0), m_overflow(false) + { + } + + int numCollected() const { return m_numCollected; } + bool overflowed() const { return m_overflow; } + + void process(const dtMeshTile* tile, dtPoly** polys, dtPolyRef* refs, int count) + { + dtIgnoreUnused(tile); + dtIgnoreUnused(polys); + + int numLeft = m_maxPolys - m_numCollected; + int toCopy = count; + if (toCopy > numLeft) + { + m_overflow = true; + toCopy = numLeft; + } + + memcpy(m_polys + m_numCollected, refs, (size_t)toCopy * sizeof(dtPolyRef)); + m_numCollected += toCopy; + } +}; + /// @par /// /// If no polygons are found, the function will return #DT_SUCCESS with a @@ -873,8 +947,34 @@ dtStatus dtNavMeshQuery::queryPolygons(const float* center, const float* extents const dtQueryFilter* filter, dtPolyRef* polys, int* polyCount, const int maxPolys) const { + if (!polys || !polyCount || maxPolys < 0) + return DT_FAILURE | DT_INVALID_PARAM; + + dtCollectPolysQuery collector(polys, maxPolys); + + dtStatus status = queryPolygons(center, extents, filter, &collector); + if (dtStatusFailed(status)) + return status; + + *polyCount = collector.numCollected(); + return collector.overflowed() ? DT_SUCCESS | DT_BUFFER_TOO_SMALL : DT_SUCCESS; +} + +/// @par +/// +/// The query will be invoked with batches of polygons. Polygons passed +/// to the query have bounding boxes that overlap with the center and extents +/// passed to this function. The dtPolyQuery::process function is invoked multiple +/// times until all overlapping polygons have been processed. +/// +dtStatus dtNavMeshQuery::queryPolygons(const float* center, const float* extents, + const dtQueryFilter* filter, dtPolyQuery* query) const +{ dtAssert(m_nav); - + + if (!center || !extents || !filter || !query) + return DT_FAILURE | DT_INVALID_PARAM; + float bmin[3], bmax[3]; dtVsub(bmin, center, extents); dtVadd(bmax, center, extents); @@ -887,7 +987,6 @@ dtStatus dtNavMeshQuery::queryPolygons(const float* center, const float* extents static const int MAX_NEIS = 32; const dtMeshTile* neis[MAX_NEIS]; - int n = 0; for (int y = miny; y <= maxy; ++y) { for (int x = minx; x <= maxx; ++x) @@ -895,16 +994,10 @@ dtStatus dtNavMeshQuery::queryPolygons(const float* center, const float* extents const int nneis = m_nav->getTilesAt(x,y,neis,MAX_NEIS); for (int j = 0; j < nneis; ++j) { - n += queryPolygonsInTile(neis[j], bmin, bmax, filter, polys+n, maxPolys-n); - if (n >= maxPolys) - { - *polyCount = n; - return DT_SUCCESS | DT_BUFFER_TOO_SMALL; - } + queryPolygonsInTile(neis[j], bmin, bmax, filter, query); } } } - *polyCount = n; return DT_SUCCESS; } @@ -929,18 +1022,14 @@ dtStatus dtNavMeshQuery::findPath(dtPolyRef startRef, dtPolyRef endRef, dtAssert(m_nodePool); dtAssert(m_openList); - *pathCount = 0; - - if (!startRef || !endRef) - return DT_FAILURE | DT_INVALID_PARAM; - - if (!maxPath) - return DT_FAILURE | DT_INVALID_PARAM; + if (pathCount) + *pathCount = 0; // Validate input - if (!m_nav->isValidPolyRef(startRef) || !m_nav->isValidPolyRef(endRef)) + if (!m_nav->isValidPolyRef(startRef) || !m_nav->isValidPolyRef(endRef) || + !startPos || !endPos || !filter || maxPath <= 0 || !path || !pathCount) return DT_FAILURE | DT_INVALID_PARAM; - + if (startRef == endRef) { path[0] = startRef; @@ -963,7 +1052,7 @@ dtStatus dtNavMeshQuery::findPath(dtPolyRef startRef, dtPolyRef endRef, dtNode* lastBestNode = startNode; float lastBestNodeCost = startNode->total; - dtStatus status = DT_SUCCESS; + bool outOfNodes = false; while (!m_openList->empty()) { @@ -1021,7 +1110,7 @@ dtStatus dtNavMeshQuery::findPath(dtPolyRef startRef, dtPolyRef endRef, dtNode* neighbourNode = m_nodePool->getNode(neighbourRef, crossSide); if (!neighbourNode) { - status |= DT_OUT_OF_NODES; + outOfNodes = true; continue; } @@ -1100,42 +1189,59 @@ dtStatus dtNavMeshQuery::findPath(dtPolyRef startRef, dtPolyRef endRef, } } } - + + dtStatus status = getPathToNode(lastBestNode, path, pathCount, maxPath); + if (lastBestNode->id != endRef) status |= DT_PARTIAL_RESULT; + + if (outOfNodes) + status |= DT_OUT_OF_NODES; - // Reverse the path. - dtNode* prev = 0; - dtNode* node = lastBestNode; + return status; +} + +dtStatus dtNavMeshQuery::getPathToNode(dtNode* endNode, dtPolyRef* path, int* pathCount, int maxPath) const +{ + // Find the length of the entire path. + dtNode* curNode = endNode; + int length = 0; do { - dtNode* next = m_nodePool->getNodeAtIdx(node->pidx); - node->pidx = m_nodePool->getNodeIdx(prev); - prev = node; - node = next; + length++; + curNode = m_nodePool->getNodeAtIdx(curNode->pidx); + } while (curNode); + + // If the path cannot be fully stored then advance to the last node we will be able to store. + curNode = endNode; + int writeCount; + for (writeCount = length; writeCount > maxPath; writeCount--) + { + dtAssert(curNode); + + curNode = m_nodePool->getNodeAtIdx(curNode->pidx); } - while (node); - - // Store path - node = prev; - int n = 0; - do + + // Write path + for (int i = writeCount - 1; i >= 0; i--) { - path[n++] = node->id; - if (n >= maxPath) - { - status |= DT_BUFFER_TOO_SMALL; - break; - } - node = m_nodePool->getNodeAtIdx(node->pidx); + dtAssert(curNode); + + path[i] = curNode->id; + curNode = m_nodePool->getNodeAtIdx(curNode->pidx); } - while (node); - - *pathCount = n; - - return status; + + dtAssert(!curNode); + + *pathCount = dtMin(length, maxPath); + + if (length > maxPath) + return DT_SUCCESS | DT_BUFFER_TOO_SMALL; + + return DT_SUCCESS; } + /// @par /// /// @warning Calling any non-slice methods before calling finalizeSlicedFindPath() @@ -1628,10 +1734,17 @@ dtStatus dtNavMeshQuery::appendVertex(const float* pos, const unsigned char flag if (straightPathRefs) straightPathRefs[(*straightPathCount)] = ref; (*straightPathCount)++; - // If reached end of path or there is no space to append more vertices, return. - if (flags == DT_STRAIGHTPATH_END || (*straightPathCount) >= maxStraightPath) + + // If there is no space to append more vertices, return. + if ((*straightPathCount) >= maxStraightPath) + { + return DT_SUCCESS | DT_BUFFER_TOO_SMALL; + } + + // If reached end of path, return. + if (flags == DT_STRAIGHTPATH_END) { - return DT_SUCCESS | (((*straightPathCount) >= maxStraightPath) ? DT_BUFFER_TOO_SMALL : 0); + return DT_SUCCESS; } } return DT_IN_PROGRESS; @@ -1756,10 +1869,12 @@ dtStatus dtNavMeshQuery::findStraightPath(const float* startPos, const float* en for (int i = 0; i < pathSize; ++i) { float left[3], right[3]; - unsigned char fromType, toType; + unsigned char toType; if (i+1 < pathSize) { + unsigned char fromType; // fromType is ignored. + // Next portal. if (dtStatusFailed(getPortalPoints(path[i], path[i+1], left, right, fromType, toType))) { @@ -1775,12 +1890,14 @@ dtStatus dtNavMeshQuery::findStraightPath(const float* startPos, const float* en // Apeend portals along the current straight path segment. if (options & (DT_STRAIGHTPATH_AREA_CROSSINGS | DT_STRAIGHTPATH_ALL_CROSSINGS)) { - stat = appendPortals(apexIndex, i, closestEndPos, path, + // Ignore status return value as we're just about to return anyway. + appendPortals(apexIndex, i, closestEndPos, path, straightPath, straightPathFlags, straightPathRefs, straightPathCount, maxStraightPath, options); } - stat = appendVertex(closestEndPos, 0, path[i], + // Ignore status return value as we're just about to return anyway. + appendVertex(closestEndPos, 0, path[i], straightPath, straightPathFlags, straightPathRefs, straightPathCount, maxStraightPath); @@ -1801,7 +1918,7 @@ dtStatus dtNavMeshQuery::findStraightPath(const float* startPos, const float* en dtVcopy(left, closestEndPos); dtVcopy(right, closestEndPos); - fromType = toType = DT_POLYTYPE_GROUND; + toType = DT_POLYTYPE_GROUND; } // Right vertex. @@ -1918,7 +2035,8 @@ dtStatus dtNavMeshQuery::findStraightPath(const float* startPos, const float* en } } - stat = appendVertex(closestEndPos, DT_STRAIGHTPATH_END, 0, + // Ignore status return value as we're just about to return anyway. + appendVertex(closestEndPos, DT_STRAIGHTPATH_END, 0, straightPath, straightPathFlags, straightPathRefs, straightPathCount, maxStraightPath); @@ -2389,10 +2507,10 @@ dtStatus dtNavMeshQuery::raycast(dtPolyRef startRef, const float* startPos, cons const dtMeshTile* prevTile, *tile, *nextTile; const dtPoly* prevPoly, *poly, *nextPoly; - dtPolyRef curRef, nextRef; + dtPolyRef curRef; // The API input has been checked already, skip checking internal data. - nextRef = curRef = startRef; + curRef = startRef; tile = 0; poly = 0; m_nav->getTileAndPolyByRefUnsafe(curRef, &tile, &poly); @@ -2421,6 +2539,9 @@ dtStatus dtNavMeshQuery::raycast(dtPolyRef startRef, const float* startPos, cons hit->pathCount = n; return status; } + + hit->hitEdgeIndex = segMax; + // Keep track of furthest t so far. if (tmax > hit->t) hit->t = tmax; @@ -2444,7 +2565,7 @@ dtStatus dtNavMeshQuery::raycast(dtPolyRef startRef, const float* startPos, cons } // Follow neighbours. - nextRef = 0; + dtPolyRef nextRef = 0; for (unsigned int i = poly->firstLink; i != DT_NULL_LINK; i = tile->links[i].next) { @@ -2635,20 +2756,6 @@ dtStatus dtNavMeshQuery::findPolysAroundCircle(dtPolyRef startRef, const float* dtStatus status = DT_SUCCESS; int n = 0; - if (n < maxResult) - { - if (resultRef) - resultRef[n] = startNode->id; - if (resultParent) - resultParent[n] = 0; - if (resultCost) - resultCost[n] = 0; - ++n; - } - else - { - status |= DT_BUFFER_TOO_SMALL; - } const float radiusSqr = dtSqr(radius); @@ -2673,6 +2780,21 @@ dtStatus dtNavMeshQuery::findPolysAroundCircle(dtPolyRef startRef, const float* parentRef = m_nodePool->getNodeAtIdx(bestNode->pidx)->id; if (parentRef) m_nav->getTileAndPolyByRefUnsafe(parentRef, &parentTile, &parentPoly); + + if (n < maxResult) + { + if (resultRef) + resultRef[n] = bestRef; + if (resultParent) + resultParent[n] = parentRef; + if (resultCost) + resultCost[n] = bestNode->total; + ++n; + } + else + { + status |= DT_BUFFER_TOO_SMALL; + } for (unsigned int i = bestPoly->firstLink; i != DT_NULL_LINK; i = bestTile->links[i].next) { @@ -2716,14 +2838,19 @@ dtStatus dtNavMeshQuery::findPolysAroundCircle(dtPolyRef startRef, const float* if (neighbourNode->flags == 0) dtVlerp(neighbourNode->pos, va, vb, 0.5f); - const float total = bestNode->total + dtVdist(bestNode->pos, neighbourNode->pos); + float cost = filter->getCost( + bestNode->pos, neighbourNode->pos, + parentRef, parentTile, parentPoly, + bestRef, bestTile, bestPoly, + neighbourRef, neighbourTile, neighbourPoly); + + const float total = bestNode->total + cost; // The node is already in open list and the new result is worse, skip. if ((neighbourNode->flags & DT_NODE_OPEN) && total >= neighbourNode->total) continue; neighbourNode->id = neighbourRef; - neighbourNode->flags = (neighbourNode->flags & ~DT_NODE_CLOSED); neighbourNode->pidx = m_nodePool->getNodeIdx(bestNode); neighbourNode->total = total; @@ -2733,20 +2860,6 @@ dtStatus dtNavMeshQuery::findPolysAroundCircle(dtPolyRef startRef, const float* } else { - if (n < maxResult) - { - if (resultRef) - resultRef[n] = neighbourNode->id; - if (resultParent) - resultParent[n] = m_nodePool->getNodeAtIdx(neighbourNode->pidx)->id; - if (resultCost) - resultCost[n] = neighbourNode->total; - ++n; - } - else - { - status |= DT_BUFFER_TOO_SMALL; - } neighbourNode->flags = DT_NODE_OPEN; m_openList->push(neighbourNode); } @@ -2815,20 +2928,6 @@ dtStatus dtNavMeshQuery::findPolysAroundShape(dtPolyRef startRef, const float* v dtStatus status = DT_SUCCESS; int n = 0; - if (n < maxResult) - { - if (resultRef) - resultRef[n] = startNode->id; - if (resultParent) - resultParent[n] = 0; - if (resultCost) - resultCost[n] = 0; - ++n; - } - else - { - status |= DT_BUFFER_TOO_SMALL; - } while (!m_openList->empty()) { @@ -2851,6 +2950,22 @@ dtStatus dtNavMeshQuery::findPolysAroundShape(dtPolyRef startRef, const float* v parentRef = m_nodePool->getNodeAtIdx(bestNode->pidx)->id; if (parentRef) m_nav->getTileAndPolyByRefUnsafe(parentRef, &parentTile, &parentPoly); + + if (n < maxResult) + { + if (resultRef) + resultRef[n] = bestRef; + if (resultParent) + resultParent[n] = parentRef; + if (resultCost) + resultCost[n] = bestNode->total; + + ++n; + } + else + { + status |= DT_BUFFER_TOO_SMALL; + } for (unsigned int i = bestPoly->firstLink; i != DT_NULL_LINK; i = bestTile->links[i].next) { @@ -2896,14 +3011,19 @@ dtStatus dtNavMeshQuery::findPolysAroundShape(dtPolyRef startRef, const float* v if (neighbourNode->flags == 0) dtVlerp(neighbourNode->pos, va, vb, 0.5f); - const float total = bestNode->total + dtVdist(bestNode->pos, neighbourNode->pos); + float cost = filter->getCost( + bestNode->pos, neighbourNode->pos, + parentRef, parentTile, parentPoly, + bestRef, bestTile, bestPoly, + neighbourRef, neighbourTile, neighbourPoly); + + const float total = bestNode->total + cost; // The node is already in open list and the new result is worse, skip. if ((neighbourNode->flags & DT_NODE_OPEN) && total >= neighbourNode->total) continue; neighbourNode->id = neighbourRef; - neighbourNode->flags = (neighbourNode->flags & ~DT_NODE_CLOSED); neighbourNode->pidx = m_nodePool->getNodeIdx(bestNode); neighbourNode->total = total; @@ -2913,20 +3033,6 @@ dtStatus dtNavMeshQuery::findPolysAroundShape(dtPolyRef startRef, const float* v } else { - if (n < maxResult) - { - if (resultRef) - resultRef[n] = neighbourNode->id; - if (resultParent) - resultParent[n] = m_nodePool->getNodeAtIdx(neighbourNode->pidx)->id; - if (resultCost) - resultCost[n] = neighbourNode->total; - ++n; - } - else - { - status |= DT_BUFFER_TOO_SMALL; - } neighbourNode->flags = DT_NODE_OPEN; m_openList->push(neighbourNode); } @@ -2938,6 +3044,21 @@ dtStatus dtNavMeshQuery::findPolysAroundShape(dtPolyRef startRef, const float* v return status; } +dtStatus dtNavMeshQuery::getPathFromDijkstraSearch(dtPolyRef endRef, dtPolyRef* path, int* pathCount, int maxPath) const +{ + if (!m_nav->isValidPolyRef(endRef) || !path || !pathCount || maxPath < 0) + return DT_FAILURE | DT_INVALID_PARAM; + + *pathCount = 0; + + dtNode* endNode; + if (m_nodePool->findNodes(endRef, &endNode, 1) != 1 || + (endNode->flags & DT_NODE_CLOSED) == 0) + return DT_FAILURE | DT_INVALID_PARAM; + + return getPathToNode(endNode, path, pathCount, maxPath); +} + /// @par /// /// This method is optimized for a small search radius and small number of result diff --git a/dep/recastnavigation/Detour/Source/DetourNode.cpp b/dep/recastnavigation/Detour/Source/DetourNode.cpp index 1d1897708f4..48abbba6b5b 100644 --- a/dep/recastnavigation/Detour/Source/DetourNode.cpp +++ b/dep/recastnavigation/Detour/Source/DetourNode.cpp @@ -22,17 +22,30 @@ #include "DetourCommon.h" #include <string.h> +#ifdef DT_POLYREF64 +// From Thomas Wang, https://gist.github.com/badboy/6267743 inline unsigned int dtHashRef(dtPolyRef a) { - // Edited by TC - a = (~a) + (a << 18); - a = a ^ (a >> 31); - a = a * 21; - a = a ^ (a >> 11); - a = a + (a << 6); - a = a ^ (a >> 22); - return (unsigned int)a; + a = (~a) + (a << 18); // a = (a << 18) - a - 1; + a = a ^ (a >> 31); + a = a * 21; // a = (a + (a << 2)) + (a << 4); + a = a ^ (a >> 11); + a = a + (a << 6); + a = a ^ (a >> 22); + return (unsigned int)a; } +#else +inline unsigned int dtHashRef(dtPolyRef a) +{ + a += ~(a<<15); + a ^= (a>>10); + a += (a<<3); + a ^= (a>>6); + a += ~(a<<11); + a ^= (a>>16); + return (unsigned int)a; +} +#endif ////////////////////////////////////////////////////////////////////////////////////////// dtNodePool::dtNodePool(int maxNodes, int hashSize) : @@ -44,7 +57,9 @@ dtNodePool::dtNodePool(int maxNodes, int hashSize) : m_nodeCount(0) { dtAssert(dtNextPow2(m_hashSize) == (unsigned int)m_hashSize); - dtAssert(m_maxNodes > 0); + // pidx is special as 0 means "none" and 1 is the first node. For that reason + // we have 1 fewer nodes available than the number of values it can contain. + dtAssert(m_maxNodes > 0 && m_maxNodes <= DT_NULL_IDX && m_maxNodes <= (1 << DT_NODE_PARENT_BITS) - 1); m_nodes = (dtNode*)dtAlloc(sizeof(dtNode)*m_maxNodes, DT_ALLOC_PERM); m_next = (dtNodeIndex*)dtAlloc(sizeof(dtNodeIndex)*m_maxNodes, DT_ALLOC_PERM); diff --git a/dep/recastnavigation/README.md b/dep/recastnavigation/README.md new file mode 100644 index 00000000000..7db7996366d --- /dev/null +++ b/dep/recastnavigation/README.md @@ -0,0 +1,89 @@ + +Recast & Detour +=============== + +[](https://travis-ci.org/recastnavigation/recastnavigation) +[](https://ci.appveyor.com/project/recastnavigation/recastnavigation/branch/master) + +[](http://www.issuestats.com/github/recastnavigation/recastnavigation) +[](http://www.issuestats.com/github/recastnavigation/recastnavigation) + + + +## Recast + +Recast is state of the art navigation mesh construction toolset for games. + +* It is automatic, which means that you can throw any level geometry at it and you will get robust mesh out +* It is fast which means swift turnaround times for level designers +* It is open source so it comes with full source and you can customize it to your heart's content. + +The Recast process starts with constructing a voxel mold from a level geometry +and then casting a navigation mesh over it. The process consists of three steps, +building the voxel mold, partitioning the mold into simple regions, peeling off +the regions as simple polygons. + +1. The voxel mold is build from the input triangle mesh by rasterizing the triangles into a multi-layer heightfield. Some simple filters are then applied to the mold to prune out locations where the character would not be able to move. +2. The walkable areas described by the mold are divided into simple overlayed 2D regions. The resulting regions have only one non-overlapping contour, which simplifies the final step of the process tremendously. +3. The navigation polygons are peeled off from the regions by first tracing the boundaries and then simplifying them. The resulting polygons are finally converted to convex polygons which makes them perfect for pathfinding and spatial reasoning about the level. + + +## Detour + +Recast is accompanied with Detour, path-finding and spatial reasoning toolkit. You can use any navigation mesh with Detour, but of course the data generated with Recast fits perfectly. + +Detour offers simple static navigation mesh which is suitable for many simple cases, as well as tiled navigation mesh which allows you to plug in and out pieces of the mesh. The tiled mesh allows you to create systems where you stream new navigation data in and out as the player progresses the level, or you may regenerate tiles as the world changes. + + +## Recast Demo + +You can find a comprehensive demo project in RecastDemo folder. It is a kitchen sink demo containing all the functionality of the library. If you are new to Recast & Detour, check out [Sample_SoloMesh.cpp](/RecastDemo/Source/Sample_SoloMesh.cpp) to get started with building navmeshes and [NavMeshTesterTool.cpp](/RecastDemo/Source/NavMeshTesterTool.cpp) to see how Detour can be used to find paths. + +### Building RecastDemo + +RecastDemo uses [premake5](http://premake.github.io/) to build platform specific projects. Download it and make sure it's available on your path, or specify the path to it. + +#### Linux + +- Install SDl2 and its dependencies according to your distro's guidelines. +- run `premake5 gmake` from the `RecastDemo` folder. +- `cd Build/gmake` then `make` +- Run `RecastDemo\Bin\RecastDemo` + +#### OSX + +- Grab the latest SDL2 development library dmg from [here](https://www.libsdl.org/download-2.0.php) and place `SDL2.framework` in `/Library/Frameworks/` +- Navigate to the `RecastDemo` folder and run `premake5 xcode4` +- Open `Build/xcode4/recastnavigation.xcworkspace` +- Select the "RecastDemo" project in the left pane, go to the "BuildPhases" tab and expand "Link Binary With Libraries" +- Remove the existing entry for SDL2 (it should have a white box icon) and re-add it by hitting the plus, selecting "Add Other", and selecting `/Library/Frameworks/SDL2.framework`. It should now have a suitcase icon. +- Set the RecastDemo project as the target and build. + +#### Windows + +- Grab the latest SDL2 development library release from [here](https://www.libsdl.org/download-2.0.php) and unzip it `RecastDemo\Contrib`. Rename the SDL folder such that the path `RecastDemo\Contrib\SDL\lib\x86` is valid. +- Run `"premake5" vs2015` from the `RecastDemo` folder +- Open the solution, build, and run. + +### Running Unit tests + +- Follow the instructions to build RecastDemo above. Premake should generate another build target called "Tests". +- Build the "Tests" project. This will generate an executable named "Tests" in `RecastDemo/Bin/` +- Run the "Tests" executable. It will execute all the unit tests, indicate those that failed, and display a count of those that succeeded. + +## Integrating with your own project + +It is recommended to add the source directories `DebugUtils`, `Detour`, `DetourCrowd`, `DetourTileCache`, and `Recast` into your own project depending on which parts of the project you need. For example your level building tool could include `DebugUtils`, `Recast`, and `Detour`, and your game runtime could just include `Detour`. + +## Contributing + +See the [Contributing document](CONTRIBUTING.md) for guidelines for making contributions. + +## Discuss + +- Discuss Recast & Detour: http://groups.google.com/group/recastnavigation +- Development blog: http://digestingduck.blogspot.com/ + +## License + +Recast & Detour is licensed under ZLib license, see License.txt for more information. diff --git a/dep/recastnavigation/Readme.txt b/dep/recastnavigation/Readme.txt deleted file mode 100644 index 1383b01d582..00000000000 --- a/dep/recastnavigation/Readme.txt +++ /dev/null @@ -1,46 +0,0 @@ - -Recast & Detour Version 1.4 - - -Recast - -Recast is state of the art navigation mesh construction toolset for games. - - * It is automatic, which means that you can throw any level geometry - at it and you will get robust mesh out - * It is fast which means swift turnaround times for level designers - * It is open source so it comes with full source and you can - customize it to your hearts content. - -The Recast process starts with constructing a voxel mold from a level geometry -and then casting a navigation mesh over it. The process consists of three steps, -building the voxel mold, partitioning the mold into simple regions, peeling off -the regions as simple polygons. - - 1. The voxel mold is build from the input triangle mesh by rasterizing - the triangles into a multi-layer heightfield. Some simple filters are - then applied to the mold to prune out locations where the character - would not be able to move. - 2. The walkable areas described by the mold are divided into simple - overlayed 2D regions. The resulting regions have only one non-overlapping - contour, which simplifies the final step of the process tremendously. - 3. The navigation polygons are peeled off from the regions by first tracing - the boundaries and then simplifying them. The resulting polygons are - finally converted to convex polygons which makes them perfect for - pathfinding and spatial reasoning about the level. - -The toolset code is located in the Recast folder and demo application using the Recast -toolset is located in the RecastDemo folder. - - -Detour - -Recast is accompanied with Detour, path-finding and spatial reasoning toolkit. You can use any navigation mesh with Detour, but of course the data generated with Recast fits perfectly. - -Detour offers simple static navigation mesh which is suitable for many simple cases, as well as tiled navigation mesh which allows you to plug in and out pieces of the mesh. The tiled mesh allows to create systems where you stream new navigation data in and out as the player progresses the level, or you may regenerate tiles as the world changes. - - -Latest code available at https://github.com/memononen/recastnavigation - -Mikko Mononen -memon@inside.org diff --git a/dep/recastnavigation/Recast/Include/Recast.h b/dep/recastnavigation/Recast/Include/Recast.h index d3e9219a9f6..79d77e4a9af 100644 --- a/dep/recastnavigation/Recast/Include/Recast.h +++ b/dep/recastnavigation/Recast/Include/Recast.h @@ -127,7 +127,7 @@ public: inline void resetTimers() { if (m_timerEnabled) doResetTimers(); } /// Starts the specified performance timer. - /// @param label The category of timer. + /// @param label The category of the timer. inline void startTimer(const rcTimerLabel label) { if (m_timerEnabled) doStartTimer(label); } /// Stops the specified performance timer. @@ -173,6 +173,26 @@ protected: bool m_timerEnabled; }; +/// A helper to first start a timer and then stop it when this helper goes out of scope. +/// @see rcContext +class rcScopedTimer +{ +public: + /// Constructs an instance and starts the timer. + /// @param[in] ctx The context to use. + /// @param[in] label The category of the timer. + inline rcScopedTimer(rcContext* ctx, const rcTimerLabel label) : m_ctx(ctx), m_label(label) { m_ctx->startTimer(m_label); } + inline ~rcScopedTimer() { m_ctx->stopTimer(m_label); } + +private: + // Explicitly disabled copy constructor and copy assignment operator. + rcScopedTimer(const rcScopedTimer&); + rcScopedTimer& operator=(const rcScopedTimer&); + + rcContext* const m_ctx; + const rcTimerLabel m_label; +}; + /// Specifies a configuration to use when performing Recast builds. /// @ingroup recast struct rcConfig @@ -243,9 +263,9 @@ struct rcConfig }; /// Defines the number of bits allocated to rcSpan::smin and rcSpan::smax. -static const int RC_SPAN_HEIGHT_BITS = 16; // EDITED BY TC +static const int RC_SPAN_HEIGHT_BITS = 16; /// Defines the maximum value for rcSpan::smin and rcSpan::smax. -static const int RC_SPAN_MAX_HEIGHT = (1<<RC_SPAN_HEIGHT_BITS)-1; +static const int RC_SPAN_MAX_HEIGHT = (1 << RC_SPAN_HEIGHT_BITS) - 1; /// The number of spans allocated per span spool. /// @see rcSpanPool @@ -255,10 +275,10 @@ static const int RC_SPANS_PER_POOL = 2048; /// @see rcHeightfield struct rcSpan { - unsigned int smin : 16; ///< The lower limit of the span. [Limit: < #smax] - unsigned int smax : 16; ///< The upper limit of the span. [Limit: <= #RC_SPAN_MAX_HEIGHT] - unsigned char area; ///< The area id assigned to the span. - rcSpan* next; ///< The next span higher up in column. + unsigned int smin : RC_SPAN_HEIGHT_BITS; ///< The lower limit of the span. [Limit: < #smax] + unsigned int smax : RC_SPAN_HEIGHT_BITS; ///< The upper limit of the span. [Limit: <= #RC_SPAN_MAX_HEIGHT] + unsigned char area; ///< The area id assigned to the span. + rcSpan* next; ///< The next span higher up in column. }; /// A memory pool used for quick allocation of spans within a heightfield. @@ -273,6 +293,9 @@ struct rcSpanPool /// @ingroup recast struct rcHeightfield { + rcHeightfield(); + ~rcHeightfield(); + int width; ///< The width of the heightfield. (Along the x-axis in cell units.) int height; ///< The height of the heightfield. (Along the z-axis in cell units.) float bmin[3]; ///< The minimum bounds in world space. [(x, y, z)] @@ -282,6 +305,11 @@ struct rcHeightfield rcSpan** spans; ///< Heightfield of spans (width*height). rcSpanPool* pools; ///< Linked list of span pools. rcSpan* freelist; ///< The next free span. + +private: + // Explicitly-disabled copy constructor and copy assignment operator. + rcHeightfield(const rcHeightfield&); + rcHeightfield& operator=(const rcHeightfield&); }; /// Provides information on the content of a cell column in a compact heightfield. @@ -376,6 +404,7 @@ struct rcContourSet int width; ///< The width of the set. (Along the x-axis in cell units.) int height; ///< The height of the set. (Along the z-axis in cell units.) int borderSize; ///< The AABB border size used to generate the source data from which the contours were derived. + float maxError; ///< The max edge error that this contour set was simplified with. }; /// Represents a polygon mesh suitable for use in building a navigation mesh. @@ -396,6 +425,7 @@ struct rcPolyMesh float cs; ///< The size of each cell. (On the xz-plane.) float ch; ///< The height of each cell. (The minimum increment along the y-axis.) int borderSize; ///< The AABB border size used to generate the source data from which the mesh was derived. + float maxEdgeError; ///< The max error of the polygon edges in the mesh. }; /// Contains triangle meshes that represent detailed height data associated @@ -497,6 +527,14 @@ void rcFreePolyMeshDetail(rcPolyMeshDetail* dmesh); /// @see rcCompactSpan::reg static const unsigned short RC_BORDER_REG = 0x8000; +/// Polygon touches multiple regions. +/// If a polygon has this region ID it was merged with or created +/// from polygons of different regions during the polymesh +/// build step that removes redundant border vertices. +/// (Used during the polymesh and detail polymesh build processes) +/// @see rcPolyMesh::regs +static const unsigned short RC_MULTIPLE_REGS = 0; + /// Border vertex flag. /// If a region ID has this bit set, then the associated element lies on /// a tile border. If a contour vertex's region ID has this bit set, the @@ -747,6 +785,7 @@ void rcCalcGridSize(const float* bmin, const float* bmax, float cs, int* w, int* /// @param[in] bmax The maximum bounds of the field's AABB. [(x, y, z)] [Units: wu] /// @param[in] cs The xz-plane cell size to use for the field. [Limit: > 0] [Units: wu] /// @param[in] ch The y-axis cell size to use for field. [Limit: > 0] [Units: wu] +/// @returns True if the operation completed successfully. bool rcCreateHeightfield(rcContext* ctx, rcHeightfield& hf, int width, int height, const float* bmin, const float* bmax, float cs, float ch); @@ -790,7 +829,8 @@ void rcClearUnwalkableTriangles(rcContext* ctx, const float walkableSlopeAngle, /// @param[in] smax The maximum height of the span. [Limit: <= #RC_SPAN_MAX_HEIGHT] [Units: vx] /// @param[in] area The area id of the span. [Limit: <= #RC_WALKABLE_AREA) /// @param[in] flagMergeThr The merge theshold. [Limit: >= 0] [Units: vx] -void rcAddSpan(rcContext* ctx, rcHeightfield& hf, const int x, const int y, +/// @returns True if the operation completed successfully. +bool rcAddSpan(rcContext* ctx, rcHeightfield& hf, const int x, const int y, const unsigned short smin, const unsigned short smax, const unsigned char area, const int flagMergeThr); @@ -804,7 +844,8 @@ void rcAddSpan(rcContext* ctx, rcHeightfield& hf, const int x, const int y, /// @param[in,out] solid An initialized heightfield. /// @param[in] flagMergeThr The distance where the walkable flag is favored over the non-walkable flag. /// [Limit: >= 0] [Units: vx] -void rcRasterizeTriangle(rcContext* ctx, const float* v0, const float* v1, const float* v2, +/// @returns True if the operation completed successfully. +bool rcRasterizeTriangle(rcContext* ctx, const float* v0, const float* v1, const float* v2, const unsigned char area, rcHeightfield& solid, const int flagMergeThr = 1); @@ -819,7 +860,8 @@ void rcRasterizeTriangle(rcContext* ctx, const float* v0, const float* v1, const /// @param[in,out] solid An initialized heightfield. /// @param[in] flagMergeThr The distance where the walkable flag is favored over the non-walkable flag. /// [Limit: >= 0] [Units: vx] -void rcRasterizeTriangles(rcContext* ctx, const float* verts, const int nv, +/// @returns True if the operation completed successfully. +bool rcRasterizeTriangles(rcContext* ctx, const float* verts, const int nv, const int* tris, const unsigned char* areas, const int nt, rcHeightfield& solid, const int flagMergeThr = 1); @@ -834,7 +876,8 @@ void rcRasterizeTriangles(rcContext* ctx, const float* verts, const int nv, /// @param[in,out] solid An initialized heightfield. /// @param[in] flagMergeThr The distance where the walkable flag is favored over the non-walkable flag. /// [Limit: >= 0] [Units: vx] -void rcRasterizeTriangles(rcContext* ctx, const float* verts, const int nv, +/// @returns True if the operation completed successfully. +bool rcRasterizeTriangles(rcContext* ctx, const float* verts, const int nv, const unsigned short* tris, const unsigned char* areas, const int nt, rcHeightfield& solid, const int flagMergeThr = 1); @@ -847,10 +890,11 @@ void rcRasterizeTriangles(rcContext* ctx, const float* verts, const int nv, /// @param[in,out] solid An initialized heightfield. /// @param[in] flagMergeThr The distance where the walkable flag is favored over the non-walkable flag. /// [Limit: >= 0] [Units: vx] -void rcRasterizeTriangles(rcContext* ctx, const float* verts, const unsigned char* areas, const int nt, +/// @returns True if the operation completed successfully. +bool rcRasterizeTriangles(rcContext* ctx, const float* verts, const unsigned char* areas, const int nt, rcHeightfield& solid, const int flagMergeThr = 1); -/// Marks non-walkable spans as walkable if their maximum is within @p walkableClimp of a walkable neihbor. +/// Marks non-walkable spans as walkable if their maximum is within @p walkableClimp of a walkable neighbor. /// @ingroup recast /// @param[in,out] ctx The build context to use during the operation. /// @param[in] walkableClimb Maximum ledge height that is considered to still be traversable. @@ -1037,7 +1081,7 @@ inline int rcGetCon(const rcCompactSpan& s, int dir) /// in the direction. inline int rcGetDirOffsetX(int dir) { - const int offset[4] = { -1, 0, 1, 0, }; + static const int offset[4] = { -1, 0, 1, 0, }; return offset[dir&0x03]; } @@ -1047,10 +1091,20 @@ inline int rcGetDirOffsetX(int dir) /// in the direction. inline int rcGetDirOffsetY(int dir) { - const int offset[4] = { 0, 1, 0, -1 }; + static const int offset[4] = { 0, 1, 0, -1 }; return offset[dir&0x03]; } +/// Gets the direction for the specified offset. One of x and y should be 0. +/// @param[in] x The x offset. [Limits: -1 <= value <= 1] +/// @param[in] y The y offset. [Limits: -1 <= value <= 1] +/// @return The direction that represents the offset. +inline int rcGetDirForOffset(int x, int y) +{ + static const int dirs[5] = { 3, 0, -1, 2, 1 }; + return dirs[((y+1)<<1)+x]; +} + /// @} /// @name Layer, Contour, Polymesh, and Detail Mesh Functions /// @see rcHeightfieldLayer, rcContourSet, rcPolyMesh, rcPolyMeshDetail diff --git a/dep/recastnavigation/Recast/Include/RecastAlloc.h b/dep/recastnavigation/Recast/Include/RecastAlloc.h index 438be9ea56b..3cdd450d42d 100644 --- a/dep/recastnavigation/Recast/Include/RecastAlloc.h +++ b/dep/recastnavigation/Recast/Include/RecastAlloc.h @@ -19,6 +19,8 @@ #ifndef RECASTALLOC_H #define RECASTALLOC_H +#include <stddef.h> + /// Provides hint values to the memory allocator on how long the /// memory is expected to be used. enum rcAllocHint @@ -32,7 +34,7 @@ enum rcAllocHint // @param[in] rcAllocHint A hint to the allocator on how long the memory is expected to be in use. // @return A pointer to the beginning of the allocated memory block, or null if the allocation failed. /// @see rcAllocSetCustom -typedef void* (rcAllocFunc)(int size, rcAllocHint hint); +typedef void* (rcAllocFunc)(size_t size, rcAllocHint hint); /// A memory deallocation function. /// @param[in] ptr A pointer to a memory block previously allocated using #rcAllocFunc. @@ -49,7 +51,7 @@ void rcAllocSetCustom(rcAllocFunc *allocFunc, rcFreeFunc *freeFunc); /// @param[in] hint A hint to the allocator on how long the memory is expected to be in use. /// @return A pointer to the beginning of the allocated memory block, or null if the allocation failed. /// @see rcFree -void* rcAlloc(int size, rcAllocHint hint); +void* rcAlloc(size_t size, rcAllocHint hint); /// Deallocates a memory block. /// @param[in] ptr A pointer to a memory block previously allocated using #rcAlloc. @@ -62,42 +64,58 @@ class rcIntArray { int* m_data; int m_size, m_cap; - inline rcIntArray(const rcIntArray&); - inline rcIntArray& operator=(const rcIntArray&); -public: + void doResize(int n); + + // Explicitly disabled copy constructor and copy assignment operator. + rcIntArray(const rcIntArray&); + rcIntArray& operator=(const rcIntArray&); + +public: /// Constructs an instance with an initial array size of zero. - inline rcIntArray() : m_data(0), m_size(0), m_cap(0) {} + rcIntArray() : m_data(0), m_size(0), m_cap(0) {} /// Constructs an instance initialized to the specified size. /// @param[in] n The initial size of the integer array. - inline rcIntArray(int n) : m_data(0), m_size(0), m_cap(0) { resize(n); } - inline ~rcIntArray() { rcFree(m_data); } + rcIntArray(int n) : m_data(0), m_size(0), m_cap(0) { resize(n); } + ~rcIntArray() { rcFree(m_data); } /// Specifies the new size of the integer array. /// @param[in] n The new size of the integer array. - void resize(int n); + void resize(int n) + { + if (n > m_cap) + doResize(n); + + m_size = n; + } /// Push the specified integer onto the end of the array and increases the size by one. /// @param[in] item The new value. - inline void push(int item) { resize(m_size+1); m_data[m_size-1] = item; } + void push(int item) { resize(m_size+1); m_data[m_size-1] = item; } /// Returns the value at the end of the array and reduces the size by one. /// @return The value at the end of the array. - inline int pop() { if (m_size > 0) m_size--; return m_data[m_size]; } + int pop() + { + if (m_size > 0) + m_size--; + + return m_data[m_size]; + } /// The value at the specified array index. /// @warning Does not provide overflow protection. /// @param[in] i The index of the value. - inline const int& operator[](int i) const { return m_data[i]; } + const int& operator[](int i) const { return m_data[i]; } /// The value at the specified array index. /// @warning Does not provide overflow protection. /// @param[in] i The index of the value. - inline int& operator[](int i) { return m_data[i]; } + int& operator[](int i) { return m_data[i]; } /// The current size of the integer array. - inline int size() const { return m_size; } + int size() const { return m_size; } }; /// A simple helper class used to delete an array when it goes out of scope. @@ -105,7 +123,6 @@ public: template<class T> class rcScopedDelete { T* ptr; - inline T* operator=(T* p); public: /// Constructs an instance with a null pointer. @@ -119,6 +136,11 @@ public: /// The root array pointer. /// @return The root array pointer. inline operator T*() { return ptr; } + +private: + // Explicitly disabled copy constructor and copy assignment operator. + rcScopedDelete(const rcScopedDelete&); + rcScopedDelete& operator=(const rcScopedDelete&); }; #endif diff --git a/dep/recastnavigation/Recast/Source/Recast.cpp b/dep/recastnavigation/Recast/Source/Recast.cpp index 59d99609446..8308d1973ec 100644 --- a/dep/recastnavigation/Recast/Source/Recast.cpp +++ b/dep/recastnavigation/Recast/Source/Recast.cpp @@ -23,6 +23,7 @@ #include <stdlib.h> #include <stdio.h> #include <stdarg.h> +#include <new> #include "Recast.h" #include "RecastAlloc.h" #include "RecastAssert.h" @@ -72,23 +73,39 @@ void rcContext::log(const rcLogCategory category, const char* format, ...) rcHeightfield* rcAllocHeightfield() { - rcHeightfield* hf = (rcHeightfield*)rcAlloc(sizeof(rcHeightfield), RC_ALLOC_PERM); - memset(hf, 0, sizeof(rcHeightfield)); - return hf; + return new (rcAlloc(sizeof(rcHeightfield), RC_ALLOC_PERM)) rcHeightfield; } -void rcFreeHeightField(rcHeightfield* hf) +rcHeightfield::rcHeightfield() + : width() + , height() + , bmin() + , bmax() + , cs() + , ch() + , spans() + , pools() + , freelist() +{ +} + +rcHeightfield::~rcHeightfield() { - if (!hf) return; // Delete span array. - rcFree(hf->spans); + rcFree(spans); // Delete span pools. - while (hf->pools) + while (pools) { - rcSpanPool* next = hf->pools->next; - rcFree(hf->pools); - hf->pools = next; + rcSpanPool* next = pools->next; + rcFree(pools); + pools = next; } +} + +void rcFreeHeightField(rcHeightfield* hf) +{ + if (!hf) return; + hf->~rcHeightfield(); rcFree(hf); } @@ -109,7 +126,6 @@ void rcFreeCompactHeightfield(rcCompactHeightfield* chf) rcFree(chf); } - rcHeightfieldLayerSet* rcAllocHeightfieldLayerSet() { rcHeightfieldLayerSet* lset = (rcHeightfieldLayerSet*)rcAlloc(sizeof(rcHeightfieldLayerSet), RC_ALLOC_PERM); @@ -245,11 +261,12 @@ static void calcTriNormal(const float* v0, const float* v1, const float* v2, flo /// /// @see rcHeightfield, rcClearUnwalkableTriangles, rcRasterizeTriangles void rcMarkWalkableTriangles(rcContext* ctx, const float walkableSlopeAngle, - const float* verts, int /*nv*/, + const float* verts, int nv, const int* tris, int nt, unsigned char* areas) { rcIgnoreUnused(ctx); + rcIgnoreUnused(nv); const float walkableThr = cosf(walkableSlopeAngle/180.0f*RC_PI); @@ -329,7 +346,7 @@ bool rcBuildCompactHeightfield(rcContext* ctx, const int walkableHeight, const i { rcAssert(ctx); - ctx->startTimer(RC_TIMER_BUILD_COMPACTHEIGHTFIELD); + rcScopedTimer timer(ctx, RC_TIMER_BUILD_COMPACTHEIGHTFIELD); const int w = hf.width; const int h = hf.height; @@ -456,8 +473,6 @@ bool rcBuildCompactHeightfield(rcContext* ctx, const int walkableHeight, const i ctx->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Heightfield has too many layers %d (max: %d)", tooHighNeighbour, MAX_LAYERS); } - - ctx->stopTimer(RC_TIMER_BUILD_COMPACTHEIGHTFIELD); return true; } diff --git a/dep/recastnavigation/Recast/Source/RecastAlloc.cpp b/dep/recastnavigation/Recast/Source/RecastAlloc.cpp index b5ec1516146..453b5fa6a60 100644 --- a/dep/recastnavigation/Recast/Source/RecastAlloc.cpp +++ b/dep/recastnavigation/Recast/Source/RecastAlloc.cpp @@ -19,8 +19,9 @@ #include <stdlib.h> #include <string.h> #include "RecastAlloc.h" +#include "RecastAssert.h" -static void *rcAllocDefault(int size, rcAllocHint) +static void *rcAllocDefault(size_t size, rcAllocHint) { return malloc(size); } @@ -41,7 +42,7 @@ void rcAllocSetCustom(rcAllocFunc *allocFunc, rcFreeFunc *freeFunc) } /// @see rcAllocSetCustom -void* rcAlloc(int size, rcAllocHint hint) +void* rcAlloc(size_t size, rcAllocHint hint) { return sRecastAllocFunc(size, hint); } @@ -72,17 +73,14 @@ void rcFree(void* ptr) /// Using this method ensures the array is at least large enough to hold /// the specified number of elements. This can improve performance by /// avoiding auto-resizing during use. -void rcIntArray::resize(int n) +void rcIntArray::doResize(int n) { - if (n > m_cap) - { - if (!m_cap) m_cap = n; - while (m_cap < n) m_cap *= 2; - int* newData = (int*)rcAlloc(m_cap*sizeof(int), RC_ALLOC_TEMP); - if (m_size && newData) memcpy(newData, m_data, m_size*sizeof(int)); - rcFree(m_data); - m_data = newData; - } - m_size = n; + if (!m_cap) m_cap = n; + while (m_cap < n) m_cap *= 2; + int* newData = (int*)rcAlloc(m_cap*sizeof(int), RC_ALLOC_TEMP); + rcAssert(newData); + if (m_size && newData) memcpy(newData, m_data, m_size*sizeof(int)); + rcFree(m_data); + m_data = newData; } diff --git a/dep/recastnavigation/Recast/Source/RecastArea.cpp b/dep/recastnavigation/Recast/Source/RecastArea.cpp index 1a338cd9b8c..97139cf996a 100644 --- a/dep/recastnavigation/Recast/Source/RecastArea.cpp +++ b/dep/recastnavigation/Recast/Source/RecastArea.cpp @@ -41,7 +41,7 @@ bool rcErodeWalkableArea(rcContext* ctx, int radius, rcCompactHeightfield& chf) const int w = chf.width; const int h = chf.height; - ctx->startTimer(RC_TIMER_ERODE_AREA); + rcScopedTimer timer(ctx, RC_TIMER_ERODE_AREA); unsigned char* dist = (unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP); if (!dist) @@ -215,8 +215,6 @@ bool rcErodeWalkableArea(rcContext* ctx, int radius, rcCompactHeightfield& chf) rcFree(dist); - ctx->stopTimer(RC_TIMER_ERODE_AREA); - return true; } @@ -245,7 +243,7 @@ bool rcMedianFilterWalkableArea(rcContext* ctx, rcCompactHeightfield& chf) const int w = chf.width; const int h = chf.height; - ctx->startTimer(RC_TIMER_MEDIAN_AREA); + rcScopedTimer timer(ctx, RC_TIMER_MEDIAN_AREA); unsigned char* areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP); if (!areas) @@ -306,8 +304,6 @@ bool rcMedianFilterWalkableArea(rcContext* ctx, rcCompactHeightfield& chf) memcpy(chf.areas, areas, sizeof(unsigned char)*chf.spanCount); rcFree(areas); - - ctx->stopTimer(RC_TIMER_MEDIAN_AREA); return true; } @@ -322,7 +318,7 @@ void rcMarkBoxArea(rcContext* ctx, const float* bmin, const float* bmax, unsigne { rcAssert(ctx); - ctx->startTimer(RC_TIMER_MARK_BOX_AREA); + rcScopedTimer timer(ctx, RC_TIMER_MARK_BOX_AREA); int minx = (int)((bmin[0]-chf.bmin[0])/chf.cs); int miny = (int)((bmin[1]-chf.bmin[1])/chf.ch); @@ -357,9 +353,6 @@ void rcMarkBoxArea(rcContext* ctx, const float* bmin, const float* bmax, unsigne } } } - - ctx->stopTimer(RC_TIMER_MARK_BOX_AREA); - } @@ -391,7 +384,7 @@ void rcMarkConvexPolyArea(rcContext* ctx, const float* verts, const int nverts, { rcAssert(ctx); - ctx->startTimer(RC_TIMER_MARK_CONVEXPOLY_AREA); + rcScopedTimer timer(ctx, RC_TIMER_MARK_CONVEXPOLY_AREA); float bmin[3], bmax[3]; rcVcopy(bmin, verts); @@ -448,8 +441,6 @@ void rcMarkConvexPolyArea(rcContext* ctx, const float* verts, const int nverts, } } } - - ctx->stopTimer(RC_TIMER_MARK_CONVEXPOLY_AREA); } int rcOffsetPoly(const float* verts, const int nverts, const float offset, @@ -541,7 +532,7 @@ void rcMarkCylinderArea(rcContext* ctx, const float* pos, { rcAssert(ctx); - ctx->startTimer(RC_TIMER_MARK_CYLINDER_AREA); + rcScopedTimer timer(ctx, RC_TIMER_MARK_CYLINDER_AREA); float bmin[3], bmax[3]; bmin[0] = pos[0] - r; @@ -597,6 +588,4 @@ void rcMarkCylinderArea(rcContext* ctx, const float* pos, } } } - - ctx->stopTimer(RC_TIMER_MARK_CYLINDER_AREA); } diff --git a/dep/recastnavigation/Recast/Source/RecastContour.cpp b/dep/recastnavigation/Recast/Source/RecastContour.cpp index a7be6691f3e..277ab015018 100644 --- a/dep/recastnavigation/Recast/Source/RecastContour.cpp +++ b/dep/recastnavigation/Recast/Source/RecastContour.cpp @@ -731,7 +731,7 @@ static void mergeRegionHoles(rcContext* ctx, rcContourRegion& region) for (int i = 0; i < region.nholes; i++) maxVerts += region.holes[i].contour->nverts; - rcScopedDelete<rcPotentialDiagonal> diags = (rcPotentialDiagonal*)rcAlloc(sizeof(rcPotentialDiagonal)*maxVerts, RC_ALLOC_TEMP); + rcScopedDelete<rcPotentialDiagonal> diags((rcPotentialDiagonal*)rcAlloc(sizeof(rcPotentialDiagonal)*maxVerts, RC_ALLOC_TEMP)); if (!diags) { ctx->log(RC_LOG_WARNING, "mergeRegionHoles: Failed to allocated diags %d.", maxVerts); @@ -831,7 +831,7 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, const int h = chf.height; const int borderSize = chf.borderSize; - ctx->startTimer(RC_TIMER_BUILD_CONTOURS); + rcScopedTimer timer(ctx, RC_TIMER_BUILD_CONTOURS); rcVcopy(cset.bmin, chf.bmin); rcVcopy(cset.bmax, chf.bmax); @@ -849,6 +849,7 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, cset.width = chf.width - chf.borderSize*2; cset.height = chf.height - chf.borderSize*2; cset.borderSize = chf.borderSize; + cset.maxError = maxError; int maxContours = rcMax((int)chf.maxRegions, 8); cset.conts = (rcContour*)rcAlloc(sizeof(rcContour)*maxContours, RC_ALLOC_PERM); @@ -856,7 +857,7 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, return false; cset.nconts = 0; - rcScopedDelete<unsigned char> flags = (unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP); + rcScopedDelete<unsigned char> flags((unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP)); if (!flags) { ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'flags' (%d).", chf.spanCount); @@ -1008,7 +1009,7 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, if (cset.nconts > 0) { // Calculate winding of all polygons. - rcScopedDelete<char> winding = (char*)rcAlloc(sizeof(char)*cset.nconts, RC_ALLOC_TEMP); + rcScopedDelete<char> winding((char*)rcAlloc(sizeof(char)*cset.nconts, RC_ALLOC_TEMP)); if (!winding) { ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'hole' (%d).", cset.nconts); @@ -1029,7 +1030,7 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, // Collect outline contour and holes contours per region. // We assume that there is one outline and multiple holes. const int nregions = chf.maxRegions+1; - rcScopedDelete<rcContourRegion> regions = (rcContourRegion*)rcAlloc(sizeof(rcContourRegion)*nregions, RC_ALLOC_TEMP); + rcScopedDelete<rcContourRegion> regions((rcContourRegion*)rcAlloc(sizeof(rcContourRegion)*nregions, RC_ALLOC_TEMP)); if (!regions) { ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'regions' (%d).", nregions); @@ -1037,7 +1038,7 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, } memset(regions, 0, sizeof(rcContourRegion)*nregions); - rcScopedDelete<rcContourHole> holes = (rcContourHole*)rcAlloc(sizeof(rcContourHole)*cset.nconts, RC_ALLOC_TEMP); + rcScopedDelete<rcContourHole> holes((rcContourHole*)rcAlloc(sizeof(rcContourHole)*cset.nconts, RC_ALLOC_TEMP)); if (!holes) { ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'holes' (%d).", cset.nconts); @@ -1100,7 +1101,5 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, } - ctx->stopTimer(RC_TIMER_BUILD_CONTOURS); - return true; } diff --git a/dep/recastnavigation/Recast/Source/RecastFilter.cpp b/dep/recastnavigation/Recast/Source/RecastFilter.cpp index bf985c362c9..9d3e63c4820 100644 --- a/dep/recastnavigation/Recast/Source/RecastFilter.cpp +++ b/dep/recastnavigation/Recast/Source/RecastFilter.cpp @@ -37,7 +37,7 @@ void rcFilterLowHangingWalkableObstacles(rcContext* ctx, const int walkableClimb { rcAssert(ctx); - ctx->startTimer(RC_TIMER_FILTER_LOW_OBSTACLES); + rcScopedTimer timer(ctx, RC_TIMER_FILTER_LOW_OBSTACLES); const int w = solid.width; const int h = solid.height; @@ -67,8 +67,6 @@ void rcFilterLowHangingWalkableObstacles(rcContext* ctx, const int walkableClimb } } } - - ctx->stopTimer(RC_TIMER_FILTER_LOW_OBSTACLES); } /// @par @@ -86,7 +84,7 @@ void rcFilterLedgeSpans(rcContext* ctx, const int walkableHeight, const int walk { rcAssert(ctx); - ctx->startTimer(RC_TIMER_FILTER_BORDER); + rcScopedTimer timer(ctx, RC_TIMER_FILTER_BORDER); const int w = solid.width; const int h = solid.height; @@ -156,20 +154,19 @@ void rcFilterLedgeSpans(rcContext* ctx, const int walkableHeight, const int walk // The current span is close to a ledge if the drop to any // neighbour span is less than the walkableClimb. if (minh < -walkableClimb) + { s->area = RC_NULL_AREA; - + } // If the difference between all neighbours is too large, // we are at steep slope, mark the span as ledge. - if ((asmax - asmin) > walkableClimb) + else if ((asmax - asmin) > walkableClimb) { s->area = RC_NULL_AREA; } } } } - - ctx->stopTimer(RC_TIMER_FILTER_BORDER); -} +} /// @par /// @@ -181,7 +178,7 @@ void rcFilterWalkableLowHeightSpans(rcContext* ctx, int walkableHeight, rcHeight { rcAssert(ctx); - ctx->startTimer(RC_TIMER_FILTER_WALKABLE); + rcScopedTimer timer(ctx, RC_TIMER_FILTER_WALKABLE); const int w = solid.width; const int h = solid.height; @@ -202,6 +199,4 @@ void rcFilterWalkableLowHeightSpans(rcContext* ctx, int walkableHeight, rcHeight } } } - - ctx->stopTimer(RC_TIMER_FILTER_WALKABLE); } diff --git a/dep/recastnavigation/Recast/Source/RecastLayers.cpp b/dep/recastnavigation/Recast/Source/RecastLayers.cpp index 41458c1ea68..acc97e44f00 100644 --- a/dep/recastnavigation/Recast/Source/RecastLayers.cpp +++ b/dep/recastnavigation/Recast/Source/RecastLayers.cpp @@ -27,7 +27,9 @@ #include "RecastAssert.h" -static const int RC_MAX_LAYERS = RC_NOT_CONNECTED; +// Must be 255 or smaller (not 256) because layer IDs are stored as +// a byte where 255 is a special value. +static const int RC_MAX_LAYERS = 63; static const int RC_MAX_NEIS = 16; struct rcLayerRegion @@ -42,25 +44,31 @@ struct rcLayerRegion }; -static void addUnique(unsigned char* a, unsigned char& an, unsigned char v) -{ - const int n = (int)an; - for (int i = 0; i < n; ++i) - if (a[i] == v) - return; - a[an] = v; - an++; -} - static bool contains(const unsigned char* a, const unsigned char an, const unsigned char v) { const int n = (int)an; for (int i = 0; i < n; ++i) + { if (a[i] == v) return true; + } return false; } +static bool addUnique(unsigned char* a, unsigned char& an, int anMax, unsigned char v) +{ + if (contains(a, an, v)) + return true; + + if ((int)an >= anMax) + return false; + + a[an] = v; + an++; + return true; +} + + inline bool overlapRange(const unsigned short amin, const unsigned short amax, const unsigned short bmin, const unsigned short bmax) { @@ -87,12 +95,12 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf, { rcAssert(ctx); - ctx->startTimer(RC_TIMER_BUILD_LAYERS); + rcScopedTimer timer(ctx, RC_TIMER_BUILD_LAYERS); const int w = chf.width; const int h = chf.height; - rcScopedDelete<unsigned char> srcReg = (unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP); + rcScopedDelete<unsigned char> srcReg((unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP)); if (!srcReg) { ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'srcReg' (%d).", chf.spanCount); @@ -101,7 +109,7 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf, memset(srcReg,0xff,sizeof(unsigned char)*chf.spanCount); const int nsweeps = chf.width; - rcScopedDelete<rcLayerSweepSpan> sweeps = (rcLayerSweepSpan*)rcAlloc(sizeof(rcLayerSweepSpan)*nsweeps, RC_ALLOC_TEMP); + rcScopedDelete<rcLayerSweepSpan> sweeps((rcLayerSweepSpan*)rcAlloc(sizeof(rcLayerSweepSpan)*nsweeps, RC_ALLOC_TEMP)); if (!sweeps) { ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'sweeps' (%d).", nsweeps); @@ -212,7 +220,7 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf, // Allocate and init layer regions. const int nregs = (int)regId; - rcScopedDelete<rcLayerRegion> regs = (rcLayerRegion*)rcAlloc(sizeof(rcLayerRegion)*nregs, RC_ALLOC_TEMP); + rcScopedDelete<rcLayerRegion> regs((rcLayerRegion*)rcAlloc(sizeof(rcLayerRegion)*nregs, RC_ALLOC_TEMP)); if (!regs) { ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'regs' (%d).", nregs); @@ -259,7 +267,12 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf, const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir); const unsigned char rai = srcReg[ai]; if (rai != 0xff && rai != ri) - addUnique(regs[ri].neis, regs[ri].nneis, rai); + { + // Don't check return value -- if we cannot add the neighbor + // it will just cause a few more regions to be created, which + // is fine. + addUnique(regs[ri].neis, regs[ri].nneis, RC_MAX_NEIS, rai); + } } } @@ -274,8 +287,13 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf, { rcLayerRegion& ri = regs[lregs[i]]; rcLayerRegion& rj = regs[lregs[j]]; - addUnique(ri.layers, ri.nlayers, lregs[j]); - addUnique(rj.layers, rj.nlayers, lregs[i]); + + if (!addUnique(ri.layers, ri.nlayers, RC_MAX_LAYERS, lregs[j]) || + !addUnique(rj.layers, rj.nlayers, RC_MAX_LAYERS, lregs[i])) + { + ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: layer overflow (too many overlapping walkable platforms). Try increasing RC_MAX_LAYERS."); + return false; + } } } } @@ -338,7 +356,13 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf, regn.layerId = layerId; // Merge current layers to root. for (int k = 0; k < regn.nlayers; ++k) - addUnique(root.layers, root.nlayers, regn.layers[k]); + { + if (!addUnique(root.layers, root.nlayers, RC_MAX_LAYERS, regn.layers[k])) + { + ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: layer overflow (too many overlapping walkable platforms). Try increasing RC_MAX_LAYERS."); + return false; + } + } root.ymin = rcMin(root.ymin, regn.ymin); root.ymax = rcMax(root.ymax, regn.ymax); } @@ -416,7 +440,14 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf, rj.layerId = newId; // Add overlaid layers from 'rj' to 'ri'. for (int k = 0; k < rj.nlayers; ++k) - addUnique(ri.layers, ri.nlayers, rj.layers[k]); + { + if (!addUnique(ri.layers, ri.nlayers, RC_MAX_LAYERS, rj.layers[k])) + { + ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: layer overflow (too many overlapping walkable platforms). Try increasing RC_MAX_LAYERS."); + return false; + } + } + // Update height bounds. ri.ymin = rcMin(ri.ymin, rj.ymin); ri.ymax = rcMax(ri.ymax, rj.ymax); @@ -446,10 +477,7 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf, // No layers, return empty. if (layerId == 0) - { - ctx->stopTimer(RC_TIMER_BUILD_LAYERS); return true; - } // Create layers. rcAssert(lset.layers == 0); @@ -612,7 +640,5 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf, layer->miny = layer->maxy = 0; } - ctx->stopTimer(RC_TIMER_BUILD_LAYERS); - return true; } diff --git a/dep/recastnavigation/Recast/Source/RecastMesh.cpp b/dep/recastnavigation/Recast/Source/RecastMesh.cpp index c8853444019..9b6f04e3092 100644 --- a/dep/recastnavigation/Recast/Source/RecastMesh.cpp +++ b/dep/recastnavigation/Recast/Source/RecastMesh.cpp @@ -528,8 +528,8 @@ static int getPolyMergeValue(unsigned short* pa, unsigned short* pb, return dx*dx + dy*dy; } -static void mergePolys(unsigned short* pa, unsigned short* pb, int ea, int eb, - unsigned short* tmp, const int nvp) +static void mergePolyVerts(unsigned short* pa, unsigned short* pb, int ea, int eb, + unsigned short* tmp, const int nvp) { const int na = countPolyVerts(pa, nvp); const int nb = countPolyVerts(pb, nvp); @@ -601,7 +601,7 @@ static bool canRemoveVertex(rcContext* ctx, rcPolyMesh& mesh, const unsigned sho // Find edges which share the removed vertex. const int maxEdges = numTouchedVerts*2; int nedges = 0; - rcScopedDelete<int> edges = (int*)rcAlloc(sizeof(int)*maxEdges*3, RC_ALLOC_TEMP); + rcScopedDelete<int> edges((int*)rcAlloc(sizeof(int)*maxEdges*3, RC_ALLOC_TEMP)); if (!edges) { ctx->log(RC_LOG_WARNING, "canRemoveVertex: Out of memory 'edges' (%d).", maxEdges*3); @@ -681,7 +681,7 @@ static bool removeVertex(rcContext* ctx, rcPolyMesh& mesh, const unsigned short } int nedges = 0; - rcScopedDelete<int> edges = (int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp*4, RC_ALLOC_TEMP); + rcScopedDelete<int> edges((int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp*4, RC_ALLOC_TEMP)); if (!edges) { ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'edges' (%d).", numRemovedVerts*nvp*4); @@ -689,15 +689,15 @@ static bool removeVertex(rcContext* ctx, rcPolyMesh& mesh, const unsigned short } int nhole = 0; - rcScopedDelete<int> hole = (int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp, RC_ALLOC_TEMP); + rcScopedDelete<int> hole((int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp, RC_ALLOC_TEMP)); if (!hole) { ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'hole' (%d).", numRemovedVerts*nvp); return false; } - + int nhreg = 0; - rcScopedDelete<int> hreg = (int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp, RC_ALLOC_TEMP); + rcScopedDelete<int> hreg((int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp, RC_ALLOC_TEMP)); if (!hreg) { ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'hreg' (%d).", numRemovedVerts*nvp); @@ -705,7 +705,7 @@ static bool removeVertex(rcContext* ctx, rcPolyMesh& mesh, const unsigned short } int nharea = 0; - rcScopedDelete<int> harea = (int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp, RC_ALLOC_TEMP); + rcScopedDelete<int> harea((int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp, RC_ALLOC_TEMP)); if (!harea) { ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'harea' (%d).", numRemovedVerts*nvp); @@ -822,21 +822,21 @@ static bool removeVertex(rcContext* ctx, rcPolyMesh& mesh, const unsigned short break; } - rcScopedDelete<int> tris = (int*)rcAlloc(sizeof(int)*nhole*3, RC_ALLOC_TEMP); + rcScopedDelete<int> tris((int*)rcAlloc(sizeof(int)*nhole*3, RC_ALLOC_TEMP)); if (!tris) { ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'tris' (%d).", nhole*3); return false; } - rcScopedDelete<int> tverts = (int*)rcAlloc(sizeof(int)*nhole*4, RC_ALLOC_TEMP); + rcScopedDelete<int> tverts((int*)rcAlloc(sizeof(int)*nhole*4, RC_ALLOC_TEMP)); if (!tverts) { ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'tverts' (%d).", nhole*4); return false; } - rcScopedDelete<int> thole = (int*)rcAlloc(sizeof(int)*nhole, RC_ALLOC_TEMP); + rcScopedDelete<int> thole((int*)rcAlloc(sizeof(int)*nhole, RC_ALLOC_TEMP)); if (!thole) { ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'thole' (%d).", nhole); @@ -863,19 +863,19 @@ static bool removeVertex(rcContext* ctx, rcPolyMesh& mesh, const unsigned short } // Merge the hole triangles back to polygons. - rcScopedDelete<unsigned short> polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*(ntris+1)*nvp, RC_ALLOC_TEMP); + rcScopedDelete<unsigned short> polys((unsigned short*)rcAlloc(sizeof(unsigned short)*(ntris+1)*nvp, RC_ALLOC_TEMP)); if (!polys) { ctx->log(RC_LOG_ERROR, "removeVertex: Out of memory 'polys' (%d).", (ntris+1)*nvp); return false; } - rcScopedDelete<unsigned short> pregs = (unsigned short*)rcAlloc(sizeof(unsigned short)*ntris, RC_ALLOC_TEMP); + rcScopedDelete<unsigned short> pregs((unsigned short*)rcAlloc(sizeof(unsigned short)*ntris, RC_ALLOC_TEMP)); if (!pregs) { ctx->log(RC_LOG_ERROR, "removeVertex: Out of memory 'pregs' (%d).", ntris); return false; } - rcScopedDelete<unsigned char> pareas = (unsigned char*)rcAlloc(sizeof(unsigned char)*ntris, RC_ALLOC_TEMP); + rcScopedDelete<unsigned char> pareas((unsigned char*)rcAlloc(sizeof(unsigned char)*ntris, RC_ALLOC_TEMP)); if (!pareas) { ctx->log(RC_LOG_ERROR, "removeVertex: Out of memory 'pareas' (%d).", ntris); @@ -895,7 +895,14 @@ static bool removeVertex(rcContext* ctx, rcPolyMesh& mesh, const unsigned short polys[npolys*nvp+0] = (unsigned short)hole[t[0]]; polys[npolys*nvp+1] = (unsigned short)hole[t[1]]; polys[npolys*nvp+2] = (unsigned short)hole[t[2]]; - pregs[npolys] = (unsigned short)hreg[t[0]]; + + // If this polygon covers multiple region types then + // mark it as such + if (hreg[t[0]] != hreg[t[1]] || hreg[t[1]] != hreg[t[2]]) + pregs[npolys] = RC_MULTIPLE_REGS; + else + pregs[npolys] = (unsigned short)hreg[t[0]]; + pareas[npolys] = (unsigned char)harea[t[0]]; npolys++; } @@ -936,7 +943,10 @@ static bool removeVertex(rcContext* ctx, rcPolyMesh& mesh, const unsigned short // Found best, merge. unsigned short* pa = &polys[bestPa*nvp]; unsigned short* pb = &polys[bestPb*nvp]; - mergePolys(pa, pb, bestEa, bestEb, tmpPoly, nvp); + mergePolyVerts(pa, pb, bestEa, bestEb, tmpPoly, nvp); + if (pregs[bestPa] != pregs[bestPb]) + pregs[bestPa] = RC_MULTIPLE_REGS; + unsigned short* last = &polys[(npolys-1)*nvp]; if (pb != last) memcpy(pb, last, sizeof(unsigned short)*nvp); @@ -983,13 +993,14 @@ bool rcBuildPolyMesh(rcContext* ctx, rcContourSet& cset, const int nvp, rcPolyMe { rcAssert(ctx); - ctx->startTimer(RC_TIMER_BUILD_POLYMESH); + rcScopedTimer timer(ctx, RC_TIMER_BUILD_POLYMESH); rcVcopy(mesh.bmin, cset.bmin); rcVcopy(mesh.bmax, cset.bmax); mesh.cs = cset.cs; mesh.ch = cset.ch; mesh.borderSize = cset.borderSize; + mesh.maxEdgeError = cset.maxError; int maxVertices = 0; int maxTris = 0; @@ -1009,7 +1020,7 @@ bool rcBuildPolyMesh(rcContext* ctx, rcContourSet& cset, const int nvp, rcPolyMe return false; } - rcScopedDelete<unsigned char> vflags = (unsigned char*)rcAlloc(sizeof(unsigned char)*maxVertices, RC_ALLOC_TEMP); + rcScopedDelete<unsigned char> vflags((unsigned char*)rcAlloc(sizeof(unsigned char)*maxVertices, RC_ALLOC_TEMP)); if (!vflags) { ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'vflags' (%d).", maxVertices); @@ -1052,7 +1063,7 @@ bool rcBuildPolyMesh(rcContext* ctx, rcContourSet& cset, const int nvp, rcPolyMe memset(mesh.regs, 0, sizeof(unsigned short)*maxTris); memset(mesh.areas, 0, sizeof(unsigned char)*maxTris); - rcScopedDelete<int> nextVert = (int*)rcAlloc(sizeof(int)*maxVertices, RC_ALLOC_TEMP); + rcScopedDelete<int> nextVert((int*)rcAlloc(sizeof(int)*maxVertices, RC_ALLOC_TEMP)); if (!nextVert) { ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'nextVert' (%d).", maxVertices); @@ -1060,7 +1071,7 @@ bool rcBuildPolyMesh(rcContext* ctx, rcContourSet& cset, const int nvp, rcPolyMe } memset(nextVert, 0, sizeof(int)*maxVertices); - rcScopedDelete<int> firstVert = (int*)rcAlloc(sizeof(int)*VERTEX_BUCKET_COUNT, RC_ALLOC_TEMP); + rcScopedDelete<int> firstVert((int*)rcAlloc(sizeof(int)*VERTEX_BUCKET_COUNT, RC_ALLOC_TEMP)); if (!firstVert) { ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'firstVert' (%d).", VERTEX_BUCKET_COUNT); @@ -1069,19 +1080,19 @@ bool rcBuildPolyMesh(rcContext* ctx, rcContourSet& cset, const int nvp, rcPolyMe for (int i = 0; i < VERTEX_BUCKET_COUNT; ++i) firstVert[i] = -1; - rcScopedDelete<int> indices = (int*)rcAlloc(sizeof(int)*maxVertsPerCont, RC_ALLOC_TEMP); + rcScopedDelete<int> indices((int*)rcAlloc(sizeof(int)*maxVertsPerCont, RC_ALLOC_TEMP)); if (!indices) { ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'indices' (%d).", maxVertsPerCont); return false; } - rcScopedDelete<int> tris = (int*)rcAlloc(sizeof(int)*maxVertsPerCont*3, RC_ALLOC_TEMP); + rcScopedDelete<int> tris((int*)rcAlloc(sizeof(int)*maxVertsPerCont*3, RC_ALLOC_TEMP)); if (!tris) { ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'tris' (%d).", maxVertsPerCont*3); return false; } - rcScopedDelete<unsigned short> polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*(maxVertsPerCont+1)*nvp, RC_ALLOC_TEMP); + rcScopedDelete<unsigned short> polys((unsigned short*)rcAlloc(sizeof(unsigned short)*(maxVertsPerCont+1)*nvp, RC_ALLOC_TEMP)); if (!polys) { ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'polys' (%d).", maxVertsPerCont*nvp); @@ -1182,7 +1193,7 @@ bool rcBuildPolyMesh(rcContext* ctx, rcContourSet& cset, const int nvp, rcPolyMe // Found best, merge. unsigned short* pa = &polys[bestPa*nvp]; unsigned short* pb = &polys[bestPb*nvp]; - mergePolys(pa, pb, bestEa, bestEb, tmpPoly, nvp); + mergePolyVerts(pa, pb, bestEa, bestEb, tmpPoly, nvp); unsigned short* lastPoly = &polys[(npolys-1)*nvp]; if (pb != lastPoly) memcpy(pb, lastPoly, sizeof(unsigned short)*nvp); @@ -1293,8 +1304,6 @@ bool rcBuildPolyMesh(rcContext* ctx, rcContourSet& cset, const int nvp, rcPolyMe ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: The resulting mesh has too many polygons %d (max %d). Data can be corrupted.", mesh.npolys, 0xffff); } - ctx->stopTimer(RC_TIMER_BUILD_POLYMESH); - return true; } @@ -1306,7 +1315,7 @@ bool rcMergePolyMeshes(rcContext* ctx, rcPolyMesh** meshes, const int nmeshes, r if (!nmeshes || !meshes) return true; - ctx->startTimer(RC_TIMER_MERGE_POLYMESH); + rcScopedTimer timer(ctx, RC_TIMER_MERGE_POLYMESH); mesh.nvp = meshes[0]->nvp; mesh.cs = meshes[0]->cs; @@ -1367,7 +1376,7 @@ bool rcMergePolyMeshes(rcContext* ctx, rcPolyMesh** meshes, const int nmeshes, r } memset(mesh.flags, 0, sizeof(unsigned short)*maxPolys); - rcScopedDelete<int> nextVert = (int*)rcAlloc(sizeof(int)*maxVerts, RC_ALLOC_TEMP); + rcScopedDelete<int> nextVert((int*)rcAlloc(sizeof(int)*maxVerts, RC_ALLOC_TEMP)); if (!nextVert) { ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'nextVert' (%d).", maxVerts); @@ -1375,7 +1384,7 @@ bool rcMergePolyMeshes(rcContext* ctx, rcPolyMesh** meshes, const int nmeshes, r } memset(nextVert, 0, sizeof(int)*maxVerts); - rcScopedDelete<int> firstVert = (int*)rcAlloc(sizeof(int)*VERTEX_BUCKET_COUNT, RC_ALLOC_TEMP); + rcScopedDelete<int> firstVert((int*)rcAlloc(sizeof(int)*VERTEX_BUCKET_COUNT, RC_ALLOC_TEMP)); if (!firstVert) { ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'firstVert' (%d).", VERTEX_BUCKET_COUNT); @@ -1384,7 +1393,7 @@ bool rcMergePolyMeshes(rcContext* ctx, rcPolyMesh** meshes, const int nmeshes, r for (int i = 0; i < VERTEX_BUCKET_COUNT; ++i) firstVert[i] = -1; - rcScopedDelete<unsigned short> vremap = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxVertsPerMesh, RC_ALLOC_PERM); + rcScopedDelete<unsigned short> vremap((unsigned short*)rcAlloc(sizeof(unsigned short)*maxVertsPerMesh, RC_ALLOC_PERM)); if (!vremap) { ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'vremap' (%d).", maxVertsPerMesh); @@ -1474,8 +1483,6 @@ bool rcMergePolyMeshes(rcContext* ctx, rcPolyMesh** meshes, const int nmeshes, r ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: The resulting mesh has too many polygons %d (max %d). Data can be corrupted.", mesh.npolys, 0xffff); } - ctx->stopTimer(RC_TIMER_MERGE_POLYMESH); - return true; } @@ -1499,6 +1506,7 @@ bool rcCopyPolyMesh(rcContext* ctx, const rcPolyMesh& src, rcPolyMesh& dst) dst.cs = src.cs; dst.ch = src.ch; dst.borderSize = src.borderSize; + dst.maxEdgeError = src.maxEdgeError; dst.verts = (unsigned short*)rcAlloc(sizeof(unsigned short)*src.nverts*3, RC_ALLOC_PERM); if (!dst.verts) diff --git a/dep/recastnavigation/Recast/Source/RecastMeshDetail.cpp b/dep/recastnavigation/Recast/Source/RecastMeshDetail.cpp index 56b059d7dd5..f953132f74c 100644 --- a/dep/recastnavigation/Recast/Source/RecastMeshDetail.cpp +++ b/dep/recastnavigation/Recast/Source/RecastMeshDetail.cpp @@ -202,7 +202,7 @@ static float distToPoly(int nvert, const float* verts, const float* p) static unsigned short getHeight(const float fx, const float fy, const float fz, const float /*cs*/, const float ics, const float ch, - const rcHeightPatch& hp) + const int radius, const rcHeightPatch& hp) { int ix = (int)floorf(fx*ics + 0.01f); int iz = (int)floorf(fz*ics + 0.01f); @@ -212,23 +212,69 @@ static unsigned short getHeight(const float fx, const float fy, const float fz, if (h == RC_UNSET_HEIGHT) { // Special case when data might be bad. - // Find nearest neighbour pixel which has valid height. - const int off[8*2] = { -1,0, -1,-1, 0,-1, 1,-1, 1,0, 1,1, 0,1, -1,1}; + // Walk adjacent cells in a spiral up to 'radius', and look + // for a pixel which has a valid height. + int x = 1, z = 0, dx = 1, dz = 0; + int maxSize = radius * 2 + 1; + int maxIter = maxSize * maxSize - 1; + + int nextRingIterStart = 8; + int nextRingIters = 16; + float dmin = FLT_MAX; - for (int i = 0; i < 8; ++i) + for (int i = 0; i < maxIter; i++) { - const int nx = ix+off[i*2+0]; - const int nz = iz+off[i*2+1]; - if (nx < 0 || nz < 0 || nx >= hp.width || nz >= hp.height) continue; - const unsigned short nh = hp.data[nx+nz*hp.width]; - if (nh == RC_UNSET_HEIGHT) continue; - - const float d = fabsf(nh*ch - fy); - if (d < dmin) + const int nx = ix + x; + const int nz = iz + z; + + if (nx >= 0 && nz >= 0 && nx < hp.width && nz < hp.height) + { + const unsigned short nh = hp.data[nx + nz*hp.width]; + if (nh != RC_UNSET_HEIGHT) + { + const float d = fabsf(nh*ch - fy); + if (d < dmin) + { + h = nh; + dmin = d; + } + } + } + + // We are searching in a grid which looks approximately like this: + // __________ + // |2 ______ 2| + // | |1 __ 1| | + // | | |__| | | + // | |______| | + // |__________| + // We want to find the best height as close to the center cell as possible. This means that + // if we find a height in one of the neighbor cells to the center, we don't want to + // expand further out than the 8 neighbors - we want to limit our search to the closest + // of these "rings", but the best height in the ring. + // For example, the center is just 1 cell. We checked that at the entrance to the function. + // The next "ring" contains 8 cells (marked 1 above). Those are all the neighbors to the center cell. + // The next one again contains 16 cells (marked 2). In general each ring has 8 additional cells, which + // can be thought of as adding 2 cells around the "center" of each side when we expand the ring. + // Here we detect if we are about to enter the next ring, and if we are and we have found + // a height, we abort the search. + if (i + 1 == nextRingIterStart) + { + if (h != RC_UNSET_HEIGHT) + break; + + nextRingIterStart += nextRingIters; + nextRingIters += 8; + } + + if ((x == z) || ((x < 0) && (x == -z)) || ((x > 0) && (x == 1 - z))) { - h = nh; - dmin = d; + int tmp = dx; + dx = -dz; + dz = tmp; } + x += dx; + z += dz; } } return h; @@ -590,9 +636,9 @@ inline float getJitterY(const int i) static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin, const float sampleDist, const float sampleMaxError, - const rcCompactHeightfield& chf, const rcHeightPatch& hp, - float* verts, int& nverts, rcIntArray& tris, - rcIntArray& edges, rcIntArray& samples) + const int heightSearchRadius, const rcCompactHeightfield& chf, + const rcHeightPatch& hp, float* verts, int& nverts, + rcIntArray& tris, rcIntArray& edges, rcIntArray& samples) { static const int MAX_VERTS = 127; static const int MAX_TRIS = 255; // Max tris for delaunay is 2n-2-k (n=num verts, k=num hull verts). @@ -601,11 +647,10 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin, int hull[MAX_VERTS]; int nhull = 0; - nverts = 0; + nverts = nin; for (int i = 0; i < nin; ++i) rcVcopy(&verts[i*3], &in[i*3]); - nverts = nin; edges.resize(0); tris.resize(0); @@ -661,7 +706,7 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin, pos[0] = vj[0] + dx*u; pos[1] = vj[1] + dy*u; pos[2] = vj[2] + dz*u; - pos[1] = getHeight(pos[0],pos[1],pos[2], cs, ics, chf.ch, hp)*chf.ch; + pos[1] = getHeight(pos[0],pos[1],pos[2], cs, ics, chf.ch, heightSearchRadius, hp)*chf.ch; } // Simplify samples. int idx[MAX_VERTS_PER_EDGE] = {0,nn}; @@ -731,7 +776,7 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin, // Tessellate the base mesh. // We're using the triangulateHull instead of delaunayHull as it tends to - // create a bit better triangulation for long thing triangles when there + // create a bit better triangulation for long thin triangles when there // are no internal points. triangulateHull(nverts, verts, nhull, hull, tris); @@ -769,7 +814,7 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin, // Make sure the samples are not too close to the edges. if (distToPoly(nin,in,pt) > -sampleDist/2) continue; samples.push(x); - samples.push(getHeight(pt[0], pt[1], pt[2], cs, ics, chf.ch, hp)); + samples.push(getHeight(pt[0], pt[1], pt[2], cs, ics, chf.ch, heightSearchRadius, hp)); samples.push(z); samples.push(0); // Not added } @@ -834,33 +879,25 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin, return true; } - -static void getHeightDataSeedsFromVertices(const rcCompactHeightfield& chf, - const unsigned short* poly, const int npoly, - const unsigned short* verts, const int bs, - rcHeightPatch& hp, rcIntArray& stack) +static void seedArrayWithPolyCenter(rcContext* ctx, const rcCompactHeightfield& chf, + const unsigned short* poly, const int npoly, + const unsigned short* verts, const int bs, + rcHeightPatch& hp, rcIntArray& array) { - // Floodfill the heightfield to get 2D height data, - // starting at vertex locations as seeds. - // Note: Reads to the compact heightfield are offset by border size (bs) // since border size offset is already removed from the polymesh vertices. - memset(hp.data, 0, sizeof(unsigned short)*hp.width*hp.height); - - stack.resize(0); - static const int offset[9*2] = { 0,0, -1,-1, 0,-1, 1,-1, 1,0, 1,1, 0,1, -1,1, -1,0, }; - // Use poly vertices as seed points for the flood fill. - for (int j = 0; j < npoly; ++j) + // Find cell closest to a poly vertex + int startCellX = 0, startCellY = 0, startSpanIndex = -1; + int dmin = RC_UNSET_HEIGHT; + for (int j = 0; j < npoly && dmin > 0; ++j) { - int cx = 0, cz = 0, ci =-1; - int dmin = RC_UNSET_HEIGHT; - for (int k = 0; k < 9; ++k) + for (int k = 0; k < 9 && dmin > 0; ++k) { const int ax = (int)verts[poly[j]*3+0] + offset[k*2+0]; const int ay = (int)verts[poly[j]*3+1]; @@ -870,191 +907,208 @@ static void getHeightDataSeedsFromVertices(const rcCompactHeightfield& chf, continue; const rcCompactCell& c = chf.cells[(ax+bs)+(az+bs)*chf.width]; - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) + for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni && dmin > 0; ++i) { const rcCompactSpan& s = chf.spans[i]; int d = rcAbs(ay - (int)s.y); if (d < dmin) { - cx = ax; - cz = az; - ci = i; + startCellX = ax; + startCellY = az; + startSpanIndex = i; dmin = d; } } } - if (ci != -1) - { - stack.push(cx); - stack.push(cz); - stack.push(ci); - } } - // Find center of the polygon using flood fill. - int pcx = 0, pcz = 0; + rcAssert(startSpanIndex != -1); + // Find center of the polygon + int pcx = 0, pcy = 0; for (int j = 0; j < npoly; ++j) { pcx += (int)verts[poly[j]*3+0]; - pcz += (int)verts[poly[j]*3+2]; + pcy += (int)verts[poly[j]*3+2]; } pcx /= npoly; - pcz /= npoly; + pcy /= npoly; - for (int i = 0; i < stack.size(); i += 3) - { - int cx = stack[i+0]; - int cy = stack[i+1]; - int idx = cx-hp.xmin+(cy-hp.ymin)*hp.width; - hp.data[idx] = 1; - } - - while (stack.size() > 0) + // Use seeds array as a stack for DFS + array.resize(0); + array.push(startCellX); + array.push(startCellY); + array.push(startSpanIndex); + + int dirs[] = { 0, 1, 2, 3 }; + memset(hp.data, 0, sizeof(unsigned short)*hp.width*hp.height); + // DFS to move to the center. Note that we need a DFS here and can not just move + // directly towards the center without recording intermediate nodes, even though the polygons + // are convex. In very rare we can get stuck due to contour simplification if we do not + // record nodes. + int cx = -1, cy = -1, ci = -1; + while (true) { - int ci = stack.pop(); - int cy = stack.pop(); - int cx = stack.pop(); - - // Check if close to center of the polygon. - if (rcAbs(cx-pcx) <= 1 && rcAbs(cy-pcz) <= 1) + if (array.size() < 3) { - stack.resize(0); - stack.push(cx); - stack.push(cy); - stack.push(ci); + ctx->log(RC_LOG_WARNING, "Walk towards polygon center failed to reach center"); break; } - + + ci = array.pop(); + cy = array.pop(); + cx = array.pop(); + + if (cx == pcx && cy == pcy) + break; + + // If we are already at the correct X-position, prefer direction + // directly towards the center in the Y-axis; otherwise prefer + // direction in the X-axis + int directDir; + if (cx == pcx) + directDir = rcGetDirForOffset(0, pcy > cy ? 1 : -1); + else + directDir = rcGetDirForOffset(pcx > cx ? 1 : -1, 0); + + // Push the direct dir last so we start with this on next iteration + rcSwap(dirs[directDir], dirs[3]); + const rcCompactSpan& cs = chf.spans[ci]; - - for (int dir = 0; dir < 4; ++dir) + for (int i = 0; i < 4; i++) { - if (rcGetCon(cs, dir) == RC_NOT_CONNECTED) continue; - - const int ax = cx + rcGetDirOffsetX(dir); - const int ay = cy + rcGetDirOffsetY(dir); - - if (ax < hp.xmin || ax >= (hp.xmin+hp.width) || - ay < hp.ymin || ay >= (hp.ymin+hp.height)) + int dir = dirs[i]; + if (rcGetCon(cs, dir) == RC_NOT_CONNECTED) continue; - - if (hp.data[ax-hp.xmin+(ay-hp.ymin)*hp.width] != 0) + + int newX = cx + rcGetDirOffsetX(dir); + int newY = cy + rcGetDirOffsetY(dir); + + int hpx = newX - hp.xmin; + int hpy = newY - hp.ymin; + if (hpx < 0 || hpx >= hp.width || hpy < 0 || hpy >= hp.height) continue; - - const int ai = (int)chf.cells[(ax+bs)+(ay+bs)*chf.width].index + rcGetCon(cs, dir); - - int idx = ax-hp.xmin+(ay-hp.ymin)*hp.width; - hp.data[idx] = 1; - - stack.push(ax); - stack.push(ay); - stack.push(ai); + + if (hp.data[hpx+hpy*hp.width] != 0) + continue; + + hp.data[hpx+hpy*hp.width] = 1; + array.push(newX); + array.push(newY); + array.push((int)chf.cells[(newX+bs)+(newY+bs)*chf.width].index + rcGetCon(cs, dir)); } + + rcSwap(dirs[directDir], dirs[3]); } - + + array.resize(0); + // getHeightData seeds are given in coordinates with borders + array.push(cx+bs); + array.push(cy+bs); + array.push(ci); + memset(hp.data, 0xff, sizeof(unsigned short)*hp.width*hp.height); - - // Mark start locations. - for (int i = 0; i < stack.size(); i += 3) - { - int cx = stack[i+0]; - int cy = stack[i+1]; - int ci = stack[i+2]; - int idx = cx-hp.xmin+(cy-hp.ymin)*hp.width; - const rcCompactSpan& cs = chf.spans[ci]; - hp.data[idx] = cs.y; - - // getHeightData seeds are given in coordinates with borders - stack[i+0] += bs; - stack[i+1] += bs; - } - + const rcCompactSpan& cs = chf.spans[ci]; + hp.data[cx-hp.xmin+(cy-hp.ymin)*hp.width] = cs.y; } +static void push3(rcIntArray& queue, int v1, int v2, int v3) +{ + queue.resize(queue.size() + 3); + queue[queue.size() - 3] = v1; + queue[queue.size() - 2] = v2; + queue[queue.size() - 1] = v3; +} -static void getHeightData(const rcCompactHeightfield& chf, +static void getHeightData(rcContext* ctx, const rcCompactHeightfield& chf, const unsigned short* poly, const int npoly, const unsigned short* verts, const int bs, - rcHeightPatch& hp, rcIntArray& stack, + rcHeightPatch& hp, rcIntArray& queue, int region) { // Note: Reads to the compact heightfield are offset by border size (bs) // since border size offset is already removed from the polymesh vertices. - stack.resize(0); + queue.resize(0); + // Set all heights to RC_UNSET_HEIGHT. memset(hp.data, 0xff, sizeof(unsigned short)*hp.width*hp.height); - + bool empty = true; - // Copy the height from the same region, and mark region borders - // as seed points to fill the rest. - for (int hy = 0; hy < hp.height; hy++) + // We cannot sample from this poly if it was created from polys + // of different regions. If it was then it could potentially be overlapping + // with polys of that region and the heights sampled here could be wrong. + if (region != RC_MULTIPLE_REGS) { - int y = hp.ymin + hy + bs; - for (int hx = 0; hx < hp.width; hx++) + // Copy the height from the same region, and mark region borders + // as seed points to fill the rest. + for (int hy = 0; hy < hp.height; hy++) { - int x = hp.xmin + hx + bs; - const rcCompactCell& c = chf.cells[x+y*chf.width]; - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) + int y = hp.ymin + hy + bs; + for (int hx = 0; hx < hp.width; hx++) { - const rcCompactSpan& s = chf.spans[i]; - if (s.reg == region) + int x = hp.xmin + hx + bs; + const rcCompactCell& c = chf.cells[x + y*chf.width]; + for (int i = (int)c.index, ni = (int)(c.index + c.count); i < ni; ++i) { - // Store height - hp.data[hx + hy*hp.width] = s.y; - empty = false; - - // If any of the neighbours is not in same region, - // add the current location as flood fill start - bool border = false; - for (int dir = 0; dir < 4; ++dir) + const rcCompactSpan& s = chf.spans[i]; + if (s.reg == region) { - if (rcGetCon(s, dir) != RC_NOT_CONNECTED) + // Store height + hp.data[hx + hy*hp.width] = s.y; + empty = false; + + // If any of the neighbours is not in same region, + // add the current location as flood fill start + bool border = false; + for (int dir = 0; dir < 4; ++dir) { - const int ax = x + rcGetDirOffsetX(dir); - const int ay = y + rcGetDirOffsetY(dir); - const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dir); - const rcCompactSpan& as = chf.spans[ai]; - if (as.reg != region) + if (rcGetCon(s, dir) != RC_NOT_CONNECTED) { - border = true; - break; + const int ax = x + rcGetDirOffsetX(dir); + const int ay = y + rcGetDirOffsetY(dir); + const int ai = (int)chf.cells[ax + ay*chf.width].index + rcGetCon(s, dir); + const rcCompactSpan& as = chf.spans[ai]; + if (as.reg != region) + { + border = true; + break; + } } } + if (border) + push3(queue, x, y, i); + break; } - if (border) - { - stack.push(x); - stack.push(y); - stack.push(i); - } - break; } } } } - // if the polygon does not contian any points from the current region (rare, but happens) - // then use the cells closest to the polygon vertices as seeds to fill the height field + // if the polygon does not contain any points from the current region (rare, but happens) + // or if it could potentially be overlapping polygons of the same region, + // then use the center as the seed point. if (empty) - getHeightDataSeedsFromVertices(chf, poly, npoly, verts, bs, hp, stack); + seedArrayWithPolyCenter(ctx, chf, poly, npoly, verts, bs, hp, queue); static const int RETRACT_SIZE = 256; int head = 0; - while (head*3 < stack.size()) + // We assume the seed is centered in the polygon, so a BFS to collect + // height data will ensure we do not move onto overlapping polygons and + // sample wrong heights. + while (head*3 < queue.size()) { - int cx = stack[head*3+0]; - int cy = stack[head*3+1]; - int ci = stack[head*3+2]; + int cx = queue[head*3+0]; + int cy = queue[head*3+1]; + int ci = queue[head*3+2]; head++; if (head >= RETRACT_SIZE) { head = 0; - if (stack.size() > RETRACT_SIZE*3) - memmove(&stack[0], &stack[RETRACT_SIZE*3], sizeof(int)*(stack.size()-RETRACT_SIZE*3)); - stack.resize(stack.size()-RETRACT_SIZE*3); + if (queue.size() > RETRACT_SIZE*3) + memmove(&queue[0], &queue[RETRACT_SIZE*3], sizeof(int)*(queue.size()-RETRACT_SIZE*3)); + queue.resize(queue.size()-RETRACT_SIZE*3); } const rcCompactSpan& cs = chf.spans[ci]; @@ -1067,7 +1121,7 @@ static void getHeightData(const rcCompactHeightfield& chf, const int hx = ax - hp.xmin - bs; const int hy = ay - hp.ymin - bs; - if (hx < 0 || hx >= hp.width || hy < 0 || hy >= hp.height) + if ((unsigned int)hx >= (unsigned int)hp.width || (unsigned int)hy >= (unsigned int)hp.height) continue; if (hp.data[hx + hy*hp.width] != RC_UNSET_HEIGHT) @@ -1078,9 +1132,7 @@ static void getHeightData(const rcCompactHeightfield& chf, hp.data[hx + hy*hp.width] = as.y; - stack.push(ax); - stack.push(ay); - stack.push(ai); + push3(queue, ax, ay, ai); } } } @@ -1120,7 +1172,7 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa { rcAssert(ctx); - ctx->startTimer(RC_TIMER_BUILD_POLYMESHDETAIL); + rcScopedTimer timer(ctx, RC_TIMER_BUILD_POLYMESHDETAIL); if (mesh.nverts == 0 || mesh.npolys == 0) return true; @@ -1130,23 +1182,24 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa const float ch = mesh.ch; const float* orig = mesh.bmin; const int borderSize = mesh.borderSize; + const int heightSearchRadius = rcMax(1, (int)ceilf(mesh.maxEdgeError)); rcIntArray edges(64); rcIntArray tris(512); - rcIntArray stack(512); + rcIntArray arr(512); rcIntArray samples(512); float verts[256*3]; rcHeightPatch hp; int nPolyVerts = 0; int maxhw = 0, maxhh = 0; - rcScopedDelete<int> bounds = (int*)rcAlloc(sizeof(int)*mesh.npolys*4, RC_ALLOC_TEMP); + rcScopedDelete<int> bounds((int*)rcAlloc(sizeof(int)*mesh.npolys*4, RC_ALLOC_TEMP)); if (!bounds) { ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'bounds' (%d).", mesh.npolys*4); return false; } - rcScopedDelete<float> poly = (float*)rcAlloc(sizeof(float)*nvp*3, RC_ALLOC_TEMP); + rcScopedDelete<float> poly((float*)rcAlloc(sizeof(float)*nvp*3, RC_ALLOC_TEMP)); if (!poly) { ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'poly' (%d).", nvp*3); @@ -1240,13 +1293,14 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa hp.ymin = bounds[i*4+2]; hp.width = bounds[i*4+1]-bounds[i*4+0]; hp.height = bounds[i*4+3]-bounds[i*4+2]; - getHeightData(chf, p, npoly, mesh.verts, borderSize, hp, stack, mesh.regs[i]); + getHeightData(ctx, chf, p, npoly, mesh.verts, borderSize, hp, arr, mesh.regs[i]); // Build detail mesh. int nverts = 0; if (!buildPolyDetail(ctx, poly, npoly, sampleDist, sampleMaxError, - chf, hp, verts, nverts, tris, + heightSearchRadius, chf, hp, + verts, nverts, tris, edges, samples)) { return false; @@ -1327,8 +1381,6 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa } } - ctx->stopTimer(RC_TIMER_BUILD_POLYMESHDETAIL); - return true; } @@ -1337,7 +1389,7 @@ bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int { rcAssert(ctx); - ctx->startTimer(RC_TIMER_MERGE_POLYMESHDETAIL); + rcScopedTimer timer(ctx, RC_TIMER_MERGE_POLYMESHDETAIL); int maxVerts = 0; int maxTris = 0; @@ -1406,7 +1458,5 @@ bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int } } - ctx->stopTimer(RC_TIMER_MERGE_POLYMESHDETAIL); - return true; } diff --git a/dep/recastnavigation/Recast/Source/RecastRasterization.cpp b/dep/recastnavigation/Recast/Source/RecastRasterization.cpp index c3bda80cd71..a4cef749098 100644 --- a/dep/recastnavigation/Recast/Source/RecastRasterization.cpp +++ b/dep/recastnavigation/Recast/Source/RecastRasterization.cpp @@ -82,7 +82,7 @@ static void freeSpan(rcHeightfield& hf, rcSpan* ptr) hf.freelist = ptr; } -static void addSpan(rcHeightfield& hf, const int x, const int y, +static bool addSpan(rcHeightfield& hf, const int x, const int y, const unsigned short smin, const unsigned short smax, const unsigned char area, const int flagMergeThr) { @@ -90,6 +90,8 @@ static void addSpan(rcHeightfield& hf, const int x, const int y, int idx = x + y*hf.width; rcSpan* s = allocSpan(hf); + if (!s) + return false; s->smin = smin; s->smax = smax; s->area = area; @@ -99,7 +101,7 @@ static void addSpan(rcHeightfield& hf, const int x, const int y, if (!hf.spans[idx]) { hf.spans[idx] = s; - return; + return true; } rcSpan* prev = 0; rcSpan* cur = hf.spans[idx]; @@ -152,6 +154,8 @@ static void addSpan(rcHeightfield& hf, const int x, const int y, s->next = hf.spans[idx]; hf.spans[idx] = s; } + + return true; } /// @par @@ -161,12 +165,19 @@ static void addSpan(rcHeightfield& hf, const int x, const int y, /// from the existing span, the span flags are merged. /// /// @see rcHeightfield, rcSpan. -void rcAddSpan(rcContext* /*ctx*/, rcHeightfield& hf, const int x, const int y, +bool rcAddSpan(rcContext* ctx, rcHeightfield& hf, const int x, const int y, const unsigned short smin, const unsigned short smax, const unsigned char area, const int flagMergeThr) { -// rcAssert(ctx); - addSpan(hf, x,y, smin, smax, area, flagMergeThr); + rcAssert(ctx); + + if (!addSpan(hf, x, y, smin, smax, area, flagMergeThr)) + { + ctx->log(RC_LOG_ERROR, "rcAddSpan: Out of memory."); + return false; + } + + return true; } // divides a convex polygons into two convex polygons on both sides of a line @@ -227,7 +238,7 @@ static void dividePoly(const float* in, int nin, -static void rasterizeTri(const float* v0, const float* v1, const float* v2, +static bool rasterizeTri(const float* v0, const float* v1, const float* v2, const unsigned char area, rcHeightfield& hf, const float* bmin, const float* bmax, const float cs, const float ics, const float ich, @@ -248,7 +259,7 @@ static void rasterizeTri(const float* v0, const float* v1, const float* v2, // If the triangle does not touch the bbox of the heightfield, skip the triagle. if (!overlapBounds(bmin, bmax, tmin, tmax)) - return; + return true; // Calculate the footprint of the triangle on the grid's y-axis int y0 = (int)((tmin[2] - bmin[2])*ics); @@ -315,9 +326,12 @@ static void rasterizeTri(const float* v0, const float* v1, const float* v2, unsigned short ismin = (unsigned short)rcClamp((int)floorf(smin * ich), 0, RC_SPAN_MAX_HEIGHT); unsigned short ismax = (unsigned short)rcClamp((int)ceilf(smax * ich), (int)ismin+1, RC_SPAN_MAX_HEIGHT); - addSpan(hf, x, y, ismin, ismax, area, flagMergeThr); + if (!addSpan(hf, x, y, ismin, ismax, area, flagMergeThr)) + return false; } } + + return true; } /// @par @@ -325,19 +339,23 @@ static void rasterizeTri(const float* v0, const float* v1, const float* v2, /// No spans will be added if the triangle does not overlap the heightfield grid. /// /// @see rcHeightfield -void rcRasterizeTriangle(rcContext* ctx, const float* v0, const float* v1, const float* v2, +bool rcRasterizeTriangle(rcContext* ctx, const float* v0, const float* v1, const float* v2, const unsigned char area, rcHeightfield& solid, const int flagMergeThr) { rcAssert(ctx); - ctx->startTimer(RC_TIMER_RASTERIZE_TRIANGLES); + rcScopedTimer timer(ctx, RC_TIMER_RASTERIZE_TRIANGLES); const float ics = 1.0f/solid.cs; const float ich = 1.0f/solid.ch; - rasterizeTri(v0, v1, v2, area, solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr); + if (!rasterizeTri(v0, v1, v2, area, solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr)) + { + ctx->log(RC_LOG_ERROR, "rcRasterizeTriangle: Out of memory."); + return false; + } - ctx->stopTimer(RC_TIMER_RASTERIZE_TRIANGLES); + return true; } /// @par @@ -345,13 +363,13 @@ void rcRasterizeTriangle(rcContext* ctx, const float* v0, const float* v1, const /// Spans will only be added for triangles that overlap the heightfield grid. /// /// @see rcHeightfield -void rcRasterizeTriangles(rcContext* ctx, const float* verts, const int /*nv*/, +bool rcRasterizeTriangles(rcContext* ctx, const float* verts, const int /*nv*/, const int* tris, const unsigned char* areas, const int nt, rcHeightfield& solid, const int flagMergeThr) { rcAssert(ctx); - ctx->startTimer(RC_TIMER_RASTERIZE_TRIANGLES); + rcScopedTimer timer(ctx, RC_TIMER_RASTERIZE_TRIANGLES); const float ics = 1.0f/solid.cs; const float ich = 1.0f/solid.ch; @@ -362,10 +380,14 @@ void rcRasterizeTriangles(rcContext* ctx, const float* verts, const int /*nv*/, const float* v1 = &verts[tris[i*3+1]*3]; const float* v2 = &verts[tris[i*3+2]*3]; // Rasterize. - rasterizeTri(v0, v1, v2, areas[i], solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr); + if (!rasterizeTri(v0, v1, v2, areas[i], solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr)) + { + ctx->log(RC_LOG_ERROR, "rcRasterizeTriangles: Out of memory."); + return false; + } } - - ctx->stopTimer(RC_TIMER_RASTERIZE_TRIANGLES); + + return true; } /// @par @@ -373,13 +395,13 @@ void rcRasterizeTriangles(rcContext* ctx, const float* verts, const int /*nv*/, /// Spans will only be added for triangles that overlap the heightfield grid. /// /// @see rcHeightfield -void rcRasterizeTriangles(rcContext* ctx, const float* verts, const int /*nv*/, +bool rcRasterizeTriangles(rcContext* ctx, const float* verts, const int /*nv*/, const unsigned short* tris, const unsigned char* areas, const int nt, rcHeightfield& solid, const int flagMergeThr) { rcAssert(ctx); - ctx->startTimer(RC_TIMER_RASTERIZE_TRIANGLES); + rcScopedTimer timer(ctx, RC_TIMER_RASTERIZE_TRIANGLES); const float ics = 1.0f/solid.cs; const float ich = 1.0f/solid.ch; @@ -390,10 +412,14 @@ void rcRasterizeTriangles(rcContext* ctx, const float* verts, const int /*nv*/, const float* v1 = &verts[tris[i*3+1]*3]; const float* v2 = &verts[tris[i*3+2]*3]; // Rasterize. - rasterizeTri(v0, v1, v2, areas[i], solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr); + if (!rasterizeTri(v0, v1, v2, areas[i], solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr)) + { + ctx->log(RC_LOG_ERROR, "rcRasterizeTriangles: Out of memory."); + return false; + } } - - ctx->stopTimer(RC_TIMER_RASTERIZE_TRIANGLES); + + return true; } /// @par @@ -401,12 +427,12 @@ void rcRasterizeTriangles(rcContext* ctx, const float* verts, const int /*nv*/, /// Spans will only be added for triangles that overlap the heightfield grid. /// /// @see rcHeightfield -void rcRasterizeTriangles(rcContext* ctx, const float* verts, const unsigned char* areas, const int nt, +bool rcRasterizeTriangles(rcContext* ctx, const float* verts, const unsigned char* areas, const int nt, rcHeightfield& solid, const int flagMergeThr) { rcAssert(ctx); - ctx->startTimer(RC_TIMER_RASTERIZE_TRIANGLES); + rcScopedTimer timer(ctx, RC_TIMER_RASTERIZE_TRIANGLES); const float ics = 1.0f/solid.cs; const float ich = 1.0f/solid.ch; @@ -417,8 +443,12 @@ void rcRasterizeTriangles(rcContext* ctx, const float* verts, const unsigned cha const float* v1 = &verts[(i*3+1)*3]; const float* v2 = &verts[(i*3+2)*3]; // Rasterize. - rasterizeTri(v0, v1, v2, areas[i], solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr); + if (!rasterizeTri(v0, v1, v2, areas[i], solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr)) + { + ctx->log(RC_LOG_ERROR, "rcRasterizeTriangles: Out of memory."); + return false; + } } - - ctx->stopTimer(RC_TIMER_RASTERIZE_TRIANGLES); + + return true; } diff --git a/dep/recastnavigation/Recast/Source/RecastRegion.cpp b/dep/recastnavigation/Recast/Source/RecastRegion.cpp index 352ba579e5f..4a87133f2a8 100644 --- a/dep/recastnavigation/Recast/Source/RecastRegion.cpp +++ b/dep/recastnavigation/Recast/Source/RecastRegion.cpp @@ -1257,7 +1257,7 @@ bool rcBuildDistanceField(rcContext* ctx, rcCompactHeightfield& chf) { rcAssert(ctx); - ctx->startTimer(RC_TIMER_BUILD_DISTANCEFIELD); + rcScopedTimer timer(ctx, RC_TIMER_BUILD_DISTANCEFIELD); if (chf.dist) { @@ -1281,25 +1281,23 @@ bool rcBuildDistanceField(rcContext* ctx, rcCompactHeightfield& chf) unsigned short maxDist = 0; - ctx->startTimer(RC_TIMER_BUILD_DISTANCEFIELD_DIST); - - calculateDistanceField(chf, src, maxDist); - chf.maxDistance = maxDist; - - ctx->stopTimer(RC_TIMER_BUILD_DISTANCEFIELD_DIST); - - ctx->startTimer(RC_TIMER_BUILD_DISTANCEFIELD_BLUR); - - // Blur - if (boxBlur(chf, 1, src, dst) != src) - rcSwap(src, dst); - - // Store distance. - chf.dist = src; - - ctx->stopTimer(RC_TIMER_BUILD_DISTANCEFIELD_BLUR); + { + rcScopedTimer timerDist(ctx, RC_TIMER_BUILD_DISTANCEFIELD_DIST); - ctx->stopTimer(RC_TIMER_BUILD_DISTANCEFIELD); + calculateDistanceField(chf, src, maxDist); + chf.maxDistance = maxDist; + } + + { + rcScopedTimer timerBlur(ctx, RC_TIMER_BUILD_DISTANCEFIELD_BLUR); + + // Blur + if (boxBlur(chf, 1, src, dst) != src) + rcSwap(src, dst); + + // Store distance. + chf.dist = src; + } rcFree(dst); @@ -1359,13 +1357,13 @@ bool rcBuildRegionsMonotone(rcContext* ctx, rcCompactHeightfield& chf, { rcAssert(ctx); - ctx->startTimer(RC_TIMER_BUILD_REGIONS); + rcScopedTimer timer(ctx, RC_TIMER_BUILD_REGIONS); const int w = chf.width; const int h = chf.height; unsigned short id = 1; - rcScopedDelete<unsigned short> srcReg = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP); + rcScopedDelete<unsigned short> srcReg((unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP)); if (!srcReg) { ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'src' (%d).", chf.spanCount); @@ -1374,7 +1372,7 @@ bool rcBuildRegionsMonotone(rcContext* ctx, rcCompactHeightfield& chf, memset(srcReg,0,sizeof(unsigned short)*chf.spanCount); const int nsweeps = rcMax(chf.width,chf.height); - rcScopedDelete<rcSweepSpan> sweeps = (rcSweepSpan*)rcAlloc(sizeof(rcSweepSpan)*nsweeps, RC_ALLOC_TEMP); + rcScopedDelete<rcSweepSpan> sweeps((rcSweepSpan*)rcAlloc(sizeof(rcSweepSpan)*nsweeps, RC_ALLOC_TEMP)); if (!sweeps) { ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'sweeps' (%d).", nsweeps); @@ -1489,23 +1487,21 @@ bool rcBuildRegionsMonotone(rcContext* ctx, rcCompactHeightfield& chf, } - ctx->startTimer(RC_TIMER_BUILD_REGIONS_FILTER); + { + rcScopedTimer timerFilter(ctx, RC_TIMER_BUILD_REGIONS_FILTER); - // Merge regions and filter out small regions. - rcIntArray overlaps; - chf.maxRegions = id; - if (!mergeAndFilterRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg, overlaps)) - return false; + // Merge regions and filter out small regions. + rcIntArray overlaps; + chf.maxRegions = id; + if (!mergeAndFilterRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg, overlaps)) + return false; - // Monotone partitioning does not generate overlapping regions. - - ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FILTER); + // Monotone partitioning does not generate overlapping regions. + } // Store the result out. for (int i = 0; i < chf.spanCount; ++i) chf.spans[i].reg = srcReg[i]; - - ctx->stopTimer(RC_TIMER_BUILD_REGIONS); return true; } @@ -1534,12 +1530,12 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf, { rcAssert(ctx); - ctx->startTimer(RC_TIMER_BUILD_REGIONS); + rcScopedTimer timer(ctx, RC_TIMER_BUILD_REGIONS); const int w = chf.width; const int h = chf.height; - rcScopedDelete<unsigned short> buf = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount*4, RC_ALLOC_TEMP); + rcScopedDelete<unsigned short> buf((unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount*4, RC_ALLOC_TEMP)); if (!buf) { ctx->log(RC_LOG_ERROR, "rcBuildRegions: Out of memory 'tmp' (%d).", chf.spanCount*4); @@ -1579,6 +1575,7 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf, // Make sure border will not overflow. const int bw = rcMin(w, borderSize); const int bh = rcMin(h, borderSize); + // Paint regions paintRectRegion(0, bw, 0, h, regionId|RC_BORDER_REG, chf, srcReg); regionId++; paintRectRegion(w-bw, w, 0, h, regionId|RC_BORDER_REG, chf, srcReg); regionId++; @@ -1603,33 +1600,41 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf, // ctx->stopTimer(RC_TIMER_DIVIDE_TO_LEVELS); - ctx->startTimer(RC_TIMER_BUILD_REGIONS_EXPAND); - - // Expand current regions until no empty connected cells found. - if (expandRegions(expandIters, level, chf, srcReg, srcDist, dstReg, dstDist, lvlStacks[sId], false) != srcReg) { - rcSwap(srcReg, dstReg); - rcSwap(srcDist, dstDist); + rcScopedTimer timerExpand(ctx, RC_TIMER_BUILD_REGIONS_EXPAND); + + // Expand current regions until no empty connected cells found. + if (expandRegions(expandIters, level, chf, srcReg, srcDist, dstReg, dstDist, lvlStacks[sId], false) != srcReg) + { + rcSwap(srcReg, dstReg); + rcSwap(srcDist, dstDist); + } } - ctx->stopTimer(RC_TIMER_BUILD_REGIONS_EXPAND); - - ctx->startTimer(RC_TIMER_BUILD_REGIONS_FLOOD); - - // Mark new regions with IDs. - for (int j=0; j<lvlStacks[sId].size(); j+=3) { - int x = lvlStacks[sId][j]; - int y = lvlStacks[sId][j+1]; - int i = lvlStacks[sId][j+2]; - if (i >= 0 && srcReg[i] == 0) + rcScopedTimer timerFloor(ctx, RC_TIMER_BUILD_REGIONS_FLOOD); + + // Mark new regions with IDs. + for (int j = 0; j<lvlStacks[sId].size(); j += 3) { - if (floodRegion(x, y, i, level, regionId, chf, srcReg, srcDist, stack)) - regionId++; + int x = lvlStacks[sId][j]; + int y = lvlStacks[sId][j+1]; + int i = lvlStacks[sId][j+2]; + if (i >= 0 && srcReg[i] == 0) + { + if (floodRegion(x, y, i, level, regionId, chf, srcReg, srcDist, stack)) + { + if (regionId == 0xFFFF) + { + ctx->log(RC_LOG_ERROR, "rcBuildRegions: Region ID overflow"); + return false; + } + + regionId++; + } + } } } - - ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FLOOD); } // Expand current regions until no empty connected cells found. @@ -1641,28 +1646,26 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf, ctx->stopTimer(RC_TIMER_BUILD_REGIONS_WATERSHED); - ctx->startTimer(RC_TIMER_BUILD_REGIONS_FILTER); - - // Merge regions and filter out smalle regions. - rcIntArray overlaps; - chf.maxRegions = regionId; - if (!mergeAndFilterRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg, overlaps)) - return false; - - // If overlapping regions were found during merging, split those regions. - if (overlaps.size() > 0) { - ctx->log(RC_LOG_ERROR, "rcBuildRegions: %d overlapping regions.", overlaps.size()); - } + rcScopedTimer timerFilter(ctx, RC_TIMER_BUILD_REGIONS_FILTER); + + // Merge regions and filter out smalle regions. + rcIntArray overlaps; + chf.maxRegions = regionId; + if (!mergeAndFilterRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg, overlaps)) + return false; - ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FILTER); + // If overlapping regions were found during merging, split those regions. + if (overlaps.size() > 0) + { + ctx->log(RC_LOG_ERROR, "rcBuildRegions: %d overlapping regions.", overlaps.size()); + } + } // Write the result out. for (int i = 0; i < chf.spanCount; ++i) chf.spans[i].reg = srcReg[i]; - ctx->stopTimer(RC_TIMER_BUILD_REGIONS); - return true; } @@ -1672,13 +1675,13 @@ bool rcBuildLayerRegions(rcContext* ctx, rcCompactHeightfield& chf, { rcAssert(ctx); - ctx->startTimer(RC_TIMER_BUILD_REGIONS); + rcScopedTimer timer(ctx, RC_TIMER_BUILD_REGIONS); const int w = chf.width; const int h = chf.height; unsigned short id = 1; - rcScopedDelete<unsigned short> srcReg = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP); + rcScopedDelete<unsigned short> srcReg((unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP)); if (!srcReg) { ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'src' (%d).", chf.spanCount); @@ -1687,7 +1690,7 @@ bool rcBuildLayerRegions(rcContext* ctx, rcCompactHeightfield& chf, memset(srcReg,0,sizeof(unsigned short)*chf.spanCount); const int nsweeps = rcMax(chf.width,chf.height); - rcScopedDelete<rcSweepSpan> sweeps = (rcSweepSpan*)rcAlloc(sizeof(rcSweepSpan)*nsweeps, RC_ALLOC_TEMP); + rcScopedDelete<rcSweepSpan> sweeps((rcSweepSpan*)rcAlloc(sizeof(rcSweepSpan)*nsweeps, RC_ALLOC_TEMP)); if (!sweeps) { ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'sweeps' (%d).", nsweeps); @@ -1802,22 +1805,20 @@ bool rcBuildLayerRegions(rcContext* ctx, rcCompactHeightfield& chf, } - ctx->startTimer(RC_TIMER_BUILD_REGIONS_FILTER); - - // Merge monotone regions to layers and remove small regions. - rcIntArray overlaps; - chf.maxRegions = id; - if (!mergeAndFilterLayerRegions(ctx, minRegionArea, chf.maxRegions, chf, srcReg, overlaps)) - return false; - - ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FILTER); + { + rcScopedTimer timerFilter(ctx, RC_TIMER_BUILD_REGIONS_FILTER); + + // Merge monotone regions to layers and remove small regions. + rcIntArray overlaps; + chf.maxRegions = id; + if (!mergeAndFilterLayerRegions(ctx, minRegionArea, chf.maxRegions, chf, srcReg, overlaps)) + return false; + } // Store the result out. for (int i = 0; i < chf.spanCount; ++i) chf.spans[i].reg = srcReg[i]; - ctx->stopTimer(RC_TIMER_BUILD_REGIONS); - return true; } diff --git a/dep/recastnavigation/recastnavigation.diff b/dep/recastnavigation/recastnavigation.diff index 0be25bc11d1..fe0c44a420e 100644 --- a/dep/recastnavigation/recastnavigation.diff +++ b/dep/recastnavigation/recastnavigation.diff @@ -1,37 +1,29 @@ -From 37b4c6d3d78ea676d8b300a282013a27a51912c1 Mon Sep 17 00:00:00 2001 +From 3790dbcc9cd4bdebbd3257ac8f3f9f28a0cf0485 Mon Sep 17 00:00:00 2001 From: jackpoz <giacomopoz@gmail.com> Date: Fri, 20 Jun 2014 23:15:04 +0200 Subject: [PATCH] Add custom trinitycore changes --- - Detour/Include/DetourNavMesh.h | 76 ++++++++++++------------------------ - Detour/Source/DetourNavMesh.cpp | 30 +++++--------- - Detour/Source/DetourNavMeshQuery.cpp | 5 ++- - Detour/Source/DetourNode.cpp | 29 ++++---------- - Recast/Include/Recast.h | 8 ++-- - Recast/Source/RecastMeshDetail.cpp | 2 +- - Recast/Source/RecastRegion.cpp | 2 +- - 7 files changed, 50 insertions(+), 102 deletions(-) + Detour/Include/DetourNavMesh.h | 24 ++++++++++++++++++------ + Detour/Source/DetourNavMeshQuery.cpp | 4 ++-- + Recast/Include/Recast.h | 4 ++-- + 3 files changed, 22 insertions(+), 10 deletions(-) diff --git a/Detour/Include/DetourNavMesh.h b/Detour/Include/DetourNavMesh.h -index 1060845..782ddbc 100644 +index 8ecd57e..f50f705 100644 --- a/Detour/Include/DetourNavMesh.h +++ b/Detour/Include/DetourNavMesh.h -@@ -22,39 +22,35 @@ - #include "DetourAlloc.h" - #include "DetourStatus.h" - --// Undefine (or define in a build cofnig) the following line to use 64bit polyref. --// Generally not needed, useful for very large worlds. --// Note: tiles build using 32bit refs are not compatible with 64bit refs! +@@ -25,13 +25,25 @@ + // Undefine (or define in a build cofnig) the following line to use 64bit polyref. + // Generally not needed, useful for very large worlds. + // Note: tiles build using 32bit refs are not compatible with 64bit refs! -//#define DT_POLYREF64 1 -- --#ifdef DT_POLYREF64 --// TODO: figure out a multiplatform version of uint64_t --// - maybe: https://code.google.com/p/msinttypes/ --// - or: http://www.azillionmonkeys.com/qed/pstdint.h -+ -+// Edited by TC ++#define DT_POLYREF64 1 + + #ifdef DT_POLYREF64 + // TODO: figure out a multiplatform version of uint64_t + // - maybe: https://code.google.com/p/msinttypes/ + // - or: http://www.azillionmonkeys.com/qed/pstdint.h +#if defined(WIN32) && !defined(__MINGW32__) +/// Do not rename back to uint64. Otherwise mac complains about typedef redefinition +typedef unsigned __int64 uint64_d; @@ -41,213 +33,51 @@ index 1060845..782ddbc 100644 +#ifdef __linux__ +#include <linux/types.h> +#endif - #endif ++#endif +/// Do not rename back to uint64. Otherwise mac complains about typedef redefinition +typedef uint64_t uint64_d; +#endif + #endif // Note: If you want to use 64-bit refs, change the types of both dtPolyRef & dtTileRef. - // It is also recommended that you change dtHashRef() to a proper 64-bit hash. - -+// Edited by TC -+// We cannot have over 31 bits for either tile nor poly -+// without changing polyCount to use 64bits too. +@@ -40,10 +52,10 @@ /// A handle to a polygon within a navigation mesh tile. /// @ingroup detour --#ifdef DT_POLYREF64 + #ifdef DT_POLYREF64 -static const unsigned int DT_SALT_BITS = 16; -static const unsigned int DT_TILE_BITS = 28; -static const unsigned int DT_POLY_BITS = 20; -typedef uint64_t dtPolyRef; --#else --typedef unsigned int dtPolyRef; --#endif -+typedef uint64_d dtPolyRef; // Edited by TC - ++static const unsigned int DT_SALT_BITS = 12; ++static const unsigned int DT_TILE_BITS = 21; ++static const unsigned int DT_POLY_BITS = 31; ++typedef uint64_d dtPolyRef; + #else + typedef unsigned int dtPolyRef; + #endif +@@ -51,7 +63,7 @@ typedef unsigned int dtPolyRef; /// A handle to a tile within a navigation mesh. /// @ingroup detour --#ifdef DT_POLYREF64 + #ifdef DT_POLYREF64 -typedef uint64_t dtTileRef; --#else --typedef unsigned int dtTileRef; --#endif -+typedef uint64_d dtTileRef; // Edited by TC - - /// The maximum number of vertices per navigation polygon. - /// @ingroup detour -@@ -94,6 +90,12 @@ static const unsigned int DT_OFFMESH_CON_BIDIR = 1; - /// @ingroup detour - static const int DT_MAX_AREAS = 64; - -+static const int STATIC_SALT_BITS = 12; -+static const int STATIC_TILE_BITS = 21; -+static const int STATIC_POLY_BITS = 31; -+// we cannot have over 31 bits for either tile nor poly -+// without changing polyCount to use 64bits too. -+ - /// Tile flags used for various functions and fields. - /// For an example, see dtNavMesh::addTile(). - enum dtTileFlags -@@ -511,11 +513,7 @@ public: - /// @param[in] ip The index of the polygon within the tile. - inline dtPolyRef encodePolyId(unsigned int salt, unsigned int it, unsigned int ip) const - { --#ifdef DT_POLYREF64 -- return ((dtPolyRef)salt << (DT_POLY_BITS+DT_TILE_BITS)) | ((dtPolyRef)it << DT_POLY_BITS) | (dtPolyRef)ip; --#else - return ((dtPolyRef)salt << (m_polyBits+m_tileBits)) | ((dtPolyRef)it << m_polyBits) | (dtPolyRef)ip; --#endif - } - - /// Decodes a standard polygon reference. -@@ -527,21 +525,12 @@ public: - /// @see #encodePolyId - inline void decodePolyId(dtPolyRef ref, unsigned int& salt, unsigned int& it, unsigned int& ip) const - { --#ifdef DT_POLYREF64 -- const dtPolyRef saltMask = ((dtPolyRef)1<<DT_SALT_BITS)-1; -- const dtPolyRef tileMask = ((dtPolyRef)1<<DT_TILE_BITS)-1; -- const dtPolyRef polyMask = ((dtPolyRef)1<<DT_POLY_BITS)-1; -- salt = (unsigned int)((ref >> (DT_POLY_BITS+DT_TILE_BITS)) & saltMask); -- it = (unsigned int)((ref >> DT_POLY_BITS) & tileMask); -- ip = (unsigned int)(ref & polyMask); --#else - const dtPolyRef saltMask = ((dtPolyRef)1<<m_saltBits)-1; - const dtPolyRef tileMask = ((dtPolyRef)1<<m_tileBits)-1; - const dtPolyRef polyMask = ((dtPolyRef)1<<m_polyBits)-1; - salt = (unsigned int)((ref >> (m_polyBits+m_tileBits)) & saltMask); - it = (unsigned int)((ref >> m_polyBits) & tileMask); - ip = (unsigned int)(ref & polyMask); --#endif - } - - /// Extracts a tile's salt value from the specified polygon reference. -@@ -550,13 +539,8 @@ public: - /// @see #encodePolyId - inline unsigned int decodePolyIdSalt(dtPolyRef ref) const - { --#ifdef DT_POLYREF64 -- const dtPolyRef saltMask = ((dtPolyRef)1<<DT_SALT_BITS)-1; -- return (unsigned int)((ref >> (DT_POLY_BITS+DT_TILE_BITS)) & saltMask); --#else - const dtPolyRef saltMask = ((dtPolyRef)1<<m_saltBits)-1; - return (unsigned int)((ref >> (m_polyBits+m_tileBits)) & saltMask); --#endif - } - - /// Extracts the tile's index from the specified polygon reference. -@@ -565,13 +549,8 @@ public: - /// @see #encodePolyId - inline unsigned int decodePolyIdTile(dtPolyRef ref) const - { --#ifdef DT_POLYREF64 -- const dtPolyRef tileMask = ((dtPolyRef)1<<DT_TILE_BITS)-1; -- return (unsigned int)((ref >> DT_POLY_BITS) & tileMask); --#else - const dtPolyRef tileMask = ((dtPolyRef)1<<m_tileBits)-1; - return (unsigned int)((ref >> m_polyBits) & tileMask); --#endif - } - - /// Extracts the polygon's index (within its tile) from the specified polygon reference. -@@ -580,13 +559,8 @@ public: - /// @see #encodePolyId - inline unsigned int decodePolyIdPoly(dtPolyRef ref) const - { --#ifdef DT_POLYREF64 -- const dtPolyRef polyMask = ((dtPolyRef)1<<DT_POLY_BITS)-1; -- return (unsigned int)(ref & polyMask); --#else - const dtPolyRef polyMask = ((dtPolyRef)1<<m_polyBits)-1; - return (unsigned int)(ref & polyMask); --#endif - } - - /// @} -@@ -645,11 +619,9 @@ private: - dtMeshTile* m_nextFree; ///< Freelist of tiles. - dtMeshTile* m_tiles; ///< List of tiles. - --#ifndef DT_POLYREF64 - unsigned int m_saltBits; ///< Number of salt bits in the tile ID. - unsigned int m_tileBits; ///< Number of tile bits in the tile ID. - unsigned int m_polyBits; ///< Number of poly bits in the tile ID. --#endif - }; - - /// Allocates a navigation mesh object using the Detour allocator. -diff --git a/Detour/Source/DetourNavMesh.cpp b/Detour/Source/DetourNavMesh.cpp -index d353d08..e8a679b 100644 ---- a/Detour/Source/DetourNavMesh.cpp -+++ b/Detour/Source/DetourNavMesh.cpp -@@ -193,13 +193,11 @@ dtNavMesh::dtNavMesh() : - m_tileLutMask(0), - m_posLookup(0), - m_nextFree(0), -- m_tiles(0) -+ m_tiles(0), -+ m_saltBits(0), -+ m_tileBits(0), -+ m_polyBits(0) - { --#ifndef DT_POLYREF64 -- m_saltBits = 0; -- m_tileBits = 0; -- m_polyBits = 0; --#endif - memset(&m_params, 0, sizeof(dtNavMeshParams)); - m_orig[0] = 0; - m_orig[1] = 0; -@@ -250,17 +248,11 @@ dtStatus dtNavMesh::init(const dtNavMeshParams* params) - m_nextFree = &m_tiles[i]; - } - -- // Init ID generator values. --#ifndef DT_POLYREF64 -- m_tileBits = dtIlog2(dtNextPow2((unsigned int)params->maxTiles)); -- m_polyBits = dtIlog2(dtNextPow2((unsigned int)params->maxPolys)); -- // Only allow 31 salt bits, since the salt mask is calculated using 32bit uint and it will overflow. -- m_saltBits = dtMin((unsigned int)31, 32 - m_tileBits - m_polyBits); -- -- if (m_saltBits < 10) -- return DT_FAILURE | DT_INVALID_PARAM; --#endif -- -+ // Edited by TC -+ m_tileBits = STATIC_TILE_BITS; -+ m_polyBits = STATIC_POLY_BITS; -+ m_saltBits = STATIC_SALT_BITS; -+ - return DT_SUCCESS; - } - -@@ -1242,11 +1234,7 @@ dtStatus dtNavMesh::removeTile(dtTileRef ref, unsigned char** data, int* dataSiz - tile->offMeshCons = 0; - - // Update salt, salt should never be zero. --#ifdef DT_POLYREF64 -- tile->salt = (tile->salt+1) & ((1<<DT_SALT_BITS)-1); --#else - tile->salt = (tile->salt+1) & ((1<<m_saltBits)-1); --#endif - if (tile->salt == 0) - tile->salt++; - ++typedef uint64_d dtTileRef; + #else + typedef unsigned int dtTileRef; + #endif diff --git a/Detour/Source/DetourNavMeshQuery.cpp b/Detour/Source/DetourNavMeshQuery.cpp -index 5fbc83e..fbf3724 100644 +index 75af102..a263106 100644 --- a/Detour/Source/DetourNavMeshQuery.cpp +++ b/Detour/Source/DetourNavMeshQuery.cpp -@@ -100,7 +100,8 @@ inline float dtQueryFilter::getCost(const float* pa, const float* pb, +@@ -100,7 +100,7 @@ inline float dtQueryFilter::getCost(const float* pa, const float* pb, } #endif -static const float H_SCALE = 0.999f; // Search heuristic scale. -+// Edited by TC +static const float H_SCALE = 2.0f; // Search heuristic scale. dtNavMeshQuery* dtAllocNavMeshQuery() -@@ -3501,7 +3502,7 @@ dtStatus dtNavMeshQuery::findDistanceToWall(dtPolyRef startRef, const float* cen +@@ -3623,7 +3623,7 @@ dtStatus dtNavMeshQuery::findDistanceToWall(dtPolyRef startRef, const float* cen dtVsub(hitNormal, centerPos, hitPos); dtVnormalize(hitNormal); @@ -256,101 +86,28 @@ index 5fbc83e..fbf3724 100644 return status; } -diff --git a/Detour/Source/DetourNode.cpp b/Detour/Source/DetourNode.cpp -index 5cf6548..1d18977 100644 ---- a/Detour/Source/DetourNode.cpp -+++ b/Detour/Source/DetourNode.cpp -@@ -22,30 +22,17 @@ - #include "DetourCommon.h" - #include <string.h> - --#ifdef DT_POLYREF64 --// From Thomas Wang, https://gist.github.com/badboy/6267743 - inline unsigned int dtHashRef(dtPolyRef a) - { -- a = (~a) + (a << 18); // a = (a << 18) - a - 1; -- a = a ^ (a >> 31); -- a = a * 21; // a = (a + (a << 2)) + (a << 4); -- a = a ^ (a >> 11); -- a = a + (a << 6); -- a = a ^ (a >> 22); -- return (unsigned int)a; -+ // Edited by TC -+ a = (~a) + (a << 18); -+ a = a ^ (a >> 31); -+ a = a * 21; -+ a = a ^ (a >> 11); -+ a = a + (a << 6); -+ a = a ^ (a >> 22); -+ return (unsigned int)a; - } --#else --inline unsigned int dtHashRef(dtPolyRef a) --{ -- a += ~(a<<15); -- a ^= (a>>10); -- a += (a<<3); -- a ^= (a>>6); -- a += ~(a<<11); -- a ^= (a>>16); -- return (unsigned int)a; --} --#endif - - ////////////////////////////////////////////////////////////////////////////////////////// - dtNodePool::dtNodePool(int maxNodes, int hashSize) : diff --git a/Recast/Include/Recast.h b/Recast/Include/Recast.h -index d8bdde2..d3e9219 100644 +index e85c0d2..79d77e4 100644 --- a/Recast/Include/Recast.h +++ b/Recast/Include/Recast.h -@@ -243,7 +243,7 @@ struct rcConfig +@@ -263,7 +263,7 @@ struct rcConfig }; /// Defines the number of bits allocated to rcSpan::smin and rcSpan::smax. -static const int RC_SPAN_HEIGHT_BITS = 13; -+static const int RC_SPAN_HEIGHT_BITS = 16; // EDITED BY TC ++static const int RC_SPAN_HEIGHT_BITS = 16; /// Defines the maximum value for rcSpan::smin and rcSpan::smax. - static const int RC_SPAN_MAX_HEIGHT = (1<<RC_SPAN_HEIGHT_BITS)-1; + static const int RC_SPAN_MAX_HEIGHT = (1 << RC_SPAN_HEIGHT_BITS) - 1; -@@ -255,9 +255,9 @@ static const int RC_SPANS_PER_POOL = 2048; - /// @see rcHeightfield - struct rcSpan +@@ -277,7 +277,7 @@ struct rcSpan { -- unsigned int smin : 13; ///< The lower limit of the span. [Limit: < #smax] -- unsigned int smax : 13; ///< The upper limit of the span. [Limit: <= #RC_SPAN_MAX_HEIGHT] -- unsigned int area : 6; ///< The area id assigned to the span. -+ unsigned int smin : 16; ///< The lower limit of the span. [Limit: < #smax] -+ unsigned int smax : 16; ///< The upper limit of the span. [Limit: <= #RC_SPAN_MAX_HEIGHT] -+ unsigned char area; ///< The area id assigned to the span. - rcSpan* next; ///< The next span higher up in column. + unsigned int smin : RC_SPAN_HEIGHT_BITS; ///< The lower limit of the span. [Limit: < #smax] + unsigned int smax : RC_SPAN_HEIGHT_BITS; ///< The upper limit of the span. [Limit: <= #RC_SPAN_MAX_HEIGHT] +- unsigned int area : 6; ///< The area id assigned to the span. ++ unsigned char area; ///< The area id assigned to the span. + rcSpan* next; ///< The next span higher up in column. }; -diff --git a/Recast/Source/RecastMeshDetail.cpp b/Recast/Source/RecastMeshDetail.cpp -index c0bba6f..56b059d 100644 ---- a/Recast/Source/RecastMeshDetail.cpp -+++ b/Recast/Source/RecastMeshDetail.cpp -@@ -511,7 +511,7 @@ static float polyMinExtent(const float* verts, const int nverts) - inline int prev(int i, int n) { return i-1 >= 0 ? i-1 : n-1; } - inline int next(int i, int n) { return i+1 < n ? i+1 : 0; } - --static void triangulateHull(const int nverts, const float* verts, const int nhull, const int* hull, rcIntArray& tris) -+static void triangulateHull(const int /*nverts*/, const float* verts, const int nhull, const int* hull, rcIntArray& tris) - { - int start = 0, left = 1, right = nhull-1; - -diff --git a/Recast/Source/RecastRegion.cpp b/Recast/Source/RecastRegion.cpp -index 38bc4ff..352ba57 100644 ---- a/Recast/Source/RecastRegion.cpp -+++ b/Recast/Source/RecastRegion.cpp -@@ -1041,7 +1041,7 @@ static void addUniqueConnection(rcRegion& reg, int n) - static bool mergeAndFilterLayerRegions(rcContext* ctx, int minRegionArea, - unsigned short& maxRegionId, - rcCompactHeightfield& chf, -- unsigned short* srcReg, rcIntArray& overlaps) -+ unsigned short* srcReg, rcIntArray& /*overlaps*/) - { - const int w = chf.width; - const int h = chf.height; -- -1.9.5.msysgit.0 +2.9.0.windows.1 |