立體幾何模型之三角網格處理技術發展

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：100

、訪客IP：18.226.164.170

姓名

賴後權(Hou-chuan Lai) 查詢紙本館藏

畢業系所

機械工程學系

論文名稱

立體幾何模型之三角網格處理技術發展
(On the Development of Triangle Meshes Processing Techniques for Geometric Models)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

三角網格為三維模型中最常見的模型資料，且廣泛應用於各個領域上，尤其為現階段產品開發流程中最常使用的模型之一。而產品開發流程多整合正向、逆向工程與快速成型製造。然而以逆向工程而言，其流程包含有量測資料、幾何特徵與幾何模型三個步驟，這三個步驟中皆以三角網格模型作為媒介，如量測的資料多以網格模型來表達，幾何特徵中的特徵與分離亦是以網格模型為基礎，而最後的幾何模型重建同樣以特徵分離後的網格模型來進行曲面重建。另外就快速成型製造而言，仍然是以三角網格作為輸出的橋梁。所以依現階段產品開發流程中，三角網格的應用情形，將有關網格的處理與技術分為三個主軸，即為本研究所發展的各項技術且具體說明如下：
(1) 網格錯誤偵錯與修正技術：將錯誤的網格情形分為5種，分別為退化網格、不合理網格邊、自交網格、不完全連接網格與網格法向量不一致。將錯誤網格的類型分類並予以判斷與修正。
(2) 發展網格二次曲面特徵辨識與分離技術：提出以網格頂點法向量與曲率值為基礎，辨識網格模型中的二次曲面特徵並與以分離。
(3) 發展網格局部特徵置換技術：使經過修改或變更過的特徵網格能夠迅速與原始網格替換，達到加速產品設計開發中的修改與確認流程。

摘要(英)

Triangle mesh is a common geometric model and is widely used in the field of engineering, especially in the product development process which involves forward engineering, reverse engineering and rapid prototyping. In reverse engineering, for rxample, the measured data is always saved as triangle meshes. Feature segmentation and surface reconstruction are generally implemented on the base of triangle meshes. Moreover, the input data of a rapid prototyping process is still triangle meshes. In this study, three important problems on triangle meshes wre investigated and appropriate algorithms are developed to deal wth these problems. Specifically, the three problems addressed are as follows:
(1) Repairing triangle meshes: it is an approach to detect and eliminate erroneous facets on triangle meshes. Five types of erroneous facets are identified, namely, degenerate, non-manifold vertices, self-intersection, incomplete connection and inconsistent plane normal. Algorithms for dealing with all these erroneous facets are developed.
(2) Feature segmentation algorithms for quadratic surfaces: it is composed of two steps. First, a region growing is developed to search for a small area near a seed point to determine the feature type, which can be a plane, a spherical surface, a cylindrical surface or a conical surface. Second, a re-growing procedure is employed to search for the points of the same feature type.
(3) Partial mesh replacement: it is composed of three steps: cutting path computation, mesh segmentation and mesh stitching. The cutting path computation is employed to evaluate the intersecting points of all meshes lying under the projection of the boundary curve. Mesh segmentation is employed to divide the original meshes into two parts: preserved and replaced meshes. Mesh stitching is finally employed to sew the boundaries of the preserved and new meshes.

關鍵字(中)

★ 局部特徵置換
★ 網格縫合
★ 網格切割
★ 幾何特徵萃取
★ 錯誤網格

關鍵字(英)

★ geometric feature extraction
★ Erroneous facets
★ mesh stitching
★ mesh segmentation
★ partial mesh replacement

論文目次

