Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1997-09-22
2001-01-09
Powell, Mark R. (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S422000
Reexamination Certificate
active
06172679
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.
In accordance with one aspect of the present invention there is disclosed a method of reducing the complexity of visibility calculations required for the production of multi-dimensional computer generated images or the reduction of multi-dimensional data to multi-dimensional data having at least oneless dimension, said method comprising the steps of:
(1) prior to an occlusion or invisibility relationship computation (known per se) being carried out on a plurality of surfaces, selected viewpoints to be calculated are divided into groups;
(2) for selected ones of said surfaces, determining for each said group whether each said selected surface is
(a) an always unoccluded surface, an always hidden surface, or a remaining surface; or
(b) an always unoccluded surface, or a remaining surface; or
(c) an always hidden surface, or a remaining surface; wherein said remaining surface is a surface which is unable to be determined with certainty as to whether it is either unoccluded or hidden;
(3) exempting from said occlusion or invisibility relationship computation those surfaces which are either always unoccluded or always hidden;
(4) maintaining a record of said remaining surfaces; and
(5) carrying out occlusion or invisibility relationship computations on said remaining surfaces.
In accordance with another aspect of the present invention there is disclosed a method of reducing the visibility related computations in an environment consisting of three-dimensional abstract or physical surfaces, said method comprising the steps of:
(1) prior to a visibility computation (known per se) being carried out, some or all viewpoints or possible occurrences of viewpoints are classified into groups of viewpoints;
(2) defining one or more projection surfaces (known per se) for the purpose of generating simultaneous projections of surfaces or surface elements with respect to a group of viewpoints;
(3) for selected surfaces, and for each group of viewpoints, determining whether those surfaces or their surface elements are always invisible to said group by computing and comparing their simultaneous projections on said projection surfaces;
(4) ignoring or treating specially some or all surfaces or surface elements which are always invisible to said group of viewpoints during the actual visibility or visibility related computations for some or all viewpoints in said group.
In accordance with another aspect of the present invention there is disclosed a method of reducing the visibility, radiosity or visibility related computations in an environment consisting of three-dimensional abstract or physical surfaces, said method comprising the steps of:
(1) prior to a visibility computation (known per se) being carried out, some or all viewpoints or possible occurrences of viewpoints are classified into groups of viewpoints;
(2) defining one or more projection surfaces (known per se) for the purpose of the simultaneous projections of surfaces or surface elements with respect to a group of viewpoints;
(3) dividing each of said projection surfaces into regular or irregular grids;
(4) defining a data structure which organizes computer storage for storing of projections on said grids;
(5) for each of the selected surfaces and for each group of viewpoints, simultaneously projecting said surfaces or their surface elements onto the projection surfaces, computing grid cells which are always under the projections, storing the furthest possible distances between viewpoints of said group and said surfaces to provide surface distances corresponding to those cells in said computer storage;
(6) for each patch element of said surfaces, determining those said grid cells that said patch element might project onto, comparing the depths stored in the cells with the furthest possible depth between the patch element and said group of viewpoints to determine whether the patch element is always occluded by other surfaces;
(7) ignoring or treating specially some or all surfaces or s
Harrison Chante′
Oppedahl & Larson LLP
Powell Mark R.
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-2470024