diff options
Diffstat (limited to 'dep/recastnavigation/Recast/Recast.h')
| -rw-r--r-- | dep/recastnavigation/Recast/Recast.h | 280 |
1 files changed, 64 insertions, 216 deletions
diff --git a/dep/recastnavigation/Recast/Recast.h b/dep/recastnavigation/Recast/Recast.h index fb36aa4c5cf..57e98ea444a 100644 --- a/dep/recastnavigation/Recast/Recast.h +++ b/dep/recastnavigation/Recast/Recast.h @@ -65,8 +65,6 @@ enum rcTimerLabel 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) @@ -85,8 +83,6 @@ enum rcTimerLabel 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) @@ -284,6 +280,9 @@ struct rcHeightfield rcSpan* freelist; ///< The next free span. }; +rcHeightfield* rcAllocHeightfield(); +void rcFreeHeightField(rcHeightfield* hf); + /// Provides information on the content of a cell column in a compact heightfield. struct rcCompactCell { @@ -309,7 +308,6 @@ struct rcCompactHeightfield 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)] @@ -322,35 +320,9 @@ struct rcCompactHeightfield 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] -}; +rcCompactHeightfield* rcAllocCompactHeightfield(); +void rcFreeCompactHeightfield(rcCompactHeightfield* chf); -/// 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 @@ -373,11 +345,12 @@ struct rcContourSet 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. }; +rcContourSet* rcAllocContourSet(); +void rcFreeContourSet(rcContourSet* cset); + + /// Represents a polygon mesh suitable for use in building a navigation mesh. /// @ingroup recast struct rcPolyMesh @@ -395,9 +368,12 @@ struct rcPolyMesh 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. }; +rcPolyMesh* rcAllocPolyMesh(); +void rcFreePolyMesh(rcPolyMesh* pmesh); + + /// Contains triangle meshes that represent detailed height data associated /// with the polygons in its associated polygon mesh object. /// @ingroup recast @@ -411,71 +387,6 @@ struct rcPolyMeshDetail int ntris; ///< The number of triangles in #tris. }; -/// @name Allocation Functions -/// Functions used to allocate and de-allocate Recast objects. -/// @see rcAllocSetCustom -/// @{ - -/// 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(); - -/// 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 @@ -546,6 +457,32 @@ static const unsigned char RC_WALKABLE_AREA = 63; /// to another span. (Has no neighbor.) static const int RC_NOT_CONNECTED = 0x3f; +// Compact span neighbour helpers. +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); +} + +inline int rcGetCon(const rcCompactSpan& s, int dir) +{ + const unsigned int shift = (unsigned int)dir*6; + return (s.con >> shift) & 0x3f; +} + +inline int rcGetDirOffsetX(int dir) +{ + const int offset[4] = { -1, 0, 1, 0, }; + return offset[dir&0x03]; +} + +inline int rcGetDirOffsetY(int dir) +{ + const int offset[4] = { 0, 1, 0, -1 }; + return offset[dir&0x03]; +} + /// @name General helper functions /// @{ @@ -710,6 +647,13 @@ inline void rcVnormalize(float* v) v[2] *= d; } +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 @@ -774,20 +718,18 @@ void rcClearUnwalkableTriangles(rcContext* ctx, const float walkableSlopeAngle, 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, +// The span addition can set to favor flags. If the span is merged to +// another span and the new smax is within 'flagMergeThr' units away +// from the existing span the span flags are merged and stored. +// Params: +// solid - (in) heightfield where the spans is added to +// x,y - (in) location on the heightfield where the span is added +// smin,smax - (in) spans min/max height +// flags - (in) span flags (zero or WALKABLE) +// flagMergeThr - (in) merge threshold. +void rcAddSpan(rcContext* ctx, rcHeightfield& solid, const int x, const int y, const unsigned short smin, const unsigned short smax, - const unsigned char area, const int flagMergeThr); + const unsigned short area, const int flagMergeThr); /// Rasterizes a triangle into the specified heightfield. /// @ingroup recast @@ -935,28 +877,6 @@ 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. -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. @@ -992,68 +912,6 @@ bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf, 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. @@ -1069,15 +927,13 @@ bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, const float maxError, const int maxEdgeLen, 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); +// 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(rcContext* ctx, rcContourSet& cset, int nvp, rcPolyMesh& mesh); /// Merges multiple polygon meshes into a single mesh. /// @ingroup recast @@ -1102,14 +958,6 @@ bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompa 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. |