簡易檢索 / 詳目顯示

回結果列表
研究生： 吳宗憲
Wu, Tsung-Hsien
論文名稱： 以多重RBF函式建構精簡3D模型表示法與動態點繪圖演算法
Dynamic Point Rendering and Compact Representations for 3D Models with Multiple Radial Basis Function (RBF) Surfaces
指導教授： 李同益
Lee, Tong-Yee
學位類別： 碩士
Master
系所名稱： 電機資訊學院 - 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年： 2002
畢業學年度： 90
語文別： 中文
論文頁數： 135
中文關鍵詞： 相機取樣場 、取樣密度 、顯像技術演算法 、小波
外文關鍵詞： Radial Basis Function, Camera Sampling Field, Implicit Surface, Splat Size
相關次數： 點閱：81  下載：1 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 本論文描述一個以點為基礎的顯像技術系統，這個系統包含了一個以正立方體為基礎的階層式解析度的架構。
    我們從多邊形模型中建立一個階層式的結構，對於在這個階層式樹中的樹葉節點，我們建立一個圓滑的 implicit surface 來描述這個節點的表面，這個 implicit surface 的方程式 (implicit function) 是由 Radial Basis Functions (RBFs) 所建立和描述出來的，我們將階層式架構中的每一個節點包括樹葉節點和非樹葉節點都細切成 n*n*n 個均勻大小的格子，再對每個樹葉節點的格子點代入 implicit function 中求出值，而非樹葉節點包括樹根的值，並不是由 implicit function 所計算出來的，而是由樹葉節點中格子點的值經過 Haar 小波轉換所得到，再來對所有的節點包括樹葉節點和非樹葉節點，我們可以根據相鄰兩個格子點的值，有正值和負值可以內差出等於零的值，由這個內差的比例可以內差位置算出正確表面點的位置，算出正確的位置後，再將這個位置移動到最接近的格子點上，這會使的我們所取樣的點更加的均勻且更容易做資料的壓縮。
    在繪圖時，我們採用一個相似 coherence rendering 的演算法來遊走階層式樹往上或往下選擇節點來繪出，coherence rendering 主要是利用相鄰兩個畫面的連慣性來做最小的節點選擇，另外我們也有一些運作機制，像 view frustum culling 及 backface culling 及使用 Camera Sampled Field (CSF) 來計算 splat size 及均勻的增加點和輪廓邊界的考量，在即時互動的時間上，所得到結果是具有高品質和且平滑的輪廓。

    The paper describes a point rendering system for complex 3D models. For a given 3D model, we build a compact representation of points that significantly compress 3D model. In this representation, we exploit 3D Harr wavelet to build a hierarchy of points that preserves key features inherent in the original models. Our rendering algorithm can use this hierarchy to dynamically choose appropriate resolution for display. In contrast to other well-known previous work such as QSplat [5] and POP [6], there are many key features in the proposed method:
    1. High compression data ratio.
    2. Points are dynamically added according to a novel camera-sampling field (CSF) to yield smooth surface representation.
    3. Point-shapes are dynamically adjusted also by CSF to yield a smooth silhouette.
    4. Points are uniformly added layer by layer to avoid blurring.
    5. 3D models are decomposed into many parts and each part is reconstructed by a radial-based function (RBF).
    At run time, our rendering algorithm takes the following into account such as frame coherence, view frustum culling, back-face culling and so on. Therefore, the proposed system can effectively render 3D models.

    第一章. 緒論 ……………………………………………………………………... 1 1.1 研究動機 …………………………………………………………… 1 1.2 研究範圍、目的、構想 …………………………………………… 2 1.2.1 可見度裁切（Visibility Culling） …………………………… 2 1.2.1.1視線區域裁切法與背面裁切法（View Frustum Culling and Back Frustum Culling） …………………………………… 2 1.2.1.2 遮蔽物裁切法（Occlusion Culling） …………………. 3 1.2.1.3 深度空間裁切（Z-buffer Culling） …………………... 5 1.2.2 影像式顯視法（Image-Based Rendering） …………………... 5 1.2.2.1 環境貼圖（Environment Map） ………………………. 6 1.2.2.2 平面 Sprite（Planar Sprite） ………………………… 7 1.2.2.3 有深度 Sprite（Sprite with Depth） ………………… 7 1.2.2.4 多層深度影像（Layered Depth Image） …………… 8 1.2.3 畫點式顯視法簡介（Point-Based Rendering） ………………. 9 1.3 論文章節安排 ……………………………………………………… 9 1.4 論文貢獻 ………………………………………………………….. 10 1.5 研究創新即時用價值評述 ……………………………………….. 12 1.5.1 研究創新 ……………………………………………………. 12 1.5.2 實用價值評述 ………………………………………………. 13 1.6 流程圖 …………………………………………………………….. 15 第二章. 相關研究…………………………………….………………………….. 17 2.1 QSplat: A Multiresolution Point Rendering System for Large Meshes [5] …..……………………….………………………………………….. 17 2.1.1 QSplat 的資料結構及演算法 ……………….……………… 17 2.1.1.1 顯像技術演算法（Rendering Algorithm） ………… 17 2.1.1.2 前處理演算法（Preprocessing Algorithm） …………. 18 2.1.2 細節說明 …………...……………………………………….. 18 2.1.2.1 位置和半徑 …………………………………………. 18 2.1.2.2 法向量（Normal） …………………………………... 19 2.1.2.3 顏色（Color） ………………………………………… 19 2.1.2.4 法向量圓錐（Normal Cone） ………………………... 19 2.1.2.5 Splat 形狀（Splat Shape） ……………………………. 20 2.2 POP: A Hybrid Point and Polygon Rendering System for Large Data [6] ……………….……………………………………………………… 20 2.2.1 建立階層式架構的資料 ………..…………………………... 21 2.2.2 顯像技術演算法 …………………….……………………… 23 2.3 Computing and Rendering Point Set Surfaces [7]….………………. 25 2.3.1 定義表面 ……………………………………………………. 26 2.3.2 產生點的集合 ………………………………………………. 27 2.3.2.1 減少取樣點的密度 …………………………………. 27 2.3.2.2 增加取樣點的密度 …………………………………. 28 2.3.3 顯像技術（Rendering） ……………………………………… 29 2.4 Surfels: Surface Elements as Rendering Primitives [8] ……………. 29 2.4.1 surfel 的定義 ………………………………………………... 29 2.4.2 取樣 …………………………………………………………. 29 2.4.2.1 LDC 取樣 …………………………………………… 29 2.4.2.2 材質預先濾鏡（Texture Prefiltering） ……………….. 30 2.4.3 資料結構 ……………………………………………………. 31 2.4.3.1 LDC 樹 ……………………………………………… 31 2.4.3.2 3-to-1 減少（Reduction） …………………………….. 31 2.4.4 顯像技術導管（Rendering Pipeline） ……………………….. 32 2.4.4.1 區塊裁切（Block Culling） ………………………….. 32 2.4.4.2 區塊變形（Block Warping） …………………………. 32 2.4.4.3 顯像技術（Rendering） ……………………………… 32 2.5 The Randomized z-Buffer Algorithm: Interactive Rendering of Highly Complex Scenes [10] …………………………………………………... 33 2.6 Interactive Sampling and Rendering for Complex and Procedural Geometry [11] ………………………………………………………….. 35 2.7 Differential Point Rendering [9] ……………………………………. 36 第三章. 取樣點的建立 ………………………………………….……………… 38 3.1 階層式架構的建立 ………………………………..……………… 38 3.1.1 座標標準化（Normalize） …………………………………… 38 3.1.2 法向量的取得 ………………………………………………. 39 3.1.3 階層式架構 …………………………………………………. 39 3.2 法向量的階層式架構預先建立 ………………………………….. 41 3.3 Implicit Surface 的建立 …………………………………………... 42 3.3.1 Implicit Surface 簡介 ……………………………………….. 42 3.3.2 採用 Radial Basis Function（RBF）來解 Implicit Function ... 42 3.3.3 由 Implicit Function 計算 Volume Value ………………….. 46 3.4 3D小波轉換（3D Wavelet Transform） ……………………………. 48 3.4.1 小波簡介 ……………………………………………………. 49 3.4.2 小波在本論文的應用 ………………………………………. 50 3.4.3 採用小波的優點 ……………………………………………. 52 3.5 均勻且規則化的取樣 …………………………………………….. 54 3.5.1 內差 Implicit Surface 的表面點 …………………………... 55 3.5.2 法向量的取得 ………………………………………………. 55 3.5.3 移動至格子點 ………………………………………………. 56 3.6 建立更精細的表面 ……………………………………………….. 59 3.7 建立 Mesh 並壓縮資料 …………………………………………. 61 3.7.1 想法概念 ……………………………………………………. 61 3.7.2 立方體處理 …………………………………………………. 61 3.7.2.1 遊走立方體 …………………………………………. 62 3.7.2.2 Four Samples Cube …………………………………... 63 3.7.2.3 Three Samples Cube ………………………………….. 65 3.7.2.4 混合型討論 …………………………………………. 66 3.7.3 編碼細節 ……………………………………………………. 67 3.7.4 判斷流程 ……………………………………………………. 69 3.7.4.1 Pseudo Code ………………………………………….. 69 3.7.4.2 流程圖 ………………………………………………. 72 3.7.5 細節探討 ……………………………………………………. 74 3.7.6 Mesh 作法 …………………………………………………... 77 3.7.7 取樣密度 ……………………………………………………. 79 3.7.8 Marching Cube 探討 ………………………………………... 80 3.7.9 Mesh 相連性問題 ……………………………………………81 第四章. Camera Sampling Field（CSF） ……………….……………………… 84 4.1 相機取樣場（Camera Sampling Field） .……………….………….. 84 4.2 3D Camera Sampling Field …………………….…………………... 86 4.3 Splat Size 計算 ……………………………………………………. 87 4.4 橢圓長短軸計算 ………………………………………………….. 89 4.5 Splat Size 與點的密度 ……………………………………………. 90 第五章. 顯像技術演算法 …………………………………………….………… 92 5.1 Frame Coherence Rendering ………………….……………………. 92 5.1.1 細節作法 ……………………………………………………. 92 5.1.2 Pseudo Code ………………………………………………….. 93 5.2 可見度裁切（Visibility Culling）……….…………………………... 94 5.2.1 Backface Culling ……………………………………………... 94 5.2.2 View Frustum Culling ………………………………………... 96 5.3 均勻且動態增加點的程序………………….……………………... 96 5.4 輪廓加強處理 …………………………………………………… 100 5.5 動態Splat Size 大小調整 ………………………………………. 101 5.6 Splat 形狀（Splat Shape）………………………………………….. 103 5.7 Rendering細節說明 ……………………………………………… 105 第六章. 實驗結果、分析比較與討論 ………………………….……………… 108 6.1 實驗結果 ………………………………………………………… 108 6.2 分析比較與討論 ………………………………………………… 117 第七章. 結論及未來工作 ……………………………………….…………….. 126 ■ 參考文獻 …………………………………………………………………….. 127 ■ 附錄A – 程式介面與使用 ………………………………………………….. 132

    [1] M. DeHaemer and M. Zyda, “Simplification of Objects Rendered by Polygonal Approximations”, Computer Graphics, 1991.
    [2] J. Cohen, A. Varshney, D. Manocha, G. Turk, H. Weber, P. Agarwal, F. Brooks and W. Wright, “Simplification Envelopes”, Computer Graphics, SIGGRAPHICS ’96, 1996.
    [3] M. Garland, P. Heckbert, “Surface Simplification using Wuadric Error Bounds”, Computer Graphics, SIGGRAPHICS ’97, 1997.
    [4] H. Hoppe, “View-Dependent Refinement of Progressive Meshes”, Computer Graphics, SIGGRAPHICS ’97, 1997.
    [5] S. Rusinkiewicz and M. Levoy, “QSplat: A Multiresolution Point Rendering System for Lage Meshes”, SIGGRAPH ’00 Proc., page 343-352,2000.
    [6] B. Chen and M. X. Nguyen, “POP: A Hybrid Point and Polygon Rendering System for Large Data”, IEEE Visualization 2001.
    [7] M. Alexa, J. Behr, D. Cohen-Or, S. Fleishman, D. Levin and C. T. Silva, ”Computing and Rendering Point Set Surfaces”, IEEE Visualization 2001, pages 21 28, October 2001.
    [8] H. Pfister, M. Zwicker, J. V. Baar and M. Gross, “Surfels: Surface Elements as Rendering Primitives”, SIGGRAPH ’00 Proc., page 335-342, 2000.
    [9] A. Kalaiah and A. Varshney, “Differential Point Rendering”, Proc. Eurographics Rendering Workshop, 2001.
    [10] M. Wand, M. Fischer, I. Peter, F. M. A. D. Heide and W. StraBer, “The Randomized z-Buffer Algorithm: Interactive Rendering of Highly Complex Scenes”, SIGGRAPH 2001 Conference Proceedings.
    [11] M. Stamminger and G. Drettakis, “Interactive Sampling and Rendering for Complex and Procedural Geometry”, Eurographics 2001.
    [12] J.P. Grossman, William J. Dally, "Point Sample Rendering", Proc. 9th Eurographics Workshop on Rendering, June 1998, page 181-192.
    [13] J. H. Clark, “Hierarchical Geometric Models for Visible Algorithms”, Communication of the ACM, 1976
    [14] S. Kumar, D. Manocha, B. Garrett, M. Lin, “Hierarchical Back-Face Culling”, Computer Science department of unc.
    [15] D. Cohen-Or, G. Fibich, D. Halperin and E. Zadicario, “Conservative Visibility and Strong Occlusion for Viewspace Partitioning of Densely Occluded Scenes”, EUROGRAPHIC ’98.
    [16] V. Doltun, Y. Chrysanthou and D. Cohen-Or, “Virtual Occluders: An Efficient Intermediate PVS Representation”, 2000.
    [17] S. Teller and C. Sequin. “Visibility Preprocessing for Interactive Walkthroughts”, Processing of ACM SIGGRAPH 91.
    [18] N. Greene, M. Kass and G. Miller, “Hierarchical Z-Buffer Visibility”, Processing of COMPUTER GRAPHICS.
    [19] M. Levoy and T. Whitted, “The Use of Points as a Display Primitive”, Technical Report TR 85-022, University of North Carolina at Chapel Hill, 1985.
    [20] C. Csuri, R. Hackathorn, R. Parent, W. Carlson and M. Howard, “Towards an Interactive High Visual Complexity Animation System”, Proc. SIGGRAPH, 1979.
    [21] W. Reeves, “Particle Systems – A Technique for Modeling a Class of Fuzzy Objects”, Proc. SIGGRAPH, 1983.
    [22] N. Max and K. Ohsaki, “Rendering Trees from Precomputed Zbu.er Views” Proc. Eurographics Rendering Workshop, 1995.
    [23] L. Westover, “Interactive Volume Rendering“, Proc. Volume Visualization Workshop, University of North Carolina at Chapel Hill, 1989.
    [24] D. Laur and P. Hanrahan, “Hierarchical Splatting: A Progressive Refinement Algorithm for Volume Rendering”, Proc. SIGGRAPH, 1991.
    [25] J. Shade, S. Gortler, L. W. He and R. Szeliski, “Layered Depth Images”, SIGGRAPH ’98.
    [26] L. McMillan and G. Bishop, “Plenoptic Modeling: An Image-Based Rendering System”, SIGGRAPH ’95, page 39-46, August 1995.
    [27] G. Schaufler and W. Stirzlinger, “A Three Dimension Image Cache for Virtual Reality”, Processings of Eurographics ’96, page 227-235.
    [28] R. Szeliski and H. Y. Shum, “Creating Full View Panoramic Image Mosaics and Environments Maps”, SIGGRAPH ’97, page 251-256, August 1997.
    [29] J. Shande, D. Lischinski, D. Salesin, T. DeRose and J. Snyder, “Hierarchical Image Caching for Accelerated Walkthroughts of Complex Environments”, SIGGRAPH ’96, page 75-82, august 1996.
    [30] F.Sillion, G. Frettakis and B. Bodelet, ”Efficient Impostor Manipulation for Real-Time Visualization of Urban Scenery”, Eurographics ’97.
    [31] S. E. Chen and L. Williams, “View Interpolation for Image Synthesis”, SIGGRAPH ’93.
    [32] H. Y. Seng and L. W. He, “Rendering with Concentric Mosaics”, SIGGRAPH ’99.
    [33] L. McMillan, “An Image-Based Approach to Three- Dimensional Computer Graphics”, PHD thesis, University of North Carolina at Chapel Hill, 1997.
    [34] Chang, Chun-Fa, G. Bishop and A. Lestra, “LDI Tree: A Hierarchical Repressentation for Image-Based Rendering”, Proc. of SIGGRAPH ’99.
    [35] M. Regan and R. Pose, “Priority Rendering with a Virtual Reality Address Recalculation Pipeline”, Proc. Of ACM SIGGRAPH ’94.
    [36] D. G. Aliaga, A. Lastra. “Automatic Image Placement to Provide A Guaranteed Frame Rate”, Proc. Of SIGGRAPH ’99, Los Angeles, August 11-13,1999.
    [37] L. Shirman and S. Abi-Ezzi, “The Cone of Normals Technique for Fast Processing of Curved Patchs”, Proc. Eurographics, 1993.
    [38] D. Levin, “Mesh-Independent Surface Interpolation”, Advances in Computational Mathematics, in press, 2001.
    [39] S. P. Lloyd, “least squares quantization in PCM”, IEEE Transactions on Information Theory, 28:128-137, 1982.
    [40] S. Kumar, D. Manocha, W. Garrett and M. Lin, “Hierachical back-face Computation”, In X. Pueyo and P. Schroder, editors, Eurographics Rendering Workshop 1996, page 235-244, New York City, NY, June 1996, Eurographics, Soringer Wien.
    [41] D. Lischinski and A. Rappoport, “Image-Based Rendering for Non-Diffuse Synthetic”, In Rendering Techniques ’98, page 301-314, Springer, Wien, Bienna, Austria, June 1998.
    [42] J. P. Grossman, “Point Sample Rendering”, Master’s thesis, Department of Electrical Engineering and Computer Science, MIT, August 1998.
    [43] M. P. do Carmo, “Differential Geometry of Curves and Surfaces”, Prentice-Hall. Inc., Englewood Cliffs, New Jersey, 1976.
    [44] M. Pauly and M. Gross, ”Spectral Processing of Point-Sampled Geometry”, SIGGRAPH 2001.
    [45] J. C. Carr, R. K. Beatson, J. B. Cherrie, T. J. Mitchell, W. R. Fright and B. C. McCallum, “Reconstruction and Representation of 3D Objects with Radial Basis Functions”, ACM SIGGRAPH 2001, 12-17, Auguest 2001.
    [46] G. Turk and James F. O’Brien, “Shape Transformation Using Variation Implicit Function”, ACM SIGGRAPH ’99, 1999.
    [47] N. Dyn, D. Levin and S. Rippa, “Numerical Procedures for Surface Fitting of Scattered Data by Radial Functions”, SIAM J. Sci. Stat Comput, 639-659, 1986.
    [48] J. Flusser, “An Adaptive Method for image registration”, Pattern Recognition, 45-54, 1992.
    [49] R. Sibson and G. Stone. Computation of thin-plate splines. SIAM J. Sci. Stat. Comput, 1304-1313, 1991.
    [50] Ping-Hsien Lin and Tong-Yee Lee, “Splat Size Decision for Image-Based Rendering through Sampling Density Analysis”, CGVIP 2001.

    下載圖示 校內：立即公開
    校外：2002-08-22公開
    QR CODE