« Back to Processing

Tutorial #6: Colliders

| No Comments | Published on April 29, 2008
The content that follows was originally published on the Don Havey website at http://donhavey.com/blog/tutorials/tutorial-6-colliders/

Colliders previewHere’s another brief tutorial. This one relates to object collisions and velocity transfers. Basically, we’re making simulated billiard balls: objects that bounce off each other and the sides of the applet. Not too much else to introduce, so I’ll just get started…

What it looks like

Here are the files: Collider classes

And here’s the final result: I’m a super collider

Click on the applet to rejuvenate each Collider’s y-velocity and prepare for another round of bouncy goodness. If you find the motion blur distracting, you can always look at this blur-free example.

What you’ll learn

Some of the math you’ll have to decipher yourself, but in general, I’ll touch on each of the following:

  • Preventing circular shapes from overlapping.
  • Constraining points within an area.
  • Transferring velocities upon object collision.
  • And I’ll show you how to do that cheesy motion blur trick… if you don’t already know.

Ready?

Let’s get started…

Giving credit where credit’s due

I should first say that much of the code here is based on a few old Flash experiments by Keith Peters of Bit-101 fame. He’s a great Actionscripter, and his old lab and Flash files are a great way to introduce yourself to some advanced programming concepts. Like many good programmers, he always finds a way to break down conceptually complex challenges into very simple code.

That said, although I reused a bunch of his code here, it is not ideal for large numbers of collisions. The optimal solution would use only vectors and their components to figure out the momentum transfer between colliding objects. This solution uses some trigonometry, which is a shortcut, but will slow an applet down when given a large number of objects to process.

The Collider class

This is a one-class tutorial. Our Collider class extends our existing Point class, adding two new methods: step(), which is simply used to increment our x and y values, and bump(), which will control our collisions and reactions. Let’s look at the step() method first:

void step(){
  //constrain the x value to within the visible area
  //reverse direction if we hit a wall
  if(x>width/2-r||x<-width/2+r){
    vx *= -1*bounce;
    x = constrain(x,-width/2+r,width/2-r);
  }
  //constrain the y value to within the visible area
  //reverse direction if we hit a wall
  if(y>height/2-r||y<-height/2+r){
    vy *= -1*bounce;
    y = constrain(y,-height/2+r,height/2-r);
  }
  //acceleration due to gravity
  vy += gravity;
  //deceleration due to friction
  vx *= friction;
  vy *= friction;
  //increment the xy position
  x += vx;
  y += vy;
}

As you can see, to contain our Colliders within the visible bounds of our applet, we’re bouncing them off the walls by negating their velocities upon impact. Our “gravity”, “friction”, and “bounce” variables located in the same .pde file control how quickly an object falls and how much energy it loses each frame and each collision.

And now for the tricky part. The collision between two Colliders:

void bump(Collider $c){
  float d = dist($c.x,$c.y,x,y); //distance between the two
  float rr = $c.r+r; //the combined radii (e.g. the minimum distance needed)
  //if we're touching...
  if(d<rr&&d!=0){
    //this part taken mostly from bit-101 (www.bit-101.com)
    float a = atan2($c.y-y,$c.x-x); //the angle between object centers
    //store our trig variables for optimization
    float cosa = cos(a);
    float sina = sin(a);
    //get our direction components
    //you get to figure this part out
    float vx1p = cosa*vx+sina*vy;
    float vy1p = cosa*vy-sina*vx;
    float vx2p = cosa*$c.vx+sina*$c.vy;
    float vy2p = cosa*$c.vy-sina*$c.vx;
    float p = vx1p*m+vx2p*$c.m;
    float v = vx1p-vx2p;
    vx1p = (p-$c.m*v)/(m+$c.m);
    vx2p = v+vx1p;
    vx = cosa*vx1p-sina*vy1p;
    vy = cosa*vy1p+sina*vx1p;
    $c.vx = cosa*vx2p-sina*vy2p;
    $c.vy = cosa*vy2p+sina*vx2p;
    float diff = bounce*((r+$c.r)-d)/2;
    float cosd = cosa*diff;
    float sind = sina*diff;
    //increment our x and y values
    x -= cosd;
    y -= sind;
    $c.x += cosd;
    $c.y += sind;
  }
}

Now the reason the above code is so complex is because we’re not simply swapping momentums. We’re redistributing momentums, so to speak, along the axis of collision and according to the mass of each Collider (which in our applet is determined by its radius).

Like I said, I’m going to leave it up to you to interpret that big unlabeled block of code… but the good news is: that’s basically all that makes up the Collider class. We’re just about done.

The cheesy motion blur trick

There are so many Processing applets that use this type of thing that it’s become rather stale. Didn’t stop me from using it again, though. Achieving the motion blur is super simple. Initialize your applet’s background color in your setup() function:

rectMode(CORNERS);
background(50);

Then add a line like this to your draw() function:
//don't add a background()!
//create a very transparent rectangle instead
fill(50,5);
noStroke();
rect(0,0,width,height);

That’s it. Here’s an example with no blur for comparison. I thought it looked a little boring.

Caveats

You’ve probably noticed a few things that need improving here:

  • I mentioned the optimization problem. Use more vector operations, minimize the trig.
  • One major failing of all applets of this type is collision skipping. Say you have a ball moving at 50px/frame that is 25px away from a stationary ball and moving directly towards it. In reality, of course, these balls collide. In a frame-based application, they don’t! The next frame, the moving ball’s position is 25px on the other side of the stationary one. The computer never registers a collision. Big problem for accurate simulations, not so much for graphical stuff. I’m sure you can think of a solution if you need to. I’d use the Segment class’ get_distance_to() method for each object in question, where a Segment is defined between the current and projected positions of an object.
  • If you just want to ensure that objects don’t overlap, you can use a much simpler approach. This solution is primarily for velocity transfers.
  • Because we’re always applying a gravity variable, our Colliders will never come to rest. That’s why you get that Brownian motion-like jittering. Without a gravity variable, the objects will eventually stop bouncing around and just sit there. Here’s a sample with no gravity.
  • Similarly, with a large number of objects (say, 100 Colliders), you’ll get some serious overlapping towards the bottom of the pile. I’m afraid I can’t think of a way around this… although it’s probably been done. Maybe using inverse kinematics or Verlet integration, but that would take the CPU intensity of the thing to a whole new level.
  • We’re limited here to circular objects. Irregular objects would require a totally different approach.

The end

Good luck with this one. A little unsatisfying… but thus is the nature of physics simulations on a non-quantum computer.

Here are the classes again: Collider classes

And here’s the final result: I’m a super collider

Next up is Voronoi diagrams…