svn merge ^/trunk/blender -r40644:40720
[blender-staging.git] / extern / recastnavigation / Recast / Source / RecastFilter.cpp
index 3421ea1899ee4d4636c9de4de937abc0e543f97f..bf985c362c91ab2ce173fa2fdd6786335fad9fc4 100644 (file)
@@ -1,5 +1,5 @@
 //
-// Copyright (c) 2009 Mikko Mononen memon@inside.org
+// Copyright (c) 2009-2010 Mikko Mononen memon@inside.org
 //
 // This software is provided 'as-is', without any express or implied
 // warranty.  In no event will the authors be held liable for any damages
 #include <math.h>
 #include <stdio.h>
 #include "Recast.h"
-#include "RecastLog.h"
-#include "RecastTimer.h"
+#include "RecastAssert.h"
 
+/// @par
+///
+/// Allows the formation of walkable regions that will flow over low lying 
+/// objects such as curbs, and up structures such as stairways. 
+/// 
+/// Two neighboring spans are walkable if: <tt>rcAbs(currentSpan.smax - neighborSpan.smax) < waklableClimb</tt>
+/// 
+/// @warning Will override the effect of #rcFilterLedgeSpans.  So if both filters are used, call
+/// #rcFilterLedgeSpans after calling this filter. 
+///
+/// @see rcHeightfield, rcConfig
+void rcFilterLowHangingWalkableObstacles(rcContext* ctx, const int walkableClimb, rcHeightfield& solid)
+{
+       rcAssert(ctx);
+
+       ctx->startTimer(RC_TIMER_FILTER_LOW_OBSTACLES);
+       
+       const int w = solid.width;
+       const int h = solid.height;
+       
+       for (int y = 0; y < h; ++y)
+       {
+               for (int x = 0; x < w; ++x)
+               {
+                       rcSpan* ps = 0;
+                       bool previousWalkable = false;
+                       unsigned char previousArea = RC_NULL_AREA;
+                       
+                       for (rcSpan* s = solid.spans[x + y*w]; s; ps = s, s = s->next)
+                       {
+                               const bool walkable = s->area != RC_NULL_AREA;
+                               // If current span is not walkable, but there is walkable
+                               // span just below it, mark the span above it walkable too.
+                               if (!walkable && previousWalkable)
+                               {
+                                       if (rcAbs((int)s->smax - (int)ps->smax) <= walkableClimb)
+                                               s->area = previousArea;
+                               }
+                               // Copy walkable flag so that it cannot propagate
+                               // past multiple non-walkable objects.
+                               previousWalkable = walkable;
+                               previousArea = s->area;
+                       }
+               }
+       }
+
+       ctx->stopTimer(RC_TIMER_FILTER_LOW_OBSTACLES);
+}
 
