← Back to branch summary

~siretart/ubuntu/utopic/blender/libav10

« back to all changes in this revision

Viewing changes to extern/recastnavigation/Recast/Source/RecastContour.cpp

  • Committer: Package Import Robot
  • Author(s): Matteo F. Vescovi
  • Date: 2012-07-23 08:54:18 UTC
  • mfrom: (14.2.16 sid)
  • mto: (14.2.19 sid)
  • mto: This revision was merged to the branch mainline in revision 42.
  • Revision ID: package-import@ubuntu.com-20120723085418-9foz30v6afaf5ffs
Tags: 2.63a-2
http://bugs.debian.org/658075
* debian/: Cycles support added (Closes: #658075)
  For now, this top feature has been enabled only
  on [any-amd64 any-i386] architectures because
  of OpenImageIO failing on all others
* debian/: scripts installation path changed
  from /usr/lib to /usr/share:
  + debian/patches/: patchset re-worked for path changing
  + debian/control: "Breaks" field added on yafaray-exporter

Show diffs side-by-side

added added

removed removed

Lines of Context:
extern/recastnavigation/Recast/Source/RecastContour.cpp
 
1
//
 
2
// Copyright (c) 2009-2010 Mikko Mononen memon@inside.org
 
3
//
 
4
// This software is provided 'as-is', without any express or implied
 
5
// warranty.  In no event will the authors be held liable for any damages
 
6
// arising from the use of this software.
 
7
// Permission is granted to anyone to use this software for any purpose,
 
8
// including commercial applications, and to alter it and redistribute it
 
9
// freely, subject to the following restrictions:
 
10
// 1. The origin of this software must not be misrepresented; you must not
 
11
//    claim that you wrote the original software. If you use this software
 
12
//    in a product, an acknowledgment in the product documentation would be
 
13
//    appreciated but is not required.
 
14
// 2. Altered source versions must be plainly marked as such, and must not be
 
15
//    misrepresented as being the original software.
 
16
// 3. This notice may not be removed or altered from any source distribution.
 
17
//
 
18
 
 
19
#define _USE_MATH_DEFINES
 
20
#include <math.h>
 
21
#include <string.h>
 
22
#include <stdio.h>
 
23
#include "Recast.h"
 
24
#include "RecastAlloc.h"
 
25
#include "RecastAssert.h"
 
26
 
 
27
 
 
28
static int getCornerHeight(int x, int y, int i, int dir,
 
29
                                                   const rcCompactHeightfield& chf,
 
30
                                                   bool& isBorderVertex)
 
31
{
 
32
        const rcCompactSpan& s = chf.spans[i];
 
33
        int ch = (int)s.y;
 
34
        int dirp = (dir+1) & 0x3;
 
35
        
 
36
        unsigned int regs[4] = {0,0,0,0};
 
37
        
 
38
        // Combine region and area codes in order to prevent
 
39
        // border vertices which are in between two areas to be removed. 
 
40
        regs[0] = chf.spans[i].reg | (chf.areas[i] << 16);
 
41
        
 
42
        if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
 
43
        {
 
44
                const int ax = x + rcGetDirOffsetX(dir);
 
45
                const int ay = y + rcGetDirOffsetY(dir);
 
46
                const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dir);
 
47
                const rcCompactSpan& as = chf.spans[ai];
 
48
                ch = rcMax(ch, (int)as.y);
 
49
                regs[1] = chf.spans[ai].reg | (chf.areas[ai] << 16);
 
50
                if (rcGetCon(as, dirp) != RC_NOT_CONNECTED)
 
51
                {
 
52
                        const int ax2 = ax + rcGetDirOffsetX(dirp);
 
53
                        const int ay2 = ay + rcGetDirOffsetY(dirp);
 
54
                        const int ai2 = (int)chf.cells[ax2+ay2*chf.width].index + rcGetCon(as, dirp);
 
55
                        const rcCompactSpan& as2 = chf.spans[ai2];
 
56
                        ch = rcMax(ch, (int)as2.y);
 
57
                        regs[2] = chf.spans[ai2].reg | (chf.areas[ai2] << 16);
 
58
                }
 
59
        }
 
60
        if (rcGetCon(s, dirp) != RC_NOT_CONNECTED)
 
61
        {
 
62
                const int ax = x + rcGetDirOffsetX(dirp);
 
63
                const int ay = y + rcGetDirOffsetY(dirp);
 
64
                const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dirp);
 
65
                const rcCompactSpan& as = chf.spans[ai];
 
66
                ch = rcMax(ch, (int)as.y);
 
67
                regs[3] = chf.spans[ai].reg | (chf.areas[ai] << 16);
 
68
                if (rcGetCon(as, dir) != RC_NOT_CONNECTED)
 
69
                {
 
70
                        const int ax2 = ax + rcGetDirOffsetX(dir);
 
71
                        const int ay2 = ay + rcGetDirOffsetY(dir);
 
72
                        const int ai2 = (int)chf.cells[ax2+ay2*chf.width].index + rcGetCon(as, dir);
 
73
                        const rcCompactSpan& as2 = chf.spans[ai2];
 
74
                        ch = rcMax(ch, (int)as2.y);
 
75
                        regs[2] = chf.spans[ai2].reg | (chf.areas[ai2] << 16);
 
76
                }
 
77
        }
 
