Project 7: Particle Simulation with Physics Engine.
Overview

The goal of this project is to give you a chance to explore the issues in doing physical simulation for animation. You must implement the basic requirement which builds a particle simulation system in 3D space like a cloth(each particle is a point mass that can have forces pushing it). For this assignment, trying different simulation methods is more important than making fancy images. The project does have various stages, that you should progress through. However, you should look ahead to make sure that your design decisions in an early phase don't preclude what you will need to do later. The early phase of the project will have you build a particle simulator where you use various forces on the particles to move them around. You should try to make your system interactive and fast so you can try lots of things. The later phase of the project will have you experiment with making a complex mass-spring simulation such as cloth. You will be able to make a springy string using the early part of the project. But if you want to make those springs connecting the particles of the string together stiff, you will need to explore different solution methods: explicit integrators (such as predictor-corrector), implicit integration (ala. Baraff&Witkin's cloth paper), and semi-implicit integration (Bridson Fedkiw).

 
  • Note: You need to implement this particle simulation system with Unity, Unreal, OGRE3D, and OpenGL.
Phase 1: build an interactive particle simulator.

The system must be able to simulate a number of particles - each particle should be able to have its mass set to a different value. You should be able to add particles interactively. In addition, the system must have interface to show the progress of the simulation.

Requirement for this phase: 

Your code must implement the following features:

 
  • Simulate a number of particles - each particle should be able to have its mass set to a different value. You should be able to add particles interactively.
     
  • Show the progress of the simulation - this is important for debugging.
     
  • Save and read in a file that describes the initial configuration of the particles, as well as any forces to be applied to them.
     
  • Save the results of a simulation and replay it. While your simulation does not have to be real time, your playback should be able to play at the correct frame rate for your simulation.
    • Note: you may want to have an adaptive step-size integrator at some point, so make sure your playback understands the simulator timing.
     
  • generalized force structure: This is described in the slides. (If youʼre using the skeleton code, you should replace delete_this_dummy_spring with a std::vector of forces.) You must implement two subclass forces:
    • Constant force(constant in a particular direction): such as gravity force acting like gravity.
    • Damping force: Velocity-dependent damping force
    • Spring force:
  1. A spring (of a setable distance) between two particles: (e.g. a force proportional to the relative velocity of particles) repulsion between particles (if the distance between particles is ever less than X, they push each other away)
  2. A spring between a particle and a specific location (or, allow some particles to be un-movable nails and then you just need springs between particles)
  3. A spring that pushes particles upward from the floor (penalty collistions with the floor), or outward from the walls.
 
  • generalized constraint structure: This is also described in the slides. (If youʼre using the skeleton code, you should replace delete_this_dummy_rod and delete_this_dummy_wire with a std::vector of forces.) You must implement at least the following two subclasses:
     
    • RodConstraint. Constrains two particles to be a fixed distance apart. (Rendering code included in the skeleton.)
    • C(x1, y1, x2, y2) = (x1 - x2)2 + (y1 - y2)2 - r2
    • CircularWireConstraint. Constrains a particle to be a fixed distance from some point:
      • C(x, y) = (x - xc)2 + (y - yc)2 - r2
    • Mouse interaction. When the user clicks and drags the mouse, a spring force should be applied between the mouse position and the given particle to make your system interactive.
     
  • Several Numerical Integration Schemes (Simulators). The integration scheme

should be selectable at runtime with keystrokes or some other interaction paradigm. You will find this easiest if you implement a pluggable integration architecture as described in the slides. The minimum integration schemes are:

  • Euler
  • Runge-Kutta 2 and
  • Runge-Kutta 4 and
     
  • The user interface should be able to draw all of the connections/forces. Especially the spring connections.

