RecastContour.cpp 30 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106
  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 <stdlib.h>
  23. #include "Recast.h"
  24. #include "RecastAlloc.h"
  25. #include "RecastAssert.h"
  26. static int getCornerHeight(int x, int y, int i, int dir,
  27. const rcCompactHeightfield& chf,
  28. bool& isBorderVertex)
  29. {
  30. const rcCompactSpan& s = chf.spans[i];
  31. int ch = (int)s.y;
  32. int dirp = (dir+1) & 0x3;
  33. unsigned int regs[4] = {0,0,0,0};
  34. // Combine region and area codes in order to prevent
  35. // border vertices which are in between two areas to be removed.
  36. regs[0] = chf.spans[i].reg | (chf.areas[i] << 16);
  37. if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
  38. {
  39. const int ax = x + rcGetDirOffsetX(dir);
  40. const int ay = y + rcGetDirOffsetY(dir);
  41. const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dir);
  42. const rcCompactSpan& as = chf.spans[ai];
  43. ch = rcMax(ch, (int)as.y);
  44. regs[1] = chf.spans[ai].reg | (chf.areas[ai] << 16);
  45. if (rcGetCon(as, dirp) != RC_NOT_CONNECTED)
  46. {
  47. const int ax2 = ax + rcGetDirOffsetX(dirp);
  48. const int ay2 = ay + rcGetDirOffsetY(dirp);
  49. const int ai2 = (int)chf.cells[ax2+ay2*chf.width].index + rcGetCon(as, dirp);
  50. const rcCompactSpan& as2 = chf.spans[ai2];
  51. ch = rcMax(ch, (int)as2.y);
  52. regs[2] = chf.spans[ai2].reg | (chf.areas[ai2] << 16);
  53. }
  54. }
  55. if (rcGetCon(s, dirp) != RC_NOT_CONNECTED)
  56. {
  57. const int ax = x + rcGetDirOffsetX(dirp);
  58. const int ay = y + rcGetDirOffsetY(dirp);
  59. const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dirp);
  60. const rcCompactSpan& as = chf.spans[ai];
  61. ch = rcMax(ch, (int)as.y);
  62. regs[3] = chf.spans[ai].reg | (chf.areas[ai] << 16);
  63. if (rcGetCon(as, dir) != RC_NOT_CONNECTED)
  64. {
  65. const int ax2 = ax + rcGetDirOffsetX(dir);
  66. const int ay2 = ay + rcGetDirOffsetY(dir);
  67. const int ai2 = (int)chf.cells[ax2+ay2*chf.width].index + rcGetCon(as, dir);
  68. const rcCompactSpan& as2 = chf.spans[ai2];
  69. ch = rcMax(ch, (int)as2.y);
  70. regs[2] = chf.spans[ai2].reg | (chf.areas[ai2] << 16);
  71. }
  72. }
  73. // Check if the vertex is special edge vertex, these vertices will be removed later.
  74. for (int j = 0; j < 4; ++j)
  75. {
  76. const int a = j;
  77. const int b = (j+1) & 0x3;
  78. const int c = (j+2) & 0x3;
  79. const int d = (j+3) & 0x3;
  80. // The vertex is a border vertex there are two same exterior cells in a row,
  81. // followed by two interior cells and none of the regions are out of bounds.
  82. const bool twoSameExts = (regs[a] & regs[b] & RC_BORDER_REG) != 0 && regs[a] == regs[b];
  83. const bool twoInts = ((regs[c] | regs[d]) & RC_BORDER_REG) == 0;
  84. const bool intsSameArea = (regs[c]>>16) == (regs[d]>>16);
  85. const bool noZeros = regs[a] != 0 && regs[b] != 0 && regs[c] != 0 && regs[d] != 0;
  86. if (twoSameExts && twoInts && intsSameArea && noZeros)
  87. {
  88. isBorderVertex = true;
  89. break;
  90. }
  91. }
  92. return ch;
  93. }
  94. static void walkContour(int x, int y, int i,
  95. rcCompactHeightfield& chf,
  96. unsigned char* flags, rcIntArray& points)
  97. {
  98. // Choose the first non-connected edge
  99. unsigned char dir = 0;
  100. while ((flags[i] & (1 << dir)) == 0)
  101. dir++;
  102. unsigned char startDir = dir;
  103. int starti = i;
  104. const unsigned char area = chf.areas[i];
  105. int iter = 0;
  106. while (++iter < 40000)
  107. {
  108. if (flags[i] & (1 << dir))
  109. {
  110. // Choose the edge corner
  111. bool isBorderVertex = false;
  112. bool isAreaBorder = false;
  113. int px = x;
  114. int py = getCornerHeight(x, y, i, dir, chf, isBorderVertex);
  115. int pz = y;
  116. switch(dir)
  117. {
  118. case 0: pz++; break;
  119. case 1: px++; pz++; break;
  120. case 2: px++; break;
  121. }
  122. int r = 0;
  123. const rcCompactSpan& s = chf.spans[i];
  124. if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
  125. {
  126. const int ax = x + rcGetDirOffsetX(dir);
  127. const int ay = y + rcGetDirOffsetY(dir);
  128. const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dir);
  129. r = (int)chf.spans[ai].reg;
  130. if (area != chf.areas[ai])
  131. isAreaBorder = true;
  132. }
  133. if (isBorderVertex)
  134. r |= RC_BORDER_VERTEX;
  135. if (isAreaBorder)
  136. r |= RC_AREA_BORDER;
  137. points.push(px);
  138. points.push(py);
  139. points.push(pz);
  140. points.push(r);
  141. flags[i] &= ~(1 << dir); // Remove visited edges
  142. dir = (dir+1) & 0x3; // Rotate CW
  143. }
  144. else
  145. {
  146. int ni = -1;
  147. const int nx = x + rcGetDirOffsetX(dir);
  148. const int ny = y + rcGetDirOffsetY(dir);
  149. const rcCompactSpan& s = chf.spans[i];
  150. if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
  151. {
  152. const rcCompactCell& nc = chf.cells[nx+ny*chf.width];
  153. ni = (int)nc.index + rcGetCon(s, dir);
  154. }
  155. if (ni == -1)
  156. {
  157. // Should not happen.
  158. return;
  159. }
  160. x = nx;
  161. y = ny;
  162. i = ni;
  163. dir = (dir+3) & 0x3; // Rotate CCW
  164. }
  165. if (starti == i && startDir == dir)
  166. {
  167. break;
  168. }
  169. }
  170. }
  171. static float distancePtSeg(const int x, const int z,
  172. const int px, const int pz,
  173. const int qx, const int qz)
  174. {
  175. float pqx = (float)(qx - px);
  176. float pqz = (float)(qz - pz);
  177. float dx = (float)(x - px);
  178. float dz = (float)(z - pz);
  179. float d = pqx*pqx + pqz*pqz;
  180. float t = pqx*dx + pqz*dz;
  181. if (d > 0)
  182. t /= d;
  183. if (t < 0)
  184. t = 0;
  185. else if (t > 1)
  186. t = 1;
  187. dx = px + t*pqx - x;
  188. dz = pz + t*pqz - z;
  189. return dx*dx + dz*dz;
  190. }
  191. static void simplifyContour(rcIntArray& points, rcIntArray& simplified,
  192. const float maxError, const int maxEdgeLen, const int buildFlags)
  193. {
  194. // Add initial points.
  195. bool hasConnections = false;
  196. for (int i = 0; i < points.size(); i += 4)
  197. {
  198. if ((points[i+3] & RC_CONTOUR_REG_MASK) != 0)
  199. {
  200. hasConnections = true;
  201. break;
  202. }
  203. }
  204. if (hasConnections)
  205. {
  206. // The contour has some portals to other regions.
  207. // Add a new point to every location where the region changes.
  208. for (int i = 0, ni = points.size()/4; i < ni; ++i)
  209. {
  210. int ii = (i+1) % ni;
  211. const bool differentRegs = (points[i*4+3] & RC_CONTOUR_REG_MASK) != (points[ii*4+3] & RC_CONTOUR_REG_MASK);
  212. const bool areaBorders = (points[i*4+3] & RC_AREA_BORDER) != (points[ii*4+3] & RC_AREA_BORDER);
  213. if (differentRegs || areaBorders)
  214. {
  215. simplified.push(points[i*4+0]);
  216. simplified.push(points[i*4+1]);
  217. simplified.push(points[i*4+2]);
  218. simplified.push(i);
  219. }
  220. }
  221. }
  222. if (simplified.size() == 0)
  223. {
  224. // If there is no connections at all,
  225. // create some initial points for the simplification process.
  226. // Find lower-left and upper-right vertices of the contour.
  227. int llx = points[0];
  228. int lly = points[1];
  229. int llz = points[2];
  230. int lli = 0;
  231. int urx = points[0];
  232. int ury = points[1];
  233. int urz = points[2];
  234. int uri = 0;
  235. for (int i = 0; i < points.size(); i += 4)
  236. {
  237. int x = points[i+0];
  238. int y = points[i+1];
  239. int z = points[i+2];
  240. if (x < llx || (x == llx && z < llz))
  241. {
  242. llx = x;
  243. lly = y;
  244. llz = z;
  245. lli = i/4;
  246. }
  247. if (x > urx || (x == urx && z > urz))
  248. {
  249. urx = x;
  250. ury = y;
  251. urz = z;
  252. uri = i/4;
  253. }
  254. }
  255. simplified.push(llx);
  256. simplified.push(lly);
  257. simplified.push(llz);
  258. simplified.push(lli);
  259. simplified.push(urx);
  260. simplified.push(ury);
  261. simplified.push(urz);
  262. simplified.push(uri);
  263. }
  264. // Add points until all raw points are within
  265. // error tolerance to the simplified shape.
  266. const int pn = points.size()/4;
  267. for (int i = 0; i < simplified.size()/4; )
  268. {
  269. int ii = (i+1) % (simplified.size()/4);
  270. int ax = simplified[i*4+0];
  271. int az = simplified[i*4+2];
  272. int ai = simplified[i*4+3];
  273. int bx = simplified[ii*4+0];
  274. int bz = simplified[ii*4+2];
  275. int bi = simplified[ii*4+3];
  276. // Find maximum deviation from the segment.
  277. float maxd = 0;
  278. int maxi = -1;
  279. int ci, cinc, endi;
  280. // Traverse the segment in lexilogical order so that the
  281. // max deviation is calculated similarly when traversing
  282. // opposite segments.
  283. if (bx > ax || (bx == ax && bz > az))
  284. {
  285. cinc = 1;
  286. ci = (ai+cinc) % pn;
  287. endi = bi;
  288. }
  289. else
  290. {
  291. cinc = pn-1;
  292. ci = (bi+cinc) % pn;
  293. endi = ai;
  294. rcSwap(ax, bx);
  295. rcSwap(az, bz);
  296. }
  297. // Tessellate only outer edges or edges between areas.
  298. if ((points[ci*4+3] & RC_CONTOUR_REG_MASK) == 0 ||
  299. (points[ci*4+3] & RC_AREA_BORDER))
  300. {
  301. while (ci != endi)
  302. {
  303. float d = distancePtSeg(points[ci*4+0], points[ci*4+2], ax, az, bx, bz);
  304. if (d > maxd)
  305. {
  306. maxd = d;
  307. maxi = ci;
  308. }
  309. ci = (ci+cinc) % pn;
  310. }
  311. }
  312. // If the max deviation is larger than accepted error,
  313. // add new point, else continue to next segment.
  314. if (maxi != -1 && maxd > (maxError*maxError))
  315. {
  316. // Add space for the new point.
  317. simplified.resize(simplified.size()+4);
  318. const int n = simplified.size()/4;
  319. for (int j = n-1; j > i; --j)
  320. {
  321. simplified[j*4+0] = simplified[(j-1)*4+0];
  322. simplified[j*4+1] = simplified[(j-1)*4+1];
  323. simplified[j*4+2] = simplified[(j-1)*4+2];
  324. simplified[j*4+3] = simplified[(j-1)*4+3];
  325. }
  326. // Add the point.
  327. simplified[(i+1)*4+0] = points[maxi*4+0];
  328. simplified[(i+1)*4+1] = points[maxi*4+1];
  329. simplified[(i+1)*4+2] = points[maxi*4+2];
  330. simplified[(i+1)*4+3] = maxi;
  331. }
  332. else
  333. {
  334. ++i;
  335. }
  336. }
  337. // Split too long edges.
  338. if (maxEdgeLen > 0 && (buildFlags & (RC_CONTOUR_TESS_WALL_EDGES|RC_CONTOUR_TESS_AREA_EDGES)) != 0)
  339. {
  340. for (int i = 0; i < simplified.size()/4; )
  341. {
  342. const int ii = (i+1) % (simplified.size()/4);
  343. const int ax = simplified[i*4+0];
  344. const int az = simplified[i*4+2];
  345. const int ai = simplified[i*4+3];
  346. const int bx = simplified[ii*4+0];
  347. const int bz = simplified[ii*4+2];
  348. const int bi = simplified[ii*4+3];
  349. // Find maximum deviation from the segment.
  350. int maxi = -1;
  351. int ci = (ai+1) % pn;
  352. // Tessellate only outer edges or edges between areas.
  353. bool tess = false;
  354. // Wall edges.
  355. if ((buildFlags & RC_CONTOUR_TESS_WALL_EDGES) && (points[ci*4+3] & RC_CONTOUR_REG_MASK) == 0)
  356. tess = true;
  357. // Edges between areas.
  358. if ((buildFlags & RC_CONTOUR_TESS_AREA_EDGES) && (points[ci*4+3] & RC_AREA_BORDER))
  359. tess = true;
  360. if (tess)
  361. {
  362. int dx = bx - ax;
  363. int dz = bz - az;
  364. if (dx*dx + dz*dz > maxEdgeLen*maxEdgeLen)
  365. {
  366. // Round based on the segments in lexilogical order so that the
  367. // max tesselation is consistent regardles in which direction
  368. // segments are traversed.
  369. const int n = bi < ai ? (bi+pn - ai) : (bi - ai);
  370. if (n > 1)
  371. {
  372. if (bx > ax || (bx == ax && bz > az))
  373. maxi = (ai + n/2) % pn;
  374. else
  375. maxi = (ai + (n+1)/2) % pn;
  376. }
  377. }
  378. }
  379. // If the max deviation is larger than accepted error,
  380. // add new point, else continue to next segment.
  381. if (maxi != -1)
  382. {
  383. // Add space for the new point.
  384. simplified.resize(simplified.size()+4);
  385. const int n = simplified.size()/4;
  386. for (int j = n-1; j > i; --j)
  387. {
  388. simplified[j*4+0] = simplified[(j-1)*4+0];
  389. simplified[j*4+1] = simplified[(j-1)*4+1];
  390. simplified[j*4+2] = simplified[(j-1)*4+2];
  391. simplified[j*4+3] = simplified[(j-1)*4+3];
  392. }
  393. // Add the point.
  394. simplified[(i+1)*4+0] = points[maxi*4+0];
  395. simplified[(i+1)*4+1] = points[maxi*4+1];
  396. simplified[(i+1)*4+2] = points[maxi*4+2];
  397. simplified[(i+1)*4+3] = maxi;
  398. }
  399. else
  400. {
  401. ++i;
  402. }
  403. }
  404. }
  405. for (int i = 0; i < simplified.size()/4; ++i)
  406. {
  407. // The edge vertex flag is take from the current raw point,
  408. // and the neighbour region is take from the next raw point.
  409. const int ai = (simplified[i*4+3]+1) % pn;
  410. const int bi = simplified[i*4+3];
  411. simplified[i*4+3] = (points[ai*4+3] & (RC_CONTOUR_REG_MASK|RC_AREA_BORDER)) | (points[bi*4+3] & RC_BORDER_VERTEX);
  412. }
  413. }
  414. static int calcAreaOfPolygon2D(const int* verts, const int nverts)
  415. {
  416. int area = 0;
  417. for (int i = 0, j = nverts-1; i < nverts; j=i++)
  418. {
  419. const int* vi = &verts[i*4];
  420. const int* vj = &verts[j*4];
  421. area += vi[0] * vj[2] - vj[0] * vi[2];
  422. }
  423. return (area+1) / 2;
  424. }
  425. // TODO: these are the same as in RecastMesh.cpp, consider using the same.
  426. // Last time I checked the if version got compiled using cmov, which was a lot faster than module (with idiv).
  427. inline int prev(int i, int n) { return i-1 >= 0 ? i-1 : n-1; }
  428. inline int next(int i, int n) { return i+1 < n ? i+1 : 0; }
  429. inline int area2(const int* a, const int* b, const int* c)
  430. {
  431. return (b[0] - a[0]) * (c[2] - a[2]) - (c[0] - a[0]) * (b[2] - a[2]);
  432. }
  433. // Exclusive or: true iff exactly one argument is true.
  434. // The arguments are negated to ensure that they are 0/1
  435. // values. Then the bitwise Xor operator may apply.
  436. // (This idea is due to Michael Baldwin.)
  437. inline bool xorb(bool x, bool y)
  438. {
  439. return !x ^ !y;
  440. }
  441. // Returns true iff c is strictly to the left of the directed
  442. // line through a to b.
  443. inline bool left(const int* a, const int* b, const int* c)
  444. {
  445. return area2(a, b, c) < 0;
  446. }
  447. inline bool leftOn(const int* a, const int* b, const int* c)
  448. {
  449. return area2(a, b, c) <= 0;
  450. }
  451. inline bool collinear(const int* a, const int* b, const int* c)
  452. {
  453. return area2(a, b, c) == 0;
  454. }
  455. // Returns true iff ab properly intersects cd: they share
  456. // a point interior to both segments. The properness of the
  457. // intersection is ensured by using strict leftness.
  458. static bool intersectProp(const int* a, const int* b, const int* c, const int* d)
  459. {
  460. // Eliminate improper cases.
  461. if (collinear(a,b,c) || collinear(a,b,d) ||
  462. collinear(c,d,a) || collinear(c,d,b))
  463. return false;
  464. return xorb(left(a,b,c), left(a,b,d)) && xorb(left(c,d,a), left(c,d,b));
  465. }
  466. // Returns T iff (a,b,c) are collinear and point c lies
  467. // on the closed segement ab.
  468. static bool between(const int* a, const int* b, const int* c)
  469. {
  470. if (!collinear(a, b, c))
  471. return false;
  472. // If ab not vertical, check betweenness on x; else on y.
  473. if (a[0] != b[0])
  474. return ((a[0] <= c[0]) && (c[0] <= b[0])) || ((a[0] >= c[0]) && (c[0] >= b[0]));
  475. else
  476. return ((a[2] <= c[2]) && (c[2] <= b[2])) || ((a[2] >= c[2]) && (c[2] >= b[2]));
  477. }
  478. // Returns true iff segments ab and cd intersect, properly or improperly.
  479. static bool intersect(const int* a, const int* b, const int* c, const int* d)
  480. {
  481. if (intersectProp(a, b, c, d))
  482. return true;
  483. else if (between(a, b, c) || between(a, b, d) ||
  484. between(c, d, a) || between(c, d, b))
  485. return true;
  486. else
  487. return false;
  488. }
  489. static bool vequal(const int* a, const int* b)
  490. {
  491. return a[0] == b[0] && a[2] == b[2];
  492. }
  493. static bool intersectSegCountour(const int* d0, const int* d1, int i, int n, const int* verts)
  494. {
  495. // For each edge (k,k+1) of P
  496. for (int k = 0; k < n; k++)
  497. {
  498. int k1 = next(k, n);
  499. // Skip edges incident to i.
  500. if (i == k || i == k1)
  501. continue;
  502. const int* p0 = &verts[k * 4];
  503. const int* p1 = &verts[k1 * 4];
  504. if (vequal(d0, p0) || vequal(d1, p0) || vequal(d0, p1) || vequal(d1, p1))
  505. continue;
  506. if (intersect(d0, d1, p0, p1))
  507. return true;
  508. }
  509. return false;
  510. }
  511. static bool inCone(int i, int n, const int* verts, const int* pj)
  512. {
  513. const int* pi = &verts[i * 4];
  514. const int* pi1 = &verts[next(i, n) * 4];
  515. const int* pin1 = &verts[prev(i, n) * 4];
  516. // If P[i] is a convex vertex [ i+1 left or on (i-1,i) ].
  517. if (leftOn(pin1, pi, pi1))
  518. return left(pi, pj, pin1) && left(pj, pi, pi1);
  519. // Assume (i-1,i,i+1) not collinear.
  520. // else P[i] is reflex.
  521. return !(leftOn(pi, pj, pi1) && leftOn(pj, pi, pin1));
  522. }
  523. static void removeDegenerateSegments(rcIntArray& simplified)
  524. {
  525. // Remove adjacent vertices which are equal on xz-plane,
  526. // or else the triangulator will get confused.
  527. int npts = simplified.size()/4;
  528. for (int i = 0; i < npts; ++i)
  529. {
  530. int ni = next(i, npts);
  531. if (vequal(&simplified[i*4], &simplified[ni*4]))
  532. {
  533. // Degenerate segment, remove.
  534. for (int j = i; j < simplified.size()/4-1; ++j)
  535. {
  536. simplified[j*4+0] = simplified[(j+1)*4+0];
  537. simplified[j*4+1] = simplified[(j+1)*4+1];
  538. simplified[j*4+2] = simplified[(j+1)*4+2];
  539. simplified[j*4+3] = simplified[(j+1)*4+3];
  540. }
  541. simplified.resize(simplified.size()-4);
  542. npts--;
  543. }
  544. }
  545. }
  546. static bool mergeContours(rcContour& ca, rcContour& cb, int ia, int ib)
  547. {
  548. const int maxVerts = ca.nverts + cb.nverts + 2;
  549. int* verts = (int*)rcAlloc(sizeof(int)*maxVerts*4, RC_ALLOC_PERM);
  550. if (!verts)
  551. return false;
  552. int nv = 0;
  553. // Copy contour A.
  554. for (int i = 0; i <= ca.nverts; ++i)
  555. {
  556. int* dst = &verts[nv*4];
  557. const int* src = &ca.verts[((ia+i)%ca.nverts)*4];
  558. dst[0] = src[0];
  559. dst[1] = src[1];
  560. dst[2] = src[2];
  561. dst[3] = src[3];
  562. nv++;
  563. }
  564. // Copy contour B
  565. for (int i = 0; i <= cb.nverts; ++i)
  566. {
  567. int* dst = &verts[nv*4];
  568. const int* src = &cb.verts[((ib+i)%cb.nverts)*4];
  569. dst[0] = src[0];
  570. dst[1] = src[1];
  571. dst[2] = src[2];
  572. dst[3] = src[3];
  573. nv++;
  574. }
  575. rcFree(ca.verts);
  576. ca.verts = verts;
  577. ca.nverts = nv;
  578. rcFree(cb.verts);
  579. cb.verts = 0;
  580. cb.nverts = 0;
  581. return true;
  582. }
  583. struct rcContourHole
  584. {
  585. rcContour* contour;
  586. int minx, minz, leftmost;
  587. };
  588. struct rcContourRegion
  589. {
  590. rcContour* outline;
  591. rcContourHole* holes;
  592. int nholes;
  593. };
  594. struct rcPotentialDiagonal
  595. {
  596. int vert;
  597. int dist;
  598. };
  599. // Finds the lowest leftmost vertex of a contour.
  600. static void findLeftMostVertex(rcContour* contour, int* minx, int* minz, int* leftmost)
  601. {
  602. *minx = contour->verts[0];
  603. *minz = contour->verts[2];
  604. *leftmost = 0;
  605. for (int i = 1; i < contour->nverts; i++)
  606. {
  607. const int x = contour->verts[i*4+0];
  608. const int z = contour->verts[i*4+2];
  609. if (x < *minx || (x == *minx && z < *minz))
  610. {
  611. *minx = x;
  612. *minz = z;
  613. *leftmost = i;
  614. }
  615. }
  616. }
  617. static int compareHoles(const void* va, const void* vb)
  618. {
  619. const rcContourHole* a = (const rcContourHole*)va;
  620. const rcContourHole* b = (const rcContourHole*)vb;
  621. if (a->minx == b->minx)
  622. {
  623. if (a->minz < b->minz)
  624. return -1;
  625. if (a->minz > b->minz)
  626. return 1;
  627. }
  628. else
  629. {
  630. if (a->minx < b->minx)
  631. return -1;
  632. if (a->minx > b->minx)
  633. return 1;
  634. }
  635. return 0;
  636. }
  637. static int compareDiagDist(const void* va, const void* vb)
  638. {
  639. const rcPotentialDiagonal* a = (const rcPotentialDiagonal*)va;
  640. const rcPotentialDiagonal* b = (const rcPotentialDiagonal*)vb;
  641. if (a->dist < b->dist)
  642. return -1;
  643. if (a->dist > b->dist)
  644. return 1;
  645. return 0;
  646. }
  647. static void mergeRegionHoles(rcContext* ctx, rcContourRegion& region)
  648. {
  649. // Sort holes from left to right.
  650. for (int i = 0; i < region.nholes; i++)
  651. findLeftMostVertex(region.holes[i].contour, &region.holes[i].minx, &region.holes[i].minz, &region.holes[i].leftmost);
  652. qsort(region.holes, region.nholes, sizeof(rcContourHole), compareHoles);
  653. int maxVerts = region.outline->nverts;
  654. for (int i = 0; i < region.nholes; i++)
  655. maxVerts += region.holes[i].contour->nverts;
  656. rcScopedDelete<rcPotentialDiagonal> diags((rcPotentialDiagonal*)rcAlloc(sizeof(rcPotentialDiagonal)*maxVerts, RC_ALLOC_TEMP));
  657. if (!diags)
  658. {
  659. ctx->log(RC_LOG_WARNING, "mergeRegionHoles: Failed to allocated diags %d.", maxVerts);
  660. return;
  661. }
  662. rcContour* outline = region.outline;
  663. // Merge holes into the outline one by one.
  664. for (int i = 0; i < region.nholes; i++)
  665. {
  666. rcContour* hole = region.holes[i].contour;
  667. int index = -1;
  668. int bestVertex = region.holes[i].leftmost;
  669. for (int iter = 0; iter < hole->nverts; iter++)
  670. {
  671. // Find potential diagonals.
  672. // The 'best' vertex must be in the cone described by 3 cosequtive vertices of the outline.
  673. // ..o j-1
  674. // |
  675. // | * best
  676. // |
  677. // j o-----o j+1
  678. // :
  679. int ndiags = 0;
  680. const int* corner = &hole->verts[bestVertex*4];
  681. for (int j = 0; j < outline->nverts; j++)
  682. {
  683. if (inCone(j, outline->nverts, outline->verts, corner))
  684. {
  685. int dx = outline->verts[j*4+0] - corner[0];
  686. int dz = outline->verts[j*4+2] - corner[2];
  687. diags[ndiags].vert = j;
  688. diags[ndiags].dist = dx*dx + dz*dz;
  689. ndiags++;
  690. }
  691. }
  692. // Sort potential diagonals by distance, we want to make the connection as short as possible.
  693. qsort(diags, ndiags, sizeof(rcPotentialDiagonal), compareDiagDist);
  694. // Find a diagonal that is not intersecting the outline not the remaining holes.
  695. index = -1;
  696. for (int j = 0; j < ndiags; j++)
  697. {
  698. const int* pt = &outline->verts[diags[j].vert*4];
  699. bool intersect = intersectSegCountour(pt, corner, diags[i].vert, outline->nverts, outline->verts);
  700. for (int k = i; k < region.nholes && !intersect; k++)
  701. intersect |= intersectSegCountour(pt, corner, -1, region.holes[k].contour->nverts, region.holes[k].contour->verts);
  702. if (!intersect)
  703. {
  704. index = diags[j].vert;
  705. break;
  706. }
  707. }
  708. // If found non-intersecting diagonal, stop looking.
  709. if (index != -1)
  710. break;
  711. // All the potential diagonals for the current vertex were intersecting, try next vertex.
  712. bestVertex = (bestVertex + 1) % hole->nverts;
  713. }
  714. if (index == -1)
  715. {
  716. ctx->log(RC_LOG_WARNING, "mergeHoles: Failed to find merge points for %p and %p.", region.outline, hole);
  717. continue;
  718. }
  719. if (!mergeContours(*region.outline, *hole, index, bestVertex))
  720. {
  721. ctx->log(RC_LOG_WARNING, "mergeHoles: Failed to merge contours %p and %p.", region.outline, hole);
  722. continue;
  723. }
  724. }
  725. }
  726. /// @par
  727. ///
  728. /// The raw contours will match the region outlines exactly. The @p maxError and @p maxEdgeLen
  729. /// parameters control how closely the simplified contours will match the raw contours.
  730. ///
  731. /// Simplified contours are generated such that the vertices for portals between areas match up.
  732. /// (They are considered mandatory vertices.)
  733. ///
  734. /// Setting @p maxEdgeLength to zero will disabled the edge length feature.
  735. ///
  736. /// See the #rcConfig documentation for more information on the configuration parameters.
  737. ///
  738. /// @see rcAllocContourSet, rcCompactHeightfield, rcContourSet, rcConfig
  739. bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf,
  740. const float maxError, const int maxEdgeLen,
  741. rcContourSet& cset, const int buildFlags)
  742. {
  743. rcAssert(ctx);
  744. const int w = chf.width;
  745. const int h = chf.height;
  746. const int borderSize = chf.borderSize;
  747. rcScopedTimer timer(ctx, RC_TIMER_BUILD_CONTOURS);
  748. rcVcopy(cset.bmin, chf.bmin);
  749. rcVcopy(cset.bmax, chf.bmax);
  750. if (borderSize > 0)
  751. {
  752. // If the heightfield was build with bordersize, remove the offset.
  753. const float pad = borderSize*chf.cs;
  754. cset.bmin[0] += pad;
  755. cset.bmin[2] += pad;
  756. cset.bmax[0] -= pad;
  757. cset.bmax[2] -= pad;
  758. }
  759. cset.cs = chf.cs;
  760. cset.ch = chf.ch;
  761. cset.width = chf.width - chf.borderSize*2;
  762. cset.height = chf.height - chf.borderSize*2;
  763. cset.borderSize = chf.borderSize;
  764. cset.maxError = maxError;
  765. int maxContours = rcMax((int)chf.maxRegions, 8);
  766. cset.conts = (rcContour*)rcAlloc(sizeof(rcContour)*maxContours, RC_ALLOC_PERM);
  767. if (!cset.conts)
  768. return false;
  769. cset.nconts = 0;
  770. rcScopedDelete<unsigned char> flags((unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP));
  771. if (!flags)
  772. {
  773. ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'flags' (%d).", chf.spanCount);
  774. return false;
  775. }
  776. ctx->startTimer(RC_TIMER_BUILD_CONTOURS_TRACE);
  777. // Mark boundaries.
  778. for (int y = 0; y < h; ++y)
  779. {
  780. for (int x = 0; x < w; ++x)
  781. {
  782. const rcCompactCell& c = chf.cells[x+y*w];
  783. for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
  784. {
  785. unsigned char res = 0;
  786. const rcCompactSpan& s = chf.spans[i];
  787. if (!chf.spans[i].reg || (chf.spans[i].reg & RC_BORDER_REG))
  788. {
  789. flags[i] = 0;
  790. continue;
  791. }
  792. for (int dir = 0; dir < 4; ++dir)
  793. {
  794. unsigned short r = 0;
  795. if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
  796. {
  797. const int ax = x + rcGetDirOffsetX(dir);
  798. const int ay = y + rcGetDirOffsetY(dir);
  799. const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);
  800. r = chf.spans[ai].reg;
  801. }
  802. if (r == chf.spans[i].reg)
  803. res |= (1 << dir);
  804. }
  805. flags[i] = res ^ 0xf; // Inverse, mark non connected edges.
  806. }
  807. }
  808. }
  809. ctx->stopTimer(RC_TIMER_BUILD_CONTOURS_TRACE);
  810. rcIntArray verts(256);
  811. rcIntArray simplified(64);
  812. for (int y = 0; y < h; ++y)
  813. {
  814. for (int x = 0; x < w; ++x)
  815. {
  816. const rcCompactCell& c = chf.cells[x+y*w];
  817. for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
  818. {
  819. if (flags[i] == 0 || flags[i] == 0xf)
  820. {
  821. flags[i] = 0;
  822. continue;
  823. }
  824. const unsigned short reg = chf.spans[i].reg;
  825. if (!reg || (reg & RC_BORDER_REG))
  826. continue;
  827. const unsigned char area = chf.areas[i];
  828. verts.resize(0);
  829. simplified.resize(0);
  830. ctx->startTimer(RC_TIMER_BUILD_CONTOURS_TRACE);
  831. walkContour(x, y, i, chf, flags, verts);
  832. ctx->stopTimer(RC_TIMER_BUILD_CONTOURS_TRACE);
  833. ctx->startTimer(RC_TIMER_BUILD_CONTOURS_SIMPLIFY);
  834. simplifyContour(verts, simplified, maxError, maxEdgeLen, buildFlags);
  835. removeDegenerateSegments(simplified);
  836. ctx->stopTimer(RC_TIMER_BUILD_CONTOURS_SIMPLIFY);
  837. // Store region->contour remap info.
  838. // Create contour.
  839. if (simplified.size()/4 >= 3)
  840. {
  841. if (cset.nconts >= maxContours)
  842. {
  843. // Allocate more contours.
  844. // This happens when a region has holes.
  845. const int oldMax = maxContours;
  846. maxContours *= 2;
  847. rcContour* newConts = (rcContour*)rcAlloc(sizeof(rcContour)*maxContours, RC_ALLOC_PERM);
  848. for (int j = 0; j < cset.nconts; ++j)
  849. {
  850. newConts[j] = cset.conts[j];
  851. // Reset source pointers to prevent data deletion.
  852. cset.conts[j].verts = 0;
  853. cset.conts[j].rverts = 0;
  854. }
  855. rcFree(cset.conts);
  856. cset.conts = newConts;
  857. ctx->log(RC_LOG_WARNING, "rcBuildContours: Expanding max contours from %d to %d.", oldMax, maxContours);
  858. }
  859. rcContour* cont = &cset.conts[cset.nconts++];
  860. cont->nverts = simplified.size()/4;
  861. cont->verts = (int*)rcAlloc(sizeof(int)*cont->nverts*4, RC_ALLOC_PERM);
  862. if (!cont->verts)
  863. {
  864. ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'verts' (%d).", cont->nverts);
  865. return false;
  866. }
  867. memcpy(cont->verts, &simplified[0], sizeof(int)*cont->nverts*4);
  868. if (borderSize > 0)
  869. {
  870. // If the heightfield was build with bordersize, remove the offset.
  871. for (int j = 0; j < cont->nverts; ++j)
  872. {
  873. int* v = &cont->verts[j*4];
  874. v[0] -= borderSize;
  875. v[2] -= borderSize;
  876. }
  877. }
  878. cont->nrverts = verts.size()/4;
  879. cont->rverts = (int*)rcAlloc(sizeof(int)*cont->nrverts*4, RC_ALLOC_PERM);
  880. if (!cont->rverts)
  881. {
  882. ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'rverts' (%d).", cont->nrverts);
  883. return false;
  884. }
  885. memcpy(cont->rverts, &verts[0], sizeof(int)*cont->nrverts*4);
  886. if (borderSize > 0)
  887. {
  888. // If the heightfield was build with bordersize, remove the offset.
  889. for (int j = 0; j < cont->nrverts; ++j)
  890. {
  891. int* v = &cont->rverts[j*4];
  892. v[0] -= borderSize;
  893. v[2] -= borderSize;
  894. }
  895. }
  896. cont->reg = reg;
  897. cont->area = area;
  898. }
  899. }
  900. }
  901. }
  902. // Merge holes if needed.
  903. if (cset.nconts > 0)
  904. {
  905. // Calculate winding of all polygons.
  906. rcScopedDelete<char> winding((char*)rcAlloc(sizeof(char)*cset.nconts, RC_ALLOC_TEMP));
  907. if (!winding)
  908. {
  909. ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'hole' (%d).", cset.nconts);
  910. return false;
  911. }
  912. int nholes = 0;
  913. for (int i = 0; i < cset.nconts; ++i)
  914. {
  915. rcContour& cont = cset.conts[i];
  916. // If the contour is wound backwards, it is a hole.
  917. winding[i] = calcAreaOfPolygon2D(cont.verts, cont.nverts) < 0 ? -1 : 1;
  918. if (winding[i] < 0)
  919. nholes++;
  920. }
  921. if (nholes > 0)
  922. {
  923. // Collect outline contour and holes contours per region.
  924. // We assume that there is one outline and multiple holes.
  925. const int nregions = chf.maxRegions+1;
  926. rcScopedDelete<rcContourRegion> regions((rcContourRegion*)rcAlloc(sizeof(rcContourRegion)*nregions, RC_ALLOC_TEMP));
  927. if (!regions)
  928. {
  929. ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'regions' (%d).", nregions);
  930. return false;
  931. }
  932. memset(regions, 0, sizeof(rcContourRegion)*nregions);
  933. rcScopedDelete<rcContourHole> holes((rcContourHole*)rcAlloc(sizeof(rcContourHole)*cset.nconts, RC_ALLOC_TEMP));
  934. if (!holes)
  935. {
  936. ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'holes' (%d).", cset.nconts);
  937. return false;
  938. }
  939. memset(holes, 0, sizeof(rcContourHole)*cset.nconts);
  940. for (int i = 0; i < cset.nconts; ++i)
  941. {
  942. rcContour& cont = cset.conts[i];
  943. // Positively would contours are outlines, negative holes.
  944. if (winding[i] > 0)
  945. {
  946. if (regions[cont.reg].outline)
  947. ctx->log(RC_LOG_ERROR, "rcBuildContours: Multiple outlines for region %d.", cont.reg);
  948. regions[cont.reg].outline = &cont;
  949. }
  950. else
  951. {
  952. regions[cont.reg].nholes++;
  953. }
  954. }
  955. int index = 0;
  956. for (int i = 0; i < nregions; i++)
  957. {
  958. if (regions[i].nholes > 0)
  959. {
  960. regions[i].holes = &holes[index];
  961. index += regions[i].nholes;
  962. regions[i].nholes = 0;
  963. }
  964. }
  965. for (int i = 0; i < cset.nconts; ++i)
  966. {
  967. rcContour& cont = cset.conts[i];
  968. rcContourRegion& reg = regions[cont.reg];
  969. if (winding[i] < 0)
  970. reg.holes[reg.nholes++].contour = &cont;
  971. }
  972. // Finally merge each regions holes into the outline.
  973. for (int i = 0; i < nregions; i++)
  974. {
  975. rcContourRegion& reg = regions[i];
  976. if (!reg.nholes) continue;
  977. if (reg.outline)
  978. {
  979. mergeRegionHoles(ctx, reg);
  980. }
  981. else
  982. {
  983. // The region does not have an outline.
  984. // This can happen if the contour becaomes selfoverlapping because of
  985. // too aggressive simplification settings.
  986. ctx->log(RC_LOG_ERROR, "rcBuildContours: Bad outline for region %d, contour simplification is likely too aggressive.", i);
  987. }
  988. }
  989. }
  990. }
  991. return true;
  992. }