DATE

TOPICS

MATERIALS

Thurs Aug 28

Introduction
to
Computational Motion


Tues Sept 2

Discussion:
Algorithmic issues in modeling motion

Related
survey article:
 Agarwal, P. K., Guibas, L. J., Edelsbrunner, H.,
Erickson,
J., Isard,
M., HarPeled, S., Hershberger, J., Jensen, C., Kavraki, L., Koehl, P.,
Lin, M., Manocha, D., Metaxas, D., Mirtich, B., Mount, D.,
Muthukrishnan, S., Pai, D., Sacks, E., Snoeyink, J., Suri, S., and
Wolefson, O. 2002. Algorithmic issues in modeling motion.
ACM Comput. Surv. 34, 4 (Dec. 2002), 550572.

Thurs Sept 4,
Tues Sept 9

EulerLagrange
Equations of Motion, and Computational Complexity

References
for Lagrangian dynamics:
 V.I. Arnold, Mathematical
Methods of Classical Mechanics, Springer, 2nd edition, 1989. (more
mathematical text)
 H. Goldstein et al., Classical
Mechanics, Addison Wesley, 3rd edition, 2001. (standard ugrad
physics text)
 S.T. Thornton and J.B. Marion, Classical Dynamics of Particles and Systems,
Brooks Cole, 5th edition, 2003. (easier ugrad physics text)
Topics discussed:
 Nbody problems (allpairs complexity)
 Reducedcoordinate deformable bodies (spatial/integration
complexity)
 2D serial manipulator (recursive complexity)
Assignment
for Thurs Sept 18:
 Regarding the
simplified Nbody planar serial manipulator
from class: What is the complexity of naive evaluation of joint
accelerations from the EulerLagrange equations given joint angles and
velocities. Provide evidence/proof to support your claim.

Thurs Sept 11

Constrained
Dynamics and DifferentialAlgebraic Equations (DAEs)

References
for DifferentialAlgebraic Equations (DAEs):
Topics discussed:
 Constrained Lagrangian dynamics
(CLD)
 Holonomic constraints
 Constraintaugmented Lagrangian
 Examples, e.g., pendulum
 DAE systems
 Differentiation index
 Structure of index1, 2, and 3 DAE systems
 Index reduction by differentiation
 Driftoff phenomena

Tues Sept 16  Thurs Sept 18

Integrating
Constrained Dynamics

Topics
discussed:
 Constrained Lagrangian dynamics in index1, 2, 3 and GGL
DAE forms
 Solving for Lagrange multiplier from index1 form.
 Constraint stabilization:
 Baumgarte's method; modified Lagrange multiplier
 Projection (position, velocity)
 Implicit integration of DAEs (for stiff problems)
 General DAEs, and semiexplicit index1 DAEs
 Backwards Euler
 BDF and multistep methods
 Halfexplicit RungeKutta methods
 Methods for ODEs on manifolds
 Poststabilization
 Coordinate projection (c.f. coordinate resetting)
 Hamiltonian dynamics; energy conservation
 Symplectic integrators w/ constraints (SHAKE & RATTLE)
Additional CLD reference:
Assignment
for Thurs Sept 25:
 Verify the DAE's nonsingularity (invertibility)
conditions are satisfied for holonomically constrained Lagrangian
dynamics in the index1, 2, 3, and GGL (index2) DAE formulations.

Thurs
Sept 18 
Student presentation:
Steven An

Reference:
Note: 2 questions due by
9am the day of the lecture.

Tues Sept 23 
Thurs Sept 25

Deformable
Models:
Cloth Motion

Topics
discussed:
 Modeling cloth with energy terms
 Implicit integration
Reference:
 Baraff, D. and Witkin, A. 1998. Large steps in cloth simulation.
In Proceedings of the 25th Annual Conference on Computer Graphics and
interactive Techniques SIGGRAPH '98. ACM, New York, NY, 4354.
Assignment
for Thurs Oct 9:
 Analytically evaluate
shear/stretch/bending force and shear
Jacobian terms for Baraff and Witkin cloth model.
 PDF

Tues
Sept 23 
Student presentation:
Yao Yuo

Reference:
Note: 2 questions due by
9am the day of the lecture. 
Thurs
Sept 25

Student presentation:
Changxi Zheng

Reference:
Note: 2 questions due by
9am the day of the lecture. 
Tues Sept 30

Thurs Oct 2

GradientDomain
Shape and Deformable Motion Modeling

References:
 Robert W. Sumner, Jovan Popović, Deformation transfer for triangle meshes,
