svn merge ^/trunk/blender -r40644:40720
[blender-staging.git] / extern / recastnavigation / Recast / Include / Recast.h
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.
23 static const float RC_PI = 3.14159265f;
24
25 /// Recast log categories.
26 /// @see rcContext
27 enum rcLogCategory
28 {
29         RC_LOG_PROGRESS = 1,    ///< A progress log entry.
30         RC_LOG_WARNING,             ///< A warning log entry.
31         RC_LOG_ERROR,               ///< An error log entry.
32 };
33
34 /// Recast performance timer categories.
35 /// @see rcContext
36 enum rcTimerLabel
37 {
38         /// The user defined total time of the build.
39         RC_TIMER_TOTAL,
40         /// A user defined build time.
41         RC_TIMER_TEMP,
42         /// The time to rasterize the triangles. (See: #rcRasterizeTriangle)
43         RC_TIMER_RASTERIZE_TRIANGLES,
44         /// The time to build the compact heightfield. (See: #rcBuildCompactHeightfield)
45         RC_TIMER_BUILD_COMPACTHEIGHTFIELD,
46         /// The total time to build the contours. (See: #rcBuildContours)
47         RC_TIMER_BUILD_CONTOURS,
48         /// The time to trace the boundaries of the contours. (See: #rcBuildContours)
49         RC_TIMER_BUILD_CONTOURS_TRACE,
50         /// The time to simplify the contours. (See: #rcBuildContours)
51         RC_TIMER_BUILD_CONTOURS_SIMPLIFY,
52         /// The time to filter ledge spans. (See: #rcFilterLedgeSpans)
53         RC_TIMER_FILTER_BORDER,
54         /// The time to filter low height spans. (See: #rcFilterWalkableLowHeightSpans)
55         RC_TIMER_FILTER_WALKABLE,
56         /// The time to apply the median filter. (See: #rcMedianFilterWalkableArea)
57         RC_TIMER_MEDIAN_AREA,
58         /// The time to filter low obstacles. (See: #rcFilterLowHangingWalkableObstacles)
59         RC_TIMER_FILTER_LOW_OBSTACLES,
60         /// The time to build the polygon mesh. (See: #rcBuildPolyMesh)
61         RC_TIMER_BUILD_POLYMESH,
62         /// The time to merge polygon meshes. (See: #rcMergePolyMeshes)
63         RC_TIMER_MERGE_POLYMESH,
64         /// The time to erode the walkable area. (See: #rcErodeWalkableArea)
65         RC_TIMER_ERODE_AREA,
66         /// The time to mark a box area. (See: #rcMarkBoxArea)
67         RC_TIMER_MARK_BOX_AREA,
68         /// The time to mark a cylinder area. (See: #rcMarkCylinderArea)
69         RC_TIMER_MARK_CYLINDER_AREA,
70         /// The time to mark a convex polygon area. (See: #rcMarkConvexPolyArea)
71         RC_TIMER_MARK_CONVEXPOLY_AREA,
72         /// The total time to build the distance field. (See: #rcBuildDistanceField)
73         RC_TIMER_BUILD_DISTANCEFIELD,
74         /// The time to build the distances of the distance field. (See: #rcBuildDistanceField)
75         RC_TIMER_BUILD_DISTANCEFIELD_DIST,
76         /// The time to blur the distance field. (See: #rcBuildDistanceField)
77         RC_TIMER_BUILD_DISTANCEFIELD_BLUR,
78         /// The total time to build the regions. (See: #rcBuildRegions, #rcBuildRegionsMonotone)
79         RC_TIMER_BUILD_REGIONS,
80         /// The total time to apply the watershed algorithm. (See: #rcBuildRegions)
81         RC_TIMER_BUILD_REGIONS_WATERSHED,
82         /// The time to expand regions while applying the watershed algorithm. (See: #rcBuildRegions)
83         RC_TIMER_BUILD_REGIONS_EXPAND,
84         /// The time to flood regions while applying the watershed algorithm. (See: #rcBuildRegions)
85         RC_TIMER_BUILD_REGIONS_FLOOD,
86         /// The time to filter out small regions. (See: #rcBuildRegions, #rcBuildRegionsMonotone)
87         RC_TIMER_BUILD_REGIONS_FILTER,
88         /// The time to build heightfield layers. (See: #rcBuildHeightfieldLayers)
89         RC_TIMER_BUILD_LAYERS, 
90         /// The time to build the polygon mesh detail. (See: #rcBuildPolyMeshDetail)
91         RC_TIMER_BUILD_POLYMESHDETAIL,
92         /// The time to merge polygon mesh details. (See: #rcMergePolyMeshDetails)
93         RC_TIMER_MERGE_POLYMESHDETAIL,
94         /// The maximum number of timers.  (Used for iterating timers.)
95         RC_MAX_TIMERS
96 };
97
98 /// Provides an interface for optional logging and performance tracking of the Recast 
99 /// build process.
100 /// @ingroup recast
101 class rcContext
102 {
103 public:
104
105         /// Contructor.
106         ///  @param[in] state  TRUE if the logging and performance timers should be enabled.  [Default: true]
107         inline rcContext(bool state = true) : m_logEnabled(state), m_timerEnabled(state) {}
108         virtual ~rcContext() {}
109
110         /// Enables or disables logging.
111         ///  @param[in] state TRUE if logging should be enabled.
112         inline void enableLog(bool state) { m_logEnabled = state; }
113
114         /// Clears all log entries.
115         inline void resetLog() { if (m_logEnabled) doResetLog(); }
116
117         /// Logs a message.
118         ///  @param[in] category The category of the message.
119         ///  @param[in] format The message.
120         void log(const rcLogCategory category, const char* format, ...);
121
122         /// Enables or disables the performance timers.
123         ///  @param[in] state  TRUE if timers should be enabled.
124         inline void enableTimer(bool state) { m_timerEnabled = state; }
125
126         /// Clears all peformance timers. (Resets all to unused.)
127         inline void resetTimers() { if (m_timerEnabled) doResetTimers(); }
128
129         /// Starts the specified performance timer.
130         ///  @param label  The category of timer.
131         inline void startTimer(const rcTimerLabel label) { if (m_timerEnabled) doStartTimer(label); }
132
133         /// Stops the specified performance timer.
134         ///  @param label  The category of the timer.
135         inline void stopTimer(const rcTimerLabel label) { if (m_timerEnabled) doStopTimer(label); }
136
137         /// Returns the total accumulated time of the specified performance timer.
138         ///  @param label  The category of the timer.
139         ///  @return The accumulated time of the timer, or -1 if timers are disabled or the timer has never been started.
140         inline int getAccumulatedTime(const rcTimerLabel label) const { return m_timerEnabled ? doGetAccumulatedTime(label) : -1; }
141
142 protected:
143
144         /// Clears all log entries.
145         virtual void doResetLog() {}
146
147         /// Logs a message.
148         ///  @param[in] category The category of the message.
149         ///  @param[in] msg The formatted message.
150         ///  @param[in] len The length of the formatted message.
151         virtual void doLog(const rcLogCategory /*category*/, const char* /*msg*/, const int /*len*/) {}
152
153         /// Clears all timers. (Resets all to unused.)
154         virtual void doResetTimers() {}
155
156         /// Starts the specified performance timer.
157         ///  @param[in] label  The category of timer.
158         virtual void doStartTimer(const rcTimerLabel /*label*/) {}
159
160         /// Stops the specified performance timer.
161         ///  @param[in] label  The category of the timer.
162         virtual void doStopTimer(const rcTimerLabel /*label*/) {}
163
164         /// Returns the total accumulated time of the specified performance timer.
165         ///  @param[in] label  The category of the timer.
166         ///  @return The accumulated time of the timer, or -1 if timers are disabled or the timer has never been started.
167         virtual int doGetAccumulatedTime(const rcTimerLabel /*label*/) const { return -1; }
168         
169         /// True if logging is enabled.
170         bool m_logEnabled;
171
172         /// True if the performance timers are enabled.
173         bool m_timerEnabled;
174 };
175
176 /// Specifies a configuration to use when performing Recast builds.
177 /// @ingroup recast
178 struct rcConfig
179 {
180         /// The width of the field along the x-axis. [Limit: >= 0] [Units: vx]
181         int width;
182
183         /// The height of the field along the z-axis. [Limit: >= 0] [Units: vx]
184         int height;     
185         
186         /// The width/height size of tile's on the xz-plane. [Limit: >= 0] [Units: vx]
187         int tileSize;   
188         
189         /// The size of the non-navigable border around the heightfield. [Limit: >=0] [Units: vx]
190         int borderSize;
191
192         /// The xz-plane cell size to use for fields. [Limit: > 0] [Units: wu] 
193         float cs;
194
195         /// The y-axis cell size to use for fields. [Limit: > 0] [Units: wu]
196         float ch;
197
198         /// The minimum bounds of the field's AABB. [(x, y, z)] [Units: wu]
199         float bmin[3]; 
200
201         /// The maximum bounds of the field's AABB. [(x, y, z)] [Units: wu]
202         float bmax[3];
203
204         /// The maximum slope that is considered walkable. [Limits: 0 <= value < 90] [Units: Degrees] 
205         float walkableSlopeAngle;
206
207         /// Minimum floor to 'ceiling' height that will still allow the floor area to 
208         /// be considered walkable. [Limit: >= 3] [Units: vx] 
209         int walkableHeight;                             
210         
211         /// Maximum ledge height that is considered to still be traversable. [Limit: >=0] [Units: vx] 
212         int walkableClimb;                              
213         
214         /// The distance to erode/shrink the walkable area of the heightfield away from 
215         /// obstructions.  [Limit: >=0] [Units: vx] 
216         int walkableRadius;                             
217         
218         /// The maximum allowed length for contour edges along the border of the mesh. [Limit: >=0] [Units: vx] 
219         int maxEdgeLen;                                 
220         
221         /// The maximum distance a simplfied contour's border edges should deviate 
222         /// the original raw contour. [Limit: >=0] [Units: wu]
223         float maxSimplificationError;   
224         
225         /// The minimum number of cells allowed to form isolated island areas. [Limit: >=0] [Units: vx] 
226         int minRegionArea;                              
227         
228         /// Any regions with a span count smaller than this value will, if possible, 
229         /// be merged with larger regions. [Limit: >=0] [Units: vx] 
230         int mergeRegionArea;                    
231         
232         /// The maximum number of vertices allowed for polygons generated during the 
233         /// contour to polygon conversion process. [Limit: >= 3] 
234         int maxVertsPerPoly;
235         
236         /// Sets the sampling distance to use when generating the detail mesh.
237         /// (For height detail only.) [Limits: 0 or >= 0.9] [Units: wu] 
238         float detailSampleDist;
239         
240         /// The maximum distance the detail mesh surface should deviate from heightfield
241         /// data. (For height detail only.) [Limit: >=0] [Units: wu] 
242         float detailSampleMaxError;
243 };
244
245 /// Defines the number of bits allocated to rcSpan::smin and rcSpan::smax.
246 static const int RC_SPAN_HEIGHT_BITS = 13;
247 /// Defines the maximum value for rcSpan::smin and rcSpan::smax.
248 static const int RC_SPAN_MAX_HEIGHT = (1<<RC_SPAN_HEIGHT_BITS)-1;
249
250 /// The number of spans allocated per span spool.
251 /// @see rcSpanPool
252 static const int RC_SPANS_PER_POOL = 2048;
253
254 /// Represents a span in a heightfield.
255 /// @see rcHeightfield
256 struct rcSpan
257 {
258     unsigned int smin : 13;                     ///< The lower limit of the span. [Limit: < #smax]
259     unsigned int smax : 13;                     ///< The upper limit of the span. [Limit: <= #RC_SPAN_MAX_HEIGHT]
260         unsigned int area : 6;                  ///< The area id assigned to the span.
261         rcSpan* next;                                   ///< The next span higher up in column.
262 };
263
264 /// A memory pool used for quick allocation of spans within a heightfield.
265 /// @see rcHeightfield
266 struct rcSpanPool
267 {
268         rcSpanPool* next;                                       ///< The next span pool.
269         rcSpan items[RC_SPANS_PER_POOL];        ///< Array of spans in the pool.
270 };
271
272 /// A dynamic heightfield representing obstructed space.
273 /// @ingroup recast
274 struct rcHeightfield
275 {
276         int width;                  ///< The width of the heightfield. (Along the x-axis in cell units.)
277         int height;                     ///< The height of the heightfield. (Along the z-axis in cell units.)
278         float bmin[3];          ///< The minimum bounds in world space. [(x, y, z)]
279         float bmax[3];          ///< The maximum bounds in world space. [(x, y, z)]
280         float cs;                   ///< The size of each cell. (On the xz-plane.)
281         float ch;                       ///< The height of each cell. (The minimum increment along the y-axis.)
282         rcSpan** spans;         ///< Heightfield of spans (width*height).
283         rcSpanPool* pools;      ///< Linked list of span pools.
284         rcSpan* freelist;       ///< The next free span.
285 };
286
287 /// Provides information on the content of a cell column in a compact heightfield. 
288 struct rcCompactCell
289 {
290         unsigned int index : 24;        ///< Index to the first span in the column.
291         unsigned int count : 8;         ///< Number of spans in the column.
292 };
293
294 /// Represents a span of unobstructed space within a compact heightfield.
295 struct rcCompactSpan
296 {
297         unsigned short y;                       ///< The lower extent of the span. (Measured from the heightfield's base.)
298         unsigned short reg;                 ///< The id of the region the span belongs to. (Or zero if not in a region.)
299         unsigned int con : 24;          ///< Packed neighbor connection data.
300         unsigned int h : 8;                     ///< The height of the span.  (Measured from #y.)
301 };
302
303 /// A compact, static heightfield representing unobstructed space.
304 /// @ingroup recast
305 struct rcCompactHeightfield
306 {
307         int width;                                  ///< The width of the heightfield. (Along the x-axis in cell units.)
308         int height;                                     ///< The height of the heightfield. (Along the z-axis in cell units.)
309         int spanCount;                          ///< The number of spans in the heightfield.
310         int walkableHeight;                 ///< The walkable height used during the build of the field.  (See: rcConfig::walkableHeight)
311         int walkableClimb;                      ///< The walkable climb used during the build of the field. (See: rcConfig::walkableClimb)
312         int borderSize;                         ///< The AABB border size used during the build of the field. (See: rcConfig::borderSize)
313         unsigned short maxDistance;     ///< The maximum distance value of any span within the field. 
314         unsigned short maxRegions;      ///< The maximum region id of any span within the field. 
315         float bmin[3];                      ///< The minimum bounds in world space. [(x, y, z)]
316         float bmax[3];                          ///< The maximum bounds in world space. [(x, y, z)]
317         float cs;                                   ///< The size of each cell. (On the xz-plane.)
318         float ch;                                       ///< The height of each cell. (The minimum increment along the y-axis.)
319         rcCompactCell* cells;           ///< Array of cells. [Size: #width*#height]
320         rcCompactSpan* spans;           ///< Array of spans. [Size: #spanCount]
321         unsigned short* dist;           ///< Array containing border distance data. [Size: #spanCount]
322         unsigned char* areas;           ///< Array containing area id data. [Size: #spanCount]
323 };
324
325 /// Represents a heightfield layer within a layer set.
326 /// @see rcHeightfieldLayerSet
327 struct rcHeightfieldLayer
328 {
329         float bmin[3];                      ///< The minimum bounds in world space. [(x, y, z)]
330         float bmax[3];                          ///< The maximum bounds in world space. [(x, y, z)]
331         float cs;                                   ///< The size of each cell. (On the xz-plane.)
332         float ch;                                       ///< The height of each cell. (The minimum increment along the y-axis.)
333         int width;                                  ///< The width of the heightfield. (Along the x-axis in cell units.)
334         int height;                                     ///< The height of the heightfield. (Along the z-axis in cell units.)
335         int minx;                                   ///< The minimum x-bounds of usable data.
336         int maxx;                                   ///< The maximum x-bounds of usable data.
337         int miny;                                   ///< The minimum y-bounds of usable data. (Along the z-axis.)
338         int maxy;                                       ///< The maximum y-bounds of usable data. (Along the z-axis.)
339         int hmin;                                   ///< The minimum height bounds of usable data. (Along the y-axis.)
340         int hmax;                                       ///< The maximum height bounds of usable data. (Along the y-axis.)
341         unsigned char* heights;         ///< The heightfield. [Size: (width - borderSize*2) * (h - borderSize*2)]
342         unsigned char* areas;           ///< Area ids. [Size: Same as #heights]
343         unsigned char* cons;            ///< Packed neighbor connection information. [Size: Same as #heights]
344 };
345
346 /// Represents a set of heightfield layers.
347 /// @ingroup recast
348 /// @see rcAllocHeightfieldLayerSet, rcFreeHeightfieldLayerSet 
349 struct rcHeightfieldLayerSet
350 {
351         rcHeightfieldLayer* layers;                     ///< The layers in the set. [Size: #nlayers]
352         int nlayers;                                            ///< The number of layers in the set.
353 };
354
355 /// Represents a simple, non-overlapping contour in field space.
356 struct rcContour
357 {
358         int* verts;                     ///< Simplified contour vertex and connection data. [Size: 4 * #nverts]
359         int nverts;                     ///< The number of vertices in the simplified contour. 
360         int* rverts;            ///< Raw contour vertex and connection data. [Size: 4 * #nrverts]
361         int nrverts;            ///< The number of vertices in the raw contour. 
362         unsigned short reg;     ///< The region id of the contour.
363         unsigned char area;     ///< The area id of the contour.
364 };
365
366 /// Represents a group of related contours.
367 /// @ingroup recast
368 struct rcContourSet
369 {
370         rcContour* conts;       ///< An array of the contours in the set. [Size: #nconts]
371         int nconts;                     ///< The number of contours in the set.
372         float bmin[3];          ///< The minimum bounds in world space. [(x, y, z)]
373         float bmax[3];          ///< The maximum bounds in world space. [(x, y, z)]
374         float cs;                   ///< The size of each cell. (On the xz-plane.)
375         float ch;                       ///< The height of each cell. (The minimum increment along the y-axis.)
376         int width;                  ///< The width of the set. (Along the x-axis in cell units.) 
377         int height;                 ///< The height of the set. (Along the z-axis in cell units.) 
378         int borderSize;         ///< The AABB border size used to generate the source data from which the contours were derived.
379 };
380
381 /// Represents a polygon mesh suitable for use in building a navigation mesh. 
382 /// @ingroup recast
383 struct rcPolyMesh
384 {       
385         unsigned short* verts;  ///< The mesh vertices. [Form: (x, y, z) * #nverts]
386         unsigned short* polys;  ///< Polygon and neighbor data. [Length: #maxpolys * 2 * #nvp]
387         unsigned short* regs;   ///< The region id assigned to each polygon. [Length: #maxpolys]
388         unsigned short* flags;  ///< The user defined flags for each polygon. [Length: #maxpolys]
389         unsigned char* areas;   ///< The area id assigned to each polygon. [Length: #maxpolys]
390         int nverts;                             ///< The number of vertices.
391         int npolys;                             ///< The number of polygons.
392         int maxpolys;                   ///< The number of allocated polygons.
393         int nvp;                                ///< The maximum number of vertices per polygon.
394         float bmin[3];              ///< The minimum bounds in world space. [(x, y, z)]
395         float bmax[3];              ///< The maximum bounds in world space. [(x, y, z)]
396         float cs;                           ///< The size of each cell. (On the xz-plane.)
397         float ch;                               ///< The height of each cell. (The minimum increment along the y-axis.)
398         int borderSize;                 ///< The AABB border size used to generate the source data from which the mesh was derived.
399 };
400
401 /// Contains triangle meshes that represent detailed height data associated 
402 /// with the polygons in its associated polygon mesh object.
403 /// @ingroup recast
404 struct rcPolyMeshDetail
405 {
406     unsigned int* meshes;       ///< The sub-mesh data. [Size: 4*#nmeshes] 
407     float* verts;                       ///< The mesh vertices. [Size: 3*#nverts] 
408     unsigned char* tris;        ///< The mesh triangles. [Size: 4*#ntris] 
409     int nmeshes;                        ///< The number of sub-meshes defined by #meshes.
410     int nverts;                         ///< The number of vertices in #verts.
411     int ntris;                          ///< The number of triangles in #tris.
412 };
413
414 /// @name Allocation Functions
415 /// Functions used to allocate and de-allocate Recast objects.
416 /// @see rcAllocSetCustom
417 /// @{
418
419 /// Allocates a heightfield object using the Recast allocator.
420 ///  @return A heightfield that is ready for initialization, or null on failure.
421 ///  @ingroup recast
422 ///  @see rcCreateHeightfield, rcFreeHeightField
423 rcHeightfield* rcAllocHeightfield();
424
425 /// Frees the specified heightfield object using the Recast allocator.
426 ///  @param[in] hf  A heightfield allocated using #rcAllocHeightfield
427 ///  @ingroup recast
428 ///  @see rcAllocHeightfield
429 void rcFreeHeightField(rcHeightfield* hf);
430
431 /// Allocates a compact heightfield object using the Recast allocator.
432 ///  @return A compact heightfield that is ready for initialization, or null on failure.
433 ///  @ingroup recast
434 ///  @see rcBuildCompactHeightfield, rcFreeCompactHeightfield
435 rcCompactHeightfield* rcAllocCompactHeightfield();
436
437 /// Frees the specified compact heightfield object using the Recast allocator.
438 ///  @param[in] chf  A compact heightfield allocated using #rcAllocCompactHeightfield
439 ///  @ingroup recast
440 ///  @see rcAllocCompactHeightfield
441 void rcFreeCompactHeightfield(rcCompactHeightfield* chf);
442
443 /// Allocates a heightfield layer set using the Recast allocator.
444 ///  @return A heightfield layer set that is ready for initialization, or null on failure.
445 ///  @ingroup recast
446 ///  @see rcBuildHeightfieldLayers, rcFreeHeightfieldLayerSet
447 rcHeightfieldLayerSet* rcAllocHeightfieldLayerSet();
448
449 /// Frees the specified heightfield layer set using the Recast allocator.
450 ///  @param[in] lset  A heightfield layer set allocated using #rcAllocHeightfieldLayerSet
451 ///  @ingroup recast
452 ///  @see rcAllocHeightfieldLayerSet
453 void rcFreeHeightfieldLayerSet(rcHeightfieldLayerSet* lset);
454
455 /// Allocates a contour set object using the Recast allocator.
456 ///  @return A contour set that is ready for initialization, or null on failure.
457 ///  @ingroup recast
458 ///  @see rcBuildContours, rcFreeContourSet
459 rcContourSet* rcAllocContourSet();
460
461 /// Frees the specified contour set using the Recast allocator.
462 ///  @param[in] cset  A contour set allocated using #rcAllocContourSet
463 ///  @ingroup recast
464 ///  @see rcAllocContourSet
465 void rcFreeContourSet(rcContourSet* cset);
466
467 /// Allocates a polygon mesh object using the Recast allocator.
468 ///  @return A polygon mesh that is ready for initialization, or null on failure.
469 ///  @ingroup recast
470 ///  @see rcBuildPolyMesh, rcFreePolyMesh
471 rcPolyMesh* rcAllocPolyMesh();
472
473 /// Frees the specified polygon mesh using the Recast allocator.
474 ///  @param[in] pmesh  A polygon mesh allocated using #rcAllocPolyMesh
475 ///  @ingroup recast
476 ///  @see rcAllocPolyMesh
477 void rcFreePolyMesh(rcPolyMesh* pmesh);
478
479 /// Allocates a detail mesh object using the Recast allocator.
480 ///  @return A detail mesh that is ready for initialization, or null on failure.
481 ///  @ingroup recast
482 ///  @see rcBuildPolyMeshDetail, rcFreePolyMeshDetail
483 rcPolyMeshDetail* rcAllocPolyMeshDetail();
484
485 /// Frees the specified detail mesh using the Recast allocator.
486 ///  @param[in] dmesh  A detail mesh allocated using #rcAllocPolyMeshDetail
487 ///  @ingroup recast
488 ///  @see rcAllocPolyMeshDetail
489 void rcFreePolyMeshDetail(rcPolyMeshDetail* dmesh);
490
491 /// @}
492
493 /// Heighfield border flag.
494 /// If a heightfield region ID has this bit set, then the region is a border 
495 /// region and its spans are considered unwalkable.
496 /// (Used during the region and contour build process.)
497 /// @see rcCompactSpan::reg
498 static const unsigned short RC_BORDER_REG = 0x8000;
499
500 /// Border vertex flag.
501 /// If a region ID has this bit set, then the associated element lies on
502 /// a tile border. If a contour vertex's region ID has this bit set, the 
503 /// vertex will later be removed in order to match the segments and vertices 
504 /// at tile boundaries.
505 /// (Used during the build process.)
506 /// @see rcCompactSpan::reg, #rcContour::verts, #rcContour::rverts
507 static const int RC_BORDER_VERTEX = 0x10000;
508
509 /// Area border flag.
510 /// If a region ID has this bit set, then the associated element lies on
511 /// the border of an area.
512 /// (Used during the region and contour build process.)
513 /// @see rcCompactSpan::reg, #rcContour::verts, #rcContour::rverts
514 static const int RC_AREA_BORDER = 0x20000;
515
516 /// Contour build flags.
517 /// @see rcBuildContours
518 enum rcBuildContoursFlags
519 {
520         RC_CONTOUR_TESS_WALL_EDGES = 0x01,      ///< Tessellate solid (impassable) edges during contour simplification.
521         RC_CONTOUR_TESS_AREA_EDGES = 0x02,      ///< Tessellate edges between areas during contour simplification.
522 };
523
524 /// Applied to the region id field of contour vertices in order to extract the region id.
525 /// The region id field of a vertex may have several flags applied to it.  So the
526 /// fields value can't be used directly.
527 /// @see rcContour::verts, rcContour::rverts
528 static const int RC_CONTOUR_REG_MASK = 0xffff;
529
530 /// An value which indicates an invalid index within a mesh.
531 /// @note This does not necessarily indicate an error.
532 /// @see rcPolyMesh::polys
533 static const unsigned short RC_MESH_NULL_IDX = 0xffff;
534
535 /// Represents the null area.
536 /// When a data element is given this value it is considered to no longer be 
537 /// assigned to a usable area.  (E.g. It is unwalkable.)
538 static const unsigned char RC_NULL_AREA = 0;
539
540 /// The default area id used to indicate a walkable polygon. 
541 /// This is also the maximum allowed area id, and the only non-null area id 
542 /// recognized by some steps in the build process. 
543 static const unsigned char RC_WALKABLE_AREA = 63;
544
545 /// The value returned by #rcGetCon if the specified direction is not connected
546 /// to another span. (Has no neighbor.)
547 static const int RC_NOT_CONNECTED = 0x3f;
548
549 /// @name General helper functions
550 /// @{
551
552 /// Swaps the values of the two parameters.
553 ///  @param[in,out] a  Value A
554 ///  @param[in,out] b  Value B
555 template<class T> inline void rcSwap(T& a, T& b) { T t = a; a = b; b = t; }
556
557 /// Returns the minimum of two values.
558 ///  @param[in] a  Value A
559 ///  @param[in] b  Value B
560 ///  @return The minimum of the two values.
561 template<class T> inline T rcMin(T a, T b) { return a < b ? a : b; }
562
563 /// Returns the maximum of two values.
564 ///  @param[in] a  Value A
565 ///  @param[in] b  Value B
566 ///  @return The maximum of the two values.
567 template<class T> inline T rcMax(T a, T b) { return a > b ? a : b; }
568
569 /// Returns the absolute value.
570 ///  @param[in] a  The value.
571 ///  @return The absolute value of the specified value.
572 template<class T> inline T rcAbs(T a) { return a < 0 ? -a : a; }
573
574 /// Return the square of a value.
575 ///  @param[in] a  The value.
576 ///  @return The square of the value.
577 template<class T> inline T rcSqr(T a) { return a*a; }
578
579 /// Clamps the value to the specified range.
580 ///  @param[in] v   The value to clamp.
581 ///  @param[in] mn  The minimum permitted return value.
582 ///  @param[in] mx  The maximum permitted return value.
583 ///  @return The value, clamped to the specified range.
584 template<class T> inline T rcClamp(T v, T mn, T mx) { return v < mn ? mn : (v > mx ? mx : v); }
585
586 /// Returns the square root of the value.
587 ///  @param[in] x  The value.
588 ///  @return The square root of the vlaue.
589 float rcSqrt(float x);
590
591 /// Not documented.  Internal use only.
592 ///  @param[in] x  Not documented.
593 ///  @return Not documented.
594 inline int rcAlign4(int x) { return (x+3) & ~3; }
595
596 /// @}
597 /// @name Vector helper functions.
598 /// @{
599
600 /// Derives the cross product of two vectors. (v1 x v2)
601 ///   @param[out] dest  The cross product. [(x, y, z)]
602 ///   @param[in]  v1    A Vector [(x, y, z)]
603 ///   @param[in]  v2    A vector [(x, y, z)]
604 inline void rcVcross(float* dest, const float* v1, const float* v2)
605 {
606         dest[0] = v1[1]*v2[2] - v1[2]*v2[1];
607         dest[1] = v1[2]*v2[0] - v1[0]*v2[2];
608         dest[2] = v1[0]*v2[1] - v1[1]*v2[0];
609 }
610
611 /// Derives the dot product of two vectors. (v1 . v2)
612 ///   @param[in]  v1    A Vector [(x, y, z)]
613 ///   @param[in]  v2    A vector [(x, y, z)]
614 ///   @return The dot product.
615 inline float rcVdot(const float* v1, const float* v2)
616 {
617         return v1[0]*v2[0] + v1[1]*v2[1] + v1[2]*v2[2];
618 }
619
620 /// Performs a scaled vector addition. (v1 + (v2 * s))
621 ///   @param[out] dest  The result vector. [(x, y, z)]
622 ///   @param[in]  v1    The base vector [(x, y, z)]
623 ///   @param[in]  v2    The vector to scale and add to @p v1. [(x, y, z)]
624 ///   @param[in]  s     The amount to scale @p v2 by before adding to @p v1.
625 inline void rcVmad(float* dest, const float* v1, const float* v2, const float s)
626 {
627         dest[0] = v1[0]+v2[0]*s;
628         dest[1] = v1[1]+v2[1]*s;
629         dest[2] = v1[2]+v2[2]*s;
630 }
631
632 /// Performs a vector addition. (@p v1 + @p v2)
633 ///   @param[out] dest  The result vector. [(x, y, z)]
634 ///   @param[in]  v1    The base vector [(x, y, z)]
635 ///   @param[in]  v2    The vector to add to @p v1. [(x, y, z)]
636 inline void rcVadd(float* dest, const float* v1, const float* v2)
637 {
638         dest[0] = v1[0]+v2[0];
639         dest[1] = v1[1]+v2[1];
640         dest[2] = v1[2]+v2[2];
641 }
642
643 /// Performs a vector subtraction. (@p v1 - @p v2)
644 ///   @param[out] dest  The result vector. [(x, y, z)]
645 ///   @param[in]  v1    The base vector [(x, y, z)]
646 ///   @param[in]  v2    The vector to subtract from @p v1. [(x, y, z)]
647 inline void rcVsub(float* dest, const float* v1, const float* v2)
648 {
649         dest[0] = v1[0]-v2[0];
650         dest[1] = v1[1]-v2[1];
651         dest[2] = v1[2]-v2[2];
652 }
653
654 /// Selects the minimum value of each element from the specified vectors.
655 ///  @param[in, out] mn  A vector.  (Will be updated with the result.) [(x, y, z)]
656 ///  @param[in]      v   A vector. [(x, y, z)]
657 inline void rcVmin(float* mn, const float* v)
658 {
659         mn[0] = rcMin(mn[0], v[0]);
660         mn[1] = rcMin(mn[1], v[1]);
661         mn[2] = rcMin(mn[2], v[2]);
662 }
663
664 /// Selects the maximum value of each element from the specified vectors.
665 ///  @param[in, out] mx  A vector.  (Will be updated with the result.) [(x, y, z)]
666 ///  @param[in]      v   A vector. [(x, y, z)]
667 inline void rcVmax(float* mx, const float* v)
668 {
669         mx[0] = rcMax(mx[0], v[0]);
670         mx[1] = rcMax(mx[1], v[1]);
671         mx[2] = rcMax(mx[2], v[2]);
672 }
673
674 /// Performs a vector copy.
675 ///  @param[out] dest  The result. [(x, y, z)]
676 ///  @param[in]  v     The vector to copy [(x, y, z)]
677 inline void rcVcopy(float* dest, const float* v)
678 {
679         dest[0] = v[0];
680         dest[1] = v[1];
681         dest[2] = v[2];
682 }
683
684 /// Returns the distance between two points.
685 ///   @param[in] v1  A point. [(x, y, z)]
686 ///   @param[in] v2  A point. [(x, y, z)]
687 ///   @return The distance between the two points.
688 inline float rcVdist(const float* v1, const float* v2)
689 {
690         float dx = v2[0] - v1[0];
691         float dy = v2[1] - v1[1];
692         float dz = v2[2] - v1[2];
693         return rcSqrt(dx*dx + dy*dy + dz*dz);
694 }
695
696 /// Returns the square of the distance between two points.
697 ///   @param[in] v1  A point. [(x, y, z)]
698 ///   @param[in] v2  A point. [(x, y, z)]
699 ///   @return The square of the distance between the two points.
700 inline float rcVdistSqr(const float* v1, const float* v2)
701 {
702         float dx = v2[0] - v1[0];
703         float dy = v2[1] - v1[1];
704         float dz = v2[2] - v1[2];
705         return dx*dx + dy*dy + dz*dz;
706 }
707
708 /// Normalizes the vector.
709 ///  @param[in,out] v  The vector to normalize. [(x, y, z)]
710 inline void rcVnormalize(float* v)
711 {
712         float d = 1.0f / rcSqrt(rcSqr(v[0]) + rcSqr(v[1]) + rcSqr(v[2]));
713         v[0] *= d;
714         v[1] *= d;
715         v[2] *= d;
716 }
717
718 /// Not documented.  Internal use only.
719 ///  @param[in] p0  Not documented.
720 ///  @param[in] p1  Not documented.
721 ///  @return Not documented.
722 inline bool rcVequal(const float* p0, const float* p1)
723 {
724         static const float thr = rcSqr(1.0f/16384.0f);
725         const float d = rcVdistSqr(p0, p1);
726         return d < thr;
727 }
728
729 /// @}
730 /// @name Heightfield Functions
731 /// @see rcHeightfield
732 /// @{
733
734 /// Calculates the bounding box of an array of vertices.
735 ///  @ingroup recast
736 ///  @param[in]  verts  An array of vertices. [(x, y, z) * @p nv]
737 ///  @param[in]  nv     The number of vertices in the @p verts array.
738 ///  @param[out] bmin   The minimum bounds of the AABB. [(x, y, z)] [Units: wu]
739 ///  @param[out] bmax   The maximum bounds of the AABB. [(x, y, z)] [Units: wu]
740 void rcCalcBounds(const float* verts, int nv, float* bmin, float* bmax);
741
742 /// Calculates the grid size based on the bounding box and grid cell size.
743 ///  @ingroup recast
744 ///  @param[in]  bmin  The minimum bounds of the AABB. [(x, y, z)] [Units: wu]
745 ///  @param[in]  bmax  The maximum bounds of the AABB. [(x, y, z)] [Units: wu]
746 ///  @param[in]  cs    The xz-plane cell size. [Limit: > 0] [Units: wu]
747 ///  @param[out] w     The width along the x-axis. [Limit: >= 0] [Units: vx]
748 ///  @param[out] h     The height along the z-axis. [Limit: >= 0] [Units: vx]
749 void rcCalcGridSize(const float* bmin, const float* bmax, float cs, int* w, int* h);
750
751 /// Initializes a new heightfield.
752 ///  @ingroup recast
753 ///  @param[in,out] ctx     The build context to use during the operation.
754 ///  @param[in,out] hf      The allocated heightfield to initialize.
755 ///  @param[in]     width   The width of the field along the x-axis. [Limit: >= 0] [Units: vx]
756 ///  @param[in]     height  The height of the field along the z-axis. [Limit: >= 0] [Units: vx]
757 ///  @param[in]     bmin    The minimum bounds of the field's AABB. [(x, y, z)] [Units: wu]
758 ///  @param[in]     bmax    The maximum bounds of the field's AABB. [(x, y, z)] [Units: wu]
759 ///  @param[in]     cs      The xz-plane cell size to use for the field. [Limit: > 0] [Units: wu]
760 ///  @param[in]     ch      The y-axis cell size to use for field. [Limit: > 0] [Units: wu]
761 bool rcCreateHeightfield(rcContext* ctx, rcHeightfield& hf, int width, int height,
762                                                  const float* bmin, const float* bmax,
763                                                  float cs, float ch);
764
765 /// Sets the area id of all triangles with a slope below the specified value
766 /// to #RC_WALKABLE_AREA.
767 ///  @ingroup recast
768 ///  @param[in,out] ctx                 The build context to use during the operation.
769 ///  @param[in]     walkableSlopeAngle  The maximum slope that is considered walkable. [Limits: 0 <= value < 90] 
770 ///                                     [Units: Degrees]
771 ///  @param[in]     verts               The vertices. [(x, y, z) * @p nv]
772 ///  @param[in]     nv                  The number of vertices.
773 ///  @param[in]     tris                The triangle vertex indices. [(vertA, vertB, vertC) * @p nt]
774 ///  @param[in]     nt                  The number of triangles.
775 ///  @param[out]    areas               The triangle area ids. [Length: >= @p nt]
776 void rcMarkWalkableTriangles(rcContext* ctx, const float walkableSlopeAngle, const float* verts, int nv,
777                                                          const int* tris, int nt, unsigned char* areas); 
778
779 /// Sets the area id of all triangles with a slope greater than or equal to the specified value to #RC_NULL_AREA.
780 ///  @ingroup recast
781 ///  @param[in,out] ctx                 The build context to use during the operation.
782 ///  @param[in]     walkableSlopeAngle  The maximum slope that is considered walkable. [Limits: 0 <= value < 90] 
783 ///                                     [Units: Degrees]
784 ///  @param[in]     verts               The vertices. [(x, y, z) * @p nv]
785 ///  @param[in]     nv                  The number of vertices.
786 ///  @param[in]     tris                The triangle vertex indices. [(vertA, vertB, vertC) * @p nt]
787 ///  @param[in]     nt                  The number of triangles.
788 ///  @param[out]    areas               The triangle area ids. [Length: >= @p nt]
789 void rcClearUnwalkableTriangles(rcContext* ctx, const float walkableSlopeAngle, const float* verts, int nv,
790                                                                 const int* tris, int nt, unsigned char* areas); 
791
792 /// Adds a span to the specified heightfield.
793 ///  @ingroup recast
794 ///  @param[in,out] ctx           The build context to use during the operation.
795 ///  @param[in,out] hf            An initialized heightfield.      
796 ///  @param[in]     x             The width index where the span is to be added. 
797 ///                               [Limits: 0 <= value < rcHeightfield::width]
798 ///  @param[in]     y             The height index where the span is to be added. 
799 ///                               [Limits: 0 <= value < rcHeightfield::height]
800 ///  @param[in]     smin          The minimum height of the span. [Limit: < @p smax] [Units: vx]
801 ///  @param[in]     smax          The maximum height of the span. [Limit: <= #RC_SPAN_MAX_HEIGHT] [Units: vx]
802 ///  @param[in]     area          The area id of the span. [Limit: <= #RC_WALKABLE_AREA)
803 ///  @param[in]     flagMergeThr  The merge theshold. [Limit: >= 0] [Units: vx]
804 void rcAddSpan(rcContext* ctx, rcHeightfield& hf, const int x, const int y,
805                            const unsigned short smin, const unsigned short smax,
806                            const unsigned char area, const int flagMergeThr);
807
808 /// Rasterizes a triangle into the specified heightfield.
809 ///  @ingroup recast
810 ///  @param[in,out]  ctx           The build context to use during the operation.
811 ///  @param[in]      v0            Triangle vertex 0 [(x, y, z)]
812 ///  @param[in]      v1            Triangle vertex 1 [(x, y, z)]
813 ///  @param[in]      v2            Triangle vertex 2 [(x, y, z)]
814 ///  @param[in]      area          The area id of the triangle. [Limit: <= #RC_WALKABLE_AREA]
815 ///  @param[in, out] solid         An initialized heightfield.
816 ///  @param[in]      flagMergeThr  The distance where the walkable flag is favored over the non-walkable flag. 
817 ///                                [Limit: >= 0] [Units: vx]
818 void rcRasterizeTriangle(rcContext* ctx, const float* v0, const float* v1, const float* v2,
819                                                  const unsigned char area, rcHeightfield& solid,
820                                                  const int flagMergeThr = 1);
821
822 /// Rasterizes an indexed triangle mesh into the specified heightfield.
823 ///  @ingroup recast
824 ///  @param[in,out]  ctx           The build context to use during the operation.
825 ///  @param[in]      verts         The vertices. [(x, y, z) * @p nv]
826 ///  @param[in]      nv            The number of vertices.
827 ///  @param[in]      tris          The triangle indices. [(vertA, vertB, vertC) * @p nt]
828 ///  @param[in]      areas         The area id's of the triangles. [Limit: <= #RC_WALKABLE_AREA] [Size: @p nt]
829 ///  @param[in]      nt            The number of triangles.
830 ///  @param[in, out] solid         An initialized heightfield.
831 ///  @param[in]      flagMergeThr  The distance where the walkable flag is favored over the non-walkable flag. 
832 ///                                [Limit: >= 0] [Units: vx]
833 void rcRasterizeTriangles(rcContext* ctx, const float* verts, const int nv,
834                                                   const int* tris, const unsigned char* areas, const int nt,
835                                                   rcHeightfield& solid, const int flagMergeThr = 1);
836
837 /// Rasterizes an indexed triangle mesh into the specified heightfield.
838 ///  @ingroup recast
839 ///  @param[in,out]  ctx           The build context to use during the operation.
840 ///  @param[in]      verts         The vertices. [(x, y, z) * @p nv]
841 ///  @param[in]      nv            The number of vertices.
842 ///  @param[in]      tris          The triangle indices. [(vertA, vertB, vertC) * @p nt]
843 ///  @param[in]      areas         The area id's of the triangles. [Limit: <= #RC_WALKABLE_AREA] [Size: @p nt]
844 ///  @param[in]      nt            The number of triangles.
845 ///  @param[in, out] solid         An initialized heightfield.
846 ///  @param[in]      flagMergeThr  The distance where the walkable flag is favored over the non-walkable flag. 
847 ///                                [Limit: >= 0] [Units: vx]
848 void rcRasterizeTriangles(rcContext* ctx, const float* verts, const int nv,
849                                                   const unsigned short* tris, const unsigned char* areas, const int nt,
850                                                   rcHeightfield& solid, const int flagMergeThr = 1);
851
852 /// Rasterizes triangles into the specified heightfield.
853 ///  @ingroup recast
854 ///  @param[in,out]  ctx           The build context to use during the operation.
855 ///  @param[in]      verts         The triangle vertices. [(ax, ay, az, bx, by, bz, cx, by, cx) * @p nt]
856 ///  @param[in]      areas         The area id's of the triangles. [Limit: <= #RC_WALKABLE_AREA] [Size: @p nt]
857 ///  @param[in]      nt            The number of triangles.
858 ///  @param[in, out] solid         An initialized heightfield.
859 ///  @param[in]      flagMergeThr  The distance where the walkable flag is favored over the non-walkable flag. 
860 ///                                [Limit: >= 0] [Units: vx]
861 void rcRasterizeTriangles(rcContext* ctx, const float* verts, const unsigned char* areas, const int nt,
862                                                   rcHeightfield& solid, const int flagMergeThr = 1);
863
864 /// Marks non-walkable spans as walkable if their maximum is within @p walkableClimp of a walkable neihbor. 
865 ///  @ingroup recast
866 ///  @param[in,out] ctx            The build context to use during the operation.
867 ///  @param[in]     walkableClimb  Maximum ledge height that is considered to still be traversable. 
868 ///                                [Limit: >=0] [Units: vx]
869 ///  @param[in,out] solid          A fully built heightfield.  (All spans have been added.)
870 void rcFilterLowHangingWalkableObstacles(rcContext* ctx, const int walkableClimb, rcHeightfield& solid);
871
872 /// Marks spans that are ledges as not-walkable. 
873 ///  @ingroup recast
874 ///  @param[in,out] ctx             The build context to use during the operation.
875 ///  @param[in]     walkableHeight  Minimum floor to 'ceiling' height that will still allow the floor area to 
876 ///                                 be considered walkable. [Limit: >= 3] [Units: vx]
877 ///  @param[in]     walkableClimb   Maximum ledge height that is considered to still be traversable. 
878 ///                                 [Limit: >=0] [Units: vx]
879 ///  @param[in,out] solid          A fully built heightfield.  (All spans have been added.)
880 void rcFilterLedgeSpans(rcContext* ctx, const int walkableHeight,
881                                                 const int walkableClimb, rcHeightfield& solid);
882
883 /// Marks walkable spans as not walkable if the clearence above the span is less than the specified height. 
884 ///  @ingroup recast
885 ///  @param[in,out] ctx             The build context to use during the operation.
886 ///  @param[in]     walkableHeight  Minimum floor to 'ceiling' height that will still allow the floor area to 
887 ///                                 be considered walkable. [Limit: >= 3] [Units: vx]
888 ///  @param[in,out] solid           A fully built heightfield.  (All spans have been added.)
889 void rcFilterWalkableLowHeightSpans(rcContext* ctx, int walkableHeight, rcHeightfield& solid);
890
891 /// Returns the number of spans contained in the specified heightfield.
892 ///  @ingroup recast
893 ///  @param[in,out] ctx  The build context to use during the operation.
894 ///  @param[in]     hf   An initialized heightfield.
895 ///  @returns The number of spans in the heightfield.
896 int rcGetHeightFieldSpanCount(rcContext* ctx, rcHeightfield& hf);
897
898 /// @}
899 /// @name Compact Heightfield Functions
900 /// @see rcCompactHeightfield
901 /// @{
902
903 /// Builds a compact heightfield representing open space, from a heightfield representing solid space.
904 ///  @ingroup recast
905 ///  @param[in,out] ctx             The build context to use during the operation.
906 ///  @param[in]     walkableHeight  Minimum floor to 'ceiling' height that will still allow the floor area 
907 ///                                 to be considered walkable. [Limit: >= 3] [Units: vx]
908 ///  @param[in]     walkableClimb   Maximum ledge height that is considered to still be traversable. 
909 ///                                 [Limit: >=0] [Units: vx]
910 ///  @param[in]     hf              The heightfield to be compacted.
911 ///  @param[out]    chf             The resulting compact heightfield. (Must be pre-allocated.)
912 ///  @returns True if the operation completed successfully.
913 bool rcBuildCompactHeightfield(rcContext* ctx, const int walkableHeight, const int walkableClimb,
914                                                            rcHeightfield& hf, rcCompactHeightfield& chf);
915
916 /// Erodes the walkable area within the heightfield by the specified radius. 
917 ///  @ingroup recast
918 ///  @param[in,out] ctx     The build context to use during the operation.
919 ///  @param[in]     radius  The radius of erosion. [Limits: 0 < value < 255] [Units: vx]
920 ///  @param[in,out] chf     The populated compact heightfield to erode.
921 ///  @returns True if the operation completed successfully.
922 bool rcErodeWalkableArea(rcContext* ctx, int radius, rcCompactHeightfield& chf);
923
924 /// Applies a median filter to walkable area types (based on area id), removing noise.
925 ///  @ingroup recast
926 ///  @param[in,out] ctx  The build context to use during the operation.
927 ///  @param[in,out] chf  A populated compact heightfield.
928 ///  @returns True if the operation completed successfully.
929 bool rcMedianFilterWalkableArea(rcContext* ctx, rcCompactHeightfield& chf);
930
931 /// Applies an area id to all spans within the specified bounding box. (AABB) 
932 ///  @ingroup recast
933 ///  @param[in,out] ctx     The build context to use during the operation.
934 ///  @param[in]     bmin    The minimum of the bounding box. [(x, y, z)]
935 ///  @param[in]     bmax    The maximum of the bounding box. [(x, y, z)]
936 ///  @param[in]     areaId  The area id to apply. [Limit: <= #RC_WALKABLE_AREA]
937 ///  @param[in,out] chf     A populated compact heightfield.
938 void rcMarkBoxArea(rcContext* ctx, const float* bmin, const float* bmax, unsigned char areaId,
939                                    rcCompactHeightfield& chf);
940
941 /// Applies the area id to the all spans within the specified convex polygon. 
942 ///  @ingroup recast
943 ///  @param[in,out] ctx     The build context to use during the operation.
944 ///  @param[in]     verts   The vertices of the polygon [Fomr: (x, y, z) * @p nverts]
945 ///  @param[in]     nverts  The number of vertices in the polygon.
946 ///  @param[in]     hmin    The height of the base of the polygon.
947 ///  @param[in]     hmax    The height of the top of the polygon.
948 ///  @param[in]     areaId  The area id to apply. [Limit: <= #RC_WALKABLE_AREA]
949 ///  @param[in,out] chf     A populated compact heightfield.
950 void rcMarkConvexPolyArea(rcContext* ctx, const float* verts, const int nverts,
951                                                   const float hmin, const float hmax, unsigned char areaId,
952                                                   rcCompactHeightfield& chf);
953
954 /// Applies the area id to all spans within the specified cylinder.
955 ///  @ingroup recast
956 ///  @param[in,out] ctx     The build context to use during the operation.
957 ///  @param[in]     pos     The center of the base of the cylinder. [Form: (x, y, z)] 
958 ///  @param[in]     r       The radius of the cylinder.
959 ///  @param[in]     h       The height of the cylinder.
960 ///  @param[in]     areaId  The area id to apply. [Limit: <= #RC_WALKABLE_AREA]
961 ///  @param[in,out] chf     A populated compact heightfield.
962 void rcMarkCylinderArea(rcContext* ctx, const float* pos,
963                                                 const float r, const float h, unsigned char areaId,
964                                                 rcCompactHeightfield& chf);
965
966 /// Builds the distance field for the specified compact heightfield. 
967 ///  @ingroup recast
968 ///  @param[in,out] ctx  The build context to use during the operation.
969 ///  @param[in,out] chf  A populated compact heightfield.
970 ///  @returns True if the operation completed successfully.
971 bool rcBuildDistanceField(rcContext* ctx, rcCompactHeightfield& chf);
972
973 /// Builds region data for the heightfield using watershed partitioning. 
974 ///  @ingroup recast
975 ///  @param[in,out] ctx          The build context to use during the operation.
976 ///  @param[in,out] chf          A populated compact heightfield.
977 ///  @param[in] borderSize       The size of the non-navigable border around the heightfield. [Limit: >=0] [Units: vx]
978 ///  @param[in] minRegionArea    The minimum number of cells allowed to form isolated island areas. [Limit: >=0] 
979 ///                              [Units: vx].
980 ///  @param[in] mergeRegionArea  Any regions with a span count smaller than this value will, if possible, 
981 ///                              be merged with larger regions. [Limit: >=0] [Units: vx] 
982 ///  @returns True if the operation completed successfully.
983 bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf,
984                                         const int borderSize, const int minRegionArea, const int mergeRegionArea);
985
986 /// Builds region data for the heightfield using simple monotone partitioning.
987 ///  @ingroup recast 
988 ///  @param[in,out] ctx          The build context to use during the operation.
989 ///  @param[in,out] chf          A populated compact heightfield.
990 ///  @param[in] borderSize       The size of the non-navigable border around the heightfield. [Limit: >=0] [Units: vx]
991 ///  @param[in] minRegionArea    The minimum number of cells allowed to form isolated island areas. [Limit: >=0] 
992 ///                              [Units: vx].
993 ///  @param[in] mergeRegionArea  Any regions with a span count smaller than this value will, if possible, 
994 ///                              be merged with larger regions. [Limit: >=0] [Units: vx] 
995 ///  @returns True if the operation completed successfully.
996 bool rcBuildRegionsMonotone(rcContext* ctx, rcCompactHeightfield& chf,
997                                                         const int borderSize, const int minRegionArea, const int mergeRegionArea);
998
999
1000 /// Sets the neighbor connection data for the specified direction.
1001 ///  @param[in] s    The span to update.
1002 ///  @param[in] dir  The direction to set. [Limits: 0 <= value < 4]
1003 ///  @param[in] i    The index of the neighbor span.
1004 inline void rcSetCon(rcCompactSpan& s, int dir, int i)
1005 {
1006         const unsigned int shift = (unsigned int)dir*6;
1007         unsigned int con = s.con;
1008         s.con = (con & ~(0x3f << shift)) | (((unsigned int)i & 0x3f) << shift);
1009 }
1010
1011 /// Gets neighbor connection data for the specified direction.
1012 ///  @param[in] s    The span to check.
1013 ///  @param[in] dir  The direction to check. [Limits: 0 <= value < 4]
1014 ///  @return The neighbor connection data for the specified direction,
1015 ///          or #RC_NOT_CONNECTED if there is no connection.
1016 inline int rcGetCon(const rcCompactSpan& s, int dir)
1017 {
1018         const unsigned int shift = (unsigned int)dir*6;
1019         return (s.con >> shift) & 0x3f;
1020 }
1021
1022 /// Gets the standard width (x-axis) offset for the specified direction.
1023 ///  @param[in] dir  The direction. [Limits: 0 <= value < 4]
1024 ///  @return The width offset to apply to the current cell position to move
1025 ///          in the direction.
1026 inline int rcGetDirOffsetX(int dir)
1027 {
1028         const int offset[4] = { -1, 0, 1, 0, };
1029         return offset[dir&0x03];
1030 }
1031
1032 /// Gets the standard height (z-axis) offset for the specified direction.
1033 ///  @param[in] dir  The direction. [Limits: 0 <= value < 4]
1034 ///  @return The height offset to apply to the current cell position to move
1035 ///          in the direction.
1036 inline int rcGetDirOffsetY(int dir)
1037 {
1038         const int offset[4] = { 0, 1, 0, -1 };
1039         return offset[dir&0x03];
1040 }
1041
1042 /// @}
1043 /// @name Layer, Contour, Polymesh, and Detail Mesh Functions
1044 /// @see rcHeightfieldLayer, rcContourSet, rcPolyMesh, rcPolyMeshDetail
1045 /// @{
1046
1047 /// Builds a layer set from the specified compact heightfield.
1048 ///  @ingroup recast
1049 ///  @param[in,out] ctx             The build context to use during the operation.
1050 ///  @param[in]     chf             A fully built compact heightfield.
1051 ///  @param[in]     borderSize      The size of the non-navigable border around the heightfield. [Limit: >=0] 
1052 ///                                 [Units: vx]
1053 ///  @param[in]     walkableHeight  Minimum floor to 'ceiling' height that will still allow the floor area 
1054 ///                                 to be considered walkable. [Limit: >= 3] [Units: vx]
1055 ///  @param[out]    lset            The resulting layer set. (Must be pre-allocated.)
1056 ///  @returns True if the operation completed successfully.
1057 bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf, 
1058                                                           const int borderSize, const int walkableHeight,
1059                                                           rcHeightfieldLayerSet& lset);
1060
1061 /// Builds a contour set from the region outlines in the provided compact heightfield.
1062 ///  @ingroup recast
1063 ///  @param[in,out] ctx      The build context to use during the operation.
1064 ///  @param[in] chf          A fully built compact heightfield.
1065 ///  @param[in] maxError     The maximum distance a simplfied contour's border edges should deviate 
1066 ///                          the original raw contour. [Limit: >=0] [Units: wu]
1067 ///  @param[in] maxEdgeLen   The maximum allowed length for contour edges along the border of the mesh. 
1068 ///                          [Limit: >=0] [Units: vx]
1069 ///  @param[out] cset        The resulting contour set. (Must be pre-allocated.)
1070 ///  @param[in]  buildFlags  The build flags. (See: #rcBuildContoursFlags)
1071 ///  @returns True if the operation completed successfully.
1072 bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf,
1073                                          const float maxError, const int maxEdgeLen,
1074                                          rcContourSet& cset, const int flags = RC_CONTOUR_TESS_WALL_EDGES);
1075
1076 /// Builds a polygon mesh from the provided contours.
1077 ///  @ingroup recast
1078 ///  @param[in,out] ctx     The build context to use during the operation.
1079 ///  @param[in]     cset    A fully built contour set.
1080 ///  @param[in]     nvp     The maximum number of vertices allowed for polygons generated during the 
1081 ///                         contour to polygon conversion process. [Limit: >= 3] 
1082 ///  @param[out]    mesh    The resulting polygon mesh. (Must be re-allocated.)
1083 ///  @returns True if the operation completed successfully.
1084 bool rcBuildPolyMesh(rcContext* ctx, rcContourSet& cset, const int nvp, rcPolyMesh& mesh);
1085
1086 /// Merges multiple polygon meshes into a single mesh.
1087 ///  @ingroup recast
1088 ///  @param[in,out] ctx      The build context to use during the operation.
1089 ///  @param[in]     meshes   An array of polygon meshes to merge. [Size: @p nmeshes]
1090 ///  @param[in]     nmeshes  The number of polygon meshes in the meshes array.
1091 ///  @param[in]     mesh     The resulting polygon mesh. (Must be pre-allocated.)
1092 ///  @returns True if the operation completed successfully.
1093 bool rcMergePolyMeshes(rcContext* ctx, rcPolyMesh** meshes, const int nmeshes, rcPolyMesh& mesh);
1094
1095 /// Builds a detail mesh from the provided polygon mesh.
1096 ///  @ingroup recast
1097 ///  @param[in,out] ctx             The build context to use during the operation.
1098 ///  @param[in]     mesh            A fully built polygon mesh.
1099 ///  @param[in]     chf             The compact heightfield used to build the polygon mesh.
1100 ///  @param[in]     sampleDist      Sets the distance to use when samping the heightfield. [Limit: >=0] [Units: wu]
1101 ///  @param[in]     sampleMaxError  The maximum distance the detail mesh surface should deviate from 
1102 ///                                 heightfield data. [Limit: >=0] [Units: wu]
1103 ///  @param[out]    dmesh           The resulting detail mesh.  (Must be pre-allocated.)
1104 ///  @returns True if the operation completed successfully.
1105 bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompactHeightfield& chf,
1106                                                    const float sampleDist, const float sampleMaxError,
1107                                                    rcPolyMeshDetail& dmesh);
1108
1109 /// Merges multiple detail meshes into a single detail mesh.
1110 ///  @ingroup recast
1111 ///  @param[in,out] ctx      The build context to use during the operation.
1112 ///  @param[in]     meshes   An array of detail meshes to merge. [Size: @p nmeshes]
1113 ///  @param[in]     nmeshes  The number of detail meshes in the meshes array.
1114 ///  @param[out]    mesh     The resulting detail mesh. (Must be pre-allocated.)
1115 ///  @returns True if the operation completed successfully.
1116 bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int nmeshes, rcPolyMeshDetail& mesh);
1117
1118 bool buildMeshAdjacency(unsigned short* polys, const int npolys, const int nverts, const int vertsPerPoly);
1119
1120 /// @}
1121
1122 #endif // RECAST_H
1123
1124 ///////////////////////////////////////////////////////////////////////////
1125
1126 // Due to the large amount of detail documentation for this file, 
1127 // the content normally located at the end of the header file has been separated
1128 // out to a file in /Docs/Extern.