← Back to branch summary

~rebel/horde3d/trunk

« back to all changes in this revision

Viewing changes to trunk/Tools/Dependencies/RecastNavigation/Recast/Source/RecastRegion.cpp

  • Committer: felix
  • Date: 2015-07-07 12:57:07 UTC
  • Revision ID: svn-v4:5ce291ac-9df0-446f-9e4f-d57731c4dda7::1699
- Updated RecastNavigation to latest version and fixed multiple issues.
- Adapted GameDetourComponent, GameDetourCrowdComponent, DetourCrowdDemo and AAA accordingly.

Show diffs side-by-side

added added

removed removed

Lines of Context:
trunk/Tools/Dependencies/RecastNavigation/Recast/Source/RecastRegion.cpp
286
286
                                if (nr & RC_BORDER_REG) // Do not take borders into account.
287
287
                                        continue;
288
288
                                if (nr != 0 && nr != r)
 
289
                                {
289
290
                                        ar = nr;
 
291
                                        break;
 
292
                                }
290
293
                                
291
294
                                const rcCompactSpan& as = chf.spans[ai];
292
295
                                
300
303
                                                continue;
301
304
                                        unsigned short nr2 = srcReg[ai2];
302
305
                                        if (nr2 != 0 && nr2 != r)
 
306
                                        {
303
307
                                                ar = nr2;
 
308
                                                break;
 
309
                                        }
304
310
                                }                               
305
311
                        }
306
312
                }
309
315
                        srcReg[ci] = 0;
310
316
                        continue;
311
317
                }
 
318
                
312
319
                count++;
313
320
                
314
321
                // Expand neighbours.
340
347
                                                                         rcCompactHeightfield& chf,
341
348
                                                                         unsigned short* srcReg, unsigned short* srcDist,
342
349
                                                                         unsigned short* dstReg, unsigned short* dstDist, 
343
 
                                                                         rcIntArray& stack)
 
350
                                                                         rcIntArray& stack,
 
351
                                                                         bool fillStack)
344
352
{
345
353
        const int w = chf.width;
346
354
        const int h = chf.height;
347
355
 
348
 
        // Find cells revealed by the raised level.
349
 
        stack.resize(0);
350
 
        for (int y = 0; y < h; ++y)
 
356
        if (fillStack)
351
357
        {
352
 
                for (int x = 0; x < w; ++x)
 
358
                // Find cells revealed by the raised level.
 
359
                stack.resize(0);
 
360
                for (int y = 0; y < h; ++y)
353
361
                {
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)
 
362
                        for (int x = 0; x < w; ++x)
356
363
                        {
357
 
                                if (chf.dist[i] >= level && srcReg[i] == 0 && chf.areas[i] != RC_NULL_AREA)
 
364
                                const rcCompactCell& c = chf.cells[x+y*w];
 
365
                                for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
358
366
                                {
359
 
                                        stack.push(x);
360
 
                                        stack.push(y);
361
 
                                        stack.push(i);
 
367
                                        if (chf.dist[i] >= level && srcReg[i] == 0 && chf.areas[i] != RC_NULL_AREA)
 
368
                                        {
 
369
                                                stack.push(x);
 
370
                                                stack.push(y);
 
371
                                                stack.push(i);
 
372
                                        }
362
373
                                }
363
374
                        }
364
375
                }
365
376
        }
366
 
        
 
377
        else // use cells in the input stack
 
378
        {
 
379
                // mark all cells which already have a region
 
380
                for (int j=0; j<stack.size(); j+=3)
 
381
                {
 
382
                        int i = stack[j+2];
 
383
                        if (srcReg[i] != 0)
 
384
                                stack[j+2] = -1;
 
385
                }
 
386
        }
 
387
 
367
388
        int iter = 0;
368
389
        while (stack.size() > 0)
369
390
        {
434
455
}
435
456
 
436
457
 
 
458
 
 
459
static void sortCellsByLevel(unsigned short startLevel,
 
460
                                                          rcCompactHeightfield& chf,
 
461
                                                          unsigned short* srcReg,
 
462
                                                          unsigned int nbStacks, rcIntArray* stacks,
 
463
                                                          unsigned short loglevelsPerStack) // the levels per stack (2 in our case) as a bit shift
 
