CS 341 Computational Geometry in Video Games Theory of Computation

CS 341 Computational Geometry in Video Games
Spring 2009
Audrey St. John

COMSC 341 Computational Geometry in Video Games



There are many challenges that are encountered by the video game industry, covering a broad cross-section of computer science (including computer graphics, robotics, AI, networks). In this course, we will view video games from the perspective of computational geometry.

Computational geometry broadly refers to the study of problems with geometric content; one way of thinking about this is to imagine problems that involve coordinates (2D or 3D usually). Because video games are generally based in some virtual "world" (2D or 3D), it is natural that many geometric problems arise.

This course will cover basic problems from computational geometry that apply to video game technology, including:
  • convex hulls
  • segment intersection
  • triangulation
  • art gallery
  • Delaunay triangulations and voronoi diagrams
  • visibility
  • point location

Further topics may include:
  • collision detection
  • kinetic data structures
  • motion planning
  • map drawing/labeling
  • morphing
  • surface/terrain representation

The textbook for this course is Computational Geometry: Algorithms and Applications by by Mark de Berg, M. van Krefeld, M. Overmars, O. Schwarzkopf.

Course Requirements

This is a seminar, and therefore students are expected to be responsible for presenting and discussing material. Roughly the first half of the semester will consist of lectures and discussions, with either exercises or reading expected weekly. During the second half of the semester, each student will be required to choose and present a topic (more details below). Students will also complete and present a final project (more details below).


  • Exercises and reading (class participation in discussions)
  • Presentation of a topic
  • Project


  • Exercises and reading 30%.
  • Class participation 5%.
  • Presentation of chosen topic 30%.
  • Project 35%.

Presentation and project

Each student is responsible for preparing and presenting a topic of their choosing that considers a geometric problem arising in video games. Potential topics include those listed above in the Overview under "Further topics."

The presentation of a topic will cover an entire week (two class periods); the first class period should be used for a formal presentation of the topic, including:
  • Introduction and description of the problem
  • Applications and motivations
  • Known algorithms or approaches (this could include demonstration of software)
  • Open questions
The second class period should be a discussion, led by the student responsible for the topic. She may choose either to assign exercises or find an interesting paper to discuss.

A significant portion of the course grade is comprised in the project. Each student must come up with a project proposal before the end of February (this should be a 1-2 paragraph description of the proposed project), submitted to me for approval. Projects will be due during the last week of class, with short presentations given by each student on what they completed. Potential ideas include:
  • Implement a video game that uses or demonstrates a problem from computational geometry -- a student may either implement a simple algorithm or use a packaged implementation of an advanced algorithm from a library (e.g., CGAL or Wykobi). I encourage students to use available video game engines as well.
  • Create a comprehensive web site that describes a topic from computational geometry and includes a demo of algorithms.
  • Research a more advanced problem from computational geometry, including finding and reading current research papers. Either create a web site that demonstrates your understanding or give a formal presentation that includes a written report.
Starting the week of 4/6, you must send me biweekly updates on the status of your final project! These status reports will be worth 25% of your final project grade.

Reminder: we are under the Honor code

While I encourage you to talk to your class mates and use resources from the book and internet, I also have to remind you that all the work that you submit should be yours! It is against the honor code to have somebody else do the assignment for you (including tutors) or to copy it from somewhere else (including books or the internet).

Lateness Policy (or lack thereof)

NO late homework will be accepted, except for very special, documented circumstances. Exercises will be due at the beginning of class (usually on a Thursday) and MUST be with you for discussion during class time!