Handmade Hero»Forums»Code
m
5 posts
Particles (episode 156)
Hi,

Been playing around with the particle system from episodes 155-156,
and having one problem with the dispersion:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
particle_cel *CelCenter = &GameState->ParticleCels[Y][X];
particle_cel *CelLeft = &GameState->ParticleCels[Y][X - 1];
particle_cel *CelRight = &GameState->ParticleCels[Y][X + 1];
particle_cel *CelDown = &GameState->ParticleCels[Y - 1][X];
particle_cel *CelUp = &GameState->ParticleCels[Y + 1][X];

v3 Dispersion = {};
real32 Dc = 1.0f;
Dispersion += Dc*(CelCenter->Density - CelLeft->Density)*V3(-1.0f, 0.0f, 0.0f);
Dispersion += Dc*(CelCenter->Density - CelRight->Density)*V3(1.0f, 0.0f, 0.0f);
Dispersion += Dc*(CelCenter->Density - CelDown->Density)*V3(0.0f, -1.0f, 0.0f);
Dispersion += Dc*(CelCenter->Density - CelUp->Density)*V3(0.0f, 1.0f, 0.0f);
v3 ddP = Particle->ddP + Dispersion;


So, if my CelCenter density = 1 and CelLeft density = 0
and CelCenter density = 1 and CelRight density = 0,
then it means they wont get pushed sideways at all (as the Dispersion.x will become 0)?

Gif image of whats happening: (not getting pushed to sides)
http://pasteboard.co/1CPjpMTT.gif

Am I getting something wrong, or should it push particles to left or right at all,
if current cell density is 1 and left & right cells have same densities?

thanks!
Casey Muratori
801 posts / 1 project
Casey Muratori is a programmer at Molly Rocket on the game 1935 and is the host of the educational programming series Handmade Hero.
Particles (episode 156)
I don't believe you are doing something wrong, that is just a consequence of doing central differencing for particle diffusion and nothing else. The physical interpretation of what's going on here is that the particles are pulled equally in both the left and right directions, and thus they stay where they are.

There are a number of ways you can choose to overcome this limitation, but again, this kind of gets into more advanced continuum dynamics stuff (what we did on HH with particle systems was super brief, and just meant to be the barest of introductions).

The simplest thing to do, although it is not necessarily the most performant, is just increase the density of the grid.

- Casey
m
5 posts
Particles (episode 156)
Ok, thanks!

Got it bit nicer by checking which side the particle is from the spawner x,
so if its more to the left, it gets pushed that way more than right (when both sides have same density)

Andrew Bromage
183 posts / 1 project
Research engineer, resident maths nerd (Erdős number 3).
Particles (episode 156)
One thing you might want to try is to use a density gradient estimate at the location of the particle, rather than just at the cel in which the particle lives.

To understand what's going on in your code, consider this code snippet:

1
2
Dispersion += Dc*(CelCenter->Density - CelLeft->Density)*V3(-1.0f, 0.0f, 0.0f);
Dispersion += Dc*(CelCenter->Density - CelRight->Density)*V3(1.0f, 0.0f, 0.0f);


This is the same as:

1
2
3
4
Dispersion += Dc*CelCenter->Density*V3(-1.0f, 0.0f, 0.0f)
Dispersion -= Dc*CelLeft->Density*V3(-1.0f, 0.0f, 0.0f);
Dispersion += Dc*CelCenter->Density*V3(1.0f, 0.0f, 0.0f);
Dispersion -= Dc* CelRight->Density)*V3(1.0f, 0.0f, 0.0f);


Two of the terms cancel to give:

1
Dispersion += Dc*(CelLeft->Density - CelRight->Density)*V3(1.0f, 0.0f, 0.0f);


A similar cancellation happens in the y direction. The upshot of this is that the density at CelCenter is never actually used. Only four density samples are being used, not five, and the one that's ignored is the one that's closest to the particle!

I can't remember how HMH did this, and don't have time to look it up right now, but suppose we record densities this way:

1
2
3
4
5
for (unsigned i = 0; i < NumParticles; ++i) {
    int X = (int)Particles[i].x;
    int Y = (int)Particles[i].y;
    ++&GameState->ParticleCels[Y][X];
}


(I know there's a scale and offset applied to the x and y coordinates; I'm ignoring that for simplicity.)

The cel at integer coordinates (X,Y) records all particles whose x coordinate is in the range [X,X+1) and y coordinate is in the range [Y,Y+1). So you can think of the cel as a square centred at (X+0.5,Y+0.5). In a sense, this point is where the density is defined.

So in the same way that we did texture mapping, you can calculate the density gradient at a point using bilinear interpolation on the four surrounding samples:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
// WARNING: Untested code follows!
int X = (int)(Particle->x - 0.5f);
int Y = (int)(Particle->y - 0.5f);
float dx = Particle->x - 0.5f - X;
float dy = Particle->y - 0.5f - Y;
particle_cel *CelLeftDown = &GameState->ParticleCels[Y][X];
particle_cel *CelRightDown = &GameState->ParticleCels[Y][X+1];
particle_cel *CelLeftUp = &GameState->ParticleCels[Y+1][X];
particle_cel *CelRightUp = &GameState->ParticleCels[Y+1][X+1];

float dDdx0 = CellRightDown->Density * dx + CellLeftDown->Density * (1.0f - dx); 
float dDdx1 = CellRightUp->Density * dx + CellLeftUp->Density * (1.0f - dx); 
float dDdx = dDdx0 * (1.0f - dy) + dDdx1 * dy;

float dDdy0 = CellLeftUp->Density * dy + CellLeftDown->Density * (1.0f - dy); 
float dDdy1 = CellRightUp->Density * dy + CellRightDown->Density * (1.0f - dy); 
float dDdy = dDdy0 * (1.0f - dx) + dDdy1 * dx;

v3 Dispersion = Dc * (dDdx * v3(1,0,0) + dDdy * v3(0,1,0);


So you're using the same number of density samples (four), but you're actually using the four that are closest to the particle this time. This should avoid numeric smoothing.

If you're curious and want to get into the vector calculus a bit more, I recommend a tutorial on the MAC grid method. This one looks pretty good.
m
5 posts
Particles (episode 156)
Edited by m on
Ok, it does change a bit, but its getting pushing more to the right at "dDdx * v3(1,0,0)", didnt had the time to check yet why. (and I do suck at math)


I modified these, if sampling should be done on each corner cell from the center?
1
2
3
4
particle_cel *CelLeftDown = &GameState->ParticleCels[Y-1][X-1];
particle_cel *CelRightDown = &GameState->ParticleCels[Y-1][X+1];
particle_cel *CelLeftUp = &GameState->ParticleCels[Y+1][X-1];
particle_cel *CelRightUp = &GameState->ParticleCels[Y+1][X+1];


So the idea would then basically be, taking average direction from those 4 cells and use that as pushing force - or, getting direction towards lowest density from the 4 samples?


but will keep testing :)

Next trying to add shared grid array, so that multiple particle systems would collide each other.. (in this image they dont yet)

Andrew Bromage
183 posts / 1 project
Research engineer, resident maths nerd (Erdős number 3).
Particles (episode 156)
mgear
Ok, it does change a bit, but its getting pushing more to the right at "dDdx * v3(1,0,0)", didnt had the time to check yet why. (and I do suck at math)

As noted, it's untested code. There's likely to be a bug in it somewhere.

mgear
I modified these, if sampling should be done on each corner cell from the center?
1
2
3
4
particle_cel *CelLeftDown = &GameState->ParticleCels[Y-1][X-1];
particle_cel *CelRightDown = &GameState->ParticleCels[Y-1][X+1];
particle_cel *CelLeftUp = &GameState->ParticleCels[Y+1][X-1];
particle_cel *CelRightUp = &GameState->ParticleCels[Y+1][X+1];


The thing to note here is that you're not consulting cel [Y][X], which is the one closest to the particle.