DM842 Computer Game Programming

Fall 2017
Rolf Fagerberg and Christian Kudahl


Official Course Description

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

Time and Place

The course starts Monday, September 4. For time and place, see the schedule in the course description above.

Textbook

As textbooks/teaching material, we will use the following (all available from the SDU bookstore in time for their use):

  • Computer Graphics Through OpenGL, 2nd edition
    By Sumanta Guha
    Published by CRC Press/Taylor and Francis Group, 2014
    ISBN 9781482258394

    The book has a website.

  • Artificial Intelligence for Games, 2nd edition
    By Ian Millington and John Funge
    Published by CRC Press/Taylor and Francis Group, 2009
    ISBN 9780123747317

    The book has a website.

  • 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.

  • Collision Detection in Interactive 3D Environments
    By Gino van den Bergen
    Published by Morgan Kaufmann/Elsevier, 2004
    ISBN 155860801X

    The book has a website (click on menu entry "Interesting").

Examination

For the oral reexam January 29, 2020, see the list of topics and further infomation.

The exam is oral, with grades on the 7-point marking scale. A programming project must be passed in order to attend the oral exam. The deadline for the project is December 22.

Reading guide for the Guha book when preparing for the oral exam: skip all explanations of OpenGl, and skip exercises. Do read all the teacher's notes.

The exam dates are January 5 and January 12. There is a reexam March 19 (and a deadline for hand-in of rexam in the project March 5).

At the oral exam, you will draw an exam topic delineating a part of curriculum which you are to present in the first part of the examination. More details of the exam form are described below the list of exam topics.

There is a spørgetime (session for asking questions on the exam and the curriculum) Wednesday, January 3, at 10:15 in U177.

Lectures

