diff options
Diffstat (limited to 'thirdparty/recastnavigation/Recast')
7 files changed, 469 insertions, 230 deletions
diff --git a/thirdparty/recastnavigation/Recast/Include/Recast.h b/thirdparty/recastnavigation/Recast/Include/Recast.h index e85c0d2e29..4d557389b5 100644 --- a/thirdparty/recastnavigation/Recast/Include/Recast.h +++ b/thirdparty/recastnavigation/Recast/Include/Recast.h @@ -332,6 +332,8 @@ struct rcCompactSpan /// @ingroup recast struct rcCompactHeightfield { + rcCompactHeightfield(); + ~rcCompactHeightfield(); 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.) int spanCount; ///< The number of spans in the heightfield. @@ -376,6 +378,8 @@ struct rcHeightfieldLayer /// @see rcAllocHeightfieldLayerSet, rcFreeHeightfieldLayerSet struct rcHeightfieldLayerSet { + rcHeightfieldLayerSet(); + ~rcHeightfieldLayerSet(); rcHeightfieldLayer* layers; ///< The layers in the set. [Size: #nlayers] int nlayers; ///< The number of layers in the set. }; @@ -395,6 +399,8 @@ struct rcContour /// @ingroup recast struct rcContourSet { + rcContourSet(); + ~rcContourSet(); rcContour* conts; ///< An array of the contours in the set. [Size: #nconts] int nconts; ///< The number of contours in the set. float bmin[3]; ///< The minimum bounds in world space. [(x, y, z)] @@ -411,6 +417,8 @@ struct rcContourSet /// @ingroup recast struct rcPolyMesh { + rcPolyMesh(); + ~rcPolyMesh(); unsigned short* verts; ///< The mesh vertices. [Form: (x, y, z) * #nverts] unsigned short* polys; ///< Polygon and neighbor data. [Length: #maxpolys * 2 * #nvp] unsigned short* regs; ///< The region id assigned to each polygon. [Length: #maxpolys] diff --git a/thirdparty/recastnavigation/Recast/Include/RecastAlloc.h b/thirdparty/recastnavigation/Recast/Include/RecastAlloc.h index 3cdd450d42..e436af9a01 100644 --- a/thirdparty/recastnavigation/Recast/Include/RecastAlloc.h +++ b/thirdparty/recastnavigation/Recast/Include/RecastAlloc.h @@ -20,6 +20,9 @@ #define RECASTALLOC_H #include <stddef.h> +#include <stdint.h> + +#include <RecastAssert.h> /// Provides hint values to the memory allocator on how long the /// memory is expected to be used. @@ -58,64 +61,257 @@ void* rcAlloc(size_t size, rcAllocHint hint); /// @see rcAlloc void rcFree(void* ptr); +/// An implementation of operator new usable for placement new. The default one is part of STL (which we don't use). +/// rcNewTag is a dummy type used to differentiate our operator from the STL one, in case users import both Recast +/// and STL. +struct rcNewTag {}; +inline void* operator new(size_t, const rcNewTag&, void* p) { return p; } +inline void operator delete(void*, const rcNewTag&, void*) {} -/// A simple dynamic array of integers. -class rcIntArray -{ - int* m_data; - int m_size, m_cap; +/// Signed to avoid warnnings when comparing to int loop indexes, and common error with comparing to zero. +/// MSVC2010 has a bug where ssize_t is unsigned (!!!). +typedef intptr_t rcSizeType; +#define RC_SIZE_MAX INTPTR_MAX - void doResize(int n); - - // Explicitly disabled copy constructor and copy assignment operator. - rcIntArray(const rcIntArray&); - rcIntArray& operator=(const rcIntArray&); +/// Macros to hint to the compiler about the likeliest branch. Please add a benchmark that demonstrates a performance +/// improvement before introducing use cases. +#if defined(__GNUC__) || defined(__clang__) +#define rcLikely(x) __builtin_expect((x), true) +#define rcUnlikely(x) __builtin_expect((x), false) +#else +#define rcLikely(x) (x) +#define rcUnlikely(x) (x) +#endif -public: - /// Constructs an instance with an initial array size of zero. - rcIntArray() : m_data(0), m_size(0), m_cap(0) {} +/// Variable-sized storage type. Mimics the interface of std::vector<T> with some notable differences: +/// * Uses rcAlloc()/rcFree() to handle storage. +/// * No support for a custom allocator. +/// * Uses signed size instead of size_t to avoid warnings in for loops: "for (int i = 0; i < foo.size(); i++)" +/// * Omits methods of limited utility: insert/erase, (bad performance), at (we don't use exceptions), operator=. +/// * assign() and the pre-sizing constructor follow C++11 semantics -- they don't construct a temporary if no value is provided. +/// * push_back() and resize() support adding values from the current vector. Range-based constructors and assign(begin, end) do not. +/// * No specialization for bool. +template <typename T, rcAllocHint H> +class rcVectorBase { + rcSizeType m_size; + rcSizeType m_cap; + T* m_data; + // Constructs a T at the give address with either the copy constructor or the default. + static void construct(T* p, const T& v) { ::new(rcNewTag(), (void*)p) T(v); } + static void construct(T* p) { ::new(rcNewTag(), (void*)p) T; } + static void construct_range(T* begin, T* end); + static void construct_range(T* begin, T* end, const T& value); + static void copy_range(T* dst, const T* begin, const T* end); + void destroy_range(rcSizeType begin, rcSizeType end); + // Creates an array of the given size, copies all of this vector's data into it, and returns it. + T* allocate_and_copy(rcSizeType size); + void resize_impl(rcSizeType size, const T* value); + public: + typedef rcSizeType size_type; + typedef T value_type; - /// Constructs an instance initialized to the specified size. - /// @param[in] n The initial size of the integer array. - rcIntArray(int n) : m_data(0), m_size(0), m_cap(0) { resize(n); } - ~rcIntArray() { rcFree(m_data); } + rcVectorBase() : m_size(0), m_cap(0), m_data(0) {}; + rcVectorBase(const rcVectorBase<T, H>& other) : m_size(0), m_cap(0), m_data(0) { assign(other.begin(), other.end()); } + explicit rcVectorBase(rcSizeType count) : m_size(0), m_cap(0), m_data(0) { resize(count); } + rcVectorBase(rcSizeType count, const T& value) : m_size(0), m_cap(0), m_data(0) { resize(count, value); } + rcVectorBase(const T* begin, const T* end) : m_size(0), m_cap(0), m_data(0) { assign(begin, end); } + ~rcVectorBase() { destroy_range(0, m_size); 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) - { - if (n > m_cap) - doResize(n); - - m_size = n; + // Unlike in std::vector, we return a bool to indicate whether the alloc was successful. + bool reserve(rcSizeType size); + + void assign(rcSizeType count, const T& value) { clear(); resize(count, value); } + void assign(const T* begin, const T* end); + + void resize(rcSizeType size) { resize_impl(size, NULL); } + void resize(rcSizeType size, const T& value) { resize_impl(size, &value); } + // Not implemented as resize(0) because resize requires T to be default-constructible. + void clear() { destroy_range(0, m_size); m_size = 0; } + + void push_back(const T& value); + void pop_back() { rcAssert(m_size > 0); back().~T(); m_size--; } + + rcSizeType size() const { return m_size; } + rcSizeType capacity() const { return m_cap; } + bool empty() const { return size() == 0; } + + const T& operator[](rcSizeType i) const { rcAssert(i >= 0 && i < m_size); return m_data[i]; } + T& operator[](rcSizeType i) { rcAssert(i >= 0 && i < m_size); return m_data[i]; } + + const T& front() const { rcAssert(m_size); return m_data[0]; } + T& front() { rcAssert(m_size); return m_data[0]; } + const T& back() const { rcAssert(m_size); return m_data[m_size - 1]; }; + T& back() { rcAssert(m_size); return m_data[m_size - 1]; }; + const T* data() const { return m_data; } + T* data() { return m_data; } + + T* begin() { return m_data; } + T* end() { return m_data + m_size; } + const T* begin() const { return m_data; } + const T* end() const { return m_data + m_size; } + + void swap(rcVectorBase<T, H>& other); + + // Explicitly deleted. + rcVectorBase& operator=(const rcVectorBase<T, H>& other); +}; + +template<typename T, rcAllocHint H> +bool rcVectorBase<T, H>::reserve(rcSizeType count) { + if (count <= m_cap) { + return true; + } + T* new_data = allocate_and_copy(count); + if (!new_data) { + return false; + } + destroy_range(0, m_size); + rcFree(m_data); + m_data = new_data; + m_cap = count; + return true; +} +template <typename T, rcAllocHint H> +T* rcVectorBase<T, H>::allocate_and_copy(rcSizeType size) { + rcAssert(RC_SIZE_MAX / static_cast<rcSizeType>(sizeof(T)) >= size); + T* new_data = static_cast<T*>(rcAlloc(sizeof(T) * size, H)); + if (new_data) { + copy_range(new_data, m_data, m_data + m_size); + } + return new_data; +} +template <typename T, rcAllocHint H> +void rcVectorBase<T, H>::assign(const T* begin, const T* end) { + clear(); + reserve(end - begin); + m_size = end - begin; + copy_range(m_data, begin, end); +} +template <typename T, rcAllocHint H> +void rcVectorBase<T, H>::push_back(const T& value) { + // rcLikely increases performance by ~50% on BM_rcVector_PushPreallocated, + // and by ~2-5% on BM_rcVector_Push. + if (rcLikely(m_size < m_cap)) { + construct(m_data + m_size++, value); + return; } - /// Push the specified integer onto the end of the array and increases the size by one. - /// @param[in] item The new value. - void push(int item) { resize(m_size+1); m_data[m_size-1] = item; } + rcAssert(RC_SIZE_MAX / 2 >= m_size); + rcSizeType new_cap = m_size ? 2*m_size : 1; + T* data = allocate_and_copy(new_cap); + // construct between allocate and destroy+free in case value is + // in this vector. + construct(data + m_size, value); + destroy_range(0, m_size); + m_size++; + m_cap = new_cap; + rcFree(m_data); + m_data = data; +} +template <typename T, rcAllocHint H> +void rcVectorBase<T, H>::resize_impl(rcSizeType size, const T* value) { + if (size < m_size) { + destroy_range(size, m_size); + m_size = size; + } else if (size > m_size) { + T* new_data = allocate_and_copy(size); + // We defer deconstructing/freeing old data until after constructing + // new elements in case "value" is there. + if (value) { + construct_range(new_data + m_size, new_data + size, *value); + } else { + construct_range(new_data + m_size, new_data + size); + } + destroy_range(0, m_size); + rcFree(m_data); + m_data = new_data; + m_cap = size; + m_size = size; + } +} +template <typename T, rcAllocHint H> +void rcVectorBase<T, H>::swap(rcVectorBase<T, H>& other) { + // TODO: Reorganize headers so we can use rcSwap here. + rcSizeType tmp_cap = other.m_cap; + rcSizeType tmp_size = other.m_size; + T* tmp_data = other.m_data; - /// Returns the value at the end of the array and reduces the size by one. - /// @return The value at the end of the array. - int pop() - { - if (m_size > 0) - m_size--; - - return m_data[m_size]; + other.m_cap = m_cap; + other.m_size = m_size; + other.m_data = m_data; + + m_cap = tmp_cap; + m_size = tmp_size; + m_data = tmp_data; +} +// static +template <typename T, rcAllocHint H> +void rcVectorBase<T, H>::construct_range(T* begin, T* end) { + for (T* p = begin; p < end; p++) { + construct(p); + } +} +// static +template <typename T, rcAllocHint H> +void rcVectorBase<T, H>::construct_range(T* begin, T* end, const T& value) { + for (T* p = begin; p < end; p++) { + construct(p, value); + } +} +// static +template <typename T, rcAllocHint H> +void rcVectorBase<T, H>::copy_range(T* dst, const T* begin, const T* end) { + for (rcSizeType i = 0 ; i < end - begin; i++) { + construct(dst + i, begin[i]); } +} +template <typename T, rcAllocHint H> +void rcVectorBase<T, H>::destroy_range(rcSizeType begin, rcSizeType end) { + for (rcSizeType i = begin; i < end; i++) { + m_data[i].~T(); + } +} - /// The value at the specified array index. - /// @warning Does not provide overflow protection. - /// @param[in] i The index of the value. - const int& operator[](int i) const { return m_data[i]; } +template <typename T> +class rcTempVector : public rcVectorBase<T, RC_ALLOC_TEMP> { + typedef rcVectorBase<T, RC_ALLOC_TEMP> Base; +public: + rcTempVector() : Base() {} + explicit rcTempVector(rcSizeType size) : Base(size) {} + rcTempVector(rcSizeType size, const T& value) : Base(size, value) {} + rcTempVector(const rcTempVector<T>& other) : Base(other) {} + rcTempVector(const T* begin, const T* end) : Base(begin, end) {} +}; +template <typename T> +class rcPermVector : public rcVectorBase<T, RC_ALLOC_PERM> { + typedef rcVectorBase<T, RC_ALLOC_PERM> Base; +public: + rcPermVector() : Base() {} + explicit rcPermVector(rcSizeType size) : Base(size) {} + rcPermVector(rcSizeType size, const T& value) : Base(size, value) {} + rcPermVector(const rcPermVector<T>& other) : Base(other) {} + rcPermVector(const T* begin, const T* end) : Base(begin, end) {} +}; - /// The value at the specified array index. - /// @warning Does not provide overflow protection. - /// @param[in] i The index of the value. - int& operator[](int i) { return m_data[i]; } - /// The current size of the integer array. - int size() const { return m_size; } +/// Legacy class. Prefer rcVector<int>. +class rcIntArray +{ + rcTempVector<int> m_impl; +public: + rcIntArray() {} + rcIntArray(int n) : m_impl(n, 0) {} + void push(int item) { m_impl.push_back(item); } + void resize(int size) { m_impl.resize(size); } + int pop() + { + int v = m_impl.back(); + m_impl.pop_back(); + return v; + } + int size() const { return static_cast<int>(m_impl.size()); } + int& operator[](int index) { return m_impl[index]; } + int operator[](int index) const { return m_impl[index]; } }; /// A simple helper class used to delete an array when it goes out of scope. diff --git a/thirdparty/recastnavigation/Recast/Source/Recast.cpp b/thirdparty/recastnavigation/Recast/Source/Recast.cpp index 8308d1973e..1b71710cdc 100644 --- a/thirdparty/recastnavigation/Recast/Source/Recast.cpp +++ b/thirdparty/recastnavigation/Recast/Source/Recast.cpp @@ -23,11 +23,34 @@ #include <stdlib.h> #include <stdio.h> #include <stdarg.h> -#include <new> #include "Recast.h" #include "RecastAlloc.h" #include "RecastAssert.h" +namespace +{ +/// Allocates and constructs an object of the given type, returning a pointer. +/// TODO: Support constructor args. +/// @param[in] hint Hint to the allocator. +template <typename T> +T* rcNew(rcAllocHint hint) { + T* ptr = (T*)rcAlloc(sizeof(T), hint); + ::new(rcNewTag(), (void*)ptr) T(); + return ptr; +} + +/// Destroys and frees an object allocated with rcNew. +/// @param[in] ptr The object pointer to delete. +template <typename T> +void rcDelete(T* ptr) { + if (ptr) { + ptr->~T(); + rcFree((void*)ptr); + } +} +} // namespace + + float rcSqrt(float x) { return sqrtf(x); @@ -73,9 +96,8 @@ void rcContext::log(const rcLogCategory category, const char* format, ...) rcHeightfield* rcAllocHeightfield() { - return new (rcAlloc(sizeof(rcHeightfield), RC_ALLOC_PERM)) rcHeightfield; + return rcNew<rcHeightfield>(RC_ALLOC_PERM); } - rcHeightfield::rcHeightfield() : width() , height() @@ -104,84 +126,133 @@ rcHeightfield::~rcHeightfield() void rcFreeHeightField(rcHeightfield* hf) { - if (!hf) return; - hf->~rcHeightfield(); - rcFree(hf); + rcDelete(hf); } rcCompactHeightfield* rcAllocCompactHeightfield() { - rcCompactHeightfield* chf = (rcCompactHeightfield*)rcAlloc(sizeof(rcCompactHeightfield), RC_ALLOC_PERM); - memset(chf, 0, sizeof(rcCompactHeightfield)); - return chf; + return rcNew<rcCompactHeightfield>(RC_ALLOC_PERM); } void rcFreeCompactHeightfield(rcCompactHeightfield* chf) { - if (!chf) return; - rcFree(chf->cells); - rcFree(chf->spans); - rcFree(chf->dist); - rcFree(chf->areas); - rcFree(chf); + rcDelete(chf); } -rcHeightfieldLayerSet* rcAllocHeightfieldLayerSet() +rcCompactHeightfield::rcCompactHeightfield() + : width(), + height(), + spanCount(), + walkableHeight(), + walkableClimb(), + borderSize(), + maxDistance(), + maxRegions(), + bmin(), + bmax(), + cs(), + ch(), + cells(), + spans(), + dist(), + areas() { - rcHeightfieldLayerSet* lset = (rcHeightfieldLayerSet*)rcAlloc(sizeof(rcHeightfieldLayerSet), RC_ALLOC_PERM); - memset(lset, 0, sizeof(rcHeightfieldLayerSet)); - return lset; +} +rcCompactHeightfield::~rcCompactHeightfield() +{ + rcFree(cells); + rcFree(spans); + rcFree(dist); + rcFree(areas); } +rcHeightfieldLayerSet* rcAllocHeightfieldLayerSet() +{ + return rcNew<rcHeightfieldLayerSet>(RC_ALLOC_PERM); +} void rcFreeHeightfieldLayerSet(rcHeightfieldLayerSet* lset) { - if (!lset) return; - for (int i = 0; i < lset->nlayers; ++i) + rcDelete(lset); +} + +rcHeightfieldLayerSet::rcHeightfieldLayerSet() + : layers(), nlayers() {} +rcHeightfieldLayerSet::~rcHeightfieldLayerSet() +{ + for (int i = 0; i < nlayers; ++i) { - rcFree(lset->layers[i].heights); - rcFree(lset->layers[i].areas); - rcFree(lset->layers[i].cons); + rcFree(layers[i].heights); + rcFree(layers[i].areas); + rcFree(layers[i].cons); } - rcFree(lset->layers); - rcFree(lset); + rcFree(layers); } rcContourSet* rcAllocContourSet() { - rcContourSet* cset = (rcContourSet*)rcAlloc(sizeof(rcContourSet), RC_ALLOC_PERM); - memset(cset, 0, sizeof(rcContourSet)); - return cset; + return rcNew<rcContourSet>(RC_ALLOC_PERM); } - void rcFreeContourSet(rcContourSet* cset) { - if (!cset) return; - for (int i = 0; i < cset->nconts; ++i) + rcDelete(cset); +} + +rcContourSet::rcContourSet() + : conts(), + nconts(), + bmin(), + bmax(), + cs(), + ch(), + width(), + height(), + borderSize(), + maxError() {} +rcContourSet::~rcContourSet() +{ + for (int i = 0; i < nconts; ++i) { - rcFree(cset->conts[i].verts); - rcFree(cset->conts[i].rverts); + rcFree(conts[i].verts); + rcFree(conts[i].rverts); } - rcFree(cset->conts); - rcFree(cset); + rcFree(conts); } + rcPolyMesh* rcAllocPolyMesh() { - rcPolyMesh* pmesh = (rcPolyMesh*)rcAlloc(sizeof(rcPolyMesh), RC_ALLOC_PERM); - memset(pmesh, 0, sizeof(rcPolyMesh)); - return pmesh; + return rcNew<rcPolyMesh>(RC_ALLOC_PERM); } - void rcFreePolyMesh(rcPolyMesh* pmesh) { - if (!pmesh) return; - rcFree(pmesh->verts); - rcFree(pmesh->polys); - rcFree(pmesh->regs); - rcFree(pmesh->flags); - rcFree(pmesh->areas); - rcFree(pmesh); + rcDelete(pmesh); +} + +rcPolyMesh::rcPolyMesh() + : verts(), + polys(), + regs(), + flags(), + areas(), + nverts(), + npolys(), + maxpolys(), + nvp(), + bmin(), + bmax(), + cs(), + ch(), + borderSize(), + maxEdgeError() {} + +rcPolyMesh::~rcPolyMesh() +{ + rcFree(verts); + rcFree(polys); + rcFree(regs); + rcFree(flags); + rcFree(areas); } rcPolyMeshDetail* rcAllocPolyMeshDetail() diff --git a/thirdparty/recastnavigation/Recast/Source/RecastAlloc.cpp b/thirdparty/recastnavigation/Recast/Source/RecastAlloc.cpp index 453b5fa6a6..bdc366116e 100644 --- a/thirdparty/recastnavigation/Recast/Source/RecastAlloc.cpp +++ b/thirdparty/recastnavigation/Recast/Source/RecastAlloc.cpp @@ -58,29 +58,3 @@ void rcFree(void* ptr) if (ptr) sRecastFreeFunc(ptr); } - -/// @class rcIntArray -/// -/// While it is possible to pre-allocate a specific array size during -/// construction or by using the #resize method, certain methods will -/// automatically resize the array as needed. -/// -/// @warning The array memory is not initialized to zero when the size is -/// manually set during construction or when using #resize. - -/// @par -/// -/// 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::doResize(int 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/thirdparty/recastnavigation/Recast/Source/RecastContour.cpp b/thirdparty/recastnavigation/Recast/Source/RecastContour.cpp index 277ab01501..6574c11b6b 100644 --- a/thirdparty/recastnavigation/Recast/Source/RecastContour.cpp +++ b/thirdparty/recastnavigation/Recast/Source/RecastContour.cpp @@ -1009,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<signed char> winding((signed char*)rcAlloc(sizeof(signed char)*cset.nconts, RC_ALLOC_TEMP)); if (!winding) { ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'hole' (%d).", cset.nconts); diff --git a/thirdparty/recastnavigation/Recast/Source/RecastMeshDetail.cpp b/thirdparty/recastnavigation/Recast/Source/RecastMeshDetail.cpp index f953132f74..9a423cab8a 100644 --- a/thirdparty/recastnavigation/Recast/Source/RecastMeshDetail.cpp +++ b/thirdparty/recastnavigation/Recast/Source/RecastMeshDetail.cpp @@ -557,15 +557,16 @@ 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, const int nin, rcIntArray& tris) { int start = 0, left = 1, right = nhull-1; // Start from an ear with shortest perimeter. // This tends to favor well formed triangles as starting point. - float dmin = 0; + float dmin = FLT_MAX; for (int i = 0; i < nhull; i++) { + if (hull[i] >= nin) continue; // Ears are triangles with original vertices as middle vertex while others are actually line segments on edges int pi = prev(i, nhull); int ni = next(i, nhull); const float* pv = &verts[hull[pi]*3]; @@ -770,7 +771,7 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin, // If the polygon minimum extent is small (sliver or small triangle), do not try to add internal points. if (minExtent < sampleDist*2) { - triangulateHull(nverts, verts, nhull, hull, tris); + triangulateHull(nverts, verts, nhull, hull, nin, tris); return true; } @@ -778,7 +779,7 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin, // We're using the triangulateHull instead of delaunayHull as it tends to // create a bit better triangulation for long thin triangles when there // are no internal points. - triangulateHull(nverts, verts, nhull, hull, tris); + triangulateHull(nverts, verts, nhull, hull, nin, tris); if (tris.size() == 0) { @@ -1140,7 +1141,8 @@ static void getHeightData(rcContext* ctx, const rcCompactHeightfield& chf, static unsigned char getEdgeFlags(const float* va, const float* vb, const float* vpoly, const int npoly) { - // Return true if edge (va,vb) is part of the polygon. + // The flag returned by this function matches dtDetailTriEdgeFlags in Detour. + // Figure out if edge (va,vb) is part of the polygon boundary. static const float thrSqr = rcSqr(0.001f); for (int i = 0, j = npoly-1; i < npoly; j=i++) { diff --git a/thirdparty/recastnavigation/Recast/Source/RecastRegion.cpp b/thirdparty/recastnavigation/Recast/Source/RecastRegion.cpp index 38a2bd6bfa..e1fc0ee788 100644 --- a/thirdparty/recastnavigation/Recast/Source/RecastRegion.cpp +++ b/thirdparty/recastnavigation/Recast/Source/RecastRegion.cpp @@ -25,8 +25,17 @@ #include "Recast.h" #include "RecastAlloc.h" #include "RecastAssert.h" -#include <new> +namespace +{ +struct LevelStackEntry +{ + LevelStackEntry(int x_, int y_, int index_) : x(x_), y(y_), index(index_) {} + int x; + int y; + int index; +}; +} // namespace static void calculateDistanceField(rcCompactHeightfield& chf, unsigned short* src, unsigned short& maxDist) { @@ -245,17 +254,15 @@ static bool floodRegion(int x, int y, int i, unsigned short level, unsigned short r, rcCompactHeightfield& chf, unsigned short* srcReg, unsigned short* srcDist, - rcIntArray& stack) + rcTempVector<LevelStackEntry>& stack) { const int w = chf.width; const unsigned char area = chf.areas[i]; // Flood fill mark region. - stack.resize(0); - stack.push((int)x); - stack.push((int)y); - stack.push((int)i); + stack.clear(); + stack.push_back(LevelStackEntry(x, y, i)); srcReg[i] = r; srcDist[i] = 0; @@ -264,9 +271,11 @@ static bool floodRegion(int x, int y, int i, while (stack.size() > 0) { - int ci = stack.pop(); - int cy = stack.pop(); - int cx = stack.pop(); + LevelStackEntry& back = stack.back(); + int cx = back.x; + int cy = back.y; + int ci = back.index; + stack.pop_back(); const rcCompactSpan& cs = chf.spans[ci]; @@ -332,9 +341,7 @@ static bool floodRegion(int x, int y, int i, { srcReg[ai] = r; srcDist[ai] = 0; - stack.push(ax); - stack.push(ay); - stack.push(ai); + stack.push_back(LevelStackEntry(ax, ay, ai)); } } } @@ -343,12 +350,20 @@ static bool floodRegion(int x, int y, int i, return count > 0; } -static unsigned short* expandRegions(int maxIter, unsigned short level, - rcCompactHeightfield& chf, - unsigned short* srcReg, unsigned short* srcDist, - unsigned short* dstReg, unsigned short* dstDist, - rcIntArray& stack, - bool fillStack) +// Struct to keep track of entries in the region table that have been changed. +struct DirtyEntry +{ + DirtyEntry(int index_, unsigned short region_, unsigned short distance2_) + : index(index_), region(region_), distance2(distance2_) {} + int index; + unsigned short region; + unsigned short distance2; +}; +static void expandRegions(int maxIter, unsigned short level, + rcCompactHeightfield& chf, + unsigned short* srcReg, unsigned short* srcDist, + rcTempVector<LevelStackEntry>& stack, + bool fillStack) { const int w = chf.width; const int h = chf.height; @@ -356,7 +371,7 @@ static unsigned short* expandRegions(int maxIter, unsigned short level, if (fillStack) { // Find cells revealed by the raised level. - stack.resize(0); + stack.clear(); for (int y = 0; y < h; ++y) { for (int x = 0; x < w; ++x) @@ -366,9 +381,7 @@ static unsigned short* expandRegions(int maxIter, unsigned short level, { if (chf.dist[i] >= level && srcReg[i] == 0 && chf.areas[i] != RC_NULL_AREA) { - stack.push(x); - stack.push(y); - stack.push(i); + stack.push_back(LevelStackEntry(x, y, i)); } } } @@ -377,27 +390,26 @@ static unsigned short* expandRegions(int maxIter, unsigned short level, else // use cells in the input stack { // mark all cells which already have a region - for (int j=0; j<stack.size(); j+=3) + for (int j=0; j<stack.size(); j++) { - int i = stack[j+2]; + int i = stack[j].index; if (srcReg[i] != 0) - stack[j+2] = -1; + stack[j].index = -1; } } + rcTempVector<DirtyEntry> dirtyEntries; int iter = 0; while (stack.size() > 0) { int failed = 0; + dirtyEntries.clear(); - memcpy(dstReg, srcReg, sizeof(unsigned short)*chf.spanCount); - memcpy(dstDist, srcDist, sizeof(unsigned short)*chf.spanCount); - - for (int j = 0; j < stack.size(); j += 3) + for (int j = 0; j < stack.size(); j++) { - int x = stack[j+0]; - int y = stack[j+1]; - int i = stack[j+2]; + int x = stack[j].x; + int y = stack[j].y; + int i = stack[j].index; if (i < 0) { failed++; @@ -426,9 +438,8 @@ static unsigned short* expandRegions(int maxIter, unsigned short level, } if (r) { - stack[j+2] = -1; // mark as used - dstReg[i] = r; - dstDist[i] = d2; + stack[j].index = -1; // mark as used + dirtyEntries.push_back(DirtyEntry(i, r, d2)); } else { @@ -436,11 +447,14 @@ static unsigned short* expandRegions(int maxIter, unsigned short level, } } - // rcSwap source and dest. - rcSwap(srcReg, dstReg); - rcSwap(srcDist, dstDist); + // Copy entries that differ between src and dst to keep them in sync. + for (int i = 0; i < dirtyEntries.size(); i++) { + int idx = dirtyEntries[i].index; + srcReg[idx] = dirtyEntries[i].region; + srcDist[idx] = dirtyEntries[i].distance2; + } - if (failed*3 == stack.size()) + if (failed == stack.size()) break; if (level > 0) @@ -450,16 +464,14 @@ static unsigned short* expandRegions(int maxIter, unsigned short level, break; } } - - return srcReg; } static void sortCellsByLevel(unsigned short startLevel, rcCompactHeightfield& chf, - unsigned short* srcReg, - unsigned int nbStacks, rcIntArray* stacks, + const unsigned short* srcReg, + unsigned int nbStacks, rcTempVector<LevelStackEntry>* stacks, unsigned short loglevelsPerStack) // the levels per stack (2 in our case) as a bit shift { const int w = chf.width; @@ -467,7 +479,7 @@ static void sortCellsByLevel(unsigned short startLevel, startLevel = startLevel >> loglevelsPerStack; for (unsigned int j=0; j<nbStacks; ++j) - stacks[j].resize(0); + stacks[j].clear(); // put all cells in the level range into the appropriate stacks for (int y = 0; y < h; ++y) @@ -487,26 +499,23 @@ static void sortCellsByLevel(unsigned short startLevel, if (sId < 0) sId = 0; - stacks[sId].push(x); - stacks[sId].push(y); - stacks[sId].push(i); + stacks[sId].push_back(LevelStackEntry(x, y, i)); } } } } -static void appendStacks(rcIntArray& srcStack, rcIntArray& dstStack, - unsigned short* srcReg) +static void appendStacks(const rcTempVector<LevelStackEntry>& srcStack, + rcTempVector<LevelStackEntry>& dstStack, + const unsigned short* srcReg) { - for (int j=0; j<srcStack.size(); j+=3) + for (int j=0; j<srcStack.size(); j++) { - int i = srcStack[j+2]; + int i = srcStack[j].index; if ((i < 0) || (srcReg[i] != 0)) continue; - dstStack.push(srcStack[j]); - dstStack.push(srcStack[j+1]); - dstStack.push(srcStack[j+2]); + dstStack.push_back(srcStack[j]); } } @@ -671,7 +680,7 @@ static bool isRegionConnectedToBorder(const rcRegion& reg) return false; } -static bool isSolidEdge(rcCompactHeightfield& chf, unsigned short* srcReg, +static bool isSolidEdge(rcCompactHeightfield& chf, const unsigned short* srcReg, int x, int y, int i, int dir) { const rcCompactSpan& s = chf.spans[i]; @@ -690,7 +699,7 @@ static bool isSolidEdge(rcCompactHeightfield& chf, unsigned short* srcReg, static void walkContour(int x, int y, int i, int dir, rcCompactHeightfield& chf, - unsigned short* srcReg, + const unsigned short* srcReg, rcIntArray& cont) { int startDir = dir; @@ -786,16 +795,15 @@ static bool mergeAndFilterRegions(rcContext* ctx, int minRegionArea, int mergeRe const int h = chf.height; const int nreg = maxRegionId+1; - rcRegion* regions = (rcRegion*)rcAlloc(sizeof(rcRegion)*nreg, RC_ALLOC_TEMP); - if (!regions) - { + rcTempVector<rcRegion> regions; + if (!regions.reserve(nreg)) { ctx->log(RC_LOG_ERROR, "mergeAndFilterRegions: Out of memory 'regions' (%d).", nreg); return false; } // Construct regions for (int i = 0; i < nreg; ++i) - new(®ions[i]) rcRegion((unsigned short)i); + regions.push_back(rcRegion((unsigned short) i)); // Find edge of a region and find connections around the contour. for (int y = 0; y < h; ++y) @@ -1021,11 +1029,6 @@ static bool mergeAndFilterRegions(rcContext* ctx, int minRegionArea, int mergeRe if (regions[i].overlap) overlaps.push(regions[i].id); - for (int i = 0; i < nreg; ++i) - regions[i].~rcRegion(); - rcFree(regions); - - return true; } @@ -1041,22 +1044,21 @@ 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) { const int w = chf.width; const int h = chf.height; const int nreg = maxRegionId+1; - rcRegion* regions = (rcRegion*)rcAlloc(sizeof(rcRegion)*nreg, RC_ALLOC_TEMP); - if (!regions) - { + rcTempVector<rcRegion> regions; + + // Construct regions + if (!regions.reserve(nreg)) { ctx->log(RC_LOG_ERROR, "mergeAndFilterLayerRegions: Out of memory 'regions' (%d).", nreg); return false; } - - // Construct regions for (int i = 0; i < nreg; ++i) - new(®ions[i]) rcRegion((unsigned short)i); + regions.push_back(rcRegion((unsigned short) i)); // Find region neighbours and overlapping regions. rcIntArray lregs(32); @@ -1234,10 +1236,6 @@ static bool mergeAndFilterLayerRegions(rcContext* ctx, int minRegionArea, srcReg[i] = regions[srcReg[i]].id; } - for (int i = 0; i < nreg; ++i) - regions[i].~rcRegion(); - rcFree(regions); - return true; } @@ -1391,9 +1389,9 @@ bool rcBuildRegionsMonotone(rcContext* ctx, rcCompactHeightfield& chf, paintRectRegion(w-bw, w, 0, h, id|RC_BORDER_REG, chf, srcReg); id++; paintRectRegion(0, w, 0, bh, id|RC_BORDER_REG, chf, srcReg); id++; paintRectRegion(0, w, h-bh, h, id|RC_BORDER_REG, chf, srcReg); id++; - - chf.borderSize = borderSize; } + + chf.borderSize = borderSize; rcIntArray prev(256); @@ -1535,7 +1533,7 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf, 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*2, RC_ALLOC_TEMP)); if (!buf) { ctx->log(RC_LOG_ERROR, "rcBuildRegions: Out of memory 'tmp' (%d).", chf.spanCount*4); @@ -1546,17 +1544,15 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf, const int LOG_NB_STACKS = 3; const int NB_STACKS = 1 << LOG_NB_STACKS; - rcIntArray lvlStacks[NB_STACKS]; + rcTempVector<LevelStackEntry> lvlStacks[NB_STACKS]; for (int i=0; i<NB_STACKS; ++i) - lvlStacks[i].resize(1024); + lvlStacks[i].reserve(256); - rcIntArray stack(1024); - rcIntArray visited(1024); + rcTempVector<LevelStackEntry> stack; + stack.reserve(256); unsigned short* srcReg = buf; unsigned short* srcDist = buf+chf.spanCount; - unsigned short* dstReg = buf+chf.spanCount*2; - unsigned short* dstDist = buf+chf.spanCount*3; memset(srcReg, 0, sizeof(unsigned short)*chf.spanCount); memset(srcDist, 0, sizeof(unsigned short)*chf.spanCount); @@ -1581,9 +1577,9 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf, paintRectRegion(w-bw, w, 0, h, regionId|RC_BORDER_REG, chf, srcReg); regionId++; paintRectRegion(0, w, 0, bh, regionId|RC_BORDER_REG, chf, srcReg); regionId++; paintRectRegion(0, w, h-bh, h, regionId|RC_BORDER_REG, chf, srcReg); regionId++; - - chf.borderSize = borderSize; } + + chf.borderSize = borderSize; int sId = -1; while (level > 0) @@ -1604,22 +1600,19 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf, 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); - } + expandRegions(expandIters, level, chf, srcReg, srcDist, lvlStacks[sId], false); } { rcScopedTimer timerFloor(ctx, RC_TIMER_BUILD_REGIONS_FLOOD); // Mark new regions with IDs. - for (int j = 0; j<lvlStacks[sId].size(); j += 3) + for (int j = 0; j<lvlStacks[sId].size(); j++) { - int x = lvlStacks[sId][j]; - int y = lvlStacks[sId][j+1]; - int i = lvlStacks[sId][j+2]; + LevelStackEntry current = lvlStacks[sId][j]; + int x = current.x; + int y = current.y; + int i = current.index; if (i >= 0 && srcReg[i] == 0) { if (floodRegion(x, y, i, level, regionId, chf, srcReg, srcDist, stack)) @@ -1638,11 +1631,7 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf, } // Expand current regions until no empty connected cells found. - if (expandRegions(expandIters*8, 0, chf, srcReg, srcDist, dstReg, dstDist, stack, true) != srcReg) - { - rcSwap(srcReg, dstReg); - rcSwap(srcDist, dstDist); - } + expandRegions(expandIters*8, 0, chf, srcReg, srcDist, stack, true); ctx->stopTimer(RC_TIMER_BUILD_REGIONS_WATERSHED); @@ -1709,9 +1698,9 @@ bool rcBuildLayerRegions(rcContext* ctx, rcCompactHeightfield& chf, paintRectRegion(w-bw, w, 0, h, id|RC_BORDER_REG, chf, srcReg); id++; paintRectRegion(0, w, 0, bh, id|RC_BORDER_REG, chf, srcReg); id++; paintRectRegion(0, w, h-bh, h, id|RC_BORDER_REG, chf, srcReg); id++; - - chf.borderSize = borderSize; } + + chf.borderSize = borderSize; rcIntArray prev(256); @@ -1809,9 +1798,8 @@ bool rcBuildLayerRegions(rcContext* ctx, rcCompactHeightfield& chf, 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)) + if (!mergeAndFilterLayerRegions(ctx, minRegionArea, chf.maxRegions, chf, srcReg)) return false; } |