Method for reducing the rendering load for high depth complexity scenes on a computer graphics display

• US 6,052,125 A
• Filed: 01/07/1998
• Issued: 04/18/2000
• Est. Priority Date: 01/07/1998
• Status: Expired due to Term

• Current Assignee: Rockwell Collins Simulation and Training Solutions, LLC (Rtx Corporation)
• Original Assignee: Evans & Sutherland Computer Corp. (Elevate Entertainment, Inc.)
• Inventors: Urry, Russell Joseph, Gardiner, Harold Dee
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): Sealey, Lance W.
• Application Number:
  US09/003,938
• Time in Patent Office: 832 Days
• Field of Search: 345/421-422, 345/426, 345/507, 345/509
• US Class Current: 345/421
• CPC Class Codes: G06T 15/40 Hidden part removal

Abstract

A method and apparatus for rendering a real-time synthetic environment on a computer display. A hidden surface removal technique is provided which combines an efficient pixel rendering architecture with a simplified modeling process. Specifically, the computer pixel graphics hardware processing load is balanced against a software geometric load to obtain optimum rendering performance by utilizing a "full" buffer in combination with adaptations of the z-Buffer and priority-list algorithms.

Claims

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

(1) performing a plurality of geometric sorting calculations on the database of modeled primitives in the frame buffer to thereby prepare the synthetic image for rendering;

(2) bypassing rendering operations for frame buffer regions which are completely covered;

(3) recording frame buffer regions in a fall buffer which are correctly covered;

(4) monitoring a length of time required to render the synthetic image to determine if a rendering load is excessive; and

(5) increasing a number of eometric sortings being calculated if the rendering load is excessive to thereby decrease the rendering load.

2. The method for increasing the rendering rate as defined in claim 1 wherein the method further comprises the step of increasing the total number of geometric sorting calculations if the pixel rendering load:

(1) exceeds a geometric sorting load which is a total time required to perform the geometric sorting calculations;

or

(2) exceeds a specified frame rate.

3. The method for increasing the rendering rate as defined in claim 2 wherein the method further comprises the step of balancing the rendering load and the geometric sorting load.

4. The method for increasing the rendering rate as defined in claim 2 wherein the method further comprises the step of minimizing a sum of the rendering load and the geometric sorting load.

5. The method for increasing the rendering rate as defined in claim 1 wherein the method further comprises the step of performing geometric sorting calculations only when the rendering load exceeds a geometric sorting load or frame time which is a total time required to perform the geometric sorting calculations.

6. The method for increasing the rendering rate as defined in claim 1 wherein the method further comprises the steps of:

(1) determining a relative size or closeness of the modeled primitives in the database;

(2) sorting the modeled primitives and selecting those primitives which meet a specified criteria defined as being equal to or greater than a selected size or closeness; and

(3) performing geometric sorting calculations on only the primitives selected in step (2).

7. The method for increasing a rendering rate as defined in claim 1 wherein the method further comprises the steps of:

(1) performing the plurality of geometric transformations in software; and

(2) simultaneously performing the rendering of the synthetic image in hardware.

8. The method for increasing the rendering rate as defined in claim 1 wherein the method further comprises the steps of:

(1) providing a reconfigurable memory structure or full buffer which contains a depth value associated with each pixel array in the frame buffer; and

(2) balancing the precision of the depth value against a total number of the pixel arrays.

9. The method for increasing the rendering rate as defined in claim 8 wherein the method further comprises the steps of decreasing a total number of bits allocated to the depth value when more pixel arrays are needed when the computer display resolution increases, and increasing a total number of bits allocated to the depth value when less pixel arrays are needed when the computer display resolution decreases, or when only a subset of the computer display needs to be covered by the full buffer.

10. The method for increasing the rendering rate as defined in claim 1 wherein the method further comprises the steps of:

(1) providing a reconfigurable memory structure or full buffer which contains a depth value associated with each pixel array in the frame buffer; and

(2) initializing the full buffer using the scanning hardware also used for rendering pixels.

11. The method for increasing the rendering rate as defined in claim 10 wherein the method further comprises the step of initializing the depth values of the full buffer to any arbitrary values.

