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