And here we go again!
The last physics thread I wrote covered a LOT of ground, and went into a lot of detail about the maths involved.
It was more or less a tutorial.... this one will be more of a blog, and of far less value for 'most' readers.

This thread will document my further adventures in the field of physical simulation. It will contain implementation notes regarding optimizations to various algorithms, as well as covering some more of the stuff that was not covered in the previous physics thread, such as articulated rigid bodies and the various joint constraints that hold them together (requirement of ragdoll physics !!).

Since constraints seem to be the order of the day, I'll begin tomorrow with a recap of constraints in general, Point Constraints,  Hook's Law and the simulating of "springs".. we'll talk about some of the ways we can use springs in our simulations (including some not-so-obvious ones), and importantly, we'll talk about some of the problems with springs, and how they can ruin your entire day. With two constraints under our belt, we'll be ready to look at some more complex constraints.

Posted on 2010-07-23 09:45:03 by Homer
I know that I have always enjoyed reading your posts regarding 3D. I doubt if I could ever create a true 3D engine - a monumental task in and of itself. I've actually tried to examine the source to things like Ogre3D, Crystal Space, and the Quake 2 engine. My brain subsequently melted...
However, your "articles" are definately insightful and help turn on a few lightbulbs in my head regarding its development.
Thank you for sharing  8)
Posted on 2010-07-24 18:44:18 by p1ranha
So what are these things called Constraints, why do we care?

Whenever we wish to place limits on the way a physical entity can move, we are constraining its motion... so we might say that a Constraint is a limit placed apon the motion of a physical entity. In fact, we can easily think of one example of a constraint: collision detection and response !!
What is the purpose of our collision detection/response code?? It is to detect and prevent our bodies from intersecting each other (and the world).
We might say that we are constraining the intersection of our bodies - preventing them from overlapping.

Constraints can limit, or completely remove(!), one or more "Degrees Of Freedom" - this is an important concept which we will soon revisit.

Let's look at our first useful example constraint : Point Constraint
In the following example, we'll see how to "anchor" a Body to the World by a single Point.

We shall define a point P in WorldSpace, and a corresponding point Q on the surface of our Body.
And we shall define our Constraint mathematically as: P == Q

Whenever the Body is moved or rotated, our Constraint will be violated: P != Q
In order to enforce our constraint, we will need to translate the entire Body such that P == Q :)

Now, what if we had two bodies, with P on body A, and Q on body B, can we enforce a Point constraint which joins together two Bodies and keeps them joined no matter what? Yep we can, and we can do it exactly the same way!

With the Point Constraint alone, we can construct rope bridges that move realistically under foot, and we can create our first simple articulations from multiple Bodies. In fact if you think about it, the Point constraint acts a bit like a Ball Joint, allowing any kinds of rotations, but enforcing the translation (position) in order to maintain the constraint.

What if we wanted to maintain a constant distance between two bodies, can we modify our Point Constraint to enforce a Distance? Sure!
We can define a Distance Constraint as: P-D == Q ; where D = Distance :)

Point and Distance Constraints are very "stiff" constraints - there is no "elasticity". Sometimes that's what we want, but sometimes it isn't.
In the next post, we'll learn about elastic constraints aka SPRINGS.
Posted on 2010-07-24 21:25:12 by Homer
Perhaps the single most useful Constraint of all are Springs.

Obviously we can use Springs to simulate things like suspension in cars.
But they can also be used for almost anything that is 'deformable' - ropes, cloth (waving flags), the surface of a liquid, soft deformable bodies such as jelly can be modelled using springs and particles, etc etc.

Springs do not directly constrain the position, like we saw in the previous examples.
Instead, springs generate a Force which indirectly imposes the position constraint for us.
Springs "fight" a change in position - the bigger the displacement in position, the bigger Force they generate.
And the Force generated is Signed - if the spring is Compressed, it will produce a Positive force.. and if the spring is Stretched, it will produce a Negative force.

Spring forces are mathematically defined by Hook's Law: F = -k * dP
where F = Force , k = "Spring Constant", and dP = "Change In Position".

We can use springs to anchor bodies to each other (and the World) instead of Point and Distance constraints.
Using springs, we could create a simulation of the Star Wars 'Pod Racers', or implement "buoyancy" for a sailing simulation.
And springs will definitely add some spice to our rope bridge simulation :)

In the next post we'll take a closer look at that "Spring Constant", we'll derive a Spring formula for 3D work, and we'll talk about the limitations and problems associated with springs.

Posted on 2010-07-24 21:47:34 by Homer
So, what is this mysterious "spring constant" ?
Well, that is a good question - its value is best discovered empirically (by experiment), but I'll toss you a bone and tell you that a value somewhere between 0.6 and 0.7 is a pretty good place to start.

