11
\$\begingroup\$

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
var _ Broadphase = (*BVHNode)(nil)

// 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?

\$\endgroup\$
3
\$\begingroup\$

Since you say this method is slower than the (also not shown) O(n^2) brute force mechanism, I can only assume that you mean for any n.

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.

You don't show your NewBoundingSphereFromSpheres function, does this recurse too? (giving another O(ln(n)) / O(n) function)

If GeneratePotentialContactsWith or NewBoundingSphereFromSpheres is an O(n) function then processing n points will yield an O(n^2) algorithm.

Note that if you want maximum performance for a given algorithm then avoid using channels. They are much much slower than function calls. Looping recursion is also significantly faster than function recursion since it avoids stack allocation and per function initialisation & exit overhead. Channels allow elegant concurrency but just make sure you are maximising the amount of productive work and minimising the amount of the channel concurrency golang runtime work that is being invisibly performed.

\$\endgroup\$
  • \$\begingroup\$ I don't know why Billal added a bunch of \ and $ to my answer; it makes it much harder to read - reverting \$\endgroup\$ – RidiculousRichard May 18 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy