臺灣博碩士論文加值系統

近年來，隨著電腦科技的進步神速及價格逐漸低廉，虛擬實境的應用已愈來愈熱門。許多物件場景是以三度空間的方式呈現，都能夠獲得身歷其境的逼真效果。諸如：三度空間建築的展示、線上商品的介紹及試用。但很不幸地，真實世界中僅有少部分的物件具有數位的形式。
取材於真實世界的物件，利用外貌重建( Surface Reconstruction)技術，獲得其數位物件是可行的。Hoppe首先在1992提出重建( Reconstruction )的問題；此問題是在三度空間的環境中輸入一系列未組織的頂點集合，利用演算法重建這些頂點成三角化網格( Triangular Mesh )的模組。
在這篇論文中，我們提出一個改良的外貌重建演算法。首先我們依據共曲面的點具有群聚的特徵，計算出每一個點的相鄰點範圍，並找出每一個點的相鄰點作為可能形成三角片的候選點。接著我們先選取一個起始參考點，並測試此參考點與相鄰點之間是否互為相鄰點，以確保能生成三角片﹔當參考點周圍的三角片生成之後，此參考點被記錄為已完成處理的點，且周圍的點之間形成邊界。我們沿著邊界上的點，以廣度優先方式依序選取邊界上的點當作參考點，並逐漸往外長成三角片，而形成物體的外貌輪廓。
我們的重建演算法基於點群聚特徵考量，所以用不著事先對每一個點計算法向量，而改由具相鄰點資格且已完成處理的點的法向量的和，當作參考點的暫時法向量。另外我們的演算法在生成三角片時，是以廣度優先方式依序由邊界上的點往外生成，故我們的方法保證是Manifold，而且可以直接產生已完成幾何壓縮的資訊。實驗證明我們的演算法能夠有效率的重建物體的外貌，且允許有洞的物體之重建。

Recently, the fast progress of computer technology and cost down of prices progressively, “Virtual Reality” becomes so popular. Many scenes of objects are displayed by 3D’s form, there are almost real effect, such as 3D (three dimension) architecture 、the introduction and trial of merchandise on line. Many object models are necessary to display a scene. Unfortunately, only a little objects of the real world have built its digital form.
Therefore users must create digital objects by themselves. To create a digital object, user can use surface reconstruction. It be first proposed on the reconstruction problem by Hoppe in 1992 ; The input is a set of unorganized vertices in 3D, and the output is triangulation mesh models.
In this dissertation, we present a proved surface reconstruction algorithm. At first, we stand on the spatial points cluster characteristic on surface to compute every point’s neighbor boundary. To find out the candidate neighbor which can possibly form triangles and do some test to ensure there can’t have narrow triangles. The point which referenced will be called complete point, and we will continue reconstruct along the boundary point. Therefore we use breadth first search to generate triangles progressively.

第一章 前言…………………………………………………………1
第二章 相關研究探討…………………………………………………5
2.1 Alpha shape 演算法……………………………………………7
2.2 Gopi’s 演算法………………………………………………8
2.3 結論……………………………………………………………9
第三章 相關重建演算法及其使用方法之探討……………………14
3.1 Alpha-shapes演算法之相關方法……………………………15
3.1.1 Voronoi Diagram及Delaunay Triangulation……………15
3.1.2 Edelsbrunner及Mucke’s之Alpha-shapes演算法……17
3.1.3 採用Alpha ball 的缺點………………………………19
3.2 Gopi’s 演算法及其使用的方法………………………………19
3.2.1空間中點的群聚特徵……………………………………20
3.2.2距離函數Q………………………………………………25
3.2.3候選點的選取法則………………………………………27
3.2.4 候選點的選取(Candidate Point Selection)……………29
3.2.5 Gopi 演算法各步驟說明………………………………30
3.3結論……………………………………………………………33
第四章 改良的重建演算法…………………………………………36
4.1 選取ms 範圍內的候選相鄰點………………………………37
4.2 對候選相鄰點作排序…………………………………………38
4.3 決定邊界上下一個參考點的方法…………41
4.4 刪除不需要的候選相鄰點…………………………………42
4.4.1 刪除離參考點p過遠的點……………………………43
4.4.2 測試是否參考點p之相鄰點間互為相鄰點…………44
4.4.3 使用Voronoi Test刪除會形成狹長形三角片的點……45
4.5 三角化…………………………………………………………47
4.6 保證Manifold…………………………………… …………49
4.7 討論……………………………………………………………50
第五章 實作及結果…………………………………………………52
5.1 實作問題的解決……………………………………………52
5.1.1 選取候選點所遇到的問題……………………………52
5.1.2洞的判別………………………………………………53
5.1.3 Manifold 的保證……………………………………55
5.2 結果…………………………………………………………56
第六章 結論與未來展望………………………………………………65
參考文獻……………………………………………………………….67

