At this point, we have calculated a Vec3 representing the linear velocity of the collision point on Body A in Contact space.

If there's a Body B in this collision, repeat for the other body, and subtract the resulting Vec3 (for Body B) from the result we have for Body A.

Let's call this vector 'the relative closing velocity of the collision point(s) in Contact Space'.

We should immediately check the sign of the X axis of this vector - if its Positive, then the collision is a fake - the body(s) move AWAY from penetration !! Let's assume we have a Negative closing velocity - if we don't resolve this collision, we shall see a penetration occur... we better do something!

Next, we calculate (in WorldSpace) the linear velocity due only to acceleration of each Body, and only in the direction of the Collision Normal.

We actually did this earlier but we calculated it directly in ContactSpace (using TransMult) - we'd be trying to get the X vector which we set to zero earlier, we'd be setting the Y and Z to zero, and then transforming the result back into WorldSpace ... so let's ignore that we already kinda had this answer, and do the operation again, but this time directly in WorldSpace:

accVelocity = DotProduct (CollisionNormal, VelocityDeltaForThisTimeStep)

Again, if there is a BodyB, we calculate this vector for BodyB, and subtract it from the result of BodyA.

We'll call the resulting vector 'the relative linear velocity due to acceleration in WorldSpace'.

To calculate the (post-collision) DesiredDeltaVelocity, we need the velocity of the contact point in contact space, velocity of the contact point in world space, and a 'coefficient of restitution'.

desiredDeltaVelocity in WorldSpace = - (contactspaceVelocity.x - (Restitution * (contactspaceVelocity.x - velocityFromAcc)))

The restitution coefficient is a floating-point value between 0.0 and 1.0 which determines how 'rubbery' the collision is... Higher values make the collision 'more bouncey' and indicate 'harder' materials (glass marble on stone floor) while smaller values make the collision 'less bouncey' and indicate 'softer' materials (glass marble on mud).

For two bodies who each have their own Restitution value, we should use the lower value of the two.

We are now ready to calculate the Impulse that will make our bodies bounce away from each other.

Let's calculate the impulse required to resolve this collision... we will build a vector that shows the change in velocity (in world space) for a UNIT impulse in the direction of the contact normal, and then we will SCALE that unit-impulse so that it causes EXACTLY the change in velocity that we desire.

To calculate the 'Torque per Unit of Impulse', we need "the collision point relative to each Body" and we need the collision normal:

torquePerUnitImpulse = CrossProduct(relativePosition,CollisionNormal)

Now we use the (WorldSpace) Inverse Inertia Tensor (of each Body) to convert torquePerUnitImpulse into rotationPerUnitImpulse:

rotationPerUnitImpulse = InverseWorldInertiaTensor * torquePerUnitImpulse

I've provided a macro called Mat33_Mul_Vec3 so don't panic :P

Now we must find the Linear Velocity that is due to only rotation and that is along the collision normal:

velocityPerUnitImpulse = CrossProduct(rotationPerUnitImpulse, relativePosition)

Now we must calculate the change of velocity in ContactSpace:

ImpulseDenominator = BodyA.OneOverMass + DotProduct(velocityPerUnitImpulse,CollisionNormal)

If we have a BodyB in this collision, we should go through the sequence again for BodyB, which we ADD rather than subtract, to the result of BodyA, so we get:

ImpulseDenominator = (BodyA.OneOverMass + DotProduct(velocityPerUnitImpulseA,CollisionNormal)) + (BodyB.OneOverMass + DotProduct(velocityPerUnitImpulseB,CollisionNormal))

Now we can calculate our desired impulse:

ContactSpaceImpulse = <desiredDeltaVelocity / ImpulseDenominator , 0.0, 0.0>

See that our impulse is returned as a Vec3 in ContactSpace, see that it only has a value in the X axis.

Note that this is clearly showing that a Frictionless collision results in an impulse that is applied ONLY in the direction of the Collision Normal.

Let's finish resolving this collision.

We need to convert the contactspace impulse into worldspace:

WorldImpulse = ContactToWorld * ContactSpaceImpulse

Now we Split the impulse into linear and angular components, and calculate the delta-velocity and delta-angMomentum:

impulsiveTorque = CrossProduct(relativePositionA,WorldImpulse)

deltaAngMomentum = impulsiveTorque * BodyA.OneOverMass

deltaVelocity = BodyA.OneOverMass * WorldImpulse

And if there's a BodyB:

impulsiveTorqueB = CrossProduct (WorldImpulse, relativePositionB) <-- note we swapped the order here

deltaAngMomentumB = impulsiveTorque * -BodyB.OneOverMass

deltaVelocityB = -BodyB.OneOverMass * WorldImpulse

We can add these deltas to the Body(s) immediately, however I suggest that there may be simultaneous collisions (ie, more than one collision at the same moment in time): we should resolve all simultaneous collisions using our current state, accumulating the deltas in the bodies... then when we're done resolving all simultaneous collisions, we should apply the delta sums to the body states. This allows us to resolve all the simultaneous collisions 'together', and then to advance our simulation 'together', so our bodies don't go 'out of synch'.

Next we'll learn how to calculate a response with Friction :)

To calculate the 'Torque per Unit of Impulse', we need "the collision point relative to each Body" and we need the collision normal:

torquePerUnitImpulse = CrossProduct(relativePosition,CollisionNormal)

Now we use the (WorldSpace) Inverse Inertia Tensor (of each Body) to convert torquePerUnitImpulse into rotationPerUnitImpulse:

rotationPerUnitImpulse = InverseWorldInertiaTensor * torquePerUnitImpulse

I've provided a macro called Mat33_Mul_Vec3 so don't panic :P

Now we must find the Linear Velocity that is due to only rotation and that is along the collision normal:

velocityPerUnitImpulse = CrossProduct(rotationPerUnitImpulse, relativePosition)

Now we must calculate the change of velocity in ContactSpace:

ImpulseDenominator = BodyA.OneOverMass + DotProduct(velocityPerUnitImpulse,CollisionNormal)

