Fix selection when adding a primitive while already in edge/face-select mode
[blender-staging.git] / extern / recastnavigation / Recast / Source / RecastFilter.cpp
1 //
2 // Copyright (c) 2009 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 "RecastLog.h"
24 #include "RecastTimer.h"
25
26
27 void rcFilterLedgeSpans(const int walkableHeight,
28                                                 const int walkableClimb,
29                                                 rcHeightfield& solid)
30 {
31         rcTimeVal startTime = rcGetPerformanceTimer();
32
33         const int w = solid.width;
34         const int h = solid.height;
35         const int MAX_HEIGHT = 0xffff;
36         
37         // Mark border spans.
38         for (int y = 0; y < h; ++y)
39         {
40                 for (int x = 0; x < w; ++x)
41                 {
42                         for (rcSpan* s = solid.spans[x + y*w]; s; s = s->next)
43                         {
44                                 // Skip non walkable spans.
45                                 if ((s->flags & RC_WALKABLE) == 0)
46                                         continue;
47                                 
48                                 const int bot = (int)s->smax;
49                                 const int top = s->next ? (int)s->next->smin : MAX_HEIGHT;
50                                 
51                                 // Find neighbours minimum height.
52                                 int minh = MAX_HEIGHT;
53
54                                 for (int dir = 0; dir < 4; ++dir)
55                                 {
56                                         int dx = x + rcGetDirOffsetX(dir);
57                                         int dy = y + rcGetDirOffsetY(dir);
58                                         // Skip neighbours which are out of bounds.
59                                         if (dx < 0 || dy < 0 || dx >= w || dy >= h)
60                                         {
61                                                 minh = rcMin(minh, -walkableClimb - bot);
62                                                 continue;
63                                         }
64
65                                         // From minus infinity to the first span.
66                                         rcSpan* ns = solid.spans[dx + dy*w];
67                                         int nbot = -walkableClimb;
68                                         int ntop = ns ? (int)ns->smin : MAX_HEIGHT;
69                                         // Skip neightbour if the gap between the spans is too small.
70                                         if (rcMin(top,ntop) - rcMax(bot,nbot) > walkableHeight)
71                                                 minh = rcMin(minh, nbot - bot);
72                                         
73                                         // Rest of the spans.
74                                         for (ns = solid.spans[dx + dy*w]; ns; ns = ns->next)
75                                         {
76                                                 nbot = (int)ns->smax;
77                                                 ntop = ns->next ? (int)ns->next->smin : MAX_HEIGHT;
78                                                 // Skip neightbour if the gap between the spans is too small.
79                                                 if (rcMin(top,ntop) - rcMax(bot,nbot) > walkableHeight)
80                                                         minh = rcMin(minh, nbot - bot);
81                                         }
82                                 }
83                                 
84                                 // The current span is close to a ledge if the drop to any
85                                 // neighbour span is less than the walkableClimb.
86                                 if (minh < -walkableClimb)
87                                         s->flags &= ~RC_WALKABLE;
88                                 
89                         }
90                 }
91         }
92         
93         rcTimeVal endTime = rcGetPerformanceTimer();
94 //      if (rcGetLog())
95 //              rcGetLog()->log(RC_LOG_PROGRESS, "Filter border: %.3f ms", rcGetDeltaTimeUsec(startTime, endTime)/1000.0f);
96         if (rcGetBuildTimes())
97                 rcGetBuildTimes()->filterBorder += rcGetDeltaTimeUsec(startTime, endTime);
98 }       
99
100 void rcFilterWalkableLowHeightSpans(int walkableHeight,
101                                                                         rcHeightfield& solid)
102 {
103         rcTimeVal startTime = rcGetPerformanceTimer();
104         
105         const int w = solid.width;
106         const int h = solid.height;
107         const int MAX_HEIGHT = 0xffff;
108         
109         // Remove walkable flag from spans which do not have enough
110         // space above them for the agent to stand there.
111         for (int y = 0; y < h; ++y)
112         {
113                 for (int x = 0; x < w; ++x)
114                 {
115                         for (rcSpan* s = solid.spans[x + y*w]; s; s = s->next)
116                         {
117                                 const int bot = (int)s->smax;
118                                 const int top = s->next ? (int)s->next->smin : MAX_HEIGHT;
119                                 if ((top - bot) <= walkableHeight)
120                                         s->flags &= ~RC_WALKABLE;
121                         }
122                 }
123         }
124         
125         rcTimeVal endTime = rcGetPerformanceTimer();
126
127 //      if (rcGetLog())
128 //              rcGetLog()->log(RC_LOG_PROGRESS, "Filter walkable: %.3f ms", rcGetDeltaTimeUsec(startTime, endTime)/1000.0f);
129         if (rcGetBuildTimes())
130                 rcGetBuildTimes()->filterWalkable += rcGetDeltaTimeUsec(startTime, endTime);
131 }
132
133
134 struct rcReachableSeed
135 {
136         inline void set(int ix, int iy, rcSpan* is)
137         {
138                 x = (unsigned short)ix;
139                 y = (unsigned short)iy;
140                 s = is;
141         }
142         unsigned short x, y;
143         rcSpan* s;
144 };
145
146 bool rcMarkReachableSpans(const int walkableHeight,
147                                                   const int walkableClimb,
148                                                   rcHeightfield& solid)
149 {
150         const int w = solid.width;
151         const int h = solid.height;
152         const int MAX_HEIGHT = 0xffff;
153         
154         rcTimeVal startTime = rcGetPerformanceTimer();
155         
156         // Build navigable space.
157         const int MAX_SEEDS = w*h;
158         rcReachableSeed* stack = new rcReachableSeed[MAX_SEEDS];
159         if (!stack)
160         {
161                 if (rcGetLog())
162                         rcGetLog()->log(RC_LOG_ERROR, "rcMarkReachableSpans: Out of memory 'stack' (%d).", MAX_SEEDS);
163                 return false;
164         }
165         int stackSize = 0;
166         
167         for (int y = 0; y < h; ++y)
168         {
169                 for (int x = 0; x < w; ++x)
170                 {
171                         rcSpan* topSpan = solid.spans[x + y*w];
172                         if (!topSpan)
173                                 continue;
174                         while (topSpan->next)
175                                 topSpan = topSpan->next;
176                         
177                         // If the span is not walkable, skip it.
178                         if ((topSpan->flags & RC_WALKABLE) == 0)
179                                 continue;
180                         // If the span has been visited already, skip it.
181                         if (topSpan->flags & RC_REACHABLE)
182                                 continue;
183                         
184                         // Start flood fill.
185                         topSpan->flags |= RC_REACHABLE;
186                         stackSize = 0;
187                         stack[stackSize].set(x, y, topSpan);
188                         stackSize++;
189                         
190                         while (stackSize)
191                         {
192                                 // Pop a seed from the stack.
193                                 stackSize--;
194                                 rcReachableSeed cur = stack[stackSize];
195                                 
196                                 const int bot = (int)cur.s->smax;
197                                 const int top = cur.s->next ? (int)cur.s->next->smin : MAX_HEIGHT;
198                                 
199                                 // Visit neighbours in all 4 directions.
200                                 for (int dir = 0; dir < 4; ++dir)
201                                 {
202                                         int dx = (int)cur.x + rcGetDirOffsetX(dir);
203                                         int dy = (int)cur.y + rcGetDirOffsetY(dir);
204                                         // Skip neighbour which are out of bounds.
205                                         if (dx < 0 || dy < 0 || dx >= w || dy >= h)
206                                                 continue;
207                                         for (rcSpan* ns = solid.spans[dx + dy*w]; ns; ns = ns->next)
208                                         {
209                                                 // Skip neighbour if it is not walkable.
210                                                 if ((ns->flags & RC_WALKABLE) == 0)
211                                                         continue;
212                                                 // Skip the neighbour if it has been visited already.
213                                                 if (ns->flags & RC_REACHABLE)
214                                                         continue;
215                                                 
216                                                 const int nbot = (int)ns->smax;
217                                                 const int ntop = ns->next ? (int)ns->next->smin : MAX_HEIGHT;
218                                                 // Skip neightbour if the gap between the spans is too small.
219                                                 if (rcMin(top,ntop) - rcMax(bot,nbot) < walkableHeight)
220                                                         continue;
221                                                 // Skip neightbour if the climb height to the neighbour is too high.
222                                                 if (rcAbs(nbot - bot) >= walkableClimb)
223                                                         continue;
224                                                 
225                                                 // This neighbour has not been visited yet.
226                                                 // Mark it as reachable and add it to the seed stack.
227                                                 ns->flags |= RC_REACHABLE;
228                                                 if (stackSize < MAX_SEEDS)
229                                                 {
230                                                         stack[stackSize].set(dx, dy, ns);
231                                                         stackSize++;
232                                                 }
233                                         }
234                                 }
235                         }
236                 }
237         }
238         
239         delete [] stack;        
240         
241         rcTimeVal endTime = rcGetPerformanceTimer();
242         
243 //      if (rcGetLog())
244 //              rcGetLog()->log(RC_LOG_PROGRESS, "Mark reachable: %.3f ms", rcGetDeltaTimeUsec(startTime, endTime)/1000.0f);
245         if (rcGetBuildTimes())
246                 rcGetBuildTimes()->filterMarkReachable += rcGetDeltaTimeUsec(startTime, endTime);
247         
248         return true;
249 }