# Bounding volume hierarchy

I'm building a bounding volume hierarchy in Golang. I can tell my code works because I did some test on it and it gives the same results as the brute force implementation (brute force is to test all possibilities, in $O(n^2)$).

My problem is that the code is slower than the brute force implementation (not by that much but enough to make me wonder why I bothered to implement this in the first place). Maybe that's normal, but I would like the opinion of my peers on this.

For those who don't know Golang but would still like to take a look. a chan is a primitive to send/receive messages from other threads (we call thread, goroutine in Go). If I have c <- m that means "send this message via this channel". Both the brute force and the BVH use this primitive so thats probably not the reason for the slowdown.

package tornago

// this line makes sure that *BVHNode is a valid Broadphase

// BVHNode represents a single node in a bounding volume hierarchy.
type BVHNode struct {
children [2]*BVHNode
parent   *BVHNode
BoundingSphere
body *RigidBody
}

// NewBVHNode returns a new bvh node. Use this to start a bvh tree.
func NewBVHNode(b *RigidBody, volume *BoundingSphere) BVHNode {
return BVHNode{
body:           b,
BoundingSphere: *volume,
}
}

// IsLeaf returns true if this node has no children.
func (n *BVHNode) IsLeaf() bool {
return n.body != nil
}

// GeneratePotentialContacts sends all colliding bounding sphere to the narrow
// phase detector.
func (n *BVHNode) GeneratePotentialContacts(narrowPhaseDetector chan<- PotentialContact) {
if n.IsLeaf() {
return
}
n.children[0].GeneratePotentialContactsWith(n.children[1], narrowPhaseDetector)
}

// GeneratePotentialContactsWith accepts a second node with a bounding volume to
// test against.
func (n *BVHNode) GeneratePotentialContactsWith(o *BVHNode, narrowPhaseDetector chan<- PotentialContact) {
//df("inspecting %p,%p\n", n, o)
// If they don't overlap then we are done.
if !n.Overlaps(&o.BoundingSphere) {
return
}

// If they're both leaves, then we have a potential contact.
if n.IsLeaf() && o.IsLeaf() {
narrowPhaseDetector <- PotentialContact{
[2]*RigidBody{n.body, o.body},
}
return
}

// Determine which node to descend into. If either is a leaf, then we
// descend the other. If both are branches, then we use the one with the
// largest size.
if n.IsLeaf() {
n.GeneratePotentialContactsWith(o.children[0], narrowPhaseDetector)
n.GeneratePotentialContactsWith(o.children[1], narrowPhaseDetector)
o.GeneratePotentialContacts(narrowPhaseDetector)
return
}

if o.IsLeaf() {
o.GeneratePotentialContactsWith(n.children[0], narrowPhaseDetector)
o.GeneratePotentialContactsWith(n.children[1], narrowPhaseDetector)
n.GeneratePotentialContacts(narrowPhaseDetector)
return
}

// If they're both branches then descent into the biggest.
if n.GetSize() < o.GetSize() {
n.GeneratePotentialContactsWith(o.children[0], narrowPhaseDetector)
n.GeneratePotentialContactsWith(o.children[1], narrowPhaseDetector)
n.GeneratePotentialContacts(narrowPhaseDetector)
} else {
n.children[0].GeneratePotentialContactsWith(o, narrowPhaseDetector)
n.children[1].GeneratePotentialContactsWith(o, narrowPhaseDetector)
o.GeneratePotentialContacts(narrowPhaseDetector)
}

// and then like do them separatelly because yknow thats what things.
}

// RecalculateBoundingVolume recalculates the bounding sphere of this node.
func (n *BVHNode) RecalculateBoundingVolume() {
if n.IsLeaf() {
return
}
n.BoundingSphere = NewBoundingSphereFromSpheres(&n.children[0].BoundingSphere, &n.children[1].BoundingSphere)
if n.parent != nil {
n.parent.RecalculateBoundingVolume()
}
}

// Insert inserts this rigid body in this node of one of it's childs.
func (n *BVHNode) Insert(b *RigidBody, volume *BoundingSphere) {
if n.IsLeaf() {
n.children[0] = &BVHNode{
BoundingSphere: n.BoundingSphere,
body:           n.body,
parent:         n,
}
n.children[1] = &BVHNode{
BoundingSphere: *volume,
body:           b,
parent:         n,
}
n.body = nil
n.RecalculateBoundingVolume()
return
}

if n.children[0].GetGrowth(volume) < n.children[1].GetGrowth(volume) {
n.children[0].Insert(b, volume)
} else {
n.children[1].Insert(b, volume)
}
}


Is there something obvious in my implementation that would make this super slow? Am I doing something twice or anything that could add a lot more work to achieve the same result?

This implies that your new algorithm is also an O(n^2) algorithm. In fact you can see in GeneratePotentialContactsWith that this is at least a O(ln(n)) function since it appears to use tree recursion; it may be an O(n) function - it's not clear to me.
If GeneratePotentialContactsWith or NewBoundingSphereFromSpheres is an O(n) function then processing n points will yield an O(n^2) algorithm.