If we have a BodyB in this collision, we should go through the sequence again for BodyB, which we ADD rather than subtract, to the result of BodyA, so we get:

ImpulseDenominator = (BodyA.OneOverMass + DotProduct(velocityPerUnitImpulseA,CollisionNormal)) + (BodyB.OneOverMass + DotProduct(velocityPerUnitImpulseB,CollisionNormal))

Now we can calculate our desired impulse:

ContactSpaceImpulse = <desiredDeltaVelocity / ImpulseDenominator , 0.0, 0.0>

See that our impulse is returned as a Vec3 in ContactSpace, see that it only has a value in the X axis.

Note that this is clearly showing that a Frictionless collision results in an impulse that is applied ONLY in the direction of the Collision Normal.

Let's finish resolving this collision.

We need to convert the contactspace impulse into worldspace:

WorldImpulse = ContactToWorld * ContactSpaceImpulse

Now we Split the impulse into linear and angular components, and calculate the delta-velocity and delta-angMomentum:

impulsiveTorque = CrossProduct(relativePositionA,WorldImpulse)

deltaAngMomentum = impulsiveTorque * BodyA.OneOverMass

deltaVelocity = BodyA.OneOverMass * WorldImpulse

And if there's a BodyB:

impulsiveTorqueB = CrossProduct (WorldImpulse, relativePositionB) <-- note we swapped the order here

deltaAngMomentumB = impulsiveTorque * -BodyB.OneOverMass

deltaVelocityB = -BodyB.OneOverMass * WorldImpulse

We can add these deltas to the Body(s) immediately, however I suggest that there may be simultaneous collisions (ie, more than one collision at the same moment in time): we should resolve all simultaneous collisions using our current state, accumulating the deltas in the bodies... then when we're done resolving all simultaneous collisions, we should apply the delta sums to the body states. This allows us to resolve all the simultaneous collisions 'together', and then to advance our simulation 'together', so our bodies don't go 'out of synch'.

Next we'll learn how to calculate a response with Friction :)

In order to implement friction, we'll use some of the previous calculations..however, the implementation is quite different.

When using Matrices, the equivalent of a CrossProduct is multiplication by a skew symmetric matrix.

Now we'll build the matrix for converting between linear and angular quantities.

impulseToTorqueA = Mat33_Star(relativePositionA)

Now we'll build the matrix to convert contactspace impulse into a change in worldspace velocity:

deltaVelWorld = - ((impulseToTorqueA, InverseWorldInertiaTensor) * impulseToTorqueA)

If theres a BodyB, we calculate its deltaVelWorld matrix the same way, and add the two result matrices.

Now we use a similarity transform to do a 'change of basis' to get results as contact coordinates:

deltaVelocity = Transpose (ContactToWorld) * deltaVelWorld * ContactToWorld

Now we'll add in the linear velocity by hand, to the Diagonal components:

deltaVelocity.m00 += inverseMass

deltaVelocity.m11 += inverseMass

deltaVelocity.m22 += inverseMass

Note that for two Bodies, inverseMass is the sum of their inverse masses.

We now need to INVERT the matrix to get 'impulse per unit velocity':

impulseMatrix = Mat33_Inverse(deltaVelocity)

Now we find the Target Velocities that we need to kill:

velKill = <desiredDeltaVelocity, ContactVelocity.y, ContactVelocity.z>

Now find the impulse needed to kill this velocity:

impulseContactSpace = impulseMatrix * vellKill

Now we need to check if theres enough PLANAR impulse to overcome STATIC friction:

planarImpulse = sqrt(impulseContactSpace.y^2 + impulseContactSpace.z^2)

IF (planarImpulse > impulseContactSpace.x * STATIC friction), we need to use DYNAMIC friction, and find a new value for impulseContactSpace...

ELSE, we're happy to use the impulseContactSpace as it stands.

My next post will show you how to implement dynamic friction (how to mangle the impulseContactSpace we have already calculated) , and that will wrap up Collision Response.

When using Matrices, the equivalent of a CrossProduct is multiplication by a skew symmetric matrix.

Now we'll build the matrix for converting between linear and angular quantities.

impulseToTorqueA = Mat33_Star(relativePositionA)

Now we'll build the matrix to convert contactspace impulse into a change in worldspace velocity:

deltaVelWorld = - ((impulseToTorqueA, InverseWorldInertiaTensor) * impulseToTorqueA)

If theres a BodyB, we calculate its deltaVelWorld matrix the same way, and add the two result matrices.

Now we use a similarity transform to do a 'change of basis' to get results as contact coordinates:

deltaVelocity = Transpose (ContactToWorld) * deltaVelWorld * ContactToWorld

Now we'll add in the linear velocity by hand, to the Diagonal components:

deltaVelocity.m00 += inverseMass

deltaVelocity.m11 += inverseMass

deltaVelocity.m22 += inverseMass

Note that for two Bodies, inverseMass is the sum of their inverse masses.

We now need to INVERT the matrix to get 'impulse per unit velocity':

impulseMatrix = Mat33_Inverse(deltaVelocity)

Now we find the Target Velocities that we need to kill:

velKill = <desiredDeltaVelocity, ContactVelocity.y, ContactVelocity.z>

Now find the impulse needed to kill this velocity:

impulseContactSpace = impulseMatrix * vellKill

Now we need to check if theres enough PLANAR impulse to overcome STATIC friction:

planarImpulse = sqrt(impulseContactSpace.y^2 + impulseContactSpace.z^2)

IF (planarImpulse > impulseContactSpace.x * STATIC friction), we need to use DYNAMIC friction, and find a new value for impulseContactSpace...

ELSE, we're happy to use the impulseContactSpace as it stands.

My next post will show you how to implement dynamic friction (how to mangle the impulseContactSpace we have already calculated) , and that will wrap up Collision Response.

OK - to implement dynamic friction, we must mangle the frictionless impulse (contact space):

