Fix build error on Windows 32 bit.
[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         rcScopedTimer timer(ctx, 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
72 /// @par
73 ///
74 /// A ledge is a span with one or more neighbors whose maximum is further away than @p walkableClimb
75 /// from the current span's maximum.
76 /// This method removes the impact of the overestimation of conservative voxelization 
77 /// so the resulting mesh will not have regions hanging in the air over ledges.
78 /// 
79 /// A span is a ledge if: <tt>rcAbs(currentSpan.smax - neighborSpan.smax) > walkableClimb</tt>
80 /// 
81 /// @see rcHeightfield, rcConfig
82 void rcFilterLedgeSpans(rcContext* ctx, const int walkableHeight, const int walkableClimb,
83                                                 rcHeightfield& solid)
84 {
85         rcAssert(ctx);
86         
87         rcScopedTimer timer(ctx, RC_TIMER_FILTER_BORDER);
88
89         const int w = solid.width;
90         const int h = solid.height;
91         const int MAX_HEIGHT = 0xffff;
92         
93         // Mark border spans.
94         for (int y = 0; y < h; ++y)
95         {
96                 for (int x = 0; x < w; ++x)
97                 {
98                         for (rcSpan* s = solid.spans[x + y*w]; s; s = s->next)
99                         {
100                                 // Skip non walkable spans.
101                                 if (s->area == RC_NULL_AREA)
102                                         continue;
103                                 
104                                 const int bot = (int)(s->smax);
105                                 const int top = s->next ? (int)(s->next->smin) : MAX_HEIGHT;
106                                 
107                                 // Find neighbours minimum height.
108                                 int minh = MAX_HEIGHT;
109
110                                 // Min and max height of accessible neighbours.
111                                 int asmin = s->smax;
112                                 int asmax = s->smax;
113
114                                 for (int dir = 0; dir < 4; ++dir)
115                                 {
116                                         int dx = x + rcGetDirOffsetX(dir);
117                                         int dy = y + rcGetDirOffsetY(dir);
118                                         // Skip neighbours which are out of bounds.
119                                         if (dx < 0 || dy < 0 || dx >= w || dy >= h)
120                                         {
121                                                 minh = rcMin(minh, -walkableClimb - bot);
122                                                 continue;
123                                         }
124
125                                         // From minus infinity to the first span.
126                                         rcSpan* ns = solid.spans[dx + dy*w];
127                                         int nbot = -walkableClimb;
128                                         int ntop = ns ? (int)ns->smin : MAX_HEIGHT;
129                                         // Skip neightbour if the gap between the spans is too small.
130                                         if (rcMin(top,ntop) - rcMax(bot,nbot) > walkableHeight)
131                                                 minh = rcMin(minh, nbot - bot);
132                                         
133                                         // Rest of the spans.
134                                         for (ns = solid.spans[dx + dy*w]; ns; ns = ns->next)
135                                         {
136                                                 nbot = (int)ns->smax;
137                                                 ntop = ns->next ? (int)ns->next->smin : MAX_HEIGHT;
138                                                 // Skip neightbour if the gap between the spans is too small.
139                                                 if (rcMin(top,ntop) - rcMax(bot,nbot) > walkableHeight)
140                                                 {
141                                                         minh = rcMin(minh, nbot - bot);
142                                                 
143                                                         // Find min/max accessible neighbour height. 
144                                                         if (rcAbs(nbot - bot) <= walkableClimb)
145                                                         {
146                                                                 if (nbot < asmin) asmin = nbot;
147                                                                 if (nbot > asmax) asmax = nbot;
148                                                         }
149                                                         
150                                                 }
151                                         }
152                                 }
153                                 
154                                 // The current span is close to a ledge if the drop to any
155                                 // neighbour span is less than the walkableClimb.
156                                 if (minh < -walkableClimb)
157                                 {
158                                         s->area = RC_NULL_AREA;
159                                 }
160                                 // If the difference between all neighbours is too large,
161                                 // we are at steep slope, mark the span as ledge.
162                                 else if ((asmax - asmin) > walkableClimb)
163                                 {
164                                         s->area = RC_NULL_AREA;
165                                 }
166                         }
167                 }
168         }
169 }
170
171 /// @par
172 ///
173 /// For this filter, the clearance above the span is the distance from the span's 
174 /// maximum to the next higher span's minimum. (Same grid column.)
175 /// 
176 /// @see rcHeightfield, rcConfig
177 void rcFilterWalkableLowHeightSpans(rcContext* ctx, int walkableHeight, rcHeightfield& solid)
178 {
179         rcAssert(ctx);
180         
181         rcScopedTimer timer(ctx, RC_TIMER_FILTER_WALKABLE);
182         
183         const int w = solid.width;
184         const int h = solid.height;
185         const int MAX_HEIGHT = 0xffff;
186         
187         // Remove walkable flag from spans which do not have enough
188         // space above them for the agent to stand there.
189         for (int y = 0; y < h; ++y)
190         {
191                 for (int x = 0; x < w; ++x)
192                 {
193                         for (rcSpan* s = solid.spans[x + y*w]; s; s = s->next)
194                         {
195                                 const int bot = (int)(s->smax);
196                                 const int top = s->next ? (int)(s->next->smin) : MAX_HEIGHT;
197                                 if ((top - bot) <= walkableHeight)
198                                         s->area = RC_NULL_AREA;
199                         }
200                 }
201         }
202 }