雖然近年來二維影像與動畫技術蓬勃發展，已有許多成熟的壓縮方法，然而三維動態網格，又稱為三維動畫的領域當中，尚沒有一個令人熟知且優異的壓縮方法。三維動畫必須記錄模型各個點在不同影格的座標位置，所以需要大量的記憶體空間與計算量來處理，使得三維動畫的相關應用發展不容易。雖然許多學者陸續提出三維動畫壓縮法，卻都還有一些缺點尚待改進，使得尋找一個壓縮法能夠適用於各種三維動畫，還能夠具有高壓縮率、低執行時間成為熱門且值得研究的主題。

在現今科技發達的時代，一個使用者可能擁有多套瀏覽多媒體的設備，現有的影音平台對同一部影片只提供一種品質(解析度)的動畫，並不會因為使用者的電腦環境不同而做改變。使得使用低效能的配備瀏覽將發生頻寬不足導致過長的等待，無法即時的看到所想要觀看的影片。

本論文提出了一個新的三維動畫表示法，稱為漸進式動畫。漸進式動畫隨著資料讀取或傳送的過程將使得正在播放的模型由模糊而漸漸變的清晰。而漸進式動畫最重要的技術就是為了減少點座標所占有的龐大資料量。除此之外，為了能夠達到漸進式播放，所使用的壓縮法也要能夠支援逐步還原的效果。

在本論文中，我們提出的第一個方法是以分群式主成份分析為基礎的壓縮法。我們改良解壓縮的公式，使得三維動畫在重建的過程能夠隨著增加一個主成份就更新一次解析度，進而實現漸進式播放。這個方法也提出了兩種策略來決定主成分傳輸的順序，而實驗結果顯示如果依照計算好的傳輸順序作更新，可以有效降低重建的誤差。除此之外，額外所增加的負擔(記錄傳輸順序所需要的資料量)也是微乎其微。

第二個方法我們融合了簡化的方法與第一個方法，改進了第一個方法不能改變動畫點數與三角面數的缺點。我們發現主成份彼此獨立的特性，發明出將點分裂運算子與主成份結合在一起的技術。使得漸進式動畫不僅能夠改變點座標的精確度，也能夠改變動畫其外型特徵的精確度。我們實作了一套模擬系統，證明使用我們的方法能夠即時且自動地提升三維動畫的解析度，或是完全交由使用者自行控制解析度的變動。最後，本論文所提出的漸進式動畫也使得三維動畫更適應於網路上的播放與傳輸。

Although 2D image and animation compression techniques have become more popular and sophisticated, there are very few popular and better compression methods for 3D animation. Since saving all the vertex displacements at each frame would require a large amount of memory space and calculation, it is difficult to develop the applications for 3D animation. There are a few of 3D animation compression methods were proposed. However, the previous methods have some disadvantages that need to be improved. Thus, developing a compression method that is suitable for 3D animation with higher compression ratio and less computation time has become one of the important topics to be studied.

As the mobile phone become popular, a user may have multiple devices for viewing the media content through the network. However, the media provider usually provides only one resolution content for each animation, which the media provider should provide different resolution according to performance of each device. Otherwise, the long latency of downloading happens on browsing by lower performance device.

This study aimed to propose a new representation for 3D animation, where the new representation is called progressive animation. The progressive animation renders the 3D animation model from blur to clear as the data keep transmitting and loading. The first important technique of progressive animation in this study is to compress the huge amount of vertex displacements through all the frames. Moreover, to achieve the progressive rendering, the compression and simplification methods should support reconstructing the animation step by step.

In this study, we first propose a compression method based on clustered principal component analysis (PCA). We rewrite the formula of PCA decompression, reconstructing the 3D animation by applying a principle component (PC) once an update. The progressive rendering from coarse to detail is realized by applying PCs incrementally. This method also provides two strategies for deciding the transmitting sequence of the PCs. The result shows that the ordered transmitting sequences is effective for reducing the distortion, and the extra overhead is extremely low.

The second method applies the simplification into the first method, which improves the disadvantages of the first method that always presents all the vertices for any resolutions. We control the independent properties of PCs and successfully combine the vertex split operator with PC. Therefore, the progressive animation is able to update connectivity or vertex displacements according to user’s environment. As the results, the resolution of animation can be free to change at real-time, where the resolution can be increased automatically or even controlled by user. Moreover, the progressive animation is more suitable for transmitting and rendering through the network.