-void rcFilterLedgeSpans(const int walkableHeight,
-                                               const int walkableClimb,
+/// @par
+///
+/// A ledge is a span with one or more neighbors whose maximum is further away than @p walkableClimb
+/// from the current span's maximum.
+/// This method removes the impact of the overestimation of conservative voxelization 
+/// so the resulting mesh will not have regions hanging in the air over ledges.
+/// 
+/// A span is a ledge if: <tt>rcAbs(currentSpan.smax - neighborSpan.smax) > walkableClimb</tt>
+/// 
+/// @see rcHeightfield, rcConfig
+void rcFilterLedgeSpans(rcContext* ctx, const int walkableHeight, const int walkableClimb,
                                                rcHeightfield& solid)
 {
-       rcTimeVal startTime = rcGetPerformanceTimer();
+       rcAssert(ctx);
+       
+       ctx->startTimer(RC_TIMER_FILTER_BORDER);
 
        const int w = solid.width;
        const int h = solid.height;
@@ -42,15 +100,19 @@ void rcFilterLedgeSpans(const int walkableHeight,
                        for (rcSpan* s = solid.spans[x + y*w]; s; s = s->next)
                        {
                                // Skip non walkable spans.
-                               if ((s->flags & RC_WALKABLE) == 0)
+                               if (s->area == RC_NULL_AREA)
                                        continue;
                                
-                               const int bot = (int)s->smax;
-                               const int top = (int)s->next ? (int)s->next->smin : MAX_HEIGHT;
+                               const int bot = (int)(s->smax);
+                               const int top = s->next ? (int)(s->next->smin) : MAX_HEIGHT;
                                
                                // Find neighbours minimum height.
                                int minh = MAX_HEIGHT;
 
+                               // Min and max height of accessible neighbours.
+                               int asmin = s->smax;
+                               int asmax = s->smax;
+
                                for (int dir = 0; dir < 4; ++dir)
                                {
                                        int dx = x + rcGetDirOffsetX(dir);
@@ -74,33 +136,52 @@ void rcFilterLedgeSpans(const int walkableHeight,
                                        for (ns = solid.spans[dx + dy*w]; ns; ns = ns->next)
                                        {
                                                nbot = (int)ns->smax;
-                                               ntop = (int)ns->next ? (int)ns->next->smin : MAX_HEIGHT;
+                                               ntop = ns->next ? (int)ns->next->smin : MAX_HEIGHT;
                                                // Skip neightbour if the gap between the spans is too small.
                                                if (rcMin(top,ntop) - rcMax(bot,nbot) > walkableHeight)
+                                               {
                                                        minh = rcMin(minh, nbot - bot);
+                                               
+                                                       // Find min/max accessible neighbour height. 
+                                                       if (rcAbs(nbot - bot) <= walkableClimb)
+                                                       {
+                                                               if (nbot < asmin) asmin = nbot;
+                                                               if (nbot > asmax) asmax = nbot;
+                                                       }
+                                                       
+                                               }
                                        }
                                }
                                
                                // The current span is close to a ledge if the drop to any
                                // neighbour span is less than the walkableClimb.
                                if (minh < -walkableClimb)
-                                       s->flags &= ~RC_WALKABLE;
-                               
+                                       s->area = RC_NULL_AREA;
+                                       
+                               // If the difference between all neighbours is too large,
+                               // we are at steep slope, mark the span as ledge.
+                               if ((asmax - asmin) > walkableClimb)
+                               {
+                                       s->area = RC_NULL_AREA;
+                               }
                        }
                }
        }
        
-       rcTimeVal endTime = rcGetPerformanceTimer();
-//     if (rcGetLog())
-//             rcGetLog()->log(RC_LOG_PROGRESS, "Filter border: %.3f ms", rcGetDeltaTimeUsec(startTime, endTime)/1000.0f);
-       if (rcGetBuildTimes())
-               rcGetBuildTimes()->filterBorder += rcGetDeltaTimeUsec(startTime, endTime);
+       ctx->stopTimer(RC_TIMER_FILTER_BORDER);
 }      
 
-void rcFilterWalkableLowHeightSpans(int walkableHeight,
-                                                                       rcHeightfield& solid)
+/// @par
+///
+/// For this filter, the clearance above the span is the distance from the span's 
+/// maximum to the next higher span's minimum. (Same grid column.)
+/// 
+/// @see rcHeightfield, rcConfig
+void rcFilterWalkableLowHeightSpans(rcContext* ctx, int walkableHeight, rcHeightfield& solid)
 {
-       rcTimeVal startTime = rcGetPerformanceTimer();
+       rcAssert(ctx);
+       
+       ctx->startTimer(RC_TIMER_FILTER_WALKABLE);
        
        const int w = solid.width;
        const int h = solid.height;
@@ -114,136 +195,13 @@ void rcFilterWalkableLowHeightSpans(int walkableHeight,
                {
                        for (rcSpan* s = solid.spans[x + y*w]; s; s = s->next)
                        {
-                               const int bot = (int)s->smax;
-                               const int top = (int)s->next ? (int)s->next->smin : MAX_HEIGHT;
+                               const int bot = (int)(s->smax);
+                               const int top = s->next ? (int)(s->next->smin) : MAX_HEIGHT;
                                if ((top - bot) <= walkableHeight)
-                                       s->flags &= ~RC_WALKABLE;
+                                       s->area = RC_NULL_AREA;
                        }
                }
        }
        
-       rcTimeVal endTime = rcGetPerformanceTimer();
-
-//     if (rcGetLog())
-//             rcGetLog()->log(RC_LOG_PROGRESS, "Filter walkable: %.3f ms", rcGetDeltaTimeUsec(startTime, endTime)/1000.0f);
-       if (rcGetBuildTimes())
-               rcGetBuildTimes()->filterWalkable += rcGetDeltaTimeUsec(startTime, endTime);
-}
-
-
-struct rcReachableSeed
-{
-       inline void set(int ix, int iy, rcSpan* is)
-       {
-               x = (unsigned short)ix;
-               y = (unsigned short)iy;
-               s = is;
-       }
-       unsigned short x, y;
-       rcSpan* s;
-};
-
-bool rcMarkReachableSpans(const int walkableHeight,
-                                                 const int walkableClimb,
-                                                 rcHeightfield& solid)
-{
-       const int w = solid.width;
-       const int h = solid.height;
-       const int MAX_HEIGHT = 0xffff;
-       
-       rcTimeVal startTime = rcGetPerformanceTimer();
-       
-       // Build navigable space.
-       const int MAX_SEEDS = w*h;
-       rcReachableSeed* stack = new rcReachableSeed[MAX_SEEDS];
-       if (!stack)
-       {
-               if (rcGetLog())
-                       rcGetLog()->log(RC_LOG_ERROR, "rcMarkReachableSpans: Out of memory 'stack' (%d).", MAX_SEEDS);
-               return false;
-       }
-       int stackSize = 0;
-       
-       for (int y = 0; y < h; ++y)
-       {
-               for (int x = 0; x < w; ++x)
-               {
-                       rcSpan* topSpan = solid.spans[x + y*w];
-                       if (!topSpan)
-                               continue;
-                       while (topSpan->next)
-                               topSpan = topSpan->next;
-                       
-                       // If the span is not walkable, skip it.
-                       if ((topSpan->flags & RC_WALKABLE) == 0)
-                               continue;
-                       // If the span has been visited already, skip it.
-                       if (topSpan->flags & RC_REACHABLE)
-                               continue;
-                       
-                       // Start flood fill.
-                       topSpan->flags |= RC_REACHABLE;
-                       stackSize = 0;
-                       stack[stackSize].set(x, y, topSpan);
-                       stackSize++;
-                       
-                       while (stackSize)
-                       {
-                               // Pop a seed from the stack.
-                               stackSize--;
-                               rcReachableSeed cur = stack[stackSize];
-                               
-                               const int bot = (int)cur.s->smax;
-                               const int top = (int)cur.s->next ? (int)cur.s->next->smin : MAX_HEIGHT;
-                               
-                               // Visit neighbours in all 4 directions.
-                               for (int dir = 0; dir < 4; ++dir)
-                               {
-                                       int dx = (int)cur.x + rcGetDirOffsetX(dir);
-                                       int dy = (int)cur.y + rcGetDirOffsetY(dir);
-                                       // Skip neighbour which are out of bounds.
-                                       if (dx < 0 || dy < 0 || dx >= w || dy >= h)
-                                               continue;
-                                       for (rcSpan* ns = solid.spans[dx + dy*w]; ns; ns = ns->next)
-                                       {
-                                               // Skip neighbour if it is not walkable.
-                                               if ((ns->flags & RC_WALKABLE) == 0)
-                                                       continue;
-                                               // Skip the neighbour if it has been visited already.
-                                               if (ns->flags & RC_REACHABLE)
-                                                       continue;
-                                               
-                                               const int nbot = (int)ns->smax;
-                                               const int ntop = (int)ns->next ? (int)ns->next->smin : MAX_HEIGHT;
-                                               // Skip neightbour if the gap between the spans is too small.
-                                               if (rcMin(top,ntop) - rcMax(bot,nbot) < walkableHeight)
-                                                       continue;
-                                               // Skip neightbour if the climb height to the neighbour is too high.
-                                               if (rcAbs(nbot - bot) >= walkableClimb)
-                                                       continue;
-                                               
-                                               // This neighbour has not been visited yet.
-                                               // Mark it as reachable and add it to the seed stack.
-                                               ns->flags |= RC_REACHABLE;
-                                               if (stackSize < MAX_SEEDS)
-                                               {
-                                                       stack[stackSize].set(dx, dy, ns);
-                                                       stackSize++;
-                                               }
-                                       }
-                               }
-                       }
-               }
-       }
-       
-       delete [] stack;        
-       
-       rcTimeVal endTime = rcGetPerformanceTimer();
-       
-//     if (rcGetLog())
-//             rcGetLog()->log(RC_LOG_PROGRESS, "Mark reachable: %.3f ms", rcGetDeltaTimeUsec(startTime, endTime)/1000.0f);
-       if (rcGetBuildTimes())
-               rcGetBuildTimes()->filterMarkReachable += rcGetDeltaTimeUsec(startTime, endTime);
-       
-       return true;
+       ctx->stopTimer(RC_TIMER_FILTER_WALKABLE);
 }