逆向工程之網格修復與特徵邊界追蹤技術發展

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：75

、訪客IP：3.147.127.55

姓名

許聖函(Sheng-han Hsu) 查詢紙本館藏

畢業系所

機械工程學系

論文名稱

逆向工程之網格修復與特徵邊界追蹤技術發展
(Development of Mesh Repair and Feature Edge Tracking Techniques in Reverse Engineering)

相關論文

★ 光纖通訊主動元件之光收發模組由上而下CAD模型設計流程探討	★ 汽車鈑金焊接之夾治具精度分析與改善
★ 輪胎模具反型加工路徑規劃之整合研究	★ 自動化活塞扣環壓入設備之開發
★ 光學鏡片模具設計製造與射出成形最佳化研究	★ CAD模型基礎擠出物之實體網格自動化建構技術發展
★ 塑膠射出薄殼件之CAD模型凸起面特徵辨識與分模應用技術發展	★ 塑膠射出成型之薄殼件中肋與管設計可製造化分析與設計變更技術研究
★ 以二維影像重建三維彩色模型之色彩紋理貼圖技術與三維模型重建系統發展	★ 結合田口法與反應曲面法之光學鏡片射出成型製程參數最佳化分析
★ 薄殼零件薄殼本體之結構化實體網格自動建構技術發展	★ Boss特徵之結構化實體網格自動化建構技術發展
★ 應用於模流分析之薄殼元件CAD模型特徵辨識與分解技術發展	★ 實體網格建構對於塑膠光學元件模流分析之影響探討
★ 螺槳葉片逆向工程CAD模型重建與檢測	★ 電腦輔助紋理影像辨識與點資料視覺化研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

逆向工程是解析成品技術的一門科學，實物經過數位化掃描之後，可得到由量測點組成的三角網格模型，最後經過曲線與曲面的處理而產生CAD模型。然而，量測資料由於精度限制、人為失誤、掃描死角或是其它因素，必須對量測資料進行處理，以確保三角網格品質，並從中萃取出所需的點資料，提供CAD模型重建所需的參考，因此本論文對量測網格資料前處理進行研究，並探討其中兩個關鍵問題：網格修復與網格特徵追蹤。
在網格修復方面，本研究提出孔洞的核心修補演算法，依據修補面需求的不同而發展對應的修補演算法，以增加補洞的效率與穩定性，並兼顧修補面的平滑性與接合處的平順，此外，真實掃描資料網格會有各種特殊的狀況與更多的應用需求，因此本研究整理出10種問題網格的形式，並提出對應解決方法，以建立完整的網格修復整合方案。在網格特徵追蹤方面，本研究發展半自動特徵搜尋演算法以取代傳統的全自動特徵搜尋演算法，只需要在特徵上點選一個種子點，演算法即可自動追蹤出所在特徵的路徑，在搜尋過程中，會由種子點為起點往四周搜尋路徑，並定義成本函式估算路徑的好壞，成本函式除了考量特徵之外也考慮路徑的品質與穩定性，路徑擴展則採用雙向多段的搜尋方式，提昇了搜尋的效率。本研究演算法皆透過大量實際掃描資料測試，證明方法的可行性與適應性。

摘要(英)

Reverse engineering is a process of reconstructing a 3D virtual model from digitalizating an existing physical part, in which scanned data are acquired by a scanning device. A triangular mesh, composed of scanned data and topology information, is built then. Owning to device limitation and improper operation, some mesh problems might occur frequently and it is hard to obtain key curves and surfaces, used to reconstruct 3D CAD model, from the triangular mesh. Hence, this study aims to solve mesh problems, focusing on two important mesh processes：quality repair and feature tracking.
As for quality repair, this study develops a hole-filling method that automatically chooses the specific algorithm depending on the type of the hole. While the hole is small and simple, the efficiency-oriented algorithm is implemented. While the hole is huge and complicate, the quality-oriented algorithm can be implemented to acquire a smooth filled mesh that has good connectivity with the original mesh. Moreover, this study analyses numerous real scanned data and induct ten type mesh problems that affect mesh quality. To solve these mesh problems, this study proposes a comprehensive method. As for feature tracking, this study proposes a new semi-automatic feature detection algorithm using one seed point to provide precise searching for feature points. A search graph, containing nodes and its access relationship, provides the candidate points for the search process. A bi-directional, multi-segment search strategy is then proposed to determine the optimized feature path. The cost function is essentially composed of four terms. The first two terms are employed to track the nodes of similar maximum curvatures and directions of minimum curvature variation, while the last two terms are employed to stabilize the path. In sum, this study demonstrates the feasibility of this approach through a great number of testing trials.

