Triangle processor for 3-D graphics display system

• US 4,945,500 A
• Filed: 11/20/1989
• Issued: 07/31/1990
• Est. Priority Date: 11/04/1987
• Status: Expired due to Fees

• Current Assignee: Applicon, Inc. (Perspecta, Inc.)
• Original Assignee: Schlumberger Technologies Incorporated (Schlumberger NV)
• Inventors: Deering, Michael F.
• Primary Examiner(s): Shoop, Jr., William M.
• Assistant Examiner(s): SALATA, ANTHONY J
• Application Number:
  US07/440,459
• Time in Patent Office: 253 Days
• Field of Search: 364/521, 364/522, 364/511, 340/721, 340/723, 340/728, 340/729, 340/731, 340/732, 340/747, 340/750, 358/104
• US Class Current: 345/422
• CPC Class Codes: F02B 2075/027 four
• CPC Class Codes: G06T 15/405 using Z-buffer
• CPC Class Codes: G09G 5/42 characterised by the display of patterns using a display memory without fixed position correspondence between the display memory contents and the display position on the screen

Abstract

A process which stores a representation of a polygon forming a portion of a three-dimensional object and compares the polygon to pixels from a scan line as they are passed by. The processor stores a representation of a polygon and compares each pixel passed by the processor to the polygon to determine whether the pixel is within the polygon. If the pixel is within the polygon, its Z position (depth) is compared to the Z position of a corresponding position in the polygon. If the Z position of the polygon position is in front of the Z position of the pixel so that the polygon would obscure the previous pixel description, the Z position and an associates material value (e.g., color) of the polygon is substituted for the Z position of the pixel. The three-dimensional object is preferably represented with triangles and each polygon processor is preferably a triangle processor, with a series of triangle processors arranged in a pipeline. Two pipelines may be provided in parallel. Several triangle processors can be placed on a single semiconductor chip with input and output buffers for performing multiplexing, delaying and skewing. An X counter on the chip rederives the pixel X position, eliminating the need for this input.

Claims

1. An image processing system comprising:

a plurality of polygon processors coupled in series, each polygon process including

means for storing a representation of a single polygon, said polygon representing a portion of a three-dimensional object;

means for comparing said representation to an input representation of a pixel to determine whether said pixel is within said polygon;

means for comparing a Z position of said pixel to a Z position of said polygon; and

means for providing to an output of said polygon processor, which is coupled to an input of a next polygon processor in said series, except for a last polygon processor, a material property and Z position of said pixel in said polygon if said polygon has a Z position for said pixel in front of a received z position associated with said pixel.

2. The polygon processor of claim 1 wherein said polygons are triangles.

3. The triangle processor of claim 2 wherein each said triangle is represented by data comprising:

X, Y coordinates of each vertex of said triangle;

a Z coordinate for each of said vertices; and

a material property for said triangle.

4. The polygon processor of claim 1 further comprising means for inputting a representation of a new polygon initially and after pixels corresponding to all positions of said first-mentioned polygon have been compared to said first polygon.

5. The polygon processor of Claim 1 wherein an output of said means for comparing a Z position is used only if said pixel is within said polygon.

9. The polygon processor of claim 1 further comprising means for interpolating a Z value for internal positions of said polygon.

10. The polygon processor of claim 9 wherein each said polygon is further represented by additional data and further comprising means for interpolating said additional data for interior positions of said polygon.

11. The polygon processor of claim 9 wherein said additional data comprises a normal vector representation for each of a plurality of vertices of said polygon and said means for interpolating additional data comprises means for interpolating a normal vector.

12. The polygon processor of claim 9 wherein said additional data comprises a texture index value into a multidimensional color and/or perturbed normal texture table.

13. The polygon processor of claim 9 wherein said additional data comprises red, green and blue (RGB) color components.

14. The polygon processor of claim 1 wherein each position in said polygon is represented according to the same coordinate map used for said pixel so that said z positions for all polygons covering a given pixel position correspond to the same point location.

15. A semiconductor chip comprising a plurality of polygon processors as set forth in claim 1 coupled in series, each of said polygon processors further comprising enable logic addressably setable for that polygon processor, said enable logic having a first state for disabling said polygon processor from storing a representation of a polygon so that said polygon processor passes said representation of a polygon unaltered to a next polygon processor.

16. A semiconductor chip comprising a plurality of polygon processors as set forth in claim 1 coupled in series and further comprising:

