Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-03-03
2001-07-17
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06262742
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to generating image data, wherein a plurality of elements 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 established 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. The system of equations is usually extremely large, and several refinements to radiosity simulation have been established in order to make implementation of this method practical for scenes containing large numbers of elements.
A known advantage of radiosity is that once the system of equations has been solved, and light emission values determined, the light emission of elements may be considered as view-independent, resulting in a separate radiosity rendering process which 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, large data structures are generated which efficiently represent all of the interactions that are necessary in order to obtain light emission values for all of the elements in a scene. In photo-realistic implementation of radiosity simulation, a hierarchical structure of elements is created, such that complex lighting gradients over the surface of various objects may be represented to a high degree of resolution. This necessitates the definition of large numbers of small mesh elements, of which object surfaces are comprised. In order to reduce the amount of memory that is used to represent the resulting system of equations, mesh elements having similar geometry may be associated with a common master element, by way of a transformation function. The use of master elements in hierarchical scene structures has been established for reducing memory requirements within photo-realistic image rendering algorithms such as ray tracing.
Master elements are considered as residing in canonical space, whereas the objects and mesh elements of a three-dimensional scene are considered as residing in world space. The set of transformation functions between master elements in canonical space and elements in world space that is required for ray tracing is known. However, radiosity simulation requires additional functionality to be available, in order to take full advantage of the data structures that are created when mapping mesh elements in world space to master elements.
It is an aim of the present invention to provide an improved method of master element mapping for use in radiosity simulation.
SUMMARY OF THE INVENTION
According to a first aspect of the present invention, there is provided a method of generating image data from scene data, wherein said scene data includes object elements in world space; wherein said object elements each have a surface that may be subdivided into a mesh; a plurality of said objects have a surface that is created in response to data from a master shape in canonical space; said surface is created by an affine transformation of said master shape; said master shape has a known area; a corresponding area of said surface is calculated with reference to the adjoint matrix of said affine transformation; and said surface areas in world space are used to determine light emission characteristics for said scene.
In a preferred embodiment, the affine transformation is applied to mesh elements in the master shape to generate mesh elements in world space, wherein the adjoint matrix of said affine transformation is determined once for a selected surface; and said adjoint matrix is applied a plurality of times to determine the areas of mesh elements of said selected surface. Preferably, the master shape is meshed hierarchically such that said surfaces derived from said master shape derive their respective mesh elements from said master shape.
In a preferred embodiment, the master shape is planar and said surface area may be calculated by a matrix-vector multiplication between adjoint matrix and a normal to said master shape, obtaining a magnitude, and multiplying this magnitude by the corresponding area in the master shape.
Preferably, the master shape is non-planar and an area function is determined with reference to a ratio between a differential area of said surface in world space and a corresponding differential area to said master shape in canonical space, said differential area in world space being determined with reference to said adjoint matrix and a normal; and a numerical quadrature integration is performed with reference to said area function in order to determine the area of said surface in world space.
Preferably, an area of said surface in world space is determined by the product of a corresponding area in the master shape in canonical space, and the magnitude of the matrix-vector multiplication between said adjoint matrix and a normal to said area of said master shape, wherein said normal has unit magnitude.
According to a second aspect of the present invention, there is provided an apparatus for generating image data from scene data, including processing means, and storage means for storing instructions for said processing means and data representing said scene; wherein said scene includes object elements in world space; said object elements each having a surface that may be subdivided into a mesh, and a plurality of said objects having a surface that is created in response to data from a master shape in canonical space; said instructions configurable to control said processing means to perform the steps of: creating said surface by an affine transformation of said master shape, wherein said master shape has a known area; calculating a corresponding area of said surface with reference to the adjoint of said affine transformation; and using said surface in world space to determine light emission characteristics for this scene.
REFERENCES:
patent: 5175808 (1992-12-01), Sayre
patent: 5488700 (1996-01-01), Glassner
patent: 5914721 (1999-06-01), Lim
patent: 5936633 (1999-08-01), Aono et al.
patent: 6078332 (2000-06-01), Ohazama
“Interactive Design of Complex Time-Dependent Lighting” J. Dorsey et al., Cornell University, IEEE Computer Graphics and Applications, vol. 15, Issue 2, Mar. 1995.*
“Implementation and Analysis of an Image-Base Global Illumination Framework for Animated Environments” J. Nimeroff et al., IEEE Transactions on Visualization and Computer Graphics, vol. 2, No. 4, Dec. 1996.*
“Discontinuity Meshing for Accurate Radiosity” Dani Lischinski et al., Cornell University, IEEE Computer Graphics & Applications, Nov. 1992.*
“Radiosity Redistribution for Dynamic Environments” D. W. George et al., Cornell University, IEEE Computer Graphics & Applications, 1990.*
“Fast Approximate Quantitative Visibility for Complex Scenes” Yiorgos Chrysanthou, IEEE, Computer Graphics International Proceedings, 1998.*
“An Efficient Implementation Of Affine Transformation Using One-Dimensional FFT's” E. Pang et al., University of Toronto, Ontario, MtS-3G4, Canada, IEEE Conference on, vol. 4, pp. 2885-2888, 1997.
Discreet Logic Inc.
Gates & Cooper LLP
Santiago Enrique L
Zimmerman Mark
LandOfFree
Generating image data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Generating image data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generating image data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2514405