ef37d569a175f9161e53367b1e01bb0a2e27b14e
[blender.git] / extern / recastnavigation / Recast / Source / RecastMesh.cpp
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 #define _USE_MATH_DEFINES
20 #include <math.h>
21 #include <string.h>
22 #include <stdio.h>
23 #include "Recast.h"
24 #include "RecastAlloc.h"
25 #include "RecastAssert.h"
26
27 struct rcEdge
28 {
29         unsigned short vert[2];
30         unsigned short polyEdge[2];
31         unsigned short poly[2];
32 };
33
34 /*static*/ bool buildMeshAdjacency(unsigned short* polys, const int npolys,
35                                                            const int nverts, const int vertsPerPoly)
36 {
37         // Based on code by Eric Lengyel from:
38         // http://www.terathon.com/code/edges.php
39         
40         int maxEdgeCount = npolys*vertsPerPoly;
41         unsigned short* firstEdge = (unsigned short*)rcAlloc(sizeof(unsigned short)*(nverts + maxEdgeCount), RC_ALLOC_TEMP);
42         if (!firstEdge)
43                 return false;
44         unsigned short* nextEdge = firstEdge + nverts;
45         int edgeCount = 0;
46         
47         rcEdge* edges = (rcEdge*)rcAlloc(sizeof(rcEdge)*maxEdgeCount, RC_ALLOC_TEMP);
48         if (!edges)
49         {
50                 rcFree(firstEdge);
51                 return false;
52         }
53         
54         for (int i = 0; i < nverts; i++)
55                 firstEdge[i] = RC_MESH_NULL_IDX;
56         
57         for (int i = 0; i < npolys; ++i)
58         {
59                 unsigned short* t = &polys[i*vertsPerPoly*2];
60                 for (int j = 0; j < vertsPerPoly; ++j)
61                 {
62                         if (t[j] == RC_MESH_NULL_IDX) break;
63                         unsigned short v0 = t[j];
64                         unsigned short v1 = (j+1 >= vertsPerPoly || t[j+1] == RC_MESH_NULL_IDX) ? t[0] : t[j+1];
65                         if (v0 < v1)
66                         {
67                                 rcEdge& edge = edges[edgeCount];
68                                 edge.vert[0] = v0;
69                                 edge.vert[1] = v1;
70                                 edge.poly[0] = (unsigned short)i;
71                                 edge.polyEdge[0] = (unsigned short)j;
72                                 edge.poly[1] = (unsigned short)i;
73                                 edge.polyEdge[1] = 0;
74                                 // Insert edge
75                                 nextEdge[edgeCount] = firstEdge[v0];
76                                 firstEdge[v0] = (unsigned short)edgeCount;
77                                 edgeCount++;
78                         }
79                 }
80         }
81         
82         for (int i = 0; i < npolys; ++i)
83         {
84                 unsigned short* t = &polys[i*vertsPerPoly*2];
85                 for (int j = 0; j < vertsPerPoly; ++j)
86                 {
87                         if (t[j] == RC_MESH_NULL_IDX) break;
88                         unsigned short v0 = t[j];
89                         unsigned short v1 = (j+1 >= vertsPerPoly || t[j+1] == RC_MESH_NULL_IDX) ? t[0] : t[j+1];
90                         if (v0 > v1)
91                         {
92                                 for (unsigned short e = firstEdge[v1]; e != RC_MESH_NULL_IDX; e = nextEdge[e])
93                                 {
94                                         rcEdge& edge = edges[e];
95                                         if (edge.vert[1] == v0 && edge.poly[0] == edge.poly[1])
96                                         {
97                                                 edge.poly[1] = (unsigned short)i;
98                                                 edge.polyEdge[1] = (unsigned short)j;
99                                                 break;
100                                         }
101                                 }
102                         }
103                 }
104         }
105         
106         // Store adjacency
107         for (int i = 0; i < edgeCount; ++i)
108         {
109                 const rcEdge& e = edges[i];
110                 if (e.poly[0] != e.poly[1])
111                 {
112                         unsigned short* p0 = &polys[e.poly[0]*vertsPerPoly*2];
113                         unsigned short* p1 = &polys[e.poly[1]*vertsPerPoly*2];
114                         p0[vertsPerPoly + e.polyEdge[0]] = e.poly[1];
115                         p1[vertsPerPoly + e.polyEdge[1]] = e.poly[0];
116                 }
117         }
118         
119         rcFree(firstEdge);
120         rcFree(edges);
121         
122         return true;
123 }
124
125
126 static const int VERTEX_BUCKET_COUNT = (1<<12);
127
128 inline int computeVertexHash(int x, int y, int z)
129 {
130         const unsigned int h1 = 0x8da6b343; // Large multiplicative constants;
131         const unsigned int h2 = 0xd8163841; // here arbitrarily chosen primes
132         const unsigned int h3 = 0xcb1ab31f;
133         unsigned int n = h1 * x + h2 * y + h3 * z;
134         return (int)(n & (VERTEX_BUCKET_COUNT-1));
135 }
136
137 static unsigned short addVertex(unsigned short x, unsigned short y, unsigned short z,
138                                                                 unsigned short* verts, int* firstVert, int* nextVert, int& nv)
139 {
140         int bucket = computeVertexHash(x, 0, z);
141         int i = firstVert[bucket];
142         
143         while (i != -1)
144         {
145                 const unsigned short* v = &verts[i*3];
146                 if (v[0] == x && (rcAbs(v[1] - y) <= 2) && v[2] == z)
147                         return (unsigned short)i;
148                 i = nextVert[i]; // next
149         }
150         
151         // Could not find, create new.
152         i = nv; nv++;
153         unsigned short* v = &verts[i*3];
154         v[0] = x;
155         v[1] = y;
156         v[2] = z;
157         nextVert[i] = firstVert[bucket];
158         firstVert[bucket] = i;
159         
160         return (unsigned short)i;
161 }
162
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 static int triangulate(int n, const int* verts, int* indices, int* tris)
292 {
293         int ntris = 0;
294         int* dst = tris;
295         
296         // The last bit of the index is used to indicate if the vertex can be removed.
297         for (int i = 0; i < n; i++)
298         {
299                 int i1 = next(i, n);
300                 int i2 = next(i1, n);
301                 if (diagonal(i, i2, n, verts, indices))
302                         indices[i1] |= 0x80000000;
303         }
304         
305         while (n > 3)
306         {
307                 int minLen = -1;
308                 int mini = -1;
309                 for (int i = 0; i < n; i++)
310                 {
311                         int i1 = next(i, n);
312                         if (indices[i1] & 0x80000000)
313                         {
314                                 const int* p0 = &verts[(indices[i] & 0x0fffffff) * 4];
315                                 const int* p2 = &verts[(indices[next(i1, n)] & 0x0fffffff) * 4];
316                                 
317                                 int dx = p2[0] - p0[0];
318                                 int dy = p2[2] - p0[2];
319                                 int len = dx*dx + dy*dy;
320                                 
321                                 if (minLen < 0 || len < minLen)
322                                 {
323                                         minLen = len;
324                                         mini = i;
325                                 }
326                         }
327                 }
328                 
329                 if (mini == -1)
330                 {
331                         // Should not happen.
332 /*                      printf("mini == -1 ntris=%d n=%d\n", ntris, n);
333                         for (int i = 0; i < n; i++)
334                         {
335                                 printf("%d ", indices[i] & 0x0fffffff);
336                         }
337                         printf("\n");*/
338                         return -ntris;
339                 }
340                 
341                 int i = mini;
342                 int i1 = next(i, n);
343                 int i2 = next(i1, n);
344                 
345                 *dst++ = indices[i] & 0x0fffffff;
346                 *dst++ = indices[i1] & 0x0fffffff;
347                 *dst++ = indices[i2] & 0x0fffffff;
348                 ntris++;
349                 
350                 // Removes P[i1] by copying P[i+1]...P[n-1] left one index.
351                 n--;
352                 for (int k = i1; k < n; k++)
353                         indices[k] = indices[k+1];
354                 
355                 if (i1 >= n) i1 = 0;
356                 i = prev(i1,n);
357                 // Update diagonal flags.
358                 if (diagonal(prev(i, n), i1, n, verts, indices))
359                         indices[i] |= 0x80000000;
360                 else
361                         indices[i] &= 0x0fffffff;
362                 
363                 if (diagonal(i, next(i1, n), n, verts, indices))
364                         indices[i1] |= 0x80000000;
365                 else
366                         indices[i1] &= 0x0fffffff;
367         }
368         
369         // Append the remaining triangle.
370         *dst++ = indices[0] & 0x0fffffff;
371         *dst++ = indices[1] & 0x0fffffff;
372         *dst++ = indices[2] & 0x0fffffff;
373         ntris++;
374         
375         return ntris;
376 }
377
378 static int countPolyVerts(const unsigned short* p, const int nvp)
379 {
380         for (int i = 0; i < nvp; ++i)
381                 if (p[i] == RC_MESH_NULL_IDX)
382                         return i;
383         return nvp;
384 }
385
386 inline bool uleft(const unsigned short* a, const unsigned short* b, const unsigned short* c)
387 {
388         return ((int)b[0] - (int)a[0]) * ((int)c[2] - (int)a[2]) -
389                    ((int)c[0] - (int)a[0]) * ((int)b[2] - (int)a[2]) < 0;
390 }
391
392 static int getPolyMergeValue(unsigned short* pa, unsigned short* pb,
393                                                          const unsigned short* verts, int& ea, int& eb,
394                                                          const int nvp)
395 {
396         const int na = countPolyVerts(pa, nvp);
397         const int nb = countPolyVerts(pb, nvp);
398         
399         // If the merged polygon would be too big, do not merge.
400         if (na+nb-2 > nvp)
401                 return -1;
402         
403         // Check if the polygons share an edge.
404         ea = -1;
405         eb = -1;
406         
407         for (int i = 0; i < na; ++i)
408         {
409                 unsigned short va0 = pa[i];
410                 unsigned short va1 = pa[(i+1) % na];
411                 if (va0 > va1)
412                         rcSwap(va0, va1);
413                 for (int j = 0; j < nb; ++j)
414                 {
415                         unsigned short vb0 = pb[j];
416                         unsigned short vb1 = pb[(j+1) % nb];
417                         if (vb0 > vb1)
418                                 rcSwap(vb0, vb1);
419                         if (va0 == vb0 && va1 == vb1)
420                         {
421                                 ea = i;
422                                 eb = j;
423                                 break;
424                         }
425                 }
426         }
427         
428         // No common edge, cannot merge.
429         if (ea == -1 || eb == -1)
430                 return -1;
431         
432         // Check to see if the merged polygon would be convex.
433         unsigned short va, vb, vc;
434         
435         va = pa[(ea+na-1) % na];
436         vb = pa[ea];
437         vc = pb[(eb+2) % nb];
438         if (!uleft(&verts[va*3], &verts[vb*3], &verts[vc*3]))
439                 return -1;
440         
441         va = pb[(eb+nb-1) % nb];
442         vb = pb[eb];
443         vc = pa[(ea+2) % na];
444         if (!uleft(&verts[va*3], &verts[vb*3], &verts[vc*3]))
445                 return -1;
446         
447         va = pa[ea];
448         vb = pa[(ea+1)%na];
449         
450         int dx = (int)verts[va*3+0] - (int)verts[vb*3+0];
451         int dy = (int)verts[va*3+2] - (int)verts[vb*3+2];
452         
453         return dx*dx + dy*dy;
454 }
455
456 static void mergePolys(unsigned short* pa, unsigned short* pb, int ea, int eb,
457                                            unsigned short* tmp, const int nvp)
458 {
459         const int na = countPolyVerts(pa, nvp);
460         const int nb = countPolyVerts(pb, nvp);
461         
462         // Merge polygons.
463         memset(tmp, 0xff, sizeof(unsigned short)*nvp);
464         int n = 0;
465         // Add pa
466         for (int i = 0; i < na-1; ++i)
467                 tmp[n++] = pa[(ea+1+i) % na];
468         // Add pb
469         for (int i = 0; i < nb-1; ++i)
470                 tmp[n++] = pb[(eb+1+i) % nb];
471         
472         memcpy(pa, tmp, sizeof(unsigned short)*nvp);
473 }
474
475
476 static void pushFront(int v, int* arr, int& an)
477 {
478         an++;
479         for (int i = an-1; i > 0; --i) arr[i] = arr[i-1];
480         arr[0] = v;
481 }
482
483 static void pushBack(int v, int* arr, int& an)
484 {
485         arr[an] = v;
486         an++;
487 }
488
489 static bool canRemoveVertex(rcContext* ctx, rcPolyMesh& mesh, const unsigned short rem)
490 {
491         const int nvp = mesh.nvp;
492         
493         // Count number of polygons to remove.
494         int numRemovedVerts = 0;
495         int numTouchedVerts = 0;
496         int numRemainingEdges = 0;
497         for (int i = 0; i < mesh.npolys; ++i)
498         {
499                 unsigned short* p = &mesh.polys[i*nvp*2];
500                 const int nv = countPolyVerts(p, nvp);
501                 int numRemoved = 0;
502                 int numVerts = 0;
503                 for (int j = 0; j < nv; ++j)
504                 {
505                         if (p[j] == rem)
506                         {
507                                 numTouchedVerts++;
508                                 numRemoved++;
509                         }
510                         numVerts++;
511                 }
512                 if (numRemoved)
513                 {
514                         numRemovedVerts += numRemoved;
515                         numRemainingEdges += numVerts-(numRemoved+1);
516                 }
517         }
518         
519         // There would be too few edges remaining to create a polygon.
520         // This can happen for example when a tip of a triangle is marked
521         // as deletion, but there are no other polys that share the vertex.
522         // In this case, the vertex should not be removed.
523         if (numRemainingEdges <= 2)
524                 return false;
525         
526         // Find edges which share the removed vertex.
527         const int maxEdges = numTouchedVerts*2;
528         int nedges = 0;
529         rcScopedDelete<int> edges = (int*)rcAlloc(sizeof(int)*maxEdges*3, RC_ALLOC_TEMP);
530         if (!edges)
531         {
532                 ctx->log(RC_LOG_WARNING, "canRemoveVertex: Out of memory 'edges' (%d).", maxEdges*3);
533                 return false;
534         }
535                 
536         for (int i = 0; i < mesh.npolys; ++i)
537         {
538                 unsigned short* p = &mesh.polys[i*nvp*2];
539                 const int nv = countPolyVerts(p, nvp);
540
541                 // Collect edges which touches the removed vertex.
542                 for (int j = 0, k = nv-1; j < nv; k = j++)
543                 {
544                         if (p[j] == rem || p[k] == rem)
545                         {
546                                 // Arrange edge so that a=rem.
547                                 int a = p[j], b = p[k];
548                                 if (b == rem)
549                                         rcSwap(a,b);
550                                         
551                                 // Check if the edge exists
552                                 bool exists = false;
553                                 for (int k = 0; k < nedges; ++k)
554                                 {
555                                         int* e = &edges[k*3];
556                                         if (e[1] == b)
557                                         {
558                                                 // Exists, increment vertex share count.
559                                                 e[2]++;
560                                                 exists = true;
561                                         }
562                                 }
563                                 // Add new edge.
564                                 if (!exists)
565                                 {
566                                         int* e = &edges[nedges*3];
567                                         e[0] = a;
568                                         e[1] = b;
569                                         e[2] = 1;
570                                         nedges++;
571                                 }
572                         }
573                 }
574         }
575
576         // There should be no more than 2 open edges.
577         // This catches the case that two non-adjacent polygons
578         // share the removed vertex. In that case, do not remove the vertex.
579         int numOpenEdges = 0;
580         for (int i = 0; i < nedges; ++i)
581         {
582                 if (edges[i*3+2] < 2)
583                         numOpenEdges++;
584         }
585         if (numOpenEdges > 2)
586                 return false;
587         
588         return true;
589 }
590
591 static bool removeVertex(rcContext* ctx, rcPolyMesh& mesh, const unsigned short rem, const int maxTris)
592 {
593         const int nvp = mesh.nvp;
594
595         // Count number of polygons to remove.
596         int numRemovedVerts = 0;
597         for (int i = 0; i < mesh.npolys; ++i)
598         {
599                 unsigned short* p = &mesh.polys[i*nvp*2];
600                 const int nv = countPolyVerts(p, nvp);
601                 for (int j = 0; j < nv; ++j)
602                 {
603                         if (p[j] == rem)
604                                 numRemovedVerts++;
605                 }
606         }
607         
608         int nedges = 0;
609         rcScopedDelete<int> edges = (int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp*4, RC_ALLOC_TEMP);
610         if (!edges)
611         {
612                 ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'edges' (%d).", numRemovedVerts*nvp*4);
613                 return false;
614         }
615
616         int nhole = 0;
617         rcScopedDelete<int> hole = (int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp, RC_ALLOC_TEMP);
618         if (!hole)
619         {
620                 ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'hole' (%d).", numRemovedVerts*nvp);
621                 return false;
622         }
623         
624         int nhreg = 0;
625         rcScopedDelete<int> hreg = (int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp, RC_ALLOC_TEMP);
626         if (!hreg)
627         {
628                 ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'hreg' (%d).", numRemovedVerts*nvp);
629                 return false;
630         }
631
632         int nharea = 0;
633         rcScopedDelete<int> harea = (int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp, RC_ALLOC_TEMP);
634         if (!harea)
635         {
636                 ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'harea' (%d).", numRemovedVerts*nvp);
637                 return false;
638         }
639         
640         for (int i = 0; i < mesh.npolys; ++i)
641         {
642                 unsigned short* p = &mesh.polys[i*nvp*2];
643                 const int nv = countPolyVerts(p, nvp);
644                 bool hasRem = false;
645                 for (int j = 0; j < nv; ++j)
646                         if (p[j] == rem) hasRem = true;
647                 if (hasRem)
648                 {
649                         // Collect edges which does not touch the removed vertex.
650                         for (int j = 0, k = nv-1; j < nv; k = j++)
651                         {
652                                 if (p[j] != rem && p[k] != rem)
653                                 {
654                                         int* e = &edges[nedges*4];
655                                         e[0] = p[k];
656                                         e[1] = p[j];
657                                         e[2] = mesh.regs[i];
658                                         e[3] = mesh.areas[i];
659                                         nedges++;
660                                 }
661                         }
662                         // Remove the polygon.
663                         unsigned short* p2 = &mesh.polys[(mesh.npolys-1)*nvp*2];
664                         memcpy(p,p2,sizeof(unsigned short)*nvp);
665                         memset(p+nvp,0xff,sizeof(unsigned short)*nvp);
666                         mesh.regs[i] = mesh.regs[mesh.npolys-1];
667                         mesh.areas[i] = mesh.areas[mesh.npolys-1];
668                         mesh.npolys--;
669                         --i;
670                 }
671         }
672         
673         // Remove vertex.
674         for (int i = (int)rem; i < mesh.nverts; ++i)
675         {
676                 mesh.verts[i*3+0] = mesh.verts[(i+1)*3+0];
677                 mesh.verts[i*3+1] = mesh.verts[(i+1)*3+1];
678                 mesh.verts[i*3+2] = mesh.verts[(i+1)*3+2];
679         }
680         mesh.nverts--;
681
682         // Adjust indices to match the removed vertex layout.
683         for (int i = 0; i < mesh.npolys; ++i)
684         {
685                 unsigned short* p = &mesh.polys[i*nvp*2];
686                 const int nv = countPolyVerts(p, nvp);
687                 for (int j = 0; j < nv; ++j)
688                         if (p[j] > rem) p[j]--;
689         }
690         for (int i = 0; i < nedges; ++i)
691         {
692                 if (edges[i*4+0] > rem) edges[i*4+0]--;
693                 if (edges[i*4+1] > rem) edges[i*4+1]--;
694         }
695
696         if (nedges == 0)
697                 return true;
698
699         // Start with one vertex, keep appending connected
700         // segments to the start and end of the hole.
701         pushBack(edges[0], hole, nhole);
702         pushBack(edges[2], hreg, nhreg);
703         pushBack(edges[3], harea, nharea);
704         
705         while (nedges)
706         {
707                 bool match = false;
708                 
709                 for (int i = 0; i < nedges; ++i)
710                 {
711                         const int ea = edges[i*4+0];
712                         const int eb = edges[i*4+1];
713                         const int r = edges[i*4+2];
714                         const int a = edges[i*4+3];
715                         bool add = false;
716                         if (hole[0] == eb)
717                         {
718                                 // The segment matches the beginning of the hole boundary.
719                                 pushFront(ea, hole, nhole);
720                                 pushFront(r, hreg, nhreg);
721                                 pushFront(a, harea, nharea);
722                                 add = true;
723                         }
724                         else if (hole[nhole-1] == ea)
725                         {
726                                 // The segment matches the end of the hole boundary.
727                                 pushBack(eb, hole, nhole);
728                                 pushBack(r, hreg, nhreg);
729                                 pushBack(a, harea, nharea);
730                                 add = true;
731                         }
732                         if (add)
733                         {
734                                 // The edge segment was added, remove it.
735                                 edges[i*4+0] = edges[(nedges-1)*4+0];
736                                 edges[i*4+1] = edges[(nedges-1)*4+1];
737                                 edges[i*4+2] = edges[(nedges-1)*4+2];
738                                 edges[i*4+3] = edges[(nedges-1)*4+3];
739                                 --nedges;
740                                 match = true;
741                                 --i;
742                         }
743                 }
744                 
745                 if (!match)
746                         break;
747         }
748
749         rcScopedDelete<int> tris = (int*)rcAlloc(sizeof(int)*nhole*3, RC_ALLOC_TEMP);
750         if (!tris)
751         {
752                 ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'tris' (%d).", nhole*3);
753                 return false;
754         }
755
756         rcScopedDelete<int> tverts = (int*)rcAlloc(sizeof(int)*nhole*4, RC_ALLOC_TEMP);
757         if (!tverts)
758         {
759                 ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'tverts' (%d).", nhole*4);
760                 return false;
761         }
762
763         rcScopedDelete<int> thole = (int*)rcAlloc(sizeof(int)*nhole, RC_ALLOC_TEMP);
764         if (!tverts)
765         {
766                 ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'thole' (%d).", nhole);
767                 return false;
768         }
769
770         // Generate temp vertex array for triangulation.
771         for (int i = 0; i < nhole; ++i)
772         {
773                 const int pi = hole[i];
774                 tverts[i*4+0] = mesh.verts[pi*3+0];
775                 tverts[i*4+1] = mesh.verts[pi*3+1];
776                 tverts[i*4+2] = mesh.verts[pi*3+2];
777                 tverts[i*4+3] = 0;
778                 thole[i] = i;
779         }
780
781         // Triangulate the hole.
782         int ntris = triangulate(nhole, &tverts[0], &thole[0], tris);
783         if (ntris < 0)
784         {
785                 ntris = -ntris;
786                 ctx->log(RC_LOG_WARNING, "removeVertex: triangulate() returned bad results.");
787         }
788         
789         // Merge the hole triangles back to polygons.
790         rcScopedDelete<unsigned short> polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*(ntris+1)*nvp, RC_ALLOC_TEMP);
791         if (!polys)
792         {
793                 ctx->log(RC_LOG_ERROR, "removeVertex: Out of memory 'polys' (%d).", (ntris+1)*nvp);
794                 return false;
795         }
796         rcScopedDelete<unsigned short> pregs = (unsigned short*)rcAlloc(sizeof(unsigned short)*ntris, RC_ALLOC_TEMP);
797         if (!pregs)
798         {
799                 ctx->log(RC_LOG_ERROR, "removeVertex: Out of memory 'pregs' (%d).", ntris);
800                 return false;
801         }
802         rcScopedDelete<unsigned char> pareas = (unsigned char*)rcAlloc(sizeof(unsigned char)*ntris, RC_ALLOC_TEMP);
803         if (!pregs)
804         {
805                 ctx->log(RC_LOG_ERROR, "removeVertex: Out of memory 'pareas' (%d).", ntris);
806                 return false;
807         }
808         
809         unsigned short* tmpPoly = &polys[ntris*nvp];
810                         
811         // Build initial polygons.
812         int npolys = 0;
813         memset(polys, 0xff, ntris*nvp*sizeof(unsigned short));
814         for (int j = 0; j < ntris; ++j)
815         {
816                 int* t = &tris[j*3];
817                 if (t[0] != t[1] && t[0] != t[2] && t[1] != t[2])
818                 {
819                         polys[npolys*nvp+0] = (unsigned short)hole[t[0]];
820                         polys[npolys*nvp+1] = (unsigned short)hole[t[1]];
821                         polys[npolys*nvp+2] = (unsigned short)hole[t[2]];
822                         pregs[npolys] = (unsigned short)hreg[t[0]];
823                         pareas[npolys] = (unsigned char)harea[t[0]];
824                         npolys++;
825                 }
826         }
827         if (!npolys)
828                 return true;
829         
830         // Merge polygons.
831         if (nvp > 3)
832         {
833                 for (;;)
834                 {
835                         // Find best polygons to merge.
836                         int bestMergeVal = 0;
837                         int bestPa = 0, bestPb = 0, bestEa = 0, bestEb = 0;
838                         
839                         for (int j = 0; j < npolys-1; ++j)
840                         {
841                                 unsigned short* pj = &polys[j*nvp];
842                                 for (int k = j+1; k < npolys; ++k)
843                                 {
844                                         unsigned short* pk = &polys[k*nvp];
845                                         int ea, eb;
846                                         int v = getPolyMergeValue(pj, pk, mesh.verts, ea, eb, nvp);
847                                         if (v > bestMergeVal)
848                                         {
849                                                 bestMergeVal = v;
850                                                 bestPa = j;
851                                                 bestPb = k;
852                                                 bestEa = ea;
853                                                 bestEb = eb;
854                                         }
855                                 }
856                         }
857                         
858                         if (bestMergeVal > 0)
859                         {
860                                 // Found best, merge.
861                                 unsigned short* pa = &polys[bestPa*nvp];
862                                 unsigned short* pb = &polys[bestPb*nvp];
863                                 mergePolys(pa, pb, bestEa, bestEb, tmpPoly, nvp);
864                                 memcpy(pb, &polys[(npolys-1)*nvp], sizeof(unsigned short)*nvp);
865                                 pregs[bestPb] = pregs[npolys-1];
866                                 pareas[bestPb] = pareas[npolys-1];
867                                 npolys--;
868                         }
869                         else
870                         {
871                                 // Could not merge any polygons, stop.
872                                 break;
873                         }
874                 }
875         }
876         
877         // Store polygons.
878         for (int i = 0; i < npolys; ++i)
879         {
880                 if (mesh.npolys >= maxTris) break;
881                 unsigned short* p = &mesh.polys[mesh.npolys*nvp*2];
882                 memset(p,0xff,sizeof(unsigned short)*nvp*2);
883                 for (int j = 0; j < nvp; ++j)
884                         p[j] = polys[i*nvp+j];
885                 mesh.regs[mesh.npolys] = pregs[i];
886                 mesh.areas[mesh.npolys] = pareas[i];
887                 mesh.npolys++;
888                 if (mesh.npolys > maxTris)
889                 {
890                         ctx->log(RC_LOG_ERROR, "removeVertex: Too many polygons %d (max:%d).", mesh.npolys, maxTris);
891                         return false;
892                 }
893         }
894         
895         return true;
896 }
897
898 /// @par
899 ///
900 /// @note If the mesh data is to be used to construct a Detour navigation mesh, then the upper 
901 /// limit must be retricted to <= #DT_VERTS_PER_POLYGON.
902 ///
903 /// @see rcAllocPolyMesh, rcContourSet, rcPolyMesh, rcConfig
904 bool rcBuildPolyMesh(rcContext* ctx, rcContourSet& cset, const int nvp, rcPolyMesh& mesh)
905 {
906         rcAssert(ctx);
907         
908         ctx->startTimer(RC_TIMER_BUILD_POLYMESH);
909
910         rcVcopy(mesh.bmin, cset.bmin);
911         rcVcopy(mesh.bmax, cset.bmax);
912         mesh.cs = cset.cs;
913         mesh.ch = cset.ch;
914         mesh.borderSize = cset.borderSize;
915         
916         int maxVertices = 0;
917         int maxTris = 0;
918         int maxVertsPerCont = 0;
919         for (int i = 0; i < cset.nconts; ++i)
920         {
921                 // Skip null contours.
922                 if (cset.conts[i].nverts < 3) continue;
923                 maxVertices += cset.conts[i].nverts;
924                 maxTris += cset.conts[i].nverts - 2;
925                 maxVertsPerCont = rcMax(maxVertsPerCont, cset.conts[i].nverts);
926         }
927         
928         if (maxVertices >= 0xfffe)
929         {
930                 ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Too many vertices %d.", maxVertices);
931                 return false;
932         }
933                 
934         rcScopedDelete<unsigned char> vflags = (unsigned char*)rcAlloc(sizeof(unsigned char)*maxVertices, RC_ALLOC_TEMP);
935         if (!vflags)
936         {
937                 ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.verts' (%d).", maxVertices);
938                 return false;
939         }
940         memset(vflags, 0, maxVertices);
941         
942         mesh.verts = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxVertices*3, RC_ALLOC_PERM);
943         if (!mesh.verts)
944         {
945                 ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.verts' (%d).", maxVertices);
946                 return false;
947         }
948         mesh.polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxTris*nvp*2, RC_ALLOC_PERM);
949         if (!mesh.polys)
950         {
951                 ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.polys' (%d).", maxTris*nvp*2);
952                 return false;
953         }
954         mesh.regs = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxTris, RC_ALLOC_PERM);
955         if (!mesh.regs)
956         {
957                 ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.regs' (%d).", maxTris);
958                 return false;
959         }
960         mesh.areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*maxTris, RC_ALLOC_PERM);
961         if (!mesh.areas)
962         {
963                 ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.areas' (%d).", maxTris);
964                 return false;
965         }
966         
967         mesh.nverts = 0;
968         mesh.npolys = 0;
969         mesh.nvp = nvp;
970         mesh.maxpolys = maxTris;
971         
972         memset(mesh.verts, 0, sizeof(unsigned short)*maxVertices*3);
973         memset(mesh.polys, 0xff, sizeof(unsigned short)*maxTris*nvp*2);
974         memset(mesh.regs, 0, sizeof(unsigned short)*maxTris);
975         memset(mesh.areas, 0, sizeof(unsigned char)*maxTris);
976         
977         rcScopedDelete<int> nextVert = (int*)rcAlloc(sizeof(int)*maxVertices, RC_ALLOC_TEMP);
978         if (!nextVert)
979         {
980                 ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'nextVert' (%d).", maxVertices);
981                 return false;
982         }
983         memset(nextVert, 0, sizeof(int)*maxVertices);
984         
985         rcScopedDelete<int> firstVert = (int*)rcAlloc(sizeof(int)*VERTEX_BUCKET_COUNT, RC_ALLOC_TEMP);
986         if (!firstVert)
987         {
988                 ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'firstVert' (%d).", VERTEX_BUCKET_COUNT);
989                 return false;
990         }
991         for (int i = 0; i < VERTEX_BUCKET_COUNT; ++i)
992                 firstVert[i] = -1;
993         
994         rcScopedDelete<int> indices = (int*)rcAlloc(sizeof(int)*maxVertsPerCont, RC_ALLOC_TEMP);
995         if (!indices)
996         {
997                 ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'indices' (%d).", maxVertsPerCont);
998                 return false;
999         }
1000         rcScopedDelete<int> tris = (int*)rcAlloc(sizeof(int)*maxVertsPerCont*3, RC_ALLOC_TEMP);
1001         if (!tris)
1002         {
1003                 ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'tris' (%d).", maxVertsPerCont*3);
1004                 return false;
1005         }
1006         rcScopedDelete<unsigned short> polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*(maxVertsPerCont+1)*nvp, RC_ALLOC_TEMP);
1007         if (!polys)
1008         {
1009                 ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'polys' (%d).", maxVertsPerCont*nvp);
1010                 return false;
1011         }
1012         unsigned short* tmpPoly = &polys[maxVertsPerCont*nvp];
1013
1014         for (int i = 0; i < cset.nconts; ++i)
1015         {
1016                 rcContour& cont = cset.conts[i];
1017                 
1018                 // Skip null contours.
1019                 if (cont.nverts < 3)
1020                         continue;
1021                 
1022                 // Triangulate contour
1023                 for (int j = 0; j < cont.nverts; ++j)
1024                         indices[j] = j;
1025                         
1026                 int ntris = triangulate(cont.nverts, cont.verts, &indices[0], &tris[0]);
1027                 if (ntris <= 0)
1028                 {
1029                         // Bad triangulation, should not happen.
1030 /*                      printf("\tconst float bmin[3] = {%ff,%ff,%ff};\n", cset.bmin[0], cset.bmin[1], cset.bmin[2]);
1031                         printf("\tconst float cs = %ff;\n", cset.cs);
1032                         printf("\tconst float ch = %ff;\n", cset.ch);
1033                         printf("\tconst int verts[] = {\n");
1034                         for (int k = 0; k < cont.nverts; ++k)
1035                         {
1036                                 const int* v = &cont.verts[k*4];
1037                                 printf("\t\t%d,%d,%d,%d,\n", v[0], v[1], v[2], v[3]);
1038                         }
1039                         printf("\t};\n\tconst int nverts = sizeof(verts)/(sizeof(int)*4);\n");*/
1040                         ctx->log(RC_LOG_WARNING, "rcBuildPolyMesh: Bad triangulation Contour %d.", i);
1041                         ntris = -ntris;
1042                 }
1043                                 
1044                 // Add and merge vertices.
1045                 for (int j = 0; j < cont.nverts; ++j)
1046                 {
1047                         const int* v = &cont.verts[j*4];
1048                         indices[j] = addVertex((unsigned short)v[0], (unsigned short)v[1], (unsigned short)v[2],
1049                                                                    mesh.verts, firstVert, nextVert, mesh.nverts);
1050                         if (v[3] & RC_BORDER_VERTEX)
1051                         {
1052                                 // This vertex should be removed.
1053                                 vflags[indices[j]] = 1;
1054                         }
1055                 }
1056                 
1057                 // Build initial polygons.
1058                 int npolys = 0;
1059                 memset(polys, 0xff, maxVertsPerCont*nvp*sizeof(unsigned short));
1060                 for (int j = 0; j < ntris; ++j)
1061                 {
1062                         int* t = &tris[j*3];
1063                         if (t[0] != t[1] && t[0] != t[2] && t[1] != t[2])
1064                         {
1065                                 polys[npolys*nvp+0] = (unsigned short)indices[t[0]];
1066                                 polys[npolys*nvp+1] = (unsigned short)indices[t[1]];
1067                                 polys[npolys*nvp+2] = (unsigned short)indices[t[2]];
1068                                 npolys++;
1069                         }
1070                 }
1071                 if (!npolys)
1072                         continue;
1073                 
1074                 // Merge polygons.
1075                 if (nvp > 3)
1076                 {
1077                         for(;;)
1078                         {
1079                                 // Find best polygons to merge.
1080                                 int bestMergeVal = 0;
1081                                 int bestPa = 0, bestPb = 0, bestEa = 0, bestEb = 0;
1082                                 
1083                                 for (int j = 0; j < npolys-1; ++j)
1084                                 {
1085                                         unsigned short* pj = &polys[j*nvp];
1086                                         for (int k = j+1; k < npolys; ++k)
1087                                         {
1088                                                 unsigned short* pk = &polys[k*nvp];
1089                                                 int ea, eb;
1090                                                 int v = getPolyMergeValue(pj, pk, mesh.verts, ea, eb, nvp);
1091                                                 if (v > bestMergeVal)
1092                                                 {
1093                                                         bestMergeVal = v;
1094                                                         bestPa = j;
1095                                                         bestPb = k;
1096                                                         bestEa = ea;
1097                                                         bestEb = eb;
1098                                                 }
1099                                         }
1100                                 }
1101                                 
1102                                 if (bestMergeVal > 0)
1103                                 {
1104                                         // Found best, merge.
1105                                         unsigned short* pa = &polys[bestPa*nvp];
1106                                         unsigned short* pb = &polys[bestPb*nvp];
1107                                         mergePolys(pa, pb, bestEa, bestEb, tmpPoly, nvp);
1108                                         memcpy(pb, &polys[(npolys-1)*nvp], sizeof(unsigned short)*nvp);
1109                                         npolys--;
1110                                 }
1111                                 else
1112                                 {
1113                                         // Could not merge any polygons, stop.
1114                                         break;
1115                                 }
1116                         }
1117                 }
1118                 
1119                 // Store polygons.
1120                 for (int j = 0; j < npolys; ++j)
1121                 {
1122                         unsigned short* p = &mesh.polys[mesh.npolys*nvp*2];
1123                         unsigned short* q = &polys[j*nvp];
1124                         for (int k = 0; k < nvp; ++k)
1125                                 p[k] = q[k];
1126                         mesh.regs[mesh.npolys] = cont.reg;
1127                         mesh.areas[mesh.npolys] = cont.area;
1128                         mesh.npolys++;
1129                         if (mesh.npolys > maxTris)
1130                         {
1131                                 ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Too many polygons %d (max:%d).", mesh.npolys, maxTris);
1132                                 return false;
1133                         }
1134                 }
1135         }
1136         
1137         
1138         // Remove edge vertices.
1139         for (int i = 0; i < mesh.nverts; ++i)
1140         {
1141                 if (vflags[i])
1142                 {
1143                         if (!canRemoveVertex(ctx, mesh, (unsigned short)i))
1144                                 continue;
1145                         if (!removeVertex(ctx, mesh, (unsigned short)i, maxTris))
1146                         {
1147                                 // Failed to remove vertex
1148                                 ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Failed to remove edge vertex %d.", i);
1149                                 return false;
1150                         }
1151                         // Remove vertex
1152                         // Note: mesh.nverts is already decremented inside removeVertex()!
1153                         for (int j = i; j < mesh.nverts; ++j)
1154                                 vflags[j] = vflags[j+1];
1155                         --i;
1156                 }
1157         }
1158         
1159         // Calculate adjacency.
1160         if (!buildMeshAdjacency(mesh.polys, mesh.npolys, mesh.nverts, nvp))
1161         {
1162                 ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Adjacency failed.");
1163                 return false;
1164         }
1165         
1166         // Find portal edges
1167         if (mesh.borderSize > 0)
1168         {
1169                 const int w = cset.width;
1170                 const int h = cset.height;
1171                 for (int i = 0; i < mesh.npolys; ++i)
1172                 {
1173                         unsigned short* p = &mesh.polys[i*2*nvp];
1174                         for (int j = 0; j < nvp; ++j)
1175                         {
1176                                 if (p[j] == RC_MESH_NULL_IDX) break;
1177                                 // Skip connected edges.
1178                                 if (p[nvp+j] != RC_MESH_NULL_IDX)
1179                                         continue;
1180                                 int nj = j+1;
1181                                 if (nj >= nvp || p[nj] == RC_MESH_NULL_IDX) nj = 0;
1182                                 const unsigned short* va = &mesh.verts[p[j]*3];
1183                                 const unsigned short* vb = &mesh.verts[p[nj]*3];
1184
1185                                 if ((int)va[0] == 0 && (int)vb[0] == 0)
1186                                         p[nvp+j] = 0x8000 | 0;
1187                                 else if ((int)va[2] == h && (int)vb[2] == h)
1188                                         p[nvp+j] = 0x8000 | 1;
1189                                 else if ((int)va[0] == w && (int)vb[0] == w)
1190                                         p[nvp+j] = 0x8000 | 2;
1191                                 else if ((int)va[2] == 0 && (int)vb[2] == 0)
1192                                         p[nvp+j] = 0x8000 | 3;
1193                         }
1194                 }
1195         }
1196
1197         // Just allocate the mesh flags array. The user is resposible to fill it.
1198         mesh.flags = (unsigned short*)rcAlloc(sizeof(unsigned short)*mesh.npolys, RC_ALLOC_PERM);
1199         if (!mesh.flags)
1200         {
1201                 ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.flags' (%d).", mesh.npolys);
1202                 return false;
1203         }
1204         memset(mesh.flags, 0, sizeof(unsigned short) * mesh.npolys);
1205         
1206         if (mesh.nverts > 0xffff)
1207         {
1208                 ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: The resulting mesh has too many vertices %d (max %d). Data can be corrupted.", mesh.nverts, 0xffff);
1209         }
1210         if (mesh.npolys > 0xffff)
1211         {
1212                 ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: The resulting mesh has too many polygons %d (max %d). Data can be corrupted.", mesh.npolys, 0xffff);
1213         }
1214         
1215         ctx->stopTimer(RC_TIMER_BUILD_POLYMESH);
1216         
1217         return true;
1218 }
1219
1220 /// @see rcAllocPolyMesh, rcPolyMesh
1221 bool rcMergePolyMeshes(rcContext* ctx, rcPolyMesh** meshes, const int nmeshes, rcPolyMesh& mesh)
1222 {
1223         rcAssert(ctx);
1224         
1225         if (!nmeshes || !meshes)
1226                 return true;
1227
1228         ctx->startTimer(RC_TIMER_MERGE_POLYMESH);
1229
1230         mesh.nvp = meshes[0]->nvp;
1231         mesh.cs = meshes[0]->cs;
1232         mesh.ch = meshes[0]->ch;
1233         rcVcopy(mesh.bmin, meshes[0]->bmin);
1234         rcVcopy(mesh.bmax, meshes[0]->bmax);
1235
1236         int maxVerts = 0;
1237         int maxPolys = 0;
1238         int maxVertsPerMesh = 0;
1239         for (int i = 0; i < nmeshes; ++i)
1240         {
1241                 rcVmin(mesh.bmin, meshes[i]->bmin);
1242                 rcVmax(mesh.bmax, meshes[i]->bmax);
1243                 maxVertsPerMesh = rcMax(maxVertsPerMesh, meshes[i]->nverts);
1244                 maxVerts += meshes[i]->nverts;
1245                 maxPolys += meshes[i]->npolys;
1246         }
1247         
1248         mesh.nverts = 0;
1249         mesh.verts = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxVerts*3, RC_ALLOC_PERM);
1250         if (!mesh.verts)
1251         {
1252                 ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'mesh.verts' (%d).", maxVerts*3);
1253                 return false;
1254         }
1255
1256         mesh.npolys = 0;
1257         mesh.polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxPolys*2*mesh.nvp, RC_ALLOC_PERM);
1258         if (!mesh.polys)
1259         {
1260                 ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'mesh.polys' (%d).", maxPolys*2*mesh.nvp);
1261                 return false;
1262         }
1263         memset(mesh.polys, 0xff, sizeof(unsigned short)*maxPolys*2*mesh.nvp);
1264
1265         mesh.regs = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxPolys, RC_ALLOC_PERM);
1266         if (!mesh.regs)
1267         {
1268                 ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'mesh.regs' (%d).", maxPolys);
1269                 return false;
1270         }
1271         memset(mesh.regs, 0, sizeof(unsigned short)*maxPolys);
1272
1273         mesh.areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*maxPolys, RC_ALLOC_PERM);
1274         if (!mesh.areas)
1275         {
1276                 ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'mesh.areas' (%d).", maxPolys);
1277                 return false;
1278         }
1279         memset(mesh.areas, 0, sizeof(unsigned char)*maxPolys);
1280
1281         mesh.flags = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxPolys, RC_ALLOC_PERM);
1282         if (!mesh.flags)
1283         {
1284                 ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'mesh.flags' (%d).", maxPolys);
1285                 return false;
1286         }
1287         memset(mesh.flags, 0, sizeof(unsigned short)*maxPolys);
1288         
1289         rcScopedDelete<int> nextVert = (int*)rcAlloc(sizeof(int)*maxVerts, RC_ALLOC_TEMP);
1290         if (!nextVert)
1291         {
1292                 ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'nextVert' (%d).", maxVerts);
1293                 return false;
1294         }
1295         memset(nextVert, 0, sizeof(int)*maxVerts);
1296         
1297         rcScopedDelete<int> firstVert = (int*)rcAlloc(sizeof(int)*VERTEX_BUCKET_COUNT, RC_ALLOC_TEMP);
1298         if (!firstVert)
1299         {
1300                 ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'firstVert' (%d).", VERTEX_BUCKET_COUNT);
1301                 return false;
1302         }
1303         for (int i = 0; i < VERTEX_BUCKET_COUNT; ++i)
1304                 firstVert[i] = -1;
1305
1306         rcScopedDelete<unsigned short> vremap = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxVertsPerMesh, RC_ALLOC_PERM);
1307         if (!vremap)
1308         {
1309                 ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'vremap' (%d).", maxVertsPerMesh);
1310                 return false;
1311         }
1312         memset(nextVert, 0, sizeof(int)*maxVerts);
1313         
1314         for (int i = 0; i < nmeshes; ++i)
1315         {
1316                 const rcPolyMesh* pmesh = meshes[i];
1317                 
1318                 const unsigned short ox = (unsigned short)floorf((pmesh->bmin[0]-mesh.bmin[0])/mesh.cs+0.5f);
1319                 const unsigned short oz = (unsigned short)floorf((pmesh->bmin[2]-mesh.bmin[2])/mesh.cs+0.5f);
1320                 
1321                 for (int j = 0; j < pmesh->nverts; ++j)
1322                 {
1323                         unsigned short* v = &pmesh->verts[j*3];
1324                         vremap[j] = addVertex(v[0]+ox, v[1], v[2]+oz,
1325                                                                   mesh.verts, firstVert, nextVert, mesh.nverts);
1326                 }
1327                 
1328                 for (int j = 0; j < pmesh->npolys; ++j)
1329                 {
1330                         unsigned short* tgt = &mesh.polys[mesh.npolys*2*mesh.nvp];
1331                         unsigned short* src = &pmesh->polys[j*2*mesh.nvp];
1332                         mesh.regs[mesh.npolys] = pmesh->regs[j];
1333                         mesh.areas[mesh.npolys] = pmesh->areas[j];
1334                         mesh.flags[mesh.npolys] = pmesh->flags[j];
1335                         mesh.npolys++;
1336                         for (int k = 0; k < mesh.nvp; ++k)
1337                         {
1338                                 if (src[k] == RC_MESH_NULL_IDX) break;
1339                                 tgt[k] = vremap[src[k]];
1340                         }
1341                 }
1342         }
1343
1344         // Calculate adjacency.
1345         if (!buildMeshAdjacency(mesh.polys, mesh.npolys, mesh.nverts, mesh.nvp))
1346         {
1347                 ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Adjacency failed.");
1348                 return false;
1349         }
1350
1351         if (mesh.nverts > 0xffff)
1352         {
1353                 ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: The resulting mesh has too many vertices %d (max %d). Data can be corrupted.", mesh.nverts, 0xffff);
1354         }
1355         if (mesh.npolys > 0xffff)
1356         {
1357                 ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: The resulting mesh has too many polygons %d (max %d). Data can be corrupted.", mesh.npolys, 0xffff);
1358         }
1359         
1360         ctx->stopTimer(RC_TIMER_MERGE_POLYMESH);
1361         
1362         return true;
1363 }