Email Updates RSS Subscribe
Line

This blog is created and maintained by the technical team at Hook in an effort to preserve and share the insights and experience gained during the research and testing phases of our development process. Often, much of this information is lost or hidden once a project is completed. These articles aim to revisit, expand and/or review the concepts that seem worth exploring further. The site also serves as a platform for releasing tools developed internally to help streamline ad development.

Launch
Line

Hook is a digital production company that develops interactive content for industry leading agencies and their brands. For more information visit www.byhook.com.

Line

Fuzzy Physics – 3.1: Rigid Body Dynamics, pt 1

Line
Posted on February 11th, 2010 by Brad
Line

While position-based dynamics can quickly create cool IK and rope effects due to its particle/constraint structure, it is often mentioned solely in the context of cloth and soft-body simulation while rigid body dynamics are only hinted at, and for good reason.  Most behaviors of position-based systems are emergent and make much of the work feel more like alchemy than robotics, melting together a combination of vertices and constraints in hopes that you’ll get something solid and well-behaved.  But those complex behaviors that materialize from such simple means are what makes the position-based approach so great.

As opposed to particle-based dynamics, rigid body dynamics are differentiated by an additional degree of freedom or 3, along with big scary words like inertia tensor, center of mass, angular momentum, moment of inertia, torque, quaternions, etc.  While these concepts are valuable to be aware of, it sure does complicate simulated and interactive movement, so I’m after something I can handle early in the morning without first mainlining a case of Red Bull.

Spending hours sifting through the search engine desert with a hair pick doesn’t turn up much in terms of specific implementation of rigid-bodies with position-based dynamics, but, there are a few decent starting points that can be found, with varying complexity:

  • The distance-constraint formed rigid-body as described in Jakobsen’s ‘Advanced Character Physics’, for example: as used in Luis Ferndando Silva’s Flave Engine.  This is similarly constructed to spring-mass models used in non-position based soft-body dynamics.
  • The stick model used by Metanet and Jamie Cheng (the PPCD diagrams can still be accessed through trickery, ask Jake)
  • The shape-matching technique described by Matthias Mullet et. al (Who also wrote the spiritual heir to Jakobsen’s paper: Position-Based Dynamics)

Each has a certain driving force behind its use, and along with that, certain strengths and weaknesses.  One of the main things I’m looking for is the ability to arbitrarily add particle ‘effectors’ to the body, moving it by imparting both translational and rotational (torque) forces.  As such, these particles can represent attachments, contacts, or mass distributions.  This is where things start getting esoteric and nebulous, as the point-masses that make up a body can end up moving in completely independent ways as dictated by other connected bodies or forces.  Also, something closer to well-behaved soft-bodies would be sweet too.
I plan on running some experimentation with each to get a feel for the nuances and sticking points, or possibly develop a different approach entirely.  This post will focus on Jakobsen’s loose box construction (as opposed to the basis-vector coordinate/particle system, or the triangle/tetrahedron approach), specifically on applying arbitrary forces to it.

The Spring-Mass Model

The real strength of the spring-mass rigid body model as described by Jakobsen is the absolute simplicity with which you can create a simple object that can fall, bounce and settle into place fairly realistically.  Besides friction and standing-contacts, this can be implemented completely with the standard Verlet integration and constraint relaxation as discussed previously.  The particle dynamics are then magically transformed into rigid body dynamics.

While moving a vertex and thus the body is as simple as moving a particle, applying a torque to somewhere other than a vertex is a little tricky.  To this end, I started with a more simplified case based on Jakobsen’s stick collision correction.  The objective here was to create an ‘edge’ rigid body, which is pretty much the most basic rigid body type you can get, defined by two-end points (a single point can’t have rotational movement applied so its not a rigid body, deal with it).

Get Adobe Flash player

The above example illustrates the point-force that will be used to push the edge. For simplicity’s sake I am using mouse movement, but that could very well be replaced with any sort of force you can boil down to the movement of a particle. Displayed are the crucial pieces of information we need initially: the point on the edge where the collision happened and the movement of the point-force as created by the collision. What we want to do is move the collision point on the edge towards the particle that flies off, and translate that movement to the edge’s end-points relative to where along the edge we collided. This is done by using the equations for stick correction as described in ‘Advanced Character Physics’.

