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 Spring 2013 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)

DATE
TOPICS
MATERIALS
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.

ThuSep05
TueSep10
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
References:
ThuSep12 No class Read for next class:
TueSep17
ThuSep19
TueSep24
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
References:
ThuSep26
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.
TueOct01
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.
ThuOct03

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.

Topics discussed:

  • ...
TueOct08

Paper discussion:

Topics discussed:

  • ...
ThuOct10

Paper discussion:

Topics discussed:

  • ...
TueOct15

Paper discussion:

Topics discussed:

  • ...
ThuOct17

Paper discussion:
  • 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.

Topics discussed:

  • ...
TueOct22
ThuOct24
No class

TueOct29

Paper discussion:

Topics discussed:

  • ...
ThuOct31

Paper discussion:
  • Phaedon Sinis & Arthur Sams lead discussion of

Topics discussed:

  • ...
TueNov05

Paper discussion:
  • Pedro Rittner leads discussion of

Topics discussed:

  • ...
ThuNov07

Paper discussion:
  • John DeCorato leads discussion of

Topics discussed:

  • ...
TueNov12

Paper discussion:
  • John DeCorato leads discussion of

Topics discussed:

  • ...
ThuNov14

Paper discussion:

Topics discussed:

  • ...
TueNov19

Paper discussion:

Topics discussed:

  • ...
























Upcoming topics (in approximate order)

Rigid body dynamics
Robot dynamics algorithms
Tracking: rigid motion
Deformable bodies
Subspace dynamics
Vibration modeling & waves (solids & fluids)
Application: Sound rendering
Constrained dynamics
Application: Yarn-level cloth
Adaptive meshing
Collision detection (culling, and exact tests)
Motion interpolation (affine, deformable)
Curvature flow
Character motion
Tracking: faces
Fabrication
Fluids
Volumetric motion data structures
Tracking: fluids (stochastic tomography)
Detail synthesis
Snow simulation