generalrelativity

The next release of the Flash Player has support for 2.5D- which boils down to 3D properties, appropriate perspective, but no depth sorting. This method takes a DisplayObjectContainer, transforms its children into world space and sorts them along that z-axis. It’s sloppy because it’s DisplayObject-based and so there will be noticeable “pop” when a DisplayObject is sorted onto the top of the display list in close proximity to another. That said it should be perfect for carousels and other views that aren’t super tight.

Here’s a demo

And here’s the algorithm:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

public static function simpleZSort3DChildren( doc:DisplayObjectContainer, recurse:Boolean = true ) : void
{
 
    //transforms from local to world oordinate frame
    var transform:Matrix3D = doc.transform.getRelativeMatrix3D( doc.stage );
 
    var numChildren:int = doc.numChildren;
 
    //v = ( n * 3 )- (x,y,z) set for each child
    var vLength:int = numChildren * 3;
 
    var vLocal:Vector.<Number> = new Vector.<Number>( vLength, true );
    var vWorld:Vector.<Number> = new Vector.<Number>( vLength, true );
 
    //insertion point for child’s coordinates into state vector
    var vIndex:int = 0;
 
    for( var i:int = 0; i <numChildren; i++ )
    {
 
        var child:DisplayObject = doc.getChildAt( i );
        if( recurse && child is DisplayObjectContainer ) simpleZSort3DChildren( DisplayObjectContainer( child ), true );
 
        vLocal[ vIndex ] = child.x;
        vLocal[ vIndex + 1 ] = child.y;
        vLocal[ vIndex + 2 ] = child.z;
 
        vIndex += 3;
 
    }
 
    //populates vWorld with children coordinates in world space
    transform.transformVectors( vLocal, vWorld );
 
 
 
    //bubble sorts children along world z-axis
    for( i = numChildren - 1; i > 0; i-- )
    {
 
        var hasSwapped:Boolean = false;
 
        vIndex = 2;
 
        for( var j:int = 0; j < i; j++ )
        {
 
            //z value at that index for each child
            var z1:Number = vWorld[ vIndex ];
 
            vIndex += 3;
 
            var z2:Number = vWorld[ vIndex ];
 
            if( z2> z1 )
            {
 
                //swap
                doc.swapChildrenAt( j, j + 1 );
 
                //swap z values (don’t need to change x and y because they’re not used anymore)
                vWorld[ vIndex - 3 ] = z2;
                vWorld[ vIndex ] = z1;
 
                //mark as swapped
                hasSwapped = true;
 
            }
 
        }
 
        //if there was no swap, we don’t need to iterate again
        if( !hasSwapped ) return;
 
    }
 
 
}

This is the first in a series of quick tutorials on helpful maths, physics and algorithms, and their ActionScript implementations. Today we’re going to learn how to shoot a projectile out of the sky. Sweet.

DEMO

First, let’s define the algorithm’s structure. We’re going to pass the time to collision. The algorithm will return the muzzle velocity that our projectile requires to hit a moving target out of the air after this specified amount of time.

function solveMuzzleVelocity( timeToImpact:Number ) : Vector

Next, we have to define the equations of motion:

x1 is a particle’s position after t seconds. x0 is the original position and the dots represent the first and second positional derivatives (velocity and acceleration, respectively). This equation allows us to solve for position after any specified time (given constant acceleration). Referring to our algorithm’s structure, we know t (timeToImpact) to be defined. This means that we can determine where the target will be when we hit it, which gives us a point of impact:

//point of impact
var poi:Vector = target.position.plus( target.velocity.times( timeToImpact ) );
poi.plusEquals( new Vector( 0, Projectile.G * timeToImpact * timeToImpact * 0.5 ) );

It’s assumed that the only accelerative force is gravity (Projectile.G here), that we know the starting position of the target and our projectile, and the current velocity of the target.
Plugging this point of impact in for our projectile’s equation of motion (as x1), we eliminate all unknowns except the muzzle velocity. Through basic algebraic manipulation, we can isolate and solve for this unknown:

Finally, divide each side of the equation by t:

The algorithm will return this value. Here’s my implementation, in full:

1
2
3
4
5
6
7
8
9
10
11
12
13

private function solveMuzzleVelocity( timeToImpact:Number ) : Vector
{
 
    //point of impact
    var poi:Vector = target.position.plus( target.velocity.times( timeToImpact ) );
    poi.plusEquals( new Vector( 0, Projectile.G * timeToImpact * timeToImpact * 0.5 ) );
 
    var diff:Vector = poi.minus( projectile.position );
    diff.y -= Projectile.G * timeToImpact * timeToImpact * 0.5;
 
    return diff.dividedBy( timeToImpact );
 
}

Super simple! Now you can integrate dynamically and knock some shit out of the sky.

