search

dimforge / parry

2D and 3D collision-detection library for Rust.
https://parry.rs
Apache License 2.0
591 stars 104 forks source link

Entered unreachable code #176

Open hakolao opened 10 months ago

hakolao commented 10 months ago

I get 

src\query\nonlinear_time_of_impact\nonlinear_time_of_impact_support_map_support_map.rs:201:40:
internal error: entered unreachable code

This should not happen. it's rather hard to provide a repro

  0: std::panicking::begin_panic_handler
             at /rustc/a2d9d73e608f1b24eba840c4fd2d68dbe3b65e01/library\std\src\panicking.rs:647
   1: core::panicking::panic_fmt
             at /rustc/a2d9d73e608f1b24eba840c4fd2d68dbe3b65e01/library\core\src\panicking.rs:72
   2: core::panicking::panic
             at /rustc/a2d9d73e608f1b24eba840c4fd2d68dbe3b65e01/library\core\src\panicking.rs:144
   3: parry2d::query::nonlinear_time_of_impact::nonlinear_time_of_impact_support_map_support_map::compute_toi<parry2d::query::default_query_dispatcher::DefaultQueryDispatcher,parry2d::shape::ball::Ball,parry2d::shape::ball::Ball>
             src\query\nonlinear_time_of_impact\nonlinear_time_of_impact_support_map_support_map.rs:201
   4: parry2d::query::nonlinear_time_of_impact::nonlinear_time_of_impact_composite_shape_shape::impl$1::visit
             src\query\nonlinear_time_of_impact\nonlinear_time_of_impact_composite_shape_shape.rs:143
   5: parry2d::partitioning::qbvh::qbvh::GenericQbvh<u32,parry2d::utils::array::DefaultStorage>::traverse_best_first_node<u32,parry2d::utils::array::DefaultStorage,parry2d::query::nonlinear_time_of_impact::nonlinear_time_of_impact_composite_shape_shape::Nonline
             src\partitioning\qbvh\traversal.rs:163
   6: parry2d::partitioning::qbvh::qbvh::GenericQbvh<u32,parry2d::utils::array::DefaultStorage>::traverse_best_first
             src\partitioning\qbvh\traversal.rs:121
   7: parry2d::query::nonlinear_time_of_impact::nonlinear_time_of_impact_composite_shape_shape::nonlinear_time_of_impact_composite_shape_shape
             src\query\nonlinear_time_of_impact\nonlinear_time_of_impact_composite_shape_shape.rs:36
   8: parry2d::query::nonlinear_time_of_impact::nonlinear_time_of_impact_composite_shape_shape::nonlinear_time_of_impact_shape_composite_shape
             src\query\nonlinear_time_of_impact\nonlinear_time_of_impact_composite_shape_shape.rs:55
   9: parry2d::query::default_query_dispatcher::impl$0::nonlinear_time_of_impact
             src\query\default_query_dispatcher.rs:406
  10: parry2d::query::nonlinear_time_of_impact::nonlinear_time_of_impact_composite_shape_shape::impl$1::visit::closure$0<parry2d::query::default_query_dispatcher::DefaultQueryDispatcher,dyn$<parry2d::shape::composite_shape::SimdCompositeShape> >
             src\query\nonlinear_time_of_impact\nonlinear_time_of_impact_composite_shape_shape.rs:160
  11: parry2d::query::nonlinear_time_of_impact::nonlinear_time_of_impact_composite_shape_shape::impl$1::visit
             src\query\nonlinear_time_of_impact\nonlinear_time_of_impact_composite_shape_shape.rs:158
  12: parry2d::partitioning::qbvh::qbvh::GenericQbvh<u32,parry2d::utils::array::DefaultStorage>::traverse_best_first_node<u32,parry2d::utils::array::DefaultStorage,parry2d::query::nonlinear_time_of_impact::nonlinear_time_of_impact_composite_shape_shape::Nonline
             src\partitioning\qbvh\traversal.rs:163
  13: parry2d::partitioning::qbvh::qbvh::GenericQbvh<u32,parry2d::utils::array::DefaultStorage>::traverse_best_first
             src\partitioning\qbvh\traversal.rs:121
  14: parry2d::query::nonlinear_time_of_impact::nonlinear_time_of_impact_composite_shape_shape::nonlinear_time_of_impact_composite_shape_shape
             src\query\nonlinear_time_of_impact\nonlinear_time_of_impact_composite_shape_shape.rs:36
  15: parry2d::query::default_query_dispatcher::impl$0::nonlinear_time_of_impact
             src\query\default_query_dispatcher.rs:393
  16: rapier2d::dynamics::ccd::toi_entry::TOIEntry::try_from_colliders<dyn$<parry2d::query::query_dispatcher::QueryDispatcher> >
             \rapier2d-0.17.2\src\dynamics\ccd\toi_entry.rs:131
  17: rapier2d::dynamics::ccd::ccd_solver::impl$1::predict_impacts_at_next_positions::closure$0
             \rapier2d-0.17.2\src\dynamics\ccd\ccd_solver.rs:317
  18: core::ops::function::impls::impl$3::call_mut<tuple$<ref$<rapier2d::geometry::collider_components::ColliderHandle> >,rapier2d::dynamics::ccd::ccd_solver::impl$1::predict_impacts_at_next_positions::closure_env$0>
             at /rustc/a2d9d73e608f1b24eba840c4fd2d68dbe3b65e01\library\core\src\ops\function.rs:294
  19: parry2d::query::visitors::bounding_volume_intersections_visitor::impl$1::visit
             src\query\visitors\bounding_volume_intersections_visitor.rs:42
  20: parry2d::partitioning::qbvh::qbvh::GenericQbvh<rapier2d::geometry::collider_components::ColliderHandle,parry2d::utils::array::DefaultStorage>::traverse_depth_first_node_with_stack
             src\partitioning\qbvh\traversal.rs:86
  21: parry2d::partitioning::qbvh::qbvh::GenericQbvh<rapier2d::geometry::collider_components::ColliderHandle,parry2d::utils::array::DefaultStorage>::traverse_depth_first_node<rapier2d::geometry::collider_components::ColliderHandle,parry2d::utils::array::Default
             src\partitioning\qbvh\traversal.rs:44
  22: rapier2d::dynamics::ccd::ccd_solver::CCDSolver::predict_impacts_at_next_positions
             \rapier2d-0.17.2\src\dynamics\ccd\ccd_solver.rs:281
  23: rapier2d::pipeline::physics_pipeline::PhysicsPipeline::run_ccd_motion_clamping
             \rapier2d-0.17.2\src\pipeline\physics_pipeline.rs:341
  24: rapier2d::pipeline::physics_pipeline::PhysicsPipeline::step
             \rapier2d-0.17.2\src\pipeline\physics_pipeline.rs:593
  25: PhysicsWorld::step_physics