The spring constant describes how "stiff" a spring is. There is another related constant which we should be aware of: spring damping.
The damping constant describes how quickly a spring "loses energy" - this affects how many times a spring will bounce back and forth before it reaches equilibrium. A good starting value for the damping constant is 0.2
We'll talk about damping soon, for the moment we can ignore it.

Choosing spring constants is a black art, make no doubt about it - and if you decide to use springs widely in your simulation, you'll spend the rest of your life tweaking those constants such that the simulation does not EXPLODE under extreme conditions.

What was that?
My simulation can EXPLODE? Yeah, we'll get to that in a minute.
At the moment, we only have a one dimensional formula for spring forces - in 3D we will need our force to have Direction as well as Magnitude - so we'll need to describe it as a 3D Vector.

How do we do that?

Well, we know a Spring has TWO ENDS - its connected at two places, separated (usually) by some Distance, which is the Natural Length of this Spring.
What we're interested in is the displacement from the natural length, and the vector between the two endpoints.
Find the displacement vector, and then stick that vector into the spring formula in place of dP.
It's that easy.

Posted on 2010-07-27 03:15:01 by Homer
So, what's the big problem? What here could make my simulation "EXPLODE" ?
Well, the problem relates specifically to STIFF springs - and we'll often be tempted to stiffen our springs.
To understand the problem, we need to analyze the behavior of a spring over very small timesteps.

We have a spring that is generating a Force.
Our numerical integrator calculates this Force once per timestep, converts it into an Acceleration, and then applies it - for the WHOLE TIMESTEP.
This would be perfectly ok if our spring never actually moved - but since (we presume) it did move, we're calculating instantaneous acceleration and then applying it for a whole timestep, this is not how the real world operates, and the result is that we can have a spring which extends beyond its original displacement at each harmonic interval, gaining energy with each bounce - uh oh!

In the real world, a spring will begin LOSING energy as soon as it begins to move. (toward equilibrium)... the equivalent to voltage in a simple electric circuit, theres only the starting maximum potential, we can't ever exceed it (without adding more energy).
Perhaps we can emulate this effect to our benefit?
So we try to fix this situation that we have created, we are foxes, we add some damping to remove energy from the system, and this helps, but cannot prevent the problem, and we have no way of detecting the problem since we don't watch how values are changing over great chunks of time.

For everyone who thought they understood Hook's Law, and springs, and wondered what all the fuss was about, you're not alone.
Notice that I'm trying not to post too much each time, I want every piece of this information to sink in.

I believe that we can actually detect this situation, if we take a moment to calculate the instantaneous energy of a rigid body (as a function of its momentum).
The energy of a body should never increase by more than gravity times mass over time, unless there was a collision.
If there was no collision in the previous frame, and the energy of the body (sum of linear and angular energies) got larger by an amount more than could have been due to gravity alone, then we have detected a failing spring before it explodes.
And another way we might deal with this problem is to calculate an Impulse rather than a Force, manipulating the Velocity instantaneously instead of indirectly via Acceleration.

So, I have proposed two possible solutions to a long-standing and common problem which vexes the game development community.
And I doubt anyone in the industry will ever read this.

Posted on 2010-07-27 04:19:28 by Homer

Anyone who has bothered to search for information about implementing joint constraints, or simply general constraints,  will no doubt have come across some disturbingly complex math... even more complex than the math we use for resolving collision contacts.

I'm going to make a very bold statement about physics, which I believe applies to all computer programming: it does not matter HOW you achieve a certain output, only that the output is what we wanted.

Physics is an attempt to express observations about the physical world in mathematical terms, simply by attempting to develop math formulas whose outputs for given inputs closely approximate those determined through empirical testing - we measure an experimental result, and then invent math to match it. Therefore, every single physics formula is JUST AN APPROXIMATION of the real world, it's technically WRONG from the outset, there is NO right or wrong way to do anything, as long as the output is what we wanted!

With this in mind, we are going to rush headfirst into the joyous world of Revolute Joint Constraints, and I'm going to propose a novel way of handling GENERAL revolute constraints using a constraint resolver that we actually already have implemented.

Posted on 2010-07-28 06:01:33 by Homer

Today we're going to to tackle Revolute Joint Constraints.
But before we do, what the hell is a Revolute Joint?

The word "revolute" should immediately remind you of another word: "revolve", clearly this word implies ROTATION.
So a Revolute Joint must be some kind of ROTATING joint.

We've already discussed how a Point Constraint acts remarkably similar to a BALL JOINT, in that it will allow any kind of rotation, but it won't allow translation (the ball joint must not be allowed to drift apart). We said that we can constrain any two bodies together by bringing together a point defined in the space of each body. What happens if we add another Point constraint, so that this pair of bodies is constrained by two points? We have just defined a primitive HINGE Joint !! The 3D vector between our two constraint points is acting like a an axis of rotation - not only have we constrained Translation as previously, but now we have reduced the degrees of freedom of rotation from 3DOF to just one: our hinge axis.
We can say that a Hinge allows only ONE degree of freedom.

