In many situations (see linked issues), especially at the first simulation frame, but also if many objects are inserted at once during the simulation, the QBVH incremental update algorithm could lead to a degenerate tree. Ideally the fix would improve the incremental update to lower risks of imbalance, but this is a very difficult problem.
A way simpler, but less efficient, fix (that is implemented in this PR) is to force a complete tree rebuild if it reaches a certain depth, indicating degeneracy. That depth is set to 15, which for a perfectly balanced QBVH, can hold 4^15 = 1.073.741.824 leaves (meaning that past that number of object in the tree you are guaranteed to trigger a forced rebuild at every update. But this is a very unlikely number to reach in practical games).
In many situations (see linked issues), especially at the first simulation frame, but also if many objects are inserted at once during the simulation, the QBVH incremental update algorithm could lead to a degenerate tree. Ideally the fix would improve the incremental update to lower risks of imbalance, but this is a very difficult problem.
A way simpler, but less efficient, fix (that is implemented in this PR) is to force a complete tree rebuild if it reaches a certain depth, indicating degeneracy. That depth is set to 15, which for a perfectly balanced QBVH, can hold
4^15 = 1.073.741.824leaves (meaning that past that number of object in the tree you are guaranteed to trigger a forced rebuild at every update. But this is a very unlikely number to reach in practical games).Fix https://github.com/dimforge/parry/issues/146 Close https://github.com/dimforge/parry/pull/169 Fix https://github.com/dimforge/rapier/issues/466 Fix https://github.com/dimforge/rapier/issues/532 Fix https://github.com/dimforge/rapier/issues/558 Fix https://github.com/dimforge/rapier/issues/450