Doable demo in this phase

  1. Make a "soft" object by taking some particles and connecting them with a lattice of springs. the simplest is a triangle. throw the object around and watch it bounce off the walls and jiggle.
  2. Make a fountain of particles - use repulsion to make a "fluid". the stream of the fountain should wind up in a puddle of particles at the bottom. (use damping to make sure that things don't explode)
  3. Make a swinging rope or chain. connect a line of particles to their neighbors, and nail the top on in place. (use a little damping to prevent explosions)
  • Note: At this point, everything should be either very springy or very damped, since you are still using simple integration methods.


Phase 2: Stiff Spring

In this phase, the first step is to improve the integrator by

 
  • Implement an implicit euler's method (as in Baraff and Witkin). Because the system is so small, you need not worry about their efficiency tricks for large sparse linear systems. Once you have an implicit solver, a semi-implicit solver should be easy (use explicit solution of the springs and gravity, and implicit solution of damping - as in Bridson&Fedkiw).

Doing the following experiments

 
  • Make a chain of 10-20 partcles, connected with springs and a little bit of damping. Nail the top one in place, and let this "rope" swing. Make a graph of the total length of the chain. Notice how it stretches and compresses. The ability to measure this stretching will be useful as we explore different integrators.
     
  • Try to raise the stiffness of the springs to prevent stretchiness. At some point, the equations will become too stiff and the string will explode.
     
  • Experiment with the tradeoff between stiffness and timestep.
     
  • You now have the ability to experiment with the various tradeoffs in creating a stiff piece of string. It should be the case that with better integrators (like implicit), you can take larger time steps, but each time step takes longer to compute. An implicit solver might allow you to take time steps that at 100 times bigger than an explicit solver, but it might take 200 times longer to compute (in which case, its probably better to do 100 explicit steps).
     
  • For this part of the assignment, you need to report on what you find. What are the tradeoffs? How much better are different solvers? Is implicit necessarily better than explicit? Is one RK4 step better than 4 Euler steps (which should be approximately the same amount of computation).
Phase 3: Create a cloth simulation

Mass-Spring Model

The Mass-Spring Model is a very basic method to simulate cloth. Since it is relatively easy to implement and could achieve good results, implementing this model could be a very good exercise before exploring some more advanced cloth simulation methods.

In this model, cloth is simulated by a grid of particles which are interconnected with spring-dampers. Each spring-damper connects two particles and generates a force based on the particles’ positions and velocities. The structure of this model could be illustrated using the image below:

cloth-configure.png

Each particle is also influenced by gravity. With these basic forces, we can form a cloth system.

 

Particle

The starter code already provides you with a particle class. Each particle has several properties at a specific time, including its position, velocity, mass and a force accumulator which stores all the forces influence the particle at that time. From these properties, we can calculate how particles would move at next time step.

 

Computing Forcesforce.png

Cloth Simulation

The algorithm of simulating cloth could be summarized as

  1. Compute forces for each particle
  2. Integrate motion: apply Forward Euler Integration for each particle
  3. Repeat
 

Reference Image

(Note: for the basic requirements, you don’t need to implement collision.)

cloth.png

  • There should be existing cloth simulation existing in your physical engine and try to use them to create a similar simulation to the one you created in phase 2 and do the comparison.
Extra Credit
  • Better integrator ( + 5 Each)
  1. Verlet Integrator. See here.
  2. Leapfrog Integrator. Evaluates position and velocity at different times. See here

for more details.

  1. Symplectic Integrator. As described in class. Compute the positions explicitly and velocities implicitly. (No need for a solver.)
  • Collision ( + 10 Each)
  1. Collisions with the Walls. Particles should bounce off the walls and floor.
  2. Collisions with other Particles. Particles bounce off each other.
  • Angular Springs (+15). Pulls a triplet of particles so that their subtending angle

approaches some rest angle.

  • Angular Constraints (+20). Like angular springs, but the angle is actually

constrained.

  • 3D Cloth with collisions.(+30)
  • Hair with collisions.(+30) How can this be implemented? What about collisions?
What you will turn in
  1. You will prepare a web page describing you assignment, complete with pictures of what your program looks like and a description of its features and user interface. Be sure to detail all of the integrators that work, and all the types of forces that the user can create. You should also document your file format for describing simulation initial conditions.
  2. You must also write a report (either in html or a pdf) that is linked to this page describing your experiments and results for phase 2. Describe how to maximize stiffness, minimize damping, and maximize performance. What are the tradeoffs? Be as detailed as possible.
  3. Wherever possible, provide quantitative details. And, be sure to discuss how what you find compares with what you would expect to find.
  4. Also, consider the computational costs. At what point would it be useful to switch to a sparse linear solver? how would the size of the system that you were simulating effect the choices in integrator?
Results

Ying-Sheng Luo, and Yan-Lin Chen, Particle Simulation with Physics Engine -- 羅應陞、陳彥霖

Detail

呂仁傑, and 鍾賢廣, Particle Simulation with Physics Engine - 呂仁傑 鍾賢廣

Detail

呂柏儒、陳柏君, Particle Simulation with Physics Engine -- 呂柏儒、陳柏君

Detail

林進仰、鄭皓宇, Cloth Simulation -- 林進仰、鄭皓宇

Detail

Yi-You Chen(陳奕佑), Particle Simulation with Physics Engine -- 陳奕佑

Detail

朱駿采、潘琮皓, Particle Simulation with Physics Engine -- 朱駿采、潘琮皓

Detail

郭昱粲, and 林俞彣, Particle Simulation with Physics Engine -- 郭昱粲、林俞彣

Detail

胡柯民, Particle Simulation with Physics Engine -- 胡柯民

Detail