Posted by: eygneph | 2010/10/09

Some ideas about Verlet based physics

First of all, integration is not just a word about in your college mathematics courses. It is used everyday in game development. Like your Update() loop, you see this everywhere:


velocity += deltaTime * acceleration;
position += deltaTime * velocity;

, this is which we called Euler integration.

Verlet integration is not a lot more difficult than (mostly used) Euler integration, but has two advantages:

  1. More numerical stability,
  2. Easy for position constraints.

If you don’t catch the idea what numerical stability is, here’s a simple graph illustrating the instability caused by Euler integration:

In the above graph, you can see that the “step” value is critical to Euler methods, as bigger step would cause the integration oscillates, and even bigger steps will “explode” the whole simulation towards the exact solution.

For more information on the stability issue, you can refer to these links: http://en.wikipedia.org/wiki/Euler_method and http://en.wikipedia.org/wiki/Stiff_equation. Note numerical stability is a topic which can cover an entire book, and I’d like to avoid digging into it here.

The basic form of Verlet integration is as follows:

x’ = 2x - x* + a*dt*dt;
x* = x;

Here x’ is the position of simulated entity in time t + dt, x* is the position in time t – dt, and x is th e position in time t. As you can see, the Verlet integration is still very simple, but it introduced an previous position x* to make Verlet integration happen. At the same time, it removes the dependency on velocity –  and this, makes life a lot easier.

Without velocity, you won’t integrate velocity explicitly, thus removes the instability of velocity integration. Also for soft body simulation such as cloth, a position constraint is very handy in Verlet integration(actually, nearly all constraints in Vertlet based method, are position constraints). A solid position constraint will prevent the cloth from behaving too elastic or unstable, which is quite hard to get right if you don’t use position constraints. Since position constraints is at the heart of Verlet based physics, it is also called particle based method or position based method.

I’m not going to show you how to do cloth physics in this article(in case you are interested, you can refer to the reference paper). Instead, I’ll talk a little about how I plan to make Verlet based physics to achieve unified dynamic physics in game.

Modern games are using physics engine extensively since Half-life 2. However, most of them are focused on rigid body physics, that is, the simulated entities are undestructible, undeformable rigid bodies. No matter how much forces push the box, or throw an grenade at it, the box won’t crash but just bounces away, which is far from how it should behave in reality. People does a lot to make things destructible to make a more emerging environment. Unreal Development Kit has an feature to pre-tessellate the mesh, and then explode them when they’re hit by weapons at runtime. CryEngine also has prescripted physics, which is actually prerecorded animation done at the design time. But none of those can achieve an truly dynamic environment, which is destructible at runtime. The only game that has true destructible environment is Star Wars: The Force Unleashed, which uses an finite element technology from Digital Molecular Matter. Their technology is based on a series of paper and I’m listing them in the reference section.

My idea is similar with finite element methods, but might be simpler since we’re just focusing on 2D. In my perspective, 2D has a lot advantages in physics simulation against 3D, especially in predictable behavior and processing power on mobile platforms.

Basically matter are made of particles(or atoms), regardless if it’s rigid, soft, or fluid. If the processing power permits, it’s quite okay to simulate rigid body or soft body by using massive particles. Since Verlet based method gives us stability and convenience to cast position constraints, we should be able to create both rigid body and soft body. Their only difference is the position constraints associated with them. The rigid body has harder constraints, and the soft body has softer constraints. A typical box can be represented as following structure:

With those constraints in mind, destructible object can be implemented by breaking some key constraints between particles. So it should be easy to simulate rigid boxes, soft blobs and even water/oil. All those objects are composed by actually same particles and constraints, so hey can be simulated within an unified solver.

No one is perfect. So far the system is still lacking of traditional constraints in rigid body systems, like revolute joint or prismatic joint. I can’t find an easy solution to include those constraints into Verlet based(or particle based) systems. So if someone needs those neat features in rigid body engines, the easiest way might be an hybrid system holds both Verlet based and impulse based rigid body systems. Based on the projection method described in “Advanced Character Physics”(see reference), I think the hybrid system is still doable.

Reference:

Advanced Character Physics, Thomas Jakobsen, http://www.gamasutra.com/resource_guide/20030121/jacobson_pfv.htm
Position based Dynamics, M. Müller
http://www.matthiasmueller.info/publications/posBasedDyn.pdf
Real-time Deformation and Fracture in Game Environment, Eric G Parker, James O’Brien
http://graphics.cs.berkeley.edu/papers/Parker-RTD-2009-08/index.html

Advertisements

Responses

  1. Hi! Something that puzzles me a bit about Verlet is how to deal with elastic collisions. With Euler or Runge Kutta we would solve the collision by

    1) push the collider out of the collidee, back in a place where they touch but don’t overlap;
    2) modify the velocities of the two bodies according to their mass (cf elastic collision wikipedia for formula).

    That way the bodies don’t overlap anymore, and they even bounce away from each other.

    Now, how do we take care of the point 2 with Verlet ? First we correct the position. But now we need to correct the velocity. Does that mean that we create a new ‘fake’ position at t-dt corresponding to that desired velocity ?


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: