[Algorithms] N-body processing

[Pierre T. <p.t...@wa...>]

Ok, while we are deeply in touch with the subject (GJK, RAPID, Q-COLLIDE,
wacky patents...) let me introduce my new brain-blaster for the week-end:
N-body processing.

Some CD libraries such as RAPID only deal with two bodies. On top of that,
you need some more code to handle collision between multiple pairs,
something known as N-body processing. For example V-Collide is just made of
some N-body code built on top of RAPID.

I know the usual ways to deal with it: cut your world into sectors, use
spatial partitionning techniques, octrees, quadtrees, whatever, and use some
sweep&prune approach as a final death-blow.

In other words, assume I know which pairs are possibly colliding. My concern
is about the way I can manage (not detect) all of them. For example, for
each pair I could have to do some processing the first time the pair gets
active, and some processing when it stops colliding. For example in GJK it
would involve computing the initial supporting vertices in an efficient way.
Then, for each possible pair I may need some data structure to store some
values. I then need a way to:
- allocate and de-allocate ram for active pairs
- track active pairs
- access any possible pair in an efficient way

The most obvious and stupid solution would be something like an array of N*N
structures, with N = the number of objects in the simulation. Of course,
this is absolutely out of question. My standard test sets N = 1024, to give
you some ideas.

I'm curious about the solutions you people could imagine. Something with an
hash-table maybe, but then what would be a good hash-key? This also can be
seen as the reference/owner problem one can have with shared
materials/textures/etc, since an (owner, ref) couple is nothing more than a
pair of colliding/touching/linked/related entities. I don't think I have any
brilliant ideas for the moment, but I'm curious about yours....

Cheers,

Pierre