John - 08/07/2009 - Control in a Newtonian Environment

[John]

Hello World!

This is my first developer blog entry for the Excalibur game and NanoFX-Evolved engine and it revolves around controlling a ship in a Newtonian environment (pardon the pun!).

As many of you know, I am the lead programmer of Excalibur and have designed/developed the architecture that supports the quality and flexibility you see now and will soon be exploring through the NanoFX-Evolved engine!

As a developer, having such awesome people making up the programming and art teams really makes all the difference, not just in terms of the final product, but also the journey we are taking to reach it! It would not be possible without you all - so congratulations and award each other cookies!

Now onto the meaty stuff!  Essentially I've been looking for a way to control ships using forces and torques in a true Newtonian system.  This has involved me learning physics, which has in turn thrown up some rather interesting abstractions which people really don't talk about.  For example: Angular momentum does not exist!  It is a lie physics teachers tell you because they don't understand the true reasons things turn.  Luckily however, angular momentum is a pretty neat model so it comes in pretty handy.

Firstly I am going to distinguish between a particle and a body.

• Particle - Something to which physics can be applied but has no size.  A point in 3D space with a given mass.  It is impossible to turn a particle.
• Body - A set of particles that have been stuck together and bound with various atomic forces.  These thus have a "size" and can be visible turned by applying forces at different points on the shape.

It starts to make sense where the term "rigid body mechanics" comes from now.   One of the requirements of the game engine is that it should allow bodies to have different moments of inertia [1].  A moment of inertia is essentially a way of describing how the layout of the particles in a body change the way it rotates.  (For example, a hollow wheel requires less force to rotate at the same speed as a solid wheel.  There is a great article on wikipedia which describes several of these formulae [2]).

To support the requirement of variable moments of inertia and a consistent acceleration value in the hard points (assuming equal moment distributions about the centre of mass in each axis), we require 6 "thrusters" to be placed at the edge of the body in each axis.  To ensure a true rotation (and no movement as a result) it is important that each thruster has an equal and opposite force pushing at the other side of the body.  Newtons laws tell us that the body will remain in the same place in space, but the forces will make the body rotate.

The following equation can be used to apply a force at a point.

Code: [Select]

## Compute the force for a thruster that rolls the ship.
vForceA =  vDirection * fMagnitude
vForceB = -vDirection * fMagnitude

## Compute the torque for this thruster. X = Cross Product.
vTorqueA = vPointA X vForceA
vTorqueB = vPointB X vForceB

## Resolve the forces from this thruster.
vThrusterForce = vForceA + vForceB
vThrusterTorque = vTorqueA + vTorqueB

Ok.. cool!  Do you notice anything we can do here to make things easier?  vForceA and vForceB are equal and opposite and so resolve to the value of 0 (the body does not move, but can rotate!).

Now we want to make the body rotate at a given rate of acceleration.  This is fairly easy because we can use the good old Force = Mass * Acceleration.
We get the following code:

Code: [Select]

## Compute the "strength" of the force required to provide a desired acceleration.
## Note here that our acceleration is simply describing our direction and speed in each axis.
vForce = vAcceleration * fMass

## Compute the torque for this thruster. X = Cross Product.
vTorqueA = vPointA X vForce
vTorqueB = vPointB X -vForce

## Resolve the forces from this thruster.
vThrusterForce = 0
vThrusterTorque = vTorqueA + vTorqueB

Right!  So that's all good. Works a treat.    Here is a screenshot!


The first problem that we run into is that the code is extremely messy, slow and could be a damn site better for each thruster.  Luckily we can simplify the above calculations by doing them in local space (i.e. relative to the model rather than the world).

Lets take a look at a simplified version of the actual code:

Code: [Select]

// Compute the force to be added by this thruster using F = ma.
// We need not apply it to the body because the forces cancel.
Vector3 vForce  = Vector3.Multiply(vAngularAccel, fMass);

// Compute the torque to be applied as a result of applying this force at a point.
Vector3 vTorque = new Vector3(0f, 0f, 0f);

// Roll.
vTorque.Add(Vector3.Cross(new Vector3(vPoint.X, 0f, 0f),      new Vector3(0f, vForce.X, 0f)));
vTorque.Add(Vector3.Cross(new Vector3(-vPoint.X, 0f, 0f),     new Vector3(0f, -vForce.X, 0f)));

// Pitch.
vTorque.Add(Vector3.Cross(new Vector3(0f, vPoint.Y, 0f),      new Vector3(0f, 0f, vForce.Y)));
vTorque.Add(Vector3.Cross(new Vector3(0f, -vPoint.Y, 0f),     new Vector3(0f, 0f, -vForce.Y)));

// Yaw.
vTorque.Add(Vector3.Cross(new Vector3(0f, 0f, vPoint.Z),      new Vector3( vForce.Z, 0f, 0f)));
vTorque.Add(Vector3.Cross(new Vector3(0f, 0f, -vPoint.Z),     new Vector3(-vForce.Z, 0f, 0f)));

Ok... now we can see that there are 15 memory allocations, 39 multiplications and I didn't even bother counting the additions, subtractions and variable assignments.  This will not do!

Luckily we can decompose our cross product call into the following maths:

Code: [Select]