Here’s a verbose implementation that doesn’t use my Vector class and isn’t dependent on my application:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

private function solveMuzzleVelocity( t:Number, xp:Point, xt:Point, vt:Point, pixelToMeterRatio:Number = 40 ) : Point
{
 
    const g:Number = 9.81;
    var vDotTerm:Number = g * pixelToMeterRatio * t * t * 0.5;
 
    var poiX:Number = xt.x + vt.x * t;
    var poiY:Number = xt.y + vt.y * t + vDotTerm;
 
    var diffX:Number = poiX - xp.x;
    var diffY:Number = poiY - xp.y - vDotTerm;
 
    return new Point( diffX / t, diffY / t );
 
}

t is time to impact, xp holds the x and y coordinates of the projectile’s starting position, xt is the target’s starting position, vt is the target’s starting velocity and pixelToMeterRatio defines how many pixels represent one meter.

I’m sorry that this took so long- especially those of you who’ve written me and patiently waited for my help with rendering… I simply don’t have as much time as I would like. Anyway- this will offer a solution for rendering your FOAM physics simulation with:

• Drawing API (SimpleFoamRenderer)
• BitmapData (BitmapFoamRenderer)
• DisplayObjects (DisplayObjectFoamRenderer)

Here’s a very silly demo- Mouse down anywhere to switch from the DisplayObject renderer to the Bitmap renderer.

demo
source

Note that these new renderers are meant as example only- I do think in most cases the developer will need a more specific setup than I could hope to generically offer. So consider this my implementation and at best a nudge in the right direction.

Hopefully both of these will be fairly self-explanatory, but I’ll briefly go over the DisplayObject renderer and what my thinking was when addressing this issue.

I wanted a means to render a DisplayObject (base class of Sprite, MovieClip etc.) that’s the visual representation of a RigidBody being simulated. I knew that I’d like to be able to pass either the DisplayObject’s Class or the instance itself. I also knew that I’d need an easy way to adjust the position of the DisplayObject- so first, I wrote a datatype to hold these properties- DisplayObjectData.

You’ll see that it has a setter for defining its displayObject property. This is what facilitates passing either a DisplayObject Class or a DisplayObject instance. The other properties:

• offsetX – the amount to offset the DisplayObject from its origin in the x direction
• offsetY – the amount to offset the DisplayObject from its origin in the y direction
• autoCenter – Boolean indicating whether to center the contents about the origin- Because of the way a RigidBody rotates about its center of mass, I figured this would be typical.
• hasBeenDisplayed – a helper Boolean for determining whether to perform the indicated transformations

In Rocket.as, you can see the way I’m embedding my visual assets:

[Embed(source="../../../bin/images/rocket/lunarPod.png")]
private var rocketSpriteClass:Class;
 
[Embed(source="../../../bin/images/rocket/asteroid.png")]
private var asteroidSpriteClass:Class;

If this is unfamiliar with you, simply note that it’s analogous to the classes you’re instantiating as MovieClips in Flash CS3. As you’ll see in a moment, it’s not necessary to pass the Class, we can pass the DisplayObject instance as well.

Here’s how I’m passing the class to FOAM to tie it to to a RigidBody. Note that the instance of DisplayObjectData simply defines Foam.addElement’s renderData argument.

foam.addElement( rocket, true, true, new DisplayObjectData( rocketSpriteClass, 0, -5 ) );

Compare this with how I’m creating the asteroid (I wanted to scale the asteroid, or else I’d have created it in the same way as the rocket- it worked out well for the purpose of demonstration):

var asteroidSprite:DisplayObject = new asteroidSpriteClass();
asteroidSprite.scaleX = asteroidSprite.scaleY = size / 64;
var asteroid:Circle = new Circle( sx, sy, size, size * 4, svx, svy, 0.5, 0.25, 0, -0.1 + Math.random() * 0.2 );
foam.addElement( asteroid, true, true, new DisplayObjectData( asteroidSprite ) );

There’s one last important thing to note in the Rocket example class. Because I don’t want to use the default FOAM renderer, I have to tell it which renderer to use:

foam.setRenderer( new DisplayObjectFoamRenderer() );

Now let’s move on to DisplayObjectFoamRenderer. Note that I’ve chosen to extend SimpleFoamRenderer so that I don’t have to rewrite drawing routines for objects I don’t have graphics for (such as the mouse dragger bungee). You’ll see my use of the DisplayObjectData properties in the addRenderable method.

So- ultimately all of this boils down to 3 lines of code which line up our DisplayObject with our RigidBody:

displayObject.x = ISimulatable( renderable.element ).x;
displayObject.y = ISimulatable( renderable.element ).y;
if( renderable.element is IBody ) displayObject.rotation = IBody( renderable.element ).q * 180 / Math.PI;

