Title page for 953207009


[Back to Results | New Search]

Student Number 953207009
Author Yu-hung Yang(楊聿宏)
Author's Email Address 953207009@cc.ncu.edu.tw
Statistics This thesis had been viewed 1427 times. Download 641 times.
Department opto-Mechatronics
Year 2008
Semester 2
Degree Master
Type of Document Master's Thesis
Language zh-TW.Big5 Chinese
Title On the study of converting CAD models into Triangular models
Date of Defense 2009-06-29
Page Count 133
Keyword
  • B-Rep Data Structure
  • Chord Error
  • Mesh Generation
  • Quadtree
  • Reverse Engineering
  • Surface Deviation
  • Triangulation
  • Abstract 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.
    Table of Content 摘要I
    ABSTRACTII
    致謝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
    Reference [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]章明、姚宏宗、鄭正元、林宸生、姚文隆,逆向工程技術與系統,全華科技圖書股份有限公司,民國九十四年。
    Advisor
  • Jing-yi Lai(賴景義)
  • Files
  • 953207009.pdf
  • approve immediately
    Date of Submission 2009-07-06

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have dissertation-related questions, please contact with the NCU library extension service section.
    Our service phone is (03)422-7151 Ext. 57407,E-mail is also welcomed.