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 | |
28 | static 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 | |
103 | static 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 | |
186 | static 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 | |
209 | static 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 | |
453 | static 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). |
467 | inline int prev(int i, int n) { return i-1 >= 0 ? i-1 : n-1; } |
468 | inline int next(int i, int n) { return i+1 < n ? i+1 : 0; } |
469 | |
470 | inline 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.) |
479 | inline 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. |
486 | inline bool left(const int* a, const int* b, const int* c) |
487 | { |
488 | return area2(a, b, c) < 0; |
489 | } |
490 | |
491 | inline bool leftOn(const int* a, const int* b, const int* c) |
492 | { |
493 | return area2(a, b, c) <= 0; |
494 | } |
495 | |
496 | inline 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. |
504 | static 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. |
516 | static 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. |
528 | static 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 | |
539 | static bool vequal(const int* a, const int* b) |
540 | { |
541 | return a[0] == b[0] && a[2] == b[2]; |
542 | } |
543 | |
544 | static 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 | |
564 | static 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 | |
579 | static 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 | |
605 | static 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 | |
649 | struct rcContourHole |
650 | { |
651 | rcContour* contour; |
652 | int minx, minz, leftmost; |
653 | }; |
654 | |
655 | struct rcContourRegion |
656 | { |
657 | rcContour* outline; |
658 | rcContourHole* holes; |
659 | int nholes; |
660 | }; |
661 | |
662 | struct rcPotentialDiagonal |
663 | { |
664 | int vert; |
665 | int dist; |
666 | }; |
667 | |
668 | // Finds the lowest leftmost vertex of a contour. |
669 | static 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 | |
687 | static 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 | |
709 | static 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 | |
721 | static 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, ®ion.holes[i].minx, ®ion.holes[i].minz, ®ion.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 |
823 | bool 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 | |