Table of Contents
摘要 I
Abstract II
Table of Contents IV
List of Figures VI
List of Tables X
1. Introduction 1
1.1. Background of Dynamic 3D Mesh 1
1.2. Motivations and Contributions 2
2. Related Work 7
2.1. Dynamic 3D Meshes Compression 7
2.1.1. Vertex Prediction 8
2.1.2. Wavelet Transform 9
2.1.3. Principal Component Analysis 10
2.2. 3D Mesh Simplification 12
2.3. Multiresolution and Progressive Rendering 14
3. Representing Progressive Animation 20
3.1. Selecting the Geometry Data Compression Method 20
3.2 Characteristics and Geometrical Significance of PCA 21
3.3. 3D Animation Compression Using PCA 25
3.4. Progressive Rendering by Using Local PCA 29
3.5. Determining the Sequence of Refinement Operators 33
4. Improved Progressive Animation Based on Simplification Technique 38
4.1. Problems of WPT and RPT 38
4.2. An Study of Mesh Simplification and Reconstruction Algorithms 39
4.3. Specialized Compression and Reconstruction Algorithm 42
4.4. Representing Progressive Animation with Vertex Split. 43
5. Applications and System Demonstration 49
6. Experiment Results 56
6.1. Experimental Environment and Tested Animation 56
6.2. Compression Error of RPT and WPT 57
6.3. Metro Error of Progressive Animation with Mesh Simplification 67
7. Conclusion and Future Works 74
References 76