Hinges are among the most useful constraint we'll ever use, that's what we would typically be using at the KNEES and ELBOWS of a RAGDOLL.
And if you think about knee and elbow joints in a human, you'll realize immediately that the axis of rotation is not the ONLY constraint that we apply to these joints - we will also want to limit the allowable range of angular motion (knees and elbows do not bend backwards, right?)
So knees and elbows are a special case of a Hinge with a reduced angular freedom - what's that, what do you call less than 1DOF? :P

Similarly, the shoulder joint of a human (or ragdoll) is a special case of a Ball Joint with a limited angular range of motion - we're limiting the angle on all three rotation axes this time... this is called a CONE constraint.
Stick your arm out horizontally, rotate your shoulder and you will see that the arc your arm moves in forms a cone shape.

As I mentioned in the previous post, there's often more than one way to solve a mathematical problem.
Often, we can greatly simplify the requirements of the mathematics by simply redefining the problem.
And prior to that, I suggested that we had already implemented one kind of Constraint in our physics simulator - I said that Contacts were a kind of constraint.

It should already be quite clear to you that a Contact is a means of transmitting 'energy' from one body to another. In the next post, I'm going to try to convince you that it's possible to implement all of the above constraints using specially modified Persistant Contacts - that we can use a special form of Contact to calculate the forces at (and transmit energy across) each of our Joints.

Posted on 2010-07-30 00:54:57 by Homer

We're going to take a rather abstract look at our Contact constraint.
The physics simulator currently supports two methods for resolving contact forces: with, and without friction.
I want you to forget all about Friction, because for Revolute joints, there will never be any relative linear motion at the Joint, so there can't be any translation in the plane orthogonal to the contact normal like there might be in a 'typical' contact situation... so no contact friction.
We may wish to implement friction on the angular motion of a revolute joint, but that's done using 'damping', so we can omit it.
So for implementing Revolute Joints, we will use the Frictionless contact resolution function.

Our physics simulator currently supports two kinds of Contacts: persistant and transient.
Persistant contacts are used to model 'resting and sliding' contact between bodies, which may persist over several TimeSteps.
We do this so we can avoid recalculating ALL collision detection and contact generation stuff for contacts that are 'still there from last time'.
For revolute joints, let's introduce a third kind of Contact: PERMANENT.

Permanent contacts will NEVER go away, as long as the Joint they represent still exists.

Further, our simulator supports 'Contact Manifolds' which are a way to group together small sets of contacts.
These are normally used to model 'contact patches' or AREAS of contact between bodies.
We might use Contact Manifolds to define permanent hinge joints.

There are a few examples of simulators which use this kind of scheme, but they tend to create and destroy a Contact for each Joint, for each Timestep, and I'm really not sure why they do that, since the Joint did not suddenly cease to exist.
Most physics simulators do NOT use contacts to model joints.
Rather, they have a pseudocode something like this:

-Calculate internal forces on all bodies
-integrate bodies to end of timestep
-determine which constraints have been violated
-determine an error metric at each violated joint
-calculate a correction force for each error metric
-rewind to the start of the current timestep
-apply the correction force to the bodies
-integrate forward to the end of the timestep

We're going to do something a little bit different.

Posted on 2010-07-30 01:21:59 by Homer
I want to break at this time to talk about something unrelated but very important: DSPACE.

We already have a good understanding of WorldSpace, and we know what BodySpace is too.
You'll see me refer to bodyspace as 'BSpace'.

Diagonalized BodySpace is a configuration at which a Body's Center Of Mass corresponds with its Origin - it pivots about its center of mass - and is aligned with the Major Axes of the Body - the Body is Oriented according to its actual shape (ie normal mass distribution in 3D Space with respect to the World axes).

Sometimes we'll be lucky, and BSpace will correspond to DSpace by default: if we have a simple body such as a Sphere or Box (aligned to world axes), we will usually set the Origin in the middle of the Body, and in these cases, the mass is evenly distributed, and BSPACE === DSPACE.
But when we load a mesh-based model from a file, or we create a COMPOUND body by aggregating several primitive bodies, we will find that the Origin is no longer at the center of mass - we will either need to rotate, translate, or BOTH, to get the body into DSpace.

