Systems and methods for providing a fine to coarse look ahead in connection with parametrization metrics in a graphics system

• US 7,218,322 B2
• Filed: 07/19/2005
• Issued: 05/15/2007
• Est. Priority Date: 05/01/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hoppe, Hugues Herve, Snyder, John Michael, Sander, Pedro Vieira, Gortler, Steven Jacob
• Primary Examiner(s): Tung; Kee M.
• Assistant Examiner(s): TRAN, TAM D
• Application Number:
  US11/185,102
• Publication Number:
  US 20050253844A1
• Time in Patent Office: 665 Days
• Field of Search: 345/582, 345/428, 345/581, 345/423
• US Class Current: 345/423
• 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

Systems and methods are provided for providing a fine-to-coarse look ahead in connection with parametrization in a graphics system. The use of a variety of parametrization metrics may be supplemented and improved by the fine-to-coarse look ahead techniques of the invention. First, the metric of a parametrization is minimized using a coarse-to-fine hierarchical solver, and then accelerated with a fine-to-coarse propagation. The resulting parametrizations have increased texture resolution in surface regions with greater signal detail at all levels of detail in the progressive mesh sequence.

Claims

1. A method for providing a fine-to-coarse look ahead in connection with parametrization in a graphics system, comprising:

parametrizing at least one chart of a mesh utilizing a parametrization metric that generates and optimizes a plurality of metric values for said mesh, wherein parametrization is defined as a one-to-one mapping between all points of a mesh and all points in the corresponding parametric domain and wherein the parametrization metric is based upon a function of at least one characteristic of the mesh; and

generating a sequence of meshes in a multiresolution representation having a plurality of level of detail mesh approximations ranging from a coarsest level of detail approximation to a finest level of detail approximation for said at least one chart based upon at least said plurality of metric values, wherein the finest level of detail concerning said at least one characteristic of the mesh is taken into account while generating the parametrizations for level of detail approximations coarser than said finest level of detail approximation.

2. A method according to claim 1, wherein said generating includes propagating the plurality of metric values fine-to-coarse from the original mesh to all meshes coarser than the original mesh.

3. A method according to claim 2, wherein said propagating includes redistributing the metric values defined on triangles of the finest mesh to the triangles of the coarser meshes in the sequence of meshes.

4. A method according to claim 2, wherein said generating further includes generating an intermediate parametrization by applying a coarse-to-fine parametrization algorithm that is based upon the propagated parametrization metric values.

5. A method according to claim 4, wherein said applying of a coarse-to-fine parametrization algorithm includes creating an initial embedding for at least one face in the original mesh using a brute-force optimization and the propagated metric values from the fine mesh.

6. A method according to claim 5, wherein said applying of a coarse-to-fine parametrization algorithm further includes:

for each vertex split refinement operation, placing the newly added vertex at a location within the kernel of its neighborhood polygon; and

optimizing the placement of the added vertex and its neighbors using the propagated metric values.

7. A method according to claim 6, wherein said applying of a coarse-to-fine parametrization algorithm further includes:

for each vertex split refinement operation, placing the newly added vertex at the centroid of the kernel of its neighborhood polygon; and

optimizing the placement of the added vertex and its neighbors using the propagated metric values.

8. A method according to claim 4, wherein said propagating the metric values fine-to-coarse and said applying of the coarse-to-fine algorithm are repeated a plurality of times.

9. A method according to claim 4, whereby said generating causes the solutions obtained on level of detail approximations coarser than said finest level of detail approximation to accurately predict the final parametrization solution obtained at the end of the applying of the coarse-to-fine refinement process.

10. A method according to claim 1, wherein said generating includes constructing a sequence of meshes in a multiresolution representation by simplifying the chart mesh using at least one half-edge collapse operation and establishing a hierarchy over the chart using the sequence.

11. A method according to claim 1, wherein said generating of the sequence of meshes in a multiresolution representation includes generating a progressive mesh (PM) sequence.

12. A computing device comprising means for performing the method of claim 1.

13. At least one computer readable medium having stored thereon a plurality of computer-executable modules for providing a fine-to-coarse look ahead in connection with parametrization in a graphics system, the computer executable modules comprising:

means for parametrizing at least one chart of an mesh utilizing a parametrization metric that generates and optimizes a plurality of metric values for said mesh, wherein parametrization refers to a one-to-one mapping between all points of a mesh and all points in the corresponding parametric domain and wherein the parametrization metric is based upon a function of at least one characteristic of the mesh; and

means for generating a sequence of meshes in a multiresolution representation having a plurality of level of detail mesh approximations ranging from a coarsest level of detail approximation to a finest level of detail approximation for said at least one chart based upon at least said plurality of metric values, wherein the finest level of detail concerning said at least one characteristic of the mesh is taken into account while generating the parametrizations for level of detail approximations coarser than said finest level of detail approximation.

14. At least one computer readable medium according to claim 13, wherein said means for generating includes means for propagating the plurality of metric values fine-to-coarse from the original mesh to all meshes coarser than the original mesh.

15. At least one computer readable medium according to claim 14, wherein said means for propagating includes means for redistributing the metric values defined on triangles of the finest mesh to the triangles of the coarser meshes in the sequence.

16. At least one computer readable medium according to claim 13, wherein said means for generating further includes means for generating an intermediate parametrization via a means for applying a coarse-to-fine parametrization algorithm that is based upon the propagated parametrization metric values.

17. At least one computer readable medium according to claim 14, wherein said means for propagating the metric values fine-to-coarse and said means for applying the coarse-to-fine algorithm are repeated a plurality of times.

18. At least one computer readable medium according to claim 13, wherein said means for generating includes means for constructing a sequence of meshes in a multiresolution representation by simplifying the chart mesh using at least one half-edge collapse operation and establishing a hierarchy over the chart using the sequence.

19. At least one computer readable medium according to claim 13, wherein said means for generating the sequence of meshes in a multiresolution representation includes generating a progressive mesh (PM) sequence.

20. At least one computer readable medium comprising computer executable modules including computer executable instructions for providing a fine-to-coarse look ahead in connection with parametrization in a graphics system, wherein parametrization refers to a one-to-one mapping between all points of a mesh and all points in the corresponding parametric domain, the modules comprising:

means for parametrizing at least one chart of a mesh utilizing a parametrization metric that generates and optimizes a plurality of metric values for said mesh, wherein the parametrization metric is based upon a function of at least one characteristic of the mesh; and

means for generating a sequence of meshes in a multiresolution representation having a plurality of level of detail mesh approximations ranging from a coarsest level of detail approximation to a finest level of detail approximation for said at least one chart based upon at least said plurality of metric values, wherein the finest level of detail concerning said at least one characteristic of the mesh is taken into account while generating the parametrizations for level of detail approximations coarser than said finest level of detail approximation.