SURFACE SIMPLIFICATION GUIDED BY MORPH-TARGETS

Uwe Berner, Thomas Rieger

Interactive Graphics Systems Group (GRIS), Department of Computer Science, Technische Universität Darmstadt,

Fraunhoferstr. 5, D-64283Darmstadt, Germany

Keywords: Surface Simplification, Morph-Targets, Quadric Error Metrics, Avatar.

Abstract: Many effective automatic surface simplification algorithms have been developed. These automatic

algorithms create very plausible results in many cases, but at very low levels of detail they do not preserve

the visual appearance of the original model very well. This could be improved if surface simplification

algorithms were able to make use of semantic or high-level meaning of models. The idea of our new method

using a morph-target-based surface simplification is to use distance information inside the morph-targets to

acquire the relative importance of different surface regions without user guidance. Using this additional

input the model is simplified by using modified quadric error metrics.

1 INTRODUCTION

An important field of activity at the Interactive

Graphics Systems Group (GRIS) are conversational

user interfaces where the primary goal is to give the

computer a face to talk with. The goal is the

development of software architectures to shift

complex tasks to human like assistants (avatars)

which can be incorporated on different stationary

and mobile devices like laptops, PDAs and mobile

phones. Our present work deals with scalability of

animation and graphical representation of avatars to

make our system available even on small platforms.

More details are provided in (Berner and Rieger,

2005) and (Rieger, Taponecco and Berner, 2005). In

this paper, we will focus on optimization strategies

for the graphical representation of a conversational

avatar.

During the last years many effective automatic

surface simplification algorithms have been

developed which generate a surface approximation

of fewer polygons from complex models. These

automatic algorithms create very plausible results in

many cases, but at very low levels of detail they do

not preserve the visual appearance of the original

model very well. This could be improved if surface

simplification algorithms were able to make use of

semantic or high-level meaning of models. Kho and

Garland introduced a user-guided mesh

simplification (Kho and Garland, 2003) that allows

the user to selectively control the relative importance

of different surface regions. While this approach

allows to preserve the visual appearance of the

original model well, interaction from the user is

required to achieve this result. The idea of morph-

target-based surface simplification is the usage of

distance information inside the morph-targets to

acquire the relative importance of different surface

regions without user guidance. Using this additional

input data the graphical model is simplified by using

the well known quadric error metrics (Garland and

Heckbert, 1997) as the base simplification

algorithm.

2 BACKGROUND

Many successful methods to simplify a given

complex mesh are based on iterative edge

contraction (Hoppe, 1996, Garland and Heckbert,

1997, Lindstrom and Turk, 1998). These approaches

iteratively collapse edges in increasing order of cost,

not regarding any semantc meaning of a

differentiated region. On the other hand, there are

amongst others three semi-automatic simplification

methods “Zeta” (Cignoni, 1998) , “Semisimp” (Li

and Watson, 2001) and “User-Guided

Simplification” (Kho and Garland, 2003) which are

using user interaction to produce improved

simplification results. Zeta requires a precomputed

sequence of simplifications as input. Users can

selectively refine a model by locally changing error

116

Berner U. and Rieger T. (2006).

SURFACE SIMPLIFICATION GUIDED BY MORPH-TARGETS.

In Proceedings of the First International Conference on Computer Graphics Theory and Applications, pages 116-121

DOI: 10.5220/0001355001160121

Copyright

c

SciTePress

thresholds. With Semisimp the user uses a vertex

tree structure to provide segmented simplification.

Now, let’s have a more detailed look at the User-

Guided Simplification. The method of Kho and

Garland modifies an input model in an interactive

manner and produces a simplified version guided by

geomety constraints. They use a quadric based

simplification method as a base algorithm (Garland

and Heckbert, 1997), working in the following way.

A given plane nv+d=0 with unit normal n and

point v defines a quadric Q. Q is

Q=(A,b,c)=(nn

T

,dn,d

2

) (1)

The squared distance of a point v to the plane is:

Q(v)=v

T

Av+2b

T

v+c (2)

and the error at a vertex v to a set of planes is the

sum of squared distances:

Σ Qi(v)=(ΣQi)(v) (3)

During the initialization phase of the algorithm each

vertex is assigned a quadric derived from the normal

and the incident faces. For each possible edge

contraction (v

i

,v

j

)→v

ij

the optimal position and the

contraction cost is computed by:

v

ij

=-(A

i

+A

j

)

-1

(b

i

+b

j

) (4)

and

Q(v

ij

)=Qi(v

ij

)+Qj(v

ij

)=(Qi+Qj)(v

ij

) (5)