Why would we want to get our Body into DSpace? Why does that matter to us?
Well, our Contact Resolver will need to transmit energy between linear and angular properties of our Body's physical state.
To do that, we use a mathematical tool called the INERTIA TENSOR, which I have described elsewhere.
This is a 3x3 matrix whose contents describes the way Mass is distributed across our Body, with respect to a CENTRAL CENTER OF MASS.
The Inertia Tensor is defined in BSpace.
If the Body was defined such that BSPACE===DSPACE , then the Inertia Tensor matrix will contain ALL ZEROES with the exception of the 'Diagonals', top left thru bottom right. This means that we can actually describe the Inertia Tensor as a 3D VECTOR, and perform MUCH FASTER MATH using the Vec3 representation of the Tensor, rather than the Matrix rep... but we can ONLY do this if the Tensor is 'Diagonalized' - and that is why we call it Diagonalized BodySpace :)

So - how do we know how we need to tranform some arbitrary Body such that it is defined in DSpace?
Well, we don't - and we don't need to know :)
We calculate the BSpace Inertia Tensor Matrix, and then we DIAGONALIZE IT.

How do we Diagonalize a Matrix? There's a few ways, but personally, I use a process called Jacobian Rotation to "row-reduce" the 3x3 Tensor matrix into Diagonalized form ... this is destructive apon the input tensor matrix, as it will zero out all the non-diagonals, leaving 3 values in the diagonals.. at the same time, it will construct another 3x3 matrix... this second matrix contains a Transform which we need to apply to our Body to get it into DSpace, at which point its Tensor is described by the Diagonalized tensor (or vector).

So guys, how am I doing, are we learning anything? Please feel free to mess up this thread with unnecessary interjections :P

Posted on 2010-07-30 05:50:53 by Homer

The simulator provides methods for combining bodies, calculating arbitrary inertia tensors and diagonalizing them.
So you don't need to worry about any of that, it's just good to understand what the term DSPACE is referring to, and why it's cool.
We could happily implement everything in BSpace but we would be forced to use the Matrix form of the Inertia Tensor everywhere in our math, which is going to directly affect how fast our simulator is, and consequently, how many bodies we can simulate at an acceptably small timestep.

Having talked briefly about DSpace, and its direct benefits to our simulation, it's time to take a very close look at our existing Contact Resolver, especially the math and what it's doing... I'll draw comparisons between Contacts, Springs and Joint Constraints, and we'll see just how similar their mechanisms are.
While we're at it, we'll cover MANIFOLDS, more Persistance, and briefly look at Resting/Sliding contacts.
Then we'll be ready to once more turn our attention to Joints, and look at how we might use Contacts to model Joints.
Posted on 2010-07-30 07:22:27 by Homer
For the purposes of this post, let us assume that we have two rigid bodies A and B which have just collided.
We have calculated PoC = the point of contact, and N = the Contact Normal, in World space.

Our first step is to calculate the position of PoC with respect to the center of mass of each Body, again in WorldSpace:
vRelPosA = PoC - A.Position
vRelPosB = PoC - B.Position

Next, we calculate the linear velocity being experienced at PoC with respect to the center of mass of each body:
WorldVelAtPoC_A = CrossProduct(A.AngularVel, vRelPosA) + A.LinearVel
WorldVelAtPoC_B = CrossProduct(B.AngularVel, vRelPosA) + B.LinearVel

Actually, we want the difference between these two:
RelativeVelocityAtPoC = WorldVelAtPoC_A - WorldVelAtPoC_B

At this point we can examine the Sign of the Relative Velocity.
If it is POSITIVE, then the PoC on each body are going to move away from one another in the next frame with no help from us.
We can consider this Contact to be a "false positive", there is no Collision to resolve - but we might keep this contact for a few more frames just in case things change.

So having determined that there is indeed a collision (the sign was negative), we can go on to calculate our collision response.
Now we want to know how hard the two bodies hit each other.

For each Body, we need to find the acceleration-induced change in linear velocity that occurred during this current Frame - ie, what's the difference between the Linear Velocity in the Body's current and previous states? I won't bother writing a formula here.
And we're specifically interested in the component of this Velocity which acts ONLY in the direction of the Contact Normal, noting that this is a MAGNITUDE, not a vector (the Normal is the vector).
Actually, we want the Sum of these, from both bodies.
Let's call the resulting sum the Closing Velocity of the Contact... even though its a magnitude, not a vector.

I just ran out of time, in the next post I will complete the discussion of contact resolution without friction, briefly mention fcontact with friction, and finish up this topic with a brief talk about CSPACE (Contact Space).

Posted on 2010-07-30 22:57:12 by Homer
So where were we? We've just calculated the relative velocity of the Impact, in the Direction of the Contact Normal.
We know that in a perfectly elastic collision response, the post-collision velocity should equal the pre-collision velocity.
But we will dampen it a little, using a scalar called the COEFFICIENT OF RESTITUTION (KR).
This is a floating point value that is less than or equal to 1.0 and its value depends on the physical material (rubber, concrete, steel) that BOTH objects are constructed from - this value, for any given two materials, can ONLY be discovered by experiment, YOU CANNOT CALCULATE THIS, but you can find tables of values for different material pairs, just search the internet or this board.
Note that if KR was bigger than 1.0, our Body or Bodies would gain energy from the impact, and that simply does not happen in the real world.

