Subversion Repository Public Repository

Divide-Framework

This repository has no backups
This repository's network speed is throttled to 100KB/sec

Diff Revisions 336 vs 337 for /trunk/Source Code/Libs/src/ReCast/ReCast/Source/RecastMeshDetail.cpp

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