Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2001-04-14
2004-02-10
Zimmerman, Mark L. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S421000
Reexamination Certificate
active
06690373
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATIONS
Australian Provisional Patent Application No. PQ6911, Apr. 14, 2000 (claiming priority)
U.S. Patent Documents
U.S. Pat. No. 5,579,455, November 1996, Greene
U.S. Pat. No. 5,613,050, March 1997, Hochmuth
U.S. Pat. No. 5,751,291, May 1998, Olsen
U.S. Pat. No. 5,914,721, June 1999, Lim
U.S. Pat. No. 5,949,423, September 1999, Olsen
U.S. Pat. No. 6,172,679, January 2001, Lim
Other References
Airey, J. M., Increasing update rates in the building walkthrough system with automatic model-space subdivision and potentially visible set calculations. PhD Thesis, University of North Carolina 1990.
Durand, F., G. Drettakis, J Thollot and C. Pucch, Conservative visibility preprocessing using extended projections Siggraph 2000.
Greene, N, Hierarchical z-buffer visibility, Siggraph—93 conference, 1993
Greene, N., Hierarchical rendering of complex environments, PhD dissertation, University of California, Santa Cruz 1995.
Hornung, C., A method for solving the visibility problem, EEE Computer Graphics & Applications, vol. 4, 1984.
Koltun, V., Y. Chrysanthou and D. Cohen-Or, Virtual Occluders: An Efficient Intermediate PVS representation, EGRW'2000.
Lim, H. L., Rendering techniques in three-dimensional computer graphics, Ph.D. thesis, University of Sydney, 1993.
Schaufler, G., J. Dorsey, X. Decoret, and F. X. Sillion, Conservative Volumetric Visibility with Occluder Fusion, Siggraph 2000.
Teller S., Visibility Preprocessing for Interactive Walkthrough, Siggraph'91.
Teller, S., Visibility computations in densely occluded polyhedral environment, PhD. thesis, University of California at Berkeley, 1992.
Wonka P., D. Schmalstieg, Occluder Shadows for Fast Walkthroughs of Urban Environments, Eurographics'99.
Wonka, P., Michael Wimmer, Dieter Schmalstieg, Visibility Preprocessing with Occluder Fusion for Urban Walkthroughs, EGRWS 2000.
Statement Regarding Federally Sponsored Research OF Development
Not Applicable
Reference TO Sequence Listing, A Table, OR A Computer Listing Appendix
Not Applicable
BACKGROUND OF THE INVENTION
1. 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 visibility or visibility-related computations, generally in 3D systems.
2. Description of the Prior Art
In 3D computer graphics, the determination of the visibility of surfaces is known as hidden surface removal and is performed by the hidden surface algorithms. The most common hidden surface algorithm has been the z-buffer algorithm. However, the traditional hidden surface removal approach is incapable of treating visible and invisible surfaces differently. They have to accord the same importance to all these surfaces and treat them in equal detail to determine their visibility. To address this limitation, a new generation of techniques known as the occlusion culling methods have been created. These methods apply various strategies to quickly decide whether some surfaces are hidden by the other surfaces (the occluders). The present invention is based heavily and borrows many terminologies from the earlier references by Airey, Teller and the inventor of this application
BRIEF 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 improved methods for performing visibility calculations.
In accordance with one aspect of the invention, there is disclosed a method of detecting, before normal hidden surface computations, surfaces or their sub-elements that are invisible, wherein said surfaces or their sub-elements are excluded from said hidden surface computations.
In accordance with another aspect of the invention, there is disclosed a method of detecting, before normal hidden surface computations, surfaces or their sub-elements that are visible, wherein said surfaces or their sub-elements are excluded from said hidden surface computations.
In accordance with another aspect of the invention, there is disclosed a method of detecting, before normal hidden surface computations, surfaces or their sub-elements that are invisible, further comprising the step of determining surfaces or their sub-elements that are visible, wherein only the remaining surfaces or their sub-elements are excluded from said hidden surface computations.
In accordance with another aspect of the invention, there is disclosed a method of detecting, before normal hidden surface computations, surfaces or their sub-elements that are invisible, wherein said surfaces or their sub-elements are excluded from said hidden surface computations. Said method further comprises the step of storing in computer storage information for said hidden surfaces, and the step of subsequently accessing said stored information for said hidden surface computations.
In accordance with another aspect of the invention, there is disclosed a method of detecting, before normal hidden surface computations, surfaces or their sub-elements that are invisible, wherein said surfaces or their sub-elements are excluded from said hidden surface computations. Said method comprises the steps of determining the penumbra regions, and checking, for each surface whose visibility is to be determined, whether the projection of said surface falls within on said penumbra regions.
In accordance with another aspect of the invention, there is disclosed a method of detecting, before normal hidden surface computations, surfaces or their sub-elements that are invisible, wherein said surfaces or their sub-elements for said hidden surface computations. Said method further comprises the steps of combining the fuzzy projections, and the determination of the relationship between the combined fuzzy projections with the projections of surfaces whose visibility are to be determined.
In accordance with another aspect of the invention, there is disclosed a method of detecting before normal hidden surface computations, surfaces or their sub-elements that are invisible, wherein said surfaces or their sub-elements are excluded from said hidden surface computations. Said method further comprises the steps of computing the probabilities of areas on the fuzzy projection planes or the combined fuzzy projection planes; and determining whether said areas are fully occluded based on the probabilities computed.
REFERENCES:
patent: 5613048 (1997-03-01), Chen et al.
patent: 5671381 (1997-09-01), Strasnick et al.
patent: 5729672 (1998-03-01), Ashton
patent: 5739819 (1998-04-01), Bar-Nahum
patent: 5808617 (1998-09-01), Kenworthy et al.
patent: 5808620 (1998-09-01), Doi et al.
patent: 5870098 (1999-02-01), Gardiner
patent: 5914721 (1999-06-01), Lim
patent: 6411297 (2002-06-01), Tampieri
patent: 6476807 (2002-11-01), Duluk et al.
Santiago Enrique L
Zimmerman Mark L.
LandOfFree
Methods for improving visibility computations in 3D computer... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods for improving visibility computations in 3D computer..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods for improving visibility computations in 3D computer... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3307818