Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2000-01-20
2003-09-09
Brier, Jeffery (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S422000
Reexamination Certificate
active
06618047
ABSTRACT:
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 an improved method for performing visibility calculations.
The invention features a method of reducing the visibility related computations in 3-D computer graphics, where the visibility related computations are performed on 3-D surfaces or their sub-elements, or a selected set of both.
In a general aspect of the invention, the method of reducing the visibility related computations includes determining which of the 3-D surfaces or their sub-elements are always invisible or always visible to a viewpoint or a group of viewpoints by projection based computations prior to a visibility computation. The method also includes treating the determined ones of the 3-D surfaces or their sub-elements differently than remaining ones of the 3-D surfaces or their sub-elements during visibility computation.
By determining which of the 3-D surfaces or their sub-elements are always invisible or always visible at the preprocessing stage and by treating the determined ones of the 3-D surfaces or their sub-elements differently than remaining ones during visibility computation, the computation complexity and time request for the visibility computations are significantly reduced.
Embodiments of this aspect of the invention may include one or more of the following features.
The projection based computations include defining projection planes and identifying regions on the projection planes. One or more projection planes are defined with respect to a viewpoint or a group of viewpoints such that projections of selected 3-D surfaces can be formed on them. For example, in one embodiment, identifying regions includes dividing each projection plane into one or more grids and defining a data structure for storing said projections on thegrids in computer storage. The grid or grids are either regular or irregular. The data structure of the computer storage is based on a z-buffer or a quadtree.
In another embodiment, the determining step includes identifying the grid cells which are under or related to the projections or extents of projections associated with said 3-D surfaces or their sub-elements and comparing the data associated with said 3-D surface or their sub-elements with the data associated with the grid cells. The data are or related to the depths of said 3-D surfaces or their surface elements.
One preferred embodiment of the treating step is to ignore the determined 3-D surfaces or surface elements which are always invisible or always visible during the visibility computation. Intuitively, this scheme results in complexity reduction in the visibility computation. Other features and advantages of the invention will be apparent from the description and drawings, and from the claims.
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), Rossignac et al.
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), Wake
patent: 5177474 (1993-01-01), Kadota
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: 5329613 (1994-07-01), Brase et al.
patent: 5377313 (1994-12-01), Scheibl
patent: 5384580 (1995-01-01), Kadota
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: 5619592 (1997-04-01), Bloomberg et al.
patent: 5619593 (1997-04-01), Ono
patent: 5644689 (1997-07-01), Ban et al.
patent: 5914721 (1999-06-01)
Brier Jeffery
Fish & Richardson P.C.
Fuzzysharp Technologies, Inc.
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-3000926