Close Window

Print Story

Star Trek Technology for Java3D

The Star Trek universe has inspired many technology ideas but I'm disappointed I don't have a transporter yet. One Star Trek technology that has been available for sometime is the particle system. No, this is not an exotic propulsion system for your flying car. The particle system was invented to animate the Genesis effect in Star Trek II: The Wrath of Khan. While the Genesis device was used to transform a barren planet into one full of life, we can adopt this technology for more modest effects in Java3D.

In the Beginning
In previous articles, we've focused on creating planetary surfaces with Java3D. One challenging area of graphics programming is rendering irregular or ill-defined objects like clouds, smoke, or fireworks. William Reeves faced that challenge when Lucasfilm was asked to create a planetary creation effect called the Genesis effect for Star Trek II: Wrath of Khan. The idea was that a planet would be hit with a missile that would transform it from a barren wasteland into one full of life. Explosions and flames on a planetary scale gave birth to a new form of animation called a particle system.

Reeves' original paper (see references) describes a particle system as one defined by clouds of primitive particles or points in three dimensions. These particles change and move with time making a particle system dynamic. How a particle changes or moves is based on a controlled stochastic process giving it a natural look. How particles evolve in a particle system is called the particle life cycle.

Your morning shower is just like a particle system. Particles are born and emitted by the system. Where the particles are born and where they are headed is assigned by the particle system. Your plumbing system determines the water temperature and velocity of the droplets. Particles exist and change under the influence of external forces. The room temperature and gravity affect how the water changes temperature and where it collides with you or the tub. So where does that fancy stochastic process come into play? To make the rate of particle emission, ejection angle, velocity, or any other attribute more interesting we need to vary them in slightly unpredictable ways. Reeves described the approach of adding a randomly selected variance to the central value of an attribute:

Attribute = CentralAttibuteValue + Random() * AttributeVariance

This approach can be applied to just about any attribute of the particle or the particle system. Figure 1 provides a simple example. The particle system evolves over time by repeating a series of steps and varying the attributes along the way. The steps are:

  1. New particles are initialized and emitted using varying attributes.
  2. Particles past their life expectancy die and are removed.
  3. Surviving particles are updated based on external forces, velocity, etc.
  4. The particles are rendered.
This cycle is repeated until the particle system has no more particles or lives beyond its lifetime. That's all you need to know to get started building a particle system, so let's build one for Java3D.

Transporting to Java3D
Before we build the particle system in Java3D, let's lay out the objectives. First of all, the particle system should be easy to add to the scene graph just like any other Java3D shape. We should allow the Java3D TransformGroup to be used to position and orient the particle system. The design should allow us to use anything from pixels to Shade3D objects for our particles. The particles should be emitted from a variety of nozzle shapes and be affected by external forces like wind or gravity. These objectives should give us the flexibility to graduate from simple water fountain particle systems to tornado simulations. Before we jump straight into an F5 tornado, let's get a simple spray working.

Figure 2 is a subset of a design that satisfies our particle system objectives. It's probably easiest to describe it from the bottom up so let's start with the Particle object. This obviously represents a particle in the particle system and logically maintains its position, velocity, and acceleration. I used the word "logically" because I am fibbing a bit to make it easier to describe. A ParticleEmitter object emits particles and controls the movement of the particles as you might expect. The particle emitter delegates the initial position of particles to a GenerationShape object. During the animation cycle, ExternalInfluence objects such as Gravity affect the particles. All of these objects are independent of Java3D so they could be used in other environments as well. Now I'm going to fess up about the particle location. The location of a particle is actually maintained by the particle emitter. This is done so that the locations of all particles can be shared in one array for use in a Java3D specific Shape3D implementation of a particle system.

Do You Have a Point, Spock?
So far we have satisfied just a few of our objectives. Let's use the particle emitter to make a single Shape3D particle system. We can do this by making ParticleSystem a subclass of the Shape3D class and using a PointArray for the geometry. Luckily for us, the particle emitter has a float array of particle locations that will fit nicely into a PointArray. This geometry class is about the simplest supported by Java3D, accepting a float value for each x, y and z location of the point. The geometry needs to change as the particles move so this means that this particle system should implement the GeometryUpdater interface. If you're not familiar with how to change the geometry of a Java3D shape during runtime, refer back to my previous article ("Casting Perlin's Movie Magic in Java3D" [JDJ, Vol. 10, issue 3]) for an overview. The last piece of the design is the ParticleSystemManager that is responsible for notifying the particle systems to run through their life-cycle steps. Before we dig into the details of how it works, have a look at two of the examples included in the source code and shown in Figure 3.

