9
3

RecastMesh.cpp 42 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552
  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. #define _USE_MATH_DEFINES
  19. #include <math.h>
  20. #include <string.h>
  21. #include <stdio.h>
  22. #include "Recast.h"
  23. #include "RecastAlloc.h"
  24. #include "RecastAssert.h"
  25. struct rcEdge
  26. {
  27. unsigned short vert[2];
  28. unsigned short polyEdge[2];
  29. unsigned short poly[2];
  30. };
  31. static bool buildMeshAdjacency(unsigned short* polys, const int npolys,
  32. const int nverts, const int vertsPerPoly)
  33. {
  34. // Based on code by Eric Lengyel from:
  35. // http://www.terathon.com/code/edges.php
  36. int maxEdgeCount = npolys*vertsPerPoly;
  37. unsigned short* firstEdge = (unsigned short*)rcAlloc(sizeof(unsigned short)*(nverts + maxEdgeCount), RC_ALLOC_TEMP);
  38. if (!firstEdge)
  39. return false;
  40. unsigned short* nextEdge = firstEdge + nverts;
  41. int edgeCount = 0;
  42. rcEdge* edges = (rcEdge*)rcAlloc(sizeof(rcEdge)*maxEdgeCount, RC_ALLOC_TEMP);
  43. if (!edges)
  44. {
  45. rcFree(firstEdge);
  46. return false;
  47. }
  48. for (int i = 0; i < nverts; i++)
  49. firstEdge[i] = RC_MESH_NULL_IDX;
  50. for (int i = 0; i < npolys; ++i)
  51. {
  52. unsigned short* t = &polys[i*vertsPerPoly*2];
  53. for (int j = 0; j < vertsPerPoly; ++j)
  54. {
  55. if (t[j] == RC_MESH_NULL_IDX) break;
  56. unsigned short v0 = t[j];
  57. unsigned short v1 = (j+1 >= vertsPerPoly || t[j+1] == RC_MESH_NULL_IDX) ? t[0] : t[j+1];
  58. if (v0 < v1)
  59. {
  60. rcEdge& edge = edges[edgeCount];
  61. edge.vert[0] = v0;
  62. edge.vert[1] = v1;
  63. edge.poly[0] = (unsigned short)i;
  64. edge.polyEdge[0] = (unsigned short)j;
  65. edge.poly[1] = (unsigned short)i;
  66. edge.polyEdge[1] = 0;
  67. // Insert edge
  68. nextEdge[edgeCount] = firstEdge[v0];
  69. firstEdge[v0] = (unsigned short)edgeCount;
  70. edgeCount++;
  71. }
  72. }
  73. }
  74. for (int i = 0; i < npolys; ++i)
  75. {
  76. unsigned short* t = &polys[i*vertsPerPoly*2];
  77. for (int j = 0; j < vertsPerPoly; ++j)
  78. {
  79. if (t[j] == RC_MESH_NULL_IDX) break;
  80. unsigned short v0 = t[j];
  81. unsigned short v1 = (j+1 >= vertsPerPoly || t[j+1] == RC_MESH_NULL_IDX) ? t[0] : t[j+1];
  82. if (v0 > v1)
  83. {
  84. for (unsigned short e = firstEdge[v1]; e != RC_MESH_NULL_IDX; e = nextEdge[e])
  85. {
  86. rcEdge& edge = edges[e];
  87. if (edge.vert[1] == v0 && edge.poly[0] == edge.poly[1])
  88. {
  89. edge.poly[1] = (unsigned short)i;
  90. edge.polyEdge[1] = (unsigned short)j;
  91. break;
  92. }
  93. }
  94. }
  95. }
  96. }
  97. // Store adjacency
  98. for (int i = 0; i < edgeCount; ++i)
  99. {
  100. const rcEdge& e = edges[i];
  101. if (e.poly[0] != e.poly[1])
  102. {
  103. unsigned short* p0 = &polys[e.poly[0]*vertsPerPoly*2];
  104. unsigned short* p1 = &polys[e.poly[1]*vertsPerPoly*2];
  105. p0[vertsPerPoly + e.polyEdge[0]] = e.poly[1];
  106. p1[vertsPerPoly + e.polyEdge[1]] = e.poly[0];
  107. }
  108. }
  109. rcFree(firstEdge);
  110. rcFree(edges);
  111. return true;
  112. }
  113. static const int VERTEX_BUCKET_COUNT = (1<<12);
  114. inline int computeVertexHash(int x, int y, int z)
  115. {
  116. const unsigned int h1 = 0x8da6b343; // Large multiplicative constants;
  117. const unsigned int h2 = 0xd8163841; // here arbitrarily chosen primes
  118. const unsigned int h3 = 0xcb1ab31f;
  119. unsigned int n = h1 * x + h2 * y + h3 * z;
  120. return (int)(n & (VERTEX_BUCKET_COUNT-1));
  121. }
  122. static unsigned short addVertex(unsigned short x, unsigned short y, unsigned short z,
  123. unsigned short* verts, int* firstVert, int* nextVert, int& nv)
  124. {
  125. int bucket = computeVertexHash(x, 0, z);
  126. int i = firstVert[bucket];
  127. while (i != -1)
  128. {
  129. const unsigned short* v = &verts[i*3];
  130. if (v[0] == x && (rcAbs(v[1] - y) <= 2) && v[2] == z)
  131. return (unsigned short)i;
  132. i = nextVert[i]; // next
  133. }
  134. // Could not find, create new.
  135. i = nv; nv++;
  136. unsigned short* v = &verts[i*3];
  137. v[0] = x;
  138. v[1] = y;
  139. v[2] = z;
  140. nextVert[i] = firstVert[bucket];
  141. firstVert[bucket] = i;
  142. return (unsigned short)i;
  143. }
  144. // Last time I checked the if version got compiled using cmov, which was a lot faster than module (with idiv).
  145. inline int prev(int i, int n) { return i-1 >= 0 ? i-1 : n-1; }
  146. inline int next(int i, int n) { return i+1 < n ? i+1 : 0; }
  147. inline int area2(const int* a, const int* b, const int* c)
  148. {
  149. return (b[0] - a[0]) * (c[2] - a[2]) - (c[0] - a[0]) * (b[2] - a[2]);
  150. }
  151. // Exclusive or: true iff exactly one argument is true.
  152. // The arguments are negated to ensure that they are 0/1
  153. // values. Then the bitwise Xor operator may apply.
  154. // (This idea is due to Michael Baldwin.)
  155. inline bool xorb(bool x, bool y)
  156. {
  157. return !x ^ !y;
  158. }
  159. // Returns true iff c is strictly to the left of the directed
  160. // line through a to b.
  161. inline bool left(const int* a, const int* b, const int* c)
  162. {
  163. return area2(a, b, c) < 0;
  164. }
  165. inline bool leftOn(const int* a, const int* b, const int* c)
  166. {
  167. return area2(a, b, c) <= 0;
  168. }
  169. inline bool collinear(const int* a, const int* b, const int* c)
  170. {
  171. return area2(a, b, c) == 0;
  172. }
  173. // Returns true iff ab properly intersects cd: they share
  174. // a point interior to both segments. The properness of the
  175. // intersection is ensured by using strict leftness.
  176. static bool intersectProp(const int* a, const int* b, const int* c, const int* d)
  177. {
  178. // Eliminate improper cases.
  179. if (collinear(a,b,c) || collinear(a,b,d) ||
  180. collinear(c,d,a) || collinear(c,d,b))
  181. return false;
  182. return xorb(left(a,b,c), left(a,b,d)) && xorb(left(c,d,a), left(c,d,b));
  183. }
  184. // Returns T iff (a,b,c) are collinear and point c lies
  185. // on the closed segement ab.
  186. static bool between(const int* a, const int* b, const int* c)
  187. {
  188. if (!collinear(a, b, c))
  189. return false;
  190. // If ab not vertical, check betweenness on x; else on y.
  191. if (a[0] != b[0])
  192. return ((a[0] <= c[0]) && (c[0] <= b[0])) || ((a[0] >= c[0]) && (c[0] >= b[0]));
  193. else
  194. return ((a[2] <= c[2]) && (c[2] <= b[2])) || ((a[2] >= c[2]) && (c[2] >= b[2]));
  195. }
  196. // Returns true iff segments ab and cd intersect, properly or improperly.
  197. static bool intersect(const int* a, const int* b, const int* c, const int* d)
  198. {
  199. if (intersectProp(a, b, c, d))
  200. return true;
  201. else if (between(a, b, c) || between(a, b, d) ||
  202. between(c, d, a) || between(c, d, b))
  203. return true;
  204. else
  205. return false;
  206. }
  207. static bool vequal(const int* a, const int* b)
  208. {
  209. return a[0] == b[0] && a[2] == b[2];
  210. }
  211. // Returns T iff (v_i, v_j) is a proper internal *or* external
  212. // diagonal of P, *ignoring edges incident to v_i and v_j*.
  213. static bool diagonalie(int i, int j, int n, const int* verts, int* indices)
  214. {
  215. const int* d0 = &verts[(indices[i] & 0x0fffffff) * 4];
  216. const int* d1 = &verts[(indices[j] & 0x0fffffff) * 4];
  217. // For each edge (k,k+1) of P
  218. for (int k = 0; k < n; k++)
  219. {
  220. int k1 = next(k, n);
  221. // Skip edges incident to i or j
  222. if (!((k == i) || (k1 == i) || (k == j) || (k1 == j)))
  223. {
  224. const int* p0 = &verts[(indices[k] & 0x0fffffff) * 4];
  225. const int* p1 = &verts[(indices[k1] & 0x0fffffff) * 4];
  226. if (vequal(d0, p0) || vequal(d1, p0) || vequal(d0, p1) || vequal(d1, p1))
  227. continue;
  228. if (intersect(d0, d1, p0, p1))
  229. return false;
  230. }
  231. }
  232. return true;
  233. }
  234. // Returns true iff the diagonal (i,j) is strictly internal to the
  235. // polygon P in the neighborhood of the i endpoint.
  236. static bool inCone(int i, int j, int n, const int* verts, int* indices)
  237. {
  238. const int* pi = &verts[(indices[i] & 0x0fffffff) * 4];
  239. const int* pj = &verts[(indices[j] & 0x0fffffff) * 4];
  240. const int* pi1 = &verts[(indices[next(i, n)] & 0x0fffffff) * 4];
  241. const int* pin1 = &verts[(indices[prev(i, n)] & 0x0fffffff) * 4];
  242. // If P[i] is a convex vertex [ i+1 left or on (i-1,i) ].
  243. if (leftOn(pin1, pi, pi1))
  244. return left(pi, pj, pin1) && left(pj, pi, pi1);
  245. // Assume (i-1,i,i+1) not collinear.
  246. // else P[i] is reflex.
  247. return !(leftOn(pi, pj, pi1) && leftOn(pj, pi, pin1));
  248. }
  249. // Returns T iff (v_i, v_j) is a proper internal
  250. // diagonal of P.
  251. static bool diagonal(int i, int j, int n, const int* verts, int* indices)
  252. {
  253. return inCone(i, j, n, verts, indices) && diagonalie(i, j, n, verts, indices);
  254. }
  255. static bool diagonalieLoose(int i, int j, int n, const int* verts, int* indices)
  256. {
  257. const int* d0 = &verts[(indices[i] & 0x0fffffff) * 4];
  258. const int* d1 = &verts[(indices[j] & 0x0fffffff) * 4];
  259. // For each edge (k,k+1) of P
  260. for (int k = 0; k < n; k++)
  261. {
  262. int k1 = next(k, n);
  263. // Skip edges incident to i or j
  264. if (!((k == i) || (k1 == i) || (k == j) || (k1 == j)))
  265. {
  266. const int* p0 = &verts[(indices[k] & 0x0fffffff) * 4];
  267. const int* p1 = &verts[(indices[k1] & 0x0fffffff) * 4];
  268. if (vequal(d0, p0) || vequal(d1, p0) || vequal(d0, p1) || vequal(d1, p1))
  269. continue;
  270. if (intersectProp(d0, d1, p0, p1))
  271. return false;
  272. }
  273. }
  274. return true;
  275. }
  276. static bool inConeLoose(int i, int j, int n, const int* verts, int* indices)
  277. {
  278. const int* pi = &verts[(indices[i] & 0x0fffffff) * 4];
  279. const int* pj = &verts[(indices[j] & 0x0fffffff) * 4];
  280. const int* pi1 = &verts[(indices[next(i, n)] & 0x0fffffff) * 4];
  281. const int* pin1 = &verts[(indices[prev(i, n)] & 0x0fffffff) * 4];
  282. // If P[i] is a convex vertex [ i+1 left or on (i-1,i) ].
  283. if (leftOn(pin1, pi, pi1))
  284. return leftOn(pi, pj, pin1) && leftOn(pj, pi, pi1);
  285. // Assume (i-1,i,i+1) not collinear.
  286. // else P[i] is reflex.
  287. return !(leftOn(pi, pj, pi1) && leftOn(pj, pi, pin1));
  288. }
  289. static bool diagonalLoose(int i, int j, int n, const int* verts, int* indices)
  290. {
  291. return inConeLoose(i, j, n, verts, indices) && diagonalieLoose(i, j, n, verts, indices);
  292. }
  293. static int triangulate(int n, const int* verts, int* indices, int* tris)
  294. {
  295. int ntris = 0;
  296. int* dst = tris;
  297. // The last bit of the index is used to indicate if the vertex can be removed.
  298. for (int i = 0; i < n; i++)
  299. {
  300. int i1 = next(i, n);
  301. int i2 = next(i1, n);
  302. if (diagonal(i, i2, n, verts, indices))
  303. indices[i1] |= 0x80000000;
  304. }
  305. while (n > 3)
  306. {
  307. int minLen = -1;
  308. int mini = -1;
  309. for (int i = 0; i < n; i++)
  310. {
  311. int i1 = next(i, n);
  312. if (indices[i1] & 0x80000000)
  313. {
  314. const int* p0 = &verts[(indices[i] & 0x0fffffff) * 4];
  315. const int* p2 = &verts[(indices[next(i1, n)] & 0x0fffffff) * 4];
  316. int dx = p2[0] - p0[0];
  317. int dy = p2[2] - p0[2];
  318. int len = dx*dx + dy*dy;
  319. if (minLen < 0 || len < minLen)
  320. {
  321. minLen = len;
  322. mini = i;
  323. }
  324. }
  325. }
  326. if (mini == -1)
  327. {
  328. // We might get here because the contour has overlapping segments, like this:
  329. //
  330. // A o-o=====o---o B
  331. // / |C D| \.
  332. // o o o o
  333. // : : : :
  334. // We'll try to recover by loosing up the inCone test a bit so that a diagonal
  335. // like A-B or C-D can be found and we can continue.
  336. minLen = -1;
  337. mini = -1;
  338. for (int i = 0; i < n; i++)
  339. {
  340. int i1 = next(i, n);
  341. int i2 = next(i1, n);
  342. if (diagonalLoose(i, i2, n, verts, indices))
  343. {
  344. const int* p0 = &verts[(indices[i] & 0x0fffffff) * 4];
  345. const int* p2 = &verts[(indices[next(i2, n)] & 0x0fffffff) * 4];
  346. int dx = p2[0] - p0[0];
  347. int dy = p2[2] - p0[2];
  348. int len = dx*dx + dy*dy;
  349. if (minLen < 0 || len < minLen)
  350. {
  351. minLen = len;
  352. mini = i;
  353. }
  354. }
  355. }
  356. if (mini == -1)
  357. {
  358. // The contour is messed up. This sometimes happens
  359. // if the contour simplification is too aggressive.
  360. return -ntris;
  361. }
  362. }
  363. int i = mini;
  364. int i1 = next(i, n);
  365. int i2 = next(i1, n);
  366. *dst++ = indices[i] & 0x0fffffff;
  367. *dst++ = indices[i1] & 0x0fffffff;
  368. *dst++ = indices[i2] & 0x0fffffff;
  369. ntris++;
  370. // Removes P[i1] by copying P[i+1]...P[n-1] left one index.
  371. n--;
  372. for (int k = i1; k < n; k++)
  373. indices[k] = indices[k+1];
  374. if (i1 >= n) i1 = 0;
  375. i = prev(i1,n);
  376. // Update diagonal flags.
  377. if (diagonal(prev(i, n), i1, n, verts, indices))
  378. indices[i] |= 0x80000000;
  379. else
  380. indices[i] &= 0x0fffffff;
  381. if (diagonal(i, next(i1, n), n, verts, indices))
  382. indices[i1] |= 0x80000000;
  383. else
  384. indices[i1] &= 0x0fffffff;
  385. }
  386. // Append the remaining triangle.
  387. *dst++ = indices[0] & 0x0fffffff;
  388. *dst++ = indices[1] & 0x0fffffff;
  389. *dst++ = indices[2] & 0x0fffffff;
  390. ntris++;
  391. return ntris;
  392. }
  393. static int countPolyVerts(const unsigned short* p, const int nvp)
  394. {
  395. for (int i = 0; i < nvp; ++i)
  396. if (p[i] == RC_MESH_NULL_IDX)
  397. return i;
  398. return nvp;
  399. }
  400. inline bool uleft(const unsigned short* a, const unsigned short* b, const unsigned short* c)
  401. {
  402. return ((int)b[0] - (int)a[0]) * ((int)c[2] - (int)a[2]) -
  403. ((int)c[0] - (int)a[0]) * ((int)b[2] - (int)a[2]) < 0;
  404. }
  405. static int getPolyMergeValue(unsigned short* pa, unsigned short* pb,
  406. const unsigned short* verts, int& ea, int& eb,
  407. const int nvp)
  408. {
  409. const int na = countPolyVerts(pa, nvp);
  410. const int nb = countPolyVerts(pb, nvp);
  411. // If the merged polygon would be too big, do not merge.
  412. if (na+nb-2 > nvp)
  413. return -1;
  414. // Check if the polygons share an edge.
  415. ea = -1;
  416. eb = -1;
  417. for (int i = 0; i < na; ++i)
  418. {
  419. unsigned short va0 = pa[i];
  420. unsigned short va1 = pa[(i+1) % na];
  421. if (va0 > va1)
  422. rcSwap(va0, va1);
  423. for (int j = 0; j < nb; ++j)
  424. {
  425. unsigned short vb0 = pb[j];
  426. unsigned short vb1 = pb[(j+1) % nb];
  427. if (vb0 > vb1)
  428. rcSwap(vb0, vb1);
  429. if (va0 == vb0 && va1 == vb1)
  430. {
  431. ea = i;
  432. eb = j;
  433. break;
  434. }
  435. }
  436. }
  437. // No common edge, cannot merge.
  438. if (ea == -1 || eb == -1)
  439. return -1;
  440. // Check to see if the merged polygon would be convex.
  441. unsigned short va, vb, vc;
  442. va = pa[(ea+na-1) % na];
  443. vb = pa[ea];
  444. vc = pb[(eb+2) % nb];
  445. if (!uleft(&verts[va*3], &verts[vb*3], &verts[vc*3]))
  446. return -1;
  447. va = pb[(eb+nb-1) % nb];
  448. vb = pb[eb];
  449. vc = pa[(ea+2) % na];
  450. if (!uleft(&verts[va*3], &verts[vb*3], &verts[vc*3]))
  451. return -1;
  452. va = pa[ea];
  453. vb = pa[(ea+1)%na];
  454. int dx = (int)verts[va*3+0] - (int)verts[vb*3+0];
  455. int dy = (int)verts[va*3+2] - (int)verts[vb*3+2];
  456. return dx*dx + dy*dy;
  457. }
  458. static void mergePolyVerts(unsigned short* pa, unsigned short* pb, int ea, int eb,
  459. unsigned short* tmp, const int nvp)
  460. {
  461. const int na = countPolyVerts(pa, nvp);
  462. const int nb = countPolyVerts(pb, nvp);
  463. // Merge polygons.
  464. memset(tmp, 0xff, sizeof(unsigned short)*nvp);
  465. int n = 0;
  466. // Add pa
  467. for (int i = 0; i < na-1; ++i)
  468. tmp[n++] = pa[(ea+1+i) % na];
  469. // Add pb
  470. for (int i = 0; i < nb-1; ++i)
  471. tmp[n++] = pb[(eb+1+i) % nb];
  472. memcpy(pa, tmp, sizeof(unsigned short)*nvp);
  473. }
  474. static void pushFront(int v, int* arr, int& an)
  475. {
  476. an++;
  477. for (int i = an-1; i > 0; --i) arr[i] = arr[i-1];
  478. arr[0] = v;
  479. }
  480. static void pushBack(int v, int* arr, int& an)
  481. {
  482. arr[an] = v;
  483. an++;
  484. }
  485. static bool canRemoveVertex(rcContext* ctx, rcPolyMesh& mesh, const unsigned short rem)
  486. {
  487. const int nvp = mesh.nvp;
  488. // Count number of polygons to remove.
  489. int numRemovedVerts = 0;
  490. int numTouchedVerts = 0;
  491. int numRemainingEdges = 0;
  492. for (int i = 0; i < mesh.npolys; ++i)
  493. {
  494. unsigned short* p = &mesh.polys[i*nvp*2];
  495. const int nv = countPolyVerts(p, nvp);
  496. int numRemoved = 0;
  497. int numVerts = 0;
  498. for (int j = 0; j < nv; ++j)
  499. {
  500. if (p[j] == rem)
  501. {
  502. numTouchedVerts++;
  503. numRemoved++;
  504. }
  505. numVerts++;
  506. }
  507. if (numRemoved)
  508. {
  509. numRemovedVerts += numRemoved;
  510. numRemainingEdges += numVerts-(numRemoved+1);
  511. }
  512. }
  513. // There would be too few edges remaining to create a polygon.
  514. // This can happen for example when a tip of a triangle is marked
  515. // as deletion, but there are no other polys that share the vertex.
  516. // In this case, the vertex should not be removed.
  517. if (numRemainingEdges <= 2)
  518. return false;
  519. // Find edges which share the removed vertex.
  520. const int maxEdges = numTouchedVerts*2;
  521. int nedges = 0;
  522. rcScopedDelete<int> edges((int*)rcAlloc(sizeof(int)*maxEdges*3, RC_ALLOC_TEMP));
  523. if (!edges)
  524. {
  525. ctx->log(RC_LOG_WARNING, "canRemoveVertex: Out of memory 'edges' (%d).", maxEdges*3);
  526. return false;
  527. }
  528. for (int i = 0; i < mesh.npolys; ++i)
  529. {
  530. unsigned short* p = &mesh.polys[i*nvp*2];
  531. const int nv = countPolyVerts(p, nvp);
  532. // Collect edges which touches the removed vertex.
  533. for (int j = 0, k = nv-1; j < nv; k = j++)
  534. {
  535. if (p[j] == rem || p[k] == rem)
  536. {
  537. // Arrange edge so that a=rem.
  538. int a = p[j], b = p[k];
  539. if (b == rem)
  540. rcSwap(a,b);
  541. // Check if the edge exists
  542. bool exists = false;
  543. for (int m = 0; m < nedges; ++m)
  544. {
  545. int* e = &edges[m*3];
  546. if (e[1] == b)
  547. {
  548. // Exists, increment vertex share count.
  549. e[2]++;
  550. exists = true;
  551. }
  552. }
  553. // Add new edge.
  554. if (!exists)
  555. {
  556. int* e = &edges[nedges*3];
  557. e[0] = a;
  558. e[1] = b;
  559. e[2] = 1;
  560. nedges++;
  561. }
  562. }
  563. }
  564. }
  565. // There should be no more than 2 open edges.
  566. // This catches the case that two non-adjacent polygons
  567. // share the removed vertex. In that case, do not remove the vertex.
  568. int numOpenEdges = 0;
  569. for (int i = 0; i < nedges; ++i)
  570. {
  571. if (edges[i*3+2] < 2)
  572. numOpenEdges++;
  573. }
  574. if (numOpenEdges > 2)
  575. return false;
  576. return true;
  577. }
  578. static bool removeVertex(rcContext* ctx, rcPolyMesh& mesh, const unsigned short rem, const int maxTris)
  579. {
  580. const int nvp = mesh.nvp;
  581. // Count number of polygons to remove.
  582. int numRemovedVerts = 0;
  583. for (int i = 0; i < mesh.npolys; ++i)
  584. {
  585. unsigned short* p = &mesh.polys[i*nvp*2];
  586. const int nv = countPolyVerts(p, nvp);
  587. for (int j = 0; j < nv; ++j)
  588. {
  589. if (p[j] == rem)
  590. numRemovedVerts++;
  591. }
  592. }
  593. int nedges = 0;
  594. rcScopedDelete<int> edges((int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp*4, RC_ALLOC_TEMP));
  595. if (!edges)
  596. {
  597. ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'edges' (%d).", numRemovedVerts*nvp*4);
  598. return false;
  599. }
  600. int nhole = 0;
  601. rcScopedDelete<int> hole((int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp, RC_ALLOC_TEMP));
  602. if (!hole)
  603. {
  604. ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'hole' (%d).", numRemovedVerts*nvp);
  605. return false;
  606. }
  607. int nhreg = 0;
  608. rcScopedDelete<int> hreg((int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp, RC_ALLOC_TEMP));
  609. if (!hreg)
  610. {
  611. ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'hreg' (%d).", numRemovedVerts*nvp);
  612. return false;
  613. }
  614. int nharea = 0;
  615. rcScopedDelete<int> harea((int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp, RC_ALLOC_TEMP));
  616. if (!harea)
  617. {
  618. ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'harea' (%d).", numRemovedVerts*nvp);
  619. return false;
  620. }
  621. for (int i = 0; i < mesh.npolys; ++i)
  622. {
  623. unsigned short* p = &mesh.polys[i*nvp*2];
  624. const int nv = countPolyVerts(p, nvp);
  625. bool hasRem = false;
  626. for (int j = 0; j < nv; ++j)
  627. if (p[j] == rem) hasRem = true;
  628. if (hasRem)
  629. {
  630. // Collect edges which does not touch the removed vertex.
  631. for (int j = 0, k = nv-1; j < nv; k = j++)
  632. {
  633. if (p[j] != rem && p[k] != rem)
  634. {
  635. int* e = &edges[nedges*4];
  636. e[0] = p[k];
  637. e[1] = p[j];
  638. e[2] = mesh.regs[i];
  639. e[3] = mesh.areas[i];
  640. nedges++;
  641. }
  642. }
  643. // Remove the polygon.
  644. unsigned short* p2 = &mesh.polys[(mesh.npolys-1)*nvp*2];
  645. if (p != p2)
  646. memcpy(p,p2,sizeof(unsigned short)*nvp);
  647. memset(p+nvp,0xff,sizeof(unsigned short)*nvp);
  648. mesh.regs[i] = mesh.regs[mesh.npolys-1];
  649. mesh.areas[i] = mesh.areas[mesh.npolys-1];
  650. mesh.npolys--;
  651. --i;
  652. }
  653. }
  654. // Remove vertex.
  655. for (int i = (int)rem; i < mesh.nverts - 1; ++i)
  656. {
  657. mesh.verts[i*3+0] = mesh.verts[(i+1)*3+0];
  658. mesh.verts[i*3+1] = mesh.verts[(i+1)*3+1];
  659. mesh.verts[i*3+2] = mesh.verts[(i+1)*3+2];
  660. }
  661. mesh.nverts--;
  662. // Adjust indices to match the removed vertex layout.
  663. for (int i = 0; i < mesh.npolys; ++i)
  664. {
  665. unsigned short* p = &mesh.polys[i*nvp*2];
  666. const int nv = countPolyVerts(p, nvp);
  667. for (int j = 0; j < nv; ++j)
  668. if (p[j] > rem) p[j]--;
  669. }
  670. for (int i = 0; i < nedges; ++i)
  671. {
  672. if (edges[i*4+0] > rem) edges[i*4+0]--;
  673. if (edges[i*4+1] > rem) edges[i*4+1]--;
  674. }
  675. if (nedges == 0)
  676. return true;
  677. // Start with one vertex, keep appending connected
  678. // segments to the start and end of the hole.
  679. pushBack(edges[0], hole, nhole);
  680. pushBack(edges[2], hreg, nhreg);
  681. pushBack(edges[3], harea, nharea);
  682. while (nedges)
  683. {
  684. bool match = false;
  685. for (int i = 0; i < nedges; ++i)
  686. {
  687. const int ea = edges[i*4+0];
  688. const int eb = edges[i*4+1];
  689. const int r = edges[i*4+2];
  690. const int a = edges[i*4+3];
  691. bool add = false;
  692. if (hole[0] == eb)
  693. {
  694. // The segment matches the beginning of the hole boundary.
  695. pushFront(ea, hole, nhole);
  696. pushFront(r, hreg, nhreg);
  697. pushFront(a, harea, nharea);
  698. add = true;
  699. }
  700. else if (hole[nhole-1] == ea)
  701. {
  702. // The segment matches the end of the hole boundary.
  703. pushBack(eb, hole, nhole);
  704. pushBack(r, hreg, nhreg);
  705. pushBack(a, harea, nharea);
  706. add = true;
  707. }
  708. if (add)
  709. {
  710. // The edge segment was added, remove it.
  711. edges[i*4+0] = edges[(nedges-1)*4+0];
  712. edges[i*4+1] = edges[(nedges-1)*4+1];
  713. edges[i*4+2] = edges[(nedges-1)*4+2];
  714. edges[i*4+3] = edges[(nedges-1)*4+3];
  715. --nedges;
  716. match = true;
  717. --i;
  718. }
  719. }
  720. if (!match)
  721. break;
  722. }
  723. rcScopedDelete<int> tris((int*)rcAlloc(sizeof(int)*nhole*3, RC_ALLOC_TEMP));
  724. if (!tris)
  725. {
  726. ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'tris' (%d).", nhole*3);
  727. return false;
  728. }
  729. rcScopedDelete<int> tverts((int*)rcAlloc(sizeof(int)*nhole*4, RC_ALLOC_TEMP));
  730. if (!tverts)
  731. {
  732. ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'tverts' (%d).", nhole*4);
  733. return false;
  734. }
  735. rcScopedDelete<int> thole((int*)rcAlloc(sizeof(int)*nhole, RC_ALLOC_TEMP));
  736. if (!thole)
  737. {
  738. ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'thole' (%d).", nhole);
  739. return false;
  740. }
  741. // Generate temp vertex array for triangulation.
  742. for (int i = 0; i < nhole; ++i)
  743. {
  744. const int pi = hole[i];
  745. tverts[i*4+0] = mesh.verts[pi*3+0];
  746. tverts[i*4+1] = mesh.verts[pi*3+1];
  747. tverts[i*4+2] = mesh.verts[pi*3+2];
  748. tverts[i*4+3] = 0;
  749. thole[i] = i;
  750. }
  751. // Triangulate the hole.
  752. int ntris = triangulate(nhole, &tverts[0], &thole[0], tris);
  753. if (ntris < 0)
  754. {
  755. ntris = -ntris;
  756. ctx->log(RC_LOG_WARNING, "removeVertex: triangulate() returned bad results.");
  757. }
  758. // Merge the hole triangles back to polygons.
  759. rcScopedDelete<unsigned short> polys((unsigned short*)rcAlloc(sizeof(unsigned short)*(ntris+1)*nvp, RC_ALLOC_TEMP));
  760. if (!polys)
  761. {
  762. ctx->log(RC_LOG_ERROR, "removeVertex: Out of memory 'polys' (%d).", (ntris+1)*nvp);
  763. return false;
  764. }
  765. rcScopedDelete<unsigned short> pregs((unsigned short*)rcAlloc(sizeof(unsigned short)*ntris, RC_ALLOC_TEMP));
  766. if (!pregs)
  767. {
  768. ctx->log(RC_LOG_ERROR, "removeVertex: Out of memory 'pregs' (%d).", ntris);
  769. return false;
  770. }
  771. rcScopedDelete<unsigned char> pareas((unsigned char*)rcAlloc(sizeof(unsigned char)*ntris, RC_ALLOC_TEMP));
  772. if (!pareas)
  773. {
  774. ctx->log(RC_LOG_ERROR, "removeVertex: Out of memory 'pareas' (%d).", ntris);
  775. return false;
  776. }
  777. unsigned short* tmpPoly = &polys[ntris*nvp];
  778. // Build initial polygons.
  779. int npolys = 0;
  780. memset(polys, 0xff, ntris*nvp*sizeof(unsigned short));
  781. for (int j = 0; j < ntris; ++j)
  782. {
  783. int* t = &tris[j*3];
  784. if (t[0] != t[1] && t[0] != t[2] && t[1] != t[2])
  785. {
  786. polys[npolys*nvp+0] = (unsigned short)hole[t[0]];
  787. polys[npolys*nvp+1] = (unsigned short)hole[t[1]];
  788. polys[npolys*nvp+2] = (unsigned short)hole[t[2]];
  789. // If this polygon covers multiple region types then
  790. // mark it as such
  791. if (hreg[t[0]] != hreg[t[1]] || hreg[t[1]] != hreg[t[2]])
  792. pregs[npolys] = RC_MULTIPLE_REGS;
  793. else
  794. pregs[npolys] = (unsigned short)hreg[t[0]];
  795. pareas[npolys] = (unsigned char)harea[t[0]];
  796. npolys++;
  797. }
  798. }
  799. if (!npolys)
  800. return true;
  801. // Merge polygons.
  802. if (nvp > 3)
  803. {
  804. for (;;)
  805. {
  806. // Find best polygons to merge.
  807. int bestMergeVal = 0;
  808. int bestPa = 0, bestPb = 0, bestEa = 0, bestEb = 0;
  809. for (int j = 0; j < npolys-1; ++j)
  810. {
  811. unsigned short* pj = &polys[j*nvp];
  812. for (int k = j+1; k < npolys; ++k)
  813. {
  814. unsigned short* pk = &polys[k*nvp];
  815. int ea, eb;
  816. int v = getPolyMergeValue(pj, pk, mesh.verts, ea, eb, nvp);
  817. if (v > bestMergeVal)
  818. {
  819. bestMergeVal = v;
  820. bestPa = j;
  821. bestPb = k;
  822. bestEa = ea;
  823. bestEb = eb;
  824. }
  825. }
  826. }
  827. if (bestMergeVal > 0)
  828. {
  829. // Found best, merge.
  830. unsigned short* pa = &polys[bestPa*nvp];
  831. unsigned short* pb = &polys[bestPb*nvp];
  832. mergePolyVerts(pa, pb, bestEa, bestEb, tmpPoly, nvp);
  833. if (pregs[bestPa] != pregs[bestPb])
  834. pregs[bestPa] = RC_MULTIPLE_REGS;
  835. unsigned short* last = &polys[(npolys-1)*nvp];
  836. if (pb != last)
  837. memcpy(pb, last, sizeof(unsigned short)*nvp);
  838. pregs[bestPb] = pregs[npolys-1];
  839. pareas[bestPb] = pareas[npolys-1];
  840. npolys--;
  841. }
  842. else
  843. {
  844. // Could not merge any polygons, stop.
  845. break;
  846. }
  847. }
  848. }
  849. // Store polygons.
  850. for (int i = 0; i < npolys; ++i)
  851. {
  852. if (mesh.npolys >= maxTris) break;
  853. unsigned short* p = &mesh.polys[mesh.npolys*nvp*2];
  854. memset(p,0xff,sizeof(unsigned short)*nvp*2);
  855. for (int j = 0; j < nvp; ++j)
  856. p[j] = polys[i*nvp+j];
  857. mesh.regs[mesh.npolys] = pregs[i];
  858. mesh.areas[mesh.npolys] = pareas[i];
  859. mesh.npolys++;
  860. if (mesh.npolys > maxTris)
  861. {
  862. ctx->log(RC_LOG_ERROR, "removeVertex: Too many polygons %d (max:%d).", mesh.npolys, maxTris);
  863. return false;
  864. }
  865. }
  866. return true;
  867. }
  868. /// @par
  869. ///
  870. /// @note If the mesh data is to be used to construct a Detour navigation mesh, then the upper
  871. /// limit must be retricted to <= #DT_VERTS_PER_POLYGON.
  872. ///
  873. /// @see rcAllocPolyMesh, rcContourSet, rcPolyMesh, rcConfig
  874. bool rcBuildPolyMesh(rcContext* ctx, rcContourSet& cset, const int nvp, rcPolyMesh& mesh)
  875. {
  876. rcAssert(ctx);
  877. rcScopedTimer timer(ctx, RC_TIMER_BUILD_POLYMESH);
  878. rcVcopy(mesh.bmin, cset.bmin);
  879. rcVcopy(mesh.bmax, cset.bmax);
  880. mesh.cs = cset.cs;
  881. mesh.ch = cset.ch;
  882. mesh.borderSize = cset.borderSize;
  883. mesh.maxEdgeError = cset.maxError;
  884. int maxVertices = 0;
  885. int maxTris = 0;
  886. int maxVertsPerCont = 0;
  887. for (int i = 0; i < cset.nconts; ++i)
  888. {
  889. // Skip null contours.
  890. if (cset.conts[i].nverts < 3) continue;
  891. maxVertices += cset.conts[i].nverts;
  892. maxTris += cset.conts[i].nverts - 2;
  893. maxVertsPerCont = rcMax(maxVertsPerCont, cset.conts[i].nverts);
  894. }
  895. if (maxVertices >= 0xfffe)
  896. {
  897. ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Too many vertices %d.", maxVertices);
  898. return false;
  899. }
  900. rcScopedDelete<unsigned char> vflags((unsigned char*)rcAlloc(sizeof(unsigned char)*maxVertices, RC_ALLOC_TEMP));
  901. if (!vflags)
  902. {
  903. ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'vflags' (%d).", maxVertices);
  904. return false;
  905. }
  906. memset(vflags, 0, maxVertices);
  907. mesh.verts = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxVertices*3, RC_ALLOC_PERM);
  908. if (!mesh.verts)
  909. {
  910. ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.verts' (%d).", maxVertices);
  911. return false;
  912. }
  913. mesh.polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxTris*nvp*2, RC_ALLOC_PERM);
  914. if (!mesh.polys)
  915. {
  916. ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.polys' (%d).", maxTris*nvp*2);
  917. return false;
  918. }
  919. mesh.regs = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxTris, RC_ALLOC_PERM);
  920. if (!mesh.regs)
  921. {
  922. ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.regs' (%d).", maxTris);
  923. return false;
  924. }
  925. mesh.areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*maxTris, RC_ALLOC_PERM);
  926. if (!mesh.areas)
  927. {
  928. ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.areas' (%d).", maxTris);
  929. return false;
  930. }
  931. mesh.nverts = 0;
  932. mesh.npolys = 0;
  933. mesh.nvp = nvp;
  934. mesh.maxpolys = maxTris;
  935. memset(mesh.verts, 0, sizeof(unsigned short)*maxVertices*3);
  936. memset(mesh.polys, 0xff, sizeof(unsigned short)*maxTris*nvp*2);
  937. memset(mesh.regs, 0, sizeof(unsigned short)*maxTris);
  938. memset(mesh.areas, 0, sizeof(unsigned char)*maxTris);
  939. rcScopedDelete<int> nextVert((int*)rcAlloc(sizeof(int)*maxVertices, RC_ALLOC_TEMP));
  940. if (!nextVert)
  941. {
  942. ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'nextVert' (%d).", maxVertices);
  943. return false;
  944. }
  945. memset(nextVert, 0, sizeof(int)*maxVertices);
  946. rcScopedDelete<int> firstVert((int*)rcAlloc(sizeof(int)*VERTEX_BUCKET_COUNT, RC_ALLOC_TEMP));
  947. if (!firstVert)
  948. {
  949. ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'firstVert' (%d).", VERTEX_BUCKET_COUNT);
  950. return false;
  951. }
  952. for (int i = 0; i < VERTEX_BUCKET_COUNT; ++i)
  953. firstVert[i] = -1;
  954. rcScopedDelete<int> indices((int*)rcAlloc(sizeof(int)*maxVertsPerCont, RC_ALLOC_TEMP));
  955. if (!indices)
  956. {
  957. ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'indices' (%d).", maxVertsPerCont);
  958. return false;
  959. }
  960. rcScopedDelete<int> tris((int*)rcAlloc(sizeof(int)*maxVertsPerCont*3, RC_ALLOC_TEMP));
  961. if (!tris)
  962. {
  963. ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'tris' (%d).", maxVertsPerCont*3);
  964. return false;
  965. }
  966. rcScopedDelete<unsigned short> polys((unsigned short*)rcAlloc(sizeof(unsigned short)*(maxVertsPerCont+1)*nvp, RC_ALLOC_TEMP));
  967. if (!polys)
  968. {
  969. ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'polys' (%d).", maxVertsPerCont*nvp);
  970. return false;
  971. }
  972. unsigned short* tmpPoly = &polys[maxVertsPerCont*nvp];
  973. for (int i = 0; i < cset.nconts; ++i)
  974. {
  975. rcContour& cont = cset.conts[i];
  976. // Skip null contours.
  977. if (cont.nverts < 3)
  978. continue;
  979. // Triangulate contour
  980. for (int j = 0; j < cont.nverts; ++j)
  981. indices[j] = j;
  982. int ntris = triangulate(cont.nverts, cont.verts, &indices[0], &tris[0]);
  983. if (ntris <= 0)
  984. {
  985. // Bad triangulation, should not happen.
  986. /* printf("\tconst float bmin[3] = {%ff,%ff,%ff};\n", cset.bmin[0], cset.bmin[1], cset.bmin[2]);
  987. printf("\tconst float cs = %ff;\n", cset.cs);
  988. printf("\tconst float ch = %ff;\n", cset.ch);
  989. printf("\tconst int verts[] = {\n");
  990. for (int k = 0; k < cont.nverts; ++k)
  991. {
  992. const int* v = &cont.verts[k*4];
  993. printf("\t\t%d,%d,%d,%d,\n", v[0], v[1], v[2], v[3]);
  994. }
  995. printf("\t};\n\tconst int nverts = sizeof(verts)/(sizeof(int)*4);\n");*/
  996. ctx->log(RC_LOG_WARNING, "rcBuildPolyMesh: Bad triangulation Contour %d.", i);
  997. ntris = -ntris;
  998. }
  999. // Add and merge vertices.
  1000. for (int j = 0; j < cont.nverts; ++j)
  1001. {
  1002. const int* v = &cont.verts[j*4];
  1003. indices[j] = addVertex((unsigned short)v[0], (unsigned short)v[1], (unsigned short)v[2],
  1004. mesh.verts, firstVert, nextVert, mesh.nverts);
  1005. if (v[3] & RC_BORDER_VERTEX)
  1006. {
  1007. // This vertex should be removed.
  1008. vflags[indices[j]] = 1;
  1009. }
  1010. }
  1011. // Build initial polygons.
  1012. int npolys = 0;
  1013. memset(polys, 0xff, maxVertsPerCont*nvp*sizeof(unsigned short));
  1014. for (int j = 0; j < ntris; ++j)
  1015. {
  1016. int* t = &tris[j*3];
  1017. if (t[0] != t[1] && t[0] != t[2] && t[1] != t[2])
  1018. {
  1019. polys[npolys*nvp+0] = (unsigned short)indices[t[0]];
  1020. polys[npolys*nvp+1] = (unsigned short)indices[t[1]];
  1021. polys[npolys*nvp+2] = (unsigned short)indices[t[2]];
  1022. npolys++;
  1023. }
  1024. }
  1025. if (!npolys)
  1026. continue;
  1027. // Merge polygons.
  1028. if (nvp > 3)
  1029. {
  1030. for(;;)
  1031. {
  1032. // Find best polygons to merge.
  1033. int bestMergeVal = 0;
  1034. int bestPa = 0, bestPb = 0, bestEa = 0, bestEb = 0;
  1035. for (int j = 0; j < npolys-1; ++j)
  1036. {
  1037. unsigned short* pj = &polys[j*nvp];
  1038. for (int k = j+1; k < npolys; ++k)
  1039. {
  1040. unsigned short* pk = &polys[k*nvp];
  1041. int ea, eb;
  1042. int v = getPolyMergeValue(pj, pk, mesh.verts, ea, eb, nvp);
  1043. if (v > bestMergeVal)
  1044. {
  1045. bestMergeVal = v;
  1046. bestPa = j;
  1047. bestPb = k;
  1048. bestEa = ea;
  1049. bestEb = eb;
  1050. }
  1051. }
  1052. }
  1053. if (bestMergeVal > 0)
  1054. {
  1055. // Found best, merge.
  1056. unsigned short* pa = &polys[bestPa*nvp];
  1057. unsigned short* pb = &polys[bestPb*nvp];
  1058. mergePolyVerts(pa, pb, bestEa, bestEb, tmpPoly, nvp);
  1059. unsigned short* lastPoly = &polys[(npolys-1)*nvp];
  1060. if (pb != lastPoly)
  1061. memcpy(pb, lastPoly, sizeof(unsigned short)*nvp);
  1062. npolys--;
  1063. }
  1064. else
  1065. {
  1066. // Could not merge any polygons, stop.
  1067. break;
  1068. }
  1069. }
  1070. }
  1071. // Store polygons.
  1072. for (int j = 0; j < npolys; ++j)
  1073. {
  1074. unsigned short* p = &mesh.polys[mesh.npolys*nvp*2];
  1075. unsigned short* q = &polys[j*nvp];
  1076. for (int k = 0; k < nvp; ++k)
  1077. p[k] = q[k];
  1078. mesh.regs[mesh.npolys] = cont.reg;
  1079. mesh.areas[mesh.npolys] = cont.area;
  1080. mesh.npolys++;
  1081. if (mesh.npolys > maxTris)
  1082. {
  1083. ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Too many polygons %d (max:%d).", mesh.npolys, maxTris);
  1084. return false;
  1085. }
  1086. }
  1087. }
  1088. // Remove edge vertices.
  1089. for (int i = 0; i < mesh.nverts; ++i)
  1090. {
  1091. if (vflags[i])
  1092. {
  1093. if (!canRemoveVertex(ctx, mesh, (unsigned short)i))
  1094. continue;
  1095. if (!removeVertex(ctx, mesh, (unsigned short)i, maxTris))
  1096. {
  1097. // Failed to remove vertex
  1098. ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Failed to remove edge vertex %d.", i);
  1099. return false;
  1100. }
  1101. // Remove vertex
  1102. // Note: mesh.nverts is already decremented inside removeVertex()!
  1103. // Fixup vertex flags
  1104. for (int j = i; j < mesh.nverts; ++j)
  1105. vflags[j] = vflags[j+1];
  1106. --i;
  1107. }
  1108. }
  1109. // Calculate adjacency.
  1110. if (!buildMeshAdjacency(mesh.polys, mesh.npolys, mesh.nverts, nvp))
  1111. {
  1112. ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Adjacency failed.");
  1113. return false;
  1114. }
  1115. // Find portal edges
  1116. if (mesh.borderSize > 0)
  1117. {
  1118. const int w = cset.width;
  1119. const int h = cset.height;
  1120. for (int i = 0; i < mesh.npolys; ++i)
  1121. {
  1122. unsigned short* p = &mesh.polys[i*2*nvp];
  1123. for (int j = 0; j < nvp; ++j)
  1124. {
  1125. if (p[j] == RC_MESH_NULL_IDX) break;
  1126. // Skip connected edges.
  1127. if (p[nvp+j] != RC_MESH_NULL_IDX)
  1128. continue;
  1129. int nj = j+1;
  1130. if (nj >= nvp || p[nj] == RC_MESH_NULL_IDX) nj = 0;
  1131. const unsigned short* va = &mesh.verts[p[j]*3];
  1132. const unsigned short* vb = &mesh.verts[p[nj]*3];
  1133. if ((int)va[0] == 0 && (int)vb[0] == 0)
  1134. p[nvp+j] = 0x8000 | 0;
  1135. else if ((int)va[2] == h && (int)vb[2] == h)
  1136. p[nvp+j] = 0x8000 | 1;
  1137. else if ((int)va[0] == w && (int)vb[0] == w)
  1138. p[nvp+j] = 0x8000 | 2;
  1139. else if ((int)va[2] == 0 && (int)vb[2] == 0)
  1140. p[nvp+j] = 0x8000 | 3;
  1141. }
  1142. }
  1143. }
  1144. // Just allocate the mesh flags array. The user is resposible to fill it.
  1145. mesh.flags = (unsigned short*)rcAlloc(sizeof(unsigned short)*mesh.npolys, RC_ALLOC_PERM);
  1146. if (!mesh.flags)
  1147. {
  1148. ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.flags' (%d).", mesh.npolys);
  1149. return false;
  1150. }
  1151. memset(mesh.flags, 0, sizeof(unsigned short) * mesh.npolys);
  1152. if (mesh.nverts > 0xffff)
  1153. {
  1154. ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: The resulting mesh has too many vertices %d (max %d). Data can be corrupted.", mesh.nverts, 0xffff);
  1155. }
  1156. if (mesh.npolys > 0xffff)
  1157. {
  1158. ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: The resulting mesh has too many polygons %d (max %d). Data can be corrupted.", mesh.npolys, 0xffff);
  1159. }
  1160. return true;
  1161. }
  1162. /// @see rcAllocPolyMesh, rcPolyMesh
  1163. bool rcMergePolyMeshes(rcContext* ctx, rcPolyMesh** meshes, const int nmeshes, rcPolyMesh& mesh)
  1164. {
  1165. rcAssert(ctx);
  1166. if (!nmeshes || !meshes)
  1167. return true;
  1168. rcScopedTimer timer(ctx, RC_TIMER_MERGE_POLYMESH);
  1169. mesh.nvp = meshes[0]->nvp;
  1170. mesh.cs = meshes[0]->cs;
  1171. mesh.ch = meshes[0]->ch;
  1172. rcVcopy(mesh.bmin, meshes[0]->bmin);
  1173. rcVcopy(mesh.bmax, meshes[0]->bmax);
  1174. int maxVerts = 0;
  1175. int maxPolys = 0;
  1176. int maxVertsPerMesh = 0;
  1177. for (int i = 0; i < nmeshes; ++i)
  1178. {
  1179. rcVmin(mesh.bmin, meshes[i]->bmin);
  1180. rcVmax(mesh.bmax, meshes[i]->bmax);
  1181. maxVertsPerMesh = rcMax(maxVertsPerMesh, meshes[i]->nverts);
  1182. maxVerts += meshes[i]->nverts;
  1183. maxPolys += meshes[i]->npolys;
  1184. }
  1185. mesh.nverts = 0;
  1186. mesh.verts = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxVerts*3, RC_ALLOC_PERM);
  1187. if (!mesh.verts)
  1188. {
  1189. ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'mesh.verts' (%d).", maxVerts*3);
  1190. return false;
  1191. }
  1192. mesh.npolys = 0;
  1193. mesh.polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxPolys*2*mesh.nvp, RC_ALLOC_PERM);
  1194. if (!mesh.polys)
  1195. {
  1196. ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'mesh.polys' (%d).", maxPolys*2*mesh.nvp);
  1197. return false;
  1198. }
  1199. memset(mesh.polys, 0xff, sizeof(unsigned short)*maxPolys*2*mesh.nvp);
  1200. mesh.regs = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxPolys, RC_ALLOC_PERM);
  1201. if (!mesh.regs)
  1202. {
  1203. ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'mesh.regs' (%d).", maxPolys);
  1204. return false;
  1205. }
  1206. memset(mesh.regs, 0, sizeof(unsigned short)*maxPolys);
  1207. mesh.areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*maxPolys, RC_ALLOC_PERM);
  1208. if (!mesh.areas)
  1209. {
  1210. ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'mesh.areas' (%d).", maxPolys);
  1211. return false;
  1212. }
  1213. memset(mesh.areas, 0, sizeof(unsigned char)*maxPolys);
  1214. mesh.flags = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxPolys, RC_ALLOC_PERM);
  1215. if (!mesh.flags)
  1216. {
  1217. ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'mesh.flags' (%d).", maxPolys);
  1218. return false;
  1219. }
  1220. memset(mesh.flags, 0, sizeof(unsigned short)*maxPolys);
  1221. rcScopedDelete<int> nextVert((int*)rcAlloc(sizeof(int)*maxVerts, RC_ALLOC_TEMP));
  1222. if (!nextVert)
  1223. {
  1224. ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'nextVert' (%d).", maxVerts);
  1225. return false;
  1226. }
  1227. memset(nextVert, 0, sizeof(int)*maxVerts);
  1228. rcScopedDelete<int> firstVert((int*)rcAlloc(sizeof(int)*VERTEX_BUCKET_COUNT, RC_ALLOC_TEMP));
  1229. if (!firstVert)
  1230. {
  1231. ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'firstVert' (%d).", VERTEX_BUCKET_COUNT);
  1232. return false;
  1233. }
  1234. for (int i = 0; i < VERTEX_BUCKET_COUNT; ++i)
  1235. firstVert[i] = -1;
  1236. rcScopedDelete<unsigned short> vremap((unsigned short*)rcAlloc(sizeof(unsigned short)*maxVertsPerMesh, RC_ALLOC_PERM));
  1237. if (!vremap)
  1238. {
  1239. ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'vremap' (%d).", maxVertsPerMesh);
  1240. return false;
  1241. }
  1242. memset(vremap, 0, sizeof(unsigned short)*maxVertsPerMesh);
  1243. for (int i = 0; i < nmeshes; ++i)
  1244. {
  1245. const rcPolyMesh* pmesh = meshes[i];
  1246. const unsigned short ox = (unsigned short)floorf((pmesh->bmin[0]-mesh.bmin[0])/mesh.cs+0.5f);
  1247. const unsigned short oz = (unsigned short)floorf((pmesh->bmin[2]-mesh.bmin[2])/mesh.cs+0.5f);
  1248. bool isMinX = (ox == 0);
  1249. bool isMinZ = (oz == 0);
  1250. bool isMaxX = ((unsigned short)floorf((mesh.bmax[0] - pmesh->bmax[0]) / mesh.cs + 0.5f)) == 0;
  1251. bool isMaxZ = ((unsigned short)floorf((mesh.bmax[2] - pmesh->bmax[2]) / mesh.cs + 0.5f)) == 0;
  1252. bool isOnBorder = (isMinX || isMinZ || isMaxX || isMaxZ);
  1253. for (int j = 0; j < pmesh->nverts; ++j)
  1254. {
  1255. unsigned short* v = &pmesh->verts[j*3];
  1256. vremap[j] = addVertex(v[0]+ox, v[1], v[2]+oz,
  1257. mesh.verts, firstVert, nextVert, mesh.nverts);
  1258. }
  1259. for (int j = 0; j < pmesh->npolys; ++j)
  1260. {
  1261. unsigned short* tgt = &mesh.polys[mesh.npolys*2*mesh.nvp];
  1262. unsigned short* src = &pmesh->polys[j*2*mesh.nvp];
  1263. mesh.regs[mesh.npolys] = pmesh->regs[j];
  1264. mesh.areas[mesh.npolys] = pmesh->areas[j];
  1265. mesh.flags[mesh.npolys] = pmesh->flags[j];
  1266. mesh.npolys++;
  1267. for (int k = 0; k < mesh.nvp; ++k)
  1268. {
  1269. if (src[k] == RC_MESH_NULL_IDX) break;
  1270. tgt[k] = vremap[src[k]];
  1271. }
  1272. if (isOnBorder)
  1273. {
  1274. for (int k = mesh.nvp; k < mesh.nvp * 2; ++k)
  1275. {
  1276. if (src[k] & 0x8000 && src[k] != 0xffff)
  1277. {
  1278. unsigned short dir = src[k] & 0xf;
  1279. switch (dir)
  1280. {
  1281. case 0: // Portal x-
  1282. if (isMinX)
  1283. tgt[k] = src[k];
  1284. break;
  1285. case 1: // Portal z+
  1286. if (isMaxZ)
  1287. tgt[k] = src[k];
  1288. break;
  1289. case 2: // Portal x+
  1290. if (isMaxX)
  1291. tgt[k] = src[k];
  1292. break;
  1293. case 3: // Portal z-
  1294. if (isMinZ)
  1295. tgt[k] = src[k];
  1296. break;
  1297. }
  1298. }
  1299. }
  1300. }
  1301. }
  1302. }
  1303. // Calculate adjacency.
  1304. if (!buildMeshAdjacency(mesh.polys, mesh.npolys, mesh.nverts, mesh.nvp))
  1305. {
  1306. ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Adjacency failed.");
  1307. return false;
  1308. }
  1309. if (mesh.nverts > 0xffff)
  1310. {
  1311. ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: The resulting mesh has too many vertices %d (max %d). Data can be corrupted.", mesh.nverts, 0xffff);
  1312. }
  1313. if (mesh.npolys > 0xffff)
  1314. {
  1315. ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: The resulting mesh has too many polygons %d (max %d). Data can be corrupted.", mesh.npolys, 0xffff);
  1316. }
  1317. return true;
  1318. }
  1319. bool rcCopyPolyMesh(rcContext* ctx, const rcPolyMesh& src, rcPolyMesh& dst)
  1320. {
  1321. rcAssert(ctx);
  1322. // Destination must be empty.
  1323. rcAssert(dst.verts == 0);
  1324. rcAssert(dst.polys == 0);
  1325. rcAssert(dst.regs == 0);
  1326. rcAssert(dst.areas == 0);
  1327. rcAssert(dst.flags == 0);
  1328. dst.nverts = src.nverts;
  1329. dst.npolys = src.npolys;
  1330. dst.maxpolys = src.npolys;
  1331. dst.nvp = src.nvp;
  1332. rcVcopy(dst.bmin, src.bmin);
  1333. rcVcopy(dst.bmax, src.bmax);
  1334. dst.cs = src.cs;
  1335. dst.ch = src.ch;
  1336. dst.borderSize = src.borderSize;
  1337. dst.maxEdgeError = src.maxEdgeError;
  1338. dst.verts = (unsigned short*)rcAlloc(sizeof(unsigned short)*src.nverts*3, RC_ALLOC_PERM);
  1339. if (!dst.verts)
  1340. {
  1341. ctx->log(RC_LOG_ERROR, "rcCopyPolyMesh: Out of memory 'dst.verts' (%d).", src.nverts*3);
  1342. return false;
  1343. }
  1344. memcpy(dst.verts, src.verts, sizeof(unsigned short)*src.nverts*3);
  1345. dst.polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*src.npolys*2*src.nvp, RC_ALLOC_PERM);
  1346. if (!dst.polys)
  1347. {
  1348. ctx->log(RC_LOG_ERROR, "rcCopyPolyMesh: Out of memory 'dst.polys' (%d).", src.npolys*2*src.nvp);
  1349. return false;
  1350. }
  1351. memcpy(dst.polys, src.polys, sizeof(unsigned short)*src.npolys*2*src.nvp);
  1352. dst.regs = (unsigned short*)rcAlloc(sizeof(unsigned short)*src.npolys, RC_ALLOC_PERM);
  1353. if (!dst.regs)
  1354. {
  1355. ctx->log(RC_LOG_ERROR, "rcCopyPolyMesh: Out of memory 'dst.regs' (%d).", src.npolys);
  1356. return false;
  1357. }
  1358. memcpy(dst.regs, src.regs, sizeof(unsigned short)*src.npolys);
  1359. dst.areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*src.npolys, RC_ALLOC_PERM);
  1360. if (!dst.areas)
  1361. {
  1362. ctx->log(RC_LOG_ERROR, "rcCopyPolyMesh: Out of memory 'dst.areas' (%d).", src.npolys);
  1363. return false;
  1364. }
  1365. memcpy(dst.areas, src.areas, sizeof(unsigned char)*src.npolys);
  1366. dst.flags = (unsigned short*)rcAlloc(sizeof(unsigned short)*src.npolys, RC_ALLOC_PERM);
  1367. if (!dst.flags)
  1368. {
  1369. ctx->log(RC_LOG_ERROR, "rcCopyPolyMesh: Out of memory 'dst.flags' (%d).", src.npolys);
  1370. return false;
  1371. }
  1372. memcpy(dst.flags, src.flags, sizeof(unsigned short)*src.npolys);
  1373. return true;
  1374. }