Project 4: Animator Assigned: Tuesday, November 18 Due: Tuesday, December 2 Artifact due: Tuesday, December 9 Project TA: Gary

Quick Links

1. MSVC 6.0 Skeleton
2. MSVC .NET Skeleton
3. Linux Skeleton
4. SP02 Sample 
5. W2K Sample (unexciting particle shower)
6. W2K Sample (much cooler particle system cloth demo)

Table of Contents

• Objectives and overview
• Keyframe animation with curves
• Particle system simulation
• Summary of the requirements
• User interface
• Animation artifact
• Bells and whistles

Objectives and overview

Objectives

In this project, you are required to extend a spline-based animation system to support multiple curve types, and implement a particle system simulation engine. After building a working system, you will use your (robust and powerful) program to produce a (compelling and arresting) animation.

Overview

The skeleton code provided is built on top of the same architecture as the Modeler, and is designed so that you can re-use your models.  If you replace steamshovel.cpp with a working model file from Project 2, you should be able to compile the program and play with the interface. As with the Modeler, this application has two windows: a viewer for the model, and a main window that allows you to manipulate the various model and camera parameters.  If you click on the "Controls" tab in the main window, you will essentially get the Modeler interface, with sliders for controlling components of your character.  The second mode, where you'll be spending most of your time, is the "Curves" mode.  Curves mode is where you edit a time-varying curve for each model parameter by adding and moving control points.  Selecting controls in the left-hand browser window brings up the corresponding curves in the graph on the right.  Here, time is plotted on the x-axis, and the value of a given parameter is plotted on the y-axis.  This graph display and interface is encapsulated in the GraphWidget class.

Keyframe animation with curves

Keyframe animation is one of the most common methods for controlling a hierarchical model.  The idea is to pose the model at select moments in time and then smoothly interpolate between the poses (sometimes called "in-betweening").  The pose is determined by the control parameters (degrees of freedom) of the model, such as joint angles, and each parameter has a separate curve describing how it changes over time.  In practice, you do not need to pose the whole model at each keyframe; you can adjust each curve independently, adding keyframes for that curve as needed.  For this component of the project, you will implement a set of curve types for keyframe interpolation.

Requirements for Animation Curves

You will need to implement each of the following curve types:

• Catmull-Rom
• B-spline

Skeleton Code for Animation Curves

The GraphWidget object owns a bunch of Curve objects. The Curve class is used to represent the time-varying splines associated with your model parameters.  You don't need to worry about most of the existing code, which is used to handle the spiffy user interface.  The one important thing to understand is the curve evaluation model.  Each curve is represented by a vector of control points, and a vector of evaluated points. 

mutable std::vector m_ptvCtrlPts;
mutable std::vector m_ptvEvaluatedCurvePts;

You will manipulate the control points using the GraphWidget interface, and the program will determine the actual shape of the curve from the control points.  In other words, given a set of control points, the system figures out what the evaluated points are.  This conversion process is handled by the CurveEvaluator member variable of each curve. 

const CurveEvaluator* m_pceEvaluator;

In the skeleton, the evaluated curve points appear to be line segments directly connecting each control point.  This is because we've only implemented the LinearEvaluator.  You should use this as a model to implement the other required curve evaluators: B-Spline, and Catmull-Rom.  C⁰ Beziers splines and C²-Interpolating splines can be added for extra credit.  The following section describes in greater detail what you need to do to add a curve.

Adding Curve Types

For each curve type, you must write a new class derived from CurveEvaluator. Inside the class, you should implement the evaluateCurve function. This function takes the following parameters: ptvCtrlPts--a collection of control points that you specify in the curve editor, ptvEvaluatedCurvePts--a collection of evaluated curve points that you return from the function calculated using the curve type's formulas, fAniLength (the maximum time that a curve is defined), and bWrap - a flag indicating whether or not the curve should be wrapped (see bells and whistles for an explanation of wrapping). To add a new curve type, you should look in the GraphWidget constructor and change the following lines to use your new set of evaluator classes.