So: noting that this is the velocity due to one frame of acceleration and in the direction of the contact normal,
Post-Collision Velocity = - (Pre-Collision Velocity * KR)

I call this the "DESIRED VELOCITY", because it's what we WANT, and not what we HAVE.
Let's express that last formula another way:
DESIRED CHANGE IN VELOCITY = DESIRED VELOCITY - pre-collision velocity

We can now calculate an IMPULSE which would produce our DESIRED CHANGE IN VELOCITY 'instantaneously'.
And it is here that we would apply Friction, if we chose to.

The calculation of this Collision Response impulse is not simple, and deserves its own post.
Besides, the stuff you've just read is really a self-contained unit of learning, and you should read THIS post a few times.
Make sure you completely understand what we just did and why, before continuing to the impulse calculation.
Posted on 2010-07-31 01:12:53 by Homer
Now that we know what our desired change of velocity is, we can find the impulse that would generate that change.
Note that we will calculate this with respect to the PoC.

The first step is as follows..
For each Body, find the Torque Per Unit Impulse at the PoC:
TorquePerUnitImpulse = CrossProduct(relativeContactPosition,contactNormal)

Next, we use the Inverse Inertia Tensor to convert TorquePerUnitImpulse into RotationPerUnitImpulse:
RotationPerUnitImpulse = Body.InvInertiaTensor * TorquePerUnitImpulse

Next, we find the Linear Velocity that is due to ONLY rotation and that acts ONLY along the contact normal:
velocityPerUnitImpulse = CrossProduct(RotationPerUnitImpulse, relativeContactPosition)

Next, we work out the change in velocity in the Direction of the contact normal.
Note that:
1. This is a Magnitude, and not a Vector
2. Here we are also adding in the Linear component of Body velocity, to the previously calculated  linear velocity (at the PoC) that was due only to rotation.
deltaVelocityMag = Body.OneOverMass + DotProduct(velocityPerUnitImpulse ,CollisionNormal)

If there's two bodies involved in the collision (typical), we repeat all those steps for the Other Body, and sum the resulting deltaVelocityMag.

The final step is to calculate the actual impulse:
ImpulseMagnitude = Magnitude of Desired Change In Velocity (along contact normal, see previous post) / deltaVelocityMag

We now have the magnitude of the Impulse which we will apply at the PoC, to EACH body, in the direction of the Contact Normal, with respect to each body. Basically, I just said that we're going to apply an 'instant force' at the contact point to each body, in the direction away from contact, equally but opposite in sign.

So we're left with just one missing piece of the (frictionless collision response) puzzle now, which is exactly how to apply the impulse.
Posted on 2010-07-31 01:47:54 by Homer

The following calculations MUST be calculated for EACH body, so no cheating!

The impulse must be applied to the Linear and Angular components of our Body (or Bodies) separately.
The Linear component is pretty straightforward.. we need to scale the Unit Impulse by 1/Mass, and by the Direction of the Contact Normal:
deltaVelocity = Contact Normal * Impulse * OneOverMass

The angular component is a bit more complex... some simulators are 'velocity based', and some are 'momentum based', I'll show both solutions, but first we need to calculate the 'impulsive torque' as follows:
impulsiveTorque = CrossProduct(relativeContactPosition, Impulse)

Now for those two angular delta calculations:

CHANGE IN ANGULAR MOMENTUM:
deltaAngularMomentum = impulsiveTorque * OneOverMass

CHANGE IN ANGULAR VELOCITY:
deltaAngularVelocity = InverseWorldInertiaTensor * impulsiveTorque

Depending on our simulation, we can either add these resulting Deltas directly to the current State of the Body in question, or we can ACCUMULATE these deltas when we've finished processing ALL of this Body's contacts. The latter is required to give believable results when there are several SIMULTANEOUS CONTACTS involving a particular Body... this is how a Contact Manifold is solved.

When we are ready to apply the accumulated delta sums, we must remember to scale them by the number of contacts involved (for each Body).

Posted on 2010-07-31 04:01:08 by Homer

All that remains is for a brief discussion about something called CSPACE (Contact Space).

When we want to perform a collision response with Friction, we need to find components of velocity not JUST along the contact normal, but also along two axes which are orthogonal to the normal, and to each other - together these three axes form an ORTHONORMAL BASIS.
Contact Space is an orthonormal configuration where the X Axis represents our Contact Normal vector, and the Y and Z axes represent the other two axes which form a Plane that is normal to our contact normal - read that a couple of times, I probably could have explained that better.
Basically, we can create a matrix which we can use to transform between WSpace and CSpace... if you think about it, Contact Space is really just a rotation about the PoC such that the X axis aligns with the contact normal.