HyperCodec commented 8 months ago

I got this too (in rapier3d after despawning a bunch of things)

Jondolf commented 8 months ago

In Rapier, this is typically caused by CCD, because that uses nonlinear_time_of_impact, which in turn uses nonlinear_time_of_impact_support_map_support_map for most shapes.

I don't have time to look into this too deeply right now, but for others wanting to debug this, here are some of my findings just based on looking at the codebase.

The problem

The actual issue here is interesting. The non-linear time of impact query calls closest_points with a max distance using the maximal real value, i.e. Real::MAX (or Bounded::max_value()):

https://github.com/dimforge/parry/blob/8823198d704a85b748b8c45ee2f54e35f24a080e/src/query/nonlinear_time_of_impact/nonlinear_time_of_impact_support_map_support_map.rs#L128-L130

Because the max distance is essentially the largest it can be, the result is expected to never be ClosestPoints::Disjoint (i.e. non-intersecting and above the max distance). This is why the Disjoint variant is specified as unreachable, but somehow it is reached regardless, which causes the panic.

https://github.com/dimforge/parry/blob/8823198d704a85b748b8c45ee2f54e35f24a080e/src/query/nonlinear_time_of_impact/nonlinear_time_of_impact_support_map_support_map.rs#L201

This indicates that the closest_points query seems to be the actual culprit for the crash, as it returns Disjoint in a case where it should never happen.

Potential reasons for returning Disjoint

One option is that the distance between two objects is somehow Real::INFINITY for whatever reason. I think this would qualify as larger than Real::MAX, which could make closest_points return Disjoint.

If the closest_points method uses GJK for the given shape pair (it depends on the shapes), a very likely reason it can return Disjoint could be that GJK returns NoIntersection, because closest_points_support_map_support_map returns Disjoint in that case:

https://github.com/dimforge/parry/blob/8823198d704a85b748b8c45ee2f54e35f24a080e/src/query/closest_points/closest_points_support_map_support_map.rs#L30

This either happens if (1) at any moment the minimum bound computed by GJK is larger than the maximum distance (it'd have to be Real::INFINITY in this case), or if (2) GJK runs out of iterations before converging on a solution.

Finally, if the specific shape pair doesn't use GJK for closest_points, it could be that its special implementation happens to have a bug that causes it to incorrectly return Disjoint.

Debugging

If someone wants to debug this, I would recommend finding what exactly returns Disjoint by adding logs in the appropriate places, like the "unreachable" match branch and the closest_points implementations. If it's caused by GJK returning NoIntersection, adding logs there to see what the shapes and isometries are could be useful.

paul-hansen commented 6 months ago

Note that for me while I previously got the same panic, after updating to parry3d 0.15.1 it is now a logged error instead of a panic:

ERROR log: Closest points not found despite setting the max distance to infinity.

See this comment for my reproduction using bevy_rapier

Jondolf commented 6 months ago

Yep, it was changed temporarily to log an error instead of panicking in #192 until a proper fix is found