12. The method for increasing the rendering rate as defined in claim 1 wherein the method further comprises the step of bypassing shading calculations for pixels which will not be rendered.

13. A system for increasing a rate of rendering a synthetic image on a computer display, wherein the synthetic image is generated from a database of modeled primitives, said system comprising:

a reconfigurable full buffer memory which allocates memory space between pixel arrays and associated depth bits;

means for reallocating the memory space between the pixel arrays and the depth bits to thereby obtain either greater screen resolution or greater precision in a depth comparison;

means for sorting the modeled primitives such that the modeled primitives can be ordered relative to distance from an observation point; and

means for rendering pixels on the computer display such that the modeled primitives which are not obscured by other modeled primitives are visible within the synthetic image.

14. The system as defined in claim 13 wherein the means for reallocating the memory space between the pixel arrays and the depth bits further comprises a means for reallocating the full buffer memory such that any rectangular portion of the frame buffer memory can be represented.

15. The system as defined in claim 13 wherein the means for reallocating the memory space between the pixel arrays and the depth bits further comprises a means for preventing different software applications from interfering with each other if the software applications both want to utilize pixels stored in a same pixel array.

16. The system as defined in claim 13 wherein the system further comprises a means for initializing the reconfigurable full buffer memory with any arbitrarily selected value.

17. The system as defined in claim 16 wherein the means for initializing the reconfigurable frame buffer memory further comprises pixel scanning hardware which is also utilized to render pixels on the display, thereby efficiently utilizing a computer resource.

18. The system as defined in claim 17 wherein the pixel scanning hardware is modified so as to be able to selectively input values into the full buffer or pixels into the frame buffer.

19. A method for increasing the rate of rendering three-dimensional synthetic images on a computer graphics display, wherein the synthetic images are generated by at least two applications which both want to utilize pixels stored in a same pixel array of a frame buffer, said method comprising the steps of:

(1) rendering the synthetic images in a full buffer by utilizing pixels stored in at least one pixel array; and

(2) defining a status of the at least one pixel array in the full buffer which is shared by the applications as not being full, to thereby prevent interference by either application with the other.

36. The method as in claim 19 further comprising the step of initializing portions of the full buffer to closest possible depth values so rendering is avoided when those portions of depth buffer are covered by two dimensional graphics.

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

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

(2) determining a closest pixel depth to each of the plurality of primitives being rendered, further comprising the steps of;

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

(ii) determining a closest depth value for the primitive within a given pixel array; and

(3) comparing the closest depth value of the primitives requiring processing against depth values in a fall buffer to thereby determine if the pixels in the given pixel array do not require further processing, wherein shading calculations are consequently terminated.

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

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

(1) determining if a closest point within the pixel array has a further depth value than a closest vertex; and

(2) utilizing the depth value of the closest array corner for the full buffer test if the closest array corner is further than the closest vertex, otherwise, utilizing the depth value of the closest vertex.

23. The method as defined in claim 22 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.

24. The method as defined in claim 23 wherein the method further comprises the step of making, a sign bit comparison to determine at which corner the depth value is to be calculated.

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

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

(2) bypassing the array when the depth value is further than the recorded depth in the full buffer, otherwise, processing the pixel array to determine a shading value for each pixel and executing z-Buffer testing.

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

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

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

(3) 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.

27. A method for recording values in a full buffer when accumulating a full status of a plurality of pixels processed in a pixel array, said method comprising:

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

(2) 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

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

28. The method as defined in claim 27 wherein the method further comprises the step of comparing the depth value of the primitives requiring processing against depth values in a full buffer to thereby determine if the pixels in a region do not require further processing, wherein shading calculations are consequently terminated.

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

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

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

(2) determining a furthest value for the primitive within a given pixel array.

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

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

(1) determining if a furthest point within the pixel array has a further depth value than a furthest vertex; and

(2) utilizing the depth value of the furthest array corner for the full buffer test if the furthest array corner is further than the further vertex, otherwise, utilizing the depth value of the further vertex.

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

34. The method as defined in claim 33 wherein the method further comprises the step of making sign bit comparison to determine at which corner the depth value is to be calculated.

35. The method as defined in claim 34 wherein the method further comprises the step of determining the furthest vertex to store in the full buffer when non-bypassed primitives fill an array region.