The particle system is created in Listing 1. The particle emitter is created with a point generation shape having a spread angle of 45 degrees, and specific central and variance values for emission rate, initial velocity, and particle lifetime. We fade the particles by adding the FadePoint influence to the particle emitter (one of many influence objects included in the source code). This influence gradually changes the transparency of the particle as it ages. Now the particle system is created with the emitter and a green particle color. Adding the particle system to the scene graph is not shown due to space constraints, but it's added just like any other Java3D shape. Finally the particle system manager is added to the scene graph and the animation begins.

The ParticleSystemManager is a Java3D behavior that notifies all active particle systems after a specified time has elapsed. I covered behaviors and their use in animation in my previous article so refer back to it if you need a refresher. This implementation uses a combination of elapsed frames and time to create a stable animation cycle. The particle system manager starts and maintains the Reeves particle system life cycle.

Emit New Particles
The particle system manager notifies the particle system that enough time has elapsed. This time is typically less than 50 milliseconds. The emitter determines how many particles need to be initialized and emitted based on the emission rate, emission rate variance, and the amount of time since the last notification. The speed of the particles is initialized based on the velocity and velocity variance while the generation shape determines the initial location. The generation shapes in the source code include point, line, disk, and radial shapes. Particles are assigned a lifetime using the same central value plus the variance approach used for other attributes.

Bury the Dead Particles
During the previous cycle, particles were aged based on the elapsed time. Now the particles that have exceeded their lifetime are collected and recycled for future emissions.

Update the Surviving Particles
The remaining particles are aged, changed by any external influences, moved, scaled, and rotated. Aging simply increments the age of the particle based on the elapsed time. External influences can affect visual characteristics such as color or transparency, or physical attributes such as scale, acceleration, velocity, or position. Updating physical attributes does involve a bit of physics, but hopefully it hasn't been too long since your last physics class.

As part of applying the influences, the accelerations are accumulated from each influence. For example, there may be a Gravity and Wind influence affecting the particles. Gravity would obviously apply a downward acceleration while wind would apply a horizontal acceleration. These accelerations and the existing velocity and position are used to move the particle. The particle is moved in the following method:


public void move(float dt) {
float[] position = getLocalPosition();
Vector3f v = getLocalVelocity();
Vector3f a = getLocalAcceleration();
v.scaleAdd(dt, a, v);
// Scale add not used with position
// to reduce number of objects created.
float x = position[0] + vx * dt;
float y = position[1] + vy * dt;
float z = position[2] + vz * dt;
setLocalPosition(x, y, z);
}

This implementation uses Euler's approach to numeric integration. This approach works for us provided the time differential (dt) between frames is small. The ParticleSystemManager controls the elapsed time so we can ensure the time differential is small. Other approaches to numeric integration such as Modified Euler, Heun, or Runge-Kutta could be used if we needed more accuracy for our particle simulation.

Because we are currently dealing with point particles, we'll skip scaling and rotation for now since these make little sense for points.

Render the Particles
This step is trivial in Java3D because the previous step changed the location of the points representing the particles. The previous step updated the geometry of the particle system shape using the GeometryUpdater interface and Java3D renders the new positions for us. As the particle system life cycle evolves, the position of the particles changes, creating the animation. Because we are dealing with points, some simulations can be disorienting unless we introduce motion blur.

It's All a Blur
You've probably seen motion blur when the Enterprise goes to light speed. Motion blur on film can occur when the subject moves quickly while the camera shutter is open. While you probably don't want the blur when taking photographs, motion blur makes animation look more lifelike and increases the perceived frame rate. How can we take our particle system to the next level and add motion blur?

Remember that each cycle of the particle system life cycle is repeated after a very short elapsed time. If we treat the elapsed time as an open camera shutter, then we want to blur the particle movement during this elapsed time. During the elapsed time, the particle moves from one location to the next. If a line segment is used instead of a point, we can connect the previous location with the new location and vary the transparency of the line to create the blur as depicted in Figure 4.