m_ppceCurveEvaluators[CURVE_TYPE_BSPLINE] = new LinearCurveEvaluator();
m_ppceCurveEvaluators[CURVE_TYPE_CATMULLROM] = new LinearCurveEvaluator();

For Bézier curves (and the splines based on them), it is sufficient to sample the curve at fixed intervals of time. The adaptive de Casteljau subdivision algorithm presented in class may be implemented for an extra bell.

You do not have to sort the control points or the evaluated curve points. This has been done for you. Note, however, that for an interpolating curve (Catmull-Rom), the fact that the control points are given to you sorted by x does not ensure that the curve itself will also monotonically increase in x. We have handled this case for you as well, and our solution is well comented in the code. However, it's important to recognize that, without making special exceptions, Catmull-Rom curves will create these artifacts.

Also, be aware that the evaluation function will linearly interpolate between the evaluated points to ensure a continuous curve on the screen.  This is why you don't have to generate infinitely many evaluated points.

Particle system simulation

1. Particle objects (which have physical properties such as mass, position and velocity)
2. Forces
3. An engine for simulating the effect of the forces acting on the particles that solves for the position and velocity of each particle at every time step

You are responsible for coming up with a representation for particles and forces.  

Requirements for Particle System 

Here are the specific requirements for the particle system:

1. Implement the simulation solver using Euler's method.
2. Create a particle system with at least one force acting on it.  The system should also be tied to your model in some way.   For example, you can have a steam particle system that shoots particles up from the chimney of a moving train.  It would be really cool if the particles initial velocity reflected that of the train when they were created (though it doesn't have to).
3. Using steamshovel.cpp as an example, hook your particle system up to the application.   

Once you've completed these tasks, you should be able to run your particle system simulation by playing your animation with the "Simulate" button turned on. 

There is already a framework in the code for "baking particles" which can be implemented as a bell . If you implement the baking bell, then as you simulate, the position of the particles at each time step are baked so that you can replay your animation without re-simulating.  When you disable simulation, normal animation continues.  The gray region in the white indicator window above the time slider indicates the time for which the simulation has been "baked."   

Skeleton Code for Particle System

The skeleton provides a very basic outline of a simulation engine, encapsulated by the ParticleSystem class.  Currently, the header file (ParticleSystem.h) specifies an interface that must be supported in order for your particle system to interact correctly with the animator UI.  Alternately, you can try to figure out how the UI works yourself by searching within the project files for all calls to the particle system's functions, and then re-organizing the code.  This second option may provide you with more flexibility in doing some very ambitious particle systems with extra UI support.  However, the framework seems general enough to support a wide range of particle systems.  There is detailed documentation in the header file itself that indicates what each function you are required to write should do.  Note that the ParticleSystem declaration is by no means complete.  As mentioned above, you will have to figure out how you want to store and organize particles and forces, and as a result, you will need to add member variables and functions.

One of the functions you are required to implement is called computeForcesAndUpdateParticles:

virtual void computeForcesAndUpdateParticles(float t);

This function represents the meat of the simulation solver.  Here you will compute the forces acting on each particle and update their positions and velocities based on these forces using Euler's method.  As mentioned above, you are responsible for modeling particles and forces in some way that allows you to perform this update step at each frame.  

Particle System As Part of a Hierarchy

One requirement of your particle system is to attach it to a node of your model other than the root.  This requires that you think carefully about about how to represent the positions of your particles. 

Suppose you want to attach a particle shower to your model's hand.  When you apply the force of gravity to these particles, the direction of the force will always be along the negative Y axis of the world.  If you mistakenly apply gravity along negative Y axis of the hand's coordinate space, you'll see some funky gravity that depends on the orientation of the hand (bad!).  To solve this problem, we recommend that you attach a particle emitter (a virtual object that releases particles into the scene) to the model's hand, but store all the particles positions as coordinates in world space.  This means that you'll need to calculate the world coordinates of the particle emitter every time a particle is spawned.

Determining the world space coordinates of the particle in a clean way is actually a little more confusing than one would initially think. this is because the camera transformations are pushed onto the MODELVIEW_MATRIX before and of the transformations related to the model are. You can find some pseudo-code that shows how to do this here, and the ParticleSystem class already has some of the utility functions for this implemented for you.

Hooking Up Your Particle System

In the sample steamshovel.cpp file, there is a comment in the main function that indicates where you should create your particle system and hook it up into the animator interface.  After creating your ParticleSystem object, you should do the following:

ParticleSystem *ps = new ParticleSystem();
...
// do some more particle system setup
...
ModelerApplication::Instance()->SetParticleSystem(ps);

Summary of requirements

• Implement the following curve types:
  • B-spline
  • Catmull-Rom
• Implement a particle system that:
  • is attached to a node of your hierarchy other than the root node.
  • has at least one force acting on the particles.

   

User interface

Graph Widget Interface

After selecting a series of model parameters in the browser window, their corresponding animation curves are displayed in the graph. Each spline is evaluated as a simple piece-wise linear curve that linearly interpolates between control points.  You can manipulate the curves as follows:

 

Command	Action
LEFT MOUSE	Clicking anywhere in the graph creates a control point for the selected curve. Ctrl points can be moved by clicking on them and dragging.
CTRL LEFT MOUSE	Selects the curve
SHIFT LEFT MOUSE	Removes a control point
ALT LEFT MOUSE	Square-region selection of control points (defined by a mouse drag)
RIGHT MOUSE	Zooms in X and Y dimensions
CTRL RIGHT MOUSE	Zooms into a square space region (defined by a mouse drag)
SHIFT RIGHT MOUSE	Pans the viewed region

Note that each of the displayed curves has a different scale. Based on the maximum and minimum values for each parameter that you specified in your model file, the curve is drawn to "fit" into the graph. You'll also notice that the other curve types in the drop-down menu are not working. One part of your requirements (outlined below) is to implement these other curves.

Controlling time

At the bottom of the window is a simple set of VCR-style controls and a time slider that let you play, pause, and seek in your animation. The Loop button will make the animation start over when it reaches the end.  The Simulate button relates to the particle system which is discussed below. 

Controlling the camera

Camera motions can be edited in two ways: 

• Setting Keyframes:  You will use the camera keyframing interface to define some basic camera movements.  The Set button will take the current camera parameters from the viewport and save them as control points in the graph widget.  Typically, you will move the time slider, adjust the camera pose in the viewport, then click Set.  If you want to remove a keyframe, use the time slider to seek to the approximate time of the keyframe, then click "Remove" button.  Remove will delete all camera control points in a narrow range around the current time.
• Editing Curves:  There are 8 camera parameters that appear as the last 8 items in the Model Controls list( Azimuth, Elevation, Dolly, Twist, LookAtX, LookAtY, LookAtZ, and FOV).  Clicking on one of these properties will cause the control points for this curve to appear in the graph widget interface.  From here, you can edit control points and curve types as you can with any other model parameter.  Before you start animating, it's probably worth spending some time familiarizing yourself with how these parameters effect the camera.

Fluid

In the skeleton code distribution, we've included the fluid file for the ModelerUIWindows class (modeleruiwindows.fl).  In addition, we've included the binary for fluid (fluid.exe) so that you can make additions to the UI if you want.  This should probably only be attempted if you want to make really large UI changes.  For minor changes it probably just makes sense for you to make the changes by hand than to learn this new interface.  However should you want to learn how to use Fluid, this is a good place to start.

Animation artifact

You will eventually use your program to produce an animated artifact for this project. There are two main ways to save artifacts.  The first is to make a file redable by animator, called a .ani file.  The second is to output bitmaps for each frame, and then to use an outside program to compile them into a movie.

Making a .ani file:

When you get all your curves just the way you like them, you can go to the File menu of the program.  There is a Save Animation Script As heading there.  This will lead to a simple file chooser menu.  If you save your file as Animator.ani then it will automatically load on opening the program (if it is in the same directory as your program).

Making another kind of movie:

Under the File menu of the program, there is a Save Movie As option, that will let you specify a base filename for a set of movie frames.  Each frame is saved as a bitmap. The Bitmaps can then be compiled in a program such as Adobe Premier (in the lab) into a common movie format, such as a .avi file. IMPORTANT: To get your movie to save correctly, you must add a call to endDraw at the very end of the draw function in your model:

void YourModel::draw()
{
    ...
    // draw your model
    ...
    ...
    endDraw();
}

Here is some more information on how to make .AVI files from animator output.

Other artifact info:

We may give extra credit to those artifacts that are exceptionally clever or aesthetically pleasing. Try to use the ideas discussed in the John Lasseter article in your CoursePak. These include anticipation, follow-through, squash and stretch, and secondary motion. 

Finally, plan for your animation to be 30 seconds long (40 seconds is the absolute maximum).  You will find this is a very small amount of time, so consider this when planning your animation.  We reserve the right to penalize artifacts that go over the time limit and/or clip the video for the purposes of voting.

• Absolute time limit: 40 seconds...shorter is better!
• Animation will count toward final grade on Homework Two.
• Brian and TAs will grade based on technical and artistic merit.

Voting:

• In-class voting on Wednesday 06/12/02
• Special 1st and 2nd place prizes
• Fun runner-up prizes

Bells and whistles

Enhance the required spline options. Some of these will require alterations to the user interface, which involves learning Fluid and the UI framework.  If you want to access mouse events in the graph window, look at the handle function in the GraphWidget class.  Also, look at the Curve class to see what control point manipulation functions are already provided.  These could be helpful, and will likely give you a better understanding of how to modify or extend your program's behavior.  A maximum of 3 whistles will be given out in this category.

• Implement C⁰ cubic Bézier splines by grouping each set of four control points that overlap each other by one control point (to give the desired continuity).  Additional credit is available if you support C¹ continuity as well, with options for selecting either C⁰ or C¹ continuity at any given joint. 
• Let the user control the tension of the Catmull-Rom spline
• Implement higher degree Bézier splines (ones that are C³ or C⁴ continuous)
• Implement one of the standard subdivision curves (e.g., Lane-Riesenfeld or Dyn-Levin-Gregory).
• Add the ability to add a new control point to any curve type without changing the curve at all.

Render a mirror in your scene. As you may already know, OpenGL has no built-in reflection capabilities. You can simulate a mirror with the following steps: 1) Reflect the world about the mirror's plane, 2) Draw the reflected world, 3) Pop the reflection about the mirror plane from your matrix stack, 4) Draw your world as normal.  After completing these steps, you may discover that some of the reflected geometry appears outside the surface of the mirror.  For an extra whistle you can clip the reflected image to the mirror's surface, you need to use something called the stencil buffer.  The stencil buffer is similar to a Z buffer and is used to restrict drawing to certain portions of the screen.  See here for more information.

