Contents of Lectures

This page records the material covered at the lectures.

  • Sept 1 Introduction to course (slides: pdf). Game programming history (slides: pdf). Generic game architecture.

    Reading: Chapters 1 and 2 in Dalmau.

  • Sept 6 2D programming techniques (slides: pdf). 3D pipeline overview (slides: pdf).

    Reading: Chapters 11 and 12 in Dalmau.

  • Sept 8 Scalings, rotations, translocations. Homogeneous coordinates and transformations. Euler angles. Quaternions. First programming project handed out. Forming of project groups.

    Reading: Pages 8-18 and 79-91 of Eberly (handout), pages 195-204 of Deloura (handout), pages 1-2 of Munkholm (handout).

  • Sept 13 No lecture this Tuesday

  • Sept 15 Quaternion interpolation. Textures.

    Reading: Pages 205-213 of Deloura (handout from September 8), Chapter 18 in Dalmau.

    The following links give nice additional details (not curriculum): Full mathematical details on quaternions and interpolation can be found in Dam, Koch, and Lillholm, 1998 (pdf). More on environment mapping can be found in two (commercial) expositions from nVIDIA (pdf, http).

  • Sept 20 More on textures. Lighting and shading, local models.

    Reading: Pages 515-530 in Dalmau. Pages 99-112 in Eberly (handout). Slides by Michael Garland (pdf, pdf) and by Anders Backman (pdf).

  • Sept 22 More on local lighting. Global lighting: radiosity.

    Reading: Pages 534-541 in Dalmau. Slides by by Anders Backman (pdf) and by Michael Garland (pdf, pdf).

    Note: Det Danske Akademi for Digital, Interaktiv Underholdning (DADIU) is a recently created collaboration between educational institutions and the Danish computer game industry. It offers what is probably the most serious computer game educational line in Denmark. The idea is to have people taking existing relevant degrees (in computer science, humanities, artistic educations) specialize their educations towards computer game production, and then let these people meet and work together on non-trivial game productions.

    For the upcoming production (final production of first series of students, duration is four weeks in March 2006), there is a shortage of programmers. Hence, for dedicated participants of DM80, participation in this production could be arranged (I have made preliminary contacts with the director of DADIU to that effect).

    If this could be of interest to you, please contact me as soon as possible. If enough people (e.g. five) are interested, I will try arranging the details. Check out further info at DADIUs website.

    Update: The production in question takes place during four (full) weeks in March 2006 (not eight weeks, as previously stated here). The production takes place in Copenhagen. Accommodation (simple) for all four weeks will be arranged and paid for by DADIU. One return ticket to Copenhagen will also be paid for. Alternatively, paid housing can be converted into money covering (parts of) a monthly train-ticket to Copenhagen (so you could sleep at home if desired).

  • Sept 27 No lecture this Tuesday.

  • Sept 29 More on radiosity. Raytracing.

    Slides by Michael Garland (pdf, pdf, pdf).

    The following links give nice additional details (not curriculum): Hugo Elias has some nice illustrations for explaining radiosity. He also explains another way (the hemi-cube method) than form factors for calculating the incoming light for each patch, and has information on patch refinement based on gradients (trying to refine patches at shadow borders). A paper by Willmott and Heckbert empirically compares various methods (including the progressive method mentioned by Dalmau, which fires light from the patch with the currently largest radiosity) for speed and quality of result.

  • Oct 4 Picking (a simple application of ray shooting). Techniques for shadows. Other multi-pass rendering techniques.

    Reading: Slides by Michael Garland (pdf). Rest of Chapter 17 in Dalmau (you may skip pages 541-7 on BRDF).

    The following survey (not curriculum) by Szymon Rusinkiewicz gives more details on BRDF.

  • Oct 6 Scene graphs. Start on AI: choreographed actions, automatons, rule based systems, fuzzy logic.

    Reading: Pages 141-148 of Eberly (handout). Pages 149-179 and 191-194 in Dalmau. Pages 319-329 of Deloura (handout).

    The following links give additional details (not curriculum): For scene graphs, see this very simple introduction by Garret Foster, or this significantly more comprehensive discussion by Avi Bar-Zeev. For information on the RETE algorithm, see e.g. its Wikipedia page, the site for the open source (Java) implementation Drools, or Chapter 2 of the Ph.D.-dissertation of Robert Doorenbos.

  • Oct 11 Chasing and evading. Bresenhams algorithm for straight line movement in tiled environments (and for straight line drawing in GPUs). A bit on patrolling, hiding, and shooting.

    Reading: Chapter 7 in Dalmau. Webpage entitled The Bresenham Line-Drawing Algorithm by Colin Flanagan (handout).

    For a bit of history on the Bresenham algorithm, see its Wikepedia entry (not curriculum).

  • Oct 13 Guest lecture entitled "Ludologi" by Bo Kampmann Walther, Center for Media Studies, University of Southern Denmark.

    Reading: Slides and paper by Bo Kampmann Walther.

  • Oct 18 Fall break (no lecture).

  • Oct 20 Fall break (no lecture).

  • Oct 25 Path finding: Crash-and-turn (for convex obstacles), Dijkstras algorithm, A*-algorithm.

    Reading: Pages 219-236 in Dalmau, pages 254-263 in Deloura, pages 22-26 and 30-31 from the Master thesis (html, doc) by F. Markus Jönsson, 1997.

    The rest of the Master thesis by Jönsson (not curriculum) contains useful information on generating grid-based graphs from maps.

    Note: The deadline for applications for participation in the DADIU March production is Tuesday, November 1. Fill out the application form (only the "Programmør" choice can be marked), supply a CV, and hand in to the lecturer.

  • Oct 27 Simple physics simulation, potential based methods, flocking, swarming. NB: this lecture takes place in U55 to accomodate students from Gymnasium which are visiting Imada this week, and are following various lectures. (This event goes by the name "Brobygning").

    Reading: The paper Flocks, Herds, and Schools: A Distributed Behavioral Model by Craig Reynolds, Computer Graphics, 21(4), 1987. Pages 52-95 in Bourge and Seemann. Pages 237-241 in Dalmau.

    A formal project description for Project II is now available. Note that the deadline for handing in your project idea is Tuesday, November 1. The deadline for the actual project is December 20.

    The recent article How to Prototype a Game in Under 7 Days, by Gabler, Gray, Kucic, and Shodhan on the gamasutra site has interesting advice on the process of generating game ideas and game prototypes fast (not curriculum). Potentially useful for Project II work.

    Note: The correct application form (March 2005 version) is now pointed to by the link in the last note above.

  • Nov 1 More on A*. More on physics based motion. Cinematography/camera placement.

    Reading: Pages 265-282 in Deloura, pages 355-364 in Kirmse, Chapter 16 in Dalmau.

  • Nov 3 No lecture this Thursday.

  • Nov 8 Guest lecture by Nis Haller Baggesen, lead programmer at the Danish game developer Runestone.

  • Nov 10 Rigid body simulation.

    Reading: Lecture notes from SIGGRAPH 2001 course by Witkin and Baraff about Particle System Dynamics and Rigid Body Simulation (Sections 1-5).

    The rest of the course notes are relevant and related reading, but not curriculum.

    The area of physically based modelling in graphics is vast. Simon Clavet maintains a very nice (and large) collection of pointers to scientific papers in the area.

  • Nov 15 Collision detection and response. A bit on OBB-trees.

    Reading: Lecture notes from SIGGRAPH 2001 course by Baraff about Rigid Body Simulation (Sections 6, 8, 9). Paper OBBTree: a hierarchical structure for rapid interference detection by Gottschalk, Lin, Manocha. In proceedings of SIGGRAPH 1996.

  • Nov 17 No lecture this Thursday.

  • Nov 22 More on collision culling, collision detection, and OBB-trees.

    Reading: Lecture notes from SIGGRAPH 2001 course by Baraff about Rigid Body Simulation (Section 7). Paper OBBTree: a hierarchical structure for rapid interference detection by Gottschalk, Lin, Manocha. In proceedings of SIGGRAPH 1996.

  • Nov 24 Terrain representation. Geomipmapping, ROAM.

    Reading: Chapter 14 in Dalmau (you can skip the section on Chunked LOD). Paper ROAMing Terrain: Real-time Optimally Adapting Meshes by Duchaineau et al., in proceedings of Eighth IEEE Visualization conference, 1997.

    For even more info on the ROAM algorithm algorithm, see its homepage (not curriculum). The geomipmapping method is from the paper Fast Terrain Rendering Using Geometrical MipMapping by de Boer, 2000 (paper not curriculum). The chunked LOD method also discussed in Chapter 14 of Dalmau (not curriculum) is from Rendering Massive Terrains using Chunked Level of Detail Control by Thatcher Ulrich, presented at course at SIGGRAPH 02 (see also homepage for paper). For a good list of papers about LOD, see this page of the Virtual Terrain Project (which has lots of information on terrain visualization).

    Note: A censor has been found who is able almost on the original exam dates (which were January 16 and 17). Specifically, he is able January 17 and 18. I will try to get all students approval (signature) for this at the lectures. Please show up.

  • Nov 29 Terrain generation.

    Reading: Paper Realtime Procedural Terrain Generation, by Jacob Olsen, Oddlabs, 2004.

  • December 1 No lecture this Thursday.

  • December 6 Animation. Guest lecture by Agata Przybyszewska (slides).

    Reading: Chapter 15 in Dalmau.

    Another exposition (not curriculum) of basically the same material is chapters 15 and 16 in Advanced Animation and Rendering Techniques by A. Watt and M. Watt, Addison-Wesley, 1992, ISBN 0201544121 (on which Agata based the her lecture).

  • December 8 No lecture this Thursday (note: previously announced as lecture taking place this day, but a Master exam will use the room).

  • December 13 Indoor rendering, portals.

    Reading: Chapter 13 in Dalmau.

    The article Occlusion Culling Algorithms, by Moeller and Haines on the gamasutra site supplements Chapter 13 in Dalmau well (not curriculum).

  • December 15 No lecture this Thursday.

  • December 20 Particle systems.

    Reading: Chapter 19 in Dalmau. Paper Particle Systems - A Technique for Modeling a Class of Fuzzy Objects, by William Reeves. In ACM Transactions on Graphics 2 (2), 1983, pp. 91-108.

  • December 22 No lecture this Thursday.


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