svn merge ^/trunk/blender -r40644:40720
[blender-staging.git] / extern / recastnavigation / Recast / Source / RecastFilter.cpp
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 #define _USE_MATH_DEFINES
20 #include <math.h>
21 #include <stdio.h>
22 #include "Recast.h"
23 #include "RecastAssert.h"
24
25 /// @par
26 ///
27 /// Allows the formation of walkable regions that will flow over low lying 
28 /// objects such as curbs, and up structures such as stairways. 
29 /// 
30 /// Two neighboring spans are walkable if: <tt>rcAbs(currentSpan.smax - neighborSpan.smax) < waklableClimb</tt>
31 /// 
32 /// @warning Will override the effect of #rcFilterLedgeSpans.  So if both filters are used, call
33 /// #rcFilterLedgeSpans after calling this filter. 
34 ///
35 /// @see rcHeightfield, rcConfig
36 void rcFilterLowHangingWalkableObstacles(rcContext* ctx, const int walkableClimb, rcHeightfield& solid)
37 {
38         rcAssert(ctx);
39
40         ctx->startTimer(RC_TIMER_FILTER_LOW_OBSTACLES);
41         
42         const int w = solid.width;
43         const int h = solid.height;
44         
45         for (int y = 0; y < h; ++y)
46         {
47                 for (int x = 0; x < w; ++x)
48                 {
49                         rcSpan* ps = 0;
50                         bool previousWalkable = false;
51                         unsigned char previousArea = RC_NULL_AREA;
52                         
53                         for (rcSpan* s = solid.spans[x + y*w]; s; ps = s, s = s->next)
54                         {
55                                 const bool walkable = s->area != RC_NULL_AREA;
56                                 // If current span is not walkable, but there is walkable
57                                 // span just below it, mark the span above it walkable too.
58                                 if (!walkable && previousWalkable)
59                                 {
60                                         if (rcAbs((int)s->smax - (int)ps->smax) <= walkableClimb)
61                                                 s->area = previousArea;
62                                 }
63                                 // Copy walkable flag so that it cannot propagate
64                                 // past multiple non-walkable objects.
65                                 previousWalkable = walkable;
66                                 previousArea = s->area;
67                         }
68                 }
69         }
70
71         ctx->stopTimer(RC_TIMER_FILTER_LOW_OBSTACLES);
72 }
73
74 /// @par
75 ///
76 /// A ledge is a span with one or more neighbors whose maximum is further away than @p walkableClimb
77 /// from the current span's maximum.
78 /// This method removes the impact of the overestimation of conservative voxelization 
79 /// so the resulting mesh will not have regions hanging in the air over ledges.
80 /// 
81 /// A span is a ledge if: <tt>rcAbs(currentSpan.smax - neighborSpan.smax) > walkableClimb</tt>
82 /// 
83 /// @see rcHeightfield, rcConfig
84 void rcFilterLedgeSpans(rcContext* ctx, const int walkableHeight, const int walkableClimb,
85                                                 rcHeightfield& solid)
86 {
87         rcAssert(ctx);
88         
89         ctx->startTimer(RC_TIMER_FILTER_BORDER);
90
91         const int w = solid.width;
92         const int h = solid.height;
93         const int MAX_HEIGHT = 0xffff;
94         
95         // Mark border spans.
96         for (int y = 0; y < h; ++y)
97         {
98                 for (int x = 0; x < w; ++x)
99                 {
100                         for (rcSpan* s = solid.spans[x + y*w]; s; s = s->next)
101                         {
102                                 // Skip non walkable spans.
103                                 if (s->area == RC_NULL_AREA)
104                                         continue;
105                                 
106                                 const int bot = (int)(s->smax);
107                                 const int top = s->next ? (int)(s->next->smin) : MAX_HEIGHT;
108                                 
109                                 // Find neighbours minimum height.
110                                 int minh = MAX_HEIGHT;
111
112                                 // Min and max height of accessible neighbours.
113                                 int asmin = s->smax;
114                                 int asmax = s->smax;
115
116                                 for (int dir = 0; dir < 4; ++dir)
117                                 {
118                                         int dx = x + rcGetDirOffsetX(dir);
119                                         int dy = y + rcGetDirOffsetY(dir);
120                                         // Skip neighbours which are out of bounds.
121                                         if (dx < 0 || dy < 0 || dx >= w || dy >= h)
122                                         {
123                                                 minh = rcMin(minh, -walkableClimb - bot);
124                                                 continue;
125                                         }
126
127                                         // From minus infinity to the first span.
128                                         rcSpan* ns = solid.spans[dx + dy*w];
129                                         int nbot = -walkableClimb;
130                                         int ntop = ns ? (int)ns->smin : MAX_HEIGHT;
131                                         // Skip neightbour if the gap between the spans is too small.
132                                         if (rcMin(top,ntop) - rcMax(bot,nbot) > walkableHeight)
133                                                 minh = rcMin(minh, nbot - bot);
134                                         
135                                         // Rest of the spans.
136                                         for (ns = solid.spans[dx + dy*w]; ns; ns = ns->next)
137                                         {
138                                                 nbot = (int)ns->smax;
139                                                 ntop = ns->next ? (int)ns->next->smin : MAX_HEIGHT;
140                                                 // Skip neightbour if the gap between the spans is too small.
141                                                 if (rcMin(top,ntop) - rcMax(bot,nbot) > walkableHeight)
142                                                 {
143                                                         minh = rcMin(minh, nbot - bot);
144                                                 
145                                                         // Find min/max accessible neighbour height. 
146                                                         if (rcAbs(nbot - bot) <= walkableClimb)
147                                                         {
148                                                                 if (nbot < asmin) asmin = nbot;
149                                                                 if (nbot > asmax) asmax = nbot;
150                                                         }
151                                                         
152                                                 }
153                                         }
154                                 }
155                                 
156                                 // The current span is close to a ledge if the drop to any
157                                 // neighbour span is less than the walkableClimb.
158                                 if (minh < -walkableClimb)
159                                         s->area = RC_NULL_AREA;
160                                         
161                                 // If the difference between all neighbours is too large,
162                                 // we are at steep slope, mark the span as ledge.
163                                 if ((asmax - asmin) > walkableClimb)
164                                 {
165                                         s->area = RC_NULL_AREA;
166                                 }
167                         }
168                 }
169         }
170         
171         ctx->stopTimer(RC_TIMER_FILTER_BORDER);
172 }       
173
174 /// @par
175 ///
176 /// For this filter, the clearance above the span is the distance from the span's 
177 /// maximum to the next higher span's minimum. (Same grid column.)
178 /// 
179 /// @see rcHeightfield, rcConfig
180 void rcFilterWalkableLowHeightSpans(rcContext* ctx, int walkableHeight, rcHeightfield& solid)
181 {
182         rcAssert(ctx);
183         
184         ctx->startTimer(RC_TIMER_FILTER_WALKABLE);
185         
186         const int w = solid.width;
187         const int h = solid.height;
188         const int MAX_HEIGHT = 0xffff;
189         
190         // Remove walkable flag from spans which do not have enough
191         // space above them for the agent to stand there.
192         for (int y = 0; y < h; ++y)
193         {
194                 for (int x = 0; x < w; ++x)
195                 {
196                         for (rcSpan* s = solid.spans[x + y*w]; s; s = s->next)
197                         {
198                                 const int bot = (int)(s->smax);
199                                 const int top = s->next ? (int)(s->next->smin) : MAX_HEIGHT;
200                                 if ((top - bot) <= walkableHeight)
201                                         s->area = RC_NULL_AREA;
202                         }
203                 }
204         }
205         
206         ctx->stopTimer(RC_TIMER_FILTER_WALKABLE);
207 }