464
{
 
465
        const int w = chf.width;
 
466
        const int h = chf.height;
 
467
        startLevel = startLevel >> loglevelsPerStack;
 
468
 
 
469
        for (unsigned int j=0; j<nbStacks; ++j)
 
470
                stacks[j].resize(0);
 
471
 
 
472
        // put all cells in the level range into the appropriate stacks
 
473
        for (int y = 0; y < h; ++y)
 
474
        {
 
475
                for (int x = 0; x < w; ++x)
 
476
                {
 
477
                        const rcCompactCell& c = chf.cells[x+y*w];
 
478
                        for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
 
479
                        {
 
480
                                if (chf.areas[i] == RC_NULL_AREA || srcReg[i] != 0)
 
481
                                        continue;
 
482
 
 
483
                                int level = chf.dist[i] >> loglevelsPerStack;
 
484
                                int sId = startLevel - level;
 
485
                                if (sId >= (int)nbStacks)
 
486
                                        continue;
 
487
                                if (sId < 0)
 
488
                                        sId = 0;
 
489
 
 
490
                                stacks[sId].push(x);
 
491
                                stacks[sId].push(y);
 
492
                                stacks[sId].push(i);
 
493
                        }
 
494
                }
 
495
        }
 
496
}
 
497
 
 
498
 
 
499
static void appendStacks(rcIntArray& srcStack, rcIntArray& dstStack,
 
500
                                                 unsigned short* srcReg)
 
501
{
 
502
        for (int j=0; j<srcStack.size(); j+=3)
 
503
        {
 
504
                int i = srcStack[j+2];
 
505
                if ((i < 0) || (srcReg[i] != 0))
 
506
                        continue;
 
507
                dstStack.push(srcStack[j]);
 
508
                dstStack.push(srcStack[j+1]);
 
509
                dstStack.push(srcStack[j+2]);
 
510
        }
 
511
}
 
512
 
437
513
struct rcRegion
438
514
{
439
515
        inline rcRegion(unsigned short i) :
441
517
                id(i),
442
518
                areaType(0),
443
519
                remap(false),
444
 
                visited(false)
 
520
                visited(false),
 
521
                overlap(false),
 
522
                connectsToBorder(false),
 
523
                ymin(0xffff),
 
524
                ymax(0)
445
525
        {}
446
526
        
447
527
        int spanCount;                                  // Number of spans belonging to this region
449
529
        unsigned char areaType;                 // Are type.
450
530
        bool remap;
451
531
        bool visited;
 
532
        bool overlap;
 
533
        bool connectsToBorder;
 
534
        unsigned short ymin, ymax;
452
535
        rcIntArray connections;
453
536
        rcIntArray floors;
454
537
};
693
776
        }
694
777
}
695
778
 
696
 
static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegionSize,
697
 
                                                           unsigned short& maxRegionId,
698
 
                                                           rcCompactHeightfield& chf,
699
 
                                                           unsigned short* srcReg)
 
779
 
 
780
static bool mergeAndFilterRegions(rcContext* ctx, int minRegionArea, int mergeRegionSize,
 
781
                                                                  unsigned short& maxRegionId,
 
782
                                                                  rcCompactHeightfield& chf,
 
783
                                                                  unsigned short* srcReg, rcIntArray& overlaps)
700
784
{
701
785
        const int w = chf.width;
702
786
        const int h = chf.height;
705
789
        rcRegion* regions = (rcRegion*)rcAlloc(sizeof(rcRegion)*nreg, RC_ALLOC_TEMP);
706
790
        if (!regions)
707
791
        {
708
 
                ctx->log(RC_LOG_ERROR, "filterSmallRegions: Out of memory 'regions' (%d).", nreg);
 
792
                ctx->log(RC_LOG_ERROR, "mergeAndFilterRegions: Out of memory 'regions' (%d).", nreg);
709
793
                return false;
710
794
        }
711
795
 
728
812
                                rcRegion& reg = regions[r];
729
813
                                reg.spanCount++;
730
814
                                
731
 
                                
732
815
                                // Update floors.
733
816
                                for (int j = (int)c.index; j < ni; ++j)
734
817
                                {
736
819
                                        unsigned short floorId = srcReg[j];
737
820
                                        if (floorId == 0 || floorId >= nreg)
738
821
                                                continue;
 
822
                                        if (floorId == r)
 
823
                                                reg.overlap = true;
739
824
                                        addUniqueFloorRegion(reg, floorId);
740
825
                                }
741
826
                                
831
916
                        }
