Collission detection - Which objects to test?

Not really a graphics programming question, but anyway. To keep collision detection fast, you should first do the most simple form of detection and discard as many objects as possible. A distance check between 2 objects is much cheaper than testing each and every triangle for example. If A and B are more than X meters away from each other, you'll be sure that none of the triangle-checks will return positive either.

However, if you have 1000 objects, you still have to do 1000 x 999 = 999.000 checks. Well, you can half that (if A does not touch B, than B doesn't touch A either of course), but its still lots of work, even for a simple check. On the other hand, if you just have a few objects, it will be fine.


Octrees/BPS's/Quadtrees are techniques to reduce the amount of unnessesary checks drastically further, based on positioning. Imagine your house. When you walk in the livingroom, there is no need to check collisions between you and the stuff from the kitchen or bedroom. Only check with other (nearby) objects in your livingroom. One way to reduce collision checks is to split up your world in sectors/cells or whatever you like to call them. If you have large worlds with lots of objects (a forest), it's still not going to help much though.


Techniques like octrees divide the world into boxes. And each box can be divided into 8-sub boxes as well. If there is lots of detail(triangles/objects/...) into a box, divide it further. Now when you have to check for collisions, you only have to:
A- determine in which (sub-sub-sub-...)box you are, and eventually its neighbour boxes
B- check collisions with the entities inside those box(es)

Step A is very easy. Is your coordinate on the left or right side? If on the right, go further into the sub-boxes of the right, and so on, until you can't go any deeper. Step B is just looping through the entities from that box. Then perform a simple distance/sphere/box collision test. If it hits, you can check again on full detail per triangle.

Iddeally, there is nothing or only 1 entity to check for each box. However, that might mean you have to divide your tree on a super small scale. Having tiny boxes and many levels isn't going to work either so you could tell the octree-building process to have 8 sub-levels at max for example, or keep the boxes bigger than 2 square meters.

Greetings,
Rick

ok, I understand that I have to subdivide the world somehow, but I don't know what the best way to do it is. How do I check which bounding sphere or box my player hits on its path from A to B? I need to make this determination before proceeding onto triangle level collision detection. I need a cheap effective way of doing this though...right now my player has a bounding sphere and so does each object. I could easily switch to boxes if I had to.

One alternative is Sweep-And-Prune.

Basically it's an optimization of testing pairs of objects on one axis at a time. On a single axis, if the space taken up by two objects doesn't overlap, then we know it can't collide, and don't have to compare the other axes.

Sweep and prune's idea is to take all of your objects min and max coordinates on a particular axis, sort them, then detect overlaps by making a single pass through the sorted list of coordinates and keeping track of which objects are currently 'active' at each index.

For example, given objects A, B and C:

(A.X1=0.0) (A.X2=1.0) (B.X1=10.0) (B.X2=11.0) (C.X1=200.0) (C.X2=400.0)AAAAAAAAAAAA          BBBBBBBBBBBBB           CCCCCCCCCCCCCC

The sweep detects that no objects overlap, so it prunes them all. For the Y and Z axes, there are no objects left to test.

Now, let's say object A has moved a bit. First, you have to re-sort the list. Luckily, in most cases it takes several frames for objects to start to overlap, so they usually stay in the same sorted positions in the list. This is called "Temporal Coherence". This also means that you can use cheaper algorithms to sort the list, since it's already MOSTLY sorted.

(A.X1=9.1) (B.X1=10.0) (A.X2=10.1) (B.X2=6.5) (C.X1=200.0) (C.X2=400.0)AAAAAAAAAAAAAAAAAAAAAAAA           BBBBBBBBBBBBBBBBBBBBBBBBB                                              CCCCCCCCCCCCCC

When the sweep reaches B.X1, it realizes that it hasn't seen A.X2 yet. That means that A and B overlap on the X axis.

This same process is repeated for each axis separately. Any object that has failed any previous axis' sweep can be ignored when making a sweep over a later axis.

After the process is finished, you have a list of objects that need to be tested up close and personal, perhaps with sphere-sphere, separating axis tests, Voronoi regions, etc.

I dont use octrees much, because they get trickier when you need moving objects, the other easy alternative to an octree is a large 2d array which encompases the whole world, or the world around the player and you run the games collision detection in 2.5d instead of 3d. this way you only need to check the grid positions where the player object intersects, and thats another way to reduce the amount of work you need for allobjects vs allobjects collision detection.

Nypyren: I think I understand. I was thinking of this, and in my mind I pictured finding the distance between a line and a point...same idea right? you talk about a separating axis, but I can just use the displacement vector for this right? or do I have this all wrong?

rouncED: working in 2.5d sounds like an effective solution, but concidering that I will have to compensate for moving objects, it doesnt seem like it will be practical for my purposes. I would like to have a smaller but more densly packed environment with lots of things happening. Thanks though.. I will keep it in mind.

I found this site:
http://www.softsurfer.com/Archive/algorithm_0102/

listed there was this code:


can I not use this and then check this squared distance against the sum of the two squared radii of the two bounding spheres?
would this not be practical, and even fast? and better yet, parralellizable?

any input on this would be much appreciated XD

That Article is not as good as you may think, I've said that before many times, the main problem is that the space switching becomes non trivial when ellipsoids rotate, and transforming all points around to match ellipsoid space is not that computationally cheap.

Besides that, the obvious problem everyone misses because of how the article is written is that it doesn't check against triangle edges, and implicitly assumes triangles to be infinite planes, here is a crude graphic I drew a while ago to illustrate this:



As you can see, the sphere is indeed in a path of collision with the triangle, but it misses it because it is not a head on collision, special cases do need to be added to handle these situations.

My recommendation is, as always, to stick to convex shapes and use the Separating Axis Theorem instead.

Kwizatz: It sounds like you may not be aware that the article I listed is the revision. The special cases have been added to that article. The article describes checking for a collision with the plane firstly, then the triangle, then the vertices and edges.

Also, In my first post, I did say that I would only be using spheres, and would not be dealing with ellipsoids.

Beside all this, the whole purpose of this post is trying to find the best "cheap test" to do before the actual collision detection to minimize the work of the actual collission detection.

I definately appreciate the fact that you took the time to draw out a diagram, but what I really need is some kind of trivial rejection for collision detection. I proposed a method in my previous post, and am looking for input.