The new vertex after the edge collapse accumulates

the quadrics by

Qv

ij

=Qi+Qj (6)

The quality of the approximation is determined by

the order of contractions, respectively by the costs.

The main idea of the algorithm from Kho and

Garland is to guide of the simplification by

manipulating the quadric associated with each

vertex. One way to do this is weighting the quadrics

adaptively. This is done by the user painting on the

surface of the geometric model. Based on this

interactive input, the quadrics are weighted with a

scalar at the initializing step:

Qi←w

i

Qi (7)

Thereby the vertices of the colored regions gain

higher costs than before. Thus the order of

contraction is rearranged via the weights, which are

dependant from the interactively marked regions of

the mesh. You can see an example from Kho and

Garland in Figure 1.

Figure 1: Simplified models, interactively improved.

3 SIMPLIFICATION WITH

MORPH-TARGETS

The key idea behind the animation with morph

targets is to combine different geometries

corresponding to given weights during an animation

(see Figure 2). During a time intervall the weights

are changing and thus the geometric objects will be

animated. In our example the different morph targets

G

1

:”normal shape”, G

2

:”eyes closed” and G

3

:”mouth

smile” were combined regarding different weights

(w

1

, w

2

w

3

) to the resulting geometry G

res

., which

results in a smiling head while closing the eyes.

Using a combination of morph-targets, an avatar

animation system can run different animations, let

the face speak or show emotions. Even all possible

combinations can be activated by choosing the

corresponding weights for the individual geometry.

SURFACE SIMPLIFICATION GUIDED BY MORPH-TARGETS

117

Figure 2: Combination of morph-targets.

The algorithm used for the morph-target-based mesh

simplification is implemented as an extension of the

quadric error metrics algorithm from Garland and

Heckbert using adaptive weighting of quadrics. The

interactive drawing on the mesh from Kho and

Garland is replaced by an automatic procedure based

on the existing morph-targets.

The key idea is that regions with a great distance

between the neutral morph-target and the others are

more animated. This implies more importance for

the visual appearance during an animation.

Therefore, this regions should be presented in more

details after a mesh simplification. This is done by

assigning bigger weights to have bigger contraction

costs and the face would be more detailed at that

regions after the simplification. The differences of

the morph-targets are used to weight the quadrics at

the initialization step. The scalars w

i

in (7) are

computed on the basis of the distances to each

morph-target.

For every vertex the distance D between the

morph-target mt and the neutral morph-target is

computed. Then all the distances belonging to one

vertex are summed up. Thus every vertex is

provided with a distance sum DS.

DS=Σ D

mt

(8)

Now the vertices are sorted by their distances DS

and weights w

i

are given depending on the position

of the vertex inside the resulting order sequence of

vertices.

This is done by grouping the vertices inside three

areas of the sequence. The first of the three with

least distances is weighted with 0.33, the second

with 0.66 and the third with 1.0. This gives for N

vertices:

Index Weights Distances

<= 1/3 N 0.33 small

1/3 N< Index < 2/3

N

0.66 middle

>= 2/3 N 1.0 great

Thus at the initialization step of the simplification

the weighting of the quadrics Qi←w

i

Qi is modified

depending of the distances of the vertices related to

the neutral morph-target. More animated regions

with greater distances get higher weights and

therefore higher contraction costs which implies a

delayed contraction of those areas.

4 RESULTS

The new simplification method was integrated inside

an existing avatar animation system, described in

(Berner, 2004). The animation system is devided in

three components: One for the graphical

representation, one for the speech synthesis and one

for controlling the behavior of the avatar. All these

components are driven from an external dialog

control giving commands to the avatar like “speak

this sentence” or “do this gesture”.

The subject discussed in this paper affects only

the representation component. The complexity of the

animated face could be changed at different levels.

The user has the possibility to select more than ten

different levels of complexity and the system

simplifies the face of the avatar with the quadric

based method of Garland and Heckbert or with our

new morph-target guided simplification. In a later

version of the system the different levels

should be selected automatically depending on the

actual performance conditions. A detailed

description for this method can be found in (Berner

and Rieger, 2005).

G

res

= w

1

*G

1

+w

2

*G

2

+w

3

*G

3

Gres

G

1

G

2

G

3

Table 1: Distance dependent quadric weights.

GRAPP 2006 - COMPUTER GRAPHICS THEORY AND APPLICATIONS

118

The first idea to evaluate the results was to look

at the reduced heads. But using our present model of

the head, the reduced results were difficult to

distinguish. In Figure 3 the original head with 3128