832
917
                }
833
918
        }
834
 
                
 
919
        
835
920
        // Merge too small regions to neighbour regions.
836
921
        int mergeCount = 0 ;
837
922
        do
841
926
                {
842
927
                        rcRegion& reg = regions[i];
843
928
                        if (reg.id == 0 || (reg.id & RC_BORDER_REG))
844
 
                                continue;                       
 
929
                                continue;
 
930
                        if (reg.overlap)
 
931
                                continue;
845
932
                        if (reg.spanCount == 0)
846
933
                                continue;
847
934
                        
858
945
                        {
859
946
                                if (reg.connections[j] & RC_BORDER_REG) continue;
860
947
                                rcRegion& mreg = regions[reg.connections[j]];
861
 
                                if (mreg.id == 0 || (mreg.id & RC_BORDER_REG)) continue;
 
948
                                if (mreg.id == 0 || (mreg.id & RC_BORDER_REG) || mreg.overlap) continue;
862
949
                                if (mreg.spanCount < smallest &&
863
950
                                        canMergeWithRegion(reg, mreg) &&
864
951
                                        canMergeWithRegion(mreg, reg))
928
1015
                if ((srcReg[i] & RC_BORDER_REG) == 0)
929
1016
                        srcReg[i] = regions[srcReg[i]].id;
930
1017
        }
931
 
        
932
 
        for (int i = 0; i < nreg; ++i)
933
 
                regions[i].~rcRegion();
934
 
        rcFree(regions);
935
 
        
936
 
        return true;
937
 
}
 
1018
 
 
1019
        // Return regions that we found to be overlapping.
 
1020
        for (int i = 0; i < nreg; ++i)
 
1021
                if (regions[i].overlap)
 
1022
                        overlaps.push(regions[i].id);
 
1023
 
 
1024
        for (int i = 0; i < nreg; ++i)
 
1025
                regions[i].~rcRegion();
 
1026
        rcFree(regions);
 
1027
        
 
1028
        
 
1029
        return true;
 
1030
}
 
1031
 
 
1032
 
 
1033
static void addUniqueConnection(rcRegion& reg, int n)
 
1034
{
 
1035
        for (int i = 0; i < reg.connections.size(); ++i)
 
1036
                if (reg.connections[i] == n)
 
1037
                        return;
 
1038
        reg.connections.push(n);
 
1039
}
 
1040
 
 
1041
static bool mergeAndFilterLayerRegions(rcContext* ctx, int minRegionArea,
 
1042
                                                                           unsigned short& maxRegionId,
 
1043
                                                                           rcCompactHeightfield& chf,
 
1044
                                                                           unsigned short* srcReg, rcIntArray& overlaps)
 
