Hard Constraints, Easy Solutions

Sep. 01, 2010
comments

In the previous post about integration methods, I took a look at gravity integration. Gravity is a good example of a soft constraint. It does not impose hard limits to movement of bodies. But what if we need hard constraints, for instance like steel beams? The following post explains how to implement hard constraints.

Contents

Sneak Peak

The conclusion of the explanations of this post is a stable hard constraint system that uses Verlet integration and constraint resolution. You can hover over the illustrations to run their simulations, press reset for a reset and click into the canvas to remove points.

Download

You can download the source of the first, second and third version of this simulation. The third one is the stable hard constraints. You will also also need the vector class

Point

In order to perform the tests to figure out how to do hard constraints, we need a data model that fits the purpose. The model consists of Points and Constraints.

The Point class has a position, velocity and acceleration.

var Point = function(x, y){
    this.position = new Vector(x, y);
    this.velocity = new Vector(0, 0);
    this.acceleration = new Vector(0, 0);
    points.push(this);
}

Two notable methods which are "accelerate" that simply adds a vector of acceleration to the existing acceleration, and "simulate" which does the typical Euler integration.

accelerate: function(vector){
    this.acceleration.iadd(vector);
},

simulate: function(delta){
    this.velocity.iadd(this.acceleration.mul(delta));
    this.acceleration.zero();
    this.position.iadd(this.velocity.mul(delta));
},

There is a second class called FixedPoint. Both accelerate and simulate don't do anything to that class, since it is assumed to be fixed.

Force Constraint

A hard constraint can be imagined as a really stiff spring. It gives a little, but not much. We could model such a constraint as a force after Hooke's law and add the acceleration to the point.

A constraint has two endpoints and a target length it aims to restore.

var Constraint = function(point1, point2){
    this.point1 = point1;
    this.point2 = point2;
    this.target = point1.position.distance(point2.position);
    constraints.push(this);
}

The resolve method of a constraint tries to apply the forces after Hooke's law

resolve: function(){
    var pos1 = this.point1.position;
    var pos2 = this.point2.position;
    var force = this.target - pos1.distance(pos2);

    var direction = pos1.sub(pos2).normalized();
    var acceleration = direction.mul(force);

    this.point1.accelerate(acceleration);
    acceleration.imul(-1);
    this.point2.accelerate(acceleration);
}

Simulation step

At each step in the simulation constraints are resolved, gravity is applied and the points are simulated. Each interval, 15 steps are executed, this should increase the accuracy of the integration.

var steps = 15;
var delta = 1/steps;

for(var j=0; j<steps; j++){
    for(var i=0, il=constraints.length; i<il; i++){
        constraints[i].resolve();
    }

    for(var i=0, il=points.length; i<il; i++){
        var point = points[i];
        point.accelerate(gravity);
        point.simulate(delta);
    }
}

Running this simulation as it is with both an Euler integration step and forces for constraints yields very bad results.

Improving Constraints

What's needed is a different way to apply constraints. Each constraint could simply move its attached points to a position that would satisfy the target requirement.

We first need a way to make corrections to Points without affecting FixedPoints. For this we introduce the method "correct" on Points. This method does nothing to FixedPoints.

correct: function(vector){
    this.position.iadd(vector);
},

Then we need a better resolution method for the Constraint. The idea is to move each point halfway in the direction as to satisfy the constraint.

resolve: function(){
    var pos1 = this.point1.position;
    var pos2 = this.point2.position;
    var direction = pos2.sub(pos1);
    var length = direction.length();
    var factor = (length-this.target)/length;
    var correction = direction.mul(factor);

    this.point1.correct(correction);
    correction.imul(-1);
    this.point2.correct(correction);
}

This does not work yet. Now the velocities are out of sync with the positions.

All roads lead to Verlet

What is required is a method of integration that can automatically track velocities from previous positions. In order to do this, we get rid of velocity in points.

var Point = function(x, y){
    this.position = new Vector(x, y);
    this.previous = new Vector(x, y);
    this.acceleration = new Vector(0, 0);
    points.push(this);
}

But we have to change the integration method for the points. If you want to know velocity you can subtract the previous position from the current position. Adding this and acceleration to the position, and then flipping the previous position and the current one we get this simulate method.

simulate: function(delta){
    this.acceleration.imul(delta*delta);

    var position = this.position
        .mul(2)
        .sub(this.previous)
        .add(this.acceleration);

    this.previous = this.position;
    this.position = position;
    this.acceleration.zero();
},

Finally the result is very satisfactory.

I hope this will help you write better hard constraint systems in the future. Stay tuned for my next post (it's will have something to do with physics).