# Bounding volume hierarchy - linked nodes (linear model)

The scenario A chain of points: (Pi)i=0,N where Pi is linked to its direct neighbours (Pi-1 and Pi+1).

The goal: perform efficient collision detection between any two, non-adjacent links: (PiPi+1) vs. (PjPj+1).

The question: it's highly recommended in all works treating this subject of collision detection to use a broad phase and to implement it via a bounding volume hierarchy. For a chain made out of Pi nodes, it can look like this:

I imagine the big blue sphere to contain all links, the green half of them, the reds a quarter and so on (the picture is not accurate, but it's there to help understand the question). What I do not understand is:

How can such a hierarchy speed up computations between segments collision pairs if one has to update it for a deformable linear object such as a chain/wire/etc. each frame? More clearly, what is the actual principle of collision detection broad phases in this particular case/ how can it work when the actual computation of bounding spheres is in itself a time consuming task and has to be done (since the geometry changes) in each frame update? I think I am missing a key point - if we look at the picture where the chain is in a spiral pose, we see that most spheres are already contained within half of others or do intersect them.. it's odd if this is the way it should work.

-

## 2 Answers

Essentially what you're describing with your spiral example is a pathological case, where all of the interesting points are co-incident. You could just as readily construct a hypothetical case where every single collision pair is identical.

The point of broad-phase culling and use of hierarchical volume trees is not to be a perfect solution for every case, but to improve efficiency in the general case. Given a relatively even distribution of collision objects through the space, hierarchical bounding systems like oct-trees or kd-trees are great at very quickly drilling down to a much smaller subset of objects to check. For a typical game where objects are distributed around a relatively large landscape rather than being localised to one tiny area, spatial partitioning is very cheap and generally very effective.

But, when choosing an algorithm for broad phase culling, you are always balancing efficiency of computation against expected results. Even if your spatial determination (the cost of figuring out where in the spatial hierarchy to put an object) only costs a tenth of the cost of a proper object-object check (the narrow phase), then to be more efficient, spatial partitioning needs to cut down the number of comparisons needed in the narrow phase by more than a factor of ten. If it doesn't, then you're better off not broad-phase culling at all.

If you know in advance your problem domain is such that the pathological cases are common (e.g. you're simulating a lot of coiled chains), then you should either a) tag those cases such that they skip the broad phase altogether and go straight to narrow phase without incurring the partitioning cost, or b) find a broad-phase culling algorithm that better fits your domain.

No algorithm will be perfect in all situations, you are looking for the best average efficiency gain for your particular situation. I can't think of a better solution off-hand for chain collision detection, but I should imagine that you can still use BVH-style culling, you just have to be smarter about how you separate out objects into cullable groups.

-
Thanks for the points highlighted in your answer, similar to a common sense intuition (i.e. there can be cases where you're better off with no broad phase). I think I'll try it by computing the BVH on a per frame basis and see how that's improving things. – teodron Jun 13 '12 at 10:58
BVH, although good in a lot of ways, is simply one sort of broad-phase culling. It's good because it's cheap and easy to maintain. For the case of chains, where you're essentially checking 2D line segments of similar lengths, it would seem to me that a simple separating-axis test would be even cheaper, and give you workable results. Each line segment has a trivially determined AABB, which could easily be compared against the other AABB prior to doing a more expensive line-intersection test. – MrCranky Jun 13 '12 at 12:45
Erm.. the chain is a 3D linear object. It can happen that an SAT test is equally complicated as the segment vs segment collision test, or am I exaggerating the cost? – teodron Jun 13 '12 at 12:57
I'd have to go back and count the operations, I'm so used to avoiding multiplies / divides that I'd presumed that even a few comparisons would be cheaper. As always, better not to assume and simply profile with the broad phase on/off in the problem scenarios. – MrCranky Jun 13 '12 at 13:02
This is one of those areas where optimisation starts to get away from the nice clean purity of a simple design. Setting flags or maintaining dynamic lists of links for processing is obviously extra work, but it's balanced against the gains from avoiding work. Avoiding recomputing information that's largely the same every frame is good, but only if the expected behaviour is that most of the time, the chains don't change much from the previous frame. – MrCranky Jun 18 '12 at 12:18

In the case you have posted, you would still get benefit from an Axis aligned bounding box based BVH - the first division could split the left/right segments (or top/bottom segments) with very little overlap, and subsequent sub-volumes would divide reasonably well too.

Unfortunately, using a circle as your bounding primitive for lines clustered in a circular shape ensures that you will always have a large amount of overlap, and an inefficient tree.

-