1045
{
 
1046
        const int w = chf.width;
 
1047
        const int h = chf.height;
 
1048
        
 
1049
        const int nreg = maxRegionId+1;
 
1050
        rcRegion* regions = (rcRegion*)rcAlloc(sizeof(rcRegion)*nreg, RC_ALLOC_TEMP);
 
1051
        if (!regions)
 
1052
        {
 
1053
                ctx->log(RC_LOG_ERROR, "mergeAndFilterLayerRegions: Out of memory 'regions' (%d).", nreg);
 
1054
                return false;
 
1055
        }
 
1056
        
 
1057
        // Construct regions
 
1058
        for (int i = 0; i < nreg; ++i)
 
1059
                new(&regions[i]) rcRegion((unsigned short)i);
 
1060
        
 
1061
        // Find region neighbours and overlapping regions.
 
1062
        rcIntArray lregs(32);
 
1063
        for (int y = 0; y < h; ++y)
 
1064
        {
 
1065
                for (int x = 0; x < w; ++x)
 
1066
                {
 
1067
                        const rcCompactCell& c = chf.cells[x+y*w];
 
1068
 
 
1069
                        lregs.resize(0);
 
1070
                        
 
1071
                        for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
 
1072
                        {
 
1073
                                const rcCompactSpan& s = chf.spans[i];
 
1074
                                const unsigned short ri = srcReg[i];
 
1075
                                if (ri == 0 || ri >= nreg) continue;
 
1076
                                rcRegion& reg = regions[ri];
 
1077
                                
 
1078
                                reg.spanCount++;
 
1079
                                
 
1080
                                reg.ymin = rcMin(reg.ymin, s.y);
 
1081
                                reg.ymax = rcMax(reg.ymax, s.y);
 
1082
                                
 
1083
                                // Collect all region layers.
 
1084
                                lregs.push(ri);
 
1085
                                
 
1086
                                // Update neighbours
 
1087
                                for (int dir = 0; dir < 4; ++dir)
 
1088
                                {
 
1089
                                        if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
 
1090
                                        {
 
1091
                                                const int ax = x + rcGetDirOffsetX(dir);
 
1092
                                                const int ay = y + rcGetDirOffsetY(dir);
 
1093
                                                const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);
 
1094
                                                const unsigned short rai = srcReg[ai];
 
1095
                                                if (rai > 0 && rai < nreg && rai != ri)
 
1096
                                                        addUniqueConnection(reg, rai);
 
1097
                                                if (rai & RC_BORDER_REG)
 
1098
                                                        reg.connectsToBorder = true;
 
1099
                                        }
 
1100
                                }
 
1101
                                
 
1102
                        }
 
1103
                        
 
1104
                        // Update overlapping regions.
 
1105
                        for (int i = 0; i < lregs.size()-1; ++i)
 
1106
                        {
 
1107
                                for (int j = i+1; j < lregs.size(); ++j)
 
1108
                                {
 
1109
                                        if (lregs[i] != lregs[j])
 
1110
                                        {
 
1111
                                                rcRegion& ri = regions[lregs[i]];
 
1112
                                                rcRegion& rj = regions[lregs[j]];
 
1113
                                                addUniqueFloorRegion(ri, lregs[j]);
 
1114
                                                addUniqueFloorRegion(rj, lregs[i]);
 
1115
                                        }
 
1116
                                }
 
1117
                        }
 
1118
                        
 
1119
                }
 
1120
        }
 
1121
 
 
1122
        // Create 2D layers from regions.
 
1123
        unsigned short layerId = 1;
 
1124
 
 
1125
        for (int i = 0; i < nreg; ++i)
 
1126
                regions[i].id = 0;
 
1127
 
 
1128
        // Merge montone regions to create non-overlapping areas.
 
1129
        rcIntArray stack(32);
 
1130
        for (int i = 1; i < nreg; ++i)
 
