3-D graphics display system using triangle processor pipeline

• US 4,885,703 A
• Filed: 11/04/1987
• Issued: 12/05/1989
• Est. Priority Date: 11/04/1987
• Status: Expired due to Fees

• Current Assignee: Applicon, Inc. (Perspecta, Inc.)
• Original Assignee: Schlumberger Systems Incorporated
• Inventors: Deering, Michael F.
• Primary Examiner(s): Pellinen, A. D.
• Assistant Examiner(s): SALATA, ANTHONY J
• Application Number:
  US07/117,111
• Time in Patent Office: 762 Days
• Field of Search: 364/518, 364/521, 364/522, 358/104, 340/721, 340/732, 340/727, 340/747, 340/750, 340/729
• US Class Current: 345/422
• CPC Class Codes: G06T 15/83 Phong shading

Abstract

A graphic processing system for representing three-dimensional objects on a monitor which uses a pipeline of polygon processors coupled in series. The three-dimensional objects are converted into a group of two-dimensional polygons. These polygons are then sorted to put them in scan line order, with each polygon having its position determined by the first scan line on which it appears. Before each scan line is processed, the descriptions of the polygons beginning on that scan line are sent into a pipeline of polygon processors. Each polygon processor accepts one of the polygon descriptions and stores it for comparison to the pixels of that scan line which are subsequently sent along the polygon processor pipeline. For each new scan line, polygons which are no longer covered are eliminated and new polygons are entered into the pipe. After each scan line is processed, the pixels can be sent directly to the CRT or can be stored in a frame buffer for later accessing. Two polygon processor pipelines can be arranged in parallel to process two halves of a display screen, with one pipeline being loaded while the other is processing. A frame buffer and frame buffer controller are provided for overflow conditions where two passes through the polygon pipeline are needed. A unique clipping algorithm forms a guardband space around a viewing space and clips only polygons intersecting both shells. Extra areas processed are simply not displayed.

Claims

1. A graphics processing system, capable of being coupled to a monitor, for representing three-dimensional images on the monitor, comprising:

means for converting a representation of three-dimensional objects into a group of two-dimensional polygons;

means for ordering said polygons by scan lines on said monitor on which said polygons will first appear;

a pipeline of polygon processors coupled in series to receive said polygons from said means for ordering at a first end of said series, each of said polygon processors including

means for storing a representation of a single, separate one of said polygons,

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

means for comparing any Z position tagged to said pixel to the Z position of said polygon, at the x-y location of said polygon corresponding to the x-y location of said pixel, if said pixel is within said polygon, and

means for tagging to said pixel a material property and Z position of said pixel in said polygon to a next polygon processor in said series if said polygon has a Z position in front of said Z position tagged to said pixel; and

means coupled to a second end of said series, for displaying said pixels on said monitor.

2. The system of claim 1 wherein said polygons are triangles.

3. The system of claim 1 wherein

said means for ordering includes means for transmitting data representing each polygon which first appears on a scan line to said polygon processor pipeline prior to a processing of said scan line by said polygon processor pipeline and

each polygon processor includes means for accepting a new representation of a polygon and discarding an old representation of a polygon after a last scan line covered by said old polygon is processed.

4. The system of claim 3 further comprising means for counting a number of available polygon processors without a stored representation of a polygon and for producing a count which represents the number of new polygon representations which can be loaded into said pipeline.

5. The system of claim 4 further comprising:

means for halting a flow of polygon representations to said polygon processor pipeline when said number of available processors reaches a predetermined minimum number;

means for storing overflow polygon representations prior to said polygon processor pipeline;

frame buffer means for storing a first group of pixel representations from said polygon pipeline;

means for providing said overflow polygon representations to said polygon pipeline in a second frame pass; and

means for comparing Z positions of pixel representations stored in said frame buffer to pixel representations from said second frame pass through said polygon pipeline.

6. The system of claim 4 wherein said means for counting comprises:

a counter;

means for incrementing said counter by a number of new polygon representations transmitted to said series of polygon processors;

means for storing a number of polygons expiring on each scan line; and

means for decrementing said counter by said number of polygons expiring on each scan line.

7. The system of claim 1 further comprising:

a second series of polgon processors coupled in parallel with said first mentioned series of polygon processors; and

means for loading one of said series of polygon processors with said representations of polygons while the other one of said series of polygon processors is processing pixels.

8. The system of claim 7 wherein said means for loading loads representations for polygons beginning in a first portion of said monitor in said first series of polygon processors and loads representations for polygons beginning in a second portion of said monitor into said second series of polygon processors.

