#### Department of Computer Science College of Arts and Sciences The University of North Carolina at Chapel Hill

COMP290-072: Physically-Based Modeling, Simulation and Animation

# COMP 290-072: Physically-Based Modeling, Simulation and Animation

## Instructor: Ming C. Lin

Time and Place: MW 12:30-1:45pm, SN011
Office Hours: MW 2:00-3:00pm, SN223
Prerequisites: COMP205 (Scientific and Geometric Computing) and COMP235 (Images, Graphics and Vision) OR Instructor's approval
Textbook: Course Notes and In-Class Handouts
TA: Scott Cooper (SN035, 962-1755, scooper@cs.unc.edu; Office Hours: TBA)

## List of Final Projects CHECK OUT THESE VIDEO CLIPS !!!

• Course Overview
• Lectures and Approximate Schedule
• Assignments and Projects
• WEBS of Physically-Based Modeling & Animation
• Geometric Algorithms & Software Available on the Web
• Conferences in Related Areas
• ### COURSE OVERVIEW:

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 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
• Rapid Prototyping
• Haptic Rendering
• Computer Game Dynamics
• Robotics and Automation
• Medical Simulation and Analysis
• 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.

### LECTURES AND APPROXIMATE SCHEDULE

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 (Wed, Jan 12, 2000)
• MLK, NO CLASS (Mon, Jan 17, 2000)
• Basics of Motion Generations for Animation (Wed, Jan 19, 2000)
• Basics of Motion Planning (Mon, Jan 24, 2000)
• NO CLASS DUE TO SNOW STORM (Wed, Jan 26, 2000)
• Motion Planning for Animation & VR (Mon, Jan 31, 2000)
• ODE Basics: Initial Value Problem (Wed, Feb 2, 2000)
• Particle Dynamics (Mon, Feb 7, 2000)
• Particle Systems (Wed, Feb 9, 2000)
• Constrained Dynamics (I) (Mon, Feb 14, 2000)
• Constrained Dynamics (II) (Wed, Feb 16, 2000)
• Special Topic: Inverse Kinematics (Mon, Feb 21, 2000)
• Collision Detection: LP & 2D Techniques (Wed, Feb 23, 2000)
• Special Topic: Randomized Motion Planning (Fri, Feb 25, 2000)
• Collision Detection: GJK and Voronoi Walking (Mon, Feb 28, 2000)
• Collision Detection: BVH's & Spatial Partitioning (Wed, Mar 1, 2000)
• Proximity Queries for Large, Dynamic Environments (Mon, Mar 6, 2000)
• Project Proposal (Wed, Mar 8, 2000)
• SPRING BREAK (Mar 10-19, 2000)
• Basics of Rigid Body Dynamics (Mon, Mar 20, 2000)
• Rigid Body Dynamics: Impulse-Based Simulation (Wed, Mar 22, 2000)
• Rigid Body Dynamics: Constrained-Based Simulation & Friction (Mon, Mar 27, 2000)
• Dynamics of Juggling (Wed, Mar 29, 2000)
• 3-DoF Haptic Rendering (Mon, Apr 3, 2000)
• 6-DoF Haptic Rendering (Wed, Apr 5, 2000)
• Applications of Particle Systems and Cloth Simulation (Mon, Apr 10, 2000)
• Project Update (Wed, Apr 12, 2000)
• Intro to Non-Rigid Body Dynamics (Mon, Apr 17, 2000)
• Simulating Deformation Using FEM (Wed, Apr 19, 2000)
• Anatomy-Based Modeling and Animation (Mon, Apr 24, 2000)
• Hardware Accelerated Computation (Wed, Apr 26, 2000)
• Timewarp Rigid Body Dynamics (Mon, May 1, 2000)
• AI for Games (Wed, May 3, 2000)

### Reference Papers Used in Lectures:

• SIGGRAPH Course Notes on Physically-Based Modeling
• Reading List for the Class (updated throughout the semester)

• ### ASSIGNMENTS AND PROJECTS

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

### RESEARCH GROUPS:

• UNC Research Group on Modeling, Physically-Based Simulation and Applications
• UNC Interactive Collision Detection Libraries
• 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)
• I.W. Hunter's Biorobotics, Newman Laboratory (MIT)
• Iowa Driving Simulator
• University of Aukland, Bioengineering Research Group
• Bio-Engineering Animations
• ### RESEARCHERS:

• David Baraff (now at Pixar)
• David Breen
• Chris Bregler
• Jessica Hodgins
• Michael Gleicher
• Dimitris Metaxas
• Brian Mirtich (now at MERL)
• Richard Parent
• Daniel Thalmann
• Demetri Terzopoulos
• Andy Witkin's Gallery (now at Pixar)
• ### INDUSTRY

• Boston Dynamics Inc.
• Engineering Animation Inc.
• Chris Hecker's Corner (Definition Six, Inc.)
• HT Medical (Surgical Simulation)
• Ipion Virtual Physics
• Kinetix 3D Studio
• MAYA (Alias|Wavefront)
• Mathengine
• Mechanical Dynamics Inc.
• Motion Factory
• MSC.Working Knowledge
• SensAble Technology
• Symbolic Dynamics
• Telekinesys
• ### GEOMETRIC ALGORITHMS AND SOFTWARES AVAILABLE ON THE WEB:

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

### 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: The Art of Scientific Computing, by Press, Flanner, Teukolsky and Vetterling, Cambridge University Press, 1986.
• 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.
• 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.