78
 
 
79
        // Check if the vertex is special edge vertex, these vertices will be removed later.
 
80
        for (int j = 0; j < 4; ++j)
 
81
        {
 
82
                const int a = j;
 
83
                const int b = (j+1) & 0x3;
 
84
                const int c = (j+2) & 0x3;
 
85
                const int d = (j+3) & 0x3;
 
86
                
 
87
                // The vertex is a border vertex there are two same exterior cells in a row,
 
88
                // followed by two interior cells and none of the regions are out of bounds.
 
89
                const bool twoSameExts = (regs[a] & regs[b] & RC_BORDER_REG) != 0 && regs[a] == regs[b];
 
90
                const bool twoInts = ((regs[c] | regs[d]) & RC_BORDER_REG) == 0;
 
91
                const bool intsSameArea = (regs[c]>>16) == (regs[d]>>16);
 
92
                const bool noZeros = regs[a] != 0 && regs[b] != 0 && regs[c] != 0 && regs[d] != 0;
 
93
                if (twoSameExts && twoInts && intsSameArea && noZeros)
 
94
                {
 
95
                        isBorderVertex = true;
 
96
                        break;
 
97
                }
 
98
        }
 
99
        
 
100
        return ch;
 
101
}
 
102
 
 
103
static void walkContour(int x, int y, int i,
 
104
                                                rcCompactHeightfield& chf,
 
105
                                                unsigned char* flags, rcIntArray& points)
 
106
{
 
107
        // Choose the first non-connected edge
 
108
        unsigned char dir = 0;
 
109
        while ((flags[i] & (1 << dir)) == 0)
 
110
                dir++;
 
111
        
 
112
        unsigned char startDir = dir;
 
113
        int starti = i;
 
114
        
 
115
        const unsigned char area = chf.areas[i];
 
116
        
 
117
        int iter = 0;
 
118
        while (++iter < 40000)
 
119
        {
 
120
                if (flags[i] & (1 << dir))
 
121
                {
 
122
                        // Choose the edge corner
 
123
                        bool isBorderVertex = false;
 
124
                        bool isAreaBorder = false;
 
125
                        int px = x;
 
126
                        int py = getCornerHeight(x, y, i, dir, chf, isBorderVertex);
 
127
                        int pz = y;
 
128
                        switch(dir)
 
129
                        {
 
130
                                case 0: pz++; break;
 
131
                                case 1: px++; pz++; break;
 
132
                                case 2: px++; break;
 
133
                        }
 
134
                        int r = 0;
 
135
                        const rcCompactSpan& s = chf.spans[i];
 
136
                        if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
 
137
                        {
 
138
                                const int ax = x + rcGetDirOffsetX(dir);
 
139
                                const int ay = y + rcGetDirOffsetY(dir);
 
140
                                const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dir);
 
141
                                r = (int)chf.spans[ai].reg;
 
142
                                if (area != chf.areas[ai])
 
143
                                        isAreaBorder = true;
 
144
                        }
 
145
                        if (isBorderVertex)
 
146
                                r |= RC_BORDER_VERTEX;
 
147
                        if (isAreaBorder)
 
148
                                r |= RC_AREA_BORDER;
 
149
                        points.push(px);
 
150
                        points.push(py);
 
151
                        points.push(pz);
 
152
                        points.push(r);
 
153
                        
 
154
                        flags[i] &= ~(1 << dir); // Remove visited edges
 
155
                        dir = (dir+1) & 0x3;  // Rotate CW
 
156
                }
 
157
                else
 
158
                {
 
159
                        int ni = -1;
 
160
                        const int nx = x + rcGetDirOffsetX(dir);
 
161
                        const int ny = y + rcGetDirOffsetY(dir);
 
162
                        const rcCompactSpan& s = chf.spans[i];
 
163
                        if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
 
164
                        {
 
165
                                const rcCompactCell& nc = chf.cells[nx+ny*chf.width];
 
166
                                ni = (int)nc.index + rcGetCon(s, dir);
 
167
                        }
 
168
                        if (ni == -1)
 
169
                        {
 
170
                                // Should not happen.
 
171
                                return;
 
172
                        }
 
173
                        x = nx;
 
174
                        y = ny;
 
175
                        i = ni;
 
176
                        dir = (dir+3) & 0x3;    // Rotate CCW
 
177
                }
 
178
                
 
179
                if (starti == i && startDir == dir)
 
180
                {
 
181
                        break;
 
182
                }
 
183
        }
 
184
}
 
185
 
 
186
static float distancePtSeg(const int x, const int z,
 
187
                                                   const int px, const int pz,
 
188
                                                   const int qx, const int qz)
 