impulseContactOut.yz /= planarImpulse

impulseContactOut.x = deltaVelocity.m00 +

deltaVelocity.m01*friction*impulseContactOut.y +

deltaVelocity.m02*friction*impulseContactOut.z

impulseContactOut.x = desiredDeltaVelocity / impulseContactOut.x

impulseContactOut.y *= Dynamic Friction * impulseContact.x

impulseContactOut.z *= Dynamic Friction* impulseContact.x

Physical objects are made of Physical Materials.

Attached is a file containing a table of static and dynamic friction coefficients for various combinations of two materials. Note that this table is incomplete, and really just something to start with.

Actually, there are three tables, representing the coefficients under Dry, Slippery and Sticky conditions :)

The file contains a macro to help us obtain a set of coefficients for a pair of materials, and also to look up the Density of a material.

We supply the Condition (dry, wet, slippery) we want, and the IDs of the two materials.

It returns in EAX a ptr to the pair of friction coefficients for those materials under those conditions.

Now we're able to put it all together :)

I've got some testing to do on the current code (theres at least one special condition to handle), so I won't provide an update just yet, but here's that Friction table to look at.

impulseContactOut.yz /= planarImpulse

impulseContactOut.x = deltaVelocity.m00 +

deltaVelocity.m01*friction*impulseContactOut.y +

deltaVelocity.m02*friction*impulseContactOut.z

impulseContactOut.x = desiredDeltaVelocity / impulseContactOut.x

impulseContactOut.y *= Dynamic Friction * impulseContact.x

impulseContactOut.z *= Dynamic Friction* impulseContact.x

Physical objects are made of Physical Materials.

Attached is a file containing a table of static and dynamic friction coefficients for various combinations of two materials. Note that this table is incomplete, and really just something to start with.

Actually, there are three tables, representing the coefficients under Dry, Slippery and Sticky conditions :)

The file contains a macro to help us obtain a set of coefficients for a pair of materials, and also to look up the Density of a material.

We supply the Condition (dry, wet, slippery) we want, and the IDs of the two materials.

It returns in EAX a ptr to the pair of friction coefficients for those materials under those conditions.

Now we're able to put it all together :)

I've got some testing to do on the current code (theres at least one special condition to handle), so I won't provide an update just yet, but here's that Friction table to look at.

There is at least one special case to consider.

OldState and NewState are both Penetrating... This shouldn't happen, it's due to poor implementation.

One way this can happen: If a body has too little velocity to escape penetration (ie due to gravity alone) then it will begin the next iteration with its OldState and NewState both penetrating. eg A body starts life with zero velocity, it is resting on a Floor Plane. In the first iteration, a collision is detected, and the body is given velocity in Y+ to fight gravity, but its not enough, so it falls a small distance. In the next iteration, the body is still falling, so its Old and New states are both Penetrating.

If we detect this state, we can attempt to Correct the Penetration.

We can determine how much the Linear and Angular motions contributed to the Penetration, and use that ratio to find linear and angular 'corrections' to force the Body backwards in Time into the Colliding position.

We should then correct all other affected state members, and resolve the Collision, assuming the collision time to be zero.

I'm not sure how my integration maths goes with negative time, so for now, we end up with the penetrating body being forced back into the colliding state, and this body glitches slightly forward in Time.

If I can get my Integrate method to work with negative Time, then I can fix this time glitch.

In my next post, I'll show you pseudocode for the penetration correction which works for any body shape.

OldState and NewState are both Penetrating... This shouldn't happen, it's due to poor implementation.

One way this can happen: If a body has too little velocity to escape penetration (ie due to gravity alone) then it will begin the next iteration with its OldState and NewState both penetrating. eg A body starts life with zero velocity, it is resting on a Floor Plane. In the first iteration, a collision is detected, and the body is given velocity in Y+ to fight gravity, but its not enough, so it falls a small distance. In the next iteration, the body is still falling, so its Old and New states are both Penetrating.

If we detect this state, we can attempt to Correct the Penetration.

We can determine how much the Linear and Angular motions contributed to the Penetration, and use that ratio to find linear and angular 'corrections' to force the Body backwards in Time into the Colliding position.

We should then correct all other affected state members, and resolve the Collision, assuming the collision time to be zero.

I'm not sure how my integration maths goes with negative time, so for now, we end up with the penetrating body being forced back into the colliding state, and this body glitches slightly forward in Time.

If I can get my Integrate method to work with negative Time, then I can fix this time glitch.

In my next post, I'll show you pseudocode for the penetration correction which works for any body shape.

So, something has slipped through our net, we have detected a Penetration case... a body is penetrating in both its Old and New states - ouch !! Can we fix it? Well, we can try :)

Let's assume that we know the Penetration Depth (in the deepest case - at the New position).

Our Body was travelling with known linear and angular motions, and it caused a Penetration.

We can work out how much the linear and angular motions each contributed to the penetration depth, and calculate linear and angular 'corrections' that should place the body back into the Colliding state.

The first thing we need to do is calculate the linear momentum that is due only to rotation.

Lets do that in stages:

Caculate Torque per unit impulse at contact point.. torque = R cross N = change in angular momentum over time:

TorquePerUnitImpulse = CrossProduct(relativeContactPosition,ContactNormal)

Convert that into Angular Momentum:

angularInertiaWorld = Body.InverseWorldInertiaTensor * TorquePerUnitImpulse

Find the inertia at the contact point:

angularInertiaWorld = CrossProduct (angularInertiaWorld,relativeContactPosition)

Find the Linear part that is along the Contact Normal:

LinearMomentumDueToRotation = DotProduct (angularInertiaWorld, ContactNormal)

When we continue, we'll learn how to use this value to determine how much Linear and Angular motions contributed to the penetration... then we can figure out how much linear and angular change is required to correct the penetration.

Let's assume that we know the Penetration Depth (in the deepest case - at the New position).

Our Body was travelling with known linear and angular motions, and it caused a Penetration.

