Advanced video object generator

• US 4,727,365 A
• Filed: 05/21/1986
• Issued: 02/23/1988
• Est. Priority Date: 08/30/1983
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: General Electric Company
• Inventors: Nelson, Michael P., Fadden, Richard G. Jr., Economy, Richard, Bunker, William M., Chandler, Jimmy E.
• Primary Examiner(s): Curtis, Marshall M.
• Application Number:
  US06/865,591
• Time in Patent Office: 643 Days
• Field of Search: 340/723, 340/725, 340/728, 340/729, 340/730, 340/703, 340/747, 340/744
• US Class Current: 345/427
• CPC Class Codes: G06T 15/80 Shading

Abstract

A computer video image generating system including a computer memory having three dimensional object data stored therein employs an advanced object generator for retrieving and processing the object data for output to a span processor for controlling the pixel-by-pixel video output signal for a video display. The advanced object generator includes a translucency processor, an edge-on fading processor, a level of detail blending processor and a bilinear interpolator for texture smoothing.

Claims

1. An advanced object generator comprising:

data memory means for storing cell-by-cell data for each of a plurality of faces of a plurality of three-dimensional objects, said cell data including data stored for each three-dimensional object on a plurality of planes, said planes being arranged in such a manner as to respectively present a plurality of viewing angles relative to a given view point;

vector processing means for calculating object transformations that translate operator inputs into image orientation control signals and for calculating pixel-by-pixel image data;

means for receiving image data from said vector processing means for selecting image data projected from selected ones of said plurality of planes for processing or video display;

edge-on fading factor processing means for calculating an edge-on fading factor for each face of said plurality of faces for each three-dimensional object to be displayed, each of said plurality of planes comprising a plurality of planes intersecting along a line within a respective object and said means for calculating an edge-on fading factor comprising;

means for calculating a viewing angle between a viewray extending from said given viewpoint to an object being displayed and the respective planes of the object being displayed, and

translucency threshold calculation means for providing a multiplier for each respective plane of a three-dimensional object, said multiplier being indicative of the size of said respective viewing angle for each plane of each object to be displayed;

span processing means responsive to said edge-on fading factor processing means for calculating a fading factor percentage value based on the calculated edge-on fading factor for each face of said plurality of faces for each three-dimensional object of pixel-by-pixel display data;

video monitor means for displaying images of said objects comprising pixel-by-pixel displays of said display data; and

wherein said translucency threshold calculation means comprises;

means for receiving viewing angle data for each respective face of an object from said means for calculating a viewing angle;

means for comparing each said respective viewing angle with a predetermined minimum angle and a predetermined maximum angle;

means for calculating a translucency coefficient for each said respective face when said viewing angle is between said minimum and said maximum viewing angles;

means for making each said respective face completely transparent when said viewing angle is less than said minimum viewing angle; and

means for supplying said respective translucency coefficient to said span processing means.

2. The invention of claim 1 wherein said means for calculating a translucency coefficient comprises:

means for calculating a translucency coefficient when a respective one of said viewing angles is less than 36 degrees and greater than 18 degrees.

3. An advanced object generator comprising:

object data memory means for storing cell-by-cell data for a plurality of levels of detail of a plurality of a plurality of faces of a plurality of three-dimensional objects for retrieval and processing for video display of such objects;

vector processing means for translating operator inputs into image orientation control signals for calculating pixel-by-pixel display data;

first level of detail calculation means for calculating address data to retrieve from said object data memory means data for a first level of detail for each object image to be processed for video display, said first level of detail calculation means comprising;

means for calculating cell image size of each cell of a scene to be displayed;

means for comparing said cell image size to a previously calculated pixel dimension in order to determine which levels of detail to process;

means for accessing a first computer memory look-up table having previously determined level of detail data stored therein;

second level of detail calculation means for calculating address data to retrieve from said object data memory means data for a second level of detail for each object image to be processed for video display, said second level of detail calculation means comprising;

means for accessing a second computer memory look-up table having previously determined level of detail data stored therein;

means for outputting cell data previously stored in computer map memory means for each of said first and second levels of detail for each object to be displayed,

level of detail blending means for combining the data for said first level of detail and the data for said second level of detail into a single level of detail output for each pixel of an image of an object, wherein said level of blending means comprises;

means for receiving as inputs gradients of image patterns upon each face image of a three-dimensional object;

means for receiving as inputs gradients of image patterns upon each face image of a three-dimensional object;

means for comparing said gradients with a predetermined maximum gradient for each of two dimensions;

means for comparing said gradients with predetermined values of said gradients to determine said higher level of detail;

means for calculating a level of detail blend control value;

means for calculating the one'"'"'s complement of said level of detail blend control output;

means for multiplying said level of detail blend control value by said cell data for said first level of detail to generate a first product output;

