Department of Computer Science
College of Computer, Mathematical, and Natural Sciences
The University of Maryland at College Park

CMSC 828X (Fall 2019): Physically-Based Modeling, Simulation and Animation


CMSC 828X (Fall 2019): Physically-Based Modeling, Simulation and Animation

Instructor: Ming C. Lin


Time and Place: Tues/Thur 3:30pm - 4:45pm, CSIC 1121
Office Hours: Tues/Thur After Class
Prerequisites: Scientific Computing AND Introductory Computer Graphics OR Instructor's approval
Textbook: Course Notes and In-Class Handouts


Check out some cool videos or find them at YouTube!

Line
  • Course Overview
  • Lectures and Approximate Schedule
  • Course Reading Materials
  • Assignments and Projects
  • WEBS of Physically-Based Modeling & Animation
  • Geometric Algorithms & Software Available on the Web
  • Additional Reference Materials
  • Conferences in Related Areas
  • Line

    COURSE OVERVIEW:

    Line

    Physically-based modeling and simulation attempts to map a natural phenomena to a computer simulation program. There are two basic processes in this mapping: mathematical modeling and numerical solution. The goal of this introductory course is to understand both of them. The mathematical modeling concerns the description of natural phenomena by mathematical equations. Differential equations that govern dynamics and geometric representation of objects are typical ingredients of the mathematical model. The numerical solution involves computing an efficient and accurate solution of the mathematical equations. Finite precision of numbers, limited computational power and memory forces us to approximate the mathematical model with simple procedures.

    In this course, we will study various techniques to simulate the physical and mechanical behavior of objects in a graphical simulation or a virtual environment. Students will learn about implementation of basic simulation programs that produce interesting results and verify its correctness. The course will cover three basic components in physically-based modeling and simulation:

  • Geometry
  • Collision Detection
  • Computing Contact Manifolds
  • Mechanics
  • Particle Dynamics
  • Rigid Body Dynamics
  • Non-Rigid Body Dynamics
  • Numerical Computing
  • Initial Value Problems
  • Boundary Value Problems
  • Constraints & Differential-Algebraic Equations
  • The goal of this class is to get students an appreciation of computational methods for modeling of motions in the physical and virtual world. We will discuss various considerations and tradeoffs used in designing simulation methodologies (e.g. time, space, robustness, and generality). This will include data structures, algorithms, computational methods and simulation techniques, their complexity and implementation. The lectures will also cover some applications of physically-based modeling and simulation to the following areas:
  • Computer Animation
  • Virtual Environments
  • Medical Simulation and Analysis
  • Special Effects Generation
  • Computer Game Dynamics
  • Rapid Prototyping for Design
  • Haptic Rendering/Interfaces
  • Robotics and Automation
  • Bio-informatics
  • Depending on the interests of the students, we may also cover geometric-based simulation techniques, such as constraint-based systems, inverse dynamics, kinematics of motions, motion planning, synethesis and generation of autonomous agents.

    Line

    LECTURES AND APPROXIMATE SCHEDULE

    Line

    Here is a list of TENTATIVE lecture topics (subject to changes). Schedule and information on each topic (e.g. readings, web pointers) will be added during the semester before each class.

  • Overview (Tues, Aug 27, 2019)
  • Basics of Motion Generations for Animation (Thur, Aug 29, 2019)
  • Principles of Animation and Inverse Kinematics (Tues, Sept 3, 2019) with Supplementary Video
  • ODE Basics: Initial Value Problem & Solutions to Spring-Mass System (Thur, Sept 5, 2019)
  • Intro to Particle Dynamics & Particle Systems (Tues, Sept 10, 2019)
  • Implicit Methods (Thur, Sept 12, 2019)
  • Constrained Dynamics (Tues, Sept 17, 2019)
  • Review on Comp Geom (Thur, Sept. 19, 2019)
  • Review on Comp Geom & Collision Detection: Convex Polyhedra & Many Bodies (Tues, Sept 24, 2019)
  • Collision Detection: Convex Polyhedra & Many Bodies (Thur, Sept 26, 2019)
  • Collision Detection: BVHs & Spatial Partitioning (Tues, Oct 1, 2019)
  • Collision Detection: BVHs & Spatial Partitioning (Thur, Oct 3, 2019)
  • Project Proposal (Tues/Thur, Oct 8-10, 2019)
  • Collision Detection for Deformable Bodies and Other CD Techiques (Tues, Oct 15, 2019)
  • Rigid Body Dynamics (Notes on Quaternion and Particle to Rigid Body Dynamics) (Thur, Oct 17, 2019)
  • Position-based Dynamics and Modeling of Deformable Models: Introduction (Tues, Oct 22, 2019)
  • Modeling of Deformable Models: Introduction and Introduction to Audio (Thurs, Oct 24, 2019)
  • Introduction to Fluid Simulation (Tues, Oct 29, 2019)
  • No Class (Thur, Oct 31, 2019; Make-up on Nov. 5)
  • Lagrangian Particle Methods for Simulating Conservative Liquid Redistribution and Simulation of Bubble Movement (Tues, Nov 5, 2019)
  • Physically-based Sound Simulation and Rigid-body Sound Simulation (Tues, Nov 5, 2019; Make-up Lecture for Oct 31)
  • Geometric-based Sound Propagation and Robot Navigation with Collision Avoidance v (Thur, Nov 7, 2019)
  • Decentralized Monte-Carlo Tree Search for multi-robot planning and Traffic Simulation (Tues, Nov 12, 2019)
  • Decentralized Collision Avoidance for Multi-Agent Systems and Learning-based Collision Avoidance (Tues, Nov 12, 2019; Make-up Lecture for Nov. 21)
  • Course Project Progress Report (Thur, Nov 14, 2019)
  • Human Motion Synthesis and Simulation and Techniques for Animating Human Athletes (Tues, Nov 19, 2019)
  • No Class (Thur, Nov 21, 2019; Make-up Lecture on Nov 12)
  • Haptics and Modeling and Simulatino of Fur and Hairs (Tues, Nov 26, 2019)
  • THANKSGIVING BREAK (Nov 27-30, 2019)
  • Data-driven Methods to Accelerate Cloth Simulation and GPU-based Differentiable Cloth Simulation (Tues, Dec 3, 2019)
  • Simulation of Relativistic Effects and Fogs & Environmental Effects (Thur, Dec 5, 2019)
  • Line

    COURSE READING MATERIALS

    Line

    Reference Papers Used in Lectures:

  • SIGGRAPH Course Notes on Physically-Based Modeling
  • Supplementary Materials and Reading List for the Class (updated throughout the semester)
  • Additional Notes on Rigid Body Dynamics: Constraint-based Dynamics, and Impulse-based Dynamics

  • Line

    ASSIGNMENTS AND PROJECTS

    Line The class grade of each student is determined by
  • Homework (30%)
  • Class Presentation (20%)
  • Final Project (50%)
  • Line

    POINTERS TO WEBSITES ON PHYSICALLY-BASED MODELING & ANIMATION:

    Line

    SELECTED INDUSTRY

  • Boston Dynamics Inc.
  • Chris Hecker's Corner (Definition Six, Inc.)
  • Dreamworks Animation
  • GamaNetwork
  • Havok
  • IBM Smarter Planet
  • Immersion Corporation
  • Legion Limited
  • Massive Software
  • MAYA (Alias|Wavefront)
  • MSC.Working Knowledge
  • NVIDIA PHYSX
  • Pixar Animation Studios
  • Rhythm & Hues Studios
  • SensAble Technology
  • Walt Disney Animation Studio
  • Weta Digital
  • SELECTED RESEARCH GROUPS:

  • UNC Research Group on Geometric Algorithms for Modeling, Motion and Animation
  • UNC Interactive Collision Detection and Proximity Queries Packages
  • Simlab: Computer Tools for Analysis and Simulation (Cornell)
  • iMAGIS (GRAVIR / IMAG research lab / INRIA)
  • Center for Human Modeling and Simulation(UPENN)
  • MIRALab (University of Geneva)
  • Rutgers Computational Biomedicine Imaging and Modeling (Rutgers)
  • National Advanced Driving Simulator
  • University of Aukland, Bioengineering Research Group
  • SELECTED RESEARCHERS

  • Norman Badler
  • David Baraff (now at Pixar)
  • Ronan Boulic
  • David Breen
  • Chris Bregler
  • Robert Bridson
  • Marie-Paule Cani
  • Stephen Chenney
  • Mathieu Desbrun
  • Petros Faloutsos
  • Ron Fedkiw
  • Eugene Fiume
  • Doug James
  • Jessica Hodgins
  • Michael Gleicher
  • Hyeong-Seok Ko
  • Dimitris Metaxas
  • Brian Mirtich (now at Cognex)
  • James O'Brien
  • Carol O'Sullivan
  • Richard Parent
  • Dinesh Pai
  • Nancy Pollard
  • Jovan Popovic
  • Zoran Popovic
  • Jos Stam
  • Peter Schroder
  • Karan Singh
  • Daniel Thalmann
  • Nadia Magnenat-Thalmann
  • Demetri Terzopoulos
  • Yizhou Yu
  • Michiel van de Panne
  • Andy Witkin's Gallery (now at Pixar)
  • Line

    GEOMETRIC ALGORITHMS AND SOFTWARES AVAILABLE ON THE WEB:

    Line Here are just some possible locations to find geometric software/libraries and algorithmic toolkits you may need:
  • Internet Finite Element Resources
  • A comprehensive collection of geometric software
  • CGAL: Computational Geometry Algorithms Library (in C++)
  • LEDA: Library of Efficient Datatypes and Algorithms (in C++)
  • The Stony Brook Algorithm Repository: Implementation in C, C++, Pascal and Fortran
  • CMU's Computer Vision Homepage
  • Finite element mesh generation and More
  • Machine learning resources
  • Line

    ADDITIONAL REFERENCE MATERIALS

    Line

    Other Reference Books in Computer Animation:

  • Making Them Move: Mechanics, Control and Animation of Articulated Figures, by Badler, Barsky and Zelter, Morgan Kaufmann Publishers, 1991.
  • Advanced Animation and Rendering Techniques: Theory and Practice, by A. Watt and M. Watt, 1992.
  • Computer Animation: Algorithms and Techniques, by Rick Parent, 1999.
  • Other Reference Books in Mechanics:

  • Concepts and Applications of Finite Element Analysis, by R. D. Cook, D. S. Malkus and M. E. Plesha, John Wiley & Sons, 1989.
  • Finite Element Procedures, by K.-J. Bathe, Prentice Hall, 1996.
  • First Course in Continuum Mechanics, by Y.C. Fung, Prentice Hall, 1993.
  • Other Reference Books in Numerical Methods:

  • Numerical Recipes, by Press, Flanner, Teukolsky and Vetterling, Cambridge University Press.
  • Handbook of Numerical Analysis, edited by Ciarlet and Lions, Vol. I - VI, North-Holland, 1994.
  • Other Reference Books in Robotics:

  • Robot Motion Planning, by Latombe, Kluwer Academic Publishers, 1991.
  • Planning Algorithms, by LaValle, Cambridge University Press, 2006.
  • Robot Manipulators: Mathematics, Programming, and Control, by R. P. Paul, MIT Press, 1981.
  • Other Reference Books in Geometry:

  • Computational Geometry (Algorithms and Applications), by de Berg, van Kreveld, Overmars and Schwarzkofp, Springer-Verlag, 1997.
  • Computational Geometry In C (Second Edition), by O'Rourke, Cambridge University Press, 1998.
  • Handbook on Discrete and Computational Geometry, by Goodman and O'Rourke (eds), CRC Press LLC, 1997.
  • Applied Computational Geometry: Toward Geometric Engineering, by Lin and Manocha (eds), Springer-Verlag, 1996.
  • Algorithms in Combinatorial Geometry, by Edelsbrunner, Springer-Verlag, 1987.
  • Computational Geometry (An Introduction), by Preparata and Shamos, Springer-Verlag, 1985.
  • Line

    For more information, contact Ming C. Lin, lin@cs.umd.edu.
    Line

    Copyright 1999-2019. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the author.

    This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.