3D Engine Principles

Generating a description of a virtual environment (i.e. position of objects, light sources) doesn't necessarily allow interaction with it. To be able to travel through the environment, render the environment in an efficient way, and to interact with it, the environment data needs to be organized in a way to allow for efficient traversal. This is where a 3D engine comes in.

A 3D engine is a system of methods to handle such tasks such as drawing the world and handling user interactions (i.e. collision detection).

Visible Surface Determination

In a typical 3D environment, there might be thousands of objects. Determining which objects are visible and needs to be drawn has been a classic problem in the development of 3D engines.

The theories for visible surface determination of complex environments have been ound for a while but it was the computer games industry that first made widespread use of them in the 1990s. John Carmack of Id Software, who wrote the engines to the Doom and Quake games, used binary space partition trees partition trees and potential visibility sets in calculating the visible parts of a world. This approach is known as a cell based method, which basically divides the world up into cells and then organizes them hierarchically.

Although the cell based method can run very fast, the problem of this approach is that the environment becomes too static. It becomes nearly impossible to change the world without having to recalculate a lot of data. Another occlusion method is the portal engine, which allows the world to be more dynamic and requires less preprocessing, but which is more CPU intensive to render.

Bsp trees, oct trees, PVSs, and portals can all be generalized as scene graphs. As is true of any graph, a scene graph contains nodes that points to relevant data. To draw the scene, the graph is traversed to find out which nodes should be drawn.

Collision Detection