Sgt. Conker We are "absolutely fine"

Article : Verlet Integration Particles

by Gorion

This article will show you what VIP's (Verlet Integration Particles) are and how to make them. If you look it up on wikipedia you can see that the math behind the concept is quite complex. While it's not in the scope of this article to explain the math, I will give you a good website which, in my opinion, explains it really well.

Some basic explanation first. The classical implementation of movement is:
Position = OldPosition + Speed or Position += Speed * Direction
Speed += Acceleration

The same thing but verlet integrated:
Position += Position - (OldPosition + Force)

This means you can influence the speed with the position and the old position instead of changing the actual speed and acceleration. The advantages are that if you change 1 particle it can effect another particle just by colliding with it, no need to set the speed and acceleration after the collision. This may sound a bit vague but you will see the result soon . In this article I'll show you bits and pieces of code, you will have to glue it together, which should not be too hard. Also this article will explain everything in 2d, but you must understand that there is no difference between 2d and 3d. XNA makes the math really transparent so this is just as easily usable in 3d as in 2d.

Code for Particle.cs

/*
* By Niels Uiterwijk. Particle which can be used in a verlet particle system
*/

using System;
using System.Collections.Generic;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
namespace VerletDemo.Verlet
{
    class Particle
    {
        private Vector2 position;
        private Vector2 oldPosition;
        private Vector2 force;
        #region Properties
        public Vector2 Position
        {
            get { return position; }
            set { position = value; }
        }
        public Vector2 OldPosition
        {
            get { return oldPosition; }
            set { oldPosition = value; }
        }

        public Vector2 Force
        {
            get { return force; }
            set { force = value; }
        }

        public float Y
        {
            get { return position.Y; }
            set { position.Y = value; }
        }

        public float X
        {
            get { return position.X; }
            set { position.X = value; }
        }
        #endregion

        public Particle(Vector2 pos, Vector2 oldPos, Vector2 force)
        {
            this.position = pos;
            this.oldPosition = oldPos;
            this.force = force;
        }

        public Particle(Vector2 pos, Vector2 force)
        {
            this.position = pos;
            this.oldPosition = pos;
            this.force = force;
        }
    }
}

This is the particle class, it holds the information you need later on (Position, OldPosition and Force). As you can see, I've choosen to not have the particle update itself. It doesn't really matter but I prefer the particle to be more of an object that cannot move itself. This is more realistic as an object in the real world doesn't move itself but an outside force does.

Now on to using the this particle, the following pieces of code will give you a headstart.

..
List<Particle> particles = new List<Particle>();
Vector2 gravity = new Vector2(0, -9.8f);
Vector2 damping = new Vector2(0.05f);
float friction = 0.1f;
float maxY;
float maxX;
float minY = 5.0f;
float minX = 5.0f;
..

public Game1()
{
    ...
    maxY = graphics.PreferredBackBufferHeight - 5;
    maxX = graphics.PreferredBackBufferWidth - 5;
    ...
}

protected override void Update(GameTime gameTime)
{
    if (mouse.RightClick)
    {
        //Create a new particle at the position of the mouse pointer.
        Particle tmpParticle = new Particle(mousePosition, gravity);
        particles.Add(tmpParticle);
    }

    float secs = (float)gameTime.ElapsedGameTime.TotalSeconds;
    int numParticles = particles.Count();

    Vector2 tmpPos;
    for (int i = numParticles-1; i >= 0; i--)
    {
        Particle p = particles[i];

        if (input.IsMouseButtonDown(MouseButtons.LeftButton))
        {
            //Drag particle code
        }

        //Here comes the formula!
        tmpPos = p.Position;
        p.Position += p.Position - (p.OldPosition + (p.Force * damping));
        p.OldPosition = tmpPos;

        //Do some bounds checking..
        handleBounds(p);
    }

    //Constraints code
    base.Update(gameTime);
}

private void handleBounds(Particle p)
{
    //Making sure that the particle does not go out of bounds
    float overY = 0;
    if (p.Y > maxY)
    overY = maxY - p.Y;
    if (p.X > maxX)
    p.X = maxX;
    if (p.X < minX)
    p.X = minX;
    if (p.Y < minY)
    p.Y = minY;

    if (overY != 0)
    {
        //If the particle collided with the bottom we move it up and slow it down
        p.Y += overY;
        float diff = p.X - p.OldPosition.X;
        if (diff != 0)
            p.X -= (diff * friction);
    }
}

private void addParticleStick(Vector2 pos)
{
    //addParticleStick code
}

private void addParticleAnchor(Vector2 pos)
{
    //addParticleAnchor code
}

private float distance(Vector2 v1, Vector2 v2)
{
    Vector2 tmp = v1 - v2;
    return tmp.Length();
}

protected override void Draw(GameTime gameTime)
{
    GraphicsDevice.Clear(Color.WhiteSmoke);
    //Draw you particles..
}

I've showed the important section's. As you can see every tick the particles get updated. If you've implemented it correctly, and if you are using the same variables as me, you should see a particle, after creating it, falling to the ground and then stop near the bottom.

Constraints

So now that we have our particles we can add constraints to them. These constraints limit the movement of particles. The simplest constraint which excist, is an anchor constraint. This constraint keeps the particle in place, but first I'll give you the base constraint class.

Code for constraint:

/*
 * By Niels Uiterwijk. An abstract class used as a base class for constraints.
 */
