9
3

DetourNavMeshBuilder.cpp 24 KB

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