Size conditioned visibility search system and method Number:6,750,859 from the United States Patent and Trademark Office (PTO) owispatent

Title: Size conditioned visibility search system and method

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.

Patent Number: 6,750,859 Issued on 06/15/2004 to Sowizral,   et al.

---

Inventors:	Sowizral; Henry A. (Bellvue, WA), Zikan; Karel (Seattle, WA), Keller; Randall G. (San Carlos, CA)
Assignee:	Sun Microsystems, Inc. (Santa Clara, CA)
Appl. No.:	09/948,960
Filed:	September 7, 2001

---

Current U.S. Class:	345/418 ; 345/619; 707/102
Current International Class:	G06T 15/40 (20060101); G06T 15/10 (20060101)
Field of Search:	707/1-206 345/418,419-428,619-628

---

References Cited [Referenced By]

---

U.S. Patent Documents

	6509898		January 2003		Chi et al.
	6522292		February 2003		Ellenby et al.
	6629097		September 2003		Keith

Other References

Seki et al., A double-layer electrically controlled birefringence liquid crystal display with a wide-viewing-angle cone, Display Research Conference, 1991, Conference Record of the 1991 International, Oct. 15-17, 1991, pp. 188-191.* . Noborio et al., Construction of the octree approximating a three-dimensionial object by using multiple views, Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 10, Issue 6, Nov. 1988, pp. 769-782.* . Ng et al., A novel method for segmentation of cones and cylinders from geometrically fused depth maps, Image processing and its Applications, 1995, Fifth International Conference on, Jul. 4-6, 1995, pp. 544-548..

Primary Examiner: Jung; David
Attorney, Agent or Firm: Meyertons Hood Kivlin Kowert & Goetzel, P.C. Hood; Jeffrey C. Brightwell; Mark K.

---

Parent Case Text

---

CROSS REFERENCES TO RELATED APPLICATIONS

This application is a continuation of U.S. patent application Ser. No. 09/894,662 filed on Jun. 28, 2001 now abandoned entitled "Size Conditioned Visibility Search System and Method" which claims the benefit of U.S. Provisional Application No. 60/214,843 filed on Jun. 28, 2000 entitled "Size Conditioned Visibility Search System and Method".

---

Claims

---

What is claimed is:

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.

---

Description

---

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates generally to the field of computer graphics, and more particularly, to the problem of determining the set of objects (and portions of objects) visible from a defined viewpoint in a graphics environment.

2. Description of the Related Art

Visualization software has proven to be very useful in evaluating three-dimensional designs long before the physical realization of those designs. In addition, visualization software has shown its cost effectiveness by allowing engineering companies to find design problems early in the design cycle, thus saving them significant amounts of money. Unfortunately, the need to view more and more complex scenes has outpaced the ability of graphics hardware systems to display them at reasonable frame rates. As scene complexity grows, visualization software designers need to carefully use the rendering resource provided by graphic hardware pipelines.

A hardware pipeline wastes rendering bandwidth when it discards rendered triangle work. Rendering bandwidth waste can be decreased by not asking the pipeline to draw triangles that it will discard. Various software methods for reducing pipeline waste have evolved over time. Each technique reduces waste at a different point within the pipeline. As an example, software culling of objects falling outside the view frustum can significantly reduce discards in a pipeline's clipping computation. Similarly, software culling of backfacing triangles can reduce discards in a pipeline's lighting computation.

The z-buffer is the final part of the graphics pipeline that discards work. In essence, the z-buffer retains visible surfaces, and discards those not visible because they are behind another surface (i.e. occluded). As scene complexity increases, especially in walk-through and CAD environments, the number of occluded surfaces rises rapidly and as a result the number of surfaces that the z-buffer discards rises as well. A frame's average depth complexity determines roughly how much work (and thus rendering bandwidth) the z-buffer discards. In a frame with a per-pixel depth complexity of d the pipeline's effectiveness is 1/d. As depth complexity rises, the hardware pipeline thus becomes proportionally less and less effective.

