Physics Simulation Question (Collision Detection no physics knowledge required)

[Jaevko]

I'm writing a physics simulation/game in java applets, I have a quick question about collision detection. DISCLAIMER: I am not a math or a CS major, so this is probably a ridiculously easy question for most people on here:

My question regards speed when there are lots of objects. Right now, the game checks all objects (circles) against all objects to see if there is a collision. I was originally going to divide space up into grids (squares) and check each item against all items in its grid and (8) adjacent grids. However, I got to thinking...checking to see if the distance is less than the sum of the radii is not that bad, and dividing into grids WILL consume resources. So to test the theory of "leaving it how it is is okay" I added one hundred objects (so each checking against every other is running through this code something like 100*100/2 times, a lot!). However, it still ran fine.

So the question is: Do I just need to add more objects to experience the slow-down that dividing into grids will save me from? Or will dividing the area into grids not provide a significant advantage/actually be worse than my current method?

Relevant code is below:

for (int counter1 = 0; counter1 < PhysicsApplet.mastercounter-1; counter1++) { //run all moveable
            for (int counter2 = counter1+1; counter2 < PhysicsApplet.mastercounter; counter2++) //run through all the ones that have not been check against it yet (anything above it on the list)
            {
                srad = PhysicsApplet.masterlist[counter1].radius + PhysicsApplet.masterlist[counter2].radius; //sum radii
                //distance between middle of objects (sum of radii):
                dis = Math.sqrt((PhysicsApplet.masterlist[counter1].x_pos - PhysicsApplet.masterlist[counter2].x_pos)*(PhysicsApplet.masterlist[counter1].x_pos - PhysicsApplet.masterlist[counter2].x_pos) + (PhysicsApplet.masterlist[counter1].y_pos - PhysicsApplet.masterlist[counter2].y_pos)*(PhysicsApplet.masterlist[counter1].y_pos - PhysicsApplet.masterlist[counter2].y_pos));
                if (srad > dis) { //if true then collision

Thanks for your time! :)
-Computational Physics Newbie


P.S. I am eventually going to do some sort of trajectory analysis to avoid fast objects going through each other, but my question has nothing to do with that issue, for now I am satisfied with the "if its touching during the frame then collision" algorithm.

 

[Filip Larsen]

Do I just need to add more objects to experience the slow-down that dividing into grids will save me from? Or will dividing the area into grids not provide a significant advantage/actually be worse than my current method?

If I remember correctly, the time complexity of making collision detection at a particular instance in time using space division structures, like octrees[1] in 3D-space, are O(log(n)²) [2] and combining that with the cost of updating the structure the overall time complexity for collision detection over time is O(n*log(n)) or something similar depending on exactly how the collision detection and structure update algorithms are combined. Compare that to the O(n²) complexity of the simple algorithm.

Complexities tell you how the algorithm performs when you scale up your problem. If you are only interested in a (low) fixed number of particles, it may very well be that a simple algorithm (with high run-time complexity) will outperform a more complex algorithm (with low run-time complexity) for a fixed problem size.[1] http://en.wikipedia.org/wiki/Octree
[2] http://en.wikipedia.org/wiki/Big_Oh_notation

 

[chiro]

Hey Jaevko and welcome to the forums.

When it comes to doing things like collision detection and rendering, you need a spatial classification structure.

The simplest one of these is the BSP tree. The BSP tree is short for binary spaces partitioning.

The way BSP works is that it divides the space up into two halves using a linear classification object (in three dimensions its your standard 3D plane). What happens is that the triangles of the polygons of your world as used as the division references (remember each triangle represents a plane and you need a minimum of three points to define a plane in 3D space), and the BSP routine partitions the whole space into left and right halves to generate the BSP tree.

Using this classification structure you can optimize rendering and optimize collection detection.

I won't go into great detail about how this is done but the basic idea is that if you take an object and it is on the right side of your first plane at the root of your tree, (i.e. the dot product of the point with the plane is positive), then when it comes to rendering, you do render everything that is behind that plane first before everything on the right hand side. It does this kind of thing recursively and its better to read the code and get some examples, but that is the basic kind of idea.

With collision detection, you simply create a routine using your data structure that allows you to eliminate objects that will never have a chance of colliding. The idea is you narrow down the space of objects that will have any chance of collision and just work with those exclusively.

With BSP, the drawback is that the world is static. If you change the world, then you have to recompile the whole tree.

Typically what people do is they use static and dynamic objects and treat them separately for performance.

The idea is the same for other spatial classification structures with the exception being that the classification structure itself is different. Instead of a plane it might be something as simple as a cube, all the way up to some convex hull or collection of convex hull objects. The hull object is simply a convex object that describes the interior of some convex hull. In case you are wondering a convex hull is just a set of planes (remember only one in BSP), where the planes are oriented in a way that they enclose a finite region of space (remember in BSP you divide space into two regions and theoretically these two spaces are infinitely big).

If you want to do this seriously, I would start off looking at BSP and its application to collision detection, and then think about what would happen when you change the classifier to another object (convex hull, or some other simple region) and how that affects the spatial structure.

 

[chiro]

(Double post)