Bibliographic Details
| Title: |
Method and apparatus for optimizing triangles into triangle strips according to a variety of criteria |
| Patent Number: |
8,237,709 |
| Publication Date: |
August 07, 2012 |
| Appl. No: |
12/140720 |
| Application Filed: |
June 17, 2008 |
| Abstract: |
Methods and computing devices enable optimized triangle strip generation using forward looking game tree evaluation methods with node evaluation of strip options based on desired performance criteria. The evaluation of possible triangle paths is performed using metrics which may be weighted for each desirable criteria at each move depth. A recursive algorithm may be used to recursively descend through alternative triangle paths and accumulates a score for the path. The final score for each evaluated triangle path at a dead end or maximum depth of evaluation provides a basis for selecting the best alternative path from the base or root triangle for graphic processing. This evaluation or alternative triangle paths may be repeated to select each subsequent triangle for processing or may be repeated after a number of triangles within the selected path have been processed. |
| Inventors: |
Dorbie, Angus MacDonald (San Diego, CA, US) |
| Assignees: |
QUALCOMM Incorporated (San Diego, CA, US) |
| Claim: |
1. A method for selecting graphic triangles for conversion in a graphics processing routine, comprising: selecting a triangle for evaluation; calculating a metric for the selected triangle; recursively repeating steps of selecting a triangle for evaluation and calculating a metric for the selected triangle to a predetermined depth of recursion or until no more triangles can be selected; calculating a score for the selected triangles based on the calculated metrics of the selected triangles, wherein the calculated score is a number of cache hits on an already generated triangle strip; and choosing a triangle for graphic processing based upon the calculated score. |
| Claim: |
2. The method of claim 1 , wherein selecting a triangle for evaluation involves selecting a triangle that has not been processed or evaluated. |
| Claim: |
3. The method of claim 1 , wherein the selected triangles form a triangle strip suitable for processing in a graphics pipeline. |
| Claim: |
4. The method of claim 3 , wherein calculating the metric for the selected triangle is based upon a criteria selected so that the calculated score for the triangle strip provides a relative measure of graphic processing efficiency of the triangle strip. |
| Claim: |
5. The method of claim 1 , further comprising: repeating the steps of recursively repeating the steps of selecting a triangle for evaluation and calculating a metric for the selected triangle to a predetermined depth of recursion or until no more triangles can be selected; and calculating a score for the selected triangles based on the calculated metrics of the selected triangles so as to generate a plurality of calculated scores characterizing a plurality of different triangle strip paths, wherein selecting a triangle for graphic processing based upon the calculated score comprises selecting a triangle at a beginning of the one of the plurality of different triangle strip paths having a best calculated score. |
| Claim: |
6. The method of claim 5 , further comprising selecting a plurality of triangles for processing within the one of the plurality of different triangle strip paths having the best calculated score. |
| Claim: |
7. The method of claim 1 , further comprising repeating the steps recited in claim 1 after the chosen triangle has been graphically processed so as to choose another triangle for graphic processing. |
| Claim: |
8. 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 triangle for evaluation; calculating a metric for the selected triangle; recursively repeating steps of selecting a triangle for evaluation and calculating a metric for the selected triangle to a predetermined depth of recursion or until no more triangles can be selected; calculating a score for the selected triangles based on the calculated metrics of the selected triangles, wherein the calculated score is a number of cache hits on an already generated triangle strip; and choosing a triangle for graphic processing based upon the calculated score. |
| Claim: |
9. The computer of claim 8 , wherein the processor is configured with software instructions so that the step of selecting a triangle for evaluation involves selecting a triangle that has not been processed or evaluated. |
| Claim: |
10. The computer of claim 8 , wherein the processor is configured with software instructions so that the selected triangles form a triangle strip suitable for processing in a graphics pipeline. |
| Claim: |
11. The computer of claim 8 , wherein the processor is configured with software instructions so that the step of calculating the metric for the selected triangle is based upon a criteria selected so that the calculated score for the triangle strip provides a relative measure of graphic processing efficiency of the triangle strip. |
| Claim: |
12. The computer of claim 8 , wherein the processor is configured with software instructions to perform steps further comprising: repeating the steps of recursively repeating the steps of selecting a triangle for evaluation and calculating a metric for the selected triangle to a predetermined depth of recursion or until no more triangles can be selected; and calculating a score for the selected triangles based on the calculated metrics of the selected triangles so as to generate a plurality of calculated scores characterizing a plurality of different triangle strip paths, wherein selecting a triangle for graphic processing based upon the calculated score comprises selecting a triangle at a beginning of the one of the plurality of different triangle strip paths having a best calculated score. |
| Claim: |
13. The computer of claim 12 , wherein the processor is configured with software instructions to perform steps further comprising selecting a plurality of triangles for processing within the one of the plurality of different triangle strip paths having the best calculated score. |
| Claim: |
14. The computer of claim 8 , wherein the processor is configured with software instructions to perform steps further comprising repeating the steps recited in claim 9 after the chosen triangle has been graphically processed so as to choose another triangle for graphic processing. |
| Claim: |
15. A computer, comprising: means for selecting a triangle for evaluation; means for calculating a metric for the selected triangle; means for recursively repeating steps of selecting a triangle for evaluation and calculating a metric for the selected triangle to a predetermined depth of recursion or until no more triangles can be selected; means for calculating a score for the selected triangles based on the calculated metrics of the selected triangles, wherein the calculated score is a number of cache hits on an already generated triangle strip; and means for choosing a triangle for graphic processing based upon the calculated score. |
| Claim: |
16. The computer of claim 15 , further comprising means for forming a triangle strip suitable for processing in a graphics pipeline from the selected triangles. |
| Claim: |
17. The computer of claim 15 , wherein the means for selecting a triangle for evaluation comprises means for selecting a triangle that has not been processed or evaluated. |
| Claim: |
18. The computer of claim 15 , wherein the means for calculating the metric for the selected triangle uses a criteria selected so that the calculated score for the triangle strip provides a relative measure of graphic processing efficiency of the triangle strip. |
| Claim: |
19. The computer of claim 15 , further comprising: means for repeating the steps of recursively repeating the steps of selecting a triangle for evaluation and calculating a metric for the selected triangle to a predetermined depth of recursion or until no more triangles can be selected; and means for calculating a score for the selected triangles based on the calculated metrics of the selected triangles so as to generate a plurality of calculated scores characterizing a plurality of different triangle strip paths, wherein the means for selecting a triangle for graphic processing based upon the calculated score comprises means for selecting a triangle at a beginning of the one of the plurality of different triangle strip paths having a best calculated score. |
| Claim: |
20. The computer of claim 19 , further comprising means for selecting a plurality of triangles for processing within the one of the plurality of different triangle strip paths having the best calculated score. |
| Claim: |
21. A non-transitory processor-readable storage medium having stored thereon processor-executable software instructions configured to cause a processor of a computer to perform steps comprising: selecting a triangle for evaluation; calculating a metric for the selected triangle; recursively repeating steps of selecting a triangle for evaluation and calculating a metric for the selected triangle to a predetermined depth of recursion or until no more triangles can be selected; calculating a score for the selected triangles based on the calculated metrics of the selected triangles, wherein the calculated score is a number of cache hits on an already generated triangle strip; and choosing a triangle for graphic processing based upon the calculated score. |
| Claim: |
22. The non-transitory processor-readable storage medium of claim 21 , wherein selecting a triangle for evaluation involves selecting a triangle that has not been processed or evaluated. |
| Claim: |
23. The non-transitory processor-readable storage medium of claim 21 , wherein the selected triangles form a triangle strip suitable for processing in a graphics pipeline. |
| Claim: |
24. The non-transitory processor-readable storage medium of claim 21 , wherein calculating the metric for the selected triangle is based upon a criteria selected so that the calculated score for the triangle strip provides a relative measure of graphic processing efficiency of the triangle strip. |
| Claim: |
25. The non-transitory processor-readable storage medium of claim 21 , wherein the stored processor-executable software instructions are configured to cause a processor of a computer to perform further steps comprising: repeating the steps of recursively repeating the steps of selecting a triangle for evaluation and calculating a metric for the selected triangle to a predetermined depth of recursion or until no more triangles can be selectet; and calculating a score for the selected triangles based on the calculated metrics of the selected triangles so as to generate a plurality of calculated scores characterizing a plurality of different triangle strip paths, wherein selecting a triangle for graphic processing based upon the calculated score comprises selecting a triangle at a beginning of the one of the plurality of different triangle strip paths having a best calculated score. |
| Claim: |
26. The non-transitory processor-readable storage medium of claim 25 , wherein the-stored processor-executable software instructions are configured to cause a processor of a computer to perform further steps comprising: selecting a plurality of triangles for processing within the one of the plurality of different triangle strip paths having the best calculated score. |
| Claim: |
27. The non-transitory processor-readable storage medium of claim 21 , wherein the-stored processor-executable software instructions configured to cause a processor of a computer to perform further steps comprising: repeating the steps recited in claim 24 after the chosen triangle has been graphically processed so as to choose another triangle for graphic processing. |
| Claim: |
28. A method for selecting a seed triangle for performing graphics processing on a modeled graphic object, comprising: selecting a first candidate seed triangle; selecting a first adjacent triangle adjacent to the first candidate seed triangle for evaluation; calculating a metric for the selected adjacent triangle; recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and calculating a metric for the selected adjacent triangle to a predetermined depth of recursion or until no more triangles can be selected; calculating a score for the selected triangles based on the calculated metrics of the selected triangles; selecting a second adjacent triangle adjacent to the first candidate seed triangle for evaluation; calculating a metric for the second selected adjacent triangle; recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and calculating a metric for the selected adjacent triangle to a predetermined depth of recursion or until no more triangles can be selected; calculating a score for the selected triangles based on the calculated metrics of the selected triangles; determining a first highest score associate with the selected first candidate seed triangle; selecting a second candidate seed triangle; selecting a first adjacent triangle adjacent to the second candidate seed triangle for evaluation; calculating a metric for the selected adjacent triangle; recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and calculating a metric for the selected adjacent triangle to a predetermined depth of recursion or until no more triangles can be selected; calculating a score for the selected triangles based on the calculated metrics of the selected triangles; selecting a second adjacent triangle adjacent to the second candidate seed triangle for evaluation; calculating a metric for the second selected adjacent triangle; recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and calculating a metric for the selected adjacent triangle to a predetermined depth of recursion or until no more triangles can be selected; calculating a score for the selected triangles based on the calculated metrics of the selected triangles; determining a second highest score associated with the selected second candidate seed triangle; and choosing one of the first and second candidate seed triangles for use as a seed triangle for graphic processing based upon the first and second highest scores associated with first and second candidate seed triangles. |
| Claim: |
29. 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 candidate seed triangle; selecting a first adjacent triangle adjacent to the first candidate seed triangle for evaluation; calculating a metric for the selected adjacent triangle; recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and calculating a metric for the selected adjacent triangle to a predetermined depth of recursion or until no more triangles can be selected; calculating a score for the selected triangles based on the calculated metrics of the selected triangles; selecting a second adjacent triangle adjacent to the first candidate seed triangle for evaluation; calculating a metric for the second selected adjacent triangle; recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and calculating a metric for the selected adjacent triangle to a predetermined depth of recursion or until no more triangles can be selected; calculating a score for the selected triangles based on the calculated metrics of the selected triangles; determining a first highest score associate with the selected first candidate seed triangle; selecting a second candidate seed triangle; selecting a first adjacent triangle adjacent to the second candidate seed triangle for evaluation; calculating a metric for the selected adjacent triangle; recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and calculating a metric for the selected adjacent triangle to a predetermined depth of recursion or until no more triangles can be selected; calculating a score for the selected triangles based on the calculated metrics of the selected triangles; selecting a second adjacent triangle adjacent to the second candidate seed triangle for evaluation; calculating a metric for the second selected adjacent triangle; recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and calculating a metric for the selected adjacent triangle to a predetermined depth of recursion or until no more triangles can be selected; calculating a score for the selected triangles based on the calculated metrics of the selected triangles; determining a second highest score associated with the selected second candidate seed triangle; and choosing one of the first and second candidate seed triangles for use as a seed triangle for graphic processing based upon the first and second highest scores associated with first and second candidate seed triangles. |
| Claim: |
30. A computer, comprising: means for selecting a first candidate seed triangle; means for selecting a first adjacent triangle adjacent to the first candidate seed triangle for evaluation; means for calculating a metric for the selected adjacent triangle; means for recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and calculating a metric for the selected adjacent triangle to a predetermined depth of recursion or until no more triangles can be selected; means for calculating a score for the selected triangles based on the calculated metrics of the selected triangles; means for selecting a second adjacent triangle adjacent to the first candidate seed triangle for evaluation; means for calculating a metric for the second selected adjacent triangle; means for recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and calculating a metric for the selected adjacent triangle to a predetermined depth of recursion or until no more triangles can be selected; means for calculating a score for the selected triangles based on the calculated metrics of the selected triangles; means for determining a first highest score associate with the selected first candidate seed triangle; means for selecting a second candidate seed triangle; means for selecting a first adjacent triangle adjacent to the second candidate seed triangle for evaluation; means for calculating a metric for the selected adjacent triangle; means for recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and calculating a metric for the selected adjacent triangle to a predetermined depth of recursion or until no more triangles can be selected; means for calculating a score for the selected triangles based on the calculated metrics of the selected triangles; means for selecting a second adjacent triangle adjacent to the second candidate seed triangle for evaluation; means for calculating a metric for the second selected adjacent triangle; means for recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and calculating a metric for the selected adjacent triangle to a predetermined depth of recursion or until no more triangles can be selected; means for calculating a score for the selected triangles based on the calculated metrics of the selected triangles; means for determining a second highest score associated with the selected second candidate seed triangle; and means for choosing one of the first and second candidate seed triangles for use as a seed triangle for graphic processing based upon the first and second highest scores associated with first and second candidate seed triangles. |
| Claim: |
31. A non-transitory processor-readable storage medium having stored thereon processor-executable software instructions configured to cause a processor of a computer to perform steps comprising: selecting a first candidate seed triangle; selecting a first adjacent triangle adjacent to the first candidate seed triangle for evaluation; calculating a metric for the selected adjacent triangle; recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and calculating a metric for the selected adjacent triangle to a predetermined depth of recursion or until no more triangles can be selected; calculating a score for the selected triangles based on the calculated metrics of the selected triangles; selecting a second adjacent triangle adjacent to the first candidate seed triangle for evaluation; calculating a metric for the second selected adjacent triangle; recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and calculating a metric for the selected adjacent triangle to a predetermined depth of recursion or until no more triangles can be selected; calculating a score for the selected triangles based on the calculated metrics of the selected triangles; determining a first highest score associate with the selected first candidate seed triangle; selecting a second candidate seed triangle; selecting a first adjacent triangle adjacent to the second candidate seed triangle for evaluation; calculating a metric for the selected adjacent triangle; recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and calculating a metric for the selected adjacent triangle to a predetermined depth of recursion or until no more triangles can be selected; calculating a score for the selected triangles based on the calculated metrics of the selected triangles; selecting a second adjacent triangle adjacent to the second candidate seed triangle for evaluation; calculating a metric for the second selected adjacent triangle; recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and calculating a metric for the selected adjacent triangle to a predetermined depth of recursion or until no more triangles can be selected; calculating a score for the selected triangles based on the calculated metrics of the selected triangles; determining a second highest score associated with the selected second candidate seed triangle; and choosing one of the first and second candidate seed triangles for use as a seed triangle for graphic processing based upon the first and second highest scores associated with first and second candidate seed triangles. |
| Claim: |
32. A method for selecting a seed triangle for performing graphics processing on a modeled graphic object, comprising: selecting a first candidate seed triangle; selecting a first adjacent triangle adjacent to the first candidate seed triangle for evaluation; counting a number of vertices on the selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips; recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and counting a number of vertices on the selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips to a predetermined depth of recursion or until no more triangles can be selected; calculating a total number of vertices already cache as a result of being part of already generated triangle strips; selecting a second adjacent triangle adjacent to the first candidate seed triangle for evaluation; counting a number of vertices on the second selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips; recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and counting a number of vertices on the selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips to a predetermined depth of recursion or until no more triangles can be selected; calculating a total number of vertices already cache as a result of being part of already generated triangle strips; determining a first highest total number of vertices already cache as a result of being part of already generated triangle strips associate with the selected first candidate seed triangle; selecting a second candidate seed triangle; selecting a first adjacent triangle adjacent to the second candidate seed triangle for evaluation; counting a number of vertices the selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips; recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and counting a number of vertices on the selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips to a predetermined depth of recursion or until no more triangles can be selected; calculating a total number of vertices already cache as a result of being part of already generated triangle strips; selecting a second adjacent triangle adjacent to the second candidate seed triangle for evaluation; counting a number of vertices on the second selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips; recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and counting a number of vertices on the selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips to a predetermined depth of recursion or until no more triangles can be selected; calculating a total number of vertices already cache as a result of being part of already generated triangle strips; determining a second highest total number of vertices already cache as a result of being part of already generated triangle strips associated with the selected second candidate seed triangle; and choosing one of the first and second candidate seed triangles for use as a seed triangle for graphic processing based upon the first and second highest total number of vertices already cache as a result of being part of already generated triangle strips associated with first and second candidate seed triangles. |
| Claim: |
33. 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 candidate seed triangle; selecting a first adjacent triangle adjacent to the first candidate seed triangle for evaluation; counting a number of vertices on the selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips; recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and counting a number of vertices on the selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips to a predetermined depth of recursion or until no more triangles can be selected; calculating a total number of vertices already cache as a result of being part of already generated triangle strips; selecting a second adjacent triangle adjacent to the first candidate seed triangle for evaluation; counting a number of vertices on the second selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips; recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and counting a number of vertices on the selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips to a predetermined depth of recursion or until no more triangles can be selected; calculating a total number of vertices already cache as a result of being part of already generated triangle strips; determining a first highest total number of vertices already cache as a result of being part of already generated triangle strips associate with the selected first candidate seed triangle; selecting a second candidate seed triangle; selecting a first adjacent triangle adjacent to the second candidate seed triangle for evaluation; counting a number of vertices the selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips; recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and counting a number of vertices on the selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips to a predetermined depth of recursion or until no more triangles can be selected; calculating a total number of vertices already cache as a result of being part of already generated triangle strips; selecting a second adjacent triangle adjacent to the second candidate seed triangle for evaluation; counting a number of vertices on the second selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips; recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and counting a number of vertices on the selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips to a predetermined depth of recursion or until no more triangles can be selected; calculating a total number of vertices already cache as a result of being part of already generated triangle strips; determining a second highest total number of vertices already cache as a result of being part of already generated triangle strips associated with the selected second candidate seed triangle; and choosing one of the first and second candidate seed triangles for use as a seed triangle for graphic processing based upon the first and second highest total number of vertices already cache as a result of being part of already generated triangle strips associated with first and second candidate seed triangles. |
| Claim: |
34. A computer, comprising: means for selecting a first candidate seed triangle; means for selecting a first adjacent triangle adjacent to the first candidate seed triangle for evaluation; means for counting a number of vertices on the selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips; means for recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and counting a number of vertices on the selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips to a predetermined depth of recursion or until no more triangles can be selected; means for calculating a total number of vertices already cache as a result of being part of already generated triangle strips; means for selecting a second adjacent triangle adjacent to the first candidate seed triangle for evaluation; means for counting a number of vertices on the second selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips; means for recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and counting a number of vertices on the selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips to a predetermined depth of recursion or until no more triangles can be selected; means for calculating a total number of vertices already cache as a result of being part of already generated triangle strips; means for determining a first highest total number of vertices already cache as a result of being part of already generated triangle strips associate with the selected first candidate seed triangle; means for selecting a second candidate seed triangle; means for selecting a first adjacent triangle adjacent to the second candidate seed triangle for evaluation; means for counting a number of vertices the selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips; means for recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and counting a number of vertices on the selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips to a predetermined depth of recursion or until no more triangles can be selected; means for calculating a total number of vertices already cache as a result of being part of already generated triangle strips; means for selecting a second adjacent triangle adjacent to the second candidate seed triangle for evaluation; means for counting a number of vertices on the second selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips; means for recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and counting a number of vertices on the selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips to a predetermined depth of recursion or until no more triangles can be selected; means for calculating a total number of vertices already cache as a result of being part of already generated triangle strips; means for determining a second highest total number of vertices already cache as a result of being part of already generated triangle strips associated with the selected second candidate seed triangle; and means for choosing one of the first and second candidate seed triangles for use as a seed triangle for graphic processing based upon the first and second highest total number of vertices already cache as a result of being part of already generated triangle strips associated with first and second candidate seed triangles. |
| Claim: |
35. A non-transitory processor-readable storage medium having stored thereon processor-executable software instructions configured to cause a processor of a computer to perform steps comprising: selecting a first candidate seed triangle; selecting a first adjacent triangle adjacent to the first candidate seed triangle for evaluation; counting a number of vertices on the selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips; recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and counting a number of vertices on the selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips to a predetermined depth of recursion or until no more triangles can be selected; calculating a total number of vertices already cache as a result of being part of already generated triangle strips; selecting a second adjacent triangle adjacent to the first candidate seed triangle for evaluation; counting a number of vertices on the second selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips; recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and counting a number of vertices on the selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips to a predetermined depth of recursion or until no more triangles can be selected; calculating a total number of vertices already cache as a result of being part of already generated triangle strips; determining a first highest total number of vertices already cache as a result of being part of already generated triangle strips associate with the selected first candidate seed triangle; selecting a second candidate seed triangle; selecting a first adjacent triangle adjacent to the second candidate seed triangle for evaluation; counting a number of vertices the selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips; recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and counting a number of vertices on the selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips to a predetermined depth of recursion or until no more triangles can be selected; calculating a total number of vertices already cache as a result of being part of already generated triangle strips; selecting a second adjacent triangle adjacent to the second candidate seed triangle for evaluation; counting a number of vertices on the second selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips; recursively repeating steps of selecting a triangle adjacent to the previously selected adjacent triangle for evaluation and counting a number of vertices on the selected adjacent triangle that are stored in cache as a result of being part of already generated triangle strips to a predetermined depth of recursion or until no more triangles can be selected; calculating a total number of vertices already cache as a result of being part of already generated triangle strips; determining a second highest total number of vertices already cache as a result of being part of already generated triangle strips associated with the selected second candidate seed triangle; and choosing one of the first and second candidate seed triangles for use as a seed triangle for graphic processing based upon the first and second highest total number of vertices already cache as a result of being part of already generated triangle strips associated with first and second candidate seed triangles. |
| Current U.S. Class: |
345/423 |
| Patent References Cited: |
6426747 July 2002 Hoppe et al.
2004/0075655 April 2004 Dunnett |
| Primary Examiner: |
Nguyen, Hau |
| Attorney, Agent or Firm: |
Hagler, James T. |
| Accession Number: |
edspgr.08237709 |
| Database: |
USPTO Patent Grants |