189
{
 
190
/*      float pqx = (float)(qx - px);
 
191
        float pqy = (float)(qy - py);
 
192
        float pqz = (float)(qz - pz);
 
193
        float dx = (float)(x - px);
 
194
        float dy = (float)(y - py);
 
195
        float dz = (float)(z - pz);
 
196
        float d = pqx*pqx + pqy*pqy + pqz*pqz;
 
197
        float t = pqx*dx + pqy*dy + pqz*dz;
 
198
        if (d > 0)
 
199
                t /= d;
 
200
        if (t < 0)
 
201
                t = 0;
 
202
        else if (t > 1)
 
203
                t = 1;
 
204
        
 
205
        dx = px + t*pqx - x;
 
206
        dy = py + t*pqy - y;
 
207
        dz = pz + t*pqz - z;
 
208
        
 
209
        return dx*dx + dy*dy + dz*dz;*/
 
210
 
 
211
        float pqx = (float)(qx - px);
 
212
        float pqz = (float)(qz - pz);
 
213
        float dx = (float)(x - px);
 
214
        float dz = (float)(z - pz);
 
215
        float d = pqx*pqx + pqz*pqz;
 
216
        float t = pqx*dx + pqz*dz;
 
217
        if (d > 0)
 
218
                t /= d;
 
219
        if (t < 0)
 
220
                t = 0;
 
221
        else if (t > 1)
 
222
                t = 1;
 
223
        
 
224
        dx = px + t*pqx - x;
 
225
        dz = pz + t*pqz - z;
 
226
        
 
227
        return dx*dx + dz*dz;
 
228
}
 
229
 
 
230
static void simplifyContour(rcIntArray& points, rcIntArray& simplified,
 
231
                                                        const float maxError, const int maxEdgeLen, const int buildFlags)
 
