svn merge ^/trunk/blender -r40644:40720
[blender-staging.git] / extern / recastnavigation / Recast / Source / RecastRegion.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 #include <float.h>
20 #define _USE_MATH_DEFINES
21 #include <math.h>
22 #include <string.h>
23 #include <stdlib.h>
24 #include <stdio.h>
25 #include "Recast.h"
26 #include "RecastAlloc.h"
27 #include "RecastAssert.h"
28 #include <new>
29
30
31 static void calculateDistanceField(rcCompactHeightfield& chf, unsigned short* src, unsigned short& maxDist)
32 {
33         const int w = chf.width;
34         const int h = chf.height;
35         
36         // Init distance and points.
37         for (int i = 0; i < chf.spanCount; ++i)
38                 src[i] = 0xffff;
39         
40         // Mark boundary cells.
41         for (int y = 0; y < h; ++y)
42         {
43                 for (int x = 0; x < w; ++x)
44                 {
45                         const rcCompactCell& c = chf.cells[x+y*w];
46                         for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
47                         {
48                                 const rcCompactSpan& s = chf.spans[i];
49                                 const unsigned char area = chf.areas[i];
50                                 
51                                 int nc = 0;
52                                 for (int dir = 0; dir < 4; ++dir)
53                                 {
54                                         if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
55                                         {
56                                                 const int ax = x + rcGetDirOffsetX(dir);
57                                                 const int ay = y + rcGetDirOffsetY(dir);
58                                                 const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);
59                                                 if (area == chf.areas[ai])
60                                                         nc++;
61                                         }
62                                 }
63                                 if (nc != 4)
64                                         src[i] = 0;
65                         }
66                 }
67         }
68         
69                         
70         // Pass 1
71         for (int y = 0; y < h; ++y)
72         {
73                 for (int x = 0; x < w; ++x)
74                 {
75                         const rcCompactCell& c = chf.cells[x+y*w];
76                         for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
77                         {
78                                 const rcCompactSpan& s = chf.spans[i];
79                                 
80                                 if (rcGetCon(s, 0) != RC_NOT_CONNECTED)
81                                 {
82                                         // (-1,0)
83                                         const int ax = x + rcGetDirOffsetX(0);
84                                         const int ay = y + rcGetDirOffsetY(0);
85                                         const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 0);
86                                         const rcCompactSpan& as = chf.spans[ai];
87                                         if (src[ai]+2 < src[i])
88                                                 src[i] = src[ai]+2;
89                                         
90                                         // (-1,-1)
91                                         if (rcGetCon(as, 3) != RC_NOT_CONNECTED)
92                                         {
93                                                 const int aax = ax + rcGetDirOffsetX(3);
94                                                 const int aay = ay + rcGetDirOffsetY(3);
95                                                 const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 3);
96                                                 if (src[aai]+3 < src[i])
97                                                         src[i] = src[aai]+3;
98                                         }
99                                 }
100                                 if (rcGetCon(s, 3) != RC_NOT_CONNECTED)
101                                 {
102                                         // (0,-1)
103                                         const int ax = x + rcGetDirOffsetX(3);
104                                         const int ay = y + rcGetDirOffsetY(3);
105                                         const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 3);
106                                         const rcCompactSpan& as = chf.spans[ai];
107                                         if (src[ai]+2 < src[i])
108                                                 src[i] = src[ai]+2;
109                                         
110                                         // (1,-1)
111                                         if (rcGetCon(as, 2) != RC_NOT_CONNECTED)
112                                         {
113                                                 const int aax = ax + rcGetDirOffsetX(2);
114                                                 const int aay = ay + rcGetDirOffsetY(2);
115                                                 const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 2);
116                                                 if (src[aai]+3 < src[i])
117                                                         src[i] = src[aai]+3;
118                                         }
119                                 }
120                         }
121                 }
122         }
123         
124         // Pass 2
125         for (int y = h-1; y >= 0; --y)
126         {
127                 for (int x = w-1; x >= 0; --x)
128                 {
129                         const rcCompactCell& c = chf.cells[x+y*w];
130                         for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
131                         {
132                                 const rcCompactSpan& s = chf.spans[i];
133                                 
134                                 if (rcGetCon(s, 2) != RC_NOT_CONNECTED)
135                                 {
136                                         // (1,0)
137                                         const int ax = x + rcGetDirOffsetX(2);
138                                         const int ay = y + rcGetDirOffsetY(2);
139                                         const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 2);
140                                         const rcCompactSpan& as = chf.spans[ai];
141                                         if (src[ai]+2 < src[i])
142                                                 src[i] = src[ai]+2;
143                                         
144                                         // (1,1)
145                                         if (rcGetCon(as, 1) != RC_NOT_CONNECTED)
146                                         {
147                                                 const int aax = ax + rcGetDirOffsetX(1);
148                                                 const int aay = ay + rcGetDirOffsetY(1);
149                                                 const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 1);
150                                                 if (src[aai]+3 < src[i])
151                                                         src[i] = src[aai]+3;
152                                         }
153                                 }
154                                 if (rcGetCon(s, 1) != RC_NOT_CONNECTED)
155                                 {
156                                         // (0,1)
157                                         const int ax = x + rcGetDirOffsetX(1);
158                                         const int ay = y + rcGetDirOffsetY(1);
159                                         const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 1);
160                                         const rcCompactSpan& as = chf.spans[ai];
161                                         if (src[ai]+2 < src[i])
162                                                 src[i] = src[ai]+2;
163                                         
164                                         // (-1,1)
165                                         if (rcGetCon(as, 0) != RC_NOT_CONNECTED)
166                                         {
167                                                 const int aax = ax + rcGetDirOffsetX(0);
168                                                 const int aay = ay + rcGetDirOffsetY(0);
169                                                 const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 0);
170                                                 if (src[aai]+3 < src[i])
171                                                         src[i] = src[aai]+3;
172                                         }
173                                 }
174                         }
175                 }
176         }       
177         
178         maxDist = 0;
179         for (int i = 0; i < chf.spanCount; ++i)
180                 maxDist = rcMax(src[i], maxDist);
181         
182 }
183
184 static unsigned short* boxBlur(rcCompactHeightfield& chf, int thr,
185                                                            unsigned short* src, unsigned short* dst)
186 {
187         const int w = chf.width;
188         const int h = chf.height;
189         
190         thr *= 2;
191         
192         for (int y = 0; y < h; ++y)
193         {
194                 for (int x = 0; x < w; ++x)
195                 {
196                         const rcCompactCell& c = chf.cells[x+y*w];
197                         for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
198                         {
199                                 const rcCompactSpan& s = chf.spans[i];
200                                 const unsigned short cd = src[i];
201                                 if (cd <= thr)
202                                 {
203                                         dst[i] = cd;
204                                         continue;
205                                 }
206
207                                 int d = (int)cd;
208                                 for (int dir = 0; dir < 4; ++dir)
209                                 {
210                                         if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
211                                         {
212                                                 const int ax = x + rcGetDirOffsetX(dir);
213                                                 const int ay = y + rcGetDirOffsetY(dir);
214                                                 const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);
215                                                 d += (int)src[ai];
216                                                 
217                                                 const rcCompactSpan& as = chf.spans[ai];
218                                                 const int dir2 = (dir+1) & 0x3;
219                                                 if (rcGetCon(as, dir2) != RC_NOT_CONNECTED)
220                                                 {
221                                                         const int ax2 = ax + rcGetDirOffsetX(dir2);
222                                                         const int ay2 = ay + rcGetDirOffsetY(dir2);
223                                                         const int ai2 = (int)chf.cells[ax2+ay2*w].index + rcGetCon(as, dir2);
224                                                         d += (int)src[ai2];
225                                                 }
226                                                 else
227                                                 {
228                                                         d += cd;
229                                                 }
230                                         }
231                                         else
232                                         {
233                                                 d += cd*2;
234                                         }
235                                 }
236                                 dst[i] = (unsigned short)((d+5)/9);
237                         }
238                 }
239         }
240         return dst;
241 }
242
243
244 static bool floodRegion(int x, int y, int i,
245                                                 unsigned short level, unsigned short r,
246                                                 rcCompactHeightfield& chf,
247                                                 unsigned short* srcReg, unsigned short* srcDist,
248                                                 rcIntArray& stack)
249 {
250         const int w = chf.width;
251         
252         const unsigned char area = chf.areas[i];
253         
254         // Flood fill mark region.
255         stack.resize(0);
256         stack.push((int)x);
257         stack.push((int)y);
258         stack.push((int)i);
259         srcReg[i] = r;
260         srcDist[i] = 0;
261         
262         unsigned short lev = level >= 2 ? level-2 : 0;
263         int count = 0;
264         
265         while (stack.size() > 0)
266         {
267                 int ci = stack.pop();
268                 int cy = stack.pop();
269                 int cx = stack.pop();
270                 
271                 const rcCompactSpan& cs = chf.spans[ci];
272                 
273                 // Check if any of the neighbours already have a valid region set.
274                 unsigned short ar = 0;
275                 for (int dir = 0; dir < 4; ++dir)
276                 {
277                         // 8 connected
278                         if (rcGetCon(cs, dir) != RC_NOT_CONNECTED)
279                         {
280                                 const int ax = cx + rcGetDirOffsetX(dir);
281                                 const int ay = cy + rcGetDirOffsetY(dir);
282                                 const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(cs, dir);
283                                 if (chf.areas[ai] != area)
284                                         continue;
285                                 unsigned short nr = srcReg[ai];
286                                 if (nr & RC_BORDER_REG) // Do not take borders into account.
287                                         continue;
288                                 if (nr != 0 && nr != r)
289                                         ar = nr;
290                                 
291                                 const rcCompactSpan& as = chf.spans[ai];
292                                 
293                                 const int dir2 = (dir+1) & 0x3;
294                                 if (rcGetCon(as, dir2) != RC_NOT_CONNECTED)
295                                 {
296                                         const int ax2 = ax + rcGetDirOffsetX(dir2);
297                                         const int ay2 = ay + rcGetDirOffsetY(dir2);
298                                         const int ai2 = (int)chf.cells[ax2+ay2*w].index + rcGetCon(as, dir2);
299                                         if (chf.areas[ai2] != area)
300                                                 continue;
301                                         unsigned short nr = srcReg[ai2];
302                                         if (nr != 0 && nr != r)
303                                                 ar = nr;
304                                 }                               
305                         }
306                 }
307                 if (ar != 0)
308                 {
309                         srcReg[ci] = 0;
310                         continue;
311                 }
312                 count++;
313                 
314                 // Expand neighbours.
315                 for (int dir = 0; dir < 4; ++dir)
316                 {
317                         if (rcGetCon(cs, dir) != RC_NOT_CONNECTED)
318                         {
319                                 const int ax = cx + rcGetDirOffsetX(dir);
320                                 const int ay = cy + rcGetDirOffsetY(dir);
321                                 const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(cs, dir);
322                                 if (chf.areas[ai] != area)
323                                         continue;
324                                 if (chf.dist[ai] >= lev && srcReg[ai] == 0)
325                                 {
326                                         srcReg[ai] = r;
327                                         srcDist[ai] = 0;
328                                         stack.push(ax);
329                                         stack.push(ay);
330                                         stack.push(ai);
331                                 }
332                         }
333                 }
334         }
335         
336         return count > 0;
337 }
338
339 static unsigned short* expandRegions(int maxIter, unsigned short level,
340                                                                          rcCompactHeightfield& chf,
341                                                                          unsigned short* srcReg, unsigned short* srcDist,
342                                                                          unsigned short* dstReg, unsigned short* dstDist, 
343                                                                          rcIntArray& stack)
344 {
345         const int w = chf.width;
346         const int h = chf.height;
347
348         // Find cells revealed by the raised level.
349         stack.resize(0);
350         for (int y = 0; y < h; ++y)
351         {
352                 for (int x = 0; x < w; ++x)
353                 {
354                         const rcCompactCell& c = chf.cells[x+y*w];
355                         for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
356                         {
357                                 if (chf.dist[i] >= level && srcReg[i] == 0 && chf.areas[i] != RC_NULL_AREA)
358                                 {
359                                         stack.push(x);
360                                         stack.push(y);
361                                         stack.push(i);
362                                 }
363                         }
364                 }
365         }
366         
367         int iter = 0;
368         while (stack.size() > 0)
369         {
370                 int failed = 0;
371                 
372                 memcpy(dstReg, srcReg, sizeof(unsigned short)*chf.spanCount);
373                 memcpy(dstDist, srcDist, sizeof(unsigned short)*chf.spanCount);
374                 
375                 for (int j = 0; j < stack.size(); j += 3)
376                 {
377                         int x = stack[j+0];
378                         int y = stack[j+1];
379                         int i = stack[j+2];
380                         if (i < 0)
381                         {
382                                 failed++;
383                                 continue;
384                         }
385                         
386                         unsigned short r = srcReg[i];
387                         unsigned short d2 = 0xffff;
388                         const unsigned char area = chf.areas[i];
389                         const rcCompactSpan& s = chf.spans[i];
390                         for (int dir = 0; dir < 4; ++dir)
391                         {
392                                 if (rcGetCon(s, dir) == RC_NOT_CONNECTED) continue;
393                                 const int ax = x + rcGetDirOffsetX(dir);
394                                 const int ay = y + rcGetDirOffsetY(dir);
395                                 const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);
396                                 if (chf.areas[ai] != area) continue;
397                                 if (srcReg[ai] > 0 && (srcReg[ai] & RC_BORDER_REG) == 0)
398                                 {
399                                         if ((int)srcDist[ai]+2 < (int)d2)
400                                         {
401                                                 r = srcReg[ai];
402                                                 d2 = srcDist[ai]+2;
403                                         }
404                                 }
405                         }
406                         if (r)
407                         {
408                                 stack[j+2] = -1; // mark as used
409                                 dstReg[i] = r;
410                                 dstDist[i] = d2;
411                         }
412                         else
413                         {
414                                 failed++;
415                         }
416                 }
417                 
418                 // rcSwap source and dest.
419                 rcSwap(srcReg, dstReg);
420                 rcSwap(srcDist, dstDist);
421                 
422                 if (failed*3 == stack.size())
423                         break;
424                 
425                 if (level > 0)
426                 {
427                         ++iter;
428                         if (iter >= maxIter)
429                                 break;
430                 }
431         }
432         
433         return srcReg;
434 }
435
436
437 struct rcRegion
438 {
439         inline rcRegion(unsigned short i) :
440                 spanCount(0),
441                 id(i),
442                 areaType(0),
443                 remap(false),
444                 visited(false)
445         {}
446         
447         int spanCount;                                  // Number of spans belonging to this region
448         unsigned short id;                              // ID of the region
449         unsigned char areaType;                 // Are type.
450         bool remap;
451         bool visited;
452         rcIntArray connections;
453         rcIntArray floors;
454 };
455
456 static void removeAdjacentNeighbours(rcRegion& reg)
457 {
458         // Remove adjacent duplicates.
459         for (int i = 0; i < reg.connections.size() && reg.connections.size() > 1; )
460         {
461                 int ni = (i+1) % reg.connections.size();
462                 if (reg.connections[i] == reg.connections[ni])
463                 {
464                         // Remove duplicate
465                         for (int j = i; j < reg.connections.size()-1; ++j)
466                                 reg.connections[j] = reg.connections[j+1];
467                         reg.connections.pop();
468                 }
469                 else
470                         ++i;
471         }
472 }
473
474 static void replaceNeighbour(rcRegion& reg, unsigned short oldId, unsigned short newId)
475 {
476         bool neiChanged = false;
477         for (int i = 0; i < reg.connections.size(); ++i)
478         {
479                 if (reg.connections[i] == oldId)
480                 {
481                         reg.connections[i] = newId;
482                         neiChanged = true;
483                 }
484         }
485         for (int i = 0; i < reg.floors.size(); ++i)
486         {
487                 if (reg.floors[i] == oldId)
488                         reg.floors[i] = newId;
489         }
490         if (neiChanged)
491                 removeAdjacentNeighbours(reg);
492 }
493
494 static bool canMergeWithRegion(const rcRegion& rega, const rcRegion& regb)
495 {
496         if (rega.areaType != regb.areaType)
497                 return false;
498         int n = 0;
499         for (int i = 0; i < rega.connections.size(); ++i)
500         {
501                 if (rega.connections[i] == regb.id)
502                         n++;
503         }
504         if (n > 1)
505                 return false;
506         for (int i = 0; i < rega.floors.size(); ++i)
507         {
508                 if (rega.floors[i] == regb.id)
509                         return false;
510         }
511         return true;
512 }
513
514 static void addUniqueFloorRegion(rcRegion& reg, int n)
515 {
516         for (int i = 0; i < reg.floors.size(); ++i)
517                 if (reg.floors[i] == n)
518                         return;
519         reg.floors.push(n);
520 }
521
522 static bool mergeRegions(rcRegion& rega, rcRegion& regb)
523 {
524         unsigned short aid = rega.id;
525         unsigned short bid = regb.id;
526         
527         // Duplicate current neighbourhood.
528         rcIntArray acon;
529         acon.resize(rega.connections.size());
530         for (int i = 0; i < rega.connections.size(); ++i)
531                 acon[i] = rega.connections[i];
532         rcIntArray& bcon = regb.connections;
533         
534         // Find insertion point on A.
535         int insa = -1;
536         for (int i = 0; i < acon.size(); ++i)
537         {
538                 if (acon[i] == bid)
539                 {
540                         insa = i;
541                         break;
542                 }
543         }
544         if (insa == -1)
545                 return false;
546         
547         // Find insertion point on B.
548         int insb = -1;
549         for (int i = 0; i < bcon.size(); ++i)
550         {
551                 if (bcon[i] == aid)
552                 {
553                         insb = i;
554                         break;
555                 }
556         }
557         if (insb == -1)
558                 return false;
559         
560         // Merge neighbours.
561         rega.connections.resize(0);
562         for (int i = 0, ni = acon.size(); i < ni-1; ++i)
563                 rega.connections.push(acon[(insa+1+i) % ni]);
564                 
565         for (int i = 0, ni = bcon.size(); i < ni-1; ++i)
566                 rega.connections.push(bcon[(insb+1+i) % ni]);
567         
568         removeAdjacentNeighbours(rega);
569         
570         for (int j = 0; j < regb.floors.size(); ++j)
571                 addUniqueFloorRegion(rega, regb.floors[j]);
572         rega.spanCount += regb.spanCount;
573         regb.spanCount = 0;
574         regb.connections.resize(0);
575
576         return true;
577 }
578
579 static bool isRegionConnectedToBorder(const rcRegion& reg)
580 {
581         // Region is connected to border if
582         // one of the neighbours is null id.
583         for (int i = 0; i < reg.connections.size(); ++i)
584         {
585                 if (reg.connections[i] == 0)
586                         return true;
587         }
588         return false;
589 }
590
591 static bool isSolidEdge(rcCompactHeightfield& chf, unsigned short* srcReg,
592                                                 int x, int y, int i, int dir)
593 {
594         const rcCompactSpan& s = chf.spans[i];
595         unsigned short r = 0;
596         if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
597         {
598                 const int ax = x + rcGetDirOffsetX(dir);
599                 const int ay = y + rcGetDirOffsetY(dir);
600                 const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dir);
601                 r = srcReg[ai];
602         }
603         if (r == srcReg[i])
604                 return false;
605         return true;
606 }
607
608 static void walkContour(int x, int y, int i, int dir,
609                                                 rcCompactHeightfield& chf,
610                                                 unsigned short* srcReg,
611                                                 rcIntArray& cont)
612 {
613         int startDir = dir;
614         int starti = i;
615
616         const rcCompactSpan& ss = chf.spans[i];
617         unsigned short curReg = 0;
618         if (rcGetCon(ss, dir) != RC_NOT_CONNECTED)
619         {
620                 const int ax = x + rcGetDirOffsetX(dir);
621                 const int ay = y + rcGetDirOffsetY(dir);
622                 const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(ss, dir);
623                 curReg = srcReg[ai];
624         }
625         cont.push(curReg);
626                         
627         int iter = 0;
628         while (++iter < 40000)
629         {
630                 const rcCompactSpan& s = chf.spans[i];
631                 
632                 if (isSolidEdge(chf, srcReg, x, y, i, dir))
633                 {
634                         // Choose the edge corner
635                         unsigned short r = 0;
636                         if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
637                         {
638                                 const int ax = x + rcGetDirOffsetX(dir);
639                                 const int ay = y + rcGetDirOffsetY(dir);
640                                 const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dir);
641                                 r = srcReg[ai];
642                         }
643                         if (r != curReg)
644                         {
645                                 curReg = r;
646                                 cont.push(curReg);
647                         }
648                         
649                         dir = (dir+1) & 0x3;  // Rotate CW
650                 }
651                 else
652                 {
653                         int ni = -1;
654                         const int nx = x + rcGetDirOffsetX(dir);
655                         const int ny = y + rcGetDirOffsetY(dir);
656                         if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
657                         {
658                                 const rcCompactCell& nc = chf.cells[nx+ny*chf.width];
659                                 ni = (int)nc.index + rcGetCon(s, dir);
660                         }
661                         if (ni == -1)
662                         {
663                                 // Should not happen.
664                                 return;
665                         }
666                         x = nx;
667                         y = ny;
668                         i = ni;
669                         dir = (dir+3) & 0x3;    // Rotate CCW
670                 }
671                 
672                 if (starti == i && startDir == dir)
673                 {
674                         break;
675                 }
676         }
677
678         // Remove adjacent duplicates.
679         if (cont.size() > 1)
680         {
681                 for (int i = 0; i < cont.size(); )
682                 {
683                         int ni = (i+1) % cont.size();
684                         if (cont[i] == cont[ni])
685                         {
686                                 for (int j = i; j < cont.size()-1; ++j)
687                                         cont[j] = cont[j+1];
688                                 cont.pop();
689                         }
690                         else
691                                 ++i;
692                 }
693         }
694 }
695
696 static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegionSize,
697                                                            unsigned short& maxRegionId,
698                                                            rcCompactHeightfield& chf,
699                                                            unsigned short* srcReg)
700 {
701         const int w = chf.width;
702         const int h = chf.height;
703         
704         const int nreg = maxRegionId+1;
705         rcRegion* regions = (rcRegion*)rcAlloc(sizeof(rcRegion)*nreg, RC_ALLOC_TEMP);
706         if (!regions)
707         {
708                 ctx->log(RC_LOG_ERROR, "filterSmallRegions: Out of memory 'regions' (%d).", nreg);
709                 return false;
710         }
711
712         // Construct regions
713         for (int i = 0; i < nreg; ++i)
714                 new(&regions[i]) rcRegion((unsigned short)i);
715         
716         // Find edge of a region and find connections around the contour.
717         for (int y = 0; y < h; ++y)
718         {
719                 for (int x = 0; x < w; ++x)
720                 {
721                         const rcCompactCell& c = chf.cells[x+y*w];
722                         for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
723                         {
724                                 unsigned short r = srcReg[i];
725                                 if (r == 0 || r >= nreg)
726                                         continue;
727                                 
728                                 rcRegion& reg = regions[r];
729                                 reg.spanCount++;
730                                 
731                                 
732                                 // Update floors.
733                                 for (int j = (int)c.index; j < ni; ++j)
734                                 {
735                                         if (i == j) continue;
736                                         unsigned short floorId = srcReg[j];
737                                         if (floorId == 0 || floorId >= nreg)
738                                                 continue;
739                                         addUniqueFloorRegion(reg, floorId);
740                                 }
741                                 
742                                 // Have found contour
743                                 if (reg.connections.size() > 0)
744                                         continue;
745                                 
746                                 reg.areaType = chf.areas[i];
747                                 
748                                 // Check if this cell is next to a border.
749                                 int ndir = -1;
750                                 for (int dir = 0; dir < 4; ++dir)
751                                 {
752                                         if (isSolidEdge(chf, srcReg, x, y, i, dir))
753                                         {
754                                                 ndir = dir;
755                                                 break;
756                                         }
757                                 }
758                                 
759                                 if (ndir != -1)
760                                 {
761                                         // The cell is at border.
762                                         // Walk around the contour to find all the neighbours.
763                                         walkContour(x, y, i, ndir, chf, srcReg, reg.connections);
764                                 }
765                         }
766                 }
767         }
768
769         // Remove too small regions.
770         rcIntArray stack(32);
771         rcIntArray trace(32);
772         for (int i = 0; i < nreg; ++i)
773         {
774                 rcRegion& reg = regions[i];
775                 if (reg.id == 0 || (reg.id & RC_BORDER_REG))
776                         continue;                       
777                 if (reg.spanCount == 0)
778                         continue;
779                 if (reg.visited)
780                         continue;
781                 
782                 // Count the total size of all the connected regions.
783                 // Also keep track of the regions connects to a tile border.
784                 bool connectsToBorder = false;
785                 int spanCount = 0;
786                 stack.resize(0);
787                 trace.resize(0);
788
789                 reg.visited = true;
790                 stack.push(i);
791                 
792                 while (stack.size())
793                 {
794                         // Pop
795                         int ri = stack.pop();
796                         
797                         rcRegion& creg = regions[ri];
798
799                         spanCount += creg.spanCount;
800                         trace.push(ri);
801
802                         for (int j = 0; j < creg.connections.size(); ++j)
803                         {
804                                 if (creg.connections[j] & RC_BORDER_REG)
805                                 {
806                                         connectsToBorder = true;
807                                         continue;
808                                 }
809                                 rcRegion& nreg = regions[creg.connections[j]];
810                                 if (nreg.visited)
811                                         continue;
812                                 if (nreg.id == 0 || (nreg.id & RC_BORDER_REG))
813                                         continue;
814                                 // Visit
815                                 stack.push(nreg.id);
816                                 nreg.visited = true;
817                         }
818                 }
819                 
820                 // If the accumulated regions size is too small, remove it.
821                 // Do not remove areas which connect to tile borders
822                 // as their size cannot be estimated correctly and removing them
823                 // can potentially remove necessary areas.
824                 if (spanCount < minRegionArea && !connectsToBorder)
825                 {
826                         // Kill all visited regions.
827                         for (int j = 0; j < trace.size(); ++j)
828                         {
829                                 regions[trace[j]].spanCount = 0;
830                                 regions[trace[j]].id = 0;
831                         }
832                 }
833         }
834                 
835         // Merge too small regions to neighbour regions.
836         int mergeCount = 0 ;
837         do
838         {
839                 mergeCount = 0;
840                 for (int i = 0; i < nreg; ++i)
841                 {
842                         rcRegion& reg = regions[i];
843                         if (reg.id == 0 || (reg.id & RC_BORDER_REG))
844                                 continue;                       
845                         if (reg.spanCount == 0)
846                                 continue;
847                         
848                         // Check to see if the region should be merged.
849                         if (reg.spanCount > mergeRegionSize && isRegionConnectedToBorder(reg))
850                                 continue;
851                         
852                         // Small region with more than 1 connection.
853                         // Or region which is not connected to a border at all.
854                         // Find smallest neighbour region that connects to this one.
855                         int smallest = 0xfffffff;
856                         unsigned short mergeId = reg.id;
857                         for (int j = 0; j < reg.connections.size(); ++j)
858                         {
859                                 if (reg.connections[j] & RC_BORDER_REG) continue;
860                                 rcRegion& mreg = regions[reg.connections[j]];
861                                 if (mreg.id == 0 || (mreg.id & RC_BORDER_REG)) continue;
862                                 if (mreg.spanCount < smallest &&
863                                         canMergeWithRegion(reg, mreg) &&
864                                         canMergeWithRegion(mreg, reg))
865                                 {
866                                         smallest = mreg.spanCount;
867                                         mergeId = mreg.id;
868                                 }
869                         }
870                         // Found new id.
871                         if (mergeId != reg.id)
872                         {
873                                 unsigned short oldId = reg.id;
874                                 rcRegion& target = regions[mergeId];
875                                 
876                                 // Merge neighbours.
877                                 if (mergeRegions(target, reg))
878                                 {
879                                         // Fixup regions pointing to current region.
880                                         for (int j = 0; j < nreg; ++j)
881                                         {
882                                                 if (regions[j].id == 0 || (regions[j].id & RC_BORDER_REG)) continue;
883                                                 // If another region was already merged into current region
884                                                 // change the nid of the previous region too.
885                                                 if (regions[j].id == oldId)
886                                                         regions[j].id = mergeId;
887                                                 // Replace the current region with the new one if the
888                                                 // current regions is neighbour.
889                                                 replaceNeighbour(regions[j], oldId, mergeId);
890                                         }
891                                         mergeCount++;
892                                 }
893                         }
894                 }
895         }
896         while (mergeCount > 0);
897         
898         // Compress region Ids.
899         for (int i = 0; i < nreg; ++i)
900         {
901                 regions[i].remap = false;
902                 if (regions[i].id == 0) continue;       // Skip nil regions.
903                 if (regions[i].id & RC_BORDER_REG) continue;    // Skip external regions.
904                 regions[i].remap = true;
905         }
906         
907         unsigned short regIdGen = 0;
908         for (int i = 0; i < nreg; ++i)
909         {
910                 if (!regions[i].remap)
911                         continue;
912                 unsigned short oldId = regions[i].id;
913                 unsigned short newId = ++regIdGen;
914                 for (int j = i; j < nreg; ++j)
915                 {
916                         if (regions[j].id == oldId)
917                         {
918                                 regions[j].id = newId;
919                                 regions[j].remap = false;
920                         }
921                 }
922         }
923         maxRegionId = regIdGen;
924         
925         // Remap regions.
926         for (int i = 0; i < chf.spanCount; ++i)
927         {
928                 if ((srcReg[i] & RC_BORDER_REG) == 0)
929                         srcReg[i] = regions[srcReg[i]].id;
930         }
931         
932         for (int i = 0; i < nreg; ++i)
933                 regions[i].~rcRegion();
934         rcFree(regions);
935         
936         return true;
937 }
938
939 /// @par
940 /// 
941 /// This is usually the second to the last step in creating a fully built
942 /// compact heightfield.  This step is required before regions are built
943 /// using #rcBuildRegions or #rcBuildRegionsMonotone.
944 /// 
945 /// After this step, the distance data is available via the rcCompactHeightfield::maxDistance
946 /// and rcCompactHeightfield::dist fields.
947 ///
948 /// @see rcCompactHeightfield, rcBuildRegions, rcBuildRegionsMonotone
949 bool rcBuildDistanceField(rcContext* ctx, rcCompactHeightfield& chf)
950 {
951         rcAssert(ctx);
952         
953         ctx->startTimer(RC_TIMER_BUILD_DISTANCEFIELD);
954         
955         if (chf.dist)
956         {
957                 rcFree(chf.dist);
958                 chf.dist = 0;
959         }
960         
961         unsigned short* src = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP);
962         if (!src)
963         {
964                 ctx->log(RC_LOG_ERROR, "rcBuildDistanceField: Out of memory 'src' (%d).", chf.spanCount);
965                 return false;
966         }
967         unsigned short* dst = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP);
968         if (!dst)
969         {
970                 ctx->log(RC_LOG_ERROR, "rcBuildDistanceField: Out of memory 'dst' (%d).", chf.spanCount);
971                 rcFree(src);
972                 return false;
973         }
974         
975         unsigned short maxDist = 0;
976
977         ctx->startTimer(RC_TIMER_BUILD_DISTANCEFIELD_DIST);
978         
979         calculateDistanceField(chf, src, maxDist);
980         chf.maxDistance = maxDist;
981         
982         ctx->stopTimer(RC_TIMER_BUILD_DISTANCEFIELD_DIST);
983         
984         ctx->startTimer(RC_TIMER_BUILD_DISTANCEFIELD_BLUR);
985         
986         // Blur
987         if (boxBlur(chf, 1, src, dst) != src)
988                 rcSwap(src, dst);
989         
990         // Store distance.
991         chf.dist = src;
992         
993         ctx->stopTimer(RC_TIMER_BUILD_DISTANCEFIELD_BLUR);
994
995         ctx->stopTimer(RC_TIMER_BUILD_DISTANCEFIELD);
996         
997         rcFree(dst);
998         
999         return true;
1000 }
1001
1002 static void paintRectRegion(int minx, int maxx, int miny, int maxy, unsigned short regId,
1003                                                         rcCompactHeightfield& chf, unsigned short* srcReg)
1004 {
1005         const int w = chf.width;        
1006         for (int y = miny; y < maxy; ++y)
1007         {
1008                 for (int x = minx; x < maxx; ++x)
1009                 {
1010                         const rcCompactCell& c = chf.cells[x+y*w];
1011                         for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
1012                         {
1013                                 if (chf.areas[i] != RC_NULL_AREA)
1014                                         srcReg[i] = regId;
1015                         }
1016                 }
1017         }
1018 }
1019
1020
1021 static const unsigned short RC_NULL_NEI = 0xffff;
1022
1023 struct rcSweepSpan
1024 {
1025         unsigned short rid;     // row id
1026         unsigned short id;      // region id
1027         unsigned short ns;      // number samples
1028         unsigned short nei;     // neighbour id
1029 };
1030
1031 /// @par
1032 /// 
1033 /// Non-null regions will consist of connected, non-overlapping walkable spans that form a single contour.
1034 /// Contours will form simple polygons.
1035 /// 
1036 /// If multiple regions form an area that is smaller than @p minRegionArea, then all spans will be
1037 /// re-assigned to the zero (null) region.
1038 /// 
1039 /// Partitioning can result in smaller than necessary regions. @p mergeRegionArea helps 
1040 /// reduce unecessarily small regions.
1041 /// 
1042 /// See the #rcConfig documentation for more information on the configuration parameters.
1043 /// 
1044 /// The region data will be available via the rcCompactHeightfield::maxRegions
1045 /// and rcCompactSpan::reg fields.
1046 /// 
1047 /// @warning The distance field must be created using #rcBuildDistanceField before attempting to build regions.
1048 /// 
1049 /// @see rcCompactHeightfield, rcCompactSpan, rcBuildDistanceField, rcBuildRegionsMonotone, rcConfig
1050 bool rcBuildRegionsMonotone(rcContext* ctx, rcCompactHeightfield& chf,
1051                                                         const int borderSize, const int minRegionArea, const int mergeRegionArea)
1052 {
1053         rcAssert(ctx);
1054         
1055         ctx->startTimer(RC_TIMER_BUILD_REGIONS);
1056         
1057         const int w = chf.width;
1058         const int h = chf.height;
1059         unsigned short id = 1;
1060         
1061         rcScopedDelete<unsigned short> srcReg = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP);
1062         if (!srcReg)
1063         {
1064                 ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'src' (%d).", chf.spanCount);
1065                 return false;
1066         }
1067         memset(srcReg,0,sizeof(unsigned short)*chf.spanCount);
1068
1069         const int nsweeps = rcMax(chf.width,chf.height);
1070         rcScopedDelete<rcSweepSpan> sweeps = (rcSweepSpan*)rcAlloc(sizeof(rcSweepSpan)*nsweeps, RC_ALLOC_TEMP);
1071         if (!sweeps)
1072         {
1073                 ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'sweeps' (%d).", nsweeps);
1074                 return false;
1075         }
1076         
1077         
1078         // Mark border regions.
1079         if (borderSize > 0)
1080         {
1081                 // Make sure border will not overflow.
1082                 const int bw = rcMin(w, borderSize);
1083                 const int bh = rcMin(h, borderSize);
1084                 // Paint regions
1085                 paintRectRegion(0, bw, 0, h, id|RC_BORDER_REG, chf, srcReg); id++;
1086                 paintRectRegion(w-bw, w, 0, h, id|RC_BORDER_REG, chf, srcReg); id++;
1087                 paintRectRegion(0, w, 0, bh, id|RC_BORDER_REG, chf, srcReg); id++;
1088                 paintRectRegion(0, w, h-bh, h, id|RC_BORDER_REG, chf, srcReg); id++;
1089                 
1090                 chf.borderSize = borderSize;
1091         }
1092         
1093         rcIntArray prev(256);
1094
1095         // Sweep one line at a time.
1096         for (int y = borderSize; y < h-borderSize; ++y)
1097         {
1098                 // Collect spans from this row.
1099                 prev.resize(id+1);
1100                 memset(&prev[0],0,sizeof(int)*id);
1101                 unsigned short rid = 1;
1102                 
1103                 for (int x = borderSize; x < w-borderSize; ++x)
1104                 {
1105                         const rcCompactCell& c = chf.cells[x+y*w];
1106                         
1107                         for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
1108                         {
1109                                 const rcCompactSpan& s = chf.spans[i];
1110                                 if (chf.areas[i] == RC_NULL_AREA) continue;
1111                                 
1112                                 // -x
1113                                 unsigned short previd = 0;
1114                                 if (rcGetCon(s, 0) != RC_NOT_CONNECTED)
1115                                 {
1116                                         const int ax = x + rcGetDirOffsetX(0);
1117                                         const int ay = y + rcGetDirOffsetY(0);
1118                                         const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 0);
1119                                         if ((srcReg[ai] & RC_BORDER_REG) == 0 && chf.areas[i] == chf.areas[ai])
1120                                                 previd = srcReg[ai];
1121                                 }
1122                                 
1123                                 if (!previd)
1124                                 {
1125                                         previd = rid++;
1126                                         sweeps[previd].rid = previd;
1127                                         sweeps[previd].ns = 0;
1128                                         sweeps[previd].nei = 0;
1129                                 }
1130
1131                                 // -y
1132                                 if (rcGetCon(s,3) != RC_NOT_CONNECTED)
1133                                 {
1134                                         const int ax = x + rcGetDirOffsetX(3);
1135                                         const int ay = y + rcGetDirOffsetY(3);
1136                                         const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 3);
1137                                         if (srcReg[ai] && (srcReg[ai] & RC_BORDER_REG) == 0 && chf.areas[i] == chf.areas[ai])
1138                                         {
1139                                                 unsigned short nr = srcReg[ai];
1140                                                 if (!sweeps[previd].nei || sweeps[previd].nei == nr)
1141                                                 {
1142                                                         sweeps[previd].nei = nr;
1143                                                         sweeps[previd].ns++;
1144                                                         prev[nr]++;
1145                                                 }
1146                                                 else
1147                                                 {
1148                                                         sweeps[previd].nei = RC_NULL_NEI;
1149                                                 }
1150                                         }
1151                                 }
1152
1153                                 srcReg[i] = previd;
1154                         }
1155                 }
1156                 
1157                 // Create unique ID.
1158                 for (int i = 1; i < rid; ++i)
1159                 {
1160                         if (sweeps[i].nei != RC_NULL_NEI && sweeps[i].nei != 0 &&
1161                                 prev[sweeps[i].nei] == (int)sweeps[i].ns)
1162                         {
1163                                 sweeps[i].id = sweeps[i].nei;
1164                         }
1165                         else
1166                         {
1167                                 sweeps[i].id = id++;
1168                         }
1169                 }
1170                 
1171                 // Remap IDs
1172                 for (int x = borderSize; x < w-borderSize; ++x)
1173                 {
1174                         const rcCompactCell& c = chf.cells[x+y*w];
1175                         
1176                         for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
1177                         {
1178                                 if (srcReg[i] > 0 && srcReg[i] < rid)
1179                                         srcReg[i] = sweeps[srcReg[i]].id;
1180                         }
1181                 }
1182         }
1183
1184         ctx->startTimer(RC_TIMER_BUILD_REGIONS_FILTER);
1185
1186         // Filter out small regions.
1187         chf.maxRegions = id;
1188         if (!filterSmallRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg))
1189                 return false;
1190
1191         ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FILTER);
1192         
1193         // Store the result out.
1194         for (int i = 0; i < chf.spanCount; ++i)
1195                 chf.spans[i].reg = srcReg[i];
1196         
1197         ctx->stopTimer(RC_TIMER_BUILD_REGIONS);
1198
1199         return true;
1200 }
1201
1202 /// @par
1203 /// 
1204 /// Non-null regions will consist of connected, non-overlapping walkable spans that form a single contour.
1205 /// Contours will form simple polygons.
1206 /// 
1207 /// If multiple regions form an area that is smaller than @p minRegionArea, then all spans will be
1208 /// re-assigned to the zero (null) region.
1209 /// 
1210 /// Watershed partitioning can result in smaller than necessary regions, especially in diagonal corridors. 
1211 /// @p mergeRegionArea helps reduce unecessarily small regions.
1212 /// 
1213 /// See the #rcConfig documentation for more information on the configuration parameters.
1214 /// 
1215 /// The region data will be available via the rcCompactHeightfield::maxRegions
1216 /// and rcCompactSpan::reg fields.
1217 /// 
1218 /// @warning The distance field must be created using #rcBuildDistanceField before attempting to build regions.
1219 /// 
1220 /// @see rcCompactHeightfield, rcCompactSpan, rcBuildDistanceField, rcBuildRegionsMonotone, rcConfig
1221 bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf,
1222                                         const int borderSize, const int minRegionArea, const int mergeRegionArea)
1223 {
1224         rcAssert(ctx);
1225         
1226         ctx->startTimer(RC_TIMER_BUILD_REGIONS);
1227         
1228         const int w = chf.width;
1229         const int h = chf.height;
1230         
1231         rcScopedDelete<unsigned short> buf = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount*4, RC_ALLOC_TEMP);
1232         if (!buf)
1233         {
1234                 ctx->log(RC_LOG_ERROR, "rcBuildRegions: Out of memory 'tmp' (%d).", chf.spanCount*4);
1235                 return false;
1236         }
1237         
1238         ctx->startTimer(RC_TIMER_BUILD_REGIONS_WATERSHED);
1239         
1240         rcIntArray stack(1024);
1241         rcIntArray visited(1024);
1242         
1243         unsigned short* srcReg = buf;
1244         unsigned short* srcDist = buf+chf.spanCount;
1245         unsigned short* dstReg = buf+chf.spanCount*2;
1246         unsigned short* dstDist = buf+chf.spanCount*3;
1247         
1248         memset(srcReg, 0, sizeof(unsigned short)*chf.spanCount);
1249         memset(srcDist, 0, sizeof(unsigned short)*chf.spanCount);
1250         
1251         unsigned short regionId = 1;
1252         unsigned short level = (chf.maxDistance+1) & ~1;
1253
1254         // TODO: Figure better formula, expandIters defines how much the 
1255         // watershed "overflows" and simplifies the regions. Tying it to
1256         // agent radius was usually good indication how greedy it could be.
1257 //      const int expandIters = 4 + walkableRadius * 2;
1258         const int expandIters = 8;
1259
1260         if (borderSize > 0)
1261         {
1262                 // Make sure border will not overflow.
1263                 const int bw = rcMin(w, borderSize);
1264                 const int bh = rcMin(h, borderSize);
1265                 // Paint regions
1266                 paintRectRegion(0, bw, 0, h, regionId|RC_BORDER_REG, chf, srcReg); regionId++;
1267                 paintRectRegion(w-bw, w, 0, h, regionId|RC_BORDER_REG, chf, srcReg); regionId++;
1268                 paintRectRegion(0, w, 0, bh, regionId|RC_BORDER_REG, chf, srcReg); regionId++;
1269                 paintRectRegion(0, w, h-bh, h, regionId|RC_BORDER_REG, chf, srcReg); regionId++;
1270
1271                 chf.borderSize = borderSize;
1272         }
1273         
1274         while (level > 0)
1275         {
1276                 level = level >= 2 ? level-2 : 0;
1277                 
1278                 ctx->startTimer(RC_TIMER_BUILD_REGIONS_EXPAND);
1279                 
1280                 // Expand current regions until no empty connected cells found.
1281                 if (expandRegions(expandIters, level, chf, srcReg, srcDist, dstReg, dstDist, stack) != srcReg)
1282                 {
1283                         rcSwap(srcReg, dstReg);
1284                         rcSwap(srcDist, dstDist);
1285                 }
1286                 
1287                 ctx->stopTimer(RC_TIMER_BUILD_REGIONS_EXPAND);
1288                 
1289                 ctx->startTimer(RC_TIMER_BUILD_REGIONS_FLOOD);
1290                 
1291                 // Mark new regions with IDs.
1292                 for (int y = 0; y < h; ++y)
1293                 {
1294                         for (int x = 0; x < w; ++x)
1295                         {
1296                                 const rcCompactCell& c = chf.cells[x+y*w];
1297                                 for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
1298                                 {
1299                                         if (chf.dist[i] < level || srcReg[i] != 0 || chf.areas[i] == RC_NULL_AREA)
1300                                                 continue;
1301                                         if (floodRegion(x, y, i, level, regionId, chf, srcReg, srcDist, stack))
1302                                                 regionId++;
1303                                 }
1304                         }
1305                 }
1306                 
1307                 ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FLOOD);
1308         }
1309         
1310         // Expand current regions until no empty connected cells found.
1311         if (expandRegions(expandIters*8, 0, chf, srcReg, srcDist, dstReg, dstDist, stack) != srcReg)
1312         {
1313                 rcSwap(srcReg, dstReg);
1314                 rcSwap(srcDist, dstDist);
1315         }
1316         
1317         ctx->stopTimer(RC_TIMER_BUILD_REGIONS_WATERSHED);
1318         
1319         ctx->startTimer(RC_TIMER_BUILD_REGIONS_FILTER);
1320         
1321         // Filter out small regions.
1322         chf.maxRegions = regionId;
1323         if (!filterSmallRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg))
1324                 return false;
1325         
1326         ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FILTER);
1327                 
1328         // Write the result out.
1329         for (int i = 0; i < chf.spanCount; ++i)
1330                 chf.spans[i].reg = srcReg[i];
1331         
1332         ctx->stopTimer(RC_TIMER_BUILD_REGIONS);
1333         
1334         return true;
1335 }
1336
1337