Sign in to follow this  
vo1d

Collision between many particles

Recommended Posts

vo1d    122
There are many 3D particles (>1000). Particle have position, velocity, force and radius. Need fast algoritm to detect (predict) collisions between particles. I already tried space subdivision with small cells. What about algoritm called "nearest neighbor list"? Thanks and sorry for my bad English.

Share this post


Link to post
Share on other sites
someusername    427
For such special cases, you can use a linear algorithm I've come up with.
I'm sure others have thought of this too, it's not that special.
(actually it may be the one you're talking about, because this would be pretty much the name to describe what I'm talking about!!!)

I'll explain it in one dimension first, so you can see how the generalization goes.
Imagine a bunch of spherical particles, with all their centers lying on the regular X axis. There are no Y/Z axes, the spheres can only move left/right on X.

At the begining of the simulation, you'll have to do a precalculation.
Sort the coordinates of the spheres' centers, and set two pointers for each particle to point to the two particles, closest to the left and closest to the right of that specific one.

During the simulation, the particles will move. The key however, is that a sphere can only collide with either the closest sphere to the left, or the closest to the right. So you only test collision with 2 particles per particle.

If you add an extra dimension, things change a bit. Add Y for instance. Now you have another couple of pointers per particle, pointing to the 2 closest particles, upper and lower the given one.
Looking at only one axis, it may look like two particles are actually colliding. However for that to hold, there must be a collision with the same particle in all axes!
Whenever such a case appears, e.g. particles p1 and p2 seem to collide in X, but this is not true for Y too, all you have to do, is rearrange their pointers to the left/right closest particles. If it seemed to happen in Y, but was not verified in X, you would have to change their "up/down closest" pointers

Example: p1 was the closest -to the right- of p2 in the X axis, and it now hit p2 in X, but not in Y. P1 will obviously have to go through p2 in X axis -from right to left-, since they don't actually collide.
When this happens, you rearrange their "X closest" pointers as such:
P2's closest X+ was P1, now becomes P1's closest in X+ (some particle P(y))
P2's closest X- was some P(x), now becomes P1
P1's closest X+ was some P(y), now becomes P2
P1's closest X- was P2, now becomes P(x)

The following may depict better what I'm trying to say:

Before:
(Px)<->(P2)<->(P1)<->(Py)
After:
(Px)<->(P1)<->(P2)<->(Py)

The only problem is, that when a particle moves, you'll have to split its motion in steps equal to its "radius + minimum particle radius" to make sure that it can't go -completely- through any particles without being able to tell.

If you need to magically "pop" a particle somewhere in the simulation, as you understand, this will screw the algorithm completely. What you can do is implement a "bubblesort" type of sorting algorithm with a stop-flag on whether there were any exchanged elements during last scan. Since you'll only have one unsorted element (the first in the list e.g.), the bubblesort will immediately put it in the right place, and by the next scan it will exit because the list was already sorted by almost 100%. Of course you'll need to do this once for each axis.

That's it. I tried to explain it the best I could... In 3d, the concept is the same, you just need a total of 6 pointers to particles, and you'll need to verify collisions in three axes to make sure.
If it sounds like a lot of job, let me remind you that it's O(n) complexity and it can't get any better. (I doubt it can get O(1)!!!).

Share this post


Link to post
Share on other sites
jjd    2140
To clarify that a bit: OP, before you calculate the "neighbourhood list" sort the particles in one dimension, say the x-axis. Iterate through the sorted list to create the neighbourhood list, but now you won't have to do a full pairwise comparison.

I've heard of using bubblesort for this before (like someusername said) but my experience is with insertion sort for this problem. Insertion sort scales almost linearly for partially ordered data, perhaps bubblesort does too. Quicksort is very bad for this kind of data though. Note that your sorted list won't change much between neighbourhood updates so it will be partialy ordered. Also, if you are using periodic boundary conditions, I would suggest using shell sort because then some particles can make very large shifts in the list.

Perhaps for large simulations sorting along multiple axes is useful, but I do not have any experience with this and I think that you would need to be dealing with many more particles before the sorting overhead in that case would be worthwhile. Using this method I could simulate about 10,000 particles on a Pentium2 (maybe it was a pentium 3...) in realtime.

If you have to deal with complex boundary geometry, however, it might be worth looking at a binary space partition (BSP) technique.

Share this post


Link to post
Share on other sites
someusername    427
Quote:
Original post by jjd
I've heard of using bubblesort for this before (like someusername said) but my experience is with insertion sort for this problem. Insertion sort scales almost linearly for partially ordered data, perhaps bubblesort does too.


I don't know what others would use with this; it just makes sense to me, to use this "modified" bubblesort when the original list is sorted, but has had a few unsorted element prepended as its beginning.

1. for( i=1; i<n; i++ )
2. {
3. bExit = true;
4. for( j=i+1; j<=n; j++ )
5. {
6. if(list(i) > list(j))
7. {
8. swap( list(i), list(j) );
9. bExit = false;
10. }
11. } // j loop
12. if( bExit && i>=nUnsorted )
13. break;
14. } // i loop

...where nUnsorted is the number of unsorted elements that were prepended to the list. The condition in (12) will become true at most at i==(2*nUnsorted+1) scans, ignoring the rest of the list and returning the sorted result.

I don't know how the continuous swap()s will scale, for numbers at the order of n=10^4 as you mentioned, but if you implement it with the 3 XORs method, it will be as fast as it can ever get...

The best way would be to have two implementations; one just like the one above, and a "rocksort" one, sorting for i=last element down to second, and j=i-1 down to first element.
Then, given a bunch of unsorted numbers, you can test which of them are smaller than the element at position=n/2 (it can be safely assumed to be the median of the list, since it's already sorted), prepend them to list and use the first implementation to sort them. Then append the rest numbers at the end and use the second implementation...

The insertion sort should be just fine too, though. I believe that the actual performance of swap() should be the one to decide which method should be used.

edit:
Quote:

The condition in (12) will become true at most at i==(2*nUnsorted+1) scans, [...]

hmm, ignore that. it doenb't seem right now that I'm thinking it over... but it shouldnt be much bigger anyway.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this