CS 348C Assignment #2: Position-based Dynamics
Due date: Tuesday, Nov 15, 2016 (midnight) [Late deadline: 10% penalty by Friday, Nov 18, 2016]
In this second assignment, you will implement a particle system
based on position-based dynamics based on [Macklin et al. 2016; Müller et al. 2006]. You system will support a similar
position-level constraint-based relaxation approach to dynamic
modeling. The core system should support cloth simulation, and you
can extend it to add additional functionality of your choosing.
Groups: Work on your own, or in a group of at most two
people. Additional work is expected from a group submission, such as
a more elaborate creative artifact or modeled phenomena. PhD
students are encouraged to work alone, and pursue a more challenging
Starter Code: This project has starter
code (available to registered students through Canvas), primarily to augment
the cs348c.particles package to represent triangle meshes for
cloth modeling, loading of OBJ triangle
meshes, and to support OpenGL rendering. Several
triangle mesh examples are provided to help you get started. In
this assignment, you will modify this package as needed. As in Assignment #1, use of the starter code is optional. The code does not depend on Assignment #1 at all, however you may use code from your previous assignment if you wish, e.g., code for fast neighbor finding.
Assignment Steps: The code provides some very basic
functionality for a particle system, but does not implement any
cloth constraints, or other collision detection, etc.
After you get the basic simulator working, you should try adding something
unique to your submission:
- Getting started: Start by familiarizing yourself with
the starter code, and modifying it to support the position-based
time-stepping scheme, as described in the PBD paper.
- Visual debugging: The simple OpenGL renderer provided
allows each particle to be rendered with its own color. Modify
the code so that you can easily set each particle or triangle's
color. Use the colors to help you debug each stage of your
pipeline by displaying relevant quantities. Try changing the
color of the particles to display simulation state.
- Particle-plane collisions: To keep the particles from
passing through the floor, or leaving the container, you need to
implement position-based collision response with the
computational cell boundaries. The basic functionality of the
assignment is to simulate fluid in a rectangular box of fixed
size. For now, modify the inner position-correction iteration so
that the particle position are kept from leaving the box when
bouncing around under the influence of gravity. You can
implement each using a general particle-plane inequality
constraint (with strength k=1), and then later reuse it for
other plane constraints.
- Cloth constraints: Following section 4 of [PBD],
implement the core constraints and constraint gradients needed
for (1) edge-based stretching constraints, and then (2) bending
constraints. Formulae for evaluating nontrivial gradients are
available in the paper's Appendix. You should represent
each piece of cloth in your simulation using a Cloth Object,
with associated simulation parameters and constraints. Cloth
vertex/particle mass should be computed using the density of the
cloth, rho, times 1/3 of the sum of the surrounding triangle
areas. Implement the position updates associated with
stretch and bend constraints, using iterative Gauss-Seidel
updates. Be sure to use the accumulated Lagrange multiplier (quasi-Newton) approach from [Macklin et al. 2016] for convergent behavior. Make sure to support multiple constraint passes per
time-step for best results.
- Interaction: Implement a position-level mouse
constraint to allow you to pull on cloth vertices. Your
simulation should remain stable during the interaction. You will
need to need to support particle picking, by finding the
particle closest to your mouse position. This can be implemented
in many ways, but probably the easiest is to determine the line
associated with your mouse position/ray, and then scan all
particles to find the particle closest to that line using 3D
geometry. The mouse particle goal position can be determined by
mouse position changes in the parallel view plane. Manipulated particle position/velocity can be overwritten, and an inverse mass of zero used to allow complete control. Not everyone has taken a 3D Graphics course here, so if you are not familiar with 3D model/view geometry, please ask for help.
- Attachments: Pin constraints should be implemented, so
that vertices can be fixed in space and/or attached to other
moving objects. This can be achieved using position-level
updates, and by setting the particle inverse mass value, w, to
zero, i.e., giving it infinite mass. You should provide an
example with cloth suspended in space, e.g., a rectangular piece
of cloth hanging from two corners.
- Damping: Implement the "rigid damping" approximation
(described in section 3.5 [PBD]). Initially, to get things going, you
could just implement a simple damping force, such as f = -c*v or
a velocity scaling filter (e.g., "v *= 0.9999"). However, these
models produce an "underwater" damping effect, whereas the
"rigid damping" model does not damp rigid-body motion.
- Balloons: To simulate closed objects with air inside,
such as a inflatable ball, implement the "cloth balloon"
constraint (see section 4.4 [PBD]).
- Collisions with rigid obstacles can be approximated
using local vertex-plane constraints as described in the paper.
In order to detect collisions for purposes of generating
time-step-specific constraints, you should use a spatial
acceleration data structure, such as a bounding volume hierarchy
(BVH) or (uniform) spatial subdivision. Robust collision
responses with rigid obstacles will enable you to implement
challenging scenarios (such as the example shown at the top of this page). Alternately, collisions with volumetric rigid
obstacles can be implemented robustly if you can tell if a
vertex is inside or outside the object, since then you can then
detect and "push" vertices to the surface during the constraint
projection phase. Implicit function definitions (such as for a
sphere), or signed distance fields, can be useful
representations for volumetric objects.
Hand-in using Canvas:
- Interactive modification of simulation parameters (such
as constraint "stiffness," or cloth density, gravity, etc.) can
be implemented using GUI sliders, etc., and can enable fun
interactions. [Difficulty: Easy]
- Cloth self-collisions can be approximated for vertex-triangle collisions using vertex-plane constraints as described
in the paper. They will require all-pairs proximity checks, so feel free to adapt your neighbor-finding code from the first assignment. [Difficulty: Medium]
- Animate something: Use your simulator to implement at
least one nontrivial animation scenario. You can use the OBJ
mesh loader to load a variety of meshes that you can either
build, or download (e.g., from TurboSquid), to help you build an
interesting scenario. Setting initial positions and velocities
of your objects, can be used to create interesting setups, e.g.,
crash scenarios, running objects through gears, etc. [Difficulty: Varies]
- Just add water: If you are feeling ambitious, you can
combine your cloth simulator with the previous Particle Based
Fluids implementation from assignment #1. You will need to implement
fluid-cloth particle collisions to ensure that fluid particles
do not pass through the cloth, and that contact-based momentum
is transferred between cloth and fluid particles. Alternately, this would make a fun final project in the course. [Difficulty: Hard]
Start early. Ask questions. Have
- Document: A brief written document (in txt or PDF) that details what you
did, your findings, and who you discussed the assignment with,
- Include comparisons or analysis/results demonstrating the
behavior of your implementation.
- Include the names of people that you discussed the
assignment details with.
- Include citations of external resources (books, webpages,
etc.) that you used in your R&D.
- Code: Documented software implementation derived from the Java
starter code, or based on an analogous framework in another
language, e.g., C++.
- Results: Your creative simulation artifacts, videos, images,
- We will run your software to evaluate your implementation,
and/or ask you to provide a demo. However including
videos that demonstrate the requested features, and
interesting behavior are strongly encouraged.
- Submit as a group: If you are working with a partner, be sure to form a
two-person group, and submit your zip file as a group.
- Late submission:
Keep in mind this is a short 2-week assignment. If for some reason you
will not be able to meet the Tuesday, Nov 15, 2016 (midnight) deadline,
you can still submit by Friday, Nov 18, 2016 (midnight) for a mild 10%
late penalty. Assignments later than this deadline are highly
discouraged--also, it's Thanksgiving Break.
On collaboration and academic
are allowed to collaborate on the assignments to the extent of
formulating ideas as a group, and derivation of physical equations.
However, you must conduct your programming and write up completely
on your own (or with your partner), and understand what you are
writing. Please also list the names
of everyone that you discussed the assignment details with. (You are
expected to maintain the utmost level of academic integrity in the
- Jan. Bender, Matthias. Müller, Miles. Macklin, Position-Based Simulation Methods in Computer Graphics, EUROGRAPHICS Tutorial Notes, 2015, Zürich, May 4-8. [Course Notes] [Slides]
- Miles Macklin, Matthias Müller, Nuttapong Chentanez: XPBD: Position-Based Simulation of Compliant Constrained Dynamics in Proceedings of ACM Motion in Games, San Francisco, October 2016. [PDF][Slides][Video][Youtube] (An improved PBD approach)
- M. Müller, B. Heidelberger, M. Hennix, J. Ratcliff, Position Based
of Virtual Reality Interactions and Physical Simulations
(VRIPhys), pp 71-80, Madrid, November 6-7 2006, Best Paper
Award, PDF, (video), (slides)
- Jos Stam, Nucleus:
Towards a Unified Dynamics Solver for Computer Graphics,
2009 Conference Proceedings: IEEE International Conference on
Computer-Aided Design and Computer Graphics, pp. 1-11, 2009. (related talk)
- T. Jakobsen, Advanced
Character Physics, Game Developer Conference, 2001.