關鍵字(中)

★ 逆向工程
★ 三角網格
★ 補洞
★ 特徵搜尋
★ 啟發式搜尋

關鍵字(英)

★ Reverse Engineering
★ Triangular Mesh
★ Hole-filling
★ Feature Detection
★ Heuristic Search

論文目次

目錄
摘要 I
ABSTRACT II
致謝 IV
目錄 V
圖目錄 VIII
表目錄 XVI
第一章緒論 1
1-1 前言 1
1-2 文獻回顧 7
1-2-1 網格補洞 7
1-2-2 特徵擷取 8
1-3 研究目的與方法 13
1-3-1 網格修復 13
1-3-2 網格特徵追蹤 18
1-4 論文架構 22
第二章網格補洞演算法 24
2-1 前言 24
2-2 孔洞辨識 27
2-3 線性補洞演算法 31
2-3-1 孔洞點網格化 31
2-3-2 內插修補面方法 37
2-4 LMLS補洞演算法 42
2-5 複合曲面補洞演算法 47
2-6 範例 52
2-7 結論 54
第三章網格孔洞修復整合方法 64
3-1 前言 64
3-2 自動化補洞方法 65
3-2-1 孔洞前處理 66
3-2-2 不依曲率補洞流程 71
3-2-3 依曲率補洞流程 72
3-3 半自動網格修剪方法 76
3-3-1 擴張孔洞 76
3-3-2 網格依關聯性分離 77
3-4 孔洞橋接方法 85
3-4-1 橋接線演算法 85
3-4-2 分區補洞 90
3-4-3 橋接補洞 97
3-5 導引式補洞方法 103
3-6 結論 108
第四章網格測地線與特徵追蹤方法 110
4-1 前言 110
4-2 拓樸結構介紹 110
4-3 啟發式搜尋方法 114
4-4 以網格為基礎之A*搜尋演算法 118
4-5 多種子點之特徵搜尋方法 123
4-5-1 離散曲率計算 123
4-5-2 特徵目標函式計算 125
4-6 範例 130
4-7 結論 142
第五章單種子點之網格特徵追蹤方法 143
5-1 前言 143
5-2 建立節點 145
5-3 建立節點關聯性 150
5-4 路徑搜尋 153
5-4-1 搜尋流程 153
5-4-2 成本函式 161
5-4-3 路徑搜尋附加法則 166
5-4-4 路徑平滑 168
5-5 範例與討論 169
5-6 結論 185
第六章結論與未來展望 186
6-1 結論 186
6-2 未來展望 192
參考文獻 194
許聖函個人簡歷 200

參考文獻

