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