System and method for increasing the performance for real-time rendering of three-dimensional polygonal data
First Claim
1. A process for optimizing rendering of polygonal data, representing a three dimensional world capable of being viewed by a user from the viewpoint of a virtual camera, said process comprising the steps of:
- constructing a ray having an orientation coinciding with the orientation of the viewpoint of the virtual camera;
prioritizing objects to be rendered according to each of said objects displacement from said ray; and
rendering said objects according to a priority from said prioritizing step.
5 Assignments
0 Petitions
Accused Products
Abstract
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.
72 Citations
32 Claims
-
1. A process for optimizing rendering of polygonal data, representing a three dimensional world capable of being viewed by a user from the viewpoint of a virtual camera, said process comprising the steps of:
-
constructing a ray having an orientation coinciding with the orientation of the viewpoint of the virtual camera; prioritizing objects to be rendered according to each of said objects displacement from said ray; and rendering said objects according to a priority from said prioritizing step. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A process for optimizing the rendering of polygonal data representing a three dimensional (3D) world having a 3D coordinate system and comprising 3D objects having up to three dimensions, said 3D world capable of being viewed by a user from the viewpoint of a virtual camera, said process comprising the steps of:
-
constructing a 3D boundary that encloses one or more objects in the 3D world; creating at least one sorted list of objects comprising the objects enclosed by said boundary, wherein each said sorted list corresponds with a particular dimension or the 3D world; constructing a subdivision grid according to said sorted list comprising a plurality of 3D cells; and prioritizing objects within said 3D cells to be rendered according the position of said 3D cells relative to the virtual camera. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
-
25. A system for optimizing the rendering of polygonal data representing a three dimensional (3D) world having a 3D coordinate system and comprising 3D objects having up to three dimensions, said 3D world capable of being viewed by a user from the viewpoint of a virtual camera, said system comprising:
-
boundary construction means for constructing a 3D boundary that encloses one or more objects in the 3D world; list creation means for creating at least one sorted list of objects comprising the objects enclosed by said boundary, wherein each said sorted list corresponds with a particular dimension or the 3D world; grid construction means for constructing a subdivision grid according to said sorted list comprising a plurality of 3D cells; and prioritizing means for prioritizing objects within said 3D cells to be rendered according the position of said 3D cells relative to the virtual camera. - View Dependent Claims (26, 27, 28)
-
-
29. A computer program product comprising a computer useable medium having computer program logic stored therein said computer program logic for enabling a computer to optimize rendering of polygonal data representing a three dimensional (3D) world having a 3D coordinate system and comprising 3D objects having up to three dimensions, said 3D world capable of being viewed by a user from the viewpoint of a virtual camera, wherein said computer program logic comprises:
-
first constructing means for enabling the computer to construct a 3D boundary that encloses one or more objects in the 3D world; creating means for enabling the computer to create at least one sorted list of objects comprising the objects enclosed by said boundary, wherein each said sorted list corresponds with a particular dimension or the 3D world; second constructing means for enabling the computer to construct a subdivision grid according to said sorted list comprising a plurality of 3D cells; and prioritizing means for enabling the computer to prioritize objects within said 3D cells to be rendered according the position of said 3D cells relative to the virtual camera. - View Dependent Claims (30, 31, 32)
-
Specification