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 <float.h>
20#include <math.h>
21#include <string.h>
22#include <stdlib.h>
23#include <stdio.h>
24#include "Recast.h"
25#include "RecastAlloc.h"
26#include "RecastAssert.h"
27
28
29static const unsigned RC_UNSET_HEIGHT = 0xffff;
30
31struct rcHeightPatch
32{
33 inline rcHeightPatch() : data(0), xmin(0), ymin(0), width(0), height(0) {}
34 inline ~rcHeightPatch() { rcFree(data); }
35 unsigned short* data;
36 int xmin, ymin, width, height;
37};
38
39
40inline float vdot2(const float* a, const float* b)
41{
42 return a[0]*b[0] + a[2]*b[2];
43}
44
45inline float vdistSq2(const float* p, const float* q)
46{
47 const float dx = q[0] - p[0];
48 const float dy = q[2] - p[2];
49 return dx*dx + dy*dy;
50}
51
52inline float vdist2(const float* p, const float* q)
53{
54 return sqrtf(vdistSq2(p,q));
55}
56
57inline float vcross2(const float* p1, const float* p2, const float* p3)
58{
59 const float u1 = p2[0] - p1[0];
60 const float v1 = p2[2] - p1[2];
61 const float u2 = p3[0] - p1[0];
62 const float v2 = p3[2] - p1[2];
63 return u1 * v2 - v1 * u2;
64}
65
66static bool circumCircle(const float* p1, const float* p2, const float* p3,
67 float* c, float& r)
68{
69 static const float EPS = 1e-6f;
70 // Calculate the circle relative to p1, to avoid some precision issues.
71 const float v1[3] = {0,0,0};
72 float v2[3], v3[3];
73 rcVsub(v2, p2,p1);
74 rcVsub(v3, p3,p1);
75
76 const float cp = vcross2(v1, v2, v3);
77 if (fabsf(cp) > EPS)
78 {
79 const float v1Sq = vdot2(v1,v1);
80 const float v2Sq = vdot2(v2,v2);
81 const float v3Sq = vdot2(v3,v3);
82 c[0] = (v1Sq*(v2[2]-v3[2]) + v2Sq*(v3[2]-v1[2]) + v3Sq*(v1[2]-v2[2])) / (2*cp);
83 c[1] = 0;
84 c[2] = (v1Sq*(v3[0]-v2[0]) + v2Sq*(v1[0]-v3[0]) + v3Sq*(v2[0]-v1[0])) / (2*cp);
85 r = vdist2(c, v1);
86 rcVadd(c, c, p1);
87 return true;
88 }
89
90 rcVcopy(c, p1);
91 r = 0;
92 return false;
93}
94
95static float distPtTri(const float* p, const float* a, const float* b, const float* c)
96{
97 float v0[3], v1[3], v2[3];
98 rcVsub(v0, c,a);
99 rcVsub(v1, b,a);
100 rcVsub(v2, p,a);
101
102 const float dot00 = vdot2(v0, v0);
103 const float dot01 = vdot2(v0, v1);
104 const float dot02 = vdot2(v0, v2);
105 const float dot11 = vdot2(v1, v1);
106 const float dot12 = vdot2(v1, v2);
107
108 // Compute barycentric coordinates
109 const float invDenom = 1.0f / (dot00 * dot11 - dot01 * dot01);
110 const float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
111 float v = (dot00 * dot12 - dot01 * dot02) * invDenom;
112
113 // If point lies inside the triangle, return interpolated y-coord.
114 static const float EPS = 1e-4f;
115 if (u >= -EPS && v >= -EPS && (u+v) <= 1+EPS)
116 {
117 const float y = a[1] + v0[1]*u + v1[1]*v;
118 return fabsf(y-p[1]);
119 }
120 return FLT_MAX;
121}
122
123static float distancePtSeg(const float* pt, const float* p, const float* q)
124{
125 float pqx = q[0] - p[0];
126 float pqy = q[1] - p[1];
127 float pqz = q[2] - p[2];
128 float dx = pt[0] - p[0];
129 float dy = pt[1] - p[1];
130 float dz = pt[2] - p[2];
131 float d = pqx*pqx + pqy*pqy + pqz*pqz;
132 float t = pqx*dx + pqy*dy + pqz*dz;
133 if (d > 0)
134 t /= d;
135 if (t < 0)
136 t = 0;
137 else if (t > 1)
138 t = 1;
139
140 dx = p[0] + t*pqx - pt[0];
141 dy = p[1] + t*pqy - pt[1];
142 dz = p[2] + t*pqz - pt[2];
143
144 return dx*dx + dy*dy + dz*dz;
145}
146
147static float distancePtSeg2d(const float* pt, const float* p, const float* q)
148{
149 float pqx = q[0] - p[0];
150 float pqz = q[2] - p[2];
151 float dx = pt[0] - p[0];
152 float dz = pt[2] - p[2];
153 float d = pqx*pqx + pqz*pqz;
154 float t = pqx*dx + pqz*dz;
155 if (d > 0)
156 t /= d;
157 if (t < 0)
158 t = 0;
159 else if (t > 1)
160 t = 1;
161
162 dx = p[0] + t*pqx - pt[0];
163 dz = p[2] + t*pqz - pt[2];
164
165 return dx*dx + dz*dz;
166}
167
168static float distToTriMesh(const float* p, const float* verts, const int /*nverts*/, const int* tris, const int ntris)
169{
170 float dmin = FLT_MAX;
171 for (int i = 0; i < ntris; ++i)
172 {
173 const float* va = &verts[tris[i*4+0]*3];
174 const float* vb = &verts[tris[i*4+1]*3];
175 const float* vc = &verts[tris[i*4+2]*3];
176 float d = distPtTri(p, va,vb,vc);
177 if (d < dmin)
178 dmin = d;
179 }
180 if (dmin == FLT_MAX) return -1;
181 return dmin;
182}
183
184static float distToPoly(int nvert, const float* verts, const float* p)
185{
186
187 float dmin = FLT_MAX;
188 int i, j, c = 0;
189 for (i = 0, j = nvert-1; i < nvert; j = i++)
190 {
191 const float* vi = &verts[i*3];
192 const float* vj = &verts[j*3];
193 if (((vi[2] > p[2]) != (vj[2] > p[2])) &&
194 (p[0] < (vj[0]-vi[0]) * (p[2]-vi[2]) / (vj[2]-vi[2]) + vi[0]) )
195 c = !c;
196 dmin = rcMin(dmin, distancePtSeg2d(p, vj, vi));
197 }
198 return c ? -dmin : dmin;
199}
200
201
202static unsigned short getHeight(const float fx, const float fy, const float fz,
203 const float /*cs*/, const float ics, const float ch,
204 const int radius, const rcHeightPatch& hp)
205{
206 int ix = (int)floorf(fx*ics + 0.01f);
207 int iz = (int)floorf(fz*ics + 0.01f);
208 ix = rcClamp(ix-hp.xmin, 0, hp.width - 1);
209 iz = rcClamp(iz-hp.ymin, 0, hp.height - 1);
210 unsigned short h = hp.data[ix+iz*hp.width];
211 if (h == RC_UNSET_HEIGHT)
212 {
213 // Special case when data might be bad.
214 // Walk adjacent cells in a spiral up to 'radius', and look
215 // for a pixel which has a valid height.
216 int x = 1, z = 0, dx = 1, dz = 0;
217 int maxSize = radius * 2 + 1;
218 int maxIter = maxSize * maxSize - 1;
219
220 int nextRingIterStart = 8;
221 int nextRingIters = 16;
222
223 float dmin = FLT_MAX;
224 for (int i = 0; i < maxIter; i++)
225 {
226 const int nx = ix + x;
227 const int nz = iz + z;
228
229 if (nx >= 0 && nz >= 0 && nx < hp.width && nz < hp.height)
230 {
231 const unsigned short nh = hp.data[nx + nz*hp.width];
232 if (nh != RC_UNSET_HEIGHT)
233 {
234 const float d = fabsf(nh*ch - fy);
235 if (d < dmin)
236 {
237 h = nh;
238 dmin = d;
239 }
240 }
241 }
242
243 // We are searching in a grid which looks approximately like this:
244 // __________
245 // |2 ______ 2|
246 // | |1 __ 1| |
247 // | | |__| | |
248 // | |______| |
249 // |__________|
250 // We want to find the best height as close to the center cell as possible. This means that
251 // if we find a height in one of the neighbor cells to the center, we don't want to
252 // expand further out than the 8 neighbors - we want to limit our search to the closest
253 // of these "rings", but the best height in the ring.
254 // For example, the center is just 1 cell. We checked that at the entrance to the function.
255 // The next "ring" contains 8 cells (marked 1 above). Those are all the neighbors to the center cell.
256 // The next one again contains 16 cells (marked 2). In general each ring has 8 additional cells, which
257 // can be thought of as adding 2 cells around the "center" of each side when we expand the ring.
258 // Here we detect if we are about to enter the next ring, and if we are and we have found
259 // a height, we abort the search.
260 if (i + 1 == nextRingIterStart)
261 {
262 if (h != RC_UNSET_HEIGHT)
263 break;
264
265 nextRingIterStart += nextRingIters;
266 nextRingIters += 8;
267 }
268
269 if ((x == z) || ((x < 0) && (x == -z)) || ((x > 0) && (x == 1 - z)))
270 {
271 int tmp = dx;
272 dx = -dz;
273 dz = tmp;
274 }
275 x += dx;
276 z += dz;
277 }
278 }
279 return h;
280}
281
282
283enum EdgeValues
284{
285 EV_UNDEF = -1,
286 EV_HULL = -2
287};
288
289static int findEdge(const int* edges, int nedges, int s, int t)
290{
291 for (int i = 0; i < nedges; i++)
292 {
293 const int* e = &edges[i*4];
294 if ((e[0] == s && e[1] == t) || (e[0] == t && e[1] == s))
295 return i;
296 }
297 return EV_UNDEF;
298}
299
300static int addEdge(rcContext* ctx, int* edges, int& nedges, const int maxEdges, int s, int t, int l, int r)
301{
302 if (nedges >= maxEdges)
303 {
304 ctx->log(RC_LOG_ERROR, "addEdge: Too many edges (%d/%d).", nedges, maxEdges);
305 return EV_UNDEF;
306 }
307
308 // Add edge if not already in the triangulation.
309 int e = findEdge(edges, nedges, s, t);
310 if (e == EV_UNDEF)
311 {
312 int* edge = &edges[nedges*4];
313 edge[0] = s;
314 edge[1] = t;
315 edge[2] = l;
316 edge[3] = r;
317 return nedges++;
318 }
319 else
320 {
321 return EV_UNDEF;
322 }
323}
324
325static void updateLeftFace(int* e, int s, int t, int f)
326{
327 if (e[0] == s && e[1] == t && e[2] == EV_UNDEF)
328 e[2] = f;
329 else if (e[1] == s && e[0] == t && e[3] == EV_UNDEF)
330 e[3] = f;
331}
332
333static int overlapSegSeg2d(const float* a, const float* b, const float* c, const float* d)
334{
335 const float a1 = vcross2(a, b, d);
336 const float a2 = vcross2(a, b, c);
337 if (a1*a2 < 0.0f)
338 {
339 float a3 = vcross2(c, d, a);
340 float a4 = a3 + a2 - a1;
341 if (a3 * a4 < 0.0f)
342 return 1;
343 }
344 return 0;
345}
346
347static bool overlapEdges(const float* pts, const int* edges, int nedges, int s1, int t1)
348{
349 for (int i = 0; i < nedges; ++i)
350 {
351 const int s0 = edges[i*4+0];
352 const int t0 = edges[i*4+1];
353 // Same or connected edges do not overlap.
354 if (s0 == s1 || s0 == t1 || t0 == s1 || t0 == t1)
355 continue;
356 if (overlapSegSeg2d(&pts[s0*3],&pts[t0*3], &pts[s1*3],&pts[t1*3]))
357 return true;
358 }
359 return false;
360}
361
362static void completeFacet(rcContext* ctx, const float* pts, int npts, int* edges, int& nedges, const int maxEdges, int& nfaces, int e)
363{
364 static const float EPS = 1e-5f;
365
366 int* edge = &edges[e*4];
367
368 // Cache s and t.
369 int s,t;
370 if (edge[2] == EV_UNDEF)
371 {
372 s = edge[0];
373 t = edge[1];
374 }
375 else if (edge[3] == EV_UNDEF)
376 {
377 s = edge[1];
378 t = edge[0];
379 }
380 else
381 {
382 // Edge already completed.
383 return;
384 }
385
386 // Find best point on left of edge.
387 int pt = npts;
388 float c[3] = {0,0,0};
389 float r = -1;
390 for (int u = 0; u < npts; ++u)
391 {
392 if (u == s || u == t) continue;
393 if (vcross2(&pts[s*3], &pts[t*3], &pts[u*3]) > EPS)
394 {
395 if (r < 0)
396 {
397 // The circle is not updated yet, do it now.
398 pt = u;
399 circumCircle(&pts[s*3], &pts[t*3], &pts[u*3], c, r);
400 continue;
401 }
402 const float d = vdist2(c, &pts[u*3]);
403 const float tol = 0.001f;
404 if (d > r*(1+tol))
405 {
406 // Outside current circumcircle, skip.
407 continue;
408 }
409 else if (d < r*(1-tol))
410 {
411 // Inside safe circumcircle, update circle.
412 pt = u;
413 circumCircle(&pts[s*3], &pts[t*3], &pts[u*3], c, r);
414 }
415 else
416 {
417 // Inside epsilon circum circle, do extra tests to make sure the edge is valid.
418 // s-u and t-u cannot overlap with s-pt nor t-pt if they exists.
419 if (overlapEdges(pts, edges, nedges, s,u))
420 continue;
421 if (overlapEdges(pts, edges, nedges, t,u))
422 continue;
423 // Edge is valid.
424 pt = u;
425 circumCircle(&pts[s*3], &pts[t*3], &pts[u*3], c, r);
426 }
427 }
428 }
429
430 // Add new triangle or update edge info if s-t is on hull.
431 if (pt < npts)
432 {
433 // Update face information of edge being completed.
434 updateLeftFace(&edges[e*4], s, t, nfaces);
435
436 // Add new edge or update face info of old edge.
437 e = findEdge(edges, nedges, pt, s);
438 if (e == EV_UNDEF)
439 addEdge(ctx, edges, nedges, maxEdges, pt, s, nfaces, EV_UNDEF);
440 else
441 updateLeftFace(&edges[e*4], pt, s, nfaces);
442
443 // Add new edge or update face info of old edge.
444 e = findEdge(edges, nedges, t, pt);
445 if (e == EV_UNDEF)
446 addEdge(ctx, edges, nedges, maxEdges, t, pt, nfaces, EV_UNDEF);
447 else
448 updateLeftFace(&edges[e*4], t, pt, nfaces);
449
450 nfaces++;
451 }
452 else
453 {
454 updateLeftFace(&edges[e*4], s, t, EV_HULL);
455 }
456}
457
458static void delaunayHull(rcContext* ctx, const int npts, const float* pts,
459 const int nhull, const int* hull,
460 rcIntArray& tris, rcIntArray& edges)
461{
462 int nfaces = 0;
463 int nedges = 0;
464 const int maxEdges = npts*10;
465 edges.resize(maxEdges*4);
466
467 for (int i = 0, j = nhull-1; i < nhull; j=i++)
468 addEdge(ctx, &edges[0], nedges, maxEdges, hull[j],hull[i], EV_HULL, EV_UNDEF);
469
470 int currentEdge = 0;
471 while (currentEdge < nedges)
472 {
473 if (edges[currentEdge*4+2] == EV_UNDEF)
474 completeFacet(ctx, pts, npts, &edges[0], nedges, maxEdges, nfaces, currentEdge);
475 if (edges[currentEdge*4+3] == EV_UNDEF)
476 completeFacet(ctx, pts, npts, &edges[0], nedges, maxEdges, nfaces, currentEdge);
477 currentEdge++;
478 }
479
480 // Create tris
481 tris.resize(nfaces*4);
482 for (int i = 0; i < nfaces*4; ++i)
483 tris[i] = -1;
484
485 for (int i = 0; i < nedges; ++i)
486 {
487 const int* e = &edges[i*4];
488 if (e[3] >= 0)
489 {
490 // Left face
491 int* t = &tris[e[3]*4];
492 if (t[0] == -1)
493 {
494 t[0] = e[0];
495 t[1] = e[1];
496 }
497 else if (t[0] == e[1])
498 t[2] = e[0];
499 else if (t[1] == e[0])
500 t[2] = e[1];
501 }
502 if (e[2] >= 0)
503 {
504 // Right
505 int* t = &tris[e[2]*4];
506 if (t[0] == -1)
507 {
508 t[0] = e[1];
509 t[1] = e[0];
510 }
511 else if (t[0] == e[0])
512 t[2] = e[1];
513 else if (t[1] == e[1])
514 t[2] = e[0];
515 }
516 }
517
518 for (int i = 0; i < tris.size()/4; ++i)
519 {
520 int* t = &tris[i*4];
521 if (t[0] == -1 || t[1] == -1 || t[2] == -1)
522 {
523 ctx->log(RC_LOG_WARNING, "delaunayHull: Removing dangling face %d [%d,%d,%d].", i, t[0],t[1],t[2]);
524 t[0] = tris[tris.size()-4];
525 t[1] = tris[tris.size()-3];
526 t[2] = tris[tris.size()-2];
527 t[3] = tris[tris.size()-1];
528 tris.resize(tris.size()-4);
529 --i;
530 }
531 }
532}
533
534// Calculate minimum extend of the polygon.
535static float polyMinExtent(const float* verts, const int nverts)
536{
537 float minDist = FLT_MAX;
538 for (int i = 0; i < nverts; i++)
539 {
540 const int ni = (i+1) % nverts;
541 const float* p1 = &verts[i*3];
542 const float* p2 = &verts[ni*3];
543 float maxEdgeDist = 0;
544 for (int j = 0; j < nverts; j++)
545 {
546 if (j == i || j == ni) continue;
547 float d = distancePtSeg2d(&verts[j*3], p1,p2);
548 maxEdgeDist = rcMax(maxEdgeDist, d);
549 }
550 minDist = rcMin(minDist, maxEdgeDist);
551 }
552 return rcSqrt(minDist);
553}
554
555// Last time I checked the if version got compiled using cmov, which was a lot faster than module (with idiv).
556inline int prev(int i, int n) { return i-1 >= 0 ? i-1 : n-1; }
557inline int next(int i, int n) { return i+1 < n ? i+1 : 0; }
558
559static void triangulateHull(const int /*nverts*/, const float* verts, const int nhull, const int* hull, const int nin, rcIntArray& tris)
560{
561 int start = 0, left = 1, right = nhull-1;
562
563 // Start from an ear with shortest perimeter.
564 // This tends to favor well formed triangles as starting point.
565 float dmin = FLT_MAX;
566 for (int i = 0; i < nhull; i++)
567 {
568 if (hull[i] >= nin) continue; // Ears are triangles with original vertices as middle vertex while others are actually line segments on edges
569 int pi = prev(i, nhull);
570 int ni = next(i, nhull);
571 const float* pv = &verts[hull[pi]*3];
572 const float* cv = &verts[hull[i]*3];
573 const float* nv = &verts[hull[ni]*3];
574 const float d = vdist2(pv,cv) + vdist2(cv,nv) + vdist2(nv,pv);
575 if (d < dmin)
576 {
577 start = i;
578 left = ni;
579 right = pi;
580 dmin = d;
581 }
582 }
583
584 // Add first triangle
585 tris.push(hull[start]);
586 tris.push(hull[left]);
587 tris.push(hull[right]);
588 tris.push(0);
589
590 // Triangulate the polygon by moving left or right,
591 // depending on which triangle has shorter perimeter.
592 // This heuristic was chose emprically, since it seems
593 // handle tesselated straight edges well.
594 while (next(left, nhull) != right)
595 {
596 // Check to see if se should advance left or right.
597 int nleft = next(left, nhull);
598 int nright = prev(right, nhull);
599
600 const float* cvleft = &verts[hull[left]*3];
601 const float* nvleft = &verts[hull[nleft]*3];
602 const float* cvright = &verts[hull[right]*3];
603 const float* nvright = &verts[hull[nright]*3];
604 const float dleft = vdist2(cvleft, nvleft) + vdist2(nvleft, cvright);
605 const float dright = vdist2(cvright, nvright) + vdist2(cvleft, nvright);
606
607 if (dleft < dright)
608 {
609 tris.push(hull[left]);
610 tris.push(hull[nleft]);
611 tris.push(hull[right]);
612 tris.push(0);
613 left = nleft;
614 }
615 else
616 {
617 tris.push(hull[left]);
618 tris.push(hull[nright]);
619 tris.push(hull[right]);
620 tris.push(0);
621 right = nright;
622 }
623 }
624}
625
626
627inline float getJitterX(const int i)
628{
629 return (((i * 0x8da6b343) & 0xffff) / 65535.0f * 2.0f) - 1.0f;
630}
631
632inline float getJitterY(const int i)
633{
634 return (((i * 0xd8163841) & 0xffff) / 65535.0f * 2.0f) - 1.0f;
635}
636
637static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin,
638 const float sampleDist, const float sampleMaxError,
639 const int heightSearchRadius, const rcCompactHeightfield& chf,
640 const rcHeightPatch& hp, float* verts, int& nverts,
641 rcIntArray& tris, rcIntArray& edges, rcIntArray& samples)
642{
643 static const int MAX_VERTS = 127;
644 static const int MAX_TRIS = 255; // Max tris for delaunay is 2n-2-k (n=num verts, k=num hull verts).
645 static const int MAX_VERTS_PER_EDGE = 32;
646 float edge[(MAX_VERTS_PER_EDGE+1)*3];
647 int hull[MAX_VERTS];
648 int nhull = 0;
649
650 nverts = nin;
651
652 for (int i = 0; i < nin; ++i)
653 rcVcopy(&verts[i*3], &in[i*3]);
654
655 edges.clear();
656 tris.clear();
657
658 const float cs = chf.cs;
659 const float ics = 1.0f/cs;
660
661 // Calculate minimum extents of the polygon based on input data.
662 float minExtent = polyMinExtent(verts, nverts);
663
664 // Tessellate outlines.
665 // This is done in separate pass in order to ensure
666 // seamless height values across the ply boundaries.
667 if (sampleDist > 0)
668 {
669 for (int i = 0, j = nin-1; i < nin; j=i++)
670 {
671 const float* vj = &in[j*3];
672 const float* vi = &in[i*3];
673 bool swapped = false;
674 // Make sure the segments are always handled in same order
675 // using lexological sort or else there will be seams.
676 if (fabsf(vj[0]-vi[0]) < 1e-6f)
677 {
678 if (vj[2] > vi[2])
679 {
680 rcSwap(vj,vi);
681 swapped = true;
682 }
683 }
684 else
685 {
686 if (vj[0] > vi[0])
687 {
688 rcSwap(vj,vi);
689 swapped = true;
690 }
691 }
692 // Create samples along the edge.
693 float dx = vi[0] - vj[0];
694 float dy = vi[1] - vj[1];
695 float dz = vi[2] - vj[2];
696 float d = sqrtf(dx*dx + dz*dz);
697 int nn = 1 + (int)floorf(d/sampleDist);
698 if (nn >= MAX_VERTS_PER_EDGE) nn = MAX_VERTS_PER_EDGE-1;
699 if (nverts+nn >= MAX_VERTS)
700 nn = MAX_VERTS-1-nverts;
701
702 for (int k = 0; k <= nn; ++k)
703 {
704 float u = (float)k/(float)nn;
705 float* pos = &edge[k*3];
706 pos[0] = vj[0] + dx*u;
707 pos[1] = vj[1] + dy*u;
708 pos[2] = vj[2] + dz*u;
709 pos[1] = getHeight(pos[0],pos[1],pos[2], cs, ics, chf.ch, heightSearchRadius, hp)*chf.ch;
710 }
711 // Simplify samples.
712 int idx[MAX_VERTS_PER_EDGE] = {0,nn};
713 int nidx = 2;
714 for (int k = 0; k < nidx-1; )
715 {
716 const int a = idx[k];
717 const int b = idx[k+1];
718 const float* va = &edge[a*3];
719 const float* vb = &edge[b*3];
720 // Find maximum deviation along the segment.
721 float maxd = 0;
722 int maxi = -1;
723 for (int m = a+1; m < b; ++m)
724 {
725 float dev = distancePtSeg(&edge[m*3],va,vb);
726 if (dev > maxd)
727 {
728 maxd = dev;
729 maxi = m;
730 }
731 }
732 // If the max deviation is larger than accepted error,
733 // add new point, else continue to next segment.
734 if (maxi != -1 && maxd > rcSqr(sampleMaxError))
735 {
736 for (int m = nidx; m > k; --m)
737 idx[m] = idx[m-1];
738 idx[k+1] = maxi;
739 nidx++;
740 }
741 else
742 {
743 ++k;
744 }
745 }
746
747 hull[nhull++] = j;
748 // Add new vertices.
749 if (swapped)
750 {
751 for (int k = nidx-2; k > 0; --k)
752 {
753 rcVcopy(&verts[nverts*3], &edge[idx[k]*3]);
754 hull[nhull++] = nverts;
755 nverts++;
756 }
757 }
758 else
759 {
760 for (int k = 1; k < nidx-1; ++k)
761 {
762 rcVcopy(&verts[nverts*3], &edge[idx[k]*3]);
763 hull[nhull++] = nverts;
764 nverts++;
765 }
766 }
767 }
768 }
769
770 // If the polygon minimum extent is small (sliver or small triangle), do not try to add internal points.
771 if (minExtent < sampleDist*2)
772 {
773 triangulateHull(nverts, verts, nhull, hull, nin, tris);
774 return true;
775 }
776
777 // Tessellate the base mesh.
778 // We're using the triangulateHull instead of delaunayHull as it tends to
779 // create a bit better triangulation for long thin triangles when there
780 // are no internal points.
781 triangulateHull(nverts, verts, nhull, hull, nin, tris);
782
783 if (tris.size() == 0)
784 {
785 // Could not triangulate the poly, make sure there is some valid data there.
786 ctx->log(RC_LOG_WARNING, "buildPolyDetail: Could not triangulate polygon (%d verts).", nverts);
787 return true;
788 }
789
790 if (sampleDist > 0)
791 {
792 // Create sample locations in a grid.
793 float bmin[3], bmax[3];
794 rcVcopy(bmin, in);
795 rcVcopy(bmax, in);
796 for (int i = 1; i < nin; ++i)
797 {
798 rcVmin(bmin, &in[i*3]);
799 rcVmax(bmax, &in[i*3]);
800 }
801 int x0 = (int)floorf(bmin[0]/sampleDist);
802 int x1 = (int)ceilf(bmax[0]/sampleDist);
803 int z0 = (int)floorf(bmin[2]/sampleDist);
804 int z1 = (int)ceilf(bmax[2]/sampleDist);
805 samples.clear();
806 for (int z = z0; z < z1; ++z)
807 {
808 for (int x = x0; x < x1; ++x)
809 {
810 float pt[3];
811 pt[0] = x*sampleDist;
812 pt[1] = (bmax[1]+bmin[1])*0.5f;
813 pt[2] = z*sampleDist;
814 // Make sure the samples are not too close to the edges.
815 if (distToPoly(nin,in,pt) > -sampleDist/2) continue;
816 samples.push(x);
817 samples.push(getHeight(pt[0], pt[1], pt[2], cs, ics, chf.ch, heightSearchRadius, hp));
818 samples.push(z);
819 samples.push(0); // Not added
820 }
821 }
822
823 // Add the samples starting from the one that has the most
824 // error. The procedure stops when all samples are added
825 // or when the max error is within treshold.
826 const int nsamples = samples.size()/4;
827 for (int iter = 0; iter < nsamples; ++iter)
828 {
829 if (nverts >= MAX_VERTS)
830 break;
831
832 // Find sample with most error.
833 float bestpt[3] = {0,0,0};
834 float bestd = 0;
835 int besti = -1;
836 for (int i = 0; i < nsamples; ++i)
837 {
838 const int* s = &samples[i*4];
839 if (s[3]) continue; // skip added.
840 float pt[3];
841 // The sample location is jittered to get rid of some bad triangulations
842 // which are cause by symmetrical data from the grid structure.
843 pt[0] = s[0]*sampleDist + getJitterX(i)*cs*0.1f;
844 pt[1] = s[1]*chf.ch;
845 pt[2] = s[2]*sampleDist + getJitterY(i)*cs*0.1f;
846 float d = distToTriMesh(pt, verts, nverts, &tris[0], tris.size()/4);
847 if (d < 0) continue; // did not hit the mesh.
848 if (d > bestd)
849 {
850 bestd = d;
851 besti = i;
852 rcVcopy(bestpt,pt);
853 }
854 }
855 // If the max error is within accepted threshold, stop tesselating.
856 if (bestd <= sampleMaxError || besti == -1)
857 break;
858 // Mark sample as added.
859 samples[besti*4+3] = 1;
860 // Add the new sample point.
861 rcVcopy(&verts[nverts*3],bestpt);
862 nverts++;
863
864 // Create new triangulation.
865 // TODO: Incremental add instead of full rebuild.
866 edges.clear();
867 tris.clear();
868 delaunayHull(ctx, nverts, verts, nhull, hull, tris, edges);
869 }
870 }
871
872 const int ntris = tris.size()/4;
873 if (ntris > MAX_TRIS)
874 {
875 tris.resize(MAX_TRIS*4);
876 ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Shrinking triangle count from %d to max %d.", ntris, MAX_TRIS);
877 }
878
879 return true;
880}
881
882static void seedArrayWithPolyCenter(rcContext* ctx, const rcCompactHeightfield& chf,
883 const unsigned short* poly, const int npoly,
884 const unsigned short* verts, const int bs,
885 rcHeightPatch& hp, rcIntArray& array)
886{
887 // Note: Reads to the compact heightfield are offset by border size (bs)
888 // since border size offset is already removed from the polymesh vertices.
889
890 static const int offset[9*2] =
891 {
892 0,0, -1,-1, 0,-1, 1,-1, 1,0, 1,1, 0,1, -1,1, -1,0,
893 };
894
895 // Find cell closest to a poly vertex
896 int startCellX = 0, startCellY = 0, startSpanIndex = -1;
897 int dmin = RC_UNSET_HEIGHT;
898 for (int j = 0; j < npoly && dmin > 0; ++j)
899 {
900 for (int k = 0; k < 9 && dmin > 0; ++k)
901 {
902 const int ax = (int)verts[poly[j]*3+0] + offset[k*2+0];
903 const int ay = (int)verts[poly[j]*3+1];
904 const int az = (int)verts[poly[j]*3+2] + offset[k*2+1];
905 if (ax < hp.xmin || ax >= hp.xmin+hp.width ||
906 az < hp.ymin || az >= hp.ymin+hp.height)
907 continue;
908
909 const rcCompactCell& c = chf.cells[(ax+bs)+(az+bs)*chf.width];
910 for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni && dmin > 0; ++i)
911 {
912 const rcCompactSpan& s = chf.spans[i];
913 int d = rcAbs(ay - (int)s.y);
914 if (d < dmin)
915 {
916 startCellX = ax;
917 startCellY = az;
918 startSpanIndex = i;
919 dmin = d;
920 }
921 }
922 }
923 }
924
925 rcAssert(startSpanIndex != -1);
926 // Find center of the polygon
927 int pcx = 0, pcy = 0;
928 for (int j = 0; j < npoly; ++j)
929 {
930 pcx += (int)verts[poly[j]*3+0];
931 pcy += (int)verts[poly[j]*3+2];
932 }
933 pcx /= npoly;
934 pcy /= npoly;
935
936 // Use seeds array as a stack for DFS
937 array.clear();
938 array.push(startCellX);
939 array.push(startCellY);
940 array.push(startSpanIndex);
941
942 int dirs[] = { 0, 1, 2, 3 };
943 memset(hp.data, 0, sizeof(unsigned short)*hp.width*hp.height);
944 // DFS to move to the center. Note that we need a DFS here and can not just move
945 // directly towards the center without recording intermediate nodes, even though the polygons
946 // are convex. In very rare we can get stuck due to contour simplification if we do not
947 // record nodes.
948 int cx = -1, cy = -1, ci = -1;
949 while (true)
950 {
951 if (array.size() < 3)
952 {
953 ctx->log(RC_LOG_WARNING, "Walk towards polygon center failed to reach center");
954 break;
955 }
956
957 ci = array.pop();
958 cy = array.pop();
959 cx = array.pop();
960
961 if (cx == pcx && cy == pcy)
962 break;
963
964 // If we are already at the correct X-position, prefer direction
965 // directly towards the center in the Y-axis; otherwise prefer
966 // direction in the X-axis
967 int directDir;
968 if (cx == pcx)
969 directDir = rcGetDirForOffset(0, pcy > cy ? 1 : -1);
970 else
971 directDir = rcGetDirForOffset(pcx > cx ? 1 : -1, 0);
972
973 // Push the direct dir last so we start with this on next iteration
974 rcSwap(dirs[directDir], dirs[3]);
975
976 const rcCompactSpan& cs = chf.spans[ci];
977 for (int i = 0; i < 4; i++)
978 {
979 int dir = dirs[i];
980 if (rcGetCon(cs, dir) == RC_NOT_CONNECTED)
981 continue;
982
983 int newX = cx + rcGetDirOffsetX(dir);
984 int newY = cy + rcGetDirOffsetY(dir);
985
986 int hpx = newX - hp.xmin;
987 int hpy = newY - hp.ymin;
988 if (hpx < 0 || hpx >= hp.width || hpy < 0 || hpy >= hp.height)
989 continue;
990
991 if (hp.data[hpx+hpy*hp.width] != 0)
992 continue;
993
994 hp.data[hpx+hpy*hp.width] = 1;
995 array.push(newX);
996 array.push(newY);
997 array.push((int)chf.cells[(newX+bs)+(newY+bs)*chf.width].index + rcGetCon(cs, dir));
998 }
999
1000 rcSwap(dirs[directDir], dirs[3]);
1001 }
1002
1003 array.clear();
1004 // getHeightData seeds are given in coordinates with borders
1005 array.push(cx+bs);
1006 array.push(cy+bs);
1007 array.push(ci);
1008
1009 memset(hp.data, 0xff, sizeof(unsigned short)*hp.width*hp.height);
1010 const rcCompactSpan& cs = chf.spans[ci];
1011 hp.data[cx-hp.xmin+(cy-hp.ymin)*hp.width] = cs.y;
1012}
1013
1014
1015static void push3(rcIntArray& queue, int v1, int v2, int v3)
1016{
1017 queue.resize(queue.size() + 3);
1018 queue[queue.size() - 3] = v1;
1019 queue[queue.size() - 2] = v2;
1020 queue[queue.size() - 1] = v3;
1021}
1022
1023static void getHeightData(rcContext* ctx, const rcCompactHeightfield& chf,
1024 const unsigned short* poly, const int npoly,
1025 const unsigned short* verts, const int bs,
1026 rcHeightPatch& hp, rcIntArray& queue,
1027 int region)
1028{
1029 // Note: Reads to the compact heightfield are offset by border size (bs)
1030 // since border size offset is already removed from the polymesh vertices.
1031
1032 queue.clear();
1033 // Set all heights to RC_UNSET_HEIGHT.
1034 memset(hp.data, 0xff, sizeof(unsigned short)*hp.width*hp.height);
1035
1036 bool empty = true;
1037
1038 // We cannot sample from this poly if it was created from polys
1039 // of different regions. If it was then it could potentially be overlapping
1040 // with polys of that region and the heights sampled here could be wrong.
1041 if (region != RC_MULTIPLE_REGS)
1042 {
1043 // Copy the height from the same region, and mark region borders
1044 // as seed points to fill the rest.
1045 for (int hy = 0; hy < hp.height; hy++)
1046 {
1047 int y = hp.ymin + hy + bs;
1048 for (int hx = 0; hx < hp.width; hx++)
1049 {
1050 int x = hp.xmin + hx + bs;
1051 const rcCompactCell& c = chf.cells[x + y*chf.width];
1052 for (int i = (int)c.index, ni = (int)(c.index + c.count); i < ni; ++i)
1053 {
1054 const rcCompactSpan& s = chf.spans[i];
1055 if (s.reg == region)
1056 {
1057 // Store height
1058 hp.data[hx + hy*hp.width] = s.y;
1059 empty = false;
1060
1061 // If any of the neighbours is not in same region,
1062 // add the current location as flood fill start
1063 bool border = false;
1064 for (int dir = 0; dir < 4; ++dir)
1065 {
1066 if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
1067 {
1068 const int ax = x + rcGetDirOffsetX(dir);
1069 const int ay = y + rcGetDirOffsetY(dir);
1070 const int ai = (int)chf.cells[ax + ay*chf.width].index + rcGetCon(s, dir);
1071 const rcCompactSpan& as = chf.spans[ai];
1072 if (as.reg != region)
1073 {
1074 border = true;
1075 break;
1076 }
1077 }
1078 }
1079 if (border)
1080 push3(queue, x, y, i);
1081 break;
1082 }
1083 }
1084 }
1085 }
1086 }
1087
1088 // if the polygon does not contain any points from the current region (rare, but happens)
1089 // or if it could potentially be overlapping polygons of the same region,
1090 // then use the center as the seed point.
1091 if (empty)
1092 seedArrayWithPolyCenter(ctx, chf, poly, npoly, verts, bs, hp, queue);
1093
1094 static const int RETRACT_SIZE = 256;
1095 int head = 0;
1096
1097 // We assume the seed is centered in the polygon, so a BFS to collect
1098 // height data will ensure we do not move onto overlapping polygons and
1099 // sample wrong heights.
1100 while (head*3 < queue.size())
1101 {
1102 int cx = queue[head*3+0];
1103 int cy = queue[head*3+1];
1104 int ci = queue[head*3+2];
1105 head++;
1106 if (head >= RETRACT_SIZE)
1107 {
1108 head = 0;
1109 if (queue.size() > RETRACT_SIZE*3)
1110 memmove(&queue[0], &queue[RETRACT_SIZE*3], sizeof(int)*(queue.size()-RETRACT_SIZE*3));
1111 queue.resize(queue.size()-RETRACT_SIZE*3);
1112 }
1113
1114 const rcCompactSpan& cs = chf.spans[ci];
1115 for (int dir = 0; dir < 4; ++dir)
1116 {
1117 if (rcGetCon(cs, dir) == RC_NOT_CONNECTED) continue;
1118
1119 const int ax = cx + rcGetDirOffsetX(dir);
1120 const int ay = cy + rcGetDirOffsetY(dir);
1121 const int hx = ax - hp.xmin - bs;
1122 const int hy = ay - hp.ymin - bs;
1123
1124 if ((unsigned int)hx >= (unsigned int)hp.width || (unsigned int)hy >= (unsigned int)hp.height)
1125 continue;
1126
1127 if (hp.data[hx + hy*hp.width] != RC_UNSET_HEIGHT)
1128 continue;
1129
1130 const int ai = (int)chf.cells[ax + ay*chf.width].index + rcGetCon(cs, dir);
1131 const rcCompactSpan& as = chf.spans[ai];
1132
1133 hp.data[hx + hy*hp.width] = as.y;
1134
1135 push3(queue, ax, ay, ai);
1136 }
1137 }
1138}
1139
1140static unsigned char getEdgeFlags(const float* va, const float* vb,
1141 const float* vpoly, const int npoly)
1142{
1143 // The flag returned by this function matches dtDetailTriEdgeFlags in Detour.
1144 // Figure out if edge (va,vb) is part of the polygon boundary.
1145 static const float thrSqr = rcSqr(0.001f);
1146 for (int i = 0, j = npoly-1; i < npoly; j=i++)
1147 {
1148 if (distancePtSeg2d(va, &vpoly[j*3], &vpoly[i*3]) < thrSqr &&
1149 distancePtSeg2d(vb, &vpoly[j*3], &vpoly[i*3]) < thrSqr)
1150 return 1;
1151 }
1152 return 0;
1153}
1154
1155static unsigned char getTriFlags(const float* va, const float* vb, const float* vc,
1156 const float* vpoly, const int npoly)
1157{
1158 unsigned char flags = 0;
1159 flags |= getEdgeFlags(va,vb,vpoly,npoly) << 0;
1160 flags |= getEdgeFlags(vb,vc,vpoly,npoly) << 2;
1161 flags |= getEdgeFlags(vc,va,vpoly,npoly) << 4;
1162 return flags;
1163}
1164
1165/// @par
1166///
1167/// See the #rcConfig documentation for more information on the configuration parameters.
1168///
1169/// @see rcAllocPolyMeshDetail, rcPolyMesh, rcCompactHeightfield, rcPolyMeshDetail, rcConfig
1170bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompactHeightfield& chf,
1171 const float sampleDist, const float sampleMaxError,
1172 rcPolyMeshDetail& dmesh)
1173{
1174 rcAssert(ctx);
1175
1176 rcScopedTimer timer(ctx, RC_TIMER_BUILD_POLYMESHDETAIL);
1177
1178 if (mesh.nverts == 0 || mesh.npolys == 0)
1179 return true;
1180
1181 const int nvp = mesh.nvp;
1182 const float cs = mesh.cs;
1183 const float ch = mesh.ch;
1184 const float* orig = mesh.bmin;
1185 const int borderSize = mesh.borderSize;
1186 const int heightSearchRadius = rcMax(1, (int)ceilf(mesh.maxEdgeError));
1187
1188 rcIntArray edges(64);
1189 rcIntArray tris(512);
1190 rcIntArray arr(512);
1191 rcIntArray samples(512);
1192 float verts[256*3];
1193 rcHeightPatch hp;
1194 int nPolyVerts = 0;
1195 int maxhw = 0, maxhh = 0;
1196
1197 rcScopedDelete<int> bounds((int*)rcAlloc(sizeof(int)*mesh.npolys*4, RC_ALLOC_TEMP));
1198 if (!bounds)
1199 {
1200 ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'bounds' (%d).", mesh.npolys*4);
1201 return false;
1202 }
1203 rcScopedDelete<float> poly((float*)rcAlloc(sizeof(float)*nvp*3, RC_ALLOC_TEMP));
1204 if (!poly)
1205 {
1206 ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'poly' (%d).", nvp*3);
1207 return false;
1208 }
1209
1210 // Find max size for a polygon area.
1211 for (int i = 0; i < mesh.npolys; ++i)
1212 {
1213 const unsigned short* p = &mesh.polys[i*nvp*2];
1214 int& xmin = bounds[i*4+0];
1215 int& xmax = bounds[i*4+1];
1216 int& ymin = bounds[i*4+2];
1217 int& ymax = bounds[i*4+3];
1218 xmin = chf.width;
1219 xmax = 0;
1220 ymin = chf.height;
1221 ymax = 0;
1222 for (int j = 0; j < nvp; ++j)
1223 {
1224 if(p[j] == RC_MESH_NULL_IDX) break;
1225 const unsigned short* v = &mesh.verts[p[j]*3];
1226 xmin = rcMin(xmin, (int)v[0]);
1227 xmax = rcMax(xmax, (int)v[0]);
1228 ymin = rcMin(ymin, (int)v[2]);
1229 ymax = rcMax(ymax, (int)v[2]);
1230 nPolyVerts++;
1231 }
1232 xmin = rcMax(0,xmin-1);
1233 xmax = rcMin(chf.width,xmax+1);
1234 ymin = rcMax(0,ymin-1);
1235 ymax = rcMin(chf.height,ymax+1);
1236 if (xmin >= xmax || ymin >= ymax) continue;
1237 maxhw = rcMax(maxhw, xmax-xmin);
1238 maxhh = rcMax(maxhh, ymax-ymin);
1239 }
1240
1241 hp.data = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxhw*maxhh, RC_ALLOC_TEMP);
1242 if (!hp.data)
1243 {
1244 ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'hp.data' (%d).", maxhw*maxhh);
1245 return false;
1246 }
1247
1248 dmesh.nmeshes = mesh.npolys;
1249 dmesh.nverts = 0;
1250 dmesh.ntris = 0;
1251 dmesh.meshes = (unsigned int*)rcAlloc(sizeof(unsigned int)*dmesh.nmeshes*4, RC_ALLOC_PERM);
1252 if (!dmesh.meshes)
1253 {
1254 ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.meshes' (%d).", dmesh.nmeshes*4);
1255 return false;
1256 }
1257
1258 int vcap = nPolyVerts+nPolyVerts/2;
1259 int tcap = vcap*2;
1260
1261 dmesh.nverts = 0;
1262 dmesh.verts = (float*)rcAlloc(sizeof(float)*vcap*3, RC_ALLOC_PERM);
1263 if (!dmesh.verts)
1264 {
1265 ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.verts' (%d).", vcap*3);
1266 return false;
1267 }
1268 dmesh.ntris = 0;
1269 dmesh.tris = (unsigned char*)rcAlloc(sizeof(unsigned char)*tcap*4, RC_ALLOC_PERM);
1270 if (!dmesh.tris)
1271 {
1272 ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.tris' (%d).", tcap*4);
1273 return false;
1274 }
1275
1276 for (int i = 0; i < mesh.npolys; ++i)
1277 {
1278 const unsigned short* p = &mesh.polys[i*nvp*2];
1279
1280 // Store polygon vertices for processing.
1281 int npoly = 0;
1282 for (int j = 0; j < nvp; ++j)
1283 {
1284 if(p[j] == RC_MESH_NULL_IDX) break;
1285 const unsigned short* v = &mesh.verts[p[j]*3];
1286 poly[j*3+0] = v[0]*cs;
1287 poly[j*3+1] = v[1]*ch;
1288 poly[j*3+2] = v[2]*cs;
1289 npoly++;
1290 }
1291
1292 // Get the height data from the area of the polygon.
1293 hp.xmin = bounds[i*4+0];
1294 hp.ymin = bounds[i*4+2];
1295 hp.width = bounds[i*4+1]-bounds[i*4+0];
1296 hp.height = bounds[i*4+3]-bounds[i*4+2];
1297 getHeightData(ctx, chf, p, npoly, mesh.verts, borderSize, hp, arr, mesh.regs[i]);
1298
1299 // Build detail mesh.
1300 int nverts = 0;
1301 if (!buildPolyDetail(ctx, poly, npoly,
1302 sampleDist, sampleMaxError,
1303 heightSearchRadius, chf, hp,
1304 verts, nverts, tris,
1305 edges, samples))
1306 {
1307 return false;
1308 }
1309
1310 // Move detail verts to world space.
1311 for (int j = 0; j < nverts; ++j)
1312 {
1313 verts[j*3+0] += orig[0];
1314 verts[j*3+1] += orig[1] + chf.ch; // Is this offset necessary?
1315 verts[j*3+2] += orig[2];
1316 }
1317 // Offset poly too, will be used to flag checking.
1318 for (int j = 0; j < npoly; ++j)
1319 {
1320 poly[j*3+0] += orig[0];
1321 poly[j*3+1] += orig[1];
1322 poly[j*3+2] += orig[2];
1323 }
1324
1325 // Store detail submesh.
1326 const int ntris = tris.size()/4;
1327
1328 dmesh.meshes[i*4+0] = (unsigned int)dmesh.nverts;
1329 dmesh.meshes[i*4+1] = (unsigned int)nverts;
1330 dmesh.meshes[i*4+2] = (unsigned int)dmesh.ntris;
1331 dmesh.meshes[i*4+3] = (unsigned int)ntris;
1332
1333 // Store vertices, allocate more memory if necessary.
1334 if (dmesh.nverts+nverts > vcap)
1335 {
1336 while (dmesh.nverts+nverts > vcap)
1337 vcap += 256;
1338
1339 float* newv = (float*)rcAlloc(sizeof(float)*vcap*3, RC_ALLOC_PERM);
1340 if (!newv)
1341 {
1342 ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'newv' (%d).", vcap*3);
1343 return false;
1344 }
1345 if (dmesh.nverts)
1346 memcpy(newv, dmesh.verts, sizeof(float)*3*dmesh.nverts);
1347 rcFree(dmesh.verts);
1348 dmesh.verts = newv;
1349 }
1350 for (int j = 0; j < nverts; ++j)
1351 {
1352 dmesh.verts[dmesh.nverts*3+0] = verts[j*3+0];
1353 dmesh.verts[dmesh.nverts*3+1] = verts[j*3+1];
1354 dmesh.verts[dmesh.nverts*3+2] = verts[j*3+2];
1355 dmesh.nverts++;
1356 }
1357
1358 // Store triangles, allocate more memory if necessary.
1359 if (dmesh.ntris+ntris > tcap)
1360 {
1361 while (dmesh.ntris+ntris > tcap)
1362 tcap += 256;
1363 unsigned char* newt = (unsigned char*)rcAlloc(sizeof(unsigned char)*tcap*4, RC_ALLOC_PERM);
1364 if (!newt)
1365 {
1366 ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'newt' (%d).", tcap*4);
1367 return false;
1368 }
1369 if (dmesh.ntris)
1370 memcpy(newt, dmesh.tris, sizeof(unsigned char)*4*dmesh.ntris);
1371 rcFree(dmesh.tris);
1372 dmesh.tris = newt;
1373 }
1374 for (int j = 0; j < ntris; ++j)
1375 {
1376 const int* t = &tris[j*4];
1377 dmesh.tris[dmesh.ntris*4+0] = (unsigned char)t[0];
1378 dmesh.tris[dmesh.ntris*4+1] = (unsigned char)t[1];
1379 dmesh.tris[dmesh.ntris*4+2] = (unsigned char)t[2];
1380 dmesh.tris[dmesh.ntris*4+3] = getTriFlags(&verts[t[0]*3], &verts[t[1]*3], &verts[t[2]*3], poly, npoly);
1381 dmesh.ntris++;
1382 }
1383 }
1384
1385 return true;
1386}
1387
1388/// @see rcAllocPolyMeshDetail, rcPolyMeshDetail
1389bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int nmeshes, rcPolyMeshDetail& mesh)
1390{
1391 rcAssert(ctx);
1392
1393 rcScopedTimer timer(ctx, RC_TIMER_MERGE_POLYMESHDETAIL);
1394
1395 int maxVerts = 0;
1396 int maxTris = 0;
1397 int maxMeshes = 0;
1398
1399 for (int i = 0; i < nmeshes; ++i)
1400 {
1401 if (!meshes[i]) continue;
1402 maxVerts += meshes[i]->nverts;
1403 maxTris += meshes[i]->ntris;
1404 maxMeshes += meshes[i]->nmeshes;
1405 }
1406
1407 mesh.nmeshes = 0;
1408 mesh.meshes = (unsigned int*)rcAlloc(sizeof(unsigned int)*maxMeshes*4, RC_ALLOC_PERM);
1409 if (!mesh.meshes)
1410 {
1411 ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'pmdtl.meshes' (%d).", maxMeshes*4);
1412 return false;
1413 }
1414
1415 mesh.ntris = 0;
1416 mesh.tris = (unsigned char*)rcAlloc(sizeof(unsigned char)*maxTris*4, RC_ALLOC_PERM);
1417 if (!mesh.tris)
1418 {
1419 ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.tris' (%d).", maxTris*4);
1420 return false;
1421 }
1422
1423 mesh.nverts = 0;
1424 mesh.verts = (float*)rcAlloc(sizeof(float)*maxVerts*3, RC_ALLOC_PERM);
1425 if (!mesh.verts)
1426 {
1427 ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.verts' (%d).", maxVerts*3);
1428 return false;
1429 }
1430
1431 // Merge datas.
1432 for (int i = 0; i < nmeshes; ++i)
1433 {
1434 rcPolyMeshDetail* dm = meshes[i];
1435 if (!dm) continue;
1436 for (int j = 0; j < dm->nmeshes; ++j)
1437 {
1438 unsigned int* dst = &mesh.meshes[mesh.nmeshes*4];
1439 unsigned int* src = &dm->meshes[j*4];
1440 dst[0] = (unsigned int)mesh.nverts+src[0];
1441 dst[1] = src[1];
1442 dst[2] = (unsigned int)mesh.ntris+src[2];
1443 dst[3] = src[3];
1444 mesh.nmeshes++;
1445 }
1446
1447 for (int k = 0; k < dm->nverts; ++k)
1448 {
1449 rcVcopy(&mesh.verts[mesh.nverts*3], &dm->verts[k*3]);
1450 mesh.nverts++;
1451 }
1452 for (int k = 0; k < dm->ntris; ++k)
1453 {
1454 mesh.tris[mesh.ntris*4+0] = dm->tris[k*4+0];
1455 mesh.tris[mesh.ntris*4+1] = dm->tris[k*4+1];
1456 mesh.tris[mesh.ntris*4+2] = dm->tris[k*4+2];
1457 mesh.tris[mesh.ntris*4+3] = dm->tris[k*4+3];
1458 mesh.ntris++;
1459 }
1460 }
1461
1462 return true;
1463}
1464