(3.238.96.184) 您好!臺灣時間:2021/05/12 15:11
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:林偉成
研究生(外文):Wei-Cheng Lin
論文名稱:三維動態網格序列之漸進式動畫表示法
論文名稱(外文):Progressive Animation for Dynamic 3D Mesh Sequences
指導教授:林聰武林聰武引用關係鍾斌賢鍾斌賢引用關係
指導教授(外文):Tsong-Wuu LinBin-Shyan Jong
學位類別:碩士
校院名稱:中原大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:中文
論文頁數:83
中文關鍵詞:漸進式動畫三維動畫壓縮與簡化
外文關鍵詞:progressive animationcompression and simplification of dynamic 3D mesh seque
相關次數:
  • 被引用被引用:0
  • 點閱點閱:108
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
三維動態網格序列,又稱為三維動畫,現今廣泛的應用在電影與遊戲工業。隨著科技的進步與儲存能力的增加,三維模型越來越複雜與精細,造就了三維動畫的資料極為龐大,更增加了應用的困難度。隨著使用者在網路存取多媒體的需求大量增加,通用媒體存取機制(Universal Media Access)的興起,針對三維動畫進行漸層式解析(Level of Detail)的考量是有必要的。根據瀏覽裝置其效能的高低,給予最適合的解析度,讓動畫能夠順利且快速的根據不同使用者環境來進行播放,不僅能夠減少頻寬的浪費,更能夠避免使用者因使用較差的瀏覽裝置造成無法看到過高解析度之動畫。
本論文提出三維動畫的多層次解析表示法,概念上結合幾何資訊與連接關係,將原始只有單一解析度的動畫,轉變為能夠由粗糙逐漸變的精細之動畫表示法,且使用的儲存空間也較少。我們主要的想法首先建立基本的動畫,稱為基礎動畫,後續藉由增加精細運算子來提高動畫的解析度。由於大部分之運算在壓縮階段已處理完成,所以在重建動畫與精細的過程可以達到即時運算。由於我們同時對幾何資訊作壓縮與連接關係作簡化,因此運算子分為幾何資訊與連接關係兩種。我們的方法建立基礎動畫只需要少許的三角片,即可將動畫基本的外型表達出來,隨著運算子的更新能得到更精細、更高解析的動畫。此外,我們的方法保證在精細的過程當中視覺的表現是連續且平滑的作更新,觀賞時不會感覺影格有嚴重跳動的現象,換句話說,我們的方法得以實現連續漸層式解析(Continuous LOD)。
Dynamic 3D mesh sequences, which are also called 3D animation, have been widely used in the movie and gaming industries. Because the 3D models are more complex and high resolution, the large requirements of dynamic mesh data make it difficult for a number of applications such as rendering, transmitting over a network. Based on universal media access (UMA), providing a suitable resolution according to characteristics of the end user’s terminal environment is needed.
This paper proposes a multiresolution representation for 3D animation. The proposed representation correlates both geometry and connectivity for refining the coarse animation. This method transforms traditional 3D animation representation into a more compact format that takes up less storage space. The main idea is to reconstruct the most important components and coarse model first, which are called base animation, and then to load the refined model with less important components as the refining operators. In addition, because considerable preprocessing is carried out during the encoding stage, this method can achieve real-time rendering, lower memory requirements, and less computation time during the decoding stage. There are two kinds of refined operators, the one is refining the geometry part and the other is refining the connectivity part. After the simplification, the base animation appears by only few faces. More detailed or highly resolution animation appears by using 80% of original faces, but only requires 3% of original storage space. Our method based on progressive concept, getting more refined animation via refined operators during playing the animation. Consequently, this approach enables a continue level of detail for dynamic 3D mesh sequences.
目錄
摘要....................................................................I
Abstract................................................................II
誌謝....................................................................III
目錄....................................................................IV
圖目錄..................................................................VI
表目錄..................................................................X
第一章 緒論.............................................................1
第二章 相關研究.........................................................5
2.1 三維動畫表示法......................................................6
2.2 三維靜態模型簡化法..................................................9
2.2.1 點移除法(Vertex Decimation).......................................10
2.2.2 點叢集法(Vertex Clustering).......................................10
2.2.3 邊收縮法(Edge Contraction)........................................10
2.3 多層次解析與漸進式表示法............................................12
2.4 三維動態網格簡化與多層次解析........................................15
2.5 三維動態網格壓縮法..................................................18
2.5.1 點預測(Vertex-based Predictive)...................................18
2.5.2 小波轉換(Wavelet Transform).......................................20
2.5.3 主成份分析(Principal Component Analysis)..........................21
第三章 漸進式三維動態網格...............................................30
3.1 幾何資訊壓縮........................................................32
3.1.1 主成份分析與漸進式表示............................................32
3.1.2 分群式主成份分析..................................................36
3.2 改良型漸進式網格表示法..............................................38
3.3 漸進式動畫表示法....................................................41
第四章 實驗結果.........................................................47
4.1 實驗動畫基本資料....................................................47
4.2 資料量之探討........................................................50
4.3 誤差之結果與其他....................................................53
第五章 結論與未來工作...................................................68
參考文獻................................................................70
作者簡介................................................................73