The first step is to define point p along the edge. This is done using the equation:

p = c_1  x_1 + c_2 x_2

where:

x1 & x2 are the end-points of our edge, and c1 & c2 are constants (totalling 1) describing where along the edge the points rests.  For example, if p is 3/4 the way between x_1 and x_2, c_2 = 0.75 while c_1 = (1 - 0.75).  Though a little abstract, what this affords us is less vector or matrix operations doing coordinate conversions, and the location of p will adjust as the edge scales.  Likewise, because of those constants, we can use it to define points p, x1 and x2 after correction:

p prime = c_1  {x_1}prime + c_2 {x_2}prime

where prime indicates the state after correction

To jump off a bit from Jakobsen, I applied the basic distance constraint math to p & q(our point-force position) to find p' as is illustrated here:

Get Adobe Flash player

As you can see {p}prime is about midway between  p and the applied force particle.
This is where Jakobsen gets a little crazy with the linear algebra, and ends up with the following formulas for x1′ and x2′

{x_1}prime = x_1 + c_1 lambda Delta

{x_2}prime = x_2 + c_2 lambda Delta

After digging through his derivation for lambda for a little too long, it turns out to be 1 over the summed squares of the line coefficients:

1 / (c_1^2 + c_2^2)

while Delta is just the displacement vector between p' & p.  As you can see, the end-points are moved relative to how close to p they are, this is what gives us that tasty torque rather than just moving the edge along the direction of the point-force’s movement.

You may notice in the above illustration that while p prime keeps its relative distances intact, the edge stretches (especially in more extreme angles and velocities).  This gets corrected in time by the distance constraint binding the edge-points, so adding additional logic to correct that wasn’t really of concern.

Get Adobe Flash player

Here I’ve just taken the above code and worked it within my update, with 1 iteration for constraints and it feels pretty tangible.  To play around with the implicit moment-of-inertia created by this technique I’ve modified the original formulas for x1' and x2' to factor in the mass of the system:

{x_1}prime = x_1 + c_1 lambda Delta {w_1/(w_1 + w_2 + w_Q)}

where w is a weight variable (inverse mass of the point-mass)

To see how this works within the context of a rigid body, I created Jakobsen’s simple box body with an additional cross constraint (cross constraints not shown).  The edge model above was then applied to the 4 sides of the box.  Through simple distance constraint relaxation, the box maintains its shape, while plausibly being affected by the mouse.

Get Adobe Flash player

Though I kept these examples minimal with some basic mouse-striking to simulate forces, this edge model technique would likely work very well with other methods of applying movement, like attached ropes or springs.  How about a good old fashioned pros and cons list?

Pros:

  • very easy to implement, requires about 3 objects max: point-mass, distance constraint, edge model/constraint to simulate
  • applying a force/torque can be described purely by particle movement, which with the minimal degrees of freedom reduces the amount of math involved

Cons:

  • because the interaction is based on edges, defining points off of those edges is nearly impossible
  • modeling more complex bodies requires massive numbers of constraints to maintain rigidity
  • when particles move at high speed artifacts such as inversion or flipping can happen

Either way, the speed and simplicity with which you can create some simple semi-rigid forms is astounding, and the spring-mass technique for rigid bodies can be a great option for more simple projects where a full-blown rigid body simulator would be overkill.  But as the bodies start becoming more complex, more constraints are required to keep things in place, becoming more like duct-tape than a tool to model behavior.

While the edge model and collision response can definitely be useful in creating ropes and chains (eliminating the inherit gap in rigid joint chains), we are still lacking a truly useful way to define a local coordinate space to apply points to create rigid body effects.  To this, a flattened version of Jakoben’s tetrahedral approach may be just the answer, as we can define vertices and point-forces with barycentric coordinates to simplify coordinate conversion.  But thats a topic for another post…

