Fix selection when adding a primitive while already in edge/face-select mode
[blender-staging.git] / extern / recastnavigation / Recast / Source / RecastContour.cpp
1 //
2 // Copyright (c) 2009 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 "RecastLog.h"
25 #include "RecastTimer.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 short regs[4] = {0,0,0,0};
37         
38         regs[0] = s.reg;
39         
40         if (rcGetCon(s, dir) != 0xf)
41         {
42                 const int ax = x + rcGetDirOffsetX(dir);
43                 const int ay = y + rcGetDirOffsetY(dir);
44                 const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dir);
45                 const rcCompactSpan& as = chf.spans[ai];
46                 ch = rcMax(ch, (int)as.y);
47                 regs[1] = as.reg;
48                 if (rcGetCon(as, dirp) != 0xf)
49                 {
50                         const int ax2 = ax + rcGetDirOffsetX(dirp);
51                         const int ay2 = ay + rcGetDirOffsetY(dirp);
52                         const int ai2 = (int)chf.cells[ax2+ay2*chf.width].index + rcGetCon(as, dirp);
53                         const rcCompactSpan& as2 = chf.spans[ai2];
54                         ch = rcMax(ch, (int)as2.y);
55                         regs[2] = as2.reg;
56                 }
57         }
58         if (rcGetCon(s, dirp) != 0xf)
59         {
60                 const int ax = x + rcGetDirOffsetX(dirp);
61                 const int ay = y + rcGetDirOffsetY(dirp);
62                 const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dirp);
63                 const rcCompactSpan& as = chf.spans[ai];
64                 ch = rcMax(ch, (int)as.y);
65                 regs[3] = as.reg;
66                 if (rcGetCon(as, dir) != 0xf)
67                 {
68                         const int ax2 = ax + rcGetDirOffsetX(dir);
69                         const int ay2 = ay + rcGetDirOffsetY(dir);
70                         const int ai2 = (int)chf.cells[ax2+ay2*chf.width].index + rcGetCon(as, dir);
71                         const rcCompactSpan& as2 = chf.spans[ai2];
72                         ch = rcMax(ch, (int)as2.y);
73                         regs[2] = as2.reg;
74                 }
75         }
76
77         // Check if the vertex is special edge vertex, these vertices will be removed later.
78         for (int j = 0; j < 4; ++j)
79         {
80                 const int a = j;
81                 const int b = (j+1) & 0x3;
82                 const int c = (j+2) & 0x3;
83                 const int d = (j+3) & 0x3;
84                 
85                 // The vertex is a border vertex there are two same exterior cells in a row,
86                 // followed by two interior cells and none of the regions are out of bounds.
87                 const bool twoSameExts = (regs[a] & regs[b] & RC_BORDER_REG) != 0 && regs[a] == regs[b];
88                 const bool twoInts = ((regs[c] | regs[d]) & RC_BORDER_REG) == 0;
89                 const bool noZeros = regs[a] != 0 && regs[b] != 0 && regs[c] != 0 && regs[d] != 0;
90                 if (twoSameExts && twoInts && noZeros)
91                 {
92                         isBorderVertex = true;
93                         break;
94                 }
95         }
96         
97         return ch;
98 }
99
100 static void walkContour(int x, int y, int i,
101                                                 rcCompactHeightfield& chf,
102                                                 unsigned char* flags, rcIntArray& points)
103 {
104         // Choose the first non-connected edge
105         unsigned char dir = 0;
106         while ((flags[i] & (1 << dir)) == 0)
107                 dir++;
108         
109         unsigned char startDir = dir;
110         int starti = i;
111         
112         int iter = 0;
113         while (++iter < 40000)
114         {
115                 if (flags[i] & (1 << dir))
116                 {
117                         // Choose the edge corner
118                         bool isBorderVertex = false;
119                         int px = x;
120                         int py = getCornerHeight(x, y, i, dir, chf, isBorderVertex);
121                         int pz = y;
122                         switch(dir)
123                         {
124                                 case 0: pz++; break;
125                                 case 1: px++; pz++; break;
126                                 case 2: px++; break;
127                         }
128                         int r = 0;
129                         const rcCompactSpan& s = chf.spans[i];
130                         if (rcGetCon(s, dir) != 0xf)
131                         {
132                                 const int ax = x + rcGetDirOffsetX(dir);
133                                 const int ay = y + rcGetDirOffsetY(dir);
134                                 const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dir);
135                                 const rcCompactSpan& as = chf.spans[ai];
136                                 r = (int)as.reg;
137                         }
138                         if (isBorderVertex)
139                                 r |= RC_BORDER_VERTEX;
140                         points.push(px);
141                         points.push(py);
142                         points.push(pz);
143                         points.push(r);
144                         
145                         flags[i] &= ~(1 << dir); // Remove visited edges
146                         dir = (dir+1) & 0x3;  // Rotate CW
147                 }
148                 else
149                 {
150                         int ni = -1;
151                         const int nx = x + rcGetDirOffsetX(dir);
152                         const int ny = y + rcGetDirOffsetY(dir);
153                         const rcCompactSpan& s = chf.spans[i];
154                         if (rcGetCon(s, dir) != 0xf)
155                         {
156                                 const rcCompactCell& nc = chf.cells[nx+ny*chf.width];
157                                 ni = (int)nc.index + rcGetCon(s, dir);
158                         }
159                         if (ni == -1)
160                         {
161                                 // Should not happen.
162                                 return;
163                         }
164                         x = nx;
165                         y = ny;
166                         i = ni;
167                         dir = (dir+3) & 0x3;    // Rotate CCW
168                 }
169                 
170                 if (starti == i && startDir == dir)
171                 {
172                         break;
173                 }
174         }
175 }
176
177 static float distancePtSeg(int x, int y, int z,
178                                                    int px, int py, int pz,
179                                                    int qx, int qy, int qz)
180 {
181 /*      float pqx = (float)(qx - px);
182         float pqy = (float)(qy - py);
183         float pqz = (float)(qz - pz);
184         float dx = (float)(x - px);
185         float dy = (float)(y - py);
186         float dz = (float)(z - pz);
187         float d = pqx*pqx + pqy*pqy + pqz*pqz;
188         float t = pqx*dx + pqy*dy + pqz*dz;
189         if (d > 0)
190                 t /= d;
191         if (t < 0)
192                 t = 0;
193         else if (t > 1)
194                 t = 1;
195         
196         dx = px + t*pqx - x;
197         dy = py + t*pqy - y;
198         dz = pz + t*pqz - z;
199         
200         return dx*dx + dy*dy + dz*dz;*/
201
202         float pqx = (float)(qx - px);
203         float pqz = (float)(qz - pz);
204         float dx = (float)(x - px);
205         float dz = (float)(z - pz);
206         float d = pqx*pqx + pqz*pqz;
207         float t = pqx*dx + pqz*dz;
208         if (d > 0)
209                 t /= d;
210         if (t < 0)
211                 t = 0;
212         else if (t > 1)
213                 t = 1;
214         
215         dx = px + t*pqx - x;
216         dz = pz + t*pqz - z;
217         
218         return dx*dx + dz*dz;
219 }
220
221 static void simplifyContour(rcIntArray& points, rcIntArray& simplified, float maxError, int maxEdgeLen)
222 {
223         // Add initial points.
224         bool noConnections = true;
225         for (int i = 0; i < points.size(); i += 4)
226         {
227                 if ((points[i+3] & 0xffff) != 0)
228                 {
229                         noConnections = false;
230                         break;
231                 }
232         }
233         
234         if (noConnections)
235         {
236                 // If there is no connections at all,
237                 // create some initial points for the simplification process. 
238                 // Find lower-left and upper-right vertices of the contour.
239                 int llx = points[0];
240                 int lly = points[1];
241                 int llz = points[2];
242                 int lli = 0;
243                 int urx = points[0];
244                 int ury = points[1];
245                 int urz = points[2];
246                 int uri = 0;
247                 for (int i = 0; i < points.size(); i += 4)
248                 {
249                         int x = points[i+0];
250                         int y = points[i+1];
251                         int z = points[i+2];
252                         if (x < llx || (x == llx && z < llz))
253                         {
254                                 llx = x;
255                                 lly = y;
256                                 llz = z;
257                                 lli = i/4;
258                         }
259                         if (x >= urx || (x == urx && z > urz))
260                         {
261                                 urx = x;
262                                 ury = y;
263                                 urz = z;
264                                 uri = i/4;
265                         }
266                 }
267                 simplified.push(llx);
268                 simplified.push(lly);
269                 simplified.push(llz);
270                 simplified.push(lli);
271                 
272                 simplified.push(urx);
273                 simplified.push(ury);
274                 simplified.push(urz);
275                 simplified.push(uri);
276         }
277         else
278         {
279                 // The contour has some portals to other regions.
280                 // Add a new point to every location where the region changes.
281                 for (int i = 0, ni = points.size()/4; i < ni; ++i)
282                 {
283                         int ii = (i+1) % ni;
284                         if ((points[i*4+3] & 0xffff) != (points[ii*4+3] & 0xffff))
285                         {
286                                 simplified.push(points[i*4+0]);
287                                 simplified.push(points[i*4+1]);
288                                 simplified.push(points[i*4+2]);
289                                 simplified.push(i);
290                         }
291                 }       
292         }
293         
294         // Add points until all raw points are within
295         // error tolerance to the simplified shape.
296         const int pn = points.size()/4;
297         for (int i = 0; i < simplified.size()/4; )
298         {
299                 int ii = (i+1) % (simplified.size()/4);
300                 
301                 int ax = simplified[i*4+0];
302                 int ay = simplified[i*4+1];
303                 int az = simplified[i*4+2];
304                 int ai = simplified[i*4+3];
305                 
306                 int bx = simplified[ii*4+0];
307                 int by = simplified[ii*4+1];
308                 int bz = simplified[ii*4+2];
309                 int bi = simplified[ii*4+3];
310                 
311                 // Find maximum deviation from the segment.
312                 float maxd = 0;
313                 int maxi = -1;
314                 int ci = (ai+1) % pn;
315                 
316                 // Tesselate only outer edges.
317                 if ((points[ci*4+3] & 0xffff) == 0)
318                 {
319                         while (ci != bi)
320                         {
321                                 float d = distancePtSeg(points[ci*4+0], points[ci*4+1]/4, points[ci*4+2],
322                                                                                 ax, ay/4, az, bx, by/4, bz);
323                                 if (d > maxd)
324                                 {
325                                         maxd = d;
326                                         maxi = ci;
327                                 }
328                                 ci = (ci+1) % pn;
329                         }
330                 }
331                 
332                 
333                 // If the max deviation is larger than accepted error,
334                 // add new point, else continue to next segment.
335                 if (maxi != -1 && maxd > (maxError*maxError))
336                 {
337                         // Add space for the new point.
338                         simplified.resize(simplified.size()+4);
339                         int n = simplified.size()/4;
340                         for (int j = n-1; j > i; --j)
341                         {
342                                 simplified[j*4+0] = simplified[(j-1)*4+0];
343                                 simplified[j*4+1] = simplified[(j-1)*4+1];
344                                 simplified[j*4+2] = simplified[(j-1)*4+2];
345                                 simplified[j*4+3] = simplified[(j-1)*4+3];
346                         }
347                         // Add the point.
348                         simplified[(i+1)*4+0] = points[maxi*4+0];
349                         simplified[(i+1)*4+1] = points[maxi*4+1];
350                         simplified[(i+1)*4+2] = points[maxi*4+2];
351                         simplified[(i+1)*4+3] = maxi;
352                 }
353                 else
354                 {
355                         ++i;
356                 }
357         }
358         
359         // Split too long edges.
360         if (maxEdgeLen > 0)
361         {
362                 for (int i = 0; i < simplified.size()/4; )
363                 {
364                         int ii = (i+1) % (simplified.size()/4);
365                         
366                         int ax = simplified[i*4+0];
367                         int az = simplified[i*4+2];
368                         int ai = simplified[i*4+3];
369                         
370                         int bx = simplified[ii*4+0];
371                         int bz = simplified[ii*4+2];
372                         int bi = simplified[ii*4+3];
373                         
374                         // Find maximum deviation from the segment.
375                         int maxi = -1;
376                         int ci = (ai+1) % pn;
377                         
378                         // Tesselate only outer edges.
379                         if ((points[ci*4+3] & 0xffff) == 0)
380                         {
381                                 int dx = bx - ax;
382                                 int dz = bz - az;
383                                 if (dx*dx + dz*dz > maxEdgeLen*maxEdgeLen)
384                                 {
385                                         int n = bi < ai ? (bi+pn - ai) : (bi - ai);
386                                         maxi = (ai + n/2) % pn;
387                                 }
388                         }
389                         
390                         // If the max deviation is larger than accepted error,
391                         // add new point, else continue to next segment.
392                         if (maxi != -1)
393                         {
394                                 // Add space for the new point.
395                                 simplified.resize(simplified.size()+4);
396                                 int n = simplified.size()/4;
397                                 for (int j = n-1; j > i; --j)
398                                 {
399                                         simplified[j*4+0] = simplified[(j-1)*4+0];
400                                         simplified[j*4+1] = simplified[(j-1)*4+1];
401                                         simplified[j*4+2] = simplified[(j-1)*4+2];
402                                         simplified[j*4+3] = simplified[(j-1)*4+3];
403                                 }
404                                 // Add the point.
405                                 simplified[(i+1)*4+0] = points[maxi*4+0];
406                                 simplified[(i+1)*4+1] = points[maxi*4+1];
407                                 simplified[(i+1)*4+2] = points[maxi*4+2];
408                                 simplified[(i+1)*4+3] = maxi;
409                         }
410                         else
411                         {
412                                 ++i;
413                         }
414                 }
415         }
416         
417         for (int i = 0; i < simplified.size()/4; ++i)
418         {
419                 // The edge vertex flag is take from the current raw point,
420                 // and the neighbour region is take from the next raw point.
421                 const int ai = (simplified[i*4+3]+1) % pn;
422                 const int bi = simplified[i*4+3];
423                 simplified[i*4+3] = (points[ai*4+3] & 0xffff) | (points[bi*4+3] & RC_BORDER_VERTEX);
424         }
425         
426 }
427
428 static void removeDegenerateSegments(rcIntArray& simplified)
429 {
430         // Remove adjacent vertices which are equal on xz-plane,
431         // or else the triangulator will get confused.
432         for (int i = 0; i < simplified.size()/4; ++i)
433         {
434                 int ni = i+1;
435                 if (ni >= (simplified.size()/4))
436                         ni = 0;
437                         
438                 if (simplified[i*4+0] == simplified[ni*4+0] &&
439                         simplified[i*4+2] == simplified[ni*4+2])
440                 {
441                         // Degenerate segment, remove.
442                         for (int j = i; j < simplified.size()/4-1; ++j)
443                         {
444                                 simplified[j*4+0] = simplified[(j+1)*4+0];
445                                 simplified[j*4+1] = simplified[(j+1)*4+1];
446                                 simplified[j*4+2] = simplified[(j+1)*4+2];
447                                 simplified[j*4+3] = simplified[(j+1)*4+3];
448                         }
449                         simplified.pop();
450                 }
451         }
452 }
453
454 static int calcAreaOfPolygon2D(const int* verts, const int nverts)
455 {
456         int area = 0;
457         for (int i = 0, j = nverts-1; i < nverts; j=i++)
458         {
459                 const int* vi = &verts[i*4];
460                 const int* vj = &verts[j*4];
461                 area += vi[0] * vj[2] - vj[0] * vi[2];
462         }
463         return (area+1) / 2;
464 }
465
466 static void getClosestIndices(const int* vertsa, const int nvertsa,
467                                                           const int* vertsb, const int nvertsb,
468                                                           int& ia, int& ib)
469 {
470         int closestDist = 0xfffffff;
471         for (int i = 0; i < nvertsa; ++i)
472         {
473                 const int* va = &vertsa[i*4];
474                 for (int j = 0; j < nvertsb; ++j)
475                 {
476                         const int* vb = &vertsb[j*4];
477                         const int dx = vb[0] - va[0];
478                         const int dz = vb[2] - va[2];
479                         const int d = dx*dx + dz*dz;
480                         if (d < closestDist)
481                         {
482                                 ia = i;
483                                 ib = j;
484                                 closestDist = d;
485                         }
486                 }
487         }
488 }
489
490 static bool mergeContours(rcContour& ca, rcContour& cb, int ia, int ib)
491 {
492         const int maxVerts = ca.nverts + cb.nverts + 2;
493         int* verts = new int[maxVerts*4];
494         if (!verts)
495                 return false;
496
497         int nv = 0;
498
499         // Copy contour A.
500         for (int i = 0; i <= ca.nverts; ++i)
501         {
502                 int* dst = &verts[nv*4];
503                 const int* src = &ca.verts[((ia+i)%ca.nverts)*4];
504                 dst[0] = src[0];
505                 dst[1] = src[1];
506                 dst[2] = src[2];
507                 dst[3] = src[3];
508                 nv++;
509         }
510
511         // Copy contour B
512         for (int i = 0; i <= cb.nverts; ++i)
513         {
514                 int* dst = &verts[nv*4];
515                 const int* src = &cb.verts[((ib+i)%cb.nverts)*4];
516                 dst[0] = src[0];
517                 dst[1] = src[1];
518                 dst[2] = src[2];
519                 dst[3] = src[3];
520                 nv++;
521         }
522         
523         delete [] ca.verts;
524         ca.verts = verts;
525         ca.nverts = nv;
526
527         delete [] cb.verts;
528         cb.verts = 0;
529         cb.nverts = 0;
530         
531         return true;
532 }
533
534 bool rcBuildContours(rcCompactHeightfield& chf,
535                                          const float maxError, const int maxEdgeLen,
536                                          rcContourSet& cset)
537 {
538         const int w = chf.width;
539         const int h = chf.height;
540         
541         rcTimeVal startTime = rcGetPerformanceTimer();
542         
543         vcopy(cset.bmin, chf.bmin);
544         vcopy(cset.bmax, chf.bmax);
545         cset.cs = chf.cs;
546         cset.ch = chf.ch;
547         
548         const int maxContours = chf.maxRegions*2;
549         cset.conts = new rcContour[maxContours];
550         if (!cset.conts)
551                 return false;
552         cset.nconts = 0;
553         
554         unsigned char* flags = new unsigned char[chf.spanCount];
555         if (!flags)
556         {
557                 if (rcGetLog())
558                         rcGetLog()->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'flags'.");
559                 return false;
560         }
561         
562         rcTimeVal traceStartTime = rcGetPerformanceTimer();
563                                         
564         
565         // Mark boundaries.
566         for (int y = 0; y < h; ++y)
567         {
568                 for (int x = 0; x < w; ++x)
569                 {
570                         const rcCompactCell& c = chf.cells[x+y*w];
571                         for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
572                         {
573                                 unsigned char res = 0;
574                                 const rcCompactSpan& s = chf.spans[i];
575                                 if (!s.reg || (s.reg & RC_BORDER_REG))
576                                 {
577                                         flags[i] = 0;
578                                         continue;
579                                 }
580                                 for (int dir = 0; dir < 4; ++dir)
581                                 {
582                                         unsigned short r = 0;
583                                         if (rcGetCon(s, dir) != 0xf)
584                                         {
585                                                 const int ax = x + rcGetDirOffsetX(dir);
586                                                 const int ay = y + rcGetDirOffsetY(dir);
587                                                 const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);
588                                                 const rcCompactSpan& as = chf.spans[ai];
589                                                 r = as.reg;
590                                         }
591                                         if (r == s.reg)
592                                                 res |= (1 << dir);
593                                 }
594                                 flags[i] = res ^ 0xf; // Inverse, mark non connected edges.
595                         }
596                 }
597         }
598         
599         rcTimeVal traceEndTime = rcGetPerformanceTimer();
600         
601         rcTimeVal simplifyStartTime = rcGetPerformanceTimer();
602         
603         rcIntArray verts(256);
604         rcIntArray simplified(64);
605         
606         for (int y = 0; y < h; ++y)
607         {
608                 for (int x = 0; x < w; ++x)
609                 {
610                         const rcCompactCell& c = chf.cells[x+y*w];
611                         for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
612                         {
613                                 if (flags[i] == 0 || flags[i] == 0xf)
614                                 {
615                                         flags[i] = 0;
616                                         continue;
617                                 }
618                                 unsigned short reg = chf.spans[i].reg;
619                                 if (!reg || (reg & RC_BORDER_REG))
620                                         continue;
621                                 
622                                 verts.resize(0);
623                                 simplified.resize(0);
624                                 walkContour(x, y, i, chf, flags, verts);
625                                 simplifyContour(verts, simplified, maxError, maxEdgeLen);
626                                 removeDegenerateSegments(simplified);
627                                 
628                                 // Store region->contour remap info.
629                                 // Create contour.
630                                 if (simplified.size()/4 >= 3)
631                                 {
632                                         if (cset.nconts >= maxContours)
633                                         {
634                                                 if (rcGetLog())
635                                                         rcGetLog()->log(RC_LOG_ERROR, "rcBuildContours: Too many contours %d, max %d.", cset.nconts, maxContours);
636                                                 return false;
637                                         }
638                                                 
639                                         rcContour* cont = &cset.conts[cset.nconts++];
640                                         
641                                         cont->nverts = simplified.size()/4;
642                                         cont->verts = new int[cont->nverts*4];
643                                         memcpy(cont->verts, &simplified[0], sizeof(int)*cont->nverts*4);
644                                         
645                                         cont->nrverts = verts.size()/4;
646                                         cont->rverts = new int[cont->nrverts*4];
647                                         memcpy(cont->rverts, &verts[0], sizeof(int)*cont->nrverts*4);
648                                         
649 /*                                      cont->cx = cont->cy = cont->cz = 0;
650                                         for (int i = 0; i < cont->nverts; ++i)
651                                         {
652                                                 cont->cx += cont->verts[i*4+0];
653                                                 cont->cy += cont->verts[i*4+1];
654                                                 cont->cz += cont->verts[i*4+2];
655                                         }
656                                         cont->cx /= cont->nverts;
657                                         cont->cy /= cont->nverts;
658                                         cont->cz /= cont->nverts;*/
659                                         
660                                         cont->reg = reg;
661                                 }
662                         }
663                 }
664         }
665         
666         // Check and merge droppings.
667         // Sometimes the previous algorithms can fail and create several countours
668         // per area. This pass will try to merge the holes into the main region.
669         for (int i = 0; i < cset.nconts; ++i)
670         {
671                 rcContour& cont = cset.conts[i];
672                 // Check if the contour is would backwards.
673                 if (calcAreaOfPolygon2D(cont.verts, cont.nverts) < 0)
674                 {
675                         // Find another contour which has the same region ID.
676                         int mergeIdx = -1;
677                         for (int j = 0; j < cset.nconts; ++j)
678                         {
679                                 if (i == j) continue;
680                                 if (cset.conts[j].nverts && cset.conts[j].reg == cont.reg)
681                                 {
682                                         // Make sure the polygon is correctly oriented.
683                                         if (calcAreaOfPolygon2D(cset.conts[j].verts, cset.conts[j].nverts))
684                                         {
685                                                 mergeIdx = j;
686                                                 break;
687                                         }
688                                 }
689                         }
690                         if (mergeIdx == -1)
691                         {
692                                 if (rcGetLog())
693                                         rcGetLog()->log(RC_LOG_WARNING, "rcBuildContours: Could not find merge target for bad contour %d.", i);
694                         }
695                         else
696                         {
697                                 rcContour& mcont = cset.conts[mergeIdx];
698                                 // Merge by closest points.
699                                 int ia, ib;
700                                 getClosestIndices(mcont.verts, mcont.nverts, cont.verts, cont.nverts, ia, ib);
701                                 if (!mergeContours(mcont, cont, ia, ib))
702                                 {
703                                         if (rcGetLog())
704                                                 rcGetLog()->log(RC_LOG_WARNING, "rcBuildContours: Failed to merge contours %d and %d.", i, mergeIdx);
705                                 }
706                         }
707                 }
708         }
709         
710                 
711         delete [] flags;
712         
713         rcTimeVal simplifyEndTime = rcGetPerformanceTimer();
714         
715         rcTimeVal endTime = rcGetPerformanceTimer();
716         
717 //      if (rcGetLog())
718 //      {
719 //              rcGetLog()->log(RC_LOG_PROGRESS, "Create contours: %.3f ms", rcGetDeltaTimeUsec(startTime, endTime)/1000.0f);
720 //              rcGetLog()->log(RC_LOG_PROGRESS, " - boundary: %.3f ms", rcGetDeltaTimeUsec(boundaryStartTime, boundaryEndTime)/1000.0f);
721 //              rcGetLog()->log(RC_LOG_PROGRESS, " - contour: %.3f ms", rcGetDeltaTimeUsec(contourStartTime, contourEndTime)/1000.0f);
722 //      }
723
724         if (rcGetBuildTimes())
725         {
726                 rcGetBuildTimes()->buildContours += rcGetDeltaTimeUsec(startTime, endTime);
727                 rcGetBuildTimes()->buildContoursTrace += rcGetDeltaTimeUsec(traceStartTime, traceEndTime);
728                 rcGetBuildTimes()->buildContoursSimplify += rcGetDeltaTimeUsec(simplifyStartTime, simplifyEndTime);
729         }
730         
731         return true;
732 }