Span-based multi-sample z-buffer pixel processor

• US 6,404,425 B1
• Filed: 01/11/1999
• Issued: 06/11/2002
• Est. Priority Date: 01/11/1999
• Status: Expired due to Term

• Current Assignee: Rockwell Collins Simulation and Training Solutions, LLC
• Original Assignee: Evans & Sutherland Computer Corp. (Elevate Entertainment, Inc.)
• Inventors: Cosman, Michael
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US09/228,146
• Time in Patent Office: 1,247 Days
• Field of Search: 345/418, 345/419, 345/420, 345/424, 345/426, 345/427, 345/589, 345/590, 345/591
• US Class Current: 345/419
• CPC Class Codes: G06T 15/40 Hidden part removal

Abstract

A method for creating a span-based multisample Z-buffer pixel processor in a computer graphics system to thereby reduce a quantity of data that must be stored for each pixel in a frame buffer thereof. By taking advantage of areal coherence, the quantity of data that must be stored in each pixel is reduced. By employing merging, the method is also able to ensure than pixel storage requirements do not grow beyond a predetermined limit.

Claims

1. A method for creating a span-based multisample Z-buffer pixel processor in a computer graphics system to thereby reduce a quantity of data that must be stored for each pixel in a frame buffer thereof, said method comprising the steps of:

(1) assigning a span to be a group of at least four pixels disposed as a contiguous array, wherein each span is associated with at least one polygon fragment that is visible in at least one pixel of the span and stored in a data block of constant size;

(2) receiving polygon fragments for each span at the pixel processor;

(3) determining which polygon fragments are visible in each span; and

(4) storing the visible polygon fragments in each span back to the frame buffer for rendering into a video display.

2. The method as defined in claim 1 wherein the method further comprises the step of assigning the span to be a contiguous array of pixels which form a matrix having an equal number of rows and columns, to thereby take advantage of areal coherence.

3. The method as defined in claim 1 wherein the method further comprises the step of assigning the span to be a contiguous 2×

2 array of four pixels.

4. The method as defined in claim 1 wherein the method further comprises the step of processing polygon fragments that are opaque, transparent, and transitioning therebetween to thereby determine proper display characteristics for the pixels.

5. The method as defined in claim 1 wherein the method further comprises the step of receiving the polygon fragments in any order to thereby process all the polygon fragments regardless of an order in which they are sent to the pixel processor.

6. The method as defined in claim 1 wherein the method further comprises the step of comparing each new polygon fragment against all previously stored polygon fragments within a span to thereby determine which of the new polygon fragments and which of the previously stored polygon fragments are visible and which are hidden.

7. The method as defined in claim 6 wherein the method further comprises the step of erasing portions of the new polygon fragment that are hidden behind any part of the previously stored polygon fragments.

8. The method as defined in claim 7 wherein the method further comprises the step of erasing portions of the new polygon fragment that are hidden behind any part of the previously stored polygon fragments by clearing associated data bits in an occultation mask.

9. The method as defined in claim 8 wherein the method further comprises the step of erasing portions of the previously stored polygon fragments that are determined to be disposed behind the new polygon fragment.

10. The method as defined in claim 9 wherein the method further comprises the step of erasing portions of the previously stored polygon fragments that are determined to be disposed behind the new polygon fragment by deleting the portions of the previously stored polygon fragments when span data is written back to the frame buffer.

11. The method as defined in claim 7 wherein the method further comprises the step of writing no new data back to the frame buffer if the new polygon is completely hidden behind the previously stored polygon fragments.

12. The method as defined in claim 1 wherein the method further comprises the steps of:

(1) generating an amount of span data that is greater than available memory space within the frame buffer; and

(2) processing the span data so that said span data will fit within available memory space of the frame buffer.

13. The method as defined in claim 12 wherein the method further comprises the step of processing the span data so as to fit within the available memory of the frame buffer by merging at least one pair of polygon fragments until the span data is smaller than the available memory space of the frame buffer.

14. The method as defined in claim 13 wherein the method further comprises the steps of:

(1) sorting the polygon fragments in a sort list within the span to thereby at least facilitate proper resolution of transparency and to support efficient merging; and

(2) selecting merge candidates from interpenetrating polygon fragments in the sort list.

15. The method as defined in claim 13 wherein the method further comprises the steps of:

(1) sorting the polygon fragments within the span in a sort list to thereby at least facilitate proper resolution of transparency and to support efficient merging; and

(2) selecting merge candidates from the polygon fragments which are adjacent in the sort list.

16. The method as defined in claim 15 wherein the method further comprises the step of selecting the merge candidates from the polygon fragments in accordance with an order n selection criteria whereby adjacent polygons are compared, wherein the merged polygon fragments are then considered as a single polygon fragment which maintains a same position within the sort list.

17. The method as defined in claim 16 wherein the method further comprises the steps of:

(1) determining if the span data will fit within the available memory space of the frame buffer after merging the at least one pair of polygon fragments;

(2) selecting a next suitable pair of polygon fragments in accordance with the order n selection criteria whereby adjacent polygons within the sort list are compared if the span data will not fit within the available memory space;

(3) merging the next suitable pair of polygon fragments; and

(4) repeating steps (1) through (3) until the span data is smaller than the available memory space of the frame buffer.

18. The method as defined in claim 13 wherein the method further comprises the steps of:

(1) sorting the polygon fragments within the span in a sort list as determined by adjacency to thereby at least facilitate proper resolution of transparency and to support efficient merging; and

