Abstract:

To keep avatars and other moving objects on the ground in virtual environments, it is necessary to find the points where these objects should contact the terrain. This is often done using collision detection; however, this is inefficient, because general collision detection solves a problem that is inherently more complex than merely determining terrain contact points. Because the Quick Oriented Terrain Algorithm (QOTA) focuses solely on the problem of intersecting lines of a predetermined orientation with a terrain model, it provides very rapid support for terrain following. For example, given a 13,000 polygon terrain, QOTA running on a 250MHz R4400 MIPS processor can calculate an intersection point in less than 19 microseconds (1.9 x 10-5 seconds). Given a preferred orientation, such as the direction of the gravity vector, for the lines to be intersected with a terrain, QOTA uses a pre-processing step that sorts the terrain polygons into a quadtree and adds bounding boxes and polygon edge equation parameters to speed up polygon containment checking. In the example above, this preprocessing takes approximately 2 seconds. In addition to terrain following, QOTA is useful for detecting certain limited kinds of collision detection and determining containment.