Completely fair collision detection

it''s a pain, but I don''t think there are any other way round.

as a thought, for each objects, I''d only keep the earliest collision involving an object and store it in the list, one per object.

I''d process the earliest collision pair, then I''d remove all collision pairs in the list either involving A and B, and keep in mind the objects involved in those collisions. then re-test all these objects again, and find the earliest collision for each one again, add them to the list, ect...

for that method, you have to keep in mind the maximum time of collision left for each objects, since the time frame between objects will be de-synchronised when a collision is processed on two objects.

Hi Meto (remember SBG?). I have discussed the same algo, a bit more detailed in recent threads. I''d like someone tries to implement a perfectly timed coldet/percussion scenary, since it''s something that runs in my head for 2 years and I''d like to see if it works as well as I can hope. But as you know I am focused on spearhead terrain rendering and I don''t have the time for anything else.

I do not think in the case of this demo it''s difficult to code. Some dead-ends to avoid and bypass are :

- infinite loops due to numerical precision issues.

- using conservative col. det. (bounding volumes) for efficiency adds exceptions in the main algo.
(tevent A predicted < tevent B, but in fact it''s the opposite)

- using space partition and creating bubbles - groups of potential interaction would probably help to speed-up things and help reorganize the whole algorithm in ''general state''.

- generalize with constraints like sliding might make the algo very nasty.

Optimizations :
- I have the idea to grow radius with time for swept spheres (dunno if it''s a common thing) to take accelerations into account and warrant conservatism in col det. Equations are still second degree polynomials.

What else ? Well very late here. I bookmark and will see this thread for later.

Hi,

Glad to see some people are interested in this and have been working on it themselves, it''s given me the motivation to develop it as fully as I can.

Talking about execution time it looks rather nasty ignoring early escape tests.

For n objects, you have n^2 initial tests, then for each collision you have to make an additional n tests which may result in a recursive number of n tests.

So what optimisations are there so far? Well I''m working it from concept to optimised so not everything is in yet.

1. Range check
2. Direction check
3. Another Range test
4. Determine collision time

Certainly space partitioning will help improve this (as the first range check is several multiplications and subtractions.

Prediciting subsequent collisions can probably be optimised also although I''m going to have to work through simple cases to see if that is actually true. I like your idea of bubbles of objects that might collide although this may only work well in optimal cases.

Acceleration would be an interesting factor too.

This algorithm could get very time consuming especially if heavy recursion occurs (imagine a object wedged tighly between two imovable walls, it will bounce back and forth, now imagine something similar to a bean bag where your going to get massive chain reactions of impacts)

A little background why I''m doing it. I''m currently working on my final year physics project on computational evolution. As we are modelling evolution we need to ensure that no natural advantages come from the method of programming. A creature that gets to move first may gain a very slight advantage (in terms of harvesting food) over another and this isn''t allowed. Randomizing move order isn''t good either as a creature may get lucky and gain an advantage. It''s already complicated enough with very simple ''creatures'' with only 3 genes and although these creases may iron out, they sometimes don''t which screws a whole set of results.

Anyway I''ll stop rambling and start working.

-Meto

p.s. I can''t wait to see the hell this becomes when I start working with triangles instead of circles/spheres.

it is hell, yes, and you are welcome

if the objects are mostly scattered in 2D, and well distributed, use a sweep and prune algorithm. This involves sorting objects on the X and Y axis by their intervals, and building lists of intersecting intervals, and merging the two resulting list together. This should give a list of pairs of potentially colliding objects, that you can test. As objects move about, you merely have to shift the object into the sorted list, so the overhead is low. That''s the algo I''d first use if there was no other ways (like if the world was not already partitioned into some other way, like a BSP tree).

Another algo I''ve heard about, but first and foremost, I''ve never tried these kind of scheme, but I''ve seen it in action in one of the Programming Gems''s article. It was a dynamic sphere tree. I don''t think I understood the exact algorithm, but it goes something like this. I''m sure someone will correct me.

a potential speed up and a nice way to do this is to cluster objects into colliding groups, as Charles B said. Each objects have a large bounding sphere (to encompass the velocity as well as the object sphere itself, plus a generous extra radius). say, you have objects A, B, C, D, E, F, G, H, I. Each group is a collection of objects, and each group has a bounding sphere as well.

A intersects B. A and B form a group G0(A, B)
C intersects D. C and D form a group G1(C, D)
F Intersects G Intersects I, forms group G2(F, G, I)
H intersects C. H stored in group G1(C, D, H)
H also intersects B. group G2 merged into group G0(A, B, C, D, H).

in each groups, you only need to tests collisions between objects inside the groups. When an objects exits a group''s bounding sphere, either you remove it from the group, or merge with an adjacent group. ect...

My feelings are mixed towards the sweep and prune algo. I find the algo pretty in itself because it exploits frame to frame coherency and a simple reinsert sort. But I also dislike how it can potentially become unoptimal in the worst conditions. Most geometric algorithms put a heavy predicate on what''s called a system in general position (specially those based on X or Y sweeping). When you think of real life problems, these general positions are often not so general because real life scenes have very often constructed patterns. I remember having analysed the sweep prune algorithm mathematically in the case of a high density of objects, and it can become really poor specially if the velocities follow diagonals.

I think a simple quadtree (QT) or even a regular 2D grid is enough for space partition and quick rejection. I would use three levels of rejection :

n moving objects :
1) Use BBoxes of the capsules and put em in the QT.
( capsule = Union( sphere(t) ) t in [tmin,tmax] )