List of Figures
Figure 1-2-1. A static 3D mesh is constructed by vertex displacements (geometry) and how the vertices connect (connectivity). In 3D animation, the connectivity does not change through frames. 2
Figure 1-2-2. Example of universal media access (UMA). This figure shows that different multimedia contents should be transmitted to the suitable devices. 4
Figure 1-2-3. The progressive images and progressive dynamic 3D meshes have similar behavior. As more data loaded, the resolution of images and meshes become more detail and more precisely. 5
Figure 2-1-1. A schematic diagram of the Dynapack algorithm. The previous and current frames and the neighboring vertices within the same frame were used to interpolate and predict the next vertex locations in the current frame [IR03]. 8
Figure 2-2-1. Schematic diagram of an edge contraction [GH97]. 13
Figure 2-2-2. Schematic diagram of a non-edge contraction [GH97]. 14
Figure 2-3-1. A dance model simplified into 300 triangles; the strategy of choosing the collapsed vertex location is the optimum location. 16
Figure 2-3-2. A dance model simplified into 300 triangles; the collapsed vertex location is one of the two edge endpoints. 16
Figure 2-3-3. A multiresolution schematic diagram of the method developed by Garland [GH97]. From left to right, the models shown in the figure were constructed of 5,804 (the original model), 994, 532, 248, and 64 triangles. 17
Figure 2-3-4. A diagram of progressive rendering using the method presented by Alliez [AD01_1]. 17
Figure 3-2-1. Schematic diagram of vertex distribution in a 2D matrix. 24
Figure 3-2-2. Schematic diagram of the first PC in a 2D matrix. 24
Figure 3-2-3. Schematic diagram of the two PCs in a 2D matrix. 24
Figure 3-3-1. Shows the geometry matrix A decomposes to the three matrices B, S, and V after executing SVD, and the relationship of PCs. 26
Figure 3-3-2. Flowcharts for the compression method proposed by Sattler [SSK05] (left) and the method employed in this study (right). With the method developed by Sattler, the compression time depends on whether the reconstruction error rapidly approaches the threshold. By contrast, the method developed in this study performs K-mean clustering, which completes clustering in one attempt without needing to iteratively calculate error values. 28
Figure 3-4-1. Different colors in the figure represent different PCs, each of which is linearly independent from the others; each transmission of one color (one PC) allows for one update. 30
Figure 3-4-2. This diagram illustrates how progressive rendering functions at the decoding side. Although the client should download, decompress and render simultaneously, the decompression and rendering thread could be processed in real time. Therefore, transmitting the refinement operators is the bottleneck which depends on the network speed. 31
Figure 3-5-1. A schematic diagram of the RPT sequence, assuming that one animation possesses two clusters (C1 and C2) after compression, and each cluster contains 5 PCs. 34
Figure 3-5-2. WPT is different from RPT, each PC has been given a weighted value, and the transmitting sequence is decided by the weighted value. 34
Figure 3-5-3. This figure shows examples of RPT and WPT through transmitting. Each PC is transmitted according to the transmitting sequence. The sequence of WPT is decided by in formula (14). 37
Figure 4-1-1. Shows the first frame of base animation of horse in wireframe mode, this animation is constructed by using 8431 vertices and 16843 triangles with 1 principal component for each cluster. 39
Figure 4-2-1. A schematic diagram of mesh simplification and reconstruction using the QSlim algorithm developed by Garland [GH97]. The following information must be retained during simplification: Vo location, the offset values (OF1 and OF2) of the distance from Vs and Vt to Vo, and NF and DF data for retriangulation. For the reconstruction stage, vertex displacements Vs and Vt must be calculated before undergoing retriangulation with NF and DF. 41
Figure 4-3-1. The procedures of the improved mesh simplification and reconstruction algorithm. 43
Figure 4-4-1. A practical illustration of base animation reconstruction. Including base connectivity and a geometry matrix that changes location with each frame, a base animation suitable for rendering is re-presented. 46
Figure 4-4-2. Possible PC changes in Matrix B' on the decoding side when an enhanced PA is rendered. As the number of vertices increase, the rows of Matrix B' increase; as the number of PCs increase, the columns of Matrix B' increase. 48
Figure 5-1. The system provides a graphic user interface (GUI) that allows users to freely change the resolution and objects of a scene. 52
Figure 5-2. A screenshot of PA rendered using a high-level device. Using the high-level device combined with the method developed in this study enables efficient processing of scenes with 7 million vertices and 14 million triangles. 53
Figure 5-3. A screenshot of PA rendered using a low-level device. The number of vertices that a low-level device can process is limited. 54
Figure 5-4. Screenshot of a close-up scene. The resolution of scene is increased from top to bottom in this picture, the left side is the rendering results of solid mode, and the right side is the wireframe mode. 55
Figure 6-2-1. Compare the boundary between clusters of RPT and WPT. The left figure is the original model, the middle figure presents the model reconstructed by RPT, and the right figure presents the model reconstructed by WPT. 58
Figure 6-2-2. Comparison of dance animation utilizing RPT and WPT updating procedures. The red circles show the portions of clear boundary non-continuity in RPT, while the effect displayed by WPT was distinctly superior. The WPT presents reasonable visual results by using no more than 3% original size. 58
Figure 6-2-3. Using KG error [KG04] to compare this study with other previous compression methods [AS07, GK04, KG04, SSK05]. These figures show that the method used in this study had a reasonable compression rate, with a reasonable error, where bpvf means bits per vertex per frame. 61
Figure 6-2-4. Results of progressive animation with few PCs. Some important parts (like the horse head) appear faster when using WPT. 63
Figure 6-2-5. Results of chicken cross animation by using WPT with different data size, different row presents different frame. 64
Figure 6-2-6. Results of cowheavy animation by using WPT with different data size, different row presents different frame. 65
Figure 6-2-7. Results of dance animation by using WPT with different data size, different row presents different frame. 66
Figure 6-3-1. RMS error of the horse animation with simplification into 800 vertices. 68
Figure 6-3-2. Metro error of chicken and dance animation with different data size. 69
Figure 6-3-3. Metro error of horse and jump animation with different data size. 70
Figure 6-3-4. Metro error of snake animation with different data size. 71
Figure 6-3-5. The progressive animation can provide any resolution that the viewer wants. This Figure shows an example of different resolutions. The top row (low resolution) needs 86KB with 320 triangles, the medium row (medium resolution) needs 200KB with 1780 triangles, and the bottom row (high resolution) needs 681KB with 5200 triangles. 72
Figure 6-3-6. More results of other animation sequences. The chicken animation shows that changing the viewpoint is supported by our method. 73
Figure 6-3-7. Progressive animation of jump animation. The number of triangles from left to right are 10436, 5218, 2136, 950, 204. 73

List of Tables
Table 3-1-1. Comparison of vertex prediction, parameterization, and PCA based methods. 21
Table 3-4-1. A comparison of the method proposed in this study and those developed by Alexa [AM00] and Sattler [SSK05]; applying the concept of progressive rendering, the data in the table shows the number of floating points required by a refinement operator and the number of refinement operators that can be employed. 33
Table 6-1-1. Basic information of tested animation. 56
Table 6-2-1. Compression time of tested dynamic 3D meshes. 57
Table 6-2-2. There are 6 clusters in the dance animation. The RMSE ( ) of each cluster was compared using RPT and WPT transmitting similar amounts of data. 59
Table 6-2-3. KG error of RPT and WPT with similar data size(KB). To show the WPT is more effective than RPT, the data size of WPT is not greater than RPT. 62
Table 6-2-4. Compare RPT and keyframe based methods by using PSNR. The keyframe based method information is referenced from [LLWC08]. 62
Table 6-3-1. More detailed information of tested progressive animation in Figure 6-3-2~6-3-4. The unit of size is KB. 71

