9
3

RecastMeshDetail.cpp 39 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464
  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 <float.h>
  19. #define _USE_MATH_DEFINES
  20. #include <math.h>
  21. #include <string.h>
  22. #include <stdlib.h>
  23. #include <stdio.h>
  24. #include "Recast.h"
  25. #include "RecastAlloc.h"
  26. #include "RecastAssert.h"
  27. static const unsigned RC_UNSET_HEIGHT = 0xffff;
  28. struct rcHeightPatch
  29. {
  30. inline rcHeightPatch() : data(0), xmin(0), ymin(0), width(0), height(0) {}
  31. inline ~rcHeightPatch() { rcFree(data); }
  32. unsigned short* data;
  33. int xmin, ymin, width, height;
  34. };
  35. inline float vdot2(const float* a, const float* b)
  36. {
  37. return a[0]*b[0] + a[2]*b[2];
  38. }
  39. inline float vdistSq2(const float* p, const float* q)
  40. {
  41. const float dx = q[0] - p[0];
  42. const float dy = q[2] - p[2];
  43. return dx*dx + dy*dy;
  44. }
  45. inline float vdist2(const float* p, const float* q)
  46. {
  47. return sqrtf(vdistSq2(p,q));
  48. }
  49. inline float vcross2(const float* p1, const float* p2, const float* p3)
  50. {
  51. const float u1 = p2[0] - p1[0];
  52. const float v1 = p2[2] - p1[2];
  53. const float u2 = p3[0] - p1[0];
  54. const float v2 = p3[2] - p1[2];
  55. return u1 * v2 - v1 * u2;
  56. }
  57. static bool circumCircle(const float* p1, const float* p2, const float* p3,
  58. float* c, float& r)
  59. {
  60. static const float EPS = 1e-6f;
  61. // Calculate the circle relative to p1, to avoid some precision issues.
  62. const float v1[3] = {0,0,0};
  63. float v2[3], v3[3];
  64. rcVsub(v2, p2,p1);
  65. rcVsub(v3, p3,p1);
  66. const float cp = vcross2(v1, v2, v3);
  67. if (fabsf(cp) > EPS)
  68. {
  69. const float v1Sq = vdot2(v1,v1);
  70. const float v2Sq = vdot2(v2,v2);
  71. const float v3Sq = vdot2(v3,v3);
  72. c[0] = (v1Sq*(v2[2]-v3[2]) + v2Sq*(v3[2]-v1[2]) + v3Sq*(v1[2]-v2[2])) / (2*cp);
  73. c[1] = 0;
  74. c[2] = (v1Sq*(v3[0]-v2[0]) + v2Sq*(v1[0]-v3[0]) + v3Sq*(v2[0]-v1[0])) / (2*cp);
  75. r = vdist2(c, v1);
  76. rcVadd(c, c, p1);
  77. return true;
  78. }
  79. rcVcopy(c, p1);
  80. r = 0;
  81. return false;
  82. }
  83. static float distPtTri(const float* p, const float* a, const float* b, const float* c)
  84. {
  85. float v0[3], v1[3], v2[3];
  86. rcVsub(v0, c,a);
  87. rcVsub(v1, b,a);
  88. rcVsub(v2, p,a);
  89. const float dot00 = vdot2(v0, v0);
  90. const float dot01 = vdot2(v0, v1);
  91. const float dot02 = vdot2(v0, v2);
  92. const float dot11 = vdot2(v1, v1);
  93. const float dot12 = vdot2(v1, v2);
  94. // Compute barycentric coordinates
  95. const float invDenom = 1.0f / (dot00 * dot11 - dot01 * dot01);
  96. const float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
  97. float v = (dot00 * dot12 - dot01 * dot02) * invDenom;
  98. // If point lies inside the triangle, return interpolated y-coord.
  99. static const float EPS = 1e-4f;
  100. if (u >= -EPS && v >= -EPS && (u+v) <= 1+EPS)
  101. {
  102. const float y = a[1] + v0[1]*u + v1[1]*v;
  103. return fabsf(y-p[1]);
  104. }
  105. return FLT_MAX;
  106. }
  107. static float distancePtSeg(const float* pt, const float* p, const float* q)
  108. {
  109. float pqx = q[0] - p[0];
  110. float pqy = q[1] - p[1];
  111. float pqz = q[2] - p[2];
  112. float dx = pt[0] - p[0];
  113. float dy = pt[1] - p[1];
  114. float dz = pt[2] - p[2];
  115. float d = pqx*pqx + pqy*pqy + pqz*pqz;
  116. float t = pqx*dx + pqy*dy + pqz*dz;
  117. if (d > 0)
  118. t /= d;
  119. if (t < 0)
  120. t = 0;
  121. else if (t > 1)
  122. t = 1;
  123. dx = p[0] + t*pqx - pt[0];
  124. dy = p[1] + t*pqy - pt[1];
  125. dz = p[2] + t*pqz - pt[2];
  126. return dx*dx + dy*dy + dz*dz;
  127. }
  128. static float distancePtSeg2d(const float* pt, const float* p, const float* q)
  129. {
  130. float pqx = q[0] - p[0];
  131. float pqz = q[2] - p[2];
  132. float dx = pt[0] - p[0];
  133. float dz = pt[2] - p[2];
  134. float d = pqx*pqx + pqz*pqz;
  135. float t = pqx*dx + pqz*dz;
  136. if (d > 0)
  137. t /= d;
  138. if (t < 0)
  139. t = 0;
  140. else if (t > 1)
  141. t = 1;
  142. dx = p[0] + t*pqx - pt[0];
  143. dz = p[2] + t*pqz - pt[2];
  144. return dx*dx + dz*dz;
  145. }
  146. static float distToTriMesh(const float* p, const float* verts, const int /*nverts*/, const int* tris, const int ntris)
  147. {
  148. float dmin = FLT_MAX;
  149. for (int i = 0; i < ntris; ++i)
  150. {
  151. const float* va = &verts[tris[i*4+0]*3];
  152. const float* vb = &verts[tris[i*4+1]*3];
  153. const float* vc = &verts[tris[i*4+2]*3];
  154. float d = distPtTri(p, va,vb,vc);
  155. if (d < dmin)
  156. dmin = d;
  157. }
  158. if (dmin == FLT_MAX) return -1;
  159. return dmin;
  160. }
  161. static float distToPoly(int nvert, const float* verts, const float* p)
  162. {
  163. float dmin = FLT_MAX;
  164. int i, j, c = 0;
  165. for (i = 0, j = nvert-1; i < nvert; j = i++)
  166. {
  167. const float* vi = &verts[i*3];
  168. const float* vj = &verts[j*3];
  169. if (((vi[2] > p[2]) != (vj[2] > p[2])) &&
  170. (p[0] < (vj[0]-vi[0]) * (p[2]-vi[2]) / (vj[2]-vi[2]) + vi[0]) )
  171. c = !c;
  172. dmin = rcMin(dmin, distancePtSeg2d(p, vj, vi));
  173. }
  174. return c ? -dmin : dmin;
  175. }
  176. static unsigned short getHeight(const float fx, const float fy, const float fz,
  177. const float /*cs*/, const float ics, const float ch,
  178. const int radius, const rcHeightPatch& hp)
  179. {
  180. int ix = (int)floorf(fx*ics + 0.01f);
  181. int iz = (int)floorf(fz*ics + 0.01f);
  182. ix = rcClamp(ix-hp.xmin, 0, hp.width - 1);
  183. iz = rcClamp(iz-hp.ymin, 0, hp.height - 1);
  184. unsigned short h = hp.data[ix+iz*hp.width];
  185. if (h == RC_UNSET_HEIGHT)
  186. {
  187. // Special case when data might be bad.
  188. // Walk adjacent cells in a spiral up to 'radius', and look
  189. // for a pixel which has a valid height.
  190. int x = 1, z = 0, dx = 1, dz = 0;
  191. int maxSize = radius * 2 + 1;
  192. int maxIter = maxSize * maxSize - 1;
  193. int nextRingIterStart = 8;
  194. int nextRingIters = 16;
  195. float dmin = FLT_MAX;
  196. for (int i = 0; i < maxIter; i++)
  197. {
  198. const int nx = ix + x;
  199. const int nz = iz + z;
  200. if (nx >= 0 && nz >= 0 && nx < hp.width && nz < hp.height)
  201. {
  202. const unsigned short nh = hp.data[nx + nz*hp.width];
  203. if (nh != RC_UNSET_HEIGHT)
  204. {
  205. const float d = fabsf(nh*ch - fy);
  206. if (d < dmin)
  207. {
  208. h = nh;
  209. dmin = d;
  210. }
  211. }
  212. }
  213. // We are searching in a grid which looks approximately like this:
  214. // __________
  215. // |2 ______ 2|
  216. // | |1 __ 1| |
  217. // | | |__| | |
  218. // | |______| |
  219. // |__________|
  220. // We want to find the best height as close to the center cell as possible. This means that
  221. // if we find a height in one of the neighbor cells to the center, we don't want to
  222. // expand further out than the 8 neighbors - we want to limit our search to the closest
  223. // of these "rings", but the best height in the ring.
  224. // For example, the center is just 1 cell. We checked that at the entrance to the function.
  225. // The next "ring" contains 8 cells (marked 1 above). Those are all the neighbors to the center cell.
  226. // The next one again contains 16 cells (marked 2). In general each ring has 8 additional cells, which
  227. // can be thought of as adding 2 cells around the "center" of each side when we expand the ring.
  228. // Here we detect if we are about to enter the next ring, and if we are and we have found
  229. // a height, we abort the search.
  230. if (i + 1 == nextRingIterStart)
  231. {
  232. if (h != RC_UNSET_HEIGHT)
  233. break;
  234. nextRingIterStart += nextRingIters;
  235. nextRingIters += 8;
  236. }
  237. if ((x == z) || ((x < 0) && (x == -z)) || ((x > 0) && (x == 1 - z)))
  238. {
  239. int tmp = dx;
  240. dx = -dz;
  241. dz = tmp;
  242. }
  243. x += dx;
  244. z += dz;
  245. }
  246. }
  247. return h;
  248. }
  249. enum EdgeValues
  250. {
  251. EV_UNDEF = -1,
  252. EV_HULL = -2,
  253. };
  254. static int findEdge(const int* edges, int nedges, int s, int t)
  255. {
  256. for (int i = 0; i < nedges; i++)
  257. {
  258. const int* e = &edges[i*4];
  259. if ((e[0] == s && e[1] == t) || (e[0] == t && e[1] == s))
  260. return i;
  261. }
  262. return EV_UNDEF;
  263. }
  264. static int addEdge(rcContext* ctx, int* edges, int& nedges, const int maxEdges, int s, int t, int l, int r)
  265. {
  266. if (nedges >= maxEdges)
  267. {
  268. ctx->log(RC_LOG_ERROR, "addEdge: Too many edges (%d/%d).", nedges, maxEdges);
  269. return EV_UNDEF;
  270. }
  271. // Add edge if not already in the triangulation.
  272. int e = findEdge(edges, nedges, s, t);
  273. if (e == EV_UNDEF)
  274. {
  275. int* edge = &edges[nedges*4];
  276. edge[0] = s;
  277. edge[1] = t;
  278. edge[2] = l;
  279. edge[3] = r;
  280. return nedges++;
  281. }
  282. else
  283. {
  284. return EV_UNDEF;
  285. }
  286. }
  287. static void updateLeftFace(int* e, int s, int t, int f)
  288. {
  289. if (e[0] == s && e[1] == t && e[2] == EV_UNDEF)
  290. e[2] = f;
  291. else if (e[1] == s && e[0] == t && e[3] == EV_UNDEF)
  292. e[3] = f;
  293. }
  294. static int overlapSegSeg2d(const float* a, const float* b, const float* c, const float* d)
  295. {
  296. const float a1 = vcross2(a, b, d);
  297. const float a2 = vcross2(a, b, c);
  298. if (a1*a2 < 0.0f)
  299. {
  300. float a3 = vcross2(c, d, a);
  301. float a4 = a3 + a2 - a1;
  302. if (a3 * a4 < 0.0f)
  303. return 1;
  304. }
  305. return 0;
  306. }
  307. static bool overlapEdges(const float* pts, const int* edges, int nedges, int s1, int t1)
  308. {
  309. for (int i = 0; i < nedges; ++i)
  310. {
  311. const int s0 = edges[i*4+0];
  312. const int t0 = edges[i*4+1];
  313. // Same or connected edges do not overlap.
  314. if (s0 == s1 || s0 == t1 || t0 == s1 || t0 == t1)
  315. continue;
  316. if (overlapSegSeg2d(&pts[s0*3],&pts[t0*3], &pts[s1*3],&pts[t1*3]))
  317. return true;
  318. }
  319. return false;
  320. }
  321. static void completeFacet(rcContext* ctx, const float* pts, int npts, int* edges, int& nedges, const int maxEdges, int& nfaces, int e)
  322. {
  323. static const float EPS = 1e-5f;
  324. int* edge = &edges[e*4];
  325. // Cache s and t.
  326. int s,t;
  327. if (edge[2] == EV_UNDEF)
  328. {
  329. s = edge[0];
  330. t = edge[1];
  331. }
  332. else if (edge[3] == EV_UNDEF)
  333. {
  334. s = edge[1];
  335. t = edge[0];
  336. }
  337. else
  338. {
  339. // Edge already completed.
  340. return;
  341. }
  342. // Find best point on left of edge.
  343. int pt = npts;
  344. float c[3] = {0,0,0};
  345. float r = -1;
  346. for (int u = 0; u < npts; ++u)
  347. {
  348. if (u == s || u == t) continue;
  349. if (vcross2(&pts[s*3], &pts[t*3], &pts[u*3]) > EPS)
  350. {
  351. if (r < 0)
  352. {
  353. // The circle is not updated yet, do it now.
  354. pt = u;
  355. circumCircle(&pts[s*3], &pts[t*3], &pts[u*3], c, r);
  356. continue;
  357. }
  358. const float d = vdist2(c, &pts[u*3]);
  359. const float tol = 0.001f;
  360. if (d > r*(1+tol))
  361. {
  362. // Outside current circumcircle, skip.
  363. continue;
  364. }
  365. else if (d < r*(1-tol))
  366. {
  367. // Inside safe circumcircle, update circle.
  368. pt = u;
  369. circumCircle(&pts[s*3], &pts[t*3], &pts[u*3], c, r);
  370. }
  371. else
  372. {
  373. // Inside epsilon circum circle, do extra tests to make sure the edge is valid.
  374. // s-u and t-u cannot overlap with s-pt nor t-pt if they exists.
  375. if (overlapEdges(pts, edges, nedges, s,u))
  376. continue;
  377. if (overlapEdges(pts, edges, nedges, t,u))
  378. continue;
  379. // Edge is valid.
  380. pt = u;
  381. circumCircle(&pts[s*3], &pts[t*3], &pts[u*3], c, r);
  382. }
  383. }
  384. }
  385. // Add new triangle or update edge info if s-t is on hull.
  386. if (pt < npts)
  387. {
  388. // Update face information of edge being completed.
  389. updateLeftFace(&edges[e*4], s, t, nfaces);
  390. // Add new edge or update face info of old edge.
  391. e = findEdge(edges, nedges, pt, s);
  392. if (e == EV_UNDEF)
  393. addEdge(ctx, edges, nedges, maxEdges, pt, s, nfaces, EV_UNDEF);
  394. else
  395. updateLeftFace(&edges[e*4], pt, s, nfaces);
  396. // Add new edge or update face info of old edge.
  397. e = findEdge(edges, nedges, t, pt);
  398. if (e == EV_UNDEF)
  399. addEdge(ctx, edges, nedges, maxEdges, t, pt, nfaces, EV_UNDEF);
  400. else
  401. updateLeftFace(&edges[e*4], t, pt, nfaces);
  402. nfaces++;
  403. }
  404. else
  405. {
  406. updateLeftFace(&edges[e*4], s, t, EV_HULL);
  407. }
  408. }
  409. static void delaunayHull(rcContext* ctx, const int npts, const float* pts,
  410. const int nhull, const int* hull,
  411. rcIntArray& tris, rcIntArray& edges)
  412. {
  413. int nfaces = 0;
  414. int nedges = 0;
  415. const int maxEdges = npts*10;
  416. edges.resize(maxEdges*4);
  417. for (int i = 0, j = nhull-1; i < nhull; j=i++)
  418. addEdge(ctx, &edges[0], nedges, maxEdges, hull[j],hull[i], EV_HULL, EV_UNDEF);
  419. int currentEdge = 0;
  420. while (currentEdge < nedges)
  421. {
  422. if (edges[currentEdge*4+2] == EV_UNDEF)
  423. completeFacet(ctx, pts, npts, &edges[0], nedges, maxEdges, nfaces, currentEdge);
  424. if (edges[currentEdge*4+3] == EV_UNDEF)
  425. completeFacet(ctx, pts, npts, &edges[0], nedges, maxEdges, nfaces, currentEdge);
  426. currentEdge++;
  427. }
  428. // Create tris
  429. tris.resize(nfaces*4);
  430. for (int i = 0; i < nfaces*4; ++i)
  431. tris[i] = -1;
  432. for (int i = 0; i < nedges; ++i)
  433. {
  434. const int* e = &edges[i*4];
  435. if (e[3] >= 0)
  436. {
  437. // Left face
  438. int* t = &tris[e[3]*4];
  439. if (t[0] == -1)
  440. {
  441. t[0] = e[0];
  442. t[1] = e[1];
  443. }
  444. else if (t[0] == e[1])
  445. t[2] = e[0];
  446. else if (t[1] == e[0])
  447. t[2] = e[1];
  448. }
  449. if (e[2] >= 0)
  450. {
  451. // Right
  452. int* t = &tris[e[2]*4];
  453. if (t[0] == -1)
  454. {
  455. t[0] = e[1];
  456. t[1] = e[0];
  457. }
  458. else if (t[0] == e[0])
  459. t[2] = e[1];
  460. else if (t[1] == e[1])
  461. t[2] = e[0];
  462. }
  463. }
  464. for (int i = 0; i < tris.size()/4; ++i)
  465. {
  466. int* t = &tris[i*4];
  467. if (t[0] == -1 || t[1] == -1 || t[2] == -1)
  468. {
  469. ctx->log(RC_LOG_WARNING, "delaunayHull: Removing dangling face %d [%d,%d,%d].", i, t[0],t[1],t[2]);
  470. t[0] = tris[tris.size()-4];
  471. t[1] = tris[tris.size()-3];
  472. t[2] = tris[tris.size()-2];
  473. t[3] = tris[tris.size()-1];
  474. tris.resize(tris.size()-4);
  475. --i;
  476. }
  477. }
  478. }
  479. // Calculate minimum extend of the polygon.
  480. static float polyMinExtent(const float* verts, const int nverts)
  481. {
  482. float minDist = FLT_MAX;
  483. for (int i = 0; i < nverts; i++)
  484. {
  485. const int ni = (i+1) % nverts;
  486. const float* p1 = &verts[i*3];
  487. const float* p2 = &verts[ni*3];
  488. float maxEdgeDist = 0;
  489. for (int j = 0; j < nverts; j++)
  490. {
  491. if (j == i || j == ni) continue;
  492. float d = distancePtSeg2d(&verts[j*3], p1,p2);
  493. maxEdgeDist = rcMax(maxEdgeDist, d);
  494. }
  495. minDist = rcMin(minDist, maxEdgeDist);
  496. }
  497. return rcSqrt(minDist);
  498. }
  499. // Last time I checked the if version got compiled using cmov, which was a lot faster than module (with idiv).
  500. inline int prev(int i, int n) { return i-1 >= 0 ? i-1 : n-1; }
  501. inline int next(int i, int n) { return i+1 < n ? i+1 : 0; }
  502. static void triangulateHull(const int /*nverts*/, const float* verts, const int nhull, const int* hull, const int nin, rcIntArray& tris)
  503. {
  504. int start = 0, left = 1, right = nhull-1;
  505. // Start from an ear with shortest perimeter.
  506. // This tends to favor well formed triangles as starting point.
  507. float dmin = FLT_MAX;
  508. for (int i = 0; i < nhull; i++)
  509. {
  510. if (hull[i] >= nin) continue; // Ears are triangles with original vertices as middle vertex while others are actually line segments on edges
  511. int pi = prev(i, nhull);
  512. int ni = next(i, nhull);
  513. const float* pv = &verts[hull[pi]*3];
  514. const float* cv = &verts[hull[i]*3];
  515. const float* nv = &verts[hull[ni]*3];
  516. const float d = vdist2(pv,cv) + vdist2(cv,nv) + vdist2(nv,pv);
  517. if (d < dmin)
  518. {
  519. start = i;
  520. left = ni;
  521. right = pi;
  522. dmin = d;
  523. }
  524. }
  525. // Add first triangle
  526. tris.push(hull[start]);
  527. tris.push(hull[left]);
  528. tris.push(hull[right]);
  529. tris.push(0);
  530. // Triangulate the polygon by moving left or right,
  531. // depending on which triangle has shorter perimeter.
  532. // This heuristic was chose emprically, since it seems
  533. // handle tesselated straight edges well.
  534. while (next(left, nhull) != right)
  535. {
  536. // Check to see if se should advance left or right.
  537. int nleft = next(left, nhull);
  538. int nright = prev(right, nhull);
  539. const float* cvleft = &verts[hull[left]*3];
  540. const float* nvleft = &verts[hull[nleft]*3];
  541. const float* cvright = &verts[hull[right]*3];
  542. const float* nvright = &verts[hull[nright]*3];
  543. const float dleft = vdist2(cvleft, nvleft) + vdist2(nvleft, cvright);
  544. const float dright = vdist2(cvright, nvright) + vdist2(cvleft, nvright);
  545. if (dleft < dright)
  546. {
  547. tris.push(hull[left]);
  548. tris.push(hull[nleft]);
  549. tris.push(hull[right]);
  550. tris.push(0);
  551. left = nleft;
  552. }
  553. else
  554. {
  555. tris.push(hull[left]);
  556. tris.push(hull[nright]);
  557. tris.push(hull[right]);
  558. tris.push(0);
  559. right = nright;
  560. }
  561. }
  562. }
  563. inline float getJitterX(const int i)
  564. {
  565. return (((i * 0x8da6b343) & 0xffff) / 65535.0f * 2.0f) - 1.0f;
  566. }
  567. inline float getJitterY(const int i)
  568. {
  569. return (((i * 0xd8163841) & 0xffff) / 65535.0f * 2.0f) - 1.0f;
  570. }
  571. static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin,
  572. const float sampleDist, const float sampleMaxError,
  573. const int heightSearchRadius, const rcCompactHeightfield& chf,
  574. const rcHeightPatch& hp, float* verts, int& nverts,
  575. rcIntArray& tris, rcIntArray& edges, rcIntArray& samples)
  576. {
  577. static const int MAX_VERTS = 127;
  578. static const int MAX_TRIS = 255; // Max tris for delaunay is 2n-2-k (n=num verts, k=num hull verts).
  579. static const int MAX_VERTS_PER_EDGE = 32;
  580. float edge[(MAX_VERTS_PER_EDGE+1)*3];
  581. int hull[MAX_VERTS];
  582. int nhull = 0;
  583. nverts = nin;
  584. for (int i = 0; i < nin; ++i)
  585. rcVcopy(&verts[i*3], &in[i*3]);
  586. edges.resize(0);
  587. tris.resize(0);
  588. const float cs = chf.cs;
  589. const float ics = 1.0f/cs;
  590. // Calculate minimum extents of the polygon based on input data.
  591. float minExtent = polyMinExtent(verts, nverts);
  592. // Tessellate outlines.
  593. // This is done in separate pass in order to ensure
  594. // seamless height values across the ply boundaries.
  595. if (sampleDist > 0)
  596. {
  597. for (int i = 0, j = nin-1; i < nin; j=i++)
  598. {
  599. const float* vj = &in[j*3];
  600. const float* vi = &in[i*3];
  601. bool swapped = false;
  602. // Make sure the segments are always handled in same order
  603. // using lexological sort or else there will be seams.
  604. if (fabsf(vj[0]-vi[0]) < 1e-6f)
  605. {
  606. if (vj[2] > vi[2])
  607. {
  608. rcSwap(vj,vi);
  609. swapped = true;
  610. }
  611. }
  612. else
  613. {
  614. if (vj[0] > vi[0])
  615. {
  616. rcSwap(vj,vi);
  617. swapped = true;
  618. }
  619. }
  620. // Create samples along the edge.
  621. float dx = vi[0] - vj[0];
  622. float dy = vi[1] - vj[1];
  623. float dz = vi[2] - vj[2];
  624. float d = sqrtf(dx*dx + dz*dz);
  625. int nn = 1 + (int)floorf(d/sampleDist);
  626. if (nn >= MAX_VERTS_PER_EDGE) nn = MAX_VERTS_PER_EDGE-1;
  627. if (nverts+nn >= MAX_VERTS)
  628. nn = MAX_VERTS-1-nverts;
  629. for (int k = 0; k <= nn; ++k)
  630. {
  631. float u = (float)k/(float)nn;
  632. float* pos = &edge[k*3];
  633. pos[0] = vj[0] + dx*u;
  634. pos[1] = vj[1] + dy*u;
  635. pos[2] = vj[2] + dz*u;
  636. pos[1] = getHeight(pos[0],pos[1],pos[2], cs, ics, chf.ch, heightSearchRadius, hp)*chf.ch;
  637. }
  638. // Simplify samples.
  639. int idx[MAX_VERTS_PER_EDGE] = {0,nn};
  640. int nidx = 2;
  641. for (int k = 0; k < nidx-1; )
  642. {
  643. const int a = idx[k];
  644. const int b = idx[k+1];
  645. const float* va = &edge[a*3];
  646. const float* vb = &edge[b*3];
  647. // Find maximum deviation along the segment.
  648. float maxd = 0;
  649. int maxi = -1;
  650. for (int m = a+1; m < b; ++m)
  651. {
  652. float dev = distancePtSeg(&edge[m*3],va,vb);
  653. if (dev > maxd)
  654. {
  655. maxd = dev;
  656. maxi = m;
  657. }
  658. }
  659. // If the max deviation is larger than accepted error,
  660. // add new point, else continue to next segment.
  661. if (maxi != -1 && maxd > rcSqr(sampleMaxError))
  662. {
  663. for (int m = nidx; m > k; --m)
  664. idx[m] = idx[m-1];
  665. idx[k+1] = maxi;
  666. nidx++;
  667. }
  668. else
  669. {
  670. ++k;
  671. }
  672. }
  673. hull[nhull++] = j;
  674. // Add new vertices.
  675. if (swapped)
  676. {
  677. for (int k = nidx-2; k > 0; --k)
  678. {
  679. rcVcopy(&verts[nverts*3], &edge[idx[k]*3]);
  680. hull[nhull++] = nverts;
  681. nverts++;
  682. }
  683. }
  684. else
  685. {
  686. for (int k = 1; k < nidx-1; ++k)
  687. {
  688. rcVcopy(&verts[nverts*3], &edge[idx[k]*3]);
  689. hull[nhull++] = nverts;
  690. nverts++;
  691. }
  692. }
  693. }
  694. }
  695. // If the polygon minimum extent is small (sliver or small triangle), do not try to add internal points.
  696. if (minExtent < sampleDist*2)
  697. {
  698. triangulateHull(nverts, verts, nhull, hull, nin, tris);
  699. return true;
  700. }
  701. // Tessellate the base mesh.
  702. // We're using the triangulateHull instead of delaunayHull as it tends to
  703. // create a bit better triangulation for long thin triangles when there
  704. // are no internal points.
  705. triangulateHull(nverts, verts, nhull, hull, nin, tris);
  706. if (tris.size() == 0)
  707. {
  708. // Could not triangulate the poly, make sure there is some valid data there.
  709. ctx->log(RC_LOG_WARNING, "buildPolyDetail: Could not triangulate polygon (%d verts).", nverts);
  710. return true;
  711. }
  712. if (sampleDist > 0)
  713. {
  714. // Create sample locations in a grid.
  715. float bmin[3], bmax[3];
  716. rcVcopy(bmin, in);
  717. rcVcopy(bmax, in);
  718. for (int i = 1; i < nin; ++i)
  719. {
  720. rcVmin(bmin, &in[i*3]);
  721. rcVmax(bmax, &in[i*3]);
  722. }
  723. int x0 = (int)floorf(bmin[0]/sampleDist);
  724. int x1 = (int)ceilf(bmax[0]/sampleDist);
  725. int z0 = (int)floorf(bmin[2]/sampleDist);
  726. int z1 = (int)ceilf(bmax[2]/sampleDist);
  727. samples.resize(0);
  728. for (int z = z0; z < z1; ++z)
  729. {
  730. for (int x = x0; x < x1; ++x)
  731. {
  732. float pt[3];
  733. pt[0] = x*sampleDist;
  734. pt[1] = (bmax[1]+bmin[1])*0.5f;
  735. pt[2] = z*sampleDist;
  736. // Make sure the samples are not too close to the edges.
  737. if (distToPoly(nin,in,pt) > -sampleDist/2) continue;
  738. samples.push(x);
  739. samples.push(getHeight(pt[0], pt[1], pt[2], cs, ics, chf.ch, heightSearchRadius, hp));
  740. samples.push(z);
  741. samples.push(0); // Not added
  742. }
  743. }
  744. // Add the samples starting from the one that has the most
  745. // error. The procedure stops when all samples are added
  746. // or when the max error is within treshold.
  747. const int nsamples = samples.size()/4;
  748. for (int iter = 0; iter < nsamples; ++iter)
  749. {
  750. if (nverts >= MAX_VERTS)
  751. break;
  752. // Find sample with most error.
  753. float bestpt[3] = {0,0,0};
  754. float bestd = 0;
  755. int besti = -1;
  756. for (int i = 0; i < nsamples; ++i)
  757. {
  758. const int* s = &samples[i*4];
  759. if (s[3]) continue; // skip added.
  760. float pt[3];
  761. // The sample location is jittered to get rid of some bad triangulations
  762. // which are cause by symmetrical data from the grid structure.
  763. pt[0] = s[0]*sampleDist + getJitterX(i)*cs*0.1f;
  764. pt[1] = s[1]*chf.ch;
  765. pt[2] = s[2]*sampleDist + getJitterY(i)*cs*0.1f;
  766. float d = distToTriMesh(pt, verts, nverts, &tris[0], tris.size()/4);
  767. if (d < 0) continue; // did not hit the mesh.
  768. if (d > bestd)
  769. {
  770. bestd = d;
  771. besti = i;
  772. rcVcopy(bestpt,pt);
  773. }
  774. }
  775. // If the max error is within accepted threshold, stop tesselating.
  776. if (bestd <= sampleMaxError || besti == -1)
  777. break;
  778. // Mark sample as added.
  779. samples[besti*4+3] = 1;
  780. // Add the new sample point.
  781. rcVcopy(&verts[nverts*3],bestpt);
  782. nverts++;
  783. // Create new triangulation.
  784. // TODO: Incremental add instead of full rebuild.
  785. edges.resize(0);
  786. tris.resize(0);
  787. delaunayHull(ctx, nverts, verts, nhull, hull, tris, edges);
  788. }
  789. }
  790. const int ntris = tris.size()/4;
  791. if (ntris > MAX_TRIS)
  792. {
  793. tris.resize(MAX_TRIS*4);
  794. ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Shrinking triangle count from %d to max %d.", ntris, MAX_TRIS);
  795. }
  796. return true;
  797. }
  798. static void seedArrayWithPolyCenter(rcContext* ctx, const rcCompactHeightfield& chf,
  799. const unsigned short* poly, const int npoly,
  800. const unsigned short* verts, const int bs,
  801. rcHeightPatch& hp, rcIntArray& array)
  802. {
  803. // Note: Reads to the compact heightfield are offset by border size (bs)
  804. // since border size offset is already removed from the polymesh vertices.
  805. static const int offset[9*2] =
  806. {
  807. 0,0, -1,-1, 0,-1, 1,-1, 1,0, 1,1, 0,1, -1,1, -1,0,
  808. };
  809. // Find cell closest to a poly vertex
  810. int startCellX = 0, startCellY = 0, startSpanIndex = -1;
  811. int dmin = RC_UNSET_HEIGHT;
  812. for (int j = 0; j < npoly && dmin > 0; ++j)
  813. {
  814. for (int k = 0; k < 9 && dmin > 0; ++k)
  815. {
  816. const int ax = (int)verts[poly[j]*3+0] + offset[k*2+0];
  817. const int ay = (int)verts[poly[j]*3+1];
  818. const int az = (int)verts[poly[j]*3+2] + offset[k*2+1];
  819. if (ax < hp.xmin || ax >= hp.xmin+hp.width ||
  820. az < hp.ymin || az >= hp.ymin+hp.height)
  821. continue;
  822. const rcCompactCell& c = chf.cells[(ax+bs)+(az+bs)*chf.width];
  823. for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni && dmin > 0; ++i)
  824. {
  825. const rcCompactSpan& s = chf.spans[i];
  826. int d = rcAbs(ay - (int)s.y);
  827. if (d < dmin)
  828. {
  829. startCellX = ax;
  830. startCellY = az;
  831. startSpanIndex = i;
  832. dmin = d;
  833. }
  834. }
  835. }
  836. }
  837. rcAssert(startSpanIndex != -1);
  838. // Find center of the polygon
  839. int pcx = 0, pcy = 0;
  840. for (int j = 0; j < npoly; ++j)
  841. {
  842. pcx += (int)verts[poly[j]*3+0];
  843. pcy += (int)verts[poly[j]*3+2];
  844. }
  845. pcx /= npoly;
  846. pcy /= npoly;
  847. // Use seeds array as a stack for DFS
  848. array.resize(0);
  849. array.push(startCellX);
  850. array.push(startCellY);
  851. array.push(startSpanIndex);
  852. int dirs[] = { 0, 1, 2, 3 };
  853. memset(hp.data, 0, sizeof(unsigned short)*hp.width*hp.height);
  854. // DFS to move to the center. Note that we need a DFS here and can not just move
  855. // directly towards the center without recording intermediate nodes, even though the polygons
  856. // are convex. In very rare we can get stuck due to contour simplification if we do not
  857. // record nodes.
  858. int cx = -1, cy = -1, ci = -1;
  859. while (true)
  860. {
  861. if (array.size() < 3)
  862. {
  863. ctx->log(RC_LOG_WARNING, "Walk towards polygon center failed to reach center");
  864. break;
  865. }
  866. ci = array.pop();
  867. cy = array.pop();
  868. cx = array.pop();
  869. if (cx == pcx && cy == pcy)
  870. break;
  871. // If we are already at the correct X-position, prefer direction
  872. // directly towards the center in the Y-axis; otherwise prefer
  873. // direction in the X-axis
  874. int directDir;
  875. if (cx == pcx)
  876. directDir = rcGetDirForOffset(0, pcy > cy ? 1 : -1);
  877. else
  878. directDir = rcGetDirForOffset(pcx > cx ? 1 : -1, 0);
  879. // Push the direct dir last so we start with this on next iteration
  880. rcSwap(dirs[directDir], dirs[3]);
  881. const rcCompactSpan& cs = chf.spans[ci];
  882. for (int i = 0; i < 4; i++)
  883. {
  884. int dir = dirs[i];
  885. if (rcGetCon(cs, dir) == RC_NOT_CONNECTED)
  886. continue;
  887. int newX = cx + rcGetDirOffsetX(dir);
  888. int newY = cy + rcGetDirOffsetY(dir);
  889. int hpx = newX - hp.xmin;
  890. int hpy = newY - hp.ymin;
  891. if (hpx < 0 || hpx >= hp.width || hpy < 0 || hpy >= hp.height)
  892. continue;
  893. if (hp.data[hpx+hpy*hp.width] != 0)
  894. continue;
  895. hp.data[hpx+hpy*hp.width] = 1;
  896. array.push(newX);
  897. array.push(newY);
  898. array.push((int)chf.cells[(newX+bs)+(newY+bs)*chf.width].index + rcGetCon(cs, dir));
  899. }
  900. rcSwap(dirs[directDir], dirs[3]);
  901. }
  902. array.resize(0);
  903. // getHeightData seeds are given in coordinates with borders
  904. array.push(cx+bs);
  905. array.push(cy+bs);
  906. array.push(ci);
  907. memset(hp.data, 0xff, sizeof(unsigned short)*hp.width*hp.height);
  908. const rcCompactSpan& cs = chf.spans[ci];
  909. hp.data[cx-hp.xmin+(cy-hp.ymin)*hp.width] = cs.y;
  910. }
  911. static void push3(rcIntArray& queue, int v1, int v2, int v3)
  912. {
  913. queue.resize(queue.size() + 3);
  914. queue[queue.size() - 3] = v1;
  915. queue[queue.size() - 2] = v2;
  916. queue[queue.size() - 1] = v3;
  917. }
  918. static void getHeightData(rcContext* ctx, const rcCompactHeightfield& chf,
  919. const unsigned short* poly, const int npoly,
  920. const unsigned short* verts, const int bs,
  921. rcHeightPatch& hp, rcIntArray& queue,
  922. int region)
  923. {
  924. // Note: Reads to the compact heightfield are offset by border size (bs)
  925. // since border size offset is already removed from the polymesh vertices.
  926. queue.resize(0);
  927. // Set all heights to RC_UNSET_HEIGHT.
  928. memset(hp.data, 0xff, sizeof(unsigned short)*hp.width*hp.height);
  929. bool empty = true;
  930. // We cannot sample from this poly if it was created from polys
  931. // of different regions. If it was then it could potentially be overlapping
  932. // with polys of that region and the heights sampled here could be wrong.
  933. if (region != RC_MULTIPLE_REGS)
  934. {
  935. // Copy the height from the same region, and mark region borders
  936. // as seed points to fill the rest.
  937. for (int hy = 0; hy < hp.height; hy++)
  938. {
  939. int y = hp.ymin + hy + bs;
  940. for (int hx = 0; hx < hp.width; hx++)
  941. {
  942. int x = hp.xmin + hx + bs;
  943. const rcCompactCell& c = chf.cells[x + y*chf.width];
  944. for (int i = (int)c.index, ni = (int)(c.index + c.count); i < ni; ++i)
  945. {
  946. const rcCompactSpan& s = chf.spans[i];
  947. if (s.reg == region)
  948. {
  949. // Store height
  950. hp.data[hx + hy*hp.width] = s.y;
  951. empty = false;
  952. // If any of the neighbours is not in same region,
  953. // add the current location as flood fill start
  954. bool border = false;
  955. for (int dir = 0; dir < 4; ++dir)
  956. {
  957. if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
  958. {
  959. const int ax = x + rcGetDirOffsetX(dir);
  960. const int ay = y + rcGetDirOffsetY(dir);
  961. const int ai = (int)chf.cells[ax + ay*chf.width].index + rcGetCon(s, dir);
  962. const rcCompactSpan& as = chf.spans[ai];
  963. if (as.reg != region)
  964. {
  965. border = true;
  966. break;
  967. }
  968. }
  969. }
  970. if (border)
  971. push3(queue, x, y, i);
  972. break;
  973. }
  974. }
  975. }
  976. }
  977. }
  978. // if the polygon does not contain any points from the current region (rare, but happens)
  979. // or if it could potentially be overlapping polygons of the same region,
  980. // then use the center as the seed point.
  981. if (empty)
  982. seedArrayWithPolyCenter(ctx, chf, poly, npoly, verts, bs, hp, queue);
  983. static const int RETRACT_SIZE = 256;
  984. int head = 0;
  985. // We assume the seed is centered in the polygon, so a BFS to collect
  986. // height data will ensure we do not move onto overlapping polygons and
  987. // sample wrong heights.
  988. while (head*3 < queue.size())
  989. {
  990. int cx = queue[head*3+0];
  991. int cy = queue[head*3+1];
  992. int ci = queue[head*3+2];
  993. head++;
  994. if (head >= RETRACT_SIZE)
  995. {
  996. head = 0;
  997. if (queue.size() > RETRACT_SIZE*3)
  998. memmove(&queue[0], &queue[RETRACT_SIZE*3], sizeof(int)*(queue.size()-RETRACT_SIZE*3));
  999. queue.resize(queue.size()-RETRACT_SIZE*3);
  1000. }
  1001. const rcCompactSpan& cs = chf.spans[ci];
  1002. for (int dir = 0; dir < 4; ++dir)
  1003. {
  1004. if (rcGetCon(cs, dir) == RC_NOT_CONNECTED) continue;
  1005. const int ax = cx + rcGetDirOffsetX(dir);
  1006. const int ay = cy + rcGetDirOffsetY(dir);
  1007. const int hx = ax - hp.xmin - bs;
  1008. const int hy = ay - hp.ymin - bs;
  1009. if ((unsigned int)hx >= (unsigned int)hp.width || (unsigned int)hy >= (unsigned int)hp.height)
  1010. continue;
  1011. if (hp.data[hx + hy*hp.width] != RC_UNSET_HEIGHT)
  1012. continue;
  1013. const int ai = (int)chf.cells[ax + ay*chf.width].index + rcGetCon(cs, dir);
  1014. const rcCompactSpan& as = chf.spans[ai];
  1015. hp.data[hx + hy*hp.width] = as.y;
  1016. push3(queue, ax, ay, ai);
  1017. }
  1018. }
  1019. }
  1020. static unsigned char getEdgeFlags(const float* va, const float* vb,
  1021. const float* vpoly, const int npoly)
  1022. {
  1023. // The flag returned by this function matches dtDetailTriEdgeFlags in Detour.
  1024. // Figure out if edge (va,vb) is part of the polygon boundary.
  1025. static const float thrSqr = rcSqr(0.001f);
  1026. for (int i = 0, j = npoly-1; i < npoly; j=i++)
  1027. {
  1028. if (distancePtSeg2d(va, &vpoly[j*3], &vpoly[i*3]) < thrSqr &&
  1029. distancePtSeg2d(vb, &vpoly[j*3], &vpoly[i*3]) < thrSqr)
  1030. return 1;
  1031. }
  1032. return 0;
  1033. }
  1034. static unsigned char getTriFlags(const float* va, const float* vb, const float* vc,
  1035. const float* vpoly, const int npoly)
  1036. {
  1037. unsigned char flags = 0;
  1038. flags |= getEdgeFlags(va,vb,vpoly,npoly) << 0;
  1039. flags |= getEdgeFlags(vb,vc,vpoly,npoly) << 2;
  1040. flags |= getEdgeFlags(vc,va,vpoly,npoly) << 4;
  1041. return flags;
  1042. }
  1043. /// @par
  1044. ///
  1045. /// See the #rcConfig documentation for more information on the configuration parameters.
  1046. ///
  1047. /// @see rcAllocPolyMeshDetail, rcPolyMesh, rcCompactHeightfield, rcPolyMeshDetail, rcConfig
  1048. bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompactHeightfield& chf,
  1049. const float sampleDist, const float sampleMaxError,
  1050. rcPolyMeshDetail& dmesh)
  1051. {
  1052. rcAssert(ctx);
  1053. rcScopedTimer timer(ctx, RC_TIMER_BUILD_POLYMESHDETAIL);
  1054. if (mesh.nverts == 0 || mesh.npolys == 0)
  1055. return true;
  1056. const int nvp = mesh.nvp;
  1057. const float cs = mesh.cs;
  1058. const float ch = mesh.ch;
  1059. const float* orig = mesh.bmin;
  1060. const int borderSize = mesh.borderSize;
  1061. const int heightSearchRadius = rcMax(1, (int)ceilf(mesh.maxEdgeError));
  1062. rcIntArray edges(64);
  1063. rcIntArray tris(512);
  1064. rcIntArray arr(512);
  1065. rcIntArray samples(512);
  1066. float verts[256*3];
  1067. rcHeightPatch hp;
  1068. int nPolyVerts = 0;
  1069. int maxhw = 0, maxhh = 0;
  1070. rcScopedDelete<int> bounds((int*)rcAlloc(sizeof(int)*mesh.npolys*4, RC_ALLOC_TEMP));
  1071. if (!bounds)
  1072. {
  1073. ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'bounds' (%d).", mesh.npolys*4);
  1074. return false;
  1075. }
  1076. rcScopedDelete<float> poly((float*)rcAlloc(sizeof(float)*nvp*3, RC_ALLOC_TEMP));
  1077. if (!poly)
  1078. {
  1079. ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'poly' (%d).", nvp*3);
  1080. return false;
  1081. }
  1082. // Find max size for a polygon area.
  1083. for (int i = 0; i < mesh.npolys; ++i)
  1084. {
  1085. const unsigned short* p = &mesh.polys[i*nvp*2];
  1086. int& xmin = bounds[i*4+0];
  1087. int& xmax = bounds[i*4+1];
  1088. int& ymin = bounds[i*4+2];
  1089. int& ymax = bounds[i*4+3];
  1090. xmin = chf.width;
  1091. xmax = 0;
  1092. ymin = chf.height;
  1093. ymax = 0;
  1094. for (int j = 0; j < nvp; ++j)
  1095. {
  1096. if(p[j] == RC_MESH_NULL_IDX) break;
  1097. const unsigned short* v = &mesh.verts[p[j]*3];
  1098. xmin = rcMin(xmin, (int)v[0]);
  1099. xmax = rcMax(xmax, (int)v[0]);
  1100. ymin = rcMin(ymin, (int)v[2]);
  1101. ymax = rcMax(ymax, (int)v[2]);
  1102. nPolyVerts++;
  1103. }
  1104. xmin = rcMax(0,xmin-1);
  1105. xmax = rcMin(chf.width,xmax+1);
  1106. ymin = rcMax(0,ymin-1);
  1107. ymax = rcMin(chf.height,ymax+1);
  1108. if (xmin >= xmax || ymin >= ymax) continue;
  1109. maxhw = rcMax(maxhw, xmax-xmin);
  1110. maxhh = rcMax(maxhh, ymax-ymin);
  1111. }
  1112. hp.data = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxhw*maxhh, RC_ALLOC_TEMP);
  1113. if (!hp.data)
  1114. {
  1115. ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'hp.data' (%d).", maxhw*maxhh);
  1116. return false;
  1117. }
  1118. dmesh.nmeshes = mesh.npolys;
  1119. dmesh.nverts = 0;
  1120. dmesh.ntris = 0;
  1121. dmesh.meshes = (unsigned int*)rcAlloc(sizeof(unsigned int)*dmesh.nmeshes*4, RC_ALLOC_PERM);
  1122. if (!dmesh.meshes)
  1123. {
  1124. ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.meshes' (%d).", dmesh.nmeshes*4);
  1125. return false;
  1126. }
  1127. int vcap = nPolyVerts+nPolyVerts/2;
  1128. int tcap = vcap*2;
  1129. dmesh.nverts = 0;
  1130. dmesh.verts = (float*)rcAlloc(sizeof(float)*vcap*3, RC_ALLOC_PERM);
  1131. if (!dmesh.verts)
  1132. {
  1133. ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.verts' (%d).", vcap*3);
  1134. return false;
  1135. }
  1136. dmesh.ntris = 0;
  1137. dmesh.tris = (unsigned char*)rcAlloc(sizeof(unsigned char)*tcap*4, RC_ALLOC_PERM);
  1138. if (!dmesh.tris)
  1139. {
  1140. ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.tris' (%d).", tcap*4);
  1141. return false;
  1142. }
  1143. for (int i = 0; i < mesh.npolys; ++i)
  1144. {
  1145. const unsigned short* p = &mesh.polys[i*nvp*2];
  1146. // Store polygon vertices for processing.
  1147. int npoly = 0;
  1148. for (int j = 0; j < nvp; ++j)
  1149. {
  1150. if(p[j] == RC_MESH_NULL_IDX) break;
  1151. const unsigned short* v = &mesh.verts[p[j]*3];
  1152. poly[j*3+0] = v[0]*cs;
  1153. poly[j*3+1] = v[1]*ch;
  1154. poly[j*3+2] = v[2]*cs;
  1155. npoly++;
  1156. }
  1157. // Get the height data from the area of the polygon.
  1158. hp.xmin = bounds[i*4+0];
  1159. hp.ymin = bounds[i*4+2];
  1160. hp.width = bounds[i*4+1]-bounds[i*4+0];
  1161. hp.height = bounds[i*4+3]-bounds[i*4+2];
  1162. getHeightData(ctx, chf, p, npoly, mesh.verts, borderSize, hp, arr, mesh.regs[i]);
  1163. // Build detail mesh.
  1164. int nverts = 0;
  1165. if (!buildPolyDetail(ctx, poly, npoly,
  1166. sampleDist, sampleMaxError,
  1167. heightSearchRadius, chf, hp,
  1168. verts, nverts, tris,
  1169. edges, samples))
  1170. {
  1171. return false;
  1172. }
  1173. // Move detail verts to world space.
  1174. for (int j = 0; j < nverts; ++j)
  1175. {
  1176. verts[j*3+0] += orig[0];
  1177. verts[j*3+1] += orig[1] + chf.ch; // Is this offset necessary?
  1178. verts[j*3+2] += orig[2];
  1179. }
  1180. // Offset poly too, will be used to flag checking.
  1181. for (int j = 0; j < npoly; ++j)
  1182. {
  1183. poly[j*3+0] += orig[0];
  1184. poly[j*3+1] += orig[1];
  1185. poly[j*3+2] += orig[2];
  1186. }
  1187. // Store detail submesh.
  1188. const int ntris = tris.size()/4;
  1189. dmesh.meshes[i*4+0] = (unsigned int)dmesh.nverts;
  1190. dmesh.meshes[i*4+1] = (unsigned int)nverts;
  1191. dmesh.meshes[i*4+2] = (unsigned int)dmesh.ntris;
  1192. dmesh.meshes[i*4+3] = (unsigned int)ntris;
  1193. // Store vertices, allocate more memory if necessary.
  1194. if (dmesh.nverts+nverts > vcap)
  1195. {
  1196. while (dmesh.nverts+nverts > vcap)
  1197. vcap += 256;
  1198. float* newv = (float*)rcAlloc(sizeof(float)*vcap*3, RC_ALLOC_PERM);
  1199. if (!newv)
  1200. {
  1201. ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'newv' (%d).", vcap*3);
  1202. return false;
  1203. }
  1204. if (dmesh.nverts)
  1205. memcpy(newv, dmesh.verts, sizeof(float)*3*dmesh.nverts);
  1206. rcFree(dmesh.verts);
  1207. dmesh.verts = newv;
  1208. }
  1209. for (int j = 0; j < nverts; ++j)
  1210. {
  1211. dmesh.verts[dmesh.nverts*3+0] = verts[j*3+0];
  1212. dmesh.verts[dmesh.nverts*3+1] = verts[j*3+1];
  1213. dmesh.verts[dmesh.nverts*3+2] = verts[j*3+2];
  1214. dmesh.nverts++;
  1215. }
  1216. // Store triangles, allocate more memory if necessary.
  1217. if (dmesh.ntris+ntris > tcap)
  1218. {
  1219. while (dmesh.ntris+ntris > tcap)
  1220. tcap += 256;
  1221. unsigned char* newt = (unsigned char*)rcAlloc(sizeof(unsigned char)*tcap*4, RC_ALLOC_PERM);
  1222. if (!newt)
  1223. {
  1224. ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'newt' (%d).", tcap*4);
  1225. return false;
  1226. }
  1227. if (dmesh.ntris)
  1228. memcpy(newt, dmesh.tris, sizeof(unsigned char)*4*dmesh.ntris);
  1229. rcFree(dmesh.tris);
  1230. dmesh.tris = newt;
  1231. }
  1232. for (int j = 0; j < ntris; ++j)
  1233. {
  1234. const int* t = &tris[j*4];
  1235. dmesh.tris[dmesh.ntris*4+0] = (unsigned char)t[0];
  1236. dmesh.tris[dmesh.ntris*4+1] = (unsigned char)t[1];
  1237. dmesh.tris[dmesh.ntris*4+2] = (unsigned char)t[2];
  1238. dmesh.tris[dmesh.ntris*4+3] = getTriFlags(&verts[t[0]*3], &verts[t[1]*3], &verts[t[2]*3], poly, npoly);
  1239. dmesh.ntris++;
  1240. }
  1241. }
  1242. return true;
  1243. }
  1244. /// @see rcAllocPolyMeshDetail, rcPolyMeshDetail
  1245. bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int nmeshes, rcPolyMeshDetail& mesh)
  1246. {
  1247. rcAssert(ctx);
  1248. rcScopedTimer timer(ctx, RC_TIMER_MERGE_POLYMESHDETAIL);
  1249. int maxVerts = 0;
  1250. int maxTris = 0;
  1251. int maxMeshes = 0;
  1252. for (int i = 0; i < nmeshes; ++i)
  1253. {
  1254. if (!meshes[i]) continue;
  1255. maxVerts += meshes[i]->nverts;
  1256. maxTris += meshes[i]->ntris;
  1257. maxMeshes += meshes[i]->nmeshes;
  1258. }
  1259. mesh.nmeshes = 0;
  1260. mesh.meshes = (unsigned int*)rcAlloc(sizeof(unsigned int)*maxMeshes*4, RC_ALLOC_PERM);
  1261. if (!mesh.meshes)
  1262. {
  1263. ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'pmdtl.meshes' (%d).", maxMeshes*4);
  1264. return false;
  1265. }
  1266. mesh.ntris = 0;
  1267. mesh.tris = (unsigned char*)rcAlloc(sizeof(unsigned char)*maxTris*4, RC_ALLOC_PERM);
  1268. if (!mesh.tris)
  1269. {
  1270. ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.tris' (%d).", maxTris*4);
  1271. return false;
  1272. }
  1273. mesh.nverts = 0;
  1274. mesh.verts = (float*)rcAlloc(sizeof(float)*maxVerts*3, RC_ALLOC_PERM);
  1275. if (!mesh.verts)
  1276. {
  1277. ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.verts' (%d).", maxVerts*3);
  1278. return false;
  1279. }
  1280. // Merge datas.
  1281. for (int i = 0; i < nmeshes; ++i)
  1282. {
  1283. rcPolyMeshDetail* dm = meshes[i];
  1284. if (!dm) continue;
  1285. for (int j = 0; j < dm->nmeshes; ++j)
  1286. {
  1287. unsigned int* dst = &mesh.meshes[mesh.nmeshes*4];
  1288. unsigned int* src = &dm->meshes[j*4];
  1289. dst[0] = (unsigned int)mesh.nverts+src[0];
  1290. dst[1] = src[1];
  1291. dst[2] = (unsigned int)mesh.ntris+src[2];
  1292. dst[3] = src[3];
  1293. mesh.nmeshes++;
  1294. }
  1295. for (int k = 0; k < dm->nverts; ++k)
  1296. {
  1297. rcVcopy(&mesh.verts[mesh.nverts*3], &dm->verts[k*3]);
  1298. mesh.nverts++;
  1299. }
  1300. for (int k = 0; k < dm->ntris; ++k)
  1301. {
  1302. mesh.tris[mesh.ntris*4+0] = dm->tris[k*4+0];
  1303. mesh.tris[mesh.ntris*4+1] = dm->tris[k*4+1];
  1304. mesh.tris[mesh.ntris*4+2] = dm->tris[k*4+2];
  1305. mesh.tris[mesh.ntris*4+3] = dm->tris[k*4+3];
  1306. mesh.ntris++;
  1307. }
  1308. }
  1309. return true;
  1310. }