[1] M. Botsch, M. Pauly, L. Kobbelt , P. Alliez, B. Lévy, S. Bischoff and C. Rössl, “Geometric Modeling Based on Polygonal Meshes”, Proceedings of the International Conference on Computer Graphics and Interactive Techniques, ACM SIGGRAPH 2007 Course Notes, 2007.
[2] J. Davies, S. Marschner, M. Garr and M. Levoy, “Filling Holes in Complex Surface Using Volumetric Diffusion”, Proceedings of First International Symposium on 3D Data Processing Visualization and Transmission, pp. 428-438, 2002.
[3] M. Bertalmio, G. Shapiro, V. Caselles and C. Ballester, “Image Inpainting”, Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques, pp. 417-424, 2000.
[4] J. Verdera, V. Caselles, M. Bertalmio and G. Sapiro, “Inpainting Surface Holes”, Proceedings of IEEE International Conference on Image Processing, pp. 903-906, 2003.
[5] Y. Jun, “A Piecewise Hole Filling Algorithm in Reverse Engineering”, Computer-Aided Design, Vol. 37, No. 2, pp. 263-270, 2005.
[6] B. Girod, G. Greiner and H. Niemann, “Principles of 3D Image Analysis and Synthesis”, The International Series in Engineering and Computer Science, Vol. 556, Springer-Verlag Inc., New York, USA, 2000.
[7] J. Wang and O. Manuel, “A Hole Filling Strategy for Reconstruction of Smooth Surfaces in Range Images”, Proceedings of XVI Brazilian Symposium on Computer Graphics and Image Processing, pp. 11-18, 2003.
[8] P. Lancaster and K. Salkauskas, Curve and Surface Fitting - An Introduction, Academic Press Inc., Orlando FL, USA, 1986.
[9] J. Wang, O. Manuel and M. Oliverira, “Filling Holes on Locally Smooth Surface Reconstruction from Point Clouds”, Image and Vision Computing, Vol. 25, No. 1, pp. 103-113, 2007.
[10] T. Ju, “Robust Repair of Polygonal Models”, Proceedings of the SIGGRAPH'04, pp. 888-895, 2004.
[11] P. Liepa, “Filling Holes in Meshes”, Proceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, pp. 200-205, 2003.
[12] A. Sharf, M. Alexa and D. Cohen-Or, “Context-Based Surface Completion”, Proceedings of the SIGGRAPH'04, pp. 878-887, 2004.
[13] L. S. Tekumalla and E. Cohen, “A Hole-Filling Algorithm for Triangular Meshes”, Technical Report, UUCS-04-019, School of Computing, University of Utah, 2004.
[14] J. P. Pernot, G. Moraru and P. Véron, “Filling Holes in Meshes Using a Mechanical Model to Simulate the Curvature Variation Minimization”, Computers & Graphics, Vol. 30, No. 6, pp. 892-902, 2006.
[15] X. Chen, F. Schmitt, “Intrinsic Surface Properties from Surface Triangulation”, Proceedings of European Conference on Computer Vision, pp. 739-743, 1992.
[16] G. Lavoue, F. Dupont and A. Baskurt, “Curvature Tensor Based Triangle Mesh Segmentation with Boundary Rectification”, Proceedings of the Computer Graphics International, pp. 10-17, 2004.
[17] J. A. Thorpe, Elementary Topics in Differential Geometry, Springer, N.Y., 1979.
[18] G. Taubin., “Estimating the Tensor of Curvature of a Surface from a Polyhedral Approximation”, Proceedings of 5th International Conference on Computer Vision, pp. 902-907, 1995.
[19] K. Watanabe and A. Belyaev, “Detection of Salient Curvature Features on Polygonal Surfaces”, Computer Graphics Forum, Vol. 20, No. 3, pp. 385-392, 2001.
[20] P. Krsek, G. Lukács and R. R. Martin, “Algorithms for Computing Curvatures from Range Data”, Proceedings of the Mathematics of Surfaces VIII, pp. 1-16, 1998.
[21] T. Langer, A. G. Belyaev and H. P. Seidel, “Exact and Approximate Quadratures for Curvature Tensor Estimation”, Proceedings of Vision, Modeling, and Visualization 2005, pp. 421-428, 2005.
[22] J. F. Canny, “Finding Edges and Lines in Images”, Technical Report, TR. 720, Massachusetts Institute of Technology, 1983.
[23] R. Deriche, “Using Canny's Criteria to Derive a Recursively Implemented Optimal Edge Detector”, International Journal of Computer Vision, Vol. 1, No. 2, pp. 167-187, 1987.
[24] O. Monga and R. Deriche, “3D Edge Detection Using Recursive Filtering: Application to Scanner Images”, Proceedings of Computer Vision and Pattern Recognition, pp. 28-35, 1989.
[25] P. Saint-Marc and J. S. Chen, “Adaptive Smoothing: a General Tool for Early Vision”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 13, No. 6, pp. 514-529, 1991.
[26] A. G. Belyaev and E. Anoshkina, “Detection of Surface Creases in Range Data”, Proceedings of the Mathematics of Surfaces XI, Vol. 3604, pp. 50-61, 2005.
[27] Y. Ohtake and A. Belyaev “Automatic Detection of Geodesic Ridges and Ravines on Polygonal Surfaces”, The Journal of Three Dimensional Images, Vol. 15, No. 1, pp. 127-132, 2001.
[28] G. Lukács and L. Andor, “Computing Natural Division Lines on Free-Form Surfaces Based on Measured Data”, Proceedings of the International Conference on Mathematical Methods for Curves and Surfaces II Lillehammer, pp. 319-326, 1997.
[29] M. Garland and P. S. Heckbert, “Surface Simplification Using Quadric Error Metrics”, Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques, pp. 209-216, 1997.
[30] M. Garland and P. S. Heckbert, “Quadric-Based Polygonal Surface Simplification”, Ph.D. Dissertation, Carnegie Mellon University, 1999.
[31] E. V. Anoshkina, A. G. Belyaev and T. L. Kunii, “Detection of Ridges and Ravines Based on Caustic Singularities”, International Journal of Shape Modeling, Vol. 1, No. 1, pp. 13-22, 1994.
[32] E. V. Anoshkina, A. G. Belyaev, O. G. Okunev and T. L. Kunii, “Ridges and Ravines: a Singularity Approach”, International Journal of Shape Modeling, Vol. 1, No. 1, pp. 1-12, 1994.
[33] A. G. Belyaev, Y. Ohtake and K. Abe, “Detection of Ridges and Ravines on Range Images and Triangular Meshes”, Proceedings of SPIE in Vision Geometry IX, Vol. 4117, pp. 146-154, 2000.
[34] G. Stylianou and G. Farin, “Crest Lines Extraction from 3D Triangulated Meshes”, Hierarchical and Geometrical Methods in Scientific Visualization, Springer Verlag, pp. 269-281, 2003.
[35] Y. Ohtake and A. Belyaev, “Automatic Detection of Geodesic Ridges and Ravines on Polygonal Surfaces”, The Journal of Three Dimensional Images, Vol. 15, No. 1, 2001.
[36] Y. Ohtake, A. G. Belyaev and H. P. Seidel, “Ridge-Valley Lines on Meshes Via Implicit Surface Fitting”, ACM Transactions on Graphics, Vol. 23, No. 3, pp. 609-612, 2004.
[37] S. Yoshizawa, A. G. Belyaev and H. P. Seidel, “Fast and Robust Detection of Crest Lines on Meshes”, Proceeding of ACM Symposium on Solid and Physical Modeling, pp. 227-232, 2005.
[38] S. K. Kim and C. H. Kim, “Finding Ridges and Valleys in a Discrete Surface Using a Modified MLS Approximation”, Computer-Aided Design, Vol. 37, No. 14, pp. 1533-1542, 2005.
[39] C. Rössl, L. Kobbelt and H. Seidel, “Extraction of Feature Lines on Triangulated Surfaces Using Morphological Operators”, Proceedings of Smart Graphics 2000, pp. 71-75 (2000).
[40] K. Demarsin, T. Volodine and D. Roose, “Detection of Feature Lines in a Point Cloud by Combination of First Order Segmentation and Graph Theory”, Technical Report, TW 440, Department of Computer Science, K. U. Leuven, Belgium, 2005.
[41] A. Hubeli and M. Gross, “Multiresolution Feature Extraction from Unstructured Meshes”, Proceedings of the conference on Visualization, pp. 287-294, 2001.
[42] L. Kobbelt and M. Botsch, “Feature Sensitive Mesh Processing”, Proceedings of the 19th Spring Conference on Computer Graphics, pp. 17-22, 2003.
[43] Y. W. Guo, Q. S. Peng, G. F. Hu and Jin. Wang, “Smooth Feature Line Detection for Meshes”, Journal of Zhejiang University Science, Vol. 6A, No. 5, pp. 460-468, 2005.
[44] T. Kanai and H. Suzuki, “Approximate Shortest Path on a Polyhedral Surface Based on Selective Refinement of the Discrete Graph and its Applications”, Proceedings of the Geometric Modeling and Processing, pp. 241-250, 2000.
[45] D. Martínez and L. Velho, “Geodesic Paths on Triangular Meshes”, Proceedings of the Computer Graphics and Image Processing, XVII Brazilian Symposium, pp. 210-217, 2004.
[46] G. P. Bonneau and S. Hahmann, “Smooth Polylines on Polygon Meshes”, Geometric Modeling for Scientific, Springer, pp. 69-84, 2003.
[47] I. Semenova, V. Savchenko and I. Hagiwara, “A New Approach for Improvement of Polygonal Meshes Representing Surfaces with Sharp Edges and Boundaries”, JSME International Journal, Series C, Vol. 48, No. 2, pp. 122-129, 2005.
[48] K. J. Chen, J. Y. Lai and W. D. Ueng, “An Extended Surface Fitting Algorithm for Random Data”, Journal of the Chinese Institute of Engineers, Vol. 30, No. 5, pp. 863-876, 2007.
[49] H. Pottmann and S. Leopoldseder, “A Concept for Parametric Surface Fitting which Avoids the Parametrization Problem”, Computer Aided Geometric Design, Vol. 20, No. 6, pp. 343-362, 2003.
[50] E. W. Dijkstra, “A Note on Two Problems in Connection with Graphs”, Numerische Mathematik, Springer Berlin, pp. 269-271, 1959.
[51] J. Pearl, Heuristics Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley Pub. Co., 1984.
[52] S. Russell and P. Norving, Artificial Intelligence: A Modern Approach 2/E, Prentice Hall, Upper Saddle River, N.J., 2003.

指導教授

賴景義(Jiing-Yih Lai)

審核日期

2011-7-7

推文