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
28
29// Must be 255 or smaller (not 256) because layer IDs are stored as
30// a byte where 255 is a special value.
31#ifndef RC_MAX_LAYERS_DEF
32#define RC_MAX_LAYERS_DEF 63
33#endif
34
35#if RC_MAX_LAYERS_DEF > 255
36#error RC_MAX_LAYERS_DEF must be 255 or smaller
37#endif
38
39#ifndef RC_MAX_NEIS_DEF
40#define RC_MAX_NEIS_DEF 16
41#endif
42
43// Keep type checking.
44static const int RC_MAX_LAYERS = RC_MAX_LAYERS_DEF;
45static const int RC_MAX_NEIS = RC_MAX_NEIS_DEF;
46
47struct rcLayerRegion
48{
49 unsigned char layers[RC_MAX_LAYERS];
50 unsigned char neis[RC_MAX_NEIS];
51 unsigned short ymin, ymax;
52 unsigned char layerId; // Layer ID
53 unsigned char nlayers; // Layer count
54 unsigned char nneis; // Neighbour count
55 unsigned char base; // Flag indicating if the region is the base of merged regions.
56};
57
58
59static bool contains(const unsigned char* a, const unsigned char an, const unsigned char v)
60{
61 const int n = (int)an;
62 for (int i = 0; i < n; ++i)
63 {
64 if (a[i] == v)
65 return true;
66 }
67 return false;
68}
69
70static bool addUnique(unsigned char* a, unsigned char& an, int anMax, unsigned char v)
71{
72 if (contains(a, an, v))
73 return true;
74
75 if ((int)an >= anMax)
76 return false;
77
78 a[an] = v;
79 an++;
80 return true;
81}
82
83
84inline bool overlapRange(const unsigned short amin, const unsigned short amax,
85 const unsigned short bmin, const unsigned short bmax)
86{
87 return (amin > bmax || amax < bmin) ? false : true;
88}
89
90
91
92struct rcLayerSweepSpan
93{
94 unsigned short ns; // number samples
95 unsigned char id; // region id
96 unsigned char nei; // neighbour id
97};
98
99/// @par
100///
101/// See the #rcConfig documentation for more information on the configuration parameters.
102///
103/// @see rcAllocHeightfieldLayerSet, rcCompactHeightfield, rcHeightfieldLayerSet, rcConfig
104bool rcBuildHeightfieldLayers(rcContext* ctx, const rcCompactHeightfield& chf,
105 const int borderSize, const int walkableHeight,
106 rcHeightfieldLayerSet& lset)
107{
108 rcAssert(ctx);
109
110 rcScopedTimer timer(ctx, RC_TIMER_BUILD_LAYERS);
111
112 const int w = chf.width;
113 const int h = chf.height;
114
115 rcScopedDelete<unsigned char> srcReg((unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP));
116 if (!srcReg)
117 {
118 ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'srcReg' (%d).", chf.spanCount);
119 return false;
120 }
121 memset(srcReg,0xff,sizeof(unsigned char)*chf.spanCount);
122
123 const int nsweeps = chf.width;
124 rcScopedDelete<rcLayerSweepSpan> sweeps((rcLayerSweepSpan*)rcAlloc(sizeof(rcLayerSweepSpan)*nsweeps, RC_ALLOC_TEMP));
125 if (!sweeps)
126 {
127 ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'sweeps' (%d).", nsweeps);
128 return false;
129 }
130
131
132 // Partition walkable area into monotone regions.
133 int prevCount[256];
134 unsigned char regId = 0;
135
136 for (int y = borderSize; y < h-borderSize; ++y)
137 {
138 memset(prevCount,0,sizeof(int)*regId);
139 unsigned char sweepId = 0;
140
141 for (int x = borderSize; x < w-borderSize; ++x)
142 {
143 const rcCompactCell& c = chf.cells[x+y*w];
144
145 for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
146 {
147 const rcCompactSpan& s = chf.spans[i];
148 if (chf.areas[i] == RC_NULL_AREA) continue;
149
150 unsigned char sid = 0xff;
151
152 // -x
153 if (rcGetCon(s, 0) != RC_NOT_CONNECTED)
154 {
155 const int ax = x + rcGetDirOffsetX(0);
156 const int ay = y + rcGetDirOffsetY(0);
157 const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 0);
158 if (chf.areas[ai] != RC_NULL_AREA && srcReg[ai] != 0xff)
159 sid = srcReg[ai];
160 }
161
162 if (sid == 0xff)
163 {
164 sid = sweepId++;
165 sweeps[sid].nei = 0xff;
166 sweeps[sid].ns = 0;
167 }
168
169 // -y
170 if (rcGetCon(s,3) != RC_NOT_CONNECTED)
171 {
172 const int ax = x + rcGetDirOffsetX(3);
173 const int ay = y + rcGetDirOffsetY(3);
174 const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 3);
175 const unsigned char nr = srcReg[ai];
176 if (nr != 0xff)
177 {
178 // Set neighbour when first valid neighbour is encoutered.
179 if (sweeps[sid].ns == 0)
180 sweeps[sid].nei = nr;
181
182 if (sweeps[sid].nei == nr)
183 {
184 // Update existing neighbour
185 sweeps[sid].ns++;
186 prevCount[nr]++;
187 }
188 else
189 {
190 // This is hit if there is nore than one neighbour.
191 // Invalidate the neighbour.
192 sweeps[sid].nei = 0xff;
193 }
194 }
195 }
196
197 srcReg[i] = sid;
198 }
199 }
200
201 // Create unique ID.
202 for (int i = 0; i < sweepId; ++i)
203 {
204 // If the neighbour is set and there is only one continuous connection to it,
205 // the sweep will be merged with the previous one, else new region is created.
206 if (sweeps[i].nei != 0xff && prevCount[sweeps[i].nei] == (int)sweeps[i].ns)
207 {
208 sweeps[i].id = sweeps[i].nei;
209 }
210 else
211 {
212 if (regId == 255)
213 {
214 ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Region ID overflow.");
215 return false;
216 }
217 sweeps[i].id = regId++;
218 }
219 }
220
221 // Remap local sweep ids to region ids.
222 for (int x = borderSize; x < w-borderSize; ++x)
223 {
224 const rcCompactCell& c = chf.cells[x+y*w];
225 for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
226 {
227 if (srcReg[i] != 0xff)
228 srcReg[i] = sweeps[srcReg[i]].id;
229 }
230 }
231 }
232
233 // Allocate and init layer regions.
234 const int nregs = (int)regId;
235 rcScopedDelete<rcLayerRegion> regs((rcLayerRegion*)rcAlloc(sizeof(rcLayerRegion)*nregs, RC_ALLOC_TEMP));
236 if (!regs)
237 {
238 ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'regs' (%d).", nregs);
239 return false;
240 }
241 memset(regs, 0, sizeof(rcLayerRegion)*nregs);
242 for (int i = 0; i < nregs; ++i)
243 {
244 regs[i].layerId = 0xff;
245 regs[i].ymin = 0xffff;
246 regs[i].ymax = 0;
247 }
248
249 // Find region neighbours and overlapping regions.
250 for (int y = 0; y < h; ++y)
251 {
252 for (int x = 0; x < w; ++x)
253 {
254 const rcCompactCell& c = chf.cells[x+y*w];
255
256 unsigned char lregs[RC_MAX_LAYERS];
257 int nlregs = 0;
258
259 for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
260 {
261 const rcCompactSpan& s = chf.spans[i];
262 const unsigned char ri = srcReg[i];
263 if (ri == 0xff) continue;
264
265 regs[ri].ymin = rcMin(regs[ri].ymin, s.y);
266 regs[ri].ymax = rcMax(regs[ri].ymax, s.y);
267
268 // Collect all region layers.
269 if (nlregs < RC_MAX_LAYERS)
270 lregs[nlregs++] = ri;
271
272 // Update neighbours
273 for (int dir = 0; dir < 4; ++dir)
274 {
275 if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
276 {
277 const int ax = x + rcGetDirOffsetX(dir);
278 const int ay = y + rcGetDirOffsetY(dir);
279 const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);
280 const unsigned char rai = srcReg[ai];
281 if (rai != 0xff && rai != ri)
282 {
283 // Don't check return value -- if we cannot add the neighbor
284 // it will just cause a few more regions to be created, which
285 // is fine.
286 addUnique(regs[ri].neis, regs[ri].nneis, RC_MAX_NEIS, rai);
287 }
288 }
289 }
290
291 }
292
293 // Update overlapping regions.
294 for (int i = 0; i < nlregs-1; ++i)
295 {
296 for (int j = i+1; j < nlregs; ++j)
297 {
298 if (lregs[i] != lregs[j])
299 {
300 rcLayerRegion& ri = regs[lregs[i]];
301 rcLayerRegion& rj = regs[lregs[j]];
302
303 if (!addUnique(ri.layers, ri.nlayers, RC_MAX_LAYERS, lregs[j]) ||
304 !addUnique(rj.layers, rj.nlayers, RC_MAX_LAYERS, lregs[i]))
305 {
306 ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: layer overflow (too many overlapping walkable platforms). Try increasing RC_MAX_LAYERS.");
307 return false;
308 }
309 }
310 }
311 }
312
313 }
314 }
315
316 // Create 2D layers from regions.
317 unsigned char layerId = 0;
318
319 static const int MAX_STACK = 64;
320 unsigned char stack[MAX_STACK];
321 int nstack = 0;
322
323 for (int i = 0; i < nregs; ++i)
324 {
325 rcLayerRegion& root = regs[i];
326 // Skip already visited.
327 if (root.layerId != 0xff)
328 continue;
329
330 // Start search.
331 root.layerId = layerId;
332 root.base = 1;
333
334 nstack = 0;
335 stack[nstack++] = (unsigned char)i;
336
337 while (nstack)
338 {
339 // Pop front
340 rcLayerRegion& reg = regs[stack[0]];
341 nstack--;
342 for (int j = 0; j < nstack; ++j)
343 stack[j] = stack[j+1];
344
345 const int nneis = (int)reg.nneis;
346 for (int j = 0; j < nneis; ++j)
347 {
348 const unsigned char nei = reg.neis[j];
349 rcLayerRegion& regn = regs[nei];
350 // Skip already visited.
351 if (regn.layerId != 0xff)
352 continue;
353 // Skip if the neighbour is overlapping root region.
354 if (contains(root.layers, root.nlayers, nei))
355 continue;
356 // Skip if the height range would become too large.
357 const int ymin = rcMin(root.ymin, regn.ymin);
358 const int ymax = rcMax(root.ymax, regn.ymax);
359 if ((ymax - ymin) >= 255)
360 continue;
361
362 if (nstack < MAX_STACK)
363 {
364 // Deepen
365 stack[nstack++] = (unsigned char)nei;
366
367 // Mark layer id
368 regn.layerId = layerId;
369 // Merge current layers to root.
370 for (int k = 0; k < regn.nlayers; ++k)
371 {
372 if (!addUnique(root.layers, root.nlayers, RC_MAX_LAYERS, regn.layers[k]))
373 {
374 ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: layer overflow (too many overlapping walkable platforms). Try increasing RC_MAX_LAYERS.");
375 return false;
376 }
377 }
378 root.ymin = rcMin(root.ymin, regn.ymin);
379 root.ymax = rcMax(root.ymax, regn.ymax);
380 }
381 }
382 }
383
384 layerId++;
385 }
386
387 // Merge non-overlapping regions that are close in height.
388 const unsigned short mergeHeight = (unsigned short)walkableHeight * 4;
389
390 for (int i = 0; i < nregs; ++i)
391 {
392 rcLayerRegion& ri = regs[i];
393 if (!ri.base) continue;
394
395 unsigned char newId = ri.layerId;
396
397 for (;;)
398 {
399 unsigned char oldId = 0xff;
400
401 for (int j = 0; j < nregs; ++j)
402 {
403 if (i == j) continue;
404 rcLayerRegion& rj = regs[j];
405 if (!rj.base) continue;
406
407 // Skip if the regions are not close to each other.
408 if (!overlapRange(ri.ymin,ri.ymax+mergeHeight, rj.ymin,rj.ymax+mergeHeight))
409 continue;
410 // Skip if the height range would become too large.
411 const int ymin = rcMin(ri.ymin, rj.ymin);
412 const int ymax = rcMax(ri.ymax, rj.ymax);
413 if ((ymax - ymin) >= 255)
414 continue;
415
416 // Make sure that there is no overlap when merging 'ri' and 'rj'.
417 bool overlap = false;
418 // Iterate over all regions which have the same layerId as 'rj'
419 for (int k = 0; k < nregs; ++k)
420 {
421 if (regs[k].layerId != rj.layerId)
422 continue;
423 // Check if region 'k' is overlapping region 'ri'
424 // Index to 'regs' is the same as region id.
425 if (contains(ri.layers,ri.nlayers, (unsigned char)k))
426 {
427 overlap = true;
428 break;
429 }
430 }
431 // Cannot merge of regions overlap.
432 if (overlap)
433 continue;
434
435 // Can merge i and j.
436 oldId = rj.layerId;
437 break;
438 }
439
440 // Could not find anything to merge with, stop.
441 if (oldId == 0xff)
442 break;
443
444 // Merge
445 for (int j = 0; j < nregs; ++j)
446 {
447 rcLayerRegion& rj = regs[j];
448 if (rj.layerId == oldId)
449 {
450 rj.base = 0;
451 // Remap layerIds.
452 rj.layerId = newId;
453 // Add overlaid layers from 'rj' to 'ri'.
454 for (int k = 0; k < rj.nlayers; ++k)
455 {
456 if (!addUnique(ri.layers, ri.nlayers, RC_MAX_LAYERS, rj.layers[k]))
457 {
458 ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: layer overflow (too many overlapping walkable platforms). Try increasing RC_MAX_LAYERS.");
459 return false;
460 }
461 }
462
463 // Update height bounds.
464 ri.ymin = rcMin(ri.ymin, rj.ymin);
465 ri.ymax = rcMax(ri.ymax, rj.ymax);
466 }
467 }
468 }
469 }
470
471 // Compact layerIds
472 unsigned char remap[256];
473 memset(remap, 0, 256);
474
475 // Find number of unique layers.
476 layerId = 0;
477 for (int i = 0; i < nregs; ++i)
478 remap[regs[i].layerId] = 1;
479 for (int i = 0; i < 256; ++i)
480 {
481 if (remap[i])
482 remap[i] = layerId++;
483 else
484 remap[i] = 0xff;
485 }
486 // Remap ids.
487 for (int i = 0; i < nregs; ++i)
488 regs[i].layerId = remap[regs[i].layerId];
489
490 // No layers, return empty.
491 if (layerId == 0)
492 return true;
493
494 // Create layers.
495 rcAssert(lset.layers == 0);
496
497 const int lw = w - borderSize*2;
498 const int lh = h - borderSize*2;
499
500 // Build contracted bbox for layers.
501 float bmin[3], bmax[3];
502 rcVcopy(bmin, chf.bmin);
503 rcVcopy(bmax, chf.bmax);
504 bmin[0] += borderSize*chf.cs;
505 bmin[2] += borderSize*chf.cs;
506 bmax[0] -= borderSize*chf.cs;
507 bmax[2] -= borderSize*chf.cs;
508
509 lset.nlayers = (int)layerId;
510
511 lset.layers = (rcHeightfieldLayer*)rcAlloc(sizeof(rcHeightfieldLayer)*lset.nlayers, RC_ALLOC_PERM);
512 if (!lset.layers)
513 {
514 ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'layers' (%d).", lset.nlayers);
515 return false;
516 }
517 memset(lset.layers, 0, sizeof(rcHeightfieldLayer)*lset.nlayers);
518
519
520 // Store layers.
521 for (int i = 0; i < lset.nlayers; ++i)
522 {
523 unsigned char curId = (unsigned char)i;
524
525 rcHeightfieldLayer* layer = &lset.layers[i];
526
527 const int gridSize = sizeof(unsigned char)*lw*lh;
528
529 layer->heights = (unsigned char*)rcAlloc(gridSize, RC_ALLOC_PERM);
530 if (!layer->heights)
531 {
532 ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'heights' (%d).", gridSize);
533 return false;
534 }
535 memset(layer->heights, 0xff, gridSize);
536
537 layer->areas = (unsigned char*)rcAlloc(gridSize, RC_ALLOC_PERM);
538 if (!layer->areas)
539 {
540 ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'areas' (%d).", gridSize);
541 return false;
542 }
543 memset(layer->areas, 0, gridSize);
544
545 layer->cons = (unsigned char*)rcAlloc(gridSize, RC_ALLOC_PERM);
546 if (!layer->cons)
547 {
548 ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'cons' (%d).", gridSize);
549 return false;
550 }
551 memset(layer->cons, 0, gridSize);
552
553 // Find layer height bounds.
554 int hmin = 0, hmax = 0;
555 for (int j = 0; j < nregs; ++j)
556 {
557 if (regs[j].base && regs[j].layerId == curId)
558 {
559 hmin = (int)regs[j].ymin;
560 hmax = (int)regs[j].ymax;
561 }
562 }
563
564 layer->width = lw;
565 layer->height = lh;
566 layer->cs = chf.cs;
567 layer->ch = chf.ch;
568
569 // Adjust the bbox to fit the heightfield.
570 rcVcopy(layer->bmin, bmin);
571 rcVcopy(layer->bmax, bmax);
572 layer->bmin[1] = bmin[1] + hmin*chf.ch;
573 layer->bmax[1] = bmin[1] + hmax*chf.ch;
574 layer->hmin = hmin;
575 layer->hmax = hmax;
576
577 // Update usable data region.
578 layer->minx = layer->width;
579 layer->maxx = 0;
580 layer->miny = layer->height;
581 layer->maxy = 0;
582
583 // Copy height and area from compact heightfield.
584 for (int y = 0; y < lh; ++y)
585 {
586 for (int x = 0; x < lw; ++x)
587 {
588 const int cx = borderSize+x;
589 const int cy = borderSize+y;
590 const rcCompactCell& c = chf.cells[cx+cy*w];
591 for (int j = (int)c.index, nj = (int)(c.index+c.count); j < nj; ++j)
592 {
593 const rcCompactSpan& s = chf.spans[j];
594 // Skip unassigned regions.
595 if (srcReg[j] == 0xff)
596 continue;
597 // Skip of does nto belong to current layer.
598 unsigned char lid = regs[srcReg[j]].layerId;
599 if (lid != curId)
600 continue;
601
602 // Update data bounds.
603 layer->minx = rcMin(layer->minx, x);
604 layer->maxx = rcMax(layer->maxx, x);
605 layer->miny = rcMin(layer->miny, y);
606 layer->maxy = rcMax(layer->maxy, y);
607
608 // Store height and area type.
609 const int idx = x+y*lw;
610 layer->heights[idx] = (unsigned char)(s.y - hmin);
611 layer->areas[idx] = chf.areas[j];
612
613 // Check connection.
614 unsigned char portal = 0;
615 unsigned char con = 0;
616 for (int dir = 0; dir < 4; ++dir)
617 {
618 if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
619 {
620 const int ax = cx + rcGetDirOffsetX(dir);
621 const int ay = cy + rcGetDirOffsetY(dir);
622 const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);
623 unsigned char alid = srcReg[ai] != 0xff ? regs[srcReg[ai]].layerId : 0xff;
624 // Portal mask
625 if (chf.areas[ai] != RC_NULL_AREA && lid != alid)
626 {
627 portal |= (unsigned char)(1<<dir);
628 // Update height so that it matches on both sides of the portal.
629 const rcCompactSpan& as = chf.spans[ai];
630 if (as.y > hmin)
631 layer->heights[idx] = rcMax(layer->heights[idx], (unsigned char)(as.y - hmin));
632 }
633 // Valid connection mask
634 if (chf.areas[ai] != RC_NULL_AREA && lid == alid)
635 {
636 const int nx = ax - borderSize;
637 const int ny = ay - borderSize;
638 if (nx >= 0 && ny >= 0 && nx < lw && ny < lh)
639 con |= (unsigned char)(1<<dir);
640 }
641 }
642 }
643
644 layer->cons[idx] = (portal << 4) | con;
645 }
646 }
647 }
648
649 if (layer->minx > layer->maxx)
650 layer->minx = layer->maxx = 0;
651 if (layer->miny > layer->maxy)
652 layer->miny = layer->maxy = 0;
653 }
654
655 return true;
656}
657