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
26struct rcEdge
27{
28 unsigned short vert[2];
29 unsigned short polyEdge[2];
30 unsigned short poly[2];
31};
32
33static 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
125static const int VERTEX_BUCKET_COUNT = (1<<12);
126
127inline 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
136static 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).
163inline int prev(int i, int n) { return i-1 >= 0 ? i-1 : n-1; }
164inline int next(int i, int n) { return i+1 < n ? i+1 : 0; }
165
166inline 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.)
175inline 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.
182inline bool left(const int* a, const int* b, const int* c)
183{
184 return area2(a, b, c) < 0;
185}
186
187inline bool leftOn(const int* a, const int* b, const int* c)
188{
189 return area2(a, b, c) <= 0;
190}
191
192inline 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.
200static 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.
212static 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.
224static 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
235static 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*.
242static 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.
269static 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.
286static 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
292static 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
317static 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
332static 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
338static 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
452static 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
460inline 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
466static 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
530static 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
550static 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
557static void pushBack(int v, int* arr, int& an)
558{
559 arr[an] = v;
560 an++;
561}
562
563static 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
663static 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
989bool 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
1308bool 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
1486bool 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