Programming assignments #3 and #4 - 3D Video Game

CS 248 - Introduction to Computer Graphics
Autumn Quarter, 1999
Marc Levoy
Handout #8

Assignment #3 Demos on Monday, November 15
Assignment #4 Demos on Friday, December 3
Assignment #4 Writeup due on Tuesday, December 7 by 5:00pm

Your assignment is to write a 3D video game using OpenGL. You are free to design and implement any sort of game you like, as long as it incorporates the required functionality described below. For purposes of this project, we consider a 3D video game to be an interactive 3D computer graphics application which has a challenging goal, is fun to play, and incorporates some concept of scoring or winning and losing. It is not required that your game idea be original, but originality will be rewarded with extra credit. If you have any questions about whether your idea meets the criteria for a 3D video game, please ask the course professor or a TA.

You are permitted (and encouraged) to form teams of 2-3 people and partition the work among the team members. The work expected from each team will be proportional to the size of the team. You can use the class newsgroup su.class.cs248 to find prospective team members.

Required functionality

• 3D viewing and objects. Your game environment must be a scene consisting primarily of 3D elements, as opposed to only "flat," 2D sprite-based graphics. Your game should provide perspective views of your 3D scene where at least sometimes the viewpoint changes smoothly under some combination of user and program control. To produce these views, you should implement transformation, clipping, and hidden-surface removal of your 3D scene using the OpenGL pipeline.

• User input. Your game must allow players to interact with the game via keyboard or mouse controls. Alternatively, you can use joysticks or more elaborate user interface devices (provided that you can supply the required devices for your program demonstration sessions; see below).

• Lighting and smooth shading. Your game must contain at least some objects that are "lit" using OpenGL's lighting model. For these objects, you'll need to define normal vectors and materials, as well as create one or more light sources. See Chapter 5 of the OpenGL Programming Guide for details on implementing lighting and shading.

• Texture mapping. You must implement texture mapping for at least one of the 3D objects in your video game. In its most common form, texture mapping applies a detailed 2D image or pattern to 3D geometric primitives. Texture mapping is used extensively in modern 3D video games to improve graphic realism. Chapter 9 of the OpenGL Programming Guide describes how to implement a variety of texturing techniques. If you want, you can use your paint program from Assignment #1 to create 2D texture maps in the .PPM image format, and borrow part of the xsupport source code for loading image files in this format.

In addition to these basic requirements, your game should incorporate some of the more advanced computer graphics techniques listed below, depending on the size of your project team. In particular, you are required to implement at least 2*N of these additional techniques, where N is the number of people on your team (i.e. groups of three people need to implement six techniques, individuals working alone are required to implement only two, etc.). Of course, you are encouraged to implement as many of these techniques as you can, depending on the requirements of your particular game engine, as well as using any other ideas you read about or invent on your own. Extra effort will be rewarded with extra credit.

• On-screen control panel. Many 3D video games reserve part of the display area for an on-screen control panel, which may include text or 2D graphical elements for user controls, scoreboards, etc. Flight simulator games often use 2D graphical overlays on the 3D world for "Heads Up Displays (HUDs)." You can implement a control panel for your game using a variety of techniques in OpenGL, such as orthographic projection and the stencil buffer. Text primitives are not explicitly supported with OpenGL, but GLUT and the window system extensions (GLX, WGL, etc.) both provide commands to help render text strings.

• Hierarchical Scene Graph. Many 3D graphics applications maintain their constituent objects and sub-objects in a tree-like data structure called a hierarchical scene graph. The scene graph provides a logical organization for the objects in the 3D world, and allows for efficient constructs and operations such as instancing, hierarchical transforms, nested bounding volumes, and traversals of the scene graph for rendering or collision detection. Object hierarchies are discussed in Chapter 7 of the textbook.

• View frustum culling. In video games with complex 3D environments, it is necessary to limit the number of 3D primitives drawn each frame in order to maintain interactive rendering rates. One way to do this is to avoid drawing any 3D objects which are outside of the viewing frustum of the camera. You can pre-compute rough bounding volumes for hierarchical objects or parts of your 3D world, and then test each bounding volume to verify that some part of it intersects the view frustum before drawing its contained objects each frame.

• Level of detail control. Another way to limit the number of 3D primitives drawn each frame is to implement level of detail (LOD) control in your game. One simple method of LOD control involves creating multiple versions of some of your 3D objects, varying in geometric complexity (such as 10, 100, and 1000 polygons). Then, before drawing the objects each frame, you can pick the most appropriate version of the object to render, depending on such metrics as the distance of the object from the viewer, the complexity of the current scene, or a user-selectable detail level.

• Occlusion culling. Yet another way to maintain good game performance with complex environments is by performing occlusion culling. Similar to view frustum culling, this technique involves using a conservative computation to avoid drawing any parts of the 3D scene which won't be seen by the viewer because they are hidden behind other objects. For static environments such as buildings, you might pre-compute which regions of space (such as rooms) are impossible to see from other regions (due to occluding walls, for example). (Don't confuse occlusion culling with simple hidden-surface removal, which is required for your video game.)

• Procedural and physically-based modeling. In addition to using scanned or hand-modeled objects to populate the 3D worlds, some video games use procedurally computed models. Chapter 20 of the textbook describes examples of procedural modeling, including fractally-generated mountainous terrains and L-grammars for generating models of plants. Procedurally generated textures may be used to simulate effects such as fire, smoke, and clouds.

• Collision detection. Video games often contain moving objects which trigger events when they collide, such as projectiles shot at a target. Collision detection can also be used to prevent the user from passing through walls or other objects. You can implement collision detection in a variety of ways; the simplest might involve comparing bounding volumes of objects to decide if they intersect or not. The Graphics Gems series of books describes efficient intersection testing algorithms for a number of different geometries.

• Simulated dynamics. Your video game implementation might include modeling dynamic behaviors and physics for objects in the 3D world. For example, the wheels of a vehicle might react realistically as they move over rough terrain, or a door might swing open differently depending on the force exerted by the player.

• Multipass rendering effects. OpenGL makes it possible to easily implement a wide variety of realistic rendering effects. Many of these effects can be achieved by drawing the scene multiple times for each frame, varying one or more parameters each pass through the scene. Examples of such effects include soft shadows, full scene antialiasing, motion blur, depth of field, bump-mapping, reflections, refractions, and compositing. Good sources of information on implementing these and other effects are in Chapters 10 and 14 of the OpenGL Programming Guide, and in the OpenGL tutorials available on the Web.

• Parametric curved surfaces. OpenGL can directly display only simple convex polygons; however, you might create a 3D model for your video game which includes smoothly curved surfaces represented mathematically by a small number of parameters. Chapter 11 of the textbook and Chapter 12 of the OpenGL Programming Guide describe how to represent and manage the display of smooth surfaces such as NURBS. Be wary about performance if you use NURBS in OpenGL; use them judiciously.

• Advanced image-based techniques. In an effort to increase graphical realism and maintain fast performance, many video games mix traditional 3D graphics rendering with 2D image-based graphics. Although 2D texture mapping is an example of a basic image-based technique, more advanced techniques such as environment mapping, billboarding, and projective textures are possible. Other ideas for image-based techniques include precomputing multiple 2D images ("sprites") of a object from different orientations, and then choosing the most appropriate sprite to warp and render in the 3D scene. See the pointers on the assignment Web page for examples and information on implementing advanced image-based techniques.

• Sound. Adding appropriate audio effects to your game can provide a more compelling experience for the player. The details of sound effect creation and implementation of audio playback in your game engine will depend on your hardware configuration; some pointers to relevant documentation and sample sound effects are included on the assignment Web page.

• AI. Some video games include computer-controlled agents that require a significant degree of artificial intelligence. Many of the techniques taught in a basic AI course are applicable to video game development, and some links to more detailed information on game AI are included on the course Web page for the assignment. If you have any doubts about whether a technique you are using qualifies as "AI" for this assignment, ask us.

• Networked multi-player capability. Networked multi-player video games allow more than one player to play at once, either collaboratively or in competition, using computer networks such as the Internet. If you add multi-player capability to your video game, you'll need to deal with issues such as network latency by using predictive techniques. Some pointers to basic information on implementing networking in games will be provided on the assignment Web page.

• Game level editor. Some video games are accompanied with supplementary computer graphics applications which allow users to design their own game levels (scenes). If you develop your own custom application to construct levels while writing your game, you might consider packaging it as a separate utility program for end-users to enjoy as well!

A few hints

• This project is purposefully designed to be more open-ended than the first two assignments of the course. You will be expected to do a considerable amount of learning on your own, particularly in gaining experience with programming in OpenGL. In order to assist and inspire you, a web page is available at the URL:

       http://graphics.stanford.EDU/courses/cs248-99/proj3/
  

  This page includes pointers to OpenGL tutorials, information on game development, useful utility programs, and sources for 3D models and other game content. Additional examples of OpenGL code from the programming guide and OpenGL and GLUT distributions are available in the class directory in /usr/class/cs248/assignment3. Of course, you are responsible for understanding and implementing your own video game code; copying of source code from others is prohibited.

  Please take advantage of the opportunity to consult the course professor and TAs with questions concerning development of your particular video game. If there are computer graphics techniques not covered in the course that you would like to implement, we will usually be able to point you to an appropriate source of information.

