Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Patent
1994-06-01
1999-06-22
Buchel, Jr., Rudolph J.
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
345422, G06T 1540
Patent
active
059147210
DESCRIPTION:
BRIEF SUMMARY
FIELD OF INVENTION
The present invention relates to computer graphics and, in particular, to the efficient determination of visible and/or invisible surfaces to thereby preferably permit improved hidden surface removal, generally in 3D systems.
BACKGROUND ART
Visible surface detection is one of the most basic operations in 3D graphics. It is applied to generate images of surfaces directly visible to a viewer. Recently, it has also been adopted in the radiosity calculations to compute the energy interactions between surfaces.
The standard strategy of visible surface detection is to divide surfaces into patch elements and compare the spatial relationship between these elements. Using this strategy, the visibility of surfaces cannot be determined until they have been analysed in detail. Although many techniques have been developed to address this issue, none are ideal as they either still require elaborate analysis of surfaces, or they impose various restrictions to the scene.
The limitations of the current techniques can seriously affect the speed of visible surface computation. If the scene is complicated, many surfaces may be invisible. However, the image generation is often slowed down by the need to analyse each surface element in detail.
The same limitation has also seriously affected the efficiency of the radiosity computations. Currently, these computations are very slow due to the need to elaborately compute the visibility between every pair of surface elements. Again, these computations may be substantially reduced if surface elements obviously visible or invisible to each other can be more easily computed.
The early visible surface techniques mainly applied various sorting schemes to find the occluding surface primitives. However, with the advancement in hardware technology, it is now common practice to reduce the need for sorting and comparisons by using a large amount of fast memory. This memory may be used to store the object data, such as a BSP-tree. It may also be used to store the depth and surface projection data, as with a z-buffer.
The z-buffer method is simple and has a very low growth rate. However, it still requires depth evaluations and comparisons at each pixel by all the patches projecting onto it, because their visibility is unknown.
The BSP-tree method has the advantage that if the scene is static, an orderly traversal of the BSP-tree is generally sufficient to establish the depth order. However, it still requires the scan-conversion of each path. In addition, the technique needs to re-compute the BSP-tree whenever objects in the scene move.
There have been two main strategies of avoiding detailed depth analysis of totally invisible entities. One strategy, applies the property that visibility changes can only occur at the contour edges of surfaces. Visibility computations of internal edges or patches can be reduced by first comparing them with these edges.
An alternative strategy is to use the invisible coherence of the scene. These techniques apply the property that an edge is likely to remain invisible in a scan line if it is invisible in the last scan line. Such an edge may therefore be treated specially to avoid unnecessary depth comparisons.
Although the above strategies can reduce some visibility computations, they have limitations. The contour-oriented techniques can operate only in environments which consist exclusively of convex or non-penetrating surfaces. Both the contour-oriented and the scan line approaches are also limited in their ability to reduce visibility computations. In the former, an edge still needs to be tested against the contour edges even if it is invisible. In the latter, all the invisible edge segments at each scan line have to be sorted. These segments also require depth comparisons with the pixels they are on. Finally, all these techniques require some sorting or searching.
SUMMARY OF THE INVENTION
It is an object of the present invention to substantially overcome, or ameliorate, the problems associated with the prior art, through provision of
REFERENCES:
patent: 4594673 (1986-06-01), Holly
patent: 4625289 (1986-11-01), Rockwood
patent: 4697178 (1987-09-01), Heckel
patent: 4819192 (1989-04-01), Kuragano et al.
patent: 4825391 (1989-04-01), Merz
patent: 4855938 (1989-08-01), Gonzalez-Lopez et al.
patent: 4901252 (1990-02-01), Fitzgerald et al.
patent: 4918626 (1990-04-01), Watkins et al.
patent: 4928250 (1990-05-01), Greenberg et al.
patent: 5027292 (1991-06-01), Matsumoto
patent: 5058042 (1991-10-01), Hanna et al.
patent: 5081698 (1992-01-01), Kohn
patent: 5084830 (1992-01-01), Doornink et al.
patent: 5086496 (1992-02-01), Mulmuley
patent: 5088054 (1992-02-01), Paris, II
patent: 5159663 (1992-10-01), Fossum
patent: 5253335 (1993-10-01), Mochizuki et al.
patent: 5268996 (1993-12-01), Steiner et al.
patent: 5295243 (1994-03-01), Robertson et al.
patent: 5299298 (1994-03-01), Elmquist et al.
patent: 5313568 (1994-05-01), Wallace et al.
patent: 5377313 (1994-12-01), Scheibl
patent: 5402532 (1995-03-01), Epstein et al.
patent: 5414801 (1995-05-01), Smith et al.
patent: 5448686 (1995-09-01), Borrel et al.
patent: 5619593 (1997-04-01), Ono
Stabbing Isothetic Boxes & Rectangles in 0(n lg n) time M. Hohmeyer S. J. Teller 1991.
A Characterization of Ten Hidden-Surface Algorithms I. E. Sutherland, R. F. Sproull, R. A. Schumacker Computing Surveys, vol. 6, No. 1, 1975.
Fast Algorithms for 3D-Graphics G. Glaeser, 1994.
Imprecision in Computer Vision R. Jain, S. Haynes Advances in Fuzzy Sets, Possibility and Applications, 1983.
Accelerated radiosity method for complex environments H. Xu Q. Peng, Y. Liang Eurographics'89 1989.
Application Challenges to Computational Geometry, CG Impact Task Force Report CG Impact Task Force Technical Report TR-521-96, Princeton University 1996.
Computer Graphics, Principles and Practice, 2nd edition J. D. Foley A. van Dam S. K. Feiner J. F. Hughes.
New Trends in Animation and Visualization N. Thalmann D. Thalmann 1991.
Graphics Systems: Architecture & Realization R. Andreev 1993.
Analysis of Radiosity Techniques in Computer Graphics B. Kwok MSc Thesis York University, May 1992.
Image display data computer forming method--uses perspective transformation with calculation time reduction on shadow and hidden surface processing Sony 86.233751/36.
Stabbing and ray shooting in 3 dimensional space M. Pellegrini 1990.
The Geometry of Beam Tracing N. Dadoun D. Kirkpatrick 1985.
Algorithms for line transversals in space D. Avis CG1987.
Optimization of the binary space partition algorithm (BSP) for the visualization of dynamic scenes E. Torres Eurographics'90.
A mathematical Semantics of Rendering II. Approximation E. Fiume CVGIP: Graphical Models and Image Processing vol. 53, No. 1, Jan. 1991.
A Characterization of Ten Rasterization Techniques N. Gharachorloo S. Gupta R. Sproull I. Sutherland Computer Graphics, vol. 23, No. 3 (Siggraph'89) 1989.
The use of projective geometry in Computer Graphics I. Herman 1992.
Ray Tracing with Cones J. Amanatides Computer Graphics, vol. 18, No. 3 (Siggraph'84) 1984.
The A-buffer, an Antialiased hidden surface method L. Carpenter Computer Graphics, vol. 18, No. 3, (Siggraph'84) 1984.
Principles and Applications of Pencil Tracing M. Shinya T. Takahashi S. Naito Computer Graphics, vol. 21, No. 4, (Siggraph'87) 1987.
Light-water interaction using backward beam tracing M. Watt Computer Graphics, vol. 24, No. 4 (Siggraph'90) 1990.
Rendering CSG Model with a ZZ-buffer D. Salesin J. Stolfi Computer Graphics, vol. 24, No. 4 (Siggraph'90) 1990.
A solution to the hidden-line problem for computer-drawn polyhedra P. Loutrel IEEE Transactions on Computers, Mar. 1970.
Sorting and the hidden-surface problem I. Sutherland R. Sproull R. Schumacker National Computer Conference, 1970.
The Notion of quantitative invisibility and the machine rendering of solids A Appel ACM National Meeting 1967.
An analytic visible surface algorithm for independent pixel processing E. Catmull Computer Graphics, vol. 18. No. 3 (Siggraph'84) 1984.
Computing the lines piercing four lines S. Te
LandOfFree
Visibility calculations for 3D computer graphics does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Visibility calculations for 3D computer graphics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Visibility calculations for 3D computer graphics will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1710949