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 "Recast.h" |
20 | #include "RecastAssert.h" |
21 | |
22 | #include <stdlib.h> |
23 | |
24 | void rcFilterLowHangingWalkableObstacles(rcContext* context, const int walkableClimb, rcHeightfield& heightfield) |
25 | { |
26 | rcAssert(context); |
27 | |
28 | rcScopedTimer timer(context, RC_TIMER_FILTER_LOW_OBSTACLES); |
29 | |
30 | const int xSize = heightfield.width; |
31 | const int zSize = heightfield.height; |
32 | |
33 | for (int z = 0; z < zSize; ++z) |
34 | { |
35 | for (int x = 0; x < xSize; ++x) |
36 | { |
37 | rcSpan* previousSpan = NULL; |
38 | bool previousWasWalkable = false; |
39 | unsigned char previousArea = RC_NULL_AREA; |
40 | |
41 | for (rcSpan* span = heightfield.spans[x + z * xSize]; span != NULL; previousSpan = span, span = span->next) |
42 | { |
43 | const bool walkable = span->area != RC_NULL_AREA; |
44 | // If current span is not walkable, but there is walkable |
45 | // span just below it, mark the span above it walkable too. |
46 | if (!walkable && previousWasWalkable) |
47 | { |
48 | if (rcAbs((int)span->smax - (int)previousSpan->smax) <= walkableClimb) |
49 | { |
50 | span->area = previousArea; |
51 | } |
52 | } |
53 | // Copy walkable flag so that it cannot propagate |
54 | // past multiple non-walkable objects. |
55 | previousWasWalkable = walkable; |
56 | previousArea = span->area; |
57 | } |
58 | } |
59 | } |
60 | } |
61 | |
62 | void rcFilterLedgeSpans(rcContext* context, const int walkableHeight, const int walkableClimb, |
63 | rcHeightfield& heightfield) |
64 | { |
65 | rcAssert(context); |
66 | |
67 | rcScopedTimer timer(context, RC_TIMER_FILTER_BORDER); |
68 | |
69 | const int xSize = heightfield.width; |
70 | const int zSize = heightfield.height; |
71 | const int MAX_HEIGHT = 0xffff; // TODO (graham): Move this to a more visible constant and update usages. |
72 | |
73 | // Mark border spans. |
74 | for (int z = 0; z < zSize; ++z) |
75 | { |
76 | for (int x = 0; x < xSize; ++x) |
77 | { |
78 | for (rcSpan* span = heightfield.spans[x + z * xSize]; span; span = span->next) |
79 | { |
80 | // Skip non walkable spans. |
81 | if (span->area == RC_NULL_AREA) |
82 | { |
83 | continue; |
84 | } |
85 | |
86 | const int bot = (int)(span->smax); |
87 | const int top = span->next ? (int)(span->next->smin) : MAX_HEIGHT; |
88 | |
89 | // Find neighbours minimum height. |
90 | int minNeighborHeight = MAX_HEIGHT; |
91 | |
92 | // Min and max height of accessible neighbours. |
93 | int accessibleNeighborMinHeight = span->smax; |
94 | int accessibleNeighborMaxHeight = span->smax; |
95 | |
96 | for (int direction = 0; direction < 4; ++direction) |
97 | { |
98 | int dx = x + rcGetDirOffsetX(direction); |
99 | int dy = z + rcGetDirOffsetY(direction); |
100 | // Skip neighbours which are out of bounds. |
101 | if (dx < 0 || dy < 0 || dx >= xSize || dy >= zSize) |
102 | { |
103 | minNeighborHeight = rcMin(minNeighborHeight, -walkableClimb - bot); |
104 | continue; |
105 | } |
106 | |
107 | // From minus infinity to the first span. |
108 | const rcSpan* neighborSpan = heightfield.spans[dx + dy * xSize]; |
109 | int neighborBot = -walkableClimb; |
110 | int neighborTop = neighborSpan ? (int)neighborSpan->smin : MAX_HEIGHT; |
111 | |
112 | // Skip neighbour if the gap between the spans is too small. |
113 | if (rcMin(top, neighborTop) - rcMax(bot, neighborBot) > walkableHeight) |
114 | { |
115 | minNeighborHeight = rcMin(minNeighborHeight, neighborBot - bot); |
116 | } |
117 | |
118 | // Rest of the spans. |
119 | for (neighborSpan = heightfield.spans[dx + dy * xSize]; neighborSpan; neighborSpan = neighborSpan->next) |
120 | { |
121 | neighborBot = (int)neighborSpan->smax; |
122 | neighborTop = neighborSpan->next ? (int)neighborSpan->next->smin : MAX_HEIGHT; |
123 | |
124 | // Skip neighbour if the gap between the spans is too small. |
125 | if (rcMin(top, neighborTop) - rcMax(bot, neighborBot) > walkableHeight) |
126 | { |
127 | minNeighborHeight = rcMin(minNeighborHeight, neighborBot - bot); |
128 | |
129 | // Find min/max accessible neighbour height. |
130 | if (rcAbs(neighborBot - bot) <= walkableClimb) |
131 | { |
132 | if (neighborBot < accessibleNeighborMinHeight) accessibleNeighborMinHeight = neighborBot; |
133 | if (neighborBot > accessibleNeighborMaxHeight) accessibleNeighborMaxHeight = neighborBot; |
134 | } |
135 | |
136 | } |
137 | } |
138 | } |
139 | |
140 | // The current span is close to a ledge if the drop to any |
141 | // neighbour span is less than the walkableClimb. |
142 | if (minNeighborHeight < -walkableClimb) |
143 | { |
144 | span->area = RC_NULL_AREA; |
145 | } |
146 | // If the difference between all neighbours is too large, |
147 | // we are at steep slope, mark the span as ledge. |
148 | else if ((accessibleNeighborMaxHeight - accessibleNeighborMinHeight) > walkableClimb) |
149 | { |
150 | span->area = RC_NULL_AREA; |
151 | } |
152 | } |
153 | } |
154 | } |
155 | } |
156 | |
157 | void rcFilterWalkableLowHeightSpans(rcContext* context, const int walkableHeight, rcHeightfield& heightfield) |
158 | { |
159 | rcAssert(context); |
160 | |
161 | rcScopedTimer timer(context, RC_TIMER_FILTER_WALKABLE); |
162 | |
163 | const int xSize = heightfield.width; |
164 | const int zSize = heightfield.height; |
165 | const int MAX_HEIGHT = 0xffff; |
166 | |
167 | // Remove walkable flag from spans which do not have enough |
168 | // space above them for the agent to stand there. |
169 | for (int z = 0; z < zSize; ++z) |
170 | { |
171 | for (int x = 0; x < xSize; ++x) |
172 | { |
173 | for (rcSpan* span = heightfield.spans[x + z*xSize]; span; span = span->next) |
174 | { |
175 | const int bot = (int)(span->smax); |
176 | const int top = span->next ? (int)(span->next->smin) : MAX_HEIGHT; |
177 | if ((top - bot) < walkableHeight) |
178 | { |
179 | span->area = RC_NULL_AREA; |
180 | } |
181 | } |
182 | } |
183 | } |
184 | } |
185 | |