Optimization of mesh locality for transparent vertex caching

• US 6,426,747 B1
• Filed: 06/04/1999
• Issued: 07/30/2002
• Est. Priority Date: 06/04/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Miller, John W., Hoppe, Hugues
• Primary Examiner(s): Vo, Cliff N
• Application Number:
  US09/326,349
• Time in Patent Office: 1,152 Days
• Field of Search: 345/418, 345/419, 345/420, 345/421, 345/441
• US Class Current: 345/419
• CPC Class Codes: G06T 1/60 Memory management
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 17/205 Re-meshing

Abstract

Methods for vertex caching to decrease geometry bandwidth and to reduce bus traffic between a graphics subsystem and memory include a strip-growing technique and a local optimization technique. The strip-growing technique determines an ordering of the faces in memory for the purpose of maximizing the use of the cache. This technique minimizes the number of vertices that are retrieved from a vertex buffer, and maximizes the number of needed vertices that are obtained from a vertex cache. The local optimization technique improves the results of the strip-growing technique by exploring a set of perturbations to the face ordering. The order is perturbed semi-randomly to determine if the perturbation improves the caching behavior. Types of perturbations include reflection and insertion. Thus, data is preprocessed to optimize the use of the cache stored data so that when the data is rendered at a future time, the rendering speed is improved.

Claims

1. A process for creating a data structure comprising a mesh representation of a three-dimensional (3D) object in a computer graphics system, wherein the mesh representation comprises vertices defining faces, and wherein the system includes a vertex cache of a predetermined size and a memory which is operatively coupled to the vertex cache via a bus, comprising:

providing vertex data, representing vertices of the faces of the mesh, and storing the vertex data in a vertex buffer portion of the memory; and

using the vertex data and a predefined process to determine an ordering of the faces of the mesh so as to minimize a cache miss rate during rendering of the object.

2. A process as recited in claim 1, wherein the predefined process comprises:

starting a strip-growing procedure in which a plurality of faces of the mesh are organized into a strip, wherein a cost function is associated with the addition of each new face to the strip;

at each current face, deciding whether to add a new face to the strip or instead to restart the strip-growing procedure, by determining the cost of restarting the strip-growing procedure at a face that is not adjacent to a current face;

performing a look-ahead simulation to determine the cost of continuing the strip at a face that is adjacent to the current face; and

restarting the strip-growing procedure if the cost of restarting is lower than the cost of continuing at an adjacent face.

3. A process as recited in claim 2, wherein, if the strip-growing procedure is to be restarted, the process first checks to determine whether any unvisited faces have been pushed onto a queue, and if so the procedure is restarted at the first unvisited face in the queue, and if not the procedure is restarted at an unvisited face having a fewest number of unvisited neighbors.

4. A process as recited in claim 2, wherein, if the strip-growing procedure is not to be restarted, a determination is made of which adjacent face to add to the strip by (a) determining the number of adjacent unvisited faces, (b) if the number of adjacent unvisited faces is one, then adding the one adjacent unvisited face to the strip, and (c) if the number of adjacent unvisited faces is two, then adding the adjacent face that is in a predetermined direction from the current face, and pushing the other adjacent unvisited face onto a queue.

5. A process as recited in claim 4, wherein, if the strip-growing procedure is not to be restarted, but the number of adjacent unvisited faces is zero, then the strip-growing procedure is restarted.

6. A process as recited in claim 1, further comprising:

providing at least one ordering perturbation process, wherein a cost function is associated with each ordering perturbation process;

determining a cost of each perturbation process;

comparing the cost of each perturbation process to a predetermined value to determine whether each perturbation process is beneficial; and

if at least one of the perturbation processes is beneficial, performing the perturbation process having the lowest cost to the ordering of the faces of the mesh so as to generate a re-ordering of the faces of the mesh to minimize a cache miss rate during rendering of the object.

7. A data structure stored in a computer readable memory created by the process recited in claim 1.

8. A data structure stored in a computer readable memory, for use in a computer graphics system including a vertex cache of a predetermined size and a memory operatively coupled to the vertex cache via a bus, comprising a mesh representation of a three-dimensional (3D) object, wherein the mesh representation comprises vertices defining faces, wherein the vertex data is stored in a vertex buffer portion of the memory, and wherein the faces of the mesh are arranged in the memory so as to minimize a cache miss rate during rendering of the object.

9. A computer graphics system for creating a data structure comprising a mesh representation of a three-dimensional (3D) object, wherein the mesh representation comprises vertices defining faces, comprising:

a vertex cache of a predetermined size;

a memory operatively coupled to the vertex cache via a bus, the memory having a vertex buffer portion for storing vertex data representing vertices of the faces of the mesh; and

a processor for using the vertex data and a predefined process to determine an ordering of the faces of the mesh so as to minimize a cache miss rate during rendering of the object.

10. A system as recited in claim 9, wherein the processor (a) starts a strip-growing procedure in which a plurality of faces of the mesh are organized into a strip, wherein a cost function is associated with the addition of each new face to the strip;

(b) at each current face, decides whether to add a new face to the strip or instead to restart the strip-growing procedure, by determining the cost of restarting the strip-growing procedure at a face that is not adjacent to a current face;

(c) performs a look-ahead simulation to determine the cost of continuing the strip at a face that is adjacent to the current face; and

(d) restarts the strip-growing procedure if the cost of restarting is lower than the cost of continuing at an adjacent face.

11. A system as recited in claim 10, further comprising a queue for storing unvisited faces, wherein, if the strip-growing procedure is to be restarted, the processor first checks to determine whether any unvisited faces have been pushed onto the queue, and if so the procedure is restarted at the first unvisited face in the queue, and if not the procedure is restarted at an unvisited face having a fewest number of unvisited neighbors.

12. A system as recited in claim 10, further comprising a queue for storing unvisited faces, wherein, if the strip-growing procedure is not to be restarted, the processor determines which adjacent face to add to the strip by (a) determining the number of adjacent unvisited faces, (b) if the number of adjacent unvisited faces is one, then adding the one adjacent unvisited face to the strip, and (c) if the number of adjacent unvisited faces is two, then adding the adjacent face that is in a predetermined direction from the current face, and pushing the other adjacent unvisited face onto the queue.

13. A system as recited in claim 12, wherein, if the strip-growing procedure is not to be restarted, but the number of adjacent unvisited faces is zero, then the processor restarts the strip-growing procedure..

14. A process for creating a data structure comprising a mesh representation of a three-dimensional (3D) object in a computer graphics system, wherein the mesh representation comprises an ordering of faces, comprising:

providing at least one ordering perturbation process, wherein a cost function is associated with each ordering perturbation process;

determining a cost of each perturbation process;

comparing the cost of each perturbation process to a predetermined value to determine whether each perturbation process is beneficial; and

if at least one of the perturbation processes is beneficial, performing the perturbation process having the lowest cost to the ordering of the faces of the mesh so as to generate a re-ordering of the faces of the mesh to minimize a cache miss rate during rendering of the object.

15. A process as recited in claim 14, wherein each ordering perturbation process is one of face subsequence reflection, face insertion, and paired face insertion.

16. A process as recited in claim 14, wherein determining the cost of each perturbation process comprises parameterizing each perturbation process by two faces of the mesh.

17. A process as recited in claim 16, wherein the two faces are adjacent in the mesh or adjacent in the ordering of faces.

18. A process as recited in claim 16, further comprising repeating the process a user specified number of times.

19. A data structure stored in a computer readable memory created by the process recited in claim 14.

20. A computer graphics system for creating a mesh representation of a three-dimensional (3D) object in a computer graphics system, wherein the mesh representation comprises an ordering of faces, comprising:

a data store for storing data representative of the ordering of faces; and

a processor for generating a re-ordering of the faces of the mesh to minimize a cache miss rate during rendering of the object.

21. A system as recited in claim 20, wherein the processor (a) determines a cost of at least one ordering perturbation process, each ordering perturbation process having an associated cost function;

(b) compares the cost of each perturbation process to a predetermined value to determine whether each perturbation process is beneficial; and

(c) if at least one of the perturbation processes is beneficial, performs the perturbation process having the lowest cost to the ordering of the faces of the mesh so as to generate a re-ordering of the faces of the mesh to minimize a cache miss rate during rendering of the object.

22. A system as recited in claim 21, wherein each ordering perturbation process is one of face subsequence reflection, face insertion, and paired face insertion.

23. A system as recited in claim 21, wherein the processor determines the cost of each perturbation process by parameterizing each perturbation process by two faces of the mesh.

24. A system as recited in claim 23, wherein the two faces are adjacent in the mesh or adjacent in the ordering of faces.

25. A system as recited in claim 23, wherein the processor repeats the process a user specified number of times.