System, method, and program product for extracting a multiresolution quadrilateral-based subdivision surface representation from an arbitrary two-manifold polygon mesh

• US 7,257,250 B2
• Filed: 10/29/2003
• Issued: 08/14/2007
• Est. Priority Date: 10/29/2003
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Boier-Martin, Ioana M., Bernardini, Fausto, Jin, Jingyi, Rushmeier, Holly E.
• Primary Examiner(s): Bella; Matthew C.
• Assistant Examiner(s): RAHMJOO, MANUCHEHR
• Application Number:
  US10/696,348
• Publication Number:
  US 20050093862A1
• Time in Patent Office: 1,385 Days
• Field of Search: 382/154
• US Class Current: 382/154
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

Disclosed is an improved computer system, method, and program product that has one or more input devices for receiving one or more input meshes representing a three dimensional model. The three dimensional model is capable of being represented as a 2-manifold triangular mesh. A conversion process automatically converts the input mesh to a multiresolution quadrilateral-based subdivision surface (MQSS) representation.

Claims

1. A computer system comprising one or more memories, one or more central processing units and further comprising:

one or more input devices for receiving one or more input meshes representing a three dimensional model, the three dimensional model capable of being represented as a 2-manifold polygon mesh; and

a conversion process that automatically converts the input mesh to a multiresolution quadrilateral-based subdivision surface (MQSS) representation.

3. A system, as in claim 1, where the system further comprises one or more of the flowing:

an output for displaying the MQSS, a process for storing the MQSS in one or more of the memories.

2. A computer system comprising one or more memories, one or more central processing units and further comprising:

one or more input devices for receiving one or more input meshes representing a three dimensional model, being a 2-manifold polygon mesh, each of the input meshes having one or more features, each of the features being a part of the model with a different curvature and scale than one or more adjacent parts; and

a conversion process that automatically converts the input mesh to a multiresolution quadrilateral-based subdivision surface (MQSS) representation.

4. A computer system comprising one or more memories, one or more central processing units and further comprising:

one or more input devices for receiving one or more input meshes representing a three dimensional model, each input mesh being a 2-manifold polygon mesh, each of the input meshes having one or more features, a feature being a perceptually important part of the model with a different curvature than one or more adjacent parts; and

a conversion process that automatically converts the input mesh into a multiresolution quadrilateral-based subdivision surface (MQSS) having a base mesh with one or more base mesh edges where one or more of the base mesh edges correspond to one of the features.

5. A computer system, as in claim 4, where the MQSS is used for one or more of the following:

model editing, compression of the input mesh, a network transmission, model storage, a level of detail representation, an input model parameterization.

6. A computer system, as in claim 4, where the base mesh is one or more of the following:

a parameterization domain for the input model, a coarse approximation of the input model, a texture mapping domain.

7. A computer system, as in claim 4, where the feature is one or more of the following:

a perceptually salient ridge on the input model, a perceptually salient ravine on the input model, a perceptually salient crease, a perceptually salient curve, or some other perceptually salient element.

8. A computer system, as in claim 4, where the conversion process comprises the steps of:

a. generating an atlas decomposition of the input mesh by using an atlas generation process;

b. extracting a quadrilateral base mesh using a quadrilateral mesh extraction process, the atlas, and the input mesh; and

c. extracting the MQSS with one or more levels from the input mesh and the quadrilateral base mesh.

9. A computer system, as in claim 8, where the quadrilateral mesh extraction process comprises the steps of:

a. extracting a boundary set of one or more boundaries curves between one or more charts in the atlas; and

b. for each of the charts, creating a polygonal approximation of the chart, by simplifying one or more boundary curves corresponding to the charts, resulting in a coarse polygonal mesh.

10. A computer system, as in claim 4, where the atlas generation process comprises the steps of:

a. selecting a seed set of one or more chart seeds;

b. computing a constrained centroidal Voronoi decomposition of the input mesh around the chart seeds, the constrained centroidal Voronoi decomposition having one or more cells;

c. splitting the cells that do not satisfy a height field approximation criterion into height fields resulting in a partition of the input mesh comprising one or more regions that are approximate height fields; and

d. splitting each region that does not satisfy a compact shape criterion into one or more subregions that are approximately convex and homeomorphic to discs, resulting in the atlas that is a refined decomposition of the input mesh comprising one or more charts, each chart being one of the approximate height fields each chart being approximately convex and homeomorphic to a disc.

11. A computer system, as in claim 10, further comprising the step of:

adjusting one or more boundaries between one or more pairs of charts.

12. A computer system, as in claim 10, where the selecting the seed set is a random process.

13. A computer system, as in claim 12, where the selecting the seed set is done by performing a seed selection process comprising the following steps:

a. computing colors for the faces of the input mesh from the information provided by the mesh normals;

b. applying an optional smoothing to colors to reduce noise;

c. applying a color quantization procedure to identify regions of relatively constant shape over the input mesh;

d. further adjusting the relatively constant shape regions by optionally straightening the boundaries between them; and

e. computing an approximate medial axis for each of the relatively constant shape regions and extracting a small set of medial axis samples from regions and letting the seed set be the union of these samples.

14. A computer system, as in claim 13, where the color quantization process comprises the following steps:

a. selecting a set of representative colors; and

b. applying a color classification procedure into classes corresponding to the set of representative colors.

15. A computer system, as in claim 14, further comprising the step of:

c. removing unnecessary faces and edges of the coarse polygonal mesh.

16. A computer system, as in claim 14, further comprising the step of:

c. quadrangulating the coarse polygonal mesh if the coarse polygonal mesh is not a quadrilateral mesh.