博碩士論文 953207009 詳細資訊


姓名 楊聿宏(Yu-hung Yang)  查詢紙本館藏   畢業系所 光機電工程研究所
論文名稱 曲面模型轉換三角網格模型之研究
(On the study of converting CAD models into Triangular models)
檔案 [Endnote RIS 格式]    [Bibtex 格式]    [檢視]  [下載]
  1. 本電子論文使用權限為同意立即開放。
  2. 已達開放權限電子全文僅授權使用者為學術研究之目的,進行個人非營利性質之檢索、閱讀、列印。
  3. 請遵守中華民國著作權法之相關規定,切勿任意重製、散佈、改作、轉貼、播送,以免觸法。

摘要(中) 三角網格可以建構為各種型態之模型,因此被廣泛應用於CAD/CAM系統、電腦圖學、醫學影像、虛擬實境等領域。而在逆向工程與快速原型之應用中,將CAD模型轉換為網格模型為非常重要之技術。網格模型之建構必須在維持精度之前提下進行,否則轉換出之網格模型即無法精準表示原始CAD模型。減少三角網格數量亦為另一項重點,過多的三角網格數量將減低資料運算之效能。本論文提出精確且快速之精度控制方式,以及藉由四元樹資料結構作為曲面細分之輔助,以期確實減少三角網格數量。為建構水密且合理之網格模型,本論文提出以B-Rep資料結構輔助剪切曲面建立曲面邊界關連性,使由多片曲面構成之CAD模型經由三角網格化後,在原曲面接合處之網格皆能正確被建立,而避免破洞或自交等不合理情況發生,藉此建構出理想之網格模型。
摘要(英) All types of the models could be structured by triangle meshes which have been widely used in CAD/CAM systems, computer graphics, medical images, Virtual Reality, etc. For applications of the reverse engineering and the rapid prototyping processes, the converting CAD models into triangular meshes is a very important technique. Keeping the accuracy is the prerequisite for the process of the model structuring, or the result triangular meshes can’t be indicated the original CAD model. Reducing the triangular mesh quantity of the model is another important procedure. Excess triangle meshes would make the efficiency of data programming be reduced. We provide an exactly and efficiently accurate controlling method and the surface subdivision method assisted by the quadtree data structure which would help to reduce the amounts of meshes. In order to structure the watertight and manifold triangular mesh, we provide the applications of the B-Rep data structure to help the trimmed NURBS surfaces establish the relationships of boundaries between surface and surface. When the CAD model structured by trimmed surfaces has been triangulated, the triangle meshes in the boundary connecting with neighbor surfaces would be structured exactly. The wrong cases such as holes or self-intersection would not be occurred. Therefore, the ideal polygon-based model has been structured.
關鍵字(中) ★ 逆向工程
★ 三角網格化
★ 網格產生
★ 四元樹
★ 弦長誤差值
★ 曲面偏差值
★ B-Rep資料結構
關鍵字(英) ★ Reverse Engineering
★ Triangulation
★ Mesh Generation
★ Quadtree
★ Chord Error
★ Surface Deviation
★ B-Rep Data Structure
論文目次 摘要 I
ABSTRACT II
致謝 III
目錄 V
圖目錄 VIII
表目錄 XI
第一章 緒論 1
1.1 前言 1
1.2 文獻回顧 5
1.2.1 曲面之剪切與三角網格化 5
1.2.2 資料結構應用與參數對應 6
1.2.3 網格模型之邊界密合處理 7
1.3 研究目的與方法 8
1.3.1 研究目的 8
1.3.2 研究方法 9
1.4 論文架構 12
第二章 NURBS曲面之三角網格化 14
2.1 前言 14
2.2 曲線與曲面之數學模型概論 15
2.2.1 NURBS曲線之概論 15
2.2.2 NURBS曲面之概論 16
2.3 四元樹資料結構 20
2.3.1 樹狀結構之簡介 20
2.3.2 四元樹之簡介與應用 23
2.3.3 四元樹之程式資料類別 25
2.3.4 四元樹之建構流程與資料搜尋 27
2.3.4.1 四元樹建構流程暨前期之相鄰資料搜尋 28
2.3.4.2 後期之相鄰資料搜尋 31
2.4 曲面偏差值演算法 34
2.5 密鋪方塊三角網格建構法 39
2.6 範例分析與討論 41
第三章 剪切曲面之三角網格化 47
3.1 前言 47
3.2 剪切曲面之概論 49
3.3 剪切曲線多邊形化 52
3.3.1 曲線弦長誤差之概論 52
3.3.2 等分內插式弦長誤差演算法與折線之建構 55
3.3.3 逐點追跡式弦長誤差演算法與折線之建構 56
3.3.4 內插式與追跡式弦差演算法之比較與分析 56
3.4 空間域與參數域之數值映射及資料對應 60
3.5 剪切曲面之三角網格化流程 63
3.5.1 基底曲面與剪切曲線之處理 63
3.5.2 基底網格與剪切多邊形之合併處理 63
3.6範例分析與討論 68
第四章 多曲面模型轉換為網格模型之技術 75
4.1 前言 75
4.2 B-Rep資料結構 78
4.3 套用B-Rep資料結構之新三角網格化流程 82
4.4 範例分析與討論 85
第五章 範例實測與分析探討 89
5.1 前言 89
5.2 本研究之曲面網格化流程 89
5.3 商用軟體與本研究之範例測試比較 91
5.3.1 範例一:機車後照鏡 91
5.3.2 範例二:維納斯女神頭像 94
5.3.3 範例三:人體左手 99
5.3.4 範例四:人體右耳 99
5.3.5 範例五:巨石像 104
5.4 分析與討論 107
第六章 結論與未來展望 111
6.1 結論 111
6.2 未來展望 113
參考文獻 115
參考文獻 [1] G. R. Hopkinson, T. M. Goodman and S. R. Prince, A guide to the use and calibration of detector array equipment, SPIE Press – The International Society for Optical Engineering, 2004.
[2] E. Hecht, Optics, the 4th Edition, Addison Wesley Longman Publishing Co. Inc., 2001.
[3] C. K. Chua, K. F. Leong and C. S. Lim, Rapid prototyping: principles and applications, the 2nd Edition, World Scientific Publishing Co. Pte. Ltd., 2003.
[4] 邱至意「3D曲面模型網格化之研究,國立中央大學機械工程研究所碩士論文,民國九十一年。
[5] 蔡耀震,逆向工程之曲面連續性理論與曲面模型自動化重建技術發展,國立中央大學機械工程研究所博士論文,民國九十八年。
[6] L. A. Piegl and A. M. Richard, “Tessellating trimmed NURBS surfaces”, Computer-Aided Design, Vol. 27, No. 1, pp. 16-26, 1995.
[7] L. A. Piegl and W. Tiller, “Geometry-Based triangulation of trimmed NURBS Surfaces”, Computer-Aided Design, Vol. 30, No. 1, pp. 11-18, 1998.
[8] W. Cho, N. M. Patrikalakis and J. Peraire, “Approximate development of trimmed patches for surface tessellation”, Computer-Aided Design, Vol. 30, No. 14, pp. 1077-1087, 1998.
[9] W. Cho, T. Maekawa, N. M. Patrikalakis and J. Peraire, “Robust tessellation of trimmed rational B-spline surface patches”, Computer Graphics International, pp. 543-555, 1998.
[10] N. Litke, A. Levin and P. Schröder, “Trimming for subdivision surfaces”, Computer-Aided Geometric Design, Vol. 18, No. 5, pp. 463-481, 2001.
[11] S. Kumar and D. Manocha, “Efficient rendering of trimmed NURBS surfaces”, Computer-Aided Design, Vol. 27, No. 7, pp. 509-521, 1995.
[12] S. Kumar, “Robust incremental polygon triangulation for fast surface rendering”, WSCG'2000: The 8th International Conference in Central Europe on Computer Graphics, visualization and computer vision, vol. 8, No.1, 2000.
[13] H. Sadoyan, A. Zakarian, V. Avagyan and P. Mohanty, “Robust uniform triangulation algorithm for computer aided design”, Computer-Aided Design, Vol. 38, No. 10, pp. 1134-1144, 2006.
[14] L. Velho, L. H. De Figueiredo and J. Gomes, “A unified approach for hierarchical adaptive tessellation of surfaces”, ACM Transactions on Graphics, Vol. 18, No. 4, pp. 329-360, 1999.
[15] M. L. Alday, “Implicit surface triangulation”, Tik-111.500 Seminar on Computer Graphics, Helsinki University of Technology, 2003.
[16] W. E. Lorensen and H. E. Cline, “Marching cubes: a high resolution 3D surface construction algorithm”, ACM SIGGRAPH Computer Graphics, Vol. 21, No. 4, pp. 163-169, 1987.
[17] L. Yu, X. Jin, Y. Zhao, J. Feng and Q. Peng, “Fast tessellation for implicit surfaces”, Computer Engineering and Applications, Vol. 41, No.2, 2005.
[18] J. Bloomenthal, “Polygonization of implicit surfaces”, Computer aided geometry design, pp.341-355, 1988.
[19] M. A. Yerry and M. S. Shephard, “A modified quadtree approach to finite element mesh generation”, IEEE Computer Graphics and Applications, Vol. 3, No. 1, pp. 39-46, 1983.
[20] J. Vörös, “A strategy for repetitive neighbor finding in images represented by quadtrees”, Pattern Recognition Letters, Vol. 18, No. 10, pp. 955-962, 1997.
[21] A. Watt, 3D computer graphics, the 3rd Edition, Addison Wesley Longman Publishing Co. Inc., 2000.
[22] K. Lee, Principles of CAD/CAM/CAE Systems, Addison Wesley Longman Publishing Co. Inc., 1999.
[23] Y. C. Huang and J. Y. Lai, “A fast error comparison method for massive STL data”, Advances in Engineering Software, Vol. 39, No. 12, pp. 962-972, 2008.
[24] B. K. Choi, Surface modeling for CAD/CAM, ELSEVIER Science Publishers B.V., 1991.
[25] A. Guéziec, G. Taubin, F. Lazarus and B. Horn, “Cutting and stitching: converting sets of polygons to manifold surfaces”, IEEE Transactions on Visualization and Computer Graphics, Vol. 7, No. 2, pp. 136-151, 2001.
[26] V. Settgast, K. Müller, C. Fünfzig and D. Fellner, “Adaptive tessellation of subdivision surfaces”, Computers & Graphics, Vol. 28, No. 1, pp. 73-78, 2004.
[27] D. Reiners, G. Voß, J. Behr, “OpenSG: basic concepts”, Proceedings of the OpenSG Symposium, 2002.
[28] G. Barequet, C. A. Duncan and S. Kumar, “RSVP: A geometric toolkit for controlled repair of solid models”, IEEE Transactions on Visualization and Computer Graphics, Vol. 4, No. 2, 1998.
[29] H. T. Yau, C. C. Kuo and C. H. Yeh, “Extension of surface reconstruction algorithm to the global stitching and repairing of STL models”, Computer-Aided Design, Vol. 35, No. 5, pp. 477-486, 2003.
[30] H. Chiyokura, Solid modeling with designbase: theory and implementation, Addison Wesley Longman Publishing Co., Inc., 1988.
[31] H. Toriya and H. Chiyokura, 3D CAD principles and applications, Springer-Verlag, 1993.
[32] R. Radovitzky and M. Ortiz, “Tetrahedral mesh generation based on node insertion in crystal lattice arrangements and advancing-front-delaunay triangulation”, Computer methods in applied mechanics and engineering, Vol. 187, No. 3-4, pp. 543-569, 2000.
[33] M. Freytag and V. Shapiro, “B-Rep SE: simplicially enhanced boundary representation”, Proceedings of the Ninth ACM Symposium on Solid Modeling and Applications, Genova, Italy, pp. 157-168, 2004.
[34] 鄒李森,數位幾何模型與類比幾何模型之轉換與應用,國立中正大學機械工程研究所碩士論文,民國九十一年。
[35] I. J. Schoenberg, “Contributions to the problem of approximation of equidistant data by analytic functions”, Quarterly of Applied Mathematics, Vol. 4, pp. 45-99 and 112-141, 1946.
[36] L. J. Doctor and J. G. Torborg, “Display techniques for octree-encoded objects”, IEEE Computer Graphics and Applications, Vol. 1, No. 3, pp. 29-38, 1981.
[37] M. A. Yerry and M. S. Shephard, “Automatic three dimensional mesh generation by the modified-octree technique”, International Journal for Numerical Methods in Engineering, Vol. 20, No. 11, pp. 1965-1990, 1984.
[38] S. S. Yeh and P. L. Hsu, “Adaptive-feedrate interpolation for parametric curves with a confined chord error”, Computer-Aided Design, Vol. 34, No. 3, pp. 229-237, 2002.
[39] X. Liu, F. Ahmad, K. Yamazaki and M. Mori, “Adaptive interpolation scheme for NURBS curves with the integration of machining dynamics”, International Journal of Machine Tools & Manufacture, Vol. 45, No. 4-5, pp. 433-444, 2005.
[40] G. Barequet and M. Sharir, “Filling gaps in the boundary of a polyhedron”, Computer Aided Geometric Design, Vol. 12, No. 2, pp.207-229, 1995.
[41] W. H. Press, B. P. Flannery, S. A. Teukolsky and W. T. Vetterling, Numerical recipes in C: the art of scientific computing, the 2nd Edition, Cambridge University Press, 1992.
[42] L. A. Piegl and W. Tiller, “The NURBS book”, the 2nd Edition, Springer-Verlag, 1997.
[43] 張真誠、蔡文輝、胡育誠,資料結構導論—C語言實作,全華科技圖書股份有限公司,民國九十二年。
[44] 賴景義、翁文德,逆向工程理論與應用,全華科技圖書股份有限公司,民國九十三年。
[45] 章明、姚宏宗、鄭正元、林宸生、姚文隆,逆向工程技術與系統,全華科技圖書股份有限公司,民國九十四年。
指導教授 賴景義(Jing-yi Lai) 審核日期 2009-7-6
推文 facebook   plurk   twitter   funp   google   live   udn   HD   myshare   reddit   netvibes   friend   youpush   delicious   baidu   

若有論文相關問題,請聯絡國立中央大學圖書館推廣服務組 TEL:(03)422-7151轉57407,或E-mail聯絡