1131
        {
 
1132
                rcRegion& root = regions[i];
 
1133
                // Skip already visited.
 
1134
                if (root.id != 0)
 
1135
                        continue;
 
1136
                
 
1137
                // Start search.
 
1138
                root.id = layerId;
 
1139
 
 
1140
                stack.resize(0);
 
1141
                stack.push(i);
 
1142
                
 
1143
                while (stack.size() > 0)
 
1144
                {
 
1145
                        // Pop front
 
1146
                        rcRegion& reg = regions[stack[0]];
 
1147
                        for (int j = 0; j < stack.size()-1; ++j)
 
1148
                                stack[j] = stack[j+1];
 
1149
                        stack.resize(stack.size()-1);
 
1150
                        
 
1151
                        const int ncons = (int)reg.connections.size();
 
1152
                        for (int j = 0; j < ncons; ++j)
 
1153
                        {
 
1154
                                const int nei = reg.connections[j];
 
1155
                                rcRegion& regn = regions[nei];
 
1156
                                // Skip already visited.
 
1157
                                if (regn.id != 0)
 
1158
                                        continue;
 
1159
                                // Skip if the neighbour is overlapping root region.
 
1160
                                bool overlap = false;
 
1161
                                for (int k = 0; k < root.floors.size(); k++)
 
1162
                                {
 
1163
                                        if (root.floors[k] == nei)
 
1164
                                        {
 
1165
                                                overlap = true;
 
1166
                                                break;
 
1167
                                        }
 
1168
                                }
 
1169
                                if (overlap)
 
1170
                                        continue;
 
1171
                                        
 
1172
                                // Deepen
 
1173
                                stack.push(nei);
 
1174
                                        
 
1175
                                // Mark layer id
 
1176
                                regn.id = layerId;
 
1177
                                // Merge current layers to root.
 
1178
                                for (int k = 0; k < regn.floors.size(); ++k)
 
1179
                                        addUniqueFloorRegion(root, regn.floors[k]);
 
1180
                                root.ymin = rcMin(root.ymin, regn.ymin);
 
1181
                                root.ymax = rcMax(root.ymax, regn.ymax);
 
1182
                                root.spanCount += regn.spanCount;
 
1183
                                regn.spanCount = 0;
 
1184
                                root.connectsToBorder = root.connectsToBorder || regn.connectsToBorder;
 
1185
                        }
 
1186
                }
 
1187
                
 
1188
                layerId++;
 
1189
        }
 
1190
        
 
1191
        // Remove small regions
 
1192
        for (int i = 0; i < nreg; ++i)
 
1193
        {
 
1194
                if (regions[i].spanCount > 0 && regions[i].spanCount < minRegionArea && !regions[i].connectsToBorder)
 
1195
                {
 
1196
                        unsigned short reg = regions[i].id;
 
1197
                        for (int j = 0; j < nreg; ++j)
 
1198
                                if (regions[j].id == reg)
 
1199
                                        regions[j].id = 0;
 
1200
                }
 
1201
        }
 
1202
        
 
1203
        // Compress region Ids.
 
1204
        for (int i = 0; i < nreg; ++i)
 
1205
        {
 
1206
                regions[i].remap = false;
 
1207
                if (regions[i].id == 0) continue;                               // Skip nil regions.
 
1208
                if (regions[i].id & RC_BORDER_REG) continue;    // Skip external regions.
 
1209
                regions[i].remap = true;
 
1210
        }
 
1211
        
 
1212
        unsigned short regIdGen = 0;
 
1213
        for (int i = 0; i < nreg; ++i)
 
1214
        {
 
1215
                if (!regions[i].remap)
 
1216
                        continue;
 
1217
                unsigned short oldId = regions[i].id;
 
1218
                unsigned short newId = ++regIdGen;
 
1219
                for (int j = i; j < nreg; ++j)
 
1220
                {
 
1221
                        if (regions[j].id == oldId)
 
1222
                        {
 
1223
                                regions[j].id = newId;
 
1224
                                regions[j].remap = false;
 
1225
                        }
 
1226
                }
 
1227
        }
 
1228
        maxRegionId = regIdGen;
 
1229
        
 
1230
        // Remap regions.
 
1231
        for (int i = 0; i < chf.spanCount; ++i)
 
1232
        {
 
1233
                if ((srcReg[i] & RC_BORDER_REG) == 0)
 
1234
                        srcReg[i] = regions[srcReg[i]].id;
 
1235
        }
 
1236
        
 
1237
        for (int i = 0; i < nreg; ++i)
 
1238
                regions[i].~rcRegion();
 
1239
        rcFree(regions);
 
1240
        
 
1241
        return true;
 
1242
}
 
1243
 
 
1244
 
938
1245
 
939
1246
/// @par
940
1247
/// 
1181
1488
                }
1182
1489
        }
1183
1490
 
 
1491
 
1184
1492
        ctx->startTimer(RC_TIMER_BUILD_REGIONS_FILTER);
1185
1493
 
1186
 
        // Filter out small regions.
 
1494
        // Merge regions and filter out small regions.
 
1495
        rcIntArray overlaps;