232
{
 
233
        // Add initial points.
 
234
        bool hasConnections = false;
 
235
        for (int i = 0; i < points.size(); i += 4)
 
236
        {
 
237
                if ((points[i+3] & RC_CONTOUR_REG_MASK) != 0)
 
238
                {
 
239
                        hasConnections = true;
 
240
                        break;
 
241
                }
 
242
        }
 
243
        
 
244
        if (hasConnections)
 
245
        {
 
246
                // The contour has some portals to other regions.
 
247
                // Add a new point to every location where the region changes.
 
248
                for (int i = 0, ni = points.size()/4; i < ni; ++i)
 
249
                {
 
250
                        int ii = (i+1) % ni;
 
251
                        const bool differentRegs = (points[i*4+3] & RC_CONTOUR_REG_MASK) != (points[ii*4+3] & RC_CONTOUR_REG_MASK);
 
252
                        const bool areaBorders = (points[i*4+3] & RC_AREA_BORDER) != (points[ii*4+3] & RC_AREA_BORDER);
 
253
                        if (differentRegs || areaBorders)
 
254
                        {
 
255
                                simplified.push(points[i*4+0]);
 
256
                                simplified.push(points[i*4+1]);
 
257
                                simplified.push(points[i*4+2]);
 
258
                                simplified.push(i);
 
259
                        }
 
260
                }       
 
261
        }
 
262
        
 
263
        if (simplified.size() == 0)
 
264
        {
 
265
                // If there is no connections at all,
 
266
                // create some initial points for the simplification process. 
 
267
                // Find lower-left and upper-right vertices of the contour.
 
268
                int llx = points[0];
 
269
                int lly = points[1];
 
270
                int llz = points[2];
 
271
                int lli = 0;
 
272
                int urx = points[0];
 
273
                int ury = points[1];
 
274
                int urz = points[2];
 
275
                int uri = 0;
 
276
                for (int i = 0; i < points.size(); i += 4)
 
277
                {
 
278
                        int x = points[i+0];
 
279
                        int y = points[i+1];
 
280
                        int z = points[i+2];
 
281
                        if (x < llx || (x == llx && z < llz))
 
282
                        {
 
283
                                llx = x;
 
284
                                lly = y;
 
285
                                llz = z;
 
286
                                lli = i/4;
 
287
                        }
 
288
                        if (x > urx || (x == urx && z > urz))
 
289
                        {
 
290
                                urx = x;
 
291
                                ury = y;
 
292
                                urz = z;
 
293
                                uri = i/4;
 
294
                        }
 
295
                }
 
296
                simplified.push(llx);
 
297
                simplified.push(lly);
 
298
                simplified.push(llz);
 
299
                simplified.push(lli);
 
300
                
 
301
                simplified.push(urx);
 
302
                simplified.push(ury);
 
303
                simplified.push(urz);
 
304
                simplified.push(uri);
 
305
        }
 
306
        
 
307
        // Add points until all raw points are within
 
308
        // error tolerance to the simplified shape.
 
309
        const int pn = points.size()/4;
 
310
        for (int i = 0; i < simplified.size()/4; )
 
311
        {
 
312
                int ii = (i+1) % (simplified.size()/4);
 
313
                
 
314
                const int ax = simplified[i*4+0];
 
315
                const int az = simplified[i*4+2];
 
316
                const int ai = simplified[i*4+3];
 
317
                
 
318
                const int bx = simplified[ii*4+0];
 
319
                const int bz = simplified[ii*4+2];
 
320
                const int bi = simplified[ii*4+3];
 
321
 
 
322
                // Find maximum deviation from the segment.
 
323
                float maxd = 0;
 
324
                int maxi = -1;
 
325
                int ci, cinc, endi;
 
326
                
 
327
                // Traverse the segment in lexilogical order so that the
 
328
                // max deviation is calculated similarly when traversing
 
329
                // opposite segments.
 
330
                if (bx > ax || (bx == ax && bz > az))
 
331
                {
 
332
                        cinc = 1;
 
333
                        ci = (ai+cinc) % pn;
 
334
                        endi = bi;
 
335
                }
 
336
                else
 
337
                {
 
338
                        cinc = pn-1;
 
339
                        ci = (bi+cinc) % pn;
 
340
                        endi = ai;
 
341
                }
 
342
                
 
343
                // Tessellate only outer edges or edges between areas.
 
344
                if ((points[ci*4+3] & RC_CONTOUR_REG_MASK) == 0 ||
 
345
                        (points[ci*4+3] & RC_AREA_BORDER))
 
346
                {
 
347
                        while (ci != endi)
 
348
                        {
 
349
                                float d = distancePtSeg(points[ci*4+0], points[ci*4+2], ax, az, bx, bz);
 
350
                                if (d > maxd)
 
351
                                {
 
352
                                        maxd = d;
 
353
                                        maxi = ci;
 
354
                                }
 
355
                                ci = (ci+cinc) % pn;
 
356
                        }
 
357
                }
 
358
                
 
359
                
 
360
                // If the max deviation is larger than accepted error,
 
361
                // add new point, else continue to next segment.
 
362
                if (maxi != -1 && maxd > (maxError*maxError))
 
363
                {
 
364
                        // Add space for the new point.
 
365
                        simplified.resize(simplified.size()+4);
 
366
                        const int n = simplified.size()/4;
 
367
                        for (int j = n-1; j > i; --j)
 
368
                        {
 
369
                                simplified[j*4+0] = simplified[(j-1)*4+0];
 
370
                                simplified[j*4+1] = simplified[(j-1)*4+1];
 
371
                                simplified[j*4+2] = simplified[(j-1)*4+2];
 
372
                                simplified[j*4+3] = simplified[(j-1)*4+3];
 
373
                        }
 
374
                        // Add the point.
 
375
                        simplified[(i+1)*4+0] = points[maxi*4+0];
 
376
                        simplified[(i+1)*4+1] = points[maxi*4+1];
 
377
                        simplified[(i+1)*4+2] = points[maxi*4+2];
 
378
                        simplified[(i+1)*4+3] = maxi;
 
379
                }
 
380
                else
 
381
                {
 
382
                        ++i;
 
383
                }
 
384
        }
 
385
        
 
386
        // Split too long edges.
 
387
        if (maxEdgeLen > 0 && (buildFlags & (RC_CONTOUR_TESS_WALL_EDGES|RC_CONTOUR_TESS_AREA_EDGES)) != 0)
 
388
        {
 
389
                for (int i = 0; i < simplified.size()/4; )
 
390
                {
 
391
                        const int ii = (i+1) % (simplified.size()/4);
 
392
                        
 
393
                        const int ax = simplified[i*4+0];
 
394
                        const int az = simplified[i*4+2];
 
395
                        const int ai = simplified[i*4+3];
 
396
                        
 
397
                        const int bx = simplified[ii*4+0];
 
398
                        const int bz = simplified[ii*4+2];
 
399
                        const int bi = simplified[ii*4+3];
 
400
 
 
401
                        // Find maximum deviation from the segment.
 
402
                        int maxi = -1;
 
403
                        int ci = (ai+1) % pn;
 
404
 
 
405
                        // Tessellate only outer edges or edges between areas.
 
406
                        bool tess = false;
 
407
                        // Wall edges.
 
408
                        if ((buildFlags & RC_CONTOUR_TESS_WALL_EDGES) && (points[ci*4+3] & RC_CONTOUR_REG_MASK) == 0)
 
409
                                tess = true;
 
410
                        // Edges between areas.
 
411
                        if ((buildFlags & RC_CONTOUR_TESS_AREA_EDGES) && (points[ci*4+3] & RC_AREA_BORDER))
 
412
                                tess = true;
 
413
                        
 
414
                        if (tess)
 
415
                        {
 
416
                                int dx = bx - ax;
 
417
                                int dz = bz - az;
 
418
                                if (dx*dx + dz*dz > maxEdgeLen*maxEdgeLen)
 
419
                                {
 
420
                                        // Round based on the segments in lexilogical order so that the
 
421
                                        // max tesselation is consistent regardles in which direction
 
422
                                        // segments are traversed.
 
423
                                        if (bx > ax || (bx == ax && bz > az))
 
424
                                        {
 
425
                                                const int n = bi < ai ? (bi+pn - ai) : (bi - ai);
 
426
                                                maxi = (ai + n/2) % pn;
 
427
                                        }
 
428
                                        else
 
429
                                        {
 
430
                                                const int n = bi < ai ? (bi+pn - ai) : (bi - ai);
 
431
                                                maxi = (ai + (n+1)/2) % pn;
 
432
                                        }
 
433
                                }
 
434
                        }
 
435
                        
 
436
                        // If the max deviation is larger than accepted error,
 
437
                        // add new point, else continue to next segment.
 
438
                        if (maxi != -1)
 
439
                        {
 
440
                                // Add space for the new point.
 
441
                                simplified.resize(simplified.size()+4);
 
442
                                const int n = simplified.size()/4;
 
443
                                for (int j = n-1; j > i; --j)
 
444
                                {
 
445
                                        simplified[j*4+0] = simplified[(j-1)*4+0];
 
446
                                        simplified[j*4+1] = simplified[(j-1)*4+1];
 
447
                                        simplified[j*4+2] = simplified[(j-1)*4+2];
 
448
                                        simplified[j*4+3] = simplified[(j-1)*4+3];
 
449
                                }
 
450
                                // Add the point.
 
451
                                simplified[(i+1)*4+0] = points[maxi*4+0];
 
452
                                simplified[(i+1)*4+1] = points[maxi*4+1];
 
453
                                simplified[(i+1)*4+2] = points[maxi*4+2];
 
454
                                simplified[(i+1)*4+3] = maxi;
 
455
                        }
 
456
                        else
 
457
                        {
 
458
                                ++i;
 
459
                        }
 
460
                }
 
461
        }
 
462
        
 
463
        for (int i = 0; i < simplified.size()/4; ++i)
 
464
        {
 
465
                // The edge vertex flag is take from the current raw point,
 
466
                // and the neighbour region is take from the next raw point.
 
467
                const int ai = (simplified[i*4+3]+1) % pn;
 
468
                const int bi = simplified[i*4+3];
 
469
                simplified[i*4+3] = (points[ai*4+3] & RC_CONTOUR_REG_MASK) | (points[bi*4+3] & RC_BORDER_VERTEX);
 
470
        }
 
471
        
 
472
}
 