9. The system of claim 1 wherein said means for converting includes means for clipping ones of said two-dimensional polygons extending from inside to outside a predetermined viewing space defined by a plurality of clipping planes, said clipping means comprising:

means for comparing each of said polygons to said clipping planes to determine whether each said polygon intersects one of said clipping planes, is totally inside said viewing space, or is totally outside said viewing space; and

means for transmitting polygons totally inside said viewing space without clipping to said means for ordering and discarding polygons totally outside said viewing space without clipping.

10. The system of claim 9 wherein said clipping means further comprises:

means for determining a guardband space, defined by a plurality of guardband planes, at least partially enclosing said viewing space such that a distance between each of said guardband planes and one of said viewing planes is greater than a predetermined estimated average polygon'"'"'s maximum dimension;

means for comparing ones of said polygons intersecting one of said clipping planes to said guardband planes;

means for transmitting without clipping to said means for ordering ones of said polygons totally inside said guardband space.

11. The system of claim 9 wherein said clipping means further comprises:

means for determining which of said clipping planes are intersected by said polygons; and

means for clipping ones of said polygons intersecting only one clipping plane with only said one clipping plane.

12. The system of claim 1 further comprising means for classifying triangles from an input of the coordinates of the vertices of a triangle, said means for classifying comprising:

calculation logic means for calculating a plurality of parameters of said triangle from said input of said coordinates; and

look-up table means, coupled to an output of said calculation logic means for determining a triangle classification for every combination of said parameters, said look-up table means storing said triangle classification with addresses corresponding to combinations of said parameters.

13. A graphics processing system for representing three-dimensional images on a monitor, comprising:

means for converting a representation of three-dimensional objects into a group of two-dimensional polygons;

means for ordering said polygons by scan lines on said monitor on which said polygons will first appear;

a pipeline of polygon processors coupled in series to receive said polygons from said means for ordering at a first end of said series, each of said polygon processors including

means for storing a representation of one of said polygons,

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

means for comparing any Z position tagged to said pixel to the Z position of said polygon, at the x-y location of said polygon corresponding to the x-y location of said pixel, if said pixel is within said polygon, and

means for tagging to said pixel a material property and Z position of said pixel in said polygon to a next polygon processor in said series if said polygon has a Z position in front of said Z position tagged to said pixel;

said means for ordering including means for transmitting data representing each polygon which first appears on a scan line to said polygon processor pipeline prior to a processing of said scan line by said polygon processor pipeline, each polygon processor including means for accepting a new representation of a polygon and discarding an old representation of a polygon after a last scan line covered by said old polygon is processed;

means for counting a number of available polygon processor without a stored representation of a polygon and for producing a count which represents the number of new polygon representations which can be loaded into said pipeline;

means for halting a flow of polygon representations to said polygon processor pipeline when said number of available processors reaches a predetermined minimum number;

means for storing overflow polygon representations prior to said polygon processor pipeline;

frame buffer means for storing a first group of pixel representations from said polygon pipeline;

means for providing said overflow polygon representations to said polygon pipeline in a second frame pass;

means for comparing Z positions of pixel representations stored in said frame buffer to pixel representations from said second frame pass through said polygon pipeline; and

means coupled to a second end of said pipeline, for displaying said pixels on said monitor.

14. A graphics processing system for representing three-dimensional images on a monitor, comprising:

means for converting a representation of three-dimensional objects in to a group of two-dimensional polygons;

means for ordering said polygons by scan lines on said monitor on which said polygons will first appear;

a pipeline of polygon processors coupled in series to receive said polygons from said means for ordering at a first end of said series, each of said polygon processors including

means for storing a representation of one of said polygons,

means for comprising said representation of one of said polygons to a pixel to determine whether said pixel is within said polygon,

means for comparing any Z position tagged to said pixel to the Z position of said polygon, at the x-y location of said polygon corresponding to the x-y location of said pixel, if said pixel is within said polygon, and

means for tagging to said pixel a material property and Z position of said pixel in said polygon to a next polygon processor in said series if said polygon has a Z position in front of said Z position tagged to said pixel;

said means for ordering including means for transmitting data representing each polygon which first appears on a scan line to said polygon processor pipeline prior to a processing of said scan line by said polygon processor pipeline, each polygon processor including means for accepting a new representation of a polygon and discarding an old representation of a polygon after a last scan line covered by said old polygon is processed;

means for counting a number of available polygon processors without a stored representation of a polygon, said means for counting including

a counter,

means for incrementing said counter by a number of new polygon representations transmitted to said pipeline of polygon processors;

means for storing a number of polygons expiring on each scan line;

means for decrementing said counter by said number of polygons expiring on each scan line; and

means coupled to a second end of said pipeline, for displaying said pixels on said monitor.