Assignment 06 - Undergraduate

• 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
• Submission
• Grading

Undergraduates will build on top of their software-based rasterization pipeline to 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

We will build on our rasterization pipeline using SDL to execute an animation loop. A key idea is that you will maintain data for the Boids (a list of positions and velocities) separately from what you will eventually render. Your SDL rendering loop should thus be modified to support iteratively updating the Boids data and then generating the image that you will draw on the screen.

In pseudocode, this looks something like this:

bool animating = false;
bool updates = true;

while (!quit) {
  ...

  while (SDL_PollEvent(&event)) {
    //handle events
  }

  if (animating) {
    //compute a Boids step
    updated = true;
  }

  if (updated) {
    //generate new image to draw
    SDL_UpdateTexture(...);
    updated = false;
  }

  renderTexture(...);
  ...
}
  

In the above, the boolean flag animating signals that you should perform another update with the Boids algorithm, computing changes in velocities and positions. The boolean flag updated signals that you need to rerender the scene, as the Boids data has changed.

You should modify your key handler so that you can support taking a single step of the Boids algorithm by pressing the s key and that you can turn on animation (animating == true) by pressing the a key (resulting in the code updating the Boids positions every time the SDL loop executes). Using the above two flags is one way to do this, for example:

while (SDL_PollEvent(&event)) {
  ...
  if (event.type == SDL_KEYDOWN){
    switch (event.key.keysym.sym){
      case SDLK_a:
        animating = !animating;
        break;
      case SDLK_s:
        //compute a Boids step
        updated = true;   
        break;
    }
  }
  ...
}

Having the functionality to both take a single step and to do a repeated animation will allow you to both debug your code (by taking one step at a time) as well as to let it run continuously.

Part 2: Simulating Boids

Your Boids should live in a box of size \([-0.5,0.5]\times[-0.5,0.5]\times[0,0]\). You should be able to initialize \(N\) boids living in this box, based on a user specified parameter (I tested with \(N == 300\) in my code). Each Boid can be initialized to have a random velocity vector (these should have fairly small magnitudes, i used magnitudes between 0 and 0.05).

Boids should take a step for each iteration based on accumulated information of nearby Boids. Steps 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 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 specified on the command line, in my code I tested with \(R == 0.4\). I used, as Reynolds suggests, a weight relative to the squared length between the positions of the two Boids:

for (each Boid i) {
  separation = (0,0,0);
  for (each Boid j != i) {
    vec3 diff = position[i] - position[j];
    float dist = diff.length();
    if (diff.length <= R) {
      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 remaining 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. In my code, I used \(w_c = 1.0\), \(w_a = 0.3\), and \(w_s = 0.1\). You will also find it helpful to initial test these behaviors by turning off certain behaviors (by setting their appropriate \(w\) to 0)r

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

...

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

This basic formula will work well, but you may find that you need to keep the velocity updates from getting too big. In my code, I made sure the length of a velocity update was never greater than 0.02 by first normalizing and then scaling the velocity update based on whichever was smaller: the original length or 0.02.

To handle boundaries, any time a Boid is outside of the bounding box \([-0.5,0.5]\times[-0.5,0.5]\), you should add a factor to the velocity to nudge it back inside of the box. Just as with velocity updates, you may need to keep velocities from getting too large.

Part 3: Rendering Boids

You should set up your camera parameters accordingly so that you can view the entire scene in a window of a size of your choosing. You need not have a scene file for this, so you can hardcode camera parameters if you choose, but you might find a configuration file helpful to vary parameters. A simple camera based above the scene (with positive \(z\)-value) and looking at the center \((0,0,0)\) should work).

Please document any information for this in your README.

To render Boids, you need to convert from the information you’re tracking for the crowd 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 use flat shaded rendering from your rasterizer and to draw four triangles aligned with each Boid, in a cone configuration that indicates which way the Boid is traveling.

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 (there are instructions in the textbook for doing this with a single vector, see section 2.4.6 for a refresher). 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.5w,p+0.2u,p+0.2v\}\), \(\{p+0.5w,p+0.2v,p-0.2u\}\), etc.

I then passed all of this geometry to my rasterizer to draw with flat shading. 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 executed from the command line as prog06 followed by six parameters: (1) the number of Boids \(N\), (2) the radius of the neighborhood \(R\), (3)-(5) the weights \(w_s\), \(w_a\), and \(w_c\), and (6) an output image filename. This execution should open up an SDL window to display the final scene. When the user presses the a key, it should toggle whether or not animation is occuring. When the user presses the s key, it should take one step and redraw. When the users presses the w key, it should write the currently displayed scene to the output image, and when the user presses the q or ESC keys, it should quit.

Include in your README specific instructions on how to execute and reproduce a Boids simulation with a chosen set of parameters. Be creative! Include a screenshot of your simulation while running with your best set of parameters.

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).

Most questions should able to be answered in 100 words or less of text.

Please create a commit a separate directory in your repo called written and post all files (text answers and written) to this directory.

1. Given the four control points for a Bezier segment, what are the four constraints for an equivalent cubic Hermite spline.

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

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

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

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

Submission

• You should use git to submit all source code files and a working CMakeLists.txt. Do not submit any build files, binary files, or otherwise. The expectation is that your code will be graded by cloning your repo and then executing:

$ mkdir build
$ cd build
$ cmake ..
$ make

Your code must compile on the lab machines in GS 930. Code that does not compile in this way will be given an automatic zero. You will be given one “warning” for the first instance during the semester that it does not compile, but after a zero will occur If you are working on a different environment, please log into these machines and test your code before submitting.

• Make sure that this build process produces an executable named prog06. You will need to edit CMakeLists.txt accordingly.

• Please provide a README.md file that provides a text description of how to run your program and any command line parameters that you used. Also document any idiosyncrasies, behaviors, or bugs of note that you want us to be aware of.

• To summarize, my expectation is that your repo will contain:

  1. A README.md file
  2. Answers to the written questions in a separate directory named written
  3. A CMakeLists.txt file
  4. All .cpp and .h files that you authored and are necessary to compile your code
  5. A rendered image myboids.ppm
  6. (Optionally) any other test scenes/images/objects

Grading

Extra Credit

For extra credit, consider implementing any other forces or phenomena to increase interactivity and realism. You may wan to consider using the mouse input to provide an extra constraint. Plenty of other forces are described in Steering Behaviors For Autonomous Characters, a followup work by Craig Reynolds. You may also want to try Boids in 3D.

Deductions

Point Breakdown of Features