473
 
 
474
static void removeDegenerateSegments(rcIntArray& simplified)
 
475
{
 
476
        // Remove adjacent vertices which are equal on xz-plane,
 
477
        // or else the triangulator will get confused.
 
478
        for (int i = 0; i < simplified.size()/4; ++i)
 
479
        {
 
480
                int ni = i+1;
 
481
                if (ni >= (simplified.size()/4))
 
482
                        ni = 0;
 
483
                        
 
484
                if (simplified[i*4+0] == simplified[ni*4+0] &&
 
485
                        simplified[i*4+2] == simplified[ni*4+2])
 
486
                {
 
487
                        // Degenerate segment, remove.
 
488
                        for (int j = i; j < simplified.size()/4-1; ++j)
 
489
                        {
 
490
                                simplified[j*4+0] = simplified[(j+1)*4+0];
 
491
                                simplified[j*4+1] = simplified[(j+1)*4+1];
 
492
                                simplified[j*4+2] = simplified[(j+1)*4+2];
 
493
                                simplified[j*4+3] = simplified[(j+1)*4+3];
 
494
                        }
 
495
                        simplified.resize(simplified.size()-4);
 
496
                }
 
497
        }
 
498
}
 
499
 
 
500
static int calcAreaOfPolygon2D(const int* verts, const int nverts)
 
501
{
 
502
        int area = 0;
 
503
        for (int i = 0, j = nverts-1; i < nverts; j=i++)
 
504
        {
 
505
                const int* vi = &verts[i*4];
 
506
                const int* vj = &verts[j*4];
 
507
                area += vi[0] * vj[2] - vj[0] * vi[2];
 
508
        }
 
509
        return (area+1) / 2;
 
510
}
 
511
 
 
512
inline bool ileft(const int* a, const int* b, const int* c)
 
513
{
 
514
        return (b[0] - a[0]) * (c[2] - a[2]) - (c[0] - a[0]) * (b[2] - a[2]) <= 0;
 
515
}
 
516
 
 
517
static void getClosestIndices(const int* vertsa, const int nvertsa,
 
518
                                                          const int* vertsb, const int nvertsb,
 
519
                                                          int& ia, int& ib)
 