圖目錄
圖2-1-1. 傳統的靜態三維模型表示方式。................................................................6
圖2-1-2. 傳統三維動畫的表示方式。........................................................................7
圖2-2-1. 共邊的兩點收縮示意圖,摘錄自[GH97]..................................................11
圖2-2-2. 未共邊的兩點收縮示意圖,摘錄自[GH97]..............................................12
圖2-3-1. 透過vsplit運算將解析度由Ωr精細到Ωr+1的示意圖。圖中也表示各記錄資訊的關係。...............................................................................................................13
圖2-3-2. Dance模型簡化到300片三角片數,合併後點的位置為計算出最佳位置(Optimal)。...................................................................................................................14
圖2-3-3. Dance模型簡化到300片三角片數,合併後點的位置為取邊的兩端點(Endpoint)之一。..........................................................................................................14
圖2-3-4. Garland [GH97]的方法多層次解析示意圖,最左邊為原始模型有5804個三角片,由左至右依序為994、532、248以及64個三角片,摘錄自[GH97]....15
圖2-3-5. 漸進式解析示意圖,摘錄自[AD01]..........................................................15
圖2-4-1. 上面為DOD + DCU的方法,下面為Kircher [KG05]的方法,紅色圈圈處可以看出DOD + DCU的方法較能保護手指的外型特徵,摘錄自[HCC06]。.......17
圖2-4-2. 左邊為DOD + DCU的方法,右邊為Kircher [KG05]的方法,紅色圈圈處可以看出DOD + DCU的方法較能保護腳趾的外型特徵,摘錄自[HCC06]。.......17
圖2-5-1. Dynapack的示意圖。利用前一個影格與目前影格以及相同影格空間中鄰近點進行內插來預測出下一個點在目前影格的位置,摘錄自[IR03]。................19
圖2-5-2. Guskov以及Khodakovsky所提出的AWC壓縮/解壓縮的演算法,摘錄自[GK04]。.......................................................................................................................20
圖2-5-3. 二維矩陣點分布示意圖..............................................................................21
圖2-5-4. 二維矩陣第一主成份方向示意圖..............................................................22
圖2-5-5. 二維矩陣第二主成份方向示意圖..............................................................22
圖2-5-6. 主成份在矩陣中資料的表示法。..............................................................23
VII
圖2-5-7. B、S、V矩陣選取P個主成份示意圖。.....................................................24
圖2-5-8. 三維動畫之主成份分析,摘錄自[AM00]。.............................................26
圖2-5-9. 分群式主成份分析的流程圖,摘錄自[SSK05]。....................................27
圖3-0-1. 靜態模型是由幾何資訊與連接關係所組成。..........................................30
圖3-0-2. 原始三維動畫表示成漸進式動畫表示法,在壓縮階段的流程圖。......31
圖3-0-3. 傳統表示法與漸進式動畫表示法示意圖。..............................................31
圖3-1-1. 三維動畫幾何資訊經過主成份分析後,主成份在B,S,V矩陣中的位置示意圖。.......................................................................................................................33
圖3-1-2. 選取P個主成份還原動畫資料的示意圖。................................................34
圖3-1-3. 以主成份分析為基礎的漸進式表示,圖中由左到右表示增加主成份的效果。每個影格皆有14118個三角片,所以在低解析的動畫中將會浪費儲存空間,圖中P代表選取的主成份數。.....................................................................................35
圖3-1-4. 馬動畫經過主成份分析後,選取一個主成份還原,圖中為第一個影格的成像圖,其中點數為8431,三角片數為16843。...................................................35
圖3-2-1. 漸進式網格(PM)與改良型漸進式網格(MPM)之間的差異。圖中*表示點的索引經過重新排序,DO為delta offsets,NF為new faces,DF為delta faces。紅線部份代表PM需要的欄位,而MPM不需要。............................................................40
圖3-2-2. 以實際範例說明漸進式網格與改良型漸進式網格之差異。紅線部份代表PM需要的欄位,而MPM不需要。............................................................................40
圖3-3-1. 建立基礎動畫的示意圖,由基礎網格取得所需的點集合,再以主成份還原幾何資訊。...............................................................................................................42
圖3-3-2. 點分裂產生新點之主成份示意圖,由點分裂運算子可以清楚的知道新點主成份的位置,且只需要給新點的主成份資料即可。...........................................43
圖3-3-3. 增加主成份之示意圖,欲增加第P個主成份,只需將第P個主成份相乘後,加入之前還原的資料即可。...............................................................................44
圖3-3-4. 漸進式動畫播放過程中,矩陣資料與動畫資訊的變化。......................46
圖4-1-1. Chicken動畫中的影格與其連接關係示意圖。..........................................47
VIII
3
圖4-1-2. Cowheavy動畫中的影格與其連接關係示意圖。......................................48
圖4-1-3. Dance動畫中的影格與其連接關係示意圖。.............................................48
圖4-1-4. Horse動畫中的影格與其連接關係示意圖。..............................................49
圖4-1-5. Jump動畫中的影格與其連接關係示意圖。...............................................49
圖4-1-6. Snake動畫中的影格與其連接關係示意圖。..............................................50
圖4-3-1. Chicken動畫於相同主成份數(10個),不同百分比的三角片數(Z軸)下還原後的誤差。...............................................................................................................54
圖4-3-2. Dance動畫於相同主成份數(10個),不同百分比的三角片數(Z軸)下還原後的誤差。...................................................................................................................54
圖4-3-3. Horse動畫於相同主成份數(10個),不同百分比的三角片數(Z軸)下還原後的誤差。...................................................................................................................55
圖4-3-4. Snake動畫於相同主成份數(10個),不同百分比的三角片數(Z軸)下還原後的誤差。...................................................................................................................55
圖4-3-5. Chicken動畫於相同主成份數(20個),不同百分比的三角片數(Z軸)下還原後的誤差。...............................................................................................................56
圖4-3-6. 在不同bpvf下,各個動畫重建後的誤差。...............................................57
圖4-3-7. dance動畫的漸進式效果圖。圖中由左而右幾何資訊的資料量大約為30KB~530KB,點數則從581增加到5581,三角片數為1158~11158。由圖可以看出資料量少卻不錯的效果。.......................................................................................62
圖4-3-8. Jump漸進式動畫示意圖。三角片數由左而右分別是10436、5218、2136、950、204。...................................................................................................................62
圖4-3-9. Horse漸進式動畫示意圖。..........................................................................63
圖4-3-10. Chicken漸進式動畫示意圖,可以看出播放中能夠任意的改變視角。6圖4-3-11. Dance漸進式動畫播放的效果。...............................................................64
圖4-3-12. 系統的擷取圖,可以自行設定主成份數跟點數來表示多層次解析的動
畫。...............................................................................................................................65圖4-3-13. 系統主成像畫面,除了顯示基本的動畫資訊,右邊為每一群的主成份
IX
數。...............................................................................................................................65圖4-3-14. 使用者可以在觀看動畫時,自由的改變視角。....................................66
圖4-3-15. 更多系統的操控介面截圖。....................................................................67