圖目錄
圖1-1:為取樣的點集合………………………………………………2
圖1-2:為其三角化網格結果…………………………………………2
圖1-3:為其外貌重建後的效果…………………………………………2
圖2-1 :自我交錯的現象……………………………………………10
圖 2-2 :有邊界的Manifold，綠色表示邊界………………………11
圖 2-3 : Non-Manifold的例子………………………………………12
圖 2-4 :簡單多面體例子……………………………………………12
圖 3-1 : 在2D上的Voronoi Diagram ………………………………16
圖 3-2 : Delaunay test………………………………………………17
圖 3-3 : 使用α-shapes 演算法重建物體的步驟………………18
圖 3-4:顯示出 在圓錐體上的示意圖…………………20
圖 3-5:表示 中的點投影到p點的正切平面示意圖………………23
圖 3-6 :表示 ，q點到p點的距離………………………………26
圖 3-7 : 且 且符合 ………………………………27
圖 3-8:為距離函數中 的示意圖………………………………28
圖 3-9: Gopi演算法的流程……………………………………………31
圖 4-1 : 對參考點p，取ms相鄰點的示意圖………………………37
圖 4-2 :點p為以完成點後，計算其法向量…………………………40
圖 4-3 :法向量可由相鄰以完成點代替……………………………40
圖 4-4: 可以生成三角片的區域…………………………………42
圖4-5 :與參考點p互為相鄰點的相鄰點……………………………43
圖 4-6 : 測試p的相鄰點是否互為相鄰點…………………………44
圖 4-7: 以Voronoi Diagram 來判別點遠近的示意圖………………45
圖 4-8: 三角片生成示意圖…………………………………………48
圖 4-9: 理想的三角片生成示意圖…………………………………48
圖 4-10 :符合Manifold的三角片……………………………………50
圖5-1:由於取樣密度無法產生出三角片的例子……………………53
圖5-2 :洞的形成與取樣密度的影響…………………………………54
圖5-3 :演算法所允許產生的三角片…………………………………55
表 1: 結果……………………………………………………………56
圖5-4 :bunny point……………………………………………………57
圖5-5 :bunny triangle………………………………………………57
圖5-6:bunny solid outline……………………………………………58
圖5-7 :bunny hole……………………………………………………58
圖5-8 :bunny ear………………………………………………………59
圖5-9 :bunny back…………………………………………………59
圖5-10 :club point……………………………………………………60
圖5-11 : club triangle…………………………………………………60
圖5-12 :club solid outline……………………………………………61
圖5-13 : club solid……………………………………………………61
圖5-14 : club桿邊有出現一個數字3………………………………62
圖5-15 : club hole…………………………………………………….62
圖5-16 : Car Point……………………………………………………63
圖5-17 : Car Triangle…………………………………………………63
圖5-18 : Car Solid Outline……………………………………………64
圖5-19 : Car Solid……………………………………………………64

