Computer graphics processing and selective visual display system – Computer graphics processing – Graphic manipulation
Reexamination Certificate
2001-12-06
2004-05-04
Jankus, Almis R. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Graphic manipulation
C345S421000
Reexamination Certificate
active
06731304
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to computer graphics, and more particularly, to the process of rendering three-dimensional objects.
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. 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 samples.
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 following references describe various applications of visible-surface ray casting (or ray tracing).
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, N.Y., 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,
Keller Randall G.
Sowizral Henry A.
Zikan Karel
Brightwell Mark K.
Hood Jeffrey C.
Jankus Almis R.
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Sun Microsystems Inc.
LandOfFree
Using ancillary geometry for visibility determination does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Using ancillary geometry for visibility determination, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Using ancillary geometry for visibility determination will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3249343