CS 6650: Computational Motion (Fall 2013)

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

Logistics:      Tues/Thurs @ 2:55--4:10pm  in  (Room Change: Thurston 203   Olin 255)
                      First Class:  Thurs, Aug 29  (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.  This offering will also explore the special role of motion processing in physically based sound rendering.

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
    05%   Project: Written proposal
    05%   Project: Mid-course show-and-tell
    05%   Project: Final public presentation
    25%   Project: Final written report

Discussion Group: Piazza (restricted access to students in course)  Preliminary list of papers to discuss.

Class Schedule: (link to fall 2008 schedule, spring 2011)

ThuAug29 Introduction to
Computational Motion
Slides: PDF
TueSep03 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)

Read for next class:

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.

Reading task for next class:
Identify THREE papers published since this survey appeared that address specific problems/issues/challenges mentioned in the survey.

Rigid Body Dynamics
Paper discussion: Algorithmic issues in modeling motion [Agarwal et al. 2002].

Topics discussed:
  • Rotational and rigid motion;  kinematics and dynamics
  • SO(3), Special Orthogonal group in 3D
  • 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
ThuSep12 No class Read for next class:
Robot Dynamics Algorithms

Topics discussed:
  • Algorithms 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
Articulated Characters,
Elastic Rods

Paper discussion:

Topics discussed:

Programming Assignment:
Recursive Simulation Algorithms
Tip: Start working early so that you can keep up with readings, and your final project proposal.
Rigid-body motion tracking, and
Discrete Elastic Rods

Paper discussion:
  • Deniz Gunceler leads discussion of 

Topics discussed:

  • Miklós Bergou, Max Wardetzky, Stephen Robinson, Basile Audoly, Eitan Grinspun, "Discrete Elastic Rods," ACM Transactions on Graphics (SIGGRAPH) 2008.
Animating Fracture
Paper discussion:
  • Patrick Berens leads discussion of
    • Matthias Müller, Nuttapong Chentanez, Tae-Yong Kim, Real time dynamic fracture with volumetric approximate convex decompositions. ACM Trans. Graph. 32(4): 115 (2013) Author Preprint Paper Video
    • Submit comments before class to Piazza forum.

Relevant Papers:

Project Proposals
  • Please use the template found here (LaTeX) or similar style.
  • Submit your proposal (in PDF format) via CMS.
  • Submit anytime -- CMS deadline (Oct 31)
  • Work alone or in pairs.
  • Please talk with me about possible project ideas, or for feedback.
Readings on Volumetric Simulation;
Constrained Dynamics

Paper discussions:

Topics discussed: On handling holonomic constraints for elastic rods in the first programming assignment:

TueOct15 No class Fall Break
ThuOct17 Fluid Animation
Paper discussion:
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
TueOct22 Topics in fluid simulation

Paper discussions:
ThuOct24 Topics in solid simulation

Topics in animation sound

ThuOct31 Project Demos ("Robots & Rods")
Animation Sound

  • Tim Langlois leads discussion of
    • Real-time rendering of aerodynamic sound using sound textures based on computational fluid dynamics. Yoshinori Dobashi, Tsuyoshi Yamamoto, and Tomoyuki Nishita. 2003. ACM Trans. Graph. 22, 3 (July 2003), 732-740. DOI=10.1145/882262.882339 http://doi.acm.org/10.1145/882262.882339 
       (images) (movie) (pdf) (ppt)
    • Submit comments before class to Piazza forum.

Project Demos

TueNov05 Animation Sound

Paper discussion:

Topics discussed:

  • Fluid equations (continuity, momentum, energy)
  • Equations of linear acoustics; velocity potential; wave equations; sources
  • Incompressible fluid case; pulsating sphere
  • Free-space Green's function


Animation Sound
Paper discussion [Nov07]:
  • Phaedon Sinis & Arthur Sams lead discussion of

Topics discussed [Nov07-Nov14]:

  • Monopoles, dipoles, quadrupoles
  • Acoustic energy and power
  • Acoustic far field approximation
    • Dipole and quadrupole source distributions
  • Lighthill's acoustic analogy
  • Curle's theory
  • Helmholtz equation
  • Frequency-domain sound sources; multipole expansions
  • Acoustic energy & power
  • Wave equation solvers
TueNov12 Animation Sound
Paper discussion:
ThuNov14 Animation Sound
Paper discussion:
  • John DeCorato leads discussion of
TueNov19 Character Skinning

Paper discussion:
  • Caleb Woo leads discussion of
    • [Shiratori et al. 2011] Motion Capture From Body-Mounted Cameras ACM DOI Paper Abstract Author Preprint Paper Video

    • Submit comments before class to Piazza forum.


Character Deformation

Paper discussion:


Topics in Collision Detection

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
  • Self-collision culling
    • Subspace and energy-based bounds
    • Representative triangles
  • Precomputed inter-object penetration depth approximations
No class
Thanksgiving Break
Final Project Presentations
  • Eston
  • John & John
  • Karl
  • James
  • Deniz
  • Caleb
  • Pedro
  • Tim
  • Dan
  • Patrick
Final Project Due Date
Submit materials on CMS (report, results, code, etc.)