Rendering engines used in today’s game titles utilize various techniques for hidden surface removal (HSR), different techniques being suitable for different game genres. For example, action games played in closed-in locations such as rooms, caves, and tunnels need an engine allowing fast rendering of a few hundred polygons, a high frame rate, and a high level of details to impress players. Conversely, a game that is taking place outdoors requires quite a different approach. Let’s discuss appropriate approaches for the latter. Not too long ago, games ran in software mode only, without the help of 3D accelerators. With the CPU doing all the work, engines rendered as few pixels as possible, typically with BSP-based scenes and BSP rendering.

Moving Games Outdoors

With the advent of 3D accelerators and the invention of the depth-buffer (or Z-buffer), the strict sorting of polygons slowly faded out of engines, and software engineers started trying out different techniques. Game designers wanted to move their worlds outdoors, and new graphics hardware made such designs possible. As graphics hardware power increases, however, so do requirements for game content and high-quality graphics, creating room to waste processing power with inefficient usage of computing resources. Let’s discuss one technique for hidden surface removal usable in 3D engines, developed while creating some of the games I’ve worked on. The technique, utilizing object occlusion, is for outdoor rendering. The fundamental entities working for us will be so-called occluders, and we’ll come to them soon.

The Scene Hierarchy Tree

One of the first steps toward optimized rendering is keeping objects in a scene organized. Most commercial modeling packages and 3D engines use a scene hierarchy, and for good reason: used smartly, it allows for fast rejection of entire hierar-chy branches based on bounding volume tests, and may also accelerate collision testing. A scene hierarchy tree is a collection of objects (visuals as well as nonvisuals) in an organized fashion. In a tree structure, a scene has its root object, which may have children objects linked to it, and these child objects may have other objects linked to them. The objects may be visuals (characters, terrain, items in the game), as well as nonvisual objects (such as 3D-positioned lights, sounds, dummies, and other helper objects).

Balancing the Tree

When creating the hierarchy tree in a commercial 3D graphics package or in-game editor, keep the tree bal-anced. For example, by linking all your objects to the root level, you lose the benefits of having a hierarchy, because all your objects are in a single list and any processing will just treat them as an array. Grouping objects logically is a big step forward. Hierarchical object linking is usually based on some logical assumptions. For preprocessing purposes, keep multiple adja-cent objects together, linked to one parent object. Object link-ing is also done for other purposes, such as inheriting the par-ent’s position, rotation, and scale. This is achieved by using matrices and matrix concatenation.

Bounding Volumes

A bounding volume is a simple geometrical object roughly representing the volume of a real object’s geometry. It’s as small as possible while still enclosing all vertices of the object. The most suitable geometric objects for bounding volumes are spheres and boxes. For the techniques presented in this article, I recommend using both types and defining a structure representing the bounding volume:

struct S_bounding_volume{
struct{
struct{
float x,y,z;
}min,max;
}box;
struct{
struct{
float x,y,z;
}pos;
float radius;
}sphere;
};

You’re probably already using an HSR technique utilizing bounding boxes or spheres, so why use a combination of both? The answer is simple: speed. While bounding spheres allow for very fast collision detection using a simple distance test, the volume it encloses is often much greater than the actual object it represents (Figure 2). Too often, then, we consider an object to be on-screen when none of its vertices actually would be.

	Figure 2: Visual object with bounding box and sphere. Notice that the sphere is a bit larger than the box.

On the other hand, a bounding box is a closer match to the shape of an object, but tests with boxes are slower. Usually we do a two-pass collision/intersection test, using a bounding sphere in a first pass and oriented bounding box (OBB) in the second pass. Because the first test rejects most invisible or non-clipped objects, the chances that a second test will never be executed are high. At the same time, performing the bounding box test yields more accurate results, leading to fewer objects being rendered.

This mixed bounding volume is also suitable for other pur-poses, such as collision detection or physics.