triangles is shown, in Figure 4 a reduced one with

878 triangles, produced from the running avatar

animation system.

Figure 3: Head, not simplified (3128 triangles).

Figure 4: Head, simplified (878 triangles).

As mentioned, it is not easy to remark the different

results of the two algorithms in an obvious manner.

To compare the results of the different algorithms in

an objective way, we used a tool called MESH

(Aspert et al., 2002), which can compare different

meshes using the Hausdorff-Distance. The

differences between the meshes are colored, blue is a

little difference, green a middle one and yellow a

bigger. We compared the simplified head with the

original and expected a greater discrepancy in the

animated regions using the original algorithm from

Garland and Heckbert. In Figure 5 the comparison

between the basic quadric based algorithm and our

new one is shown. The figure on the right hand side,

is the result of our simplification algorithm where

the head is reduced to 878 triangles. You can see

more blue (dark) areas in the animated regions

defined by the distances of the morph-targets. This is

most obvious at the cheeks.

Figure 5: Comparison of the output.

In Figure 6 the differences between the neutral

morph-target and the animated ones are shown.

There you can see, that the cheeks, the chin and the

eyebrows are the most animated regions of the

avatar. And the results above shows that the

animated regions are better approximated than in the

classical algorithm.

SURFACE SIMPLIFICATION GUIDED BY MORPH-TARGETS

119

5 CONCLUSION AND FUTURE

WORK

We have developed an extension of the algorithm

from Kho and Garland presented in the paper “User-

Guided Simplification” (Kho and Garland, 2003).

Our new approach uses the morph-targets related to

the face animation to determine areas which are

highly animated. Using a distance measure the

quadrics of the simplification algorithm are

weighted automatically at the initialization phase.

While our experimental results show that our

idea works satisfactorily, there is still room for

further development in different directions. The

algorithm should be applied to other geometric

models, which are more complex or animate other

regions. Neverthenless it must not be a head. Also

3D scanned datasets should be involved in the

testing of new models.

The strategy of weighting the quadrics should be

more improved, this first one was only implemented

for testing the fundamental method. It can be

advanced for instance by regarding the number of

existing vertices or the total amount of the distances.

Even the function over the order sequence must not

be linear. Another point is, that the not animated, but

relevant regions could be included in the weighting.

This could be the ears or the nose which are relative

important to represent the visual appearance of a

head.

ACKNOWLEDGEMENTS

Our thanks to Eric Hofmann, who did the

measurements, some programming and the graphics.

This work was partially funded by the German

"Bundesministerium für Bildung und Forschung”,

(Federal Ministry of Education and Research)

Figure 6: Comparison of the morph-targets.

GRAPP 2006 - COMPUTER GRAPHICS THEORY AND APPLICATIONS

120

through the Research Project Virtual Human, see

(VirtualHuman, 2005).

REFERENCES

Aspert, M., Santa-Cruz, D. and Ebrahimi, T. 2002. MESH:

Measuring Errors Between Surfaces Using The

Hausdorff Distance. In IEEE International Conference

in Multimedia and Expo (ICME)

Berner, U., 2004. Optimized Face Animation with Morph-

Targets. In Proceedings of WSCG 2004.

Berner, U. and Rieger, T. 2005. An Architecture To Adapt

Scalable Virtual Characters. In Proceedings of WSCG

2005.

Cignoni, P., Montani, C.,Rocchini, C., and Scorpigno, R.,

1998. Zeta: A resolution modeling system. GIMP:

Graphical Models and Image Processing 60.

Garland, M. and Heckbert, P.S. 1997. Surface

simplification using quadric error metrics. In

Proceedings of ACM SIGGRAPH 97

Hoppe, H. 1996. Progressive Meshes. In Proceedings of

ACM SIGGRAPH 96

Kho, Y. and Garland, M. 2003. User-Guided

Simplification. In ACM Symposium on Interactive 3D

Graphics.

Li, G. and Watson, B. 2001. Semiautomatic simplification.

In ACM Symposium on Interactive 3D Graphics

Lindstrom, P. and Turk, G. 1998. Fast and memory

efficient polygonal simplification. In IEEE

Visualization 98

Rieger, T., Taponecco, F. and Berner, U., 2005. Multilevel

XML based Behavior Controller for 2d and 3d Virtual

Characters. In Conference on Computational

Intelligence for Modelling, Control and Automation

(CIMCA).

Virtual Human Web-Site 2005. www.virtualhuman.de

SURFACE SIMPLIFICATION GUIDED BY MORPH-TARGETS

121