Collision Detection with Enneatrees

Many of my games boil down to, at some level, a large collection of circles (or spheres) interacting with each other. I use circles for collision detection, and otherwise whenever I can for organization, because the results look more natural than using boxes. If you organize using boxes, your simulation will tend to “align” to the axes, which nature surely does not do.

So naturally, detecting when two of these circles are touching each other is one of the larger computational problems that my games face. And bewilderingly, I have not found anywhere a good solution that covers circles in a wide variety of sizes. That is what this article is about.

If your circles are all about the same size, and in particular fairly small in comparison to the needed accuracy of the algorithm, the obvious and de-facto solution is to use a quadtree. That is, start with the whole screen and divide it up into 4 regions, and do so recursively until you have a nice spatial arrangement of your objects, categorizing objects by which region their center lies in.

When you have a circle and want to see what other circles are touching it, you just look for other objects in the smallest region. Well, except you are not a point, you are a circle, so you might penetrate the edge of the region, in which case you need to look at the adjacent region as well. Well, except other circles might penetrate the edges of their regions, so you actually need to look at all adjacent regions. Well, except you might be really big, so you need to look in all the regions that you touch. Well, except other objects might be really big, so… you need to look in all the regions.

A quadtree has not bought us anything if circles can be arbitrary sizes; collision detection is still linear. You could say things like the number of very big circles is usually small (because they would collide away their competition), so you can put an upper bound on the size of circles in the tree then just do a linear check on the big ones. But that is an awful hack with a tuning parameter and doesn’t generalize. Shouldn’t the right solution work without hacks like that (for the fellow game developers in my audience: despite your instincts, the answer is yes :-).

I have worked with quadtrees before, and saw this problem a mile away for my game with circles of many different sizes. The first variation I tried was to put circles into regions only if they fit entirely. Circles on the boundaries would be added to the lowest branch that they could fit into. Then to check collisions on an object, you look at where it is in the tree, check all subregions, and then check all superregions (but not the superregions’ subregions). You will get small things in your vicinity on your way down, and large things on your way up. And it’s still logarithmic time… right?

Wrong. Suppose that every object in the world lay on the horizontal and vertical center lines. Even very small objects would accumulate in the top node, and no region subdividing would ever occur. This degenerate situation causes linear behavior, even though just by shifting the center of the region a little bit you get a sane subdividing. It’s not just a “let’s hope that doesn’t happen” thing: there are a lot of bad situations nearby it, too. Any object lying on those center lines will be checked when any other object is testing for its collisions, because it is on the way up. This did, in fact, become a major issue in my 10,000 particle simulation.

But if we could somehow salvage the original idea of this solution without the degenerate case, then we would get logarithmic behavior (when the field size is large relative to the radii of the particles).

To understand this solution, I would like you to turn your attention to one dimensional simulations. Here the previous solution would be subdividing the real line into a binary tree.

But the new solution divides intervals into not two, not four, but three child intervals. However, not in thirds like you would expect. (0,1) is divided into (0,1/2), (1/4, 3/4), and (1/2,1) — the intervals overlap. Any “circle” (in 1-D, so it’s another interval) with diameter less than 1/4 must fit into at least one of these subregions.

We use that property to organize the circles so that their size corresponds to their depth in the tree. If you know the diameter of the circle, you know exactly how deep it will be. So now when we are looking downward, we really are looking for small circles, and when we are looking upward we are looking for large ones, and there is no possibility of an accumulation of small irrelevant circles above us that are really far away.

However, on your way up, you also have to check back down again. If you are in the left portion of the (1/4,3/4) interval, you might intersect something from the right portion of the (0,1/2) interval, so you have to descend into it. But you can prune your search on the way down, cutting out “most” (all but a logarithm) of it. For example, you don’t need to check the interval (1/16,1/8) and its children even though you are checking its parent (0, 1/2) — it is too far away.

When you are deciding which region to put a circle in and you have a choice, i.e. the circle fits in multiple subregions, always pick the center one. When the circles are in motion, this gets rid of the degenerate case where a circle bounces back and forth across a deep, expensive boundary.

If you generalize to 2D, you end up cutting a region into 9 subregions (thus the name enneatree). The way I did it was to alternate cutting horizontally and vertically, so that I didn’t have to have 9-way if-else chains. That had more subtleties than I had expected. I have yet to find a straightforward, elegant implementation.

