search

dimforge / parry

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

QBVH `rebalance` still panics at 'attempt to add with overflow' #146

Closed Jondolf closed 3 months ago

Jondolf commented 12 months ago

Bevy XPBD is using Parry internally for spatial queries, and the rebalance method of Qbvh is causing panics with the error 'attempt to add with overflow'. #139 claims to fix this, but it doesn't seem like it, although the error is on a slightly different line.

thread 'TaskPool (6)' panicked at 'attempt to add with overflow', /home/nisevoid/.cargo/registry/src/index.crates.io-6f17d22bba15001f/parry3d-0.13.5/src/partitioning/qbvh/update.rs:367:54
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
Encountered a panic in system `bevy_xpbd_3d::plugins::spatial_query::update_query_pipeline`!
Encountered a panic in exclusive system `bevy_xpbd_3d::plugins::setup::run_physics_schedule`!
Encountered a panic in system `bevy_app::main_schedule::Main::run_main`!

This is the code that calls rebalance, in the update_incremental method, similar to Rapier's query pipeline:

if refit_and_balance {
    let _ = self.qbvh.refit(0.0, &mut self.workspace, |entity_index| {
        // Construct entity ID (used as key in a hash map)
        let generation = self.entity_generations.get(entity_index).map_or(0, |i| *i);
        let entity = Entity::from_bits((generation as u64) << 32 | *entity_index as u64);
        // Compute and return AABB
        let (iso, shape) = colliders.get(&entity).unwrap();
        shape.compute_aabb(iso)
    });
    self.qbvh.rebalance(0.0, &mut self.workspace);
}
tesselode commented 10 months ago

I am also having this issue.

hakolao commented 7 months ago

Still getting this (just using rapier & passing query pipeline in step).

LachlanHogan commented 6 months ago