We can work out how much the linear and angular motions each contributed to the penetration depth, and calculate linear and angular 'corrections' that should place the body back into the Colliding state.

The first thing we need to do is calculate the linear momentum that is due only to rotation.

Lets do that in stages:

Caculate Torque per unit impulse at contact point.. torque = R cross N = change in angular momentum over time:

TorquePerUnitImpulse = CrossProduct(relativeContactPosition,ContactNormal)

Convert that into Angular Momentum:

angularInertiaWorld = Body.InverseWorldInertiaTensor * TorquePerUnitImpulse

Find the inertia at the contact point:

angularInertiaWorld = CrossProduct (angularInertiaWorld,relativeContactPosition)

Find the Linear part that is along the Contact Normal:

LinearMomentumDueToRotation = DotProduct (angularInertiaWorld, ContactNormal)

When we continue, we'll learn how to use this value to determine how much Linear and Angular motions contributed to the penetration... then we can figure out how much linear and angular change is required to correct the penetration.

Now that we know the linear momentum at the contact point that is due only to Rotation and is in the direction of the collision normal.. we need to find the 'total' linear momentum, by adding the NON-rotational component of linear momentum, which is simply the Mass of the Body... if theres another Body, repeat these steps, summing the result.. we now have the TOTAL momentum at the point of collision due to our body or bodies.

We can now determine how much the Angular motion contributed to the Penetration Depth:

AngularMove = ((AngularInertia / TotalInertia) * fPenetrationDepth)

We can now also find the linear correction value:

LinearMove = fPenetrationDepth - AngularMove

Now we know how much the Angular motion contributed to the penetration, we need to calculate the Rotation which caused this..we want the correct rotation direction, and scaled to produce the change we want:

targetAngularDirection = CrossProduct (relativeContactPosition,contactNormal)

angularChange = Body.InverseWorldInertiaTensor * targetAngularDirection * (angularMove/AngularInertia )

The result is the change in Angular Momentum required to produce the desired change in rotation :)

As for the Linear change, well, thats a straightforward change in Position which consumes whatever penetration depth remains. And if we have a second Body, as usual, we must reproduce these steps for Body B.

And that brings us to the end of this brief but meaty introduction to Penetration Correction :)

We can now determine how much the Angular motion contributed to the Penetration Depth:

AngularMove = ((AngularInertia / TotalInertia) * fPenetrationDepth)

We can now also find the linear correction value:

LinearMove = fPenetrationDepth - AngularMove

Now we know how much the Angular motion contributed to the penetration, we need to calculate the Rotation which caused this..we want the correct rotation direction, and scaled to produce the change we want:

targetAngularDirection = CrossProduct (relativeContactPosition,contactNormal)

angularChange = Body.InverseWorldInertiaTensor * targetAngularDirection * (angularMove/AngularInertia )

The result is the change in Angular Momentum required to produce the desired change in rotation :)

As for the Linear change, well, thats a straightforward change in Position which consumes whatever penetration depth remains. And if we have a second Body, as usual, we must reproduce these steps for Body B.

And that brings us to the end of this brief but meaty introduction to Penetration Correction :)

Now its time to start laying out the pseudocode for the collision detection and response algorithm.

WITHOUT any collision detection, the main loop of the simulator looks like this:

-Calculate the instantaneous Forces acting on our Body based on its Old state

-Integrate to find the New state, based on the Old state, instantaneous Forces, and TIMESTEP.

WITH collision detection, we add the following steps:

-For all unique Pairs of Bodies:

--Perform Broadphase collision detection (based on BoundingSphere)

--If collision detected,

----Perform Narrowphase collision detection (based on actual shape)

----Add record of collision event to a List which is Sorted by CollisionTime

--Endif

-EndFor

-For all Collision records:

--Peek at the first Collision record

--If the CollisionTime is NOT ZERO

----Integrate the entire simulation forward to the CollisionTime

--EndIf

--For all CollisionRecords which have the same CollisionTime:

----Resolve Collision... accumulate resulting changes to LinVelocity / AngMomentum

--EndFor

--Apply accumulated changes to affected Bodies, and swap the States of those Bodies

--If there are more Collisions

----Integrate the entire Simulation forward to the time of the NEXT collision

--Else

----Integrate the entire Simulation forward to the end of the current TimeStep

--EndIf

-EndFor

You can see that I am making particular effort to:

1 - handle multiple simultaneous collision events as a GROUP

2 - integrate the simulation forwards in time as a GROUP

I'm trying hard to keep the simulation 'in synch' , but this won't always be possible - and there are implementations where this is absolutely undesirable, which I might yet talk about at some point.

Please note that this is just a rough draft of the algorithm I've already implemented, it should serve only as a guide and is liable to be changed (there is at least one problematic singularity that I feel can be handled better).

Now I've talked about integration, collision detection, collision response, and penetration correction for rigid body dynamics using Spheres, it's probably time to turn our attention to more complex geometries, and as we go, introduce some mathematical shortcuts and speedups that work only for specific geometries.

It's probably time for me to post another update of the testbed code too, and sometime very soon I'll have to add some 3D rendering code so we can actually see something ;)

WITHOUT any collision detection, the main loop of the simulator looks like this:

-Calculate the instantaneous Forces acting on our Body based on its Old state

-Integrate to find the New state, based on the Old state, instantaneous Forces, and TIMESTEP.

WITH collision detection, we add the following steps:

-For all unique Pairs of Bodies:

--Perform Broadphase collision detection (based on BoundingSphere)

--If collision detected,

----Perform Narrowphase collision detection (based on actual shape)

----Add record of collision event to a List which is Sorted by CollisionTime

--Endif

-EndFor

-For all Collision records:

--Peek at the first Collision record

--If the CollisionTime is NOT ZERO

----Integrate the entire simulation forward to the CollisionTime

--EndIf

--For all CollisionRecords which have the same CollisionTime:

----Resolve Collision... accumulate resulting changes to LinVelocity / AngMomentum

--EndFor