1187
1496
        chf.maxRegions = id;
1188
 
        if (!filterSmallRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg))
 
1497
        if (!mergeAndFilterRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg, overlaps))
1189
1498
                return false;
1190
1499
 
 
1500
        // Monotone partitioning does not generate overlapping regions.
 
1501
        
1191
1502
        ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FILTER);
1192
1503
        
1193
1504
        // Store the result out.
1236
1547
        }
1237
1548
        
1238
1549
        ctx->startTimer(RC_TIMER_BUILD_REGIONS_WATERSHED);
1239
 
        
 
1550
 
 
1551
        const int LOG_NB_STACKS = 3;
 
1552
        const int NB_STACKS = 1 << LOG_NB_STACKS;
 
1553
        rcIntArray lvlStacks[NB_STACKS];
 
1554
        for (int i=0; i<NB_STACKS; ++i)
 
1555
                lvlStacks[i].resize(1024);
 
1556
 
1240
1557
        rcIntArray stack(1024);
1241
1558
        rcIntArray visited(1024);
1242
1559
        
1271
1588
                chf.borderSize = borderSize;
1272
1589
        }
1273
1590
        
 
1591
        int sId = -1;
1274
1592
        while (level > 0)
1275
1593
        {
1276
1594
                level = level >= 2 ? level-2 : 0;
1277
 
                
 
1595
                sId = (sId+1) & (NB_STACKS-1);
 
1596
 
 
1597
//              ctx->startTimer(RC_TIMER_DIVIDE_TO_LEVELS);
 
1598
 
 
1599
                if (sId == 0)
 
1600
                        sortCellsByLevel(level, chf, srcReg, NB_STACKS, lvlStacks, 1);
 
1601
                else 
 
1602
                        appendStacks(lvlStacks[sId-1], lvlStacks[sId], srcReg); // copy left overs from last level
 
1603
 
 
1604
//              ctx->stopTimer(RC_TIMER_DIVIDE_TO_LEVELS);
 
1605
 
1278
1606
                ctx->startTimer(RC_TIMER_BUILD_REGIONS_EXPAND);
1279
1607
                
1280
1608
                // Expand current regions until no empty connected cells found.
1281
 
                if (expandRegions(expandIters, level, chf, srcReg, srcDist, dstReg, dstDist, stack) != srcReg)
 
1609
                if (expandRegions(expandIters, level, chf, srcReg, srcDist, dstReg, dstDist, lvlStacks[sId], false) != srcReg)
1282
1610
                {
1283
1611
                        rcSwap(srcReg, dstReg);
1284
1612
                        rcSwap(srcDist, dstDist);
1289
1617
                ctx->startTimer(RC_TIMER_BUILD_REGIONS_FLOOD);
1290
1618
                
1291
1619
                // Mark new regions with IDs.
1292
 
                for (int y = 0; y < h; ++y)
 
1620
                for (int j=0; j<lvlStacks[sId].size(); j+=3)
1293
1621
                {
1294
 
                        for (int x = 0; x < w; ++x)
 
1622
                        int x = lvlStacks[sId][j];
 
1623
                        int y = lvlStacks[sId][j+1];
 
1624
                        int i = lvlStacks[sId][j+2];
 
1625
                        if (i >= 0 && srcReg[i] == 0)
1295
1626
                        {
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
 
                                }
 
1627
                                if (floodRegion(x, y, i, level, regionId, chf, srcReg, srcDist, stack))
 
1628
                                        regionId++;
1304
1629
                        }
1305
1630
                }
1306
1631
                
1308
1633
        }
1309
1634
        
1310
1635
        // Expand current regions until no empty connected cells found.
1311
 
        if (expandRegions(expandIters*8, 0, chf, srcReg, srcDist, dstReg, dstDist, stack) != srcReg)
 
1636
        if (expandRegions(expandIters*8, 0, chf, srcReg, srcDist, dstReg, dstDist, stack, true) != srcReg)
