In this assignment, you will build on top of their software-based rasterization pipeline to construct a physics-based animation system, based on a simple spring-mass model of cloth-like materials. We will use the framework described in class, and take very simple explicit Euler time steps.

Please click here to create your repository.

Objectives

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

  • Implement a basic algorithm for simulating spring-mass systems
  • Use this algorithm to model cloth-like materials, accumulating forces and then performing a simple numerical integration of the resulting ODE
  • Develop a simple rendering system based on treating the input spring-mass mesh as a triangle mesh.
  • 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 spring-mass mesh (a list of positions, velocities, and forces) separately from what you will eventually render. Your SDL rendering loop should thus be modified to support iteratively updating the spring-mass data and then generating the image that you will draw on the screen.

In pseudocode, this looks something like this:

bool animating = false;
bool updated = true;

while (!quit) {
  ...

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

  if (animating) {
    //compute a spring-mass 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 spring-mass system, computing changes in velocities and positions. The boolean flag updated signals that you need to rerender the scene, as the spring-mass data has changed.

You should modify your key handler so that you can support taking a single spring-mass step 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 mesh 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 spring-mass 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: Computing Spring-Mass Systems

Your code will read in an input triangle mesh. All edges in the mesh will be treated as springs, and their rest lengths should be computed from their original lengths.

We will use a scene file format similar to the one used by A05. You need only support scene files that have one mesh M specified. Additionally, your scene files should support:

  • Reading the parameter, for the time step increment, as h followed by a float.
  • Reading a mass parameter , for the mass of each vertex in the system as m followed by a float.
  • Reading the spring constant , used for all springs as k followed by a float.
  • Reading an accumulated external acceleration vector, as a followed by three floats.
  • Reading a list of constraint vertices as C followed by an integer for how many constraints. Next, you will read however many constraints that are used as a list of vertex ids (integers) in the mesh. For example C 4 0 1 2 3 specifies four constraints: the vertices with ids 0, 1, 2, and 3.

To do an update of the physics, it is helpful to think of separating the functionality into a force computation step, and a position update step.

For the force computation step, for each vertex , you should accumulate:

  1. All external forces, such as gravity (be sure to account for mass by multiplying it into this force);
  2. A basic drag force, in the direction opposite of the current velocity of the particle. I used a drag constant of 0.02;
  3. All spring forces due the any other vertex that shares an edge with . You can treat springs as standard Hookean springs, and compute a force based on how much their length differs from rest length, multiplied by a spring constant .

For the position update step, you will use the accumulated forces from the previous step. We will use a simplectic Euler update of velocity and position. Simplectic Euler offers us some additional stability without the need for extremely small time steps.

For the velocity update, you should divide the forces by the mass of the particle and then multiply by the input , Next, to compute the position update of the particle, you should multiply the new velocity by and step the position. This means that for simulation step ,

Note that the position update step uses instead of (using would be standard explicit Euler). After computing new velocities and new positions for all particles, you should update them for the next iteration (this requires tracking both the current and future velocities).

Finally, your system must support vertex constraints. Constraints are specified in the scene file as a list of vertex ids. All constraint vertices will not have their positions updated, nor will they accumulate velocity, during the position update step.

Part 3: Rendering Mass-Spring Meshes

After each update of positions, you should render the triangle mesh. To do so, you will need to update the positions of all vertices in the mesh, and then recompute any necessary information (such as triangle and vertex normals). Luckily, connectivity of the mesh will not change from one time step to the next, but any geometric information that you use for rendering with your rasterizer will need to be updated.

As we will treat cloth simulations using meshes that have boundary, we need functionality to render the mesh by potentially coloring both sides of it. Thus, you will need to modify your lighting and shading equations to appropriately compute colors even if the light is on the wrong side of the mesh. One way to do this is to replace the terms using for certain dot products.

Part 4: Execution and Testing

Your program should be executed from the command line as prog06 followed by two parameters: (1) an input scene file, modified as described above and (2) 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 occurring. 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 run your code. Also include a scene file myscene.txt of your choice as well as a screenshot of the scene myscene.ppm after running for a while. Be creative! Feel free to use any of the meshes that we’ve created in class and set up constraints accordingly.

Part 5: Written Questions

Please answer the following written questions. Note that there are 7 questions included, you need only choose 5. The remaining two are extra credit, thus you can receive a maximum of 28/20 for the written portion of this assignment.

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. Explain what gimbal lock is and what causes it.

  2. Explain the difference between explicit and implicit integration.

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

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

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

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

  7. What is the difference between and continuity?

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 CS lab machines, in particular we will test on cambridge. 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 cambridge 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 scene file myscene.txt and associate mesh files, as well as a rendered image myscene.ppm
    6. (Optionally) any other test scenes/images/objects

Grading

Deductions

Reason Value
Program does not compile. (First instance across all assignments will receive a warning with a chance to resubmit, but subsequence non-compiling assignments will receive the full penalty) -100
Program crashes due to bugs -10 each bug at grader's discretion to fix


Point Breakdown of Features

Requirement Value
Consistent modular coding style 10
External documentation (README.md), Providing a working CMakeLists.txt 5
Class documentation, Internal documentation (Block and Inline). Wherever applicable / for all files 15
Expected output / behavior based on the assignment specification, including

Correctly parsing all inputs5
Modifying the SDL loop to support animations and controls with `a` and `s`10
Correctly computing the accumulated force update10
Correctly implementing vertex-based constraints5
Computing the Euler step, correctly including drag5
Updating the cloth geometry in preparation for rasterization10
Producing a cloth simulation of your choice5

50
Written Questions 20 (max possible is 28)
Total 100 (max possible is 108)


Extra Credit

For extra credit, consider implementing extra features, including: (1) additional external forces beyond just a constant acceleration, (2) additional integration techniques such as Runge-Kutta or implicit techniques, (3) collision detection of additional meshes, and/or self-collision.