24.1 Data Reduction

1.1 Game World Organization

Figure 24-1 Fixed Size Grid Database Organization

You could also build a hierarchy of different-sized grids to give you a quadtree:

Figure 24-2 Quadtrees

You can extend this into 3D and get either a fixed size cube organization or oct trees. Keep in mind that you are trying to eliminate work; not just graphics rendering, but also texture loads and animation processing such as collision detection.

The grid need not be regular either, you could also use other boundaries if it suits your data. One example of this is a "portal connectivity" organization inside of a building. In a building with rooms and hallways, the possible list of things that you can see can be represented by a portal connectivity description, which lists the rooms of the building that are visible.

You can further reject more data by testing a list of screen projected portal rectangles against visibility to determine whether to consider data in a particular room or hallway.

Figure 24-3 Portals Connectivity Visibility

Throwing away geometry to eliminate processing does not have to stop at the top level. A common organization at the object level is a bounding volume test to eliminate objects (see gSPCullDisplayList()).

Figure 24-4 Bounding Sphere Test