Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2002-01-29
2003-02-25
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06525730
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to generating image data, wherein a plurality of surfaces are defined in three dimensional space.
BACKGROUND TO THE INVENTION
Several procedures are known for rendering images containing elements defined as three-dimensional data. A known approach to generating images of photo-realistic quality is to consider reflections between all elements simultaneously. The light emission of any given element is considered as being dependent upon the sum of contributions from all other elements and a set of equations is defined that represents these interactions. The light emission values for all the elements are then determined simultaneously by solving a system of equations.
This procedure is known as radiosity simulation. Surfaces of objects are sub-divided into mesh elements of varying sizes in order to determine an appropriate level of resolution required to represent the change in brightness that will be encountered across the surface of the object. The total number of mesh elements required for a scene is typically very large, and the resulting system of equations is also extremely large. Several refinements to radiosity simulation have been established in order to make implementation of this method practical for scenes containing large numbers of objects.
A known advantage of radiosity simulation is that once the system of equations has been solved, and light emission values determined, the light emission of mesh elements may be considered as view independent, resulting in a separate radiosity rendering process that is capable of rendering a view from any position. The high efficiency of radiosity rendering makes radiosity particularly suitable for demanding applications, such as generating long sequences of image data frames for film or video, or generating image data in real-time.
In the process of radiosity simulation, the presence of intersecting surfaces may result in problems being encountered when surfaces are sub-divided into mesh elements, and element boundaries do not coincide with surface intersections. This results in inappropriate brightness values being encountered at such intersections. A known method for avoiding this problem is to identify intersecting surfaces prior to subdivision into mesh elements, and to create mesh element boundaries along such intersections.
Radiosity simulation is increasingly used for the generation of photo-realistic scenes, comprising many tens of thousands of polygons, of which object surfaces are comprised. Identification of intersecting polygons as a prior step to constructing a radiosity simulation equation is therefore restricted by the number of combinations of intersecting polygons that must be checked. For example, if fifty thousand polygons are present in a scene, the number of potential intersections that must be checked, according to known methods, would be five times ten raised to the power of eight (5×10
8
). Checking each individual pair of polygons for intersection is a non-trivial mathematical operation. In practice, therefore, the identification of intersecting surfaces in photo-realistic scenes is impossible to achieve directly, using known methods, and operator intervention is necessary in order to identify surfaces where such problems occur.
SUMMARY OF THE INVENTION
According to a first aspect of the present invention, there is provided a method of generating image data for a scene, wherein said scene includes object surfaces in three-dimensions, comprising the steps of identifying intersecting or touching surfaces by analysing said surface within a hierarchy of bounding volumes; and constructing a multi-resolution representation of the radiosity equation for said scene, wherein one of said identified surface is considered separately for the light emission on either side of a line of contact or intersection.
In a preferred embodiment, the step of identifying intersecting or touching surfaces by analysis of bounding volumes, includes the component steps: considering bounding volumes and surfaces as items; identifying pairs of items; determining whether both items in the pair are surfaces; determining an overlap of items or an intersection of surfaces; and upon a condition of overlap, recursing the above component steps, retaining the smaller item and selecting another; or upon condition of an intersection, storing an indication of this condition; or upon condition of an intersection, storing an indication of this condition.
Preferably, the hierarchy of bounding volumes is created for the dual purpose of identifying intersecting or touching surfaces, and an additional method for generating image data from said scene.
According to a second aspect of the present invention, there is provided apparatus for generating image data from scene data, including processing means, and storage means for storing said scene data and for storing instructions for said processing means, wherein said scene includes object surface in three-dimensions and said instructions are arranged to control said processing means to perform the steps of: identifying intersection or touching surfaces by analysing said surfaces within a hierarchy of bounding volumes; and constructing a multi-resolution representation of the radiosity equation for said scene, wherein one of said identified surfaces is considered separately for light emission on either side of a line of contact with intersection.
In a preferred embodiment, the apparatus is further configurable to perform the step of solving the radiosity equation. Preferably, the apparatus is further configurable to perform a step-by-step rendering of said image data in response to a user specified view. Preferably, the apparatus is further configurable to include the step of rendering the image data in response to camera data generated within a virtual set.
REFERENCES:
patent: 4928250 (1990-05-01), Greenberg et al.
patent: 5175808 (1992-12-01), Sayre
patent: 5313568 (1994-05-01), Wallace et al.
patent: 5488700 (1996-01-01), Glassner
patent: 5579455 (1996-11-01), Greene et al.
patent: 5734385 (1998-03-01), Mima
patent: 5808620 (1998-09-01), Doi et al.
patent: 5894309 (1999-04-01), Freeman et al.
patent: 5909087 (1999-06-01), Bryde et al.
patent: 5914721 (1999-06-01), Lim
patent: 5936633 (1999-08-01), Aono et al.
patent: 6058259 (2000-05-01), Murakami
patent: 6078332 (2000-07-01), Ohazama
patent: 6084587 (2000-07-01), Tarr et al.
patent: 6084590 (2000-07-01), Robotham et al.
patent: 6366283 (2002-04-01), Tampieri
J. Dorsey et al., “Interactive Design of Complex Time-Dependent Lighting,” IEEE Comp. Graphics and Applications, 15(2):26-35, 1995.
J. Nimeroff, “Implementation and Analysis of an Image-Based . . . Environments,” IEEE Trans. On Visalization and Comp. Graphics, 2(4):283-297, 1996.
D. Lischinski et al, “Discontinuity Meshing for Accurate Radiosity,” Cornell Univ., IEEE Comp. Graphics and Applications, pp. 25-39, 1992.
D.W. George et al., “Radiosity Redistribution for Dynamic Environments,” Cornell Univ., IEEE Comp. Graphics and Applications, pp. 26-34, 1990.
Y. Chrysanthou, “Fast Approximate Quantitative Visibility for Complex Scenes,” IEEE Comp. Graphics Int'l Proceedings, pp. 220-227, 1998.
E. Pang et al., “An Efficient Implementation of Affine Transformation Using One-Dimensional FFT's,” University of Toronto, Ontario, Canada MTS 3G4, IEEE Conf., 4:2885-2888, 1997.
Autodesk Canada Inc.
Gates & Cooper LLP
Santiago Enrique L
Zimmerman Mark
LandOfFree
Radiosity with intersecting or touching surfaces does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Radiosity with intersecting or touching surfaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Radiosity with intersecting or touching surfaces will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3119223