芸術科学会論文誌 Vol.4 No.4 pp.145-150

Progressive 3D Animated Models for Mobile & Web Uses
Bing-Yu Chen*
Sheng-Yao Cho†
Henry Johan‡
Tomoyuki Nishita‡†‡* National Taiwan University
The University of Tokyo†‡
ven@cmlab.csie.ntu.edu.tw{henry, nis}@is.s.u-tokyo.ac.jp*robin@ntu.edu.tw
Figure 1, it may destroy some features of the cat model insome particular poses. As an example shown in Figures 2(a) and (b), which are the first and third frames of the simplified animated model of Figure 1. The simplified animated model is obtained by using the QEM method which
only references the first pose of the animated model andapplies the simplification process to all of the poses.
Hence, the features which can be detected at the first
frame can be reserved, but the features which are hidden at
the first frame are ignored.

Abstract
To date, more high resolution 3D animated models are
required to present important details and fine structures,
however, sometimes such high resolution models are unnecessary and undesired, especially on web and mobile
phone environments. Though there are many well-known
algorithms dealing well on simplifying 3D models, most ofthem are limited to static ones. Applying these mesh simplification methods to 3D animated models, a good simplified model in a specified pose can be obtained. However, some features of the original animated model, which
can be shown in other poses, may be destroyed. In thispaper, we propose an automatic method to simplify a 3D
animated model which takes the features shown in every
poses into account and preserves the geometry details ofthem. Therefore, a progressive 3D animated model can begenerated for mobile or web uses.

(a)
(b)
(c)
(d)
(e)
Figure 1. Five poses of an original 3D animated model,
which is composed of 31 3D models and every model isdeformed from the same cat model. (a) ~ (e) shows theposes at the first, third, sixth, eighth, and tenth frame, respectively.

Keywords: Progressive Animated Models, AnimatedModel Simplification, Level-of-Details.

1. Introduction
Progressive Meshes (PM) [9] is a famous method forconstructing a sequence of 3D models with continuous
level-of-detail (LOD) based on recursive edge collapse
operations. It can be used widely not only for displaying a
3D model with continuous LOD, but also for transmitting
the 3D model over the Internet. The 3D model here onlymeans a static 3D model without motion data. However,the 3D model with motion data, or so-called 3D animatedmodel, is more widely used in many fields, like on-line
games, animations, etc. Therefore, how to provide amethod similar with PM but for the 3D animated model isnecessary. In this paper, we present a novel scheme toconstruct a sequence of 3D animated models with LOD
based on PM and the mesh simplification method presented by Garland and Heckbert [6], which is known as
the Quadric Error Metric (QEM) method. The generated
progressive 3D animated model can be used for web
presentation or showing on hand-held devices.
In general, most of the mesh simplification methods are
based on the error approximation of a 3D model in a single pose, since most of the 3D models are static. Thesemethods can result good simplified models in a neutral
pose. However, when applying these methods to an animated 3D model, like the 3D cat animation shown in

(a)

(b)

(c)
(d)
Figure 2. (a) (b) The simplified models of the first andthird frames when simplifying the animated model by only
considering the first frame. (c) (d) The simplified modelsof the first and third frames when using our method. Obviously, the shape of the cat’s tail shown in (b) and (d) are
different. The carved shape of the cat’s tail is preserved in
our method.
The simplified models shown in Figures 2 (c) and (d)are obtained by our method. By comparing the tail parts of145

芸術科学会論文誌 Vol.4 No.4 pp.145-150