References

[AM00] Alexa, M., Muller, W., Representing animations by principal components. Computer Graphics Forum, vol. 19, no. 3, pp. 411-418, 2000.
[AD01_1] Alliez, P., Desbrun, M., Progressive compression for lossless transmission of triangle meshes. In Proceedings of the ACM SIGGRAPH 2001, 2001, pp. 198-205.
[AD01_2] Alliez, P., Desbrun, M., Valence-driven connectivity encoding for 3D meshes. Computer Graphics Forum, vol. 20, no. 3, pp. 480-489, 2001.
[AS07] Amjoun, R., Straßer, W., Efficient Compression of 3D Dynamic Mesh Sequences. Journal of the WSCG, vol. 15, no. 1-3, pp. 99-106, 2007.
[Ari06] Arikan, O., Compression of motion capture databases. ACM Trans. Graph., vol. 25, no. 3, pp. 890-897, Jul, 2006.
[BSM*03] Briceño, H. M., Sander, P. V., McMillan, L., Gortler, S., Hoppe, H., Geometry videos: a new representation for 3D animations. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 2003, pp. 136-146.
[CRS98] Cignoni, P., Rocchini, C., Scopigno, R., Metro: measuring error on simplified surfaces. Computer Graphics Forum, vol. 17, no. 2, pp. 167-174 1998.
[COM98] Cohen, J., Olano, M., Manocha, D., Appearance-preserving simplification. In Proceedings of the 25th annual conference on Computer graphics and interactive techniques, 1998.
[DJ05] Donner, C., Jensen, H. W., Light diffusion in multi-layered translucent materials. ACM Trans. Graph., vol. 24, no. 3, pp. 1032-1039, 2005.
[GH97] Garland, M., Heckbert, P. S., Surface Simplification Using Quadric Error Metrics. In Proceedings of the ACM SIGGRAPH 1997, 1997, pp. 209-216.
[GK04] Guskov, I., Khodakovsky, A., Wavelet Compression of Parametrically Coherent Mesh Sequences. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 2004, pp. 183-192.
[Ham94] Hamann, B., A data reduction scheme for triangulated surfaces. Comput. Aided Geom. Des., vol. 11, no. 2, pp. 197-214, 1994.
[Hop96] Hoppe, H., Progressive Meshes. In Proceedings of the ACM SIGGRAPH 1996, 1996, pp. 99-108.
[HDD93] Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., Stuetzle, W., Mesh optimization. In Proceedings of the 20th annual conference on Computer graphics and interactive techniques, Anaheim, CA, 1993.
[Hot33] Hotelling, H., Analysis of a Complex of Statistical Variables into Principal Components. Journal of Educ. Psychol, vol. 24, pp. 417-441, 1933.
[HCC06] Huang, F. C., Chen, B. Y., Chuang, Y. Y., Progressive Deforming Meshes based on Deformation Oriented Decimation and Dynamic Connectivity Updating. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 2006, pp. 53-62.
[HCHY05] Huang, K.-S., Chang, C.-F., Hsu, Y.-Y., Yang, S.-N., Key Probe: a technique for animation keyframe extraction. The Visual Computer, vol. 21, no. 8, pp. 532-541, 2005.
[IR03] Ibarria, L., Rossignac, J., Dynapack: Space-Time compression of the 3D animations of triangle meshes with fixed connectivity. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 2003, pp. 126-135.
[JKTL11] Jong, B. S., Kao, C. K., Tseng, J. L., Lin, T. W., Compression of Dynamic 3D Meshes and Progressive Displaying. IEICE Transactions on Information and Systems, vol. E94D, no. 11, pp. 2271-2279, Nov, 2011.
[KMN*04] Kanungo, T., Mount, D. M., Netanyahu, N. S., Piatko, C. D., Silverman, R., Wu, A. Y., A Local Search Approximation Algorithm for k-Means Clustering. Computational Geometry: Theory and Applications, vol. 28, pp. 89-112, 2004.
[KG04] Karni, Z., Gotsman, C., Compression of soft-body animation sequences. Computers & Graphics, vol. 28, no. 1, pp. 25-34, Feb, 2004.
[KG05] Kircher, S., Garland, M., Progressive Multiresolution Meshes for Deforming Surfaces. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 2005, pp. 191-200.
[LKT*07] Lee, P.-F., Kao, C.-K., Tseng, J.-L., Jong, B.-S., Lin, T.-W., 3D Animation Compression Using Affine Transformation Matrix and Principal Component Analysis. IEICE Trans. Inf. & Syst., vol. 90-D, no. 7, pp. 1073-1084, 2007.
[LLWC08] Lee, T.-Y., Lin, C.-H., Wang, Y.-S., Chen, T.-G., Animation key-frame extraction and simplification using deformation analysis. IEEE Transactions on Circuits and Systems for Video Technology, vol. 18, no. 4, pp. 478-486, Apr, 2008.
[LWC06] Lee, T.-Y., Wang, Y.-S., Chen, T.-G., Segmenting a deforming mesh into near-rigid components. The Visual Computer, vol. 22, no. 9, pp. 729-739, 2006.
[Len99] Lengyel, J. E., Compression of Time-Dependent Geometry. In Proceedings of the ACM Symposium on Interactive 3D Graphics, 1999, pp. 89-95.
[LM06] Liu, G., McMillan, L., Segment-based human motion compression. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Vienna, Austria, 2006, pp. 127-135
[MKN*04] Müller, M., Keiser, R., Nealen, A., Pauly, M., Gross, M., Alexa, M., Point based animation of elastic, plastic and melting objects. In Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, Grenoble, France, 2004.
[MZP06] Mamou, K., Zaharia, T., Prêteux, F., A skinning approach for dynamic 3D mesh compression. Computer Animation and Virtual Worlds, vol. 17, no. 3-4, pp. 337-346, 2006.
[Pea01] Pearson, K., On lines and planes of closest t to systems of points in space. Philosophical Magazine, vol. 2, pp. 559-572, 1901.
[RR96] Ronfard, R., Rossignac, J., Full-range approximation of triangulated polyhedra. Computer Graphics Forum, vol. 15, no. 3, pp. 67-76, 1996.
[RB93] Rossignac, J., Borrel, P., Multi-resolution 3D approximations for rendering complex scenes. In Geometric Modeling in Computer Graphics, 1993, pp. 455-465.
[SSK05] Sattler, M., Sarlette, R., Klein, R., Simple and efficient compression of animation sequences. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 2005, pp. 209-217.
[SZL92] Schroeder, W. J., Zarge, J. A., Lorensen, W. E., Decimation of triangle meshes. SIGGRAPH Comput. Graph., vol. 26, no. 2, pp. 65-70, 1992.
[SBP00] Shamir, A., Bajaj, C., Pascucci, V., Multi-resolution dynamic meshes with arbitrary deformations. In Proceedings of the conference on Visualization '00, Salt Lake City, Utah, USA, 2000.
[SP01] Shamir, A., Pascucci, V., Temporal and spatial level of details for dynamic meshes. In Proceedings of the ACM symposium on Virtual reality software and technology, 2001, pp. 77-84.
[SL95] Soucy, M., Laurendeau, D., A dynamic integration algorithm to model surfaces from multiple range views. Mach. Vision Appl., vol. 8, no. 1, pp. 53-62, 1995.
[TLCL06] Tack, K., Lafruit, G., Catthoor, F., Lauwereins, R., Platform independent optimisation of multi-resolution 3D content to enable universal media access. The Visual Computer, vol. 22, no. 8, pp. 577-590, 2006.
[TGHL98] Taubin, G., Guéziec, A., Horn, W., Lazarus, F., Progressive Forest Split Compression. In Proceedings of the ACM SIGGRAPH 1998, 1998, pp. 123-132.
[Turk92] Turk, G., Re-tiling polygonal surfaces. SIGGRAPH Comput. Graph., vol. 26, no. 2, pp. 55-64, 1992.
[VS09_2] Vasa, L., Skala, V., COBRA: Compression of the Basis for PCA Represented Animations. Computer Graphics Forum, vol. 28, no. 6, pp. 1529-1540, 2009.
[VS07] Vasa, L., Skala, V., CODDYAC: Connectivity Driven Dynamic Mesh Compression. In 3DTV Conference, 2007, 2007, pp. 1-4.
[VS09_1] Vasa, L., Skala, V., Combined compression and simplification of dynamic 3D meshes. Computer Animation and Virtual Worlds, vol. 20, no. 4, pp. 447-456, 2009.
[ZO07] Zhang, J., Owen, C. B., Octree-based animated geometry compression. Computers & Graphics, vol. 31, no. 3, pp. 463-479, 2007.