means for multiplying said one'"'"'s complement of said blend control value by said cell data for said second level of detail to generate a second product output;

summing means for adding the first product output to the second product output to produce a single modulation value output for each pixel of an image;

span processing means for translating said level of detail output into pixel-by-pixel display data; and

video monitor means for displaying a plurality of images of objects comprising pixel-by-pixel displays of said display data.

4. The invention of claim 3 comprising:

a plurality of said level of detail blending means each providing a level of detail modulation value output for a plurality of pixels of said image.

5. An advanced object generator comprising:

data memory means for storing cell-by-cell object data for each of one or more faces of a plurality of objects for retrieval and processing for video display of such objects;

vector processing means for calculating object transformations that translate operator inputs into image orientation control signals and for calculating pixel-by-pixel image data;

cell texture address means for determining a memory location to be accessed for retrieval of cell texture data from said data memory means for display, said cell texture address comprising;

first and second floating point dual multiplying and summing means for calculating a first numerator and a second numerator needed for calculating object location coefficients for each object face to be displayed;

floating point dual summing and multiplying means for calculating a denominator common to both said coefficients;

means for calculating the reciprocal of said demoninator;

means for multiplying said denominator reciprocal by said first numerator and said second numerator and for adding to the resulting products reference values of said respective first and second numerators to obtain addresses on an object face corresponding to a span corner;

vertical interpolator means for calculating intermediate address parameters of image texture data of image elements disposed in one dimension between points located at addresses output by said floating point dual summing and multiplying means and for accessing texture data of predetermined columns of pixels on a span of said video display;

horizontal interpolator means for calculating intermediate address parameters of image texture data of image elements disposed in a second dimension on lines between points on first and second ones of said columns of pixels;

cell texture output means for outputting said cell texture data; and

span processing means for translating said cell texture data into pixel-by-pixel displays of said display data,

6. The invention of claim 5 further comprising bilinear interpolation means comprising:

means for receiving a set of vertical and horizontal address pairs defining a span from said data memory means;

means for calculating an incrementing value;

incerementing means for incrementing a plurality of intermediate vertical addresses defining a plurality of pixel addresses separated vertically by said incrementing value along respective left and right hand columns of pixels defining respective edges of said span;

means for calculating horizontal addresses for respective rows of pixels located between respective pairs of vertically aligned pixels of said left and right hand columns to define a complete array of pixel addresses for said span; and

output means for accessing a texture map memory at each pixel address of said array of pixel addresses.

7. The invention of claim 6 wherein said means for calculating an incrementing value comprises:

means for subtracting a vertical address of a first pixel at one end of a column of pixels from a vertical address of a second pixel at the other end of said column of pixels to obtain a vertical address difference; and

means for dividing said vertical address difference by a predetermined constant equal to a number of desired vertical increments in said column.

8. The invention of claim 7 wherein said incrementing means comprises:

adder means for repetitively adding said incrementing value to a first vertical address and outputting a new vertical address after each successive addition until said first vertical address equals a second vertical address.

9. The invention of claim 8 wherein said means for calculating horizontal address values comprises:

first horizontal address summing means for adding two horizontal addresses input from said data memory means;

first divider means for dividing the sum of said horizontal addresses to yield a span horizontal midpoint address;

second horizontal summing means for adding a first horizontal address from said data memory means and said horizontal midpoint address;

second divider means for dividing the sum of said first horizontal address and said horizontal midpoint address to yield a one-fourth span horizontal address;

third horizontal summing means for adding a second horizontal address from said data memory means and said horizontal midpoint address; and

third divider means for dividing the sum of said second horizontal address and said horizontal midpoint address to yield a three-fourths span horizontal address.

10. An advanced object generator for providing computer generated image control signals for real-time display comprising:

data memory means for storing cell-by-cell data for a plurality of levels of detail for a plurality of faces of a plurality of three-dimensional objects for retrieval and computer processing for video display of such objects;

said cell data including data stored for each three-dimensional object on a plurality of planes;

said planes being arranged in such manner as to respectively present a plurality of viewing angles to a given viewpoint;

vector processing means for calculating object transformations that translate operator inputs into image orientation control signals and for calculating valid pixel-by-pixel image data;

translucency code storage means for storing predetermined translucency factors for selected cells of the object faces;

translucency code processing means for calculating translucency factors on a pixel-by-pixel basis for said selected cells of an object;

means for receiving image data from said vector processing means for selecting image data projected from selected ones of said plurality of planes for processing for video display;

means for calculating an edge-on fading factor for each face of said plurality of faces for each three-dimensional object to be displayed;

first level of detail calculation means for calculating address data to retrieve from said object data memory means data for a first level of detail for each object image to be processed for video display;

