# Particles self-collision algorythm

This topic is 2880 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi all !

I'm new on the forum and sorry for my poor english.

I'm starting to play with python and particles physics for fun. I'm not a hardcore coder/developper , I never study in that and I'm learning by myself.
I did with python and Blender a verlet integration and I want to do self-collision. It's take a lot of processing time when you compare each particles
between each other particles at each substep.This "brute force" method take 3sec for 1000particles ... 48sec for 4096 .... and it's growing up exponentialy
like that more I add particles and it's normal.

I start to check for kd-tree or octree. This algorythm if fast to find neighbours and I have to compare less particles for distance and if a collision occur.
I find a simple kdtree implementation in python and I'm starting to playwith it.

But because I move particles several time in a substep to satisfy different constraint/collision. For that I need to modify particlesposiitions informations
in the tree. But I read than modify a kdtree and keep it balanced is very hard. I need to regenerate de kdtree for each particles move ( if I have
1000 particles ... it's 1000times to regen the kdtree ). It's not very efficient... probably not more then brute force medthod.

Octree is more faster/simpler/efficient for dynamic objets ? But I not finding a working octree example in python.

Better algorythm exist for that ?

My only solution for now is to continu to use kd-tree but enlarge search-neighbourg radius to compensate for the mist of sync between kdtree data
generate only at beginning or end of substep and the real currently position of particles in the substep.

here is a video of what I'm truing to do :

"Brute Force" without any algorythm for finding neighbours:

My objectifs is to have 1-2millions particles with 5-10minute per substep of processing. I know it's possible with smarth system like kdtree or octree.
Realtime is not my goal but I know game developpement always have fast and good algorythm for this king of things.

thanks a lot !

##### Share on other sites
Search for 'hash-grid' on google - you may not even need the hash part if your world is small enough

##### Share on other sites
If your algorithm takes 3 secs to do a brute-force collision check on a 1000 particles, then either your computer is *very* slow or your algorithm can be optimized quite a lot. A somewhat modern pc is supposed to run that many particles in real-time without any problems. How exactly are you doing this?

##### Share on other sites
@wildbunny: thanks for the tip! I do some search on that now

@h4tt3n: my computer is not the most powerful: AMD Phenom2 X6 3ghz with 6gig ram. But you may notive my script is done with python not in C++ or other compiled language. . I don't know if I do it right too, I'm really novice like I said. I just pass trought every particles with for loop to check if the squareroot distance is lower then the squareroot radius. If it's the case, I calculate the real distance ( by did a inverse 2 exponent to the squareroot distance ) and place 2 particles at the exact distance it need to be to satisfy the collision. Really basic math. But I calculate distance twice like: I gave particles 1,2,3. For 1 I calculate distance between 1 - 2 and 1 - 3 , for particles 2 , distance betwen 2 - 1 and 2 - 3. But has you see , 2 - 1 is already done when I calculate 1 - 2. I need to fix that but this make the script just 2time faster , not realtime :S

##### Share on other sites
Ok I read a bit about grid hashing and it's similar to a idea I have two week ago beforestarting to play with octree and kdtree.

I want to have your opinions on that.It's simple.

Just by converting point coordinate to Interger and put it has key of a dictionary.This make point with the same key, in the same place of the dictionary.
I things it's fast because I don't have to check and create empty cell and cell with point is fast created by just convert value to integer. And to add or
remove point to cell , is really easy too. I don't know if something can be faster than that ?
And for searching neighbourg I got two ideas:

-One: by just check neighbourg cells

-The second: by placing nears points of a cell in this cell. For that create virtual cell at the same size but at the half position of the real cell.
Just by subtracting and add a value ( half of the cell size). I'm not sure if it's clear ... I joint a image to explain:

##### Share on other sites
The method where you assign each particle to a cell and do collision detection only with particles assigned to the same cell or neighboring cells works just fine. I use it in a particle fluid simulation, and it handles around 14000 particles in real-time on a 4 year old machine. Never heard of the other method you mention.

##### Share on other sites
Thank h4tt3n.
I try that when I have a bit of time. I don't know if I can make 14 000 particles with python but it's would be faster then brute force. And you use the same grid force collision with object too?

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 15
• 11
• 9
• 11
• 15