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

Jondolf · 2023-07-10T14:51:20Z

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);
}

The text was updated successfully, but these errors were encountered:

tesselode · 2023-08-28T03:32:07Z

I am also having this issue.

hakolao · 2023-11-16T11:16:49Z

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

LachlanHogan · 2024-01-02T10:28:16Z

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 · 2024-03-07T23:59:37Z

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

Parry occasionally panics due to add overflow (dimforge#146). I couldn't write a test that reliably replicates the condition, but since it occurs at `src/partitioning/update.rs:367` and the only addition on that line is `depth + 1`, I'm willing to bet money that the problem is that we are overflowing `depth`, which is a `u8`. I bumped it to `u32`, which should still have low memory cost and be more space than we ever need for a tree structure.

axelmagn · 2024-03-10T18:57:15Z

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 dimforge/rapier#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 · 2024-03-17T17:07:36Z

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

Fix dimforge/rapier#466 Fix #146 Fix #169 Fix dimforge/rapier#532 Fix dimforge/rapier#558 Fix dimforge/rapier#450

Jondolf mentioned this issue Sep 11, 2023

Avoid incremental updates to Qbvh Jondolf/avian#152

Merged

Jondolf changed the title ~~QBVH rebalance still panicks at 'attempt to add with overflow'~~ QBVH rebalance still panics at 'attempt to add with overflow' Feb 20, 2024

axelmagn mentioned this issue Mar 8, 2024

QbvhUpdateWorkspace stack depth change u8 to u16 to prevent overflow #169

Closed

sebcrozet added a commit that referenced this issue Mar 23, 2024

fix: force a complete QBVH rebuild when it gets too imbalanced.

97145f2

Fix dimforge/rapier#466 Fix #146 Fix #169 Fix dimforge/rapier#532 Fix dimforge/rapier#558 Fix dimforge/rapier#450

sebcrozet mentioned this issue Mar 23, 2024

fix: force a complete QBVH rebuild when it gets too imbalanced. #185

Merged

sebcrozet closed this as completed in #185 Mar 23, 2024

sebcrozet added a commit that referenced this issue Mar 23, 2024

fix: force a complete QBVH rebuild when it gets too imbalanced.

7df2728

Fix dimforge/rapier#466 Fix #146 Fix #169 Fix dimforge/rapier#532 Fix dimforge/rapier#558 Fix dimforge/rapier#450

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

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

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

Jondolf commented Jul 10, 2023 •

edited

Loading

tesselode commented Aug 28, 2023

hakolao commented Nov 16, 2023

LachlanHogan commented Jan 2, 2024

axelmagn commented Mar 7, 2024

axelmagn commented Mar 10, 2024

tadeohepperle commented Mar 17, 2024

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

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

Comments

Jondolf commented Jul 10, 2023 • edited Loading

tesselode commented Aug 28, 2023

hakolao commented Nov 16, 2023

LachlanHogan commented Jan 2, 2024

axelmagn commented Mar 7, 2024

axelmagn commented Mar 10, 2024

tadeohepperle commented Mar 17, 2024

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

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

Jondolf commented Jul 10, 2023 •

edited

Loading