CS 428 - Fall 2011 Project 3: Modeling and Animation Due electronically: Wednesday, November 16th, 12 noon (The image and MPEG movie are due the following Monday, November 21) Check this page frequently for updates and clarifications (Significant changes or clarifications are marked with [Update])

Description

The automatic generation of objects and their motions is required in applications such as games or simulations. This generation starts with a model of a particular phenomena (in this case: rocks, trees, or wandering motion). Ideally, this model takes into account knowledge such as the object's formation, growth, or biomechanics, to produce a greater degree of realism. More typically, such information simply inspires an approach to procedural generation.

Objective

From this assignment, you will understand how structures such as trees and rocks can be generated using procedural methods. You will also implement a behavior-based approach for animating some crawling bugs (where only the leg motions are keyframed).

Program

You will be provided with skeleton code for this program, which supplies the necessary user interface and main program structure. The basic data structures for the rock, tree and bug are provided for you, which you must complete in particular places. You will also need to create the "scene" which contains any number of rocks, trees or bugs. You will mostly be filling in the missing parts in functions (which are marked with "// ..."). In some cases, you will find code that is a placeholder for what you need to write (so that you at least see something where the tree and rock are) -- just remove it once you start on that part. In addition, you will probably have to add code elsewhere, and not just where the comment markers are. So don't feel confined by where these comments are placed; they're a guide.

The skeleton code for this project can be found (on the iLab machines) in the directory
      ~decarlo/428/proj3/
Also included is a Makefile.

This assignment is a bit vague so that you can make a lot of the design decisions yourself. There are several approaches to the problems here. Use your best judgement to try and get the most useful result. Ask for help or clarification when you need it.

Handing in

Hand in the following:

1. all of your java files (no class files please)
2. your makefile
3. a description file descrip.txt
4. a still frame in PPM format and an MPEG movie (see the section below)
   Hand in the image and movie separately from the rest of your program. There is a separate hand-in for it.
   Pick any still frame from your animation (save one of the PPM files from /tmp; the first one in there is just fine)

You will need to create a tar archive to hand in, that contains your java files, Makefile, and description:

   tar cf proj3.tar Makefile *.java descrip.txt

This assignment is a bit vague so that you can make a lot of the design decisions yourself. There are several approaches to the problems here. Use your best judgement to try and get the most useful result. Ask for help or clarification when you need it.

Program use

To simply run the program with default options:     java Main

There are a number of command line options available (italicized words indicate you need to specify a particular value):

• -speed TimeSpeed
  Time passes in the program by a factor of TimeSpeed. If you want to view the animation in slow motion, say 4 times slower, then you use a TimeSpeed value of 0.25. Values greater than 1 speed up the animation. The default value is 1.

• -seed RandomSeed
  This value is used to seed the random number generator Random(). By providing the same seed twice, the program will run exactly the same way, regarding the sequence of random numbers generated. If unspecified, the program automatically generates its own seed (printed out, in case you want to know it). Typically, this will only be used for debugging (to make the same thing happen again), or if you like a particular scene it generated, and want to view it again.

• -nice
  When the scene is built, higher quality trees and rocks are generated (and perhaps more of them). The animation will probably run too slowly (although not really less than one frame per second). When saving images to make a movie, it doesn't have to run in real-time, so this is ok. It is up to you to produce a more complex scene based on this value in Scene.build().

• -dump
    or
  -dump DumpFilePrefix
  Used when you want to make a movie of an animation. When you specify this command line switch, the window is set to 320x240 resolution (so the movie file doesn't get too big), and whenever the scene is animated, each frame is saved in a file given by the DumpFilePrefix, with a particular number added on to the filename given the frame number. The default prefix is /tmp/your-userid/image, which is used when you do not provide a DumpFilePrefix. For example, if your userid is decarlo, the first image generated would be /tmp/decarlo/image0000.ppm. No matter how much elapsed time has passed, each frame is computed as if they were 1/30 of a second apart (so you don't have to worry about your program running fast enough when it is making a movie). Use the image viewing program eog to examine the image files.
  Be sure to create your dump directory first!

For example, to run the program in "nice" mode with the seed value of 37:
    java Main -nice -seed 37

Once the program is running, you can transform the scene, turn on/off animation, or reset the scene.

Making MPEG Movies

It's easy to make MPEG movies of your animations. You should not only do this when your program is completed, but also during its development to record any interesting or amusing "out-takes".