The MotionBlurredParticleSystem implements motion blurred points using the Java3D LineArray geometry array class. The ParticleEmitter supports both the previous and current location of the particle, enabling the particle system to use this information to create the line segments. The blurring is accomplished by assigning colors to the end points of the lines with different alpha values. The current location has a fully opaque alpha value while the previous location has a fully transparent alpha value. Java3D takes care of smoothly interpolating the transparency of the line, conveniently creating the motion blur for us.

Light Speed, Mr. Sulu!
Using points and motion-blurred lines for particles in Java3D performs very well. Several thousand particles can be used simultaneously on modest hardware with reasonable performance. I pushed my antiquated one-gigahertz machine to run three motion-blurred particle systems consisting of 8635 particles, gravity, and particle bouncing at 14 frames per second. The 14 frames per second is not stellar; it looks terrific with the blurring. Clearly the advantage of using points or lines is that they are fast and allow the use of thousands of particles. The disadvantage to using points or lines is the lack of scale. Each particle is one pixel in size regardless of the distance from the viewer. While you can change the pixel size of the particles via the PointAttributes and LineAttributes, the particles are still all the same size. Ideally our particles should have scale and, for performance sake, reduce the need for a large number of particles. An approach to solving these issues is to make the particles full-blown Java3D shapes. With this approach we can create fantastic effects like the tornado shown in Figure 5.

We Need More Power, Scotty!
Let's extend our particle system design to incorporate Shape3D particles. We still want to easily add the particle system to the Java3D scene, and reuse as much of what we've done up to this point. Recall that our particle systems use an emitter to control the initial position and velocity of the particles. The point and motion blurred particle systems deal with pixel size particles so we'll have to create a new type of particle system to handle Java3D shapes. So far, the particle systems have been Shape3D objects, so how can particles be any Shape3D object? Java3D supports the aggregation of shapes into a Group.

As you can see from Figure 6, the Shape3DParticle-System is a subclass of the Java3D Group class to allow shapes to be grouped together into a particle system. By implementing the IParticleSystem interface, the Shape3DParticleSystem can use the particle emitter unchanged. To help organize and control the shapes, the shape particle system maintains a scene graph segment for each shape in the particle system. Each shape has a scene graph segment consisting of a branch group to maintain membership in the particle system and a transform group to control the location, scale, and rotation of the shape.

Because particles are born and die during the particle system life cycle, shapes must be added and removed from the scene during the animation. Java3D limits the changes to the content of live scene graphs to branch groups. Provided the group (the particle system) has the ALLOW_CHILDREN_EXTEND and the ALLOW_CHILDREN_WRITE capabilities set and the branch group has the ALLOW_DETACH capability set, the branch group and its children can be added or removed from the scene. For our purposes, the only child of the branch group is a transform group. The transform group maintains the standard Java3D translation, scale, and rotation attributes of its child shape in a Transform3D object. With this structure in place, let's briefly review the Reeves life cycle for our new shape particle system.

Emit New Particles
From Figure 6 you can see that the shape particle system implements the IParticleLifeCycleListener interface. The particle emitter notifies listeners as particles evolve through their lifetime. This notification can be used to create additional effects such as spawning additional particle systems. Just before particles are emitted, the aboutToEmit() method is called on the listener, passing a list of particles to be emitted. The shape particle system reflects the initial particle position in the transform group and adds the branch group, transform group, and shape to the scene.

Bury the Dead Particles
When the particle emitter is ready to bury dead particles, it notifies listeners of their impending demise by calling the aboutToDie() method. The shape particle system takes the news pretty well by removing the branch group for the particles from the particle system, removing the shapes from the scene. To reduce object creation, the shape, transform group, and branch group are recycled for a future reincarnation.

Update the Surviving Particles
While particles are alive, the particle emitter applies the influences and the particles are moved, scaled, and rotated. After the particles have been updated by the particle emitter, it notifies the listeners by calling the updated() method. The shape particle system reflects the new particle position, scale, and rotation in the transform group. We discussed how linear acceleration and velocity of a particle can affect its new position, but how about rotation?

Slicker Than Euler
Realistic rotation of Shape3D particles with Euler angles can be mathematically intensive and computationally expensive. I'll try to keep the math to a minimum but if you are interested in the details, have a look at the references. If you have read much about three-dimensional graphics, you've probably already heard of Euler angles. An example of Euler angles is the yaw, pitch, and roll used to describe the orientation of an airplane. There are a few problems with using Euler angles that make them difficult to use for animation.