Line
11 Responses to “Fuzzy Physics – 3.1: Rigid Body Dynamics, pt 1”
  1. brad says:

    @d34n: thanks! more coming, soon

    @dfm: you’re correct, I had accounted for that in a formula just below example 3

  2. dfm says:

    To acount for mass, I believe the edge resolution also requires:

    (upsideDownY) = 1 / (c1 ^ 2 * (w1 / (w1 + w2)) + c2 ^ 2 * (w2 / (w1 + w2)))

  3. d34n 4lex says:

    This is a brilliant article!
    Really informative and well written.

    best,
    d

  4. [...] Ok, I’ll be the first to admit… logging isn’t the most exciting topic out there especially compared to some of the other hotness on this site: Kutout – An application for cutting out images and Fuzzy Physics – 3.1: Rigid Body Dynamics, pt 1 [...]

  5. [...] experiments (a continuation from my previous post on Jakobsen-style position based dynamics: here) , the hooplah around the iPad and Apple getting all ‘The Hills’ on Adobe provided a [...]

  6. raigan says:

    Yeah, using a stick as a basis is analogous to a triangle, it’s just simpler (or at least, it makes a lot more sense for me); actually now that I think about it, it’s just an extension of your single-stick examples above.

    In all cases you have some “embedded” geometry (collision shapes, joint positions) which is defined relative to a dymamic model — the simulated particles — using some sort of “parametric” coordinates (in your above case, a single scalar coordinate describing position between particles; when using a triangle, the coordinates would be a triplet of barycentric weights).

    Constraints are defined relative to this embedded geometry, and you then need to figure out how to satisfy them by altering the dynamic model (i.e moving particles around in order to move the embedded points around). Your examples above are great because they’re easy to understand and in they’re exactly what happens in general regardless of the dynamics model — the only thing that changes is the “embedding” equation/coordinates.

    Our stick basis (well, one of them.. we found that you can get lots of weird/interesting behaviours by using different bases) is very similar to yours above; you have:
    p = c1*x1 + c2*x2

    but instead of thinking about it as blending between two points x1,x2 using weights c1,c2, you could also think about it as starting at x1 and adding some amount a of the vector between points (x2-x1):
    p = x1 + a*(x2 – x1)

    This can describe any point on the line containing x1,x2. To get a full 2D space in which to embed points, the wonderful “perp” operator lets us define an axis perpendicular to the line through x1,x2:
    p = x1 + a*(x2 – x1) + b*Perp(x2 – x1)

    Where Perp(v) = [-v.y, v.x]

    This provides you with a full 2D coordinate system in which to embed constraint geometry, using the coordinates a,b. Of course, you can construct lots of other types of embedding too, such as:
    p = 0.5*(x1+x2) + a*(x2 – x1)/Len(x2 – x1) + b*Perp(x2 – x1)/Len(x2 – x1)

    This basis is a bit more complicated, but it behaves better when the particles are stretched (i.e the original basis scales as the particles are stretched, which makes things a bit bouncy; this more complicated basis keeps constraint geometry centered on the midpoint between particles and doesn’t scale as the distance between particles changes).

    Anyway, I’m interested to see what you come up with because our understanding is very vague and different perspectives would be useful — it’s quite possible that there are better or different ways to apply these basic ideas.

    Raigan
    p.s – sorry for belching this out here, I’m definitely an amateur and I don’t really have a great grasp on vector calculus so there’s a lot of fumbling as I struggle to understand the fundamentals of why this all works :)

  7. brad says:

    Thanks Raigan!

    I’m currently doing some tests with a triangle-based/barycentric rigid-body dynamics model (along with haXe and canvas), it’s looking promising thus far. I’m hoping that will give me some greater insight on the stick approach too.

    I’m looking forward to seeing what you guys do post-GDC, looked like there was amazing stuff on display there!

  8. raigan says:

    Yeah, keep up the great posts!

    I’m especially interested in hearing your experiences with the stick-model. We really want to write something up about our experiments, but we want to have a game finished first :(

  9. Niall says:

    These are great, please keep going.

  10. Brad says:

    @Petermonium: Yeah, that’s definitely one of the downsides of this approach as noted, it has the possibility to cave in and invert under extreme forces. I’m going to try out a couple other methods to get something stable in the future, hopefully before the Large Hotdog Collider is complete

  11. Peter Dee says:

    If you SLAM the box just right, you can get it to deform and spin forever. Hard to reproduce though.


Leave a Reply

*

Line
Line
Pony