Method and apparatus for generating realistic images using a discrete representation

• US 5,442,733 A
• Filed: 03/20/1992
• Issued: 08/15/1995
• Est. Priority Date: 03/20/1992
• Status: Expired due to Fees

• Current Assignee: The Research Foundation for The State University of New York (State University of New York)
• Original Assignee: The Research Foundation for The State University of New York (State University of New York)
• Inventors: Cohen, Daniel, Yagel, Roni, Kaufman, Arie E.
• Primary Examiner(s): Jankus, Almis R.
• Application Number:
  US07/855,223
• Time in Patent Office: 1,243 Days
• Field of Search: 395/119, 395/120, 395/121, 395/123, 395/124, 395/127, 395/128, 395/133, 364/413.13, 324/306
• US Class Current: 345/424
• CPC Class Codes: G06T 15/06 Ray-tracing
• CPC Class Codes: G06T 15/50 Lighting effects

Abstract

A method for generating realistic images using discrete representations employs a discrete voxel based representation of the scene within a three-dimensional (3-D) Cubic Frame Buffer of infinitesimal voxels. Each voxel stores information corresponding to the attributes of that portion of the scene. Numerous sight rays are traversed through the Cubic Frame Buffer. When a non-transparent infinitesimal voxel is encountered by a traversing sight ray, a hit is recognized. The attributes of that portion of the object that is encountered are then used for generating secondary rays. Depending upon the number and characteristics of the secondary rays that are generated, an appropriate representation of the scene can be generated from any viewing direction.

Claims

1. A method for generating a 2-D realistic image having a plurality of pixels, the method using discrete 3-D voxel representations of 3-D continuous objects that make up a scene, the method comprising:

a) forming a discrete 3-D voxel representation of each 3-D continuous object, each discrete 3-D voxel representation utilizing a plurality of voxels, each voxel representing a particular unit volume of the 3-D continuous object, each voxel having a plurality of attributes corresponding to characteristics of a corresponding unit volume of the 3-D continuous object;

b) storing each discrete 3-D voxel representation in a 3-D cubic frame buffer of voxels;

c) selecting a voxel connectivity for a plurality of families of 3-D discrete rays, each 3-D discrete ray of each family of 3-D discrete rays being formed according to the selected voxel connectivity, each family of 3-D discrete rays including at least one ray;

d) traversing the at least one ray of each family of 3-D discrete rays from a corresponding pixel through the 3-D cubic frame buffer of voxels, the traversal of the at least one ray of each family of 3-D discrete rays being performed for each of the plurality of pixels of the 2-D realistic image;

e) detecting encounters for each of the plurality of families of 3-D discrete rays with the discrete 3-D voxel representations, each encounter providing illumination values for each family of 3-D discrete rays; and

f) combining the illumination values to provide a composite illumination value for each of the plurality of families of 3-D discrete rays, each composite illumination value corresponding to a pixel value for generating the 2-D realistic image.

2. A method for generating a 2-D image having a plurality of pixels and using discrete 3-D voxel representations of 3-D continuous objects as defined by claim 1 wherein the plurality of voxel attributes include a proximity indicator, the proximity indicator denoting a nearness to a 3-D object, and wherein when the proximity indicator is encountered by one of the plurality of families of 3-D discrete rays, the voxel connectivity of the family of 3-D discrete rays is reselected.

3. A method for generating a 2-D image having a plurality of pixels and using discrete 3-D voxel representations of 3-D continuous objects as defined by claim 1 wherein the plurality of voxel attributes include a light source illumination indicator, the light source illumination indicator denoting whether a corresponding light source is visible from a voxel location, not visible from a voxel location or partially visible from a voxel location, wherein shadow-illumination rays are generated in a direction of a corresponding light source if the light source illumination indicator denotes that the light source is partially visible from the corresponding voxel.

4. A method for generating a 2-D image having a plurality of pixels and using discrete 3-D voxel representations of 3-D continuous objects as defined by claim 1 wherein the family of 3-D discrete rays includes a primary ray.

5. A method for generating a 2-D image having a plurality of pixels and using discrete 3-D voxel representations of 3-D continuous objects as defined by claim 4 wherein the family of 3-D discrete rays also includes at least one secondary ray.

6. A method for generating a 2-D image having a plurality of pixels and using discrete 3-D voxel representations of 3-D continuous objects as defined by claim 4 wherein when an encounter is detected between the primary ray and one of the discrete 3-D voxel representations a secondary ray is generated.

7. A method for generating a 2-D image having a plurality of pixels and using discrete 3-D voxel representations of 3-D continuous objects as defined by claim 6 wherein the secondary ray is generated by referring to the primary ray and the attributes of the encountered voxel.

8. A method for generating a 2-D image having a plurality of pixels and using discrete 3-D voxel representations of 3-D continuous objects as defined by claim 6 wherein when an encounter is detected between a first secondary ray and the 3-D discrete voxel representation, at least a second secondary ray is generated.

9. Apparatus for generating a 2-D image having a plurality of pixels using discrete 3-D voxel representations of 3-D continuous objects that make up a scene as defined by claim 1 wherein the means for traversing each family of 3-D discrete rays includes:

a) a ray retrieval mechanism coupled to the 3-D Cubic Frame Buffer of voxels, the ray retrieval mechanism fetching from the 3-D Cubic Frame Buffer of voxels a plurality of voxels which make up a discrete voxel form of the families of 3-D discrete rays;

b) a ray projection mechanism coupled to the ray retrieval mechanism and receiving the plurality of voxels that make up the discrete voxel form of the families of 3-D discrete rays, the ray projection mechanism locating the first non-transparent voxel along the discrete voxel form of the families of 3-D discrete rays; and

c) a ray manager coupled to the ray retrieval mechanism, the ray manager also being coupled to the ray projection mechanism, the ray manager receiving a signal from the ray projection mechanism indicating that an encounter has been detected between a family of 3-D discrete rays and the discrete 3-D voxel representations, the ray manager providing a signal to the ray retrieval mechanism denoting a definition of the next ray to be accessed from the 3-D Cubic Frame Buffer of voxels.

10. A method for generating a three-dimensional (3-D) discrete voxel representation of a 3-D continuous ray within a Cubic Frame Buffer, the method comprising:

a) determining a plurality of geometric parameters which represent the 3-D continuous ray;

b) setting a pointer in the Cubic Frame Buffer according to a start point of the 3-D continuous ray;

c) selecting a first voxel connectivity corresponding to the set of geometric parameters which represent the 3-D continuous ray in 3-D discrete voxel space;

d) determining a set of relative Cubic Frame Buffer memory address offsets which interrelate neighboring voxels of the Cubic Frame Buffer;

e) calculating a plurality of threshold variables utilizing the set of geometric parameters and the selected voxel connectivity;

f) calculating a plurality of threshold variable increments according to the selected voxel connectivity;

g) determining a voxel along the 3-D continuous line based upon a family of decisions using the threshold variables;

h) stepping along the Cubic Frame Buffer memory to locate the voxel according to the relative Cubic Frame Buffer memory address offsets; and

i) updating the plurality of threshold variables utilizing the plurality of threshold variable increments.

11. A method for generating a 3-D discrete voxel representation of a 3-D continuous ray as defined by claim 10, the method further comprising:

a) selecting a second voxel connectivity with which to represent the 3-D continuous ray;

b) determining a plurality of connectivity switching variables; and

c) updating the plurality of decision variables utilizing the connectivity switching variables.

12. A method for generating a 3-D discrete voxel representation of a 3-D continuous ray as defined by claim 11, wherein the first voxel connectivity is 26-connected and the second voxel connectivity is 6-connected.

13. A method for generating a three-dimensional (3-D) voxel representation of a two-dimensional (2-D) continuous object in 3-D space comprising:

a) selecting a surface connectivity;

b) determining a set of geometric parameters corresponding to the 2-D continuous object in 3-D space;

c) specifying a base line and a template line based upon the geometric parameters;

d) selecting a voxel connectivity for the base line based upon the selected surface connectivity;

e) selecting a voxel connectivity for the template line based upon the selected surface connectivity;

f) generating voxel representations for the base line and the template line according to the selected voxel connectivities and based upon the specified geometric parameters;

g) determining the boundaries of the 2-D continuous object in 3-D space according to the geometric parameters;

h) storing the base line and template line according to the selected voxel connectivity in a Cubic Frame Buffer of voxels; and

i) replicating the template line for each voxel along the base line, the replication being performed within the boundaries of the 2-D continuous object in 3-D space,

j) storing the replicated template lines in the Cubic Frame Buffer of voxels.

14. Apparatus for generating a two-dimensional (2-D) realistic image having a plurality of pixels using discrete three-dimensional (3-D) voxel representations of 3-D continuous objects that make up a scene, the apparatus comprising:

a) means for forming a discrete 3-D voxel representation of each 3-D continuous object utilizing a plurality of voxels, each voxel representing a particular unit volume of the 3-D continuous object, each voxel having a plurality of attributes corresponding to characteristics of a corresponding unit volume of the 3-D continuous object;

b) a 3-D Cubic Frame Buffer of voxels;

c) means for storing each discrete 3-D voxel representation in the 3-D Cubic Frame Buffer of voxels;

d) means for selecting a voxel connectivity for a plurality of family of 3-D discrete rays, each ray of the plurality of families of 3-D discrete rays being formed according to the selected voxel connectivity;

e) means for traversing each family of 3-D discrete rays through the 3-D Cubic Frame Buffer of voxels, the traversal of the plurality of families of 3-D discrete rays being performed for the plurality of pixels of the 2-D realistic image;

f) means for detecting encounters for each of the plurality of families of 3-D discrete rays with the discrete 3-D voxel representations, each encounter providing illumination values for each family of 3-D discrete rays;

g) means for combining the illumination values to provide a composite illumination value for each of the plurality of families of 3-D discrete rays, each composite illumination value corresponding to a pixel value for generating the 2-D realistic image; and

h) a video screen for displaying the composite illumination values, the video screen having a plurality of pixels, each composite illumination value corresponding to one pixel of the plurality of pixels of the video screen, the video screen providing a 2-D realistic image of the scene.