Assignment 07 - Graduate

• Objectives
• Part 1: Setting up the Animation Pipeline
• Part 2: Simulating Boids
• Part 3: Rendering Boids
• Part 4: Execution and Testing
• Part 5: Written Questions
• Grading

Graduates will construct a behaviorial-based animation system, based on the well-known Boids simulation of Reynolds. It will be helpful to read up on the original algorithm as well as the original paper. I also found this pseudocode to be quite helpful for me debugging, and I have reproduced some of the important notes here.

Objectives

This assignment is designed to teach students the central concepts of a simple animation pipeline for rendering time-varying graphics. Specifically, students will:

• Implement a basic algorithm for simulating Boids
• Experiment with varying parameters that accumulate the weights
• Develop a simple transformation from animation data to geometric data
• Render the resulting simulation in real time.

Part 1: Setting up the Animation Pipeline

Instructor’s Note: You are welcome to use your rasterizer from A06, but this is not required for this assignment. Instead, I have provided an updated gl-rasterizer.js in your default repo, and what follows discusses setting up the animation pipeline relative to that.

In the default repo, you’ll see I’ve provided a collection of javascript files for scaffolding, including: a07.js, filereader.js, gl-rasterizer.js, and mesh.js. These interact with index.html in the following ways:

• index.html loads all javascript files. It also provides a multiple file loader input, as in A06, where you will need to specify a .js scene file and associated .obj.
• Upon selecting a scene, filereader.js will parse input files for you. Notably, you’ll see that the function allFilesLoaded() parses only the first mesh object, using the Mesh class from mesh.js. Next, it calls the function setupAnimation() which is defined in a07.js
  • The Mesh class I’ve provided is a simplified, skeleton data structure that knows how to go from a string containing the contents of an .obj file to a list of positions and faces. It also provides the functions getVertList() and getFaceList() used by the gl-rasterizer.js. Note that the .obj files we will load will not have any faces, you will have to construct the geometry as described below.
• In a07.js, the function setupAnimation() makes a few calls. First, it configures the camera and canvas using the function configureRasterizer() (defined in gl-rasterizer.js). Next, it calls startRender() with the input mesh, similar to A05. Finally, it also provides a default implementation for the function animate(), which can be turned on/off with the toggle button.
• In a07.js the animate() function is your animation pipeline workhorse. This function will be called repeatedly when animation is enabled, and will attempt to update the screen at 60 frames per second. Your animation code should update any information it needs and then call updateMesh() to update the visual information in gl-rasterizer.js
• Finally, index.html also has a button to toggle the animation on and off. You’ll see in a07.js that this function enables or disables the animate() callback.

Thus, I envision that your task in this assignment is to make updates in three places:

1. Modify allFilesLoaded() in filereader.js, as necessary.
2. Modify the Mesh class in mesh.js, as necessary.
3. Modify the animate() function in a07.js to make calls to perform the Boids animation.

As described below, many of these updates make use of information that will be stored in the Mesh, so you may want to consider developing a function nextStep() which updates the mesh in preparation for the eventual updateMesh() call to gl-rasterizer.js.

Part 2: Simulating Boids

To simulate Boids, you will initialize them using the vertices of the .obj file that is specified by the scene. This .obj only has vertex information, which will be used to seed the position of the Boids. You Boids should live in a bounding box that is specified by looking at the bounding box of the input vertex set. Particular, you should compute both the minimum and maximum values in \(x\), \(y\), and \(z\) of the input point set, and use a bounding box that is 20% larger in all dimensions.

Each Boid should be initialized to have a random velocity vector. I used a random unit length vector for my implementation, but I zero’d out any coordinate whose range was 0 in the bounding box. Notably, two of the input examples provided have no \(y\)-coordinate, so should be treated as two-dimensional Boids. This is easy to do by simply initializing the \(y\)-coordinate of the velocity vector to zero.

Boids should take a step based on an accumulated velocity vector computed from the positions and velocities of nearby Boids. Your implementation of nextStep() should have three phases: (1) accumulate the velocities based on the behaviors being modeled, (2) Update the positions/velocities of Boids, using the variable scene.timestep to take an Euler-like update to the position of the Boids based on the accumulated velocity, and (3) update (or rebuild) the geometry that you will use for rendering the Boids.

The velocity accumulation should accumulate 3 types of behaviors: (1) separation, (2) alignment, and (3) cohesion. Balanced appropriately, such behaviors will induce flocking behavior. Each of these forces will be computed by examining a certain neighborhood of nearby Boids. You will need to check, potentially, all pairs of Boids to compute the velocity update.

Separation can be modeled by taking all Boids within a radius \(R\) and computing a repulsive force from every other nearby Boid. \(R\) should be initialized based on the scene file’s value radius, but you should also allow the user to control it with a slider. For computing separation, I used, as Reynolds suggests, a weight relative to the squared length between the positions of the two Boids, resulting in the following pseudocode:

for (each Boid i) {
  separation = (0,0,0);
  for (each Boid j != i) {
    diff = position[i] - position[j];
    dist = diff.length();
    if (diff.length <= R) {
      //skip any neighbors with exactly the same position
      if (dist > 0.0) {  
        separation += diff / (dist*dist);
      }
    }
  }
}

Alignment can be modeled by considering the velocities of all Boids, not just those in your neighborhood. Alignment seeks to modify a Boid’s direction to match the average direction of the flock of Boids:

for (each Boid i) {
  alignment = (0,0,0);
  for (each Boid j != i) {
    alignment += velocities[j]
  }
  alignment /= (N-1);
  alignment -= velocities[i];
}

Finally, cohesion attracts each Boid to the center of the entire group, pulling Boids closer to the flock. To compute it, one averages the positions of all other Boids, and then takes the vector moves from the current position to the center of the group:

for (each Boid i) {
  cohesion = (0,0,0);
  for (each Boid j != i) {
    cohesion += positions[j]
  }
  cohesion /= (N-1);
  cohesion -= positions[i];
}

After computing all three behaviors, one can then update the Boid’s velocity. It is helpful to scale each of these by user driven parameters, \(w_s\), \(w_a\), and \(w_c\), to produce a variety of different behaviors. The should be initialized from the scene file variables separation (for \(w_s\)), alignment (for \(w_a\)), and cohesion (for \(w_c\)). You should let the user control these parameters using sliders. Particularly, it will be helpful to debug your Boids by turning off certain behaviors (i.e. by setting their appropriate \(w\) to 0).

Finally, one can accumulate the Boids by adding the three components together. To provide an appropriate balance, I first normalize each of the vector and then accumulate them in a velocity_update. Some care needs to be taken when normalizing, if the vector your produce is \((0,0,0)\) then it should not be normalized (otherwise, you would divide by zero!) Next, to control the speed of the simulation, I perform a modified “Euler” step, by updating the position in the direction of the velocity scaled by a value in the scene called timestep:

for (each Boid i) {
  velocity_update[i] = (0,0,0);
  //compute separation, alignment, and cohesion
  velocity_update[i] += w_s*separation.normalized();
  velocity_update[i] += w_a*alignment.normalized();
  velocity_update[i] += w_c*cohesion.normalized();
}

...

for (each Boid i) {
  velocity[i] += velocity_update[i];
  positions[i] += velocity[i]*timestep;
}

To handle boundaries, any time a Boid is outside of the bounding box you should negate the velocity component for which direction it has violated. For example, if the new position of the Boid is greater than 20% beyond the maximum \(x\)-coordinate, then negate the \(x\) component of the Boid’s velocity to bring it back within the box. This should cause the Boid to “bounce” off of the boundary wall.

To prevent Boids from being stuck outside of the boundary, this requires a two stage update:

for (each Boid i) {
  velocity[i] += velocity_update[i];
  test_pos = positions[i] + velocity[i]*timestep;

  //check if test_pos is outside of the boundary and
  //invert components of the velocity if necessary

  new_pos = positions[i] + velocity[i]*timestep;
  positions[i] = new_pos;
}

Part 3: Rendering Boids

To render, I’ve provided the gl-rasterizer.js code which takes the input scene information and sets up the camera. This rasterizer ignores any lights or color information on the mesh, but you’re welcome to modify it if you would like to add additional effects (particularly, using your knowledge from A06, modifying the vsSource and fsSource are equivalent to performing your vertex processing and fragment processing).

You are also welcome to remove the gl-rasterizer.js code and replace it with your rasterizer from A06. Please document any information for this in your README.

To render Boids, you need to convert from the information you’re tracking for the flocking simulation to primitives that you can render. You are encouraged to do this however you would like. One way that is fairly easy is to draw four triangles aligned with each Boid, in a cone configuration that indicates which way the Boid is traveling. In my demo, this is what I used.

To compute such geometry, you can take the velocity vector of each Boid and compute a \((u,v,w)\) coordinate system that aligns with the Boid. I did this so that \(w\) aligned with the Boids velocity. Next, for a Boid at position \(p\) I drew four triangles, with coordinates \(\{p+0.05w,p+0.02u,p+0.02v\}\), \(\{p+0.05w,p+0.02v,p-0.02u\}\), etc.

I then passed all of this geometry to my rasterizer by enumerating the set of triangles and their vertices in the functions getVertList() and getFaceList(). You’re welcome to use whatever scheme you like to draw the Boids, even a single triangle would be sufficient.

Part 4: Execution and Testing

Your program should be able to load all scene files that I’ve provided and display the resulting simulation. You should also provide an interface that allows the user to vary \(R\) as well as the weights \(w_s\), \(w_a\), and \(w_c\).

There is no need to save any information about the simulation, but if you’d like you could employ your screen shot saving technique from previous assignments.

Include in your README specific instructions on how to execute your animation.

Finally, you are also required to provide a sample scene file with a Boids simulation of your own creation. Be creative! Make sure that you include a file myscene.js with any other .obj files that are necessary for it.

Part 5: Written Questions

Please answer the following written questions. You are not required to typeset these questions in any particular format, but you may want to take the opportunity to include images (either photographed hand-drawings or produced using an image editing tool).

These questions are both intended to provide you additional material to consider the conceptual aspects of the course as well as to provide sample questions in a similar format to the questions on the midterm and final exam. Most questions should able to be answered in 100 words or less of text.

Note that there are 8 questions included, you need only choose 5. Particularly, the last three cover material to be described later in class, and included as extra credit to study for the final. If you complete all 8, you can receive a maximum of 32/20 for the written portion of this assignment.

Please create a separate directory in your repo called written and post all files (text answers and written) to this directory. Recall that the written component is due BEFORE the programming component.

1. The pseudocode described above shows the direct computation of each force for Boids, but can be made more efficient by storing additional information in the mesh and combining loops. Briefly describe how you plan to implement the force update what additional information you might store.

2. Explain what gimbal lock is and what causes it.

3. Explain the difference between explicit and implicit integration.

4. Give one reason to and one reason not to use physically-based animation techniques instead of using character animation.

5. In class, we discussed multiple options for handling collisions. Briefly (in one sentence) describe one technique as well its advantages and disadvantages.

6. Explain the difference between an approximating and an interpolating curve formulation. Give an example of a type of curve of each.

7. Using higher degree polynomials to model curves with many constraints can lead to many issues. Describe one problem with using them.

8. What is the difference between \(C^0\) and \(C^1\) continuity?

Grading

Deductions

Point Breakdown of Features