It places the DisplayObject at the x and y coordinates of the RigidBody’s center of mass. Because rotation is given in radians, we have to convert to an angle which is what DisplayObject.rotation expects.

And that’s pretty much it; for the most part a FOAM renderer is bookkeeping. It might suit you far better to just maintain reference to your DisplayObject and update it every frame just as I am in the above 3 lines of code… simply set render to false in Foam.addElement.

This article walks through my implementation of modeling orbit with FOAM. The content lays a groundwork which could be used to simulate (a ridiculously simplified version of) our solar system for instance. It has 2 main goals:

1. Give the reader a solid and quick understanding of how one might use FOAM specifically.
2. Exemplify the difference between differential equation solvers.

Orbit Demo
FOAM source

When wanting to create physically realistic animation using FOAM, the first step will often be deciding how to develop the forces required to create the desired motion. Forces in FOAM are primarily handled via modular implementations of IForceGenerator- which simply dictates that the method generate generates a force for its passed element. Gravity in the context of our atmosphere and friction are 2 force generators included in the source.

But how would we go about modeling the force an extremely massive object exerts on another?

Firstly, we need to define an equation which ultimately yields a force that we can apply. Newtonian gravity offers the simple force equation:

• F is the force we’re solving for
• G is a gravitational constant
• m1/m2 are the masses of the bodies in question
• r is the distance between the bodies

It should be clear from looking at this equation that the larger the mass, the shorter the distance, the greater the force- which is about as complex as we need to go to get realistic looking results. One simplification we’ll make is assuming that the body exerting the gravitational force is so much larger than the body being acted on, that we can neglect the force acting back on it.

This is simple enough, but we need to translate Newton’s equation into a form our physics engine can execute- We need to create a new force generator. We’ll look at what’s going on in its constructor and generate method; the class in its entirety can be found here.

First, the constructor takes the element we want to exert the force and gravitationalConstant- this is a magic number that should be tweaked per simulation:

1
2
3
4
5

public function GravitationalForceGenerator( source:ISimulatable, gravitationalConstant:Number = 1.2 )
{
   this.source = source;
   g = gravitationalConstant;
}

I’ve left out some error checking for the sake of brevity here- reference the complete class. Next we implement generate:

1
2
3
4
5
6
7

public function generate( element:ISimulatable ) : void
{
   //find the difference vector
   var diff:Vector = source.position.minus( element.position );
   //add our solved force along the difference vector to the supplied element
   element.addForce( diff.getUnit().times( g * source.mass * element.mass / diff.dot( diff ) ) );
}

Line 6 contains our equation for universal gravitation as discussed above. The change worth noting here is that the force is applied in the direction of the exerting body (GravitationalForceGenerator.source). We do this by normalizing the bodies’ difference vector, and scaling it by the force found in Newton’s equation. Note also that the dot product of a vector and itself is its squared magnitude- this is how we’re finding the square of the bodies’ distance- the equation’s right-hand side denominator.

Now let’s look at how I’ve used this force generator in the context of a FOAM application. Remember that we’re also going to examine the difference between IODESolvers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

//create a source of the gravitational pull
var source:Circle = new Circle( 400, 300, 60, 10000 );
 
//create an element influenced by source's gravitational pull to be integrated with the Euler IODESolver
var eulerOrbital:Circle = new Circle( 700, 300, 30, 100, 0, -7 );
//create an element influenced by source's gravitational pull to be integrated with the RK4 IODESolver
var rungaKuttaOrbital:Circle = new Circle( 700, 300, 30, 100, 0, -7 );
 
//create the gravitational force generator
var gravity:GravitationalForceGenerator = new GravitationalForceGenerator( source );
 
//add this to each orbital
eulerOrbital.addForceGenerator( gravity );
rungaKuttaOrbital.addForceGenerator( gravity );
 
//add each element to FOAM (no collisions)
foam.addElement( source, false, true, { color:SimpleOrbit.SOURCE_COLOR, alpha:1 } );
//specify the use of our Euler solver
foam.addElement( eulerOrbital, false, true, { color:SimpleOrbit.EULER_COLOR }, new Euler( eulerOrbital ) );
//RK4 is default, no need to explicitly set
foam.addElement( rungaKuttaOrbital, false, true, { color:SimpleOrbit.RK4_COLOR } );

The important aspects here are:

• we create a new GravitationalForceGenerator and add it as a force generator to each of our orbiting bodies, setting our source Circle as its source.
• the orbitals are created with identical masses, positions and initial velocities (tangent to desired orbit at location)
• one orbital gets added with FOAM’s default solver, RK4- the other with an explicitly defined Euler solver.

The whole SimpleOrbit class can be found here.