An example movie/image pair are in ~decarlo/428/proj3.mpg and ~decarlo/428/proj3.ppm

The "-dump" command-line switch described above is used to save a numbered series of images. You can use "ppmtompeg" to build an MPEG animation file from these images (type "man ppmtompeg" to see brief documentation). Instead of reading about the details of the encoder, you can use the pre-made encoding file, which tells the encoder where the files are, and how they are to be constructed. All you will need to do is edit the top of the file.

The sample encoding file is on cereal in:    ~decarlo/428/encode.txt

Copy this file into your directory. The first few lines of this file specify the input and output files as:

  OUTPUT          anim.mpg

  INPUT_DIR       /tmp/decarlo

  INPUT
  image*.ppm [0000-0299]
  END_INPUT

Remember that "/tmp" is on the local machine, so that when you log in somewhere else, the images you left won't be there. Plus, if a machine reboots, your images in "/tmp" on that machine will probably be lost. It's also not a bad idea to clear everything out of that directory each time you make a movie, so you don't confuse which files you just created.

In the above example, the encoder will use the files "/tmp/decarlo/image0000.ppm" through "/tmp/decarlo/image0299.ppm" to produce an mpeg file called "anim.mpg". It uses 300 files: at 30 frames per second, this animation will last for 10 seconds.

If you want to include only a sub-range of the images (say you only wanted to use [0060-0209]), use the image viewing program "eog" to figure out which ones. If you load many images at once using "eog *.ppm", then you can advance to the next/previous one using the left/right mouse buttons (the scroll wheel works too). A useful trick to see every 10th image is to run "eog *0.ppm".

Once you're done, you can play your MPEG animations using "xine anim.mpg".

In summary:

1. If dumping for the first time on a particular machine:
      mkdir /tmp/your-userid
2. java Main -dump    (let the animation run for the duration you want.)
3. ls -lt /tmp/your-userid    (to determine the largest indexed file)
4. Update the encode.txt file
5. ppmtompeg encode.txt    (this might take a while)
6. xine anim.mpg
7. mv anim.mpg new-name.mpg    (if you want to keep it)

• Move the camera in close enough so that you get a clear view of the action in the scene.
• If you move the camera while recording the animation, do it very slowly and uniformly so that it looks smooth in the final animation. It's probably best not to move the camera.
• Don't let any other windows on your screen cover up your program while it is generating images. (If you do, what you overlapped with it will appear in the result).
• Don't make a really long animation -- the file is very big, and it probably won't be all that exciting.

Data structures

The rocks are represented using the Rock class. It contains information about the location and size of the rock, and it stores a two-dimensional array of height values.

The trees are represented using the Tree class, which contains information about the location of the tree, as well as a recursive data structure from the class TreePart which stores the branches and leaves of the tree as a hierarchical model.

Instances of Rock and Tree also implement the Obstacle interface, so they can be treated uniformly as scene objects when drawn, and when doing bug computations (obstacles should be avoided by bugs).