second level of detail calculation means for calculating address data to retrieve from said object data memory means data for a second level of detail for each object image to be processed for video display;

level of detail blending means for combining the data for said first level of detail with the data for said second level of detail into a single level of detail output for each pixel of a video image of an object;

bilinear interpolation means for calculating pixel-by-pixel address data for each span to be processed;

cell texture address means for determining a memory location in said data memory means to be accessed for retrieval of cell texture data;

output means for outputting pixel-by-pixel image control data;

span processing means for receiving said pixel-by-pixel image control data and translating said image control data into pixel-by-pixel display data; and

video monitor means for displaying a plurality of images of objects comprising pixel-by-pixel displays of said display data.

11. The invention of claim 10 wherein said translucency code processing means comprises:

means for selecting one translucency map, from a plurality of translucency maps stored in said data memory means, for each of the object faces to be processed for display upon said video monitor means; and

means for multiplying a translucency code for each pixel in an object retrieved from said one translucency map by cell data for each pixel of said object.

12. The invention of claim 10 wherein each of said plurality of planes comprises a plurality of planes intersecting along a line within a respective object and said means for calculating an edge-on fading factor comprises:

means for calculating a viewing angle between a viewray extending from said given viewpiont to an object being displayed and the respective planes of the object being displayed; and

translucency threshold calculation means for providing a multiplier for each respective plane of a three-dimensional object, said multiplier being indicative of the size of said respective viewing angle for each plane of each object to be displayed.

13. The invention of claim 12 wherein said translucency threshold calculation means comprises:

means for receiving viewing angle data for each respective face of an object from said means for calculating a viewing angle;

means for comparing each said respective viewing angle with a predetermined minimum angle and a predetermined maximum angle;

means for calculating a translucency coefficient for each said respective face when said viewing angle is between said minimum and said maximum viewing angles;

means for making each said respective face completely transparent when said viewing angle is less than said minimum viewing angle; and

means for supplying said respective translucency coefficient to said span processing means.

14. The invention of claim 13 wherein said means for calculating a translucency coefficient comprises:

means for calculating a translucency coefficient when a respectively one of said viewing angles is less than 36 degrees and greater than 18 degrees.

15. The invention of claim 14 wherein each said plurality of planes comprises:

a plurality of planes intersecting along a line within a respective object.

16. The invention of claim 10 wherein said first level of detail calculation means comprises:

means for calculating cell image size of each cell of a scene to be displayed;

means for comparing said cell image size to a previously calculated pixel dimension in order to determine which levels of detail to process;

means for accessing a first computer memory lookup table having previously determined level of detail data stored therein; and

wherein said second level of detail calculation means comprises;

means for accessing a second computer memory look-up table having previously determined level of detail data stored therein; and

means for outputting cell data previously stored in computer map memory means for each of said first and second levels of detail for each object to be displayed.

17. The invention of claim 16 wherein said first level of detail comprises a higher level of detail than said second level of detail and said level of detail blending means comprises:

means for receiving as inputs gradients of image patterns upon each face image of a three-dimensional object;

means for comparing said gradients with a predetermined maximum gradient for each of two dimensions;

means for comparing said gradients with predetermined values of said gradients to determine said higher level of detail;

means for calculating a level of detail blend control value;

means for calculating the one'"'"'s complement of said level of detail blend control output;

means for multiplying said level of detail blend control value by said cell data for said first level of detail to generate a first product output;

means for multiplying said one'"'"'s complement of said blend control value by said cell data for said second level of detail to generate a second product output;

summing means for adding the first product output to the second product output to produce a single modulation value output for each pixel of an image.

18. The invention of claim 17 comprising:

a plurality of said level of detail blending means each providing a level of detail modulation value output for a plurality of pixels of said image.

19. The invention of claim 10 wherein said cell texture address means comprises:

first and second floating point dual multiplying and summing means for calculating a first numerator and a second numerator needed for calculating object location coefficients for each object face to be displayed;

floating point dual summing and multiplying means for calculating a denominator common to both said coefficients;

means for calculating the reciprocal of said denominator; and

means for multiplying said denominator reciprocal by said first numerator and said second numerator and for adding to the resulting products reference values of said respective first and second numerators to obtain addrsses on an object face corresponding to a span corner;

vertical interpolator means for calculating intermediate address parameters of image texture data of image elements disposed in one dimension between points located at addresses output by said floating point dual summing and multiplying means and for accessing texture data of predetermined columns of pixels on a span of said video display; and

horizontal interpolator meana for calculating intermediate address parameters of image texture data of image elements disposed in a second dimension on lines between points on first and second ones of said columns of pixels.

20. The invention of claim 19 wherein said bilinear interpolation means comprises:

means for receiving a set of vertical and horizontal address pairs defining a span from said data memory means;

