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