1//
2// Copyright (c) 2009-2010 Mikko Mononen memon@inside.org
3//
4// This software is provided 'as-is', without any express or implied
5// warranty. In no event will the authors be held liable for any damages
6// arising from the use of this software.
7// Permission is granted to anyone to use this software for any purpose,
8// including commercial applications, and to alter it and redistribute it
9// freely, subject to the following restrictions:
10// 1. The origin of this software must not be misrepresented; you must not
11// claim that you wrote the original software. If you use this software
12// in a product, an acknowledgment in the product documentation would be
13// appreciated but is not required.
14// 2. Altered source versions must be plainly marked as such, and must not be
15// misrepresented as being the original software.
16// 3. This notice may not be removed or altered from any source distribution.
17//
18
19#ifndef RECAST_H
20#define RECAST_H
21
22/// The value of PI used by Recast.
23static const float RC_PI = 3.14159265f;
24
25/// Used to ignore unused function parameters and silence any compiler warnings.
26template<class T> void rcIgnoreUnused(const T&) { }
27
28/// Recast log categories.
29/// @see rcContext
30enum rcLogCategory
31{
32 RC_LOG_PROGRESS = 1, ///< A progress log entry.
33 RC_LOG_WARNING, ///< A warning log entry.
34 RC_LOG_ERROR ///< An error log entry.
35};
36
37/// Recast performance timer categories.
38/// @see rcContext
39enum rcTimerLabel
40{
41 /// The user defined total time of the build.
42 RC_TIMER_TOTAL,
43 /// A user defined build time.
44 RC_TIMER_TEMP,
45 /// The time to rasterize the triangles. (See: #rcRasterizeTriangle)
46 RC_TIMER_RASTERIZE_TRIANGLES,
47 /// The time to build the compact heightfield. (See: #rcBuildCompactHeightfield)
48 RC_TIMER_BUILD_COMPACTHEIGHTFIELD,
49 /// The total time to build the contours. (See: #rcBuildContours)
50 RC_TIMER_BUILD_CONTOURS,
51 /// The time to trace the boundaries of the contours. (See: #rcBuildContours)
52 RC_TIMER_BUILD_CONTOURS_TRACE,
53 /// The time to simplify the contours. (See: #rcBuildContours)
54 RC_TIMER_BUILD_CONTOURS_SIMPLIFY,
55 /// The time to filter ledge spans. (See: #rcFilterLedgeSpans)
56 RC_TIMER_FILTER_BORDER,
57 /// The time to filter low height spans. (See: #rcFilterWalkableLowHeightSpans)
58 RC_TIMER_FILTER_WALKABLE,
59 /// The time to apply the median filter. (See: #rcMedianFilterWalkableArea)
60 RC_TIMER_MEDIAN_AREA,
61 /// The time to filter low obstacles. (See: #rcFilterLowHangingWalkableObstacles)
62 RC_TIMER_FILTER_LOW_OBSTACLES,
63 /// The time to build the polygon mesh. (See: #rcBuildPolyMesh)
64 RC_TIMER_BUILD_POLYMESH,
65 /// The time to merge polygon meshes. (See: #rcMergePolyMeshes)
66 RC_TIMER_MERGE_POLYMESH,
67 /// The time to erode the walkable area. (See: #rcErodeWalkableArea)
68 RC_TIMER_ERODE_AREA,
69 /// The time to mark a box area. (See: #rcMarkBoxArea)
70 RC_TIMER_MARK_BOX_AREA,
71 /// The time to mark a cylinder area. (See: #rcMarkCylinderArea)
72 RC_TIMER_MARK_CYLINDER_AREA,
73 /// The time to mark a convex polygon area. (See: #rcMarkConvexPolyArea)
74 RC_TIMER_MARK_CONVEXPOLY_AREA,
75 /// The total time to build the distance field. (See: #rcBuildDistanceField)
76 RC_TIMER_BUILD_DISTANCEFIELD,
77 /// The time to build the distances of the distance field. (See: #rcBuildDistanceField)
78 RC_TIMER_BUILD_DISTANCEFIELD_DIST,
79 /// The time to blur the distance field. (See: #rcBuildDistanceField)
80 RC_TIMER_BUILD_DISTANCEFIELD_BLUR,
81 /// The total time to build the regions. (See: #rcBuildRegions, #rcBuildRegionsMonotone)
82 RC_TIMER_BUILD_REGIONS,
83 /// The total time to apply the watershed algorithm. (See: #rcBuildRegions)
84 RC_TIMER_BUILD_REGIONS_WATERSHED,
85 /// The time to expand regions while applying the watershed algorithm. (See: #rcBuildRegions)
86 RC_TIMER_BUILD_REGIONS_EXPAND,
87 /// The time to flood regions while applying the watershed algorithm. (See: #rcBuildRegions)
88 RC_TIMER_BUILD_REGIONS_FLOOD,
89 /// The time to filter out small regions. (See: #rcBuildRegions, #rcBuildRegionsMonotone)
90 RC_TIMER_BUILD_REGIONS_FILTER,
91 /// The time to build heightfield layers. (See: #rcBuildHeightfieldLayers)
92 RC_TIMER_BUILD_LAYERS,
93 /// The time to build the polygon mesh detail. (See: #rcBuildPolyMeshDetail)
94 RC_TIMER_BUILD_POLYMESHDETAIL,
95 /// The time to merge polygon mesh details. (See: #rcMergePolyMeshDetails)
96 RC_TIMER_MERGE_POLYMESHDETAIL,
97 /// The maximum number of timers. (Used for iterating timers.)
98 RC_MAX_TIMERS
99};
100
101/// Provides an interface for optional logging and performance tracking of the Recast
102/// build process.
103///
104/// This class does not provide logging or timer functionality on its
105/// own. Both must be provided by a concrete implementation
106/// by overriding the protected member functions. Also, this class does not
107/// provide an interface for extracting log messages. (Only adding them.)
108/// So concrete implementations must provide one.
109///
110/// If no logging or timers are required, just pass an instance of this
111/// class through the Recast build process.
112///
113/// @ingroup recast
114class rcContext
115{
116public:
117 /// Constructor.
118 /// @param[in] state TRUE if the logging and performance timers should be enabled. [Default: true]
119 inline rcContext(bool state = true) : m_logEnabled(state), m_timerEnabled(state) {}
120 virtual ~rcContext() {}
121
122 /// Enables or disables logging.
123 /// @param[in] state TRUE if logging should be enabled.
124 inline void enableLog(bool state) { m_logEnabled = state; }
125
126 /// Clears all log entries.
127 inline void resetLog() { if (m_logEnabled) doResetLog(); }
128
129 /// Logs a message.
130 ///
131 /// Example:
132 /// @code
133 /// // Where ctx is an instance of rcContext and filepath is a char array.
134 /// ctx->log(RC_LOG_ERROR, "buildTiledNavigation: Could not load '%s'", filepath);
135 /// @endcode
136 ///
137 /// @param[in] category The category of the message.
138 /// @param[in] format The message.
139 void log(const rcLogCategory category, const char* format, ...);
140
141 /// Enables or disables the performance timers.
142 /// @param[in] state TRUE if timers should be enabled.
143 inline void enableTimer(bool state) { m_timerEnabled = state; }
144
145 /// Clears all performance timers. (Resets all to unused.)
146 inline void resetTimers() { if (m_timerEnabled) doResetTimers(); }
147
148 /// Starts the specified performance timer.
149 /// @param label The category of the timer.
150 inline void startTimer(const rcTimerLabel label) { if (m_timerEnabled) doStartTimer(label); }
151
152 /// Stops the specified performance timer.
153 /// @param label The category of the timer.
154 inline void stopTimer(const rcTimerLabel label) { if (m_timerEnabled) doStopTimer(label); }
155
156 /// Returns the total accumulated time of the specified performance timer.
157 /// @param label The category of the timer.
158 /// @return The accumulated time of the timer, or -1 if timers are disabled or the timer has never been started.
159 inline int getAccumulatedTime(const rcTimerLabel label) const { return m_timerEnabled ? doGetAccumulatedTime(label) : -1; }
160
161protected:
162 /// Clears all log entries.
163 virtual void doResetLog();
164
165 /// Logs a message.
166 /// @param[in] category The category of the message.
167 /// @param[in] msg The formatted message.
168 /// @param[in] len The length of the formatted message.
169 virtual void doLog(const rcLogCategory category, const char* msg, const int len) { rcIgnoreUnused(category); rcIgnoreUnused(msg); rcIgnoreUnused(len); }
170
171 /// Clears all timers. (Resets all to unused.)
172 virtual void doResetTimers() {}
173
174 /// Starts the specified performance timer.
175 /// @param[in] label The category of timer.
176 virtual void doStartTimer(const rcTimerLabel label) { rcIgnoreUnused(label); }
177
178 /// Stops the specified performance timer.
179 /// @param[in] label The category of the timer.
180 virtual void doStopTimer(const rcTimerLabel label) { rcIgnoreUnused(label); }
181
182 /// Returns the total accumulated time of the specified performance timer.
183 /// @param[in] label The category of the timer.
184 /// @return The accumulated time of the timer, or -1 if timers are disabled or the timer has never been started.
185 virtual int doGetAccumulatedTime(const rcTimerLabel label) const { rcIgnoreUnused(label); return -1; }
186
187 /// True if logging is enabled.
188 bool m_logEnabled;
189
190 /// True if the performance timers are enabled.
191 bool m_timerEnabled;
192};
193
194/// A helper to first start a timer and then stop it when this helper goes out of scope.
195/// @see rcContext
196class rcScopedTimer
197{
198public:
199 /// Constructs an instance and starts the timer.
200 /// @param[in] ctx The context to use.
201 /// @param[in] label The category of the timer.
202 inline rcScopedTimer(rcContext* ctx, const rcTimerLabel label) : m_ctx(ctx), m_label(label) { m_ctx->startTimer(m_label); }
203 inline ~rcScopedTimer() { m_ctx->stopTimer(m_label); }
204
205private:
206 // Explicitly disabled copy constructor and copy assignment operator.
207 rcScopedTimer(const rcScopedTimer&);
208 rcScopedTimer& operator=(const rcScopedTimer&);
209
210 rcContext* const m_ctx;
211 const rcTimerLabel m_label;
212};
213
214/// Specifies a configuration to use when performing Recast builds.
215/// @ingroup recast
216struct rcConfig
217{
218 /// The width of the field along the x-axis. [Limit: >= 0] [Units: vx]
219 int width;
220
221 /// The height of the field along the z-axis. [Limit: >= 0] [Units: vx]
222 int height;
223
224 /// The width/height size of tile's on the xz-plane. [Limit: >= 0] [Units: vx]
225 int tileSize;
226
227 /// The size of the non-navigable border around the heightfield. [Limit: >=0] [Units: vx]
228 int borderSize;
229
230 /// The xz-plane cell size to use for fields. [Limit: > 0] [Units: wu]
231 float cs;
232
233 /// The y-axis cell size to use for fields. [Limit: > 0] [Units: wu]
234 float ch;
235
236 /// The minimum bounds of the field's AABB. [(x, y, z)] [Units: wu]
237 float bmin[3];
238
239 /// The maximum bounds of the field's AABB. [(x, y, z)] [Units: wu]
240 float bmax[3];
241
242 /// The maximum slope that is considered walkable. [Limits: 0 <= value < 90] [Units: Degrees]
243 float walkableSlopeAngle;
244
245 /// Minimum floor to 'ceiling' height that will still allow the floor area to
246 /// be considered walkable. [Limit: >= 3] [Units: vx]
247 int walkableHeight;
248
249 /// Maximum ledge height that is considered to still be traversable. [Limit: >=0] [Units: vx]
250 int walkableClimb;
251
252 /// The distance to erode/shrink the walkable area of the heightfield away from
253 /// obstructions. [Limit: >=0] [Units: vx]
254 int walkableRadius;
255
256 /// The maximum allowed length for contour edges along the border of the mesh. [Limit: >=0] [Units: vx]
257 int maxEdgeLen;
258
259 /// The maximum distance a simplified contour's border edges should deviate
260 /// the original raw contour. [Limit: >=0] [Units: vx]
261 float maxSimplificationError;
262
263 /// The minimum number of cells allowed to form isolated island areas. [Limit: >=0] [Units: vx]
264 int minRegionArea;
265
266 /// Any regions with a span count smaller than this value will, if possible,
267 /// be merged with larger regions. [Limit: >=0] [Units: vx]
268 int mergeRegionArea;
269
270 /// The maximum number of vertices allowed for polygons generated during the
271 /// contour to polygon conversion process. [Limit: >= 3]
272 int maxVertsPerPoly;
273
274 /// Sets the sampling distance to use when generating the detail mesh.
275 /// (For height detail only.) [Limits: 0 or >= 0.9] [Units: wu]
276 float detailSampleDist;
277
278 /// The maximum distance the detail mesh surface should deviate from heightfield
279 /// data. (For height detail only.) [Limit: >=0] [Units: wu]
280 float detailSampleMaxError;
281};
282
283/// Defines the number of bits allocated to rcSpan::smin and rcSpan::smax.
284static const int RC_SPAN_HEIGHT_BITS = 13;
285/// Defines the maximum value for rcSpan::smin and rcSpan::smax.
286static const int RC_SPAN_MAX_HEIGHT = (1 << RC_SPAN_HEIGHT_BITS) - 1;
287
288/// The number of spans allocated per span spool.
289/// @see rcSpanPool
290static const int RC_SPANS_PER_POOL = 2048;
291
292/// Represents a span in a heightfield.
293/// @see rcHeightfield
294struct rcSpan
295{
296 unsigned int smin : RC_SPAN_HEIGHT_BITS; ///< The lower limit of the span. [Limit: < #smax]
297 unsigned int smax : RC_SPAN_HEIGHT_BITS; ///< The upper limit of the span. [Limit: <= #RC_SPAN_MAX_HEIGHT]
298 unsigned int area : 6; ///< The area id assigned to the span.
299 rcSpan* next; ///< The next span higher up in column.
300};
301
302/// A memory pool used for quick allocation of spans within a heightfield.
303/// @see rcHeightfield
304struct rcSpanPool
305{
306 rcSpanPool* next; ///< The next span pool.
307 rcSpan items[RC_SPANS_PER_POOL]; ///< Array of spans in the pool.
308};
309
310/// A dynamic heightfield representing obstructed space.
311/// @ingroup recast
312struct rcHeightfield
313{
314 rcHeightfield();
315 ~rcHeightfield();
316
317 int width; ///< The width of the heightfield. (Along the x-axis in cell units.)
318 int height; ///< The height of the heightfield. (Along the z-axis in cell units.)
319 float bmin[3]; ///< The minimum bounds in world space. [(x, y, z)]
320 float bmax[3]; ///< The maximum bounds in world space. [(x, y, z)]
321 float cs; ///< The size of each cell. (On the xz-plane.)
322 float ch; ///< The height of each cell. (The minimum increment along the y-axis.)
323 rcSpan** spans; ///< Heightfield of spans (width*height).
324 rcSpanPool* pools; ///< Linked list of span pools.
325 rcSpan* freelist; ///< The next free span.
326
327private:
328 // Explicitly-disabled copy constructor and copy assignment operator.
329 rcHeightfield(const rcHeightfield&);
330 rcHeightfield& operator=(const rcHeightfield&);
331};
332
333/// Provides information on the content of a cell column in a compact heightfield.
334struct rcCompactCell
335{
336 unsigned int index : 24; ///< Index to the first span in the column.
337 unsigned int count : 8; ///< Number of spans in the column.
338};
339
340/// Represents a span of unobstructed space within a compact heightfield.
341struct rcCompactSpan
342{
343 unsigned short y; ///< The lower extent of the span. (Measured from the heightfield's base.)
344 unsigned short reg; ///< The id of the region the span belongs to. (Or zero if not in a region.)
345 unsigned int con : 24; ///< Packed neighbor connection data.
346 unsigned int h : 8; ///< The height of the span. (Measured from #y.)
347};
348
349/// A compact, static heightfield representing unobstructed space.
350/// @ingroup recast
351struct rcCompactHeightfield
352{
353 rcCompactHeightfield();
354 ~rcCompactHeightfield();
355
356 int width; ///< The width of the heightfield. (Along the x-axis in cell units.)
357 int height; ///< The height of the heightfield. (Along the z-axis in cell units.)
358 int spanCount; ///< The number of spans in the heightfield.
359 int walkableHeight; ///< The walkable height used during the build of the field. (See: rcConfig::walkableHeight)
360 int walkableClimb; ///< The walkable climb used during the build of the field. (See: rcConfig::walkableClimb)
361 int borderSize; ///< The AABB border size used during the build of the field. (See: rcConfig::borderSize)
362 unsigned short maxDistance; ///< The maximum distance value of any span within the field.
363 unsigned short maxRegions; ///< The maximum region id of any span within the field.
364 float bmin[3]; ///< The minimum bounds in world space. [(x, y, z)]
365 float bmax[3]; ///< The maximum bounds in world space. [(x, y, z)]
366 float cs; ///< The size of each cell. (On the xz-plane.)
367 float ch; ///< The height of each cell. (The minimum increment along the y-axis.)
368 rcCompactCell* cells; ///< Array of cells. [Size: #width*#height]
369 rcCompactSpan* spans; ///< Array of spans. [Size: #spanCount]
370 unsigned short* dist; ///< Array containing border distance data. [Size: #spanCount]
371 unsigned char* areas; ///< Array containing area id data. [Size: #spanCount]
372
373private:
374 // Explicitly-disabled copy constructor and copy assignment operator.
375 rcCompactHeightfield(const rcCompactHeightfield&);
376 rcCompactHeightfield& operator=(const rcCompactHeightfield&);
377};
378
379/// Represents a heightfield layer within a layer set.
380/// @see rcHeightfieldLayerSet
381struct rcHeightfieldLayer
382{
383 float bmin[3]; ///< The minimum bounds in world space. [(x, y, z)]
384 float bmax[3]; ///< The maximum bounds in world space. [(x, y, z)]
385 float cs; ///< The size of each cell. (On the xz-plane.)
386 float ch; ///< The height of each cell. (The minimum increment along the y-axis.)
387 int width; ///< The width of the heightfield. (Along the x-axis in cell units.)
388 int height; ///< The height of the heightfield. (Along the z-axis in cell units.)
389 int minx; ///< The minimum x-bounds of usable data.
390 int maxx; ///< The maximum x-bounds of usable data.
391 int miny; ///< The minimum y-bounds of usable data. (Along the z-axis.)
392 int maxy; ///< The maximum y-bounds of usable data. (Along the z-axis.)
393 int hmin; ///< The minimum height bounds of usable data. (Along the y-axis.)
394 int hmax; ///< The maximum height bounds of usable data. (Along the y-axis.)
395 unsigned char* heights; ///< The heightfield. [Size: width * height]
396 unsigned char* areas; ///< Area ids. [Size: Same as #heights]
397 unsigned char* cons; ///< Packed neighbor connection information. [Size: Same as #heights]
398};
399
400/// Represents a set of heightfield layers.
401/// @ingroup recast
402/// @see rcAllocHeightfieldLayerSet, rcFreeHeightfieldLayerSet
403struct rcHeightfieldLayerSet
404{
405 rcHeightfieldLayerSet();
406 ~rcHeightfieldLayerSet();
407
408 rcHeightfieldLayer* layers; ///< The layers in the set. [Size: #nlayers]
409 int nlayers; ///< The number of layers in the set.
410
411private:
412 // Explicitly-disabled copy constructor and copy assignment operator.
413 rcHeightfieldLayerSet(const rcHeightfieldLayerSet&);
414 rcHeightfieldLayerSet& operator=(const rcHeightfieldLayerSet&);
415};
416
417/// Represents a simple, non-overlapping contour in field space.
418struct rcContour
419{
420 int* verts; ///< Simplified contour vertex and connection data. [Size: 4 * #nverts]
421 int nverts; ///< The number of vertices in the simplified contour.
422 int* rverts; ///< Raw contour vertex and connection data. [Size: 4 * #nrverts]
423 int nrverts; ///< The number of vertices in the raw contour.
424 unsigned short reg; ///< The region id of the contour.
425 unsigned char area; ///< The area id of the contour.
426};
427
428/// Represents a group of related contours.
429/// @ingroup recast
430struct rcContourSet
431{
432 rcContourSet();
433 ~rcContourSet();
434
435 rcContour* conts; ///< An array of the contours in the set. [Size: #nconts]
436 int nconts; ///< The number of contours in the set.
437 float bmin[3]; ///< The minimum bounds in world space. [(x, y, z)]
438 float bmax[3]; ///< The maximum bounds in world space. [(x, y, z)]
439 float cs; ///< The size of each cell. (On the xz-plane.)
440 float ch; ///< The height of each cell. (The minimum increment along the y-axis.)
441 int width; ///< The width of the set. (Along the x-axis in cell units.)
442 int height; ///< The height of the set. (Along the z-axis in cell units.)
443 int borderSize; ///< The AABB border size used to generate the source data from which the contours were derived.
444 float maxError; ///< The max edge error that this contour set was simplified with.
445
446private:
447 // Explicitly-disabled copy constructor and copy assignment operator.
448 rcContourSet(const rcContourSet&);
449 rcContourSet& operator=(const rcContourSet&);
450};
451
452/// Represents a polygon mesh suitable for use in building a navigation mesh.
453/// @ingroup recast
454struct rcPolyMesh
455{
456 rcPolyMesh();
457 ~rcPolyMesh();
458
459 unsigned short* verts; ///< The mesh vertices. [Form: (x, y, z) * #nverts]
460 unsigned short* polys; ///< Polygon and neighbor data. [Length: #maxpolys * 2 * #nvp]
461 unsigned short* regs; ///< The region id assigned to each polygon. [Length: #maxpolys]
462 unsigned short* flags; ///< The user defined flags for each polygon. [Length: #maxpolys]
463 unsigned char* areas; ///< The area id assigned to each polygon. [Length: #maxpolys]
464 int nverts; ///< The number of vertices.
465 int npolys; ///< The number of polygons.
466 int maxpolys; ///< The number of allocated polygons.
467 int nvp; ///< The maximum number of vertices per polygon.
468 float bmin[3]; ///< The minimum bounds in world space. [(x, y, z)]
469 float bmax[3]; ///< The maximum bounds in world space. [(x, y, z)]
470 float cs; ///< The size of each cell. (On the xz-plane.)
471 float ch; ///< The height of each cell. (The minimum increment along the y-axis.)
472 int borderSize; ///< The AABB border size used to generate the source data from which the mesh was derived.
473 float maxEdgeError; ///< The max error of the polygon edges in the mesh.
474
475private:
476 // Explicitly-disabled copy constructor and copy assignment operator.
477 rcPolyMesh(const rcPolyMesh&);
478 rcPolyMesh& operator=(const rcPolyMesh&);
479};
480
481/// Contains triangle meshes that represent detailed height data associated
482/// with the polygons in its associated polygon mesh object.
483/// @ingroup recast
484struct rcPolyMeshDetail
485{
486 rcPolyMeshDetail();
487
488 unsigned int* meshes; ///< The sub-mesh data. [Size: 4*#nmeshes]
489 float* verts; ///< The mesh vertices. [Size: 3*#nverts]
490 unsigned char* tris; ///< The mesh triangles. [Size: 4*#ntris]
491 int nmeshes; ///< The number of sub-meshes defined by #meshes.
492 int nverts; ///< The number of vertices in #verts.
493 int ntris; ///< The number of triangles in #tris.
494
495private:
496 // Explicitly-disabled copy constructor and copy assignment operator.
497 rcPolyMeshDetail(const rcPolyMeshDetail&);
498 rcPolyMeshDetail& operator=(const rcPolyMeshDetail&);
499};
500
501/// @name Allocation Functions
502/// Functions used to allocate and de-allocate Recast objects.
503/// @see rcAllocSetCustom
504/// @{
505
506/// Allocates a heightfield object using the Recast allocator.
507/// @return A heightfield that is ready for initialization, or null on failure.
508/// @ingroup recast
509/// @see rcCreateHeightfield, rcFreeHeightField
510rcHeightfield* rcAllocHeightfield();
511
512/// Frees the specified heightfield object using the Recast allocator.
513/// @param[in] heightfield A heightfield allocated using #rcAllocHeightfield
514/// @ingroup recast
515/// @see rcAllocHeightfield
516void rcFreeHeightField(rcHeightfield* heightfield);
517
518/// Allocates a compact heightfield object using the Recast allocator.
519/// @return A compact heightfield that is ready for initialization, or null on failure.
520/// @ingroup recast
521/// @see rcBuildCompactHeightfield, rcFreeCompactHeightfield
522rcCompactHeightfield* rcAllocCompactHeightfield();
523
524/// Frees the specified compact heightfield object using the Recast allocator.
525/// @param[in] compactHeightfield A compact heightfield allocated using #rcAllocCompactHeightfield
526/// @ingroup recast
527/// @see rcAllocCompactHeightfield
528void rcFreeCompactHeightfield(rcCompactHeightfield* compactHeightfield);
529
530/// Allocates a heightfield layer set using the Recast allocator.
531/// @return A heightfield layer set that is ready for initialization, or null on failure.
532/// @ingroup recast
533/// @see rcBuildHeightfieldLayers, rcFreeHeightfieldLayerSet
534rcHeightfieldLayerSet* rcAllocHeightfieldLayerSet();
535
536/// Frees the specified heightfield layer set using the Recast allocator.
537/// @param[in] layerSet A heightfield layer set allocated using #rcAllocHeightfieldLayerSet
538/// @ingroup recast
539/// @see rcAllocHeightfieldLayerSet
540void rcFreeHeightfieldLayerSet(rcHeightfieldLayerSet* layerSet);
541
542/// Allocates a contour set object using the Recast allocator.
543/// @return A contour set that is ready for initialization, or null on failure.
544/// @ingroup recast
545/// @see rcBuildContours, rcFreeContourSet
546rcContourSet* rcAllocContourSet();
547
548/// Frees the specified contour set using the Recast allocator.
549/// @param[in] contourSet A contour set allocated using #rcAllocContourSet
550/// @ingroup recast
551/// @see rcAllocContourSet
552void rcFreeContourSet(rcContourSet* contourSet);
553
554/// Allocates a polygon mesh object using the Recast allocator.
555/// @return A polygon mesh that is ready for initialization, or null on failure.
556/// @ingroup recast
557/// @see rcBuildPolyMesh, rcFreePolyMesh
558rcPolyMesh* rcAllocPolyMesh();
559
560/// Frees the specified polygon mesh using the Recast allocator.
561/// @param[in] polyMesh A polygon mesh allocated using #rcAllocPolyMesh
562/// @ingroup recast
563/// @see rcAllocPolyMesh
564void rcFreePolyMesh(rcPolyMesh* polyMesh);
565
566/// Allocates a detail mesh object using the Recast allocator.
567/// @return A detail mesh that is ready for initialization, or null on failure.
568/// @ingroup recast
569/// @see rcBuildPolyMeshDetail, rcFreePolyMeshDetail
570rcPolyMeshDetail* rcAllocPolyMeshDetail();
571
572/// Frees the specified detail mesh using the Recast allocator.
573/// @param[in] detailMesh A detail mesh allocated using #rcAllocPolyMeshDetail
574/// @ingroup recast
575/// @see rcAllocPolyMeshDetail
576void rcFreePolyMeshDetail(rcPolyMeshDetail* detailMesh);
577
578/// @}
579
580/// Heightfield border flag.
581/// If a heightfield region ID has this bit set, then the region is a border
582/// region and its spans are considered un-walkable.
583/// (Used during the region and contour build process.)
584/// @see rcCompactSpan::reg
585static const unsigned short RC_BORDER_REG = 0x8000;
586
587/// Polygon touches multiple regions.
588/// If a polygon has this region ID it was merged with or created
589/// from polygons of different regions during the polymesh
590/// build step that removes redundant border vertices.
591/// (Used during the polymesh and detail polymesh build processes)
592/// @see rcPolyMesh::regs
593static const unsigned short RC_MULTIPLE_REGS = 0;
594
595/// Border vertex flag.
596/// If a region ID has this bit set, then the associated element lies on
597/// a tile border. If a contour vertex's region ID has this bit set, the
598/// vertex will later be removed in order to match the segments and vertices
599/// at tile boundaries.
600/// (Used during the build process.)
601/// @see rcCompactSpan::reg, #rcContour::verts, #rcContour::rverts
602static const int RC_BORDER_VERTEX = 0x10000;
603
604/// Area border flag.
605/// If a region ID has this bit set, then the associated element lies on
606/// the border of an area.
607/// (Used during the region and contour build process.)
608/// @see rcCompactSpan::reg, #rcContour::verts, #rcContour::rverts
609static const int RC_AREA_BORDER = 0x20000;
610
611/// Contour build flags.
612/// @see rcBuildContours
613enum rcBuildContoursFlags
614{
615 RC_CONTOUR_TESS_WALL_EDGES = 0x01, ///< Tessellate solid (impassable) edges during contour simplification.
616 RC_CONTOUR_TESS_AREA_EDGES = 0x02 ///< Tessellate edges between areas during contour simplification.
617};
618
619/// Applied to the region id field of contour vertices in order to extract the region id.
620/// The region id field of a vertex may have several flags applied to it. So the
621/// fields value can't be used directly.
622/// @see rcContour::verts, rcContour::rverts
623static const int RC_CONTOUR_REG_MASK = 0xffff;
624
625/// An value which indicates an invalid index within a mesh.
626/// @note This does not necessarily indicate an error.
627/// @see rcPolyMesh::polys
628static const unsigned short RC_MESH_NULL_IDX = 0xffff;
629
630/// Represents the null area.
631/// When a data element is given this value it is considered to no longer be
632/// assigned to a usable area. (E.g. It is un-walkable.)
633static const unsigned char RC_NULL_AREA = 0;
634
635/// The default area id used to indicate a walkable polygon.
636/// This is also the maximum allowed area id, and the only non-null area id
637/// recognized by some steps in the build process.
638static const unsigned char RC_WALKABLE_AREA = 63;
639
640/// The value returned by #rcGetCon if the specified direction is not connected
641/// to another span. (Has no neighbor.)
642static const int RC_NOT_CONNECTED = 0x3f;
643
644/// @name General helper functions
645/// @{
646
647/// Swaps the values of the two parameters.
648/// @param[in,out] a Value A
649/// @param[in,out] b Value B
650template<class T> inline void rcSwap(T& a, T& b) { T t = a; a = b; b = t; }
651
652/// Returns the minimum of two values.
653/// @param[in] a Value A
654/// @param[in] b Value B
655/// @return The minimum of the two values.
656template<class T> inline T rcMin(T a, T b) { return a < b ? a : b; }
657
658/// Returns the maximum of two values.
659/// @param[in] a Value A
660/// @param[in] b Value B
661/// @return The maximum of the two values.
662template<class T> inline T rcMax(T a, T b) { return a > b ? a : b; }
663
664/// Returns the absolute value.
665/// @param[in] a The value.
666/// @return The absolute value of the specified value.
667template<class T> inline T rcAbs(T a) { return a < 0 ? -a : a; }
668
669/// Returns the square of the value.
670/// @param[in] a The value.
671/// @return The square of the value.
672template<class T> inline T rcSqr(T a) { return a*a; }
673
674/// Clamps the value to the specified range.
675/// @param[in] value The value to clamp.
676/// @param[in] minInclusive The minimum permitted return value.
677/// @param[in] maxInclusive The maximum permitted return value.
678/// @return The value, clamped to the specified range.
679template<class T> inline T rcClamp(T value, T minInclusive, T maxInclusive)
680{
681 return value < minInclusive ? minInclusive: (value > maxInclusive ? maxInclusive : value);
682}
683
684/// Returns the square root of the value.
685/// @param[in] x The value.
686/// @return The square root of the vlaue.
687float rcSqrt(float x);
688
689/// @}
690/// @name Vector helper functions.
691/// @{
692
693/// Derives the cross product of two vectors. (@p v1 x @p v2)
694/// @param[out] dest The cross product. [(x, y, z)]
695/// @param[in] v1 A Vector [(x, y, z)]
696/// @param[in] v2 A vector [(x, y, z)]
697inline void rcVcross(float* dest, const float* v1, const float* v2)
698{
699 dest[0] = v1[1]*v2[2] - v1[2]*v2[1];
700 dest[1] = v1[2]*v2[0] - v1[0]*v2[2];
701 dest[2] = v1[0]*v2[1] - v1[1]*v2[0];
702}
703
704/// Derives the dot product of two vectors. (@p v1 . @p v2)
705/// @param[in] v1 A Vector [(x, y, z)]
706/// @param[in] v2 A vector [(x, y, z)]
707/// @return The dot product.
708inline float rcVdot(const float* v1, const float* v2)
709{
710 return v1[0]*v2[0] + v1[1]*v2[1] + v1[2]*v2[2];
711}
712
713/// Performs a scaled vector addition. (@p v1 + (@p v2 * @p s))
714/// @param[out] dest The result vector. [(x, y, z)]
715/// @param[in] v1 The base vector. [(x, y, z)]
716/// @param[in] v2 The vector to scale and add to @p v1. [(x, y, z)]
717/// @param[in] s The amount to scale @p v2 by before adding to @p v1.
718inline void rcVmad(float* dest, const float* v1, const float* v2, const float s)
719{
720 dest[0] = v1[0]+v2[0]*s;
721 dest[1] = v1[1]+v2[1]*s;
722 dest[2] = v1[2]+v2[2]*s;
723}
724
725/// Performs a vector addition. (@p v1 + @p v2)
726/// @param[out] dest The result vector. [(x, y, z)]
727/// @param[in] v1 The base vector. [(x, y, z)]
728/// @param[in] v2 The vector to add to @p v1. [(x, y, z)]
729inline void rcVadd(float* dest, const float* v1, const float* v2)
730{
731 dest[0] = v1[0]+v2[0];
732 dest[1] = v1[1]+v2[1];
733 dest[2] = v1[2]+v2[2];
734}
735
736/// Performs a vector subtraction. (@p v1 - @p v2)
737/// @param[out] dest The result vector. [(x, y, z)]
738/// @param[in] v1 The base vector. [(x, y, z)]
739/// @param[in] v2 The vector to subtract from @p v1. [(x, y, z)]
740inline void rcVsub(float* dest, const float* v1, const float* v2)
741{
742 dest[0] = v1[0]-v2[0];
743 dest[1] = v1[1]-v2[1];
744 dest[2] = v1[2]-v2[2];
745}
746
747/// Selects the minimum value of each element from the specified vectors.
748/// @param[in,out] mn A vector. (Will be updated with the result.) [(x, y, z)]
749/// @param[in] v A vector. [(x, y, z)]
750inline void rcVmin(float* mn, const float* v)
751{
752 mn[0] = rcMin(mn[0], v[0]);
753 mn[1] = rcMin(mn[1], v[1]);
754 mn[2] = rcMin(mn[2], v[2]);
755}
756
757/// Selects the maximum value of each element from the specified vectors.
758/// @param[in,out] mx A vector. (Will be updated with the result.) [(x, y, z)]
759/// @param[in] v A vector. [(x, y, z)]
760inline void rcVmax(float* mx, const float* v)
761{
762 mx[0] = rcMax(mx[0], v[0]);
763 mx[1] = rcMax(mx[1], v[1]);
764 mx[2] = rcMax(mx[2], v[2]);
765}
766
767/// Performs a vector copy.
768/// @param[out] dest The result. [(x, y, z)]
769/// @param[in] v The vector to copy. [(x, y, z)]
770inline void rcVcopy(float* dest, const float* v)
771{
772 dest[0] = v[0];
773 dest[1] = v[1];
774 dest[2] = v[2];
775}
776
777/// Returns the distance between two points.
778/// @param[in] v1 A point. [(x, y, z)]
779/// @param[in] v2 A point. [(x, y, z)]
780/// @return The distance between the two points.
781inline float rcVdist(const float* v1, const float* v2)
782{
783 float dx = v2[0] - v1[0];
784 float dy = v2[1] - v1[1];
785 float dz = v2[2] - v1[2];
786 return rcSqrt(dx*dx + dy*dy + dz*dz);
787}
788
789/// Returns the square of the distance between two points.
790/// @param[in] v1 A point. [(x, y, z)]
791/// @param[in] v2 A point. [(x, y, z)]
792/// @return The square of the distance between the two points.
793inline float rcVdistSqr(const float* v1, const float* v2)
794{
795 float dx = v2[0] - v1[0];
796 float dy = v2[1] - v1[1];
797 float dz = v2[2] - v1[2];
798 return dx*dx + dy*dy + dz*dz;
799}
800
801/// Normalizes the vector.
802/// @param[in,out] v The vector to normalize. [(x, y, z)]
803inline void rcVnormalize(float* v)
804{
805 float d = 1.0f / rcSqrt(rcSqr(v[0]) + rcSqr(v[1]) + rcSqr(v[2]));
806 v[0] *= d;
807 v[1] *= d;
808 v[2] *= d;
809}
810
811/// @}
812/// @name Heightfield Functions
813/// @see rcHeightfield
814/// @{
815
816/// Calculates the bounding box of an array of vertices.
817/// @ingroup recast
818/// @param[in] verts An array of vertices. [(x, y, z) * @p nv]
819/// @param[in] numVerts The number of vertices in the @p verts array.
820/// @param[out] minBounds The minimum bounds of the AABB. [(x, y, z)] [Units: wu]
821/// @param[out] maxBounds The maximum bounds of the AABB. [(x, y, z)] [Units: wu]
822void rcCalcBounds(const float* verts, int numVerts, float* minBounds, float* maxBounds);
823
824/// Calculates the grid size based on the bounding box and grid cell size.
825/// @ingroup recast
826/// @param[in] minBounds The minimum bounds of the AABB. [(x, y, z)] [Units: wu]
827/// @param[in] maxBounds The maximum bounds of the AABB. [(x, y, z)] [Units: wu]
828/// @param[in] cellSize The xz-plane cell size. [Limit: > 0] [Units: wu]
829/// @param[out] sizeX The width along the x-axis. [Limit: >= 0] [Units: vx]
830/// @param[out] sizeZ The height along the z-axis. [Limit: >= 0] [Units: vx]
831void rcCalcGridSize(const float* minBounds, const float* maxBounds, float cellSize, int* sizeX, int* sizeZ);
832
833/// Initializes a new heightfield.
834/// See the #rcConfig documentation for more information on the configuration parameters.
835///
836/// @see rcAllocHeightfield, rcHeightfield
837/// @ingroup recast
838///
839/// @param[in,out] context The build context to use during the operation.
840/// @param[in,out] heightfield The allocated heightfield to initialize.
841/// @param[in] sizeX The width of the field along the x-axis. [Limit: >= 0] [Units: vx]
842/// @param[in] sizeZ The height of the field along the z-axis. [Limit: >= 0] [Units: vx]
843/// @param[in] minBounds The minimum bounds of the field's AABB. [(x, y, z)] [Units: wu]
844/// @param[in] maxBounds The maximum bounds of the field's AABB. [(x, y, z)] [Units: wu]
845/// @param[in] cellSize The xz-plane cell size to use for the field. [Limit: > 0] [Units: wu]
846/// @param[in] cellHeight The y-axis cell size to use for field. [Limit: > 0] [Units: wu]
847/// @returns True if the operation completed successfully.
848bool rcCreateHeightfield(rcContext* context, rcHeightfield& heightfield, int sizeX, int sizeZ,
849 const float* minBounds, const float* maxBounds,
850 float cellSize, float cellHeight);
851
852/// Sets the area id of all triangles with a slope below the specified value
853/// to #RC_WALKABLE_AREA.
854///
855/// Only sets the area id's for the walkable triangles. Does not alter the
856/// area id's for un-walkable triangles.
857///
858/// See the #rcConfig documentation for more information on the configuration parameters.
859///
860/// @see rcHeightfield, rcClearUnwalkableTriangles, rcRasterizeTriangles
861///
862/// @ingroup recast
863/// @param[in,out] context The build context to use during the operation.
864/// @param[in] walkableSlopeAngle The maximum slope that is considered walkable.
865/// [Limits: 0 <= value < 90] [Units: Degrees]
866/// @param[in] verts The vertices. [(x, y, z) * @p nv]
867/// @param[in] numVerts The number of vertices.
868/// @param[in] tris The triangle vertex indices. [(vertA, vertB, vertC) * @p nt]
869/// @param[in] numTris The number of triangles.
870/// @param[out] triAreaIDs The triangle area ids. [Length: >= @p nt]
871void rcMarkWalkableTriangles(rcContext* context, float walkableSlopeAngle, const float* verts, int numVerts,
872 const int* tris, int numTris, unsigned char* triAreaIDs);
873
874/// Sets the area id of all triangles with a slope greater than or equal to the specified value to #RC_NULL_AREA.
875///
876/// Only sets the area id's for the un-walkable triangles. Does not alter the
877/// area id's for walkable triangles.
878///
879/// See the #rcConfig documentation for more information on the configuration parameters.
880///
881/// @see rcHeightfield, rcClearUnwalkableTriangles, rcRasterizeTriangles
882///
883/// @ingroup recast
884/// @param[in,out] context The build context to use during the operation.
885/// @param[in] walkableSlopeAngle The maximum slope that is considered walkable.
886/// [Limits: 0 <= value < 90] [Units: Degrees]
887/// @param[in] verts The vertices. [(x, y, z) * @p nv]
888/// @param[in] numVerts The number of vertices.
889/// @param[in] tris The triangle vertex indices. [(vertA, vertB, vertC) * @p nt]
890/// @param[in] numTris The number of triangles.
891/// @param[out] triAreaIDs The triangle area ids. [Length: >= @p nt]
892void rcClearUnwalkableTriangles(rcContext* context, float walkableSlopeAngle, const float* verts, int numVerts,
893 const int* tris, int numTris, unsigned char* triAreaIDs);
894
895/// Adds a span to the specified heightfield.
896///
897/// The span addition can be set to favor flags. If the span is merged to
898/// another span and the new @p spanMax is within @p flagMergeThreshold units
899/// from the existing span, the span flags are merged.
900///
901/// @ingroup recast
902/// @param[in,out] context The build context to use during the operation.
903/// @param[in,out] heightfield An initialized heightfield.
904/// @param[in] x The column x index where the span is to be added.
905/// [Limits: 0 <= value < rcHeightfield::width]
906/// @param[in] z The column z index where the span is to be added.
907/// [Limits: 0 <= value < rcHeightfield::height]
908/// @param[in] spanMin The minimum height of the span. [Limit: < @p spanMax] [Units: vx]
909/// @param[in] spanMax The maximum height of the span. [Limit: <= #RC_SPAN_MAX_HEIGHT] [Units: vx]
910/// @param[in] areaID The area id of the span. [Limit: <= #RC_WALKABLE_AREA)
911/// @param[in] flagMergeThreshold The merge threshold. [Limit: >= 0] [Units: vx]
912/// @returns True if the operation completed successfully.
913bool rcAddSpan(rcContext* context, rcHeightfield& heightfield,
914 int x, int z,
915 unsigned short spanMin, unsigned short spanMax,
916 unsigned char areaID, int flagMergeThreshold);
917
918/// Rasterizes a single triangle into the specified heightfield.
919///
920/// Calling this for each triangle in a mesh is less efficient than calling rcRasterizeTriangles
921///
922/// No spans will be added if the triangle does not overlap the heightfield grid.
923///
924/// @see rcHeightfield
925/// @ingroup recast
926/// @param[in,out] context The build context to use during the operation.
927/// @param[in] v0 Triangle vertex 0 [(x, y, z)]
928/// @param[in] v1 Triangle vertex 1 [(x, y, z)]
929/// @param[in] v2 Triangle vertex 2 [(x, y, z)]
930/// @param[in] areaID The area id of the triangle. [Limit: <= #RC_WALKABLE_AREA]
931/// @param[in,out] heightfield An initialized heightfield.
932/// @param[in] flagMergeThreshold The distance where the walkable flag is favored over the non-walkable flag.
933/// [Limit: >= 0] [Units: vx]
934/// @returns True if the operation completed successfully.
935bool rcRasterizeTriangle(rcContext* context,
936 const float* v0, const float* v1, const float* v2,
937 unsigned char areaID, rcHeightfield& heightfield, int flagMergeThreshold = 1);
938
939/// Rasterizes an indexed triangle mesh into the specified heightfield.
940///
941/// Spans will only be added for triangles that overlap the heightfield grid.
942///
943/// @see rcHeightfield
944/// @ingroup recast
945/// @param[in,out] context The build context to use during the operation.
946/// @param[in] verts The vertices. [(x, y, z) * @p nv]
947/// @param[in] numVerts The number of vertices. (unused) TODO (graham): Remove in next major release
948/// @param[in] tris The triangle indices. [(vertA, vertB, vertC) * @p nt]
949/// @param[in] triAreaIDs The area id's of the triangles. [Limit: <= #RC_WALKABLE_AREA] [Size: @p nt]
950/// @param[in] numTris The number of triangles.
951/// @param[in,out] heightfield An initialized heightfield.
952/// @param[in] flagMergeThreshold The distance where the walkable flag is favored over the non-walkable flag.
953/// [Limit: >= 0] [Units: vx]
954/// @returns True if the operation completed successfully.
955bool rcRasterizeTriangles(rcContext* context,
956 const float* verts, int numVerts,
957 const int* tris, const unsigned char* triAreaIDs, int numTris,
958 rcHeightfield& heightfield, int flagMergeThreshold = 1);
959
960/// Rasterizes an indexed triangle mesh into the specified heightfield.
961///
962/// Spans will only be added for triangles that overlap the heightfield grid.
963///
964/// @see rcHeightfield
965/// @ingroup recast
966/// @param[in,out] context The build context to use during the operation.
967/// @param[in] verts The vertices. [(x, y, z) * @p nv]
968/// @param[in] numVerts The number of vertices. (unused) TODO (graham): Remove in next major release
969/// @param[in] tris The triangle indices. [(vertA, vertB, vertC) * @p nt]
970/// @param[in] triAreaIDs The area id's of the triangles. [Limit: <= #RC_WALKABLE_AREA] [Size: @p nt]
971/// @param[in] numTris The number of triangles.
972/// @param[in,out] heightfield An initialized heightfield.
973/// @param[in] flagMergeThreshold The distance where the walkable flag is favored over the non-walkable flag.
974/// [Limit: >= 0] [Units: vx]
975/// @returns True if the operation completed successfully.
976bool rcRasterizeTriangles(rcContext* context,
977 const float* verts, int numVerts,
978 const unsigned short* tris, const unsigned char* triAreaIDs, int numTris,
979 rcHeightfield& heightfield, int flagMergeThreshold = 1);
980
981/// Rasterizes a triangle list into the specified heightfield.
982///
983/// Expects each triangle to be specified as three sequential vertices of 3 floats.
984///
985/// Spans will only be added for triangles that overlap the heightfield grid.
986///
987/// @see rcHeightfield
988/// @ingroup recast
989/// @param[in,out] context The build context to use during the operation.
990/// @param[in] verts The triangle vertices. [(ax, ay, az, bx, by, bz, cx, by, cx) * @p nt]
991/// @param[in] triAreaIDs The area id's of the triangles. [Limit: <= #RC_WALKABLE_AREA] [Size: @p nt]
992/// @param[in] numTris The number of triangles.
993/// @param[in,out] heightfield An initialized heightfield.
994/// @param[in] flagMergeThreshold The distance where the walkable flag is favored over the non-walkable flag.
995/// [Limit: >= 0] [Units: vx]
996/// @returns True if the operation completed successfully.
997bool rcRasterizeTriangles(rcContext* context,
998 const float* verts, const unsigned char* triAreaIDs, int numTris,
999 rcHeightfield& heightfield, int flagMergeThreshold = 1);
1000
1001/// Marks non-walkable spans as walkable if their maximum is within @p walkableClimb of a walkable neighbor.
1002///
1003/// Allows the formation of walkable regions that will flow over low lying
1004/// objects such as curbs, and up structures such as stairways.
1005///
1006/// Two neighboring spans are walkable if: <tt>rcAbs(currentSpan.smax - neighborSpan.smax) < waklableClimb</tt>
1007///
1008/// @warning Will override the effect of #rcFilterLedgeSpans. So if both filters are used, call
1009/// #rcFilterLedgeSpans after calling this filter.
1010///
1011/// @see rcHeightfield, rcConfig
1012///
1013/// @ingroup recast
1014/// @param[in,out] context The build context to use during the operation.
1015/// @param[in] walkableClimb Maximum ledge height that is considered to still be traversable.
1016/// [Limit: >=0] [Units: vx]
1017/// @param[in,out] heightfield A fully built heightfield. (All spans have been added.)
1018void rcFilterLowHangingWalkableObstacles(rcContext* context, int walkableClimb, rcHeightfield& heightfield);
1019
1020/// Marks spans that are ledges as not-walkable.
1021///
1022/// A ledge is a span with one or more neighbors whose maximum is further away than @p walkableClimb
1023/// from the current span's maximum.
1024/// This method removes the impact of the overestimation of conservative voxelization
1025/// so the resulting mesh will not have regions hanging in the air over ledges.
1026///
1027/// A span is a ledge if: <tt>rcAbs(currentSpan.smax - neighborSpan.smax) > walkableClimb</tt>
1028///
1029/// @see rcHeightfield, rcConfig
1030///
1031/// @ingroup recast
1032/// @param[in,out] context The build context to use during the operation.
1033/// @param[in] walkableHeight Minimum floor to 'ceiling' height that will still allow the floor area to
1034/// be considered walkable. [Limit: >= 3] [Units: vx]
1035/// @param[in] walkableClimb Maximum ledge height that is considered to still be traversable.
1036/// [Limit: >=0] [Units: vx]
1037/// @param[in,out] heightfield A fully built heightfield. (All spans have been added.)
1038void rcFilterLedgeSpans(rcContext* context, int walkableHeight, int walkableClimb, rcHeightfield& heightfield);
1039
1040/// Marks walkable spans as not walkable if the clearance above the span is less than the specified height.
1041///
1042/// For this filter, the clearance above the span is the distance from the span's
1043/// maximum to the next higher span's minimum. (Same grid column.)
1044///
1045/// @see rcHeightfield, rcConfig
1046/// @ingroup recast
1047///
1048/// @param[in,out] context The build context to use during the operation.
1049/// @param[in] walkableHeight Minimum floor to 'ceiling' height that will still allow the floor area to
1050/// be considered walkable. [Limit: >= 3] [Units: vx]
1051/// @param[in,out] heightfield A fully built heightfield. (All spans have been added.)
1052void rcFilterWalkableLowHeightSpans(rcContext* context, int walkableHeight, rcHeightfield& heightfield);
1053
1054/// Returns the number of spans contained in the specified heightfield.
1055/// @ingroup recast
1056/// @param[in,out] context The build context to use during the operation.
1057/// @param[in] heightfield An initialized heightfield.
1058/// @returns The number of spans in the heightfield.
1059int rcGetHeightFieldSpanCount(rcContext* context, const rcHeightfield& heightfield);
1060
1061/// @}
1062/// @name Compact Heightfield Functions
1063/// @see rcCompactHeightfield
1064/// @{
1065
1066/// Builds a compact heightfield representing open space, from a heightfield representing solid space.
1067///
1068/// This is just the beginning of the process of fully building a compact heightfield.
1069/// Various filters may be applied, then the distance field and regions built.
1070/// E.g: #rcBuildDistanceField and #rcBuildRegions
1071///
1072/// See the #rcConfig documentation for more information on the configuration parameters.
1073///
1074/// @see rcAllocCompactHeightfield, rcHeightfield, rcCompactHeightfield, rcConfig
1075/// @ingroup recast
1076///
1077/// @param[in,out] context The build context to use during the operation.
1078/// @param[in] walkableHeight Minimum floor to 'ceiling' height that will still allow the floor area
1079/// to be considered walkable. [Limit: >= 3] [Units: vx]
1080/// @param[in] walkableClimb Maximum ledge height that is considered to still be traversable.
1081/// [Limit: >=0] [Units: vx]
1082/// @param[in] heightfield The heightfield to be compacted.
1083/// @param[out] compactHeightfield The resulting compact heightfield. (Must be pre-allocated.)
1084/// @returns True if the operation completed successfully.
1085bool rcBuildCompactHeightfield(rcContext* context, int walkableHeight, int walkableClimb,
1086 const rcHeightfield& heightfield, rcCompactHeightfield& compactHeightfield);
1087
1088/// Erodes the walkable area within the heightfield by the specified radius.
1089/// @ingroup recast
1090/// @param[in,out] ctx The build context to use during the operation.
1091/// @param[in] radius The radius of erosion. [Limits: 0 < value < 255] [Units: vx]
1092/// @param[in,out] chf The populated compact heightfield to erode.
1093/// @returns True if the operation completed successfully.
1094bool rcErodeWalkableArea(rcContext* ctx, int radius, rcCompactHeightfield& chf);
1095
1096/// Applies a median filter to walkable area types (based on area id), removing noise.
1097/// @ingroup recast
1098/// @param[in,out] ctx The build context to use during the operation.
1099/// @param[in,out] chf A populated compact heightfield.
1100/// @returns True if the operation completed successfully.
1101bool rcMedianFilterWalkableArea(rcContext* ctx, rcCompactHeightfield& chf);
1102
1103/// Applies an area id to all spans within the specified bounding box. (AABB)
1104/// @ingroup recast
1105/// @param[in,out] ctx The build context to use during the operation.
1106/// @param[in] bmin The minimum of the bounding box. [(x, y, z)]
1107/// @param[in] bmax The maximum of the bounding box. [(x, y, z)]
1108/// @param[in] areaId The area id to apply. [Limit: <= #RC_WALKABLE_AREA]
1109/// @param[in,out] chf A populated compact heightfield.
1110void rcMarkBoxArea(rcContext* ctx, const float* bmin, const float* bmax, unsigned char areaId,
1111 rcCompactHeightfield& chf);
1112
1113/// Applies the area id to the all spans within the specified convex polygon.
1114/// @ingroup recast
1115/// @param[in,out] ctx The build context to use during the operation.
1116/// @param[in] verts The vertices of the polygon [Fomr: (x, y, z) * @p nverts]
1117/// @param[in] nverts The number of vertices in the polygon.
1118/// @param[in] hmin The height of the base of the polygon.
1119/// @param[in] hmax The height of the top of the polygon.
1120/// @param[in] areaId The area id to apply. [Limit: <= #RC_WALKABLE_AREA]
1121/// @param[in,out] chf A populated compact heightfield.
1122void rcMarkConvexPolyArea(rcContext* ctx, const float* verts, const int nverts,
1123 const float hmin, const float hmax, unsigned char areaId,
1124 rcCompactHeightfield& chf);
1125
1126/// Helper function to offset voncex polygons for rcMarkConvexPolyArea.
1127/// @ingroup recast
1128/// @param[in] verts The vertices of the polygon [Form: (x, y, z) * @p nverts]
1129/// @param[in] nverts The number of vertices in the polygon.
1130/// @param[in] offset How much to offset the polygon by. [Units: wu]
1131/// @param[out] outVerts The offset vertices (should hold up to 2 * @p nverts) [Form: (x, y, z) * return value]
1132/// @param[in] maxOutVerts The max number of vertices that can be stored to @p outVerts.
1133/// @returns Number of vertices in the offset polygon or 0 if too few vertices in @p outVerts.
1134int rcOffsetPoly(const float* verts, const int nverts, const float offset,
1135 float* outVerts, const int maxOutVerts);
1136
1137/// Applies the area id to all spans within the specified cylinder.
1138/// @ingroup recast
1139/// @param[in,out] ctx The build context to use during the operation.
1140/// @param[in] pos The center of the base of the cylinder. [Form: (x, y, z)]
1141/// @param[in] r The radius of the cylinder.
1142/// @param[in] h The height of the cylinder.
1143/// @param[in] areaId The area id to apply. [Limit: <= #RC_WALKABLE_AREA]
1144/// @param[in,out] chf A populated compact heightfield.
1145void rcMarkCylinderArea(rcContext* ctx, const float* pos,
1146 const float r, const float h, unsigned char areaId,
1147 rcCompactHeightfield& chf);
1148
1149/// Builds the distance field for the specified compact heightfield.
1150/// @ingroup recast
1151/// @param[in,out] ctx The build context to use during the operation.
1152/// @param[in,out] chf A populated compact heightfield.
1153/// @returns True if the operation completed successfully.
1154bool rcBuildDistanceField(rcContext* ctx, rcCompactHeightfield& chf);
1155
1156/// Builds region data for the heightfield using watershed partitioning.
1157/// @ingroup recast
1158/// @param[in,out] ctx The build context to use during the operation.
1159/// @param[in,out] chf A populated compact heightfield.
1160/// @param[in] borderSize The size of the non-navigable border around the heightfield.
1161/// [Limit: >=0] [Units: vx]
1162/// @param[in] minRegionArea The minimum number of cells allowed to form isolated island areas.
1163/// [Limit: >=0] [Units: vx].
1164/// @param[in] mergeRegionArea Any regions with a span count smaller than this value will, if possible,
1165/// be merged with larger regions. [Limit: >=0] [Units: vx]
1166/// @returns True if the operation completed successfully.
1167bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf, int borderSize, int minRegionArea, int mergeRegionArea);
1168
1169/// Builds region data for the heightfield by partitioning the heightfield in non-overlapping layers.
1170/// @ingroup recast
1171/// @param[in,out] ctx The build context to use during the operation.
1172/// @param[in,out] chf A populated compact heightfield.
1173/// @param[in] borderSize The size of the non-navigable border around the heightfield.
1174/// [Limit: >=0] [Units: vx]
1175/// @param[in] minRegionArea The minimum number of cells allowed to form isolated island areas.
1176/// [Limit: >=0] [Units: vx].
1177/// @returns True if the operation completed successfully.
1178bool rcBuildLayerRegions(rcContext* ctx, rcCompactHeightfield& chf, int borderSize, int minRegionArea);
1179
1180/// Builds region data for the heightfield using simple monotone partitioning.
1181/// @ingroup recast
1182/// @param[in,out] ctx The build context to use during the operation.
1183/// @param[in,out] chf A populated compact heightfield.
1184/// @param[in] borderSize The size of the non-navigable border around the heightfield.
1185/// [Limit: >=0] [Units: vx]
1186/// @param[in] minRegionArea The minimum number of cells allowed to form isolated island areas.
1187/// [Limit: >=0] [Units: vx].
1188/// @param[in] mergeRegionArea Any regions with a span count smaller than this value will, if possible,
1189/// be merged with larger regions. [Limit: >=0] [Units: vx]
1190/// @returns True if the operation completed successfully.
1191bool rcBuildRegionsMonotone(rcContext* ctx, rcCompactHeightfield& chf,
1192 int borderSize, int minRegionArea, int mergeRegionArea);
1193
1194/// Sets the neighbor connection data for the specified direction.
1195/// @param[in] span The span to update.
1196/// @param[in] direction The direction to set. [Limits: 0 <= value < 4]
1197/// @param[in] neighborIndex The index of the neighbor span.
1198inline void rcSetCon(rcCompactSpan& span, int direction, int neighborIndex)
1199{
1200 const unsigned int shift = (unsigned int)direction * 6;
1201 const unsigned int con = span.con;
1202 span.con = (con & ~(0x3f << shift)) | (((unsigned int)neighborIndex & 0x3f) << shift);
1203}
1204
1205/// Gets neighbor connection data for the specified direction.
1206/// @param[in] span The span to check.
1207/// @param[in] direction The direction to check. [Limits: 0 <= value < 4]
1208/// @return The neighbor connection data for the specified direction, or #RC_NOT_CONNECTED if there is no connection.
1209inline int rcGetCon(const rcCompactSpan& span, int direction)
1210{
1211 const unsigned int shift = (unsigned int)direction * 6;
1212 return (span.con >> shift) & 0x3f;
1213}
1214
1215/// Gets the standard width (x-axis) offset for the specified direction.
1216/// @param[in] direction The direction. [Limits: 0 <= value < 4]
1217/// @return The width offset to apply to the current cell position to move in the direction.
1218inline int rcGetDirOffsetX(int direction)
1219{
1220 static const int offset[4] = { -1, 0, 1, 0, };
1221 return offset[direction & 0x03];
1222}
1223
1224// TODO (graham): Rename this to rcGetDirOffsetZ
1225/// Gets the standard height (z-axis) offset for the specified direction.
1226/// @param[in] direction The direction. [Limits: 0 <= value < 4]
1227/// @return The height offset to apply to the current cell position to move in the direction.
1228inline int rcGetDirOffsetY(int direction)
1229{
1230 static const int offset[4] = { 0, 1, 0, -1 };
1231 return offset[direction & 0x03];
1232}
1233
1234/// Gets the direction for the specified offset. One of x and y should be 0.
1235/// @param[in] offsetX The x offset. [Limits: -1 <= value <= 1]
1236/// @param[in] offsetZ The z offset. [Limits: -1 <= value <= 1]
1237/// @return The direction that represents the offset.
1238inline int rcGetDirForOffset(int offsetX, int offsetZ)
1239{
1240 static const int dirs[5] = { 3, 0, -1, 2, 1 };
1241 return dirs[((offsetZ + 1) << 1) + offsetX];
1242}
1243
1244/// @}
1245/// @name Layer, Contour, Polymesh, and Detail Mesh Functions
1246/// @see rcHeightfieldLayer, rcContourSet, rcPolyMesh, rcPolyMeshDetail
1247/// @{
1248
1249/// Builds a layer set from the specified compact heightfield.
1250/// @ingroup recast
1251/// @param[in,out] ctx The build context to use during the operation.
1252/// @param[in] chf A fully built compact heightfield.
1253/// @param[in] borderSize The size of the non-navigable border around the heightfield. [Limit: >=0]
1254/// [Units: vx]
1255/// @param[in] walkableHeight Minimum floor to 'ceiling' height that will still allow the floor area
1256/// to be considered walkable. [Limit: >= 3] [Units: vx]
1257/// @param[out] lset The resulting layer set. (Must be pre-allocated.)
1258/// @returns True if the operation completed successfully.
1259bool rcBuildHeightfieldLayers(rcContext* ctx, const rcCompactHeightfield& chf,
1260 int borderSize, int walkableHeight,
1261 rcHeightfieldLayerSet& lset);
1262
1263/// Builds a contour set from the region outlines in the provided compact heightfield.
1264/// @ingroup recast
1265/// @param[in,out] ctx The build context to use during the operation.
1266/// @param[in] chf A fully built compact heightfield.
1267/// @param[in] maxError The maximum distance a simplified contour's border edges should deviate
1268/// the original raw contour. [Limit: >=0] [Units: wu]
1269/// @param[in] maxEdgeLen The maximum allowed length for contour edges along the border of the mesh.
1270/// [Limit: >=0] [Units: vx]
1271/// @param[out] cset The resulting contour set. (Must be pre-allocated.)
1272/// @param[in] buildFlags The build flags. (See: #rcBuildContoursFlags)
1273/// @returns True if the operation completed successfully.
1274bool rcBuildContours(rcContext* ctx, const rcCompactHeightfield& chf,
1275 float maxError, int maxEdgeLen,
1276 rcContourSet& cset, int buildFlags = RC_CONTOUR_TESS_WALL_EDGES);
1277
1278/// Builds a polygon mesh from the provided contours.
1279/// @ingroup recast
1280/// @param[in,out] ctx The build context to use during the operation.
1281/// @param[in] cset A fully built contour set.
1282/// @param[in] nvp The maximum number of vertices allowed for polygons generated during the
1283/// contour to polygon conversion process. [Limit: >= 3]
1284/// @param[out] mesh The resulting polygon mesh. (Must be re-allocated.)
1285/// @returns True if the operation completed successfully.
1286bool rcBuildPolyMesh(rcContext* ctx, const rcContourSet& cset, const int nvp, rcPolyMesh& mesh);
1287
1288/// Merges multiple polygon meshes into a single mesh.
1289/// @ingroup recast
1290/// @param[in,out] ctx The build context to use during the operation.
1291/// @param[in] meshes An array of polygon meshes to merge. [Size: @p nmeshes]
1292/// @param[in] nmeshes The number of polygon meshes in the meshes array.
1293/// @param[in] mesh The resulting polygon mesh. (Must be pre-allocated.)
1294/// @returns True if the operation completed successfully.
1295bool rcMergePolyMeshes(rcContext* ctx, rcPolyMesh** meshes, const int nmeshes, rcPolyMesh& mesh);
1296
1297/// Builds a detail mesh from the provided polygon mesh.
1298/// @ingroup recast
1299/// @param[in,out] ctx The build context to use during the operation.
1300/// @param[in] mesh A fully built polygon mesh.
1301/// @param[in] chf The compact heightfield used to build the polygon mesh.
1302/// @param[in] sampleDist Sets the distance to use when sampling the heightfield. [Limit: >=0] [Units: wu]
1303/// @param[in] sampleMaxError The maximum distance the detail mesh surface should deviate from
1304/// heightfield data. [Limit: >=0] [Units: wu]
1305/// @param[out] dmesh The resulting detail mesh. (Must be pre-allocated.)
1306/// @returns True if the operation completed successfully.
1307bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompactHeightfield& chf,
1308 float sampleDist, float sampleMaxError,
1309 rcPolyMeshDetail& dmesh);
1310
1311/// Copies the poly mesh data from src to dst.
1312/// @ingroup recast
1313/// @param[in,out] ctx The build context to use during the operation.
1314/// @param[in] src The source mesh to copy from.
1315/// @param[out] dst The resulting detail mesh. (Must be pre-allocated, must be empty mesh.)
1316/// @returns True if the operation completed successfully.
1317bool rcCopyPolyMesh(rcContext* ctx, const rcPolyMesh& src, rcPolyMesh& dst);
1318
1319/// Merges multiple detail meshes into a single detail mesh.
1320/// @ingroup recast
1321/// @param[in,out] ctx The build context to use during the operation.
1322/// @param[in] meshes An array of detail meshes to merge. [Size: @p nmeshes]
1323/// @param[in] nmeshes The number of detail meshes in the meshes array.
1324/// @param[out] mesh The resulting detail mesh. (Must be pre-allocated.)
1325/// @returns True if the operation completed successfully.
1326bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int nmeshes, rcPolyMeshDetail& mesh);
1327
1328/// @}
1329
1330#endif // RECAST_H
1331
1332///////////////////////////////////////////////////////////////////////////
1333
1334// Due to the large amount of detail documentation for this file,
1335// the content normally located at the end of the header file has been separated
1336// out to a file in /Docs/Extern.
1337