means for calculating an incrementing value;

incrementing means for incrementing a plurality of intermediate vertical addresses defining a plurality of pixel addresses separated vertically by said incrementing value along respective left and right hand columns of pixels defining respective edges of said spans;

means for calculating horizontal addresses for respective rows of pixels located between respective pairs of vertically aligned pixels of said left and right hand columns to define a complete array of pixel addresses for said span; and

output means for accessing a texture map memory at each pixel address of said array of pixel addresses.

21. The invention of claim 20 wherein said means for calculating an incrementing value comprises

means for subtracting a vertical address of a first pixel at one end of a column of pixels from a vertical address of a second pixel at the other end of said column of pixels to obtain a vertical address difference;

and

means for dividing said vertical address difference by a predetermined constant equal to a number of desired vertical increments in said column.

22. The invention of claim 21 wherein said incrementing means comprises:

adder means for repetitively adding said incrementing value to a first vertical address and outputting a new vertical address after each successive addition until said first vertical address equals a second vertical address.

23. The invention of claim 22 wherein said means for calculating horizontal address values comprises:

first horizontal address summing means for adding two horizontal addresses input from said data memory means;

first divider means for dividing the sum of said horizontal addresses to yield a span horizontal midpoint address;

second horizontal summing means for adding a first horizontal address from said data memory means and said horizontal midpoint address;

second divider means for dividing the sum of said first horizontal address and said horizontal midpoint address to yield a one-fourth span horizontal address;

third horizontal summing means for adding a second horizontal address from said data memory means and said horizontal midpoint address; and

third divider means for dividing the sum of said second horizontal address and said horizontal midpoint address to yield a three-fourths span horizontal address.

24. In a computer image generating system for generating an image of an object from stored data by color intensity control of a plurality of pixels forming the image of the object, the color intensity for each pixel being derived from a plurality of cells each having a predetermined color intensity value and a predetermined center position, and further a grouping of cells defining a texture pattern formed on a surface of the object, a method for determining color intensity for the plurality of pixels while obtaining smooth transitions between cell boundaries, the method comprising the steps of:

(a) defining a location of a pixel to be displayed;

(b) identifying the cells about a projection of the pixel whose centers define the corners of a polygon containing the center of the projection of the pixel;

(c) determining the location of the projection of the pixel center with respect to each cell identified in step (b);

(d) forming a weighted average value of color intensity for the pixel as a function of each cell color intensity value for cells identified in step (b) and the respective location determined in step (c); and

(e) providing the weighted average value determined in step (d) for color intensity control of the pixel.

25. The method of claim 24 including the further steps of:

(f) storing a translucency value for each cell;

(g) determining a translucency mask having a predetermined number of subpixels for the pixel to be displayed; and

(h) modifying the weighted average color intensity value in response to the translucency mask, wherein the modified weighted average color intensity value is supplied for color intenity control of the pixel.

26. The method of claim 24 and including the further steps of:

computing an apparent distance from a viewer to the object; and

filtering the cell data to selectively reduce the level of detail of the object as the apparent distance increases.

27. The method of claim 26 and including the step of establishing a plurality of zones of apparent distances between the viewer and the object, the step of filtering occurring at each transition between zones.

28. The method of claim 24 and including the step of establishing from a single high level of detail image map of the object a plurality of level of detail image maps for a stored image of the object, each subsequent level of detail map being obtained by filering data representative of predetermined ones of the plurality of cells to obtain a filtered color intensity value for a single cell representative of the predetermined ones of the plurality of cells.

29. The method of claim 24 and including the steps of:

determining an apparent distance from a viewer to the object;

identifying two consecutive level of detail maps bracketing the determined apparent distance;

computing the weighted average value of color intensity for the pixel for each of the two consecutive level of detail maps; and

blending the two computed weighted average color intensity values to obtain a blended color intensity value, wherein the blended color intensity value is supplied for color intensity control of the pixel.

30. The method of claim 29 wherein said step of blending comprises the step of bilinearly interpolating the blended value in proportion to the relation apparent distance from each of the two level of detail maps.

31. The method of claim 24, wherein a stored image of the object to be displayed is defined by a face having cells defined by the stored data and including the steps of:

determining the angle of a view ray from a predetermined view-point to a plane of the face;

computing a translucency factor as a function of the determined angle; and

modifying the weighted average value in response to the translucency factor thereby gradually to fade out faces oriented edge-on to a viewer.

32. The method of claim 24 wherein the step of forming a weight average value comprises the step of bilinearly interpolating the respective color intensity value for each cell identified in step (b) in response to the respective distance from each cell center to the projection of the pixel center.

33. The method of claim 24 wherein the step of identifying cells comprises the step of identifying four adjacent cells whose centers define a polygon containing the center of the projection of the pixel.