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