1312
1637
        {
1313
1638
                rcSwap(srcReg, dstReg);
1314
1639
                rcSwap(srcDist, dstDist);
1318
1643
        
1319
1644
        ctx->startTimer(RC_TIMER_BUILD_REGIONS_FILTER);
1320
1645
        
1321
 
        // Filter out small regions.
 
1646
        // Merge regions and filter out smalle regions.
 
1647
        rcIntArray overlaps;
1322
1648
        chf.maxRegions = regionId;
1323
 
        if (!filterSmallRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg))
 
1649
        if (!mergeAndFilterRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg, overlaps))
1324
1650
                return false;
1325
 
        
 
1651
 
 
1652
        // If overlapping regions were found during merging, split those regions.
 
1653
        if (overlaps.size() > 0)
 
1654
        {
 
1655
                ctx->log(RC_LOG_ERROR, "rcBuildRegions: %d overlapping regions.", overlaps.size());
 
1656
        }
 
1657
 
1326
1658
        ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FILTER);
1327
1659
                
1328
1660
        // Write the result out.
1335
1667
}
1336
1668
 
1337
1669
 
 
1670
bool rcBuildLayerRegions(rcContext* ctx, rcCompactHeightfield& chf,
 
1671
                                                 const int borderSize, const int minRegionArea)
 
1672
{
 
1673
        rcAssert(ctx);
 
1674
        
 
1675
        ctx->startTimer(RC_TIMER_BUILD_REGIONS);
 
1676
        
 
1677
        const int w = chf.width;
 
1678
        const int h = chf.height;
 
1679
        unsigned short id = 1;
 
1680
        
 
1681
        rcScopedDelete<unsigned short> srcReg = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP);
 
1682
        if (!srcReg)
 
1683
        {
 
1684
                ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'src' (%d).", chf.spanCount);
 
1685
                return false;
 
1686
        }
 
1687
        memset(srcReg,0,sizeof(unsigned short)*chf.spanCount);
 
1688
        
 
1689
        const int nsweeps = rcMax(chf.width,chf.height);
 
1690
        rcScopedDelete<rcSweepSpan> sweeps = (rcSweepSpan*)rcAlloc(sizeof(rcSweepSpan)*nsweeps, RC_ALLOC_TEMP);
 
1691
        if (!sweeps)
 
1692
        {
 
1693
                ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'sweeps' (%d).", nsweeps);
 
1694
                return false;
 
1695
        }
 
1696
        
 
1697
        
 
1698
        // Mark border regions.
 
1699
        if (borderSize > 0)
 
1700
        {
 
1701
                // Make sure border will not overflow.
 
1702
                const int bw = rcMin(w, borderSize);
 
1703
                const int bh = rcMin(h, borderSize);
 
1704
                // Paint regions
 
1705
                paintRectRegion(0, bw, 0, h, id|RC_BORDER_REG, chf, srcReg); id++;
 
1706
                paintRectRegion(w-bw, w, 0, h, id|RC_BORDER_REG, chf, srcReg); id++;
 
1707
                paintRectRegion(0, w, 0, bh, id|RC_BORDER_REG, chf, srcReg); id++;
 
1708
                paintRectRegion(0, w, h-bh, h, id|RC_BORDER_REG, chf, srcReg); id++;
 
1709
                
 
1710
                chf.borderSize = borderSize;
 
1711
        }
 
1712
        
 
1713
        rcIntArray prev(256);
 
1714
        
 
1715
        // Sweep one line at a time.
 
1716
        for (int y = borderSize; y < h-borderSize; ++y)
 
