System and method for reducing the rendering load for high depth complexity scenes on a computer graphics display

• US 6,362,818 B1
• Filed: 02/24/1999
• Issued: 03/26/2002
• Est. Priority Date: 01/07/1998
• Status: Expired due to Term

• Current Assignee: Rockwell Collins Simulation and Training Solutions, LLC
• Original Assignee: Evans & Sutherland Computer Corp. (Elevate Entertainment, Inc.)
• Inventors: Urry, Russell J., Gardiner, Harold D.
• Primary Examiner(s): Vo, Cliff N.
• Application Number:
  US09/256,818
• Time in Patent Office: 1,126 Days
• Field of Search: 345/418, 345/421, 345/422, 345/426, 345/424, 345/425, 345/427
• US Class Current: 345/421
• CPC Class Codes: G06T 15/40 Hidden part removal

Abstract

This invention relates generally to the field of computer graphics display, and more particularly to reducing the amount of time needed to render complex virtual scenes on a computer graphics display. This invention combines the advantages of the prior art methods of list priority and depth buffering (e.g. Z-buffering) with new simplified and enhanced full buffer processes. In one embodiment, a simplified full buffer arrangement enables the elimination of rendering primitives prior to pixel shading for regions of the screen which have previously been covered by closer primitives. Another embodiment provides for an enhanced full buffer that combines the coverage of a previously rendered primitive in a partial buffer and associates it with a current primitive to cover pixel arrays. This enhanced full buffer technique enables the use of higher order model primitives such as strips, fans and meshes, to increase the effectiveness of the full buffer by allowing more than one primitive to combine to fill a scanned pixel region on the screen.

Claims

1. A computer graphics rendering system for efficiently rendering three-dimensional scenes of high depth complexity with a graphics display unit, comprising:

(a) means for bypassing rendering operations for frame buffer regions in which the pixels are completely covered by primitives,

(b) means for accumulating coverage of frame buffer regions by both individual primitives and groups of primitives,

(c) a full buffer having memory locations arranged for recording frame buffer regions which are completely covered, and

(d) a partial buffer coupled to the full buffer to enable multiple primitives to combine to fill frame buffer regions.

2. The graphics rendering system of claim 1 and further comprising means for copying pixel array coverage information to the partial buffer for later use by adjacent primitives.

3. The graphics rendering system of claim 1 and further comprising means for determining whether the current primitive in the sequence is connected to the previous primitive;

means for determining when the combined coverage of primitives has filled the frame buffer region, and means for recording that coverage in the full buffer.

4. The graphics rendering system as in claim 2 where the partial buffer further comprises:

(a) a plurality of pixel count values in the partial buffer wherein each corresponds to a pixel array in the partial buffer to thereby store the number of pixels covered in the pixel array by the previously scanned primitive for the pixel array,

(b) a plurality of opacity flags in the partial buffer wherein each opacity flag corresponds to a pixel array in the partial buffer which indicates if all the pixels counted by the current pixel count accumulator were opaque; and

(c) a plurality of farthest depth values in the partial buffer wherein each depth storage location corresponds to a pixel array in the partial buffer to thereby store the farthest depth value of the most recently processed primitive within the pixel array.

5. The graphics rendering system as in claim 4 where the means for copying further includes a means for copying the accumulated values from the partial buffer further comprises a means for copying the pixel count value from the partial buffer to the combined pixel count accumulator, and the opacity flags from the partial buffer to the combined opacity flag accumulator, and the farthest depth value to the combined farthest depth value.

6. The graphics rendering system as in claim 5 where the means for determining when a next connected primitive has combined with results in the partial buffer to fill pixel arrays further comprises:

(a) a plurality of valid flag pairs in the partial buffer wherein each pair of valid flags is a current and previous flag and corresponds to a pixel array in the partial buffer such that partial buffer appears double buffered even though there is only one memory location per pixel array which stores pixel values,

(b) a means for determining whether the data in the partial buffer is valid such that the next step of combining the partial buffer coverage information is skipped if the partial buffer data is not valid.

7. The graphics rendering system as in claim 6 further comprising a plurality of coincident full flags in the fill buffer wherein each coincident full flag corresponds to a pixel array in the full buffer to thereby indicate that a pixel array has been filled by one or more coincident primitives and the pixel array calculations to determine pixel values may be skipped if other coincident primitives within the same coincident group are encountered.

8. The graphics rendering system as in claim 5 further comprising a combined pixel count accumulator coupled to the partial buffer and the current primitive, to thereby determine the total number of pixels in the pixel array filled by both the previous connected primitive recorded in the partial buffer and the current connected primitive.

