Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/extern/recastnavigation/Recast/Source/RecastFilter.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'extern/recastnavigation/Recast/Source/RecastFilter.cpp')
-rw-r--r--extern/recastnavigation/Recast/Source/RecastFilter.cpp250
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);
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-27 20:01:18 +0300