1717
        {
 
1718
                // Collect spans from this row.
 
1719
                prev.resize(id+1);
 
1720
                memset(&prev[0],0,sizeof(int)*id);
 
1721
                unsigned short rid = 1;
 
1722
                
 
1723
                for (int x = borderSize; x < w-borderSize; ++x)
 
1724
                {
 
1725
                        const rcCompactCell& c = chf.cells[x+y*w];
 
1726
                        
 
1727
                        for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
 
1728
                        {
 
1729
                                const rcCompactSpan& s = chf.spans[i];
 
1730
                                if (chf.areas[i] == RC_NULL_AREA) continue;
 
1731
                                
 
1732
                                // -x
 
1733
                                unsigned short previd = 0;
 
1734
                                if (rcGetCon(s, 0) != RC_NOT_CONNECTED)
 
1735
                                {
 
1736
                                        const int ax = x + rcGetDirOffsetX(0);
 
1737
                                        const int ay = y + rcGetDirOffsetY(0);
 
1738
                                        const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 0);
 
1739
                                        if ((srcReg[ai] & RC_BORDER_REG) == 0 && chf.areas[i] == chf.areas[ai])
 
1740
                                                previd = srcReg[ai];
 
1741
                                }
 
1742
                                
 
1743
                                if (!previd)
 
1744
                                {
 
1745
                                        previd = rid++;
 
1746
                                        sweeps[previd].rid = previd;
 
1747
                                        sweeps[previd].ns = 0;
 
1748
                                        sweeps[previd].nei = 0;
 
1749
                                }
 
1750
                                
 
1751
                                // -y
 
1752
                                if (rcGetCon(s,3) != RC_NOT_CONNECTED)
 
1753
                                {
 
1754
                                        const int ax = x + rcGetDirOffsetX(3);
 
1755
                                        const int ay = y + rcGetDirOffsetY(3);
 
1756
                                        const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 3);
 
1757
                                        if (srcReg[ai] && (srcReg[ai] & RC_BORDER_REG) == 0 && chf.areas[i] == chf.areas[ai])
 
1758
                                        {
 
1759
                                                unsigned short nr = srcReg[ai];
 
1760
                                                if (!sweeps[previd].nei || sweeps[previd].nei == nr)
 
1761
                                                {
 
1762
                                                        sweeps[previd].nei = nr;
 
1763
                                                        sweeps[previd].ns++;
 
1764
                                                        prev[nr]++;
 
1765
                                                }
 
1766
                                                else
 
1767
                                                {
 
1768
                                                        sweeps[previd].nei = RC_NULL_NEI;
 
1769
                                                }
 
1770
                                        }
 
1771
                                }
 
1772
                                
 
1773
                                srcReg[i] = previd;
 
1774
                        }
 
1775
                }
 
1776
                
 
1777
                // Create unique ID.
 
1778
                for (int i = 1; i < rid; ++i)
 
1779
                {
 
1780
                        if (sweeps[i].nei != RC_NULL_NEI && sweeps[i].nei != 0 &&
 
1781
                                prev[sweeps[i].nei] == (int)sweeps[i].ns)
 
1782
                        {
 
1783
                                sweeps[i].id = sweeps[i].nei;
 
1784
                        }
 
1785
                        else
 
1786
                        {
 
1787
                                sweeps[i].id = id++;
 
1788
                        }
 
1789
                }
 
1790
                
 
1791
                // Remap IDs
 
1792
                for (int x = borderSize; x < w-borderSize; ++x)
 
1793
                {
 
1794
                        const rcCompactCell& c = chf.cells[x+y*w];
 
1795
                        
 
1796
                        for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
 
1797
                        {
 
1798
                                if (srcReg[i] > 0 && srcReg[i] < rid)
 
1799
                                        srcReg[i] = sweeps[srcReg[i]].id;
 
1800
                        }
 
1801
                }
 
1802
        }
 
1803
        
 
1804
        
 
1805
        ctx->startTimer(RC_TIMER_BUILD_REGIONS_FILTER);
 
1806
        
 
1807
        // Merge monotone regions to layers and remove small regions.
 
1808
        rcIntArray overlaps;
 
1809
        chf.maxRegions = id;
 
1810
        if (!mergeAndFilterLayerRegions(ctx, minRegionArea, chf.maxRegions, chf, srcReg, overlaps))
 
1811
                return false;
 
1812
        
 
1813
        ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FILTER);
 
1814
        
 
1815
        
 
1816
        // Store the result out.
 
1817
        for (int i = 0; i < chf.spanCount; ++i)
 
1818
                chf.spans[i].reg = srcReg[i];
 
1819
        
 
1820
        ctx->stopTimer(RC_TIMER_BUILD_REGIONS);
 
1821
        
 
1822
        return true;
 
1823
}