Figures 2 (b) and (d), although the two models have thesame number of triangles, the curved shape of the tail partis preserved in Figure 2 (d) as Figure 1 (b), but that is notpreserved in Figure 2 (b).
The major contribution of our method is that we propose a mesh simplification method for 3D animated model
while preserving the features of the model, even the features are only shown in a few frame. This paper has beenpresented in NICOGRAPH International 2005. [4]both temporal and spatial LOD. They divided temporalvariation into factors with low and high frequencies. In
their definition, low-frequency factor stands for global
affine transformation while high-frequency factor stands
for local vertex deformations. They had different and good
LOD effects by applying different updates (e.g. spatial andtemporal); however, the size of the encoded data is muchlarger than the original mesh.
Based on "Geometry Images" [7], Briceno et al. proposed "Geometry Videos" [3] as a new representation for
3D animation. For each key-frame model, it uses global
cut algorithm and parameterization method to create consistent geometry images. It inherits many advantages from
Geometry Images and provides meshes in each frame withregular connectivity, LOD, and allows for applying numerous processing and compression methods targeted atvideos to animated models. Though it has several advantages over previous techniques; however, for models withhigh-genus, it will cause high distortion due to the defeatsof Geometry Images.

2. Related WorkPM provided by Hoppe [9] is a famous method for 3D
mesh simplification and is based on the edge collapse oredge contraction operation. Although this method could
result in an almost optimized simplified model, it is wellknown to be time-consuming. A derived method, QEM [6],has been provided to make the calculation faster. Insteadof using edge collapse or edge contraction operation foredge or vertex removal, it uses vertex-pair collapse operation which is also similar with edge collapse or edge contraction operation. The heuristic function used by QEM isgeometry-based, since it calculates the geometric distance
between the newly generated vertex and the faces which
are deformed before generating it. Both of them are good
methods for simplifying static 3D models for continuous
LOD.
For simplifying 3D animated models, Alexa and Müller
[1] proposed an approach to represent time-varying geometry by principal components. Through their method, amatrix composed of consistent meshes of original
key-frames is build at first. The vertices of each frame ofthis matrix are then decomposed to the bases and weights
after a Singular Value Decomposition (SVD) operation.
By adapting different number of the basis, the LOD can beachieved. It also supports progressive animation compression with spatial, as well as temporal. However, the computational time for SVD decomposition is expensive andthe view-dependent property cannot be fulfilled with thisapproach. Kircher and Garland also provide a method forthis problem [11].
Houle and Poulin presented a very similar algorithm as
ours on skeletal meshes [10]. They combined the PM concept and skeletal models to produce animation with continuous LOD. Their contribution is major for game industry, especially on-line games; however, it is limited to themodels with skeleton, e.g. human or animals. Furthermore,they simplify the articulated mesh by taking only one single static model into account without considering the allposes contained in the animation sequences, so they had toadjust the model to a special pose by hand for better simplification effect.
Shamir and Pascucci proposed a scheme for creating
LOD models for time-dependent meshes [12]. It supports

3. Animated Model Simplification
3.1 3D Animated ModelIn this paper, we describe an animation comprised of asequence of 3D animated models which are denoted asMˆ = Mˆ + ∆M for the i -th key-frame, where M̂ is a
i

0

i

0

generic triangle mesh; each animated model is deformed
from it, and it can also be the model at the first key-frame,i.e., Mˆ 1 = Mˆ 0 . ∆M i means the geometric difference of
the i -th key-frame between Mˆ and M̂ , which is geni

0erated by the object’s skeleton or other deformation methods like other animation generating methods. Then, thestate of the object can be calculated by interpolating two
in-between models on two consecutive key-frames. Therefore, if the number of polygons of the object is large, togenerate the model sequence is a time-consuming task.

3.2 Simplification Scheme
To decrease the number of polygons of the object is agood idea to solve the problem. However, if we simplified
the 3D animated models by simplifying each pose separately using traditional mesh simplification method, theinterpolation of two in-between models may be an artifact.
To make the simplified animated models consistent as theoriginal model sequence, we only simplify the initial meshMˆ 0 = M 0n into a coarser mesh M 00 by applying a sequence of n successive edge collapse operations. Sinceedge collapse operations are invertible, M̂ 0 can therefore

146

芸術科学会論文誌 Vol.4 No.4 pp.145-150