--Apply accumulated changes to affected Bodies, and swap the States of those Bodies

--If there are more Collisions

----Integrate the entire Simulation forward to the time of the NEXT collision

--Else

----Integrate the entire Simulation forward to the end of the current TimeStep

--EndIf

-EndFor

You can see that I am making particular effort to:

1 - handle multiple simultaneous collision events as a GROUP

2 - integrate the simulation forwards in time as a GROUP

I'm trying hard to keep the simulation 'in synch' , but this won't always be possible - and there are implementations where this is absolutely undesirable, which I might yet talk about at some point.

Please note that this is just a rough draft of the algorithm I've already implemented, it should serve only as a guide and is liable to be changed (there is at least one problematic singularity that I feel can be handled better).

Now I've talked about integration, collision detection, collision response, and penetration correction for rigid body dynamics using Spheres, it's probably time to turn our attention to more complex geometries, and as we go, introduce some mathematical shortcuts and speedups that work only for specific geometries.

It's probably time for me to post another update of the testbed code too, and sometime very soon I'll have to add some 3D rendering code so we can actually see something ;)

I spent a little time today fusing the Physics engine into the framework from Biterider's D3D 'Vectors' demo.

Having done that, I began deriving some new objects based on OA32's D3D_MeshManager and D3D_MeshManaged.

Here's a rundown of my new objects:

D3D_Simulator - derived from my physics Simulator class, this object is a replacement for D3D_MeshManager.

Apart from doing everything that the Simulator normally does, it keeps a list of 'reference meshes' (These are used to efficiently support 'instancing' of meshes using shared resources).

D3D_PhysicalEntity - derived from my CollisionBody class, this object is a replacement for D3D_MeshManaged.

Apart from doing everything that the CollisionBody class normally does, it implements a 'Living Instance' of a Reference Mesh.

If these objects work out for me, I'll probably port all the 'inherited' code (from Simulator / CollisionBody) into them, and eliminate the inheritance layer.

Anyway, it means I'm pretty much ready to start rendering objects on-screen, although there's a fair bit of duplication of resources to eliminate (things like bounding sphere are already in the D3D_Mesh baseclass) and the Simulator needs to be made more friendly to externally-stored entities.

Having done that, I began deriving some new objects based on OA32's D3D_MeshManager and D3D_MeshManaged.

Here's a rundown of my new objects:

D3D_Simulator - derived from my physics Simulator class, this object is a replacement for D3D_MeshManager.

Apart from doing everything that the Simulator normally does, it keeps a list of 'reference meshes' (These are used to efficiently support 'instancing' of meshes using shared resources).

D3D_PhysicalEntity - derived from my CollisionBody class, this object is a replacement for D3D_MeshManaged.

Apart from doing everything that the CollisionBody class normally does, it implements a 'Living Instance' of a Reference Mesh.

If these objects work out for me, I'll probably port all the 'inherited' code (from Simulator / CollisionBody) into them, and eliminate the inheritance layer.

Anyway, it means I'm pretty much ready to start rendering objects on-screen, although there's a fair bit of duplication of resources to eliminate (things like bounding sphere are already in the D3D_Mesh baseclass) and the Simulator needs to be made more friendly to externally-stored entities.

Anyway, it means I'm pretty much ready to start rendering objects on-screen,

Woo-hoo! I'm looking forward to a graphical demo to play around with :)

I've been reading most of your posts in the thread, btw, but since I've never done physics myself I haven't had anything intelligent to say :)

Nvidia claims that PhysX enables super-accurate physics simulation with minimal coding effort and they advertise it by showing how it uses hardware acceleration on "GeForce 200"-series cards. Is this really our future or kinda worthless crap given that the modern CPUs don't have anythig to do, because GFX cards handle like 95% of the rendering process..?

NVIDIA deliberately makes/keeps PhysX slow on the CPU. It doesn't make proper use of SSE, and it doesn't do multi-threading.

The result is quite ironic. In 'software' mode only a fraction of your CPU's true power is used,

*leading to low framerates*, and in 'hardware' mode the CPU is mostly idle while the GPU gets to do graphics

**and**physics,

*leading to low framerates*.

Please note that all the current work is involved in the efficient importing of MESH-based geometries into the simulation.

Arbitrary collision hulls will still be supported: although the PhysicalEntity class supports Loading/Instancing/Rendering

of specific meshes, we can still declare the shape to be used for collision detection

I had to 'retrograde' my D3D_Simulator (formerly D3D_MeshManager), D3D_PhysicalEntity (formerly D3D_MeshManaged) and D3D_SimpleMesh (aka D3D_Mesh) classes.

The public version of MeshManager stores all intances of a reference mesh WITHIN that reference mesh ... if we have several different reference meshes, with instances of each, we end up with several Collections of instances, and that's not very good for collision detection purposes... so I've modified my D3D_Simulator class to store ALL instances (doesnt matter which ref mesh) under a single collection within the Simulator class.

This just means that when we perform 'BroadPhase' collision testing, we're 'touching' less memory pages and can better take advantage of caching in the cpu (less cache misses leading to faster execution).

Another key change I made was to modify the Simulator.AddCollisionSphere method and move/rename it to D3D_PhysicalEntity.SetProperties : we can use this method to set up the physical properties of a meshed body we already instanced, specify whether or not the mesh is HOLLOW (and if so specify the THICKNESS), specify the SHAPE to use for Volume/Mass calculation and NarrowPhase collision detection, and take advantage of the fact that the D3D_Mesh class has already calculated the BoundingSphere for all meshes.

Arbitrary collision hulls will still be supported: although the PhysicalEntity class supports Loading/Instancing/Rendering

of specific meshes, we can still declare the shape to be used for collision detection

I had to 'retrograde' my D3D_Simulator (formerly D3D_MeshManager), D3D_PhysicalEntity (formerly D3D_MeshManaged) and D3D_SimpleMesh (aka D3D_Mesh) classes.