If we want friction, it is far more efficient for us to transform all of our input values into CSpace, do all our calculations there, and then transform the output back into WSpace. The alternative involves extracting pairs of orthonormal vectors at various points in our collision resolver math, its simply untenable.

This brings us to the end of this review of Contact Constraint with respect to Collisions.
In the next post' we'll analyze what's happening in the Contact Constraint math from a God's Eye view, and compare and contrast the fundamentals that we identify with the other Constraints that have been mentioned.
Posted on 2010-07-31 09:36:03 by Homer
Let's look at what we've learned from a different point of view.

The Contact Constraint tries to keep our Bodies apart, and especially tries not to let them overlap.
It does this by examining the Relative Velocity (RV) of the PoC with respect to each Body, and enforces a zero or positive RV... if the bodies are 'just touching', or are moving apart, the constraint is satisfied.

The Point Constraint tries to keep our Bodies together by making sure that the PoC (on each body) coincide in WSpace.
Can we modify the Contact Constraint to enforce a Point Constraint? YES.
With no relative velocity, the PoC (on each Body) are travelling at the same rate in 3D space.
They can ONLY move apart if the RV drifts away from zero !!!
Our constraint will be satisfied when the RV is zero.

Would we use this expensive method of holding two relative points together in space? Yes, we'll see why shortly.

The Spring Constraint tries to keep our Bodies together at a fixed Distance by applying Hook's Law to the actual displacement and determining a Force which will, over time, bring the displacement back to the natural length of the Spring.
Can we modify the Contact Constraint to enforce a Spring Constraint? Again, YES !!
Instead of an Impulse, we're looking for a Force - and rather than RV, we're interested in relative position.
Our constraint is now directly calculating a force to be applied equally and oppositely to each Body, based on two points defined on two Bodies (sound familiar?).

The reason that we would use a Contact Constraint to model a Point Constraint?
Simply that the point constraint directly controls Position - of ONE of the two bodies, relative to the other.In a point constraint, someone has to be the master, and someone has to be the slave. The result of directly manipulating position of course, is that the physical state of the Body OTHER than position is not modified, and this is incorrect.
Surely, the Point Constraint has applied an Impulse to the Slave, and the Master is left completely unconstrained.
We could calculate this inferred force, but does it not make more sense that BOTH bodies can contribute to a motion that breached our constraint... and therefore a force should be applied to both?

If we pull on Body A, then the Joint should transfer a force to Body B, AND VICE VERSA, like an infinitely stiff spring - right?
(Now think about what happens if we pull on them both, in different directions...)
We already talked about problems with stiff springs, so we know that springs are not really suitable for point constraints... and we want a constraint that is good at transferring forces IMMEDIATELY, not over time... just like a Contact Constraint ;)
We need a constraint that generates an Impulse whose purpose is to hold the VR at zero, regardless of the motions of the bodies contributing to said VR.

Note that these Modified Contact Constraints only need to implement a subset of our Collision Response stuff - calculate relative velocity, determine if the constraint is breached, and if so, generate a corrective impulse that DOES NOT depend on Contact Normal.
And since this is ONLY about the transfer of energy via the Joint, we won't consider Friction, either.

I hope I've been clear enough in this post, if you think I'm nuts, say so.
But I think I'm onto something :)

Next it's time to discuss the finer points of contact persistence, resting contact, and sliding contact aka microcollision.
After that, we'll zoom from this 'micro' level all the way back to the 'macro' level and discuss broadphase collision testing (including swept tests) and simulation partitioning. Finally, we'll get our hands REALLY dirty with some quite advanced narrowphase collision tests for convex shapes.

Posted on 2010-08-03 09:50:01 by Homer
Today we look at two closely aligned topics - interframe coherence, and persistence.

During our simulation, the most common event that will occur is , of course, collisions between bodies (and the static World, which can be considered as a body of infinite mass). When the Relative Velocity of the contact(s) is strongly negative, the bodies will repel from one another cleanly... but if the energy of the collision is low, the bodies may 'rattle' against one another, creating many short-lived contacts.
This situation is known as MICROCOLLISION... It may surprise you to learn that some of the most difficult things to model in a physics simulation include an object resting on the floor, and an object resting on another object, without sliding around all by itself.

If our simulator destroys contacts as soon as they have been resolved (ie responded to), and creates them as soon as they occur, microcollisions will cause our simulation to become bogged down just by the cost of constantly creating, collecting, discarding and detroying of what may be thousands of collisions, per body, per second.

The solution of course, is NOT to immediately discard contact information once a contact has been resolved.
We'll hang on to it for a few frames, just in case the contact reoccurs. This is what is meant by a PERSISTANT CONTACT.

