# 15-462 Graphics Project 3: Simulating a Jello Cube

## An Overview

For this assignment you will program a physically-based simulation of a jello cube. The jello cube is made of elastic material, much like the jello sold in grocery stores (the one obtained by mixing the jello powder with water and putting it into the fridge for a couple of hours). When the jello cube is stretched, it will try to contract. When squeezed together, it will tend to inflate back to the original shape. As with the previous assignment, you will also create an interesting animation demonstrating your results.

 Undeformed jello cube Deformed jello cube

Nature is complex and to generate computer graphics simulations of interesting phenomena such as cloth on a virtual character, ocean waves, or trees deforming in the wind, one common approach is to write down the underlying equations of physics and solve them numerically on a computer. Sophisticated algorithms exist for simulations of cloth, fluids or deformable objects, and the results can often be seen in recent computer-generated movies. This assignment will familiarize you with computer animation and physically-based modeling by simulating a simple system, namely the jello cube. You will also be able to expand your knowledge of OpenGL.

## What you need to do

You will model a 3D chunk of jello, which, when undeformed, has the shape of a cube of dimensions 1 meter x 1 meter x 1 meter.

The cube will be constrained to only travel in the interior of a bounding box of dimensions 4 meters x 4 meters x 4 meters. The center of the bounding box is located at the origin of the world-coordinate system. The axes of the bounding box are aligned with the world-coordinate system axes. The cube will stretch, contract, oscillate, change velocity, bounce off the walls of the bounding box, based on the physical laws for a mass-spring system. The cube will stay inside the bounding box. When the cube reaches one of the walls of the bounding box, it should bounce off that wall back towards the interior of the bounding box. Consult the lecture material to see how to achieve this effect.

A real-world jello cube is a continuous object, and if we were to simulate every small infinitesimal part of the elastic material, infinite memory would be required. For this reason, we will discretize the jello cube. This approach (discretization) is very common in phyisically-based modeling, and also applied mathematics and engineering in general. The cube will be modeled by 8 * 8 * 8 = 512 discrete points, which will, in the undeformed configuration, form a uniform grid covering the volume of the cube. When the cube is undeformed and positioned such that it occupies the unit cube in R^3, these points will be positioned at (i / 7, j / 7, k / 7) for i=0,...,7, j=0,...,7, k=0,...,7. As the cube deforms, these points will change position, giving us the shape of the cube at any given moment of time. Note that as the cube deforms, these points will no longer be the same distance apart from their neighbors. At places where the jello cube is squeezed, the points will be closer together, and where it is stretched, they will be farther apart than in the undeformed position. The points with i=0 or i=7 or j=0 or j=7 or k=0 or k=7 are the points on the boundary of the cube. We will call these point surface points, since they define the surface of the jello cube. There are a total of 296 surface points. The surface of the cube can be rendered by drawing triangles connecting the surface points. We provided the complete code to do cube rendering - look for it in showCube.cpp. Interior points are not necessary for rendering, as they are invisible. They are, however, necessary for simulating physics.

The 296 surface control points, connected with structural springs (only structural springs connecting two surface points are shown). This is what wireframe mode looks like (see below).

You will model the movement of the cube by numerically solving a system of ordinary differential equations, which sounds perhaps a bit scary, but is actually not that difficult. The equations to be solved incorporate Newton's second law (F=ma), Hook's linear model of elasticity (F=kx), and linear damping (F=-kv). Further clarification on this will be given in class. To solve the differential equations, you will use two methods: Euler integration, and Runge-Kutta 4th order (RK4) integration. We provided the code which implements both the Euler method and the RK4 method - look for it in physics.cpp. All you have to do is appropriately call either of these two methods during the simulation. For a particular simulation, you will typically just use one of the two methods - but you have to make sure that both methods work correctly with your code.

The cube will deform as a result of different velocities at different locations inside the cube. These differences in velocities will happen for three reasons:

• Initial velocities (specified by the world file) might not be the same everywhere inside the cube.
• There might be an external force field (time-independent, as described below).
• Cube bounces off the wall of the bounding box or off some other collision object.

To obtain a good view of the scene, the camera has to be positioned appropriately. We provide a complete code to do this (see jello.cpp). It allows the user to move the camera around in real-time, and observe the jello-cube from different angles. The description of the method that we use to position the camera is here.

Your program will allow two rendering modes: wireframe and triangle. In the wireframe mode, only the surface points (no filled triangles) are shown, together with the structural springs connecting them. Structural springs are one of the three kinds of springs that are used with the mass-spring system. You can learn more about this from the lecture slides (see Background info section). In the triangle mode, surface of the cube is rendered as triangles (and the surface points are vertices of these triangles). We provided the code to support both the wireframe and triangle rendering mode. It is possible for the user to switch among the two rendering methods at run-time, by pressing 'v' (see also showCube.cpp). Also, in wireframe mode, user can independently turn on/off the display of structural springs, shear springs and bend springs. Thus, any of the 8 on/off combinations can be selected. Pressing 's','h','b' toggles the display of structural, shear and bend springs, respectively. Note that to avoid screen clutter, only the springs connecting two surface points are shown, but the simulation of course has to simulate the structural, shear and bend springs appropriately connecting all the 512 simulation points.

In the triangle mode, the jello is illuminated using proper OpenGL lighting. We provide a complete lighting environment in jello.cpp . You are free to change lighting parameters, or make other rendering improvements/modifications. This way, you can personalize your assignment - otherwise all the cubes for the entire class will look the same (except for any differences in implementation of physics of course), which would make for a quite boring final assignment movie.

You have to implement collision detection and response for the jello cube hitting any of the six walls of the bounding box. In addition, you have to implement collision detection and bouncing response for the jello cube impacting an inclined plane. An inclined plane is a static planar surface, positioned in a certain way inside the bounding box. In the world structure, there are special fields to specify the position of the inclined plane. Use these fields to determine if an inclined plane is present. If present, use the a,b,c,d fields to render the plane and implement collision detection and response. For the inclined plane, use the same collision spring parameters (collision elasticity, collision damping) as for collision with the bounding box. Any position and orientation of the inclined plane could occur and should be supported. When the inclined plane is present in the simulation, assume that the initial position of the cube is such that it completely lies on one side of the plane.

The world file might also specify an external non-homogeneous time-independent (i.e. possibly varying with location, but not with time) force field. If the force field is present, you must model its effect on the cube. The force field is given as an array of vectors, each specifying the 3D force vector (in Newtons) at a node of a 3D discrete grid. Note that this is a different grid than the jello cube grid; this force field grid covers the entire scene bounding box. Use interpolation to obtain values of the force field at an arbitrary position inside the bounding box. The grid is uniform, covers precisely the volume of the bounding box, and consists of n x n x n equally spaced points, where the parameter n is the resolution of the grid. It is specified in the world file. For this assignment, you need to support values of n <= 30.

You will have to implement the acceleration function (computeAcceleration, see physics.cpp). This function takes as input the positions of the 512 nodes, the velocities of the 512 nodes, plus the physical parameters of the model. It returns the acceleration for each of the 512 points. It also adds any effects of an external force field, if such a field is present of course. In general, the acceleration will of course be different for each of the 512 simulation points. To compute the acceleration, the function must take into account the forces due to

• structural, shear and bend springs,
• external forces (force field, if any), and
• bouncing off the wall, or off some other collision object, such as an inclined plane.

## Extra credit

The following are some suggestions:
• Implement collision detection with some other interesting object, such as a sphere, a cone, a spiral, etc.
• Make the animation interactive. Allow the user to interactively (i.e. while the program is running) push the cube in a certain direction by dragging the mouse. The cube should move/deform accordingly. Apply the user force equally to all the simulation points of the cube, regardless of where on the screen mouse dragging occurred.
• Extra extra credit: Allow the user to push only a certain (surface) simulation point, by selecting that simulation point on the screen and then pulling on it by dragging the mouse. For this, you will need to make use of selection and feedback capabilities of OpenGL (see OpenGL Red Book, Chapter 13). Or, you can distribute the force, making it larger closer to the cube location where the user pulled with the mouse. You can make the force falloff radius into a parameter, potentially modifiable at runtime. This will allow you to control how localized deformations your system will produce (extremely localized if force only applies to one simulation point, or not localized at all if all simulation points always receive the same user force; and anything in between).

Also, you might be awarded credit for any other creative or interesting solution to an issue in your implementation, as long as it is well-documented in your readme file. So, if you can think of any interesting feature, feel free to implement it.

Please note that the amount of extra credit awarded will not exceed 10% of this assignment's total value.

## Background Information

The lecture slides contain information on:
• how to organize the springs (structural, shear, bend springs),
• how to compute forces due to springs,
• how to implement collision detection and bouncing response,
• and many other tips.
The slides are here: ppt, ps, pdf (black & white - good for printing).

## Starter code

This assignment consists of two applications: jello and createWorld. We provide complete implementation for createWorld, which is a tool to design your own physical environments. createWorld is a single-file application, and independent from the rest of the assignment. Its implementation is createWorld.cpp .

