Entered unreachable code

[hakolao]

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]

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

[Jondolf]

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()):

parry/src/query/nonlinear_time_of_impact/nonlinear_time_of_impact_support_map_support_map.rs

Lines 128 to 130 in 8823198

	match dispatcher
	.closest_points(&pos12, g1, g2, Bounded::max_value())
	.ok()?

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.

parry/src/query/nonlinear_time_of_impact/nonlinear_time_of_impact_support_map_support_map.rs

Line 201 in 8823198

ClosestPoints::Disjoint => unreachable!(),

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:

parry/src/query/closest_points/closest_points_support_map_support_map.rs

Line 30 in 8823198

GJKResult::NoIntersection(_) => ClosestPoints::Disjoint,

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.