editor+project crash if use_bvh=false

[pseidemann]

Godot version

v3.5.1.stable.official (6fed1ff)

System information

macOS 13.1 (22C65)

Issue description

when I enable the project setting 3d/godot_physics/use_bvh=false, the editor will always crash when opening the project. also the project crashes on startup when running it via the command line

ERROR: Condition "_first != nullptr" is true.
   at: ~List (./core/self_list.h:108)
ERROR: Condition "_first != nullptr" is true.
   at: ~List (./core/self_list.h:108)

================================================================
handle_crash: Program crashed with signal 11
Engine version: Godot Engine v3.5.1.stable.official (6fed1ffa313c6760fa88b368ae580378daaef0f0)
Dumping the backtrace. Please include this when reporting the bug on: https://github.com/godotengine/godot/issues
[1] 1   libsystem_platform.dylib            0x00007ff804dd5c1d _sigtramp + 29
[2] 2   ???                                 0x00007ff7bf55c370 0x0 + 140702043718512
[3] GjkEpa2::MinkowskiDiff::get_support_without_margin(ShapeSW const*, Vector3 const&, float)
[4] DirAccess* DirAccess::_create_builtin<DirAccessOSX>()
[5] DefaultAllocator::alloc(unsigned long)
[6] DirAccess* DirAccess::_create_builtin<DirAccessOSX>()
[7] 7   dyld                                0x00007ff804a78310 start + 2432
-- END OF BACKTRACE --
================================================================

Steps to reproduce

• set 3d/godot_physics/use_bvh=false in project settings
• open project in editor or start project

Minimal reproduction project

I can't isolate what is causing this crash.
I'm using SurfaceTool, MeshDataTool and Navigation all at runtime

[lawnjelly]

It seems to crash on 3D platformer demo BTW, not that it's very minimal but it's a start and repeatable...

It's a crash on this line in Viewport::_process_picking(bool):

bool col = space->intersect_ray(from, from + dir * far, result, Set<RID>(), 0xFFFFFFFF, true, true, true);

1  typeinfo name for Object                           0x206c290 
2  Viewport::_process_picking     viewport.cpp   655  0x4e07ccb 
3  Viewport::_notification        viewport.cpp   399  0x4e05c73 
4  Viewport::_notificationv       viewport.h     91   0x4e284db 
5  Object::notification           object.cpp     927  0x600afab 
6  SceneTree::_notify_group_pause scene_tree.cpp 1133 0x4dd8439 
7  SceneTree::iteration           scene_tree.cpp 585  0x4dd7a4e 
8  Main::iteration                main.cpp       2309 0x2c5173f 
9  OS_X11::run                    os_x11.cpp     4035 0x2c05b1e 
10 main                           godot_x11.cpp  59   0x2bedc59 

Getting lots of errors from the octree:

ERROR: Condition "!E" is true.
   at: move (./core/math/octree_definition.inc:918)

Also getting a couple of these errors, which don't occur when BVH is used:

ERROR: Condition "_first != nullptr" is true.
   at: ~List (./core/self_list.h:108)

This might be a Nan being passed to octree, and maybe BVH is dealing with it more gracefully (or maybe the Nan is a symptom). Will investigate.

EDIT:

The selflist error is occurring with this stack:

1  SelfList<BodySW>::List::~List                                           self_list.h             110  0x5c37482 
2  SpaceSW::~SpaceSW                                                       space_sw.cpp            1328 0x5c36a18 
3  memdelete<ConstraintSW>                                                 memory.h                115  0x5c36ff0 
4  SpaceSW::_broadphase_unpair                                             space_sw.cpp            1136 0x5c3599a 
5  BroadPhaseOctree::_unpair_callback                                      broad_phase_octree.cpp  115  0x5c030bf 
6  Octree<CollisionObjectSW, true, DefaultAllocator>::_pair_check          octree_definition.inc   291  0x5c08903 
7  Octree<CollisionObjectSW, true, DefaultAllocator>::_element_check_pairs octree_definition.inc   370  0x5c05a8e 
8  Octree<CollisionObjectSW, true, DefaultAllocator>::move                 octree_definition.inc   951  0x5c03fa9 
9  BroadPhaseOctree::move                                                  broad_phase_octree.cpp  40   0x5c02bfc 
10 CollisionObjectSW::_update_shapes                                       collision_object_sw.cpp 179  0x5c0c1a4 
11 CollisionObjectSW::_set_transform                                       collision_object_sw.h   96   0x5c0fae5 
12 BodySW::integrate_velocities                                            body_sw.cpp             637  0x5c13113 
13 StepSW::step                                                            step_sw.cpp             264  0x5c7c55c 
14 PhysicsServerSW::step                                                   physics_server_sw.cpp   1312 0x5befda9 
15 Main::iteration                                                         main.cpp                2318 0x2c517a0 
16 OS_X11::run                                                             os_x11.cpp              4035 0x2c05b1e 
17 main                                                                    godot_x11.cpp           59   0x2bedc59 

I am slightly suspect this might be a regression that has crept in as the BVH and Octree may do their callbacks at slightly different times, and most people are using BVH now as it is default. 🤔

UPDATE:
The regression was introduced somewhere between 3.5 beta 1 (works) and beta 2 (broken).
Somewhere in these commits:
b9b23d2...7a4f9df

It may be tricky to find as the artifacts have expired for these builds so it would require manual bisecting. I don't know if any physics contributor at that time might have any ideas. I had a look through my PRs for the period (as I do the BVH but not the physics) but I couldn't see anything leaping out at me as a possible candidate (although it's not impossible).

On the other hand we may end up just deprecating octree in 3.x anyway at some point. We already have removed it from 4.x, and I don't know if anyone still uses it?

Actually thinking about it, if it's taken nearly a year for anyone to notice it is broken, that is a fairly good indicator maybe there aren't a whole lot of people using it anymore. 🤔

[lawnjelly]

@rburing has bisected down to #55640 so it's due to me. 😊

It's probably we shifted some code around to octree that was no longer required for BVH. Am investigating. 👍

EDIT: Yes can confirm that un-shifting the valid collision pair section of code from SpaceSW::_broadphase_pair to BroadPhaseOctree::_pair_callback fixes the bug, so I'll see if I can work out why it is happening.
Ideally don't want to shift it back, as this check is already done on the BVH so it has no need for it in BVH mode.

Ah fixed it. It was fairly simple, and it was understandable because there are two pointers at the end of the function and fairly easy to get them mixed up what they were meant to mean (I have no idea what the functions here in the physics do, so just reverse engineering 😄 ). Will make PR soon. 👍

[akien-mga]

Fixed by #70365.

[pseidemann]

thanks all!