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