Multiresolution mesh morphing

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.


In computer graphics, shapes are described by triangular meshes. These meshes are expensive to save, transfer, render, and are not easy to edit. Multiresolution analysis express a simple and theoretically approach to dealing with these problems.The process of Metamorphosis (or morphing) is an interpolation technique that gradually changing a source objects through intermediate objects to make a smooth transition into a target object. A new method is user controlled morphing of two homeomorphic triangle meshes of arbitrary topology. The problem for Multiresolution Mesh Morphing is the setting up a correspondence map between source and target meshes. That method is used by the MAPS algorithm to express both meshes over uncomplicated base domains and a further harmonic map taking the next part into correspondence. In order to manage the mapping the user can indicate the arbitrary number of feature pairs, which manipulate the parameterizations developed by the MAPS algorithm. Further controls are given by a clear calculation program allowing the user to adjust the mapping between the base domains.

1 Introduction

Because of the improvements in 3D scanning and acquisition technology have made dense triangle meshes popular as representations of complex objects. These scanning devices typically create triangulations which form a surface of arbitrary topology. The large size of the meshes makes it difficult to manipulate them efficiently, an issue which can be addressed through the use of multiresolution representations. It has numerous applications from modeling to the generation of animation sequences for the movie and advertising industries. Much of the work done in this area has been on 2D metamorphosis, i.e., morphing of filmed or rendered sequences. 3D morphs change the geometry of an object independent of subsequent rendering. Specifically we make the following contributions in this paper:

1.1 Dense correspondences for arbitrary meshes

The problem of establishing dense correspondences between any two irregular connectivity meshes is equivalent by topologically. This involves the construction of mappings from the fine meshes to their coarse base domains and of a mapping between the base domains. These mappings are realized through the metamesh, a topologically and geometrically merged version of source and destination meshes.

1.2 Fine and coarse user control

For fine features, marking vertices or connected sets of edges on each mesh and pairing them up, is sufficient. Coarse control can be done by modifying the mapping between the coarse source and destination domains.

Algorithm proceeds by creating parameterizations of the source and destination mesh using the MAPS (Multiresolution Adaptive Parameterization of Surfaces) algorithm. These two parameterizations are placed into correspondence through the construction of a map between the source and destination domains.

2 Compute the Correspondence Map

The key problem in morphing from one mesh to another is the establishment of the correspondence map with user controls.

Notation : A triangle mesh (P3, K), where P denotes a set of N point positions

pi = (xi, yi, zi) ∈ R3 with 1 ≤ i ≤ N, and K denotes abstract simplicial complex which including all the topological information. K is a set of subsets of {1,.., N}.

Three kinds of simplices: vertices v = {i} ∈ K, edges e = {i, j} ∈ K, and faces f = {i, j, k} ∈ K.

The geometric realization φ(a) for a ∈ K is convex hull of all points pi with i ∈ a. Thus φ(i) = pi, φ(i,j) is the open line segment between pi and pj, and φ(i,j,k) is the open triangle between pi, pj, and pk. The φ(K) is given by ∪a∈K φ(a) and forms a polyhedron embedded in R3. {i} and {j} are adjacent if (i,j) ∈ K. A set of vertices is independent if no two vertices are adjacent. The 1-ring neighborhood of a vertex i is the set V (i) = {j | {i, j} ∈ K}. The degree of a vertex is its number of adjacencies.

2.1 Algorithm

Two meshes: the source mesh (S,Ks) with Ns vertices and the target mesh (T, Kt) with Nt vertices. Goal is the construction of a correspondence map M between φ (S) and φ (T ). The correspondence map has to be a bijection to avoid cracks and folds in the morph. Note that the mapping M(si) of a vertex of the source is not a vertex of the target. In the first stage we apply the MAPS algorithm to both source and target mesh, constructing coarse base domains (S(0),K(0) ) and (T(0),K(0) ), IIs: two bijective mappings φ (S) φ (S(0)) and IIt(T) →(T (0)). Compute a correspondence map M(0) between the source base domain φ (S(0)) and target base domain φ (T (0)). M: φ (S) → (T) with M = IIt -1 M(0) IIs

The MAPS algorithm ensures that these features are mapped to edges in the base domain. M(0) is not determined by the user defined and it is computed automatically but can still be adjusted by the user. Feature pairs can be given by vertices, such as the tip of the nose, and lines which are a sequence of connected edges such as the mouth (see Fig 2). On the top row is the source and target mesh. The bottom row shows the corresponding source and target base domains. The user can specify feature points and lines.

Review of MAPS: User specified U feature points and corresponding vertex indices are numbered from 1 to U. IIs(si) = si and IIt (ti) = ti for 1 ≤ i ≤ U

Note that using linear interpolation the maps II are defined for every point on the mesh, not only the vertices. The map II-1 can be computed for every point on the base domain using a point location algorithm.

3 Additional User Controls

In general, the base domain of the source mesh and the target mesh are quite different and this initial solution may not be what the user desires. The user can map a vertex on the source base domain onto any point on the target base domain to adjust the mapping.

The source base domain triangle maps to a triangular shaped region on the target base domain. We compute the harmonic mapping of this region to a triangle so as to place the target base domain vertices on the source base domain.

The intersections between the source edge drawn on the target base domain and the target edges on the target base domain define the new vertices of the metamesh.

4 Conclusions

Effective and easy to use systems for user controlled morphing of dense, arbitrary connectivity triangle meshes of arbitrary topology have been demonstrated.

  • The main restriction is the source and target share the same genus. Thus fundamental work on extending MAPS to deal with genus changes is needed.
  • Once a dense correspondence map is established the characteristics of the morph can be influenced by the interpolation functions used.
  • We can compute a wavelet transform on the metamesh and give the user the option to schedule different morphing speeds for different scales/frequencies.
  • User can have more control over the actual morph by editing the metamesh in certain key frames. The morph will then smoothly adjust itself to those key frames.
  • The user needs to spend more time to guide the correspondence map. More tools are needed which naturally combine user control with automated computation.