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 <stdio.h>
20 #include <stdlib.h>
21 #include <string.h>
22 #include <float.h>
23 #include "DetourNavMesh.h"
24 #include "DetourCommon.h"
25 #include "DetourMath.h"
26 #include "DetourNavMeshBuilder.h"
27 #include "DetourAlloc.h"
28 #include "DetourAssert.h"
29
30 static unsigned short MESH_NULL_IDX = 0xffff;
31
32
33 struct BVItem
34 {
35 unsigned short bmin[3];
36 unsigned short bmax[3];
37 int i;
38 };
39
compareItemX(const void * va,const void * vb)40 static int compareItemX(const void* va, const void* vb)
41 {
42 const BVItem* a = (const BVItem*)va;
43 const BVItem* b = (const BVItem*)vb;
44 if (a->bmin[0] < b->bmin[0])
45 return -1;
46 if (a->bmin[0] > b->bmin[0])
47 return 1;
48 return 0;
49 }
50
compareItemY(const void * va,const void * vb)51 static int compareItemY(const void* va, const void* vb)
52 {
53 const BVItem* a = (const BVItem*)va;
54 const BVItem* b = (const BVItem*)vb;
55 if (a->bmin[1] < b->bmin[1])
56 return -1;
57 if (a->bmin[1] > b->bmin[1])
58 return 1;
59 return 0;
60 }
61
compareItemZ(const void * va,const void * vb)62 static int compareItemZ(const void* va, const void* vb)
63 {
64 const BVItem* a = (const BVItem*)va;
65 const BVItem* b = (const BVItem*)vb;
66 if (a->bmin[2] < b->bmin[2])
67 return -1;
68 if (a->bmin[2] > b->bmin[2])
69 return 1;
70 return 0;
71 }
72
calcExtends(BVItem * items,const int,const int imin,const int imax,unsigned short * bmin,unsigned short * bmax)73 static void calcExtends(BVItem* items, const int /*nitems*/, const int imin, const int imax,
74 unsigned short* bmin, unsigned short* bmax)
75 {
76 bmin[0] = items[imin].bmin[0];
77 bmin[1] = items[imin].bmin[1];
78 bmin[2] = items[imin].bmin[2];
79
80 bmax[0] = items[imin].bmax[0];
81 bmax[1] = items[imin].bmax[1];
82 bmax[2] = items[imin].bmax[2];
83
84 for (int i = imin+1; i < imax; ++i)
85 {
86 const BVItem& it = items[i];
87 if (it.bmin[0] < bmin[0]) bmin[0] = it.bmin[0];
88 if (it.bmin[1] < bmin[1]) bmin[1] = it.bmin[1];
89 if (it.bmin[2] < bmin[2]) bmin[2] = it.bmin[2];
90
91 if (it.bmax[0] > bmax[0]) bmax[0] = it.bmax[0];
92 if (it.bmax[1] > bmax[1]) bmax[1] = it.bmax[1];
93 if (it.bmax[2] > bmax[2]) bmax[2] = it.bmax[2];
94 }
95 }
96
longestAxis(unsigned short x,unsigned short y,unsigned short z)97 inline int longestAxis(unsigned short x, unsigned short y, unsigned short z)
98 {
99 int axis = 0;
100 unsigned short maxVal = x;
101 if (y > maxVal)
102 {
103 axis = 1;
104 maxVal = y;
105 }
106 if (z > maxVal)
107 {
108 axis = 2;
109 maxVal = z;
110 }
111 return axis;
112 }
113
subdivide(BVItem * items,int nitems,int imin,int imax,int & curNode,dtBVNode * nodes)114 static void subdivide(BVItem* items, int nitems, int imin, int imax, int& curNode, dtBVNode* nodes)
115 {
116 int inum = imax - imin;
117 int icur = curNode;
118
119 dtBVNode& node = nodes[curNode++];
120
121 if (inum == 1)
122 {
123 // Leaf
124 node.bmin[0] = items[imin].bmin[0];
125 node.bmin[1] = items[imin].bmin[1];
126 node.bmin[2] = items[imin].bmin[2];
127
128 node.bmax[0] = items[imin].bmax[0];
129 node.bmax[1] = items[imin].bmax[1];
130 node.bmax[2] = items[imin].bmax[2];
131
132 node.i = items[imin].i;
133 }
134 else
135 {
136 // Split
137 calcExtends(items, nitems, imin, imax, node.bmin, node.bmax);
138
139 int axis = longestAxis(node.bmax[0] - node.bmin[0],
140 node.bmax[1] - node.bmin[1],
141 node.bmax[2] - node.bmin[2]);
142
143 if (axis == 0)
144 {
145 // Sort along x-axis
146 qsort(items+imin, inum, sizeof(BVItem), compareItemX);
147 }
148 else if (axis == 1)
149 {
150 // Sort along y-axis
151 qsort(items+imin, inum, sizeof(BVItem), compareItemY);
152 }
153 else
154 {
155 // Sort along z-axis
156 qsort(items+imin, inum, sizeof(BVItem), compareItemZ);
157 }
158
159 int isplit = imin+inum/2;
160
161 // Left
162 subdivide(items, nitems, imin, isplit, curNode, nodes);
163 // Right
164 subdivide(items, nitems, isplit, imax, curNode, nodes);
165
166 int iescape = curNode - icur;
167 // Negative index means escape.
168 node.i = -iescape;
169 }
170 }
171
createBVTree(const unsigned short * verts,const int,const unsigned short * polys,const int npolys,const int nvp,const float cs,const float ch,const int,dtBVNode * nodes)172 static int createBVTree(const unsigned short* verts, const int /*nverts*/,
173 const unsigned short* polys, const int npolys, const int nvp,
174 const float cs, const float ch,
175 const int /*nnodes*/, dtBVNode* nodes)
176 {
177 // Build tree
178 BVItem* items = (BVItem*)dtAlloc(sizeof(BVItem)*npolys, DT_ALLOC_TEMP);
179 for (int i = 0; i < npolys; i++)
180 {
181 BVItem& it = items[i];
182 it.i = i;
183 // Calc polygon bounds.
184 const unsigned short* p = &polys[i*nvp*2];
185 it.bmin[0] = it.bmax[0] = verts[p[0]*3+0];
186 it.bmin[1] = it.bmax[1] = verts[p[0]*3+1];
187 it.bmin[2] = it.bmax[2] = verts[p[0]*3+2];
188
189 for (int j = 1; j < nvp; ++j)
190 {
191 if (p[j] == MESH_NULL_IDX) break;
192 unsigned short x = verts[p[j]*3+0];
193 unsigned short y = verts[p[j]*3+1];
194 unsigned short z = verts[p[j]*3+2];
195
196 if (x < it.bmin[0]) it.bmin[0] = x;
197 if (y < it.bmin[1]) it.bmin[1] = y;
198 if (z < it.bmin[2]) it.bmin[2] = z;
199
200 if (x > it.bmax[0]) it.bmax[0] = x;
201 if (y > it.bmax[1]) it.bmax[1] = y;
202 if (z > it.bmax[2]) it.bmax[2] = z;
203 }
204 // Remap y
205 it.bmin[1] = (unsigned short)dtMathFloorf((float)it.bmin[1]*ch/cs);
206 it.bmax[1] = (unsigned short)dtMathCeilf((float)it.bmax[1]*ch/cs);
207 }
208
209 int curNode = 0;
210 subdivide(items, npolys, 0, npolys, curNode, nodes);
211
212 dtFree(items);
213
214 return curNode;
215 }
216
classifyOffMeshPoint(const float * pt,const float * bmin,const float * bmax)217 static unsigned char classifyOffMeshPoint(const float* pt, const float* bmin, const float* bmax)
218 {
219 static const unsigned char XP = 1<<0;
220 static const unsigned char ZP = 1<<1;
221 static const unsigned char XM = 1<<2;
222 static const unsigned char ZM = 1<<3;
223
224 unsigned char outcode = 0;
225 outcode |= (pt[0] >= bmax[0]) ? XP : 0;
226 outcode |= (pt[2] >= bmax[2]) ? ZP : 0;
227 outcode |= (pt[0] < bmin[0]) ? XM : 0;
228 outcode |= (pt[2] < bmin[2]) ? ZM : 0;
229
230 switch (outcode)
231 {
232 case XP: return 0;
233 case XP|ZP: return 1;
234 case ZP: return 2;
235 case XM|ZP: return 3;
236 case XM: return 4;
237 case XM|ZM: return 5;
238 case ZM: return 6;
239 case XP|ZM: return 7;
240 };
241
242 return 0xff;
243 }
244
245 // TODO: Better error handling.
246
247 /// @par
248 ///
249 /// The output data array is allocated using the detour allocator (dtAlloc()). The method
250 /// used to free the memory will be determined by how the tile is added to the navigation
251 /// mesh.
252 ///
253 /// @see dtNavMesh, dtNavMesh::addTile()
dtCreateNavMeshData(dtNavMeshCreateParams * params,unsigned char ** outData,int * outDataSize)254 bool dtCreateNavMeshData(dtNavMeshCreateParams* params, unsigned char** outData, int* outDataSize)
255 {
256 if (params->nvp > DT_VERTS_PER_POLYGON)
257 return false;
258 if (params->vertCount >= 0xffff)
259 return false;
260 if (!params->vertCount || !params->verts)
261 return false;
262 if (!params->polyCount || !params->polys)
263 return false;
264
265 const int nvp = params->nvp;
266
267 // Classify off-mesh connection points. We store only the connections
268 // whose start point is inside the tile.
269 unsigned char* offMeshConClass = 0;
270 int storedOffMeshConCount = 0;
271 int offMeshConLinkCount = 0;
272
273 if (params->offMeshConCount > 0)
274 {
275 offMeshConClass = (unsigned char*)dtAlloc(sizeof(unsigned char)*params->offMeshConCount*2, DT_ALLOC_TEMP);
276 if (!offMeshConClass)
277 return false;
278
279 // Find tight heigh bounds, used for culling out off-mesh start locations.
280 float hmin = FLT_MAX;
281 float hmax = -FLT_MAX;
282
283 if (params->detailVerts && params->detailVertsCount)
284 {
285 for (int i = 0; i < params->detailVertsCount; ++i)
286 {
287 const float h = params->detailVerts[i*3+1];
288 hmin = dtMin(hmin,h);
289 hmax = dtMax(hmax,h);
290 }
291 }
292 else
293 {
294 for (int i = 0; i < params->vertCount; ++i)
295 {
296 const unsigned short* iv = ¶ms->verts[i*3];
297 const float h = params->bmin[1] + iv[1] * params->ch;
298 hmin = dtMin(hmin,h);
299 hmax = dtMax(hmax,h);
300 }
301 }
302 hmin -= params->walkableClimb;
303 hmax += params->walkableClimb;
304 float bmin[3], bmax[3];
305 dtVcopy(bmin, params->bmin);
306 dtVcopy(bmax, params->bmax);
307 bmin[1] = hmin;
308 bmax[1] = hmax;
309
310 for (int i = 0; i < params->offMeshConCount; ++i)
311 {
312 const float* p0 = ¶ms->offMeshConVerts[(i*2+0)*3];
313 const float* p1 = ¶ms->offMeshConVerts[(i*2+1)*3];
314 offMeshConClass[i*2+0] = classifyOffMeshPoint(p0, bmin, bmax);
315 offMeshConClass[i*2+1] = classifyOffMeshPoint(p1, bmin, bmax);
316
317 // Zero out off-mesh start positions which are not even potentially touching the mesh.
318 if (offMeshConClass[i*2+0] == 0xff)
319 {
320 if (p0[1] < bmin[1] || p0[1] > bmax[1])
321 offMeshConClass[i*2+0] = 0;
322 }
323
324 // Cound how many links should be allocated for off-mesh connections.
325 if (offMeshConClass[i*2+0] == 0xff)
326 offMeshConLinkCount++;
327 if (offMeshConClass[i*2+1] == 0xff)
328 offMeshConLinkCount++;
329
330 if (offMeshConClass[i*2+0] == 0xff)
331 storedOffMeshConCount++;
332 }
333 }
334
335 // Off-mesh connectionss are stored as polygons, adjust values.
336 const int totPolyCount = params->polyCount + storedOffMeshConCount;
337 const int totVertCount = params->vertCount + storedOffMeshConCount*2;
338
339 // Find portal edges which are at tile borders.
340 int edgeCount = 0;
341 int portalCount = 0;
342 for (int i = 0; i < params->polyCount; ++i)
343 {
344 const unsigned short* p = ¶ms->polys[i*2*nvp];
345 for (int j = 0; j < nvp; ++j)
346 {
347 if (p[j] == MESH_NULL_IDX) break;
348 edgeCount++;
349
350 if (p[nvp+j] & 0x8000)
351 {
352 unsigned short dir = p[nvp+j] & 0xf;
353 if (dir != 0xf)
354 portalCount++;
355 }
356 }
357 }
358
359 const int maxLinkCount = edgeCount + portalCount*2 + offMeshConLinkCount*2;
360
361 // Find unique detail vertices.
362 int uniqueDetailVertCount = 0;
363 int detailTriCount = 0;
364 if (params->detailMeshes)
365 {
366 // Has detail mesh, count unique detail vertex count and use input detail tri count.
367 detailTriCount = params->detailTriCount;
368 for (int i = 0; i < params->polyCount; ++i)
369 {
370 const unsigned short* p = ¶ms->polys[i*nvp*2];
371 int ndv = params->detailMeshes[i*4+1];
372 int nv = 0;
373 for (int j = 0; j < nvp; ++j)
374 {
375 if (p[j] == MESH_NULL_IDX) break;
376 nv++;
377 }
378 ndv -= nv;
379 uniqueDetailVertCount += ndv;
380 }
381 }
382 else
383 {
384 // No input detail mesh, build detail mesh from nav polys.
385 uniqueDetailVertCount = 0; // No extra detail verts.
386 detailTriCount = 0;
387 for (int i = 0; i < params->polyCount; ++i)
388 {
389 const unsigned short* p = ¶ms->polys[i*nvp*2];
390 int nv = 0;
391 for (int j = 0; j < nvp; ++j)
392 {
393 if (p[j] == MESH_NULL_IDX) break;
394 nv++;
395 }
396 detailTriCount += nv-2;
397 }
398 }
399
400 // Calculate data size
401 const int headerSize = dtAlign4(sizeof(dtMeshHeader));
402 const int vertsSize = dtAlign4(sizeof(float)*3*totVertCount);
403 const int polysSize = dtAlign4(sizeof(dtPoly)*totPolyCount);
404 const int linksSize = dtAlign4(sizeof(dtLink)*maxLinkCount);
405 const int detailMeshesSize = dtAlign4(sizeof(dtPolyDetail)*params->polyCount);
406 const int detailVertsSize = dtAlign4(sizeof(float)*3*uniqueDetailVertCount);
407 const int detailTrisSize = dtAlign4(sizeof(unsigned char)*4*detailTriCount);
408 const int bvTreeSize = params->buildBvTree ? dtAlign4(sizeof(dtBVNode)*params->polyCount*2) : 0;
409 const int offMeshConsSize = dtAlign4(sizeof(dtOffMeshConnection)*storedOffMeshConCount);
410
411 const int dataSize = headerSize + vertsSize + polysSize + linksSize +
412 detailMeshesSize + detailVertsSize + detailTrisSize +
413 bvTreeSize + offMeshConsSize;
414
415 unsigned char* data = (unsigned char*)dtAlloc(sizeof(unsigned char)*dataSize, DT_ALLOC_PERM);
416 if (!data)
417 {
418 dtFree(offMeshConClass);
419 return false;
420 }
421 memset(data, 0, dataSize);
422
423 unsigned char* d = data;
424 dtMeshHeader* header = (dtMeshHeader*)d; d += headerSize;
425 float* navVerts = (float*)d; d += vertsSize;
426 dtPoly* navPolys = (dtPoly*)d; d += polysSize;
427 d += linksSize;
428 dtPolyDetail* navDMeshes = (dtPolyDetail*)d; d += detailMeshesSize;
429 float* navDVerts = (float*)d; d += detailVertsSize;
430 unsigned char* navDTris = (unsigned char*)d; d += detailTrisSize;
431 dtBVNode* navBvtree = (dtBVNode*)d; d += bvTreeSize;
432 dtOffMeshConnection* offMeshCons = (dtOffMeshConnection*)d; d += offMeshConsSize;
433
434
435 // Store header
436 header->magic = DT_NAVMESH_MAGIC;
437 header->version = DT_NAVMESH_VERSION;
438 header->x = params->tileX;
439 header->y = params->tileY;
440 header->layer = params->tileLayer;
441 header->userId = params->userId;
442 header->polyCount = totPolyCount;
443 header->vertCount = totVertCount;
444 header->maxLinkCount = maxLinkCount;
445 dtVcopy(header->bmin, params->bmin);
446 dtVcopy(header->bmax, params->bmax);
447 header->detailMeshCount = params->polyCount;
448 header->detailVertCount = uniqueDetailVertCount;
449 header->detailTriCount = detailTriCount;
450 header->bvQuantFactor = 1.0f / params->cs;
451 header->offMeshBase = params->polyCount;
452 header->walkableHeight = params->walkableHeight;
453 header->walkableRadius = params->walkableRadius;
454 header->walkableClimb = params->walkableClimb;
455 header->offMeshConCount = storedOffMeshConCount;
456 header->bvNodeCount = params->buildBvTree ? params->polyCount*2 : 0;
457
458 const int offMeshVertsBase = params->vertCount;
459 const int offMeshPolyBase = params->polyCount;
460
461 // Store vertices
462 // Mesh vertices
463 for (int i = 0; i < params->vertCount; ++i)
464 {
465 const unsigned short* iv = ¶ms->verts[i*3];
466 float* v = &navVerts[i*3];
467 v[0] = params->bmin[0] + iv[0] * params->cs;
468 v[1] = params->bmin[1] + iv[1] * params->ch;
469 v[2] = params->bmin[2] + iv[2] * params->cs;
470 }
471 // Off-mesh link vertices.
472 int n = 0;
473 for (int i = 0; i < params->offMeshConCount; ++i)
474 {
475 // Only store connections which start from this tile.
476 if (offMeshConClass[i*2+0] == 0xff)
477 {
478 const float* linkv = ¶ms->offMeshConVerts[i*2*3];
479 float* v = &navVerts[(offMeshVertsBase + n*2)*3];
480 dtVcopy(&v[0], &linkv[0]);
481 dtVcopy(&v[3], &linkv[3]);
482 n++;
483 }
484 }
485
486 // Store polygons
487 // Mesh polys
488 const unsigned short* src = params->polys;
489 for (int i = 0; i < params->polyCount; ++i)
490 {
491 dtPoly* p = &navPolys[i];
492 p->vertCount = 0;
493 p->flags = params->polyFlags[i];
494 p->setArea(params->polyAreas[i]);
495 p->setType(DT_POLYTYPE_GROUND);
496 for (int j = 0; j < nvp; ++j)
497 {
498 if (src[j] == MESH_NULL_IDX) break;
499 p->verts[j] = src[j];
500 if (src[nvp+j] & 0x8000)
501 {
502 // Border or portal edge.
503 unsigned short dir = src[nvp+j] & 0xf;
504 if (dir == 0xf) // Border
505 p->neis[j] = 0;
506 else if (dir == 0) // Portal x-
507 p->neis[j] = DT_EXT_LINK | 4;
508 else if (dir == 1) // Portal z+
509 p->neis[j] = DT_EXT_LINK | 2;
510 else if (dir == 2) // Portal x+
511 p->neis[j] = DT_EXT_LINK | 0;
512 else if (dir == 3) // Portal z-
513 p->neis[j] = DT_EXT_LINK | 6;
514 }
515 else
516 {
517 // Normal connection
518 p->neis[j] = src[nvp+j]+1;
519 }
520
521 p->vertCount++;
522 }
523 src += nvp*2;
524 }
525 // Off-mesh connection vertices.
526 n = 0;
527 for (int i = 0; i < params->offMeshConCount; ++i)
528 {
529 // Only store connections which start from this tile.
530 if (offMeshConClass[i*2+0] == 0xff)
531 {
532 dtPoly* p = &navPolys[offMeshPolyBase+n];
533 p->vertCount = 2;
534 p->verts[0] = (unsigned short)(offMeshVertsBase + n*2+0);
535 p->verts[1] = (unsigned short)(offMeshVertsBase + n*2+1);
536 p->flags = params->offMeshConFlags[i];
537 p->setArea(params->offMeshConAreas[i]);
538 p->setType(DT_POLYTYPE_OFFMESH_CONNECTION);
539 n++;
540 }
541 }
542
543 // Store detail meshes and vertices.
544 // The nav polygon vertices are stored as the first vertices on each mesh.
545 // We compress the mesh data by skipping them and using the navmesh coordinates.
546 if (params->detailMeshes)
547 {
548 unsigned short vbase = 0;
549 for (int i = 0; i < params->polyCount; ++i)
550 {
551 dtPolyDetail& dtl = navDMeshes[i];
552 const int vb = (int)params->detailMeshes[i*4+0];
553 const int ndv = (int)params->detailMeshes[i*4+1];
554 const int nv = navPolys[i].vertCount;
555 dtl.vertBase = (unsigned int)vbase;
556 dtl.vertCount = (unsigned char)(ndv-nv);
557 dtl.triBase = (unsigned int)params->detailMeshes[i*4+2];
558 dtl.triCount = (unsigned char)params->detailMeshes[i*4+3];
559 // Copy vertices except the first 'nv' verts which are equal to nav poly verts.
560 if (ndv-nv)
561 {
562 memcpy(&navDVerts[vbase*3], ¶ms->detailVerts[(vb+nv)*3], sizeof(float)*3*(ndv-nv));
563 vbase += (unsigned short)(ndv-nv);
564 }
565 }
566 // Store triangles.
567 memcpy(navDTris, params->detailTris, sizeof(unsigned char)*4*params->detailTriCount);
568 }
569 else
570 {
571 // Create dummy detail mesh by triangulating polys.
572 int tbase = 0;
573 for (int i = 0; i < params->polyCount; ++i)
574 {
575 dtPolyDetail& dtl = navDMeshes[i];
576 const int nv = navPolys[i].vertCount;
577 dtl.vertBase = 0;
578 dtl.vertCount = 0;
579 dtl.triBase = (unsigned int)tbase;
580 dtl.triCount = (unsigned char)(nv-2);
581 // Triangulate polygon (local indices).
582 for (int j = 2; j < nv; ++j)
583 {
584 unsigned char* t = &navDTris[tbase*4];
585 t[0] = 0;
586 t[1] = (unsigned char)(j-1);
587 t[2] = (unsigned char)j;
588 // Bit for each edge that belongs to poly boundary.
589 t[3] = (1<<2);
590 if (j == 2) t[3] |= (1<<0);
591 if (j == nv-1) t[3] |= (1<<4);
592 tbase++;
593 }
594 }
595 }
596
597 // Store and create BVtree.
598 // TODO: take detail mesh into account! use byte per bbox extent?
599 if (params->buildBvTree)
600 {
601 createBVTree(params->verts, params->vertCount, params->polys, params->polyCount,
602 nvp, params->cs, params->ch, params->polyCount*2, navBvtree);
603 }
604
605 // Store Off-Mesh connections.
606 n = 0;
607 for (int i = 0; i < params->offMeshConCount; ++i)
608 {
609 // Only store connections which start from this tile.
610 if (offMeshConClass[i*2+0] == 0xff)
611 {
612 dtOffMeshConnection* con = &offMeshCons[n];
613 con->poly = (unsigned short)(offMeshPolyBase + n);
614 // Copy connection end-points.
615 const float* endPts = ¶ms->offMeshConVerts[i*2*3];
616 dtVcopy(&con->pos[0], &endPts[0]);
617 dtVcopy(&con->pos[3], &endPts[3]);
618 con->rad = params->offMeshConRad[i];
619 con->flags = params->offMeshConDir[i] ? DT_OFFMESH_CON_BIDIR : 0;
620 con->side = offMeshConClass[i*2+1];
621 if (params->offMeshConUserID)
622 con->userId = params->offMeshConUserID[i];
623 n++;
624 }
625 }
626
627 dtFree(offMeshConClass);
628
629 *outData = data;
630 *outDataSize = dataSize;
631
632 return true;
633 }
634
dtNavMeshHeaderSwapEndian(unsigned char * data,const int)635 bool dtNavMeshHeaderSwapEndian(unsigned char* data, const int /*dataSize*/)
636 {
637 dtMeshHeader* header = (dtMeshHeader*)data;
638
639 int swappedMagic = DT_NAVMESH_MAGIC;
640 int swappedVersion = DT_NAVMESH_VERSION;
641 dtSwapEndian(&swappedMagic);
642 dtSwapEndian(&swappedVersion);
643
644 if ((header->magic != DT_NAVMESH_MAGIC || header->version != DT_NAVMESH_VERSION) &&
645 (header->magic != swappedMagic || header->version != swappedVersion))
646 {
647 return false;
648 }
649
650 dtSwapEndian(&header->magic);
651 dtSwapEndian(&header->version);
652 dtSwapEndian(&header->x);
653 dtSwapEndian(&header->y);
654 dtSwapEndian(&header->layer);
655 dtSwapEndian(&header->userId);
656 dtSwapEndian(&header->polyCount);
657 dtSwapEndian(&header->vertCount);
658 dtSwapEndian(&header->maxLinkCount);
659 dtSwapEndian(&header->detailMeshCount);
660 dtSwapEndian(&header->detailVertCount);
661 dtSwapEndian(&header->detailTriCount);
662 dtSwapEndian(&header->bvNodeCount);
663 dtSwapEndian(&header->offMeshConCount);
664 dtSwapEndian(&header->offMeshBase);
665 dtSwapEndian(&header->walkableHeight);
666 dtSwapEndian(&header->walkableRadius);
667 dtSwapEndian(&header->walkableClimb);
668 dtSwapEndian(&header->bmin[0]);
669 dtSwapEndian(&header->bmin[1]);
670 dtSwapEndian(&header->bmin[2]);
671 dtSwapEndian(&header->bmax[0]);
672 dtSwapEndian(&header->bmax[1]);
673 dtSwapEndian(&header->bmax[2]);
674 dtSwapEndian(&header->bvQuantFactor);
675
676 // Freelist index and pointers are updated when tile is added, no need to swap.
677
678 return true;
679 }
680
681 /// @par
682 ///
683 /// @warning This function assumes that the header is in the correct endianess already.
684 /// Call #dtNavMeshHeaderSwapEndian() first on the data if the data is expected to be in wrong endianess
685 /// to start with. Call #dtNavMeshHeaderSwapEndian() after the data has been swapped if converting from
686 /// native to foreign endianess.
dtNavMeshDataSwapEndian(unsigned char * data,const int)687 bool dtNavMeshDataSwapEndian(unsigned char* data, const int /*dataSize*/)
688 {
689 // Make sure the data is in right format.
690 dtMeshHeader* header = (dtMeshHeader*)data;
691 if (header->magic != DT_NAVMESH_MAGIC)
692 return false;
693 if (header->version != DT_NAVMESH_VERSION)
694 return false;
695
696 // Patch header pointers.
697 const int headerSize = dtAlign4(sizeof(dtMeshHeader));
698 const int vertsSize = dtAlign4(sizeof(float)*3*header->vertCount);
699 const int polysSize = dtAlign4(sizeof(dtPoly)*header->polyCount);
700 const int linksSize = dtAlign4(sizeof(dtLink)*(header->maxLinkCount));
701 const int detailMeshesSize = dtAlign4(sizeof(dtPolyDetail)*header->detailMeshCount);
702 const int detailVertsSize = dtAlign4(sizeof(float)*3*header->detailVertCount);
703 const int detailTrisSize = dtAlign4(sizeof(unsigned char)*4*header->detailTriCount);
704 const int bvtreeSize = dtAlign4(sizeof(dtBVNode)*header->bvNodeCount);
705 const int offMeshLinksSize = dtAlign4(sizeof(dtOffMeshConnection)*header->offMeshConCount);
706
707 unsigned char* d = data + headerSize;
708 float* verts = (float*)d; d += vertsSize;
709 dtPoly* polys = (dtPoly*)d; d += polysSize;
710 /*dtLink* links = (dtLink*)d;*/ d += linksSize;
711 dtPolyDetail* detailMeshes = (dtPolyDetail*)d; d += detailMeshesSize;
712 float* detailVerts = (float*)d; d += detailVertsSize;
713 /*unsigned char* detailTris = (unsigned char*)d;*/ d += detailTrisSize;
714 dtBVNode* bvTree = (dtBVNode*)d; d += bvtreeSize;
715 dtOffMeshConnection* offMeshCons = (dtOffMeshConnection*)d; d += offMeshLinksSize;
716
717 // Vertices
718 for (int i = 0; i < header->vertCount*3; ++i)
719 {
720 dtSwapEndian(&verts[i]);
721 }
722
723 // Polys
724 for (int i = 0; i < header->polyCount; ++i)
725 {
726 dtPoly* p = &polys[i];
727 // poly->firstLink is update when tile is added, no need to swap.
728 for (int j = 0; j < DT_VERTS_PER_POLYGON; ++j)
729 {
730 dtSwapEndian(&p->verts[j]);
731 dtSwapEndian(&p->neis[j]);
732 }
733 dtSwapEndian(&p->flags);
734 }
735
736 // Links are rebuild when tile is added, no need to swap.
737
738 // Detail meshes
739 for (int i = 0; i < header->detailMeshCount; ++i)
740 {
741 dtPolyDetail* pd = &detailMeshes[i];
742 dtSwapEndian(&pd->vertBase);
743 dtSwapEndian(&pd->triBase);
744 }
745
746 // Detail verts
747 for (int i = 0; i < header->detailVertCount*3; ++i)
748 {
749 dtSwapEndian(&detailVerts[i]);
750 }
751
752 // BV-tree
753 for (int i = 0; i < header->bvNodeCount; ++i)
754 {
755 dtBVNode* node = &bvTree[i];
756 for (int j = 0; j < 3; ++j)
757 {
758 dtSwapEndian(&node->bmin[j]);
759 dtSwapEndian(&node->bmax[j]);
760 }
761 dtSwapEndian(&node->i);
762 }
763
764 // Off-mesh Connections.
765 for (int i = 0; i < header->offMeshConCount; ++i)
766 {
767 dtOffMeshConnection* con = &offMeshCons[i];
768 for (int j = 0; j < 6; ++j)
769 dtSwapEndian(&con->pos[j]);
770 dtSwapEndian(&con->rad);
771 dtSwapEndian(&con->poly);
772 }
773
774 return true;
775 }
776