changed. That means a vertex will be the feature at certain
frame, but it can be removed at other frames since it is not
the feature in these frames. If we do not consider thissituation and just remove it since it is not the feature in
most frames, the feature will be disappeared like thecurved shape of the tail part shown in Figure 2 (b).
Hence, we modified the quadric error metrics Q(v) of

be denoted as its simplified mesh M 00 with a sequence ofn vsplit records as described in [9], where vsplit is a vertex split operation which is the inverse operation of edge
collapse. Hence, Mˆ 0 = M 0n can be denoted asnMˆ 0 = M 0n = M 00 + ∑ j =1 vsplit j .

Then, the pose of the animated model at the i -th
key-frame can be defined asnMˆ i = Mˆ 0 + ∆M i = M 00 + ∑ j =1 vsplit j + ∆M i.
n
= M i0 + ∑ j =1 vsplit j = M ineach vertex v of the initial mesh M̂ 0 to beQ(v) = max Qi (v) , where Q(v) is the quadric error metrics of the corresponding vertex v of the animated models Mˆ i for the i -th key-frame. The value of Q(v ) isused to select a proper vertex v with the minimumQ(v ) to remove. Hence, we use the maximum Q(v ) ,among the key-frames to guarantee the removed vertex is
the proper one for all of the models which composed theanimated model. To drive M 0j by adding ∆M i , i.e.,

Therefore, by applying some vsplit records to M i0 , wecan get multiresolution animated models for each
key-frame.

M i j = M 0j + ∆M i , a deformed model at the i -th
key-frame and j -th level can be achieved. The geometricdifference ∆M i is generated by the model’s skeleton orsome deformation methods, so when applying ∆M i to
M 0j , if some parts or vertices of the model has been simplified, this geometric difference will be ignored. Thatmeans if a part of the model has been removed, the motionof this part should also be ignored.
The reasons that we use this QEM function are basedon the following two heuristics: (1) The decimation cost of
the original features of the initial model are certainly highwithin all frames. (2) Features caused by the deformation
will introduce the peaks of the QEM value as shown in
Figure 3. From the first heuristic, we can still preserve theoriginal features of the animated model because those features are motion independent, and the second one takes thefeatures caused by some specific motions into account
whether those motions are frequent or not. If the motion isfrequent in this animation, it will introduce many peaks of
QEM value in the chart.

Figure 3. The features which are only appeared in somecertain frames can be detected by considering their QEM
values.

3.3 The QEM Function
To simplify the initial mesh M̂ 0 , we use the algorithm
modified from the QEM method. The original QEM
method simplifies the mesh by considering the quadricerror metrics Q(v) of each vertex v of the mesh. If
Q(v ) is large, that means the vertex v is located at a
bumpy surface and it might be a feature and will be removed later. Otherwise, it will be removed earlier. Since
the initial mesh M̂ 0 is deformed to be other poses to perform the animated model, to simplify it, it is necessary totake other poses of the animated model into account at thesame time.
In Figure 3, we show the variance of two QEM valuesof two vertex-pairs along the time. During the animation
playing, the QEM values of some vertices might be

4. Result
Figure 4 shows the simplification result of an angry cat
animation which is composed by 31 cat models with different poses. Obviously, even the number of triangles ismuch decreased; the features of the animation can still berecognized, such as the curved shape of the tail part andthe variance of the cat’s back.
The lower row of Figure 5 shows a dog walking animation
which is generated by 20 deformed dog models. Since theentire animated dog models are generated by deforming
the same initial dog model, these models are vertex-wisecorrespondence. Simplifying the initial dog model while147

芸術科学会論文誌 Vol.4 No.4 pp.145-150

considering the quadric error metrics of the other poses,
the multiresolution dog walking animation can be obtained
as the upper and middle rows of Figure 5. Applying thedeformation data to the simplified dog models, multiresolution dog walking animations can be obtained. To simplify the dog models, it costs about 3.76sec. on a desktop

PC with an Intel Pentium 4 2.6GHz CPU. The performance of simplification depends on the number of verticesof the initial model and the key-frame number of the animation. To display our progressive 3D animated model,
we provide the viewers on several platforms including
web environments and mobile phones.

