diff options
21 files changed, 2676 insertions, 1388 deletions
diff --git a/extern/recastnavigation/Recast/Include/Recast.h b/extern/recastnavigation/Recast/Include/Recast.h index 4e20b0f0fff..6f18247d527 100644 --- a/extern/recastnavigation/Recast/Include/Recast.h +++ b/extern/recastnavigation/Recast/Include/Recast.h @@ -15,7 +15,7 @@ // misrepresented as being the original software. // 3. This notice may not be removed or altered from any source distribution. // - + #ifndef RECAST_H #define RECAST_H @@ -27,8 +27,8 @@ static const float RC_PI = 3.14159265f; enum rcLogCategory { RC_LOG_PROGRESS = 1, ///< A progress log entry. - RC_LOG_WARNING, ///< A warning log entry. - RC_LOG_ERROR, ///< An error log entry. + RC_LOG_WARNING, ///< A warning log entry. + RC_LOG_ERROR, ///< An error log entry. }; /// Recast performance timer categories. @@ -86,7 +86,7 @@ enum rcTimerLabel /// The time to filter out small regions. (See: #rcBuildRegions, #rcBuildRegionsMonotone) RC_TIMER_BUILD_REGIONS_FILTER, /// The time to build heightfield layers. (See: #rcBuildHeightfieldLayers) - RC_TIMER_BUILD_LAYERS, + RC_TIMER_BUILD_LAYERS, /// The time to build the polygon mesh detail. (See: #rcBuildPolyMeshDetail) RC_TIMER_BUILD_POLYMESHDETAIL, /// The time to merge polygon mesh details. (See: #rcMergePolyMeshDetails) @@ -95,7 +95,7 @@ enum rcTimerLabel RC_MAX_TIMERS }; -/// Provides an interface for optional logging and performance tracking of the Recast +/// Provides an interface for optional logging and performance tracking of the Recast /// build process. /// @ingroup recast class rcContext @@ -103,39 +103,39 @@ class rcContext public: /// Contructor. - /// @param[in] state TRUE if the logging and performance timers should be enabled. [Default: true] + /// @param[in] state TRUE if the logging and performance timers should be enabled. [Default: true] inline rcContext(bool state = true) : m_logEnabled(state), m_timerEnabled(state) {} virtual ~rcContext() {} /// Enables or disables logging. - /// @param[in] state TRUE if logging should be enabled. + /// @param[in] state TRUE if logging should be enabled. inline void enableLog(bool state) { m_logEnabled = state; } /// Clears all log entries. inline void resetLog() { if (m_logEnabled) doResetLog(); } /// Logs a message. - /// @param[in] category The category of the message. - /// @param[in] format The message. + /// @param[in] category The category of the message. + /// @param[in] format The message. void log(const rcLogCategory category, const char* format, ...); /// Enables or disables the performance timers. - /// @param[in] state TRUE if timers should be enabled. + /// @param[in] state TRUE if timers should be enabled. inline void enableTimer(bool state) { m_timerEnabled = state; } /// Clears all peformance timers. (Resets all to unused.) 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. - /// @param label The category of the timer. + /// @param label The category of the timer. inline void stopTimer(const rcTimerLabel label) { if (m_timerEnabled) doStopTimer(label); } /// Returns the total accumulated time of the specified performance timer. - /// @param label The category of the timer. + /// @param label The category of the timer. /// @return The accumulated time of the timer, or -1 if timers are disabled or the timer has never been started. inline int getAccumulatedTime(const rcTimerLabel label) const { return m_timerEnabled ? doGetAccumulatedTime(label) : -1; } @@ -145,27 +145,27 @@ protected: virtual void doResetLog() {} /// Logs a message. - /// @param[in] category The category of the message. - /// @param[in] msg The formatted message. - /// @param[in] len The length of the formatted message. + /// @param[in] category The category of the message. + /// @param[in] msg The formatted message. + /// @param[in] len The length of the formatted message. virtual void doLog(const rcLogCategory /*category*/, const char* /*msg*/, const int /*len*/) {} /// Clears all timers. (Resets all to unused.) virtual void doResetTimers() {} /// Starts the specified performance timer. - /// @param[in] label The category of timer. + /// @param[in] label The category of timer. virtual void doStartTimer(const rcTimerLabel /*label*/) {} /// Stops the specified performance timer. - /// @param[in] label The category of the timer. + /// @param[in] label The category of the timer. virtual void doStopTimer(const rcTimerLabel /*label*/) {} /// Returns the total accumulated time of the specified performance timer. - /// @param[in] label The category of the timer. + /// @param[in] label The category of the timer. /// @return The accumulated time of the timer, or -1 if timers are disabled or the timer has never been started. virtual int doGetAccumulatedTime(const rcTimerLabel /*label*/) const { return -1; } - + /// True if logging is enabled. bool m_logEnabled; @@ -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 @@ -181,71 +201,71 @@ struct rcConfig int width; /// The height of the field along the z-axis. [Limit: >= 0] [Units: vx] - int height; - + int height; + /// The width/height size of tile's on the xz-plane. [Limit: >= 0] [Units: vx] - int tileSize; - + int tileSize; + /// The size of the non-navigable border around the heightfield. [Limit: >=0] [Units: vx] int borderSize; - /// The xz-plane cell size to use for fields. [Limit: > 0] [Units: wu] + /// The xz-plane cell size to use for fields. [Limit: > 0] [Units: wu] float cs; /// The y-axis cell size to use for fields. [Limit: > 0] [Units: wu] float ch; /// The minimum bounds of the field's AABB. [(x, y, z)] [Units: wu] - float bmin[3]; + float bmin[3]; /// The maximum bounds of the field's AABB. [(x, y, z)] [Units: wu] float bmax[3]; - /// The maximum slope that is considered walkable. [Limits: 0 <= value < 90] [Units: Degrees] + /// The maximum slope that is considered walkable. [Limits: 0 <= value < 90] [Units: Degrees] float walkableSlopeAngle; - /// Minimum floor to 'ceiling' height that will still allow the floor area to - /// be considered walkable. [Limit: >= 3] [Units: vx] - int walkableHeight; - - /// Maximum ledge height that is considered to still be traversable. [Limit: >=0] [Units: vx] - int walkableClimb; - - /// The distance to erode/shrink the walkable area of the heightfield away from - /// obstructions. [Limit: >=0] [Units: vx] - int walkableRadius; - - /// The maximum allowed length for contour edges along the border of the mesh. [Limit: >=0] [Units: vx] - int maxEdgeLen; - - /// The maximum distance a simplfied contour's border edges should deviate - /// the original raw contour. [Limit: >=0] [Units: wu] - float maxSimplificationError; - - /// The minimum number of cells allowed to form isolated island areas. [Limit: >=0] [Units: vx] - int minRegionArea; - - /// Any regions with a span count smaller than this value will, if possible, - /// be merged with larger regions. [Limit: >=0] [Units: vx] - int mergeRegionArea; - - /// The maximum number of vertices allowed for polygons generated during the - /// contour to polygon conversion process. [Limit: >= 3] + /// Minimum floor to 'ceiling' height that will still allow the floor area to + /// be considered walkable. [Limit: >= 3] [Units: vx] + int walkableHeight; + + /// Maximum ledge height that is considered to still be traversable. [Limit: >=0] [Units: vx] + int walkableClimb; + + /// The distance to erode/shrink the walkable area of the heightfield away from + /// obstructions. [Limit: >=0] [Units: vx] + int walkableRadius; + + /// The maximum allowed length for contour edges along the border of the mesh. [Limit: >=0] [Units: vx] + int maxEdgeLen; + + /// The maximum distance a simplfied contour's border edges should deviate + /// the original raw contour. [Limit: >=0] [Units: vx] + float maxSimplificationError; + + /// The minimum number of cells allowed to form isolated island areas. [Limit: >=0] [Units: vx] + int minRegionArea; + + /// Any regions with a span count smaller than this value will, if possible, + /// be merged with larger regions. [Limit: >=0] [Units: vx] + int mergeRegionArea; + + /// The maximum number of vertices allowed for polygons generated during the + /// contour to polygon conversion process. [Limit: >= 3] int maxVertsPerPoly; - + /// Sets the sampling distance to use when generating the detail mesh. - /// (For height detail only.) [Limits: 0 or >= 0.9] [Units: wu] + /// (For height detail only.) [Limits: 0 or >= 0.9] [Units: wu] float detailSampleDist; - + /// The maximum distance the detail mesh surface should deviate from heightfield - /// data. (For height detail only.) [Limit: >=0] [Units: wu] + /// data. (For height detail only.) [Limit: >=0] [Units: wu] float detailSampleMaxError; }; /// Defines the number of bits allocated to rcSpan::smin and rcSpan::smax. static const int RC_SPAN_HEIGHT_BITS = 13; /// 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 : 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. - 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. + rcSpan* next; ///< The next span higher up in column. }; /// A memory pool used for quick allocation of spans within a heightfield. @@ -273,18 +293,18 @@ struct rcSpanPool /// @ingroup recast struct rcHeightfield { - int width; ///< The width of the heightfield. (Along the x-axis in cell units.) + 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)] float bmax[3]; ///< The maximum bounds in world space. [(x, y, z)] - float cs; ///< The size of each cell. (On the xz-plane.) + 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.) rcSpan** spans; ///< Heightfield of spans (width*height). rcSpanPool* pools; ///< Linked list of span pools. rcSpan* freelist; ///< The next free span. }; -/// Provides information on the content of a cell column in a compact heightfield. +/// Provides information on the content of a cell column in a compact heightfield. struct rcCompactCell { unsigned int index : 24; ///< Index to the first span in the column. @@ -295,7 +315,7 @@ struct rcCompactCell struct rcCompactSpan { unsigned short y; ///< The lower extent of the span. (Measured from the heightfield's base.) - unsigned short reg; ///< The id of the region the span belongs to. (Or zero if not in a region.) + unsigned short reg; ///< The id of the region the span belongs to. (Or zero if not in a region.) unsigned int con : 24; ///< Packed neighbor connection data. unsigned int h : 8; ///< The height of the span. (Measured from #y.) }; @@ -304,17 +324,17 @@ struct rcCompactSpan /// @ingroup recast struct rcCompactHeightfield { - int width; ///< The width of the heightfield. (Along the x-axis in cell units.) + 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. - int walkableHeight; ///< The walkable height used during the build of the field. (See: rcConfig::walkableHeight) + int walkableHeight; ///< The walkable height used during the build of the field. (See: rcConfig::walkableHeight) int walkableClimb; ///< The walkable climb used during the build of the field. (See: rcConfig::walkableClimb) int borderSize; ///< The AABB border size used during the build of the field. (See: rcConfig::borderSize) - unsigned short maxDistance; ///< The maximum distance value of any span within the field. - unsigned short maxRegions; ///< The maximum region id of any span within the field. - float bmin[3]; ///< The minimum bounds in world space. [(x, y, z)] + unsigned short maxDistance; ///< The maximum distance value of any span within the field. + unsigned short maxRegions; ///< The maximum region id of any span within the field. + float bmin[3]; ///< The minimum bounds in world space. [(x, y, z)] float bmax[3]; ///< The maximum bounds in world space. [(x, y, z)] - float cs; ///< The size of each cell. (On the xz-plane.) + 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.) rcCompactCell* cells; ///< Array of cells. [Size: #width*#height] rcCompactSpan* spans; ///< Array of spans. [Size: #spanCount] @@ -326,26 +346,26 @@ struct rcCompactHeightfield /// @see rcHeightfieldLayerSet struct rcHeightfieldLayer { - float bmin[3]; ///< The minimum bounds in world space. [(x, y, z)] + float bmin[3]; ///< The minimum bounds in world space. [(x, y, z)] float bmax[3]; ///< The maximum bounds in world space. [(x, y, z)] - float cs; ///< The size of each cell. (On the xz-plane.) + 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 width; ///< The width of the heightfield. (Along the x-axis in cell units.) + 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 minx; ///< The minimum x-bounds of usable data. - int maxx; ///< The maximum x-bounds of usable data. - int miny; ///< The minimum y-bounds of usable data. (Along the z-axis.) + int minx; ///< The minimum x-bounds of usable data. + int maxx; ///< The maximum x-bounds of usable data. + int miny; ///< The minimum y-bounds of usable data. (Along the z-axis.) int maxy; ///< The maximum y-bounds of usable data. (Along the z-axis.) - int hmin; ///< The minimum height bounds of usable data. (Along the y-axis.) + int hmin; ///< The minimum height bounds of usable data. (Along the y-axis.) int hmax; ///< The maximum height bounds of usable data. (Along the y-axis.) - unsigned char* heights; ///< The heightfield. [Size: (width - borderSize*2) * (h - borderSize*2)] + unsigned char* heights; ///< The heightfield. [Size: width * height] unsigned char* areas; ///< Area ids. [Size: Same as #heights] unsigned char* cons; ///< Packed neighbor connection information. [Size: Same as #heights] }; /// Represents a set of heightfield layers. /// @ingroup recast -/// @see rcAllocHeightfieldLayerSet, rcFreeHeightfieldLayerSet +/// @see rcAllocHeightfieldLayerSet, rcFreeHeightfieldLayerSet struct rcHeightfieldLayerSet { rcHeightfieldLayer* layers; ///< The layers in the set. [Size: #nlayers] @@ -356,9 +376,9 @@ struct rcHeightfieldLayerSet struct rcContour { int* verts; ///< Simplified contour vertex and connection data. [Size: 4 * #nverts] - int nverts; ///< The number of vertices in the simplified contour. + int nverts; ///< The number of vertices in the simplified contour. int* rverts; ///< Raw contour vertex and connection data. [Size: 4 * #nrverts] - int nrverts; ///< The number of vertices in the raw contour. + int nrverts; ///< The number of vertices in the raw contour. unsigned short reg; ///< The region id of the contour. unsigned char area; ///< The area id of the contour. }; @@ -371,17 +391,18 @@ struct rcContourSet int nconts; ///< The number of contours in the set. float bmin[3]; ///< The minimum bounds in world space. [(x, y, z)] float bmax[3]; ///< The maximum bounds in world space. [(x, y, z)] - float cs; ///< The size of each cell. (On the xz-plane.) + 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 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 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. +/// Represents a polygon mesh suitable for use in building a navigation mesh. /// @ingroup recast struct 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] @@ -391,24 +412,25 @@ struct rcPolyMesh int npolys; ///< The number of polygons. int maxpolys; ///< The number of allocated polygons. int nvp; ///< The maximum number of vertices per polygon. - float bmin[3]; ///< The minimum bounds in world space. [(x, y, z)] - float bmax[3]; ///< The maximum bounds in world space. [(x, y, z)] - float cs; ///< The size of each cell. (On the xz-plane.) + float bmin[3]; ///< The minimum bounds in world space. [(x, y, z)] + float bmax[3]; ///< The maximum bounds in world space. [(x, y, z)] + 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 +/// Contains triangle meshes that represent detailed height data associated /// with the polygons in its associated polygon mesh object. /// @ingroup recast struct rcPolyMeshDetail { - unsigned int* meshes; ///< The sub-mesh data. [Size: 4*#nmeshes] - float* verts; ///< The mesh vertices. [Size: 3*#nverts] - unsigned char* tris; ///< The mesh triangles. [Size: 4*#ntris] - int nmeshes; ///< The number of sub-meshes defined by #meshes. - int nverts; ///< The number of vertices in #verts. - int ntris; ///< The number of triangles in #tris. + unsigned int* meshes; ///< The sub-mesh data. [Size: 4*#nmeshes] + float* verts; ///< The mesh vertices. [Size: 3*#nverts] + unsigned char* tris; ///< The mesh triangles. [Size: 4*#ntris] + int nmeshes; ///< The number of sub-meshes defined by #meshes. + int nverts; ///< The number of vertices in #verts. + int ntris; ///< The number of triangles in #tris. }; /// @name Allocation Functions @@ -423,7 +445,7 @@ struct rcPolyMeshDetail rcHeightfield* rcAllocHeightfield(); /// Frees the specified heightfield object using the Recast allocator. -/// @param[in] hf A heightfield allocated using #rcAllocHeightfield +/// @param[in] hf A heightfield allocated using #rcAllocHeightfield /// @ingroup recast /// @see rcAllocHeightfield void rcFreeHeightField(rcHeightfield* hf); @@ -435,7 +457,7 @@ void rcFreeHeightField(rcHeightfield* hf); rcCompactHeightfield* rcAllocCompactHeightfield(); /// Frees the specified compact heightfield object using the Recast allocator. -/// @param[in] chf A compact heightfield allocated using #rcAllocCompactHeightfield +/// @param[in] chf A compact heightfield allocated using #rcAllocCompactHeightfield /// @ingroup recast /// @see rcAllocCompactHeightfield void rcFreeCompactHeightfield(rcCompactHeightfield* chf); @@ -447,7 +469,7 @@ void rcFreeCompactHeightfield(rcCompactHeightfield* chf); rcHeightfieldLayerSet* rcAllocHeightfieldLayerSet(); /// Frees the specified heightfield layer set using the Recast allocator. -/// @param[in] lset A heightfield layer set allocated using #rcAllocHeightfieldLayerSet +/// @param[in] lset A heightfield layer set allocated using #rcAllocHeightfieldLayerSet /// @ingroup recast /// @see rcAllocHeightfieldLayerSet void rcFreeHeightfieldLayerSet(rcHeightfieldLayerSet* lset); @@ -459,7 +481,7 @@ void rcFreeHeightfieldLayerSet(rcHeightfieldLayerSet* lset); rcContourSet* rcAllocContourSet(); /// Frees the specified contour set using the Recast allocator. -/// @param[in] cset A contour set allocated using #rcAllocContourSet +/// @param[in] cset A contour set allocated using #rcAllocContourSet /// @ingroup recast /// @see rcAllocContourSet void rcFreeContourSet(rcContourSet* cset); @@ -471,7 +493,7 @@ void rcFreeContourSet(rcContourSet* cset); rcPolyMesh* rcAllocPolyMesh(); /// Frees the specified polygon mesh using the Recast allocator. -/// @param[in] pmesh A polygon mesh allocated using #rcAllocPolyMesh +/// @param[in] pmesh A polygon mesh allocated using #rcAllocPolyMesh /// @ingroup recast /// @see rcAllocPolyMesh void rcFreePolyMesh(rcPolyMesh* pmesh); @@ -483,7 +505,7 @@ void rcFreePolyMesh(rcPolyMesh* pmesh); rcPolyMeshDetail* rcAllocPolyMeshDetail(); /// Frees the specified detail mesh using the Recast allocator. -/// @param[in] dmesh A detail mesh allocated using #rcAllocPolyMeshDetail +/// @param[in] dmesh A detail mesh allocated using #rcAllocPolyMeshDetail /// @ingroup recast /// @see rcAllocPolyMeshDetail void rcFreePolyMeshDetail(rcPolyMeshDetail* dmesh); @@ -491,16 +513,24 @@ void rcFreePolyMeshDetail(rcPolyMeshDetail* dmesh); /// @} /// Heighfield border flag. -/// If a heightfield region ID has this bit set, then the region is a border +/// If a heightfield region ID has this bit set, then the region is a border /// region and its spans are considered unwalkable. /// (Used during the region and contour build process.) /// @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 -/// vertex will later be removed in order to match the segments and vertices +/// a tile border. If a contour vertex's region ID has this bit set, the +/// vertex will later be removed in order to match the segments and vertices /// at tile boundaries. /// (Used during the build process.) /// @see rcCompactSpan::reg, #rcContour::verts, #rcContour::rverts @@ -533,13 +563,13 @@ static const int RC_CONTOUR_REG_MASK = 0xffff; static const unsigned short RC_MESH_NULL_IDX = 0xffff; /// Represents the null area. -/// When a data element is given this value it is considered to no longer be +/// When a data element is given this value it is considered to no longer be /// assigned to a usable area. (E.g. It is unwalkable.) static const unsigned char RC_NULL_AREA = 0; -/// The default area id used to indicate a walkable polygon. -/// This is also the maximum allowed area id, and the only non-null area id -/// recognized by some steps in the build process. +/// The default area id used to indicate a walkable polygon. +/// This is also the maximum allowed area id, and the only non-null area id +/// recognized by some steps in the build process. static const unsigned char RC_WALKABLE_AREA = 63; /// The value returned by #rcGetCon if the specified direction is not connected @@ -549,58 +579,58 @@ static const int RC_NOT_CONNECTED = 0x3f; /// @name General helper functions /// @{ +/// Used to ignore a function parameter. VS complains about unused parameters +/// and this silences the warning. +/// @param [in] _ Unused parameter +template<class T> void rcIgnoreUnused(const T&) { } + /// Swaps the values of the two parameters. -/// @param[in,out] a Value A -/// @param[in,out] b Value B +/// @param[in,out] a Value A +/// @param[in,out] b Value B template<class T> inline void rcSwap(T& a, T& b) { T t = a; a = b; b = t; } /// Returns the minimum of two values. -/// @param[in] a Value A -/// @param[in] b Value B +/// @param[in] a Value A +/// @param[in] b Value B /// @return The minimum of the two values. template<class T> inline T rcMin(T a, T b) { return a < b ? a : b; } /// Returns the maximum of two values. -/// @param[in] a Value A -/// @param[in] b Value B +/// @param[in] a Value A +/// @param[in] b Value B /// @return The maximum of the two values. template<class T> inline T rcMax(T a, T b) { return a > b ? a : b; } /// Returns the absolute value. -/// @param[in] a The value. +/// @param[in] a The value. /// @return The absolute value of the specified value. template<class T> inline T rcAbs(T a) { return a < 0 ? -a : a; } -/// Return the square of a value. -/// @param[in] a The value. +/// Returns the square of the value. +/// @param[in] a The value. /// @return The square of the value. template<class T> inline T rcSqr(T a) { return a*a; } /// Clamps the value to the specified range. -/// @param[in] v The value to clamp. -/// @param[in] mn The minimum permitted return value. -/// @param[in] mx The maximum permitted return value. +/// @param[in] v The value to clamp. +/// @param[in] mn The minimum permitted return value. +/// @param[in] mx The maximum permitted return value. /// @return The value, clamped to the specified range. template<class T> inline T rcClamp(T v, T mn, T mx) { return v < mn ? mn : (v > mx ? mx : v); } /// Returns the square root of the value. -/// @param[in] x The value. +/// @param[in] x The value. /// @return The square root of the vlaue. float rcSqrt(float x); -/// Not documented. Internal use only. -/// @param[in] x Not documented. -/// @return Not documented. -inline int rcAlign4(int x) { return (x+3) & ~3; } - /// @} /// @name Vector helper functions. /// @{ -/// Derives the cross product of two vectors. (v1 x v2) -/// @param[out] dest The cross product. [(x, y, z)] -/// @param[in] v1 A Vector [(x, y, z)] -/// @param[in] v2 A vector [(x, y, z)] +/// Derives the cross product of two vectors. (@p v1 x @p v2) +/// @param[out] dest The cross product. [(x, y, z)] +/// @param[in] v1 A Vector [(x, y, z)] +/// @param[in] v2 A vector [(x, y, z)] inline void rcVcross(float* dest, const float* v1, const float* v2) { dest[0] = v1[1]*v2[2] - v1[2]*v2[1]; @@ -608,20 +638,20 @@ inline void rcVcross(float* dest, const float* v1, const float* v2) dest[2] = v1[0]*v2[1] - v1[1]*v2[0]; } -/// Derives the dot product of two vectors. (v1 . v2) -/// @param[in] v1 A Vector [(x, y, z)] -/// @param[in] v2 A vector [(x, y, z)] -/// @return The dot product. +/// Derives the dot product of two vectors. (@p v1 . @p v2) +/// @param[in] v1 A Vector [(x, y, z)] +/// @param[in] v2 A vector [(x, y, z)] +/// @return The dot product. inline float rcVdot(const float* v1, const float* v2) { return v1[0]*v2[0] + v1[1]*v2[1] + v1[2]*v2[2]; } -/// Performs a scaled vector addition. (v1 + (v2 * s)) -/// @param[out] dest The result vector. [(x, y, z)] -/// @param[in] v1 The base vector [(x, y, z)] -/// @param[in] v2 The vector to scale and add to @p v1. [(x, y, z)] -/// @param[in] s The amount to scale @p v2 by before adding to @p v1. +/// Performs a scaled vector addition. (@p v1 + (@p v2 * @p s)) +/// @param[out] dest The result vector. [(x, y, z)] +/// @param[in] v1 The base vector. [(x, y, z)] +/// @param[in] v2 The vector to scale and add to @p v1. [(x, y, z)] +/// @param[in] s The amount to scale @p v2 by before adding to @p v1. inline void rcVmad(float* dest, const float* v1, const float* v2, const float s) { dest[0] = v1[0]+v2[0]*s; @@ -630,9 +660,9 @@ inline void rcVmad(float* dest, const float* v1, const float* v2, const float s) } /// Performs a vector addition. (@p v1 + @p v2) -/// @param[out] dest The result vector. [(x, y, z)] -/// @param[in] v1 The base vector [(x, y, z)] -/// @param[in] v2 The vector to add to @p v1. [(x, y, z)] +/// @param[out] dest The result vector. [(x, y, z)] +/// @param[in] v1 The base vector. [(x, y, z)] +/// @param[in] v2 The vector to add to @p v1. [(x, y, z)] inline void rcVadd(float* dest, const float* v1, const float* v2) { dest[0] = v1[0]+v2[0]; @@ -641,9 +671,9 @@ inline void rcVadd(float* dest, const float* v1, const float* v2) } /// Performs a vector subtraction. (@p v1 - @p v2) -/// @param[out] dest The result vector. [(x, y, z)] -/// @param[in] v1 The base vector [(x, y, z)] -/// @param[in] v2 The vector to subtract from @p v1. [(x, y, z)] +/// @param[out] dest The result vector. [(x, y, z)] +/// @param[in] v1 The base vector. [(x, y, z)] +/// @param[in] v2 The vector to subtract from @p v1. [(x, y, z)] inline void rcVsub(float* dest, const float* v1, const float* v2) { dest[0] = v1[0]-v2[0]; @@ -652,8 +682,8 @@ inline void rcVsub(float* dest, const float* v1, const float* v2) } /// Selects the minimum value of each element from the specified vectors. -/// @param[in, out] mn A vector. (Will be updated with the result.) [(x, y, z)] -/// @param[in] v A vector. [(x, y, z)] +/// @param[in,out] mn A vector. (Will be updated with the result.) [(x, y, z)] +/// @param[in] v A vector. [(x, y, z)] inline void rcVmin(float* mn, const float* v) { mn[0] = rcMin(mn[0], v[0]); @@ -662,8 +692,8 @@ inline void rcVmin(float* mn, const float* v) } /// Selects the maximum value of each element from the specified vectors. -/// @param[in, out] mx A vector. (Will be updated with the result.) [(x, y, z)] -/// @param[in] v A vector. [(x, y, z)] +/// @param[in,out] mx A vector. (Will be updated with the result.) [(x, y, z)] +/// @param[in] v A vector. [(x, y, z)] inline void rcVmax(float* mx, const float* v) { mx[0] = rcMax(mx[0], v[0]); @@ -672,8 +702,8 @@ inline void rcVmax(float* mx, const float* v) } /// Performs a vector copy. -/// @param[out] dest The result. [(x, y, z)] -/// @param[in] v The vector to copy [(x, y, z)] +/// @param[out] dest The result. [(x, y, z)] +/// @param[in] v The vector to copy. [(x, y, z)] inline void rcVcopy(float* dest, const float* v) { dest[0] = v[0]; @@ -682,9 +712,9 @@ inline void rcVcopy(float* dest, const float* v) } /// Returns the distance between two points. -/// @param[in] v1 A point. [(x, y, z)] -/// @param[in] v2 A point. [(x, y, z)] -/// @return The distance between the two points. +/// @param[in] v1 A point. [(x, y, z)] +/// @param[in] v2 A point. [(x, y, z)] +/// @return The distance between the two points. inline float rcVdist(const float* v1, const float* v2) { float dx = v2[0] - v1[0]; @@ -694,9 +724,9 @@ inline float rcVdist(const float* v1, const float* v2) } /// Returns the square of the distance between two points. -/// @param[in] v1 A point. [(x, y, z)] -/// @param[in] v2 A point. [(x, y, z)] -/// @return The square of the distance between the two points. +/// @param[in] v1 A point. [(x, y, z)] +/// @param[in] v2 A point. [(x, y, z)] +/// @return The square of the distance between the two points. inline float rcVdistSqr(const float* v1, const float* v2) { float dx = v2[0] - v1[0]; @@ -706,7 +736,7 @@ inline float rcVdistSqr(const float* v1, const float* v2) } /// Normalizes the vector. -/// @param[in,out] v The vector to normalize. [(x, y, z)] +/// @param[in,out] v The vector to normalize. [(x, y, z)] inline void rcVnormalize(float* v) { float d = 1.0f / rcSqrt(rcSqr(v[0]) + rcSqr(v[1]) + rcSqr(v[2])); @@ -715,17 +745,6 @@ inline void rcVnormalize(float* v) v[2] *= d; } -/// Not documented. Internal use only. -/// @param[in] p0 Not documented. -/// @param[in] p1 Not documented. -/// @return Not documented. -inline bool rcVequal(const float* p0, const float* p1) -{ - static const float thr = rcSqr(1.0f/16384.0f); - const float d = rcVdistSqr(p0, p1); - return d < thr; -} - /// @} /// @name Heightfield Functions /// @see rcHeightfield @@ -733,31 +752,32 @@ inline bool rcVequal(const float* p0, const float* p1) /// Calculates the bounding box of an array of vertices. /// @ingroup recast -/// @param[in] verts An array of vertices. [(x, y, z) * @p nv] -/// @param[in] nv The number of vertices in the @p verts array. -/// @param[out] bmin The minimum bounds of the AABB. [(x, y, z)] [Units: wu] -/// @param[out] bmax The maximum bounds of the AABB. [(x, y, z)] [Units: wu] +/// @param[in] verts An array of vertices. [(x, y, z) * @p nv] +/// @param[in] nv The number of vertices in the @p verts array. +/// @param[out] bmin The minimum bounds of the AABB. [(x, y, z)] [Units: wu] +/// @param[out] bmax The maximum bounds of the AABB. [(x, y, z)] [Units: wu] void rcCalcBounds(const float* verts, int nv, float* bmin, float* bmax); /// Calculates the grid size based on the bounding box and grid cell size. /// @ingroup recast -/// @param[in] bmin The minimum bounds of the AABB. [(x, y, z)] [Units: wu] -/// @param[in] bmax The maximum bounds of the AABB. [(x, y, z)] [Units: wu] -/// @param[in] cs The xz-plane cell size. [Limit: > 0] [Units: wu] -/// @param[out] w The width along the x-axis. [Limit: >= 0] [Units: vx] -/// @param[out] h The height along the z-axis. [Limit: >= 0] [Units: vx] +/// @param[in] bmin The minimum bounds of the AABB. [(x, y, z)] [Units: wu] +/// @param[in] bmax The maximum bounds of the AABB. [(x, y, z)] [Units: wu] +/// @param[in] cs The xz-plane cell size. [Limit: > 0] [Units: wu] +/// @param[out] w The width along the x-axis. [Limit: >= 0] [Units: vx] +/// @param[out] h The height along the z-axis. [Limit: >= 0] [Units: vx] void rcCalcGridSize(const float* bmin, const float* bmax, float cs, int* w, int* h); /// Initializes a new heightfield. /// @ingroup recast -/// @param[in,out] ctx The build context to use during the operation. -/// @param[in,out] hf The allocated heightfield to initialize. -/// @param[in] width The width of the field along the x-axis. [Limit: >= 0] [Units: vx] -/// @param[in] height The height of the field along the z-axis. [Limit: >= 0] [Units: vx] -/// @param[in] bmin The minimum bounds of the field's AABB. [(x, y, z)] [Units: wu] -/// @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] +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in,out] hf The allocated heightfield to initialize. +/// @param[in] width The width of the field along the x-axis. [Limit: >= 0] [Units: vx] +/// @param[in] height The height of the field along the z-axis. [Limit: >= 0] [Units: vx] +/// @param[in] bmin The minimum bounds of the field's AABB. [(x, y, z)] [Units: wu] +/// @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); @@ -765,133 +785,138 @@ bool rcCreateHeightfield(rcContext* ctx, rcHeightfield& hf, int width, int heigh /// Sets the area id of all triangles with a slope below the specified value /// to #RC_WALKABLE_AREA. /// @ingroup recast -/// @param[in,out] ctx The build context to use during the operation. -/// @param[in] walkableSlopeAngle The maximum slope that is considered walkable. [Limits: 0 <= value < 90] -/// [Units: Degrees] -/// @param[in] verts The vertices. [(x, y, z) * @p nv] -/// @param[in] nv The number of vertices. -/// @param[in] tris The triangle vertex indices. [(vertA, vertB, vertC) * @p nt] -/// @param[in] nt The number of triangles. -/// @param[out] areas The triangle area ids. [Length: >= @p nt] +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in] walkableSlopeAngle The maximum slope that is considered walkable. +/// [Limits: 0 <= value < 90] [Units: Degrees] +/// @param[in] verts The vertices. [(x, y, z) * @p nv] +/// @param[in] nv The number of vertices. +/// @param[in] tris The triangle vertex indices. [(vertA, vertB, vertC) * @p nt] +/// @param[in] nt The number of triangles. +/// @param[out] areas The triangle area ids. [Length: >= @p nt] void rcMarkWalkableTriangles(rcContext* ctx, const float walkableSlopeAngle, const float* verts, int nv, - const int* tris, int nt, unsigned char* areas); + const int* tris, int nt, unsigned char* areas); /// Sets the area id of all triangles with a slope greater than or equal to the specified value to #RC_NULL_AREA. /// @ingroup recast -/// @param[in,out] ctx The build context to use during the operation. -/// @param[in] walkableSlopeAngle The maximum slope that is considered walkable. [Limits: 0 <= value < 90] -/// [Units: Degrees] -/// @param[in] verts The vertices. [(x, y, z) * @p nv] -/// @param[in] nv The number of vertices. -/// @param[in] tris The triangle vertex indices. [(vertA, vertB, vertC) * @p nt] -/// @param[in] nt The number of triangles. -/// @param[out] areas The triangle area ids. [Length: >= @p nt] +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in] walkableSlopeAngle The maximum slope that is considered walkable. +/// [Limits: 0 <= value < 90] [Units: Degrees] +/// @param[in] verts The vertices. [(x, y, z) * @p nv] +/// @param[in] nv The number of vertices. +/// @param[in] tris The triangle vertex indices. [(vertA, vertB, vertC) * @p nt] +/// @param[in] nt The number of triangles. +/// @param[out] areas The triangle area ids. [Length: >= @p nt] void rcClearUnwalkableTriangles(rcContext* ctx, const float walkableSlopeAngle, const float* verts, int nv, - const int* tris, int nt, unsigned char* areas); + const int* tris, int nt, unsigned char* areas); /// Adds a span to the specified heightfield. /// @ingroup recast -/// @param[in,out] ctx The build context to use during the operation. -/// @param[in,out] hf An initialized heightfield. -/// @param[in] x The width index where the span is to be added. -/// [Limits: 0 <= value < rcHeightfield::width] -/// @param[in] y The height index where the span is to be added. -/// [Limits: 0 <= value < rcHeightfield::height] -/// @param[in] smin The minimum height of the span. [Limit: < @p smax] [Units: vx] -/// @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, +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in,out] hf An initialized heightfield. +/// @param[in] x The width index where the span is to be added. +/// [Limits: 0 <= value < rcHeightfield::width] +/// @param[in] y The height index where the span is to be added. +/// [Limits: 0 <= value < rcHeightfield::height] +/// @param[in] smin The minimum height of the span. [Limit: < @p smax] [Units: vx] +/// @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] +/// @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); /// Rasterizes a triangle into the specified heightfield. /// @ingroup recast -/// @param[in,out] ctx The build context to use during the operation. -/// @param[in] v0 Triangle vertex 0 [(x, y, z)] -/// @param[in] v1 Triangle vertex 1 [(x, y, z)] -/// @param[in] v2 Triangle vertex 2 [(x, y, z)] -/// @param[in] area The area id of the triangle. [Limit: <= #RC_WALKABLE_AREA] -/// @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, +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in] v0 Triangle vertex 0 [(x, y, z)] +/// @param[in] v1 Triangle vertex 1 [(x, y, z)] +/// @param[in] v2 Triangle vertex 2 [(x, y, z)] +/// @param[in] area The area id of the triangle. [Limit: <= #RC_WALKABLE_AREA] +/// @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] +/// @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); /// Rasterizes an indexed triangle mesh into the specified heightfield. /// @ingroup recast -/// @param[in,out] ctx The build context to use during the operation. -/// @param[in] verts The vertices. [(x, y, z) * @p nv] -/// @param[in] nv The number of vertices. -/// @param[in] tris The triangle indices. [(vertA, vertB, vertC) * @p nt] -/// @param[in] areas The area id's of the triangles. [Limit: <= #RC_WALKABLE_AREA] [Size: @p nt] -/// @param[in] nt The number of triangles. -/// @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, +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in] verts The vertices. [(x, y, z) * @p nv] +/// @param[in] nv The number of vertices. +/// @param[in] tris The triangle indices. [(vertA, vertB, vertC) * @p nt] +/// @param[in] areas The area id's of the triangles. [Limit: <= #RC_WALKABLE_AREA] [Size: @p nt] +/// @param[in] nt The number of triangles. +/// @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] +/// @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); /// Rasterizes an indexed triangle mesh into the specified heightfield. /// @ingroup recast -/// @param[in,out] ctx The build context to use during the operation. -/// @param[in] verts The vertices. [(x, y, z) * @p nv] -/// @param[in] nv The number of vertices. -/// @param[in] tris The triangle indices. [(vertA, vertB, vertC) * @p nt] -/// @param[in] areas The area id's of the triangles. [Limit: <= #RC_WALKABLE_AREA] [Size: @p nt] -/// @param[in] nt The number of triangles. -/// @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, +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in] verts The vertices. [(x, y, z) * @p nv] +/// @param[in] nv The number of vertices. +/// @param[in] tris The triangle indices. [(vertA, vertB, vertC) * @p nt] +/// @param[in] areas The area id's of the triangles. [Limit: <= #RC_WALKABLE_AREA] [Size: @p nt] +/// @param[in] nt The number of triangles. +/// @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] +/// @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); /// Rasterizes triangles into the specified heightfield. /// @ingroup recast -/// @param[in,out] ctx The build context to use during the operation. -/// @param[in] verts The triangle vertices. [(ax, ay, az, bx, by, bz, cx, by, cx) * @p nt] -/// @param[in] areas The area id's of the triangles. [Limit: <= #RC_WALKABLE_AREA] [Size: @p nt] -/// @param[in] nt The number of triangles. -/// @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, +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in] verts The triangle vertices. [(ax, ay, az, bx, by, bz, cx, by, cx) * @p nt] +/// @param[in] areas The area id's of the triangles. [Limit: <= #RC_WALKABLE_AREA] [Size: @p nt] +/// @param[in] nt The number of triangles. +/// @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] +/// @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 neihbor. /// @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. -/// [Limit: >=0] [Units: vx] -/// @param[in,out] solid A fully built heightfield. (All spans have been added.) +/// @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. +/// [Limit: >=0] [Units: vx] +/// @param[in,out] solid A fully built heightfield. (All spans have been added.) void rcFilterLowHangingWalkableObstacles(rcContext* ctx, const int walkableClimb, rcHeightfield& solid); -/// Marks spans that are ledges as not-walkable. +/// Marks spans that are ledges as not-walkable. /// @ingroup recast -/// @param[in,out] ctx The build context to use during the operation. -/// @param[in] walkableHeight Minimum floor to 'ceiling' height that will still allow the floor area to -/// be considered walkable. [Limit: >= 3] [Units: vx] -/// @param[in] walkableClimb Maximum ledge height that is considered to still be traversable. -/// [Limit: >=0] [Units: vx] -/// @param[in,out] solid A fully built heightfield. (All spans have been added.) +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in] walkableHeight Minimum floor to 'ceiling' height that will still allow the floor area to +/// be considered walkable. [Limit: >= 3] [Units: vx] +/// @param[in] walkableClimb Maximum ledge height that is considered to still be traversable. +/// [Limit: >=0] [Units: vx] +/// @param[in,out] solid A fully built heightfield. (All spans have been added.) void rcFilterLedgeSpans(rcContext* ctx, const int walkableHeight, const int walkableClimb, rcHeightfield& solid); -/// Marks walkable spans as not walkable if the clearence above the span is less than the specified height. +/// Marks walkable spans as not walkable if the clearence above the span is less than the specified height. /// @ingroup recast -/// @param[in,out] ctx The build context to use during the operation. -/// @param[in] walkableHeight Minimum floor to 'ceiling' height that will still allow the floor area to -/// be considered walkable. [Limit: >= 3] [Units: vx] -/// @param[in,out] solid A fully built heightfield. (All spans have been added.) +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in] walkableHeight Minimum floor to 'ceiling' height that will still allow the floor area to +/// be considered walkable. [Limit: >= 3] [Units: vx] +/// @param[in,out] solid A fully built heightfield. (All spans have been added.) void rcFilterWalkableLowHeightSpans(rcContext* ctx, int walkableHeight, rcHeightfield& solid); /// Returns the number of spans contained in the specified heightfield. /// @ingroup recast -/// @param[in,out] ctx The build context to use during the operation. -/// @param[in] hf An initialized heightfield. +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in] hf An initialized heightfield. /// @returns The number of spans in the heightfield. int rcGetHeightFieldSpanCount(rcContext* ctx, rcHeightfield& hf); @@ -902,105 +927,128 @@ int rcGetHeightFieldSpanCount(rcContext* ctx, rcHeightfield& hf); /// Builds a compact heightfield representing open space, from a heightfield representing solid space. /// @ingroup recast -/// @param[in,out] ctx The build context to use during the operation. -/// @param[in] walkableHeight Minimum floor to 'ceiling' height that will still allow the floor area -/// to be considered walkable. [Limit: >= 3] [Units: vx] -/// @param[in] walkableClimb Maximum ledge height that is considered to still be traversable. -/// [Limit: >=0] [Units: vx] -/// @param[in] hf The heightfield to be compacted. -/// @param[out] chf The resulting compact heightfield. (Must be pre-allocated.) +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in] walkableHeight Minimum floor to 'ceiling' height that will still allow the floor area +/// to be considered walkable. [Limit: >= 3] [Units: vx] +/// @param[in] walkableClimb Maximum ledge height that is considered to still be traversable. +/// [Limit: >=0] [Units: vx] +/// @param[in] hf The heightfield to be compacted. +/// @param[out] chf The resulting compact heightfield. (Must be pre-allocated.) /// @returns True if the operation completed successfully. bool rcBuildCompactHeightfield(rcContext* ctx, const int walkableHeight, const int walkableClimb, rcHeightfield& hf, rcCompactHeightfield& chf); -/// Erodes the walkable area within the heightfield by the specified radius. +/// Erodes the walkable area within the heightfield by the specified radius. /// @ingroup recast -/// @param[in,out] ctx The build context to use during the operation. -/// @param[in] radius The radius of erosion. [Limits: 0 < value < 255] [Units: vx] -/// @param[in,out] chf The populated compact heightfield to erode. +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in] radius The radius of erosion. [Limits: 0 < value < 255] [Units: vx] +/// @param[in,out] chf The populated compact heightfield to erode. /// @returns True if the operation completed successfully. bool rcErodeWalkableArea(rcContext* ctx, int radius, rcCompactHeightfield& chf); /// Applies a median filter to walkable area types (based on area id), removing noise. /// @ingroup recast -/// @param[in,out] ctx The build context to use during the operation. -/// @param[in,out] chf A populated compact heightfield. +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in,out] chf A populated compact heightfield. /// @returns True if the operation completed successfully. bool rcMedianFilterWalkableArea(rcContext* ctx, rcCompactHeightfield& chf); -/// Applies an area id to all spans within the specified bounding box. (AABB) +/// Applies an area id to all spans within the specified bounding box. (AABB) /// @ingroup recast -/// @param[in,out] ctx The build context to use during the operation. -/// @param[in] bmin The minimum of the bounding box. [(x, y, z)] -/// @param[in] bmax The maximum of the bounding box. [(x, y, z)] -/// @param[in] areaId The area id to apply. [Limit: <= #RC_WALKABLE_AREA] -/// @param[in,out] chf A populated compact heightfield. +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in] bmin The minimum of the bounding box. [(x, y, z)] +/// @param[in] bmax The maximum of the bounding box. [(x, y, z)] +/// @param[in] areaId The area id to apply. [Limit: <= #RC_WALKABLE_AREA] +/// @param[in,out] chf A populated compact heightfield. void rcMarkBoxArea(rcContext* ctx, const float* bmin, const float* bmax, unsigned char areaId, rcCompactHeightfield& chf); -/// Applies the area id to the all spans within the specified convex polygon. +/// Applies the area id to the all spans within the specified convex polygon. /// @ingroup recast -/// @param[in,out] ctx The build context to use during the operation. -/// @param[in] verts The vertices of the polygon [Fomr: (x, y, z) * @p nverts] -/// @param[in] nverts The number of vertices in the polygon. -/// @param[in] hmin The height of the base of the polygon. -/// @param[in] hmax The height of the top of the polygon. -/// @param[in] areaId The area id to apply. [Limit: <= #RC_WALKABLE_AREA] -/// @param[in,out] chf A populated compact heightfield. +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in] verts The vertices of the polygon [Fomr: (x, y, z) * @p nverts] +/// @param[in] nverts The number of vertices in the polygon. +/// @param[in] hmin The height of the base of the polygon. +/// @param[in] hmax The height of the top of the polygon. +/// @param[in] areaId The area id to apply. [Limit: <= #RC_WALKABLE_AREA] +/// @param[in,out] chf A populated compact heightfield. void rcMarkConvexPolyArea(rcContext* ctx, const float* verts, const int nverts, const float hmin, const float hmax, unsigned char areaId, rcCompactHeightfield& chf); +/// Helper function to offset voncex polygons for rcMarkConvexPolyArea. +/// @ingroup recast +/// @param[in] verts The vertices of the polygon [Form: (x, y, z) * @p nverts] +/// @param[in] nverts The number of vertices in the polygon. +/// @param[out] outVerts The offset vertices (should hold up to 2 * @p nverts) [Form: (x, y, z) * return value] +/// @param[in] maxOutVerts The max number of vertices that can be stored to @p outVerts. +/// @returns Number of vertices in the offset polygon or 0 if too few vertices in @p outVerts. +int rcOffsetPoly(const float* verts, const int nverts, const float offset, + float* outVerts, const int maxOutVerts); + /// Applies the area id to all spans within the specified cylinder. /// @ingroup recast -/// @param[in,out] ctx The build context to use during the operation. -/// @param[in] pos The center of the base of the cylinder. [Form: (x, y, z)] -/// @param[in] r The radius of the cylinder. -/// @param[in] h The height of the cylinder. -/// @param[in] areaId The area id to apply. [Limit: <= #RC_WALKABLE_AREA] -/// @param[in,out] chf A populated compact heightfield. +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in] pos The center of the base of the cylinder. [Form: (x, y, z)] +/// @param[in] r The radius of the cylinder. +/// @param[in] h The height of the cylinder. +/// @param[in] areaId The area id to apply. [Limit: <= #RC_WALKABLE_AREA] +/// @param[in,out] chf A populated compact heightfield. void rcMarkCylinderArea(rcContext* ctx, const float* pos, const float r, const float h, unsigned char areaId, rcCompactHeightfield& chf); -/// Builds the distance field for the specified compact heightfield. +/// Builds the distance field for the specified compact heightfield. /// @ingroup recast -/// @param[in,out] ctx The build context to use during the operation. -/// @param[in,out] chf A populated compact heightfield. +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in,out] chf A populated compact heightfield. /// @returns True if the operation completed successfully. bool rcBuildDistanceField(rcContext* ctx, rcCompactHeightfield& chf); -/// Builds region data for the heightfield using watershed partitioning. +/// Builds region data for the heightfield using watershed partitioning. /// @ingroup recast -/// @param[in,out] ctx The build context to use during the operation. -/// @param[in,out] chf A populated compact heightfield. -/// @param[in] borderSize The size of the non-navigable border around the heightfield. [Limit: >=0] [Units: vx] -/// @param[in] minRegionArea The minimum number of cells allowed to form isolated island areas. [Limit: >=0] -/// [Units: vx]. -/// @param[in] mergeRegionArea Any regions with a span count smaller than this value will, if possible, -/// be merged with larger regions. [Limit: >=0] [Units: vx] +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in,out] chf A populated compact heightfield. +/// @param[in] borderSize The size of the non-navigable border around the heightfield. +/// [Limit: >=0] [Units: vx] +/// @param[in] minRegionArea The minimum number of cells allowed to form isolated island areas. +/// [Limit: >=0] [Units: vx]. +/// @param[in] mergeRegionArea Any regions with a span count smaller than this value will, if possible, +/// be merged with larger regions. [Limit: >=0] [Units: vx] /// @returns True if the operation completed successfully. bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf, const int borderSize, const int minRegionArea, const int mergeRegionArea); +/// Builds region data for the heightfield by partitioning the heightfield in non-overlapping layers. +/// @ingroup recast +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in,out] chf A populated compact heightfield. +/// @param[in] borderSize The size of the non-navigable border around the heightfield. +/// [Limit: >=0] [Units: vx] +/// @param[in] minRegionArea The minimum number of cells allowed to form isolated island areas. +/// [Limit: >=0] [Units: vx]. +/// @returns True if the operation completed successfully. +bool rcBuildLayerRegions(rcContext* ctx, rcCompactHeightfield& chf, + const int borderSize, const int minRegionArea); + /// Builds region data for the heightfield using simple monotone partitioning. -/// @ingroup recast -/// @param[in,out] ctx The build context to use during the operation. -/// @param[in,out] chf A populated compact heightfield. -/// @param[in] borderSize The size of the non-navigable border around the heightfield. [Limit: >=0] [Units: vx] -/// @param[in] minRegionArea The minimum number of cells allowed to form isolated island areas. [Limit: >=0] -/// [Units: vx]. -/// @param[in] mergeRegionArea Any regions with a span count smaller than this value will, if possible, -/// be merged with larger regions. [Limit: >=0] [Units: vx] +/// @ingroup recast +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in,out] chf A populated compact heightfield. +/// @param[in] borderSize The size of the non-navigable border around the heightfield. +/// [Limit: >=0] [Units: vx] +/// @param[in] minRegionArea The minimum number of cells allowed to form isolated island areas. +/// [Limit: >=0] [Units: vx]. +/// @param[in] mergeRegionArea Any regions with a span count smaller than this value will, if possible, +/// be merged with larger regions. [Limit: >=0] [Units: vx] /// @returns True if the operation completed successfully. bool rcBuildRegionsMonotone(rcContext* ctx, rcCompactHeightfield& chf, const int borderSize, const int minRegionArea, const int mergeRegionArea); - /// Sets the neighbor connection data for the specified direction. -/// @param[in] s The span to update. -/// @param[in] dir The direction to set. [Limits: 0 <= value < 4] -/// @param[in] i The index of the neighbor span. +/// @param[in] s The span to update. +/// @param[in] dir The direction to set. [Limits: 0 <= value < 4] +/// @param[in] i The index of the neighbor span. inline void rcSetCon(rcCompactSpan& s, int dir, int i) { const unsigned int shift = (unsigned int)dir*6; @@ -1009,10 +1057,10 @@ inline void rcSetCon(rcCompactSpan& s, int dir, int i) } /// Gets neighbor connection data for the specified direction. -/// @param[in] s The span to check. -/// @param[in] dir The direction to check. [Limits: 0 <= value < 4] +/// @param[in] s The span to check. +/// @param[in] dir The direction to check. [Limits: 0 <= value < 4] /// @return The neighbor connection data for the specified direction, -/// or #RC_NOT_CONNECTED if there is no connection. +/// or #RC_NOT_CONNECTED if there is no connection. inline int rcGetCon(const rcCompactSpan& s, int dir) { const unsigned int shift = (unsigned int)dir*6; @@ -1020,25 +1068,35 @@ inline int rcGetCon(const rcCompactSpan& s, int dir) } /// Gets the standard width (x-axis) offset for the specified direction. -/// @param[in] dir The direction. [Limits: 0 <= value < 4] +/// @param[in] dir The direction. [Limits: 0 <= value < 4] /// @return The width offset to apply to the current cell position to move -/// in the direction. +/// 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]; } /// Gets the standard height (z-axis) offset for the specified direction. -/// @param[in] dir The direction. [Limits: 0 <= value < 4] +/// @param[in] dir The direction. [Limits: 0 <= value < 4] /// @return The height offset to apply to the current cell position to move -/// in the direction. +/// 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 @@ -1046,72 +1104,80 @@ inline int rcGetDirOffsetY(int dir) /// Builds a layer set from the specified compact heightfield. /// @ingroup recast -/// @param[in,out] ctx The build context to use during the operation. -/// @param[in] chf A fully built compact heightfield. -/// @param[in] borderSize The size of the non-navigable border around the heightfield. [Limit: >=0] -/// [Units: vx] -/// @param[in] walkableHeight Minimum floor to 'ceiling' height that will still allow the floor area -/// to be considered walkable. [Limit: >= 3] [Units: vx] -/// @param[out] lset The resulting layer set. (Must be pre-allocated.) +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in] chf A fully built compact heightfield. +/// @param[in] borderSize The size of the non-navigable border around the heightfield. [Limit: >=0] +/// [Units: vx] +/// @param[in] walkableHeight Minimum floor to 'ceiling' height that will still allow the floor area +/// to be considered walkable. [Limit: >= 3] [Units: vx] +/// @param[out] lset The resulting layer set. (Must be pre-allocated.) /// @returns True if the operation completed successfully. -bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf, +bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf, const int borderSize, const int walkableHeight, rcHeightfieldLayerSet& lset); /// Builds a contour set from the region outlines in the provided compact heightfield. /// @ingroup recast -/// @param[in,out] ctx The build context to use during the operation. -/// @param[in] chf A fully built compact heightfield. -/// @param[in] maxError The maximum distance a simplfied contour's border edges should deviate -/// the original raw contour. [Limit: >=0] [Units: wu] -/// @param[in] maxEdgeLen The maximum allowed length for contour edges along the border of the mesh. -/// [Limit: >=0] [Units: vx] -/// @param[out] cset The resulting contour set. (Must be pre-allocated.) -/// @param[in] buildFlags The build flags. (See: #rcBuildContoursFlags) +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in] chf A fully built compact heightfield. +/// @param[in] maxError The maximum distance a simplfied contour's border edges should deviate +/// the original raw contour. [Limit: >=0] [Units: wu] +/// @param[in] maxEdgeLen The maximum allowed length for contour edges along the border of the mesh. +/// [Limit: >=0] [Units: vx] +/// @param[out] cset The resulting contour set. (Must be pre-allocated.) +/// @param[in] buildFlags The build flags. (See: #rcBuildContoursFlags) /// @returns True if the operation completed successfully. bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, const float maxError, const int maxEdgeLen, - rcContourSet& cset, const int flags = RC_CONTOUR_TESS_WALL_EDGES); + rcContourSet& cset, const int buildFlags = RC_CONTOUR_TESS_WALL_EDGES); /// Builds a polygon mesh from the provided contours. /// @ingroup recast -/// @param[in,out] ctx The build context to use during the operation. -/// @param[in] cset A fully built contour set. -/// @param[in] nvp The maximum number of vertices allowed for polygons generated during the -/// contour to polygon conversion process. [Limit: >= 3] -/// @param[out] mesh The resulting polygon mesh. (Must be re-allocated.) +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in] cset A fully built contour set. +/// @param[in] nvp The maximum number of vertices allowed for polygons generated during the +/// contour to polygon conversion process. [Limit: >= 3] +/// @param[out] mesh The resulting polygon mesh. (Must be re-allocated.) /// @returns True if the operation completed successfully. bool rcBuildPolyMesh(rcContext* ctx, rcContourSet& cset, const int nvp, rcPolyMesh& mesh); /// Merges multiple polygon meshes into a single mesh. /// @ingroup recast -/// @param[in,out] ctx The build context to use during the operation. -/// @param[in] meshes An array of polygon meshes to merge. [Size: @p nmeshes] -/// @param[in] nmeshes The number of polygon meshes in the meshes array. -/// @param[in] mesh The resulting polygon mesh. (Must be pre-allocated.) +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in] meshes An array of polygon meshes to merge. [Size: @p nmeshes] +/// @param[in] nmeshes The number of polygon meshes in the meshes array. +/// @param[in] mesh The resulting polygon mesh. (Must be pre-allocated.) /// @returns True if the operation completed successfully. bool rcMergePolyMeshes(rcContext* ctx, rcPolyMesh** meshes, const int nmeshes, rcPolyMesh& mesh); /// Builds a detail mesh from the provided polygon mesh. /// @ingroup recast -/// @param[in,out] ctx The build context to use during the operation. -/// @param[in] mesh A fully built polygon mesh. -/// @param[in] chf The compact heightfield used to build the polygon mesh. -/// @param[in] sampleDist Sets the distance to use when samping the heightfield. [Limit: >=0] [Units: wu] -/// @param[in] sampleMaxError The maximum distance the detail mesh surface should deviate from -/// heightfield data. [Limit: >=0] [Units: wu] -/// @param[out] dmesh The resulting detail mesh. (Must be pre-allocated.) +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in] mesh A fully built polygon mesh. +/// @param[in] chf The compact heightfield used to build the polygon mesh. +/// @param[in] sampleDist Sets the distance to use when samping the heightfield. [Limit: >=0] [Units: wu] +/// @param[in] sampleMaxError The maximum distance the detail mesh surface should deviate from +/// heightfield data. [Limit: >=0] [Units: wu] +/// @param[out] dmesh The resulting detail mesh. (Must be pre-allocated.) /// @returns True if the operation completed successfully. bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompactHeightfield& chf, const float sampleDist, const float sampleMaxError, rcPolyMeshDetail& dmesh); +/// Copies the poly mesh data from src to dst. +/// @ingroup recast +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in] src The source mesh to copy from. +/// @param[out] dst The resulting detail mesh. (Must be pre-allocated, must be empty mesh.) +/// @returns True if the operation completed successfully. +bool rcCopyPolyMesh(rcContext* ctx, const rcPolyMesh& src, rcPolyMesh& dst); + /// Merges multiple detail meshes into a single detail mesh. /// @ingroup recast -/// @param[in,out] ctx The build context to use during the operation. -/// @param[in] meshes An array of detail meshes to merge. [Size: @p nmeshes] -/// @param[in] nmeshes The number of detail meshes in the meshes array. -/// @param[out] mesh The resulting detail mesh. (Must be pre-allocated.) +/// @param[in,out] ctx The build context to use during the operation. +/// @param[in] meshes An array of detail meshes to merge. [Size: @p nmeshes] +/// @param[in] nmeshes The number of detail meshes in the meshes array. +/// @param[out] mesh The resulting detail mesh. (Must be pre-allocated.) /// @returns True if the operation completed successfully. bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int nmeshes, rcPolyMeshDetail& mesh); @@ -1123,6 +1189,6 @@ bool buildMeshAdjacency(unsigned short* polys, const int npolys, const int nvert /////////////////////////////////////////////////////////////////////////// -// Due to the large amount of detail documentation for this file, +// Due to the large amount of detail documentation for this file, // the content normally located at the end of the header file has been separated // out to a file in /Docs/Extern. diff --git a/extern/recastnavigation/Recast/Include/RecastAlloc.h b/extern/recastnavigation/Recast/Include/RecastAlloc.h index 0038c1a5c54..f1608fb5537 100644 --- a/extern/recastnavigation/Recast/Include/RecastAlloc.h +++ b/extern/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 @@ -28,30 +30,32 @@ enum rcAllocHint }; /// A memory allocation function. -// @param[in] size The size, in bytes of memory, to allocate. -// @param[in] rcAllocHint A hint to the allocator on how long the memory is expected to be in use. +// @param[in] size The size, in bytes of memory, to allocate. +// @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. /// @see rcAllocSetCustom -// @param[in] ptr typedef void (rcFreeFunc)(void* ptr); /// Sets the base custom allocation functions to be used by Recast. -/// @param[in] allocFunc The memory allocation function to be used by #rcAlloc -/// @param[in] freeFunc The memory de-allocation function to be used by #rcFree +/// @param[in] allocFunc The memory allocation function to be used by #rcAlloc +/// @param[in] freeFunc The memory de-allocation function to be used by #rcFree void rcAllocSetCustom(rcAllocFunc *allocFunc, rcFreeFunc *freeFunc); /// Allocates a memory block. -/// @param[in] size The size, in bytes of memory, to allocate. -/// @param[in] hint A hint to the allocator on how long the memory is expected to be in use. +/// @param[in] size The size, in bytes of memory, to allocate. +/// @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. -void* rcAlloc(int size, rcAllocHint hint); +/// @see rcFree +void* rcAlloc(size_t size, rcAllocHint hint); /// Deallocates a memory block. -/// @param[in] ptr A pointer to a memory block previously allocated using #rcAlloc. +/// @param[in] ptr A pointer to a memory block previously allocated using #rcAlloc. +/// @see rcAlloc void rcFree(void* ptr); @@ -60,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); } + /// @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); } /// Specifies the new size of the integer array. - /// @param[in] n The new size of the integer array. - void resize(int n); + /// @param[in] n The new size of the integer array. + 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; } + /// @param[in] item The new value. + 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]; } + /// @param[in] i The index of the value. + 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]; } + /// @param[in] i The index of the value. + 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. @@ -110,13 +130,18 @@ public: inline rcScopedDelete() : ptr(0) {} /// Constructs an instance with the specified pointer. - /// @param[in] p An pointer to an allocated array. + /// @param[in] p An pointer to an allocated array. inline rcScopedDelete(T* p) : ptr(p) {} inline ~rcScopedDelete() { rcFree(ptr); } /// 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/extern/recastnavigation/Recast/Include/RecastAssert.h b/extern/recastnavigation/Recast/Include/RecastAssert.h index 45cb01fb595..2aca0d9a14f 100644 --- a/extern/recastnavigation/Recast/Include/RecastAssert.h +++ b/extern/recastnavigation/Recast/Include/RecastAssert.h @@ -24,7 +24,7 @@ #ifdef NDEBUG // From http://cnicholson.net/2009/02/stupid-c-tricks-adventures-in-assert/ -# define rcAssert(x) do { (void)sizeof(x); } while((void)(__LINE__ == -1), false) +# define rcAssert(x) do { (void)sizeof(x); } while((void)(__LINE__==-1),false) #else # include <assert.h> # define rcAssert assert diff --git a/extern/recastnavigation/Recast/Include/RecastLog.h b/extern/recastnavigation/Recast/Include/RecastLog.h deleted file mode 100644 index 026ef73a3aa..00000000000 --- a/extern/recastnavigation/Recast/Include/RecastLog.h +++ /dev/null @@ -1,80 +0,0 @@ -// -// Copyright (c) 2009 Mikko Mononen memon@inside.org -// -// This software is provided 'as-is', without any express or implied -// warranty. In no event will the authors be held liable for any damages -// arising from the use of this software. -// Permission is granted to anyone to use this software for any purpose, -// including commercial applications, and to alter it and redistribute it -// freely, subject to the following restrictions: -// 1. The origin of this software must not be misrepresented; you must not -// claim that you wrote the original software. If you use this software -// in a product, an acknowledgment in the product documentation would be -// appreciated but is not required. -// 2. Altered source versions must be plainly marked as such, and must not be -// misrepresented as being the original software. -// 3. This notice may not be removed or altered from any source distribution. -// - -#ifndef RECAST_LOG_H -#define RECAST_LOG_H - -enum rcLogCategory -{ - RC_LOG_PROGRESS = 1, - RC_LOG_WARNING, - RC_LOG_ERROR, -}; - -class rcLog -{ -public: - rcLog(); - ~rcLog(); - - void log(rcLogCategory category, const char* format, ...); - inline void clear() { m_messageCount = 0; m_textPoolSize = 0; } - inline int getMessageCount() const { return m_messageCount; } - inline char getMessageType(int i) const { return *m_messages[i]; } - inline const char* getMessageText(int i) const { return m_messages[i]+1; } - -private: - static const int MAX_MESSAGES = 1000; - const char* m_messages[MAX_MESSAGES]; - int m_messageCount; - static const int TEXT_POOL_SIZE = 8000; - char m_textPool[TEXT_POOL_SIZE]; - int m_textPoolSize; -}; - -struct rcBuildTimes -{ - int rasterizeTriangles; - int buildCompact; - int buildContours; - int buildContoursTrace; - int buildContoursSimplify; - int filterBorder; - int filterWalkable; - int filterMarkReachable; - int buildPolymesh; - int buildDistanceField; - int buildDistanceFieldDist; - int buildDistanceFieldBlur; - int buildRegions; - int buildRegionsReg; - int buildRegionsExp; - int buildRegionsFlood; - int buildRegionsFilter; - int buildDetailMesh; - int mergePolyMesh; - int mergePolyMeshDetail; -}; - -void rcSetLog(rcLog* log); -rcLog* rcGetLog(); - -void rcSetBuildTimes(rcBuildTimes* btimes); -rcBuildTimes* rcGetBuildTimes(); - -#endif // RECAST_LOG_H diff --git a/extern/recastnavigation/Recast/Include/RecastTimer.h b/extern/recastnavigation/Recast/Include/RecastTimer.h deleted file mode 100644 index d4f21e58776..00000000000 --- a/extern/recastnavigation/Recast/Include/RecastTimer.h +++ /dev/null @@ -1,31 +0,0 @@ -// -// Copyright (c) 2009 Mikko Mononen memon@inside.org -// -// This software is provided 'as-is', without any express or implied -// warranty. In no event will the authors be held liable for any damages -// arising from the use of this software. -// Permission is granted to anyone to use this software for any purpose, -// including commercial applications, and to alter it and redistribute it -// freely, subject to the following restrictions: -// 1. The origin of this software must not be misrepresented; you must not -// claim that you wrote the original software. If you use this software -// in a product, an acknowledgment in the product documentation would be -// appreciated but is not required. -// 2. Altered source versions must be plainly marked as such, and must not be -// misrepresented as being the original software. -// 3. This notice may not be removed or altered from any source distribution. -// -#ifndef RECAST_TIMER_H -#define RECAST_TIMER_H - -#ifdef __GNUC__ -#include <stdint.h> -typedef int64_t rcTimeVal; -#else -typedef __int64 rcTimeVal; -#endif - -rcTimeVal rcGetPerformanceTimer(); -int rcGetDeltaTimeUsec(rcTimeVal start, rcTimeVal end); - -#endif // RECAST_TIMER_H diff --git a/extern/recastnavigation/Recast/Source/Recast.cpp b/extern/recastnavigation/Recast/Source/Recast.cpp index 283cf0c128b..46bc8b7810d 100644 --- a/extern/recastnavigation/Recast/Source/Recast.cpp +++ b/extern/recastnavigation/Recast/Source/Recast.cpp @@ -208,12 +208,11 @@ void rcCalcGridSize(const float* bmin, const float* bmax, float cs, int* w, int* /// See the #rcConfig documentation for more information on the configuration parameters. /// /// @see rcAllocHeightfield, rcHeightfield -bool rcCreateHeightfield(rcContext* /*ctx*/, rcHeightfield& hf, int width, int height, +bool rcCreateHeightfield(rcContext* ctx, rcHeightfield& hf, int width, int height, const float* bmin, const float* bmax, float cs, float ch) { - // TODO: VC complains about unref formal variable, figure out a way to handle this better. -// rcAssert(ctx); + rcIgnoreUnused(ctx); hf.width = width; hf.height = height; @@ -239,19 +238,18 @@ static void calcTriNormal(const float* v0, const float* v1, const float* v2, flo /// @par /// -/// Only sets the aread id's for the walkable triangles. Does not alter the +/// Only sets the area id's for the walkable triangles. Does not alter the /// area id's for unwalkable triangles. /// /// See the #rcConfig documentation for more information on the configuration parameters. /// /// @see rcHeightfield, rcClearUnwalkableTriangles, rcRasterizeTriangles -void rcMarkWalkableTriangles(rcContext* /*ctx*/, const float walkableSlopeAngle, +void rcMarkWalkableTriangles(rcContext* ctx, const float walkableSlopeAngle, const float* verts, int /*nv*/, const int* tris, int nt, unsigned char* areas) { - // TODO: VC complains about unref formal variable, figure out a way to handle this better. -// rcAssert(ctx); + rcIgnoreUnused(ctx); const float walkableThr = cosf(walkableSlopeAngle/180.0f*RC_PI); @@ -269,19 +267,18 @@ void rcMarkWalkableTriangles(rcContext* /*ctx*/, const float walkableSlopeAngle, /// @par /// -/// Only sets the aread id's for the unwalkable triangles. Does not alter the +/// Only sets the area id's for the unwalkable triangles. Does not alter the /// area id's for walkable triangles. /// /// See the #rcConfig documentation for more information on the configuration parameters. /// /// @see rcHeightfield, rcClearUnwalkableTriangles, rcRasterizeTriangles -void rcClearUnwalkableTriangles(rcContext* /*ctx*/, const float walkableSlopeAngle, +void rcClearUnwalkableTriangles(rcContext* ctx, const float walkableSlopeAngle, const float* verts, int /*nv*/, const int* tris, int nt, unsigned char* areas) { - // TODO: VC complains about unref formal variable, figure out a way to handle this better. -// rcAssert(ctx); + rcIgnoreUnused(ctx); const float walkableThr = cosf(walkableSlopeAngle/180.0f*RC_PI); @@ -297,10 +294,9 @@ void rcClearUnwalkableTriangles(rcContext* /*ctx*/, const float walkableSlopeAng } } -int rcGetHeightFieldSpanCount(rcContext* /*ctx*/, rcHeightfield& hf) +int rcGetHeightFieldSpanCount(rcContext* ctx, rcHeightfield& hf) { - // TODO: VC complains about unref formal variable, figure out a way to handle this better. -// rcAssert(ctx); + rcIgnoreUnused(ctx); const int w = hf.width; const int h = hf.height; @@ -322,7 +318,7 @@ int rcGetHeightFieldSpanCount(rcContext* /*ctx*/, rcHeightfield& hf) /// @par /// /// This is just the beginning of the process of fully building a compact heightfield. -/// Various filters may be applied applied, then the distance field and regions built. +/// Various filters may be applied, then the distance field and regions built. /// E.g: #rcBuildDistanceField and #rcBuildRegions /// /// See the #rcConfig documentation for more information on the configuration parameters. @@ -333,7 +329,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; @@ -439,13 +435,13 @@ bool rcBuildCompactHeightfield(rcContext* ctx, const int walkableHeight, const i if ((top - bot) >= walkableHeight && rcAbs((int)ns.y - (int)s.y) <= walkableClimb) { // Mark direction as walkable. - const int idx = k - (int)nc.index; - if (idx < 0 || idx > MAX_LAYERS) + const int lidx = k - (int)nc.index; + if (lidx < 0 || lidx > MAX_LAYERS) { - tooHighNeighbour = rcMax(tooHighNeighbour, idx); + tooHighNeighbour = rcMax(tooHighNeighbour, lidx); continue; } - rcSetCon(s, dir, idx); + rcSetCon(s, dir, lidx); break; } } @@ -460,8 +456,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; } @@ -490,4 +484,4 @@ static int getCompactHeightFieldMemoryusage(const rcCompactHeightfield& chf) size += sizeof(rcCompactCell) * chf.width * chf.height; return size; } -*/
\ No newline at end of file +*/ diff --git a/extern/recastnavigation/Recast/Source/RecastAlloc.cpp b/extern/recastnavigation/Recast/Source/RecastAlloc.cpp index b5ec1516146..ee1039f2f4f 100644 --- a/extern/recastnavigation/Recast/Source/RecastAlloc.cpp +++ b/extern/recastnavigation/Recast/Source/RecastAlloc.cpp @@ -20,7 +20,7 @@ #include <string.h> #include "RecastAlloc.h" -static void *rcAllocDefault(int size, rcAllocHint) +static void *rcAllocDefault(size_t size, rcAllocHint) { return malloc(size); } @@ -41,7 +41,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 +72,13 @@ 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); + if (m_size && newData) memcpy(newData, m_data, m_size*sizeof(int)); + rcFree(m_data); + m_data = newData; } diff --git a/extern/recastnavigation/Recast/Source/RecastArea.cpp b/extern/recastnavigation/Recast/Source/RecastArea.cpp index a59acc53eb6..97139cf996a 100644 --- a/extern/recastnavigation/Recast/Source/RecastArea.cpp +++ b/extern/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) @@ -75,8 +75,8 @@ bool rcErodeWalkableArea(rcContext* ctx, int radius, rcCompactHeightfield& chf) { const int nx = x + rcGetDirOffsetX(dir); const int ny = y + rcGetDirOffsetY(dir); - const int ni = (int)chf.cells[nx+ny*w].index + rcGetCon(s, dir); - if (chf.areas[ni] != RC_NULL_AREA) + const int nidx = (int)chf.cells[nx+ny*w].index + rcGetCon(s, dir); + if (chf.areas[nidx] != RC_NULL_AREA) { nc++; } @@ -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,10 +441,86 @@ void rcMarkConvexPolyArea(rcContext* ctx, const float* verts, const int nverts, } } } +} + +int rcOffsetPoly(const float* verts, const int nverts, const float offset, + float* outVerts, const int maxOutVerts) +{ + const float MITER_LIMIT = 1.20f; + + int n = 0; + + for (int i = 0; i < nverts; i++) + { + const int a = (i+nverts-1) % nverts; + const int b = i; + const int c = (i+1) % nverts; + const float* va = &verts[a*3]; + const float* vb = &verts[b*3]; + const float* vc = &verts[c*3]; + float dx0 = vb[0] - va[0]; + float dy0 = vb[2] - va[2]; + float d0 = dx0*dx0 + dy0*dy0; + if (d0 > 1e-6f) + { + d0 = 1.0f/rcSqrt(d0); + dx0 *= d0; + dy0 *= d0; + } + float dx1 = vc[0] - vb[0]; + float dy1 = vc[2] - vb[2]; + float d1 = dx1*dx1 + dy1*dy1; + if (d1 > 1e-6f) + { + d1 = 1.0f/rcSqrt(d1); + dx1 *= d1; + dy1 *= d1; + } + const float dlx0 = -dy0; + const float dly0 = dx0; + const float dlx1 = -dy1; + const float dly1 = dx1; + float cross = dx1*dy0 - dx0*dy1; + float dmx = (dlx0 + dlx1) * 0.5f; + float dmy = (dly0 + dly1) * 0.5f; + float dmr2 = dmx*dmx + dmy*dmy; + bool bevel = dmr2 * MITER_LIMIT*MITER_LIMIT < 1.0f; + if (dmr2 > 1e-6f) + { + const float scale = 1.0f / dmr2; + dmx *= scale; + dmy *= scale; + } - ctx->stopTimer(RC_TIMER_MARK_CONVEXPOLY_AREA); + if (bevel && cross < 0.0f) + { + if (n+2 >= maxOutVerts) + return 0; + float d = (1.0f - (dx0*dx1 + dy0*dy1))*0.5f; + outVerts[n*3+0] = vb[0] + (-dlx0+dx0*d)*offset; + outVerts[n*3+1] = vb[1]; + outVerts[n*3+2] = vb[2] + (-dly0+dy0*d)*offset; + n++; + outVerts[n*3+0] = vb[0] + (-dlx1-dx1*d)*offset; + outVerts[n*3+1] = vb[1]; + outVerts[n*3+2] = vb[2] + (-dly1-dy1*d)*offset; + n++; + } + else + { + if (n+1 >= maxOutVerts) + return 0; + outVerts[n*3+0] = vb[0] - dmx*offset; + outVerts[n*3+1] = vb[1]; + outVerts[n*3+2] = vb[2] - dmy*offset; + n++; + } + } + + return n; } + /// @par /// /// The value of spacial parameters are in world units. @@ -463,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; @@ -519,6 +588,4 @@ void rcMarkCylinderArea(rcContext* ctx, const float* pos, } } } - - ctx->stopTimer(RC_TIMER_MARK_CYLINDER_AREA); } diff --git a/extern/recastnavigation/Recast/Source/RecastContour.cpp b/extern/recastnavigation/Recast/Source/RecastContour.cpp index df943838ffb..277ab015018 100644 --- a/extern/recastnavigation/Recast/Source/RecastContour.cpp +++ b/extern/recastnavigation/Recast/Source/RecastContour.cpp @@ -20,6 +20,7 @@ #include <math.h> #include <string.h> #include <stdio.h> +#include <stdlib.h> #include "Recast.h" #include "RecastAlloc.h" #include "RecastAssert.h" @@ -36,7 +37,7 @@ static int getCornerHeight(int x, int y, int i, int dir, unsigned int regs[4] = {0,0,0,0}; // Combine region and area codes in order to prevent - // border vertices which are in between two areas to be removed. + // border vertices which are in between two areas to be removed. regs[0] = chf.spans[i].reg | (chf.areas[i] << 16); if (rcGetCon(s, dir) != RC_NOT_CONNECTED) @@ -187,27 +188,6 @@ static float distancePtSeg(const int x, const int z, const int px, const int pz, const int qx, const int qz) { -/* float pqx = (float)(qx - px); - float pqy = (float)(qy - py); - float pqz = (float)(qz - pz); - float dx = (float)(x - px); - float dy = (float)(y - py); - float dz = (float)(z - pz); - float d = pqx*pqx + pqy*pqy + pqz*pqz; - float t = pqx*dx + pqy*dy + pqz*dz; - if (d > 0) - t /= d; - if (t < 0) - t = 0; - else if (t > 1) - t = 1; - - dx = px + t*pqx - x; - dy = py + t*pqy - y; - dz = pz + t*pqz - z; - - return dx*dx + dy*dy + dz*dz;*/ - float pqx = (float)(qx - px); float pqz = (float)(qz - pz); float dx = (float)(x - px); @@ -257,13 +237,13 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified, simplified.push(points[i*4+2]); simplified.push(i); } - } + } } if (simplified.size() == 0) { // If there is no connections at all, - // create some initial points for the simplification process. + // create some initial points for the simplification process. // Find lower-left and upper-right vertices of the contour. int llx = points[0]; int lly = points[1]; @@ -311,19 +291,19 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified, { int ii = (i+1) % (simplified.size()/4); - const int ax = simplified[i*4+0]; - const int az = simplified[i*4+2]; - const int ai = simplified[i*4+3]; - - const int bx = simplified[ii*4+0]; - const int bz = simplified[ii*4+2]; - const int bi = simplified[ii*4+3]; + int ax = simplified[i*4+0]; + int az = simplified[i*4+2]; + int ai = simplified[i*4+3]; + + int bx = simplified[ii*4+0]; + int bz = simplified[ii*4+2]; + int bi = simplified[ii*4+3]; // Find maximum deviation from the segment. float maxd = 0; - int i_max = -1; + int maxi = -1; int ci, cinc, endi; - + // Traverse the segment in lexilogical order so that the // max deviation is calculated similarly when traversing // opposite segments. @@ -338,6 +318,8 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified, cinc = pn-1; ci = (bi+cinc) % pn; endi = ai; + rcSwap(ax, bx); + rcSwap(az, bz); } // Tessellate only outer edges or edges between areas. @@ -350,7 +332,7 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified, if (d > maxd) { maxd = d; - i_max = ci; + maxi = ci; } ci = (ci+cinc) % pn; } @@ -359,7 +341,7 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified, // If the max deviation is larger than accepted error, // add new point, else continue to next segment. - if (i_max != -1 && maxd > (maxError*maxError)) + if (maxi != -1 && maxd > (maxError*maxError)) { // Add space for the new point. simplified.resize(simplified.size()+4); @@ -372,10 +354,10 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified, simplified[j*4+3] = simplified[(j-1)*4+3]; } // Add the point. - simplified[(i+1)*4+0] = points[i_max*4+0]; - simplified[(i+1)*4+1] = points[i_max*4+1]; - simplified[(i+1)*4+2] = points[i_max*4+2]; - simplified[(i+1)*4+3] = i_max; + simplified[(i+1)*4+0] = points[maxi*4+0]; + simplified[(i+1)*4+1] = points[maxi*4+1]; + simplified[(i+1)*4+2] = points[maxi*4+2]; + simplified[(i+1)*4+3] = maxi; } else { @@ -397,11 +379,11 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified, const int bx = simplified[ii*4+0]; const int bz = simplified[ii*4+2]; const int bi = simplified[ii*4+3]; - + // Find maximum deviation from the segment. - int i_max = -1; + int maxi = -1; int ci = (ai+1) % pn; - + // Tessellate only outer edges or edges between areas. bool tess = false; // Wall edges. @@ -420,22 +402,20 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified, // Round based on the segments in lexilogical order so that the // max tesselation is consistent regardles in which direction // segments are traversed. - if (bx > ax || (bx == ax && bz > az)) + const int n = bi < ai ? (bi+pn - ai) : (bi - ai); + if (n > 1) { - const int n = bi < ai ? (bi+pn - ai) : (bi - ai); - i_max = (ai + n/2) % pn; - } - else - { - const int n = bi < ai ? (bi+pn - ai) : (bi - ai); - i_max = (ai + (n+1)/2) % pn; + if (bx > ax || (bx == ax && bz > az)) + maxi = (ai + n/2) % pn; + else + maxi = (ai + (n+1)/2) % pn; } } } // If the max deviation is larger than accepted error, // add new point, else continue to next segment. - if (i_max != -1) + if (maxi != -1) { // Add space for the new point. simplified.resize(simplified.size()+4); @@ -448,10 +428,10 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified, simplified[j*4+3] = simplified[(j-1)*4+3]; } // Add the point. - simplified[(i+1)*4+0] = points[i_max*4+0]; - simplified[(i+1)*4+1] = points[i_max*4+1]; - simplified[(i+1)*4+2] = points[i_max*4+2]; - simplified[(i+1)*4+3] = i_max; + simplified[(i+1)*4+0] = points[maxi*4+0]; + simplified[(i+1)*4+1] = points[maxi*4+1]; + simplified[(i+1)*4+2] = points[maxi*4+2]; + simplified[(i+1)*4+3] = maxi; } else { @@ -466,37 +446,11 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified, // and the neighbour region is take from the next raw point. const int ai = (simplified[i*4+3]+1) % pn; const int bi = simplified[i*4+3]; - simplified[i*4+3] = (points[ai*4+3] & RC_CONTOUR_REG_MASK) | (points[bi*4+3] & RC_BORDER_VERTEX); + simplified[i*4+3] = (points[ai*4+3] & (RC_CONTOUR_REG_MASK|RC_AREA_BORDER)) | (points[bi*4+3] & RC_BORDER_VERTEX); } } -static void removeDegenerateSegments(rcIntArray& simplified) -{ - // Remove adjacent vertices which are equal on xz-plane, - // or else the triangulator will get confused. - for (int i = 0; i < simplified.size()/4; ++i) - { - int ni = i+1; - if (ni >= (simplified.size()/4)) - ni = 0; - - if (simplified[i*4+0] == simplified[ni*4+0] && - simplified[i*4+2] == simplified[ni*4+2]) - { - // Degenerate segment, remove. - for (int j = i; j < simplified.size()/4-1; ++j) - { - simplified[j*4+0] = simplified[(j+1)*4+0]; - simplified[j*4+1] = simplified[(j+1)*4+1]; - simplified[j*4+2] = simplified[(j+1)*4+2]; - simplified[j*4+3] = simplified[(j+1)*4+3]; - } - simplified.resize(simplified.size()-4); - } - } -} - static int calcAreaOfPolygon2D(const int* verts, const int nverts) { int area = 0; @@ -509,54 +463,155 @@ static int calcAreaOfPolygon2D(const int* verts, const int nverts) return (area+1) / 2; } -inline bool ileft(const int* a, const int* b, const int* c) +// TODO: these are the same as in RecastMesh.cpp, consider using the same. +// Last time I checked the if version got compiled using cmov, which was a lot faster than module (with idiv). +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; } + +inline int area2(const int* a, const int* b, const int* c) +{ + return (b[0] - a[0]) * (c[2] - a[2]) - (c[0] - a[0]) * (b[2] - a[2]); +} + +// Exclusive or: true iff exactly one argument is true. +// The arguments are negated to ensure that they are 0/1 +// values. Then the bitwise Xor operator may apply. +// (This idea is due to Michael Baldwin.) +inline bool xorb(bool x, bool y) { - return (b[0] - a[0]) * (c[2] - a[2]) - (c[0] - a[0]) * (b[2] - a[2]) <= 0; + return !x ^ !y; } -static void getClosestIndices(const int* vertsa, const int nvertsa, - const int* vertsb, const int nvertsb, - int& ia, int& ib) +// Returns true iff c is strictly to the left of the directed +// line through a to b. +inline bool left(const int* a, const int* b, const int* c) { - int closestDist = 0xfffffff; - ia = -1, ib = -1; - for (int i = 0; i < nvertsa; ++i) + return area2(a, b, c) < 0; +} + +inline bool leftOn(const int* a, const int* b, const int* c) +{ + return area2(a, b, c) <= 0; +} + +inline bool collinear(const int* a, const int* b, const int* c) +{ + return area2(a, b, c) == 0; +} + +// Returns true iff ab properly intersects cd: they share +// a point interior to both segments. The properness of the +// intersection is ensured by using strict leftness. +static bool intersectProp(const int* a, const int* b, const int* c, const int* d) +{ + // Eliminate improper cases. + if (collinear(a,b,c) || collinear(a,b,d) || + collinear(c,d,a) || collinear(c,d,b)) + return false; + + return xorb(left(a,b,c), left(a,b,d)) && xorb(left(c,d,a), left(c,d,b)); +} + +// Returns T iff (a,b,c) are collinear and point c lies +// on the closed segement ab. +static bool between(const int* a, const int* b, const int* c) +{ + if (!collinear(a, b, c)) + return false; + // If ab not vertical, check betweenness on x; else on y. + if (a[0] != b[0]) + return ((a[0] <= c[0]) && (c[0] <= b[0])) || ((a[0] >= c[0]) && (c[0] >= b[0])); + else + return ((a[2] <= c[2]) && (c[2] <= b[2])) || ((a[2] >= c[2]) && (c[2] >= b[2])); +} + +// Returns true iff segments ab and cd intersect, properly or improperly. +static bool intersect(const int* a, const int* b, const int* c, const int* d) +{ + if (intersectProp(a, b, c, d)) + return true; + else if (between(a, b, c) || between(a, b, d) || + between(c, d, a) || between(c, d, b)) + return true; + else + return false; +} + +static bool vequal(const int* a, const int* b) +{ + return a[0] == b[0] && a[2] == b[2]; +} + +static bool intersectSegCountour(const int* d0, const int* d1, int i, int n, const int* verts) +{ + // For each edge (k,k+1) of P + for (int k = 0; k < n; k++) + { + int k1 = next(k, n); + // Skip edges incident to i. + if (i == k || i == k1) + continue; + const int* p0 = &verts[k * 4]; + const int* p1 = &verts[k1 * 4]; + if (vequal(d0, p0) || vequal(d1, p0) || vequal(d0, p1) || vequal(d1, p1)) + continue; + + if (intersect(d0, d1, p0, p1)) + return true; + } + return false; +} + +static bool inCone(int i, int n, const int* verts, const int* pj) +{ + const int* pi = &verts[i * 4]; + const int* pi1 = &verts[next(i, n) * 4]; + const int* pin1 = &verts[prev(i, n) * 4]; + + // If P[i] is a convex vertex [ i+1 left or on (i-1,i) ]. + if (leftOn(pin1, pi, pi1)) + return left(pi, pj, pin1) && left(pj, pi, pi1); + // Assume (i-1,i,i+1) not collinear. + // else P[i] is reflex. + return !(leftOn(pi, pj, pi1) && leftOn(pj, pi, pin1)); +} + + +static void removeDegenerateSegments(rcIntArray& simplified) +{ + // Remove adjacent vertices which are equal on xz-plane, + // or else the triangulator will get confused. + int npts = simplified.size()/4; + for (int i = 0; i < npts; ++i) { - const int in = (i+1) % nvertsa; - const int ip = (i+nvertsa-1) % nvertsa; - const int* va = &vertsa[i*4]; - const int* van = &vertsa[in*4]; - const int* vap = &vertsa[ip*4]; + int ni = next(i, npts); - for (int j = 0; j < nvertsb; ++j) + if (vequal(&simplified[i*4], &simplified[ni*4])) { - const int* vb = &vertsb[j*4]; - // vb must be "infront" of va. - if (ileft(vap,va,vb) && ileft(va,van,vb)) + // Degenerate segment, remove. + for (int j = i; j < simplified.size()/4-1; ++j) { - const int dx = vb[0] - va[0]; - const int dz = vb[2] - va[2]; - const int d = dx*dx + dz*dz; - if (d < closestDist) - { - ia = i; - ib = j; - closestDist = d; - } + simplified[j*4+0] = simplified[(j+1)*4+0]; + simplified[j*4+1] = simplified[(j+1)*4+1]; + simplified[j*4+2] = simplified[(j+1)*4+2]; + simplified[j*4+3] = simplified[(j+1)*4+3]; } + simplified.resize(simplified.size()-4); + npts--; } } } + static bool mergeContours(rcContour& ca, rcContour& cb, int ia, int ib) { const int maxVerts = ca.nverts + cb.nverts + 2; int* verts = (int*)rcAlloc(sizeof(int)*maxVerts*4, RC_ALLOC_PERM); if (!verts) return false; - + int nv = 0; - + // Copy contour A. for (int i = 0; i <= ca.nverts; ++i) { @@ -584,7 +639,7 @@ static bool mergeContours(rcContour& ca, rcContour& cb, int ia, int ib) rcFree(ca.verts); ca.verts = verts; ca.nverts = nv; - + rcFree(cb.verts); cb.verts = 0; cb.nverts = 0; @@ -592,18 +647,179 @@ static bool mergeContours(rcContour& ca, rcContour& cb, int ia, int ib) return true; } +struct rcContourHole +{ + rcContour* contour; + int minx, minz, leftmost; +}; + +struct rcContourRegion +{ + rcContour* outline; + rcContourHole* holes; + int nholes; +}; + +struct rcPotentialDiagonal +{ + int vert; + int dist; +}; + +// Finds the lowest leftmost vertex of a contour. +static void findLeftMostVertex(rcContour* contour, int* minx, int* minz, int* leftmost) +{ + *minx = contour->verts[0]; + *minz = contour->verts[2]; + *leftmost = 0; + for (int i = 1; i < contour->nverts; i++) + { + const int x = contour->verts[i*4+0]; + const int z = contour->verts[i*4+2]; + if (x < *minx || (x == *minx && z < *minz)) + { + *minx = x; + *minz = z; + *leftmost = i; + } + } +} + +static int compareHoles(const void* va, const void* vb) +{ + const rcContourHole* a = (const rcContourHole*)va; + const rcContourHole* b = (const rcContourHole*)vb; + if (a->minx == b->minx) + { + if (a->minz < b->minz) + return -1; + if (a->minz > b->minz) + return 1; + } + else + { + if (a->minx < b->minx) + return -1; + if (a->minx > b->minx) + return 1; + } + return 0; +} + + +static int compareDiagDist(const void* va, const void* vb) +{ + const rcPotentialDiagonal* a = (const rcPotentialDiagonal*)va; + const rcPotentialDiagonal* b = (const rcPotentialDiagonal*)vb; + if (a->dist < b->dist) + return -1; + if (a->dist > b->dist) + return 1; + return 0; +} + + +static void mergeRegionHoles(rcContext* ctx, rcContourRegion& region) +{ + // Sort holes from left to right. + for (int i = 0; i < region.nholes; i++) + findLeftMostVertex(region.holes[i].contour, ®ion.holes[i].minx, ®ion.holes[i].minz, ®ion.holes[i].leftmost); + + qsort(region.holes, region.nholes, sizeof(rcContourHole), compareHoles); + + int maxVerts = region.outline->nverts; + 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)); + if (!diags) + { + ctx->log(RC_LOG_WARNING, "mergeRegionHoles: Failed to allocated diags %d.", maxVerts); + return; + } + + rcContour* outline = region.outline; + + // Merge holes into the outline one by one. + for (int i = 0; i < region.nholes; i++) + { + rcContour* hole = region.holes[i].contour; + + int index = -1; + int bestVertex = region.holes[i].leftmost; + for (int iter = 0; iter < hole->nverts; iter++) + { + // Find potential diagonals. + // The 'best' vertex must be in the cone described by 3 cosequtive vertices of the outline. + // ..o j-1 + // | + // | * best + // | + // j o-----o j+1 + // : + int ndiags = 0; + const int* corner = &hole->verts[bestVertex*4]; + for (int j = 0; j < outline->nverts; j++) + { + if (inCone(j, outline->nverts, outline->verts, corner)) + { + int dx = outline->verts[j*4+0] - corner[0]; + int dz = outline->verts[j*4+2] - corner[2]; + diags[ndiags].vert = j; + diags[ndiags].dist = dx*dx + dz*dz; + ndiags++; + } + } + // Sort potential diagonals by distance, we want to make the connection as short as possible. + qsort(diags, ndiags, sizeof(rcPotentialDiagonal), compareDiagDist); + + // Find a diagonal that is not intersecting the outline not the remaining holes. + index = -1; + for (int j = 0; j < ndiags; j++) + { + const int* pt = &outline->verts[diags[j].vert*4]; + bool intersect = intersectSegCountour(pt, corner, diags[i].vert, outline->nverts, outline->verts); + for (int k = i; k < region.nholes && !intersect; k++) + intersect |= intersectSegCountour(pt, corner, -1, region.holes[k].contour->nverts, region.holes[k].contour->verts); + if (!intersect) + { + index = diags[j].vert; + break; + } + } + // If found non-intersecting diagonal, stop looking. + if (index != -1) + break; + // All the potential diagonals for the current vertex were intersecting, try next vertex. + bestVertex = (bestVertex + 1) % hole->nverts; + } + + if (index == -1) + { + ctx->log(RC_LOG_WARNING, "mergeHoles: Failed to find merge points for %p and %p.", region.outline, hole); + continue; + } + if (!mergeContours(*region.outline, *hole, index, bestVertex)) + { + ctx->log(RC_LOG_WARNING, "mergeHoles: Failed to merge contours %p and %p.", region.outline, hole); + continue; + } + } +} + + /// @par /// /// The raw contours will match the region outlines exactly. The @p maxError and @p maxEdgeLen /// parameters control how closely the simplified contours will match the raw contours. /// -/// Simplified contours are generated such that the vertices for portals between areas match up. +/// Simplified contours are generated such that the vertices for portals between areas match up. /// (They are considered mandatory vertices.) /// /// Setting @p maxEdgeLength to zero will disabled the edge length feature. -/// +/// /// See the #rcConfig documentation for more information on the configuration parameters. -/// +/// /// @see rcAllocContourSet, rcCompactHeightfield, rcContourSet, rcConfig bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, const float maxError, const int maxEdgeLen, @@ -615,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); @@ -633,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); @@ -640,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); @@ -706,17 +923,17 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, verts.resize(0); simplified.resize(0); - + ctx->startTimer(RC_TIMER_BUILD_CONTOURS_TRACE); walkContour(x, y, i, chf, flags, verts); ctx->stopTimer(RC_TIMER_BUILD_CONTOURS_TRACE); - + ctx->startTimer(RC_TIMER_BUILD_CONTOURS_SIMPLIFY); simplifyContour(verts, simplified, maxError, maxEdgeLen, buildFlags); removeDegenerateSegments(simplified); ctx->stopTimer(RC_TIMER_BUILD_CONTOURS_SIMPLIFY); - + // Store region->contour remap info. // Create contour. if (simplified.size()/4 >= 3) @@ -724,7 +941,7 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, if (cset.nconts >= maxContours) { // Allocate more contours. - // This can happen when there are tiny holes in the heightfield. + // This happens when a region has holes. const int oldMax = maxContours; maxContours *= 2; rcContour* newConts = (rcContour*)rcAlloc(sizeof(rcContour)*maxContours, RC_ALLOC_PERM); @@ -737,10 +954,10 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, } rcFree(cset.conts); cset.conts = newConts; - + ctx->log(RC_LOG_WARNING, "rcBuildContours: Expanding max contours from %d to %d.", oldMax, maxContours); } - + rcContour* cont = &cset.conts[cset.nconts++]; cont->nverts = simplified.size()/4; @@ -754,9 +971,9 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, if (borderSize > 0) { // If the heightfield was build with bordersize, remove the offset. - for (int i = 0; i < cont->nverts; ++i) + for (int j = 0; j < cont->nverts; ++j) { - int* v = &cont->verts[i*4]; + int* v = &cont->verts[j*4]; v[0] -= borderSize; v[2] -= borderSize; } @@ -773,25 +990,14 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, if (borderSize > 0) { // If the heightfield was build with bordersize, remove the offset. - for (int i = 0; i < cont->nrverts; ++i) + for (int j = 0; j < cont->nrverts; ++j) { - int* v = &cont->rverts[i*4]; + int* v = &cont->rverts[j*4]; v[0] -= borderSize; v[2] -= borderSize; } } -/* cont->cx = cont->cy = cont->cz = 0; - for (int i = 0; i < cont->nverts; ++i) - { - cont->cx += cont->verts[i*4+0]; - cont->cy += cont->verts[i*4+1]; - cont->cz += cont->verts[i*4+2]; - } - cont->cx /= cont->nverts; - cont->cy /= cont->nverts; - cont->cz /= cont->nverts;*/ - cont->reg = reg; cont->area = area; } @@ -799,55 +1005,101 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, } } - // Check and merge droppings. - // Sometimes the previous algorithms can fail and create several contours - // per area. This pass will try to merge the holes into the main region. - for (int i = 0; i < cset.nconts; ++i) + // Merge holes if needed. + if (cset.nconts > 0) { - rcContour& cont = cset.conts[i]; - // Check if the contour is would backwards. - if (calcAreaOfPolygon2D(cont.verts, cont.nverts) < 0) + // Calculate winding of all polygons. + 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); + return false; + } + int nholes = 0; + for (int i = 0; i < cset.nconts; ++i) + { + rcContour& cont = cset.conts[i]; + // If the contour is wound backwards, it is a hole. + winding[i] = calcAreaOfPolygon2D(cont.verts, cont.nverts) < 0 ? -1 : 1; + if (winding[i] < 0) + nholes++; + } + + if (nholes > 0) { - // Find another contour which has the same region ID. - int mergeIdx = -1; - for (int j = 0; j < cset.nconts; ++j) + // 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)); + if (!regions) + { + ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'regions' (%d).", nregions); + return false; + } + memset(regions, 0, sizeof(rcContourRegion)*nregions); + + rcScopedDelete<rcContourHole> holes((rcContourHole*)rcAlloc(sizeof(rcContourHole)*cset.nconts, RC_ALLOC_TEMP)); + if (!holes) { - if (i == j) continue; - if (cset.conts[j].nverts && cset.conts[j].reg == cont.reg) + ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'holes' (%d).", cset.nconts); + return false; + } + memset(holes, 0, sizeof(rcContourHole)*cset.nconts); + + for (int i = 0; i < cset.nconts; ++i) + { + rcContour& cont = cset.conts[i]; + // Positively would contours are outlines, negative holes. + if (winding[i] > 0) { - // Make sure the polygon is correctly oriented. - if (calcAreaOfPolygon2D(cset.conts[j].verts, cset.conts[j].nverts)) - { - mergeIdx = j; - break; - } + if (regions[cont.reg].outline) + ctx->log(RC_LOG_ERROR, "rcBuildContours: Multiple outlines for region %d.", cont.reg); + regions[cont.reg].outline = &cont; + } + else + { + regions[cont.reg].nholes++; + } + } + int index = 0; + for (int i = 0; i < nregions; i++) + { + if (regions[i].nholes > 0) + { + regions[i].holes = &holes[index]; + index += regions[i].nholes; + regions[i].nholes = 0; } } - if (mergeIdx == -1) + for (int i = 0; i < cset.nconts; ++i) { - ctx->log(RC_LOG_WARNING, "rcBuildContours: Could not find merge target for bad contour %d.", i); + rcContour& cont = cset.conts[i]; + rcContourRegion& reg = regions[cont.reg]; + if (winding[i] < 0) + reg.holes[reg.nholes++].contour = &cont; } - else + + // Finally merge each regions holes into the outline. + for (int i = 0; i < nregions; i++) { - rcContour& mcont = cset.conts[mergeIdx]; - // Merge by closest points. - int ia = 0, ib = 0; - getClosestIndices(mcont.verts, mcont.nverts, cont.verts, cont.nverts, ia, ib); - if (ia == -1 || ib == -1) + rcContourRegion& reg = regions[i]; + if (!reg.nholes) continue; + + if (reg.outline) { - ctx->log(RC_LOG_WARNING, "rcBuildContours: Failed to find merge points for %d and %d.", i, mergeIdx); - continue; + mergeRegionHoles(ctx, reg); } - if (!mergeContours(mcont, cont, ia, ib)) + else { - ctx->log(RC_LOG_WARNING, "rcBuildContours: Failed to merge contours %d and %d.", i, mergeIdx); - continue; + // The region does not have an outline. + // This can happen if the contour becaomes selfoverlapping because of + // too aggressive simplification settings. + ctx->log(RC_LOG_ERROR, "rcBuildContours: Bad outline for region %d, contour simplification is likely too aggressive.", i); } } } + } - ctx->stopTimer(RC_TIMER_BUILD_CONTOURS); - return true; } diff --git a/extern/recastnavigation/Recast/Source/RecastFilter.cpp b/extern/recastnavigation/Recast/Source/RecastFilter.cpp index 9df71ea3fbf..9d3e63c4820 100644 --- a/extern/recastnavigation/Recast/Source/RecastFilter.cpp +++ b/extern/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; @@ -128,7 +126,7 @@ void rcFilterLedgeSpans(rcContext* ctx, const int walkableHeight, const int walk rcSpan* ns = solid.spans[dx + dy*w]; int nbot = -walkableClimb; int ntop = ns ? (int)ns->smin : MAX_HEIGHT; - // Skip neighbor if the gap between the spans is too small. + // Skip neightbour if the gap between the spans is too small. if (rcMin(top,ntop) - rcMax(bot,nbot) > walkableHeight) minh = rcMin(minh, nbot - bot); @@ -137,7 +135,7 @@ void rcFilterLedgeSpans(rcContext* ctx, const int walkableHeight, const int walk { nbot = (int)ns->smax; ntop = ns->next ? (int)ns->next->smin : MAX_HEIGHT; - // Skip neighbor if the gap between the spans is too small. + // Skip neightbour if the gap between the spans is too small. if (rcMin(top,ntop) - rcMax(bot,nbot) > walkableHeight) { minh = rcMin(minh, nbot - bot); @@ -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/extern/recastnavigation/Recast/Source/RecastLayers.cpp b/extern/recastnavigation/Recast/Source/RecastLayers.cpp index 2d9658b2bed..22a357effa1 100644 --- a/extern/recastnavigation/Recast/Source/RecastLayers.cpp +++ b/extern/recastnavigation/Recast/Source/RecastLayers.cpp @@ -38,7 +38,7 @@ struct rcLayerRegion unsigned char layerId; // Layer ID unsigned char nlayers; // Layer count unsigned char nneis; // Neighbour count - unsigned char base; // Flag indicating if the region is hte base of merged regions. + unsigned char base; // Flag indicating if the region is the base of merged regions. }; @@ -87,12 +87,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 +101,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 +212,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); @@ -258,7 +258,7 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf, const int ay = y + rcGetDirOffsetY(dir); const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir); const unsigned char rai = srcReg[ai]; - if (rai != 0xff && rai != ri) + if (rai != 0xff && rai != ri && regs[ri].nneis < RC_MAX_NEIS) addUnique(regs[ri].neis, regs[ri].nneis, rai); } } @@ -293,7 +293,7 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf, for (int i = 0; i < nregs; ++i) { rcLayerRegion& root = regs[i]; - // Skip alreadu visited. + // Skip already visited. if (root.layerId != 0xff) continue; @@ -325,7 +325,7 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf, continue; // Skip if the height range would become too large. const int ymin = rcMin(root.ymin, regn.ymin); - const int ymax = rcMin(root.ymax, regn.ymax); + const int ymax = rcMax(root.ymax, regn.ymax); if ((ymax - ymin) >= 255) continue; @@ -373,11 +373,11 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf, continue; // Skip if the height range would become too large. const int ymin = rcMin(ri.ymin, rj.ymin); - const int ymax = rcMin(ri.ymax, rj.ymax); + const int ymax = rcMax(ri.ymax, rj.ymax); if ((ymax - ymin) >= 255) continue; - // Make sure that there is no overlap when mergin 'ri' and 'rj'. + // Make sure that there is no overlap when merging 'ri' and 'rj'. bool overlap = false; // Iterate over all regions which have the same layerId as 'rj' for (int k = 0; k < nregs; ++k) @@ -417,7 +417,7 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf, // Add overlaid layers from 'rj' to 'ri'. for (int k = 0; k < rj.nlayers; ++k) addUnique(ri.layers, ri.nlayers, rj.layers[k]); - // Update heigh bounds. + // Update height bounds. ri.ymin = rcMin(ri.ymin, rj.ymin); ri.ymax = rcMax(ri.ymax, rj.ymax); } @@ -446,10 +446,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); @@ -481,10 +478,8 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf, for (int i = 0; i < lset.nlayers; ++i) { unsigned char curId = (unsigned char)i; - - // Allocate memory for the current layer. + rcHeightfieldLayer* layer = &lset.layers[i]; - memset(layer, 0, sizeof(rcHeightfieldLayer)); const int gridSize = sizeof(unsigned char)*lw*lh; @@ -528,7 +523,7 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf, layer->cs = chf.cs; layer->ch = chf.ch; - // Adjust the bbox to fit the heighfield. + // Adjust the bbox to fit the heightfield. rcVcopy(layer->bmin, bmin); rcVcopy(layer->bmax, bmax); layer->bmin[1] = bmin[1] + hmin*chf.ch; @@ -542,7 +537,7 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf, layer->miny = layer->height; layer->maxy = 0; - // Copy height and area from compact heighfield. + // Copy height and area from compact heightfield. for (int y = 0; y < lh; ++y) { for (int x = 0; x < lw; ++x) @@ -550,14 +545,14 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf, const int cx = borderSize+x; const int cy = borderSize+y; const rcCompactCell& c = chf.cells[cx+cy*w]; - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) + for (int j = (int)c.index, nj = (int)(c.index+c.count); j < nj; ++j) { - const rcCompactSpan& s = chf.spans[i]; + const rcCompactSpan& s = chf.spans[j]; // Skip unassigned regions. - if (srcReg[i] == 0xff) + if (srcReg[j] == 0xff) continue; // Skip of does nto belong to current layer. - unsigned char lid = regs[srcReg[i]].layerId; + unsigned char lid = regs[srcReg[j]].layerId; if (lid != curId) continue; @@ -570,7 +565,7 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf, // Store height and area type. const int idx = x+y*lw; layer->heights[idx] = (unsigned char)(s.y - hmin); - layer->areas[idx] = chf.areas[i]; + layer->areas[idx] = chf.areas[j]; // Check connection. unsigned char portal = 0; @@ -614,7 +609,5 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf, layer->miny = layer->maxy = 0; } - ctx->stopTimer(RC_TIMER_BUILD_LAYERS); - return true; } diff --git a/extern/recastnavigation/Recast/Source/RecastLog.cpp b/extern/recastnavigation/Recast/Source/RecastLog.cpp deleted file mode 100644 index 27868042a1c..00000000000 --- a/extern/recastnavigation/Recast/Source/RecastLog.cpp +++ /dev/null @@ -1,77 +0,0 @@ -// -// Copyright (c) 2009 Mikko Mononen memon@inside.org -// -// This software is provided 'as-is', without any express or implied -// warranty. In no event will the authors be held liable for any damages -// arising from the use of this software. -// Permission is granted to anyone to use this software for any purpose, -// including commercial applications, and to alter it and redistribute it -// freely, subject to the following restrictions: -// 1. The origin of this software must not be misrepresented; you must not -// claim that you wrote the original software. If you use this software -// in a product, an acknowledgment in the product documentation would be -// appreciated but is not required. -// 2. Altered source versions must be plainly marked as such, and must not be -// misrepresented as being the original software. -// 3. This notice may not be removed or altered from any source distribution. -// - -#include "RecastLog.h" -#include <stdio.h> -#include <stdarg.h> - -static rcLog* g_log = 0; -static rcBuildTimes* g_btimes = 0; - -rcLog::rcLog() : - m_messageCount(0), - m_textPoolSize(0) -{ -} - -rcLog::~rcLog() -{ - if (g_log == this) - g_log = 0; -} - -void rcLog::log(rcLogCategory category, const char* format, ...) -{ - if (m_messageCount >= MAX_MESSAGES) - return; - char* dst = &m_textPool[m_textPoolSize]; - int n = TEXT_POOL_SIZE - m_textPoolSize; - if (n < 2) - return; - // Store category - *dst = (char)category; - n--; - // Store message - va_list ap; - va_start(ap, format); - int ret = vsnprintf(dst+1, n-1, format, ap); - va_end(ap); - if (ret > 0) - m_textPoolSize += ret+2; - m_messages[m_messageCount++] = dst; -} - -void rcSetLog(rcLog* log) -{ - g_log = log; -} - -rcLog* rcGetLog() -{ - return g_log; -} - -void rcSetBuildTimes(rcBuildTimes* btimes) -{ - g_btimes = btimes; -} - -rcBuildTimes* rcGetBuildTimes() -{ - return g_btimes; -} diff --git a/extern/recastnavigation/Recast/Source/RecastMesh.cpp b/extern/recastnavigation/Recast/Source/RecastMesh.cpp index e6d89eed3a8..e762318431f 100644 --- a/extern/recastnavigation/Recast/Source/RecastMesh.cpp +++ b/extern/recastnavigation/Recast/Source/RecastMesh.cpp @@ -160,6 +160,7 @@ static unsigned short addVertex(unsigned short x, unsigned short y, unsigned sho return (unsigned short)i; } +// Last time I checked the if version got compiled using cmov, which was a lot faster than module (with idiv). 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; } @@ -288,6 +289,53 @@ static bool diagonal(int i, int j, int n, const int* verts, int* indices) return inCone(i, j, n, verts, indices) && diagonalie(i, j, n, verts, indices); } + +static bool diagonalieLoose(int i, int j, int n, const int* verts, int* indices) +{ + const int* d0 = &verts[(indices[i] & 0x0fffffff) * 4]; + const int* d1 = &verts[(indices[j] & 0x0fffffff) * 4]; + + // For each edge (k,k+1) of P + for (int k = 0; k < n; k++) + { + int k1 = next(k, n); + // Skip edges incident to i or j + if (!((k == i) || (k1 == i) || (k == j) || (k1 == j))) + { + const int* p0 = &verts[(indices[k] & 0x0fffffff) * 4]; + const int* p1 = &verts[(indices[k1] & 0x0fffffff) * 4]; + + if (vequal(d0, p0) || vequal(d1, p0) || vequal(d0, p1) || vequal(d1, p1)) + continue; + + if (intersectProp(d0, d1, p0, p1)) + return false; + } + } + return true; +} + +static bool inConeLoose(int i, int j, int n, const int* verts, int* indices) +{ + const int* pi = &verts[(indices[i] & 0x0fffffff) * 4]; + const int* pj = &verts[(indices[j] & 0x0fffffff) * 4]; + const int* pi1 = &verts[(indices[next(i, n)] & 0x0fffffff) * 4]; + const int* pin1 = &verts[(indices[prev(i, n)] & 0x0fffffff) * 4]; + + // If P[i] is a convex vertex [ i+1 left or on (i-1,i) ]. + if (leftOn(pin1, pi, pi1)) + return leftOn(pi, pj, pin1) && leftOn(pj, pi, pi1); + // Assume (i-1,i,i+1) not collinear. + // else P[i] is reflex. + return !(leftOn(pi, pj, pi1) && leftOn(pj, pi, pin1)); +} + +static bool diagonalLoose(int i, int j, int n, const int* verts, int* indices) +{ + return inConeLoose(i, j, n, verts, indices) && diagonalieLoose(i, j, n, verts, indices); +} + + static int triangulate(int n, const int* verts, int* indices, int* tris) { int ntris = 0; @@ -305,7 +353,7 @@ static int triangulate(int n, const int* verts, int* indices, int* tris) while (n > 3) { int minLen = -1; - int i_min = -1; + int mini = -1; for (int i = 0; i < n; i++) { int i1 = next(i, n); @@ -321,24 +369,51 @@ static int triangulate(int n, const int* verts, int* indices, int* tris) if (minLen < 0 || len < minLen) { minLen = len; - i_min = i; + mini = i; } } } - if (i_min == -1) + if (mini == -1) { - // Should not happen. -/* printf("mini == -1 ntris=%d n=%d\n", ntris, n); + // We might get here because the contour has overlapping segments, like this: + // + // A o-o=====o---o B + // / |C D| \ + // o o o o + // : : : : + // We'll try to recover by loosing up the inCone test a bit so that a diagonal + // like A-B or C-D can be found and we can continue. + minLen = -1; + mini = -1; for (int i = 0; i < n; i++) { - printf("%d ", indices[i] & 0x0fffffff); + int i1 = next(i, n); + int i2 = next(i1, n); + if (diagonalLoose(i, i2, n, verts, indices)) + { + const int* p0 = &verts[(indices[i] & 0x0fffffff) * 4]; + const int* p2 = &verts[(indices[next(i2, n)] & 0x0fffffff) * 4]; + int dx = p2[0] - p0[0]; + int dy = p2[2] - p0[2]; + int len = dx*dx + dy*dy; + + if (minLen < 0 || len < minLen) + { + minLen = len; + mini = i; + } + } + } + if (mini == -1) + { + // The contour is messed up. This sometimes happens + // if the contour simplification is too aggressive. + return -ntris; } - printf("\n");*/ - return -ntris; } - int i = i_min; + int i = mini; int i1 = next(i, n); int i2 = next(i1, n); @@ -453,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); @@ -526,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); @@ -550,9 +625,9 @@ static bool canRemoveVertex(rcContext* ctx, rcPolyMesh& mesh, const unsigned sho // Check if the edge exists bool exists = false; - for (int k = 0; k < nedges; ++k) + for (int m = 0; m < nedges; ++m) { - int* e = &edges[k*3]; + int* e = &edges[m*3]; if (e[1] == b) { // Exists, increment vertex share count. @@ -606,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); @@ -614,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); @@ -630,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); @@ -661,7 +736,8 @@ static bool removeVertex(rcContext* ctx, rcPolyMesh& mesh, const unsigned short } // Remove the polygon. unsigned short* p2 = &mesh.polys[(mesh.npolys-1)*nvp*2]; - memcpy(p,p2,sizeof(unsigned short)*nvp); + if (p != p2) + memcpy(p,p2,sizeof(unsigned short)*nvp); memset(p+nvp,0xff,sizeof(unsigned short)*nvp); mesh.regs[i] = mesh.regs[mesh.npolys-1]; mesh.areas[i] = mesh.areas[mesh.npolys-1]; @@ -671,7 +747,7 @@ static bool removeVertex(rcContext* ctx, rcPolyMesh& mesh, const unsigned short } // Remove vertex. - for (int i = (int)rem; i < mesh.nverts; ++i) + for (int i = (int)rem; i < mesh.nverts - 1; ++i) { mesh.verts[i*3+0] = mesh.verts[(i+1)*3+0]; mesh.verts[i*3+1] = mesh.verts[(i+1)*3+1]; @@ -746,22 +822,22 @@ 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); - if (!tverts) + 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); return false; @@ -787,20 +863,20 @@ 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); - if (!pregs) + 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); return false; @@ -819,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++; } @@ -860,8 +943,13 @@ 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); - memcpy(pb, &polys[(npolys-1)*nvp], sizeof(unsigned short)*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); pregs[bestPb] = pregs[npolys-1]; pareas[bestPb] = pareas[npolys-1]; npolys--; @@ -905,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; @@ -931,10 +1020,10 @@ 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 'mesh.verts' (%d).", maxVertices); + ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'vflags' (%d).", maxVertices); return false; } memset(vflags, 0, maxVertices); @@ -974,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); @@ -982,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); @@ -991,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); @@ -1053,7 +1142,7 @@ bool rcBuildPolyMesh(rcContext* ctx, rcContourSet& cset, const int nvp, rcPolyMe vflags[indices[j]] = 1; } } - + // Build initial polygons. int npolys = 0; memset(polys, 0xff, maxVertsPerCont*nvp*sizeof(unsigned short)); @@ -1104,8 +1193,10 @@ 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); - memcpy(pb, &polys[(npolys-1)*nvp], sizeof(unsigned short)*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); npolys--; } else @@ -1150,6 +1241,7 @@ bool rcBuildPolyMesh(rcContext* ctx, rcContourSet& cset, const int nvp, rcPolyMe } // Remove vertex // Note: mesh.nverts is already decremented inside removeVertex()! + // Fixup vertex flags for (int j = i; j < mesh.nverts; ++j) vflags[j] = vflags[j+1]; --i; @@ -1212,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; } @@ -1225,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; @@ -1286,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); @@ -1294,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); @@ -1303,13 +1393,13 @@ 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); return false; } - memset(nextVert, 0, sizeof(int)*maxVerts); + memset(vremap, 0, sizeof(unsigned short)*maxVertsPerMesh); for (int i = 0; i < nmeshes; ++i) { @@ -1318,6 +1408,12 @@ bool rcMergePolyMeshes(rcContext* ctx, rcPolyMesh** meshes, const int nmeshes, r const unsigned short ox = (unsigned short)floorf((pmesh->bmin[0]-mesh.bmin[0])/mesh.cs+0.5f); const unsigned short oz = (unsigned short)floorf((pmesh->bmin[2]-mesh.bmin[2])/mesh.cs+0.5f); + bool isMinX = (ox == 0); + bool isMinZ = (oz == 0); + bool isMaxX = ((unsigned short)floorf((mesh.bmax[0] - pmesh->bmax[0]) / mesh.cs + 0.5f)) == 0; + bool isMaxZ = ((unsigned short)floorf((mesh.bmax[2] - pmesh->bmax[2]) / mesh.cs + 0.5f)) == 0; + bool isOnBorder = (isMinX || isMinZ || isMaxX || isMaxZ); + for (int j = 0; j < pmesh->nverts; ++j) { unsigned short* v = &pmesh->verts[j*3]; @@ -1338,6 +1434,36 @@ bool rcMergePolyMeshes(rcContext* ctx, rcPolyMesh** meshes, const int nmeshes, r if (src[k] == RC_MESH_NULL_IDX) break; tgt[k] = vremap[src[k]]; } + + if (isOnBorder) + { + for (int k = mesh.nvp; k < mesh.nvp * 2; ++k) + { + if (src[k] & 0x8000 && src[k] != 0xffff) + { + unsigned short dir = src[k] & 0xf; + switch (dir) + { + case 0: // Portal x- + if (isMinX) + tgt[k] = src[k]; + break; + case 1: // Portal z+ + if (isMaxZ) + tgt[k] = src[k]; + break; + case 2: // Portal x+ + if (isMaxX) + tgt[k] = src[k]; + break; + case 3: // Portal z- + if (isMinZ) + tgt[k] = src[k]; + break; + } + } + } + } } } @@ -1357,7 +1483,70 @@ 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; +} + +bool rcCopyPolyMesh(rcContext* ctx, const rcPolyMesh& src, rcPolyMesh& dst) +{ + rcAssert(ctx); + + // Destination must be empty. + rcAssert(dst.verts == 0); + rcAssert(dst.polys == 0); + rcAssert(dst.regs == 0); + rcAssert(dst.areas == 0); + rcAssert(dst.flags == 0); + + dst.nverts = src.nverts; + dst.npolys = src.npolys; + dst.maxpolys = src.npolys; + dst.nvp = src.nvp; + rcVcopy(dst.bmin, src.bmin); + rcVcopy(dst.bmax, src.bmax); + 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) + { + ctx->log(RC_LOG_ERROR, "rcCopyPolyMesh: Out of memory 'dst.verts' (%d).", src.nverts*3); + return false; + } + memcpy(dst.verts, src.verts, sizeof(unsigned short)*src.nverts*3); + + dst.polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*src.npolys*2*src.nvp, RC_ALLOC_PERM); + if (!dst.polys) + { + ctx->log(RC_LOG_ERROR, "rcCopyPolyMesh: Out of memory 'dst.polys' (%d).", src.npolys*2*src.nvp); + return false; + } + memcpy(dst.polys, src.polys, sizeof(unsigned short)*src.npolys*2*src.nvp); + + dst.regs = (unsigned short*)rcAlloc(sizeof(unsigned short)*src.npolys, RC_ALLOC_PERM); + if (!dst.regs) + { + ctx->log(RC_LOG_ERROR, "rcCopyPolyMesh: Out of memory 'dst.regs' (%d).", src.npolys); + return false; + } + memcpy(dst.regs, src.regs, sizeof(unsigned short)*src.npolys); + + dst.areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*src.npolys, RC_ALLOC_PERM); + if (!dst.areas) + { + ctx->log(RC_LOG_ERROR, "rcCopyPolyMesh: Out of memory 'dst.areas' (%d).", src.npolys); + return false; + } + memcpy(dst.areas, src.areas, sizeof(unsigned char)*src.npolys); + + dst.flags = (unsigned short*)rcAlloc(sizeof(unsigned short)*src.npolys, RC_ALLOC_PERM); + if (!dst.flags) + { + ctx->log(RC_LOG_ERROR, "rcCopyPolyMesh: Out of memory 'dst.flags' (%d).", src.npolys); + return false; + } + memcpy(dst.flags, src.flags, sizeof(unsigned short)*src.npolys); return true; } diff --git a/extern/recastnavigation/Recast/Source/RecastMeshDetail.cpp b/extern/recastnavigation/Recast/Source/RecastMeshDetail.cpp index b52da597675..f1270cf2027 100644 --- a/extern/recastnavigation/Recast/Source/RecastMeshDetail.cpp +++ b/extern/recastnavigation/Recast/Source/RecastMeshDetail.cpp @@ -37,11 +37,12 @@ struct rcHeightPatch int xmin, ymin, width, height; }; + inline float vdot2(const float* a, const float* b) { return a[0]*b[0] + a[2]*b[2]; } - + inline float vdistSq2(const float* p, const float* q) { const float dx = q[0] - p[0]; @@ -55,7 +56,7 @@ inline float vdist2(const float* p, const float* q) } inline float vcross2(const float* p1, const float* p2, const float* p3) -{ +{ const float u1 = p2[0] - p1[0]; const float v1 = p2[2] - p1[2]; const float u2 = p3[0] - p1[0]; @@ -67,21 +68,27 @@ static bool circumCircle(const float* p1, const float* p2, const float* p3, float* c, float& r) { static const float EPS = 1e-6f; + // Calculate the circle relative to p1, to avoid some precision issues. + const float v1[3] = {0,0,0}; + float v2[3], v3[3]; + rcVsub(v2, p2,p1); + rcVsub(v3, p3,p1); - const float cp = vcross2(p1, p2, p3); + const float cp = vcross2(v1, v2, v3); if (fabsf(cp) > EPS) { - const float p1Sq = vdot2(p1,p1); - const float p2Sq = vdot2(p2,p2); - const float p3Sq = vdot2(p3,p3); - c[0] = (p1Sq*(p2[2]-p3[2]) + p2Sq*(p3[2]-p1[2]) + p3Sq*(p1[2]-p2[2])) / (2*cp); - c[2] = (p1Sq*(p3[0]-p2[0]) + p2Sq*(p1[0]-p3[0]) + p3Sq*(p2[0]-p1[0])) / (2*cp); - r = vdist2(c, p1); + const float v1Sq = vdot2(v1,v1); + const float v2Sq = vdot2(v2,v2); + const float v3Sq = vdot2(v3,v3); + c[0] = (v1Sq*(v2[2]-v3[2]) + v2Sq*(v3[2]-v1[2]) + v3Sq*(v1[2]-v2[2])) / (2*cp); + c[1] = 0; + c[2] = (v1Sq*(v3[0]-v2[0]) + v2Sq*(v1[0]-v3[0]) + v3Sq*(v2[0]-v1[0])) / (2*cp); + r = vdist2(c, v1); + rcVadd(c, c, p1); return true; } - - c[0] = p1[0]; - c[2] = p1[2]; + + rcVcopy(c, p1); r = 0; return false; } @@ -92,7 +99,7 @@ static float distPtTri(const float* p, const float* a, const float* b, const flo rcVsub(v0, c,a); rcVsub(v1, b,a); rcVsub(v2, p,a); - + const float dot00 = vdot2(v0, v0); const float dot01 = vdot2(v0, v1); const float dot02 = vdot2(v0, v2); @@ -177,7 +184,7 @@ static float distToTriMesh(const float* p, const float* verts, const int /*nvert static float distToPoly(int nvert, const float* verts, const float* p) { - + float dmin = FLT_MAX; int i, j, c = 0; for (i = 0, j = nvert-1; i < nvert; j = i++) @@ -195,42 +202,79 @@ 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); - ix = rcClamp(ix-hp.xmin, 0, hp.width); - iz = rcClamp(iz-hp.ymin, 0, hp.height); + ix = rcClamp(ix-hp.xmin, 0, hp.width - 1); + iz = rcClamp(iz-hp.ymin, 0, hp.height - 1); unsigned short h = hp.data[ix+iz*hp.width]; 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 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; + } + } + } - const float d = fabsf(nh*ch - fy); - if (d < dmin) + // 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) { - h = nh; - dmin = d; + if (h != RC_UNSET_HEIGHT) + break; + + nextRingIterStart += nextRingIters; + nextRingIters += 8; } - -/* const float dx = (nx+0.5f)*cs - fx; - const float dz = (nz+0.5f)*cs - fz; - const float d = dx*dx+dz*dz; - if (d < dmin) + + 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; @@ -239,8 +283,8 @@ static unsigned short getHeight(const float fx, const float fy, const float fz, enum EdgeValues { - UNDEF = -1, - HULL = -2, + EV_UNDEF = -1, + EV_HULL = -2, }; static int findEdge(const int* edges, int nedges, int s, int t) @@ -251,7 +295,7 @@ static int findEdge(const int* edges, int nedges, int s, int t) if ((e[0] == s && e[1] == t) || (e[0] == t && e[1] == s)) return i; } - return UNDEF; + return EV_UNDEF; } static int addEdge(rcContext* ctx, int* edges, int& nedges, const int maxEdges, int s, int t, int l, int r) @@ -259,33 +303,33 @@ static int addEdge(rcContext* ctx, int* edges, int& nedges, const int maxEdges, if (nedges >= maxEdges) { ctx->log(RC_LOG_ERROR, "addEdge: Too many edges (%d/%d).", nedges, maxEdges); - return UNDEF; + return EV_UNDEF; } - // Add edge if not already in the triangulation. + // Add edge if not already in the triangulation. int e = findEdge(edges, nedges, s, t); - if (e == UNDEF) + if (e == EV_UNDEF) { - int* e = &edges[nedges*4]; - e[0] = s; - e[1] = t; - e[2] = l; - e[3] = r; + int* edge = &edges[nedges*4]; + edge[0] = s; + edge[1] = t; + edge[2] = l; + edge[3] = r; return nedges++; } else { - return UNDEF; + return EV_UNDEF; } } static void updateLeftFace(int* e, int s, int t, int f) { - if (e[0] == s && e[1] == t && e[2] == UNDEF) + if (e[0] == s && e[1] == t && e[2] == EV_UNDEF) e[2] = f; - else if (e[1] == s && e[0] == t && e[3] == UNDEF) + else if (e[1] == s && e[0] == t && e[3] == EV_UNDEF) e[3] = f; -} +} static int overlapSegSeg2d(const float* a, const float* b, const float* c, const float* d) { @@ -297,7 +341,7 @@ static int overlapSegSeg2d(const float* a, const float* b, const float* c, const float a4 = a3 + a2 - a1; if (a3 * a4 < 0.0f) return 1; - } + } return 0; } @@ -319,28 +363,28 @@ static bool overlapEdges(const float* pts, const int* edges, int nedges, int s1, static void completeFacet(rcContext* ctx, const float* pts, int npts, int* edges, int& nedges, const int maxEdges, int& nfaces, int e) { static const float EPS = 1e-5f; - + int* edge = &edges[e*4]; // Cache s and t. int s,t; - if (edge[2] == UNDEF) + if (edge[2] == EV_UNDEF) { s = edge[0]; t = edge[1]; } - else if (edge[3] == UNDEF) + else if (edge[3] == EV_UNDEF) { s = edge[1]; t = edge[0]; } else { - // Edge already completed. + // Edge already completed. return; } - // Find best point on left of edge. + // Find best point on left of edge. int pt = npts; float c[3] = {0,0,0}; float r = -1; @@ -384,23 +428,23 @@ static void completeFacet(rcContext* ctx, const float* pts, int npts, int* edges } } - // Add new triangle or update edge info if s-t is on hull. + // Add new triangle or update edge info if s-t is on hull. if (pt < npts) { - // Update face information of edge being completed. + // Update face information of edge being completed. updateLeftFace(&edges[e*4], s, t, nfaces); - // Add new edge or update face info of old edge. + // Add new edge or update face info of old edge. e = findEdge(edges, nedges, pt, s); - if (e == UNDEF) - addEdge(ctx, edges, nedges, maxEdges, pt, s, nfaces, UNDEF); + if (e == EV_UNDEF) + addEdge(ctx, edges, nedges, maxEdges, pt, s, nfaces, EV_UNDEF); else updateLeftFace(&edges[e*4], pt, s, nfaces); - // Add new edge or update face info of old edge. + // Add new edge or update face info of old edge. e = findEdge(edges, nedges, t, pt); - if (e == UNDEF) - addEdge(ctx, edges, nedges, maxEdges, t, pt, nfaces, UNDEF); + if (e == EV_UNDEF) + addEdge(ctx, edges, nedges, maxEdges, t, pt, nfaces, EV_UNDEF); else updateLeftFace(&edges[e*4], t, pt, nfaces); @@ -408,7 +452,7 @@ static void completeFacet(rcContext* ctx, const float* pts, int npts, int* edges } else { - updateLeftFace(&edges[e*4], s, t, HULL); + updateLeftFace(&edges[e*4], s, t, EV_HULL); } } @@ -422,18 +466,18 @@ static void delaunayHull(rcContext* ctx, const int npts, const float* pts, edges.resize(maxEdges*4); for (int i = 0, j = nhull-1; i < nhull; j=i++) - addEdge(ctx, &edges[0], nedges, maxEdges, hull[j],hull[i], HULL, UNDEF); + addEdge(ctx, &edges[0], nedges, maxEdges, hull[j],hull[i], EV_HULL, EV_UNDEF); int currentEdge = 0; while (currentEdge < nedges) { - if (edges[currentEdge*4+2] == UNDEF) + if (edges[currentEdge*4+2] == EV_UNDEF) completeFacet(ctx, pts, npts, &edges[0], nedges, maxEdges, nfaces, currentEdge); - if (edges[currentEdge*4+3] == UNDEF) + if (edges[currentEdge*4+3] == EV_UNDEF) completeFacet(ctx, pts, npts, &edges[0], nedges, maxEdges, nfaces, currentEdge); currentEdge++; } - + // Create tris tris.resize(nfaces*4); for (int i = 0; i < nfaces*4; ++i) @@ -488,6 +532,97 @@ static void delaunayHull(rcContext* ctx, const int npts, const float* pts, } } +// Calculate minimum extend of the polygon. +static float polyMinExtent(const float* verts, const int nverts) +{ + float minDist = FLT_MAX; + for (int i = 0; i < nverts; i++) + { + const int ni = (i+1) % nverts; + const float* p1 = &verts[i*3]; + const float* p2 = &verts[ni*3]; + float maxEdgeDist = 0; + for (int j = 0; j < nverts; j++) + { + if (j == i || j == ni) continue; + float d = distancePtSeg2d(&verts[j*3], p1,p2); + maxEdgeDist = rcMax(maxEdgeDist, d); + } + minDist = rcMin(minDist, maxEdgeDist); + } + return rcSqrt(minDist); +} + +// Last time I checked the if version got compiled using cmov, which was a lot faster than module (with idiv). +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) +{ + 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; + for (int i = 0; i < nhull; i++) + { + int pi = prev(i, nhull); + int ni = next(i, nhull); + const float* pv = &verts[hull[pi]*3]; + const float* cv = &verts[hull[i]*3]; + const float* nv = &verts[hull[ni]*3]; + const float d = vdist2(pv,cv) + vdist2(cv,nv) + vdist2(nv,pv); + if (d < dmin) + { + start = i; + left = ni; + right = pi; + dmin = d; + } + } + + // Add first triangle + tris.push(hull[start]); + tris.push(hull[left]); + tris.push(hull[right]); + tris.push(0); + + // Triangulate the polygon by moving left or right, + // depending on which triangle has shorter perimeter. + // This heuristic was chose emprically, since it seems + // handle tesselated straight edges well. + while (next(left, nhull) != right) + { + // Check to see if se should advance left or right. + int nleft = next(left, nhull); + int nright = prev(right, nhull); + + const float* cvleft = &verts[hull[left]*3]; + const float* nvleft = &verts[hull[nleft]*3]; + const float* cvright = &verts[hull[right]*3]; + const float* nvright = &verts[hull[nright]*3]; + const float dleft = vdist2(cvleft, nvleft) + vdist2(nvleft, cvright); + const float dright = vdist2(cvright, nvright) + vdist2(cvleft, nvright); + + if (dleft < dright) + { + tris.push(hull[left]); + tris.push(hull[nleft]); + tris.push(hull[right]); + tris.push(0); + left = nleft; + } + else + { + tris.push(hull[left]); + tris.push(hull[nright]); + tris.push(hull[right]); + tris.push(0); + right = nright; + } + } +} + inline float getJitterX(const int i) { @@ -501,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). @@ -511,16 +646,22 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin, float edge[(MAX_VERTS_PER_EDGE+1)*3]; int hull[MAX_VERTS]; int nhull = 0; - + nverts = 0; - + for (int i = 0; i < nin; ++i) rcVcopy(&verts[i*3], &in[i*3]); nverts = nin; + edges.resize(0); + tris.resize(0); + const float cs = chf.cs; const float ics = 1.0f/cs; + // Calculate minimum extents of the polygon based on input data. + float minExtent = polyMinExtent(verts, nverts); + // Tessellate outlines. // This is done in separate pass in order to ensure // seamless height values across the ply boundaries. @@ -566,7 +707,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}; @@ -579,23 +720,23 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin, const float* vb = &edge[b*3]; // Find maximum deviation along the segment. float maxd = 0; - int i_max = -1; + int maxi = -1; for (int m = a+1; m < b; ++m) { - float d = distancePtSeg(&edge[m*3],va,vb); - if (d > maxd) + float dev = distancePtSeg(&edge[m*3],va,vb); + if (dev > maxd) { - maxd = d; - i_max = m; + maxd = dev; + maxi = m; } } // If the max deviation is larger than accepted error, // add new point, else continue to next segment. - if (i_max != -1 && maxd > rcSqr(sampleMaxError)) + if (maxi != -1 && maxd > rcSqr(sampleMaxError)) { for (int m = nidx; m > k; --m) idx[m] = idx[m-1]; - idx[k+1] = i_max; + idx[k+1] = maxi; nidx++; } else @@ -627,27 +768,26 @@ 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); + return true; + } + // Tessellate the base mesh. - edges.resize(0); - tris.resize(0); - - delaunayHull(ctx, nverts, verts, nhull, hull, tris, edges); + // We're using the triangulateHull instead of delaunayHull as it tends to + // create a bit better triangulation for long thing triangles when there + // are no internal points. + triangulateHull(nverts, verts, nhull, hull, tris); if (tris.size() == 0) { // Could not triangulate the poly, make sure there is some valid data there. - ctx->log(RC_LOG_WARNING, "buildPolyDetail: Could not triangulate polygon, adding default data."); - for (int i = 2; i < nverts; ++i) - { - tris.push(0); - tris.push(i-1); - tris.push(i); - tris.push(0); - } + ctx->log(RC_LOG_WARNING, "buildPolyDetail: Could not triangulate polygon (%d verts).", nverts); return true; } - + if (sampleDist > 0) { // Create sample locations in a grid. @@ -675,12 +815,12 @@ 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 } } - + // Add the samples starting from the one that has the most // error. The procedure stops when all samples are added // or when the max error is within treshold. @@ -689,7 +829,7 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin, { if (nverts >= MAX_VERTS) break; - + // Find sample with most error. float bestpt[3] = {0,0,0}; float bestd = 0; @@ -727,45 +867,38 @@ static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin, edges.resize(0); tris.resize(0); delaunayHull(ctx, nverts, verts, nhull, hull, tris, edges); - } + } } - + const int ntris = tris.size()/4; if (ntris > MAX_TRIS) { tris.resize(MAX_TRIS*4); ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Shrinking triangle count from %d to max %d.", ntris, MAX_TRIS); } - + return true; } -static void getHeightData(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]; @@ -775,118 +908,210 @@ static void getHeightData(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; - - 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; - } + pcy /= npoly; - 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); + const rcCompactSpan& cs = chf.spans[ci]; + hp.data[cx-hp.xmin+(cy-hp.ymin)*hp.width] = cs.y; +} + - // Mark start locations. - for (int i = 0; i < stack.size(); i += 3) +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(rcContext* ctx, const rcCompactHeightfield& chf, + const unsigned short* poly, const int npoly, + const unsigned short* verts, const int bs, + 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. + + queue.resize(0); + // Set all heights to RC_UNSET_HEIGHT. + memset(hp.data, 0xff, sizeof(unsigned short)*hp.width*hp.height); + + bool empty = true; + + // 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 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; + // 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 y = hp.ymin + hy + bs; + for (int hx = 0; hx < hp.width; hx++) + { + 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) + { + const rcCompactSpan& s = chf.spans[i]; + if (s.reg == region) + { + // 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) + { + if (rcGetCon(s, dir) != RC_NOT_CONNECTED) + { + 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 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) + 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]; for (int dir = 0; dir < 4; ++dir) { @@ -894,26 +1119,23 @@ static void getHeightData(const rcCompactHeightfield& chf, const int ax = cx + rcGetDirOffsetX(dir); const int ay = cy + rcGetDirOffsetY(dir); + const int hx = ax - hp.xmin - bs; + const int hy = ay - hp.ymin - bs; - if (ax < hp.xmin || ax >= (hp.xmin+hp.width) || - ay < hp.ymin || ay >= (hp.ymin+hp.height)) + if ((unsigned int)hx >= (unsigned int)hp.width || (unsigned int)hy >= (unsigned int)hp.height) continue; - if (hp.data[ax-hp.xmin+(ay-hp.ymin)*hp.width] != RC_UNSET_HEIGHT) + if (hp.data[hx + hy*hp.width] != RC_UNSET_HEIGHT) continue; - const int ai = (int)chf.cells[(ax+bs)+(ay+bs)*chf.width].index + rcGetCon(cs, dir); - + const int ai = (int)chf.cells[ax + ay*chf.width].index + rcGetCon(cs, dir); const rcCompactSpan& as = chf.spans[ai]; - int idx = ax-hp.xmin+(ay-hp.ymin)*hp.width; - hp.data[idx] = as.y; - - stack.push(ax); - stack.push(ay); - stack.push(ai); + + hp.data[hx + hy*hp.width] = as.y; + + push3(queue, ax, ay, ai); } } - } static unsigned char getEdgeFlags(const float* va, const float* vb, @@ -923,7 +1145,7 @@ static unsigned char getEdgeFlags(const float* va, const float* vb, static const float thrSqr = rcSqr(0.001f); for (int i = 0, j = npoly-1; i < npoly; j=i++) { - if (distancePtSeg2d(va, &vpoly[j*3], &vpoly[i*3]) < thrSqr && + if (distancePtSeg2d(va, &vpoly[j*3], &vpoly[i*3]) < thrSqr && distancePtSeg2d(vb, &vpoly[j*3], &vpoly[i*3]) < thrSqr) return 1; } @@ -951,8 +1173,8 @@ 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; @@ -961,23 +1183,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); @@ -1015,7 +1238,7 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa maxhh = rcMax(maxhh, ymax-ymin); } - hp.data = (unsigned short *)rcAlloc(sizeof(unsigned short)*maxhw*maxhh, RC_ALLOC_TEMP); + hp.data = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxhw*maxhh, RC_ALLOC_TEMP); if (!hp.data) { ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'hp.data' (%d).", maxhw*maxhh); @@ -1031,10 +1254,10 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.meshes' (%d).", dmesh.nmeshes*4); return false; } - + int vcap = nPolyVerts+nPolyVerts/2; int tcap = vcap*2; - + dmesh.nverts = 0; dmesh.verts = (float*)rcAlloc(sizeof(float)*vcap*3, RC_ALLOC_PERM); if (!dmesh.verts) @@ -1043,7 +1266,7 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa return false; } dmesh.ntris = 0; - dmesh.tris = (unsigned char*)rcAlloc(sizeof(unsigned char*)*tcap*4, RC_ALLOC_PERM); + dmesh.tris = (unsigned char*)rcAlloc(sizeof(unsigned char)*tcap*4, RC_ALLOC_PERM); if (!dmesh.tris) { ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.tris' (%d).", tcap*4); @@ -1071,18 +1294,19 @@ 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); + 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; } - + // Move detail verts to world space. for (int j = 0; j < nverts; ++j) { @@ -1097,21 +1321,21 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa poly[j*3+1] += orig[1]; poly[j*3+2] += orig[2]; } - + // Store detail submesh. const int ntris = tris.size()/4; - + dmesh.meshes[i*4+0] = (unsigned int)dmesh.nverts; dmesh.meshes[i*4+1] = (unsigned int)nverts; dmesh.meshes[i*4+2] = (unsigned int)dmesh.ntris; - dmesh.meshes[i*4+3] = (unsigned int)ntris; + dmesh.meshes[i*4+3] = (unsigned int)ntris; // Store vertices, allocate more memory if necessary. if (dmesh.nverts+nverts > vcap) { while (dmesh.nverts+nverts > vcap) vcap += 256; - + float* newv = (float*)rcAlloc(sizeof(float)*vcap*3, RC_ALLOC_PERM); if (!newv) { @@ -1157,9 +1381,7 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa dmesh.ntris++; } } - - ctx->stopTimer(RC_TIMER_BUILD_POLYMESHDETAIL); - + return true; } @@ -1168,12 +1390,12 @@ 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; int maxMeshes = 0; - + for (int i = 0; i < nmeshes; ++i) { if (!meshes[i]) continue; @@ -1181,7 +1403,7 @@ bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int maxTris += meshes[i]->ntris; maxMeshes += meshes[i]->nmeshes; } - + mesh.nmeshes = 0; mesh.meshes = (unsigned int*)rcAlloc(sizeof(unsigned int)*maxMeshes*4, RC_ALLOC_PERM); if (!mesh.meshes) @@ -1189,7 +1411,7 @@ bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'pmdtl.meshes' (%d).", maxMeshes*4); return false; } - + mesh.ntris = 0; mesh.tris = (unsigned char*)rcAlloc(sizeof(unsigned char)*maxTris*4, RC_ALLOC_PERM); if (!mesh.tris) @@ -1197,7 +1419,7 @@ bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.tris' (%d).", maxTris*4); return false; } - + mesh.nverts = 0; mesh.verts = (float*)rcAlloc(sizeof(float)*maxVerts*3, RC_ALLOC_PERM); if (!mesh.verts) @@ -1221,7 +1443,7 @@ bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int dst[3] = src[3]; mesh.nmeshes++; } - + for (int k = 0; k < dm->nverts; ++k) { rcVcopy(&mesh.verts[mesh.nverts*3], &dm->verts[k*3]); @@ -1236,9 +1458,6 @@ bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int mesh.ntris++; } } - - ctx->stopTimer(RC_TIMER_MERGE_POLYMESHDETAIL); return true; } - diff --git a/extern/recastnavigation/Recast/Source/RecastRasterization.cpp b/extern/recastnavigation/Recast/Source/RecastRasterization.cpp index d2bb7c98f18..a4cef749098 100644 --- a/extern/recastnavigation/Recast/Source/RecastRasterization.cpp +++ b/extern/recastnavigation/Recast/Source/RecastRasterization.cpp @@ -50,7 +50,7 @@ static rcSpan* allocSpan(rcHeightfield& hf) // Allocate memory for the new pool. rcSpanPool* pool = (rcSpanPool*)rcAlloc(sizeof(rcSpanPool), RC_ALLOC_PERM); if (!pool) return 0; - pool->next = 0; + // Add the pool into the list of pools. pool->next = hf.pools; hf.pools = pool; @@ -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,16 +90,18 @@ 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; s->next = 0; - // Empty cell, add he first span. + // Empty cell, add the first span. 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,45 +165,80 @@ 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; } -static int clipPoly(const float* in, int n, float* out, float pnx, float pnz, float pd) +// divides a convex polygons into two convex polygons on both sides of a line +static void dividePoly(const float* in, int nin, + float* out1, int* nout1, + float* out2, int* nout2, + float x, int axis) { float d[12]; - for (int i = 0; i < n; ++i) - d[i] = pnx*in[i*3+0] + pnz*in[i*3+2] + pd; - - int m = 0; - for (int i = 0, j = n-1; i < n; j=i, ++i) + for (int i = 0; i < nin; ++i) + d[i] = x - in[i*3+axis]; + + int m = 0, n = 0; + for (int i = 0, j = nin-1; i < nin; j=i, ++i) { bool ina = d[j] >= 0; bool inb = d[i] >= 0; if (ina != inb) { float s = d[j] / (d[j] - d[i]); - out[m*3+0] = in[j*3+0] + (in[i*3+0] - in[j*3+0])*s; - out[m*3+1] = in[j*3+1] + (in[i*3+1] - in[j*3+1])*s; - out[m*3+2] = in[j*3+2] + (in[i*3+2] - in[j*3+2])*s; + out1[m*3+0] = in[j*3+0] + (in[i*3+0] - in[j*3+0])*s; + out1[m*3+1] = in[j*3+1] + (in[i*3+1] - in[j*3+1])*s; + out1[m*3+2] = in[j*3+2] + (in[i*3+2] - in[j*3+2])*s; + rcVcopy(out2 + n*3, out1 + m*3); m++; + n++; + // add the i'th point to the right polygon. Do NOT add points that are on the dividing line + // since these were already added above + if (d[i] > 0) + { + rcVcopy(out1 + m*3, in + i*3); + m++; + } + else if (d[i] < 0) + { + rcVcopy(out2 + n*3, in + i*3); + n++; + } } - if (inb) + else // same side { - out[m*3+0] = in[i*3+0]; - out[m*3+1] = in[i*3+1]; - out[m*3+2] = in[i*3+2]; - m++; + // add the i'th point to the right polygon. Addition is done even for points on the dividing line + if (d[i] >= 0) + { + rcVcopy(out1 + m*3, in + i*3); + m++; + if (d[i] != 0) + continue; + } + rcVcopy(out2 + n*3, in + i*3); + n++; } } - return m; + + *nout1 = m; + *nout2 = n; } -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, @@ -220,50 +259,59 @@ 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 footpring of the triangle on the grid. - int x0 = (int)((tmin[0] - bmin[0])*ics); + // Calculate the footprint of the triangle on the grid's y-axis int y0 = (int)((tmin[2] - bmin[2])*ics); - int x1 = (int)((tmax[0] - bmin[0])*ics); int y1 = (int)((tmax[2] - bmin[2])*ics); - x0 = rcClamp(x0, 0, w-1); y0 = rcClamp(y0, 0, h-1); - x1 = rcClamp(x1, 0, w-1); y1 = rcClamp(y1, 0, h-1); // Clip the triangle into all grid cells it touches. - float in[7*3], out[7*3], inrow[7*3]; + float buf[7*3*4]; + float *in = buf, *inrow = buf+7*3, *p1 = inrow+7*3, *p2 = p1+7*3; + + rcVcopy(&in[0], v0); + rcVcopy(&in[1*3], v1); + rcVcopy(&in[2*3], v2); + int nvrow, nvIn = 3; for (int y = y0; y <= y1; ++y) { - // Clip polygon to row. - rcVcopy(&in[0], v0); - rcVcopy(&in[1*3], v1); - rcVcopy(&in[2*3], v2); - int nvrow = 3; + // Clip polygon to row. Store the remaining polygon as well const float cz = bmin[2] + y*cs; - nvrow = clipPoly(in, nvrow, out, 0, 1, -cz); - if (nvrow < 3) continue; - nvrow = clipPoly(out, nvrow, inrow, 0, -1, cz+cs); + dividePoly(in, nvIn, inrow, &nvrow, p1, &nvIn, cz+cs, 2); + rcSwap(in, p1); if (nvrow < 3) continue; + // find the horizontal bounds in the row + float minX = inrow[0], maxX = inrow[0]; + for (int i=1; i<nvrow; ++i) + { + if (minX > inrow[i*3]) minX = inrow[i*3]; + if (maxX < inrow[i*3]) maxX = inrow[i*3]; + } + int x0 = (int)((minX - bmin[0])*ics); + int x1 = (int)((maxX - bmin[0])*ics); + x0 = rcClamp(x0, 0, w-1); + x1 = rcClamp(x1, 0, w-1); + + int nv, nv2 = nvrow; + for (int x = x0; x <= x1; ++x) { - // Clip polygon to column. - int nv = nvrow; + // Clip polygon to column. store the remaining polygon as well const float cx = bmin[0] + x*cs; - nv = clipPoly(inrow, nv, out, 1, 0, -cx); - if (nv < 3) continue; - nv = clipPoly(out, nv, in, -1, 0, cx+cs); + dividePoly(inrow, nv2, p1, &nv, p2, &nv2, cx+cs, 0); + rcSwap(inrow, p2); if (nv < 3) continue; // Calculate min and max of the span. - float smin = in[1], smax = in[1]; + float smin = p1[1], smax = p1[1]; for (int i = 1; i < nv; ++i) { - smin = rcMin(smin, in[i*3+1]); - smax = rcMax(smax, in[i*3+1]); + smin = rcMin(smin, p1[i*3+1]); + smax = rcMax(smax, p1[i*3+1]); } smin -= bmin[1]; smax -= bmin[1]; @@ -278,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 @@ -288,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 @@ -308,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; @@ -325,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 @@ -336,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; @@ -353,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 @@ -364,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; @@ -380,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/extern/recastnavigation/Recast/Source/RecastRegion.cpp b/extern/recastnavigation/Recast/Source/RecastRegion.cpp index 4290972ed24..54acf4b736b 100644 --- a/extern/recastnavigation/Recast/Source/RecastRegion.cpp +++ b/extern/recastnavigation/Recast/Source/RecastRegion.cpp @@ -286,7 +286,10 @@ static bool floodRegion(int x, int y, int i, if (nr & RC_BORDER_REG) // Do not take borders into account. continue; if (nr != 0 && nr != r) + { ar = nr; + break; + } const rcCompactSpan& as = chf.spans[ai]; @@ -298,9 +301,12 @@ static bool floodRegion(int x, int y, int i, const int ai2 = (int)chf.cells[ax2+ay2*w].index + rcGetCon(as, dir2); if (chf.areas[ai2] != area) continue; - unsigned short nr = srcReg[ai2]; - if (nr != 0 && nr != r) - ar = nr; + unsigned short nr2 = srcReg[ai2]; + if (nr2 != 0 && nr2 != r) + { + ar = nr2; + break; + } } } } @@ -309,6 +315,7 @@ static bool floodRegion(int x, int y, int i, srcReg[ci] = 0; continue; } + count++; // Expand neighbours. @@ -340,30 +347,44 @@ 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) + rcIntArray& stack, + bool fillStack) { const int w = chf.width; const int h = chf.height; - // Find cells revealed by the raised level. - stack.resize(0); - for (int y = 0; y < h; ++y) + if (fillStack) { - for (int x = 0; x < w; ++x) + // Find cells revealed by the raised level. + stack.resize(0); + for (int y = 0; y < h; ++y) { - const rcCompactCell& c = chf.cells[x+y*w]; - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) + for (int x = 0; x < w; ++x) { - if (chf.dist[i] >= level && srcReg[i] == 0 && chf.areas[i] != RC_NULL_AREA) + const rcCompactCell& c = chf.cells[x+y*w]; + for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) { - stack.push(x); - stack.push(y); - stack.push(i); + if (chf.dist[i] >= level && srcReg[i] == 0 && chf.areas[i] != RC_NULL_AREA) + { + stack.push(x); + stack.push(y); + stack.push(i); + } } } } } - + else // use cells in the input stack + { + // mark all cells which already have a region + for (int j=0; j<stack.size(); j+=3) + { + int i = stack[j+2]; + if (srcReg[i] != 0) + stack[j+2] = -1; + } + } + int iter = 0; while (stack.size() > 0) { @@ -434,6 +455,61 @@ static unsigned short* expandRegions(int maxIter, unsigned short level, } + +static void sortCellsByLevel(unsigned short startLevel, + rcCompactHeightfield& chf, + unsigned short* srcReg, + unsigned int nbStacks, rcIntArray* stacks, + unsigned short loglevelsPerStack) // the levels per stack (2 in our case) as a bit shift +{ + const int w = chf.width; + const int h = chf.height; + startLevel = startLevel >> loglevelsPerStack; + + for (unsigned int j=0; j<nbStacks; ++j) + stacks[j].resize(0); + + // put all cells in the level range into the appropriate stacks + for (int y = 0; y < h; ++y) + { + for (int x = 0; x < w; ++x) + { + const rcCompactCell& c = chf.cells[x+y*w]; + for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) + { + if (chf.areas[i] == RC_NULL_AREA || srcReg[i] != 0) + continue; + + int level = chf.dist[i] >> loglevelsPerStack; + int sId = startLevel - level; + if (sId >= (int)nbStacks) + continue; + if (sId < 0) + sId = 0; + + stacks[sId].push(x); + stacks[sId].push(y); + stacks[sId].push(i); + } + } + } +} + + +static void appendStacks(rcIntArray& srcStack, rcIntArray& dstStack, + unsigned short* srcReg) +{ + for (int j=0; j<srcStack.size(); j+=3) + { + int i = srcStack[j+2]; + if ((i < 0) || (srcReg[i] != 0)) + continue; + dstStack.push(srcStack[j]); + dstStack.push(srcStack[j+1]); + dstStack.push(srcStack[j+2]); + } +} + struct rcRegion { inline rcRegion(unsigned short i) : @@ -441,7 +517,11 @@ struct rcRegion id(i), areaType(0), remap(false), - visited(false) + visited(false), + overlap(false), + connectsToBorder(false), + ymin(0xffff), + ymax(0) {} int spanCount; // Number of spans belonging to this region @@ -449,6 +529,9 @@ struct rcRegion unsigned char areaType; // Are type. bool remap; bool visited; + bool overlap; + bool connectsToBorder; + unsigned short ymin, ymax; rcIntArray connections; rcIntArray floors; }; @@ -678,25 +761,26 @@ static void walkContour(int x, int y, int i, int dir, // Remove adjacent duplicates. if (cont.size() > 1) { - for (int i = 0; i < cont.size(); ) + for (int j = 0; j < cont.size(); ) { - int ni = (i+1) % cont.size(); - if (cont[i] == cont[ni]) + int nj = (j+1) % cont.size(); + if (cont[j] == cont[nj]) { - for (int j = i; j < cont.size()-1; ++j) - cont[j] = cont[j+1]; + for (int k = j; k < cont.size()-1; ++k) + cont[k] = cont[k+1]; cont.pop(); } else - ++i; + ++j; } } } -static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegionSize, - unsigned short& maxRegionId, - rcCompactHeightfield& chf, - unsigned short* srcReg) + +static bool mergeAndFilterRegions(rcContext* ctx, int minRegionArea, int mergeRegionSize, + unsigned short& maxRegionId, + rcCompactHeightfield& chf, + unsigned short* srcReg, rcIntArray& overlaps) { const int w = chf.width; const int h = chf.height; @@ -705,7 +789,7 @@ static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegio rcRegion* regions = (rcRegion*)rcAlloc(sizeof(rcRegion)*nreg, RC_ALLOC_TEMP); if (!regions) { - ctx->log(RC_LOG_ERROR, "filterSmallRegions: Out of memory 'regions' (%d).", nreg); + ctx->log(RC_LOG_ERROR, "mergeAndFilterRegions: Out of memory 'regions' (%d).", nreg); return false; } @@ -728,7 +812,6 @@ static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegio rcRegion& reg = regions[r]; reg.spanCount++; - // Update floors. for (int j = (int)c.index; j < ni; ++j) { @@ -736,6 +819,8 @@ static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegio unsigned short floorId = srcReg[j]; if (floorId == 0 || floorId >= nreg) continue; + if (floorId == r) + reg.overlap = true; addUniqueFloorRegion(reg, floorId); } @@ -806,14 +891,14 @@ static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegio connectsToBorder = true; continue; } - rcRegion& nreg = regions[creg.connections[j]]; - if (nreg.visited) + rcRegion& neireg = regions[creg.connections[j]]; + if (neireg.visited) continue; - if (nreg.id == 0 || (nreg.id & RC_BORDER_REG)) + if (neireg.id == 0 || (neireg.id & RC_BORDER_REG)) continue; // Visit - stack.push(nreg.id); - nreg.visited = true; + stack.push(neireg.id); + neireg.visited = true; } } @@ -831,7 +916,7 @@ static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegio } } } - + // Merge too small regions to neighbour regions. int mergeCount = 0 ; do @@ -841,7 +926,9 @@ static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegio { rcRegion& reg = regions[i]; if (reg.id == 0 || (reg.id & RC_BORDER_REG)) - continue; + continue; + if (reg.overlap) + continue; if (reg.spanCount == 0) continue; @@ -858,7 +945,7 @@ static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegio { if (reg.connections[j] & RC_BORDER_REG) continue; rcRegion& mreg = regions[reg.connections[j]]; - if (mreg.id == 0 || (mreg.id & RC_BORDER_REG)) continue; + if (mreg.id == 0 || (mreg.id & RC_BORDER_REG) || mreg.overlap) continue; if (mreg.spanCount < smallest && canMergeWithRegion(reg, mreg) && canMergeWithRegion(mreg, reg)) @@ -928,6 +1015,224 @@ static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegio if ((srcReg[i] & RC_BORDER_REG) == 0) srcReg[i] = regions[srcReg[i]].id; } + + // Return regions that we found to be overlapping. + for (int i = 0; i < nreg; ++i) + if (regions[i].overlap) + overlaps.push(regions[i].id); + + for (int i = 0; i < nreg; ++i) + regions[i].~rcRegion(); + rcFree(regions); + + + return true; +} + + +static void addUniqueConnection(rcRegion& reg, int n) +{ + for (int i = 0; i < reg.connections.size(); ++i) + if (reg.connections[i] == n) + return; + reg.connections.push(n); +} + +static bool mergeAndFilterLayerRegions(rcContext* ctx, int minRegionArea, + unsigned short& maxRegionId, + rcCompactHeightfield& chf, + unsigned short* srcReg, rcIntArray& /*overlaps*/) +{ + 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) + { + 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); + + // Find region neighbours and overlapping regions. + rcIntArray lregs(32); + for (int y = 0; y < h; ++y) + { + for (int x = 0; x < w; ++x) + { + const rcCompactCell& c = chf.cells[x+y*w]; + + lregs.resize(0); + + for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) + { + const rcCompactSpan& s = chf.spans[i]; + const unsigned short ri = srcReg[i]; + if (ri == 0 || ri >= nreg) continue; + rcRegion& reg = regions[ri]; + + reg.spanCount++; + + reg.ymin = rcMin(reg.ymin, s.y); + reg.ymax = rcMax(reg.ymax, s.y); + + // Collect all region layers. + lregs.push(ri); + + // Update neighbours + for (int dir = 0; dir < 4; ++dir) + { + if (rcGetCon(s, dir) != RC_NOT_CONNECTED) + { + const int ax = x + rcGetDirOffsetX(dir); + const int ay = y + rcGetDirOffsetY(dir); + const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir); + const unsigned short rai = srcReg[ai]; + if (rai > 0 && rai < nreg && rai != ri) + addUniqueConnection(reg, rai); + if (rai & RC_BORDER_REG) + reg.connectsToBorder = true; + } + } + + } + + // Update overlapping regions. + for (int i = 0; i < lregs.size()-1; ++i) + { + for (int j = i+1; j < lregs.size(); ++j) + { + if (lregs[i] != lregs[j]) + { + rcRegion& ri = regions[lregs[i]]; + rcRegion& rj = regions[lregs[j]]; + addUniqueFloorRegion(ri, lregs[j]); + addUniqueFloorRegion(rj, lregs[i]); + } + } + } + + } + } + + // Create 2D layers from regions. + unsigned short layerId = 1; + + for (int i = 0; i < nreg; ++i) + regions[i].id = 0; + + // Merge montone regions to create non-overlapping areas. + rcIntArray stack(32); + for (int i = 1; i < nreg; ++i) + { + rcRegion& root = regions[i]; + // Skip already visited. + if (root.id != 0) + continue; + + // Start search. + root.id = layerId; + + stack.resize(0); + stack.push(i); + + while (stack.size() > 0) + { + // Pop front + rcRegion& reg = regions[stack[0]]; + for (int j = 0; j < stack.size()-1; ++j) + stack[j] = stack[j+1]; + stack.resize(stack.size()-1); + + const int ncons = (int)reg.connections.size(); + for (int j = 0; j < ncons; ++j) + { + const int nei = reg.connections[j]; + rcRegion& regn = regions[nei]; + // Skip already visited. + if (regn.id != 0) + continue; + // Skip if the neighbour is overlapping root region. + bool overlap = false; + for (int k = 0; k < root.floors.size(); k++) + { + if (root.floors[k] == nei) + { + overlap = true; + break; + } + } + if (overlap) + continue; + + // Deepen + stack.push(nei); + + // Mark layer id + regn.id = layerId; + // Merge current layers to root. + for (int k = 0; k < regn.floors.size(); ++k) + addUniqueFloorRegion(root, regn.floors[k]); + root.ymin = rcMin(root.ymin, regn.ymin); + root.ymax = rcMax(root.ymax, regn.ymax); + root.spanCount += regn.spanCount; + regn.spanCount = 0; + root.connectsToBorder = root.connectsToBorder || regn.connectsToBorder; + } + } + + layerId++; + } + + // Remove small regions + for (int i = 0; i < nreg; ++i) + { + if (regions[i].spanCount > 0 && regions[i].spanCount < minRegionArea && !regions[i].connectsToBorder) + { + unsigned short reg = regions[i].id; + for (int j = 0; j < nreg; ++j) + if (regions[j].id == reg) + regions[j].id = 0; + } + } + + // Compress region Ids. + for (int i = 0; i < nreg; ++i) + { + regions[i].remap = false; + if (regions[i].id == 0) continue; // Skip nil regions. + if (regions[i].id & RC_BORDER_REG) continue; // Skip external regions. + regions[i].remap = true; + } + + unsigned short regIdGen = 0; + for (int i = 0; i < nreg; ++i) + { + if (!regions[i].remap) + continue; + unsigned short oldId = regions[i].id; + unsigned short newId = ++regIdGen; + for (int j = i; j < nreg; ++j) + { + if (regions[j].id == oldId) + { + regions[j].id = newId; + regions[j].remap = false; + } + } + } + maxRegionId = regIdGen; + + // Remap regions. + for (int i = 0; i < chf.spanCount; ++i) + { + if ((srcReg[i] & RC_BORDER_REG) == 0) + srcReg[i] = regions[srcReg[i]].id; + } for (int i = 0; i < nreg; ++i) regions[i].~rcRegion(); @@ -936,6 +1241,8 @@ static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegio return true; } + + /// @par /// /// This is usually the second to the last step in creating a fully built @@ -950,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) { @@ -974,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); @@ -1052,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); @@ -1067,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); @@ -1181,20 +1486,22 @@ bool rcBuildRegionsMonotone(rcContext* ctx, rcCompactHeightfield& chf, } } - ctx->startTimer(RC_TIMER_BUILD_REGIONS_FILTER); - // Filter out small regions. - chf.maxRegions = id; - if (!filterSmallRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg)) - return false; + { + rcScopedTimer timerFilter(ctx, RC_TIMER_BUILD_REGIONS_FILTER); - ctx->stopTimer(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; + + // 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; } @@ -1223,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); @@ -1236,7 +1543,13 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf, } ctx->startTimer(RC_TIMER_BUILD_REGIONS_WATERSHED); - + + const int LOG_NB_STACKS = 3; + const int NB_STACKS = 1 << LOG_NB_STACKS; + rcIntArray lvlStacks[NB_STACKS]; + for (int i=0; i<NB_STACKS; ++i) + lvlStacks[i].resize(1024); + rcIntArray stack(1024); rcIntArray visited(1024); @@ -1262,6 +1575,13 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf, // Make sure border will not overflow. const int bw = rcMin(w, borderSize); const int bh = rcMin(h, borderSize); + + if (regionId > 0xFFFB) + { + ctx->log(RC_LOG_ERROR, "rcBuildRegions: Region ID overflow"); + return false; + } + // 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++; @@ -1271,44 +1591,60 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf, chf.borderSize = borderSize; } + int sId = -1; while (level > 0) { level = level >= 2 ? level-2 : 0; - - 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, stack) != srcReg) + sId = (sId+1) & (NB_STACKS-1); + +// ctx->startTimer(RC_TIMER_DIVIDE_TO_LEVELS); + + if (sId == 0) + sortCellsByLevel(level, chf, srcReg, NB_STACKS, lvlStacks, 1); + else + appendStacks(lvlStacks[sId-1], lvlStacks[sId], srcReg); // copy left overs from last level + +// ctx->stopTimer(RC_TIMER_DIVIDE_TO_LEVELS); + { - 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 y = 0; y < h; ++y) { - for (int x = 0; x < w; ++x) + rcScopedTimer timerFloor(ctx, RC_TIMER_BUILD_REGIONS_FLOOD); + + // Mark new regions with IDs. + for (int j = 0; j<lvlStacks[sId].size(); j += 3) { - const rcCompactCell& c = chf.cells[x+y*w]; - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) + int x = lvlStacks[sId][j]; + int y = lvlStacks[sId][j+1]; + int i = lvlStacks[sId][j+2]; + if (i >= 0 && srcReg[i] == 0) { - if (chf.dist[i] < level || srcReg[i] != 0 || chf.areas[i] == RC_NULL_AREA) - continue; 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. - if (expandRegions(expandIters*8, 0, chf, srcReg, srcDist, dstReg, dstDist, stack) != srcReg) + if (expandRegions(expandIters*8, 0, chf, srcReg, srcDist, dstReg, dstDist, stack, true) != srcReg) { rcSwap(srcReg, dstReg); rcSwap(srcDist, dstDist); @@ -1316,22 +1652,179 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf, ctx->stopTimer(RC_TIMER_BUILD_REGIONS_WATERSHED); - ctx->startTimer(RC_TIMER_BUILD_REGIONS_FILTER); - - // Filter out small regions. - chf.maxRegions = regionId; - if (!filterSmallRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg)) - return false; - - ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FILTER); + { + 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; + + // 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; } +bool rcBuildLayerRegions(rcContext* ctx, rcCompactHeightfield& chf, + const int borderSize, const int minRegionArea) +{ + rcAssert(ctx); + + 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)); + if (!srcReg) + { + ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'src' (%d).", chf.spanCount); + return false; + } + 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)); + if (!sweeps) + { + ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'sweeps' (%d).", nsweeps); + return false; + } + + + // Mark border regions. + if (borderSize > 0) + { + // 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, id|RC_BORDER_REG, chf, srcReg); id++; + 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; + } + + rcIntArray prev(256); + + // Sweep one line at a time. + for (int y = borderSize; y < h-borderSize; ++y) + { + // Collect spans from this row. + prev.resize(id+1); + memset(&prev[0],0,sizeof(int)*id); + unsigned short rid = 1; + + for (int x = borderSize; x < w-borderSize; ++x) + { + const rcCompactCell& c = chf.cells[x+y*w]; + + for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) + { + const rcCompactSpan& s = chf.spans[i]; + if (chf.areas[i] == RC_NULL_AREA) continue; + + // -x + unsigned short previd = 0; + if (rcGetCon(s, 0) != RC_NOT_CONNECTED) + { + const int ax = x + rcGetDirOffsetX(0); + const int ay = y + rcGetDirOffsetY(0); + const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 0); + if ((srcReg[ai] & RC_BORDER_REG) == 0 && chf.areas[i] == chf.areas[ai]) + previd = srcReg[ai]; + } + + if (!previd) + { + previd = rid++; + sweeps[previd].rid = previd; + sweeps[previd].ns = 0; + sweeps[previd].nei = 0; + } + + // -y + if (rcGetCon(s,3) != RC_NOT_CONNECTED) + { + const int ax = x + rcGetDirOffsetX(3); + const int ay = y + rcGetDirOffsetY(3); + const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 3); + if (srcReg[ai] && (srcReg[ai] & RC_BORDER_REG) == 0 && chf.areas[i] == chf.areas[ai]) + { + unsigned short nr = srcReg[ai]; + if (!sweeps[previd].nei || sweeps[previd].nei == nr) + { + sweeps[previd].nei = nr; + sweeps[previd].ns++; + prev[nr]++; + } + else + { + sweeps[previd].nei = RC_NULL_NEI; + } + } + } + + srcReg[i] = previd; + } + } + + // Create unique ID. + for (int i = 1; i < rid; ++i) + { + if (sweeps[i].nei != RC_NULL_NEI && sweeps[i].nei != 0 && + prev[sweeps[i].nei] == (int)sweeps[i].ns) + { + sweeps[i].id = sweeps[i].nei; + } + else + { + sweeps[i].id = id++; + } + } + + // Remap IDs + for (int x = borderSize; x < w-borderSize; ++x) + { + const rcCompactCell& c = chf.cells[x+y*w]; + + for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) + { + if (srcReg[i] > 0 && srcReg[i] < rid) + srcReg[i] = sweeps[srcReg[i]].id; + } + } + } + + + { + 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]; + + return true; +} diff --git a/extern/recastnavigation/Recast/Source/RecastTimer.cpp b/extern/recastnavigation/Recast/Source/RecastTimer.cpp deleted file mode 100644 index 51ffb7d3160..00000000000 --- a/extern/recastnavigation/Recast/Source/RecastTimer.cpp +++ /dev/null @@ -1,58 +0,0 @@ -#include "RecastTimer.h" - -#if defined(WIN32) - -// Win32 -#include <windows.h> - -rcTimeVal rcGetPerformanceTimer() -{ - __int64 count; - QueryPerformanceCounter((LARGE_INTEGER*)&count); - return count; -} - -int rcGetDeltaTimeUsec(rcTimeVal start, rcTimeVal end) -{ - static __int64 freq = 0; - if (freq == 0) - QueryPerformanceFrequency((LARGE_INTEGER*)&freq); - __int64 elapsed = end - start; - return (int)(elapsed*1000000 / freq); -} - -#elif defined(__MACH__) - -// OSX -#include <mach/mach_time.h> - -rcTimeVal rcGetPerformanceTimer() -{ - return mach_absolute_time(); -} - -int rcGetDeltaTimeUsec(rcTimeVal start, rcTimeVal end) -{ - static mach_timebase_info_data_t timebaseInfo; - if (timebaseInfo.denom == 0) - mach_timebase_info(&timebaseInfo); - uint64_t elapsed = end - start; - uint64_t nanosec = elapsed * timebaseInfo.numer / timebaseInfo.denom; - return (int)(nanosec / 1000); -} - -#else - -// TODO: Linux, etc - -rcTimeVal rcGetPerformanceTimer() -{ - return 0; -} - -int rcGetDeltaTimeUsec(rcTimeVal start, rcTimeVal end) -{ - return 0; -} - -#endif
\ No newline at end of file diff --git a/extern/recastnavigation/readme-blender.txt b/extern/recastnavigation/readme-blender.txt new file mode 100644 index 00000000000..2a1b2882ce2 --- /dev/null +++ b/extern/recastnavigation/readme-blender.txt @@ -0,0 +1,22 @@ +The version of Recast is 1.5.0, from: +https://github.com/recastnavigation/recastnavigation +Changes made: + * Recast/Source/RecastMesh.cpp: made buildMeshAdjacency() non-static so it can be used with recast-capi + * Recast/Include/Recast.h: Added forward declaration for buildMeshAdjacency() + +The following additional files were added: + * recast-capi.cpp + * recast-capi.h +These expose a C interface to the Recast library, which has only C++ headers. + +The version of Detour is 1.4, from: +https://code.google.com/archive/p/recastnavigation/downloads +Changes made: + * DetourStatNavMesh.h: use more portable definition of DT_STAT_NAVMESH_MAGIC + * DetourStatNavMesh.cpp: comment out some unused variables to avoid compiler warnings + * DetourStatNavMeshBuilder.h: add forward declaration for createBVTree + * DetourStatNavMeshBuilder.cpp: made createBVTree non-static for use with recast-capi + +The CMakeLists.txt file has been added, since the original software does not include build files for the libraries. + +~rdb diff --git a/extern/recastnavigation/recast-capi.cpp b/extern/recastnavigation/recast-capi.cpp index 38c14118156..1163265722b 100644 --- a/extern/recastnavigation/recast-capi.cpp +++ b/extern/recastnavigation/recast-capi.cpp @@ -68,17 +68,41 @@ int recast_createHeightfield(struct recast_heightfield *hf, int width, int heigh } void recast_markWalkableTriangles(const float walkableSlopeAngle,const float *verts, int nv, - const int *tris, int nt, unsigned char *flags) + const int *tris, int nt, unsigned char *areas) { INIT_SCTX(); - rcMarkWalkableTriangles(sctx, walkableSlopeAngle, verts, nv, tris, nt, flags); + rcMarkWalkableTriangles(sctx, walkableSlopeAngle, verts, nv, tris, nt, areas); } -void recast_rasterizeTriangles(const float *verts, int nv, const int *tris, - const unsigned char *flags, int nt, struct recast_heightfield *solid) +void recast_clearUnwalkableTriangles(const float walkableSlopeAngle, const float* verts, int nv, + const int* tris, int nt, unsigned char* areas) { INIT_SCTX(); - rcRasterizeTriangles(sctx, verts, nv, tris, flags, nt, *(rcHeightfield *) solid); + rcClearUnwalkableTriangles(sctx, walkableSlopeAngle, verts, nv, tris, nt, areas); +} + +int recast_addSpan(struct recast_heightfield *hf, const int x, const int y, + const unsigned short smin, const unsigned short smax, + const unsigned char area, const int flagMergeThr) +{ + INIT_SCTX(); + return rcAddSpan(sctx, *(rcHeightfield *) hf, x, y, smin, smax, area, flagMergeThr); +} + +int recast_rasterizeTriangle(const float *v0, const float *v1, const float *v2, + const unsigned char area, struct recast_heightfield *solid, + const int flagMergeThr) +{ + INIT_SCTX(); + return rcRasterizeTriangle(sctx, v0, v1, v2, area, *(rcHeightfield *) solid, flagMergeThr); +} + +int recast_rasterizeTriangles(const float *verts, const int nv, const int *tris, + const unsigned char *areas, const int nt, struct recast_heightfield *solid, + const int flagMergeThr) +{ + INIT_SCTX(); + return rcRasterizeTriangles(sctx, verts, nv, tris, areas, nt, *(rcHeightfield *) solid, flagMergeThr); } void recast_filterLedgeSpans(const int walkableHeight, const int walkableClimb, @@ -100,6 +124,22 @@ void recast_filterLowHangingWalkableObstacles(const int walkableClimb, struct re rcFilterLowHangingWalkableObstacles(sctx, walkableClimb, *(rcHeightfield *) solid); } +int recast_getHeightFieldSpanCount(struct recast_heightfield *hf) +{ + INIT_SCTX(); + return rcGetHeightFieldSpanCount(sctx, *(rcHeightfield *) hf); +} + +struct recast_heightfieldLayerSet *recast_newHeightfieldLayerSet(void) +{ + return (struct recast_heightfieldLayerSet *) rcAllocHeightfieldLayerSet(); +} + +void recast_destroyHeightfieldLayerSet(struct recast_heightfieldLayerSet *lset) +{ + rcFreeHeightfieldLayerSet( (rcHeightfieldLayerSet *) lset); +} + struct recast_compactHeightfield *recast_newCompactHeightfield(void) { return (struct recast_compactHeightfield *) rcAllocCompactHeightfield(); @@ -124,18 +164,68 @@ int recast_erodeWalkableArea(int radius, struct recast_compactHeightfield *chf) return rcErodeWalkableArea(sctx, radius, *(rcCompactHeightfield *) chf); } +int recast_medianFilterWalkableArea(struct recast_compactHeightfield *chf) +{ + INIT_SCTX(); + return rcMedianFilterWalkableArea(sctx, *(rcCompactHeightfield *) chf); +} + +void recast_markBoxArea(const float *bmin, const float *bmax, unsigned char areaId, + struct recast_compactHeightfield *chf) +{ + INIT_SCTX(); + rcMarkBoxArea(sctx, bmin, bmax, areaId, *(rcCompactHeightfield *) chf); +} + +void recast_markConvexPolyArea(const float* verts, const int nverts, + const float hmin, const float hmax, unsigned char areaId, + struct recast_compactHeightfield *chf) +{ + INIT_SCTX(); + rcMarkConvexPolyArea(sctx, verts, nverts, hmin, hmax, areaId, *(rcCompactHeightfield *) chf); +} + +int recast_offsetPoly(const float* verts, const int nverts, + const float offset, float *outVerts, const int maxOutVerts) +{ + return rcOffsetPoly(verts, nverts, offset, outVerts, maxOutVerts); +} + +void recast_markCylinderArea(const float* pos, const float r, const float h, + unsigned char areaId, struct recast_compactHeightfield *chf) +{ + INIT_SCTX(); + rcMarkCylinderArea(sctx, pos, r, h, areaId, *(rcCompactHeightfield *) chf); +} + int recast_buildDistanceField(struct recast_compactHeightfield *chf) { INIT_SCTX(); return rcBuildDistanceField(sctx, *(rcCompactHeightfield *) chf); } -int recast_buildRegions(struct recast_compactHeightfield *chf, int borderSize, - int minRegionSize, int mergeRegionSize) +int recast_buildRegions(struct recast_compactHeightfield *chf, + const int borderSize, const int minRegionArea, const int mergeRegionArea) { INIT_SCTX(); return rcBuildRegions(sctx, *(rcCompactHeightfield *) chf, borderSize, - minRegionSize, mergeRegionSize); + minRegionArea, mergeRegionArea); +} + +int recast_buildLayerRegions(struct recast_compactHeightfield *chf, + const int borderSize, const int minRegionArea) +{ + INIT_SCTX(); + return rcBuildLayerRegions(sctx, *(rcCompactHeightfield *) chf, borderSize, + minRegionArea); +} + +int recast_buildRegionsMonotone(struct recast_compactHeightfield *chf, + const int borderSize, const int minRegionArea, const int mergeRegionArea) +{ + INIT_SCTX(); + return rcBuildRegionsMonotone(sctx, *(rcCompactHeightfield *) chf, borderSize, + minRegionArea, mergeRegionArea); } struct recast_contourSet *recast_newContourSet(void) @@ -149,10 +239,11 @@ void recast_destroyContourSet(struct recast_contourSet *contourSet) } int recast_buildContours(struct recast_compactHeightfield *chf, - const float maxError, const int maxEdgeLen, struct recast_contourSet *cset) + const float maxError, const int maxEdgeLen, struct recast_contourSet *cset, + const int buildFlags) { INIT_SCTX(); - return rcBuildContours(sctx, *(rcCompactHeightfield *) chf, maxError, maxEdgeLen, *(rcContourSet *) cset); + return rcBuildContours(sctx, *(rcCompactHeightfield *) chf, maxError, maxEdgeLen, *(rcContourSet *) cset, buildFlags); } struct recast_polyMesh *recast_newPolyMesh(void) @@ -165,10 +256,22 @@ void recast_destroyPolyMesh(struct recast_polyMesh *polyMesh) rcFreePolyMesh((rcPolyMesh *) polyMesh); } -int recast_buildPolyMesh(struct recast_contourSet *cset, int nvp, struct recast_polyMesh *mesh) +int recast_buildPolyMesh(struct recast_contourSet *cset, const int nvp, struct recast_polyMesh *mesh) +{ + INIT_SCTX(); + return rcBuildPolyMesh(sctx, *(rcContourSet *) cset, nvp, *(rcPolyMesh *) mesh); +} + +int recast_mergePolyMeshes(struct recast_polyMesh **meshes, const int nmeshes, struct recast_polyMesh *mesh) { INIT_SCTX(); - return rcBuildPolyMesh(sctx, *(rcContourSet *) cset, nvp, * (rcPolyMesh *) mesh); + return rcMergePolyMeshes(sctx, (rcPolyMesh **) meshes, nmeshes, *(rcPolyMesh *) mesh); +} + +int recast_copyPolyMesh(const struct recast_polyMesh *src, struct recast_polyMesh *dst) +{ + INIT_SCTX(); + return rcCopyPolyMesh(sctx, *(const rcPolyMesh *) src, *(rcPolyMesh *) dst); } unsigned short *recast_polyMeshGetVerts(struct recast_polyMesh *mesh, int *nverts) @@ -240,6 +343,12 @@ int recast_buildPolyMeshDetail(const struct recast_polyMesh *mesh, const struct sampleDist, sampleMaxError, *(rcPolyMeshDetail *) dmesh); } +int recast_mergePolyMeshDetails(struct recast_polyMeshDetail **meshes, const int nmeshes, struct recast_polyMeshDetail *mesh) +{ + INIT_SCTX(); + return rcMergePolyMeshDetails(sctx, (rcPolyMeshDetail **) meshes, nmeshes, *(rcPolyMeshDetail *) mesh); +} + float *recast_polyMeshDetailGetVerts(struct recast_polyMeshDetail *mesh, int *nverts) { rcPolyMeshDetail *dmesh = (rcPolyMeshDetail *)mesh; diff --git a/extern/recastnavigation/recast-capi.h b/extern/recastnavigation/recast-capi.h index 54bf84931c4..306bf79c167 100644 --- a/extern/recastnavigation/recast-capi.h +++ b/extern/recastnavigation/recast-capi.h @@ -38,12 +38,13 @@ struct recast_polyMesh; struct recast_polyMeshDetail; struct recast_heightfield; struct recast_compactHeightfield; +struct recast_heightfieldLayerSet; struct recast_contourSet; -enum recast_SpanFlags +enum recast_BuildContoursFlags { - RECAST_WALKABLE = 0x01, - RECAST_REACHABLE = 0x02 + RECAST_CONTOUR_TESS_WALL_EDGES = 0x01, + RECAST_CONTOUR_TESS_AREA_EDGES = 0x02, }; int recast_buildMeshAdjacency(unsigned short* polys, const int npolys, @@ -61,10 +62,22 @@ int recast_createHeightfield(struct recast_heightfield *hf, int width, int heigh const float *bmin, const float* bmax, float cs, float ch); void recast_markWalkableTriangles(const float walkableSlopeAngle,const float *verts, int nv, - const int *tris, int nt, unsigned char *flags); + const int *tris, int nt, unsigned char *areas); -void recast_rasterizeTriangles(const float *verts, int nv, const int *tris, - const unsigned char *flags, int nt, struct recast_heightfield *solid); +void recast_clearUnwalkableTriangles(const float walkableSlopeAngle, const float* verts, int nv, + const int* tris, int nt, unsigned char* areas); + +int recast_addSpan(struct recast_heightfield *hf, const int x, const int y, + const unsigned short smin, const unsigned short smax, + const unsigned char area, const int flagMergeThr); + +int recast_rasterizeTriangle(const float* v0, const float* v1, const float* v2, + const unsigned char area, struct recast_heightfield *solid, + const int flagMergeThr); + +int recast_rasterizeTriangles(const float *verts, const int nv, const int *tris, + const unsigned char *areas, const int nt, struct recast_heightfield *solid, + const int flagMergeThr); void recast_filterLedgeSpans(const int walkableHeight, const int walkableClimb, struct recast_heightfield *solid); @@ -73,6 +86,12 @@ void recast_filterWalkableLowHeightSpans(int walkableHeight, struct recast_heigh void recast_filterLowHangingWalkableObstacles(const int walkableClimb, struct recast_heightfield *solid); +int recast_getHeightFieldSpanCount(struct recast_heightfield *hf); + +struct recast_heightfieldLayerSet *recast_newHeightfieldLayerSet(void); + +void recast_destroyHeightfieldLayerSet(struct recast_heightfieldLayerSet *lset); + struct recast_compactHeightfield *recast_newCompactHeightfield(void); void recast_destroyCompactHeightfield(struct recast_compactHeightfield *compactHeightfield); @@ -82,10 +101,31 @@ int recast_buildCompactHeightfield(const int walkableHeight, const int walkableC int recast_erodeWalkableArea(int radius, struct recast_compactHeightfield *chf); +int recast_medianFilterWalkableArea(struct recast_compactHeightfield *chf); + +void recast_markBoxArea(const float *bmin, const float *bmax, unsigned char areaId, + struct recast_compactHeightfield *chf); + +void recast_markConvexPolyArea(const float* verts, const int nverts, + const float hmin, const float hmax, unsigned char areaId, + struct recast_compactHeightfield *chf); + +int recast_offsetPoly(const float* verts, const int nverts, + const float offset, float *outVerts, const int maxOutVerts); + +void recast_markCylinderArea(const float* pos, const float r, const float h, + unsigned char areaId, struct recast_compactHeightfield *chf); + int recast_buildDistanceField(struct recast_compactHeightfield *chf); -int recast_buildRegions(struct recast_compactHeightfield *chf, int borderSize, - int minRegionSize, int mergeRegionSize); +int recast_buildRegions(struct recast_compactHeightfield *chf, + const int borderSize, const int minRegionArea, const int mergeRegionArea); + +int recast_buildLayerRegions(struct recast_compactHeightfield *chf, + const int borderSize, const int minRegionArea); + +int recast_buildRegionsMonotone(struct recast_compactHeightfield *chf, + const int borderSize, const int minRegionArea, const int mergeRegionArea); /* Contour set */ @@ -94,7 +134,8 @@ struct recast_contourSet *recast_newContourSet(void); void recast_destroyContourSet(struct recast_contourSet *contourSet); int recast_buildContours(struct recast_compactHeightfield *chf, - const float maxError, const int maxEdgeLen, struct recast_contourSet *cset); + const float maxError, const int maxEdgeLen, struct recast_contourSet *cset, + const int buildFlags); /* Poly mesh */ @@ -102,7 +143,11 @@ struct recast_polyMesh *recast_newPolyMesh(void); void recast_destroyPolyMesh(struct recast_polyMesh *polyMesh); -int recast_buildPolyMesh(struct recast_contourSet *cset, int nvp, struct recast_polyMesh *mesh); +int recast_buildPolyMesh(struct recast_contourSet *cset, const int nvp, struct recast_polyMesh *mesh); + +int recast_mergePolyMeshes(struct recast_polyMesh **meshes, const int nmeshes, struct recast_polyMesh *mesh); + +int recast_copyPolyMesh(const struct recast_polyMesh *src, struct recast_polyMesh *dst); unsigned short *recast_polyMeshGetVerts(struct recast_polyMesh *mesh, int *nverts); @@ -121,6 +166,8 @@ void recast_destroyPolyMeshDetail(struct recast_polyMeshDetail *polyMeshDetail); int recast_buildPolyMeshDetail(const struct recast_polyMesh *mesh, const struct recast_compactHeightfield *chf, const float sampleDist, const float sampleMaxError, struct recast_polyMeshDetail *dmesh); +int recast_mergePolyMeshDetails(struct recast_polyMeshDetail **meshes, const int nmeshes, struct recast_polyMeshDetail *mesh); + float *recast_polyMeshDetailGetVerts(struct recast_polyMeshDetail *mesh, int *nverts); unsigned char *recast_polyMeshDetailGetTris(struct recast_polyMeshDetail *mesh, int *ntris); diff --git a/source/blender/editors/mesh/mesh_navmesh.c b/source/blender/editors/mesh/mesh_navmesh.c index 85868da0b15..4d07d509616 100644 --- a/source/blender/editors/mesh/mesh_navmesh.c +++ b/source/blender/editors/mesh/mesh_navmesh.c @@ -216,7 +216,7 @@ static bool buildNavMesh(const RecastData *recastParams, int nverts, float *vert /* Find triangles which are walkable based on their slope and rasterize them */ recast_markWalkableTriangles(RAD2DEGF(recastParams->agentmaxslope), verts, nverts, tris, ntris, triflags); - recast_rasterizeTriangles(verts, nverts, tris, triflags, ntris, solid); + recast_rasterizeTriangles(verts, nverts, tris, triflags, ntris, solid, 1); MEM_freeN(triflags); /* ** Step 3: Filter walkables surfaces ** */ @@ -265,7 +265,7 @@ static bool buildNavMesh(const RecastData *recastParams, int nverts, float *vert /* Create contours */ cset = recast_newContourSet(); - if (!recast_buildContours(chf, recastParams->edgemaxerror, maxEdgeLen, cset)) { + if (!recast_buildContours(chf, recastParams->edgemaxerror, maxEdgeLen, cset, RECAST_CONTOUR_TESS_WALL_EDGES)) { recast_destroyCompactHeightfield(chf); recast_destroyContourSet(cset); |