跳到主要內容

臺灣博碩士論文加值系統

(34.204.176.71) 您好!臺灣時間:2024/11/07 23:56
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:康正道
研究生(外文):Cheng-Tao Kang
論文名稱:利用多重3D掃描資料建構數位牙齒模型之網格架構系統
論文名稱(外文):A Triangle-Based System to the Creation of Digital Tooth Models from Multi-View 3D Scanned Data
指導教授:姚宏宗姚宏宗引用關係
指導教授(外文):H. T. Yau
學位類別:碩士
校院名稱:國立中正大學
系所名稱:機械工程所
學門:工程學門
學類:機械工程學類
論文種類:學術論文
論文出版年:2010
畢業學年度:98
語文別:中文
論文頁數:141
中文關鍵詞:網格模型資料壓縮齒模掃描資料定位繪圖硬體亂點資料重建
外文關鍵詞:surface reconstructionmulti-view registrationTooth Modeltriangle mesh compressiongraphics processing unit
相關次數:
  • 被引用被引用:1
  • 點閱點閱:868
  • 評分評分:
  • 下載下載:168
  • 收藏至我的研究室書目清單書目收藏:0
本論文針對齒模開發出一套具有良好效率與符合精度的數位模型重建系統。該系統整合多筆掃描點資料定位、亂點資料重建網格模型與網格模型資料壓縮演算法。
在多筆掃描點資料定位的演算法中,針對機械定位後的掃描點資料,採用Global ICP(Iterative Closest Point)演算法,改善傳統將多重掃描點資料以ICP演算法兩兩相定位所產生的累積誤差。而後在亂點資料重建網格模型中,則透過Hybrid的概念,結合因內插於取樣點而建構出較高精度網格模型的DBRG(Delaunay-Based Region-Growing)與僅考慮一次所有點資料而非分區域的計算,所以可有效處理雜訊的Poisson兩種演算法,此外更利用繪圖硬體加速計算Poisson來提升整體重建的效率。最後在網格模型資料壓縮的流程中,則透過Edgebreaker演算法,藉由移除網格,並記錄剩下的網格與其邊界拓撲關係來達成有效率的壓縮效果。
因此本系統可提升定位的精確度與成功率、建立出高效率與高精度的網格模型,最後亦可有效地壓縮三角網格的拓撲資料,代替以往儲存三角網格資料時,所需要耗費較大的記憶體空間,以減少傳輸所花費的時間,提升產業競爭力。
In this paper, a digital model reconstruction system is developed for the use in tooth model. This proposed system includes the multi-view registration, surface reconstruction and triangle mesh compression.
For the multi-view registration, the mechanical positioning scan data, the traditional method calculates a transformation for each view separately, but the diffusing errors are generated in the alignment. Therefore, the global iterative closet point (ICP) algorithm is used to improve the accumulative errors. For the surface reconstruction, The Delaunay-Based Region-Growing (DBRG) method interpolates sample points and thus easily meets the accuracy requirement of model representation. On the other hand, the Poisson method considers all the points at once, without resorting to heuristic spatial partitioning or blending, and is therefore highly resilient to data noise. Thus, a hybrid method which combines the DBRG method with the Poisson method is proposed in this paper. Moreover, the Poisson in hybrid method is accelerated using graphics processing unit (GPU). For the triangle mesh compression, the Edgebreaker algorithm is applied in this system. The algorithm can produce efficiently a compressed file describing the topological relation between the current triangle and the boundary of the remaining part of the mesh.
Therefore, the proposed system can’t only raise powerfully the accuracy for the multi-view registration but also reconstruct efficiently mesh model for the surface reconstruction. Moreover, the system provides a simple and effective compression which can decrease the memory used to store the mesh model. Finally, the system can’t reduce transmission time, but also improve the industrial competitiveness.
中文摘要 i
Abstract ii
目錄 iii
圖目錄 v
表目錄 viii
第一章 緒論 1
1-1研究動機 3
1-2研究目的 5
1-3文獻回顧 8
1-3-1多筆掃描點資料定位 8
1-3-2亂點資料重建網格模型 9
1-3-3網格模型資料壓縮 17
1-4研究方法 23
第二章 平行處理概論 26
2-1平行處理 26
2-2 GPGPU概念 32
2-3 CUDA程式架構 35
2-4 CUDA的記憶體模型 39
2-5 CUDA的優缺點 41
第三章 多筆掃描資料定位 44
3-1初始定位 45
3-2精確定位 47
第四章 重建數位模型 54
4-1 DBRG演算法 56
4-2 Poisson演算法 60
4-3指向函數(Indicator Function) 62
4-3-1指向函數的梯度場 62
4-3-2逼近梯度場 64
4-4實作演算法 66
4-4-1資料結構 66
4-4-2空間函數 68
4-4-3基底函數 69
4-4-4定義向量場 70
4-4-5計算指向函數 71
4-4-6網格萃取 72
4-4-7不均勻點資料 73
4-5硬體加速Poisson演算法 77
4-5-1八元樹資料結構 78
4-5-2節點陣列 80
4-5-3鄰居節點資訊 84
4-5-4計算向量場、Divergence 87
4-5-5解矩陣與隱函數值 90
4-5-6擷取等值面 92
4.6 Hybrid重建方式 95
第五章 網格壓縮 99
5-1模型拓撲 99
5-2半邊結構(Half-Edge) 102
5-3網格壓縮 104
5-4解壓縮 107
5-4-1前處理(Preprocessing) 107
5-4-2生成網格(Generation) 110
第六章 成果分析與展示 112
6-1精細定位(ICP) 113
6-2模型拓撲重建 116
6-3網格壓縮 123
6-4結果展示 126
第七章 結論與未來展望 131
7-1結論 131
7-2未來展望 134
參考文獻 138
【1】K. Pulli, “Multiview registration for large data sets”, 3-D Digital Imaging and Modeling Conference, pp. 160-168, 1999.
【2】N. Gelfand, L. Ikemoto, S. Rusinkiewicz and M. Levoy, “Geometrically stable sampling for the ICP algorithm”, 3-D Digital Imaging and Modeling Conference, pp. 260-267, 2003.
【3】N. Amenta, M. Bern and M. Kamvysselisy, “A new voronoi-based surface reconstruction algorithm”, Computer Graphics and Interactive Techniques Conference, pp. 415-421, 1998.
【4】N. Amenta, S. Choi and R. K. Kolluri, “The power crust, unions of balls, and the medial axis transform”, Computational Geometry, Vol. 19, No. 2, pp. 127-153, 2001.
【5】R. Kolluri, J. R. Shewchuk and J. F. O''Brien, “Spectral surface reconstruction from noisy point clouds”, Geometry processing Conference, Vol. 71, pp. 11-21, 2004.
【6】C. C. Kuo and H. T. Yau, “Reconstruction of virtual parts from unorganized scanned data for automated dimensional Inspection”, ASME/ACM Transaction, Journal of Computing and Information Science in Engineering, Vol. 3, No. 1, pp. 76-86, 2003.
【7】T. Itoh and Y. Kanda, “Surface reconstruction from 3D scattered points with normals using both delaunay tetrahedralization and implicit function”, International Conference on System Simulation and Scientific Computing, Asia Simulation Conference, pp. 950-955, 2008.
【8】H. Hoppe, T. DeRose, T. Duchampy, J. McDonaldz and W. Stuetzle, “Surface reconstruction from unorganized points”, Computer Graphics and Interactive Techniques Conference, Vol. 26, No. 2, pp. 71-78, 1992.
【9】C. L. Bajaj, F. Bernardini and G. Xu, “Automatic reconstruction of surfaces and scalar fields from 3D scans”, Computer Graphics and Interactive Techniques Conference, pp. 109-118, 1995.
【10】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”, Computer Graphics and Interactive Techniques Conference, pp. 67-76, 2001.
【11】M. Alexa, J. Behr, D. Cohen-Or, S. Fleishman, D. Levin and C. T. Silva, “Point set surfaces”, Visualization Conference, pp. 21-28, 2001.
【12】M. Kazhdan, M. Bolitho and H. Hoppe, “Poisson surface reconstruction”, Geometry Processing Conference, Vol. 256, pp. 61-70, 2006.
【13】K. Zhou, M. Gong, X. Huang and B. Guo, “Highly parallel surface reconstruction”, Microsoft Research Asia, MSR-TR-2008-53, 2008.
【14】J. D. Boissonnat, “Geometric structures for three-dimensional shape representation”, ACM Transaction on Graphics, Vol. 3, No. 4, pp. 266-286, 1984.
【15】E. Mencl and H. Müller, “Graph-based surface reconstruction using structures in scattered point sets”, Computer Graphics International, pp. 298-311, 1998.
【16】M. Gopi and S. Krishnan, “A fast and efficient projection-based approach for surface reconstruction”, International Journal of High Performance Computer Graphics, Multimedia and Visualisation, Vol. 1, No. 1, pp. 1-12, 2000.
【17】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, Vol. 5, No. 4 , pp. 349-359, 1999.
【18】C. C. Kuo and H. T. Yau, “A delaunay-based region-growing approach to surface reconstruction from unorganized points”, Computer-Aided Design, Vol. 37, No. 8, pp. 825-835, 2005.
【19】C. C. Kuo and H. T. Yau, “A new combinatorial approach to surface reconstruction with sharp features”, Visualization and Computer Graphics, Vol. 12, No. 1, pp. 73-82, 2006.
【20】M. Deering, “Geometry compression”, Computer Graphics and Interactive Techniques Conference, pp. 13-20, 1995.
【21】G. Taubin and J. Rossignac, “Geometric compression through topological surgery”, ACM Transactions on Graphics, Vol. 17, No. 2, pp. 84-115, 1998.
【22】M. Chaw, “Optimized geometry compression for real-time rendering”, IEEE Visualization, pp. 347-354, 1997.
【23】H. Hoppe, “Progressive meshes”, Computer Graphics and Interactive Techniques Conference, pp. 99-108, 1996.
【24】G. Taubin, A. Gueziec, W. Horn and F. Lazarus, “Progressive forest split compression”, Computer Graphics and Interactive Techniques Conference, pp. 123-132, 1998.
【25】G. Taubin, W. Horn, F. Lazarus and J. Rossignac, “Geometry coding and VRML”, Proceedings of the IEEE, Vol. 86, No. 6, pp. 1228-1243, 1998.
【26】S. Gumhold and W. Strasser, “Real time compression of triangle mesh connectivity”, Computer Graphics and Interactive Techniques Conference, pp. 133-140, 1998.
【27】J. Rossignac, “Edgebreaker: connectivity compression for triangle meshes”, IEEE Transactions on Visualization and Computer Graphics, Vol. 5, No. 1, pp. 47-61, 1999.
【28】M. Isenburg, “Triangle strip compression”, Journal of Computer Graphics Forum, Vol. 20, No. 2, pp. 91-101, 2001.
【29】W. E. Lorensen and H. E. Cline, “Marching cubes: a high resolution 3D surface reconstruction algorithm”, ACM SIGGRAPH Computer Graphics, Vol. 21, No. 4, pp. 163-169, 1987.
【30】M. Kazhdan, “Reconstruction of solid models from oriented point sets”, Geometry processing Conference, Vol. 255, pp. 73-82, 2005.
【31】J. Wilhelms and A. V. Gelder, “Octrees for faster isosurface generation”, Transactions on Graphics, Vol. 24, No. 5, 1992, 201-227.
【32】J. Bolz, I. Farmer, E. Grinspun and P. Schröder, “Sparse matrix solvers on the GPU: conjugate gradients and multigrid”, ACM Transactions on Graphics, Vol. 22, No. 3, pp. 917-924, 2003.
【33】NVIDIA CUDA compute unified device architecture programming guide, NVIDIA Corporation, 2010.
【34】CUDA. [Online]. Available: http://zh.wikipedia.org/zh/CUDA.
【35】CUDA. [Online]. Available: http://www2.kimicat.com/home.
【36】(2007) CUDPP::GPGPU.org. [Online]. Available: http://gpgpu.org/developer/cudpp.
【37】陳俊諺, “利用3D多重掃描資料建構多面體架構之實體模型”, 國立中正大學, 2000.
【38】平行處理應用簡介. [Online]. Available: http://www.cc.ntu.edu.tw/chinese/epaper/0012/20100320_1208.htm.
【39】王詔緯, “三角網格補洞在數位模型上之應用”, 國立中正大學, 2010.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top