Collision Detection and Particle Interaction

Collision Detection and Particle Interaction

In many particle systems, you will want the particles to interact in some way. You might want them to repel, bounce or stick together. However, the process of comparing each particle with every other can be very slow. The number of comparisons you will have to do is proportional to the square of the number of particles. So if you double the number of particles, the number of comparisons will have to increase fourfold.

Particles Comparisons
1 0
2 1
3 3
4 6
5 10
6 15
7 21
8 28
9 36
10 45
11 55
12 66
13 78
14 91
15 105
16 120
17 136
18 153
19 171
20 190
50 1225
100 4950
500 124750
1000 499500
5000 12497500
10000 49995000

As you can see from the table, the number of comparisons can be very large indeed. If, for example, you were modeling a field of 10,000 stars moving under gravity, you would be performing 149985000 multiplies and 49995000 square roots per time frame! So, anything that can be done to reduce the time taken to perform a comparison or, even better, reduce the number of comparisons that need to be done, is well worth the effort.

In this page, I will be introducing the idea of a blockmap to reduce the number of comparisons needed. This has the disadvantage of requiring a lot of memory, and can only be used in some circumstances, but can provide a very real improvment in speed.

I first heard about this method while I was learning to make Doom II .WADs. Doom uses a block map to manage collision detection between objects & walls.

The idea behind a blockmap is to only compare particles that are close by. The area is divided up into discrete blocks, and particles check surrounding blocks to see if they contain a particle.

If you are allowing your particles to move around in an infinite arena, you may find it hard to divide up the space efficiently. If you are doing this in 3D, then be warned. You will need a lot of blocks. So this is best suited to something finite and 2D, like Doom.

A Quick Overview

So you divide up the space into blocks. Each block is capable of holding a list of the particles that are in it. At the begining of each time frame, you clear the data in each block. Loop through all the particles and decide which blocks they cover. Mark those blocks as containing that particle. Next, you loop through all the blocks that have been modified, and if a block has more than one particle in it, then you perform your interactions on those particles.

An Example

Here we have a 4x4 blockmap, containing three particles of various sizes.

The GREEN one covers block d1
The YELLOW one covers blocks a2, a3, b2, b3
The RED one covers blocks b3, b4, c3, c4


So now each block is marked as containing certain particles.

Now, you have two choices. Either:

  • Go through block, check that it has more than two particles in it, and if so, perform all the comparisons on them. This is best done when most of the blocks will contain particles. We can see from the small diagram that block b3 contains two particles. So, you know that those two particles might be touching.
  • Go through each particle, calculate (again) which blocks it covers and check if there are any other particles in those blocks. If there are, then perform the comparisons on them. This is best done if the particles are distributed sparsely about the area.

    Block Structure

    So how do you store the blocks? Well, this depends on your particle system.

    Either you can allocate space in each block for a finite number of particles: 

    structure BLOCK
  INT         number_of_particles
  POINTER     p1, p2, p3, p4, p5
end structure
    . . . or you can use linked lists. 
    structure BLOCK
  INT         number_of_particles
  POINTER     first_particle
end structure
    If you can be sure that there won't ever be any more than, say, five particles covering any one block, then it is well worth using the first method. If, however, you cannot be sure, then it's best to use the second, although it may be slower.

    Notes on BlockMaps

    One thing to be wary of. It is quite easy to accidently compare a pair of particles twice. Imagine if the yellow block was one block higher. The block map would look like this:

    If you're not careful, the program would think that the red and yellow particles had collided twice. Now, this may or may not matter. If it does, then you will have to take steps to avoid it.

    The blockmap is only suitable for particle systems with short range interactions, like snooker balls. Long, or infinite range systems, like gravity stars are best left to the brute force method.