2) Check the moving spheres combinations, accelerate with the QT. Put potential any event(A,B) in the time ordered list. As Oii said remove any potential event(A,X) if t(A,B) < t(A,X).
time : between n and nlog(n) ? (in normal conditions)

3) Advance time and process the list of the potential events.
time : n2 (outputs)

- if event(A,B) (time tAB) actually occurs before the next potential event (*) you can safely process a percussion and set the states of A and B right after tAB.

- even if event(A,B) do not occur, do not forget to :

redo 1) and 2) for A and B only.

(*) Else you have to handle an exception, swap two events.

4) Advance all the states to time tmax, the supposed end of the frame, render.

Remark, the algorithm requires a dynamic state per object AND the time it''s been integrated to. Each object stores a different time between tmin and tmax.

To me the process time is close to the absolute minimum. It''s quasi equal to the output, that is the number of collision events you have to detect and process anyway. Adding the fact that conservatism can be fully asserted (growing radii for acceleration), it''s not only fast it is robust.

I could point great improvements of the algorithm. For instance how tmax could in fact be far beyond the end of the ''frame''. This way collision detection could be dispatched with a far lower ''frequency'' (say 5FPS). Concretely, if only gravity acts, you can predict a collision between two rockets, many frames ahead, and during many frames this won''t be recomputed.

Now it''s certain that it works well in a general case. A magma of balls with impulse responses would work rather well. But what if physics based on constraints are mixed ?

What happens in the case Metorical described (many bounces) ?

- If there is enough space left and movement, your ball actually bounces. Of course many events, thus more processing. But how is it compared to a typical physics engine ? It''s more accurate and far more speedy for ColDet. Basically, as the algorithm is, with space partition, you only check the ball against the two walls. Plane equations and a first degree equation root extraction won''t hurt much. Now this won''t bounce forever if you assert than cinetic energy diminishes.

- Next when the energy is quasi null make it exactly null, and set your body as ''quiet'' (*). Thus you avoid an infinitely growing rate of smaller and smaller microscopic bounces. Wake it up only if a new collision occurs.

- Else if the ball does not bounce much but rolls on a surface, make the velocity follow exactly the surface (remove the normal component of V). Do not forget to act the reaction of the surface (may counter gravity if it''s the ground). Set the object as constrained on this surface, until a new percussion occurs or until it leaves the surface.

Well I know it''s better said than done. But if I had to work on physics again, I would dig in this direction. To me mechanics hold discrete events (like percussion) because transitive (*)states are quasi impossible to model accurately. Physics engines are alwys error prone numerically and algorihmically because time is necessarilly dicretized.

That is why I would not rely 100 percent on simulators based on one big linear programming matrix. I would add some exceptions and some scenarii to accelerate and assert very common situations. And I would try to hack the difficult cases with a game coder spirit.