520
{
 
521
        int closestDist = 0xfffffff;
 
522
        ia = -1, ib = -1;
 
523
        for (int i = 0; i < nvertsa; ++i)
 
524
        {
 
525
                const int in = (i+1) % nvertsa;
 
526
                const int ip = (i+nvertsa-1) % nvertsa;
 
527
                const int* va = &vertsa[i*4];
 
528
                const int* van = &vertsa[in*4];
 
529
                const int* vap = &vertsa[ip*4];
 
530
                
 
531
                for (int j = 0; j < nvertsb; ++j)
 
532
                {
 
533
                        const int* vb = &vertsb[j*4];
 
534
                        // vb must be "infront" of va.
 
535
                        if (ileft(vap,va,vb) && ileft(va,van,vb))
 
536
                        {
 
537
                                const int dx = vb[0] - va[0];
 
538
                                const int dz = vb[2] - va[2];
 
539
                                const int d = dx*dx + dz*dz;
 
540
                                if (d < closestDist)
 
541
                                {
 
542
                                        ia = i;
 
543
                                        ib = j;
 
544
                                        closestDist = d;
 
545
                                }
 
546
                        }
 
547
                }
 
548
        }
 
549
}
 
550
 
 
551
static bool mergeContours(rcContour& ca, rcContour& cb, int ia, int ib)
 
552
{
 
553
        const int maxVerts = ca.nverts + cb.nverts + 2;
 
554
        int* verts = (int*)rcAlloc(sizeof(int)*maxVerts*4, RC_ALLOC_PERM);
 
555
        if (!verts)
 
556
                return false;
 
557
 
 
558
        int nv = 0;
 
559
 
 
560
        // Copy contour A.
 
561
        for (int i = 0; i <= ca.nverts; ++i)
 
562
        {
 
563
                int* dst = &verts[nv*4];
 
564
                const int* src = &ca.verts[((ia+i)%ca.nverts)*4];
 
565
                dst[0] = src[0];
 
566
                dst[1] = src[1];
 
567
                dst[2] = src[2];
 
568
                dst[3] = src[3];
 
569
                nv++;
 
570
        }
 
571
 
 
572
        // Copy contour B
 
573
        for (int i = 0; i <= cb.nverts; ++i)
 
574
        {
 
575
                int* dst = &verts[nv*4];
 
576
                const int* src = &cb.verts[((ib+i)%cb.nverts)*4];
 
577
                dst[0] = src[0];
 
578
                dst[1] = src[1];
 
579
                dst[2] = src[2];
 
580
                dst[3] = src[3];
 
581
                nv++;
 
582
        }
 
583
        
 
584
        rcFree(ca.verts);
 
585
        ca.verts = verts;
 
586
        ca.nverts = nv;
 
587
 
 
588
        rcFree(cb.verts);
 
589
        cb.verts = 0;
 
590
        cb.nverts = 0;
 
591
        
 
592
        return true;
 
593
}
 
594
 
 
595
/// @par
 
596
///
 
597
/// The raw contours will match the region outlines exactly. The @p maxError and @p maxEdgeLen
 
598
/// parameters control how closely the simplified contours will match the raw contours.
 
599
///
 
600
/// Simplified contours are generated such that the vertices for portals between areas match up. 
 
601
/// (They are considered mandatory vertices.)
 
602
///
 
603
/// Setting @p maxEdgeLength to zero will disabled the edge length feature.
 
604
/// 
 
605
/// See the #rcConfig documentation for more information on the configuration parameters.
 
606
/// 
 
607
/// @see rcAllocContourSet, rcCompactHeightfield, rcContourSet, rcConfig
 
608
bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf,
 
609
                                         const float maxError, const int maxEdgeLen,
 
610
                                         rcContourSet& cset, const int buildFlags)
 