Software occlusion culling has been proposed as an additional tool for improving rendering effectiveness. A visualization program which performs occlusion culling effectively increases the overall rendering bandwidth of the graphics hardware by not asking the hardware pipeline to draw occluded objects. Computing a scene's visible objects is the complementary problem to that of occlusion culling. Rather than removing occluded objects from the set of objects in a scene or frustum-culled scene, a program instead computes which objects are visible and instructs the rendering hardware to draw just those. A simple visualization program can compute the set of visible objects and draw those objects from the current viewpoint, thus allowing the pipeline to focus on removing backfacing polygons and the z-buffer to remove any non-visible surfaces of those objects.

One technique for computing the visible object set uses ray casting as shown in FIG. 1. RealEyes [Sowizral, H. A., Zikan, K., Esposito, C., Janin, A., Mizell, D., "RealEyes: A System for Visualizing Very Large Physical Structures", SIGGRAPH '94, Visual Proceedings, 1994, p. 228], a system that implemented the ray casting technique, was demonstrated in SIGGRAPH 1994's BOOM room. At interactive rates, visitors could "walk" around the interior of a Boeing 747 or explore the structures comprising Space Station Freedom's lab module.

The intuition for the use of rays in determining visibility relies on the properties of light. The first object encountered along a ray is visible since it alone can reflect light into the viewer's eye. Also, that object interposes itself between the viewer and all succeeding objects along the ray making them not visible. In the discrete world of computer graphics, it is difficult to propagate a continuum of rays. So a discrete subset of rays is invariably used. Of course, this implies that visible objects or segments of objects smaller than the resolution of the ray sample may be missed and not discovered. This is because rays guarantee correct determination of visible objects only up to the density of the ray-sample. FIG. 1 illustrates the ray-based method of visible object detection. Rays that interact with one or more objects are marked with a dot at the point of their first contact with an object. It is this point of first contact that determines the value of the screen pixel corresponding to the ray. Also observe that the object 10 is small enough to be entirely missed by the given ray sample.

Visible-object determination has its roots in visible-surface determination. Foley et al. [Foley, J., van Dam, A., Feiner, S. and Hughes, J. Computer Graphics: Principles and Practice, 2nd ed., Addison-Wesley, Chapter 15, pp. 649-718, 1996] classify visible-surface determination approaches into two broad groups: image-precision and object-precision algorithms. Image precision algorithms typically operate at the resolution of the display device and tend to have superior performance computationally. Object precision approaches operate in object space - usually performing object to object comparisons.

A prototypical image-precision visible-surface-determination algorithm casts rays from the viewpoint through the center of each display pixel to determine the nearest visible surface along each ray. The list of applications of visible-surface ray casting (or ray tracing) is long and distinguished. Appel ["Some Techniques for Shading Machine Rendering of Solids", SJCC'68, pp. 37-45, 1968] uses ray casting for shading. Goldstein and Nagel [Mathematical Applications Group, Inc., "3-D Simulated Graphics Offered by Service Bureau," Datamation, 13(1), February 1968, p. 69.; see also Goldstein, R. A. and Nagel, R., "3-D Visual Simulation", Simulation, 16(1), pp. 25-31, 1971] use ray casting for boolean set operations. Kay et al. [Kay, D. S. and Greenberg, D., "Transparency for Computer Synthesized Images," SIGGRAPH'79, pp. 158-164] and Whitted ["An Improved Illumination Model for Shaded Display", CACM, 23(6), pp. 343-349, 1980] use ray tracing for refraction and specular reflection computations. Airey et al. [Airey, J. M., Rohlf, J. H. and Brooks, Jr. F. P., "Towards Image Realism with Interactive Update Rates in Complex Virtual Building Environments", ACM SIGGRAPH Symposium on Interactive 3D Graphics, 24, 2(1990), pp. 41-50] uses ray casting for computing the portion of a model visible from a given cell.

Another approach to visible-surface determination relies on sending beams or cones into a database of surfaces [see Dadoun et al., "Hierarchical approachs to hidden surface intersection testing", Proceeedings of Graphics Interface '82, Toronto, May 1982, 49-56; see also Dadoun et al., "The geometry of beam tracing", In Joseph O'Rourke, ed., Proceeedings of the Symposium on Computational Geometry, pp. 55-61, ACM Press, New York, 1985]. Essentially, beams become a replacement for rays. The approach usually results in compact beams decomposing into a set of possibly non-connected cone(s) after interacting with an object.

A variety of spatial subdivision schemes have been used to impose a spatial structure on the objects in a scene. The following four references pertain to spatial subdivision schemes: (a) Glassner, "Space subdivision for fast ray tracing," IEEE CG&A, 4(10):15-22, October 1984; (b) Jevans et al., "Adaptive voxel subdivision for ray tracing," Proceedings Graphics Interface '89, 164-172, June 1989; (c) Kaplan, M. "The use of spatial coherence in ray tracing," in Techniques for Computer Graphics . . . , Rogers, D. and Eamshaw, R. A. (eds), Springer-Verlag, New York, 1987; and (d) Rubin, S. M. and Whitted, T. "A 3-dimensional representation for fast rendering of complex scenes," Computer Graphics, 14(3):110-116, July 1980.

Kay et al. [Kay, T. L. and Kajiya, J. T., "Ray Tracing Complex Scenes", SIGGRAPH 1986, pp. 269-278, 1986], concentrating on the computational aspect of ray casting, employed a hierarchy of spatial bounding volumes in conjunction with rays, to determine the visible objects along each ray. Of course, the spatial hierarchy needs to be precomputed. However, once in place, such a hierarchy facilitates a recursive computation for finding objects. If the environment is stationary, the same data-structure facilitates finding the visible object along any ray from any origin.

Teller et al. [Teller, S. and Sequin, C. H., "Visibility Preprocessing for Interactive Walkthroughs," SIGGRAPH '91, pp. 61-69] use preprocessing to full advantage in visible-object computation by precomputing cell-to-cell visibility. Their approach is essentially an object precision approach and they report over 6 hours of preprocessing time to calculate 58 Mbytes of visibility information for a 250,000 polygon model on a 50 MIP machine [Teller, S. and Sequin. C. H., "Visibility computations in polyhedral three-dimensional environments," U.C. Berkeley Report No. UCB/CSD 92/680, April 1992].

In a different approach to visibility computation, Greene et al. [Greene, N., Kass, M., and Miller, G., "Hierarchical z-Buffer Visibility," SIGGRAPH '93, pp. 231-238] use a variety of hierarchical data structures to help exploit the spatial structure inherent in object space (an octree of objects), the image structure inherent in pixels (a Z pyramid), and the temporal structure inherent in frame-by-frame rendering (a list of previously visible octree nodes). The Z-pyramid permits the rapid culling of large portions of the model by testing for visibility using a rapid scan conversion of the cubes in the octree.

As used herein, the term "octree" refers to a data structure derived from a hierarchical subdivision of a three-dimensional space based on octants. The three-dimensional space may be divided into octants based on three mutually perpendicular partitioning planes. Each octant may be further partitioned into eight sub-octants based on three more partitioning planes. Each sub-octant may be partitioned into eight sub-suboctants, and so forth. Each octant, sub-octant, etc., may be assigned a node in the data structure. For more information concerning octrees, see pages 550-555, 559-560 and 695-698 of Computer Graphics: principles and practice, James D. Foley et al., 2.sup.nd edition in C, ISBN 0-201-84840-6, T385.C5735, 1996.

The depth complexity of graphical environments continues to increase in response to consumer demand for realism and performance. Thus, the efficiency of an algorithm for visible object determination has a direct impact on the marketability of a visualization system. The computational bandwidth required by the visible object determination algorithm determines the class of processor required for the visualization system, and thereby affects overall system cost. Thus, a system and method for improving the efficiency of visible object determination is greatly desired.

SUMMARY OF THE PRESENT INVENTION

Various embodiments of a system and method for performing visible object determination based upon a dual search of a cone hierarchy and a bounding hierarchy are herein disclosed. In one embodiment, the system may comprise a processor, a display device, system memory, and optionally a graphics accelerator. The processor executes visualization software which operates on a collection of graphics objects to determine a visible subset of the objects from a defined viewpoint. The objects may reside in a three-dimensional space and thus admit the possibility of occluding one another.

The visualization software represents space in terms of a hierarchy of cones emanating from a viewpoint. In one embodiment, the leaf-cones of the cone hierarchy, i.e. the cones at the ultimate level of refinement, subtend an area which corresponds to a fraction of a pixel in screen area. For example, two cones may conveniently fill the area of a pixel. In other embodiments, a leaf-cone may subtend areas which include one or more pixels.

An initial view frustum or neighborhood of the view frustum may be recursively tessellated (i.e. refined) to generate a cone hierarchy. Alternatively, the entire space around the viewpoint may be recursively tessellated to generate the cone hierarchy. In this embodiment, the cone hierarchy is recomputed for changes in the viewpoint and view-direction. The cone hierarchy is also referred to herein as the cone tree structure.

The visualization software may also generate a hierarchy of bounds from the collection of objects. In particular, the bounding hierarchy may be generated by: (a) recursively grouping clusters starting with the objects themselves as order-zero clusters, (b) bounding each object and cluster (of all orders) with a corresponding bound, e.g. a polytope hull, (c) allocating a node in the bounding hierarchy for each object and cluster, and (d) organizing the nodes in the bounding hierarchy to reflect cluster membership. For example if node A is the parent of node B, the cluster corresponding to node A contains a subcluster (or object) corresponding to node B. Each node stores parameters which characterize the bound of the corresponding cluster or object. The bounding hierarchy is also referred to herein as the bound tree structure.

The visualization software may perform a search of the cone tree structure and the bound tree structure starting with the root cone and the root bound. In one embodiment, each leaf-cone may be assigned a visibility distance value which represents the distance to the closest known object as perceived from within the leaf-cone. Each leaf-cone may also be assigned an object attribute which specifies the closest known object within view of the leaf-cone. Similarly, each non-leaf cone may be assigned a visibility distance value. However, the visibility distance value of a non-leaf cone is set equal to the maximum of the visibility distance values for its subcone children. This implies that the visibility distance value for each non-leaf cone equals the maximum of the visibility distance values of its leaf-cone descendents.

In response to execution of the visualization software, the processor may perform a visibility search method which comprises: (a) receiving a cone pointer which points to the cone tree structure stored in a memory, (b) receiving a bound pointer which points to the bound tree structure stored in the memory, wherein leaf bounds of the bound tree structure approximate a collection of graphical objects, (c) searching 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, and (d) transmitting an indication of the one or more nearest graphical objects for the one or more cones to a rendering agent such as a software renderer or a hardware rendering unit. The rendering agent generates pixel values (and/or samples) for the indicated objects.

The dual-tree search may be illustrated in terms of a first cone of the cone tree structure and a first bound of the bound tree structure. The processor may compute a bound size for the first bound, and may compare the bound size to a cone size which corresponds to the first cone. If the bound size is larger than the cone size, the processor may search subbounds of the first bound with respect to the first cone. Conversely, if the cone size is larger than the bound size, the processor may search subcones of the first cone with respect to the first bound. A variety of methods are contemplated for computing the cone size and the bound size. By selecting the larger entity (first bound or first cone) for refinement, the visibility search method may, in some embodiments, prune the combined cone-bound tree more effectively, and determine the set of visible objects with increased efficiency.

BRIEF DESCRIPTION OF THE FIGURES

The foregoing, as well as other objects, features, and advantages of this invention may be more completely understood by reference to the following detailed description when read together with the accompanying drawings in which:

FIG. 1 illustrates the ray-based method of visible object detection according to the prior art;

FIG. 2A illustrates one embodiment of a graphical computing system for performing visible object determination;

FIG. 2B is a block diagram illustrating one embodiment of the graphical computing 80;

FIG. 3 illustrates several main phases of one embodiment of a visualization program;

FIG. 4A illustrates a collection of objects in a graphics environment;

FIG. 4B illustrates a first step in one embodiment of a method for forming a hull hierarchy, i.e. the step of bounding objects with containing hulls and allocating hull nodes for the containing hulls;

FIG. 4C illustrates one embodiment of the process of grouping together hulls to form higher order hulls, and allocating nodes in the hull hierarchy which correspond to the higher order hulls;

FIG. 4D illustrates the culmination of one embodiment of the recursive grouping process wherein all objects are contained in a universal containing hull which corresponds to the root node of the hull hierarhcy;

FIG. 5A illustrates the mathematical expressions which describe lines and half-planes in two dimensional space;

FIG. 5B illustrates the description of a rectangular region as the intersection of four half-planes in a two dimensional space;

FIG. 6 illustrates a two-dimensional cone partitioned into a number of subcones which interact with a collection of objects by means of wavefronts propagating within each of the subcones;

FIG. 7 illustrates polyhedral cones with rectangular and triangular cross-section emanating from the origin;

FIG. 8A illustrates mathematical expressions which describe a line through the origin and a corresponding half-plane given a normal vector in two-dimensional space;

FIG. 8B illustrates the specification of a two-dimensional conic region as the intersection of two half-planes;

FIGS. 9A-9C illustrate the formation of a cone hierarchy based on repeated subdivision of an initial cone with rectangular cross-section;

FIGS. 10A-C illustrates one embodiment of a visibility search program for determining a set of visible objects in a graphics environment;

FIG. 10D illustrates a cone C which has a small normalized size compared to a bound hull H;

FIG. 10E illustrates a hull H which has a small normalized size compared to a cone C;

FIG. 10F illustrates one embodiment of step 336 of the visibility search algorithm;

FIG. 11 illustrates one embodiment of a visibility search method for identifying and displaying visible objects in a graphics environment;

FIG. 12 illustrates processing steps which may be performed when the visibility search method arrives at a terminal cone and a terminal bound;

FIG. 13 illustrates processing steps which may be performed when the visibility search method arrives at a terminal cone and a non-terminal bound;

FIG. 14 illustrates processing steps which may be performed when the visibility search arrives at a terminal bound and a non-terminal cone;

FIG. 15 illustrates one embodiment of the process of recursively clustering a collection of objects to form a bounding hierarchy;

While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that the drawings and detailed description thereto are not intended to limit the invention to the particular forms disclosed, but on the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope of the present invention as defined by the appended claims. Please note that the section headings used herein are for organizational purposes only and are not meant to limit the description or claims. The word "may" is used in this application in a permissive sense (i.e., having the potential to, being able to), not a mandatory sense (i.e., must). Similarly, the word include, and derivations thereof, are used herein to mean "including, but not limited to."

DETAILED DESCRIPTION OF SEVERAL EMBODIMENTS

U.S. patent application Ser. No. 09/894,662 filed on Jun. 28, 2001 entitled "Size Conditioned Visibility Search System and Method" is hereby incorporated by reference in its entirety.

U.S. Provisional Application No. 60/214,843 filed on Jun. 28, 2000 entitled "Size Conditioned Visibility Search System and Method" is hereby incorporated by reference in its entirety.

FIG. 2A presents one embodiment of a graphical computing system 80 for performing visible object determination. Graphical computing system 80 may include a system unit 82, and a display device 84 coupled to the system unit 82. The display device 84 may be realized by any of various types of video monitors or graphical displays. Graphics computer system 80 may include a keyboard 86 and preferably a mouse 88.

FIG. 2B is a block diagram illustrating one embodiment of graphical computing system 80. Graphical computing system 80 may include a host central processing unit (CPU) 102 coupled to a high speed bus or system bus 104. A system memory 106 may also be coupled to system bus 104. The system memory 106 may include any of various types of memory subsystems including random access memory, read only memory, and/or mass storage devices. The host processor 102 may execute a visualization software program which determines the set of visible objects in a scene. The visualization software program may be stored in system memory 106. In an alternative embodiment, the visualization software program executes on a processor comprised within graphics accelerator 112.

In some embodiments, a 3-D graphics accelerator 112 may be coupled to system bus 104. If 3D accelerator 112 is not included in graphical computing system 80, then display device 84 may couple directly to system bus 104. It is assumed that various other peripheral devices, or other buses, may be connected to system bus 104, as is well known in the art. Display device 84 may couple to 3-D graphics accelerator 112. CPU 102 may transfer information to and from the graphics accelerator 112 according to a programmed input/output (I/O) protocol over the system bus 104. In one embodiment, the graphics accelerator 112 may access system memory 106 according to a direct memory access (DMA) protocol or through intelligent bus mastering.

3-D graphics accelerator 112 may be a specialized graphics rendering subsystem which is designed to off-load the 3-D rendering functions from the host processor, thus providing improved system performance. In a system with a 3-D graphics accelerator, a graphics application program executing on the host processor 102 may generate three-dimensional geometry data that defines three-dimensional graphics elements for output on a display device 84. The application program may transfer the geometry data to the graphics accelerator 112. The graphics accelerator 112 may receive the geometry data and render the corresponding graphics elements on the display device. A fundamental goal of computer graphics is to render objects that are realistic to the user. The problem of visual realism, however, is quite complex. Objects in the "real world" include an incredible amount of detail, including subtle variations in color, reflections, and surface irregularities. Applications which display three-dimensional graphics may require a tremendous amount of processing bandwidth.

The computer system 80 may include visualization software configured to operate on a collection of objects to determine a visible subset of the objects with respect to a viewpoint in a virtual screen space. The visualization software may be executed by the host processor 102, or by one or more processors comprised within the graphics accelerator 112.

Visualization Software Architecture

FIG. 3 illustrates one embodiment of the visualization software. In an initial step 210, the visualization software may load a scene. The scene may comprise a plurality of objects. Scene loading may include constructing an object hierarchy--if it has not already been constructed. In step 220, the visualization software may discover the set of visible objects in the scene with respect to a current viewpoint. In the preferred embodiment, the visualization software may be configured to compute visibility for three-dimensional objects from a view point in a three-dimensional coordinate space. However, the methodologies herein described naturally generalize to spaces of arbitrary dimension.

In one embodiment of the visualization software, the viewpoint in the graphical environment may be changed in response to user input. For example, by manipulating mouse 88 and/or depressing keys on keyboard 86, the user may cause the viewpoint and/or view orientation to change. Thus, the visualization software may recompute the set of visible objects whenever the viewpoint and/or the view orientation changes.

In step 230, the visualization software may display the visible objects (or visible portions of objects). For example, the visualization software may command the graphics accelerator 112 to render the visible objects on the display screen. By performing visible object determination prior to object rendering, graphics accelerator 112 may operate with increased efficiency. Thereby, the overall processing capacity of graphics system 80 may be improved. Determination and display of the visible-object-set may be performed repeatedly as the viewpoint and/or view direction (i.e. orientation) changes, and/or as the objects themselves evolve in time. The determination and display steps may be performed as concurrent processes. However, in alternative embodiments, they may be performed sequentially.

In some embodiments, objects may be modeled as opaque convex polytopes. A three-dimensional solid is said to be convex if any two points in the solid (or on the surface of the solid) may be connected with a line segment which resides entirely within the solid. Thus a solid cube is convex, while a donut (i.e. solid torus) is not. A polytope is an object with planar sides (e.g. cube, tetrahedron, etc.). The methodologies described herein for opaque objects naturally extend to transparent or semi-transparent objects by not allowing such objects to terminate a cone computation. Although not all objects are convex, every object can be approximated as a union of convex polytopes. It is helpful to note that the visible-object-set computation does not require an exact computation, but rather a conservative one. In other words, it is permissible to over-estimate the set of visible objects.

Constructing the Object Hierarchy

Initially, the objects in a scene may be organized into a hierarchy that groups objects spatially. An octree is one possibility for generating the object hierarchy. However, in the preferred embodiment, a clustering algorithm is used which groups nearby objects then recursively clusters pairs of groups into larger containing spaces. The clustering algorithm employs a simple distance measure and thresholding operation to achieve the object clustering. FIGS. 4A-4D illustrate one embodiment of a clustering process for a collection of four objects J00 through J11. The objects are indexed in a fashion which anticipates their ultimate position in a binary tree of object groups. The objects are depicted as polygons situated in a plane (see FIG. 4A). However, the reader may imagine these objects as arbitrary three-dimensional objects. In one embodiment, the objects are three-dimensional polytopes.

Each object may be bounded, i.e. enclosed, by a corresponding bounding surface referred to herein as a bound. In the preferred embodiment, the bound for each object is a polytope hull (i.e. a hull having planar faces) as shown in FIG. 4B. The hulls H00 through H11 are given labels which are consistent with the objects they bound. For example, hull H00 bounds object J00. The hulls are illustrated as rectangles with sides parallel to a pair of coordinate axes. These hulls are intended to represent rectangular boxes (parallelepipeds) in three dimensions whose sides are normal to a fixed set of coordinate axes. For each hull a corresponding node data structure is generated. The node stores parameters which characterize the corresponding hull.

Since a hull has a surface which is comprised of a finite number of planar components, the description of a hull is intimately connected to the description of a plane in three-space. In FIG. 5A, a two dimensional example is given from which the equation of an arbitrary plane may be generalized. A unit vector n [any vector suffices but a vector of length one is convenient for discussion] defines a line L through the origin of the two dimensional space. By taking the dot product v.multidot.n of a vector v with the unit vector n, one obtains the length of the projection of vector v in the direction defined by unit vector n. Thus, given a real constant c, it follows that the equation x.multidot.n=c, where x is a vector variable, defines a line M perpendicular to line L and situated at a distance c from the origin along line L. In the context of three-dimensional space, this same equation defines a plane perpendicular to the line L, again displaced distance c from the origin along line L. Observe that the constant c may be negative, in which case the line (or plane) M is displaced from the origin at distance .vertline.c.vertline. along line L in the direction opposite to unit vector n.

The line x.multidot.n=c divides the plane into two half-planes. By replacing the equality in the above equation with an inequality, one obtains the description of one of these half-planes. The equality x.multidot.n<c defines the half-plane which contains the negative infinity end of line L. [The unit vector n defines the positive direction of line L.] In three dimensions, the plane x.multidot.n=c divides the three-dimensional space into two half-spaces. The inequality x.multidot.n<c defines the half-space which contains the negative infinity end of line L.

FIG. 5B shows how a rectangular region may be defined as the intersection of four half-planes. Given four normal vectors n.sub.1 through n.sub.4, and four corresponding constants c.sub.1 through c.sub.4, a rectangular region is defined as the set of points which simultaneously satisfy the set of inequalities x.multidot.n.sub.i <c.sub.i, where i ranges from one to four. This system of inequalities may be summarized by the matrix-vector expression N.multidot.x<c, where the rows of matrix N are the normal vectors n.sub.1 through n.sub.4, and the components of vector c are the corresponding constants c.sub.1 through c.sub.4. If the normal vectors are chosen so as to lie in the positive and negative axial directions (as shown in FIG. 5B), the resulting rectangular region has sides parallel to the axes. It is noted that the rectangular hulls H00 through H11 shown in FIG. 4B all use a common set of normal vectors. Thus, each hull is characterized by a unique c vector.

In three-dimensional space, a rectangular box may be analogously defined as the intersection of six half-spaces. Given six normal vectors n.sub.1 through n.sub.6, oriented in each of the three positive and three negative axial directions, and six corresponding constants c.sub.1 through c.sub.6, the simultaneous solution of the inequalities x.multidot.n.sub.i <c.sub.i, where i runs from one to six, defines a rectangular box with sides parallel to the coordinate planes. Thus, a rectangular box may be compactly represented with the same matrix-vector expression Nx<c, where matrix N now has six rows for the six normal vectors, and vector c has six elements for the six corresponding constants.

To construct an object hierarchy, object hulls H00 through H11 are paired together as shown in FIG. 4C. Each pair of object hulls is bounded by a containing hull. For example, hulls H00 and H01 are paired together and bounded by containing hull H0. Containing-hull H0 contains the two component hulls H00 and H01. Likewise, object hulls H10 and H11 are paired together and bounded by containing-hull H1. In addition, two parent nodes are generated in the object hierarchy, one for each of the containing-hulls H0 and H1. For simplicity, the parent nodes are commonly labeled as their corresponding containing-hulls. Thus, parent node H0 points to its children nodes H00 and H01, while parent node H1 points to its children nodes H10 and H11. Each parent node contains the characterizing c vector for the corresponding containing-hull.

The containing-hulls H0 and H1 may be referred to as first order containing-hulls since they are the result of a first pairing operation on the original object hulls. A second pairing operation is applied to the first-order containing hulls to obtain second-order containing-hulls. Each second-order containing-hull contains two first-order hulls. For each of the second-order containing-hulls a parent node is generated in the object hierarchy. The parent node reflects the same parent-child relationship as the corresponding second-order containing-hull. For example, in FIG. 4D, second-order containing-hull H contains first-order containing-hulls H0 and H1. Thus, parent node H in the object hierarchy points to children nodes H0 and H1. Parent node H stores the characterizing vector c for the containing-hull H. In the example presented in FIGS. 4A-4D, the object hierarchy is complete after two pairing operations since the original object collections contained only four objects.

In general, a succession of pairing operations is performed. At each stage, a higher-order set of containing-hulls and corresponding nodes for the object hierarchy are generated. Each node contains the describing vector c for the corresponding containing-hull. At the end of the process, the object hierarchy comprises a binary tree with a single root node. The root node corresponds to a total containing-hull which contains all sub-hulls of all orders including all the original object-hulls. The object hierarchy, because it comprises a hierarchy of bounding hulls, will also be referred to as the hull hierarchy. In the preferred embodiment, the pairing operations are based on proximity, i.e. objects (and hulls of the same order) are paired based on proximity. Proximity based pairing results in a more efficient visible object determination algorithm. This tree of containing hulls provides a computationally efficient, hierarchical representation of the entire scene. For instance, when a cone completely misses a node's containing-hull, none of the node's descendents need to be examined.

Bounding hulls (i.e. containing hulls) serve the purpose of simplifying and approximating objects. Any hierarchy of containing hulls works in principle. However, hierarchies of hulls based on a common set of normal vectors are particularly efficient computationally. A collection of hulls based on a common set of normal vectors will be referred to herein as a fixed-direction or commonly-generated collection. As described above, a polytope hull is described by a bounding system of linear inequalities {x:Nx.ltoreq.c}, where the rows of the matrix N are a set of normal vectors, and the elements of the vector c define the distances to move along each of the normal vectors to obtain a corresponding side of the polytope. In a fixed-direction collection of hulls, the normal matrix N is common to all the hulls in the collection, while the vector c is unique for each hull in the collection. The problem of calculating the coefficient vector c for a containing hull given a collection of subhulls is greatly simplified when a common set of normal vectors is used. In addition, the nodes of the hull hierarchy may advantageously consume less memory space since the normal matrix N need not be stored in the nodes. In some embodiments, the hull hierarchy comprises a fixed-direction collection of hulls.

In a first embodiment, six normal vectors oriented in the three positive and three negative axial directions are used to generate a fixed-direction hierarchy of hulls shaped like rectangular boxes with sides parallel to the coordinate planes. These axis-aligned bounding hulls pr