100 triangles

1,000 triangles

5,400 triangles

Figure 4. An angry cat animation. The lower row shows five poses of the original animated model. The model consists of
5,400 triangles. The middle and upper rows show the corresponding simplified results, which consist of 1,000 and 100
triangles, respectively.

150 triangles

1000 triangles

8135 triangles

Figure 5. A walking dog animation. The lower row shows five poses of the original animated model. The model consists of
8,136 triangles. The middle and upper rows show the corresponding simplified results, which consist of 1,000 and 150
triangles, respectively.
Figure 2 (b), the curved shape of the tail part of the cat
model will be simplified since that part was not a feature
at the initial model. Someone may want to use the average
QEM value for simplification as average poses approach.
As shown in Figure 6 (c), compare to Figure 6 (b), theback feet part of Figure 6 (c) becomes strange, since average poses approach makes the importance of that partdecreased. This is because that part is not always the feature.
To measure the statistic differences of these simplifica-

To compare our method with other simplification
schemes, we use two kinds of quadric error metrics:
Q(v) = Q 0 (v) and Q(v) = ∑ i = 0 Qi (v) / m ,m −1

where m is the number of frames and Q1 (v ) = Q 0 (v) .
We call the two kinds of QEM functions as single poseapproach and average poses approach. The result of using single pose approach is like the result of [10], sinceboth of single pose approach and [10] only consider thefeatures appeared in one certain frame. Hence, as shown in148

芸術科学会論文誌 Vol.4 No.4 pp.145-150

tion schemes, we use Metro [5] as a measuring tool tocompare the simplified models to the original ones. It is
designed to compensate for a deficiency in many simplification methods proposed in literature. It allows one tocompare the difference between a pair of surfaces (e.g. a
triangulated mesh and its simplified representation) byadopting a surface sampling approach. It has been designed as a highly general tool, and it does no assumption
on the particular approach used to build the simplified
representation. It can also return both numerical results(meshes areas and volumes, maximum and mean error,etc.) and visual results, by coloring the input surface ac-cording to the approximation error.

(a)
(b)
(c)
Figure 6. (a) The original dog model which is the firstpose of a dog animation sequence. (b) The simplified dog
model generated by our method. (c) The simplified dog
model generated by using average poses approach.

(a)
(b)
(c)
Figure 7. RMS distance between the simplified animated model and the original one for (a) our method, (b) simplification
due to the first frame as single pose approach, and (c) simplification using average poses approach.
Figure 7 shows the RMS distance approximation of all
simplified models generated by three different simplification approaches. RMS distance is a better measurement or
metric than mean distance, because it is two-norm distances and it considers the space-relationship of distances
between sampled points on original model and simplified
model. From Figure 7, we find out that the RMS distance
between the original model and the simplified model aresmaller if we use our method or average poses approach.
Another observation is that the surface of the chart createdby our method is much smoother than those by other simplification approaches. That means some features are simplified in other two approaches, so at some certain frames,
the differences between the simplified model and theoriginal one become large and it makes the chart becomesbumpy.
Since the target of our method is to provide a progressive animated model for web and mobile uses, we therefore provide two kinds of viewers as shown in Figure 8.
One is developed for mobile phones and the other is forJava-enabled browsers.

(a)(b)
Figure 8. Progressive animated model viewer on (a) a mobile phone and (b) a Java-enabled browser.
For each simplified model (in different level and different frame), we measure the root mean square (RMS)
distance from its surface to the corresponding model (inthe same frame but full resolution). Then Matlab1 is used
to make charts for observation: x-axis stands for the level(from 10 to 1) of the simplified model, where level-10 isthe full resolution and level-1 contains 10% faces of theoriginal model; y-axis stands for the frame number, andz-axis stands for the measured error approximations.
1

5. Conclusions and Future WorkIn this paper, a fully automatic simplification scheme,
which preserves the deformation features of objects, foranimated models is proposed. 3D animated models, either
key-framing or skeletal models, can be inputs of our sys-