The public version of MeshManager stores all intances of a reference mesh WITHIN that reference mesh ... if we have several different reference meshes, with instances of each, we end up with several Collections of instances, and that's not very good for collision detection purposes... so I've modified my D3D_Simulator class to store ALL instances (doesnt matter which ref mesh) under a single collection within the Simulator class.

This just means that when we perform 'BroadPhase' collision testing, we're 'touching' less memory pages and can better take advantage of caching in the cpu (less cache misses leading to faster execution).

Another key change I made was to modify the Simulator.AddCollisionSphere method and move/rename it to D3D_PhysicalEntity.SetProperties : we can use this method to set up the physical properties of a meshed body we already instanced, specify whether or not the mesh is HOLLOW (and if so specify the THICKNESS), specify the SHAPE to use for Volume/Mass calculation and NarrowPhase collision detection, and take advantage of the fact that the D3D_Mesh class has already calculated the BoundingSphere for all meshes.

I'm trying now to handle better the 'special case' of collision at time T=0

Most of the time, collision will occur somewhere between T=0 and T=PhysicsTimeStep

IE, the Body.NewState is Penetrating, unless we correct it via a response.

If collision occurs at Time Zero, we should IMMEDIATELY resolve the collision, apply the results to the Body, and integrate this Body forwards in time so that its post-collision trajectory can be tested correctly against the other entities.

Fortunately, I'm already collecting collision events in a list that is sorted by Collision Time... so we'll find all these T=0 collisions right at the start of the list... the ResolveCollisions method can deal with these renegades, but if ResolveCollisions detects T=0 collisions, it should ONLY handle these ones, and then cause a secondary call to detect collisions so that we can properly detect subsequent collisions of our renegades, and then make another call to resolve all the pending collisions (including the ones we ignored).

As long as we do all this without actually integrating the whole system forwards in time, the bodies will remain synchronized.

At first it will appear like I'm cracking a walnut with a sledgehammer, but if you think about it, we're integrating BEFORE we detect/resolve collisions, so if something collides at T=0, it HAS no post-collision trajectory for the remainder of the current timestep (since its not APPLIED until the next Integrate call) so we really NEED to fix these, and Integrate them forwards, or they cannot interact for the remainder of this timestep!

Most of the time, collision will occur somewhere between T=0 and T=PhysicsTimeStep

IE, the Body.NewState is Penetrating, unless we correct it via a response.

If collision occurs at Time Zero, we should IMMEDIATELY resolve the collision, apply the results to the Body, and integrate this Body forwards in time so that its post-collision trajectory can be tested correctly against the other entities.

Fortunately, I'm already collecting collision events in a list that is sorted by Collision Time... so we'll find all these T=0 collisions right at the start of the list... the ResolveCollisions method can deal with these renegades, but if ResolveCollisions detects T=0 collisions, it should ONLY handle these ones, and then cause a secondary call to detect collisions so that we can properly detect subsequent collisions of our renegades, and then make another call to resolve all the pending collisions (including the ones we ignored).

As long as we do all this without actually integrating the whole system forwards in time, the bodies will remain synchronized.

At first it will appear like I'm cracking a walnut with a sledgehammer, but if you think about it, we're integrating BEFORE we detect/resolve collisions, so if something collides at T=0, it HAS no post-collision trajectory for the remainder of the current timestep (since its not APPLIED until the next Integrate call) so we really NEED to fix these, and Integrate them forwards, or they cannot interact for the remainder of this timestep!

I've handled part of that special case, and set up an INT 3 trap and a debug message on the unhandled part, if I see it being triggered, I'll deal with it. Found a couple of small memory leaks involving the CollisionPair object (this object is a record of a point-collision, we store them in a Sorted List).

Most important new change is the implementation of a 'sleep' flag... if a Body collides with a fixed World Plane, and the Body has very little pre-collision velocity, we will say that the body is 'at rest', and put it to sleep.

Sleeping bodies will not be Integrated, and cannot be the CAUSE of collisions - bodies which are at rest can only be 'woken' by a collision with another body (which obviously is NOT at rest).

You can probably see that sleeping bodies are much cheaper to deal with... in a game environment which has a lot of physical bodies, we want to spend our cpu time on the MOVING stuff, something that isn't moving SHOULD cost less than something that is moving.

Today I'll be experimenting with my existing code - if all is well, I'll begin implementing code for collision against a fixed Triangle as an introduction to collision against a body composed of moving triangles (mesh body).

I'll be sure to make a post or two about how I detect these collisions, but the collision response will be handled generically by the existing code.

Remember - we need to know about the moment of impact, position in worldspace, and contact normal for each point of impact, the shapes involved are absolutely irrelevant.

Most important new change is the implementation of a 'sleep' flag... if a Body collides with a fixed World Plane, and the Body has very little pre-collision velocity, we will say that the body is 'at rest', and put it to sleep.

Sleeping bodies will not be Integrated, and cannot be the CAUSE of collisions - bodies which are at rest can only be 'woken' by a collision with another body (which obviously is NOT at rest).

You can probably see that sleeping bodies are much cheaper to deal with... in a game environment which has a lot of physical bodies, we want to spend our cpu time on the MOVING stuff, something that isn't moving SHOULD cost less than something that is moving.

Today I'll be experimenting with my existing code - if all is well, I'll begin implementing code for collision against a fixed Triangle as an introduction to collision against a body composed of moving triangles (mesh body).

I'll be sure to make a post or two about how I detect these collisions, but the collision response will be handled generically by the existing code.

Remember - we need to know about the moment of impact, position in worldspace, and contact normal for each point of impact, the shapes involved are absolutely irrelevant.

There's some good news, and some bad news.

For my current testing, I am allowing gravity to whack a single body into a single 'floor plane'.

With friction enabled, the response appears to be perfect under all conditions.

But with NO friction, and with the floor plane tilted on an angle, the collision response is too powerful.

The problem is obviously in the 'CalculateFrictionlessImpulse' method.