• Interactive 3D graphics programs such as video games place special demands on computer hardware. If your 3D world is particularly large or complex, or if you use certain OpenGL rendering features (such as texture mapping), you will probably need special graphics hardware in order to get real-time performance. Note that the SGI machines in Sweet Hall do not implement texture mapping in graphics hardware, so games making intensive use of texturing will suffer performance limitations on these systems. Modern PC systems with fast 3D graphics accelerator cards will usually yield better texturing performance than the SGI machines in Sweet Hall. If you develop your game on multiple platforms, it will probably be useful to add options to disable expensive features (such as texturing) on request. The performance of your video game is important, so do not implement too many expensive rendering features if the gameplay is negatively impacted! There are some pointers on the assignment Web page to sources of information on maximizing OpenGL performance.

• Most successful video games include richly detailed 3D models, textures, sounds, and other content for representing the game world and characters. You have several options available in creating the 3D models for your video game:
  • Simple models can be sketched on graph paper, and the coordinates manually typed into your source code.
  • Models can be procedurally generated, as mentioned above.
  • You can use a 3D modeling package and export the model in a format your program can read. The assignment Web page will contain pointers to several freely available modeling packages.
  • The GLUT library provides functions for drawing a few simple 3D shapes (sphere, cube, teapot, etc.)
  • You can find a wide variety of 3D models available on the Web (see the pointers on the assignment Web page). These may need to be converted to a format your program can use.

• You are free to develop your video game on any computer platform that supports OpenGL, provided that you will be able to demonstrate your program at the two required demonstration periods at Sweet Hall. If your program cannot run on the Sweet Hall SGI machines, you will be responsible for bringing a system on which to run your video game. We are currently investigating the possibility of making a PC running Windows with a 3D graphics accelerator and sound card available for testing and demos in Sweet Hall, but we cannot yet make any guarantees. Even if we do succeed in installing a PC, demand will be high, so you should be prepared to bring your own, or collaborate with other groups in different demo time slots to bring a PC. Versions of OpenGL for most common computing platforms are available for download at sites pointed at from the assignment Web page.

  To keep things simple, our recommendation is to develop your video game on the Sweet Hall SGI systems. OpenGL is window system independent, so an additional toolkit is necessary to provide the necessary windowing and input event management; for this we recommend using the GLUT package. GLUT is used for all the examples in recent editions of the OpenGL Programming Guide, and is available for most all common computing platforms. An example program and Makefile using OpenGL and GLUT on the Sweet Hall SGI machines is available in /usr/class/cs248/assignment3/example.

  GLUT offers a very limited set of user interface widgets (little more than menus). If you require more extensive user interface functionality, we recommend the MUI toolkit; it is very easy to use, and is written entirely on top of GLUT and OpenGL. The MUI libraries are available in the class directory, and documentation for MUI is available on the Web (see the assignment Web page for the pointer). You are free to use other user interface toolkits of your choice.

• In the course of designing and implementing your video game, keep in mind that CS248 is a computer graphics course. Focus your efforts on the computer graphics techniques underlying the game; don't spend the majority of your time on game design or object modeling if the graphics engine will suffer as a result!

Video game submission requirements

Assignment #3 will serve as a checkpoint on the progress of your video game. On Monday, November 15 you will demonstrate your program to a member of the CS248 course staff. No writeup or submission of source code or other files is required for this phase of the project. To show reasonable progress, your "gameplay" should be basically working, and most of the required graphics functionality (3D viewing, user input, lighting, and texture mapping) should be implemented. The 2*N "advanced" techniques need not be in place. At the demo, we will give you feedback about your game, and we will discuss with you your plans for assignment #4. However, your grade for assignment #3 will be based only on the functionality you demonstrate on November 15.

Your final video game (assignment #4) will be demonstrated on Friday, Dec. 3. In addition to the CS248 course staff, a jury of computer graphics experts from industry and academia will be on hand to evaluate your programs as part of a video game competition. There will be one grand prize - an all-expenses-paid trip to Siggraph 2000 in New Orleans next summer, one second-place prize - dinner for two at Il Fornaio in Palo Alto and a copy of the Siggraph '99 Electronic Theater videotape, and three third-place prizes - a copy of the Siggraph '99 Electronic Theater videotape. If the grand prize is won by a team, it must be split among the team members. All other prizes will be duplicated as necessary to cover the team.

Final writeups and code and content submission for assignment #4 will be due on Tuesday, Dec. 7 at 5:00pm. At that time you should include a README file which describes how to build and run your video game, as well as explaining the computer graphics techniques you used. Also, your README file should include references to any external sources you referred to for inspiration, and should indicate how your 3D models and other game content were obtained. To submit your video game files, simply change the current directory to your assignment #4 directory and run the submit script, as you did for the first two assignments. Remember - no late demonstrations or writeup submissions will be accepted for assignment #4.

Good luck, and have fun!