CS 6650: Computational Motion (Fall 2008)

Professor:     Doug James
                      5146 Upson Hall
                      Office Hours: after class, or by appointment
                      djames 'at' cs.cornell.edu

Logistics:      Tues/Thurs @ 1:25--2:40pm  in  401 Hollister Hall
                      First Class:  Thurs Aug 28  (please attend for more information)

Course Description: Covers computational aspects of motion, broadly construed. Topics include the computer representation, modeling, analysis, and simulation of motion, and its relationship to various areas, including computational geometry, mesh generation, physical simulation, computer animation, robotics, biology, computer vision, acoustics, and spatio-temporal databases. Students implement several of the algorithms covered in the course and complete a final project.

Prerequisites: Undergraduate-level understanding of algorithms, and some scientific computing.

Grade options: Letter or S/U

Credit hours: 4

Offered: Fall only

Cross-Listing: None

Grading Rubric:
    30%   Paper presentations, and submitted questions.
    30%   Written homeworks (approximately six)
    05%   Project: Written proposal
    05%   Project: Mid-course show-and-tell
    05%   Project: Final public presentation
    25%   Project: Final written report

Class Schedule:

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., Har-Peled, 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), 550-572. 
Thurs Sept 4,
Tues Sept 9
 Euler-Lagrange Equations of Motion, and Computational Complexity


 References for Lagrangian dynamics:
Topics discussed:
  • N-body problems (all-pairs complexity)
  • Reduced-coordinate deformable bodies (spatial/integration complexity)
  • 2D serial manipulator (recursive complexity)
Assignment for Thurs Sept 18:
  • Regarding the simplified N-body planar serial manipulator from class: What is the complexity of naive evaluation of joint accelerations from the Euler-Lagrange equations given joint angles and velocities. Provide evidence/proof to support your claim.
Thurs Sept 11
 Constrained Dynamics and Differential-Algebraic Equations (DAEs)

 References for Differential-Algebraic Equations (DAEs):
Topics discussed:
  • Constrained Lagrangian dynamics (CLD)
    • Holonomic constraints
    • Constraint-augmented Lagrangian
    • Examples, e.g., pendulum
  • DAE systems
    • Differentiation index
    • Structure of index-1, -2, and -3 DAE systems
    • Index reduction by differentiation
    • Drift-off phenomena
Tues Sept 16 - Thurs Sept 18
 Integrating Constrained Dynamics


 Topics discussed:
  • Constrained Lagrangian dynamics in index-1, -2, -3 and GGL DAE forms
  • Solving for Lagrange multiplier from index-1 form.
  • Constraint stabilization:
    • Baumgarte's method;  modified Lagrange multiplier
    • Projection (position, velocity)
  • Implicit integration of DAEs (for stiff problems)
    • General DAEs, and semi-explicit index-1 DAEs
    • Backwards Euler
    • BDF and multistep methods
  • Half-explicit Runge-Kutta 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 index-1, -2, -3, and GGL (index-2) 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, 43-54.
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
 Gradient-Domain Shape and Deformable Motion Modeling

 References:
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.91-98, 2007.  [PDF] [Video]
Note: 2 questions due by 9am the day of the lecture.
Tues Oct 7 --
Thurs Oct 9
 Rotational and Rigid-Body Motion

 Topics discussed:
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 3-by-3 rotation matrices, A and B,  i.e., ||A-B||_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
 Rigid-Body 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 71-80, Madrid, November 6-7 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
 Rigid-Body Motion (cont'd)

 Reminder: Assignment due (from Oct 7)

Topics discussed:
  • SE(3), Special Euclidean group in 3D
  • Rigid-body 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
  • Newton-Euler equations of motion
  • Integrating rigid-body dynamics
  • Deformable bodies;  mode matrix, U;  extensions to framework
References:
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
  • Navier-Stokes equation
  • MAC grid discretization;  interpolation and averaging;  upwinding
  • Time-stepping schemes (Eulerian, and semi-Lagrangian)
  • Projection to divergence-free velocity
  • Poisson equation; discretization;  compatibility condition;  PCG solution
  • DAE view of incompressible flow
  • Higher-order semi-Lagrangian schemes;  monotone interpolation;  BFECC;  CIP and USCIP
Reference:
Assignment for Tues Nov 11:
  1. Derive an index-1 DAE by eliminating the constraint from the index-2 discrete Navier-Stokes equations presented in class.
  2. Describe an algorithm to evaluate a single forward Euler step for the index-1 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 Multi-view Silhouettes, ACM Transactions on Graphics, 27(3), August 2008, pp. 97:1-97:9. [paper] [video] [data]
Tues Nov 4 -
Tues Nov 11
 Collision Detection, and Deformation Bounds

 Topics discussed:
  • Bounding volumes (spheres, boxes, k-DOPs, etc)
  • Separating axis theorem
  • Space-time bounds
  • Bounding moving points
  • Bounding subspace deformations;
    • Bounded Deformation Trees
    • O(r) and O(1) updates
    • Spheres, boxes, k-DOPs
    • Translational and affine/rotational models
References:
Assignment for Tues Nov 25: Building on the affine motion model (described for spheres in class), propose a tight 6-DOP 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 Newton-Euler Algorithm (RNEA)
    • O(N) inverse dynamics
  • Composite-Rigid-Body Algorithm (CRBA)
    • O(n^2)  mass matrix 
    • Usage in O(N^3) forward dynamics (CRBA + RNEA + dense solve)
  • Articulated-Body Algorithm (ABA)
    • a.k.a. "Featherstone's algorithm"
    • O(N) forward dynamics
  • Closed-loop systems
    • Constraints and fast solution methods
  • Global analysis techniques
    • Fast robot algorithms as sparse matrix methods
References:
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;  Signorini-Fichera condition
    • Maximal dissipation principle
  • "Staggered Projections" contact algorithm
References:
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: Data-driven Mesh Animation with Constraints, ACM Transactions on Graphics, 26(4), October 2007, pp. 17:1-17:16. Project page

End of classes!
Tues Dec 16
@1:25--2:40pm (Upson 5130)
 Computational Motion
Project Presentations