Method and apparatus for organizing object geometry for spatial and memory coherency and optimal rendering
| Title: | Method and apparatus for organizing object geometry for spatial and memory coherency and optimal rendering |
|---|---|
| Patent Number: | 8,188,999 |
| Publication Date: | May 29, 2012 |
| Appl. No: | 12/140770 |
| Application Filed: | June 17, 2008 |
| Abstract: | Methods and computing devices enable the generation of contiguous triangle patches for use in generating triangle strips for processing in a computer graphics engine. A seed triangle is selected and a patch of contiguous triangles is formed by incrementally adding adjacent triangles to the patch at equal steps from the seed triangle until a limit is reached or no more triangles can be added to the patch. Triangles whose vertices are already included in the patch are also added to the patch. If no more triangles can be added to the patch before the vertex limit is reached, a new seed triangle may be selected and another patch generated until the vertex limit is reached. Forming patches of contiguous triangles before generating triangle strips improves memory utilization can speed the processing of computer graphic objects. |
| Inventors: | Dorbie, Angus MacDonald (San Diego, CA, US) |
| Assignees: | QUALCOMM Incorporated (San Diego, CA, US) |
| Claim: | 1. A method for generating a patch of contiguous triangles for processing in a graphics processing engine, comprising: a processor selecting a first seed triangle for the patch; the processor recursively adding contiguous triangles to a first patch at equal path lengths from the first seed triangle until a count of triangle vertices in the first patch reaches a limit; the processor including in the patch any triangles whose vertices are included in the patch; and the processor selecting a second seed triangle and recursively adding contiguous triangles to a second patch at equal path lengths from the second seed triangle until a count of triangle vertices in the first and second patches reaches the limit if no more contiguous triangles can be added to the first patch and the count of triangle vertices in the first patch is less than the limit. |
| Claim: | 2. The method of claim 1 , further comprising the processor forming a triangle strip within the first patch that is suitable for processing in a graphics pipeline. |
| Claim: | 3. The method of claim 1 , wherein the step of recursively adding contiguous triangles to a first patch comprises: the processor selecting a triangle from a list triangles added to the patch in a previous dilation step; the processor adding any triangle adjacent to the selected triangle that is not already included in the patch; and the processor storing an identifier of the added triangle in a list of triangles added in the current dilation step. |
| Claim: | 4. The method of claim 1 , wherein the step of recursively adding contiguous triangles to a first patch comprises: the processor following each traversal path through adjacent triangles from the first seed triangle to a traversal length; the processor adding a triangle at the end of each traversal path to the patch if it is not already included in the path; and the processor incrementing the traversal length once all traversal paths through adjacent triangles from the first seed triangle have been evaluated. |
| Claim: | 5. The method of claim 1 , further comprising the processor indexing triangle vertices as each triangle is added to the patch. |
| Claim: | 6. A computer, comprising: a processor; and a memory coupled to the processor, wherein the processor is configured with software instructions to perform steps comprising: selecting a first seed triangle for forming a first patch of contiguous triangles; recursively adding contiguous triangles to a first patch at equal path lengths from the first seed triangle until a count of triangle vertices in the first patch reaches a limit; including in the patch any triangles whose vertices are included in the patch; and selecting a second seed triangle and recursively adding contiguous triangles to a second patch at equal path lengths from the second seed triangle until a count of triangle vertices in the first and second patches reaches the limit if no more contiguous triangles can be added to the first patch and the count of triangle vertices in the first patch is less than the limit. |
| Claim: | 7. The computer of claim 6 , wherein the processor is configured with software instructions to perform steps further comprising forming a triangle strip within the first patch that is suitable for processing in a graphics pipeline. |
| Claim: | 8. The computer of claim 6 , wherein the processor is configured with software instructions to perform steps further comprising: selecting a triangle from a list triangles added to the patch in a previous dilation step; adding any triangle adjacent to the selected triangle that is not already included in the patch; and storing an identifier of the added triangle in a list of triangles added in the current dilation step. |
| Claim: | 9. The computer of claim 6 , wherein the processor is configured with software instructions to perform steps further comprising: following each traversal path through adjacent triangles from the first seed triangle to a traversal length; adding a triangle at the end of each traversal path to the patch if it is not already included in the path; and incrementing the traversal length once all traversal paths through adjacent triangles from the first seed triangle have been evaluated. |
| Claim: | 10. The computer of claim 6 , wherein the processor is configured with software instructions to perform steps further comprising indexing triangle vertices as each triangle is added to the patch. |
| Claim: | 11. A computer, comprising: means for selecting a first seed triangle for forming a first patch of contiguous triangles; means for recursively adding contiguous triangles to a first patch at equal path lengths from the first seed triangle until a count of triangle vertices in the first patch reaches a limit; and means for including in the patch any triangles whose vertices are included in the patch; and means for selecting a second seed triangle and recursively adding contiguous triangles to a second patch at equal path lengths from the second seed triangle until a count of triangle vertices in the first and second patches reaches the limit if no more contiguous triangles can be added to the first patch and the count of triangle vertices in the first patch is less than the limit. |
| Claim: | 12. The computer of claim 11 , further comprising means for forming a triangle strip within the first patch that is suitable for processing in a graphics pipeline. |
| Claim: | 13. The computer of claim 11 , further comprising: means for selecting a triangle from a list triangles added to the patch in a previous dilation step; means for adding any triangle adjacent to the selected triangle that is not already included in the patch; and means for storing an identifier of the added triangle in a list of triangles added in the current dilation step. |
| Claim: | 14. The computer of claim 11 , further comprising: means for following each traversal path through adjacent triangles from the first seed triangle to a traversal length; means for adding a triangle at the end of each traversal path to the patch if it is not already included in the path; and means for incrementing the traversal length once all traversal paths through adjacent triangles from the first seed triangle have been evaluated. |
| Claim: | 15. The computer of claim 11 , further comprising means for indexing triangle vertices as each triangle is added to the patch. |
| Claim: | 16. A non-transitory storage medium having stored thereon processor-executable software instructions configured to cause a processor of a computer to perform steps comprising: selecting a first seed triangle for forming a first patch of contiguous triangles; recursively adding contiguous triangles to a first patch at equal path lengths from the first seed triangle until a count of triangle vertices in the first patch reaches a limit; including in the patch any triangles whose vertices are included in the patch; and selecting a second seed triangle and recursively adding contiguous triangles to a second patch at equal path lengths from the second seed triangle until a count of triangle vertices in the first and second patches reaches the limit if no more contiguous triangles can be added to the first patch and the count of triangle vertices in the first patch is less than the limit. |
| Claim: | 17. The non-transitory storage medium of claim 16 , wherein the stored processor-executable software instructions are configured to cause a processor of a computer to perform further steps comprising forming a triangle strip within the first patch that is suitable for processing in a graphics pipeline. |
| Claim: | 18. The non-transitory storage medium of claim 16 , wherein the stored processor-executable software instructions are configured to cause a processor of a computer to perform further steps comprising: selecting a triangle from a list triangles added to the patch in a previous dilation step; adding any triangle adjacent to the selected triangle that is not already included in the patch; and storing an identifier of the added triangle in a list of triangles added in the current dilation step. |
| Claim: | 19. The non-transitory storage medium of claim 16 , wherein the stored processor-executable software instructions are configured to cause a processor of a computer to perform further steps comprising: following each traversal path through adjacent triangles from the first seed triangle to a traversal length; adding a triangle at the end of each traversal path to the patch if it is not already included in the path; and incrementing the traversal length once all traversal paths through adjacent triangles from the first seed triangle have been evaluated. |
| Claim: | 20. The non-transitory storage medium of claim 16 , wherein the stored processor-executable software instructions are configured to cause a processor of a computer to perform further steps comprising indexing triangle vertices as each triangle is added to the patch. |
| Current U.S. Class: | 345/420 |
| Patent References Cited: | 5553206 September 1996 Meshkat 5896139 April 1999 Strauss 6108006 August 2000 Hoppe 6256038 July 2001 Krishnamurthy 6429865 August 2002 Marshall 6469701 October 2002 Gumhold 6476816 November 2002 Deming et al. 6518963 February 2003 Waupotitsch et al. 7190362 March 2007 Baker et al. 7245299 July 2007 Sfarti 7436405 October 2008 Losasso Petterson et al. |
| Other References: | Xiang, X. et al., Fast and Effective Stripification of Polygonal Surface Models, 1999 Symposium on Interactive 3D Graphics Atlanta GA USA, ACM 1999 (month unknown). cited by examiner El-Sana, J. et al., Efficiently Computing and Updating Triangle Strips for Real-Time Rendering, Computer-Aided Design, vol. 32, Issue 13 pp. 753-772; Elsevier, Nov. 2000. cited by examiner |
| Assistant Examiner: | Perromat, Carlos |
| Primary Examiner: | Tung, Kee M |
| Attorney, Agent or Firm: | Hagler, James T. |
| Accession Number: | edspgr.08188999 |
| Database: | USPTO Patent Grants |
| Language: | English |
|---|