1//
2// Copyright (c) 2009-2010 Mikko Mononen memon@inside.org
3//
4// This software is provided 'as-is', without any express or implied
5// warranty. In no event will the authors be held liable for any damages
6// arising from the use of this software.
7// Permission is granted to anyone to use this software for any purpose,
8// including commercial applications, and to alter it and redistribute it
9// freely, subject to the following restrictions:
10// 1. The origin of this software must not be misrepresented; you must not
11// claim that you wrote the original software. If you use this software
12// in a product, an acknowledgment in the product documentation would be
13// appreciated but is not required.
14// 2. Altered source versions must be plainly marked as such, and must not be
15// misrepresented as being the original software.
16// 3. This notice may not be removed or altered from any source distribution.
17//
18
19#include <float.h>
20#include <math.h>
21#include <string.h>
22#include <stdlib.h>
23#include <stdio.h>
24#include "Recast.h"
25#include "RecastAlloc.h"
26#include "RecastAssert.h"
27
28namespace
29{
30struct LevelStackEntry
31{
32 LevelStackEntry(int x_, int y_, int index_) : x(x_), y(y_), index(index_) {}
33 int x;
34 int y;
35 int index;
36};
37} // namespace
38
39static void calculateDistanceField(rcCompactHeightfield& chf, unsigned short* src, unsigned short& maxDist)
40{
41 const int w = chf.width;
42 const int h = chf.height;
43
44 // Init distance and points.
45 for (int i = 0; i < chf.spanCount; ++i)
46 src[i] = 0xffff;
47
48 // Mark boundary cells.
49 for (int y = 0; y < h; ++y)
50 {
51 for (int x = 0; x < w; ++x)
52 {
53 const rcCompactCell& c = chf.cells[x+y*w];
54 for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
55 {
56 const rcCompactSpan& s = chf.spans[i];
57 const unsigned char area = chf.areas[i];
58
59 int nc = 0;
60 for (int dir = 0; dir < 4; ++dir)
61 {
62 if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
63 {
64 const int ax = x + rcGetDirOffsetX(dir);
65 const int ay = y + rcGetDirOffsetY(dir);
66 const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);
67 if (area == chf.areas[ai])
68 nc++;
69 }
70 }
71 if (nc != 4)
72 src[i] = 0;
73 }
74 }
75 }
76
77
78 // Pass 1
79 for (int y = 0; y < h; ++y)
80 {
81 for (int x = 0; x < w; ++x)
82 {
83 const rcCompactCell& c = chf.cells[x+y*w];
84 for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
85 {
86 const rcCompactSpan& s = chf.spans[i];
87
88 if (rcGetCon(s, 0) != RC_NOT_CONNECTED)
89 {
90 // (-1,0)
91 const int ax = x + rcGetDirOffsetX(0);
92 const int ay = y + rcGetDirOffsetY(0);
93 const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 0);
94 const rcCompactSpan& as = chf.spans[ai];
95 if (src[ai]+2 < src[i])
96 src[i] = src[ai]+2;
97
98 // (-1,-1)
99 if (rcGetCon(as, 3) != RC_NOT_CONNECTED)
100 {
101 const int aax = ax + rcGetDirOffsetX(3);
102 const int aay = ay + rcGetDirOffsetY(3);
103 const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 3);
104 if (src[aai]+3 < src[i])
105 src[i] = src[aai]+3;
106 }
107 }
108 if (rcGetCon(s, 3) != RC_NOT_CONNECTED)
109 {
110 // (0,-1)
111 const int ax = x + rcGetDirOffsetX(3);
112 const int ay = y + rcGetDirOffsetY(3);
113 const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 3);
114 const rcCompactSpan& as = chf.spans[ai];
115 if (src[ai]+2 < src[i])
116 src[i] = src[ai]+2;
117
118 // (1,-1)
119 if (rcGetCon(as, 2) != RC_NOT_CONNECTED)
120 {
121 const int aax = ax + rcGetDirOffsetX(2);
122 const int aay = ay + rcGetDirOffsetY(2);
123 const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 2);
124 if (src[aai]+3 < src[i])
125 src[i] = src[aai]+3;
126 }
127 }
128 }
129 }
130 }
131
132 // Pass 2
133 for (int y = h-1; y >= 0; --y)
134 {
135 for (int x = w-1; x >= 0; --x)
136 {
137 const rcCompactCell& c = chf.cells[x+y*w];
138 for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
139 {
140 const rcCompactSpan& s = chf.spans[i];
141
142 if (rcGetCon(s, 2) != RC_NOT_CONNECTED)
143 {
144 // (1,0)
145 const int ax = x + rcGetDirOffsetX(2);
146 const int ay = y + rcGetDirOffsetY(2);
147 const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 2);
148 const rcCompactSpan& as = chf.spans[ai];
149 if (src[ai]+2 < src[i])
150 src[i] = src[ai]+2;
151
152 // (1,1)
153 if (rcGetCon(as, 1) != RC_NOT_CONNECTED)
154 {
155 const int aax = ax + rcGetDirOffsetX(1);
156 const int aay = ay + rcGetDirOffsetY(1);
157 const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 1);
158 if (src[aai]+3 < src[i])
159 src[i] = src[aai]+3;
160 }
161 }
162 if (rcGetCon(s, 1) != RC_NOT_CONNECTED)
163 {
164 // (0,1)
165 const int ax = x + rcGetDirOffsetX(1);
166 const int ay = y + rcGetDirOffsetY(1);
167 const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 1);
168 const rcCompactSpan& as = chf.spans[ai];
169 if (src[ai]+2 < src[i])
170 src[i] = src[ai]+2;
171
172 // (-1,1)
173 if (rcGetCon(as, 0) != RC_NOT_CONNECTED)
174 {
175 const int aax = ax + rcGetDirOffsetX(0);
176 const int aay = ay + rcGetDirOffsetY(0);
177 const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 0);
178 if (src[aai]+3 < src[i])
179 src[i] = src[aai]+3;
180 }
181 }
182 }
183 }
184 }
185
186 maxDist = 0;
187 for (int i = 0; i < chf.spanCount; ++i)
188 maxDist = rcMax(src[i], maxDist);
189
190}
191
192static unsigned short* boxBlur(rcCompactHeightfield& chf, int thr,
193 unsigned short* src, unsigned short* dst)
194{
195 const int w = chf.width;
196 const int h = chf.height;
197
198 thr *= 2;
199
200 for (int y = 0; y < h; ++y)
201 {
202 for (int x = 0; x < w; ++x)
203 {
204 const rcCompactCell& c = chf.cells[x+y*w];
205 for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
206 {
207 const rcCompactSpan& s = chf.spans[i];
208 const unsigned short cd = src[i];
209 if (cd <= thr)
210 {
211 dst[i] = cd;
212 continue;
213 }
214
215 int d = (int)cd;
216 for (int dir = 0; dir < 4; ++dir)
217 {
218 if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
219 {
220 const int ax = x + rcGetDirOffsetX(dir);
221 const int ay = y + rcGetDirOffsetY(dir);
222 const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);
223 d += (int)src[ai];
224
225 const rcCompactSpan& as = chf.spans[ai];
226 const int dir2 = (dir+1) & 0x3;
227 if (rcGetCon(as, dir2) != RC_NOT_CONNECTED)
228 {
229 const int ax2 = ax + rcGetDirOffsetX(dir2);
230 const int ay2 = ay + rcGetDirOffsetY(dir2);
231 const int ai2 = (int)chf.cells[ax2+ay2*w].index + rcGetCon(as, dir2);
232 d += (int)src[ai2];
233 }
234 else
235 {
236 d += cd;
237 }
238 }
239 else
240 {
241 d += cd*2;
242 }
243 }
244 dst[i] = (unsigned short)((d+5)/9);
245 }
246 }
247 }
248 return dst;
249}
250
251
252static bool floodRegion(int x, int y, int i,
253 unsigned short level, unsigned short r,
254 rcCompactHeightfield& chf,
255 unsigned short* srcReg, unsigned short* srcDist,
256 rcTempVector<LevelStackEntry>& stack)
257{
258 const int w = chf.width;
259
260 const unsigned char area = chf.areas[i];
261
262 // Flood fill mark region.
263 stack.clear();
264 stack.push_back(LevelStackEntry(x, y, i));
265 srcReg[i] = r;
266 srcDist[i] = 0;
267
268 unsigned short lev = level >= 2 ? level-2 : 0;
269 int count = 0;
270
271 while (stack.size() > 0)
272 {
273 LevelStackEntry& back = stack.back();
274 int cx = back.x;
275 int cy = back.y;
276 int ci = back.index;
277 stack.pop_back();
278
279 const rcCompactSpan& cs = chf.spans[ci];
280
281 // Check if any of the neighbours already have a valid region set.
282 unsigned short ar = 0;
283 for (int dir = 0; dir < 4; ++dir)
284 {
285 // 8 connected
286 if (rcGetCon(cs, dir) != RC_NOT_CONNECTED)
287 {
288 const int ax = cx + rcGetDirOffsetX(dir);
289 const int ay = cy + rcGetDirOffsetY(dir);
290 const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(cs, dir);
291 if (chf.areas[ai] != area)
292 continue;
293 unsigned short nr = srcReg[ai];
294 if (nr & RC_BORDER_REG) // Do not take borders into account.
295 continue;
296 if (nr != 0 && nr != r)
297 {
298 ar = nr;
299 break;
300 }
301
302 const rcCompactSpan& as = chf.spans[ai];
303
304 const int dir2 = (dir+1) & 0x3;
305 if (rcGetCon(as, dir2) != RC_NOT_CONNECTED)
306 {
307 const int ax2 = ax + rcGetDirOffsetX(dir2);
308 const int ay2 = ay + rcGetDirOffsetY(dir2);
309 const int ai2 = (int)chf.cells[ax2+ay2*w].index + rcGetCon(as, dir2);
310 if (chf.areas[ai2] != area)
311 continue;
312 unsigned short nr2 = srcReg[ai2];
313 if (nr2 != 0 && nr2 != r)
314 {
315 ar = nr2;
316 break;
317 }
318 }
319 }
320 }
321 if (ar != 0)
322 {
323 srcReg[ci] = 0;
324 continue;
325 }
326
327 count++;
328
329 // Expand neighbours.
330 for (int dir = 0; dir < 4; ++dir)
331 {
332 if (rcGetCon(cs, dir) != RC_NOT_CONNECTED)
333 {
334 const int ax = cx + rcGetDirOffsetX(dir);
335 const int ay = cy + rcGetDirOffsetY(dir);
336 const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(cs, dir);
337 if (chf.areas[ai] != area)
338 continue;
339 if (chf.dist[ai] >= lev && srcReg[ai] == 0)
340 {
341 srcReg[ai] = r;
342 srcDist[ai] = 0;
343 stack.push_back(LevelStackEntry(ax, ay, ai));
344 }
345 }
346 }
347 }
348
349 return count > 0;
350}
351
352// Struct to keep track of entries in the region table that have been changed.
353struct DirtyEntry
354{
355 DirtyEntry(int index_, unsigned short region_, unsigned short distance2_)
356 : index(index_), region(region_), distance2(distance2_) {}
357 int index;
358 unsigned short region;
359 unsigned short distance2;
360};
361static void expandRegions(int maxIter, unsigned short level,
362 rcCompactHeightfield& chf,
363 unsigned short* srcReg, unsigned short* srcDist,
364 rcTempVector<LevelStackEntry>& stack,
365 bool fillStack)
366{
367 const int w = chf.width;
368 const int h = chf.height;
369
370 if (fillStack)
371 {
372 // Find cells revealed by the raised level.
373 stack.clear();
374 for (int y = 0; y < h; ++y)
375 {
376 for (int x = 0; x < w; ++x)
377 {
378 const rcCompactCell& c = chf.cells[x+y*w];
379 for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
380 {
381 if (chf.dist[i] >= level && srcReg[i] == 0 && chf.areas[i] != RC_NULL_AREA)
382 {
383 stack.push_back(LevelStackEntry(x, y, i));
384 }
385 }
386 }
387 }
388 }
389 else // use cells in the input stack
390 {
391 // mark all cells which already have a region
392 for (int j=0; j<stack.size(); j++)
393 {
394 int i = stack[j].index;
395 if (srcReg[i] != 0)
396 stack[j].index = -1;
397 }
398 }
399
400 rcTempVector<DirtyEntry> dirtyEntries;
401 int iter = 0;
402 while (stack.size() > 0)
403 {
404 int failed = 0;
405 dirtyEntries.clear();
406
407 for (int j = 0; j < stack.size(); j++)
408 {
409 int x = stack[j].x;
410 int y = stack[j].y;
411 int i = stack[j].index;
412 if (i < 0)
413 {
414 failed++;
415 continue;
416 }
417
418 unsigned short r = srcReg[i];
419 unsigned short d2 = 0xffff;
420 const unsigned char area = chf.areas[i];
421 const rcCompactSpan& s = chf.spans[i];
422 for (int dir = 0; dir < 4; ++dir)
423 {
424 if (rcGetCon(s, dir) == RC_NOT_CONNECTED) continue;
425 const int ax = x + rcGetDirOffsetX(dir);
426 const int ay = y + rcGetDirOffsetY(dir);
427 const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);
428 if (chf.areas[ai] != area) continue;
429 if (srcReg[ai] > 0 && (srcReg[ai] & RC_BORDER_REG) == 0)
430 {
431 if ((int)srcDist[ai]+2 < (int)d2)
432 {
433 r = srcReg[ai];
434 d2 = srcDist[ai]+2;
435 }
436 }
437 }
438 if (r)
439 {
440 stack[j].index = -1; // mark as used
441 dirtyEntries.push_back(DirtyEntry(i, r, d2));
442 }
443 else
444 {
445 failed++;
446 }
447 }
448
449 // Copy entries that differ between src and dst to keep them in sync.
450 for (int i = 0; i < dirtyEntries.size(); i++) {
451 int idx = dirtyEntries[i].index;
452 srcReg[idx] = dirtyEntries[i].region;
453 srcDist[idx] = dirtyEntries[i].distance2;
454 }
455
456 if (failed == stack.size())
457 break;
458
459 if (level > 0)
460 {
461 ++iter;
462 if (iter >= maxIter)
463 break;
464 }
465 }
466}
467
468
469
470static void sortCellsByLevel(unsigned short startLevel,
471 rcCompactHeightfield& chf,
472 const unsigned short* srcReg,
473 unsigned int nbStacks, rcTempVector<LevelStackEntry>* stacks,
474 unsigned short loglevelsPerStack) // the levels per stack (2 in our case) as a bit shift
475{
476 const int w = chf.width;
477 const int h = chf.height;
478 startLevel = startLevel >> loglevelsPerStack;
479
480 for (unsigned int j=0; j<nbStacks; ++j)
481 stacks[j].clear();
482
483 // put all cells in the level range into the appropriate stacks
484 for (int y = 0; y < h; ++y)
485 {
486 for (int x = 0; x < w; ++x)
487 {
488 const rcCompactCell& c = chf.cells[x+y*w];
489 for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
490 {
491 if (chf.areas[i] == RC_NULL_AREA || srcReg[i] != 0)
492 continue;
493
494 int level = chf.dist[i] >> loglevelsPerStack;
495 int sId = startLevel - level;
496 if (sId >= (int)nbStacks)
497 continue;
498 if (sId < 0)
499 sId = 0;
500
501 stacks[sId].push_back(LevelStackEntry(x, y, i));
502 }
503 }
504 }
505}
506
507
508static void appendStacks(const rcTempVector<LevelStackEntry>& srcStack,
509 rcTempVector<LevelStackEntry>& dstStack,
510 const unsigned short* srcReg)
511{
512 for (int j=0; j<srcStack.size(); j++)
513 {
514 int i = srcStack[j].index;
515 if ((i < 0) || (srcReg[i] != 0))
516 continue;
517 dstStack.push_back(srcStack[j]);
518 }
519}
520
521struct rcRegion
522{
523 inline rcRegion(unsigned short i) :
524 spanCount(0),
525 id(i),
526 areaType(0),
527 remap(false),
528 visited(false),
529 overlap(false),
530 connectsToBorder(false),
531 ymin(0xffff),
532 ymax(0)
533 {}
534
535 int spanCount; // Number of spans belonging to this region
536 unsigned short id; // ID of the region
537 unsigned char areaType; // Are type.
538 bool remap;
539 bool visited;
540 bool overlap;
541 bool connectsToBorder;
542 unsigned short ymin, ymax;
543 rcIntArray connections;
544 rcIntArray floors;
545};
546
547static void removeAdjacentNeighbours(rcRegion& reg)
548{
549 // Remove adjacent duplicates.
550 for (int i = 0; i < reg.connections.size() && reg.connections.size() > 1; )
551 {
552 int ni = (i+1) % reg.connections.size();
553 if (reg.connections[i] == reg.connections[ni])
554 {
555 // Remove duplicate
556 for (int j = i; j < reg.connections.size()-1; ++j)
557 reg.connections[j] = reg.connections[j+1];
558 reg.connections.pop();
559 }
560 else
561 ++i;
562 }
563}
564
565static void replaceNeighbour(rcRegion& reg, unsigned short oldId, unsigned short newId)
566{
567 bool neiChanged = false;
568 for (int i = 0; i < reg.connections.size(); ++i)
569 {
570 if (reg.connections[i] == oldId)
571 {
572 reg.connections[i] = newId;
573 neiChanged = true;
574 }
575 }
576 for (int i = 0; i < reg.floors.size(); ++i)
577 {
578 if (reg.floors[i] == oldId)
579 reg.floors[i] = newId;
580 }
581 if (neiChanged)
582 removeAdjacentNeighbours(reg);
583}
584
585static bool canMergeWithRegion(const rcRegion& rega, const rcRegion& regb)
586{
587 if (rega.areaType != regb.areaType)
588 return false;
589 int n = 0;
590 for (int i = 0; i < rega.connections.size(); ++i)
591 {
592 if (rega.connections[i] == regb.id)
593 n++;
594 }
595 if (n > 1)
596 return false;
597 for (int i = 0; i < rega.floors.size(); ++i)
598 {
599 if (rega.floors[i] == regb.id)
600 return false;
601 }
602 return true;
603}
604
605static void addUniqueFloorRegion(rcRegion& reg, int n)
606{
607 for (int i = 0; i < reg.floors.size(); ++i)
608 if (reg.floors[i] == n)
609 return;
610 reg.floors.push(n);
611}
612
613static bool mergeRegions(rcRegion& rega, rcRegion& regb)
614{
615 unsigned short aid = rega.id;
616 unsigned short bid = regb.id;
617
618 // Duplicate current neighbourhood.
619 rcIntArray acon;
620 acon.resize(rega.connections.size());
621 for (int i = 0; i < rega.connections.size(); ++i)
622 acon[i] = rega.connections[i];
623 rcIntArray& bcon = regb.connections;
624
625 // Find insertion point on A.
626 int insa = -1;
627 for (int i = 0; i < acon.size(); ++i)
628 {
629 if (acon[i] == bid)
630 {
631 insa = i;
632 break;
633 }
634 }
635 if (insa == -1)
636 return false;
637
638 // Find insertion point on B.
639 int insb = -1;
640 for (int i = 0; i < bcon.size(); ++i)
641 {
642 if (bcon[i] == aid)
643 {
644 insb = i;
645 break;
646 }
647 }
648 if (insb == -1)
649 return false;
650
651 // Merge neighbours.
652 rega.connections.clear();
653 for (int i = 0, ni = acon.size(); i < ni-1; ++i)
654 rega.connections.push(acon[(insa+1+i) % ni]);
655
656 for (int i = 0, ni = bcon.size(); i < ni-1; ++i)
657 rega.connections.push(bcon[(insb+1+i) % ni]);
658
659 removeAdjacentNeighbours(rega);
660
661 for (int j = 0; j < regb.floors.size(); ++j)
662 addUniqueFloorRegion(rega, regb.floors[j]);
663 rega.spanCount += regb.spanCount;
664 regb.spanCount = 0;
665 regb.connections.resize(0);
666
667 return true;
668}
669
670static bool isRegionConnectedToBorder(const rcRegion& reg)
671{
672 // Region is connected to border if
673 // one of the neighbours is null id.
674 for (int i = 0; i < reg.connections.size(); ++i)
675 {
676 if (reg.connections[i] == 0)
677 return true;
678 }
679 return false;
680}
681
682static bool isSolidEdge(rcCompactHeightfield& chf, const unsigned short* srcReg,
683 int x, int y, int i, int dir)
684{
685 const rcCompactSpan& s = chf.spans[i];
686 unsigned short r = 0;
687 if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
688 {
689 const int ax = x + rcGetDirOffsetX(dir);
690 const int ay = y + rcGetDirOffsetY(dir);
691 const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dir);
692 r = srcReg[ai];
693 }
694 if (r == srcReg[i])
695 return false;
696 return true;
697}
698
699static void walkContour(int x, int y, int i, int dir,
700 rcCompactHeightfield& chf,
701 const unsigned short* srcReg,
702 rcIntArray& cont)
703{
704 int startDir = dir;
705 int starti = i;
706
707 const rcCompactSpan& ss = chf.spans[i];
708 unsigned short curReg = 0;
709 if (rcGetCon(ss, dir) != RC_NOT_CONNECTED)
710 {
711 const int ax = x + rcGetDirOffsetX(dir);
712 const int ay = y + rcGetDirOffsetY(dir);
713 const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(ss, dir);
714 curReg = srcReg[ai];
715 }
716 cont.push(curReg);
717
718 int iter = 0;
719 while (++iter < 40000)
720 {
721 const rcCompactSpan& s = chf.spans[i];
722
723 if (isSolidEdge(chf, srcReg, x, y, i, dir))
724 {
725 // Choose the edge corner
726 unsigned short r = 0;
727 if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
728 {
729 const int ax = x + rcGetDirOffsetX(dir);
730 const int ay = y + rcGetDirOffsetY(dir);
731 const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dir);
732 r = srcReg[ai];
733 }
734 if (r != curReg)
735 {
736 curReg = r;
737 cont.push(curReg);
738 }
739
740 dir = (dir+1) & 0x3; // Rotate CW
741 }
742 else
743 {
744 int ni = -1;
745 const int nx = x + rcGetDirOffsetX(dir);
746 const int ny = y + rcGetDirOffsetY(dir);
747 if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
748 {
749 const rcCompactCell& nc = chf.cells[nx+ny*chf.width];
750 ni = (int)nc.index + rcGetCon(s, dir);
751 }
752 if (ni == -1)
753 {
754 // Should not happen.
755 return;
756 }
757 x = nx;
758 y = ny;
759 i = ni;
760 dir = (dir+3) & 0x3; // Rotate CCW
761 }
762
763 if (starti == i && startDir == dir)
764 {
765 break;
766 }
767 }
768
769 // Remove adjacent duplicates.
770 if (cont.size() > 1)
771 {
772 for (int j = 0; j < cont.size(); )
773 {
774 int nj = (j+1) % cont.size();
775 if (cont[j] == cont[nj])
776 {
777 for (int k = j; k < cont.size()-1; ++k)
778 cont[k] = cont[k+1];
779 cont.pop();
780 }
781 else
782 ++j;
783 }
784 }
785}
786
787
788static bool mergeAndFilterRegions(rcContext* ctx, int minRegionArea, int mergeRegionSize,
789 unsigned short& maxRegionId,
790 rcCompactHeightfield& chf,
791 unsigned short* srcReg, rcIntArray& overlaps)
792{
793 const int w = chf.width;
794 const int h = chf.height;
795
796 const int nreg = maxRegionId+1;
797 rcTempVector<rcRegion> regions;
798 if (!regions.reserve(nreg)) {
799 ctx->log(RC_LOG_ERROR, "mergeAndFilterRegions: Out of memory 'regions' (%d).", nreg);
800 return false;
801 }
802
803 // Construct regions
804 for (int i = 0; i < nreg; ++i)
805 regions.push_back(rcRegion((unsigned short) i));
806
807 // Find edge of a region and find connections around the contour.
808 for (int y = 0; y < h; ++y)
809 {
810 for (int x = 0; x < w; ++x)
811 {
812 const rcCompactCell& c = chf.cells[x+y*w];
813 for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
814 {
815 unsigned short r = srcReg[i];
816 if (r == 0 || r >= nreg)
817 continue;
818
819 rcRegion& reg = regions[r];
820 reg.spanCount++;
821
822 // Update floors.
823 for (int j = (int)c.index; j < ni; ++j)
824 {
825 if (i == j) continue;
826 unsigned short floorId = srcReg[j];
827 if (floorId == 0 || floorId >= nreg)
828 continue;
829 if (floorId == r)
830 reg.overlap = true;
831 addUniqueFloorRegion(reg, floorId);
832 }
833
834 // Have found contour
835 if (reg.connections.size() > 0)
836 continue;
837
838 reg.areaType = chf.areas[i];
839
840 // Check if this cell is next to a border.
841 int ndir = -1;
842 for (int dir = 0; dir < 4; ++dir)
843 {
844 if (isSolidEdge(chf, srcReg, x, y, i, dir))
845 {
846 ndir = dir;
847 break;
848 }
849 }
850
851 if (ndir != -1)
852 {
853 // The cell is at border.
854 // Walk around the contour to find all the neighbours.
855 walkContour(x, y, i, ndir, chf, srcReg, reg.connections);
856 }
857 }
858 }
859 }
860
861 // Remove too small regions.
862 rcIntArray stack(32);
863 rcIntArray trace(32);
864 for (int i = 0; i < nreg; ++i)
865 {
866 rcRegion& reg = regions[i];
867 if (reg.id == 0 || (reg.id & RC_BORDER_REG))
868 continue;
869 if (reg.spanCount == 0)
870 continue;
871 if (reg.visited)
872 continue;
873
874 // Count the total size of all the connected regions.
875 // Also keep track of the regions connects to a tile border.
876 bool connectsToBorder = false;
877 int spanCount = 0;
878 stack.clear();
879 trace.clear();
880
881 reg.visited = true;
882 stack.push(i);
883
884 while (stack.size())
885 {
886 // Pop
887 int ri = stack.pop();
888
889 rcRegion& creg = regions[ri];
890
891 spanCount += creg.spanCount;
892 trace.push(ri);
893
894 for (int j = 0; j < creg.connections.size(); ++j)
895 {
896 if (creg.connections[j] & RC_BORDER_REG)
897 {
898 connectsToBorder = true;
899 continue;
900 }
901 rcRegion& neireg = regions[creg.connections[j]];
902 if (neireg.visited)
903 continue;
904 if (neireg.id == 0 || (neireg.id & RC_BORDER_REG))
905 continue;
906 // Visit
907 stack.push(neireg.id);
908 neireg.visited = true;
909 }
910 }
911
912 // If the accumulated regions size is too small, remove it.
913 // Do not remove areas which connect to tile borders
914 // as their size cannot be estimated correctly and removing them
915 // can potentially remove necessary areas.
916 if (spanCount < minRegionArea && !connectsToBorder)
917 {
918 // Kill all visited regions.
919 for (int j = 0; j < trace.size(); ++j)
920 {
921 regions[trace[j]].spanCount = 0;
922 regions[trace[j]].id = 0;
923 }
924 }
925 }
926
927 // Merge too small regions to neighbour regions.
928 int mergeCount = 0 ;
929 do
930 {
931 mergeCount = 0;
932 for (int i = 0; i < nreg; ++i)
933 {
934 rcRegion& reg = regions[i];
935 if (reg.id == 0 || (reg.id & RC_BORDER_REG))
936 continue;
937 if (reg.overlap)
938 continue;
939 if (reg.spanCount == 0)
940 continue;
941
942 // Check to see if the region should be merged.
943 if (reg.spanCount > mergeRegionSize && isRegionConnectedToBorder(reg))
944 continue;
945
946 // Small region with more than 1 connection.
947 // Or region which is not connected to a border at all.
948 // Find smallest neighbour region that connects to this one.
949 int smallest = 0xfffffff;
950 unsigned short mergeId = reg.id;
951 for (int j = 0; j < reg.connections.size(); ++j)
952 {
953 if (reg.connections[j] & RC_BORDER_REG) continue;
954 rcRegion& mreg = regions[reg.connections[j]];
955 if (mreg.id == 0 || (mreg.id & RC_BORDER_REG) || mreg.overlap) continue;
956 if (mreg.spanCount < smallest &&
957 canMergeWithRegion(reg, mreg) &&
958 canMergeWithRegion(mreg, reg))
959 {
960 smallest = mreg.spanCount;
961 mergeId = mreg.id;
962 }
963 }
964 // Found new id.
965 if (mergeId != reg.id)
966 {
967 unsigned short oldId = reg.id;
968 rcRegion& target = regions[mergeId];
969
970 // Merge neighbours.
971 if (mergeRegions(target, reg))
972 {
973 // Fixup regions pointing to current region.
974 for (int j = 0; j < nreg; ++j)
975 {
976 if (regions[j].id == 0 || (regions[j].id & RC_BORDER_REG)) continue;
977 // If another region was already merged into current region
978 // change the nid of the previous region too.
979 if (regions[j].id == oldId)
980 regions[j].id = mergeId;
981 // Replace the current region with the new one if the
982 // current regions is neighbour.
983 replaceNeighbour(regions[j], oldId, mergeId);
984 }
985 mergeCount++;
986 }
987 }
988 }
989 }
990 while (mergeCount > 0);
991
992 // Compress region Ids.
993 for (int i = 0; i < nreg; ++i)
994 {
995 regions[i].remap = false;
996 if (regions[i].id == 0) continue; // Skip nil regions.
997 if (regions[i].id & RC_BORDER_REG) continue; // Skip external regions.
998 regions[i].remap = true;
999 }
1000
1001 unsigned short regIdGen = 0;
1002 for (int i = 0; i < nreg; ++i)
1003 {
1004 if (!regions[i].remap)
1005 continue;
1006 unsigned short oldId = regions[i].id;
1007 unsigned short newId = ++regIdGen;
1008 for (int j = i; j < nreg; ++j)
1009 {
1010 if (regions[j].id == oldId)
1011 {
1012 regions[j].id = newId;
1013 regions[j].remap = false;
1014 }
1015 }
1016 }
1017 maxRegionId = regIdGen;
1018
1019 // Remap regions.
1020 for (int i = 0; i < chf.spanCount; ++i)
1021 {
1022 if ((srcReg[i] & RC_BORDER_REG) == 0)
1023 srcReg[i] = regions[srcReg[i]].id;
1024 }
1025
1026 // Return regions that we found to be overlapping.
1027 for (int i = 0; i < nreg; ++i)
1028 if (regions[i].overlap)
1029 overlaps.push(regions[i].id);
1030
1031 return true;
1032}
1033
1034
1035static void addUniqueConnection(rcRegion& reg, int n)
1036{
1037 for (int i = 0; i < reg.connections.size(); ++i)
1038 if (reg.connections[i] == n)
1039 return;
1040 reg.connections.push(n);
1041}
1042
1043static bool mergeAndFilterLayerRegions(rcContext* ctx, int minRegionArea,
1044 unsigned short& maxRegionId,
1045 rcCompactHeightfield& chf,
1046 unsigned short* srcReg)
1047{
1048 const int w = chf.width;
1049 const int h = chf.height;
1050
1051 const int nreg = maxRegionId+1;
1052 rcTempVector<rcRegion> regions;
1053
1054 // Construct regions
1055 if (!regions.reserve(nreg)) {
1056 ctx->log(RC_LOG_ERROR, "mergeAndFilterLayerRegions: Out of memory 'regions' (%d).", nreg);
1057 return false;
1058 }
1059 for (int i = 0; i < nreg; ++i)
1060 regions.push_back(rcRegion((unsigned short) i));
1061
1062 // Find region neighbours and overlapping regions.
1063 rcIntArray lregs(32);
1064 for (int y = 0; y < h; ++y)
1065 {
1066 for (int x = 0; x < w; ++x)
1067 {
1068 const rcCompactCell& c = chf.cells[x+y*w];
1069
1070 lregs.clear();
1071
1072 for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
1073 {
1074 const rcCompactSpan& s = chf.spans[i];
1075 const unsigned short ri = srcReg[i];
1076 if (ri == 0 || ri >= nreg) continue;
1077 rcRegion& reg = regions[ri];
1078
1079 reg.spanCount++;
1080
1081 reg.ymin = rcMin(reg.ymin, s.y);
1082 reg.ymax = rcMax(reg.ymax, s.y);
1083
1084 // Collect all region layers.
1085 lregs.push(ri);
1086
1087 // Update neighbours
1088 for (int dir = 0; dir < 4; ++dir)
1089 {
1090 if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
1091 {
1092 const int ax = x + rcGetDirOffsetX(dir);
1093 const int ay = y + rcGetDirOffsetY(dir);
1094 const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);
1095 const unsigned short rai = srcReg[ai];
1096 if (rai > 0 && rai < nreg && rai != ri)
1097 addUniqueConnection(reg, rai);
1098 if (rai & RC_BORDER_REG)
1099 reg.connectsToBorder = true;
1100 }
1101 }
1102
1103 }
1104
1105 // Update overlapping regions.
1106 for (int i = 0; i < lregs.size()-1; ++i)
1107 {
1108 for (int j = i+1; j < lregs.size(); ++j)
1109 {
1110 if (lregs[i] != lregs[j])
1111 {
1112 rcRegion& ri = regions[lregs[i]];
1113 rcRegion& rj = regions[lregs[j]];
1114 addUniqueFloorRegion(ri, lregs[j]);
1115 addUniqueFloorRegion(rj, lregs[i]);
1116 }
1117 }
1118 }
1119
1120 }
1121 }
1122
1123 // Create 2D layers from regions.
1124 unsigned short layerId = 1;
1125
1126 for (int i = 0; i < nreg; ++i)
1127 regions[i].id = 0;
1128
1129 // Merge montone regions to create non-overlapping areas.
1130 rcIntArray stack(32);
1131 for (int i = 1; i < nreg; ++i)
1132 {
1133 rcRegion& root = regions[i];
1134 // Skip already visited.
1135 if (root.id != 0)
1136 continue;
1137
1138 // Start search.
1139 root.id = layerId;
1140
1141 stack.clear();
1142 stack.push(i);
1143
1144 while (stack.size() > 0)
1145 {
1146 // Pop front
1147 rcRegion& reg = regions[stack[0]];
1148 for (int j = 0; j < stack.size()-1; ++j)
1149 stack[j] = stack[j+1];
1150 stack.resize(stack.size()-1);
1151
1152 const int ncons = (int)reg.connections.size();
1153 for (int j = 0; j < ncons; ++j)
1154 {
1155 const int nei = reg.connections[j];
1156 rcRegion& regn = regions[nei];
1157 // Skip already visited.
1158 if (regn.id != 0)
1159 continue;
1160 // Skip if the neighbour is overlapping root region.
1161 bool overlap = false;
1162 for (int k = 0; k < root.floors.size(); k++)
1163 {
1164 if (root.floors[k] == nei)
1165 {
1166 overlap = true;
1167 break;
1168 }
1169 }
1170 if (overlap)
1171 continue;
1172
1173 // Deepen
1174 stack.push(nei);
1175
1176 // Mark layer id
1177 regn.id = layerId;
1178 // Merge current layers to root.
1179 for (int k = 0; k < regn.floors.size(); ++k)
1180 addUniqueFloorRegion(root, regn.floors[k]);
1181 root.ymin = rcMin(root.ymin, regn.ymin);
1182 root.ymax = rcMax(root.ymax, regn.ymax);
1183 root.spanCount += regn.spanCount;
1184 regn.spanCount = 0;
1185 root.connectsToBorder = root.connectsToBorder || regn.connectsToBorder;
1186 }
1187 }
1188
1189 layerId++;
1190 }
1191
1192 // Remove small regions
1193 for (int i = 0; i < nreg; ++i)
1194 {
1195 if (regions[i].spanCount > 0 && regions[i].spanCount < minRegionArea && !regions[i].connectsToBorder)
1196 {
1197 unsigned short reg = regions[i].id;
1198 for (int j = 0; j < nreg; ++j)
1199 if (regions[j].id == reg)
1200 regions[j].id = 0;
1201 }
1202 }
1203
1204 // Compress region Ids.
1205 for (int i = 0; i < nreg; ++i)
1206 {
1207 regions[i].remap = false;
1208 if (regions[i].id == 0) continue; // Skip nil regions.
1209 if (regions[i].id & RC_BORDER_REG) continue; // Skip external regions.
1210 regions[i].remap = true;
1211 }
1212
1213 unsigned short regIdGen = 0;
1214 for (int i = 0; i < nreg; ++i)
1215 {
1216 if (!regions[i].remap)
1217 continue;
1218 unsigned short oldId = regions[i].id;
1219 unsigned short newId = ++regIdGen;
1220 for (int j = i; j < nreg; ++j)
1221 {
1222 if (regions[j].id == oldId)
1223 {
1224 regions[j].id = newId;
1225 regions[j].remap = false;
1226 }
1227 }
1228 }
1229 maxRegionId = regIdGen;
1230
1231 // Remap regions.
1232 for (int i = 0; i < chf.spanCount; ++i)
1233 {
1234 if ((srcReg[i] & RC_BORDER_REG) == 0)
1235 srcReg[i] = regions[srcReg[i]].id;
1236 }
1237
1238 return true;
1239}
1240
1241
1242
1243/// @par
1244///
1245/// This is usually the second to the last step in creating a fully built
1246/// compact heightfield. This step is required before regions are built
1247/// using #rcBuildRegions or #rcBuildRegionsMonotone.
1248///
1249/// After this step, the distance data is available via the rcCompactHeightfield::maxDistance
1250/// and rcCompactHeightfield::dist fields.
1251///
1252/// @see rcCompactHeightfield, rcBuildRegions, rcBuildRegionsMonotone
1253bool rcBuildDistanceField(rcContext* ctx, rcCompactHeightfield& chf)
1254{
1255 rcAssert(ctx);
1256
1257 rcScopedTimer timer(ctx, RC_TIMER_BUILD_DISTANCEFIELD);
1258
1259 if (chf.dist)
1260 {
1261 rcFree(chf.dist);
1262 chf.dist = 0;
1263 }
1264
1265 unsigned short* src = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP);
1266 if (!src)
1267 {
1268 ctx->log(RC_LOG_ERROR, "rcBuildDistanceField: Out of memory 'src' (%d).", chf.spanCount);
1269 return false;
1270 }
1271 unsigned short* dst = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP);
1272 if (!dst)
1273 {
1274 ctx->log(RC_LOG_ERROR, "rcBuildDistanceField: Out of memory 'dst' (%d).", chf.spanCount);
1275 rcFree(src);
1276 return false;
1277 }
1278
1279 unsigned short maxDist = 0;
1280
1281 {
1282 rcScopedTimer timerDist(ctx, RC_TIMER_BUILD_DISTANCEFIELD_DIST);
1283
1284 calculateDistanceField(chf, src, maxDist);
1285 chf.maxDistance = maxDist;
1286 }
1287
1288 {
1289 rcScopedTimer timerBlur(ctx, RC_TIMER_BUILD_DISTANCEFIELD_BLUR);
1290
1291 // Blur
1292 if (boxBlur(chf, 1, src, dst) != src)
1293 rcSwap(src, dst);
1294
1295 // Store distance.
1296 chf.dist = src;
1297 }
1298
1299 rcFree(dst);
1300
1301 return true;
1302}
1303
1304static void paintRectRegion(int minx, int maxx, int miny, int maxy, unsigned short regId,
1305 rcCompactHeightfield& chf, unsigned short* srcReg)
1306{
1307 const int w = chf.width;
1308 for (int y = miny; y < maxy; ++y)
1309 {
1310 for (int x = minx; x < maxx; ++x)
1311 {
1312 const rcCompactCell& c = chf.cells[x+y*w];
1313 for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
1314 {
1315 if (chf.areas[i] != RC_NULL_AREA)
1316 srcReg[i] = regId;
1317 }
1318 }
1319 }
1320}
1321
1322
1323static const unsigned short RC_NULL_NEI = 0xffff;
1324
1325struct rcSweepSpan
1326{
1327 unsigned short rid; // row id
1328 unsigned short id; // region id
1329 unsigned short ns; // number samples
1330 unsigned short nei; // neighbour id
1331};
1332
1333/// @par
1334///
1335/// Non-null regions will consist of connected, non-overlapping walkable spans that form a single contour.
1336/// Contours will form simple polygons.
1337///
1338/// If multiple regions form an area that is smaller than @p minRegionArea, then all spans will be
1339/// re-assigned to the zero (null) region.
1340///
1341/// Partitioning can result in smaller than necessary regions. @p mergeRegionArea helps
1342/// reduce unecessarily small regions.
1343///
1344/// See the #rcConfig documentation for more information on the configuration parameters.
1345///
1346/// The region data will be available via the rcCompactHeightfield::maxRegions
1347/// and rcCompactSpan::reg fields.
1348///
1349/// @warning The distance field must be created using #rcBuildDistanceField before attempting to build regions.
1350///
1351/// @see rcCompactHeightfield, rcCompactSpan, rcBuildDistanceField, rcBuildRegionsMonotone, rcConfig
1352bool rcBuildRegionsMonotone(rcContext* ctx, rcCompactHeightfield& chf,
1353 const int borderSize, const int minRegionArea, const int mergeRegionArea)
1354{
1355 rcAssert(ctx);
1356
1357 rcScopedTimer timer(ctx, RC_TIMER_BUILD_REGIONS);
1358
1359 const int w = chf.width;
1360 const int h = chf.height;
1361 unsigned short id = 1;
1362
1363 rcScopedDelete<unsigned short> srcReg((unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP));
1364 if (!srcReg)
1365 {
1366 ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'src' (%d).", chf.spanCount);
1367 return false;
1368 }
1369 memset(srcReg,0,sizeof(unsigned short)*chf.spanCount);
1370
1371 const int nsweeps = rcMax(chf.width,chf.height);
1372 rcScopedDelete<rcSweepSpan> sweeps((rcSweepSpan*)rcAlloc(sizeof(rcSweepSpan)*nsweeps, RC_ALLOC_TEMP));
1373 if (!sweeps)
1374 {
1375 ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'sweeps' (%d).", nsweeps);
1376 return false;
1377 }
1378
1379
1380 // Mark border regions.
1381 if (borderSize > 0)
1382 {
1383 // Make sure border will not overflow.
1384 const int bw = rcMin(w, borderSize);
1385 const int bh = rcMin(h, borderSize);
1386 // Paint regions
1387 paintRectRegion(0, bw, 0, h, id|RC_BORDER_REG, chf, srcReg); id++;
1388 paintRectRegion(w-bw, w, 0, h, id|RC_BORDER_REG, chf, srcReg); id++;
1389 paintRectRegion(0, w, 0, bh, id|RC_BORDER_REG, chf, srcReg); id++;
1390 paintRectRegion(0, w, h-bh, h, id|RC_BORDER_REG, chf, srcReg); id++;
1391 }
1392
1393 chf.borderSize = borderSize;
1394
1395 rcIntArray prev(256);
1396
1397 // Sweep one line at a time.
1398 for (int y = borderSize; y < h-borderSize; ++y)
1399 {
1400 // Collect spans from this row.
1401 prev.resize(id+1);
1402 memset(&prev[0],0,sizeof(int)*id);
1403 unsigned short rid = 1;
1404
1405 for (int x = borderSize; x < w-borderSize; ++x)
1406 {
1407 const rcCompactCell& c = chf.cells[x+y*w];
1408
1409 for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
1410 {
1411 const rcCompactSpan& s = chf.spans[i];
1412 if (chf.areas[i] == RC_NULL_AREA) continue;
1413
1414 // -x
1415 unsigned short previd = 0;
1416 if (rcGetCon(s, 0) != RC_NOT_CONNECTED)
1417 {
1418 const int ax = x + rcGetDirOffsetX(0);
1419 const int ay = y + rcGetDirOffsetY(0);
1420 const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 0);
1421 if ((srcReg[ai] & RC_BORDER_REG) == 0 && chf.areas[i] == chf.areas[ai])
1422 previd = srcReg[ai];
1423 }
1424
1425 if (!previd)
1426 {
1427 previd = rid++;
1428 sweeps[previd].rid = previd;
1429 sweeps[previd].ns = 0;
1430 sweeps[previd].nei = 0;
1431 }
1432
1433 // -y
1434 if (rcGetCon(s,3) != RC_NOT_CONNECTED)
1435 {
1436 const int ax = x + rcGetDirOffsetX(3);
1437 const int ay = y + rcGetDirOffsetY(3);
1438 const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 3);
1439 if (srcReg[ai] && (srcReg[ai] & RC_BORDER_REG) == 0 && chf.areas[i] == chf.areas[ai])
1440 {
1441 unsigned short nr = srcReg[ai];
1442 if (!sweeps[previd].nei || sweeps[previd].nei == nr)
1443 {
1444 sweeps[previd].nei = nr;
1445 sweeps[previd].ns++;
1446 prev[nr]++;
1447 }
1448 else
1449 {
1450 sweeps[previd].nei = RC_NULL_NEI;
1451 }
1452 }
1453 }
1454
1455 srcReg[i] = previd;
1456 }
1457 }
1458
1459 // Create unique ID.
1460 for (int i = 1; i < rid; ++i)
1461 {
1462 if (sweeps[i].nei != RC_NULL_NEI && sweeps[i].nei != 0 &&
1463 prev[sweeps[i].nei] == (int)sweeps[i].ns)
1464 {
1465 sweeps[i].id = sweeps[i].nei;
1466 }
1467 else
1468 {
1469 sweeps[i].id = id++;
1470 }
1471 }
1472
1473 // Remap IDs
1474 for (int x = borderSize; x < w-borderSize; ++x)
1475 {
1476 const rcCompactCell& c = chf.cells[x+y*w];
1477
1478 for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
1479 {
1480 if (srcReg[i] > 0 && srcReg[i] < rid)
1481 srcReg[i] = sweeps[srcReg[i]].id;
1482 }
1483 }
1484 }
1485
1486
1487 {
1488 rcScopedTimer timerFilter(ctx, RC_TIMER_BUILD_REGIONS_FILTER);
1489
1490 // Merge regions and filter out small regions.
1491 rcIntArray overlaps;
1492 chf.maxRegions = id;
1493 if (!mergeAndFilterRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg, overlaps))
1494 return false;
1495
1496 // Monotone partitioning does not generate overlapping regions.
1497 }
1498
1499 // Store the result out.
1500 for (int i = 0; i < chf.spanCount; ++i)
1501 chf.spans[i].reg = srcReg[i];
1502
1503 return true;
1504}
1505
1506/// @par
1507///
1508/// Non-null regions will consist of connected, non-overlapping walkable spans that form a single contour.
1509/// Contours will form simple polygons.
1510///
1511/// If multiple regions form an area that is smaller than @p minRegionArea, then all spans will be
1512/// re-assigned to the zero (null) region.
1513///
1514/// Watershed partitioning can result in smaller than necessary regions, especially in diagonal corridors.
1515/// @p mergeRegionArea helps reduce unecessarily small regions.
1516///
1517/// See the #rcConfig documentation for more information on the configuration parameters.
1518///
1519/// The region data will be available via the rcCompactHeightfield::maxRegions
1520/// and rcCompactSpan::reg fields.
1521///
1522/// @warning The distance field must be created using #rcBuildDistanceField before attempting to build regions.
1523///
1524/// @see rcCompactHeightfield, rcCompactSpan, rcBuildDistanceField, rcBuildRegionsMonotone, rcConfig
1525bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf,
1526 const int borderSize, const int minRegionArea, const int mergeRegionArea)
1527{
1528 rcAssert(ctx);
1529
1530 rcScopedTimer timer(ctx, RC_TIMER_BUILD_REGIONS);
1531
1532 const int w = chf.width;
1533 const int h = chf.height;
1534
1535 rcScopedDelete<unsigned short> buf((unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount*2, RC_ALLOC_TEMP));
1536 if (!buf)
1537 {
1538 ctx->log(RC_LOG_ERROR, "rcBuildRegions: Out of memory 'tmp' (%d).", chf.spanCount*4);
1539 return false;
1540 }
1541
1542 ctx->startTimer(RC_TIMER_BUILD_REGIONS_WATERSHED);
1543
1544 const int LOG_NB_STACKS = 3;
1545 const int NB_STACKS = 1 << LOG_NB_STACKS;
1546 rcTempVector<LevelStackEntry> lvlStacks[NB_STACKS];
1547 for (int i=0; i<NB_STACKS; ++i)
1548 lvlStacks[i].reserve(256);
1549
1550 rcTempVector<LevelStackEntry> stack;
1551 stack.reserve(256);
1552
1553 unsigned short* srcReg = buf;
1554 unsigned short* srcDist = buf+chf.spanCount;
1555
1556 memset(srcReg, 0, sizeof(unsigned short)*chf.spanCount);
1557 memset(srcDist, 0, sizeof(unsigned short)*chf.spanCount);
1558
1559 unsigned short regionId = 1;
1560 unsigned short level = (chf.maxDistance+1) & ~1;
1561
1562 // TODO: Figure better formula, expandIters defines how much the
1563 // watershed "overflows" and simplifies the regions. Tying it to
1564 // agent radius was usually good indication how greedy it could be.
1565// const int expandIters = 4 + walkableRadius * 2;
1566 const int expandIters = 8;
1567
1568 if (borderSize > 0)
1569 {
1570 // Make sure border will not overflow.
1571 const int bw = rcMin(w, borderSize);
1572 const int bh = rcMin(h, borderSize);
1573
1574 // Paint regions
1575 paintRectRegion(0, bw, 0, h, regionId|RC_BORDER_REG, chf, srcReg); regionId++;
1576 paintRectRegion(w-bw, w, 0, h, regionId|RC_BORDER_REG, chf, srcReg); regionId++;
1577 paintRectRegion(0, w, 0, bh, regionId|RC_BORDER_REG, chf, srcReg); regionId++;
1578 paintRectRegion(0, w, h-bh, h, regionId|RC_BORDER_REG, chf, srcReg); regionId++;
1579 }
1580
1581 chf.borderSize = borderSize;
1582
1583 int sId = -1;
1584 while (level > 0)
1585 {
1586 level = level >= 2 ? level-2 : 0;
1587 sId = (sId+1) & (NB_STACKS-1);
1588
1589// ctx->startTimer(RC_TIMER_DIVIDE_TO_LEVELS);
1590
1591 if (sId == 0)
1592 sortCellsByLevel(level, chf, srcReg, NB_STACKS, lvlStacks, 1);
1593 else
1594 appendStacks(lvlStacks[sId-1], lvlStacks[sId], srcReg); // copy left overs from last level
1595
1596// ctx->stopTimer(RC_TIMER_DIVIDE_TO_LEVELS);
1597
1598 {
1599 rcScopedTimer timerExpand(ctx, RC_TIMER_BUILD_REGIONS_EXPAND);
1600
1601 // Expand current regions until no empty connected cells found.
1602 expandRegions(expandIters, level, chf, srcReg, srcDist, lvlStacks[sId], false);
1603 }
1604
1605 {
1606 rcScopedTimer timerFloor(ctx, RC_TIMER_BUILD_REGIONS_FLOOD);
1607
1608 // Mark new regions with IDs.
1609 for (int j = 0; j<lvlStacks[sId].size(); j++)
1610 {
1611 LevelStackEntry current = lvlStacks[sId][j];
1612 int x = current.x;
1613 int y = current.y;
1614 int i = current.index;
1615 if (i >= 0 && srcReg[i] == 0)
1616 {
1617 if (floodRegion(x, y, i, level, regionId, chf, srcReg, srcDist, stack))
1618 {
1619 if (regionId == 0xFFFF)
1620 {
1621 ctx->log(RC_LOG_ERROR, "rcBuildRegions: Region ID overflow");
1622 return false;
1623 }
1624
1625 regionId++;
1626 }
1627 }
1628 }
1629 }
1630 }
1631
1632 // Expand current regions until no empty connected cells found.
1633 expandRegions(expandIters*8, 0, chf, srcReg, srcDist, stack, true);
1634
1635 ctx->stopTimer(RC_TIMER_BUILD_REGIONS_WATERSHED);
1636
1637 {
1638 rcScopedTimer timerFilter(ctx, RC_TIMER_BUILD_REGIONS_FILTER);
1639
1640 // Merge regions and filter out smalle regions.
1641 rcIntArray overlaps;
1642 chf.maxRegions = regionId;
1643 if (!mergeAndFilterRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg, overlaps))
1644 return false;
1645
1646 // If overlapping regions were found during merging, split those regions.
1647 if (overlaps.size() > 0)
1648 {
1649 ctx->log(RC_LOG_ERROR, "rcBuildRegions: %d overlapping regions.", overlaps.size());
1650 }
1651 }
1652
1653 // Write the result out.
1654 for (int i = 0; i < chf.spanCount; ++i)
1655 chf.spans[i].reg = srcReg[i];
1656
1657 return true;
1658}
1659
1660
1661bool rcBuildLayerRegions(rcContext* ctx, rcCompactHeightfield& chf,
1662 const int borderSize, const int minRegionArea)
1663{
1664 rcAssert(ctx);
1665
1666 rcScopedTimer timer(ctx, RC_TIMER_BUILD_REGIONS);
1667
1668 const int w = chf.width;
1669 const int h = chf.height;
1670 unsigned short id = 1;
1671
1672 rcScopedDelete<unsigned short> srcReg((unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP));
1673 if (!srcReg)
1674 {
1675 ctx->log(RC_LOG_ERROR, "rcBuildLayerRegions: Out of memory 'src' (%d).", chf.spanCount);
1676 return false;
1677 }
1678 memset(srcReg,0,sizeof(unsigned short)*chf.spanCount);
1679
1680 const int nsweeps = rcMax(chf.width,chf.height);
1681 rcScopedDelete<rcSweepSpan> sweeps((rcSweepSpan*)rcAlloc(sizeof(rcSweepSpan)*nsweeps, RC_ALLOC_TEMP));
1682 if (!sweeps)
1683 {
1684 ctx->log(RC_LOG_ERROR, "rcBuildLayerRegions: Out of memory 'sweeps' (%d).", nsweeps);
1685 return false;
1686 }
1687
1688
1689 // Mark border regions.
1690 if (borderSize > 0)
1691 {
1692 // Make sure border will not overflow.
1693 const int bw = rcMin(w, borderSize);
1694 const int bh = rcMin(h, borderSize);
1695 // Paint regions
1696 paintRectRegion(0, bw, 0, h, id|RC_BORDER_REG, chf, srcReg); id++;
1697 paintRectRegion(w-bw, w, 0, h, id|RC_BORDER_REG, chf, srcReg); id++;
1698 paintRectRegion(0, w, 0, bh, id|RC_BORDER_REG, chf, srcReg); id++;
1699 paintRectRegion(0, w, h-bh, h, id|RC_BORDER_REG, chf, srcReg); id++;
1700 }
1701
1702 chf.borderSize = borderSize;
1703
1704 rcIntArray prev(256);
1705
1706 // Sweep one line at a time.
1707 for (int y = borderSize; y < h-borderSize; ++y)
1708 {
1709 // Collect spans from this row.
1710 prev.resize(id+1);
1711 memset(&prev[0],0,sizeof(int)*id);
1712 unsigned short rid = 1;
1713
1714 for (int x = borderSize; x < w-borderSize; ++x)
1715 {
1716 const rcCompactCell& c = chf.cells[x+y*w];
1717
1718 for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
1719 {
1720 const rcCompactSpan& s = chf.spans[i];
1721 if (chf.areas[i] == RC_NULL_AREA) continue;
1722
1723 // -x
1724 unsigned short previd = 0;
1725 if (rcGetCon(s, 0) != RC_NOT_CONNECTED)
1726 {
1727 const int ax = x + rcGetDirOffsetX(0);
1728 const int ay = y + rcGetDirOffsetY(0);
1729 const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 0);
1730 if ((srcReg[ai] & RC_BORDER_REG) == 0 && chf.areas[i] == chf.areas[ai])
1731 previd = srcReg[ai];
1732 }
1733
1734 if (!previd)
1735 {
1736 previd = rid++;
1737 sweeps[previd].rid = previd;
1738 sweeps[previd].ns = 0;
1739 sweeps[previd].nei = 0;
1740 }
1741
1742 // -y
1743 if (rcGetCon(s,3) != RC_NOT_CONNECTED)
1744 {
1745 const int ax = x + rcGetDirOffsetX(3);
1746 const int ay = y + rcGetDirOffsetY(3);
1747 const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 3);
1748 if (srcReg[ai] && (srcReg[ai] & RC_BORDER_REG) == 0 && chf.areas[i] == chf.areas[ai])
1749 {
1750 unsigned short nr = srcReg[ai];
1751 if (!sweeps[previd].nei || sweeps[previd].nei == nr)
1752 {
1753 sweeps[previd].nei = nr;
1754 sweeps[previd].ns++;
1755 prev[nr]++;
1756 }
1757 else
1758 {
1759 sweeps[previd].nei = RC_NULL_NEI;
1760 }
1761 }
1762 }
1763
1764 srcReg[i] = previd;
1765 }
1766 }
1767
1768 // Create unique ID.
1769 for (int i = 1; i < rid; ++i)
1770 {
1771 if (sweeps[i].nei != RC_NULL_NEI && sweeps[i].nei != 0 &&
1772 prev[sweeps[i].nei] == (int)sweeps[i].ns)
1773 {
1774 sweeps[i].id = sweeps[i].nei;
1775 }
1776 else
1777 {
1778 sweeps[i].id = id++;
1779 }
1780 }
1781
1782 // Remap IDs
1783 for (int x = borderSize; x < w-borderSize; ++x)
1784 {
1785 const rcCompactCell& c = chf.cells[x+y*w];
1786
1787 for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
1788 {
1789 if (srcReg[i] > 0 && srcReg[i] < rid)
1790 srcReg[i] = sweeps[srcReg[i]].id;
1791 }
1792 }
1793 }
1794
1795
1796 {
1797 rcScopedTimer timerFilter(ctx, RC_TIMER_BUILD_REGIONS_FILTER);
1798
1799 // Merge monotone regions to layers and remove small regions.
1800 chf.maxRegions = id;
1801 if (!mergeAndFilterLayerRegions(ctx, minRegionArea, chf.maxRegions, chf, srcReg))
1802 return false;
1803 }
1804
1805
1806 // Store the result out.
1807 for (int i = 0; i < chf.spanCount; ++i)
1808 chf.spans[i].reg = srcReg[i];
1809
1810 return true;
1811}
1812