x = Ay * Bz - Az * By;
y = Az * Bx - Ax * Bz;
z = Ax * By - Ay * Bx;

Since we are doing our calculations in local space (i.e. the thruster directions and positions will never impact on the axes other than the ones they deal with), we can basically find the axes for each operation where the value is 0 and remove them from the calculation.

This means the above section of code to compute the torque translates into the following call:

Code: [Select]

// Compute the force to be added by this thruster using F = ma.
// We need not apply it to the body because the forces cancel.
Vector3 vForce  = Vector3.Multiply(vAngularAccel, fMass);

// Compute the torque to be applied as a result of applying this force at a point.
Vector3 vTorque = new Vector3(vPoint.Y * vForce.Z * 2, vPoint.Z * vForce.X * 2, vPoint.X * vForce.Y * 2);

Notice that the *2 is there because the force we apply is as a result of both engines (and we know that a minus times a minus is a plus - so it works out as *2).  2 Memory allocations and 9 multiplications, no additions and considerably less memory copies.



Tips and tricks:
(1) Local space calculations are awesome for optimising things!
(2) Don't just "use the toolkits".  Understand what your code is doing under the hood and decompose your cross products!
(3) Fitting it into an architecture can be tricky and I'm going to cover that in the next blog post thing.

References
[1] http://en.wikipedia.org/wiki/Moment_of_inertia
[2] http://en.wikipedia.org/wiki/List_of_moment_of_inertia_tensors

Next...
In my next post I will describe how I used these mechanisms to provide a nicer interface for the AI and player to control the ships.

John

_{Disclaimer:  I am not a physics person, actually quite the opposite.  You know, the kind of geek who can "get" a physics joke without actually understanding what is funny!  This series of blog entries is based on my own research and tests and should not be used in any sort of safety critical or production environment.  It should be taken as a rough guide, nothing more.}

[MyOwnSling]

Nice!  It's great to see some of the technical workings inside this project and it's nice to see the attention to detail you are giving.  Very well done!

[joe5]

exselent

[szekeres2008]

 I never liked learning physics in school but this article was a good reading, it was easy to understand, can't wait for the next blog entry

[Legacy]

I never liked learning physics in school but this article was a good reading, it was easy to understand, can't wait for the next blog entry

Either John writes it easy or noone in the team beside him will understand it... J/K

[Shinzon]

I always knew my physics teacher was a liar! I should demand a higher mark

[Chris]

I always knew my physics teacher was a liar! I should demand a higher mark

I don't think it works like that

[MyOwnSling]

So how are you going to assign a mass to an object?  Given that you are talking about moments of inertia, it seems like you would have to do more than just assign a lump-value mass to an entire object model (another glance through the blog seems to indicate that the use of hardpoints plays into this).  On a related note, are you going to be going so far as to assign densities to the various different materials that will be represented?  I guess, depending on how you implement the representation of mass, you could end up with implied densities whether you explicitly assign them or not.

[John]

Good questions!

Currently we only have a basic material properties used by the physics engine for computing collisions. While it is possible to compute a volume for each mesh and derive a mass from that, specifying the value by hand gives more control to the modder and keeps things simple.  There is no reason a MPE/Hardpoint application could not offer a "suggested mass" function though.

However, unlike the mass property -a moment of inertia for a mesh will be *optionally* precomputed using the solid rectangle formulae.  The code I am currently using for this pre-computation is as follows:

Code: [Select]

    ## Calculate mass matrix.  Use the formulea for a solid cuboid.  Not optimised for clarity reasons.
    fIxx = (1/12.0) * fMass * (fWidth**2  + fDepth**2)
    fIyy = (1/12.0) * fMass * (fHeight**2 + fDepth**2)
    fIzz = (1/12.0) * fMass * (fHeight**2 + fWidth**2)

    ## Setup mass, position and rotation.
    pShip.setMassMatrix(fMass, fIxx, fIyy, fIzz)

This can easily be overridden in the hardpoints for those modders who want to add that something extra to their ships physics behaviour.

[MyOwnSling]

Ok, that makes sense.  It looks like you are implementing an approximation of a ship's inertial properties, which seems good enough considering how symmetric these ships generally are. Thanks for the good answer 

I have another question if you don't mind.  Will certain weapon types like torpedoes have a mass value?  You never really see the kinetic effect of a torpedo impact portrayed in any of the series (given the explosive force of a torpedo, it probably doesn't really matter anyway), but if a mass value can be assigned to a weapon like that, it opens doors for the implementation of mass-driver type weapons.  Can the engine support something like this?  It seems open-ended enough to, but I'm not the expert.

[Kaempfer]

It's this kind of thing that made me go into the medical sciences. I just find physics boring (at least the mathematics parts, the smashing things into other things part is a blast ). Though I am glad that such care and forethought is being placed into the game, it's stuff like this that makes or breaks a game

[szekeres2008]

 Of course, after all everything the team presented us was absolutely realistic, why not the physics engine?

[FAR]

Will you be adding code for thruster hard points? Or is that just plain silly (20 fps that is)?

[Jon]

I will probably need to add a system for each thruster, this is so the game know its an 'engine' and the manouvering works as expected.

As for visual effects, I'm sure it could be added, if not by us then a modder.