Date Time Room Contents Reading
Monday, September 4 16-18 Imada seminar room Introduction to course (slides). Some elements of 3D graphics and OpenGL (slides). The slides. Chapter 2 in the textbook. Chapter 3 is not curriculum for the oral exam (and will not be covered in depth at the lectures), but is useful to read with respect to the programming.
Wednesday, September 6 08-10 Imada seminar room Transformations (slides). The slides. Sections 4.1-5 in the textbook. Sections 5.4.1-3 (indtil side 224) in the textbook.
Monday, September 11 16-18 Imada seminar room Rotation around a general axis. Rest of Section 5.4.3 in the textbook (You may also look at the lecturer's informal notes on the proof).
Wednesday, September 13 08-10 Imada seminar room Rotations specified as a change of coordinate system, and its use in the viewing transformation. Affine transformations. The lecturer's notes on change of coordinate system and Section 4.6 in the textbook (read lightly). Sections 5.2 and 5.4.4-8. No proofs of sections 5.2, 5.4.5 and 5.4.7 are curriculum, but you should know the contents of the statements. These sections are summarized in the lecturer's informal notes (in these the proofs are also not curriculum (even if the notes say otherwise)).
Monday, September 18 16-18 Imada seminar room Start on derivation of the perspective projection matrix. Section 19.1.3. An alternative presentation is pages 81-82 in 3D Game Engine Design by David H. Eberly, Morgan Kaufmann, 2001 (handout) and the lecturer's notes (new typed version version, old handwritten version).
Wednesday, September 20 08-10 Imada seminar room More on the derivation of the perspective projection matrix. Section 18.1. An alternative derivation (not relying on Appendix A, which is not curriculum) is the lecturer's notes (new typed version version, old handwritten version).
Monday, September 25 16-18 Imada seminar room End of derivation of the perspective projection matrix. Start on light and shading (first pages of slides). Section 11.1 in the textbook.
Wednesday, September 27 08-10 Imada seminar room Handout of the project. More on light and shading (slides). Sections 11.1-9, 11.11.1-2, 11.12. 11.14 in the textbook. In the course, we only cover the (Blinn-)Phong light model. Many others models (as well as empirically based reflection data sets) exists, see Section 11.13 or (not curriculum) the Wikipedia page on BRDFs for overview and directions. Also, the paper (not curriculum) Experimental Validation of Analytical BRDF Models (Ngan, Durand, Matusik, SIGGRAPH 2004) is a nice read with good introductory value. In particular, it explains (presentation slides of paper, page 44-52) better than the textbook (pages 420-22) why using the half-vector in the specular term is a better choice than using the reflection vector (in particular, the claim of Example 11.3 in the textbook that they are essentially equal is only true when the eye vector lies in the plane determined by the normal vector and the light vector). Empirically, using the half-vector is in better correspondance with real life - specular reflections at oblique angles are not round (which turns out to be the case when using the reflection vector), but vertically elongated (which turns out to be the case when using the half-vector), as can be seen on any photograph of a harbor at night.
Monday, October 2 16-18 Imada seminar room Textures (slides). Chapter 12 (excluding Section 12.4.2), Section 13.6 (actual math of 13.6.1 is not curriculum, the method in Section 13.6.2 is both simpler and much easier to create textures for). Sections 13.9-10 (actual math of 13.9 is not curriculum - think instead of the normal vectors of Figure 13.27 being stored in a texture).
Wednesday, October 4 08-10 Imada seminar room Various smaller subjects (slides). Change of normal vectors during transformations. Barycentric coordinates. Sections 13.1-5. Sections 13.7-8. Section 4.8, Chapter 9. Section 6.2. Sections 11.11.5-6. Sections 7.1-3. The lecturers notes on barycentric coordinates is an alternative to Section 7.2.
Monday, October 9 16-18 Imada seminar room Perspectively correct interpolation via barycentric coordinates. Clipping. Page 83 in 3D Game Engine Design by David H. Eberly, Morgan Kaufmann, 2001 (handout). Sections 14.1-2.
Wednesday, October 11 08-10 Imada seminar room Rasterization, Bresenham's algorithm. Euler angles. Start on quaternions. Section 14.3. Pages 566-567, 569-571, 578-580 (note in particular Remark 14.7) of Section 14.4. Sections 6.3 and 6.4.1.
Monday, October 23 16-18 Imada seminar room End of quaternions. Midterm course feedback. Start on AI. Section 6.4.2 (except for page 281). Lecturers notes on the use of quaternions for interpolation (takes the place of page 281). Overview of representations of rotations.

Date Time Room Contents Reading
Monday, October 2316-18Imada seminar roomAI for Games,
Movement behaviors,
kinematic
From textbook [MF]: Ch. 1, 2, 3.1-3.2.
Wednesday, October 2508-10U168Movement behaviors,
steering and delegated
[MF] Ch. 3.3
Monday, October 3016-18Imada seminar roomMovement behaviors
Combined, Coordinated, Physics
[MF] 3.4-3.8
Wednesday, November 108-10U168 Movement behaviors
Combined, Coordinated, Physics
[MF] 3.4-3.8
Monday, November 616-18Imada seminar room3D Movement and Pathfinding[MF] 3.9, 4.1-4.3.3
Links: Pathfinding animation
Wednesday, November 0808-10U168Pathfinding[MF] 4.3.4-4.6
Monday, November 1316-18Imada seminar roomDecision making: Decision trees, State Machine, Behavior Trees[MF] 4.7-4.9, 5.1-5.2, 11.3-11.4, 5.3-5.4
Wednesday, November 1508-10 Imada seminar room Decision making: Fuzzy Logic and Goal-Oriented Behavior[MF] 5.5-5.9
Monday, November 2016-18Imada seminar roomTactical and Strategic AI[MF]6.1-6.2.7
Wednesday, November 2208-10Imada seminar roomTactical Analysis,
Board Games AI
[MF] 6.2.8-6.4; 8.1-8.2;
Moday, November 27 16-18 Imada seminar room Board Games AI [MF] 8.2-8.2.5.
Links: Monte Carlo Tree Search

Date Time Room Contents Reading
Wednesday, November 29 08-10 U168 Physics simulation of particles. From SIGGRAPH course on Physically Based Modeling: slides and notes (derivation of the midpoint method is not curriculum) on Differential Equation Basics Particle Dynamics, slides and notes (Section 6 is not curriculum) on Particle Dynamics. Notes by Chad Berchek on elastic collisions of balls in 2D (in 3D, simply change the separating line to a separating plane in the last half of the notes). The math left out in the derivation in the 1D part in the first half of the notes can be found in these notes by Patrick Rutkowski (not curriculum).
Monday, December 4 16-18 Imada seminar room Physics simulation of rigid bodies - equations of movement. From SIGGRAPH course on Physically Based Modeling: slides and notes on Rigid Body Dynamics, sections 1-2 (none of the proofs are curriculum). Overview over terminology (English and Danish) for physical quantities underlying rigid body simulation.
Wednesday, December 6 08-10 U168 Simulation of rigid bodies - collision handling. From SIGGRAPH course on Physically Based Modeling: notes on Rigid Body Dynamics, sections 6 and 8 (none of the proofs are curriculum).
Monday, December 11 16-18 Imada seminar room Physics simulation of rigid bodies - contact forces. Start on collision detection. From SIGGRAPH course on Physically Based Modeling: slides and notes on Rigid Body Dynamics, sections 9 and 7 (none of the proofs are curriculum).
Wednesday, December 13 08-10 Imada seminar room Collision detection: spatial partitioning. Handout (in Blackboard entry for the course): Collision Detection in Interactive 3D Environments (Gino van den Bergen), Section 5.2 (pages 184-189 are not curriculum).
Monday, December 18 16-18 Imada seminar room Collision detection: end of spatial partitioning, model partitioning. Handout (in Blackboard entry for the course): Collision Detection in Interactive 3D Environments (Gino van den Bergen), End of Section 5.2 (pages 184-189 are not curriculum). Section 5.3 (pages 203-206 can be read lightly, and Section 5.3.4 is not curriculum).
Wednesday, December 20 08-10 Imada seminar room Collision testing between basic primitives. Handout (in Blackboard entry for the course): Collision Detection in Interactive 3D Environments (Gino van den Bergen), Chapter 3. For time reasons, we covered only 3.1 to 3.3, and only this is curriculum. [Reading the parts of 3.4 not dealing with polygons (polygons are not needed, as they can be converted to triangles) is suggested if you would like to get full coverage of testing relevant primitives].

Course Evaluation

As part of the Study Board's schedule of course evaluations, a course evaluation has been carried out. 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)