[On GitHub] Bounding Volume Hierarchy with basic physics queries

Heya,

As a half learning / half serious project I created a BVH that supports some basic primitives and physics queries, all done in Burst.

https://github.com/marijnz/NativePhysicsBVH

The README has an overview on what's supported, how it performs and has some example code.

Feedback is welcome!

 

I love you, and I mean that in the best possible way.

Was just looking into this topic and wondered what some good orientation points could be. Serendipitous timing!

I was a little surprised to see your fixed size TreeTraversalStackSize. That makes my danger sense tingle a little; for the most part because I don't quite know what's "a lot of depth" in a typical BVH use case yet.

In the distance query, you mention you want to make it SIMD, how do you think you will do that? My first approach would be to just descend into the tree breadth-first to a degree that I have enough relevant branches (subtrees), and run individual workerson those. Hints about the tree depth on these nodes can help balance the workload here, but they might be impossible to properly maintain without another performance hit.

Perhaps the tree could be made to be *very* balanced though, like an AVL tree, but that would make insertions and movement more expensive.

 

Heya, glad to hear!

You're right about the stack size. I went a bit overboard there to avoid heap allocs and capacity checks, but probably should do it safer. A good start would be another test that tries to break this on purpose.
Note that the tree rotations does a good job at balancing the tree. Run `TestBalancedTreeSortedInput` and then run it with the TreeRotations commented out, it's an interesting difference.

As for distance queries, have a look at the raycast. There it's done with simd (the transposed aabb is from Unity.Physics). I prepare the bounds of the grandchildren, that wastes some memory but allowed for a 2x speedup of raycasts.
I have a half baked attempt with multiple aabb's in a single node here: https://github.com/marijnz/NativePhysicsBVH/tree/simd_attempt. But that complicated so many things that I'd rather avoid it. Performance wise it was (just like my new approach) about 2x faster, but that was without some balancing optimizations I did since then.

I'm not sure about the running of individual workers, what does that have to do with simd?

As for a -very- balanced tree, not sure. That's probably not desirable as it would create a lot more surface area (imagine a couple stones that are far away from a huge forest, the huge forest ideally doesn't impact a raycast near the stones).