using Microsoft.Xna.Framework.Graphics;
namespace VerletDemo.Verlet
{
    abstract class Constraint
    {
        public abstract bool Satisfy();
        public abstract void Draw(SpriteBatch sp);
        public abstract bool Uses(Particle p);
    }
}

The function Satisify() will be called each tick to satisfy the constraints, if it returns false the system needs to remove the constraint because it did not get satisfied and if not removed might cause the whole system become unstable, this is because all particles influence each other.

class AnchorConstraint : Constraint
{
    private Particle p = null;
    private Vector2 position = Vector2.Zero;
    public AnchorConstraint(Particle p, Vector2 pos)
    {
        this.p = p;
        this.position = pos;
    }

    public override bool Satisfy()
    {
        p.Position = position;
        p.OldPosition = position;
        return true;
    }

    public override void Draw(SpriteBatch sp)
    {

    }

    public override bool Uses(Particle p)
    {
        return (this.p == p);
    }
}

This AnchorConstraint sets the position and the old position of the particle to the position of the anchor. For this simple constraint we can simply return true.

Here's some updated code for Game1:

..
List<Constraint> constraints = new List<Constraint>();
..

protected override void Update(GameTime gameTime)
{
    ..
    int numConstraints = constraints.Count();
    for (int i = numConstraints-1; i >= 0; i--)
    //We run backwards so we can remove stuff.
    {
        Constraint c = constraints[i];
        if (c.Satisfy())
            continue;
        constraints.Remove(c);
    }
}

private void addParticleAnchor(Vector2 pos)
{
    Particle p = new Particle(pos, gravity);
    particles.Add(p);
    AnchorConstraint ac = new AnchorConstraint(p, pos);
    constraints.Add(ac);
}

If you place a particle with the AnchorConstraint you will notice that it will not move, as expected .

With this simple sample I will explain how we can recreate a world of goo like experience. For the constraint we are going to use, we need to keep 2 particles at a certain distance from each other.

We will have to define the 2 particle's we need to keep at bay, the length between the 2 particles and we also will define the stiffness of the constraint.

To do the actual "keeping at bay" we will need the difference between the 2 particles. Then we adjust the position of the particles together with the differences multiplied with the stiffness we gave the constraint.

Resulting code:

Vector2 delta = p2.Position - p1.Position;
float deltaLength = delta.Length();
float difference = ((deltaLength - length) / deltaLength);
p1.Position += delta * (0.5f * stiffness * difference);
p2.Position -= delta * (0.5f * stiffness * difference);

As this constraint needs 2 particles to work, we need code that will find the 2nd particle, or even both particles to work with.

To do this we need to iterate over all particles and save the 2 particles which are the closest to the position of the newly generated particle. If we did not find 2 particles we are just going to create a new one and don't add a constraint. If we have found at least 1 particle we will add the constraint between the closest particle and the new particle.

If we did find 2 particles and the distance between them is small enough we can add the constraint between these 2 particles. So we do not create a new particle but just add the constraint between these particles. If the distance between them is to big we create a new particle and add a constraint between particle 1, particle new and particle 2, particle new.

Some example code:

Particle p1 = null;
Particle p2 = null;

//Assign 2 closest particles to p1 and p2.
..

if (p1 == null || p2 == null)
{
    tmpParticle = new Particle(pos, gravity);
    particles.Add(tmpParticle);
    if (p1 != null && p2 == null)
    {
        if (distance(p1.Position, pos) < maxDistance)
        {
            StickConstraint sc = new StickConstraint(p1, tmpParticle, minLengthStickConstraint, 1.0f);
            tmpConstraints.Add(sc);
        }
    }
    return;
}

float distanceP1 = distance(p1.Position, pos);
float distanceP2 = distance(p2.Position, pos);

//Need to make sure that the distance is not ridiculous, else the system might go instable.
if (distanceP1 > maxDistance && distanceP2 > maxDistance)
{
    //We add the particle, but no constraint!
    tmpParticle = new Particle(pos, gravity);
    particle.Add(tmpParticle);
    return;
}

//Finally we founded our closest 2 particles
float length = minLengthStickConstraint;
float stiffness = minStiffnessStickConstraint;
float maxLength = length * 1.2f;
float distanceP1P2 = distanceP1 + distanceP2;

if ((p1 != null) && (p2 != null) && distanceP1P2 < maxLength)
{
    //We can add a stick constraint between the 2 allready excisting particles
    StickConstraint sc = new StickConstraint(p1, p2, length, stiffness);
    tmpConstraints.Add(sc);
    return;
}

//We have to create a new particle
tmpParticle = new Particle(pos, gravity);
particles.Add(tmpParticle);
if (p1 != null && distanceP1 < maxDistance)
{
    StickConstraint sc = new StickConstraint(p1, tmpParticle, length, stiffness);
    tmpConstraints.Add(sc);
}

if (p2 != null && distanceP2 < maxDistance)
{
    StickConstraint sc = new StickConstraint(p2, tmpParticle, length, stiffness);
    tmpConstraints.Add(sc);
}

Now we have come to the end of this article, I hope you learned something from reading this. This is only a small introduction into the world of verlet integration, some topics we have not touched is cloth simulation, fluid simulation etc. All those awesome looking things are based on this kind of simulation. Download the sample project and have a look. The sample project uses some helper classes (for input and drawing), I won't explain those as these are not part of this article. You can always email me at nielsuiterwijk @ gmail.com

About Sgt. Conker

The Sergeant!