Method of edge smoothing for a computer image generation system

• US 4,811,245 A
• Filed: 12/19/1985
• Issued: 03/07/1989
• Est. Priority Date: 12/19/1985
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: General Electric Company
• Inventors: Merz, Donald M., Fadden, Richard G., Bunker, William M.
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): HERNDON, HEATHER R
• Application Number:
  US06/810,738
• Time in Patent Office: 1,174 Days
• Field of Search: 364/518, 364/521, 364/424, 340/703, 340/724, 340/729, 340/750, 340/798-800
• US Class Current: 345/592
• CPC Class Codes: G06T 15/503 Blending, e.g. for anti-aliasing
• CPC Class Codes: G09B 9/301 by computer-processed or -generated image

Abstract

A method for computer image generation simulated visual scenes for applications such as flight training. The processing to generate the image takes place in three sequential stages: Controller, Geometry Processor, and Display Processor. At any point in time, the stages are processing data for three consecutive scenes. Each scene is comprised of a plurality of faces. Processing prior to the Display Processor accomplishes clipping and perspective transformation of faces. The Display Processor then generates the scene with pipeline processing accomplishing four major tasks: span detection or windowing, span sequencing, mask processing, and color processing. The improved realism of the computer generated image includes application of area-times-color smoothing, using fractional face areas to improve scene quality and reduce quantizing artifacts.

Claims

1. In an image generating system of the type for converting digital data into a sequence of display frames of image data suitable for display on a video image system, the image system forming a display by individually illuminating each of a plurality of color pixels, each of the frames of image data defining a plurality of faces and each of the frames being divided into a plurality of spans, a method for determining the faces to be displayed in each of the spans comprising the steps of:

(a) identifying data for one of the frames of display, the data defining face locations, each of the faces associated with at least one span and being arranged in a descending order of priority;

(b) determining the highest priority face for each span;

(c) determining an area within each span covered by the highest priority face;

(d) computing pixel image data representative of the pixels within each span covered by the highest priority face of the span;

(e) repeating step (b) through step (d) for each span by replacing the highest priority face of each span with the next highest priority face not having been processed until the last face of each span is processed into pixel image data or until all areas of each span are fully covered by faces and the corresponding pixel image data have been computer; and

(f) transferring the pixel image data to the video image system;

wherein he step of determining an edge further comprises the steps of;

identifying data representative of an edge of a face, each edge having a beginning and ending vertex and a slope;

searching along the edges of a face in a predetermined direction, starting with a beginning vertex of an edge of the face, for each span that the edge passes through;

storing each span intersected by the edge;

calculating a perpendicular distance from each corner of each intersected span to the edge;

determining a next span intersected by an edge;

repeating the steps of searching, storing, calculating and determining a next edge until the last edge of the face is processed; and

repeating the steps of searching, storing, calculating, determining a next edge and repeating using the next face, until all the faces are processed.

2. The method of claim 1, wherein the step of calculating further comprises the steps of:

obtaining data representative of the slope of an edge and the endpoints of the edge;

calculating the perpendicular distance from the corner of each span according to the formula D=LO+LI*I+LJ*J, where;

D is the perpendicular distance from a point (I,J) to an edge;

LO is an initial predetermined distance from a fixed reference point such as I=0 and J=0;

LI is the cosine of the edge slope; and

LJ is the sine of the edge slope; and

supplying data representative of the perpendicular distance from the corner of a span to an edge.

3. The method of claim 1, further comprising the steps of:

(g) determining a span to be processed based upon data representative of the area covered by previously processed faces;

(h) the edges of the highest priority non-processed face intersecting a span;

(i) determining the portions of the span covered by the face defined by the recalled edges; and

(j) repeating steps (g) of determining through step (i) of determining until all areas of all spans are covered or until all faces are processed.

4. The method of claim 3, wherein the step (i) of determining the portions of the span further comprises the steps of:

(k) determining a pixel of a span intersected by an edge of a face;

(l) dividing the pixel into a plurality of subpixel areas;

(m) computing a distance from the center of each pixel area to the edge;

(n) determining the subpixel areas covered by the face bounded by the edge;

(o) computing a weight for each sub-pixel area from the area covered by the face and the color of the face;

(p) repeating step (l) of dividing through step n of computing for each edge through the pixel;

(q) summing the weighted values for each pixel;

(r) generating a color for each pixel corresponding to the summed weighted values; and