Currently hitting the same issue intermittently (will come back to it in the future to fix for what I'm working on now if nobody else picks it up). Here is a stack trace:

thread 'main' panicked at ...\.cargo\registry\src\index.crates.io-6f17d22bba15001f\parry3d-0.13.5\src\partitioning\qbvh\update.rs:367:54:
attempt to add with overflow
stack backtrace:
   0: std::panicking::begin_panic_handler
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33/library\std\src\panicking.rs:595
   1: core::panicking::panic_fmt
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33/library\core\src\panicking.rs:67
   2: core::panicking::panic
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33/library\core\src\panicking.rs:117
   3: parry3d::partitioning::qbvh::qbvh::GenericQbvh<rapier3d::geometry::collider_components::ColliderHandle,parry3d::utils::array::DefaultStorage>::rebalance<rapier3d::geometry::collider_components::ColliderHandle>
             at ...\.cargo\registry\src\index.crates.io-6f17d22bba15001f\parry3d-0.13.5\src\partitioning\qbvh\update.rs:367
   4: rapier3d::pipeline::query_pipeline::QueryPipeline::update_incremental
             at ...\.cargo\registry\src\index.crates.io-6f17d22bba15001f\rapier3d-0.17.2\src\pipeline\query_pipeline.rs:352
   5: rapier3d::pipeline::physics_pipeline::PhysicsPipeline::step
             at ...\.cargo\registry\src\index.crates.io-6f17d22bba15001f\rapier3d-0.17.2\src\pipeline\physics_pipeline.rs:624
   6: moss_renderer::resources::physics::Physics::step
             at .\src\resources\physics.rs:104
   7: moss_renderer::main::closure$0
             at .\src\main.rs:177
   8: winit::platform_impl::platform::event_loop::impl$3::run_return::closure$0<tuple$<>,moss_renderer::main::closure_env$0>
             at ...\.cargo\registry\src\index.crates.io-6f17d22bba15001f\winit-0.28.1\src\platform_impl\windows\event_loop.rs:256
   9: alloc::boxed::impl$48::call_mut<tuple$<enum2$<winit::event::Event<tuple$<> > >,ref_mut$<enum2$<winit::event_loop::ControlFlow> > >,dyn$<core::ops::function::FnMut<tuple$<enum2$<winit::event::Event<tuple$<> > >,ref_mut$<enum2$<winit::event_loop::ControlFlo
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33\library\alloc\src\boxed.rs:2014
  10: winit::platform_impl::platform::event_loop::runner::impl$3::call_event_handler::closure$0<tuple$<> >
             at ...\.cargo\registry\src\index.crates.io-6f17d22bba15001f\winit-0.28.1\src\platform_impl\windows\event_loop\runner.rs:250
  11: core::panic::unwind_safe::impl$23::call_once<tuple$<>,winit::platform_impl::platform::event_loop::runner::impl$3::call_event_handler::closure_env$0<tuple$<> > >
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33\library\core\src\panic\unwind_safe.rs:271
  12: std::panicking::try::do_call<core::panic::unwind_safe::AssertUnwindSafe<winit::platform_impl::platform::event_loop::runner::impl$3::call_event_handler::closure_env$0<tuple$<> > >,tuple$<> >
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33\library\std\src\panicking.rs:502
  13: once_cell::sync::OnceCell<tuple$<> >::set<tuple$<> >
  14: std::panicking::try<tuple$<>,core::panic::unwind_safe::AssertUnwindSafe<winit::platform_impl::platform::event_loop::runner::impl$3::call_event_handler::closure_env$0<tuple$<> > > >
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33\library\std\src\panicking.rs:466
  15: std::panic::catch_unwind<core::panic::unwind_safe::AssertUnwindSafe<winit::platform_impl::platform::event_loop::runner::impl$3::call_event_handler::closure_env$0<tuple$<> > >,tuple$<> >
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33\library\std\src\panic.rs:142
  16: winit::platform_impl::platform::event_loop::runner::EventLoopRunner<tuple$<> >::catch_unwind<tuple$<>,tuple$<>,winit::platform_impl::platform::event_loop::runner::impl$3::call_event_handler::closure_env$0<tuple$<> > >
             at ...\.cargo\registry\src\index.crates.io-6f17d22bba15001f\winit-0.28.1\src\platform_impl\windows\event_loop\runner.rs:157
  17: winit::platform_impl::platform::event_loop::runner::EventLoopRunner<tuple$<> >::call_event_handler<tuple$<> >
             at ...\.cargo\registry\src\index.crates.io-6f17d22bba15001f\winit-0.28.1\src\platform_impl\windows\event_loop\runner.rs:242
  18: winit::platform_impl::platform::event_loop::runner::EventLoopRunner<tuple$<> >::move_state_to<tuple$<> >
             at ...\.cargo\registry\src\index.crates.io-6f17d22bba15001f\winit-0.28.1\src\platform_impl\windows\event_loop\runner.rs:344
  19: winit::platform_impl::platform::event_loop::runner::EventLoopRunner<tuple$<> >::main_events_cleared<tuple$<> >
             at ...\.cargo\registry\src\index.crates.io-6f17d22bba15001f\winit-0.28.1\src\platform_impl\windows\event_loop\runner.rs:230
  20: winit::platform_impl::platform::event_loop::flush_paint_messages<tuple$<> >
             at ...\.cargo\registry\src\index.crates.io-6f17d22bba15001f\winit-0.28.1\src\platform_impl\windows\event_loop.rs:756
  21: winit::platform_impl::platform::event_loop::thread_event_target_callback::closure$0<tuple$<> >
             at ...\.cargo\registry\src\index.crates.io-6f17d22bba15001f\winit-0.28.1\src\platform_impl\windows\event_loop.rs:2316
  22: core::ops::function::FnOnce::call_once<winit::platform_impl::platform::event_loop::thread_event_target_callback::closure_env$0<tuple$<> >,tuple$<> >
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33\library\core\src\ops\function.rs:250
  23: core::panic::unwind_safe::impl$23::call_once<isize,winit::platform_impl::platform::event_loop::thread_event_target_callback::closure_env$0<tuple$<> > >
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33\library\core\src\panic\unwind_safe.rs:271
  24: std::panicking::try::do_call<core::panic::unwind_safe::AssertUnwindSafe<winit::platform_impl::platform::event_loop::thread_event_target_callback::closure_env$0<tuple$<> > >,isize>
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33\library\std\src\panicking.rs:502
  25: once_cell::sync::OnceCell<tuple$<> >::set<tuple$<> >
  26: std::panicking::try<isize,core::panic::unwind_safe::AssertUnwindSafe<winit::platform_impl::platform::event_loop::thread_event_target_callback::closure_env$0<tuple$<> > > >
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33\library\std\src\panicking.rs:466
  27: std::panic::catch_unwind<core::panic::unwind_safe::AssertUnwindSafe<winit::platform_impl::platform::event_loop::thread_event_target_callback::closure_env$0<tuple$<> > >,isize>
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33\library\std\src\panic.rs:142
  28: winit::platform_impl::platform::event_loop::runner::EventLoopRunner<tuple$<> >::catch_unwind<tuple$<>,isize,winit::platform_impl::platform::event_loop::thread_event_target_callback::closure_env$0<tuple$<> > >
             at ...\.cargo\registry\src\index.crates.io-6f17d22bba15001f\winit-0.28.1\src\platform_impl\windows\event_loop\runner.rs:157
  29: winit::platform_impl::platform::event_loop::thread_event_target_callback<tuple$<> >
             at ...\.cargo\registry\src\index.crates.io-6f17d22bba15001f\winit-0.28.1\src\platform_impl\windows\event_loop.rs:2493
  30: DispatchMessageW
  31: DispatchMessageW
  32: GetClassLongW
  33: KiUserCallbackDispatcher
  34: NtUserDispatchMessage
  35: DispatchMessageW
  36: winit::platform_impl::platform::event_loop::EventLoop<tuple$<> >::run_return<tuple$<>,moss_renderer::main::closure_env$0>
             at ...\.cargo\registry\src\index.crates.io-6f17d22bba15001f\winit-0.28.1\src\platform_impl\windows\event_loop.rs:278
  37: winit::platform::run_return::impl$0::run_return<tuple$<>,moss_renderer::main::closure_env$0>
             at ...\.cargo\registry\src\index.crates.io-6f17d22bba15001f\winit-0.28.1\src\platform\run_return.rs:51
  38: moss_renderer::main
             at .\src\main.rs:130
  39: core::ops::function::FnOnce::call_once<void (*)(),tuple$<> >
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33\library\core\src\ops\function.rs:250
axelmagn commented 4 months ago

I am also hitting this issue intermittently in parry2d:

thread 'main' panicked at /home/axelmagn/.cargo/registry/src/index.crates.io-6f17d22bba15001f/parry2d-0.13.6/src/partitioning/qbvh/update.rs:367:54:
attempt to add with overflow
stack backtrace:
   0: rust_begin_unwind
             at /rustc/82e1608dfa6e0b5569232559e3d385fea5a93112/library/std/src/panicking.rs:645:5
   1: core::panicking::panic_fmt
             at /rustc/82e1608dfa6e0b5569232559e3d385fea5a93112/library/core/src/panicking.rs:72:14
   2: core::panicking::panic
             at /rustc/82e1608dfa6e0b5569232559e3d385fea5a93112/library/core/src/panicking.rs:127:5
   3: parry2d::partitioning::qbvh::update::<impl parry2d::partitioning::qbvh::qbvh::GenericQbvh<LeafData,parry2d::utils::array::DefaultStorage>>::rebalance
             at /home/axelmagn/.cargo/registry/src/index.crates.io-6f17d22bba15001f/parry2d-0.13.6/src/partitioning/qbvh/update.rs:367:54
   4: rapier2d::pipeline::query_pipeline::QueryPipeline::update_incremental
             at /home/axelmagn/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rapier2d-0.18.0/src/pipeline/query_pipeline.rs:351:13
   5: rapier2d::pipeline::physics_pipeline::PhysicsPipeline::step
             at /home/axelmagn/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rapier2d-0.18.0/src/pipeline/physics_pipeline.rs:622:17
   6: stonehold::physics::Physics::step
             at ./src/physics.rs:40:9
   7: stonehold::game::Game::update
             at ./src/game.rs:116:52
   8: stonehold::game::Game::run::{{closure}}
             at ./src/game.rs:101:13
   9: stonehold::amain::{{closure}}
             at ./src/main.rs:14:16
  10: macroquad::exec::resume
             at /home/axelmagn/.cargo/registry/src/index.crates.io-6f17d22bba15001f/macroquad-0.4.5/src/exec.rs:72:11
  11: <macroquad::Stage as miniquad::event::EventHandler>::draw::{{closure}}
             at /home/axelmagn/.cargo/registry/src/index.crates.io-6f17d22bba15001f/macroquad-0.4.5/src/lib.rs:688:24
  12: <macroquad::Stage as miniquad::event::EventHandler>::draw::maybe_unwind
             at /home/axelmagn/.cargo/registry/src/index.crates.io-6f17d22bba15001f/macroquad-0.4.5/src/lib.rs:679:21
  13: <macroquad::Stage as miniquad::event::EventHandler>::draw
             at /home/axelmagn/.cargo/registry/src/index.crates.io-6f17d22bba15001f/macroquad-0.4.5/src/lib.rs:684:26
  14: miniquad::native::linux_x11::glx_main_loop
             at /home/axelmagn/.cargo/registry/src/index.crates.io-6f17d22bba15001f/miniquad-0.4.0/src/native/linux_x11.rs:404:9
  15: miniquad::native::linux_x11::run
             at /home/axelmagn/.cargo/registry/src/index.crates.io-6f17d22bba15001f/miniquad-0.4.0/src/native/linux_x11.rs:572:39
  16: miniquad::start
             at /home/axelmagn/.cargo/registry/src/index.crates.io-6f17d22bba15001f/miniquad-0.4.0/src/lib.rs:253:17
  17: macroquad::Window::from_config
             at /home/axelmagn/.cargo/registry/src/index.crates.io-6f17d22bba15001f/macroquad-0.4.5/src/lib.rs:764:9
  18: macroquad::Window::new
             at /home/axelmagn/.cargo/registry/src/index.crates.io-6f17d22bba15001f/macroquad-0.4.5/src/lib.rs:753:9
  19: stonehold::main
             at ./src/main.rs:10:1
  20: core::ops::function::FnOnce::call_once
             at /rustc/82e1608dfa6e0b5569232559e3d385fea5a93112/library/core/src/ops/function.rs:250:5
axelmagn commented 3 months ago

For others in this thread who are using rapier: my workaround has been to pass None for the query_pipeline argument in PhysicsPipeline::step. As detailed in https://github.com/dimforge/rapier/issues/532, this seems to bypass the update_incremental call that has a bug in it. Obviously this only works if you don't need to pass a query pipeline, but in my case it seems to resolve the issue.

tadeohepperle commented 3 months ago

I am also still hitting this issue. It would be nice to understand the root cause of it.