(2) selecting merge candidates from the polygon fragments which are adjacent in the sort list.

19. The method as defined in claim 13 wherein the method further comprises the step of dividing the sort list into two separate categories of polygon fragments, (1) a plurality of transparent polygons that are sorted among themselves, and (2) a plurality of opaque polygons that are sorted among themselves.

20. The method as defined in claim 19 wherein the method further comprises the steps of:

(1) sorting the polygons by placing a first polygon ahead of a second polygon on the sort list when the first polygon overlaps the second polygon; and

(2) if the first polygon does not overlap and is not overlapped by the second polygon, sorting the polygons relative to an average z depth.

21. The method as defined in claim 13 wherein the method further comprises the step of merging the at least one pair of polygon fragments relative to a weighted average of a depth thereof.

22. The method as defined in claim 21 wherein the method further comprises the step of defining the weighted average of the pair of polygon fragments as a total number of samples each polygon fragment wins in the span.

23. The method as defined in claim 22 wherein the method further comprises the step of defining a renormalization factor as a sum of the total number of samples assigned to the pair of polygon fragments.

24. The method as defined in claim 13 wherein the method further comprises the step of accounting for color, transmittance, and interpenetration of the pair of polygon fragments, one pixel at a time.

25. The method as defined in claim 24 wherein the method further comprises the steps of:

(1) generating a sample mask for each of the pair of polygon fragments to be merged;

(2) determining four regions within the pixel which are defined as a first polygon only, a second polygon only, the first polygon behind the second polygon, and the second polygon behind the first polygon;

(3) determining a total number of sample counts associated with each of the four regions; and

(4) determining the weighted average using the total number of sample counts.

26. The method as defined in claim 25 wherein the method further comprises the step of determining a merged transmittance value as:

$\mathrm{Tm}=\frac{\left[\mathrm{T1}*\mathrm{N1}+\mathrm{T2}*\mathrm{N2}+\mathrm{T1}*\mathrm{T2}*\left(\mathrm{N12}+\mathrm{N21}\right)\right]}{N<br><br>\text{\hspace{1em}<br><br>}<br><br>T}$

where N1 is a total number of samples for the first polygon, where N2 is a total number of samples for the second polygon, where N12 is a total number of samples where the first polygon is in front the second polygon, where N21 is a total number of samples where the second polygon is in front of the first polygon, where T1 is a transmittance value of the first polygon, where T2 is a transmittance value of the second polygon, and where NT=N1+N2+N12+N21.

27. The method as defined in claim 26 wherein the method further comprises the step of determining a merged red color value as:

$\mathrm{Rm}=\frac{\left[\mathrm{R1}*\mathrm{N1}+\mathrm{R2}*\mathrm{N2}+\mathrm{R1}*\mathrm{T2}*\mathrm{N21}+\mathrm{R2}*\mathrm{T1}*\mathrm{N12}\right]}{N<br><br>\text{\hspace{1em}<br><br>}<br><br>T}$

where R1 is a red component of the first polygon, and where R2 is a red component of the second polygon.

28. The method as defined in claim 26 wherein the method further comprises the step of determining a merged green color value as:

$\mathrm{Gm}=\frac{\left[\mathrm{G1}*\mathrm{N1}+\mathrm{G2}*\mathrm{N2}+\mathrm{G1}*\mathrm{T2}*\mathrm{N21}+\mathrm{G2}*\mathrm{T1}*\mathrm{N12}\right]}{N<br><br>\text{\hspace{1em}<br><br>}<br><br>T}$

where G1 is a green component of the first polygon, and where G2 is a green component of the second polygon.

29. The method as defined in claim 26 wherein the method further comprises the step of determining a merged blue color value as:

$\mathrm{Bm}=\frac{\left[\mathrm{B1}*\mathrm{N1}+\mathrm{B2}*\mathrm{N2}+\mathrm{B1}*\mathrm{T2}*\mathrm{N21}+\mathrm{B2}*\mathrm{T1}*\mathrm{N12}\right]}{N<br><br>\text{\hspace{1em}<br><br>}<br><br>T}$

where B1 is a blue component of the first polygon, and where B2 is a blue component of the second polygon.

30. The method as defined in claim 24 wherein the method further comprises the step of forcing a merge when a pair of transparent polygon fragments are determined to be interpenetrating to thereby eliminate aliased pixels at an edge of intersection of the pair of polygon fragments.

31. The method as defined in claim 1 wherein the method further comprises the step of defining a span record for storing polygon fragment data as including (1) a count of a total number of currently stored polygon fragments, and (2) a resolved display video for the pixels of the span.

32. The method as defined in claim 31 wherein the method further comprises the step of defining a data record for each polygon fragment which includes (1) a span center depth value, (2) two depth slope values, and (3) a plurality of flag bits which indicate which pixels in the span actually contain a portion of the polygon fragment.

33. The method as defined in claim 32 wherein the method further comprises the step of defining a shade data block which corresponds to a set flag of the plurality of flag bits, wherein the shade data block includes (1) a color value, (2) a transmittance value, and (3) a pixel sample mask.

34. The method as defined in claim 1 wherein the method further comprises the step of including within each of the polygon fragments data regarding a lateral screen extent and a depth behavior.

35. The method as defined in claim 34 wherein the method further comprises the step of including a multisample mask as a portion of the lateral screen extent.

36. The method as defined in claim 35 wherein the method further comprises the step of including a span center depth and depth slopes in a pixel line and element directions as at least a portion of the depth behavior.