[1].B. Curless and M. Levoy. A volumetric method for building complex models from range images. In Proceedings of ACM Siggraph, pages 303–312, 1996.
[2]. B. O’Neill. Elementary Differential Geometry. Academic Press, London, UK, 1966.
[3].C. Bajaj, F. Bernardini, and G. Xu. Automatic reconstruction of surfaces and scalar fields from 3d scans. In Proceedings of ACM Siggraph, pages 109–118, 1995.
[4].Chandrajit L. Bajaj, Fausto Bernardini, Guoliang Xu, “Automatic Reconstruction of Surfaces and Scalar Fields from 3D Scans.” Proceedings of the 22nd annual ACM conference on Computer graphics, Pages 109 - 118, 1995
[5].D. Attali. r-regular shape reconstruction from unorganized points. In ACM Symposium on Computationl Geometry, pages 248–253, 1997.
[6].E. P. Mucke. Shapes and Implementations in Three Dimensional Geometry. PhD thesis, Department of Computer Science, University of Illinois at Urbana-Champaign, 1993.
[7].F. Bernardini, J.Mittleman, H. Rushmeier, C. Silva, and G. Taubin. The ball-pivoting algorithm for surface reconstruction. IEEE Transactions on Visualization and Computer Graphics, 1999.
[8]. Gabriel Taubin ,”3D Geometry Compression and Progressive Transmission ” EUROGRAPHICS ’99
[9].G. M. Voromoi. Nouvelles applications des parameters continues a la theorie des formes quadratiques. Deuxieme Memoire: Recherches sur les parallelloedres primitives. J. Reine Angew.Math.,134:198-287,1908.
[10].H. Edelsbrunner and E. Mucke. Three dimensional alpha shapes. ACM Transactions on Graphics, 13(1):43–72, 1994.
[11].H. Hoppe, T. Derose, T. Duchamp, J. McDonald, and W. Stuetzle. Surface reconstruction from unorganized point clouds. In Proceedings of ACM Siggraph, pages 71–78, 1992.
[12].H. Hoppe, T. Derose, T. Duchamp, J. McDonald, and W. Stuetzle. Mesh optimization. In Proceedings of ACM Siggraph, pages 21–26, 1993.
[13].J.Cohen. �cConcepts and Algorithms for Polygonal Simplification.�cSIGGRAPH 99 Course Tutorial #20: Interactive Walkthroughs of Large Geometric Datasets. pages C1-C34. 1999. also in SIGGRAPH 2000 Course Tutorial.
[14].J. D. Boissonnat. Geometric structures for three dimensional shape representation. ACM Transactions on Graphics, 3(4):266–286, 1984.
[15].J. Koenderink. Solid Shape. MIT Press, 1989.
[16]. Michael Deering.” Geometry Compression “,ACM SIGGRAPH 1995 , p13~p20
[17].M. Gopi and S. Krishnan. A Fast and Efficient Projection-Based Approach for Surface Reconstruction. High Performance Computer Graphics, Multimedia and Visualisation .Vol.1 , No.1 , pages 1-12,2000.
[18].M. Gopi and S. Krishnan C.T.Silva ,Surface Reconstruction based on Lower Dimensional Localized Delaunay Triangulation, EUROGRAPHICS ,Vol 19,No 3, 2000.
[19].M. Teichmann and M. Capps. Surface reconstruction with anisotropic density-scaled alpha shapes. In Proceedings of IEEE Visualization, pages 67–72, 1998.
[20].N. Amenta and M. Bern. Surface reconstruction by voronoi filtering. In ACM Symposium on Computationl Geometry, 1998.
[21].N. Amenta, M. Bern, and M. Kamvysselis. A new voronoi-based surface reconstruction algorithm. In Proceedings of ACM Siggraph, pages 415–421, 1998.
[22].R. Szeliski and D. Tonnesen. Surface modeling with oriented particle systems. In Proceedings of ACM Siggraph, pages 185–194, 1992.
[23].R. Szeliski and D. Tonnesen. Surface modeling with oriented particle systems. In Proceedings of ACM Siggraph, pages 185–194, 1992.
[24].P. Crossno and E. Angel. Spiraling edge: Fast surface reconstruction from partially organized sample points. IEEE Visualization ’99, pages 317–324, October 1999.
[25].W. Schroeder, J. Zarge, and W. Lorensen. �cDecimation of Triangle Meshes.�c ACM Computer Graphics(SIGGRAPH '92 Proceedings), volume 26, pages 65-70, July 1992.