diff options
Diffstat (limited to 'extern/recastnavigation/Recast/Source/RecastFilter.cpp')
-rw-r--r-- | extern/recastnavigation/Recast/Source/RecastFilter.cpp | 250 |
1 files changed, 104 insertions, 146 deletions
diff --git a/extern/recastnavigation/Recast/Source/RecastFilter.cpp b/extern/recastnavigation/Recast/Source/RecastFilter.cpp index ebe60714a18..bf985c362c9 100644 --- a/extern/recastnavigation/Recast/Source/RecastFilter.cpp +++ b/extern/recastnavigation/Recast/Source/RecastFilter.cpp @@ -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 @@ -20,15 +20,73 @@ #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 = 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); @@ -77,30 +139,49 @@ void rcFilterLedgeSpans(const int walkableHeight, 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 = 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 = 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 = 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); } |