JavaScript EditorFree JavaScript Editor     Ajax Editor 

Main Page
  Previous Section Next Section

Hybrid Approaches

Pure BSPs, portals, and octrees are just general-purpose, academic solutions. Real-world games have specific requirements and often combine these approaches along with other clever ideas to create unique, high-quality solutions. In this section, I will show you some of the hybrid algorithms used by some high-end games today.

Portal-Octree Hybrid

Some games show very detailed and dense indoors environments. Think of a game that takes place in a large castle with rooms full of objects: lamps, tables, chairs, and treasure chests galore. The overall environment gives a sense of density and richness to the player. Also, the design of the game calls for a highly interactive world. We need to be able to push objects, grab items, and drop them wherever we want to. Can we handle this kind of environment with the techniques explained earlier? Although all methods will definitely support such a scenario, performance will not be very good. BSPs, for example, will tend to grow indefinitely, because the triangle count will be extremely high. Even worse, using a BSP will also impose the restriction of geometry being static. How does that fit with our interactivity requirements for the game world?

Portal methods look a bit more promising at the beginning, until you realize that each room is actually composed of a high number of triangles, thus making it slow to test for triangle visibility. You could choose to test for the room walls only, but you need some fast way to test for the visibility of room contents as well.

A better solution to this problem is to use a nested portal-octree system, which combines portal visibility for the rooms and hierarchical culling using an octree for the room contents. Thus, the level is laid out in a series of rooms connected by portals, as in a regular portal renderer. Rooms include the geometry for the room walls only, but not for the contents. Each room must hold a small octree with the contents arranged in it. This octree will only be a few levels deep, but will allow us to test for object visibility hierarchically.

Another benefit of this technique is that the octree must not really hold the object data, but instances to it. By doing so, we can have a room full of chairs with just one chair model, thus reducing the memory footprint. In this type of scenario, level-of-detail policies for the room contents could be easily integrated with the core algorithms, thus creating a complete solution. A global visibility algorithm would be implemented using portals, and octrees would deal with the room contents. This approach also allows objects to be moved around with just a small cost for redoing the affected octree. In addition, level-of-detail processing can be used to ensure that triangles are spent where they can affect the results, not on distant, background objects.

Quadtree-BSP Hybrid

A quadtree-BSP hybrid approach can be used in games where large areas need to be explored, especially if very precise collision detection needs to be used. Here the idea is to divide the game world into a quadtree, stopping the creation process when leaves reach a certain number of triangles or a predefined size. We could start with a level that is one kilometer in size and subdivide until a cell is either below 500 triangles or 10 meters in size. Then, each leaf node would store the geometry in a BSP tree data structure. The implementation details are definitely nontrivial, but the resulting structure has a number of advantages.

Quadtrees converge faster than BSPs do. A quadtree divides the input data by four in each level, whereas BSPs only divide in half. A quadtree would thus be faster in determining the area the player is in. A pure quadtree is not very helpful for collision detection. BSPs, on the other hand, can be configured to speed up this process significantly. (Take a look at Chapter 22 for information on computing collisions with a BSP.) Thus, blending the two structures gives us the best of both worlds. The quadtree allows us to detect where we are quickly, and then a BSP helps us refine our location to the triangle level to perform collision detection efficiently.

      Previous Section Next Section

    JavaScript EditorAjax Editor     JavaScript Editor