TIGSource Forums

This question was asked to me a week ago by a friend and I haven't been able to find a reasonable answer despite searching for various ways. Does anyone know of a good solution?

Question:

Suppose I have been given an extremely large number of spheres in 3D space. I know their x,y,z coordinates and radii. I only need to find the number of spheres that collide with each other, as fast as possible.

Typically you'd use some kind of spatial data structure -- grid, loose octree, whatever.

The details usually depend on how much the size of the spheres varies (are they all roughly similar sizes?) and how they're distributed in space (uniformly? concentrated in sparse regions?) -- any expectations re that stuff?

It depends a bit, mainly on whether you want to do it more than once and how much (if at all) everything is moving around.  Storing things spatially can be a big help, especially for games where you're checking everything many many times and most collidable objects are (relatively) stationary, but can sometimes actually be slower (because of the overhead of maintaing the data structure) than the simpler option of just checking each object against every other object.

You can also increase the speed of the calculation by doing faster, less-accurate collision tests (axis-aligned-bounding-boxes for instance) first to see whether they might be touching, then (if so), slower more accurate collision detection to see whether/where they actually are.  Again though, this will only help if most spheres are not that close together - if all of them intersect each other at once it's just going to slow things down.

In brief: there's not necessarily a 'right' answer to this - although there are a lot of tricks you can use they won't work for every situation.  Best thing to do is try several approaches and see what works for you.

Since you asked about spheres specifically, one thing that can speed it up considerably is, when looking at the distance between the spheres to see whether they intersect or not, check the square of the distance rather than the distance itself.  This avoids having to use a square-root function which is iterative and hence slow as hell.

I could say a lot of things, but, use Box2D. Or any other collision engine.
Don't reinvent a wheel that is so complicated and so standard, there's really no point.

Although given that Mhaine said an "extremely large" number of spheres, that probably won't be the case here.

Box2D and other collision engines are already very optimized for cases with a lot of objects, using internally the data structures described here.
For example, I saw here on TIGSource a screenshot of Chipmunk managing more than 1000 circles without effort, so their performance is for sure "good enough" for any sane PC game.

Obviously Chipmunk, Box2D and the others are generic libraries, so Mhaine could achieve better performance knowing the details of his problem.
But probabily that would be hard and time consuming for anyone that is not a physics expert, and useless because existing libraries are good enough.

EDIT: just found this video (http://www.youtube.com/watch?v=V1xiVyJ3EOM), I don't think anyone could do better while also finishing a game  ;)

Anyway, I don't understand why, given such a specialised problem, you wouldn't write your own collision detection code. Especially rather than using box2d to find collisions between spheres.
Octrees are surprisingly easy to implement, and work great for objects that move around a lot. If the spheres aren't actually moving, the sweep and prune algorithm might do better.

On the other hand, if you're actually writing a game, you'll probably want to collide all sorts of different types of objects, at which point a collision detection package will almost certainly be a much faster way to get something done.

Doh  :durr:

Anyway he said "spheres on a plane", and spheres that only collide on a plane are to all effects 2D circles, so box2D is ok. Should it be full-3D, there's always Bullet.

IF he will ever only do sphere-sphere collisions, and IF he can make something better optimized than existing libraries, and IF the spheres are really A LOT, a custom solution could be needed.

Premature optimization is the root of all evils, and deciding to write a custom system when there exist excellent and flexible libraries without even testing them is just stupid.
So I'll insist, try some collision library. ONLY THEN decide if they won't make the cut.

Thanks for responding, everyone!


Oh! I hadn't heard of spatial partitioning before. Just took some time to learn about it. It indeed seems like the best case for collision checking is O(n^2), but at least I now know about BSP trees and octrees and whatever. All I knew about collisions before was from a verlet integration-based physics engine I had built for myself. Seems like there are a lot of things to consider when working on larger systems.


Indeed, this was all I was able to find by myself when googling. I will look at those less accurate methods you mentioned.


That is precisely what I am asking for. I am not caring about a dynamic system either, though judging from what I've learnt so far, it could be better to learn whatever there is. I am considering extreme cases with much more than several thousand objects, but the question itself is just about collision detection in an extremely large static set of objects.

By the way, sorry, I meant "space", not "plane" when asking the question. Missed the mistake probably because I had "3D" too much in mind (and perhaps because of the excessive use of "plane" in tensor calculus books I am reading right now). That doesn't affect the main question too much, however (in the sense that the solution methods should be theoretically similar, if not exact).

? Maybe I'm not parsing this right but, to be clear ... O(n^2) is the worst case; O(n) is the best case ... that's the point of the binning.

For example (as the simplest case) if your sphere size is some relatively small constant*, you could get O(n) by:
(1) voxelize** the relevant 3D space***
(2) raster each sphere into space
(3) as you raster each sphere, check if you're writing 'solid' onto an already-solid spot, if so the sphere is colliding.

(* if the sphere size is not constant some hierarchy could be applied to avoid excessively large rasterizations.)

(** voxels of course are only accurate to the resolution of the grid, however if that is an issue you could specially mark ambiguous/border voxels and do additional processing just for those cases.)

(*** if this is too has too much empty space, some smarter hashing and/or hierarchy could be used instead)

Mhaine: Thanks for clarifying. It's important to know that these are static spheres, because performance in a dynamic system depends in part on being able to update the broadphase entries efficiently while static systems do not have that constraint. You might have success applying kd-trees (http://en.wikipedia.org/wiki/Kd-tree), as I know they are used for raytracing large static datasets. Unfortunately I pretty much only deal with dynamic situations so the remainder of my comment will focus on that.

The simplest (optimized) broadphase I know of: sort+sweep aka sweep+prune. It's easy enough to describe.

First you sort all spheres in a list ordering their position along one axis. Then you apply this algorithm:

1. Start at the head of the list. The head is your first pivot.
2. Look ahead through the list, comparing the position of each entry against the radius of the pivot. Mark all the entries that are inside the radius.
3. Stop when you've exceeded the radius and perform a narrowphase test on the marked entries.
4. Increment the pivot by one and repeat.

For most dynamic situations, this is excellent since the list will stay mostly-sorted in between runs, so you get close to O(n) behavior if your other axes aren't heavily overlapped. The algorithm can be extended to cover additional axes, but with diminishing returns.

Anyone know if this is the sort of thing GPU-based computing could help with? It seems like it, being massively parallel and all.