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 | |
29 | static const unsigned RC_UNSET_HEIGHT = 0xffff; |
30 | |
31 | struct 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 | |
40 | inline float vdot2(const float* a, const float* b) |
41 | { |
42 | return a[0]*b[0] + a[2]*b[2]; |
43 | } |
44 | |
45 | inline 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 | |
52 | inline float vdist2(const float* p, const float* q) |
53 | { |
54 | return sqrtf(vdistSq2(p,q)); |
55 | } |
56 | |
57 | inline 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 | |
66 | static 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 | |
95 | static 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 | |
123 | static 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 | |
147 | static 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 | |
168 | static 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 | |
184 | static 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 | |
202 | static 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 | |
283 | enum EdgeValues |
284 | { |
285 | EV_UNDEF = -1, |
286 | EV_HULL = -2 |
287 | }; |
288 | |
289 | static 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 | |
300 | static 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 | |
325 | static 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 | |
333 | static 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 | |
347 | static 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 | |
362 | static 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 | |
458 | static 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. |
535 | static 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). |
556 | inline int prev(int i, int n) { return i-1 >= 0 ? i-1 : n-1; } |
557 | inline int next(int i, int n) { return i+1 < n ? i+1 : 0; } |
558 | |
559 | static 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 | |
627 | inline float getJitterX(const int i) |
628 | { |
629 | return (((i * 0x8da6b343) & 0xffff) / 65535.0f * 2.0f) - 1.0f; |
630 | } |
631 | |
632 | inline float getJitterY(const int i) |
633 | { |
634 | return (((i * 0xd8163841) & 0xffff) / 65535.0f * 2.0f) - 1.0f; |
635 | } |
636 | |
637 | static 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 | |
882 | static 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 | |
1015 | static 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 | |
1023 | static 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 | |
1140 | static 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 | |
1155 | static 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 |
1170 | bool 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 |
1389 | bool 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 | |