Particles rendered as points or spheres may not look that realistic.  You can achieve more spectacular effects with a simple technique called billboarding.  A billboarded quad (aka "sprite") is a textured square that always faces the camera.  See here for a demo.  For full credit, you should load a texture with transparency (some sample textures are available here), and turn on alpha blending (see this NeHe turotial for more information).  Hint:  When rotating your particles to face the camera, it's helpful to know the camera's up and right vectors in world-coordinates.

Use the billboarded quads you implemented above to render the following effects.  Each of these effects is worth one whistle provided you have put in a whistle worth of effort making the effect look good.

• Fire (example) (You'll probably want to use additive blending for your particles - glBlendFunc(GL_SRC_ALPHA,GL_ONE); )
• Snow (example)
• Water fountain (example)
• Fireworks (example)

Use environment mapping to simulate a reflective material.  This technique is particularly effective at faking a metallic material or reflective, rippling water surface.  See here for more information on the algorithm.  Note that OpenGL provides some very useful functions for generating texture coordinates for spherical environment mapping.  Part of the challenge of this whistle is to find these functions and understand how they work.

Add baking to your particle system.  For simulations that are expensive to process, some systems allow you to cache the results of a simulation.  This is called "baking."  After simulating once, the cached simulation can then be played back without having to recompute the particle properties at each time step.  See this page for more information on how to implement particle baking.    

 Implement a motion blur effect (example).  The easy way to implement motion blur is using an accumulation buffer - however, consumer grade graphics cards do not implement an accumulation buffer.  You'll need to simulate an accumulation buffer by rendering individual frames to a texture, then combining those textures.  See this NeHe tutorial for an example of rendering to a texture.

Euler's method is a very simple technique for solving the system of differential equations that defines particle motion.  However, more powerful methods can be used to get better, more accurate results.  Implement your simulation engine using a higher-order method such as the Runge-Kutta technique.  See here (Numerical Recipes, Sections 16.0, 16.1) for a description of Runge-Kutta and pseudo-code.

The linear curve code provided in the skeleton can be "wrapped," which means that the curve has C⁰ continuity between the end of the animation and the beginning.  As a result, looping the animation does not result in abrupt jumps.  You will be given a whistle for each (nonlinear) curve that you wrap, see here.  

Implement adaptive Bézier curve generation; i.e., use a recursive, divide-and-conquer, de Casteljau algorithm to produce Bézier curves, rather than just sampling them at some arbitrary interval. You are required to provide some way to change these variables, with a keystroke or mouse click.  In addition, you should have some way of showing (a printf statement is fine) the number of points generated for a curve to demonstrate your adaptive algorithm at work.  If you provide visual controls to toggle the feature, modify the flatness parameter (with a slider for e.g.) and show the number of points generated for each curve, you will get an extra whistle.

Extend the particle system to handle springs. For example, a pony tail can be simulated with a simple spring system where one spring endpoint is attached to the character's head, while the others are floating in space.  In the case of springs, the force acting on the particle is calculated at every step, and it depends on the distance between the two endpoints.  For one more bell, implement spring-based cloth.  For 2 more bells, implement spring-based fur.  The fur must respond to collisions with other geometry and interact with at least two forces like wind and gravity.

Allow for particles to bounce off each other by detecting collisions when updating their positions and velocities.  Although it is difficult to make this very robust, your system should behave reasonably.

Implement a "general" subdivision curve, so the user can specify an arbitrary averaging mask  You will receive still more credit if you can generate, display, and apply the evaluation masks as well.  There's a site at Caltech with a few interesting applets that may be useful.

Add a lens flare.  This effect has components both in screen space and world space effect.  See here for what's involved.  For full credit, your lens flare should have at least 5 flare "drops", and the transparency of the drops should change depending on how far the light source is from the center of the screen.  You do not have to handle the case where the light source is occluded by other geometry (but this is worth an extra whistle).

If you find something you don't like about the interface, or something you think you could do better, change it!  Any really good changes will be incorporated into the next Animator.  Credit varies with the quality of the improvement.

Add flocking behaviors to your particles to simulate creatures moving in flocks, herds, or schools.  A convincing way of doing this is called "boids"  (see here for a demo and for more information).  For full credit, use a model for your creatures that makes it easy to see their direction and orientation (for example, the yellow/green pyramids in the boids demo would be a minimum requirement).  For up to one more bell, make realistic creature model and have it move realistically according to its motion path.  For example, a bird model would flap its wings when it rises, and hold it's wings outstretched when turning.

Implement a C²-Interpolating curve.  There is already an entry for it in the drop-down menu.  C² interpolating curve notes by Bartels, Beatty, and Barsky (in your course reader as well) will probably be helpful.  More credit is available if you allow the user to specify the derivatives at the two endpoints of your C² interpolating curves.

Add the ability to edit Catmull-Rom curves using the two "inner" Bézier control points as "handles" on the interpolated "outer" Catmull-Rom control points. After the user tugs on handles, the curve may no longer be Catmull-Rom.  In other words, the user is really drawing a C¹ continuous curve that starts off with the Catmull-Rom choice for the inner Bézier points, but can then be edited by selecting and editing the handles.  The user should be allowed to drag the interpolated point in a manner that causes the inner Bézier points to be dragged along.  See PowerPoint and Illustrator pencil-drawn curves for an example.

Implement picking of a part in the model hierarchy.  In other words, make it so that you can click on a part of your model to select its animation curve.  To recognize which body part you're picking, you need to first render all body parts into a hidden buffer using only an emissive color that corresponds to an object ID.  After modifying the mouse-ing UI to know about your new picking mode, you'll figure out which body part the user has picked by reading out the ID from your object ID buffer at the location where the mouse clicked.  This should then trigger the GraphWidget to select the appropriate curve for editing.  If you're thinking of doing either of the inverse kinematics (IK) extensions below, this kind of interface would be required.  

If you implemented twist for your original model, the camera movement for your old modeler can give some unexpected results.  For example, twist your model 90 degrees.  Now try to do rotations as normal.  This effect is called gimbal lock and we'll likely discuss it in class.  Change the camera to use quaternions as a method for avoiding the gimbal lock.

Implement projected textures.  Projected textures are used to simulate things like a slide projector, spotlight illumination, or casting shadows onto arbitrary geometry.  Check out this demo and read details of the effect at glBase, nVidia, and SGI.

An alternative way to do animations is to transform an already existing animation by way of motion warping (animations). Extend the animator to support this type of motion editing.

We've talked about rigid-body simulations in class.  Incorporate this functionality into your program, so that you can correctly simulate collisions and response between rigid objects in your scene.  You should be able to specify a set of objects in your model to be included in the simulation, and the user should have the ability to enable and disable the simulation either using the existing "Simulate" button, or with a new button.;

Disclaimer: please consult the course staff before spending any serious time on these. They are quite difficult, and credit can vary depending on the quality of your method and implementation.

Inverse Kinematics: The hierarchical model that you created is controlled by forward kinematics; that is, the positions of the parts vary as a function of joint angles. More mathematically stated, the positions of the joints are computed as a function of the degrees of freedom (these DOFs are most often rotations). The problem is inverse kinematics is to determine the DOFs of a model to satisfy a set of positional constraints, subject to the DOF constraints of the model (a knee on a human model, for instance, should not bend backwards).

This is a significantly harder problem than forward kinematics. Aside from the complicated math involved, many inverse kinematics problems do unique solutions. Imagine a human model, with the feet constrained to the ground. Now we wish to place the hand, say, about five feet off the ground. We need to figure out the value of every joint angle in the body to achieve the desired pose. Clearly, there are an infinite number of solutions. Which one is "best"?

Now imagine that we wish to place the hand 15 feet off the ground. It's fairly unlikely that a realistic human model can do this with its feet still planted on the ground. But inverse kinematics must provide a good solution anyway. How is a good solution defined?

Your solver should be fully general and not rely on your specific model (although you can assume that the degrees of freedom are all rotational). Additionally, you should modify your user interface to allow interactive control of your model though the inverse kinematics solver. The solver should run quickly enough to respond to mouse movement.

If you're interested in implementing this, you will probably want to consult the CSE558 lecture notes.

Interactive Control of Physically-Based Animation: Create a character whose physics can be controlled by moving a mouse or pressing keys on the keyboard.  For example, moving the mouse up or down may make the knees bend or extend the knees (so your character can jump), while moving it the left or right could control the waist angle (so your character can lean forward or backward).  Rather than have these controls change joint angles directly, as was done in the modeler project, the controls should create torques on the joints so that the character moves in very realistic ways.  This huge bell requires components of the rigid body simulation extension above, but you will receive credit for both extensions as long as both are fully implemented..  For this extension, you will create a hierarchical character composed of several rigid bodies.   Next, devise a way user interactively control your character.  

This technique can produce some organic looking movements that are a lot of fun to control.  For example, you could create a little Luxo Jr. that hops around and kicks a ball.  Or, you could create a downhill skier that can jump over gaps and perform backflips (see the Ski Stunt example below).

SIGGRAPH paper - http://www.dgp.toronto.edu/~jflaszlo/sig2000.pdf

Several movie examples - http://www.dgp.toronto.edu/~jflaszlo/interactive-control.html

Ski Stunt - a fun game that implements this bell - http://motionplayground.com/sss/

If you want, you can do it in 2D, like the examples shown in this paper (in this case you will get full credit for this component, but half credit for the rigid body component).