摘要 i
ABSTRACT ii
致謝 iv
目錄 v
圖目錄 viii
表目錄 xii
第一章緒論 1
1-1 前言 1
1-2 三角網格的應用領域 5
1-2-1 逆向工程中的應用 5
1-2-2 快速成型中的應用 11
1-2-3 NC加工中的應用 12
1-3 網格資料處理 13
1-4 文獻回顧 15
1-5 研究目的與方法 22
1-6 論文架構 26
第二章網格錯誤偵測與修正 27
2-1 前言 27
2-2 網格資料結構 30
2-2-1 網格點資料分群演算法 31
2-2-2 搜尋演算法 35
2-3 錯誤網格分類和偵測與修正演算法 42
2-3-1 退化網格 42
2-3-2 不合理網格邊 46
2-3-3 自交網格 46
2-3-4 網格不完全連接 54
2-3-5 網格法向量不一致 58
2-4 結果分析與討論 64
第三章網格二次曲面特徵分離 67
3-1 前言 67
3-2 三角網格的幾何特性 68
3-2-1 網格頂點法向量 69
3-2-2 網格頂點的主曲率與方向 72
3-3 二次曲面特徵分離 80
3-3-1 初始區域成長 80
3-3-2 二次曲面特徵辨識與分離 86
3-3-3 結果與範例 97
3-4 平面自動化分離 100
3-4-1 種子點的搜尋與平面成長 101
3-4-2 平面特徵區域分離 102
3-4-3 結果與範例 103
3-5 結果分析與討論 106
第四章網格局部特徵置換 107
4-1 前言 107
4-2 切割路徑計算 112
4-3 網格切割與分離 121
4-3-1 建立網格切割資料表 124
4-3-2 建立多邊形與三角化 128
4-3-3 網格分離 132
4-4 網格縫合 137
4-5 結果與範例 143
4-6 結果分析與討論 147
第五章結論與未來展望 153
5-1 結論 153
5-2 未來展望 155
參考文獻 157
賴後權簡歷 165

參考文獻