The algorithm seems to work well — I am able to support 5,000 densely packed circles in C# without optimizations.

The inspiration for this algorithm comes from the field of computable real numbers (infinite — not arbitrary, but infinite precision numbers). You run into trouble if you try to represent computable reals infinite streams of bits, because some interactions might be “non-local”; i.e. you might have to look infinitely far down a stream to find out whether a bit should be 0 or 1. Those guys solve the problem in the same way I did, by dividing intervals into 3 overlapping subintervals, and using this 3-symbol system as their number representation.

I see a glimmer of a connection between the two problems, but I can’t see it formally. Maybe it would become clearer if I considered infinite collections of infinitesimal objects needing collision detection.

About these ads

12 thoughts on “Collision Detection with Enneatrees

  1. Im skeptical about this:

    “I use circles for collision detection, and otherwise whenever I can for organization, because the results look more natural than using boxes. If you organize using boxes, your simulation will tend to “align” to the axes, which nature surely does not do.”

    I would distinguish between geometry that /participates/ in the simulation (leaf object hulls), and geometry that /optimizes/ the simulation (axis-aligned bounding boxes [AABB]). I’d be curious to understand if you believe use of AABBs could “axis-align” the simulation dynamics, if the AABBs themselves never result in collision responses?

  2. Also… Im curious why you dont consider/discuss object-based hierarchies like AABBs, as well as spatial subdivision method like Quadtrees.

    A property of AABBs I like is that sibling bounding-boxes can overlap slightly, with little impact on overall utility. Also, when objects move “a little”, AABB extents can be re-adjusted without shuffling objects between nodes, whereas (as you point out) spatial subdivision methods typically requires shuffling moving objects around whenever they cross a boundary

  3. Well, the circles comment was more relevant for Gravmari. In Gravmari we had to approximate up the yin-yang — calculating exact gravitational forces would be way too expensive. We used an object-based hierarchy for that based around bounding circles, which did indeed “hide” the approximations very well. I could have gone into that algorithm as well, but I’m having enough trouble finding time to write in-depth blog entries as it is.

  4. Joe: Could you elaborate, or give me a pointer to a paper or site that describes what you are thinking about? From what I gather, “recursive spatial hashing” is a lot like a quadtree, but there are many more children per branch than 4, and some sort of hash function is used to organize them. Is that accurate? Is there a special property the hash function must have?

  5. Firstly I highly recommend this book: http://tinyurl.com/yhcf83s (links to amazon).

    The trouble with tree based structures is they’re expensive to build. Unlike hashing, where for each frame, you can just iterate through every object inserting it into a hash table and check for collisions at the same time.

    Also I have a little opengl/C demo that throws ~1k balls around the screen. I could send you the source to if you want more explanation?

  6. It’s similar, but not the same as, loose octrees. In particular enneatrees encode three intervals along a dimension, instead of splitting the interval and specifying a “looseness”.

    It shares some characteristics with a centered interval tree (http://en.wikipedia.org/wiki/Interval_tree#Centered_interval_tree)

    A CIT is however adaptive (like a kdTree) whereas the enneatree uses fixed intervals as a spatial hash (as described in the post).

    I’d like to see more details, in particular how it might perform versus a CIT. It seems like insertion/deletion would be (or could be) more efficient with the hash than the CIT.

  7. Have you ever considered hierarchical spatial hashes?

    In a normal spatial hash for similarly sized objects, you get nearly a constant time for insert and query. The biggest determining factor is how many hash cells you have to visit. In general, increasing the size of an object by n means you need to visit 2^n times as many hash cells. That is where spatial hashing falls flat.

    Implementing hierarchical spatial hashes is a fairly trivial modification of composing multiple spatial hashes like a mipmap. Each level at half the resolution of the one proceeding it. Levels can be removed if there are empty. When inserting an object, use it’s bounding area to guess which hash level to insert into. When rehashing, rehash the lowest resolution hash first querying for collisions during the rehash. When rehashing the rest of the levels, also query the levels above them for collision. This algorithm is also logarithmic, and is still flexible enough to run in constant time for a set of like sized objects.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s