Persistence helps us efficiently deal with microcollision in a much more efficient way, not only because we are no longer destroying/recreating contacts at an alarming rate, but because we are able to cache some of the results of CONTACT CALCULATIONS THEMSELVES, and re-use them in subsequent frames.

This concept of retaining the output of calculations made in previous frames in order to accelerate the calculations of current and subsequent frames is known as COHERENCE, and it is a VERY powerful tool, not just in physics simulators, but in any kind of cpu-intensive and repetitive situation.

When the energy of microcollision response drops below some threshold, we declare that the body is in a RESTING state - and we then "put it to sleep" - our simulator will no longer integrate the state of this body, unless it is "woken up" (usually by a collision with a moving, and therefore "awake" body).

Let's assume that a body was dropped from a height onto the floor.
It bounces around for a bit, then settles down and comes to a stop, and now it is Resting on the floor (it is asleep).
Imagine that we try to push on the side of it.
If the floor was made of something like ice, with "no friction", it will immediately begin to SLIDE. Let's assume the floor is made of something else, and so there is friction.

Friction will fight our attempt to set the body into motion... this kind of friction is called STATIC FRICTION.
Lots of people also refer to it as "STICTION" - because it makes things tend to want to stick in place, or act as if they are sticky.
Static friction introduces a threshold energy which we must overcome before the body will move... if we don't push hard enough, nothing will happen.. but if we push a bit harder, and a bit harder, SUDDENLY we will OVERCOME STATIC FRICTION, and the body will begin to move.

The moving body, still in contact with the floor, is now subjected to another kind of friction called DYNAMIC FRICTION.
It's really kind of the same thing, except we use different values for static and dynamic friction.
OK, now the fun bit.
If we don't push hard enough to overcome dynamic friction, the body will want to ROLL, tending to pivot apon the Support Point which is furthest in the Direction of the force we applied, and in contact with the floor.
But if we gave it a REALLY hard push, and overcome dynamic friction, then the body will SLIDE rather than roll - we're pushing so hard that friction doesn't have a chance to exert a force on the persistent contact(s) with the floor, which is what causes rolling to occur.

Friction is not something we can calculate... it completely depends on the physical material which BOTH bodies are made of: the only way to find values for coefficients of friction (ie a pair of values: static and dynamic), is the empirical method of discovery, otherwise known as EXPERIMENTAL OBSERVATION. But don't worry, you can find tables of friction coefficients for all kinds of pairs of materials, just search the intertoobs.

Next time, we'll begin looking at macrocollision detection, better known as BROADPHASE. We'll begin by discussing why we might want to partition our simulation, and how we might go about it. Then we'll look at a fast, efficient broadphase collision detection algorithm which is immune to the effects of rotation and high velocities... sometimes referred to as CONTINUOUS COLLISION DETECTION, as opposed to 'discrete' collision detection.

Posted on 2010-08-04 06:40:37 by Homer
Changed my mind - first we'll tackle the fast broadphase collision test, and then look at spatial partitioning.

I like spheres.
I mean I really, REALLY like spheres.

The cheapest possible intersection tests are always those which compare a 3D Point to something else.
Of course, a Point has no physical dimensions, and occupies no space... not very useful unless we're dealing with particle physics.
The next cheapest tests are those involving Spheres... we can think of a sphere as a Point which has some 'thickness' (ie, its radius).
Personally, I find spheres to be the most easy 3D object to visualize and apply in thought experiments, and I would argue that they are the most simple 3D shape, although some would disagree and say that a tetrahedron is the most primitive.

Spheres are ROTATIONALLY INVARIANT. This means that no matter how we orient a sphere, its mass distribution (with respect to WSpace axes) never changes - its Inertia Tensor never changes.

Today I was going to cover what I think is the most elegant and beautiful 'broadphase' collision detection mechanism that I've ever encountered.
It is rotationally invariant, and it is immune to high velocities and large timesteps.
Its name is Swept Sphere Test, and it can be implemented using a cheap, fast quadratic equation.
Not only does this test tell us if two sphere will intersect during the timestep, but also WHEN - if their paths intersect, it will return the Time when they first begin to intersect, and the Time when they last intersect, had they been allowed to pass through each other as clouds in the sky.

Unfortunately I broke my left thumb today and I'm in quite a lot of pain, so it's going to have to wait, sorry guys.
Anyway as soon as I've covered the theory and math behind that test, I'll be introducing our first example of a partitiioning scheme, known as a Bounding Volume Hierarchy (BVH), and specifically we'll look at using a dynamic sphere tree as a tool for speeding up collision testing.

Ouch, Ouch, Ouch.
Posted on 2010-08-05 04:57:06 by Homer

Collision detection in 3D environments is a very active field of research even to this day, it's taken seriously because of industrial robotics requiring motion planning and so forth. There are dozens and dozens of algorithms, and at least a dozen variants of each, but they can all be classified into just two categories: instantaneous tests, and SWEPT tests.