611
{
 
612
        rcAssert(ctx);
 
613
        
 
614
        const int w = chf.width;
 
615
        const int h = chf.height;
 
616
        const int borderSize = chf.borderSize;
 
617
        
 
618
        ctx->startTimer(RC_TIMER_BUILD_CONTOURS);
 
619
        
 
620
        rcVcopy(cset.bmin, chf.bmin);
 
621
        rcVcopy(cset.bmax, chf.bmax);
 
622
        if (borderSize > 0)
 
623
        {
 
624
                // If the heightfield was build with bordersize, remove the offset.
 
625
                const float pad = borderSize*chf.cs;
 
626
                cset.bmin[0] += pad;
 
627
                cset.bmin[2] += pad;
 
628
                cset.bmax[0] -= pad;
 
629
                cset.bmax[2] -= pad;
 
630
        }
 
631
        cset.cs = chf.cs;
 
632
        cset.ch = chf.ch;
 
633
        cset.width = chf.width - chf.borderSize*2;
 
634
        cset.height = chf.height - chf.borderSize*2;
 
635
        cset.borderSize = chf.borderSize;
 
636
        
 
637
        int maxContours = rcMax((int)chf.maxRegions, 8);
 
638
        cset.conts = (rcContour*)rcAlloc(sizeof(rcContour)*maxContours, RC_ALLOC_PERM);
 
639
        if (!cset.conts)
 
640
                return false;
 
641
        cset.nconts = 0;
 
642
        
 
643
        rcScopedDelete<unsigned char> flags = (unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP);
 
644
        if (!flags)
 
645
        {
 
646
                ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'flags' (%d).", chf.spanCount);
 
647
                return false;
 
648
        }
 
649
        
 
650
        ctx->startTimer(RC_TIMER_BUILD_CONTOURS_TRACE);
 
651
        
 
652
        // Mark boundaries.
 
653
        for (int y = 0; y < h; ++y)
 
654
        {
 
655
                for (int x = 0; x < w; ++x)
 
656
                {
 
657
                        const rcCompactCell& c = chf.cells[x+y*w];
 
658
                        for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
 
659
                        {
 
660
                                unsigned char res = 0;
 
661
                                const rcCompactSpan& s = chf.spans[i];
 
662
                                if (!chf.spans[i].reg || (chf.spans[i].reg & RC_BORDER_REG))
 
663
                                {
 
664
                                        flags[i] = 0;
 
665
                                        continue;
 
666
                                }
 
667
                                for (int dir = 0; dir < 4; ++dir)
 
668
                                {
 
669
                                        unsigned short r = 0;
 
670
                                        if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
 
671
                                        {
 
672
                                                const int ax = x + rcGetDirOffsetX(dir);
 
673
                                                const int ay = y + rcGetDirOffsetY(dir);
 
674
                                                const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);
 
675
                                                r = chf.spans[ai].reg;
 
676
                                        }
 
677
                                        if (r == chf.spans[i].reg)
 
678
                                                res |= (1 << dir);
 
679
                                }
 
680
                                flags[i] = res ^ 0xf; // Inverse, mark non connected edges.
 
681
                        }
 
682
                }
 
683
        }
 
684
        
 
685
        ctx->stopTimer(RC_TIMER_BUILD_CONTOURS_TRACE);
 
686
        
 
687
        rcIntArray verts(256);
 
688
        rcIntArray simplified(64);
 
689
        
 
690
        for (int y = 0; y < h; ++y)
 
691
        {
 
692
                for (int x = 0; x < w; ++x)
 
693
                {
 
694
                        const rcCompactCell& c = chf.cells[x+y*w];
 
695
                        for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
 
696
                        {
 
697
                                if (flags[i] == 0 || flags[i] == 0xf)
 
698
                                {
 
699
                                        flags[i] = 0;
 
700
                                        continue;
 
701
                                }
 
702
                                const unsigned short reg = chf.spans[i].reg;
 
703
                                if (!reg || (reg & RC_BORDER_REG))
 
704
                                        continue;
 
705
                                const unsigned char area = chf.areas[i];
 
706
                                
 
707
                                verts.resize(0);
 
708
                                simplified.resize(0);
 
709
 
 
710
                                ctx->startTimer(RC_TIMER_BUILD_CONTOURS_TRACE);
 
711
                                walkContour(x, y, i, chf, flags, verts);
 
712
                                ctx->stopTimer(RC_TIMER_BUILD_CONTOURS_TRACE);
 
713
 
 
714
                                ctx->startTimer(RC_TIMER_BUILD_CONTOURS_SIMPLIFY);
 
715
                                simplifyContour(verts, simplified, maxError, maxEdgeLen, buildFlags);
 
716
                                removeDegenerateSegments(simplified);
 
717
                                ctx->stopTimer(RC_TIMER_BUILD_CONTOURS_SIMPLIFY);
 
718
                                
 
719
 
 
720
                                // Store region->contour remap info.
 
721
                                // Create contour.
 
722
                                if (simplified.size()/4 >= 3)
 
723
                                {
 
724
                                        if (cset.nconts >= maxContours)
 
725
                                        {
 
726
                                                // Allocate more contours.
 
727
                                                // This can happen when there are tiny holes in the heightfield.
 
728
                                                const int oldMax = maxContours;
 
729
                                                maxContours *= 2;
 
730
                                                rcContour* newConts = (rcContour*)rcAlloc(sizeof(rcContour)*maxContours, RC_ALLOC_PERM);
 
731
                                                for (int j = 0; j < cset.nconts; ++j)
 
732
                                                {
 
733
                                                        newConts[j] = cset.conts[j];
 
734
                                                        // Reset source pointers to prevent data deletion.
 
735
                                                        cset.conts[j].verts = 0;
 
736
                                                        cset.conts[j].rverts = 0;
 
737
                                                }
 
738
                                                rcFree(cset.conts);
 
739
                                                cset.conts = newConts;
 
740
                                        
 
741
                                                ctx->log(RC_LOG_WARNING, "rcBuildContours: Expanding max contours from %d to %d.", oldMax, maxContours);
 
742
                                        }
 
743
                                                
 
744
                                        rcContour* cont = &cset.conts[cset.nconts++];
 
745
                                        
 
746
                                        cont->nverts = simplified.size()/4;
 
747
                                        cont->verts = (int*)rcAlloc(sizeof(int)*cont->nverts*4, RC_ALLOC_PERM);
 
748
                                        if (!cont->verts)
 
749
                                        {
 
750
                                                ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'verts' (%d).", cont->nverts);
 
751
                                                return false;
 
752
                                        }
 
753
                                        memcpy(cont->verts, &simplified[0], sizeof(int)*cont->nverts*4);
 
754
                                        if (borderSize > 0)
 
755
                                        {
 
756
                                                // If the heightfield was build with bordersize, remove the offset.
 
757
                                                for (int i = 0; i < cont->nverts; ++i)
 
758
                                                {
 
759
                                                        int* v = &cont->verts[i*4];
 
760
                                                        v[0] -= borderSize;
 
761
                                                        v[2] -= borderSize;
 
762
                                                }
 
763
                                        }
 
764
                                        
 
765
                                        cont->nrverts = verts.size()/4;
 
766
                                        cont->rverts = (int*)rcAlloc(sizeof(int)*cont->nrverts*4, RC_ALLOC_PERM);
 
767
                                        if (!cont->rverts)
 
768
                                        {
 
769
                                                ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'rverts' (%d).", cont->nrverts);
 
770
                                                return false;
 
771
                                        }
 
772
                                        memcpy(cont->rverts, &verts[0], sizeof(int)*cont->nrverts*4);
 
773
                                        if (borderSize > 0)
 
774
                                        {
 
775
                                                // If the heightfield was build with bordersize, remove the offset.
 
776
                                                for (int i = 0; i < cont->nrverts; ++i)
 
777
                                                {
 
778
                                                        int* v = &cont->rverts[i*4];
 
779
                                                        v[0] -= borderSize;
 
780
                                                        v[2] -= borderSize;
 
781
                                                }
 
782
                                        }
 
783
                                        
 
784
/*                                      cont->cx = cont->cy = cont->cz = 0;
 
785
                                        for (int i = 0; i < cont->nverts; ++i)
 
786
                                        {
 
787
                                                cont->cx += cont->verts[i*4+0];
 
788
                                                cont->cy += cont->verts[i*4+1];
 
789
                                                cont->cz += cont->verts[i*4+2];
 
790
                                        }
 
791
                                        cont->cx /= cont->nverts;
 
792
                                        cont->cy /= cont->nverts;
 
793
                                        cont->cz /= cont->nverts;*/
 
794
                                        
 
795
                                        cont->reg = reg;
 
796
                                        cont->area = area;
 
797
                                }
 
798
                        }
 
799
                }
 
800
        }
 
