CULLING OCCLUSIONS WHEN RENDERING GRAPHICS ON COMPUTERS
An occlusion culling system is provided. In various embodiments, the occlusion culling system can combine a hierarchical object space tree with image space occlusion queries to reduce the number of occlusion queries that are issued to a GPU. In various embodiments, the occlusion culling system can enable culling of dynamic objects, identification of sections of a hierarchical tree representing objects to be rendered, and continuous refinement of the object hierarchy. The occlusion culling system can perform further refinements to reduce the number of occlusion queries that are issued to the GPU during rendering of computer graphics.
1 . A method performed by a computing system for reducing occlusion queries when displaying multiple objects, comprising:
receiving a set of objects, the set of objects associated with nodes in a hierarchical tree data structure and together defining a model, each object defining a portion of the model and identified by a set of coordinates associated with an object space;
receiving an indication of a view frustum, the view frustum identifying a region of a three-dimensional coordinate system into which the objects are transformed;
determining whether a specified object of the set of objects is within the view frustum, the determining comprising:
computing whether the specified object is within the view frustum, outside the view frustum, or intersects the view frustum; and
when the object intersects the view frustum,
adding the specified object to a list of hidden objects when the specified object is associated with a leaf node of the hierarchical tree data structure, and
recursively adding children of the node associated with the specified object that intersects the view frustum to the list of hidden objects when the children are associated with leaf nodes of the hierarchical tree data structure; when the specified object is inside the view frustum after previously being hidden, issuing an occlusion query for the specified object; and
when a result of the occlusion query indicates that greater than a threshold number of pixels will be displayed for the specified object, causing the specified object to be rendered.
2 . The method of claim 1 wherein the recursively adding further comprises:
adding a second object associated with a child node of the specified object to a list of objects that are outside the view frustum when the second object does not intersect the view frustum and is computed to be outside the view frustum.
3 . The method of claim 1 wherein the recursively adding further comprises:
adding a second object associated with a child node of the specified object to a list of hidden objects when the second object does not intersect the view frustum but is inside the view frustum.
4 . The method of claim 1 further comprising:
updating a time bounding volume for the specified object, the time bounding volume indicating a time at or after which the specified object should be analyzed again prior to rendering; and
scheduling an event relating to the specified object, the event causing the specified object to be analyzed again prior to rendering and scheduled upon the expiry of the time bounding volume.
5 . The method of claim 1 wherein the occlusion query is performed by a hardware graphics processing unit.
6 . The method of claim 1 further comprising issuing an occlusion query when the specified object is inside the view frustum after previously being hidden.
7 . The method of claim 1 further comprising issuing an occlusion query when the specified object is associated with a leaf node of the hierarchical tree data structure and intersects the view frustum after previously being hidden.
8 . The method of claim 1 further comprising causing the specified object to be rendered when the result of the occlusion query indicates that greater than a threshold number of pixels will be displayed for the specified object and the specified object is associated with a leaf node of the hierarchical tree data structure.
9 . The method of claim 1 further comprising adding the specified object to a list of hidden objects when the result of the occlusion query indicates that greater than a threshold number of pixels will not be displayed for the specified object.
10 . The method of claim 1 further comprising refining a list of hidden objects by performing an occlusion refinement wherein a second object is marked as hidden when all children nodes of the node associated with the second object are marked as hidden.
11 . The method of claim 1 further comprising refining a list of objects that are outside the view frustum by performing a frustum refinement wherein a parent node of a node associated with a second object is marked as being outside the view frustum when the second node's sibling nodes are marked as being outside the view frustum.
12 . A system for reducing occlusion queries when displaying multiple objects, comprising:
a set of modeling information that describes a geometric model of a group of objects that can be displayed;
a transformation component that receives the set of modeling information and a selection of a viewing frustum, the viewing frustum establishing a subset of the set of modeling information that is to be displayed;
a graphics processing unit that efficiently handles occlusion queries wherein an occlusion query identifies an object and the graphics processing unit provides an indication of a number of pixels that correspond to rendering the object; and
an occlusion culling component that identifies an occlusion query to issue to the graphics processing unit based at least on whether the object was previously visible and is presently not outside the viewing frustum so that the graphics processing unit can provide an indication of whether the object is to be rendered.
13 . The system of claim 12 wherein the occlusion culling component identifies the occlusion query to issue to the graphics processing unit based on whether the object presently intersects the viewing frustum.
14 . The system of claim 12 wherein the occlusion culling component identifies the occlusion query to issue to the graphics processing unit based additionally on whether the object was previously hidden and is presently inside the viewing frustum.
15 . The system of claim 12 wherein the occlusion culling component identifies the occlusion query to issue to the graphics processing unit based additionally on whether the object was previously hidden, presently intersects the viewing frustum, and is associated with a leaf node of a hierarchical tree data structure corresponding to the set of modeling information.
16 . The system of claim 12 wherein the occlusion culling component issues the occlusion query to the graphics processing unit when analyzing a list of visible objects.
17 . The system of claim 12 wherein the occlusion culling component issues the occlusion query to the graphics processing unit when analyzing a list of hidden objects that are now visible.
18 . A computer-readable medium storing computer-executable instructions that, when executed, cause a computing system to perform a method for reducing occlusion queries when displaying multiple objects, the method comprising:
updating motion parameters relating to an object;
determining whether a flag has been set indicating that the object has moved but has not yet been analyzed after the movement;
when the flag has not been set,
updating a time bounding volume for the object;
scheduling an event, the event indicating a time at or after which to analyze the object; and
issuing an occlusion query for the object when the analysis indicates that a status for the object was previously visible and is presently not outside a viewing frustum.
19 . The computer-readable medium of claim 18 further comprising updating the time bounding volume and unsetting the flag at or after the indicated time.
20 . The computer-readable medium of claim 18 further comprising updating the viewing frustum and rendering the object.