[1] 蔡耀震，「逆向工程之曲面連續性理論與曲面模型自動化重建技術發展」，國立中央大學，博士論文，民國97年。
[2] 陳國仁，「最佳化嵌合理論於逆向工程與座標量測之研究」，國立中央大學，博士論文，民國96年。
[3] 許智超，「逆向工程與快速原型整合系統之研究」，國立台灣大學，碩士論文，民國88年。
[4] D. T. Pham and R. S. Gault, “A comparison of rapid prototyping technologies”, International Journal of Machine Tools & Manufacture, Vol. 38, pp. 1257-1287, 1998.
[5] 陳譽文，「五軸CNC曲面加工原理之研究」，國立中正大學，碩士論文，民國88年。
[6] 莊宗憲，「STL曲面加工之CNC刀具路徑規劃」，國立中正大學，碩士論文，民國90年。
[7] 莊振明，「STL模型之刀具路徑演算法與其應用」，國立中正大學，博士論文，民國92年。
[8] 蔡耀震，黃仲儀，林冠元，賴景義，翁文德，「逆向工程之連續性曲面模型自動化建構」，先進工程學刊，第三卷，第三期，209-215頁，民國97年7月。
[9] S. Melax, “A simple, fast, and effective polygon reduction algorithm”, Game Developer, November, pp. 44-49, 1998.
[10] M. Botsch, S. Steinberg, S. Bischoff, L. Kobbelt, “OpenMesh - a generic and efficient polygon mesh data structure” Computer Graphics and Multimedia RwTH Aachen, OpenSG Symposium, 2002.
[11] A. Gueziec and G. Taubin, “Cutting and stitching: Converting sets of polygons to manifold surfaces”, IEEE Trans. On Visualization and Computer Graphics, Vol. 7, No. 2, pp. 136-151, 2001.
[12] G. Barequet and M. Sharir, “Filling gaps in the boundary of a polyhedron”, Computer Aided Geometric Design, Vol. 12, pp. 207-229, 1995.
[13] G. Barequet and S. Kumar, “Repairing CAD models”, Proceedings of the 8th Conference on Visualization, pp. 363-370, October 1997.
[14] G. Barequet, “Using geometric hashing to repair CAD objects”, IEEE Computational Science and Engineering, October-December, pp. 22-28, 1997.
[15] M. Botsch and L.P. Kobbelt, “A robust procedure to eliminate degenerate facets from triangle meshes”, Proceedings of the Vision Modeling and Visualization Conference , pp. 283-290, November 2001.
[16] A. Petik “Some aspects of using STL file format in CAE systems”, International Workshop CA Systems and Technologies, pp. 80-86, 2000.
[17] I. Stroud and P. C. Xirouchakis, “STL and extensions”, Advances in Engineering Software, Vol. 31, No. 2, pp. 83-95, 2000.
[18] K. F. Leong, C. K. Chua and Y. M. Ng, “A study of StereoLithography file errors and repair, Part I: Generic solutions”, International Journal of Advanced Manufacturing Technology, Vol. 12, pp. 407-414, 1996.
[19] K. F. Leong, C. K. Chua and Y. M. Ng, “A study of StereoLithography file errors and repair, Part II: Special cases”, International Journal of Advanced Manufacturing Technology, Vol. 12, pp. 415-422, 1996.
[20] J. Wang and O. Manuel “A hole filling strategy for reconstruction of smooth surfaces in range images”, XVI Brazilian Symposium on Computer Graphics and Image Processing, pp. 12-15, Sao Carlos, October 2003.
[21] 許聖函，「三角網格資料定位整合與平滑性補洞之研究」，國立中央大學，碩士論文，民國93年。
[22] J. Davis, S. R. Marschner, M. Garr, M. Levoy , “Filling holes in complex surface using volumetric diffusion”, First International Symposium on 3D Data Processing, Visualization, and Transmission, pp. 19-21, Padova, Italy, June 2002.
[23] Y. Jun, “A piecewise hole filling algorithm in reverse engineering”, Computer-Aided Design, Vol. 37, No. 2, pp. 263-270, 2005.
[24] J. H. Bohn, “Removing zero-volume parts from CAD models for layered manufacturing”, IEEE Computer Graphics and Applications, pp. 27-34, November 1995
[25] P. Liepa, “Filling holes in meshes”, Eurographics Symposium on Geometry Processing, pp. 200-205, 2003.
[26] F. Bianconi, “Bridging the gap between CAD and CAE using STL files”, International Journal of CAD/CAM, Vol. 2, No. 1, pp. 55-67, 2002.
[27] P. Borodin, M. Novotni and R. Klein, “Progressive gap closing for mesh repairing”, Advances in Modeling, Animation and Rendering, Proceedings of Computer Graphics International, pp. 201-213, July 2002.
[28] C. Loop, “Managing adjacency in triangular meshes”, Technical Report, MSR-TR-2000-24, Microsoft Research, January 2000.
[29] S. J. Rock and M. J. Wozny, “Generating topological information from a “bucket of facets” ”, Solid Freeform Fabrication Proceedings, pp. 251-259, 1992.
[30] T．Fan，G. Medioni and R．Nevatia, “Segmented description of 3-D surface”, IEEE Transactions on Robotics and Automation, Vol. 3, No. 6, pp. 527-538, 1987.
[31] Y．H．Chen and C．Y．Liu, “Robust segmentation of CMM data based on NURBS”, The Intemational Joumal of Advanced Manufacturing Technology, Vol. 13, pp. 530-534, 1997.
[32] M．Yang and E. Lee, “Segmentation of measured point data using a parametric quadric surface approximation”, Computer-Aided Design, Vol. 31, pp. 449-457, 1999.
[33] H. Woo, E. Kang, S. Wang, K. H. Lee, “A new segmentation method for point cloud data”, International Journal of Machine tools and Manufacture, Vol. 42, pp. 167-178, 2002.
[34] J. A. Thorpe, Elementary topics in differential geometry, Springer, Berlin, 1978.
[35] G. Taubin, “Estimating the tensor of curvature of a surface from a polyhedral approximation”, Proceedings of the 5th International Conference on Computer Vision, pp. 902-907, 1995.
[36] T. Surazhsky, E. Magid, O. Soldea, G. Elber and E. Rivlin, “A comparison of Gaussian and mean curvatures estimation methods on triangular meshes”, International Conference on Robotics and Automation, pp. 1021-1026, Taipei, Taiwan, September 2003.
[37] E. Magid, O. Soldea and E. Rivlin, “A comparison of Gaussian and mean curvature estimation methods on triangular meshes of range image data”, Computer Vision and Image Understanding, Vol. 107, pp. 139-159, 2007.
[38] P. Krsek, G. Lukacs and R. R. Martin, “Algorithms for computing curvatures from range data”, The Mathematics of Surfaces VIII, Information Geometers, pp. 1-16, 1998.
[39] D. L. Page and A. F. Koschan and M. A. Abidi, ”Perception-based 3D triangle mesh segmentation using fast marching watersheds”, Proceedings of International Conference on Computer Vision and Pattern Recognition, Vol. 2, pp. 27-32, June 2003.
[40] J. Huang and C. H. Menq, “Automatic data segmentation for geometric feature extraction from unorganized 3D coordinate points”, IEEE Transactions on Robotics and Automation, Vol. 17, No. 3, pp. 268-79, June 2001.
[41] P. J. Besl and R. C． Jain, “Segmentation through variable-order surface fitting”, IEEE Transactions on Patten Analysis and Machine Intelligence, Vol. 10, No. 2, pp. 167-192, 1988.
[42] J. Y. Lai and T. C. Tsai, “A data segmentation technique for triangular meshes in reverse engineering”, Journal of the Chinese Society of Mechanical Engineers, Vol. 28, No. 3, pp. 289-300, 2007.
[43] G. Lavoue, F. Dupont and A. Baskurt, “Curvature tensor-based triangle mesh segmentation with boundary rectification”, Proceedings of Computer Graphics International Conference, pp. 10-25, 2004.
[44] H. C. Kim, S. M. Hur and S. H. Lee, “Segmentation of the measured point data in reverse engineering”, International Journal of Advanced Manufacturing Technology, Vol. 20, pp. 571-580, 2002.
[45] M. Vanco, “A direct approach for the segmentation of unorganized points and recognition of simple algebraic surfaces”, Ph.D. Dissertation, University of Technology Chemnitz, German, 2002.
[46] N. S. Sapidis and P. J. Besl, “Direct construction of polynomial surfaces from dense range images through region growing”, ACM Transactions on Graphics, Vol. 14, No. 2, pp. 271-200, 1995.
[47] A. Leonardis, A. Gupta and R. Bajcsy, “Segmentation of range images as the search for geometric parametric models”, International Journal of Computer Vision, Vol. 14, pp. 253-277, 1995.
[48] A. W. Fitzgibbon, D. Eggert and R. B. Fisher, “High-level CAD model acquisition from range images”, Computer-Aided Design, Vol. 29, No. 4, pp. 321-330, 1997.
[49] Y．H．Chen and C．Y．Liu, “Quadric surface extraction using genetic algorithms”, Computer-Aided Design, Vol. 31, No. 2, pp. 101-110, 1999.
[50] C. D. Bruyns, S. Senger, A. Menon, K. Montgomery, S. Wildermuth and R. Boyle, “A survey of interactive mesh-cutting techniques and a new method for implementing generalized interactive mesh cutting using virtual tools”, The Journal of Visualization and Computer Animation, Vol. 13, pp. 21-42, 2002.
[51] D. Bielser, and M. Gross, “Interactive simulation of surgical cuts”, Proceedings of Pacific Graphics, pp. 116-125, 2000.
[52] D. Bielser, P. Glardon, M. Teschner and M. Gross, “A state machine for real-time cutting of tetrahedral meshes”, Graphical Models, Vol. 66, No. 6, pp. 398-417, 2004.
[53] Y. Li, J. Yu, K. L. Ma and J. Shi, “3D paper-cut modeling and animation”, Computer Animation and Virtual Worlds, Vol. 18, pp. 395-403, 2007.
[54] H. Q. H. Viet, T. Kamada and H. T. Tanaka, “An algorithm for cutting 3D surface Meshes”, The 18th International Conference on Pattern Recognition, IEEE Computer Society , pp. 762-765, Hong Kong, 2006.
[55] W. C. Li, B. Levy and J. C. Paul, “Mesh editing with an embedded network of curves”, International Conference on Shape Modeling and Applications, pp. 63-71, 2005.
[56] K. C. H. Wong, T. Y. H. Siu, P. A. Heng and H. Sun, “Interactive volume cutting”, Proceedings of the Graphics Interface 1998 Conference, pp. 99-105, Vancouver, BC, Canada, 1998.
[57] H. W. Nienhuys and A. F. van der Stappen, “A surgery simulation supporting cuts and finite element deformation”, Proceedings of the 4th International Conference on MICCAI, pp. 145-152, Springer, Berlin, 2001.
[58] G. Slabaugh, V. Mihalef, and G. Unal, “A contour-based approach to 3D text labeling on triangulated surfaces”, Proceedings of the 5th International Conference on 3-D Digital Imaging and Modeling, pp. 416-423, 2005.
[59] C. D. Bruyns and S. Senger, “Technical Section: Interactive cutting of 3D surface meshes”, Computers & Graphics, Vol. 25, pp. 635-642, 2001.
[60] S. Cotin, H. Delingette and N. Ayache, “A hybrid elastic model for real-time cutting, deformations, and force feedback for surgery training and simulation”, The Visual Computer, Vol. 16, No. 8, pp. 437-452, 2000.
[61] H. W. Nienhuys and A. F. van der Stappen, “A Delaunay approach to interactive cutting in triangulated surfaces”, Proceedings of the 5th International Workshop Algorithmic Foundations of Robotics, pp. 113-130, Springer, Berlin, 2002.
[62] J. Verdera, V. Caselles, M. Bertalmio and G. Sapiro, “Inpainting surface holes”, IEEE International Conference on Image Processing, pp. 14-17, Barcelona, Spain, 2003.
[63] W. Schroeder, K. Martin and B. Lorensen, The visualization toolkit: An object oriented approach to 3D graphics (3rd ed.), Kitware, 2003.
[64] K. Lee, Principle of CAD/CAM/CAE Systems, Addison-Wesley, 1999.
[65] P. Benko, R. R. Martin and T. Varady, “Algorithms for reverse engineering boundary representation models”, Computer-Aided Design, Vol. 33, No. 11, pp. 839-851, 2001.
[66] P. Benko and T. Varady, “Segmentation methods for smooth point regions of conventional engineering objects”, Computer-Aided Design, Vol. 36, No. 6, pp. 511-523, 2004.
[67] A. Razdan and M. S. Bae, “A hybrid approach to feature segmentation of triangle meshes”, Computer-Aided Design, Vol. 35, No. 9, pp. 783-789, 2003.
[68] L. Moura and R. Kitney, “A direct method for least-square circle fitting”, Computer Physics Communications, Vol. 64, pp. 57-63, 1991.
[69] W. H. Press, S. A. Teukolsky, W. T. Vetterling and B. P. Flannery, Numerical recipes in C: The art of scientific computing (2nd ed.), Cambridge, New York, 1992.
[70] J. Y. Lai and H. C. Lai, “Repairing triangular meshes for reverse engineering applications”, Advances in Engineering Software, Vol. 37, pp. 667-683, 2006.
[71] J. Y. Lai, S. H. Shu and Y. C. Huang, “A cell subdivision strategy for r-nearest neighbors computation”, Journal of the Chinese Institute of Engineers, Vol. 29, No. 6, pp. 953-965, 2006.
[72] J. O’Rourke, Computational Geometry in C (2nd ed.), Cambridge University Press., New York, 2001.
[73] L. Piegl and W. Tiller, The NURBS book (2nd ed.), Springer-Verlag, Berlin, 1997.

指導教授

賴景義(Jiing-yih Lai)

審核日期

2010-7-20

推文