D Scene Management Using BSP Trees

KEY TOPICS

• BSP Tree Intro
• Binary Tree Basics
• The One-Dimensional BSP Tree
• The Two-Dimensional BSP Tree
• Implementing a 2D BSP Tree
• Drawing Polygons Front to Back
• First BSP Example
• Drawing Objects in the Scene
• Loading Maps from a File
• Putting It All Together
• Enhancements
• Summary

In the real world—not the gaming world, actually—a lot of effort has been put into designing buildings that withstand earthquakes. Of course, you wouldn't want to construct a building with earthquake reinforcement in, say, Kansas. That would be a bit of overkill. But earthquake reinforcement makes sense in places such as Los Angeles and Tokyo. You've got to design your buildings for what works best in their environments. That brings us to the topic of this chapter. In 3D rendering, you want to design your polygon-management technique, also called scene management, for what works best in your game environment. If you can assume that the polygons in the scene are stationary, you can apply some techniques to speed up the rendering. The technique you'll use in this chapter is organizing polygons in a data structure called a binary space partitioned tree, or BSP tree. A BSP tree enables you to store polygons in a way so that you can quickly draw the scene, and later they will help with collision detection and path finding.