ACM Transactions on Graphics, 23(3), August 2004, pp. 399405.
 Robert W. Sumner, Matthias Zwicker, Craig Gotsman, Jovan
Popović, Meshbased Inverse Kinematics,
ACM Transactions on Graphics, 24(3), August 2005, pp. 488495.
 Aside:

Tues
Sept 30

Student presentation:
Levent Kartaltepe

Reference:
Note: 2 questions due by
9am the day of the lecture. 
Thurs
Oct 2 
Student
presentation:
Jeffery Chadwick

Reference:
 Akash Garg, Eitan Grinspun, Max Wardetzky, Denis Zorin, Cubic Shells, Symposium on Computer
Animation, pp.9198, 2007. [PDF]
[Video]
Note: 2 questions due by
9am the day of the lecture. 
Tues Oct 7 
Thurs Oct 9

Rotational
and RigidBody Motion

Topics
discussed:
 Rotational and rigid motion; kinematics and dynamics
 Murray, R. M., Sastry, S. S., and Zexiang, Li, A Mathematical Introduction to Robotic
Manipulation. 1st. CRC Press, Inc., 1994.
 Summary in appendix of:
 Rodrigues' rotation formula
 Averaging rotations:
 Clustering rotation sequences:
 Doug L. James, Christopher D. Twigg, Skinning Mesh Animations, ACM
Transactions on Graphics, 24(3), August 2005, pp. 399407.
Assignment
for Thurs Oct 16:
 Derive Rodrigues'
rotation
formula using Taylor series expressions (for exp, sin and cos) and the
properties of skew symmetric matrices.
 Derive an expression for the
Frobenius norm squared of the
difference between two 3by3 rotation matrices, A and B, i.e.,
AB_F^2. Express your answer in terms of the axis angle,
\theta,
of the relative rotation, (A^T B).

Tues
Oct 7 
Student
presentation:
June Andrews

Reference:
Note: 2 questions due by
9am the day of the lecture. 
Thurs Oct 9

