diff options
Diffstat (limited to 'extern/recastnavigation/Recast/Include/Recast.h')
| -rw-r--r-- | extern/recastnavigation/Recast/Include/Recast.h | 1297 |
1 files changed, 962 insertions, 335 deletions
diff --git a/extern/recastnavigation/Recast/Include/Recast.h b/extern/recastnavigation/Recast/Include/Recast.h index f25ab47f8fa..4e20b0f0fff 100644 --- a/extern/recastnavigation/Recast/Include/Recast.h +++ b/extern/recastnavigation/Recast/Include/Recast.h @@ -1,5 +1,5 @@ // -// Copyright (c) 2009 Mikko Mononen memon@inside.org +// Copyright (c) 2009-2010 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 @@ -19,298 +19,685 @@ #ifndef RECAST_H #define RECAST_H -// The units of the parameters are specified in parenthesis as follows: -// (vx) voxels, (wu) world units -struct rcConfig +/// The value of PI used by Recast. +static const float RC_PI = 3.14159265f; + +/// Recast log categories. +/// @see rcContext +enum rcLogCategory { - int width, height; // Dimensions of the rasterized heighfield (vx) - int tileSize; // Width and Height of a tile (vx) - int borderSize; // Non-navigable Border around the heightfield (vx) - float cs, ch; // Grid cell size and height (wu) - float bmin[3], bmax[3]; // Grid bounds (wu) - float walkableSlopeAngle; // Maximum walkble slope angle in degrees. - int walkableHeight; // Minimum height where the agent can still walk (vx) - int walkableClimb; // Maximum height between grid cells the agent can climb (vx) - int walkableRadius; // Radius of the agent in cells (vx) - int maxEdgeLen; // Maximum contour edge length (vx) - float maxSimplificationError; // Maximum distance error from contour to cells (vx) - int minRegionSize; // Minimum regions size. Smaller regions will be deleted (vx) - int mergeRegionSize; // Minimum regions size. Smaller regions will be merged (vx) - int maxVertsPerPoly; // Max number of vertices per polygon - float detailSampleDist; // Detail mesh sample spacing. - float detailSampleMaxError; // Detail mesh simplification max sample error. + RC_LOG_PROGRESS = 1, ///< A progress log entry. + RC_LOG_WARNING, ///< A warning log entry. + RC_LOG_ERROR, ///< An error log entry. }; -// Heightfield span. -struct rcSpan +/// Recast performance timer categories. +/// @see rcContext +enum rcTimerLabel +{ + /// The user defined total time of the build. + RC_TIMER_TOTAL, + /// A user defined build time. + RC_TIMER_TEMP, + /// The time to rasterize the triangles. (See: #rcRasterizeTriangle) + RC_TIMER_RASTERIZE_TRIANGLES, + /// The time to build the compact heightfield. (See: #rcBuildCompactHeightfield) + RC_TIMER_BUILD_COMPACTHEIGHTFIELD, + /// The total time to build the contours. (See: #rcBuildContours) + RC_TIMER_BUILD_CONTOURS, + /// The time to trace the boundaries of the contours. (See: #rcBuildContours) + RC_TIMER_BUILD_CONTOURS_TRACE, + /// The time to simplify the contours. (See: #rcBuildContours) + RC_TIMER_BUILD_CONTOURS_SIMPLIFY, + /// The time to filter ledge spans. (See: #rcFilterLedgeSpans) + RC_TIMER_FILTER_BORDER, + /// The time to filter low height spans. (See: #rcFilterWalkableLowHeightSpans) + RC_TIMER_FILTER_WALKABLE, + /// The time to apply the median filter. (See: #rcMedianFilterWalkableArea) + RC_TIMER_MEDIAN_AREA, + /// The time to filter low obstacles. (See: #rcFilterLowHangingWalkableObstacles) + RC_TIMER_FILTER_LOW_OBSTACLES, + /// The time to build the polygon mesh. (See: #rcBuildPolyMesh) + RC_TIMER_BUILD_POLYMESH, + /// The time to merge polygon meshes. (See: #rcMergePolyMeshes) + RC_TIMER_MERGE_POLYMESH, + /// The time to erode the walkable area. (See: #rcErodeWalkableArea) + RC_TIMER_ERODE_AREA, + /// The time to mark a box area. (See: #rcMarkBoxArea) + RC_TIMER_MARK_BOX_AREA, + /// The time to mark a cylinder area. (See: #rcMarkCylinderArea) + RC_TIMER_MARK_CYLINDER_AREA, + /// The time to mark a convex polygon area. (See: #rcMarkConvexPolyArea) + RC_TIMER_MARK_CONVEXPOLY_AREA, + /// The total time to build the distance field. (See: #rcBuildDistanceField) + RC_TIMER_BUILD_DISTANCEFIELD, + /// The time to build the distances of the distance field. (See: #rcBuildDistanceField) + RC_TIMER_BUILD_DISTANCEFIELD_DIST, + /// The time to blur the distance field. (See: #rcBuildDistanceField) + RC_TIMER_BUILD_DISTANCEFIELD_BLUR, + /// The total time to build the regions. (See: #rcBuildRegions, #rcBuildRegionsMonotone) + RC_TIMER_BUILD_REGIONS, + /// The total time to apply the watershed algorithm. (See: #rcBuildRegions) + RC_TIMER_BUILD_REGIONS_WATERSHED, + /// The time to expand regions while applying the watershed algorithm. (See: #rcBuildRegions) + RC_TIMER_BUILD_REGIONS_EXPAND, + /// The time to flood regions while applying the watershed algorithm. (See: #rcBuildRegions) + RC_TIMER_BUILD_REGIONS_FLOOD, + /// 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, + /// The time to build the polygon mesh detail. (See: #rcBuildPolyMeshDetail) + RC_TIMER_BUILD_POLYMESHDETAIL, + /// The time to merge polygon mesh details. (See: #rcMergePolyMeshDetails) + RC_TIMER_MERGE_POLYMESHDETAIL, + /// The maximum number of timers. (Used for iterating timers.) + RC_MAX_TIMERS +}; + +/// Provides an interface for optional logging and performance tracking of the Recast +/// build process. +/// @ingroup recast +class rcContext +{ +public: + + /// Contructor. + /// @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. + 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. + void log(const rcLogCategory category, const char* format, ...); + + /// Enables or disables the performance timers. + /// @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. + inline void startTimer(const rcTimerLabel label) { if (m_timerEnabled) doStartTimer(label); } + + /// Stops the specified performance 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. + /// @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; } + +protected: + + /// Clears all log entries. + 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. + 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. + virtual void doStartTimer(const rcTimerLabel /*label*/) {} + + /// Stops the specified performance 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. + /// @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; + + /// True if the performance timers are enabled. + bool m_timerEnabled; +}; + +/// Specifies a configuration to use when performing Recast builds. +/// @ingroup recast +struct rcConfig { - unsigned int smin : 15; // Span min height. - unsigned int smax : 15; // Span max height. - unsigned int flags : 2; // Span flags. - rcSpan* next; // Next span in column. + /// The width of the field along the x-axis. [Limit: >= 0] [Units: vx] + int width; + + /// The height of the field along the z-axis. [Limit: >= 0] [Units: vx] + int height; + + /// The width/height size of tile's on the xz-plane. [Limit: >= 0] [Units: vx] + 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] + 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]; + + /// 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] + 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] + int maxVertsPerPoly; + + /// Sets the sampling distance to use when generating the detail mesh. + /// (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] + 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; + +/// The number of spans allocated per span spool. +/// @see rcSpanPool static const int RC_SPANS_PER_POOL = 2048; -// Memory pool used for quick span allocation. +/// Represents a span in a heightfield. +/// @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. +}; + +/// A memory pool used for quick allocation of spans within a heightfield. +/// @see rcHeightfield struct rcSpanPool { - rcSpanPool* next; // Pointer to next pool. - rcSpan items[1]; // Array of spans (size RC_SPANS_PER_POOL). + rcSpanPool* next; ///< The next span pool. + rcSpan items[RC_SPANS_PER_POOL]; ///< Array of spans in the pool. }; -// Dynamic span-heightfield. +/// A dynamic heightfield representing obstructed space. +/// @ingroup recast struct rcHeightfield { - inline rcHeightfield() : width(0), height(0), spans(0), pools(0), freelist(0) {} - inline ~rcHeightfield() - { - // Delete span array. - delete [] spans; - // Delete span pools. - while (pools) - { - rcSpanPool* next = pools->next; - delete [] reinterpret_cast<unsigned char*>(pools); - pools = next; - } - } - int width, height; // Dimension of the heightfield. - float bmin[3], bmax[3]; // Bounding box of the heightfield - float cs, ch; // Cell size and height. - rcSpan** spans; // Heightfield of spans (width*height). - rcSpanPool* pools; // Linked list of span pools. - rcSpan* freelist; // Pointer to next free span. + 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 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. struct rcCompactCell { - unsigned int index : 24; // Index to first span in column. - unsigned int count : 8; // Number of spans in this column. + unsigned int index : 24; ///< Index to the first span in the column. + unsigned int count : 8; ///< Number of spans in the column. }; +/// Represents a span of unobstructed space within a compact heightfield. struct rcCompactSpan { - unsigned short y; // Bottom coordinate of the span. - unsigned short reg; // Region ID - unsigned short dist; // Distance to border - unsigned short con; // Connections to neighbour cells. - unsigned char h; // Height of the span. - unsigned char flags; // Flags. + 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 int con : 24; ///< Packed neighbor connection data. + unsigned int h : 8; ///< The height of the span. (Measured from #y.) }; -// Compact static heightfield. +/// A compact, static heightfield representing unobstructed space. +/// @ingroup recast struct rcCompactHeightfield { - inline rcCompactHeightfield() : maxDistance(0), maxRegions(0), cells(0), spans(0) {} - inline ~rcCompactHeightfield() { delete [] cells; delete [] spans; } - int width, height; // Width and height of the heighfield. - int spanCount; // Number of spans in the heightfield. - int walkableHeight, walkableClimb; // Agent properties. - unsigned short maxDistance; // Maximum distance value stored in heightfield. - unsigned short maxRegions; // Maximum Region Id stored in heightfield. - float bmin[3], bmax[3]; // Bounding box of the heightfield. - float cs, ch; // Cell size and height. - rcCompactCell* cells; // Pointer to width*height cells. - rcCompactSpan* spans; // Pointer to spans. + 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 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)] + 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.) + rcCompactCell* cells; ///< Array of cells. [Size: #width*#height] + rcCompactSpan* spans; ///< Array of spans. [Size: #spanCount] + unsigned short* dist; ///< Array containing border distance data. [Size: #spanCount] + unsigned char* areas; ///< Array containing area id data. [Size: #spanCount] +}; + +/// Represents a heightfield layer within a layer set. +/// @see rcHeightfieldLayerSet +struct rcHeightfieldLayer +{ + 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 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 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 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* 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 +struct rcHeightfieldLayerSet +{ + rcHeightfieldLayer* layers; ///< The layers in the set. [Size: #nlayers] + int nlayers; ///< The number of layers in the set. }; +/// Represents a simple, non-overlapping contour in field space. struct rcContour { - inline rcContour() : verts(0), nverts(0), rverts(0), nrverts(0) { } - inline ~rcContour() { delete [] verts; delete [] rverts; } - int* verts; // Vertex coordinates, each vertex contains 4 components. - int nverts; // Number of vertices. - int* rverts; // Raw vertex coordinates, each vertex contains 4 components. - int nrverts; // Number of raw vertices. - unsigned short reg; // Region ID of the contour. + int* verts; ///< Simplified contour vertex and connection data. [Size: 4 * #nverts] + 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. + unsigned short reg; ///< The region id of the contour. + unsigned char area; ///< The area id of the contour. }; +/// Represents a group of related contours. +/// @ingroup recast struct rcContourSet { - inline rcContourSet() : conts(0), nconts(0) {} - inline ~rcContourSet() { delete [] conts; } - rcContour* conts; // Pointer to all contours. - int nconts; // Number of contours. - float bmin[3], bmax[3]; // Bounding box of the heightfield. - float cs, ch; // Cell size and height. + rcContour* conts; ///< An array of the contours in the set. [Size: #nconts] + int nconts; ///< The number of contours in the set. + float bmin[3]; ///< The minimum bounds in world space. [(x, y, z)] + 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 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. }; -// Polymesh store a connected mesh of polygons. -// The polygons are store in an array where each polygons takes -// 'nvp*2' elements. The first 'nvp' elements are indices to vertices -// and the second 'nvp' elements are indices to neighbour polygons. -// If a polygona has less than 'bvp' vertices, the remaining indices -// are set os 0xffff. If an polygon edge does not have a neighbour -// the neighbour index is set to 0xffff. -// Vertices can be transformed into world space as follows: -// x = bmin[0] + verts[i*3+0]*cs; -// y = bmin[1] + verts[i*3+1]*ch; -// z = bmin[2] + verts[i*3+2]*cs; +/// Represents a polygon mesh suitable for use in building a navigation mesh. +/// @ingroup recast struct rcPolyMesh -{ - inline rcPolyMesh() : verts(0), polys(0), regs(0), nverts(0), npolys(0), nvp(3) {} - inline ~rcPolyMesh() { delete [] verts; delete [] polys; delete [] regs; } - unsigned short* verts; // Vertices of the mesh, 3 elements per vertex. - unsigned short* polys; // Polygons of the mesh, nvp*2 elements per polygon. - unsigned short* regs; // Regions of the polygons. - int nverts; // Number of vertices. - int npolys; // Number of polygons. - int nvp; // Max number of vertices per polygon. - float bmin[3], bmax[3]; // Bounding box of the mesh. - float cs, ch; // Cell size and height. +{ + 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] + unsigned short* flags; ///< The user defined flags for each polygon. [Length: #maxpolys] + unsigned char* areas; ///< The area id assigned to each polygon. [Length: #maxpolys] + int nverts; ///< The number of vertices. + 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 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. }; -// Detail mesh generated from a rcPolyMesh. -// Each submesh represents a polygon in the polymesh and they are stored in -// excatly same order. Each submesh is described as 4 values: -// base vertex, vertex count, base triangle, triangle count. That is, -// const unsigned char* t = &dtl.tris[(tbase+i)*3]; and -// const float* v = &dtl.verts[(vbase+t[j])*3]; -// If the input polygon has 'n' vertices, those vertices are first in the -// submesh vertex list. This allows to compres the mesh by not storing the -// first vertices and using the polymesh vertices instead. - +/// Contains triangle meshes that represent detailed height data associated +/// with the polygons in its associated polygon mesh object. +/// @ingroup recast struct rcPolyMeshDetail { - inline rcPolyMeshDetail() : - meshes(0), verts(0), tris(0), - nmeshes(0), nverts(0), ntris(0) {} - inline ~rcPolyMeshDetail() - { - delete [] meshes; delete [] verts; delete [] tris; - } - - unsigned short* meshes; // Pointer to all mesh data. - float* verts; // Pointer to all vertex data. - unsigned char* tris; // Pointer to all triangle data. - int nmeshes; // Number of meshes. - int nverts; // Number of total vertices. - int ntris; // Number of triangles. + 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 +/// Functions used to allocate and de-allocate Recast objects. +/// @see rcAllocSetCustom +/// @{ -// Simple dynamic array ints. -class rcIntArray -{ - int* m_data; - int m_size, m_cap; -public: - inline rcIntArray() : m_data(0), m_size(0), m_cap(0) {} - inline rcIntArray(int n) : m_data(0), m_size(0), m_cap(n) { m_data = new int[n]; } - inline ~rcIntArray() { delete [] m_data; } - void resize(int n); - inline void push(int item) { resize(m_size+1); m_data[m_size-1] = item; } - inline int pop() { if (m_size > 0) m_size--; return m_data[m_size]; } - inline const int& operator[](int i) const { return m_data[i]; } - inline int& operator[](int i) { return m_data[i]; } - inline int size() const { return m_size; } -}; +/// Allocates a heightfield object using the Recast allocator. +/// @return A heightfield that is ready for initialization, or null on failure. +/// @ingroup recast +/// @see rcCreateHeightfield, rcFreeHeightField +rcHeightfield* rcAllocHeightfield(); -enum rcSpanFlags -{ - RC_WALKABLE = 0x01, - RC_REACHABLE = 0x02, -}; +/// Frees the specified heightfield object using the Recast allocator. +/// @param[in] hf A heightfield allocated using #rcAllocHeightfield +/// @ingroup recast +/// @see rcAllocHeightfield +void rcFreeHeightField(rcHeightfield* hf); + +/// Allocates a compact heightfield object using the Recast allocator. +/// @return A compact heightfield that is ready for initialization, or null on failure. +/// @ingroup recast +/// @see rcBuildCompactHeightfield, rcFreeCompactHeightfield +rcCompactHeightfield* rcAllocCompactHeightfield(); + +/// Frees the specified compact heightfield object using the Recast allocator. +/// @param[in] chf A compact heightfield allocated using #rcAllocCompactHeightfield +/// @ingroup recast +/// @see rcAllocCompactHeightfield +void rcFreeCompactHeightfield(rcCompactHeightfield* chf); + +/// Allocates a heightfield layer set using the Recast allocator. +/// @return A heightfield layer set that is ready for initialization, or null on failure. +/// @ingroup recast +/// @see rcBuildHeightfieldLayers, rcFreeHeightfieldLayerSet +rcHeightfieldLayerSet* rcAllocHeightfieldLayerSet(); + +/// Frees the specified heightfield layer set using the Recast allocator. +/// @param[in] lset A heightfield layer set allocated using #rcAllocHeightfieldLayerSet +/// @ingroup recast +/// @see rcAllocHeightfieldLayerSet +void rcFreeHeightfieldLayerSet(rcHeightfieldLayerSet* lset); + +/// Allocates a contour set object using the Recast allocator. +/// @return A contour set that is ready for initialization, or null on failure. +/// @ingroup recast +/// @see rcBuildContours, rcFreeContourSet +rcContourSet* rcAllocContourSet(); + +/// Frees the specified contour set using the Recast allocator. +/// @param[in] cset A contour set allocated using #rcAllocContourSet +/// @ingroup recast +/// @see rcAllocContourSet +void rcFreeContourSet(rcContourSet* cset); + +/// Allocates a polygon mesh object using the Recast allocator. +/// @return A polygon mesh that is ready for initialization, or null on failure. +/// @ingroup recast +/// @see rcBuildPolyMesh, rcFreePolyMesh +rcPolyMesh* rcAllocPolyMesh(); + +/// Frees the specified polygon mesh using the Recast allocator. +/// @param[in] pmesh A polygon mesh allocated using #rcAllocPolyMesh +/// @ingroup recast +/// @see rcAllocPolyMesh +void rcFreePolyMesh(rcPolyMesh* pmesh); + +/// Allocates a detail mesh object using the Recast allocator. +/// @return A detail mesh that is ready for initialization, or null on failure. +/// @ingroup recast +/// @see rcBuildPolyMeshDetail, rcFreePolyMeshDetail +rcPolyMeshDetail* rcAllocPolyMeshDetail(); + +/// Frees the specified detail mesh using the Recast allocator. +/// @param[in] dmesh A detail mesh allocated using #rcAllocPolyMeshDetail +/// @ingroup recast +/// @see rcAllocPolyMeshDetail +void rcFreePolyMeshDetail(rcPolyMeshDetail* dmesh); -// If heightfield region ID has the following bit set, the region is on border area -// and excluded from many calculations. +/// @} + +/// Heighfield border flag. +/// 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; -// If contour region ID has the following bit set, the vertex will be later -// removed in order to match the segments and vertices at tile boundaries. +/// 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 +/// at tile boundaries. +/// (Used during the build process.) +/// @see rcCompactSpan::reg, #rcContour::verts, #rcContour::rverts static const int RC_BORDER_VERTEX = 0x10000; -// Compact span neighbour helpers. -inline int rcGetCon(const rcCompactSpan& s, int dir) -{ - return (s.con >> (dir*4)) & 0xf; -} +/// Area border flag. +/// If a region ID has this bit set, then the associated element lies on +/// the border of an area. +/// (Used during the region and contour build process.) +/// @see rcCompactSpan::reg, #rcContour::verts, #rcContour::rverts +static const int RC_AREA_BORDER = 0x20000; -inline int rcGetDirOffsetX(int dir) +/// Contour build flags. +/// @see rcBuildContours +enum rcBuildContoursFlags { - const int offset[4] = { -1, 0, 1, 0, }; - return offset[dir&0x03]; -} + RC_CONTOUR_TESS_WALL_EDGES = 0x01, ///< Tessellate solid (impassable) edges during contour simplification. + RC_CONTOUR_TESS_AREA_EDGES = 0x02, ///< Tessellate edges between areas during contour simplification. +}; -inline int rcGetDirOffsetY(int dir) -{ - const int offset[4] = { 0, 1, 0, -1 }; - return offset[dir&0x03]; -} +/// Applied to the region id field of contour vertices in order to extract the region id. +/// The region id field of a vertex may have several flags applied to it. So the +/// fields value can't be used directly. +/// @see rcContour::verts, rcContour::rverts +static const int RC_CONTOUR_REG_MASK = 0xffff; + +/// An value which indicates an invalid index within a mesh. +/// @note This does not necessarily indicate an error. +/// @see rcPolyMesh::polys +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 +/// 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. +static const unsigned char RC_WALKABLE_AREA = 63; + +/// The value returned by #rcGetCon if the specified direction is not connected +/// to another span. (Has no neighbor.) +static const int RC_NOT_CONNECTED = 0x3f; + +/// @name General helper functions +/// @{ -// Common helper functions +/// Swaps the values of the two parameters. +/// @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 +/// @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 +/// @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. +/// @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. +/// @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. +/// @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); } -// Common vector helper functions. -inline void vcross(float* dest, const float* v1, const float* v2) +/// Returns the square root of 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)] +inline void rcVcross(float* dest, const float* v1, const float* v2) { dest[0] = v1[1]*v2[2] - v1[2]*v2[1]; dest[1] = v1[2]*v2[0] - v1[0]*v2[2]; - dest[2] = v1[0]*v2[1] - v1[1]*v2[0]; + dest[2] = v1[0]*v2[1] - v1[1]*v2[0]; } -inline float vdot(const float* v1, const float* v2) +/// 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. +inline float rcVdot(const float* v1, const float* v2) { return v1[0]*v2[0] + v1[1]*v2[1] + v1[2]*v2[2]; } -inline void vmad(float* dest, const float* v1, const float* v2, const float s) +/// 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. +inline void rcVmad(float* dest, const float* v1, const float* v2, const float s) { dest[0] = v1[0]+v2[0]*s; dest[1] = v1[1]+v2[1]*s; dest[2] = v1[2]+v2[2]*s; } -inline void vadd(float* dest, const float* v1, const float* v2) +/// 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)] +inline void rcVadd(float* dest, const float* v1, const float* v2) { dest[0] = v1[0]+v2[0]; dest[1] = v1[1]+v2[1]; dest[2] = v1[2]+v2[2]; } -inline void vsub(float* dest, const float* v1, const float* v2) +/// 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)] +inline void rcVsub(float* dest, const float* v1, const float* v2) { dest[0] = v1[0]-v2[0]; dest[1] = v1[1]-v2[1]; dest[2] = v1[2]-v2[2]; } -inline void vmin(float* mn, const float* v) +/// 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)] +inline void rcVmin(float* mn, const float* v) { mn[0] = rcMin(mn[0], v[0]); mn[1] = rcMin(mn[1], v[1]); mn[2] = rcMin(mn[2], v[2]); } -inline void vmax(float* mx, 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)] +inline void rcVmax(float* mx, const float* v) { mx[0] = rcMax(mx[0], v[0]); mx[1] = rcMax(mx[1], v[1]); mx[2] = rcMax(mx[2], v[2]); } -inline void vcopy(float* dest, 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)] +inline void rcVcopy(float* dest, const float* v) { dest[0] = v[0]; dest[1] = v[1]; dest[2] = v[2]; } -inline float vdist(const float* v1, const float* v2) +/// 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. +inline float rcVdist(const float* v1, const float* v2) { float dx = v2[0] - v1[0]; float dy = v2[1] - v1[1]; float dz = v2[2] - v1[2]; - return sqrtf(dx*dx + dy*dy + dz*dz); + return rcSqrt(dx*dx + dy*dy + dz*dz); } -inline float vdistSqr(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. +inline float rcVdistSqr(const float* v1, const float* v2) { float dx = v2[0] - v1[0]; float dy = v2[1] - v1[1]; @@ -318,184 +705,424 @@ inline float vdistSqr(const float* v1, const float* v2) return dx*dx + dy*dy + dz*dz; } -inline void vnormalize(float* v) +/// Normalizes the vector. +/// @param[in,out] v The vector to normalize. [(x, y, z)] +inline void rcVnormalize(float* v) { - float d = 1.0f / sqrtf(rcSqr(v[0]) + rcSqr(v[1]) + rcSqr(v[2])); + float d = 1.0f / rcSqrt(rcSqr(v[0]) + rcSqr(v[1]) + rcSqr(v[2])); v[0] *= d; v[1] *= d; v[2] *= d; } -inline bool vequal(const float* p0, const float* p1) +/// 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 = vdistSqr(p0, p1); + const float d = rcVdistSqr(p0, p1); return d < thr; } +/// @} +/// @name Heightfield Functions +/// @see rcHeightfield +/// @{ -// Calculated bounding box of array of vertices. -// Params: -// verts - (in) array of vertices -// nv - (in) vertex count -// bmin, bmax - (out) bounding box +/// 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] void rcCalcBounds(const float* verts, int nv, float* bmin, float* bmax); -// Calculates grid size based on bounding box and grid cell size. -// Params: -// bmin, bmax - (in) bounding box -// cs - (in) grid cell size -// w - (out) grid width -// h - (out) grid height +/// 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] void rcCalcGridSize(const float* bmin, const float* bmax, float cs, int* w, int* h); -// Creates and initializes new heightfield. -// Params: -// hf - (in/out) heightfield to initialize. -// width - (in) width of the heightfield. -// height - (in) height of the heightfield. -// bmin, bmax - (in) bounding box of the heightfield -// cs - (in) grid cell size -// ch - (in) grid cell height -bool rcCreateHeightfield(rcHeightfield& hf, int width, int height, +/// 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] +bool rcCreateHeightfield(rcContext* ctx, rcHeightfield& hf, int width, int height, const float* bmin, const float* bmax, float cs, float ch); -// Sets the WALKABLE flag for every triangle whose slope is below -// the maximun walkable slope angle. -// Params: -// walkableSlopeAngle - (in) maximun slope angle in degrees. -// verts - (in) array of vertices -// nv - (in) vertex count -// tris - (in) array of triangle vertex indices -// nt - (in) triangle count -// flags - (out) array of triangle flags -void rcMarkWalkableTriangles(const float walkableSlopeAngle, - const float* verts, int nv, - const int* tris, int nt, - unsigned char* flags); - -// Rasterizes a triangle into heightfield spans. -// Params: -// v0,v1,v2 - (in) the vertices of the triangle. -// flags - (in) triangle flags (uses WALKABLE) -// solid - (in) heighfield where the triangle is rasterized -void rcRasterizeTriangle(const float* v0, const float* v1, const float* v2, - unsigned char flags, rcHeightfield& solid); - -// Rasterizes the triangles into heightfield spans. -// Params: -// verts - (in) array of vertices -// nv - (in) vertex count -// tris - (in) array of triangle vertex indices -// norms - (in) array of triangle normals -// flags - (in) array of triangle flags (uses WALKABLE) -// nt - (in) triangle count -// solid - (in) heighfield where the triangles are rasterized -void rcRasterizeTriangles(const float* verts, int nv, - const int* tris, const unsigned char* flags, int nt, - rcHeightfield& solid); - -// Removes WALKABLE flag from all spans that are at ledges. This filtering -// removes possible overestimation of the conservative voxelization so that -// the resulting mesh will not have regions hanging in air over ledges. -// Params: -// walkableHeight - (in) minimum height where the agent can still walk -// walkableClimb - (in) maximum height between grid cells the agent can climb -// solid - (in/out) heightfield describing the solid space -void rcFilterLedgeSpans(const int walkableHeight, - const int walkableClimb, - rcHeightfield& solid); - -// Removes WALKABLE flag from all spans which have smaller than -// 'walkableHeight' clearane above them. -// Params: -// walkableHeight - (in) minimum height where the agent can still walk -// solid - (in/out) heightfield describing the solid space -void rcFilterWalkableLowHeightSpans(int walkableHeight, - rcHeightfield& solid); - -// Marks spans which are reachable from any of the topmost spans. -// Params: -// walkableHeight - (in) minimum height where the agent can still walk -// walkableClimb - (in) maximum height between grid cells the agent can climb -// solid - (in/out) heightfield describing the solid space -// Returns false if operation ran out of memory. -bool rcMarkReachableSpans(const int walkableHeight, - const int walkableClimb, - rcHeightfield& solid); - -// Builds compact representation of the heightfield. -// Params: -// walkableHeight - (in) minimum height where the agent can still walk -// walkableClimb - (in) maximum height between grid cells the agent can climb -// hf - (in) heightfield to be compacted -// chf - (out) compact heightfield representing the open space. -// Returns false if operation ran out of memory. -bool rcBuildCompactHeightfield(const int walkableHeight, const int walkableClimb, - unsigned char flags, - rcHeightfield& hf, - rcCompactHeightfield& chf); - -// Builds distance field and stores it into the combat heightfield. -// Params: -// chf - (in/out) compact heightfield representing the open space. -// Returns false if operation ran out of memory. -bool rcBuildDistanceField(rcCompactHeightfield& chf); - -// Divides the walkable heighfied into simple regions. -// Each region has only one contour and no overlaps. -// The regions are stored in the compact heightfield 'reg' field. -// The regions will be shrinked by the radius of the agent. -// The process sometimes creates small regions. The parameter -// 'minRegionSize' specifies the smallest allowed regions size. -// If the area of a regions is smaller than allowed, the regions is -// removed or merged to neighbour region. -// Params: -// chf - (in/out) compact heightfield representing the open space. -// walkableRadius - (in) the radius of the agent. -// minRegionSize - (in) the smallest allowed regions size. -// maxMergeRegionSize - (in) the largest allowed regions size which can be merged. -// Returns false if operation ran out of memory. -bool rcBuildRegions(rcCompactHeightfield& chf, - int walkableRadius, int borderSize, - int minRegionSize, int mergeRegionSize); - -// Builds simplified contours from the regions outlines. -// Params: -// chf - (in) compact heightfield which has regions set. -// maxError - (in) maximum allowed distance between simplified countour and cells. -// maxEdgeLen - (in) maximum allowed contour edge length in cells. -// cset - (out) Resulting contour set. -// Returns false if operation ran out of memory. -bool rcBuildContours(rcCompactHeightfield& chf, +/// 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] +void rcMarkWalkableTriangles(rcContext* ctx, const float walkableSlopeAngle, const float* verts, int nv, + 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] +void rcClearUnwalkableTriangles(rcContext* ctx, const float walkableSlopeAngle, const float* verts, int nv, + 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, + 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, + 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, + 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, + 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, + rcHeightfield& solid, const int flagMergeThr = 1); + +/// 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.) +void rcFilterLowHangingWalkableObstacles(rcContext* ctx, const int walkableClimb, rcHeightfield& solid); + +/// 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.) +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. +/// @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.) +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. +/// @returns The number of spans in the heightfield. +int rcGetHeightFieldSpanCount(rcContext* ctx, rcHeightfield& hf); + +/// @} +/// @name Compact Heightfield Functions +/// @see rcCompactHeightfield +/// @{ + +/// 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.) +/// @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. +/// @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. +/// @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. +/// @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) +/// @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. +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. +/// @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. +void rcMarkConvexPolyArea(rcContext* ctx, const float* verts, const int nverts, + const float hmin, const float hmax, unsigned char areaId, + rcCompactHeightfield& chf); + +/// 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. +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. +/// @ingroup recast +/// @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. +/// @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 rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf, + const int borderSize, const int minRegionArea, const int mergeRegionArea); + +/// 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] +/// @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. +inline void rcSetCon(rcCompactSpan& s, int dir, int i) +{ + const unsigned int shift = (unsigned int)dir*6; + unsigned int con = s.con; + s.con = (con & ~(0x3f << shift)) | (((unsigned int)i & 0x3f) << shift); +} + +/// 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] +/// @return The neighbor connection data for the specified direction, +/// 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; + return (s.con >> shift) & 0x3f; +} + +/// Gets the standard width (x-axis) offset for the specified direction. +/// @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. +inline int rcGetDirOffsetX(int dir) +{ + 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] +/// @return The height offset to apply to the current cell position to move +/// in the direction. +inline int rcGetDirOffsetY(int dir) +{ + const int offset[4] = { 0, 1, 0, -1 }; + return offset[dir&0x03]; +} + +/// @} +/// @name Layer, Contour, Polymesh, and Detail Mesh Functions +/// @see rcHeightfieldLayer, rcContourSet, rcPolyMesh, rcPolyMeshDetail +/// @{ + +/// 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.) +/// @returns True if the operation completed successfully. +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) +/// @returns True if the operation completed successfully. +bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, const float maxError, const int maxEdgeLen, - rcContourSet& cset); - -// Builds connected convex polygon mesh from contour polygons. -// Params: -// cset - (in) contour set. -// nvp - (in) maximum number of vertices per polygon. -// mesh - (out) poly mesh. -// Returns false if operation ran out of memory. -bool rcBuildPolyMesh(rcContourSet& cset, int nvp, rcPolyMesh& mesh); - -bool rcMergePolyMeshes(rcPolyMesh** meshes, const int nmeshes, rcPolyMesh& mesh); - -// Builds detail triangle mesh for each polygon in the poly mesh. -// Params: -// mesh - (in) poly mesh to detail. -// chf - (in) compacy height field, used to query height for new vertices. -// sampleDist - (in) spacing between height samples used to generate more detail into mesh. -// sampleMaxError - (in) maximum allowed distance between simplified detail mesh and height sample. -// pmdtl - (out) detail mesh. -// Returns false if operation ran out of memory. -bool rcBuildPolyMeshDetail(const rcPolyMesh& mesh, const rcCompactHeightfield& chf, + rcContourSet& cset, const int flags = 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.) +/// @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.) +/// @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.) +/// @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); -bool rcMergePolyMeshDetails(rcPolyMeshDetail** meshes, const int nmeshes, rcPolyMeshDetail& mesh); +/// 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.) +/// @returns True if the operation completed successfully. +bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int nmeshes, rcPolyMeshDetail& mesh); bool buildMeshAdjacency(unsigned short* polys, const int npolys, const int nverts, const int vertsPerPoly); +/// @} + #endif // RECAST_H + +/////////////////////////////////////////////////////////////////////////// + +// 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. |