9. The graphics rendering system as in claim 5 further comprising a combined opacity flag accumulator coupled to the partial buffer and the current primitive, wherein each opacity flag corresponds to a partial buffer and a full buffer pixel array and stores a true value if all pixel values in the corresponding pixel arrays are opaque and a false value if any pixel value is transparent.

10. A computer graphics rendering process for efficiently rendering three-dimensional scenes of high depth complexity with a graphics display unit, comprising:

(a) bypassing rendering operations for frame buffer regions which are completely covered,

(b) accumulating coverage of frame buffer regions by both individual primitives and groups of primitives,

(c) recording frame buffer regions which are completely covered using a full buffer having memory locations, and

(d) combining multiple primitives to fill frame buffer regions using a partial buffer coupled to the full buffer.

11. The method for rendering graphics as in claim 10 and further comprising the steps of skipping the next pixel array in the sequence if the pixel array in the full buffer is already filled with rendered pixel values;

and analyzing whether the next pixel array is a new pixel array wherein the pixel array has not been filled with any pixel values.

12. The method for rendering graphics as in claim 10 and further comprising the step of analyzing whether the primitive currently being scanned is connected to the primitive which was previously scanned.

13. The method for rendering graphics as in claim 12 where the step of analyzing whether the primitive currently being scanned is connected to the primitive which was previously scanned further comprises the step of marking the pixel array data as valid.

14. The method for rendering graphics as in claim 12 where the step of transferring the current accumulator data to the partial buffer further comprises:

transferring the pixel count value, opacity flag, and farthest depth value for a current primitive to a corresponding pixel count opacity flag, and farthest depth value in the partial buffer.

15. The method for rendering graphics as in claim 14 where the step of retrieving the information stored in the partial buffer further comprises the next step of selecting between the currently scanned primitive depth and partial buffers primitive depth value.

16. The method for rendering graphics as in claim 12 where the step of combining both the current primitive data and the partial buffer if their combined pixels cover a whole pixel array comprises the next steps of:

(a) incrementing to the combined pixel count accumulator and the current pixel count accumulator;

(b) marking combined opacity flag and the current opacity flag to thereby store a value which shows whether all the pixels in the pixel array are opaque; and

(c) analyzing the combined pixel accumulator and combined opaque flags to determine if the pixel array is completely filled with pixel values.

17. The method for rendering graphics as in claim 16 which further comprises the step of storing the farthest depth in the full buffer if the pixel array is completely filled.

18. The method for rendering graphics as in claim 13 where the steps of retrieving the information and combining the partial buffer and the current primitive are skipped if the primitives are not connected and further comprising the steps of:

(a) overwriting the combined pixel count accumulator with data from the current pixel count accumulator;

(b) overwriting the combined opacity flag with the current opacity flag to thereby store a value which shows whether all the pixels in the pixel array are opaque relative to only the current primitive; and

(c) overwriting the combined farthest depth value with the current primitive'"'"'s farthest depth.

19. A method for rendering graphics as in claim 18 where the next steps comprise:

(a) testing to decide if the pixel array is filled;

(b) storing the farthest depth of the currently scanned primitive in the full buffer if the pixel array is filled;

(c) selecting a new primitive to be scanned; and

(d) repeating all the above steps until all the primitives have been scanned for all the pixel arrays.

20. A method for rendering graphics as in claim 12 wherein it is determined that the current primitive and next primitive to be scanned are not connected, further comprising the steps of:

(a) skipping over the partial buffer operations;

(b) resetting the pixel count accumulator;

(c) selecting the current primitives furthest depth;

(d) accumulating the pixel count and the opacity flag;

(e) testing to decide if the pixel array is filled;

(f) storing the farthest depth of the primitive in the full buffer if the pixel array is filled;

(g) selecting a new primitive to be scanned by the graphics systems and repeating the steps above.

21. A method for rendering graphics as in claim 12 wherein it is determined that the current primitive and next primitive to be scanned are connected, further comprising the steps of:

(a) determining that the partial buffer data is valid;

(b) retrieving the sub-pixel count, opacity flag and farthest depth from the partial buffer;

(c) selecting between current and partial farthest depth;

(d) accumulating the pixel count and the opacity flag;

(e) testing to decide if the pixel array is filled;

(f) storing the farthest depth of the primitive in the full buffer if the pixel array is filled;

(g) selecting a new primitive to be scanned by the graphics systems and repeating the steps above.

22. A method for increasing a rate of rendering a synthetic image on a computer graphics display, wherein the synthetic image is generated from a database of a plurality of primitives, said method comprising the steps of:

(a) determining which pixels require processing for each of the plurality of primitives;