repeating step (k) through step (r) for each pixel intersected by an edge in the span.

5. The method of claim 4, wherein the step (q) of summing further comprises the steps of:

receiving data representative of a translucency of a face in a subpixel area;

summing the translucency of the subpixel of the face with the weighted value for the subpixel area to obtain a translucency weighted value.

6. The method of claim 4, wherein the step (m) of computing, further comprises the step of computing the distance from the center of a subpixel area to the edge by bilinear interpolation of the distances from the corners of the pixel to the edge.

7. The method of claim 6, further comprising the step of receiving data representative of a translucency of a face in a subpixel area based upon a programmatic event, the programmatic event representative of smoke, fog and events characteristic of simulated warfare.

8. The method of claim 4, wherein the step (n) of determining, further comprises the step of determining the subpixel areas assigned to the face as a function of the distance to the edge and slope of the edge.

9. The method of claim 4, wherein the step (m) of computing, further comprises the steps of:

calculating the perpendicular distance from the corner of each span according to the formula D=LO=LI*I+LJ*J, where;

D is the perpendicular distance from a point (I,J) to an edge;

LO is an initial predetermined distance from a fixed reference point such as I=0 and J=0;

LI is the cosine of the edge slope; and

LJ is the sine of the edge slope; and

determining the subpixel areas assigned to the face in response to the distance to the edge and the slope of the edge.

10. The method of claim 9, further comprising the step of determining the accuracy of a subpixel area assigned to the face by a total area accuracy of at least one-half subpixel area.

11. The method of claim 10, further comprising the step of determining the accuracy of a subpixel assigned to the face by a positioned accuracy of at least one subpixel.

12. The method of claim 4, wherein the step (o) of computing, further comprises the step of computing a weight for each subpixel representative of the area covered by a face times the color.

13. The method of claim 1, wherein the step of transferring, further comprises the steps of:

receiving modification data for a pixel, the modification data including a haze control, an illumination control and a texture control;

computing a color contribution for the pixel image data from the modification data and the previous pixel image data; and

transferring the color contribution of the pixel image data to the video display.

14. The method of claim 1, wherein the step of calculating, further comprises the step of determining the intersection of the edge of the face with a subsequent span from the distance for each previous span corner to the edge and the slope of the edge.

15. The method of claim 14, further comprising the step of determining the intersection of the edge with a subsequent span from look up table data in a memory.

16. The method of claim 15, wherein the memory is a read only memory, further comprising the steps of:

inputting into the address lines of a read only memory, data representative of the slope of the edge and the endpoints;

calculating the perpendicular distance from the corner of each span according to the formula D=LO=LI*I+LJ*J, where;

D is the perpendicular distance from a point (I,J) to an edge;

LO is an initial predetermined distance from a fixed reference point such as I=0 and J=0;

LI is the cosine of the edge slope; and

LJ is the sine of the edge slope; and

(c) outputting from the data lines of the read only memory, data representative of the subsequent span intersected by an edge of a face.

17. A method for attributing a value to a pixel when an edge of a face intersects the pixel, the face having a predetermined characteristic, wherein the pixel includes a predetermined number of subpixels and further wherein the value attributed to the pixel is representative of a predetermined combination of the characteristic assigned to each subpixel of the pixel, comprising:

assigning the predetermined characteristic to each subpixel that lies entirely on one side of the edge, wherein the one side is determinable with respect to a predetermined direction along the edge;

assigning the predetermined characteristic to subpixels intersected by the edge in proportion to the area of subpixels intersected by the edge, the area lying on the one side of the edge; and

attributing the value to the pixel in response to the predetermined combination of the characteristic assigned to each subpixel of the pixel;

whereby a smooth transition between pixels along an edge is obtained.

18. The method as in claim 17, wherein the step of assigning to subpixels includes assigning the predetermined characteristic to subpixels from the anterior to the posterior portion of the edge with respect to the predetermined direction along the edge.

19. The method as in claim 18, wherein the step of assigning to subpixels further includes assigning the predetermined characteristic to a number of subpixels intersected by the edge equal to the integer portion of the sum of the areas of the subpixels intersected by the edge and lying on the one side of the edge when the edge is substantially parallel to a side of the pixel and further assigning the predetermined characteristic to another subpixel intersected by the edge when the fractional portion of the sum of the areas of the subpixels intersected by the edge and lying on the one side of the edge is greater than about one-half subpixel.