DM815 Computer Game Programming III: Physics

Spring 09, 3rd quarter
Rolf Fagerberg

Official Course Description

See the course description at the web pages of the faculty.

Time and Place

With a few exceptions, the schedule is:

The course takes place in weeks 6 through 12. The first lecture is Tuesday, February 3.

Textbook

We will use the following as a textbook for the first part of the course:

Real-Time Collision Detection
By Christer Ericson
Published by Morgan Kaufmann, 2005
ISBN 1558607323, 978-1558607323

The book can be bought in the SDU bookstore. The book has a website which includes errata, among other things.

For the second part of the course, we will use the lecture notes from the Particle Dynamics and Rigid Body Dynamics parts of the 2001 SIGGRAPH Course on Physically Based Modeling by Witkin and Baraff.

Examination

The exam is oral, with grades on the 7-point marking scale. There is a programming project which must be passed in order to attend the exam. The deadline for the project is Monday, March 23, 2009, at 12:00.

The exam date is March 30, and the exam takes place in the Imada seminar room. At the oral exam, you draw an exam question delineating a part of curriculum which you are to present. The details of the exam format and the exact exam curriculum are described at the bottom of the list of exam questions.

There is a spørgetime (session for asking questions on the exam and the curriculum) Friday, March 27, at 12.15 in U49E.

The grades at the exam ended up with the following distribution.

Lectures

Date Time Room Contents Reading
Tuesday, February 3 12-14 Imada seminar room Introduction to course (slides). Introduction to collision detection. Start on bounding volumes. The slides. Chapters 1-2 and sections 4.1-2 in the textbook.
Friday, February 6 12-14 U49E Convex sets, convex hulls, separating planes/axes. More on bounding volumes. Pages 58 (top half) and 64 (top half), and sections 3.6, 3.9, 5.2.1, 4.3 (4.3.3 can be read lightly), and 4.4 in textbook. More on the randomized linear time algorithm for smallest enclosing sphere can be found in Welzls original paper (not curriculum).
Monday, February 9 10-12 U49B The covariance matrix. Minkowsky sum. Rest of bounding volumes. Start on bounding volume hierarchies. Sections 3.11, 4.5-6, and 6.1 in the textbook. More on the covariance matrix can be found in the paper by Gottschalk et al. on OBB-Trees (not curriculum).
Tuesday, February 10 12-14 Imada seminar room More on bounding volume hierarchies. Hand-out and discussion of the project. Sections 6.2-4 in the textbook.
Friday, February 20 12-14 U49E Rest of bounding volume hierarchies. Rest of Chapter 6 in the textbook.
Monday, February 23 10-12 U49B Start on spatial partitioning. Section 7.1 in the textbook.
Tuesday, February 24 12-14 Imada seminar room More on spatial partitioning. Sections 7.2 and 7.3.1-6 in the textbook.
Friday, February 27 12-14 U49E End of spatial partitioning. Rest of Chapter 7 in the textbook. Section 7 in Baraff notes. More on the classic Bresenham line-drawing algorithm mentioned in Section 7.4.2 can be found here (not curriculum).
Tuesday, March 3 12-14 Imada seminar room Start on basic primitive tests. Planes and line segments. Barycentric coordinates. Sections 3.5, 3.6, 5.1.1, 5.3.1, and 3.4 in the textbook.
Friday, March 6 12-14 U49E Triangle-triangle tests. Start on physics simulation: particles. Section 5.2.10 in the textbook. The rest of sections 5.1-4 is fairly simple given what has been covered so far, and is left for your own reading (skimming to get the ideas, not the details, is sufficient). All of the Witkin notes.
Tuesday, March 10 12-14 Imada seminar room Collision response: elastic collisions. Rigid body simulation. Notes by Chad Berchek on elastic collisions. Sections 1, 2, and 6 in Baraff notes.
Friday, March 13 12-14 U49E More on rigid body simulation. Sections 3, 5, and 8 in Baraff notes. Table of physics terms in English and Danish.
Tuesday, March 17 12-14 Imada seminar room End of rigid body simulation. Sections 8 and 9 in Baraff notes.
Friday, March 20 12-14 U49E Binary space partition trees. Chapter 8 in the textbook.

Further Resources

  • David Eberlys large collection of C++ geometry code (open source).
  • Also check the resource page of the course DM80 from fall 2005 (some links stale by now).
  • For specific codes for triangle-triangle tests (the most central of tests), see e.g. the code by Eberly, by Möller, or by Guigue.
  • The following thesis (in Danish) by Kenny Erleben gives a very nice and elaborate exposition of rigid body simulation. It can be seen as a longer alternative to the Witkin and Baraff notes.

Course Evaluation

As part of the Study Boards schedule of course evaluations, a course evaluation has been carried out (after the course, before the exam). The aggregated answers (with comments removed for anonymity, as required by the Study Board) and the teachers plan of actions are now available.

Maintained by Rolf Fagerberg (rolf@imada.sdu.dk)