The instantaneous tests are the easiest to understand: given two shapes of known geometry and physical state (position, orientation), determine whether or not the shapes are overlapping. I say that these tests are easiest to understand because they are easiest to visualize.
One example of an instantaneous intersection test for bodies of arbitrary shape is called the SEPARATING AXIS TEST (SAT).
As usual, there are dozens of variations on this algorithm, but the logic behind them all is the same: if there exists some PLANE (axis) which separates two bodies, then the bodies do not intersect - this sounds pretty obvious to us humans, but we need to teach the computer what to look for.
The most simple version of this algorithm is to project both of our 3D shapes onto the 2D (XY, ZY and XZ) planes - if the 2D projections overlap in ALL THREE cases, then the 3D shapes are intersecting - and if we can find any axis where they don't overlap, then the 3D shapes don't intersect.

The problem with instantaneous tests is that our physics simulation is advancing in DISCRETE TIMESTEPS, which means that we only apply our intersection test at discrete timesteps. Since that is the case, it is possible to completely miss detecting a collision, and especially if the relative velocity is high(ly negative). For example, a bullet is fired from a gun... as it leaves the barrel of the gun, our simulator performs an instantaneous collision check and finds no collision occurred. Now we advance the simulation by one timestep, during which time the bullet, moving at a high velocity,  travels right through our enemy, through the wall behind him, and off into the infinite void.. now our simulator tests for collision again, and finds none... we missed two important collision events, and worse, the bullet has escaped the boundaries of our simulation, and is in unconstrained space !! Uh Oh.

The obvious solution is to use smaller timesteps, but this means performing more tests, more often... our simulation gets bogged down looking for intersections which more often than not are not occuring at that exact moment in time.

A less obvious solution involves the introduction of Time in our calculations. We extend our 3D instantaneous test into a 4D SWEPT TEST.
It's easy to imagine this: we find the position of our object now, and at the end of the timestep, and we 'stretch' (extrude) the object in 3D space between its current and next position. Now we do the same for the other object we're checking against, and then we perform an instantaneous intersection test on the extruded shapes.
Now, given that the bodies may be of arbitrary shape, and may be ROTATING, it is not immediately obvious what shape these extrusions will be, let alone how to test them for intersection.. but for some simple shapes, this is not a problem... and given that today we are talking about BROADPHASE collision testing, it is acceptable that we wrap our arbitrarily shaped 3D bodies in a COLLISION HULL, a proxy shape which is more simple than the actual shape. Many if not MOST physics simulators use some kind of 'Bounding Volume' (collision hull) which encloses their objects.. many use bounding boxes, I shall today talk of using the humble SPHERE for this purpose.

Recall that I said how much I liked spheres? We can forget all about rotation (spheres are invariant), and the 3D extrusion of a sphere is always a simple CAPSULE.
We can write intersection tests for geometric capsules, but it is not necessary.
A much better solution is to define the capsules 'parametrically', and write a parametric equation which can determine whether or not they intersect.
Is this beginning to sound expensive? Don't panic :) This can in fact be done quite cheaply using a Quadratic Equation.
The great thing about this particular test is that it returns more useful information than simply whether or not the objects will collide during their travel... if they do, it also tells us the Time Of Impact of the spheres, and the Time where they part ways.
See the following page for a thorough description of this solution, including sourcecode... http://www.gamasutra.com/view/feature/3383/simple_intersection_tests_for_games.php?page=2

As you can now appreciate, this test is also immune to the effects of high velocities: we don't have to worry about fast-moving entities, our test will never miss the intersection of a pair of bounding spheres.... but just because a pair of bounding hulls are going to intersect does not necessarily mean that the actual geometries of the two bodies in question are going to intersect... although our test may never miss a collision, it can generate 'false positives'. This means that although the extrusions of the spheres intersect, the actual geometries may never intersect... the objects may pass each other, ALMOST colliding. Obviously, we're going to need to check more closely to determine whether the bodies actually collided.
Recall that our test returned two Time values which are the bounds of the timespan during which the spheres are overlapping.
We can use these two Times as the upper and lower boundaries of our NARROWPHASE collision testing, since we know that they definitely are NOT intersecting outside of that timespan. My solution from that point is based on BISECTING this timespan, performing instantaneous tests.
In fact, we can begin testing at the midpoint of that timespan, where logically, penetration would typically be deepest.
Then we hunt backwards through the first half of the timespan, using a 'binary search in Time' for the moment where the objects first intersected, if ever. I expect to cover some of the algorithms used in the narrow phase at some point in the near future, among them are GJK and its close relative EPA.

Tomorrow we will look at Spatial Partitioning and its relevance to physics simulations.

Posted on 2010-08-06 09:42:33 by Homer