Hardware-assisted visibility-ordering algorithm

• US 6,801,215 B1
• Filed: 11/29/2001
• Issued: 10/05/2004
• Est. Priority Date: 11/29/2001
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Wei, Bin, Silva, Claudio T.
• Primary Examiner(s): Razavi, Michael
• Assistant Examiner(s): HAVAN, THU THAO
• Application Number:
  US09/995,683
• Time in Patent Office: 1,041 Days
• Field of Search: 345/629-641, 345/418-428, 345/581-606, 345/611, 345/614, 382/164-167, 382/174, 382/269
• US Class Current: 345/629
• CPC Class Codes: G06T 15/40 Hidden part removal

Abstract

A hardware assisted system and method for computing a visibility ordering of a set of primitives and rendering the set of primitives is described, comprising the steps of and means for locating primitives potentially in a layer and removing occluded primitives from the layer. The hardware assisted locating step further includes the steps of initializing hardware buffers, initializing a layer number, assigning the layer number to each primitive, extracting a subset of the primitives from the set of primitives assigned to the layer number, and storing the subset of primitives in a color buffer. The hardware assisted removing step further includes the steps of reading the color buffer to locate all primitives of the layer number, traversing a pixel array of the subset of primitives to obtain primitive ids and depth complexities, testing depth complexity for each primitive using a stencil buffer, removing those primitives from the layer number if the depth complexity greater than one, re-inserting the primitives with a depth complexity greater than one back into the set of primitives, rendering the primitives of the layer number, incrementing the layer number, determining if any primitives have been extracted from the set of primitives in the layer number, halting execution if no primitives have been removed from the layer number, and repeating all of the above steps.

Claims

1. A hardware assisted method for computing a visibility ordering of a set of primitives and rendering the set of primitives, comprising the steps of:

locating primitives potentially in a layer, wherein the step of locating comprises;

initializing hardware buffers,

initializing a layer number,

assigning said layer number to each primitive,

extracting a subset of said primitives from said set of primitives assigned to said layer number, and

storing said subset of primitives in a color buffer; and

removing occluded primitives from the layer, wherein the step of removing comprises the steps of;

reading said color buffer to locate all primitives of said layer number;

traversing a pixel array of said subset of primitives to obtain primitive ids and depth complexities;

testing depth complexity for each primitive using a stencil buffer;

removing those primitives from said layer number if said depth complexity is greater than one;

re-inserting said primitives with a depth complexity greater than one back into said set of primitives;

rendering said primitives of said layer number;

incrementing said layer number;

determining if any primitives have been extracted from said set of primitives in said layer number;

halting execution if no primitives have been removed from said layer number; and

repeating all of said above steps in said step of removing.

2. The method according to claim 1, wherein said method is a front-to-back algorithm.

3. The method according to claim 1, wherein said method is a back-to-front algorithm.

4. The method according to claim 1, wherein said hardware buffers are OpenGL hardware buffers.

5. The method according to claim 4, wherein said OpenGL hardware buffers include a color buffer, a stencil buffer and a z-buffer.

6. The method according to claim 5, further comprising the steps of:

clearing said color buffer;

disabling said stencil buffer; and

configuring and setting said z-buffer to far.

7. The method according to claim 5, after said re-inserting step, further comprising the steps of:

clearing and enabling said stencil buffer;

clearing said color buffer; and

clearing said z-buffer.

8. The method according to claim 1, further comprising the step of subdividing an image consisting of said set of primitives.

9. The method according to claim 1, wherein said set of primitives is acyclic.

10. A system for computing a visibility ordering of a set of primitives and rendering said set of primitives comprising:

a host processor having a host memory, the host memory including machine readable instructions which when executed by the processor, locate primitives potentially in a layer, wherein the step of locating comprises;

initializing hardware buffers, initializing a layer number, assigning said layer number to each primitive, extracting a subset of said primitives from said set of primitives assigned to said layer number, and

storing said subset of primitives in a color buffer; and

removing occluded primitives from the layer, wherein the step of removing comprises the steps of;

reading said color buffer to locate all primitives of said layer number;

traversing a pixel array of said subset of primitives to obtain primitive ids and depth complexities;

testing depth complexity for each primitive using a stencil buffer;

removing those primitives from said layer number if said depth complexity is A greater than one;

re-inserting said primitives with a depth complexity greater than one back into said set of primitives, rendering said primitives of said layer number;

incrementing said layer number;

determining if any primitives have been extracted from said set of primitives in said layer numberl;

halting execution if no primitives have been removed from said layer number; and

repeating all of said above steps;

a pixel storage operations module coupled to and interacting with said host memory;

a pixel transfer operations module coupled to and interacting with said pixel storage operations module;

a rasterization module for breaking primitives into fragments, said rasterization module coupled to and interacting with said pixel transfer operations module;

a texture memory module coupled to interacting with said pixel transfer operations module, said texture memory module further coupled to and interacting with said rasterization module;

a per-fragment operations module coupled to and interacting with said rasterization module; and

a framebuffer coupled to and interacting with said per-fragment module, said framebuffer further providing feedback to said pixel transfer operations module.

11. The system according to claim 10, wherein said per-fragment operations module further comprises:

a stencil buffer;

a z-buffer; and

a color buffer.

12. The system according to claim 10, wherein said system supports a front-to-back algorithm.

13. The system according to claim 10, wherein said system supports a front-to-back algorithm.

14. The system according to claim 10, wherein said set of primitives is acyclic.

15. A system for computing a visibility ordering of a set of primitives and rendering said set of primitives comprising:

a first controller for locating primitives potentially in a layer, wherein said first controller performs functions comprising the steps of;

initializing hardware buffers;

initializing a layer number;

assigning said layer number to each primitive;

extracting a subset of said primitives from said set of primitives assigned to said layer number; and

storing said subset of primitives in a color buffer in computer readable memory; and

a second controller for removing occluded primitives from the layer, wherein said second controller performs functions comprising the steps of;

reading said color buffer to locate all primitives of said layer number;

traversing a pixel array of said subset of primitives to obtain primitive ids and depth complexities;

testing depth complexity for each primitive using a stencil buffer;

removing those primitives from said layer number if said depth complexity greater than one;

re-inserting said primitives with a depth complexity greater than one back into said set of primitives;

rendering said primitives of said layer number;

incrementing said layer number;

determining if any primitives have been extracted from said set of primitives in said layer number;

halting execution if no primitives have been removed from said layer number; and

repeating all of said above steps for removing occluded primitives from the layer.

16. The system according to claim 15, wherein said system supports a front-to-back algorithm.

17. The system according to claim 15, wherein said system supports a back-to-front algorithm.