(b) comparing the depth values of the primitives requiring processing against depth values in a full buffer to thereby determine whether the pixels in a region require further processing; and

(c) skipping shading value calculations for pixels not requiring further processing.

23. The method of claim 22 wherein the method further comprises the step of determining a closest pixel depth to each of the plurality of primitives being rendered.

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

(a) determining a closest vertex relative to an observer of each of the primitives being rendered; and

(b) determining a closest value for the primitive within a given pixel array.

25. The method as defined in claim 24 wherein the step of determining a closest vertex relative to the observer of each of the primitives being rendered further comprises the step of comparing depth values at each vertex of the primitive to thereby locate a closest depth value.

26. The method as defined in claim 24 wherein the step of determining a closest value for the primitive within a given pixel array further comprises the steps of:

(a) determining whether a closest point within the pixel array has a further depth value than the closest vertex of a primitive; and

(b) utilizing the depth value of the closest array corner for the full buffer test if the closest array comer is further than the closest vertex of the primitive; and

(c) utilizing the depth value of the closest vertex of the primitive if the closest array comer is not further than the closest vertex of the primitive.

27. The method as defined in claim 26 wherein the step of determining whether the closest value for the primitive within a given pixel array has a further depth value than a closest vertex further comprises the step of utilizing a depth slope comparison.

28. The method as defined in claim 27 wherein the method further comprises the step of making a sign bit comparison to determine at which comer the depth value is to be calculated.

29. The method as defined in claim 28 wherein the method further comprises the steps of:

(a) comparing the closest depth value with a depth value already stored in the full buffer for each pixel array requiring processing for the primitive;

(b) bypassing the array if the depth value is further than the recorded depth in the full buffer; and

(c) processing the pixel array to determine a shading value for each pixel and executing z-buffer testing, if the depth value is closer than the recorded depth in the full buffer.

30. The method as defined in claim 29 wherein the method further comprises the steps of:

(a) monitoring a rendering process to determine whether the primitives which are being recorded in the frame buffer completely fill any pixel arrays of the full buffer being processed;

(b) loading a maximum depth value of a primitive into the full buffer if the pixel array is completely filled; and

(c) overwriting an old full buffer depth value if the primitive completely fills the array, and the maximum depth value is closer than the depth value already in the buffer.

31. A method for increasing a rate of rendering a synthetic image on a computer graphics display, wherein the synthetic image is generated from a database of a plurality of primitives, said method comprising the steps of:

(a) determining which pixels of the plurality of pixels require processing for each of the plurality of primitives;

(b) serially accumulating a full status of a plurality of pixels stored in at least one pixel array as the plurality of pixels are processed; and

(c) marking the pixel array as full if the plurality of pixels in the pixel array are determined to be completely covered.

32. The method as defined in claim 31 wherein the method further comprises the step of comparing the depth value of the primitives requiring processing against the depth values in a full buffer to thereby determine whether the pixels in a region require further processing and skipping shading of the pixels if the depth value of the primitives is greater than the depth values in the full buffer.

33. The method as defined in claim 31 wherein the method further comprises the step of determining a furthest pixel depth relative to each of the plurality of primitives being rendered.

34. The method as defined in claim 33 wherein the method further comprises the step of determining a furthest value for the primitive within a given pixel array.

35. The method as defined in claim 34 wherein the step of determining a furthest value for the primitive within a given pixel array further comprises utilizing the depth value of the furthest array comer for the full buffer test.

36. The method as defined in claim 34 wherein the step of determining the furthest value for the primitive within a given pixel array further comprises the step of utilizing a depth slope comparison.

37. The method as defined in claim 36 wherein the method further comprises the step of making a sign bit comparison to determine at which comer the depth value is to be calculated.

38. The method as defined in claim 37 wherein the method further comprises the step of determining the furthest depth value to store in the full buffer when primitives which are not bypassed fill an array region in the full buffer.

39. A system for increasing a rate of rendering a synthetic image on a computer graphics display, where the synthetic image is generated from a database of a plurality of primitives, comprising:

(a) means for determining which pixels require processing for each of the plurality of primitives;

(b) means for comparing the depth values of the primitives requiring processing against depth values in a full buffer to thereby determine whether the pixels in a region require further processing; and

(c) means for skipping shading value calculations for pixels not requiring further processing.

40. The system of claim 39 and further comprising means for determining a closest pixel depth to each of the plurality of primitives being rendered.

41. The method as defined in claim 40 and further comprising (a) means for determining a closest vertex relative to an observer of each of the primitives being rendered;

and (b) means for determining a closest value for the primitive within a given pixel array.