System and method for increasing the performance for real-time rendering of three-dimensional polygonal data

摘要

A process for optimally rendering 3D worlds so that a sufficiently detailed representation of the 3D world is displayed at a frame rate that provides fluidity of motion while maintaining enough context of the world to enable user interaction. A data structure is computed that contains information about how the world is spatially organized. The 3D world is divided into a non-uniform subdivision grid in each of the three dimensions. Each element in the data structure represents one 3D rectangular cell within the spacial subdivision. Each element stores a list of all the objects in the world which occupy any portion of the 3D cell represented by the data element. The subdivision grid and the array are used to determine which portions of the scene are most visually important to the user. An imaginary ray is cast into the subdivision grid from the viewer's perspective along the viewer's line of sight. The first objects rendered are those within the first cell the ray intersects. The next objects that are rendered are those within the second cell the ray intersects. This continues until all objects within each cell that the ray intersects are rendered. Next, objects that are within cells adjacent to each intersecting cell are rendered. This is followed by rendering objects that are two cells away, and so on, until all object are rendered or the allotted time to render a single frame has expired.