From cc43c2ea16b3fb2186d255eb2759aefadbfb677e Mon Sep 17 00:00:00 2001 From: PouleyKetchoupp Date: Fri, 7 May 2021 19:16:04 -0700 Subject: Optimize area detection and intersect_shape queries with concave shapes Whenever contact points are not needed, collision checks with concave shapes (triangle mesh and heightmap) stop at the first colliding triangle. --- servers/physics_2d/collision_solver_2d_sw.cpp | 10 +++++----- servers/physics_2d/collision_solver_2d_sw.h | 2 +- servers/physics_2d/shape_2d_sw.cpp | 6 ++++-- servers/physics_2d/shape_2d_sw.h | 8 +++++--- 4 files changed, 15 insertions(+), 11 deletions(-) (limited to 'servers/physics_2d') diff --git a/servers/physics_2d/collision_solver_2d_sw.cpp b/servers/physics_2d/collision_solver_2d_sw.cpp index f7a8593c50..ae50615953 100644 --- a/servers/physics_2d/collision_solver_2d_sw.cpp +++ b/servers/physics_2d/collision_solver_2d_sw.cpp @@ -149,20 +149,20 @@ struct _ConcaveCollisionInfo2D { Vector2 *sep_axis; }; -void CollisionSolver2DSW::concave_callback(void *p_userdata, Shape2DSW *p_convex) { +bool CollisionSolver2DSW::concave_callback(void *p_userdata, Shape2DSW *p_convex) { _ConcaveCollisionInfo2D &cinfo = *(_ConcaveCollisionInfo2D *)(p_userdata); cinfo.aabb_tests++; - if (!cinfo.result_callback && cinfo.collided) { - return; //already collided and no contacts requested, don't test anymore - } bool collided = collision_solver(cinfo.shape_A, *cinfo.transform_A, cinfo.motion_A, p_convex, *cinfo.transform_B, cinfo.motion_B, cinfo.result_callback, cinfo.userdata, cinfo.swap_result, cinfo.sep_axis, cinfo.margin_A, cinfo.margin_B); if (!collided) { - return; + return false; } cinfo.collided = true; cinfo.collisions++; + + // Stop at first collision if contacts are not needed. + return !cinfo.result_callback; } bool CollisionSolver2DSW::solve_concave(const Shape2DSW *p_shape_A, const Transform2D &p_transform_A, const Vector2 &p_motion_A, const Shape2DSW *p_shape_B, const Transform2D &p_transform_B, const Vector2 &p_motion_B, CallbackResult p_result_callback, void *p_userdata, bool p_swap_result, Vector2 *r_sep_axis, real_t p_margin_A, real_t p_margin_B) { diff --git a/servers/physics_2d/collision_solver_2d_sw.h b/servers/physics_2d/collision_solver_2d_sw.h index 0678e3526c..62fccc4ff3 100644 --- a/servers/physics_2d/collision_solver_2d_sw.h +++ b/servers/physics_2d/collision_solver_2d_sw.h @@ -39,7 +39,7 @@ public: private: static bool solve_static_world_margin(const Shape2DSW *p_shape_A, const Transform2D &p_transform_A, const Shape2DSW *p_shape_B, const Transform2D &p_transform_B, CallbackResult p_result_callback, void *p_userdata, bool p_swap_result); - static void concave_callback(void *p_userdata, Shape2DSW *p_convex); + static bool concave_callback(void *p_userdata, Shape2DSW *p_convex); static bool solve_concave(const Shape2DSW *p_shape_A, const Transform2D &p_transform_A, const Vector2 &p_motion_A, const Shape2DSW *p_shape_B, const Transform2D &p_transform_B, const Vector2 &p_motion_B, CallbackResult p_result_callback, void *p_userdata, bool p_swap_result, Vector2 *r_sep_axis = nullptr, real_t p_margin_A = 0, real_t p_margin_B = 0); static bool solve_separation_ray(const Shape2DSW *p_shape_A, const Vector2 &p_motion_A, const Transform2D &p_transform_A, const Shape2DSW *p_shape_B, const Transform2D &p_transform_B, CallbackResult p_result_callback, void *p_userdata, bool p_swap_result, Vector2 *r_sep_axis = nullptr, real_t p_margin = 0); diff --git a/servers/physics_2d/shape_2d_sw.cpp b/servers/physics_2d/shape_2d_sw.cpp index 757b2e0583..064c4afe52 100644 --- a/servers/physics_2d/shape_2d_sw.cpp +++ b/servers/physics_2d/shape_2d_sw.cpp @@ -921,7 +921,7 @@ Variant ConcavePolygonShape2DSW::get_data() const { return rsegments; } -void ConcavePolygonShape2DSW::cull(const Rect2 &p_local_aabb, Callback p_callback, void *p_userdata) const { +void ConcavePolygonShape2DSW::cull(const Rect2 &p_local_aabb, QueryCallback p_callback, void *p_userdata) const { uint32_t *stack = (uint32_t *)alloca(sizeof(int) * bvh_depth); enum { @@ -969,7 +969,9 @@ void ConcavePolygonShape2DSW::cull(const Rect2 &p_local_aabb, Callback p_callbac SegmentShape2DSW ss(a, b, (b - a).orthogonal().normalized()); - p_callback(p_userdata, &ss); + if (p_callback(p_userdata, &ss)) { + return; + } stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node; } else { diff --git a/servers/physics_2d/shape_2d_sw.h b/servers/physics_2d/shape_2d_sw.h index bc321adb42..1185d343ee 100644 --- a/servers/physics_2d/shape_2d_sw.h +++ b/servers/physics_2d/shape_2d_sw.h @@ -465,9 +465,11 @@ public: class ConcaveShape2DSW : public Shape2DSW { public: virtual bool is_concave() const override { return true; } - typedef void (*Callback)(void *p_userdata, Shape2DSW *p_convex); - virtual void cull(const Rect2 &p_local_aabb, Callback p_callback, void *p_userdata) const = 0; + // Returns true to stop the query. + typedef bool (*QueryCallback)(void *p_userdata, Shape2DSW *p_convex); + + virtual void cull(const Rect2 &p_local_aabb, QueryCallback p_callback, void *p_userdata) const = 0; }; class ConcavePolygonShape2DSW : public ConcaveShape2DSW { @@ -525,7 +527,7 @@ public: virtual void set_data(const Variant &p_data) override; virtual Variant get_data() const override; - virtual void cull(const Rect2 &p_local_aabb, Callback p_callback, void *p_userdata) const override; + virtual void cull(const Rect2 &p_local_aabb, QueryCallback p_callback, void *p_userdata) const override; DEFAULT_PROJECT_RANGE_CAST }; -- cgit v1.2.3