diff options
Diffstat (limited to 'extern/recastnavigation/Recast/Source/RecastFilter.cpp')
-rw-r--r-- | extern/recastnavigation/Recast/Source/RecastFilter.cpp | 249 |
1 files changed, 249 insertions, 0 deletions
diff --git a/extern/recastnavigation/Recast/Source/RecastFilter.cpp b/extern/recastnavigation/Recast/Source/RecastFilter.cpp new file mode 100644 index 00000000000..ebe60714a18 --- /dev/null +++ b/extern/recastnavigation/Recast/Source/RecastFilter.cpp @@ -0,0 +1,249 @@ +// +// Copyright (c) 2009 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 +// arising from the use of this software. +// Permission is granted to anyone to use this software for any purpose, +// including commercial applications, and to alter it and redistribute it +// freely, subject to the following restrictions: +// 1. The origin of this software must not be misrepresented; you must not +// claim that you wrote the original software. If you use this software +// in a product, an acknowledgment in the product documentation would be +// appreciated but is not required. +// 2. Altered source versions must be plainly marked as such, and must not be +// misrepresented as being the original software. +// 3. This notice may not be removed or altered from any source distribution. +// + +#define _USE_MATH_DEFINES +#include <math.h> +#include <stdio.h> +#include "Recast.h" +#include "RecastLog.h" +#include "RecastTimer.h" + + +void rcFilterLedgeSpans(const int walkableHeight, + const int walkableClimb, + rcHeightfield& solid) +{ + rcTimeVal startTime = rcGetPerformanceTimer(); + + const int w = solid.width; + const int h = solid.height; + const int MAX_HEIGHT = 0xffff; + + // Mark border spans. + for (int y = 0; y < h; ++y) + { + for (int x = 0; x < w; ++x) + { + for (rcSpan* s = solid.spans[x + y*w]; s; s = s->next) + { + // Skip non walkable spans. + if ((s->flags & RC_WALKABLE) == 0) + continue; + + 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; + + for (int dir = 0; dir < 4; ++dir) + { + int dx = x + rcGetDirOffsetX(dir); + int dy = y + rcGetDirOffsetY(dir); + // Skip neighbours which are out of bounds. + if (dx < 0 || dy < 0 || dx >= w || dy >= h) + { + minh = rcMin(minh, -walkableClimb - bot); + continue; + } + + // From minus infinity to the first span. + rcSpan* ns = solid.spans[dx + dy*w]; + int nbot = -walkableClimb; + int ntop = ns ? (int)ns->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); + + // Rest of the spans. + for (ns = solid.spans[dx + dy*w]; ns; ns = ns->next) + { + nbot = (int)ns->smax; + 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); + } + } + + // 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; + + } + } + } + + 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); +} + +void rcFilterWalkableLowHeightSpans(int walkableHeight, + rcHeightfield& solid) +{ + rcTimeVal startTime = rcGetPerformanceTimer(); + + const int w = solid.width; + const int h = solid.height; + const int MAX_HEIGHT = 0xffff; + + // Remove walkable flag from spans which do not have enough + // space above them for the agent to stand there. + for (int y = 0; y < h; ++y) + { + for (int x = 0; x < w; ++x) + { + 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; + if ((top - bot) <= walkableHeight) + s->flags &= ~RC_WALKABLE; + } + } + } + + 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; +} |