The order in which Euler angle rotations are applied can result in different orientations. While applying the rotations, a degree of freedom can be lost to something called a "gimbal lock". Over the course of multiple rotations, numeric corrections are often needed to keep the rotational animation looking good. Too make matters worse, it's computationally expensive to interpolate between orientations. Chris Hecker summed it up pretty well: "It's possible to prove that no three-scalar parameterization of 3D orientation exists that doesn't suck, for some suitably mathematically rigorous definition of suck." I did say that I would try to keep the math to a minimum. While Euler angles are easy to understand, we need something that overcomes the weaknesses of using Euler angles for rotational animation. This is where something called a quaternion can save the day (see the sidebar: Pop Quiz Hot Shot).

A quaternion is an extension to complex numbers consisting of a vector and a scalar. There's no use trying to picture a quaternion because it exists in four-dimensional space. In the spirit of keeping the math to a minimum, let's review the key features of quaternions. A unit length quaternion is perfect for representing a rotational orientation of an object. Java3D supports a unit quaternion with the Quat4f class. As the name implies, it consists of four floating-point numbers to make up the vector and scalar components of the quaternion. It's straightforward to convert Euler angles to a quaternion as shown in Figure 7.

Performing successive rotations with quaternions is as easy as multiplying them together. When compared to the traditional rotational matrix approach, quaternion multiplication (the details of which we won't cover here) and orientation interpolation is much more efficient, making it ideal for animating our rotating particle shapes. To animate the rotation, we need to specify the angular velocity in the vector portion of a quaternion. The angular velocity quaternion used to calculate the time differential of a quaternion is shown in Figure 7. The time differential can be used to interpolate quaternions, which helps us spin objects. That was probably the world's shortest description of quaternions, so be sure to review the references if you need more detail. Let's put this new knowledge to work in our shape particle system.

When shape particles are about to be emitted, the orientation is assigned through the use of Euler angles. The angular velocity is also assigned using the now familiar central value and variance approach discussed above. The orientation and angular velocity is converted into quaternions by the particle. When the particle is updated, the quaternion differential is calculated using the time interval of the particle system manager as described in Figure 7. Finally, the new orientation quaternion is set on the Transform3D of the shape along with the new position and scale and Java3D rotates the shape.


Vector3f translation = new Vector3f();
translation.set(aParticle.getLocalPosition());
aTransform3D.set(aParticle.getOrientation(),
translation, aParticle.getScale());

Quaternions are put to work in the ColorCubeParticleSystemExample example. This example uses the Java3D ColorCube utility class for the rotating particles and includes the Gravity and BounceShape influences. When running the example, note how the spinning is affected by the collision with the ground. There is a bit of physics at work in the BounceShape influence to calculate the torque of the impact and the resulting spin. You can see that the influences provide an extension point to begin adding physical simulation aspects to the particle system. You can add your own Java3D shape as a particle by creating a factory and assigning it to the particle system as shown in Listing 2.

How about simulating some weather? Clouds as particles would be a powerful tool for steam, smoke, and even a tornado. However, You might be thinking, "But a cloud would take thousands of particles!" All it takes is one particle with just the right shape, an implicit shape to be precise.

Implicit Surfaces
Java3D excels at rendering objects with distinct geometries. How can we render difficult to describe electron density fields, flames or clouds? Complex organic or other vaguely defined objects can be rendered with an approach called implicit surface modeling. This approach is known by several names in the literature including blobby molecules, metaballs, and soft objects. We'll use the term implicit surface because the shape of the object is implicitly determined by a function such as a sphere or ellipsoid. The implicit function is combined with other attributes to create the resulting object. For example, a spherical function can implicitly determine the shape of a cloud without making the cloud look like a ball. Vaguely defined objects like clouds cannot be defined with triangles, but with a visual trick called a billboard as shown in Figure 8.

A billboard is a geometrically flat image whose orien-tation is aligned with the view. You might know bill-boards better as sprites from older computer games. Games like Doom used eight different views for each monster, showing the appropriate image on the billboard based on the direction the monster was heading and the direction the player was facing. You never saw the edge of the image because the billboard was always oriented along a vertical axis to face the player. Java3D includes support for billboards with the Oriented-Shape3D class.

OrientedShape3D goes beyond the Doom-style sprites to include any geometry with orientation about either an axis or a point. You might consider using an axis-oriented OrientedShape3D object if the user cannot move above the object and look down on it. Doing so would spoil the illusion since they would be able to see the image on edge. For this article, we'll use point-oriented OrientedShape3D objects so that they face the user regardless of the view position. We will use a flat geometry, but through the use of textures, transparency, and vertex normals, we'll be able to give the oriented shapes the feeling of depth.

Our overall strategy to implement implicit surfaces is to combine the material color and transparency with an alpha-enabled texture on an OrientedShape3D object as shown in Figure 9. The implicit surface is a sphere and our flat geometry slice of the sphere is a circle. The first texture is fully opaque within the sphere and fully transparent outside of the sphere. The ambient material color is combined with the MODULATE texture mode and vertex normals to create the fake sphere. While the geometry of the implicit surface is a flat QuadArray, the vertex normals are based on the implicit sphere. You can see from the rendered object that Java3D lights the flat geometry as though it is a real sphere. While this may not be a practical use of implicit surfaces, it does demonstrate the effectiveness of the approach. By varying the texture transparency based on the distance from the center of the sphere, we can create a fuzzy ball as shown in the second example. The final example uses the same varying transparency with Perlin noise-based turbulence texture to create a cloud.

The source code includes the ImplicitSurface, Fake-Sphere, FuzzyBall and CloudPuff classes to implement the examples in Figure 9. The ImplicitSurface class extends OrientedShape3D to support the others. The CloudPuff class can be used to implement volumetric fog without our particle system. Because these are all Java3D shapes, they can be used as particles in our shape particle system to create awesome special effects.

Implicit Surface Particles
Implicit surface particles depend heavily on transparency and rendering these objects takes additional care. Java3D logically renders our scene back to front based on the position of the view. This means that visible distant objects are rendered first and the closest objects are rendered last. This depth sorting ensures that the closer objects properly obscure the more distant objects. Ordinarily Java3D draws all of the opaque objects back to front, followed by the transparent objects. The transparent objects are not depth sorted and look incorrect when we use our transparent particles. Java3D depth sorts transparent objects if we call the following method on the view object:

setTransparencySortingPolicy(View.TRANSPARENCY_SORT_GEOMETRY)

Using this sorting policy correctly sorts transparent objects back to front. Now we can use our implicit surface particles to create more advanced examples.

Use Enough Dynamite There, Butch?
The source code included with this article includes several destructive examples worth mentioning. The tornado in Figure 5 was accomplished with the combination of three particle systems. The TornadoExample includes a particle system for the swirling clouds, the twisting funnel, and the resulting debris. Additional destruction is possible with fire as shown in Figure 10.

The FlamesExample combines the use of ridged fractal noise and light-emitting particles to create a real-time fire. The implicit surface particles are textured with a variety of Perlin noise to create the flame. The particle system shoots the particles straight up while shrinking the particles and making them more transparent as they age. Invisible Phantom particles are used to move and dynamically attenuate point lights to make the fire appear to flicker. The BlackHoleExample sucks asteroids into a black abyss by using the Attract influence. And finally, everything we have done is demonstrated in the explosive finale shown in Figure 11.

The ExplosionExample combines most of the features of our particle system into one example. The example begins with a lit stick of dynamite next to large boulder. The fuse burns as a motion blurred point particle system. When the fuse is gone, the boulder explodes with dust, spinning rocks, fire, smoke and lights combined to complete the effect.

Acknowledgments
I would like to thank Ben Moxon and Brad Myers for reviewing this article. Star Trek is a registered trademark of Paramount Pictures. Doom is a registered trademark of id Software.

References

SIDEBAR

Pop Quiz Hot Shot
What is a Quaternion?
a) A resident of the planet Quatern
b) A rogue protein responsible for Bad Programmers Disease
c) A mathematical representation of the rotational position of rigid bodies
d) An elementary particle found in high energy collisions of animated characters

Answer: c. Invented by Sir William Rowan Hamilton in 1845. Quaternions are supported by Java3D, but barely documented.

© 2008 SYS-CON Media Inc.