Size conditioned visibility search system and method

• US 6,750,859 B2
• Filed: 09/07/2001
• Issued: 06/15/2004
• Est. Priority Date: 06/28/2000
• Status: Active Grant

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Sowizral, Henry A., Zikan, Karel, Keller, Randall G.
• Primary Examiner(s): Jung, David
• Application Number:
  US09/948,960
• Publication Number:
  US 20020033835A1
• Time in Patent Office: 1,012 Days
• Field of Search: 707/1-206, 345/418, 345/419-428, 345/619-628
• US Class Current: 345/418
• CPC Class Codes: G06T 15/405 using Z-buffer
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

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.

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.

2. The method of claim 1, wherein said one or more cones comprise leaf cones of the cone tree structure.

3. The method of claim 1, wherein said searching subbounds of the first bound with respect to the first cone comprises:

computing a first cone-bound separation value for a first subbound of the first bound with respect to the first cone;

determining whether the first cone-bound separation value satisfies an inequality condition with respect to a measurement value associated with the first cone;

searching said first subbound with respect to said first cone in response to determining that the first cone-bound separation value satisfies the inequality condition with respect to the measurement value associated with the first cone.

4. The method of claim 1, wherein, for the first cone and the first bound, said searching the cone tree structure and the bound tree structure further comprises:

searching subcones of the first cone with respect to the first bound if the bound size is smaller than the cone size.

5. The method of claim 4, wherein said searching the subcones of the first cone with respect to the first bound includes:

computing a first cone-bound separation value for a first subcone of the first cone with respect to the first bound;

determining whether the first cone-bound separation value satisfies an inequality condition with respect to a measurement value associated with the first subcone;

searching the first subcone with respect to the first bound in response to the first cone-bound separation value satisfying the inequality condition with respect to the measurement value associated with the first subcone.

6. The method of claim 5 further comprising setting the measurement value associated with the first cone equal to an extremum of measurement values associated with said subcones after said searching said subcones with respect to the first bound.

7. The method of claim 1, further comprising initializing each cone of the cone tree structure with a measurement value which corresponds to un-occluded visibility.

8. The method of claim 1, wherein, for a second cone of the cone tree structure and a second bound of the bound tree structure, said searching the cone tree structure and the bound tree structure comprises:

(a) determining if said second cone is a leaf of the cone tree structure and said second bound is a leaf bound of the bound tree structure;

(b) setting a measurement value associated with the second cone equal to an extent of separation between the second bound and the second cone;

(c) setting a visible object attribute associated with the second cone equal to an object pointer value corresponding to the second bound;

wherein (b) and (c) are performed in response to said second cone being a leaf of the cone tree structure and said second bound being a leaf of the bound tree structure.

9. The method of claim 1, wherein, for the first cone and first bound, said searching the cone tree structure and the bound tree structure further comprises:

computing the cone size for the first cone based on cone parameters associated with the first cone stored in the cone tree structure.

10. The method of claim 1, wherein, for the first cone and first bound, said searching the cone tree structure and the bound tree structure further comprises:

reading the cone size corresponding to the first cone from a memory.

11. The method of claim 1 further comprising:

receiving a cone pointer which points to the cone tree structure stored in a memory; and

receiving a bound pointer which points to a bound tree structure stored in the memory, wherein leaf bounds of the bound tree structure approximate a collection of graphical objects.

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.

13. The computer system of claim 12, wherein said one or more cones comprise leaf cones of the cone hierarchy.

14. The computer system of claim 12, wherein said processor is configured to search subbounds of the first bound with respect to the first cone by:

computing a first cone-bound separation value for a first subbound of the first bound with respect to the first cone;

determining whether the first cone-bound separation value satisfies an inequality condition with respect to a measurement value associated with the first cone;

searching the first subbound with respect to the first cone in response to determining that the first cone-bound separation value satisfies the inequality condition with respect to the measurement value associated with the first cone.

15. The computer system of claim 12, wherein said processor is further configured to search subcones of the first cone with respect to the first bound if the bound size is smaller than the cone size.

16. The computer system of claim 15, wherein said processor is configured to search the subcones of the first cone with respect to the first bound by:

computing a first cone-bound separation value for a first subcone of the first cone with respect to the first bound;

determining whether the first cone-bound separation value satisfies an inequality condition with respect to a measurement value associated with the first subcone; and

searching said first subcone with respect to said first bound in response to the first cone-bound separation value satisfying the inequality condition with respect to the measurement value associated with the first subcone.

17. The computer system of claim 16, wherein the processor is further configured to set the measurement value associated with the first cone equal to an extremum of measurement values associated with said subcones after said searching said subcones with respect to the first bound.

18. The computer system of claim 12, wherein said processor is configured to search a second bound with respect to a second cone by:

(i) determining if said second cone is a leaf of the cone tree structure and said second bound is a leaf bound of the bound tree structure;

(ii) setting the measurement value associated with the second cone equal to a second measurement value of separation between the second bound and the second cone;

(iii) setting a visible object attribute associated with the second cone equal to an object pointer value corresponding to the second bound;

wherein said processor is configured to perform (ii) and (iii) in response to said second cone being a leaf of the cone tree structure and said second bound being a leaf of the bound tree structure.

19. The computer system of claim 12, wherein the processor is configured to compute the cone size for the first cone based on cone parameters associated with the first cone stored in the cone tree structure.

20. The computer system of claim 12, wherein the processor is configured to read the cone size from the memory.

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.

22. The computer system of claim 21 further comprising a display device operatively coupled to the processor and configured to display the one or more nearest graphical objects for the one or more cones.