You will be developing the application called 'jello'. It consists of the following source-code files: jello.cpp, jello.h, input.cpp, input.h, physics.cpp, physics.h, showCube.cpp and showCube.h . The main file is jello.cpp.

In the starter package, all of these files already contain code for pre-implemented functionality such as lighting, camera positions, integrators, etc. You can modify any of these files in any way you want and you can add your own files, if you need to. We provide a makefile which builds both applications: createWorld and jello. Also in the starter package, there are some examples of world files. You can download the complete starter package here. To unpack the starter package, copy the zip file to an empty directory, and run 'unzip starter.zip'.

## Steps you need to take

The following list is one suggestion to pull off the assignment. You can of course take alternative routes. At some point down the pipeline you will need to study the spring model and understand how it applies to the jello cube.

1. Make sure starter and createWorld code compiles.
2. Add code to setup a window (640x640). Note:This window size is not the same as for the last assignments.
3. Understand the createWorld/loadWorld/saveWorld functionality. Create a couple of your own world files.
4. Familiarize yourself with the provided routines which, given a world structure, render the surface of the cube. Be able to use both the wireframe and the triangle mode. See how the camera and lighting work. Experiment with different world files. Personalize your assignment by changing the lighting parameters, or change/improve the lighting environment in some other interesting way.
5. Do a test: move the points of the cube according to a prescribed made-up (non-physical) sequence of deformations, and observe if the cube on the screen changes accordingly. To do this, hard-code the modifications of the world structure as time evolves (i.e. don't use the physical model, but just model some simple movement, e.g. by manipulating positions and velocities in some simple way as the time evolves). For example, increment the z-value of all positions. See if the cube is moving appropriately on the screen.
6. Implement the acceleration function (computeAcceleration, see physics.c, and description above). For now, however, don't implement any collision or the force field.
7. Test the acceleration function:
Make up a world structure, which you will use for the test: Position the points at some position, assign certain velocities, use the Euler or RK4 integrator, assign spring constants, ... As a starting point, you should definitely use one of the world structures we provided. Selecting good values for elasticity and damping factors can be tricky. See the tips below.
8. Implement the force field. Test if it works. Make up some force fields which create really cool effects.
9. Implement collision detection and response for bouncing off the wall. Test it.
10. Render the inclined plane (careful: intersection of the plane and the bounding box can take several shapes, some of which might be easy to miss). Implement collision detection and response for the inclined plane.
11. Extra credit
12. Make the animation jpegs.
13. Submit assignment. Congratulations!!

• Animate the movement of a jello cube based on a realistic physical model.
• Must incorporate a bounding box, including collision detection and response.
• Must implement collision detection and response with an inclined plane. Don't forget to render the plane. You must only show the part of the plane which is inside the bounding box.
• Must implement an arbitrary non-homogeneous time-independent force field, with appropriate force-field interpolation.
• Use the code that we provided to interactively position the camera, use proper lighting, and render the cube in wireframe and triangle mode.
• Read the description of the world from a world file and simulate the cube according to this information. Your program should work with arbitrary world files and should be executed by: `<`name of program`>` `<`name of world file`>` .
Your program, of course, need not work correctly for world files containing invalid data, bad integrator parameters (blow up effects and similar), bad elasticity, damping parameters and other physical parameters, or bad position or velocity parameters.
• Run at interactive frame rates (>15fps at 640x640)
• Be reasonably commented and written in an understandable manner--we will read your code.
• Be submitted along with JPEG frames for the required animation (see below).
• Be submitted along with a readme file documenting your program's features and describing the approaches you took to each of the open-ended problems we posed here. This is especially important if you have done something spectacular for which you wish to receive extra credit!
• Be submitted to your handin directory as described in the guidelines below--deviating from this procedure makes it harder for us to grade your assignment, and we may deduct points for this.

### Animation Requirement

As last time, you are required to submit an animation, represented by a series of JPEG images which are screenshots from your program. Do not exceed 300 frames. The frame rate for the animation, again, is 15fps, which corresponds to 20 seconds of animation running time maximum. Please name your JPEG frames 000.jpg, 001.jpg, and so on. Be warned that the animate program installed in the cluster may have problems with excessively large numbers of images--it may be wise to use it to test subsequences of 100 frames or so.

The animation represents a smaller portion of your grade than in the assignment 1, and about the same portion as for assignment 2. As with assignment 2, the implementation of the program itself is much more important and involves much more thinking. You will still receive points, however, for showing off your jello cube in a creative manner.

A note for those of you who have had trouble dealing with storage for all your images: It is wise not to try to store your frames on your Andrew account, as this will likely fill your quota very quickly. If you have your program write its frames to ./movie, then you can submit it to the correct handin directory for the assignment, run your program, and write your frames directly into the movie handin directory. This avoids worries about intermediate storage.

## Submission

Please submit your code along with your makefile and readme to /afs/andrew/scs/cs/15-462/students/your_andrew_id/, in a sub-directory called asst3. Running "make" in this directory should compile your program successfully--if not, you've left out a necessary file. Within this directory, make a sub-directory called movie, and place the frames for your animation within, numbered as described above.

## Tips

• Use double precision for all internal calculations. That is to say, declare all the floating-point variables as 'double'.
• The code that we provided uses some elements of C++, such as declarations in the middle of the code, and parameter passing by reference (`&`). It doesn't use object-oriented programming. You have to compile the code with 'g++', not with 'gcc'. The makefile that we provide already does this for you.
• The code for this project consists of multiple source files, including several header files. In order for the code to compile properly, it is essential to follow certain guidelines. A good tutorial on managing multi-source-file projects can be found here.
• ```(by Ian): The starter code for Lab 3 is in C++.  In order to get C++ code to compile
in the graphics cluster, the environment variable LD_LIBRARY_PATH needs to
be set to /usr/local/lib.  So you don't have to do this manually every
file:

setenv LD_LIBRARY_PATH /usr/local/lib

This should get your C++ code compiling without any problems--compile the
starter code as a test to make sure it works.
```
• Default key and mouse setup as provided by input.cpp:
• ESC: exit application
• v: switch wireframe/triangle mode
• s: display structural springs on/off
• h: display shear springs on/off
• b: display bend springs on/off
• space: save the current screen to a file, filename index increments automatically
• p: pause on/off
• z: camera zoom in
• x: camera zoom out
• right mouse button + move mouse: camera control
• e: reset camera to default position
• Don't over-stretch the z-buffer. It has only finite precision. A good call to setup perspective is:
```    gluPerspective(90.0,1.0,0.01,1000.0);
```
```    gluPerspective(90.0,1.0,0.0001,100000.0);
```
or even worse:
```    gluPerspective(90.0,1.0,0.0,100000.0);
```
In the last two examples, the problem is that the ratio between the distance of the far clipping plane (=last parameter to gluPerspective), and the distance of the near clipping plane (=third parameter to gluPerspective) is way too big. Since the z-buffer has only finite precision (only a finite number of bits to store the z-value), it cannot represent such a large range. OpenGL will not warn you of this. Instead, you will get all sorts of strange artifacts on the screen and your scene will look nothing like what you intended it to.
• Position your camera before applying any other modeling transformations. It's best to do it the following way:
```   (in display() )
...
glMatrixMode(GL_MODELVIEW);
gluLookAt(...);
...
glTranslatef(...);
...
glBegin(GL_LINES);
glVertex3f(bla,ble,blu);
...
glEnd();
...
```
The code that we provide already follows this sequence.
• Our code uses the Gouraud shading model to do the lighting. Since there are only 64 points on every face, you might experience some aliasing effects along the edges of the triangles.
• Tips for choosing elasticity and damping constants:
• If you set any of these constants (elasticity or damping) to too high a value, your simulation will "blow up" (if it's a collision parameter, the simulation will blow up when the cube reaches a wall). Blowing up means that the mass points of your cube will fly towards infinity. It is a good idea to add some code which will make the simulation terminate when it detects that point coordinates have become unreasonably large. To avoid the blow-up effect, decrease the value of timestep, or decrease the value of the elasticity/damping parameter. Euler tends to blow up much faster than RK4, so you have to decrease the parameter more for Euler than for RK4.
• Euler is faster than RK4, but less accurate and much more unstable. It requires smaller values of the timestep to avoid blowing up.
• Without damping, the simulation will be unstable.
• A general rule of thumb is that the time step should be inversely proportional to the square root of the spring elasticity [Courant condition]
• A time-step of 0.001 is a good start.
• Start this assignment as soon as you can. Much like assignment 2, it is a significant endeavor, with many intermediate steps. If you wait until a few days before the assignment is due, you probably will not finish. This project is a lot of fun if you're not rushed, and if enough time is put in the end product is something fun that you can show off to your friends.
• Reuse any code from the previous assignment that might save you some time. Particularly, you might want to borrow some user control functionality, functions to read/write images, any functions you might have made to automatically write out the frames for your animation. Don't overdo this to the degree that you have an awkward time changing things for this project--the general structure of your transformations and the state of your simulation will be significantly different from the layout of the previous assignment.
• Experiment with your own ideas, and have fun.
written by Jernej Barbic