469ordering. Because this algorithm traverses all of the triangles in the scene, the
order of the traversal is independent of the direction the camera is looking. A
secondary frustum culling step would be required in order to traverse only
visible triangles. A simple BSP tree is shown in Figure 10.47, along with the
tree traversal that would be done for the camera position shown.
Full coverage of BSP tree generation and usage algorithms is beyond our
scope here. See htt p://www.ccs.neu.edu/home/donghui/teaching/slides/ge-
ometry/BSP2D.ppt and htt p://www.gamedev.net/reference/articles/article657.
asp for more details on BSP trees.
10.2.7.5. Choosing a Scene Graph
Clearly there are many diff erent kinds of scene graphs. Which data structure
to select for your game will depend upon the nature of the scenes you expect
to be rendering. To make the choice wisely, you must have a clear understand-
ing of what is required—and more importantly what is not required—when
rendering scenes for your particular game.
For example, if you’re implementing a fi ghting game, in which two char-
acters batt le it out in a ring surrounded by a mostly static environment, you
may not need much of a scene graph at all. If your game takes place primarily
in enclosed indoor environments, a BSP tree or portal system may serve you
well. If the action takes place outdoors on relatively fl at terrain, and the scene
is viewed primarily from above (as might be the case in a real-time strategy
game or god game), a simple quad tree might be all that’s required to achieve
high rendering speeds. On the other hand, if an outdoor scene is viewed pri-
marily from the point of view of someone on the ground, we may need addi-
tional culling mechanisms. Densely populated scenes can benefi t from an oc-
clusion volume (antiportal) system, because there will be plenty of occluders.
On the other hand, if your outdoor scene is very sparse, adding an antiportal
system probably won’t pay dividends (and might even hurt your frame rate).
Ultimately, your choice of scene graph should be based on hard data ob-
tained by actually measuring the performance of your rendering engine. You
may be surprised to learn where all your cycles are actually going! But once
you know, you can select scene graph data structures and/or other optimiza-
tions to target the specifi c problems at hand.
10.3 Advanced Lighting and Global Illumination
In order to render photorealistic scenes, we need physically accurate global
illumination algorithms. A complete coverage of these techniques is beyond
our scope. In the following sections, we will briefl y outline the most prevalent
10.3. Advanced Lighting and Global Illumination