23. The computer system of claim 21 wherein said processor is further configured to (d) search subcones of the first cone with respect to the first hull if the hull size is smaller than the cone size.

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.

25. The computer-readable medium of claim 24, wherein said transmitting comprises transmitting the indication of the one or more visible object to a hardware rendering unit.

26. The computer-readable medium of claim 24, wherein said searching subbounds of the first bound with respect to the first cone comprises:

computing a first cone-bound separation value for a first subbound of the first bound with respect to the first cone;

determining whether the first cone-bound separation value satisfies an inequality condition with respect to a measurement value associated with the first cone;

searching said first subbound with respect to said first cone in response to determining that the first cone-bound separation value satisfies the inequality condition with respect to the measurement value associated with the first cone.

27. The computer-readable medium of claim 24, wherein said searching the first cone with respect to the first bound further comprises:

searching subcones of the first cone with respect to the first bound if the normalized bound size is smaller than the normalized cone size.

28. The computer-readable medium of claim 27, wherein said searching the subcones of the first cone with respect to the first bound includes:

computing a first cone-bound separation value for a first subcone of the first cone with respect to the first bound;

determining whether the first cone-bound separation value satisfies an inequality condition with respect to a measurement value associated with the first subcone;

searching the first subcone with respect to the first bound in response to the first cone-bound separation value satisfying the inequality condition with respect to the measurement value associated with the first subcone.

29. The computer-readable medium of claim 28 wherein the computer program instructions are executable by the one or more processors to further perform:

setting the measurement value associated with the first cone equal to an extremum of measurement values associated with said subcones after said searching said subcones with respect to the first bound.

30. The computer-readable medium of claim 24, wherein the computer program instructions comprise a visibility search program, wherein the visibility search program is configured to receive a collection of graphical objects from a graphical application program, and to construct the bound tree structure in response to receiving the collection of graphical objects.

31. The computer-readable medium of claim 24, wherein said searching the cone structure and the bound tree structure comprises searching a second cone of the cone tree structure with respect to a second bound of the bound tree structure, wherein said searching the second cone with respect to the second bound comprises:

(a) determining if said second cone is a leaf of the cone tree structure and said second bound is a leaf bound of the bound tree structure;

(b) setting a measurement value associated with the second cone equal to an extent of separation between the second bound and the second cone;

(c) setting a visible object attribute associated with the second cone equal to an object pointer value corresponding to the second bound;

wherein (b) and (c) are performed in response to said second cone being a leaf of the cone tree structure and said second bound being a leaf of the bound tree structure.

32. The computer-readable medium of claim 24, wherein said searching the first cone with respect to the first bound further comprises:

computing the normalized cone size for the first cone based on cone parameters associated with the first cone stored in the cone tree structure.

33. The computer-readable medium of claim 24, wherein said searching the first cone with respect to the first bound further comprises:

reading the normalized cone size corresponding to the first cone from a memory.

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.

35. The computer-readable medium of claim 34, wherein said rendering agent comprises a software renderer executing on at least one of the one or more processors.

36. The computer-readable medium of claim 34, wherein said rendering agent comprises a hardware rendering unit.

37. The computer-readable medium of claim 34, wherein said searching the first cone with respect to the first bound further comprises:

searching subcones of the first cone with respect to the first bound if the bound size is smaller than the cone size.

38. The computer-readable medium of claim 34, wherein said searching the cone hierarchy and the bounding hierarchy comprises searching a second cone of the cone hierarchy with respect to a second bound of the bounding hierarchy, wherein said searching the second cone with respect to the second bound comprises:

(a) determining if said second cone is a leaf of the cone hierarchy and said second bound is a leaf bound of the bounding hierarchy;

(b) setting a measurement value associated with the second cone equal to an extent of separation between the second bound and the second cone;

(c) setting a visible object attribute associated with the second cone equal to an object pointer value corresponding to the second bound;

wherein (b) and (c) are performed in response to said second cone being a leaf of the cone hierarchy and said second bound being a leaf of the bounding hierarchy.

39. The computer-readable medium of claim 34, wherein said searching the first cone with respect to the first bound further comprises:

computing the cone size for the first cone based on cone parameters associated with the first cone stored in the cone hierarchy.

40. The computer-readable medium of claim 34, wherein said searching the first cone with respect to the first bound further comprises:

reading the cone size corresponding to the first cone from a memory.

41. The computer-readable medium of claim 34 wherein the plurality of computer program instructions are executable by the one or more processors to further perform:

receiving a cone pointer which points to the cone hierarchy stored in a memory; and

receiving a bound pointer which points to a bounding hierarchy stored in the memory, wherein leaf bounds of the bounding hierarchy approximate a collection of graphical objects.

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.

43. The method of claim 42 further comprising:

searching subcones of the first cone with respect to the first bound if the cone size is larger than the bound size, wherein said searching subcones of the first cone with respect to the first bound is also used to identify the one or more graphics objects which are visible with respect to the first cone.

44. The method of claim 42 further comprising computing the cone size of the first cone.

45. The method of claim 42 further comprising computing the bound size of the first bound.

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.

47. The computer system of claim 46, wherein said processor is further configured to search subcones of the first cone with respect to the first bound if the cone size is larger than the bound size, wherein said searching subcones of the first cone with respect to the first bound is also used identify the one or more objects which are visible with respect to the first cone.

48. The computer system of claim 46, wherein said processor is further configured to compute the cone size of the first cone.

49. The method of claim 46 further comprising computing the bound size of the first bound.

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;

or

repeating (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.