If you take a look at the demo, you’ll notice that slowly but surely the orbital being integrated with our Euler solver drifts out of desirable orbit. It will continue to spiral outward. If we set the number of iterations we allow the engine to use per frame to 1, you would see that this error accumulates faster. If instead, we set the iterations to 100 for instance, its orbit would match the more precise RK4-integrated orbital much longer.

So why is this happening? To better explain, I’ll steal some images and description from an earlier post of mine- reference the Euler and RK4 classes also.

At every step in time in which we evaluate state and derivative, the forces acting on our orbiting bodies is different. If we were able to do this evaluation an infinite number of times every frame, Euler would provide the correct answer. This is obviously impossible and so even though the forces acting on the body continually change, we’re limited to apply the force found at a single moment in time across the entire interval over which we’re integrating.

The line segment piercing the starting point represents the derivative. Because Euler simply advances the equation via this derivative, it should be easy to see why it is so error prone. Compare this with how RK4 works:

Because it uses the slope at multiple points over the interval to evaluate the ultimate derivative, our approximation using RK4 is entirely more accurate. This accuracy comes at a cost- RK4 is very much more expensive to calculate- although if you tried the different iteration suggestion I made, you’d see it is more accurate at 3 iterations than Euler is at 100. This is one of FOAM’s strong points- it lets you choose the solver best suited for a specific task within a simulation.

Hopefully this has been helpful in understanding both how to solve a problem with FOAM and what the different integrators are useful for. Future releases will include many more solvers.

Sorry for the super lame demo graphics- another early article will detail the implementation of a decent FOAM renderer.

Re-zipped up the source after making numerous bug fixes and adding a new example. This fixes the clumsy, problematic way I was removing elements across the board. Check it out here.

I also put the documentation up on my server and will keep it up-to-date.

• googlecode project hosting with svn repository
• zipped source

I’ve been working on FOAM off and on in my spare time for the past few months. Recently I’ve been working on solving constraints on a global level- which is no easy task. I decided to work laterally for a bit and get a release out.

FOAM is primarily intended as a resource for developers interested in simulating physics. It has a carefully thought out OOP structure and modular design. A savvy developer should have no problem extending and repurposing FOAM to his own ends. The Foam datatype is in fact not a physics engine but an interface for simulating physics. It offers a simple means to create, control and run a simulation- it purposefully keeps the more nitty gritty, behind-the-scenes operations shielded from the casual developer. A physics engine is simply part of its composition.

I think the best way to use FOAM as a resource for creating physics simulations is to look through the source. I did a decent job commenting and use fairly descriptive variable names. When I set out working on simulating rigid body physics, I didn’t find one comprehensive resource- an article would be helpful here, a tutorial there, but then the matching source would be a comment-less single-letter-variable mess. Also- not coming from a mathematical background, the often obtuse-sounding descriptions in articles can be daunting. In practice, seemingly complex equations can translate to very simple algorithms in the world of computers. I hope that FOAM bridges some of these gaps.

Over the next few weeks, I’ll be posting tutorials and examples- Please let me know of anything that interests or confuses you and what you think in general!

simple demos included in source:

• Perpetual Fall
• Zero G Toy Chest

I updated my tutorial on dynamic circle collision detection in Flash to demonstrate a more physically realistic reaction. Reaction is given only to illustrate how to implement the results of the detection scheme, but is physically viable.

I started work on a 2D rigid body physics engine that I’ll be releasing as open-source. There are a few AS3 physics engines out there- Fisix, APE, the unreleased Motor… and while I’m sure this will fill a few holes, I’m most interested in it being a resource for developers wanting to simulate physics, as I’ve had trouble finding a comprehensive source of the hows and whys.

Here’s a demo. Use left and right arrow keys to spin the wheel. You can grab the movable objects and toss them, too.

As it gets further into development I’ll write some tutorials to explain some of the engine’s inner-workings etc.

Current Features:

• Rigid body simulation
• Arbitrary convex polygons
• Circles
• Cubic Bezier curves
• Lines
• Constraints
• Springs
• Bungees
• Easily swappable numerical integrators
• RK4
• Euler
• Midpoint
• Separation Axis Theorem based collision detection
• Modular force generation

Next up is splitting collision detection into coarse and fine phases via spatial partitioning.

Oh- and I’m calling it FOAM.

Sorry to everyone who posted comments- in my inexperience, generalrelativity got inundated in spam sauce!! It was so cumbersome that I had to dump all comments from the database… I’ve learned my lesson.

Also- I intend to write a TON over the next couple months.

For my billions of readers out there whose lives hinge on my every word, I’m sorry; I haven’t had a half-ounce of time to do anything, notleastofwhich ride this stallion. I was busy legally binding my bank account to m’lady’s- Wall Street Journal listed it as one of the most important mergers of ’07.

I doubt anyone who stumbles across generalrelativity actually cares, but it was, quite seriously, the greatest time I’ve ever and probably will ever have.