801
        
 
802
        // Check and merge droppings.
 
803
        // Sometimes the previous algorithms can fail and create several contours
 
804
        // per area. This pass will try to merge the holes into the main region.
 
805
        for (int i = 0; i < cset.nconts; ++i)
 
806
        {
 
807
                rcContour& cont = cset.conts[i];
 
808
                // Check if the contour is would backwards.
 
809
                if (calcAreaOfPolygon2D(cont.verts, cont.nverts) < 0)
 
810
                {
 
811
                        // Find another contour which has the same region ID.
 
812
                        int mergeIdx = -1;
 
813
                        for (int j = 0; j < cset.nconts; ++j)
 
814
                        {
 
815
                                if (i == j) continue;
 
816
                                if (cset.conts[j].nverts && cset.conts[j].reg == cont.reg)
 
817
                                {
 
818
                                        // Make sure the polygon is correctly oriented.
 
819
                                        if (calcAreaOfPolygon2D(cset.conts[j].verts, cset.conts[j].nverts))
 
820
                                        {
 
821
                                                mergeIdx = j;
 
822
                                                break;
 
823
                                        }
 
824
                                }
 
825
                        }
 
826
                        if (mergeIdx == -1)
 
827
                        {
 
828
                                ctx->log(RC_LOG_WARNING, "rcBuildContours: Could not find merge target for bad contour %d.", i);
 
829
                        }
 
830
                        else
 
831
                        {
 
832
                                rcContour& mcont = cset.conts[mergeIdx];
 
833
                                // Merge by closest points.
 
834
                                int ia = 0, ib = 0;
 
835
                                getClosestIndices(mcont.verts, mcont.nverts, cont.verts, cont.nverts, ia, ib);
 
836
                                if (ia == -1 || ib == -1)
 
837
                                {
 
838
                                        ctx->log(RC_LOG_WARNING, "rcBuildContours: Failed to find merge points for %d and %d.", i, mergeIdx);
 
839
                                        continue;
 
840
                                }
 
841
                                if (!mergeContours(mcont, cont, ia, ib))
 
842
                                {
 
843
                                        ctx->log(RC_LOG_WARNING, "rcBuildContours: Failed to merge contours %d and %d.", i, mergeIdx);
 
844
                                        continue;
 
845
                                }
 
846
                        }
 
847
                }
 
848
        }
 
849
        
 
850
        ctx->stopTimer(RC_TIMER_BUILD_CONTOURS);
 
851
        
 
852
        return true;
 
853
}