Since physics simulation is SO much cooler with friction enabled (we'll pretty much always have it turned on), I'm not that inclined to dig too deeply into this problem right now, however I'll certainly come back to it just for the sake of that warm fuzzy feeling you get when you actually complete what you set out to do.

On the bright side, with friction enabled, I see my body bounce a few times, losing velocity as it does so... eventually it Penetrates the floor plane just once, Penetration Correction occurs, it tries to move just once more, and then it gets put to sleep - I'd say that's damned near to perfect :)

For my current testing, I am allowing gravity to whack a single body into a single 'floor plane'.

With friction enabled, the response appears to be perfect under all conditions.

But with NO friction, and with the floor plane tilted on an angle, the collision response is too powerful.

The problem is obviously in the 'CalculateFrictionlessImpulse' method.

Since physics simulation is SO much cooler with friction enabled (we'll pretty much always have it turned on), I'm not that inclined to dig too deeply into this problem right now, however I'll certainly come back to it just for the sake of that warm fuzzy feeling you get when you actually complete what you set out to do.

On the bright side, with friction enabled, I see my body bounce a few times, losing velocity as it does so... eventually it Penetrates the floor plane just once, Penetration Correction occurs, it tries to move just once more, and then it gets put to sleep - I'd say that's damned near to perfect :)

It is useful to note that a Triangle is ALWAYS FLAT - that is to say, it always rests apon some 3D Plane.

So in order to detect collision between a Triangle and another Body, we begin by testing for collision against that Plane.. if we see collision, we note the intersection point apon the Plane, and then determine whether the Point lays INSIDE THE TRIANGLE, or outside of it.

Here is some code that can tell us whether a Point is inside a triangle, or not... I've commented the code with pseudocode that describes what the code is doing, however I'm not inclined to explain it further.

You can read about Barycentric coordinates in your own time.. suffice to say, this technique is a lot faster than the more common 'which side of all edges does the point lay' technique.

I haven't tested this code yet, however I am confident that it will work correctly.

So in order to detect collision between a Triangle and another Body, we begin by testing for collision against that Plane.. if we see collision, we note the intersection point apon the Plane, and then determine whether the Point lays INSIDE THE TRIANGLE, or outside of it.

Here is some code that can tell us whether a Point is inside a triangle, or not... I've commented the code with pseudocode that describes what the code is doing, however I'm not inclined to explain it further.

You can read about Barycentric coordinates in your own time.. suffice to say, this technique is a lot faster than the more common 'which side of all edges does the point lay' technique.

;This procedure uses the Barycentric technique

;to determine whether the given Point

;is located within the given 3D Triangle

;Returns TRUE/FALSE

;pvPoint = Point to be tested

;pvA = Triangle Vertex A

;pvB = Triangle Vertex B

;pvC = Triangle Vertex C

;

;NOTES : The Barycentric coordinates (u,v) can be

;thought of as 'weights' for linear interpolation along

;the triangle edges AB and AC.

;It is therefore possible to convert these coordinates

;into TEXTURE COORDINATES via linear interpolation

;of the texcoords at the three points of the triangle

IsPointInTriangle proc uses ebx ecx pvPoint,pvA,pvB,pvC

LOCAL v0:Vec3

LOCAL v1:Vec3

LOCAL v2:Vec3

LOCAL dot00:real8

LOCAL dot01:real8

LOCAL dot02:real8

LOCAL dot11:real8

LOCAL dot12:real8

LOCAL invDenom:real8

; Compute vectors

;v0 = C - A

;v1 = B - A

;v2 = P - A

mov eax,pvA

mov ebx,pvB

mov ecx,pvC

mov edx,pvPoint

Vec3_Sub .Vec3, .Vec3

Vec3_Stow v0

Vec3_Sub .Vec3, .Vec3

Vec3_Stow v1

Vec3_Sub .Vec3, .Vec3

Vec3_Stow v2

; Compute dot products

;dot00 = dot(v0, v0)

;dot01 = dot(v0, v1)

;dot02 = dot(v0, v2)

;dot11 = dot(v1, v1)

;dot12 = dot(v1, v2)

Vec3_Dot v0,v0

fstp dot00

Vec3_Dot v0,v1

fstp dot01

Vec3_Dot v0,v2

fstp dot02

Vec3_Dot v1,v1

fstp dot11

Vec3_Dot v1,v2

fstp dot12

; Compute barycentric coordinates:

;invDenom = 1 / (dot00 * dot11 - dot01 * dot01)

;u = (dot11 * dot02 - dot01 * dot12) * invDenom

;v = (dot00 * dot12 - dot01 * dot02) * invDenom

fld1

fld dot00

fmul dot11

fld dot01

fmul st(0),st(0)

fsub

fdiv

fst invDenom

fld dot11

fmul dot02

fld dot01

fmul dot12

fsub

fmul ;invDenom

fstp u

fld dot00

fmul dot12

fld dot01

fmul dot02

fsub

fmul invDenom

fstp v

; Check if point is in triangle

;return (u > 0) && (v > 0) && (u + v < 1)

fld u

fldz

fcompp

fjle @F

fld v

fldz

fcompp

fjle @F

fld u

fadd v

fld1

fjge @F

return TRUE

@@:

return FALSE

IsPointInTriangle endp

I haven't tested this code yet, however I am confident that it will work correctly.

Collision testing for two arbitrary meshes begins with a broadphase swept test of their bounding spheres.

If those collide, a narrowphase test is made for the earliest Time of Impact (TOI).

It is worth noting that just because the Spheres collide, actual collision of the GEOMETRY may not occur - we could have a 'near miss' !!! But let's assume the collision is not a 'near miss'.

Since we have already placed the spheres so they are touching, and since the spheres are generally larger than the mesh they contain, we know that our bodies are either 'just touching', or are damn close to it.

At this point, we can find the CLOSEST FEATURES on both the Bodies, and then iteratively search for the earliest time of impact (or impacts).

We need to find which Points of Body A are closest to which Faces of Body B... we also need to find which Points of Body B are closest to which Faces of Body A.