RigidBody
Motion (cont'd)

Reminder:
[Baraff and Witkin] assignment due (from Sept 23) 
Thurs
Oct 9

Student
presentation:
Spencer Perreault

Reference:
 M. Müller, B. Heidelberger, M. Hennix, J. Ratcliff, Position Based Dynamics, Proceedings
of Virtual Reality Interactions and Physical Simulations (VRIPhys), pp
7180, Madrid, November 67 2006. [PDF]
[Video]
Note: 2 questions due by
9am the day of the lecture. 
Tues
Oct 14

No
class  Fall break


Thurs Oct 16 
Tues Oct 21

RigidBody
Motion (cont'd)

Reminder:
Assignment due (from Oct 7)
Topics discussed:
 SE(3), Special Euclidean group in 3D
 Rigidbody motion
 Spatial velocity vectors (contravariant twists);
se(3); transformation
 Kinetic energy; inertia, principal axes
 Spatial forces (covariant wrenches); se*(3); transformation
 Velocity of contact points, and relation to twists
 Forces at contact points, and relation to wrenches
 NewtonEuler equations of motion
 Integrating rigidbody dynamics
 Deformable bodies; mode matrix, U; extensions
to framework
References:
 Murray, R. M., Sastry, S. S., and Zexiang, Li, A Mathematical Introduction to Robotic
Manipulation. 1st. CRC Press, Inc., 1994.
 Summary in appendix of:
 Ball's screw theory
 Ahmed A. Shabana, Dynamics of Multibody Systems,
Cambridge, 3rd ed, 2005.

Thurs
Oct 16 
Student
presentation:
Dustin Tseng

Reference:
Note: 2 questions due by
9am the day of the lecture. 
Tues
Oct 21

Student
presentation:
Clayton Chang

Reference:

Thurs Oct 23 
Tues Oct 28

Incompressible
Flow

Topics
discussed:
 Advection; upwind differencing; ENO schemes
 Incompressibility constraint
 NavierStokes equation
 MAC grid discretization; interpolation and
averaging; upwinding
 Timestepping schemes (Eulerian, and semiLagrangian)
 Projection to divergencefree velocity
 Poisson equation; discretization; compatibility
condition; PCG solution
 DAE view of incompressible flow
 Higherorder semiLagrangian schemes; monotone
interpolation; BFECC; CIP and USCIP
Reference:
 S. Osher and R. Fedkiw, Level Set Methods and Dynamic Implicit
Surfaces, Applied Mathematical Sciences, volume 153,
SpringerVerlag, 2003.
 U.M. Ascher and L.R. Petzold, Computer
Methods for Ordinary Differential Equations and DifferentialAlgebraic
Equations, SIAM.
 Jos Stam,
Stable Fluids, Proceedings of
SIGGRAPH 99, Computer Graphics Proceedings, Annual Conference Series,
August 1999, pp. 121128.
 Ronald Fedkiw, Jos Stam, Henrik Wann Jensen, Visual Simulation of Smoke,
Proceedings of ACM SIGGRAPH 2001, Computer Graphics Proceedings, Annual
Conference Series, August 2001, pp. 1522. (introduces vorticity confinement forces)
 Bridson, R., Fedkiw, R., and MullerFischer, M. 2006. Fluid simulation: SIGGRAPH 2006 course notes,
In ACM SIGGRAPH 2006 Courses (Boston, Massachusetts, July 30  August
03, 2006). SIGGRAPH '06. ACM Press, New York, NY, 187. [Slides]
 Foster, N. and Fedkiw, R., Practical Animation of Liquids,
SIGGRAPH 2001, 1522 (2001).
 Enright, D., Marschner, S. and Fedkiw, R., Animation and Rendering of Complex Water
Surfaces,
SIGGRAPH 2002, ACM TOG 21, 736744 (2002).
 Yongning Zhu , Robert Bridson, Animating
sand as a fluid, ACM Transactions on Graphics (TOG), v.24 n.3, July
2005. (Discusses PIC and FLIP hybrid particle/grid methods)
 Higherorder advection schemes:
 BFECC and MacCormack methods:
 Byungmoon Kim, Yingjie Liu, Ignacio Llamas, Jarek
Rossignac,
Advections
with Significantly Reduced Dissipation and Diffusion, IEEE
Transactions on Visualization and Computer Graphics, Volume 13, Issue
1, Pages 135144, 2007. video(DivX)
 Selle, A., Fedkiw, R., Kim, B., Liu, Y., and Rossignac,
J. 2008. An Unconditionally Stable MacCormack Method.
J. Sci. Comput. 35, 23 (Jun. 2008), 350371.
 Methods with small stencils (constrained interpolation
profile (CIP)):
 A projection method to approximate complex boundaries:
Assignment
for Tues Nov 11:
 Derive an index1
DAE by eliminating the constraint from the index2 discrete
NavierStokes equations presented in class.
 Describe an
algorithm to evaluate a single forward Euler step for the index1 DAE.
Be clear about how matrix inverses ( )^{1} are implemented.

Thurs
Oct 23

Student
presentation:
Don Holden

Reference:
Note: 2 questions due by
9am the day of the lecture. 
Thurs
Oct 30

Project
"Show and Tell"

Description: Short presentations (10
min) of
proposed project, including topic, related work, your approach,
preliminary results, and your ultimate goal.

Tues
Nov 4

Student
presentation:
Attila Bergou

Reference:
 Daniel Vlasic, Ilya Baran, Wojciech Matusik, Jovan Popović,
Articulated Mesh Animation
from Multiview Silhouettes, ACM Transactions on Graphics,
27(3), August 2008, pp. 97:197:9. [paper]
[video]
[data]

Tues Nov 4 
Tues Nov 11

Collision
Detection, and Deformation Bounds

Topics
discussed:
 Bounding volumes (spheres, boxes, kDOPs, etc)
 Separating axis theorem
 Spacetime bounds
 Bounding moving points
 Bounding subspace deformations;
 Bounded Deformation Trees
 O(r) and O(1) updates
 Spheres, boxes, kDOPs
 Translational and affine/rotational models
References:
 B. Gaertner, Fast and
Robust Smallest Enclosing Balls, Lecture Notes in Computer
Science, Springer, pp. 325338, 1999.
 Miniball
software, Smallest Enclosing Balls of Points  Fast and Robust in
C++.
 Doug L. James, Dinesh K. Pai, BDTree: Outputsensitive collision
detection for reduced deformable models, ACM Transactions on
Graphics, 23(3), August 2004, pp. 393398.
 M. Teschner et al., Collision Detection for Deformable Objects,
Eurographics StateoftheArt Report (EGSTAR), Eurographics
Association, pages 119139, 2004.
Assignment
for Tues Nov 25: Building
on the affine motion model (described for spheres in class), propose a
tight 6DOP deformation bound that supports large rotations (is affine
invariant) and has an O(r) update cost for r displacement modes.

Thurs
Nov 13

No
class


Tues
Nov 18 
Tues Nov 25

Robot
Dynamics Algorithms

Topics discussed:
 Algorithm overview
 Forward and inverse kinematics
 Inverse dynamics (control)
 Forward dynamics (simulation)
 Notation
 Recurrence relations
 Recursive NewtonEuler Algorithm (RNEA)
 CompositeRigidBody Algorithm (CRBA)
 Usage in O(N^3) forward dynamics (CRBA + RNEA + dense
solve)
 ArticulatedBody Algorithm (ABA)
 a.k.a. "Featherstone's algorithm"
 O(N) forward dynamics
 Closedloop systems
 Constraints and fast solution methods
 Global analysis techniques
 Fast robot algorithms as sparse matrix methods
References:
 Roy Featherstone and David Orin, Robot Dynamics: Equations and Algorithms,
Proc. IEEE Int. Conf. Robotics & Automation, San Francisco, CA,
2000, pp. 826–834. (an excellent review)
 Roy Featherstone, Robot Dynamics Algorithms,
Kluwer Academic Publishers, 1987. (classic bookhighly readable)
 Roy Featherstone, A DivideandConquer ArticulatedBody
Algorithm for Parallel O(log(n)) Calculation of RigidBody Dynamics.
Part 1: Basic Algorithm, The International Journal of
Robotics Research, Vol. 18, No. 9, 867875, 1999. (has good
appendix on spatial notation)
 Roy Featherstone, Rigid
Body Dynamics Algorithms, Boston: Springer, 2007.
 E. Kokkevis, Practical Physics for Articulated Characters,
Proc. of Game Developers Conference (GCG), 2004. (good overview of
system integration issues for ABA, e.g., handling contact and
constraints)
 David Baraff, LinearTime Dynamics using
Lagrange Multipliers, Proceedings of
SIGGRAPH 96, Computer Graphics
Proceedings, Annual Conference Series, August
1996, pp. 137146.
 Robot
dynamics, Scholarpedia page.
 D.K. Pai, STRANDS: Interactive Simulation of Thin
Solids using Cosserat Models, Computer Graphics Forum,
21(3), pp. 347352, 2002.

Thurs
Nov 27 
Thanksgiving
Break 

Tues
Dec 2 
Frictional
Contact

Topics
discussed:
 Impact models; restitution coefficient
 Nonpenetration constraints
 Linear complementarity problems (LCP); QP
formulations; Dantzig's algorithm
 Friction
 Painleve's paradox; frictional indeterminacy;
frictional inconsistency; the importance of impulses
 The myth of "contact points"; distributed friction
forces;
planar sliding; center of friction
 Contacting multibody systems
 Nonpenetration constraints; SignoriniFichera
condition
 Maximal dissipation principle
 "Staggered Projections" contact algorithm
References:
 D.E. Stewart, RigidBody Dynamics with Friction and Impact,
SIAM Review, 42(1), pp. 339, 2000.
 D. Baraff, Fast contact force computation for
nonpenetrating rigid bodies, Computer Graphics Proceedings,
Annual Conference Series: 2334, 1994.
 D. Baraff, Coping with
friction for nonpenetrating rigid body simulation, Computer
Graphics 25(4): 3140, 1991.
 Danny M. Kaufman, Shinjiro Sueda, Doug L. James and Dinesh
K. Pai, Staggered Projections for Frictional
Contact in Multibody Systems, ACM Trans. Graph.(Proc.
SIGGRAPH Asia), 27, 2008.
 Brian Mirtich, Impulsebased Dynamic Simulation of Rigid
Body Systems, Ph.D. thesis, UC Berkeley, 1996.

Thurs
Dec 4

SIGGRAPH Asia 2008
Presentations

Papers
presented:
 Danny
M. Kaufman, Shinjiro Sueda,
Doug L. James
and Dinesh K. Pai, Staggered
Projections for Frictional
Contact in Multibody Systems, ACM Transactions on
Graphics (SIGGRAPH ASIA Conference Proceedings), 27(?), December
2008. Project page
 Steven An, Theodore
Kim and Doug
L. James, Optimizing Cubature for
Efficient Integration of Subspace Deformations, ACM
Transactions on Graphics (SIGGRAPH ASIA Conference Proceedings),
27(?), December 2008 (to appear). Project page
 Doug
L. James, Christopher
D. Twigg, Andrew
Cove and Robert Y.
Wang, Mesh Ensemble Motion
Graphs: Datadriven
Mesh Animation with Constraints, ACM Transactions on Graphics,
26(4), October 2007, pp. 17:117:16. Project page


End of classes!


Tues Dec 16
@1:252:40pm (Upson 5130)

Computational
Motion
Project Presentations