http://www.mathworks.com/

149

芸術科学会論文誌 Vol.4 No.4 pp.145-150

tem, and a progressive animated model is generated. The
scheme we proposed takes every pose of the animatedmodel into account, and determines a better decimation
sequence to simplify it. We can find out that our method
really produce better simplified models than other schemes
from the visualized results. Moreover, we can conclude
that our method can generate a smooth animated modelfrom the statistic results, though the evaluation of error
approximation of our method is slightly higher than the
average scheme.
Currently our simplification method does not consider
the attributes of the vertices, like colors, textures, and eventhe binding weights of the skeletal models. Though theanimated model is scalable, the storage space is huge. We
would like to propose a well-organized data structure to
store those data in the near future. The TDAG (Temporal
Directed Acyclic Graph) structure used by Shamir andPascucci in [10] is a good reference for us to start.

[4] B.-Y. Chen, S.-Y. Cho, H. Johan, and T. Nishita. Pro-

gressive 3D animated models for mobile & web uses.
In NICOGRAPH International 2005 Conference Proceedings, pages 135-140, 2005.
[5] P. Cignoni, C. Rocchini and R. Scopigno. Metro:measuring error on simplified surfaces. Computer
Graphics Forum, 17(2):167–174, 1998.
[6] M. Garland and P. S. Heckbert. Surface simplification

using quadric error metrics. In ACM SIGGRAPH
1997 Conference Proceedings, pages 209–216, 1997.
[7] X. Gu, S. J. Gortler, and H. Hoppe. Geometry images.

ACM Transactions on Graphics (SIGGRAPH 2002
Conference Proceedings), 21(3):355–361, 2002.
[8] A. Gueziec, G. Taubin, B. Horn, and F. Lazarus. A

framework for streaming geometry in VRML. IEEE
Computer Graphics and Applications, 19(2):68–78,
1999.

Acknowledgements[9] H. Hoppe. Progressive meshes. In ACM SIGGRAPH

1996 Conference Proceedings, pages 99–108, 1996.

This work was partially supported by the National Science Council of Taiwan under the numbers: 92-2218-E002-056, 93-2213-E-002-084, and 94-2213-E-002-097.
The third author, Henry Johan, is supported by the Japan
Society for the Promotion of Science (JSPS) Postdoctoral
Fellowship for Foreign Researchers.

[10] J. Houle and P. Poulin. Simplification and real-timesmooth transitions of articulated meshes. In Graphics
Interface 2001 Conference Proceedings, pages 55–60,
2001.
[11] S. Kircher and M. Garland. Progressive Multiresolu-

tion Meshes for Deforming Surfaces. In Proceedingsof ACM Symposium on Computer Animation 2005,
2005.

References[1] M. Alexa and W. Müller. Representing animations by[12] A. Shamir and V. Pascucci. Temporal and spatial

principal components. Computer Graphics Forum(Eurographics 2000 Conference Proceedings),
19(3):411–418, 2000.

level of details for dynamic meshes. In Proceedings of
ACM Symposium on Virtual Reality Software andTechnology 2001, pages 77–84, 2001.

[2] C. L. Bajaj, V. Pascucci, and G. Zhuang. Progressive[13] M. Soucy and D. Laurendeau. Multiresolution surface

compressive and transmission of arbitrary triangularmeshes. In IEEE Visualization 1999 Conference Proceedings, pages 307–316, 1999.

modeling based on hierarchical triangulation. Computer Vision and Image Understanding, 63(1):1–14,
1996.

[3] H. M. Briceno, P. V. Sander, L. McMillan, S. Gortler,[14] J. Rossignac and P. Borrel. Multi-resolution 3D ap-

and H. Hoppe. Geometry videos: a new representationfor 3D animations. In Proceedings of ACM Symposium on Computer Animation 2003, pages 136–146,
2003.

proximations for rendering complex scenes. In Proceedings of Geometric Modeling in Computer Graphics, pages 455–465, 1993.

150