counting means for providing an X position of a plurality of pixels to each of said polygon processors;

input buffer means for coupling a plurality of input pins to said X counter means and a first one of said polygon processors; and

output buffer means for coupling a last one of said polygon processors to a plurality of output pins.

17. The semiconductor chip of claim 16 wherein said input buffer includes multiplexing means for coupling said input pins to a larger number of input lines to said first triangle processor and said X counter means, and said output buffer means includes multiplexing means for coupling a plurality of output lines from said triangle processor to a smaller number of said output pins.

18. The semiconductor chip of claim 16 wherein said input buffer means further comprises means for delaying a first segment of multiplexed data until the arrival of a second set of multiplexed data, and said buffer means includes means for delaying a second segment of data until after a first segment of data is provided to said output pins.

19. The semiconductor chip of claim 16 further comprising means for delaying a plurality of data bits until a plurality of command bits are decoded

6. A pipeline as set forth in claim 6 wherein said polygons are triangles and further comprising:

a second pipeline of triangle processors coupled in parallel with said first-mentioned pipeline;

means for loading said pipelines with triangle descriptions;

means for alternating providing pixel processing instructions to alternate ones of said triangle processor pipelines; and

means, coupled to an output of each said triangle processor pipelines, for multiplexing signals from said outputs of said triangle processor pipelines.

7. The apparatus of claim 6 further comprising at least one first-in, first-out buffer coupled to an input of one of said pipelines, for temporarily storing triangle descriptions.

8. The polygon processor pipeline of claim 6 further comprising:

a second pipeline of polygon processors coupled in parallel with said first-mentioned pipeline;

means, in each polygon processor, for storing additional data representing a polygon; and

means for providing a first portion of additional data describing a single polygon to said first pipeline and a second portion of additional data describing said single polygon to said second pipeline.

20. A semiconductor chip comprising:

a plurality of polygon processors coupled in series, each polygon processor including

means for storing a representation of a polygon, said polygon representing a portion of a three-dimensional object,

means for comparing said representation to a pixel to determine whether said pixel is within said polygon,

means for comparing a Z position of said pixel to a Z position of said polygon, and

means for providing to an output a material property and Z position of said pixel in said polygon if said polygon has a Z position for said pixel in front of a Z position associated with said pixel;

counting means for providing an X position of a plurality of pixels to each of said polygon processors;

input buffer means for coupling a plurality of input pins to said X counter means and a first one of said polygon processors; and

output buffer means for coupling a last one of said polygon processors to a plurality of output pins.

21. The semiconductor chip of claim 20 further comprising:

a plurality of said polygon processors coupled in series to form a first pipeline;

a plurality of said polygon processors coupled in series to form a second pipeline of polygon processors coupled in parallel with said first pipeline;

means for loading one of said pipelines with polygon descriptions while the other of said pipelines is processing pixels;

means for alternating providing pixel processing instructions to alternate ones of said polygon processor pipelines; and

means, coupled to an output of each said polygon processor pipelines, for multiplexing signals from said outputs of said polygon processor pipelines.

22. An image processing system comprising:

a plurality of triangle processors, each triangle processor being a special purpose processor including;

X unit means for comparing a representation of a triangle to a pixel to determine whether said pixel is within said triangle;

Z unit means for comparing a Z position of said pixel to a Z position of said triangle;

material unit means for storing a material property of said triangle; and

control unit means for providing said material property to an output along with the Z position in said triangle if said triangle has a Z position for said pixel in front of a Z position associated with said pixel.

23. The triangle processor of claim 22 further comprising N-unit means for storing a normal vector for a plurality of positions of said triangle and for interpolating said normal vector in X, Y and Z directions for a plurality of pixel positions within said triangle.

24. The triangle processor of claim 23 wherein said control unit means further comprises:

means for loading a new triangle representation into said triangle processor; and

means for determining when all pixels contained within said triangle have been processed.

25. The triangle processor of claim 24 wherein;

said X unit means includes a plurality of registers for storing data indicating the boundaries of a triangle;

said Z unit means includes a first register for storing an initial value of Z and at least a second register for storing an incremental value of Z;

said N unit means includes NX, NY and NZ unit means for determining the X, Y and Z components of a normal vector, respectively, each of said NX, NY and NZ unit means containing at least one register for storing an initial value of NX, NY and NZ, respectively, and at least one additional register for storing an incremental value of NX, NY and NZ, respectively.