Size conditioned visibility search system and method
First Claim
1. A method for displaying visible objects on a display device, the method comprising:
- searching a cone tree structure and a bound tree structure to determine one or more nearest graphical objects for one or more cones of the cone tree structure, wherein, for a first cone of the cone tree structure and a first bound of the bound tree structure, said searching the cone tree structure and the bound tree structure includes;
computing a bound size for the first bound;
comparing the bound size to a cone size corresponding to the first cone;
searching subbounds of the first bound with respect to the first cone if the bound size is larger than the cone size;
transmitting an indication of the one or more nearest graphical objects for each of the one or more cones for rendering.
1 Assignment
0 Petitions
Accused Products
Abstract
A system for performing visible object determination. Visualization software running on a host processor represents space with a hierarchy of cones, and generates a hierarchy of bounding hulls from a collection of objects by recursively grouping clusters of objects. Each hull node in the hull hierarchy stores parameters which characterize a bounding hull for the corresponding cluster or object. The visualization software searches the cone and hull hierarchies starting with the root cone and the root hull. Before exploring a given cone-hull pair, a normalized cone size for the cone and a normalized hull size for the hull may be computed, and the sizes compared. If the cone size is larger than the hull size, subcones of the cone are explored with respect to the hull. Conversely, if the hull size is larger than the cone size, subhulls of the hull are explored with respect to the cone.
77 Citations
50 Claims
-
1. A method for displaying visible objects on a display device, the method comprising:
-
searching a cone tree structure and a bound tree structure to determine one or more nearest graphical objects for one or more cones of the cone tree structure, wherein, for a first cone of the cone tree structure and a first bound of the bound tree structure, said searching the cone tree structure and the bound tree structure includes;
computing a bound size for the first bound;
comparing the bound size to a cone size corresponding to the first cone;
searching subbounds of the first bound with respect to the first cone if the bound size is larger than the cone size;
transmitting an indication of the one or more nearest graphical objects for each of the one or more cones for rendering. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
12. A computer system for displaying visible objects on a display device, the computer system comprising:
-
a memory configured to store a cone tree structure and a bound tree structure, wherein leaf bounds of the bound tree structure approximate a collection of graphical objects;
a processor configured to execute a visibility search algorithm stored in the memory;
wherein, in response to an execution of the visibility search algorithm, the processor is configured to search the cone tree structure and the bound tree structure to determine one or more nearest graphical objects for one or more cones of the cone tree structure, wherein, for a first cone of the cone tree structure and a first bound of the bound tree structure, said processor is configured to (a) compute a bound size for the first bound, (b) compare the bound size to a cone size corresponding to the first cone, (c) search subbounds of the first bound with respect to the first cone if the bound size is larger than the cone size, wherein the processor is further configured to transmit an indication of the one or more nearest graphical objects for each of the one or more cones for rendering.
-
-
21. A computer system for displaying visible objects on a display device, the computer system comprising:
-
a memory configured to store a cone hierarchy and a bounding hull hierarchy, wherein terminal bounds of the bounding hull hierarchy approximate a collection of graphical objects;
a processor configured to execute a visibility search algorithm stored in the memory;
wherein, in response to an execution of the visibility search algorithm, the processor is configured to search the cone hierarchy and the bounding hull hierarchy to determine one or more nearest graphical objects for one or more cones of the cone hierarchy, wherein said processor is configured to (a) compute a hull size for a first hull of the bounding hull hierarchy, (b) compare the hull size to a cone size corresponding to a first cone of the cone hierarchy, and (c) search subhulls of the first hull with respect to the first cone if the hull size is larger than the cone size, wherein the processor is further configured to transmit an indication of the one or more nearest graphical objects for the one or more cones for rendering and display. - View Dependent Claims (22, 23, 25, 26, 27, 28, 29, 30, 31, 32, 33, 35, 36, 37, 38, 39, 40, 41)
-
-
24. A computer-readable medium comprising a plurality of computer program instructions, wherein the plurality of computer program instructions are executable by one or more processors to perform:
-
searching a cone tree structure and a bound tree structure to determine one or more visible objects for one or more cones of the cone tree structure, wherein, said searching the cone tree structure and the bound tree structure comprises searching a first cone of the cone tree structure with respect to a first bound of the bound tree structure, wherein said searching the first cone with respect to the first bound comprises;
estimating a normalized bound size for the first bound;
comparing the normalized bound size to a normalized cone size corresponding to the first cone;
searching subbounds of the first bound with respect to the first cone if the normalized bound size is larger than the normalized cone size;
transmitting an indication of the one or more visible objects for each of the one or more cones for rendering and display.
-
-
34. A computer-readable medium comprising a plurality of computer program instructions, wherein the plurality of computer program instructions are executable by one or more processors to perform:
-
searching a cone hierarchy and a bounding hierarchy to determine one or more visible objects for one or more cones of the cone hierarchy, wherein, said searching the cone hierarchy and the bounding hierarchy comprises searching a first cone of the cone hierarchy with respect to a first bound of the bound hierarchy, wherein said searching the first cone with respect to the first bound comprises;
estimating a bound size for the first bound;
comparing the bound size to a cone size corresponding to the first cone;
searching subbounds of the first bound with respect to the first cone if the bound size is larger than the cone size;
transmitting an indication of the one or more visible objects for each of the one or more cones to a rendering agent for rendering and display.
-
-
42. A method for displaying visible objects on a display device, the method comprising:
-
comparing a bound size for a first bound in a bound tree structure to a cone size corresponding to a first cone in a cone tree structure;
searching subbounds of the first bound with respect to the first cone if the bound size is larger than the cone size, wherein said searching subbounds of the first bound with respect to the first cone is used to identify one or more graphical objects which are visible with respect to the first cone; and
transmitting an indication of the one or more graphical objects for rendering. - View Dependent Claims (43, 44, 45, 47, 48, 49)
-
-
46. A computer system for displaying visible objects on a display device, the computer system comprising:
-
a memory configured to store a cone tree structure and a bound tree structure, wherein leaf bounds of the bound tree structure approximate a collection of graphical objects;
a processor configured to execute a visibility search algorithm stored in the memory;
wherein, in response to an execution of the visibility search algorithm, the processor is configured to compare a bound size of a first bound of a bound tree structure to a cone size of a first cone of a cone tree structure, and to search subbounds of the first bound with respect to the first cone if the bound size is larger than the cone size, wherein said searching subbounds of the first bound with respect to the first cone is used to identify one or more objects which are visible with respect to the first cone, wherein the processor is further configured to transmit an indication of the one or more graphical objects for rendering.
-
-
50. A method for displaying visible objects on a display device, the method comprising:
-
(a) receiving a hierarchy of boundary information for a plurality of three-dimensional graphical objects;
(b) receiving a hierarchy of cones; and
(c) determining whether a particular cone and a particular bound intersect, and in response to determining that the particular cone and the particular bound intersect;
determining a relative size value for the particular cone and the particular bound; and
repeating (c) for a subcone of the particular cone if the relative size of the particular cone is larger than the relative size of the particular bound;
orrepeating (c) for a subbound of the particular bound if the relative size of the particular bound is larger than the relative size of the particular cone.
-
Specification