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 #include <float.h>
20 #define _USE_MATH_DEFINES
21 #include <math.h>
22 #include <string.h>
23 #include <stdlib.h>
24 #include <stdio.h>
25 #include <stdarg.h>
26 #include "Recast.h"
27 #include "RecastAlloc.h"
28 #include "RecastAssert.h"
29
30 namespace
31 {
32 /// Allocates and constructs an object of the given type, returning a pointer.
33 /// TODO: Support constructor args.
34 /// @param[in] hint Hint to the allocator.
35 template <typename T>
rcNew(rcAllocHint hint)36 T* rcNew(rcAllocHint hint) {
37 T* ptr = (T*)rcAlloc(sizeof(T), hint);
38 ::new(rcNewTag(), (void*)ptr) T();
39 return ptr;
40 }
41
42 /// Destroys and frees an object allocated with rcNew.
43 /// @param[in] ptr The object pointer to delete.
44 template <typename T>
rcDelete(T * ptr)45 void rcDelete(T* ptr) {
46 if (ptr) {
47 ptr->~T();
48 rcFree((void*)ptr);
49 }
50 }
51 } // namespace
52
53
rcSqrt(float x)54 float rcSqrt(float x)
55 {
56 return sqrtf(x);
57 }
58
59 /// @class rcContext
60 /// @par
61 ///
62 /// This class does not provide logging or timer functionality on its
63 /// own. Both must be provided by a concrete implementation
64 /// by overriding the protected member functions. Also, this class does not
65 /// provide an interface for extracting log messages. (Only adding them.)
66 /// So concrete implementations must provide one.
67 ///
68 /// If no logging or timers are required, just pass an instance of this
69 /// class through the Recast build process.
70 ///
71
72 /// @par
73 ///
74 /// Example:
75 /// @code
76 /// // Where ctx is an instance of rcContext and filepath is a char array.
77 /// ctx->log(RC_LOG_ERROR, "buildTiledNavigation: Could not load '%s'", filepath);
78 /// @endcode
log(const rcLogCategory category,const char * format,...)79 void rcContext::log(const rcLogCategory category, const char* format, ...)
80 {
81 if (!m_logEnabled)
82 return;
83 static const int MSG_SIZE = 512;
84 char msg[MSG_SIZE];
85 va_list ap;
86 va_start(ap, format);
87 int len = vsnprintf(msg, MSG_SIZE, format, ap);
88 if (len >= MSG_SIZE)
89 {
90 len = MSG_SIZE-1;
91 msg[MSG_SIZE-1] = '\0';
92 }
93 va_end(ap);
94 doLog(category, msg, len);
95 }
96
rcAllocHeightfield()97 rcHeightfield* rcAllocHeightfield()
98 {
99 return rcNew<rcHeightfield>(RC_ALLOC_PERM);
100 }
rcHeightfield()101 rcHeightfield::rcHeightfield()
102 : width()
103 , height()
104 , bmin()
105 , bmax()
106 , cs()
107 , ch()
108 , spans()
109 , pools()
110 , freelist()
111 {
112 }
113
~rcHeightfield()114 rcHeightfield::~rcHeightfield()
115 {
116 // Delete span array.
117 rcFree(spans);
118 // Delete span pools.
119 while (pools)
120 {
121 rcSpanPool* next = pools->next;
122 rcFree(pools);
123 pools = next;
124 }
125 }
126
rcFreeHeightField(rcHeightfield * hf)127 void rcFreeHeightField(rcHeightfield* hf)
128 {
129 rcDelete(hf);
130 }
131
rcAllocCompactHeightfield()132 rcCompactHeightfield* rcAllocCompactHeightfield()
133 {
134 return rcNew<rcCompactHeightfield>(RC_ALLOC_PERM);
135 }
136
rcFreeCompactHeightfield(rcCompactHeightfield * chf)137 void rcFreeCompactHeightfield(rcCompactHeightfield* chf)
138 {
139 rcDelete(chf);
140 }
141
rcCompactHeightfield()142 rcCompactHeightfield::rcCompactHeightfield()
143 : width(),
144 height(),
145 spanCount(),
146 walkableHeight(),
147 walkableClimb(),
148 borderSize(),
149 maxDistance(),
150 maxRegions(),
151 bmin(),
152 bmax(),
153 cs(),
154 ch(),
155 cells(),
156 spans(),
157 dist(),
158 areas()
159 {
160 }
~rcCompactHeightfield()161 rcCompactHeightfield::~rcCompactHeightfield()
162 {
163 rcFree(cells);
164 rcFree(spans);
165 rcFree(dist);
166 rcFree(areas);
167 }
168
rcAllocHeightfieldLayerSet()169 rcHeightfieldLayerSet* rcAllocHeightfieldLayerSet()
170 {
171 return rcNew<rcHeightfieldLayerSet>(RC_ALLOC_PERM);
172 }
rcFreeHeightfieldLayerSet(rcHeightfieldLayerSet * lset)173 void rcFreeHeightfieldLayerSet(rcHeightfieldLayerSet* lset)
174 {
175 rcDelete(lset);
176 }
177
rcHeightfieldLayerSet()178 rcHeightfieldLayerSet::rcHeightfieldLayerSet()
179 : layers(), nlayers() {}
~rcHeightfieldLayerSet()180 rcHeightfieldLayerSet::~rcHeightfieldLayerSet()
181 {
182 for (int i = 0; i < nlayers; ++i)
183 {
184 rcFree(layers[i].heights);
185 rcFree(layers[i].areas);
186 rcFree(layers[i].cons);
187 }
188 rcFree(layers);
189 }
190
191
rcAllocContourSet()192 rcContourSet* rcAllocContourSet()
193 {
194 return rcNew<rcContourSet>(RC_ALLOC_PERM);
195 }
rcFreeContourSet(rcContourSet * cset)196 void rcFreeContourSet(rcContourSet* cset)
197 {
198 rcDelete(cset);
199 }
200
rcContourSet()201 rcContourSet::rcContourSet()
202 : conts(),
203 nconts(),
204 bmin(),
205 bmax(),
206 cs(),
207 ch(),
208 width(),
209 height(),
210 borderSize(),
211 maxError() {}
~rcContourSet()212 rcContourSet::~rcContourSet()
213 {
214 for (int i = 0; i < nconts; ++i)
215 {
216 rcFree(conts[i].verts);
217 rcFree(conts[i].rverts);
218 }
219 rcFree(conts);
220 }
221
222
rcAllocPolyMesh()223 rcPolyMesh* rcAllocPolyMesh()
224 {
225 return rcNew<rcPolyMesh>(RC_ALLOC_PERM);
226 }
rcFreePolyMesh(rcPolyMesh * pmesh)227 void rcFreePolyMesh(rcPolyMesh* pmesh)
228 {
229 rcDelete(pmesh);
230 }
231
rcPolyMesh()232 rcPolyMesh::rcPolyMesh()
233 : verts(),
234 polys(),
235 regs(),
236 flags(),
237 areas(),
238 nverts(),
239 npolys(),
240 maxpolys(),
241 nvp(),
242 bmin(),
243 bmax(),
244 cs(),
245 ch(),
246 borderSize(),
247 maxEdgeError() {}
248
~rcPolyMesh()249 rcPolyMesh::~rcPolyMesh()
250 {
251 rcFree(verts);
252 rcFree(polys);
253 rcFree(regs);
254 rcFree(flags);
255 rcFree(areas);
256 }
257
rcAllocPolyMeshDetail()258 rcPolyMeshDetail* rcAllocPolyMeshDetail()
259 {
260 rcPolyMeshDetail* dmesh = (rcPolyMeshDetail*)rcAlloc(sizeof(rcPolyMeshDetail), RC_ALLOC_PERM);
261 memset(dmesh, 0, sizeof(rcPolyMeshDetail));
262 return dmesh;
263 }
264
rcFreePolyMeshDetail(rcPolyMeshDetail * dmesh)265 void rcFreePolyMeshDetail(rcPolyMeshDetail* dmesh)
266 {
267 if (!dmesh) return;
268 rcFree(dmesh->meshes);
269 rcFree(dmesh->verts);
270 rcFree(dmesh->tris);
271 rcFree(dmesh);
272 }
273
rcCalcBounds(const float * verts,int nv,float * bmin,float * bmax)274 void rcCalcBounds(const float* verts, int nv, float* bmin, float* bmax)
275 {
276 // Calculate bounding box.
277 rcVcopy(bmin, verts);
278 rcVcopy(bmax, verts);
279 for (int i = 1; i < nv; ++i)
280 {
281 const float* v = &verts[i*3];
282 rcVmin(bmin, v);
283 rcVmax(bmax, v);
284 }
285 }
286
rcCalcGridSize(const float * bmin,const float * bmax,float cs,int * w,int * h)287 void rcCalcGridSize(const float* bmin, const float* bmax, float cs, int* w, int* h)
288 {
289 *w = (int)((bmax[0] - bmin[0])/cs+0.5f);
290 *h = (int)((bmax[2] - bmin[2])/cs+0.5f);
291 }
292
293 /// @par
294 ///
295 /// See the #rcConfig documentation for more information on the configuration parameters.
296 ///
297 /// @see rcAllocHeightfield, rcHeightfield
rcCreateHeightfield(rcContext * ctx,rcHeightfield & hf,int width,int height,const float * bmin,const float * bmax,float cs,float ch)298 bool rcCreateHeightfield(rcContext* ctx, rcHeightfield& hf, int width, int height,
299 const float* bmin, const float* bmax,
300 float cs, float ch)
301 {
302 rcIgnoreUnused(ctx);
303
304 hf.width = width;
305 hf.height = height;
306 rcVcopy(hf.bmin, bmin);
307 rcVcopy(hf.bmax, bmax);
308 hf.cs = cs;
309 hf.ch = ch;
310 hf.spans = (rcSpan**)rcAlloc(sizeof(rcSpan*)*hf.width*hf.height, RC_ALLOC_PERM);
311 if (!hf.spans)
312 return false;
313 memset(hf.spans, 0, sizeof(rcSpan*)*hf.width*hf.height);
314 return true;
315 }
316
calcTriNormal(const float * v0,const float * v1,const float * v2,float * norm)317 static void calcTriNormal(const float* v0, const float* v1, const float* v2, float* norm)
318 {
319 float e0[3], e1[3];
320 rcVsub(e0, v1, v0);
321 rcVsub(e1, v2, v0);
322 rcVcross(norm, e0, e1);
323 rcVnormalize(norm);
324 }
325
326 /// @par
327 ///
328 /// Only sets the area id's for the walkable triangles. Does not alter the
329 /// area id's for unwalkable triangles.
330 ///
331 /// See the #rcConfig documentation for more information on the configuration parameters.
332 ///
333 /// @see rcHeightfield, rcClearUnwalkableTriangles, rcRasterizeTriangles
rcMarkWalkableTriangles(rcContext * ctx,const float walkableSlopeAngle,const float * verts,int nv,const int * tris,int nt,unsigned char * areas)334 void rcMarkWalkableTriangles(rcContext* ctx, const float walkableSlopeAngle,
335 const float* verts, int nv,
336 const int* tris, int nt,
337 unsigned char* areas)
338 {
339 rcIgnoreUnused(ctx);
340 rcIgnoreUnused(nv);
341
342 const float walkableThr = cosf(walkableSlopeAngle/180.0f*RC_PI);
343
344 float norm[3];
345
346 for (int i = 0; i < nt; ++i)
347 {
348 const int* tri = &tris[i*3];
349 calcTriNormal(&verts[tri[0]*3], &verts[tri[1]*3], &verts[tri[2]*3], norm);
350 // Check if the face is walkable.
351 if (norm[1] > walkableThr)
352 areas[i] = RC_WALKABLE_AREA;
353 }
354 }
355
356 /// @par
357 ///
358 /// Only sets the area id's for the unwalkable triangles. Does not alter the
359 /// area id's for walkable triangles.
360 ///
361 /// See the #rcConfig documentation for more information on the configuration parameters.
362 ///
363 /// @see rcHeightfield, rcClearUnwalkableTriangles, rcRasterizeTriangles
rcClearUnwalkableTriangles(rcContext * ctx,const float walkableSlopeAngle,const float * verts,int,const int * tris,int nt,unsigned char * areas)364 void rcClearUnwalkableTriangles(rcContext* ctx, const float walkableSlopeAngle,
365 const float* verts, int /*nv*/,
366 const int* tris, int nt,
367 unsigned char* areas)
368 {
369 rcIgnoreUnused(ctx);
370
371 const float walkableThr = cosf(walkableSlopeAngle/180.0f*RC_PI);
372
373 float norm[3];
374
375 for (int i = 0; i < nt; ++i)
376 {
377 const int* tri = &tris[i*3];
378 calcTriNormal(&verts[tri[0]*3], &verts[tri[1]*3], &verts[tri[2]*3], norm);
379 // Check if the face is walkable.
380 if (norm[1] <= walkableThr)
381 areas[i] = RC_NULL_AREA;
382 }
383 }
384
rcGetHeightFieldSpanCount(rcContext * ctx,rcHeightfield & hf)385 int rcGetHeightFieldSpanCount(rcContext* ctx, rcHeightfield& hf)
386 {
387 rcIgnoreUnused(ctx);
388
389 const int w = hf.width;
390 const int h = hf.height;
391 int spanCount = 0;
392 for (int y = 0; y < h; ++y)
393 {
394 for (int x = 0; x < w; ++x)
395 {
396 for (rcSpan* s = hf.spans[x + y*w]; s; s = s->next)
397 {
398 if (s->area != RC_NULL_AREA)
399 spanCount++;
400 }
401 }
402 }
403 return spanCount;
404 }
405
406 /// @par
407 ///
408 /// This is just the beginning of the process of fully building a compact heightfield.
409 /// Various filters may be applied, then the distance field and regions built.
410 /// E.g: #rcBuildDistanceField and #rcBuildRegions
411 ///
412 /// See the #rcConfig documentation for more information on the configuration parameters.
413 ///
414 /// @see rcAllocCompactHeightfield, rcHeightfield, rcCompactHeightfield, rcConfig
rcBuildCompactHeightfield(rcContext * ctx,const int walkableHeight,const int walkableClimb,rcHeightfield & hf,rcCompactHeightfield & chf)415 bool rcBuildCompactHeightfield(rcContext* ctx, const int walkableHeight, const int walkableClimb,
416 rcHeightfield& hf, rcCompactHeightfield& chf)
417 {
418 rcAssert(ctx);
419
420 rcScopedTimer timer(ctx, RC_TIMER_BUILD_COMPACTHEIGHTFIELD);
421
422 const int w = hf.width;
423 const int h = hf.height;
424 const int spanCount = rcGetHeightFieldSpanCount(ctx, hf);
425
426 // Fill in header.
427 chf.width = w;
428 chf.height = h;
429 chf.spanCount = spanCount;
430 chf.walkableHeight = walkableHeight;
431 chf.walkableClimb = walkableClimb;
432 chf.maxRegions = 0;
433 rcVcopy(chf.bmin, hf.bmin);
434 rcVcopy(chf.bmax, hf.bmax);
435 chf.bmax[1] += walkableHeight*hf.ch;
436 chf.cs = hf.cs;
437 chf.ch = hf.ch;
438 chf.cells = (rcCompactCell*)rcAlloc(sizeof(rcCompactCell)*w*h, RC_ALLOC_PERM);
439 if (!chf.cells)
440 {
441 ctx->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Out of memory 'chf.cells' (%d)", w*h);
442 return false;
443 }
444 memset(chf.cells, 0, sizeof(rcCompactCell)*w*h);
445 chf.spans = (rcCompactSpan*)rcAlloc(sizeof(rcCompactSpan)*spanCount, RC_ALLOC_PERM);
446 if (!chf.spans)
447 {
448 ctx->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Out of memory 'chf.spans' (%d)", spanCount);
449 return false;
450 }
451 memset(chf.spans, 0, sizeof(rcCompactSpan)*spanCount);
452 chf.areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*spanCount, RC_ALLOC_PERM);
453 if (!chf.areas)
454 {
455 ctx->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Out of memory 'chf.areas' (%d)", spanCount);
456 return false;
457 }
458 memset(chf.areas, RC_NULL_AREA, sizeof(unsigned char)*spanCount);
459
460 const int MAX_HEIGHT = 0xffff;
461
462 // Fill in cells and spans.
463 int idx = 0;
464 for (int y = 0; y < h; ++y)
465 {
466 for (int x = 0; x < w; ++x)
467 {
468 const rcSpan* s = hf.spans[x + y*w];
469 // If there are no spans at this cell, just leave the data to index=0, count=0.
470 if (!s) continue;
471 rcCompactCell& c = chf.cells[x+y*w];
472 c.index = idx;
473 c.count = 0;
474 while (s)
475 {
476 if (s->area != RC_NULL_AREA)
477 {
478 const int bot = (int)s->smax;
479 const int top = s->next ? (int)s->next->smin : MAX_HEIGHT;
480 chf.spans[idx].y = (unsigned short)rcClamp(bot, 0, 0xffff);
481 chf.spans[idx].h = (unsigned char)rcClamp(top - bot, 0, 0xff);
482 chf.areas[idx] = s->area;
483 idx++;
484 c.count++;
485 }
486 s = s->next;
487 }
488 }
489 }
490
491 // Find neighbour connections.
492 const int MAX_LAYERS = RC_NOT_CONNECTED-1;
493 int tooHighNeighbour = 0;
494 for (int y = 0; y < h; ++y)
495 {
496 for (int x = 0; x < w; ++x)
497 {
498 const rcCompactCell& c = chf.cells[x+y*w];
499 for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
500 {
501 rcCompactSpan& s = chf.spans[i];
502
503 for (int dir = 0; dir < 4; ++dir)
504 {
505 rcSetCon(s, dir, RC_NOT_CONNECTED);
506 const int nx = x + rcGetDirOffsetX(dir);
507 const int ny = y + rcGetDirOffsetY(dir);
508 // First check that the neighbour cell is in bounds.
509 if (nx < 0 || ny < 0 || nx >= w || ny >= h)
510 continue;
511
512 // Iterate over all neighbour spans and check if any of the is
513 // accessible from current cell.
514 const rcCompactCell& nc = chf.cells[nx+ny*w];
515 for (int k = (int)nc.index, nk = (int)(nc.index+nc.count); k < nk; ++k)
516 {
517 const rcCompactSpan& ns = chf.spans[k];
518 const int bot = rcMax(s.y, ns.y);
519 const int top = rcMin(s.y+s.h, ns.y+ns.h);
520
521 // Check that the gap between the spans is walkable,
522 // and that the climb height between the gaps is not too high.
523 if ((top - bot) >= walkableHeight && rcAbs((int)ns.y - (int)s.y) <= walkableClimb)
524 {
525 // Mark direction as walkable.
526 const int lidx = k - (int)nc.index;
527 if (lidx < 0 || lidx > MAX_LAYERS)
528 {
529 tooHighNeighbour = rcMax(tooHighNeighbour, lidx);
530 continue;
531 }
532 rcSetCon(s, dir, lidx);
533 break;
534 }
535 }
536
537 }
538 }
539 }
540 }
541
542 if (tooHighNeighbour > MAX_LAYERS)
543 {
544 ctx->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Heightfield has too many layers %d (max: %d)",
545 tooHighNeighbour, MAX_LAYERS);
546 }
547
548 return true;
549 }
550
551 /*
552 static int getHeightfieldMemoryUsage(const rcHeightfield& hf)
553 {
554 int size = 0;
555 size += sizeof(hf);
556 size += hf.width * hf.height * sizeof(rcSpan*);
557
558 rcSpanPool* pool = hf.pools;
559 while (pool)
560 {
561 size += (sizeof(rcSpanPool) - sizeof(rcSpan)) + sizeof(rcSpan)*RC_SPANS_PER_POOL;
562 pool = pool->next;
563 }
564 return size;
565 }
566
567 static int getCompactHeightFieldMemoryusage(const rcCompactHeightfield& chf)
568 {
569 int size = 0;
570 size += sizeof(rcCompactHeightfield);
571 size += sizeof(rcCompactSpan) * chf.spanCount;
572 size += sizeof(rcCompactCell) * chf.width * chf.height;
573 return size;
574 }
575 */
576