9
3

DetourTileCacheBuilder.cpp 57 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250
  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 "DetourCommon.h"
  19. #include "DetourMath.h"
  20. #include "DetourStatus.h"
  21. #include "DetourAssert.h"
  22. #include "DetourTileCacheBuilder.h"
  23. #include <string.h>
  24. template<class T> class dtFixedArray
  25. {
  26. dtTileCacheAlloc* m_alloc;
  27. T* m_ptr;
  28. const int m_size;
  29. inline void operator=(dtFixedArray<T>& p);
  30. public:
  31. inline dtFixedArray(dtTileCacheAlloc* a, const int s) : m_alloc(a), m_ptr((T*)a->alloc(sizeof(T)*s)), m_size(s) {}
  32. inline ~dtFixedArray() { if (m_alloc) m_alloc->free(m_ptr); }
  33. inline operator T*() { return m_ptr; }
  34. inline int size() const { return m_size; }
  35. };
  36. inline int getDirOffsetX(int dir)
  37. {
  38. const int offset[4] = { -1, 0, 1, 0, };
  39. return offset[dir&0x03];
  40. }
  41. inline int getDirOffsetY(int dir)
  42. {
  43. const int offset[4] = { 0, 1, 0, -1 };
  44. return offset[dir&0x03];
  45. }
  46. static const int MAX_VERTS_PER_POLY = 6; // TODO: use the DT_VERTS_PER_POLYGON
  47. static const int MAX_REM_EDGES = 48; // TODO: make this an expression.
  48. dtTileCacheContourSet* dtAllocTileCacheContourSet(dtTileCacheAlloc* alloc)
  49. {
  50. dtAssert(alloc);
  51. dtTileCacheContourSet* cset = (dtTileCacheContourSet*)alloc->alloc(sizeof(dtTileCacheContourSet));
  52. memset(cset, 0, sizeof(dtTileCacheContourSet));
  53. return cset;
  54. }
  55. void dtFreeTileCacheContourSet(dtTileCacheAlloc* alloc, dtTileCacheContourSet* cset)
  56. {
  57. dtAssert(alloc);
  58. if (!cset) return;
  59. for (int i = 0; i < cset->nconts; ++i)
  60. alloc->free(cset->conts[i].verts);
  61. alloc->free(cset->conts);
  62. alloc->free(cset);
  63. }
  64. dtTileCachePolyMesh* dtAllocTileCachePolyMesh(dtTileCacheAlloc* alloc)
  65. {
  66. dtAssert(alloc);
  67. dtTileCachePolyMesh* lmesh = (dtTileCachePolyMesh*)alloc->alloc(sizeof(dtTileCachePolyMesh));
  68. memset(lmesh, 0, sizeof(dtTileCachePolyMesh));
  69. return lmesh;
  70. }
  71. void dtFreeTileCachePolyMesh(dtTileCacheAlloc* alloc, dtTileCachePolyMesh* lmesh)
  72. {
  73. dtAssert(alloc);
  74. if (!lmesh) return;
  75. alloc->free(lmesh->verts);
  76. alloc->free(lmesh->polys);
  77. alloc->free(lmesh->flags);
  78. alloc->free(lmesh->areas);
  79. alloc->free(lmesh);
  80. }
  81. struct dtLayerSweepSpan
  82. {
  83. unsigned short ns; // number samples
  84. unsigned char id; // region id
  85. unsigned char nei; // neighbour id
  86. };
  87. static const int DT_LAYER_MAX_NEIS = 16;
  88. struct dtLayerMonotoneRegion
  89. {
  90. int area;
  91. unsigned char neis[DT_LAYER_MAX_NEIS];
  92. unsigned char nneis;
  93. unsigned char regId;
  94. unsigned char areaId;
  95. };
  96. struct dtTempContour
  97. {
  98. inline dtTempContour(unsigned char* vbuf, const int nvbuf,
  99. unsigned short* pbuf, const int npbuf) :
  100. verts(vbuf), nverts(0), cverts(nvbuf),
  101. poly(pbuf), npoly(0), cpoly(npbuf)
  102. {
  103. }
  104. unsigned char* verts;
  105. int nverts;
  106. int cverts;
  107. unsigned short* poly;
  108. int npoly;
  109. int cpoly;
  110. };
  111. inline bool overlapRangeExl(const unsigned short amin, const unsigned short amax,
  112. const unsigned short bmin, const unsigned short bmax)
  113. {
  114. return (amin >= bmax || amax <= bmin) ? false : true;
  115. }
  116. static void addUniqueLast(unsigned char* a, unsigned char& an, unsigned char v)
  117. {
  118. const int n = (int)an;
  119. if (n > 0 && a[n-1] == v) return;
  120. a[an] = v;
  121. an++;
  122. }
  123. inline bool isConnected(const dtTileCacheLayer& layer,
  124. const int ia, const int ib, const int walkableClimb)
  125. {
  126. if (layer.areas[ia] != layer.areas[ib]) return false;
  127. if (dtAbs((int)layer.heights[ia] - (int)layer.heights[ib]) > walkableClimb) return false;
  128. return true;
  129. }
  130. static bool canMerge(unsigned char oldRegId, unsigned char newRegId, const dtLayerMonotoneRegion* regs, const int nregs)
  131. {
  132. int count = 0;
  133. for (int i = 0; i < nregs; ++i)
  134. {
  135. const dtLayerMonotoneRegion& reg = regs[i];
  136. if (reg.regId != oldRegId) continue;
  137. const int nnei = (int)reg.nneis;
  138. for (int j = 0; j < nnei; ++j)
  139. {
  140. if (regs[reg.neis[j]].regId == newRegId)
  141. count++;
  142. }
  143. }
  144. return count == 1;
  145. }
  146. dtStatus dtBuildTileCacheRegions(dtTileCacheAlloc* alloc,
  147. dtTileCacheLayer& layer,
  148. const int walkableClimb)
  149. {
  150. dtAssert(alloc);
  151. const int w = (int)layer.header->width;
  152. const int h = (int)layer.header->height;
  153. memset(layer.regs,0xff,sizeof(unsigned char)*w*h);
  154. const int nsweeps = w;
  155. dtFixedArray<dtLayerSweepSpan> sweeps(alloc, nsweeps);
  156. if (!sweeps)
  157. return DT_FAILURE | DT_OUT_OF_MEMORY;
  158. memset(sweeps,0,sizeof(dtLayerSweepSpan)*nsweeps);
  159. // Partition walkable area into monotone regions.
  160. unsigned char prevCount[256];
  161. unsigned char regId = 0;
  162. for (int y = 0; y < h; ++y)
  163. {
  164. if (regId > 0)
  165. memset(prevCount,0,sizeof(unsigned char)*regId);
  166. unsigned char sweepId = 0;
  167. for (int x = 0; x < w; ++x)
  168. {
  169. const int idx = x + y*w;
  170. if (layer.areas[idx] == DT_TILECACHE_NULL_AREA) continue;
  171. unsigned char sid = 0xff;
  172. // -x
  173. const int xidx = (x-1)+y*w;
  174. if (x > 0 && isConnected(layer, idx, xidx, walkableClimb))
  175. {
  176. if (layer.regs[xidx] != 0xff)
  177. sid = layer.regs[xidx];
  178. }
  179. if (sid == 0xff)
  180. {
  181. sid = sweepId++;
  182. sweeps[sid].nei = 0xff;
  183. sweeps[sid].ns = 0;
  184. }
  185. // -y
  186. const int yidx = x+(y-1)*w;
  187. if (y > 0 && isConnected(layer, idx, yidx, walkableClimb))
  188. {
  189. const unsigned char nr = layer.regs[yidx];
  190. if (nr != 0xff)
  191. {
  192. // Set neighbour when first valid neighbour is encoutered.
  193. if (sweeps[sid].ns == 0)
  194. sweeps[sid].nei = nr;
  195. if (sweeps[sid].nei == nr)
  196. {
  197. // Update existing neighbour
  198. sweeps[sid].ns++;
  199. prevCount[nr]++;
  200. }
  201. else
  202. {
  203. // This is hit if there is nore than one neighbour.
  204. // Invalidate the neighbour.
  205. sweeps[sid].nei = 0xff;
  206. }
  207. }
  208. }
  209. layer.regs[idx] = sid;
  210. }
  211. // Create unique ID.
  212. for (int i = 0; i < sweepId; ++i)
  213. {
  214. // If the neighbour is set and there is only one continuous connection to it,
  215. // the sweep will be merged with the previous one, else new region is created.
  216. if (sweeps[i].nei != 0xff && (unsigned short)prevCount[sweeps[i].nei] == sweeps[i].ns)
  217. {
  218. sweeps[i].id = sweeps[i].nei;
  219. }
  220. else
  221. {
  222. if (regId == 255)
  223. {
  224. // Region ID's overflow.
  225. return DT_FAILURE | DT_BUFFER_TOO_SMALL;
  226. }
  227. sweeps[i].id = regId++;
  228. }
  229. }
  230. // Remap local sweep ids to region ids.
  231. for (int x = 0; x < w; ++x)
  232. {
  233. const int idx = x+y*w;
  234. if (layer.regs[idx] != 0xff)
  235. layer.regs[idx] = sweeps[layer.regs[idx]].id;
  236. }
  237. }
  238. // Allocate and init layer regions.
  239. const int nregs = (int)regId;
  240. dtFixedArray<dtLayerMonotoneRegion> regs(alloc, nregs);
  241. if (!regs)
  242. return DT_FAILURE | DT_OUT_OF_MEMORY;
  243. memset(regs, 0, sizeof(dtLayerMonotoneRegion)*nregs);
  244. for (int i = 0; i < nregs; ++i)
  245. regs[i].regId = 0xff;
  246. // Find region neighbours.
  247. for (int y = 0; y < h; ++y)
  248. {
  249. for (int x = 0; x < w; ++x)
  250. {
  251. const int idx = x+y*w;
  252. const unsigned char ri = layer.regs[idx];
  253. if (ri == 0xff)
  254. continue;
  255. // Update area.
  256. regs[ri].area++;
  257. regs[ri].areaId = layer.areas[idx];
  258. // Update neighbours
  259. const int ymi = x+(y-1)*w;
  260. if (y > 0 && isConnected(layer, idx, ymi, walkableClimb))
  261. {
  262. const unsigned char rai = layer.regs[ymi];
  263. if (rai != 0xff && rai != ri)
  264. {
  265. addUniqueLast(regs[ri].neis, regs[ri].nneis, rai);
  266. addUniqueLast(regs[rai].neis, regs[rai].nneis, ri);
  267. }
  268. }
  269. }
  270. }
  271. for (int i = 0; i < nregs; ++i)
  272. regs[i].regId = (unsigned char)i;
  273. for (int i = 0; i < nregs; ++i)
  274. {
  275. dtLayerMonotoneRegion& reg = regs[i];
  276. int merge = -1;
  277. int mergea = 0;
  278. for (int j = 0; j < (int)reg.nneis; ++j)
  279. {
  280. const unsigned char nei = reg.neis[j];
  281. dtLayerMonotoneRegion& regn = regs[nei];
  282. if (reg.regId == regn.regId)
  283. continue;
  284. if (reg.areaId != regn.areaId)
  285. continue;
  286. if (regn.area > mergea)
  287. {
  288. if (canMerge(reg.regId, regn.regId, regs, nregs))
  289. {
  290. mergea = regn.area;
  291. merge = (int)nei;
  292. }
  293. }
  294. }
  295. if (merge != -1)
  296. {
  297. const unsigned char oldId = reg.regId;
  298. const unsigned char newId = regs[merge].regId;
  299. for (int j = 0; j < nregs; ++j)
  300. if (regs[j].regId == oldId)
  301. regs[j].regId = newId;
  302. }
  303. }
  304. // Compact ids.
  305. unsigned char remap[256];
  306. memset(remap, 0, 256);
  307. // Find number of unique regions.
  308. regId = 0;
  309. for (int i = 0; i < nregs; ++i)
  310. remap[regs[i].regId] = 1;
  311. for (int i = 0; i < 256; ++i)
  312. if (remap[i])
  313. remap[i] = regId++;
  314. // Remap ids.
  315. for (int i = 0; i < nregs; ++i)
  316. regs[i].regId = remap[regs[i].regId];
  317. layer.regCount = regId;
  318. for (int i = 0; i < w*h; ++i)
  319. {
  320. if (layer.regs[i] != 0xff)
  321. layer.regs[i] = regs[layer.regs[i]].regId;
  322. }
  323. return DT_SUCCESS;
  324. }
  325. static bool appendVertex(dtTempContour& cont, const int x, const int y, const int z, const int r)
  326. {
  327. // Try to merge with existing segments.
  328. if (cont.nverts > 1)
  329. {
  330. unsigned char* pa = &cont.verts[(cont.nverts-2)*4];
  331. unsigned char* pb = &cont.verts[(cont.nverts-1)*4];
  332. if ((int)pb[3] == r)
  333. {
  334. if (pa[0] == pb[0] && (int)pb[0] == x)
  335. {
  336. // The verts are aligned aling x-axis, update z.
  337. pb[1] = (unsigned char)y;
  338. pb[2] = (unsigned char)z;
  339. return true;
  340. }
  341. else if (pa[2] == pb[2] && (int)pb[2] == z)
  342. {
  343. // The verts are aligned aling z-axis, update x.
  344. pb[0] = (unsigned char)x;
  345. pb[1] = (unsigned char)y;
  346. return true;
  347. }
  348. }
  349. }
  350. // Add new point.
  351. if (cont.nverts+1 > cont.cverts)
  352. return false;
  353. unsigned char* v = &cont.verts[cont.nverts*4];
  354. v[0] = (unsigned char)x;
  355. v[1] = (unsigned char)y;
  356. v[2] = (unsigned char)z;
  357. v[3] = (unsigned char)r;
  358. cont.nverts++;
  359. return true;
  360. }
  361. static unsigned char getNeighbourReg(dtTileCacheLayer& layer,
  362. const int ax, const int ay, const int dir)
  363. {
  364. const int w = (int)layer.header->width;
  365. const int ia = ax + ay*w;
  366. const unsigned char con = layer.cons[ia] & 0xf;
  367. const unsigned char portal = layer.cons[ia] >> 4;
  368. const unsigned char mask = (unsigned char)(1<<dir);
  369. if ((con & mask) == 0)
  370. {
  371. // No connection, return portal or hard edge.
  372. if (portal & mask)
  373. return 0xf8 + (unsigned char)dir;
  374. return 0xff;
  375. }
  376. const int bx = ax + getDirOffsetX(dir);
  377. const int by = ay + getDirOffsetY(dir);
  378. const int ib = bx + by*w;
  379. return layer.regs[ib];
  380. }
  381. static bool walkContour(dtTileCacheLayer& layer, int x, int y, dtTempContour& cont)
  382. {
  383. const int w = (int)layer.header->width;
  384. const int h = (int)layer.header->height;
  385. cont.nverts = 0;
  386. int startX = x;
  387. int startY = y;
  388. int startDir = -1;
  389. for (int i = 0; i < 4; ++i)
  390. {
  391. const int dir = (i+3)&3;
  392. unsigned char rn = getNeighbourReg(layer, x, y, dir);
  393. if (rn != layer.regs[x+y*w])
  394. {
  395. startDir = dir;
  396. break;
  397. }
  398. }
  399. if (startDir == -1)
  400. return true;
  401. int dir = startDir;
  402. const int maxIter = w*h;
  403. int iter = 0;
  404. while (iter < maxIter)
  405. {
  406. unsigned char rn = getNeighbourReg(layer, x, y, dir);
  407. int nx = x;
  408. int ny = y;
  409. int ndir = dir;
  410. if (rn != layer.regs[x+y*w])
  411. {
  412. // Solid edge.
  413. int px = x;
  414. int pz = y;
  415. switch(dir)
  416. {
  417. case 0: pz++; break;
  418. case 1: px++; pz++; break;
  419. case 2: px++; break;
  420. }
  421. // Try to merge with previous vertex.
  422. if (!appendVertex(cont, px, (int)layer.heights[x+y*w], pz,rn))
  423. return false;
  424. ndir = (dir+1) & 0x3; // Rotate CW
  425. }
  426. else
  427. {
  428. // Move to next.
  429. nx = x + getDirOffsetX(dir);
  430. ny = y + getDirOffsetY(dir);
  431. ndir = (dir+3) & 0x3; // Rotate CCW
  432. }
  433. if (iter > 0 && x == startX && y == startY && dir == startDir)
  434. break;
  435. x = nx;
  436. y = ny;
  437. dir = ndir;
  438. iter++;
  439. }
  440. // Remove last vertex if it is duplicate of the first one.
  441. unsigned char* pa = &cont.verts[(cont.nverts-1)*4];
  442. unsigned char* pb = &cont.verts[0];
  443. if (pa[0] == pb[0] && pa[2] == pb[2])
  444. cont.nverts--;
  445. return true;
  446. }
  447. static float distancePtSeg(const int x, const int z,
  448. const int px, const int pz,
  449. const int qx, const int qz)
  450. {
  451. float pqx = (float)(qx - px);
  452. float pqz = (float)(qz - pz);
  453. float dx = (float)(x - px);
  454. float dz = (float)(z - pz);
  455. float d = pqx*pqx + pqz*pqz;
  456. float t = pqx*dx + pqz*dz;
  457. if (d > 0)
  458. t /= d;
  459. if (t < 0)
  460. t = 0;
  461. else if (t > 1)
  462. t = 1;
  463. dx = px + t*pqx - x;
  464. dz = pz + t*pqz - z;
  465. return dx*dx + dz*dz;
  466. }
  467. static void simplifyContour(dtTempContour& cont, const float maxError)
  468. {
  469. cont.npoly = 0;
  470. for (int i = 0; i < cont.nverts; ++i)
  471. {
  472. int j = (i+1) % cont.nverts;
  473. // Check for start of a wall segment.
  474. unsigned char ra = cont.verts[j*4+3];
  475. unsigned char rb = cont.verts[i*4+3];
  476. if (ra != rb)
  477. cont.poly[cont.npoly++] = (unsigned short)i;
  478. }
  479. if (cont.npoly < 2)
  480. {
  481. // If there is no transitions at all,
  482. // create some initial points for the simplification process.
  483. // Find lower-left and upper-right vertices of the contour.
  484. int llx = cont.verts[0];
  485. int llz = cont.verts[2];
  486. int lli = 0;
  487. int urx = cont.verts[0];
  488. int urz = cont.verts[2];
  489. int uri = 0;
  490. for (int i = 1; i < cont.nverts; ++i)
  491. {
  492. int x = cont.verts[i*4+0];
  493. int z = cont.verts[i*4+2];
  494. if (x < llx || (x == llx && z < llz))
  495. {
  496. llx = x;
  497. llz = z;
  498. lli = i;
  499. }
  500. if (x > urx || (x == urx && z > urz))
  501. {
  502. urx = x;
  503. urz = z;
  504. uri = i;
  505. }
  506. }
  507. cont.npoly = 0;
  508. cont.poly[cont.npoly++] = (unsigned short)lli;
  509. cont.poly[cont.npoly++] = (unsigned short)uri;
  510. }
  511. // Add points until all raw points are within
  512. // error tolerance to the simplified shape.
  513. for (int i = 0; i < cont.npoly; )
  514. {
  515. int ii = (i+1) % cont.npoly;
  516. const int ai = (int)cont.poly[i];
  517. const int ax = (int)cont.verts[ai*4+0];
  518. const int az = (int)cont.verts[ai*4+2];
  519. const int bi = (int)cont.poly[ii];
  520. const int bx = (int)cont.verts[bi*4+0];
  521. const int bz = (int)cont.verts[bi*4+2];
  522. // Find maximum deviation from the segment.
  523. float maxd = 0;
  524. int maxi = -1;
  525. int ci, cinc, endi;
  526. // Traverse the segment in lexilogical order so that the
  527. // max deviation is calculated similarly when traversing
  528. // opposite segments.
  529. if (bx > ax || (bx == ax && bz > az))
  530. {
  531. cinc = 1;
  532. ci = (ai+cinc) % cont.nverts;
  533. endi = bi;
  534. }
  535. else
  536. {
  537. cinc = cont.nverts-1;
  538. ci = (bi+cinc) % cont.nverts;
  539. endi = ai;
  540. }
  541. // Tessellate only outer edges or edges between areas.
  542. while (ci != endi)
  543. {
  544. float d = distancePtSeg(cont.verts[ci*4+0], cont.verts[ci*4+2], ax, az, bx, bz);
  545. if (d > maxd)
  546. {
  547. maxd = d;
  548. maxi = ci;
  549. }
  550. ci = (ci+cinc) % cont.nverts;
  551. }
  552. // If the max deviation is larger than accepted error,
  553. // add new point, else continue to next segment.
  554. if (maxi != -1 && maxd > (maxError*maxError))
  555. {
  556. cont.npoly++;
  557. for (int j = cont.npoly-1; j > i; --j)
  558. cont.poly[j] = cont.poly[j-1];
  559. cont.poly[i+1] = (unsigned short)maxi;
  560. }
  561. else
  562. {
  563. ++i;
  564. }
  565. }
  566. // Remap vertices
  567. int start = 0;
  568. for (int i = 1; i < cont.npoly; ++i)
  569. if (cont.poly[i] < cont.poly[start])
  570. start = i;
  571. cont.nverts = 0;
  572. for (int i = 0; i < cont.npoly; ++i)
  573. {
  574. const int j = (start+i) % cont.npoly;
  575. unsigned char* src = &cont.verts[cont.poly[j]*4];
  576. unsigned char* dst = &cont.verts[cont.nverts*4];
  577. dst[0] = src[0];
  578. dst[1] = src[1];
  579. dst[2] = src[2];
  580. dst[3] = src[3];
  581. cont.nverts++;
  582. }
  583. }
  584. static unsigned char getCornerHeight(dtTileCacheLayer& layer,
  585. const int x, const int y, const int z,
  586. const int walkableClimb,
  587. bool& shouldRemove)
  588. {
  589. const int w = (int)layer.header->width;
  590. const int h = (int)layer.header->height;
  591. int n = 0;
  592. unsigned char portal = 0xf;
  593. unsigned char height = 0;
  594. unsigned char preg = 0xff;
  595. bool allSameReg = true;
  596. for (int dz = -1; dz <= 0; ++dz)
  597. {
  598. for (int dx = -1; dx <= 0; ++dx)
  599. {
  600. const int px = x+dx;
  601. const int pz = z+dz;
  602. if (px >= 0 && pz >= 0 && px < w && pz < h)
  603. {
  604. const int idx = px + pz*w;
  605. const int lh = (int)layer.heights[idx];
  606. if (dtAbs(lh-y) <= walkableClimb && layer.areas[idx] != DT_TILECACHE_NULL_AREA)
  607. {
  608. height = dtMax(height, (unsigned char)lh);
  609. portal &= (layer.cons[idx] >> 4);
  610. if (preg != 0xff && preg != layer.regs[idx])
  611. allSameReg = false;
  612. preg = layer.regs[idx];
  613. n++;
  614. }
  615. }
  616. }
  617. }
  618. int portalCount = 0;
  619. for (int dir = 0; dir < 4; ++dir)
  620. if (portal & (1<<dir))
  621. portalCount++;
  622. shouldRemove = false;
  623. if (n > 1 && portalCount == 1 && allSameReg)
  624. {
  625. shouldRemove = true;
  626. }
  627. return height;
  628. }
  629. // TODO: move this somewhere else, once the layer meshing is done.
  630. dtStatus dtBuildTileCacheContours(dtTileCacheAlloc* alloc,
  631. dtTileCacheLayer& layer,
  632. const int walkableClimb, const float maxError,
  633. dtTileCacheContourSet& lcset)
  634. {
  635. dtAssert(alloc);
  636. const int w = (int)layer.header->width;
  637. const int h = (int)layer.header->height;
  638. lcset.nconts = layer.regCount;
  639. lcset.conts = (dtTileCacheContour*)alloc->alloc(sizeof(dtTileCacheContour)*lcset.nconts);
  640. if (!lcset.conts)
  641. return DT_FAILURE | DT_OUT_OF_MEMORY;
  642. memset(lcset.conts, 0, sizeof(dtTileCacheContour)*lcset.nconts);
  643. // Allocate temp buffer for contour tracing.
  644. const int maxTempVerts = (w+h)*2 * 2; // Twice around the layer.
  645. dtFixedArray<unsigned char> tempVerts(alloc, maxTempVerts*4);
  646. if (!tempVerts)
  647. return DT_FAILURE | DT_OUT_OF_MEMORY;
  648. dtFixedArray<unsigned short> tempPoly(alloc, maxTempVerts);
  649. if (!tempPoly)
  650. return DT_FAILURE | DT_OUT_OF_MEMORY;
  651. dtTempContour temp(tempVerts, maxTempVerts, tempPoly, maxTempVerts);
  652. // Find contours.
  653. for (int y = 0; y < h; ++y)
  654. {
  655. for (int x = 0; x < w; ++x)
  656. {
  657. const int idx = x+y*w;
  658. const unsigned char ri = layer.regs[idx];
  659. if (ri == 0xff)
  660. continue;
  661. dtTileCacheContour& cont = lcset.conts[ri];
  662. if (cont.nverts > 0)
  663. continue;
  664. cont.reg = ri;
  665. cont.area = layer.areas[idx];
  666. if (!walkContour(layer, x, y, temp))
  667. {
  668. // Too complex contour.
  669. // Note: If you hit here ofte, try increasing 'maxTempVerts'.
  670. return DT_FAILURE | DT_BUFFER_TOO_SMALL;
  671. }
  672. simplifyContour(temp, maxError);
  673. // Store contour.
  674. cont.nverts = temp.nverts;
  675. if (cont.nverts > 0)
  676. {
  677. cont.verts = (unsigned char*)alloc->alloc(sizeof(unsigned char)*4*temp.nverts);
  678. if (!cont.verts)
  679. return DT_FAILURE | DT_OUT_OF_MEMORY;
  680. for (int i = 0, j = temp.nverts-1; i < temp.nverts; j=i++)
  681. {
  682. unsigned char* dst = &cont.verts[j*4];
  683. unsigned char* v = &temp.verts[j*4];
  684. unsigned char* vn = &temp.verts[i*4];
  685. unsigned char nei = vn[3]; // The neighbour reg is stored at segment vertex of a segment.
  686. bool shouldRemove = false;
  687. unsigned char lh = getCornerHeight(layer, (int)v[0], (int)v[1], (int)v[2],
  688. walkableClimb, shouldRemove);
  689. dst[0] = v[0];
  690. dst[1] = lh;
  691. dst[2] = v[2];
  692. // Store portal direction and remove status to the fourth component.
  693. dst[3] = 0x0f;
  694. if (nei != 0xff && nei >= 0xf8)
  695. dst[3] = nei - 0xf8;
  696. if (shouldRemove)
  697. dst[3] |= 0x80;
  698. }
  699. }
  700. }
  701. }
  702. return DT_SUCCESS;
  703. }
  704. static const int VERTEX_BUCKET_COUNT2 = (1<<8);
  705. inline int computeVertexHash2(int x, int y, int z)
  706. {
  707. const unsigned int h1 = 0x8da6b343; // Large multiplicative constants;
  708. const unsigned int h2 = 0xd8163841; // here arbitrarily chosen primes
  709. const unsigned int h3 = 0xcb1ab31f;
  710. unsigned int n = h1 * x + h2 * y + h3 * z;
  711. return (int)(n & (VERTEX_BUCKET_COUNT2-1));
  712. }
  713. static unsigned short addVertex(unsigned short x, unsigned short y, unsigned short z,
  714. unsigned short* verts, unsigned short* firstVert, unsigned short* nextVert, int& nv)
  715. {
  716. int bucket = computeVertexHash2(x, 0, z);
  717. unsigned short i = firstVert[bucket];
  718. while (i != DT_TILECACHE_NULL_IDX)
  719. {
  720. const unsigned short* v = &verts[i*3];
  721. if (v[0] == x && v[2] == z && (dtAbs(v[1] - y) <= 2))
  722. return i;
  723. i = nextVert[i]; // next
  724. }
  725. // Could not find, create new.
  726. i = (unsigned short)nv; nv++;
  727. unsigned short* v = &verts[i*3];
  728. v[0] = x;
  729. v[1] = y;
  730. v[2] = z;
  731. nextVert[i] = firstVert[bucket];
  732. firstVert[bucket] = i;
  733. return (unsigned short)i;
  734. }
  735. struct rcEdge
  736. {
  737. unsigned short vert[2];
  738. unsigned short polyEdge[2];
  739. unsigned short poly[2];
  740. };
  741. static bool buildMeshAdjacency(dtTileCacheAlloc* alloc,
  742. unsigned short* polys, const int npolys,
  743. const unsigned short* verts, const int nverts,
  744. const dtTileCacheContourSet& lcset)
  745. {
  746. // Based on code by Eric Lengyel from:
  747. // http://www.terathon.com/code/edges.php
  748. const int maxEdgeCount = npolys*MAX_VERTS_PER_POLY;
  749. dtFixedArray<unsigned short> firstEdge(alloc, nverts + maxEdgeCount);
  750. if (!firstEdge)
  751. return false;
  752. unsigned short* nextEdge = firstEdge + nverts;
  753. int edgeCount = 0;
  754. dtFixedArray<rcEdge> edges(alloc, maxEdgeCount);
  755. if (!edges)
  756. return false;
  757. for (int i = 0; i < nverts; i++)
  758. firstEdge[i] = DT_TILECACHE_NULL_IDX;
  759. for (int i = 0; i < npolys; ++i)
  760. {
  761. unsigned short* t = &polys[i*MAX_VERTS_PER_POLY*2];
  762. for (int j = 0; j < MAX_VERTS_PER_POLY; ++j)
  763. {
  764. if (t[j] == DT_TILECACHE_NULL_IDX) break;
  765. unsigned short v0 = t[j];
  766. unsigned short v1 = (j+1 >= MAX_VERTS_PER_POLY || t[j+1] == DT_TILECACHE_NULL_IDX) ? t[0] : t[j+1];
  767. if (v0 < v1)
  768. {
  769. rcEdge& edge = edges[edgeCount];
  770. edge.vert[0] = v0;
  771. edge.vert[1] = v1;
  772. edge.poly[0] = (unsigned short)i;
  773. edge.polyEdge[0] = (unsigned short)j;
  774. edge.poly[1] = (unsigned short)i;
  775. edge.polyEdge[1] = 0xff;
  776. // Insert edge
  777. nextEdge[edgeCount] = firstEdge[v0];
  778. firstEdge[v0] = (unsigned short)edgeCount;
  779. edgeCount++;
  780. }
  781. }
  782. }
  783. for (int i = 0; i < npolys; ++i)
  784. {
  785. unsigned short* t = &polys[i*MAX_VERTS_PER_POLY*2];
  786. for (int j = 0; j < MAX_VERTS_PER_POLY; ++j)
  787. {
  788. if (t[j] == DT_TILECACHE_NULL_IDX) break;
  789. unsigned short v0 = t[j];
  790. unsigned short v1 = (j+1 >= MAX_VERTS_PER_POLY || t[j+1] == DT_TILECACHE_NULL_IDX) ? t[0] : t[j+1];
  791. if (v0 > v1)
  792. {
  793. bool found = false;
  794. for (unsigned short e = firstEdge[v1]; e != DT_TILECACHE_NULL_IDX; e = nextEdge[e])
  795. {
  796. rcEdge& edge = edges[e];
  797. if (edge.vert[1] == v0 && edge.poly[0] == edge.poly[1])
  798. {
  799. edge.poly[1] = (unsigned short)i;
  800. edge.polyEdge[1] = (unsigned short)j;
  801. found = true;
  802. break;
  803. }
  804. }
  805. if (!found)
  806. {
  807. // Matching edge not found, it is an open edge, add it.
  808. rcEdge& edge = edges[edgeCount];
  809. edge.vert[0] = v1;
  810. edge.vert[1] = v0;
  811. edge.poly[0] = (unsigned short)i;
  812. edge.polyEdge[0] = (unsigned short)j;
  813. edge.poly[1] = (unsigned short)i;
  814. edge.polyEdge[1] = 0xff;
  815. // Insert edge
  816. nextEdge[edgeCount] = firstEdge[v1];
  817. firstEdge[v1] = (unsigned short)edgeCount;
  818. edgeCount++;
  819. }
  820. }
  821. }
  822. }
  823. // Mark portal edges.
  824. for (int i = 0; i < lcset.nconts; ++i)
  825. {
  826. dtTileCacheContour& cont = lcset.conts[i];
  827. if (cont.nverts < 3)
  828. continue;
  829. for (int j = 0, k = cont.nverts-1; j < cont.nverts; k=j++)
  830. {
  831. const unsigned char* va = &cont.verts[k*4];
  832. const unsigned char* vb = &cont.verts[j*4];
  833. const unsigned char dir = va[3] & 0xf;
  834. if (dir == 0xf)
  835. continue;
  836. if (dir == 0 || dir == 2)
  837. {
  838. // Find matching vertical edge
  839. const unsigned short x = (unsigned short)va[0];
  840. unsigned short zmin = (unsigned short)va[2];
  841. unsigned short zmax = (unsigned short)vb[2];
  842. if (zmin > zmax)
  843. dtSwap(zmin, zmax);
  844. for (int m = 0; m < edgeCount; ++m)
  845. {
  846. rcEdge& e = edges[m];
  847. // Skip connected edges.
  848. if (e.poly[0] != e.poly[1])
  849. continue;
  850. const unsigned short* eva = &verts[e.vert[0]*3];
  851. const unsigned short* evb = &verts[e.vert[1]*3];
  852. if (eva[0] == x && evb[0] == x)
  853. {
  854. unsigned short ezmin = eva[2];
  855. unsigned short ezmax = evb[2];
  856. if (ezmin > ezmax)
  857. dtSwap(ezmin, ezmax);
  858. if (overlapRangeExl(zmin,zmax, ezmin, ezmax))
  859. {
  860. // Reuse the other polyedge to store dir.
  861. e.polyEdge[1] = dir;
  862. }
  863. }
  864. }
  865. }
  866. else
  867. {
  868. // Find matching vertical edge
  869. const unsigned short z = (unsigned short)va[2];
  870. unsigned short xmin = (unsigned short)va[0];
  871. unsigned short xmax = (unsigned short)vb[0];
  872. if (xmin > xmax)
  873. dtSwap(xmin, xmax);
  874. for (int m = 0; m < edgeCount; ++m)
  875. {
  876. rcEdge& e = edges[m];
  877. // Skip connected edges.
  878. if (e.poly[0] != e.poly[1])
  879. continue;
  880. const unsigned short* eva = &verts[e.vert[0]*3];
  881. const unsigned short* evb = &verts[e.vert[1]*3];
  882. if (eva[2] == z && evb[2] == z)
  883. {
  884. unsigned short exmin = eva[0];
  885. unsigned short exmax = evb[0];
  886. if (exmin > exmax)
  887. dtSwap(exmin, exmax);
  888. if (overlapRangeExl(xmin,xmax, exmin, exmax))
  889. {
  890. // Reuse the other polyedge to store dir.
  891. e.polyEdge[1] = dir;
  892. }
  893. }
  894. }
  895. }
  896. }
  897. }
  898. // Store adjacency
  899. for (int i = 0; i < edgeCount; ++i)
  900. {
  901. const rcEdge& e = edges[i];
  902. if (e.poly[0] != e.poly[1])
  903. {
  904. unsigned short* p0 = &polys[e.poly[0]*MAX_VERTS_PER_POLY*2];
  905. unsigned short* p1 = &polys[e.poly[1]*MAX_VERTS_PER_POLY*2];
  906. p0[MAX_VERTS_PER_POLY + e.polyEdge[0]] = e.poly[1];
  907. p1[MAX_VERTS_PER_POLY + e.polyEdge[1]] = e.poly[0];
  908. }
  909. else if (e.polyEdge[1] != 0xff)
  910. {
  911. unsigned short* p0 = &polys[e.poly[0]*MAX_VERTS_PER_POLY*2];
  912. p0[MAX_VERTS_PER_POLY + e.polyEdge[0]] = 0x8000 | (unsigned short)e.polyEdge[1];
  913. }
  914. }
  915. return true;
  916. }
  917. // Last time I checked the if version got compiled using cmov, which was a lot faster than module (with idiv).
  918. inline int prev(int i, int n) { return i-1 >= 0 ? i-1 : n-1; }
  919. inline int next(int i, int n) { return i+1 < n ? i+1 : 0; }
  920. inline int area2(const unsigned char* a, const unsigned char* b, const unsigned char* c)
  921. {
  922. return ((int)b[0] - (int)a[0]) * ((int)c[2] - (int)a[2]) - ((int)c[0] - (int)a[0]) * ((int)b[2] - (int)a[2]);
  923. }
  924. // Exclusive or: true iff exactly one argument is true.
  925. // The arguments are negated to ensure that they are 0/1
  926. // values. Then the bitwise Xor operator may apply.
  927. // (This idea is due to Michael Baldwin.)
  928. inline bool xorb(bool x, bool y)
  929. {
  930. return !x ^ !y;
  931. }
  932. // Returns true iff c is strictly to the left of the directed
  933. // line through a to b.
  934. inline bool left(const unsigned char* a, const unsigned char* b, const unsigned char* c)
  935. {
  936. return area2(a, b, c) < 0;
  937. }
  938. inline bool leftOn(const unsigned char* a, const unsigned char* b, const unsigned char* c)
  939. {
  940. return area2(a, b, c) <= 0;
  941. }
  942. inline bool collinear(const unsigned char* a, const unsigned char* b, const unsigned char* c)
  943. {
  944. return area2(a, b, c) == 0;
  945. }
  946. // Returns true iff ab properly intersects cd: they share
  947. // a point interior to both segments. The properness of the
  948. // intersection is ensured by using strict leftness.
  949. static bool intersectProp(const unsigned char* a, const unsigned char* b,
  950. const unsigned char* c, const unsigned char* d)
  951. {
  952. // Eliminate improper cases.
  953. if (collinear(a,b,c) || collinear(a,b,d) ||
  954. collinear(c,d,a) || collinear(c,d,b))
  955. return false;
  956. return xorb(left(a,b,c), left(a,b,d)) && xorb(left(c,d,a), left(c,d,b));
  957. }
  958. // Returns T iff (a,b,c) are collinear and point c lies
  959. // on the closed segement ab.
  960. static bool between(const unsigned char* a, const unsigned char* b, const unsigned char* c)
  961. {
  962. if (!collinear(a, b, c))
  963. return false;
  964. // If ab not vertical, check betweenness on x; else on y.
  965. if (a[0] != b[0])
  966. return ((a[0] <= c[0]) && (c[0] <= b[0])) || ((a[0] >= c[0]) && (c[0] >= b[0]));
  967. else
  968. return ((a[2] <= c[2]) && (c[2] <= b[2])) || ((a[2] >= c[2]) && (c[2] >= b[2]));
  969. }
  970. // Returns true iff segments ab and cd intersect, properly or improperly.
  971. static bool intersect(const unsigned char* a, const unsigned char* b,
  972. const unsigned char* c, const unsigned char* d)
  973. {
  974. if (intersectProp(a, b, c, d))
  975. return true;
  976. else if (between(a, b, c) || between(a, b, d) ||
  977. between(c, d, a) || between(c, d, b))
  978. return true;
  979. else
  980. return false;
  981. }
  982. static bool vequal(const unsigned char* a, const unsigned char* b)
  983. {
  984. return a[0] == b[0] && a[2] == b[2];
  985. }
  986. // Returns T iff (v_i, v_j) is a proper internal *or* external
  987. // diagonal of P, *ignoring edges incident to v_i and v_j*.
  988. static bool diagonalie(int i, int j, int n, const unsigned char* verts, const unsigned short* indices)
  989. {
  990. const unsigned char* d0 = &verts[(indices[i] & 0x7fff) * 4];
  991. const unsigned char* d1 = &verts[(indices[j] & 0x7fff) * 4];
  992. // For each edge (k,k+1) of P
  993. for (int k = 0; k < n; k++)
  994. {
  995. int k1 = next(k, n);
  996. // Skip edges incident to i or j
  997. if (!((k == i) || (k1 == i) || (k == j) || (k1 == j)))
  998. {
  999. const unsigned char* p0 = &verts[(indices[k] & 0x7fff) * 4];
  1000. const unsigned char* p1 = &verts[(indices[k1] & 0x7fff) * 4];
  1001. if (vequal(d0, p0) || vequal(d1, p0) || vequal(d0, p1) || vequal(d1, p1))
  1002. continue;
  1003. if (intersect(d0, d1, p0, p1))
  1004. return false;
  1005. }
  1006. }
  1007. return true;
  1008. }
  1009. // Returns true iff the diagonal (i,j) is strictly internal to the
  1010. // polygon P in the neighborhood of the i endpoint.
  1011. static bool inCone(int i, int j, int n, const unsigned char* verts, const unsigned short* indices)
  1012. {
  1013. const unsigned char* pi = &verts[(indices[i] & 0x7fff) * 4];
  1014. const unsigned char* pj = &verts[(indices[j] & 0x7fff) * 4];
  1015. const unsigned char* pi1 = &verts[(indices[next(i, n)] & 0x7fff) * 4];
  1016. const unsigned char* pin1 = &verts[(indices[prev(i, n)] & 0x7fff) * 4];
  1017. // If P[i] is a convex vertex [ i+1 left or on (i-1,i) ].
  1018. if (leftOn(pin1, pi, pi1))
  1019. return left(pi, pj, pin1) && left(pj, pi, pi1);
  1020. // Assume (i-1,i,i+1) not collinear.
  1021. // else P[i] is reflex.
  1022. return !(leftOn(pi, pj, pi1) && leftOn(pj, pi, pin1));
  1023. }
  1024. // Returns T iff (v_i, v_j) is a proper internal
  1025. // diagonal of P.
  1026. static bool diagonal(int i, int j, int n, const unsigned char* verts, const unsigned short* indices)
  1027. {
  1028. return inCone(i, j, n, verts, indices) && diagonalie(i, j, n, verts, indices);
  1029. }
  1030. static int triangulate(int n, const unsigned char* verts, unsigned short* indices, unsigned short* tris)
  1031. {
  1032. int ntris = 0;
  1033. unsigned short* dst = tris;
  1034. // The last bit of the index is used to indicate if the vertex can be removed.
  1035. for (int i = 0; i < n; i++)
  1036. {
  1037. int i1 = next(i, n);
  1038. int i2 = next(i1, n);
  1039. if (diagonal(i, i2, n, verts, indices))
  1040. indices[i1] |= 0x8000;
  1041. }
  1042. while (n > 3)
  1043. {
  1044. int minLen = -1;
  1045. int mini = -1;
  1046. for (int i = 0; i < n; i++)
  1047. {
  1048. int i1 = next(i, n);
  1049. if (indices[i1] & 0x8000)
  1050. {
  1051. const unsigned char* p0 = &verts[(indices[i] & 0x7fff) * 4];
  1052. const unsigned char* p2 = &verts[(indices[next(i1, n)] & 0x7fff) * 4];
  1053. const int dx = (int)p2[0] - (int)p0[0];
  1054. const int dz = (int)p2[2] - (int)p0[2];
  1055. const int len = dx*dx + dz*dz;
  1056. if (minLen < 0 || len < minLen)
  1057. {
  1058. minLen = len;
  1059. mini = i;
  1060. }
  1061. }
  1062. }
  1063. if (mini == -1)
  1064. {
  1065. // Should not happen.
  1066. /* printf("mini == -1 ntris=%d n=%d\n", ntris, n);
  1067. for (int i = 0; i < n; i++)
  1068. {
  1069. printf("%d ", indices[i] & 0x0fffffff);
  1070. }
  1071. printf("\n");*/
  1072. return -ntris;
  1073. }
  1074. int i = mini;
  1075. int i1 = next(i, n);
  1076. int i2 = next(i1, n);
  1077. *dst++ = indices[i] & 0x7fff;
  1078. *dst++ = indices[i1] & 0x7fff;
  1079. *dst++ = indices[i2] & 0x7fff;
  1080. ntris++;
  1081. // Removes P[i1] by copying P[i+1]...P[n-1] left one index.
  1082. n--;
  1083. for (int k = i1; k < n; k++)
  1084. indices[k] = indices[k+1];
  1085. if (i1 >= n) i1 = 0;
  1086. i = prev(i1,n);
  1087. // Update diagonal flags.
  1088. if (diagonal(prev(i, n), i1, n, verts, indices))
  1089. indices[i] |= 0x8000;
  1090. else
  1091. indices[i] &= 0x7fff;
  1092. if (diagonal(i, next(i1, n), n, verts, indices))
  1093. indices[i1] |= 0x8000;
  1094. else
  1095. indices[i1] &= 0x7fff;
  1096. }
  1097. // Append the remaining triangle.
  1098. *dst++ = indices[0] & 0x7fff;
  1099. *dst++ = indices[1] & 0x7fff;
  1100. *dst++ = indices[2] & 0x7fff;
  1101. ntris++;
  1102. return ntris;
  1103. }
  1104. static int countPolyVerts(const unsigned short* p)
  1105. {
  1106. for (int i = 0; i < MAX_VERTS_PER_POLY; ++i)
  1107. if (p[i] == DT_TILECACHE_NULL_IDX)
  1108. return i;
  1109. return MAX_VERTS_PER_POLY;
  1110. }
  1111. inline bool uleft(const unsigned short* a, const unsigned short* b, const unsigned short* c)
  1112. {
  1113. return ((int)b[0] - (int)a[0]) * ((int)c[2] - (int)a[2]) -
  1114. ((int)c[0] - (int)a[0]) * ((int)b[2] - (int)a[2]) < 0;
  1115. }
  1116. static int getPolyMergeValue(unsigned short* pa, unsigned short* pb,
  1117. const unsigned short* verts, int& ea, int& eb)
  1118. {
  1119. const int na = countPolyVerts(pa);
  1120. const int nb = countPolyVerts(pb);
  1121. // If the merged polygon would be too big, do not merge.
  1122. if (na+nb-2 > MAX_VERTS_PER_POLY)
  1123. return -1;
  1124. // Check if the polygons share an edge.
  1125. ea = -1;
  1126. eb = -1;
  1127. for (int i = 0; i < na; ++i)
  1128. {
  1129. unsigned short va0 = pa[i];
  1130. unsigned short va1 = pa[(i+1) % na];
  1131. if (va0 > va1)
  1132. dtSwap(va0, va1);
  1133. for (int j = 0; j < nb; ++j)
  1134. {
  1135. unsigned short vb0 = pb[j];
  1136. unsigned short vb1 = pb[(j+1) % nb];
  1137. if (vb0 > vb1)
  1138. dtSwap(vb0, vb1);
  1139. if (va0 == vb0 && va1 == vb1)
  1140. {
  1141. ea = i;
  1142. eb = j;
  1143. break;
  1144. }
  1145. }
  1146. }
  1147. // No common edge, cannot merge.
  1148. if (ea == -1 || eb == -1)
  1149. return -1;
  1150. // Check to see if the merged polygon would be convex.
  1151. unsigned short va, vb, vc;
  1152. va = pa[(ea+na-1) % na];
  1153. vb = pa[ea];
  1154. vc = pb[(eb+2) % nb];
  1155. if (!uleft(&verts[va*3], &verts[vb*3], &verts[vc*3]))
  1156. return -1;
  1157. va = pb[(eb+nb-1) % nb];
  1158. vb = pb[eb];
  1159. vc = pa[(ea+2) % na];
  1160. if (!uleft(&verts[va*3], &verts[vb*3], &verts[vc*3]))
  1161. return -1;
  1162. va = pa[ea];
  1163. vb = pa[(ea+1)%na];
  1164. int dx = (int)verts[va*3+0] - (int)verts[vb*3+0];
  1165. int dy = (int)verts[va*3+2] - (int)verts[vb*3+2];
  1166. return dx*dx + dy*dy;
  1167. }
  1168. static void mergePolys(unsigned short* pa, unsigned short* pb, int ea, int eb)
  1169. {
  1170. unsigned short tmp[MAX_VERTS_PER_POLY*2];
  1171. const int na = countPolyVerts(pa);
  1172. const int nb = countPolyVerts(pb);
  1173. // Merge polygons.
  1174. memset(tmp, 0xff, sizeof(unsigned short)*MAX_VERTS_PER_POLY*2);
  1175. int n = 0;
  1176. // Add pa
  1177. for (int i = 0; i < na-1; ++i)
  1178. tmp[n++] = pa[(ea+1+i) % na];
  1179. // Add pb
  1180. for (int i = 0; i < nb-1; ++i)
  1181. tmp[n++] = pb[(eb+1+i) % nb];
  1182. memcpy(pa, tmp, sizeof(unsigned short)*MAX_VERTS_PER_POLY);
  1183. }
  1184. static void pushFront(unsigned short v, unsigned short* arr, int& an)
  1185. {
  1186. an++;
  1187. for (int i = an-1; i > 0; --i)
  1188. arr[i] = arr[i-1];
  1189. arr[0] = v;
  1190. }
  1191. static void pushBack(unsigned short v, unsigned short* arr, int& an)
  1192. {
  1193. arr[an] = v;
  1194. an++;
  1195. }
  1196. static bool canRemoveVertex(dtTileCachePolyMesh& mesh, const unsigned short rem)
  1197. {
  1198. // Count number of polygons to remove.
  1199. int numRemovedVerts = 0;
  1200. int numTouchedVerts = 0;
  1201. int numRemainingEdges = 0;
  1202. for (int i = 0; i < mesh.npolys; ++i)
  1203. {
  1204. unsigned short* p = &mesh.polys[i*MAX_VERTS_PER_POLY*2];
  1205. const int nv = countPolyVerts(p);
  1206. int numRemoved = 0;
  1207. int numVerts = 0;
  1208. for (int j = 0; j < nv; ++j)
  1209. {
  1210. if (p[j] == rem)
  1211. {
  1212. numTouchedVerts++;
  1213. numRemoved++;
  1214. }
  1215. numVerts++;
  1216. }
  1217. if (numRemoved)
  1218. {
  1219. numRemovedVerts += numRemoved;
  1220. numRemainingEdges += numVerts-(numRemoved+1);
  1221. }
  1222. }
  1223. // There would be too few edges remaining to create a polygon.
  1224. // This can happen for example when a tip of a triangle is marked
  1225. // as deletion, but there are no other polys that share the vertex.
  1226. // In this case, the vertex should not be removed.
  1227. if (numRemainingEdges <= 2)
  1228. return false;
  1229. // Check that there is enough memory for the test.
  1230. const int maxEdges = numTouchedVerts*2;
  1231. if (maxEdges > MAX_REM_EDGES)
  1232. return false;
  1233. // Find edges which share the removed vertex.
  1234. unsigned short edges[MAX_REM_EDGES];
  1235. int nedges = 0;
  1236. for (int i = 0; i < mesh.npolys; ++i)
  1237. {
  1238. unsigned short* p = &mesh.polys[i*MAX_VERTS_PER_POLY*2];
  1239. const int nv = countPolyVerts(p);
  1240. // Collect edges which touches the removed vertex.
  1241. for (int j = 0, k = nv-1; j < nv; k = j++)
  1242. {
  1243. if (p[j] == rem || p[k] == rem)
  1244. {
  1245. // Arrange edge so that a=rem.
  1246. int a = p[j], b = p[k];
  1247. if (b == rem)
  1248. dtSwap(a,b);
  1249. // Check if the edge exists
  1250. bool exists = false;
  1251. for (int m = 0; m < nedges; ++m)
  1252. {
  1253. unsigned short* e = &edges[m*3];
  1254. if (e[1] == b)
  1255. {
  1256. // Exists, increment vertex share count.
  1257. e[2]++;
  1258. exists = true;
  1259. }
  1260. }
  1261. // Add new edge.
  1262. if (!exists)
  1263. {
  1264. unsigned short* e = &edges[nedges*3];
  1265. e[0] = (unsigned short)a;
  1266. e[1] = (unsigned short)b;
  1267. e[2] = 1;
  1268. nedges++;
  1269. }
  1270. }
  1271. }
  1272. }
  1273. // There should be no more than 2 open edges.
  1274. // This catches the case that two non-adjacent polygons
  1275. // share the removed vertex. In that case, do not remove the vertex.
  1276. int numOpenEdges = 0;
  1277. for (int i = 0; i < nedges; ++i)
  1278. {
  1279. if (edges[i*3+2] < 2)
  1280. numOpenEdges++;
  1281. }
  1282. if (numOpenEdges > 2)
  1283. return false;
  1284. return true;
  1285. }
  1286. static dtStatus removeVertex(dtTileCachePolyMesh& mesh, const unsigned short rem, const int maxTris)
  1287. {
  1288. // Count number of polygons to remove.
  1289. int numRemovedVerts = 0;
  1290. for (int i = 0; i < mesh.npolys; ++i)
  1291. {
  1292. unsigned short* p = &mesh.polys[i*MAX_VERTS_PER_POLY*2];
  1293. const int nv = countPolyVerts(p);
  1294. for (int j = 0; j < nv; ++j)
  1295. {
  1296. if (p[j] == rem)
  1297. numRemovedVerts++;
  1298. }
  1299. }
  1300. int nedges = 0;
  1301. unsigned short edges[MAX_REM_EDGES*3];
  1302. int nhole = 0;
  1303. unsigned short hole[MAX_REM_EDGES];
  1304. int nharea = 0;
  1305. unsigned short harea[MAX_REM_EDGES];
  1306. for (int i = 0; i < mesh.npolys; ++i)
  1307. {
  1308. unsigned short* p = &mesh.polys[i*MAX_VERTS_PER_POLY*2];
  1309. const int nv = countPolyVerts(p);
  1310. bool hasRem = false;
  1311. for (int j = 0; j < nv; ++j)
  1312. if (p[j] == rem) hasRem = true;
  1313. if (hasRem)
  1314. {
  1315. // Collect edges which does not touch the removed vertex.
  1316. for (int j = 0, k = nv-1; j < nv; k = j++)
  1317. {
  1318. if (p[j] != rem && p[k] != rem)
  1319. {
  1320. if (nedges >= MAX_REM_EDGES)
  1321. return DT_FAILURE | DT_BUFFER_TOO_SMALL;
  1322. unsigned short* e = &edges[nedges*3];
  1323. e[0] = p[k];
  1324. e[1] = p[j];
  1325. e[2] = mesh.areas[i];
  1326. nedges++;
  1327. }
  1328. }
  1329. // Remove the polygon.
  1330. unsigned short* p2 = &mesh.polys[(mesh.npolys-1)*MAX_VERTS_PER_POLY*2];
  1331. memcpy(p,p2,sizeof(unsigned short)*MAX_VERTS_PER_POLY);
  1332. memset(p+MAX_VERTS_PER_POLY,0xff,sizeof(unsigned short)*MAX_VERTS_PER_POLY);
  1333. mesh.areas[i] = mesh.areas[mesh.npolys-1];
  1334. mesh.npolys--;
  1335. --i;
  1336. }
  1337. }
  1338. // Remove vertex.
  1339. for (int i = (int)rem; i < mesh.nverts; ++i)
  1340. {
  1341. mesh.verts[i*3+0] = mesh.verts[(i+1)*3+0];
  1342. mesh.verts[i*3+1] = mesh.verts[(i+1)*3+1];
  1343. mesh.verts[i*3+2] = mesh.verts[(i+1)*3+2];
  1344. }
  1345. mesh.nverts--;
  1346. // Adjust indices to match the removed vertex layout.
  1347. for (int i = 0; i < mesh.npolys; ++i)
  1348. {
  1349. unsigned short* p = &mesh.polys[i*MAX_VERTS_PER_POLY*2];
  1350. const int nv = countPolyVerts(p);
  1351. for (int j = 0; j < nv; ++j)
  1352. if (p[j] > rem) p[j]--;
  1353. }
  1354. for (int i = 0; i < nedges; ++i)
  1355. {
  1356. if (edges[i*3+0] > rem) edges[i*3+0]--;
  1357. if (edges[i*3+1] > rem) edges[i*3+1]--;
  1358. }
  1359. if (nedges == 0)
  1360. return DT_SUCCESS;
  1361. // Start with one vertex, keep appending connected
  1362. // segments to the start and end of the hole.
  1363. pushBack(edges[0], hole, nhole);
  1364. pushBack(edges[2], harea, nharea);
  1365. while (nedges)
  1366. {
  1367. bool match = false;
  1368. for (int i = 0; i < nedges; ++i)
  1369. {
  1370. const unsigned short ea = edges[i*3+0];
  1371. const unsigned short eb = edges[i*3+1];
  1372. const unsigned short a = edges[i*3+2];
  1373. bool add = false;
  1374. if (hole[0] == eb)
  1375. {
  1376. // The segment matches the beginning of the hole boundary.
  1377. if (nhole >= MAX_REM_EDGES)
  1378. return DT_FAILURE | DT_BUFFER_TOO_SMALL;
  1379. pushFront(ea, hole, nhole);
  1380. pushFront(a, harea, nharea);
  1381. add = true;
  1382. }
  1383. else if (hole[nhole-1] == ea)
  1384. {
  1385. // The segment matches the end of the hole boundary.
  1386. if (nhole >= MAX_REM_EDGES)
  1387. return DT_FAILURE | DT_BUFFER_TOO_SMALL;
  1388. pushBack(eb, hole, nhole);
  1389. pushBack(a, harea, nharea);
  1390. add = true;
  1391. }
  1392. if (add)
  1393. {
  1394. // The edge segment was added, remove it.
  1395. edges[i*3+0] = edges[(nedges-1)*3+0];
  1396. edges[i*3+1] = edges[(nedges-1)*3+1];
  1397. edges[i*3+2] = edges[(nedges-1)*3+2];
  1398. --nedges;
  1399. match = true;
  1400. --i;
  1401. }
  1402. }
  1403. if (!match)
  1404. break;
  1405. }
  1406. unsigned short tris[MAX_REM_EDGES*3];
  1407. unsigned char tverts[MAX_REM_EDGES*3];
  1408. unsigned short tpoly[MAX_REM_EDGES*3];
  1409. // Generate temp vertex array for triangulation.
  1410. for (int i = 0; i < nhole; ++i)
  1411. {
  1412. const unsigned short pi = hole[i];
  1413. tverts[i*4+0] = (unsigned char)mesh.verts[pi*3+0];
  1414. tverts[i*4+1] = (unsigned char)mesh.verts[pi*3+1];
  1415. tverts[i*4+2] = (unsigned char)mesh.verts[pi*3+2];
  1416. tverts[i*4+3] = 0;
  1417. tpoly[i] = (unsigned short)i;
  1418. }
  1419. // Triangulate the hole.
  1420. int ntris = triangulate(nhole, tverts, tpoly, tris);
  1421. if (ntris < 0)
  1422. {
  1423. // TODO: issue warning!
  1424. ntris = -ntris;
  1425. }
  1426. if (ntris > MAX_REM_EDGES)
  1427. return DT_FAILURE | DT_BUFFER_TOO_SMALL;
  1428. unsigned short polys[MAX_REM_EDGES*MAX_VERTS_PER_POLY];
  1429. unsigned char pareas[MAX_REM_EDGES];
  1430. // Build initial polygons.
  1431. int npolys = 0;
  1432. memset(polys, 0xff, ntris*MAX_VERTS_PER_POLY*sizeof(unsigned short));
  1433. for (int j = 0; j < ntris; ++j)
  1434. {
  1435. unsigned short* t = &tris[j*3];
  1436. if (t[0] != t[1] && t[0] != t[2] && t[1] != t[2])
  1437. {
  1438. polys[npolys*MAX_VERTS_PER_POLY+0] = hole[t[0]];
  1439. polys[npolys*MAX_VERTS_PER_POLY+1] = hole[t[1]];
  1440. polys[npolys*MAX_VERTS_PER_POLY+2] = hole[t[2]];
  1441. pareas[npolys] = (unsigned char)harea[t[0]];
  1442. npolys++;
  1443. }
  1444. }
  1445. if (!npolys)
  1446. return DT_SUCCESS;
  1447. // Merge polygons.
  1448. int maxVertsPerPoly = MAX_VERTS_PER_POLY;
  1449. if (maxVertsPerPoly > 3)
  1450. {
  1451. for (;;)
  1452. {
  1453. // Find best polygons to merge.
  1454. int bestMergeVal = 0;
  1455. int bestPa = 0, bestPb = 0, bestEa = 0, bestEb = 0;
  1456. for (int j = 0; j < npolys-1; ++j)
  1457. {
  1458. unsigned short* pj = &polys[j*MAX_VERTS_PER_POLY];
  1459. for (int k = j+1; k < npolys; ++k)
  1460. {
  1461. unsigned short* pk = &polys[k*MAX_VERTS_PER_POLY];
  1462. int ea, eb;
  1463. int v = getPolyMergeValue(pj, pk, mesh.verts, ea, eb);
  1464. if (v > bestMergeVal)
  1465. {
  1466. bestMergeVal = v;
  1467. bestPa = j;
  1468. bestPb = k;
  1469. bestEa = ea;
  1470. bestEb = eb;
  1471. }
  1472. }
  1473. }
  1474. if (bestMergeVal > 0)
  1475. {
  1476. // Found best, merge.
  1477. unsigned short* pa = &polys[bestPa*MAX_VERTS_PER_POLY];
  1478. unsigned short* pb = &polys[bestPb*MAX_VERTS_PER_POLY];
  1479. mergePolys(pa, pb, bestEa, bestEb);
  1480. memcpy(pb, &polys[(npolys-1)*MAX_VERTS_PER_POLY], sizeof(unsigned short)*MAX_VERTS_PER_POLY);
  1481. pareas[bestPb] = pareas[npolys-1];
  1482. npolys--;
  1483. }
  1484. else
  1485. {
  1486. // Could not merge any polygons, stop.
  1487. break;
  1488. }
  1489. }
  1490. }
  1491. // Store polygons.
  1492. for (int i = 0; i < npolys; ++i)
  1493. {
  1494. if (mesh.npolys >= maxTris) break;
  1495. unsigned short* p = &mesh.polys[mesh.npolys*MAX_VERTS_PER_POLY*2];
  1496. memset(p,0xff,sizeof(unsigned short)*MAX_VERTS_PER_POLY*2);
  1497. for (int j = 0; j < MAX_VERTS_PER_POLY; ++j)
  1498. p[j] = polys[i*MAX_VERTS_PER_POLY+j];
  1499. mesh.areas[mesh.npolys] = pareas[i];
  1500. mesh.npolys++;
  1501. if (mesh.npolys > maxTris)
  1502. return DT_FAILURE | DT_BUFFER_TOO_SMALL;
  1503. }
  1504. return DT_SUCCESS;
  1505. }
  1506. dtStatus dtBuildTileCachePolyMesh(dtTileCacheAlloc* alloc,
  1507. dtTileCacheContourSet& lcset,
  1508. dtTileCachePolyMesh& mesh)
  1509. {
  1510. dtAssert(alloc);
  1511. int maxVertices = 0;
  1512. int maxTris = 0;
  1513. int maxVertsPerCont = 0;
  1514. for (int i = 0; i < lcset.nconts; ++i)
  1515. {
  1516. // Skip null contours.
  1517. if (lcset.conts[i].nverts < 3) continue;
  1518. maxVertices += lcset.conts[i].nverts;
  1519. maxTris += lcset.conts[i].nverts - 2;
  1520. maxVertsPerCont = dtMax(maxVertsPerCont, lcset.conts[i].nverts);
  1521. }
  1522. // TODO: warn about too many vertices?
  1523. mesh.nvp = MAX_VERTS_PER_POLY;
  1524. dtFixedArray<unsigned char> vflags(alloc, maxVertices);
  1525. if (!vflags)
  1526. return DT_FAILURE | DT_OUT_OF_MEMORY;
  1527. memset(vflags, 0, maxVertices);
  1528. mesh.verts = (unsigned short*)alloc->alloc(sizeof(unsigned short)*maxVertices*3);
  1529. if (!mesh.verts)
  1530. return DT_FAILURE | DT_OUT_OF_MEMORY;
  1531. mesh.polys = (unsigned short*)alloc->alloc(sizeof(unsigned short)*maxTris*MAX_VERTS_PER_POLY*2);
  1532. if (!mesh.polys)
  1533. return DT_FAILURE | DT_OUT_OF_MEMORY;
  1534. mesh.areas = (unsigned char*)alloc->alloc(sizeof(unsigned char)*maxTris);
  1535. if (!mesh.areas)
  1536. return DT_FAILURE | DT_OUT_OF_MEMORY;
  1537. mesh.flags = (unsigned short*)alloc->alloc(sizeof(unsigned short)*maxTris);
  1538. if (!mesh.flags)
  1539. return DT_FAILURE | DT_OUT_OF_MEMORY;
  1540. // Just allocate and clean the mesh flags array. The user is resposible for filling it.
  1541. memset(mesh.flags, 0, sizeof(unsigned short) * maxTris);
  1542. mesh.nverts = 0;
  1543. mesh.npolys = 0;
  1544. memset(mesh.verts, 0, sizeof(unsigned short)*maxVertices*3);
  1545. memset(mesh.polys, 0xff, sizeof(unsigned short)*maxTris*MAX_VERTS_PER_POLY*2);
  1546. memset(mesh.areas, 0, sizeof(unsigned char)*maxTris);
  1547. unsigned short firstVert[VERTEX_BUCKET_COUNT2];
  1548. for (int i = 0; i < VERTEX_BUCKET_COUNT2; ++i)
  1549. firstVert[i] = DT_TILECACHE_NULL_IDX;
  1550. dtFixedArray<unsigned short> nextVert(alloc, maxVertices);
  1551. if (!nextVert)
  1552. return DT_FAILURE | DT_OUT_OF_MEMORY;
  1553. memset(nextVert, 0, sizeof(unsigned short)*maxVertices);
  1554. dtFixedArray<unsigned short> indices(alloc, maxVertsPerCont);
  1555. if (!indices)
  1556. return DT_FAILURE | DT_OUT_OF_MEMORY;
  1557. dtFixedArray<unsigned short> tris(alloc, maxVertsPerCont*3);
  1558. if (!tris)
  1559. return DT_FAILURE | DT_OUT_OF_MEMORY;
  1560. dtFixedArray<unsigned short> polys(alloc, maxVertsPerCont*MAX_VERTS_PER_POLY);
  1561. if (!polys)
  1562. return DT_FAILURE | DT_OUT_OF_MEMORY;
  1563. for (int i = 0; i < lcset.nconts; ++i)
  1564. {
  1565. dtTileCacheContour& cont = lcset.conts[i];
  1566. // Skip null contours.
  1567. if (cont.nverts < 3)
  1568. continue;
  1569. // Triangulate contour
  1570. for (int j = 0; j < cont.nverts; ++j)
  1571. indices[j] = (unsigned short)j;
  1572. int ntris = triangulate(cont.nverts, cont.verts, &indices[0], &tris[0]);
  1573. if (ntris <= 0)
  1574. {
  1575. // TODO: issue warning!
  1576. ntris = -ntris;
  1577. }
  1578. // Add and merge vertices.
  1579. for (int j = 0; j < cont.nverts; ++j)
  1580. {
  1581. const unsigned char* v = &cont.verts[j*4];
  1582. indices[j] = addVertex((unsigned short)v[0], (unsigned short)v[1], (unsigned short)v[2],
  1583. mesh.verts, firstVert, nextVert, mesh.nverts);
  1584. if (v[3] & 0x80)
  1585. {
  1586. // This vertex should be removed.
  1587. vflags[indices[j]] = 1;
  1588. }
  1589. }
  1590. // Build initial polygons.
  1591. int npolys = 0;
  1592. memset(polys, 0xff, sizeof(unsigned short) * maxVertsPerCont * MAX_VERTS_PER_POLY);
  1593. for (int j = 0; j < ntris; ++j)
  1594. {
  1595. const unsigned short* t = &tris[j*3];
  1596. if (t[0] != t[1] && t[0] != t[2] && t[1] != t[2])
  1597. {
  1598. polys[npolys*MAX_VERTS_PER_POLY+0] = indices[t[0]];
  1599. polys[npolys*MAX_VERTS_PER_POLY+1] = indices[t[1]];
  1600. polys[npolys*MAX_VERTS_PER_POLY+2] = indices[t[2]];
  1601. npolys++;
  1602. }
  1603. }
  1604. if (!npolys)
  1605. continue;
  1606. // Merge polygons.
  1607. int maxVertsPerPoly =MAX_VERTS_PER_POLY ;
  1608. if (maxVertsPerPoly > 3)
  1609. {
  1610. for(;;)
  1611. {
  1612. // Find best polygons to merge.
  1613. int bestMergeVal = 0;
  1614. int bestPa = 0, bestPb = 0, bestEa = 0, bestEb = 0;
  1615. for (int j = 0; j < npolys-1; ++j)
  1616. {
  1617. unsigned short* pj = &polys[j*MAX_VERTS_PER_POLY];
  1618. for (int k = j+1; k < npolys; ++k)
  1619. {
  1620. unsigned short* pk = &polys[k*MAX_VERTS_PER_POLY];
  1621. int ea, eb;
  1622. int v = getPolyMergeValue(pj, pk, mesh.verts, ea, eb);
  1623. if (v > bestMergeVal)
  1624. {
  1625. bestMergeVal = v;
  1626. bestPa = j;
  1627. bestPb = k;
  1628. bestEa = ea;
  1629. bestEb = eb;
  1630. }
  1631. }
  1632. }
  1633. if (bestMergeVal > 0)
  1634. {
  1635. // Found best, merge.
  1636. unsigned short* pa = &polys[bestPa*MAX_VERTS_PER_POLY];
  1637. unsigned short* pb = &polys[bestPb*MAX_VERTS_PER_POLY];
  1638. mergePolys(pa, pb, bestEa, bestEb);
  1639. memcpy(pb, &polys[(npolys-1)*MAX_VERTS_PER_POLY], sizeof(unsigned short)*MAX_VERTS_PER_POLY);
  1640. npolys--;
  1641. }
  1642. else
  1643. {
  1644. // Could not merge any polygons, stop.
  1645. break;
  1646. }
  1647. }
  1648. }
  1649. // Store polygons.
  1650. for (int j = 0; j < npolys; ++j)
  1651. {
  1652. unsigned short* p = &mesh.polys[mesh.npolys*MAX_VERTS_PER_POLY*2];
  1653. unsigned short* q = &polys[j*MAX_VERTS_PER_POLY];
  1654. for (int k = 0; k < MAX_VERTS_PER_POLY; ++k)
  1655. p[k] = q[k];
  1656. mesh.areas[mesh.npolys] = cont.area;
  1657. mesh.npolys++;
  1658. if (mesh.npolys > maxTris)
  1659. return DT_FAILURE | DT_BUFFER_TOO_SMALL;
  1660. }
  1661. }
  1662. // Remove edge vertices.
  1663. for (int i = 0; i < mesh.nverts; ++i)
  1664. {
  1665. if (vflags[i])
  1666. {
  1667. if (!canRemoveVertex(mesh, (unsigned short)i))
  1668. continue;
  1669. dtStatus status = removeVertex(mesh, (unsigned short)i, maxTris);
  1670. if (dtStatusFailed(status))
  1671. return status;
  1672. // Remove vertex
  1673. // Note: mesh.nverts is already decremented inside removeVertex()!
  1674. for (int j = i; j < mesh.nverts; ++j)
  1675. vflags[j] = vflags[j+1];
  1676. --i;
  1677. }
  1678. }
  1679. // Calculate adjacency.
  1680. if (!buildMeshAdjacency(alloc, mesh.polys, mesh.npolys, mesh.verts, mesh.nverts, lcset))
  1681. return DT_FAILURE | DT_OUT_OF_MEMORY;
  1682. return DT_SUCCESS;
  1683. }
  1684. dtStatus dtMarkCylinderArea(dtTileCacheLayer& layer, const float* orig, const float cs, const float ch,
  1685. const float* pos, const float radius, const float height, const unsigned char areaId)
  1686. {
  1687. float bmin[3], bmax[3];
  1688. bmin[0] = pos[0] - radius;
  1689. bmin[1] = pos[1];
  1690. bmin[2] = pos[2] - radius;
  1691. bmax[0] = pos[0] + radius;
  1692. bmax[1] = pos[1] + height;
  1693. bmax[2] = pos[2] + radius;
  1694. const float r2 = dtSqr(radius/cs + 0.5f);
  1695. const int w = (int)layer.header->width;
  1696. const int h = (int)layer.header->height;
  1697. const float ics = 1.0f/cs;
  1698. const float ich = 1.0f/ch;
  1699. const float px = (pos[0]-orig[0])*ics;
  1700. const float pz = (pos[2]-orig[2])*ics;
  1701. int minx = (int)dtMathFloorf((bmin[0]-orig[0])*ics);
  1702. int miny = (int)dtMathFloorf((bmin[1]-orig[1])*ich);
  1703. int minz = (int)dtMathFloorf((bmin[2]-orig[2])*ics);
  1704. int maxx = (int)dtMathFloorf((bmax[0]-orig[0])*ics);
  1705. int maxy = (int)dtMathFloorf((bmax[1]-orig[1])*ich);
  1706. int maxz = (int)dtMathFloorf((bmax[2]-orig[2])*ics);
  1707. if (maxx < 0) return DT_SUCCESS;
  1708. if (minx >= w) return DT_SUCCESS;
  1709. if (maxz < 0) return DT_SUCCESS;
  1710. if (minz >= h) return DT_SUCCESS;
  1711. if (minx < 0) minx = 0;
  1712. if (maxx >= w) maxx = w-1;
  1713. if (minz < 0) minz = 0;
  1714. if (maxz >= h) maxz = h-1;
  1715. for (int z = minz; z <= maxz; ++z)
  1716. {
  1717. for (int x = minx; x <= maxx; ++x)
  1718. {
  1719. const float dx = (float)(x+0.5f) - px;
  1720. const float dz = (float)(z+0.5f) - pz;
  1721. if (dx*dx + dz*dz > r2)
  1722. continue;
  1723. const int y = layer.heights[x+z*w];
  1724. if (y < miny || y > maxy)
  1725. continue;
  1726. layer.areas[x+z*w] = areaId;
  1727. }
  1728. }
  1729. return DT_SUCCESS;
  1730. }
  1731. dtStatus dtMarkBoxArea(dtTileCacheLayer& layer, const float* orig, const float cs, const float ch,
  1732. const float* bmin, const float* bmax, const unsigned char areaId)
  1733. {
  1734. const int w = (int)layer.header->width;
  1735. const int h = (int)layer.header->height;
  1736. const float ics = 1.0f/cs;
  1737. const float ich = 1.0f/ch;
  1738. int minx = (int)floorf((bmin[0]-orig[0])*ics);
  1739. int miny = (int)floorf((bmin[1]-orig[1])*ich);
  1740. int minz = (int)floorf((bmin[2]-orig[2])*ics);
  1741. int maxx = (int)floorf((bmax[0]-orig[0])*ics);
  1742. int maxy = (int)floorf((bmax[1]-orig[1])*ich);
  1743. int maxz = (int)floorf((bmax[2]-orig[2])*ics);
  1744. if (maxx < 0) return DT_SUCCESS;
  1745. if (minx >= w) return DT_SUCCESS;
  1746. if (maxz < 0) return DT_SUCCESS;
  1747. if (minz >= h) return DT_SUCCESS;
  1748. if (minx < 0) minx = 0;
  1749. if (maxx >= w) maxx = w-1;
  1750. if (minz < 0) minz = 0;
  1751. if (maxz >= h) maxz = h-1;
  1752. for (int z = minz; z <= maxz; ++z)
  1753. {
  1754. for (int x = minx; x <= maxx; ++x)
  1755. {
  1756. const int y = layer.heights[x+z*w];
  1757. if (y < miny || y > maxy)
  1758. continue;
  1759. layer.areas[x+z*w] = areaId;
  1760. }
  1761. }
  1762. return DT_SUCCESS;
  1763. }
  1764. dtStatus dtMarkBoxArea(dtTileCacheLayer& layer, const float* orig, const float cs, const float ch,
  1765. const float* center, const float* halfExtents, const float* rotAux, const unsigned char areaId)
  1766. {
  1767. const int w = (int)layer.header->width;
  1768. const int h = (int)layer.header->height;
  1769. const float ics = 1.0f/cs;
  1770. const float ich = 1.0f/ch;
  1771. float cx = (center[0] - orig[0])*ics;
  1772. float cz = (center[2] - orig[2])*ics;
  1773. float maxr = 1.41f*dtMax(halfExtents[0], halfExtents[2]);
  1774. int minx = (int)floorf(cx - maxr*ics);
  1775. int maxx = (int)floorf(cx + maxr*ics);
  1776. int minz = (int)floorf(cz - maxr*ics);
  1777. int maxz = (int)floorf(cz + maxr*ics);
  1778. int miny = (int)floorf((center[1]-halfExtents[1]-orig[1])*ich);
  1779. int maxy = (int)floorf((center[1]+halfExtents[1]-orig[1])*ich);
  1780. if (maxx < 0) return DT_SUCCESS;
  1781. if (minx >= w) return DT_SUCCESS;
  1782. if (maxz < 0) return DT_SUCCESS;
  1783. if (minz >= h) return DT_SUCCESS;
  1784. if (minx < 0) minx = 0;
  1785. if (maxx >= w) maxx = w-1;
  1786. if (minz < 0) minz = 0;
  1787. if (maxz >= h) maxz = h-1;
  1788. float xhalf = halfExtents[0]*ics + 0.5f;
  1789. float zhalf = halfExtents[2]*ics + 0.5f;
  1790. for (int z = minz; z <= maxz; ++z)
  1791. {
  1792. for (int x = minx; x <= maxx; ++x)
  1793. {
  1794. float x2 = 2.0f*(float(x) - cx);
  1795. float z2 = 2.0f*(float(z) - cz);
  1796. float xrot = rotAux[1]*x2 + rotAux[0]*z2;
  1797. if (xrot > xhalf || xrot < -xhalf)
  1798. continue;
  1799. float zrot = rotAux[1]*z2 - rotAux[0]*x2;
  1800. if (zrot > zhalf || zrot < -zhalf)
  1801. continue;
  1802. const int y = layer.heights[x+z*w];
  1803. if (y < miny || y > maxy)
  1804. continue;
  1805. layer.areas[x+z*w] = areaId;
  1806. }
  1807. }
  1808. return DT_SUCCESS;
  1809. }
  1810. dtStatus dtBuildTileCacheLayer(dtTileCacheCompressor* comp,
  1811. dtTileCacheLayerHeader* header,
  1812. const unsigned char* heights,
  1813. const unsigned char* areas,
  1814. const unsigned char* cons,
  1815. unsigned char** outData, int* outDataSize)
  1816. {
  1817. const int headerSize = dtAlign4(sizeof(dtTileCacheLayerHeader));
  1818. const int gridSize = (int)header->width * (int)header->height;
  1819. const int maxDataSize = headerSize + comp->maxCompressedSize(gridSize*3);
  1820. unsigned char* data = (unsigned char*)dtAlloc(maxDataSize, DT_ALLOC_PERM);
  1821. if (!data)
  1822. return DT_FAILURE | DT_OUT_OF_MEMORY;
  1823. memset(data, 0, maxDataSize);
  1824. // Store header
  1825. memcpy(data, header, sizeof(dtTileCacheLayerHeader));
  1826. // Concatenate grid data for compression.
  1827. const int bufferSize = gridSize*3;
  1828. unsigned char* buffer = (unsigned char*)dtAlloc(bufferSize, DT_ALLOC_TEMP);
  1829. if (!buffer)
  1830. {
  1831. dtFree(data);
  1832. return DT_FAILURE | DT_OUT_OF_MEMORY;
  1833. }
  1834. memcpy(buffer, heights, gridSize);
  1835. memcpy(buffer+gridSize, areas, gridSize);
  1836. memcpy(buffer+gridSize*2, cons, gridSize);
  1837. // Compress
  1838. unsigned char* compressed = data + headerSize;
  1839. const int maxCompressedSize = maxDataSize - headerSize;
  1840. int compressedSize = 0;
  1841. dtStatus status = comp->compress(buffer, bufferSize, compressed, maxCompressedSize, &compressedSize);
  1842. if (dtStatusFailed(status))
  1843. {
  1844. dtFree(buffer);
  1845. dtFree(data);
  1846. return status;
  1847. }
  1848. *outData = data;
  1849. *outDataSize = headerSize + compressedSize;
  1850. dtFree(buffer);
  1851. return DT_SUCCESS;
  1852. }
  1853. void dtFreeTileCacheLayer(dtTileCacheAlloc* alloc, dtTileCacheLayer* layer)
  1854. {
  1855. dtAssert(alloc);
  1856. // The layer is allocated as one conitguous blob of data.
  1857. alloc->free(layer);
  1858. }
  1859. dtStatus dtDecompressTileCacheLayer(dtTileCacheAlloc* alloc, dtTileCacheCompressor* comp,
  1860. unsigned char* compressed, const int compressedSize,
  1861. dtTileCacheLayer** layerOut)
  1862. {
  1863. dtAssert(alloc);
  1864. dtAssert(comp);
  1865. if (!layerOut)
  1866. return DT_FAILURE | DT_INVALID_PARAM;
  1867. if (!compressed)
  1868. return DT_FAILURE | DT_INVALID_PARAM;
  1869. *layerOut = 0;
  1870. dtTileCacheLayerHeader* compressedHeader = (dtTileCacheLayerHeader*)compressed;
  1871. if (compressedHeader->magic != DT_TILECACHE_MAGIC)
  1872. return DT_FAILURE | DT_WRONG_MAGIC;
  1873. if (compressedHeader->version != DT_TILECACHE_VERSION)
  1874. return DT_FAILURE | DT_WRONG_VERSION;
  1875. const int layerSize = dtAlign4(sizeof(dtTileCacheLayer));
  1876. const int headerSize = dtAlign4(sizeof(dtTileCacheLayerHeader));
  1877. const int gridSize = (int)compressedHeader->width * (int)compressedHeader->height;
  1878. const int bufferSize = layerSize + headerSize + gridSize*4;
  1879. unsigned char* buffer = (unsigned char*)alloc->alloc(bufferSize);
  1880. if (!buffer)
  1881. return DT_FAILURE | DT_OUT_OF_MEMORY;
  1882. memset(buffer, 0, bufferSize);
  1883. dtTileCacheLayer* layer = (dtTileCacheLayer*)buffer;
  1884. dtTileCacheLayerHeader* header = (dtTileCacheLayerHeader*)(buffer + layerSize);
  1885. unsigned char* grids = buffer + layerSize + headerSize;
  1886. const int gridsSize = bufferSize - (layerSize + headerSize);
  1887. // Copy header
  1888. memcpy(header, compressedHeader, headerSize);
  1889. // Decompress grid.
  1890. int size = 0;
  1891. dtStatus status = comp->decompress(compressed+headerSize, compressedSize-headerSize,
  1892. grids, gridsSize, &size);
  1893. if (dtStatusFailed(status))
  1894. {
  1895. alloc->free(buffer);
  1896. return status;
  1897. }
  1898. layer->header = header;
  1899. layer->heights = grids;
  1900. layer->areas = grids + gridSize;
  1901. layer->cons = grids + gridSize*2;
  1902. layer->regs = grids + gridSize*3;
  1903. *layerOut = layer;
  1904. return DT_SUCCESS;
  1905. }
  1906. bool dtTileCacheHeaderSwapEndian(unsigned char* data, const int dataSize)
  1907. {
  1908. dtIgnoreUnused(dataSize);
  1909. dtTileCacheLayerHeader* header = (dtTileCacheLayerHeader*)data;
  1910. int swappedMagic = DT_TILECACHE_MAGIC;
  1911. int swappedVersion = DT_TILECACHE_VERSION;
  1912. dtSwapEndian(&swappedMagic);
  1913. dtSwapEndian(&swappedVersion);
  1914. if ((header->magic != DT_TILECACHE_MAGIC || header->version != DT_TILECACHE_VERSION) &&
  1915. (header->magic != swappedMagic || header->version != swappedVersion))
  1916. {
  1917. return false;
  1918. }
  1919. dtSwapEndian(&header->magic);
  1920. dtSwapEndian(&header->version);
  1921. dtSwapEndian(&header->tx);
  1922. dtSwapEndian(&header->ty);
  1923. dtSwapEndian(&header->tlayer);
  1924. dtSwapEndian(&header->bmin[0]);
  1925. dtSwapEndian(&header->bmin[1]);
  1926. dtSwapEndian(&header->bmin[2]);
  1927. dtSwapEndian(&header->bmax[0]);
  1928. dtSwapEndian(&header->bmax[1]);
  1929. dtSwapEndian(&header->bmax[2]);
  1930. dtSwapEndian(&header->hmin);
  1931. dtSwapEndian(&header->hmax);
  1932. // width, height, minx, maxx, miny, maxy are unsigned char, no need to swap.
  1933. return true;
  1934. }