The bugs are represented using the Bug class, which is an extension of the Critter class. (This way, if you want to add another type of critter, it won't be too hard.) The keyframes for the bug are stored in the Bug class, although the Critter.keyframe() method is used to compute the current bug parameters given the time. The state (position, velocity, acceleration) is stored in Critter, which is also where you should compute accelerations, and do the numerical integration for the bug simulation.

The scene is represented using the Scene class, and stores the obstacles and critters in the scene, and has methods which you will need to complete which create and simulate the scene.

Requirements

The following is a description of what you must do for this project.

• Rock: For the rock, you need to compute the geometry; the data structure for storing the rock is already there, along with code that draws it. The rock is represented using a polygon mesh, but the x and y values are equally spaced, and all we need to store are the z values of the vertices, and nothing about the mesh connectivity. This is called a height field. Looking at Rock.getRockPoint should be enough for you to figure out how this is stored. (Rock.getRockNormal uses a heavily simplified formula for the averaged normal vectors on a height field; see this maple code if you're curious how it was derived.)

  There are two 2-dimensional arrays: Rock.height stores the height values, and Rock.locked stores flags that are used to initialize the rock. If a locked value is true, then your code should not change the corresponding height value. This allows the center of the rock to be initialized off the ground, which gives the rock it's rough shape. See Rock.compute for details.

  You need to complete Rock.computeFractal which is a recursive function that uses random midpoint displacement (of only the height values), as discussed in class. See § 8.23 of the textbook, starting on pp. 480 for details. When working on this, you might consider not adding a random offset at first, as it's easy to have errors here. If you do this, your rock should look like a smooth pyramid, no matter how finely the mesh is created. Also, don't forget that the rock is translated down a bit to yield a more interesting boundary, so you might need to look below the ground plane to see what's happening. Once you complete this part, uncomment the line in Scene.draw that is enabling the clipping plane (which will hide the junk below the ground plane).

  The rock is created in Scene.build, and you should make adjustments there (for instance, use a finer mesh).

  Methods affected: Rock.compute(), Rock.computeFractal(), Scene.build()

• Tree: Create a procedurally generated tree consisting of branches (cylinders) and leaves (each is a polygon). An instance of TreePart (which represents a single branch substructure or leaf) should store the transformation required to place itself with respect to its parent (yes, this is a recursive data structure too). Figure out what transformations you need (having a fully general affine transformation here is overkill; just figure out what translations and rotations you need to properly place a tree's parts). The data structure is not a general scene-graph. But rather each component of a tree (TreePart) stores its modeling transformation with respect to its parent. (The location of the tree in the world is stored in Tree.)

  Most of the coding is in class TreePart. (In fact, you probably will only change Tree by adding arguments to the constructor, as you'll need more flexibility in defining your tree).

  You need to complete the TreePart constructor which creates a particular tree sub-structure (where the argument depth is zero to represent a leaf -- the base case, and a larger value for branches -- the recursive case; the object type is represented in each TreePart with a flag called leaf). TreePart.draw is the method to draw a tree substructure. You need to apply a transformation to place the part, as well as write code to draw a leaf and the children.

  Your tree should not have a regular structure -- it should have some non-trivial randomness in it (vary the branching factor, the length of branches, or the placement of child branches along the parent's limb, throughout the entire tree). This should be done using the methods discussed in class. § 8.23 of the text describes a similar algorithm, applied to 2D displays.

  Methods affected: TreePart.TreePart(), TreePart.draw(), Scene.build()

• Bug: Create a bug that is animated using behaviors that keep it close to the center of the scene (the origin) so it doesn't wander off, and avoid the objects in the scene (rocks, trees). To make it more interesting to watch, it should also occasionally move in some other direction (a new "goal" location is generated every few seconds). The accelerations for the bug are computed during Scene.process using various methods in Critter that compute accelerations due to obstacles or drag (for stability).

  That method should call Critter methods that compute accelerations, and then call Critter.integrate to update the current position based on the acceleration and velocity. Instead of taking one large time step (based on however much time has passed since the last computation), you need to break it down into several smaller steps to prevent numerical errors; so you will need to compute accelerations and integrate many times in succession each time you call process. When you run the program with a higher speed (using a command line argument -speed 5 for instance), the integration will need to take larger steps. As you turn up the speed, the program should remain stable (although if you do it enough, the animation will be choppy as the simulation can't proceed fast enough to be real-time anymore -- that's unavoidable).

  To draw the bug in the correct position (and orientation, based on its velocity, so that it's facing the right way) you will need to complete the Bug.transform method. It's easiest to use Math.atan2() when computing the orientation of the bug, as it computes an angle in a 360 degree range. The bug drawing is already done for you in Bug.draw (the bug is facing in the positive x direction). The legs of the bug are specified with keyfames. Implement the Bug.keyframe method to compute the current set of bug parameters given the current time. Note that the keyframes are only provided for times in the range [0,1]; this is because the walking is cyclic, and has a cycle length of 1 second.

  When writing Bug.keyframe, do not assume that there will be 4 keyframes in one cycle, or that the keyframes within a cycle are evenly spaced in time. Keep your implementation general. You can easily check that you've done this right by running the program at slow speed (using a command line argument -speed 0.1 for instance). Zoom in and check that the legs are moving smoothly and uniformly.

  The rate at which the bug's legs move should depend on the speed the bug is traveling, and the size of the bug. This means you should not use the current time as the argument t to Bug.keyframe, but rather distance traveled taking the size of the bug (Bug.scale) and the length of its stride for unit scale (Bug.stride).

  You only need to have 1 bug (see extra credit about having more).

  See the notes from class [PDF].

  Methods affected: Bug.transform(), Bug.keyframe(), Critter.integrate(), Critter.accelDrag(), Critter.accelAttract(), Scene.process() Scene.build()

• Scene: Create a number of scene elements (several rocks, and at least one tree, and one bug) in Scene.build(). Make sure they all are non-overlapping. It's ok if you explicitly specify positions for all of the scene elements (see extra credit below for an alternative). Don't make the scene too complicated so that it runs slowly. Your animation will start to look jumpy if you do this -- and the framerate (the FPS display is the frames per second) will drop below 10 or so. Keep the framerate around 30. However, when -nice is specified, you should make the scene more complicated (shoot for the range 2-5 fps).

  Update the critter positions in the scene in Scene.process() where you implement the behaviors that ensure that the bug avoids the obstacles, yet stays in the scene.

  The scene is drawn so that x is forward, y is right, and z is up.

  Methods affected: Scene.build(), Scene.process()

Extensions

The following is a list of optional extensions. The first two are required for graduate students.

• [Required for CS grad students] [Easy]
  Implement the "Bug Cam" option, for displaying a bug's eye view of the world. (This checkbox is already there). Just apply the required transformation to do this in Scene.transformation(). To get a better effect, make the field of view much larger, in WorldView.projection().

• [Required for CS grad students] [Medium]
  Add several other bugs to the scene, and make sure they don't collide with each other. Still, one of the bugs should be the primary bug (distinguished as Scene.mainBug), used for Bug Cam, for instance. One possibility is to have the other bugs be smaller (baby bugs!), and have them follow the primary one. If you want to implement flocking/herding, you can read the paper below for more details (you don't need to do this, though).

• [Easy] Add simple shadows to your scene by drawing dark polygons ever so slightly above the ground in the right shape. You can do this easily by putting just the right projection matrix on the modelview stack, and re-drawing the trees and bug (in black, with lighting off). A discussion on what projection matrix to use is in the OpenGL programming guide, and is also available here as PDF. The shadows should be placed based on the location of the light source.
  You'll need to use glMultMatrix (see the JOGL notes about matrices), which gets passed a double-dimensioned array (a 4x4 matrix) in the Java interface. Also, it's ok if you don't have shadows caused by rocks.

• [Easy] Add a predator bug that chases the ordinary bugs (add a new critter, and make it look quite different from the current bug). No need to actually have any of the bugs get eaten though -- just chased.

• [Easy] Randomly place the objects in your scene, so they aren't always in the same place; make sure they don't overlap.

• [Medium] Add a command-line option for "The Little Prince" world , where the instead of a flat plane, the ground is a medium-sized green sphere. (It should be easy to turn this option off, and run your program the regular way). The elements of your scene should be drawn normal to the sphere's surface. The bug no longer has to be attracted to the middle of the scene, and should move around the sphere's surface. Can you get your tree looking a little like a baobob? (Also, you can't draw shadows on the sphere using the trick above; so you'll have no shadows in this scene).

• [Hard] Have your bugs plan their paths, so they don't look so dumb all the time. Planning the next second or two of motion will make a big difference. Don't make it optimal, or it won't run in real-time without a lot of work!

• Feel free to add additional features other than those listed here. The book has some nice material that isn't too difficult to code. Or you can put extra effort into implementing the required features (beyond what is required).

Hints

The following are some suggestions...

• Don't worry too much if your bug, on rare occasion, slightly collides with an object. This is a problem with behavior-based methods. It should happen only rarely, though, and only for particular scenes.
• You should be using the random number generator class, Random to generate values sampled from from uniform and Gaussian distributions.
• This needs to run in real-time, so avoid creating unnecessary objects using new in the animation loop. Garbage collection takes time, and can cause your smooth animation to have occasional little jumps. If you do create objects, set them to null when you're done. This speeds up garbage collection. Look at Rock.draw for an example of this. Also, this is why getRockPoint expects a Point3d passed in, as this avoids the need to create a new point for each location on the rock. The optimization in the compiler will often do this for you, but not always. Try writing the code the easy way first, and see how it affects things, and optimize when necessary.
• Be sure to reset (zero out) the accelerations using Critter.accelReset() before computing them each time. Otherwise, you'll be adding onto those from the previous call.
• Enforcing an upper bound on the magnitude of the acceleration for your bug can help prevent it from flying off when it approaches obstacles too closely (in rare situations). If this is happening very often, however, you probably have another problem (or haven't tweaked the constants enough).
• Refer to the OpenGL documentation provided on the course home page.
• If you're stuck, ask for help! Don't waste hours of your time trying to find some strange bug. Go get a beer or something. Or ice cream. Or maybe just do your homework for another class!