synched with trunk at revision 36569
[blender.git] / extern / recastnavigation / Recast / Include / Recast.h
1 //
2 // Copyright (c) 2009 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 units of the parameters are specified in parenthesis as follows:
23 // (vx) voxels, (wu) world units
24 struct rcConfig
25 {
26         int width, height;                              // Dimensions of the rasterized heighfield (vx)
27         int tileSize;                                   // Width and Height of a tile (vx)
28         int borderSize;                                 // Non-navigable Border around the heightfield (vx)
29         float cs, ch;                                   // Grid cell size and height (wu)
30         float bmin[3], bmax[3];                 // Grid bounds (wu)
31         float walkableSlopeAngle;               // Maximum walkble slope angle in degrees.
32         int walkableHeight;                             // Minimum height where the agent can still walk (vx)
33         int walkableClimb;                              // Maximum height between grid cells the agent can climb (vx)
34         int walkableRadius;                             // Radius of the agent in cells (vx)
35         int maxEdgeLen;                                 // Maximum contour edge length (vx)
36         float maxSimplificationError;   // Maximum distance error from contour to cells (vx)
37         int minRegionSize;                              // Minimum regions size. Smaller regions will be deleted (vx)
38         int mergeRegionSize;                    // Minimum regions size. Smaller regions will be merged (vx)
39         int maxVertsPerPoly;                    // Max number of vertices per polygon
40         float detailSampleDist;                 // Detail mesh sample spacing.
41         float detailSampleMaxError;             // Detail mesh simplification max sample error.
42 };
43
44 // Heightfield span.
45 struct rcSpan
46 {
47         unsigned int smin : 15;                 // Span min height.
48         unsigned int smax : 15;                 // Span max height.
49         unsigned int flags : 2;                 // Span flags.
50         rcSpan* next;                                   // Next span in column.
51 };
52
53 static const int RC_SPANS_PER_POOL = 2048;
54
55 // Memory pool used for quick span allocation.
56 struct rcSpanPool
57 {
58         rcSpanPool* next;       // Pointer to next pool.
59         rcSpan items[1];        // Array of spans (size RC_SPANS_PER_POOL).
60 };
61
62 // Dynamic span-heightfield.
63 struct rcHeightfield
64 {
65         inline rcHeightfield() : width(0), height(0), spans(0), pools(0), freelist(0) {}
66         inline ~rcHeightfield()
67         {
68                 // Delete span array.
69                 delete [] spans;
70                 // Delete span pools.
71                 while (pools)
72                 {
73                         rcSpanPool* next = pools->next;
74                         delete [] reinterpret_cast<unsigned char*>(pools);
75                         pools = next;
76                 }
77         }
78         int width, height;                      // Dimension of the heightfield.
79         float bmin[3], bmax[3];         // Bounding box of the heightfield
80         float cs, ch;                           // Cell size and height.
81         rcSpan** spans;                         // Heightfield of spans (width*height).
82         rcSpanPool* pools;                      // Linked list of span pools.
83         rcSpan* freelist;                       // Pointer to next free span.
84 };
85
86 struct rcCompactCell
87 {
88         unsigned int index : 24;        // Index to first span in column.
89         unsigned int count : 8;         // Number of spans in this column.
90 };
91
92 struct rcCompactSpan
93 {
94         unsigned short y;                       // Bottom coordinate of the span.
95         unsigned short reg;                     // Region ID
96         unsigned short dist;            // Distance to border
97         unsigned short con;                     // Connections to neighbour cells.
98         unsigned char h;                        // Height of the span.
99         unsigned char flags;            // Flags.
100 };
101
102 // Compact static heightfield. 
103 struct rcCompactHeightfield
104 {
105         inline rcCompactHeightfield() : maxDistance(0), maxRegions(0), cells(0), spans(0) {}
106         inline ~rcCompactHeightfield() { delete [] cells; delete [] spans; }
107         int width, height;                                      // Width and height of the heighfield.
108         int spanCount;                                          // Number of spans in the heightfield.
109         int walkableHeight, walkableClimb;      // Agent properties.
110         unsigned short maxDistance;                     // Maximum distance value stored in heightfield.
111         unsigned short maxRegions;                      // Maximum Region Id stored in heightfield.
112         float bmin[3], bmax[3];                         // Bounding box of the heightfield.
113         float cs, ch;                                           // Cell size and height.
114         rcCompactCell* cells;                           // Pointer to width*height cells.
115         rcCompactSpan* spans;                           // Pointer to spans.
116 };
117
118 struct rcContour
119 {
120         inline rcContour() : verts(0), nverts(0), rverts(0), nrverts(0) { }
121         inline ~rcContour() { delete [] verts; delete [] rverts; }
122         int* verts;                     // Vertex coordinates, each vertex contains 4 components.
123         int nverts;                     // Number of vertices.
124         int* rverts;            // Raw vertex coordinates, each vertex contains 4 components.
125         int nrverts;            // Number of raw vertices.
126         unsigned short reg;     // Region ID of the contour.
127 };
128
129 struct rcContourSet
130 {
131         inline rcContourSet() : conts(0), nconts(0) {}
132         inline ~rcContourSet() { delete [] conts; }
133         rcContour* conts;               // Pointer to all contours.
134         int nconts;                             // Number of contours.
135         float bmin[3], bmax[3]; // Bounding box of the heightfield.
136         float cs, ch;                   // Cell size and height.
137 };
138
139 // Polymesh store a connected mesh of polygons.
140 // The polygons are store in an array where each polygons takes
141 // 'nvp*2' elements. The first 'nvp' elements are indices to vertices
142 // and the second 'nvp' elements are indices to neighbour polygons.
143 // If a polygona has less than 'bvp' vertices, the remaining indices
144 // are set os 0xffff. If an polygon edge does not have a neighbour
145 // the neighbour index is set to 0xffff.
146 // Vertices can be transformed into world space as follows:
147 //   x = bmin[0] + verts[i*3+0]*cs;
148 //   y = bmin[1] + verts[i*3+1]*ch;
149 //   z = bmin[2] + verts[i*3+2]*cs;
150 struct rcPolyMesh
151 {
152         inline rcPolyMesh() : verts(0), polys(0), regs(0), nverts(0), npolys(0), nvp(3) {}
153         inline ~rcPolyMesh() { delete [] verts; delete [] polys; delete [] regs; }
154         unsigned short* verts;  // Vertices of the mesh, 3 elements per vertex.
155         unsigned short* polys;  // Polygons of the mesh, nvp*2 elements per polygon.
156         unsigned short* regs;   // Regions of the polygons.
157         int nverts;                             // Number of vertices.
158         int npolys;                             // Number of polygons.
159         int nvp;                                // Max number of vertices per polygon.
160         float bmin[3], bmax[3]; // Bounding box of the mesh.
161         float cs, ch;                   // Cell size and height.
162 };
163
164 // Detail mesh generated from a rcPolyMesh.
165 // Each submesh represents a polygon in the polymesh and they are stored in
166 // excatly same order. Each submesh is described as 4 values:
167 // base vertex, vertex count, base triangle, triangle count. That is,
168 //   const unsigned char* t = &dtl.tris[(tbase+i)*3]; and
169 //   const float* v = &dtl.verts[(vbase+t[j])*3];
170 // If the input polygon has 'n' vertices, those vertices are first in the
171 // submesh vertex list. This allows to compres the mesh by not storing the
172 // first vertices and using the polymesh vertices instead.
173
174 struct rcPolyMeshDetail
175 {
176         inline rcPolyMeshDetail() :
177                 meshes(0), verts(0), tris(0),
178                 nmeshes(0), nverts(0), ntris(0) {}
179         inline ~rcPolyMeshDetail()
180         {
181                 delete [] meshes; delete [] verts; delete [] tris;
182         }
183         
184         unsigned short* meshes; // Pointer to all mesh data.
185         float* verts;                   // Pointer to all vertex data.
186         unsigned char* tris;    // Pointer to all triangle data.
187         int nmeshes;                    // Number of meshes.
188         int nverts;                             // Number of total vertices.
189         int ntris;                              // Number of triangles.
190 };
191
192
193 // Simple dynamic array ints.
194 class rcIntArray
195 {
196         int* m_data;
197         int m_size, m_cap;
198 public:
199         inline rcIntArray() : m_data(0), m_size(0), m_cap(0) {}
200         inline rcIntArray(int n) : m_data(0), m_size(0), m_cap(n) { m_data = new int[n]; }
201         inline ~rcIntArray() { delete [] m_data; }
202         void resize(int n);
203         inline void push(int item) { resize(m_size+1); m_data[m_size-1] = item; }
204         inline int pop() { if (m_size > 0) m_size--; return m_data[m_size]; }
205         inline const int& operator[](int i) const { return m_data[i]; }
206         inline int& operator[](int i) { return m_data[i]; }
207         inline int size() const { return m_size; }
208 };
209
210 enum rcSpanFlags
211 {
212         RC_WALKABLE = 0x01,
213         RC_REACHABLE = 0x02,
214 };
215
216 // If heightfield region ID has the following bit set, the region is on border area
217 // and excluded from many calculations.
218 static const unsigned short RC_BORDER_REG = 0x8000;
219
220 // If contour region ID has the following bit set, the vertex will be later
221 // removed in order to match the segments and vertices at tile boundaries.
222 static const int RC_BORDER_VERTEX = 0x10000;
223
224 // Compact span neighbour helpers.
225 inline int rcGetCon(const rcCompactSpan& s, int dir)
226 {
227         return (s.con >> (dir*4)) & 0xf;
228 }
229
230 inline int rcGetDirOffsetX(int dir)
231 {
232         const int offset[4] = { -1, 0, 1, 0, };
233         return offset[dir&0x03];
234 }
235
236 inline int rcGetDirOffsetY(int dir)
237 {
238         const int offset[4] = { 0, 1, 0, -1 };
239         return offset[dir&0x03];
240 }
241
242 // Common helper functions
243 template<class T> inline void rcSwap(T& a, T& b) { T t = a; a = b; b = t; }
244 template<class T> inline T rcMin(T a, T b) { return a < b ? a : b; }
245 template<class T> inline T rcMax(T a, T b) { return a > b ? a : b; }
246 template<class T> inline T rcAbs(T a) { return a < 0 ? -a : a; }
247 template<class T> inline T rcSqr(T a) { return a*a; }
248 template<class T> inline T rcClamp(T v, T mn, T mx) { return v < mn ? mn : (v > mx ? mx : v); }
249
250 // Common vector helper functions.
251 inline void vcross(float* dest, const float* v1, const float* v2)
252 {
253         dest[0] = v1[1]*v2[2] - v1[2]*v2[1];
254         dest[1] = v1[2]*v2[0] - v1[0]*v2[2];
255         dest[2] = v1[0]*v2[1] - v1[1]*v2[0]; 
256 }
257
258 inline float vdot(const float* v1, const float* v2)
259 {
260         return v1[0]*v2[0] + v1[1]*v2[1] + v1[2]*v2[2];
261 }
262
263 inline void vmad(float* dest, const float* v1, const float* v2, const float s)
264 {
265         dest[0] = v1[0]+v2[0]*s;
266         dest[1] = v1[1]+v2[1]*s;
267         dest[2] = v1[2]+v2[2]*s;
268 }
269
270 inline void vadd(float* dest, const float* v1, const float* v2)
271 {
272         dest[0] = v1[0]+v2[0];
273         dest[1] = v1[1]+v2[1];
274         dest[2] = v1[2]+v2[2];
275 }
276
277 inline void vsub(float* dest, const float* v1, const float* v2)
278 {
279         dest[0] = v1[0]-v2[0];
280         dest[1] = v1[1]-v2[1];
281         dest[2] = v1[2]-v2[2];
282 }
283
284 inline void vmin(float* mn, const float* v)
285 {
286         mn[0] = rcMin(mn[0], v[0]);
287         mn[1] = rcMin(mn[1], v[1]);
288         mn[2] = rcMin(mn[2], v[2]);
289 }
290
291 inline void vmax(float* mx, const float* v)
292 {
293         mx[0] = rcMax(mx[0], v[0]);
294         mx[1] = rcMax(mx[1], v[1]);
295         mx[2] = rcMax(mx[2], v[2]);
296 }
297
298 inline void vcopy(float* dest, const float* v)
299 {
300         dest[0] = v[0];
301         dest[1] = v[1];
302         dest[2] = v[2];
303 }
304
305 inline float vdist(const float* v1, const float* v2)
306 {
307         float dx = v2[0] - v1[0];
308         float dy = v2[1] - v1[1];
309         float dz = v2[2] - v1[2];
310         return sqrtf(dx*dx + dy*dy + dz*dz);
311 }
312
313 inline float vdistSqr(const float* v1, const float* v2)
314 {
315         float dx = v2[0] - v1[0];
316         float dy = v2[1] - v1[1];
317         float dz = v2[2] - v1[2];
318         return dx*dx + dy*dy + dz*dz;
319 }
320
321 inline void vnormalize(float* v)
322 {
323         float d = 1.0f / sqrtf(rcSqr(v[0]) + rcSqr(v[1]) + rcSqr(v[2]));
324         v[0] *= d;
325         v[1] *= d;
326         v[2] *= d;
327 }
328
329 inline bool vequal(const float* p0, const float* p1)
330 {
331         static const float thr = rcSqr(1.0f/16384.0f);
332         const float d = vdistSqr(p0, p1);
333         return d < thr;
334 }
335
336
337 // Calculated bounding box of array of vertices.
338 // Params:
339 //      verts - (in) array of vertices
340 //      nv - (in) vertex count
341 //      bmin, bmax - (out) bounding box
342 void rcCalcBounds(const float* verts, int nv, float* bmin, float* bmax);
343
344 // Calculates grid size based on bounding box and grid cell size.
345 // Params:
346 //      bmin, bmax - (in) bounding box
347 //      cs - (in) grid cell size
348 //      w - (out) grid width
349 //      h - (out) grid height
350 void rcCalcGridSize(const float* bmin, const float* bmax, float cs, int* w, int* h);
351
352 // Creates and initializes new heightfield.
353 // Params:
354 //      hf - (in/out) heightfield to initialize.
355 //      width - (in) width of the heightfield.
356 //      height - (in) height of the heightfield.
357 //      bmin, bmax - (in) bounding box of the heightfield
358 //      cs - (in) grid cell size
359 //      ch - (in) grid cell height
360 bool rcCreateHeightfield(rcHeightfield& hf, int width, int height,
361                                                  const float* bmin, const float* bmax,
362                                                  float cs, float ch);
363
364 // Sets the WALKABLE flag for every triangle whose slope is below
365 // the maximun walkable slope angle.
366 // Params:
367 //      walkableSlopeAngle - (in) maximun slope angle in degrees.
368 //      verts - (in) array of vertices
369 //      nv - (in) vertex count
370 //      tris - (in) array of triangle vertex indices
371 //      nt - (in) triangle count
372 //      flags - (out) array of triangle flags
373 void rcMarkWalkableTriangles(const float walkableSlopeAngle,
374                                                          const float* verts, int nv,
375                                                          const int* tris, int nt,
376                                                          unsigned char* flags); 
377
378 // Rasterizes a triangle into heightfield spans.
379 // Params:
380 //      v0,v1,v2 - (in) the vertices of the triangle.
381 //      flags - (in) triangle flags (uses WALKABLE)
382 //      solid - (in) heighfield where the triangle is rasterized
383 void rcRasterizeTriangle(const float* v0, const float* v1, const float* v2,
384                                                  unsigned char flags, rcHeightfield& solid);
385
386 // Rasterizes the triangles into heightfield spans.
387 // Params:
388 //      verts - (in) array of vertices
389 //      nv - (in) vertex count
390 //      tris - (in) array of triangle vertex indices
391 //      norms - (in) array of triangle normals
392 //      flags - (in) array of triangle flags (uses WALKABLE)
393 //      nt - (in) triangle count
394 //      solid - (in) heighfield where the triangles are rasterized
395 void rcRasterizeTriangles(const float* verts, int nv,
396                                                   const int* tris, const unsigned char* flags, int nt,
397                                                   rcHeightfield& solid);
398
399 // Removes WALKABLE flag from all spans that are at ledges. This filtering
400 // removes possible overestimation of the conservative voxelization so that
401 // the resulting mesh will not have regions hanging in air over ledges.
402 // Params:
403 //      walkableHeight - (in) minimum height where the agent can still walk
404 //      walkableClimb - (in) maximum height between grid cells the agent can climb
405 //      solid - (in/out) heightfield describing the solid space
406 void rcFilterLedgeSpans(const int walkableHeight,
407                                                 const int walkableClimb,
408                                                 rcHeightfield& solid);
409
410 // Removes WALKABLE flag from all spans which have smaller than
411 // 'walkableHeight' clearane above them.
412 // Params:
413 //      walkableHeight - (in) minimum height where the agent can still walk
414 //      solid - (in/out) heightfield describing the solid space
415 void rcFilterWalkableLowHeightSpans(int walkableHeight,
416                                                                         rcHeightfield& solid);
417
418 // Marks spans which are reachable from any of the topmost spans.
419 // Params:
420 //      walkableHeight - (in) minimum height where the agent can still walk
421 //      walkableClimb - (in) maximum height between grid cells the agent can climb
422 //      solid - (in/out) heightfield describing the solid space
423 // Returns false if operation ran out of memory.
424 bool rcMarkReachableSpans(const int walkableHeight,
425                                                   const int walkableClimb,
426                                                   rcHeightfield& solid);
427
428 // Builds compact representation of the heightfield.
429 // Params:
430 //      walkableHeight - (in) minimum height where the agent can still walk
431 //      walkableClimb - (in) maximum height between grid cells the agent can climb
432 //      hf - (in) heightfield to be compacted
433 //      chf - (out) compact heightfield representing the open space.
434 // Returns false if operation ran out of memory.
435 bool rcBuildCompactHeightfield(const int walkableHeight, const int walkableClimb,
436                                                            unsigned char flags,
437                                                            rcHeightfield& hf,
438                                                            rcCompactHeightfield& chf);
439
440 // Builds distance field and stores it into the combat heightfield.
441 // Params:
442 //      chf - (in/out) compact heightfield representing the open space.
443 // Returns false if operation ran out of memory.
444 bool rcBuildDistanceField(rcCompactHeightfield& chf);
445
446 // Divides the walkable heighfied into simple regions.
447 // Each region has only one contour and no overlaps.
448 // The regions are stored in the compact heightfield 'reg' field.
449 // The regions will be shrinked by the radius of the agent.
450 // The process sometimes creates small regions. The parameter
451 // 'minRegionSize' specifies the smallest allowed regions size.
452 // If the area of a regions is smaller than allowed, the regions is
453 // removed or merged to neighbour region. 
454 // Params:
455 //      chf - (in/out) compact heightfield representing the open space.
456 //      walkableRadius - (in) the radius of the agent.
457 //      minRegionSize - (in) the smallest allowed regions size.
458 //      maxMergeRegionSize - (in) the largest allowed regions size which can be merged.
459 // Returns false if operation ran out of memory.
460 bool rcBuildRegions(rcCompactHeightfield& chf,
461                                         int walkableRadius, int borderSize,
462                                         int minRegionSize, int mergeRegionSize);
463
464 // Builds simplified contours from the regions outlines.
465 // Params:
466 //      chf - (in) compact heightfield which has regions set.
467 //      maxError - (in) maximum allowed distance between simplified countour and cells.
468 //      maxEdgeLen - (in) maximum allowed contour edge length in cells.
469 //      cset - (out) Resulting contour set.
470 // Returns false if operation ran out of memory.
471 bool rcBuildContours(rcCompactHeightfield& chf,
472                                          const float maxError, const int maxEdgeLen,
473                                          rcContourSet& cset);
474
475 // Builds connected convex polygon mesh from contour polygons.
476 // Params:
477 //      cset - (in) contour set.
478 //      nvp - (in) maximum number of vertices per polygon.
479 //      mesh - (out) poly mesh.
480 // Returns false if operation ran out of memory.
481 bool rcBuildPolyMesh(rcContourSet& cset, int nvp, rcPolyMesh& mesh);
482
483 bool rcMergePolyMeshes(rcPolyMesh** meshes, const int nmeshes, rcPolyMesh& mesh);
484
485 // Builds detail triangle mesh for each polygon in the poly mesh.
486 // Params:
487 //      mesh - (in) poly mesh to detail.
488 //      chf - (in) compacy height field, used to query height for new vertices.
489 //  sampleDist - (in) spacing between height samples used to generate more detail into mesh.
490 //  sampleMaxError - (in) maximum allowed distance between simplified detail mesh and height sample.
491 //      pmdtl - (out) detail mesh.
492 // Returns false if operation ran out of memory.
493 bool rcBuildPolyMeshDetail(const rcPolyMesh& mesh, const rcCompactHeightfield& chf,
494                                                    const float sampleDist, const float sampleMaxError,
495                                                    rcPolyMeshDetail& dmesh);
496
497 bool rcMergePolyMeshDetails(rcPolyMeshDetail** meshes, const int nmeshes, rcPolyMeshDetail& mesh);
498
499 bool buildMeshAdjacency(unsigned short* polys, const int npolys, const int nverts, const int vertsPerPoly);
500
501 #endif // RECAST_H