Having collected this data, we can then integrate 'just these points' within a search loop.

Please note that since a Face is DESCRIBED by a set of Points, so we really only need to deal with points.

To find the closest features, we use the standard 'Distance from Point to Plane' , which involves a DotProduct of the Point and the Normal of the plane, and subtracting of 'PlaneD' (the Plane.w component).

It is possible to accelerate this testing by performing the testing in the Space of one of the Bodies.

Although we still Integrate both Bodies, we only need to Transform the features of the Other body (from its bodyspace, into worldspace, and then into the test bodyspace, via a single Similarity Transform).

As the bodies grow in complexity, this optimization becomes worth ever more to us.

Once we've collected all the collisions that occur at the earliest TOI, we can resolve that manifold as usual.

If those collide, a narrowphase test is made for the earliest Time of Impact (TOI).

It is worth noting that just because the Spheres collide, actual collision of the GEOMETRY may not occur - we could have a 'near miss' !!! But let's assume the collision is not a 'near miss'.

Since we have already placed the spheres so they are touching, and since the spheres are generally larger than the mesh they contain, we know that our bodies are either 'just touching', or are damn close to it.

At this point, we can find the CLOSEST FEATURES on both the Bodies, and then iteratively search for the earliest time of impact (or impacts).

We need to find which Points of Body A are closest to which Faces of Body B... we also need to find which Points of Body B are closest to which Faces of Body A.

Having collected this data, we can then integrate 'just these points' within a search loop.

Please note that since a Face is DESCRIBED by a set of Points, so we really only need to deal with points.

To find the closest features, we use the standard 'Distance from Point to Plane' , which involves a DotProduct of the Point and the Normal of the plane, and subtracting of 'PlaneD' (the Plane.w component).

It is possible to accelerate this testing by performing the testing in the Space of one of the Bodies.

Although we still Integrate both Bodies, we only need to Transform the features of the Other body (from its bodyspace, into worldspace, and then into the test bodyspace, via a single Similarity Transform).

As the bodies grow in complexity, this optimization becomes worth ever more to us.

Once we've collected all the collisions that occur at the earliest TOI, we can resolve that manifold as usual.

I just changed the value for Gravity from 0.86 to 0.9806, and now I am seeing the body escape through the plane - the debug stream shows me that we are detecting zerotime collisions where it should clearly be a penetration correction - not sure whats going on here but I'll get to the bottom of it.

I want my engine to be an out-of-the-box solution, not something that relies on 'tweaks'.

It should be robust, maybe I need to be a little more aggressive in the collision side of things.

I want my engine to be an out-of-the-box solution, not something that relies on 'tweaks'.

It should be robust, maybe I need to be a little more aggressive in the collision side of things.

There were some small bugs in the collision resolution code, just silly stuff really.

Collision Response now works perfectly, with friction disabled OR enabled.

In the latter case, both static and dynamic friction are implemented, which means that bodies interact more realistically, for example causing a sphere to ROLL apon a surface rather than simply SLIDE along it.

Good stuff!

Now I'm ready to start making a real effort to handle arbitrary meshes, which will introduce a new problem to be solved in regards to collision detection and response.

So far, my simulator only works correctly with 'single point of contact' collisions between bodies.

Very soon I will have to deal with 'edge collisions' and 'face collisions', which are a little more complicated.. we can't simply process these simultaneous point collisions sequentially and expect plausible results... can we?

Collision Response now works perfectly, with friction disabled OR enabled.

In the latter case, both static and dynamic friction are implemented, which means that bodies interact more realistically, for example causing a sphere to ROLL apon a surface rather than simply SLIDE along it.

Good stuff!

Now I'm ready to start making a real effort to handle arbitrary meshes, which will introduce a new problem to be solved in regards to collision detection and response.

So far, my simulator only works correctly with 'single point of contact' collisions between bodies.

Very soon I will have to deal with 'edge collisions' and 'face collisions', which are a little more complicated.. we can't simply process these simultaneous point collisions sequentially and expect plausible results... can we?

I'm having trouble sourcing information that I can actually understand in regards to multiple simultaneous contact resolution. If anyone knows of good websites or whitepapers which can help me, I'd certainly appreciate you letting me know.

The major issue for me is the way my CURRENT code works... I currently calculate a 'desired post-collision velocity' based on the impact velocity along the contact normal, then I calculate the impulse that causes a UNIT change in velocity along the normal, and finally I scale the impulse so that it produces my 'desired' velocity.

This approach won't work if there's more than one collision normal - I don't know how to find the 'desired velocity' anymore, and besides that, we have multiple impulses whose torques fight one another, so the linear part of the impulse becomes unclear.

I know that I need to solve this as a simultaneous equation, I'm just not good enough with maths to elegantly describe the problem, much less solve it. I understand this problem falls under the category of "Linear Complementary Problem" (LCP) and normally an iterative approach is taken to find an impulse for each contact that doesn't break the contraints imposed by the other contacts.

Is anyone willing to assist in regards to developing a viable solver without friction? If I can solve the non-friction case I think I can go on and solve the friction case by myself.

The major issue for me is the way my CURRENT code works... I currently calculate a 'desired post-collision velocity' based on the impact velocity along the contact normal, then I calculate the impulse that causes a UNIT change in velocity along the normal, and finally I scale the impulse so that it produces my 'desired' velocity.

This approach won't work if there's more than one collision normal - I don't know how to find the 'desired velocity' anymore, and besides that, we have multiple impulses whose torques fight one another, so the linear part of the impulse becomes unclear.

I know that I need to solve this as a simultaneous equation, I'm just not good enough with maths to elegantly describe the problem, much less solve it. I understand this problem falls under the category of "Linear Complementary Problem" (LCP) and normally an iterative approach is taken to find an impulse for each contact that doesn't break the contraints imposed by the other contacts.

Is anyone willing to assist in regards to developing a viable solver without friction? If I can solve the non-friction case I think I can go on and solve the friction case by myself.