表目錄
表3-1-1. 雞動畫對空間分群後,每一群點數與執行SVD時間,以及與不分群執行SVD時間比較,總點數為3030個點。.....................................................................36
表4-1-1. 本論文實驗使用的測試動畫資訊。..........................................................47
表4-2-1. 連接關係與幾何資訊的資料量(KB)與bpvf。...........................................51
表4-2-2. 各動畫模型於初始、點分裂運算、增加主成份所需之資料量(KB)。..53
表4-3-1. 不同動畫在選取不同主成份數還原後,計算PSNR(dB),#KF代表關鍵影格數。...........................................................................................................................60
表4-3-2. 演算法每個步驟的計算時間(sec)。...........................................................61
[AM00] Alexa, M. Muller, W.: Representing Animations by Principal Components. Computer Graphics Forum, 19, 3, 2000, 411-418.
[AD01] Alliez, P. Desbrun, M.: Progressive Compression for Lossless Transmission of Triangle Meshes. In Proceedings of the ACM SIGGRAPH 2001, 2001, 198-205.
[AD01_2] Alliez, P. Desbrun, M.: Valence-Driven Connectivity Encoding for 3d Meshes. Computer Graphics Forum, 20, 3, 2001, 480-489.
[AS07] Amjoun, R. Straßer, W.: Efficient Compression of 3d Dynamic Mesh Sequences. Journal of the WSCG, 15, 1-3, 2007, 99-106.
[Ari06]Arikan, O.: Compression of Motion Capture Databases. In Proceedings of the ACM SIGGRAPH 2006 (ACM Trans. Graph.), 25, 2006, 890-897.
[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, 136-146.
[CCHT05] Chen, B. Y., Cho, S. Y., Johan, H. Nishita, T.: Progressive 3d Animated Models for Mobile & Web Uses. Journal of the Society for Art and Science, 4, 4, 2005, 145-150.
[CRS98] Cignoni, P., Rocchini, C. Scopigno, R.: Metro: Measuring Error on Simplified Surfaces. Computer Graphics Forum, 17, 2, 1998, 167-174
[COM98] Cohen, J., Olano, M. Manocha, D.: Appearance-Preserving Simplification. In Proceedings of the 25th annual conference on Computer graphics and interactive techniques, 1998, 115-122.
[CH05] Collins, G. Hilton, A.: A Rigid Transform Basis for Animation Compression and Level of Detail. In Vision, Video, and Graphics, 2005, 1-7.
[GH97] Garland, M. Heckbert, P. S.: Surface Simplification Using Quadric Error Metrics. In Proceedings of the ACM SIGGRAPH 1997, 1997, 209-216.
[GGH02]Gu, X., Gortler, S. J. Hoppe, H.: Geometry Images. ACM Trans. Graph., 21, 3, 2002, 355-361.
[Gue95] Guéziec, A.: Surface Simplification with Variable Tolerance. In Proceedings of the Second Annual International Symposium on Medical Robotics and Computer Assisted Surgery, 1995, 132-139.
[GK04] Guskov, I. Khodakovsky, A.: Wavelet Compression of Parametrically Coherent Mesh Sequences. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 2004, 183-192.
[Ham94] Hamann, B.: A Data Reduction Scheme for Triangulated Surfaces. Computer Aided Geometric Design, 11, 2, 1994, 197-214.
[Hop96] Hoppe, H.: Progressive Meshes. In Proceedings of the ACM SIGGRAPH 1996, 1996, 99-108.
[HDD*93] Hoppe, H., DeRose, T., Duchamp, T., McDonald, J. Stuetzle, W.: Mesh
71
Optimization. In Proceedings of the 20th annual conference on Computer graphics and interactive techniques, 1993, 19-26.
[Hot33] Hotelling, H.: Analysis of a Complex of Statistical Variables into Principal Components. Journal of Educ. Psychol, 24, 1933, 417-441.
[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, 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, 21, 8-10, 2005, 532-541.
[Huf52] Huffman, D. A.: A Method for the Construction of Minimum-Redundancy Codes. Proceedings of the Institute of Radio Engineers, 40, 9, 1952, 1098-1101.
[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, 126-135.
[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, 28, 2004, 89-112.
[KG04] Karni, Z. Gotsman, C.: Compression of Soft-Body Animation Sequences. Computers & Graphics, 28, 1, 2004, 25-34.
[KG05] Kircher, S. Garland, M.: Progressive Multiresolution Meshes for Deforming Surfaces. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 2005, 191-200.
[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, 18, 4, 2008, 478-486.
[Len99] Lengyel, J. E.: Compression of Time-Dependent Geometry. In Proceedings of the ACM Symposium on Interactive 3D Graphics, 1999, 89-95.
[GL06]Liu, G. McMillan, L.: Segment-Based Human Motion Compression. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 2006, 127-135.
[MNW95] Moffat, A., Neal, R. Witten, I. H.: Arithmetic Coding Revisited. In DCC '95: Proceedings of the Conference on Data Compression, 1995, 202-211.
[Pea01] Pearson, K. (1901). On Lines and Planes of Closest T to Systems of Points in Space. Philosophical Magazine. 2: 559-572.
[RR96] Ronfard, R. Rossignac, J.: Full-Range Approximation of Triangulated Polyhedra. In Proceeding of Eurographics, Computer Graphics Forum, 15, 1996, 67-76.
[RB93] Rossignac, J. Borrel, P.: Multi-Resolution 3d Approximations for Rendering Complex Scenes. In Geometric Modeling in Computer Graphics, 1993, 455-465.
[SSK05] Sattler, M., Sarlette, R. Klein, R.: Simple and Efficient Compression of Animation
72
Sequences. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 2005, 209-217.
[SZL92] Schroeder, W. J., Zarge, J. A. Lorensen, W. E.: Decimation of Triangle Meshes. In Proceedings of the 19th annual conference on Computer graphics and interactive techniques, 1992, 65-70
[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, 77-84.
[SPB00] Shamir, A., Pascucci, V. Bajaj, C.: Multi-Resolution Dynamic Meshes with Arbitrary Deformation. In Proceedings of the 11th IEEE Visualization 2000 Conference (VIS 2000), 2000.
[SL95] Soucy, M. Laurendeau, D.: A Dynamic Integration Algorithm to Model Surfaces from Multiple Range Views. Mach. Vision Appl., 8, 1, 1995, 53-62.
[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, 22, 8, 2006, 577-590.
[TGHL98] Taubin, G., Guéziec, A., Horn, W. Lazarus, F.: Progressive Forest Split Compression. In Proceedings of the ACM SIGGRAPH 1998, 1998, 123 -132.
[Tur92] Turk, G.: Re-Tiling Polygonal Surfaces. In Proceedings of the 19th annual conference on Computer graphics and interactive techniques, 1992, 55-64.
[VS08]Vása, L. Skala, V.: Combined Compression and Simplification of Dynamic 3d Meshes. Computer Animation and Virtual Worlds, 20, 4, 2008, 447-456.
[ZO07]Zhang, J. Owen, C. B.: Octree-Based Animated Geometry Compression. In Computers & Graphics, 31, 2007, 463-479.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