臺灣博碩士論文加值系統

在逆向工程中，對於掃描資料的處理，通常是轉成三角網格。但一些傳統產業仍是以曲面模型為主。因此必須再進行後處理，例如人工拉取曲線以建立曲面模型。然而這方面是需要花費時間及人力的，且由於經驗的不同導致結果亦不同。
本研究主要提供一個建立曲面模型的前處理---區域分割的流程。之後藉由分割出的區域，便可以直接拿來鋪設曲面。研究方法主要是直接藉由計算幾何學的方法建構出點與點間的關係，擷取出特徵點。利用最小擴張樹(Minimum Spanning Tree)將邊界線串連起來。最後再利用B-Rep實體模型的特性找出不同的區域，達到區域分割的動作。
經由此一前處理，可以大大降低人為因素而產生的錯誤，讓傳統繁雜的鋪設曲面步驟簡化，可以加速模型的曲面建構流程，相信對工業界的競爭力有很大的幫助。另外，在一個程序化的流程下，也可以讓產品的品質得到更好的保障。

For manipulating the scanning database, it is usually transform to STL in the reverse engineering. The NURBS surface is still the major way to cope with scanning data in the conventional industry and the results have to be processed further, for instance, fetching the curve artificially to establish NURBS surface. However, it needs more cost and human power and the different experiences on it might cause different results. In this study, we try to establish a preprocess of NURBS surface -- Segmentation to reduce the error of conventional way due to the different judgements.

This research mainly provide a pre-process which establish NURBS surface model - a procedures of segmentation. Then, with the region that is cut apart to build NURBS surface directly. The main purpose of this research directly use the method of the computational geometry to establish the relation of points, and then extract the feature points. Then, we compute a minimum spanning tree (MST) for these feature point to become boundary lines. Finally, found out the different region by using the property of B-rep solid model for the segmentation purpose.

By this process could reduce human-made error and simplify the conventional steps. It is expected that this process could shorten the processing time of NURBS surface`s establishment. And under the standard processing, it could ensure the quality of product and has a lot of favor to the industry.

中文摘要......................................................................................I
英文摘要.....................................................................................II
目錄...........................................................................................III
圖目錄......................................................................................VII
表目錄......................................................................XII
第一章 緒論……………………….…………………………01
1.1 前言…………………………..………………………01
1.2 研究動機………………………..……………………02
1.3 研究目的………………………..……………………04
1.4 文獻回顧………………………..……………………04
1.4.1銳利邊界點群的擷取………………....………05
1.4.2區域的分割………………..……………………09
1.5 研究方法……………………………………………12
第二章 幾何定義…………………….………………………15
2.1 Voronoi diagram………………..…………………..…15
2.2 Delaunay triangulation………....………...……………17
2.3 Medial Axis………….…..…………………….....……18
2.4 Poles...............................................................................19
2.5 Local Feature Size.........................................................21
2.6 Sampling Criterion --- r-sample.....................................21
2.7 Skinniness Formula.......................................................22
第三章 最小擴張樹………………………...…………..……24
3.1 最小擴張樹介紹………………………….…….……24
3.2 最小擴張樹相關之理論及原理..................................25
3.2.1 圖形追蹤………………………………………25
3.2.2 擴張樹…………..…...…………………………26
3.2.3 最小擴張樹………...…………………………27
3.2.4 Prim’s Algorithm…...….……………….….……28
3.2.5 Kruskal’s algorithm………………………...…...34
3.3 最小擴張樹的應用......................................................37
第四章 特徵點的找尋……………………………………..38
4.1 Pole與LFS的關係…………….......................….……40
4.2 LFS與Skinniness Formula的關係…………………43
4.3演算流程…………………………………….………...45
4.4結果與討讑……………………………………………47
4.4.1 結果………………………………………….…47
4.4.1討論………………………………………….…49
第五章 應用MST於串連特徵點關係………………..55
5.1權重的分配……………………………………………57
5.2成本(Cost)的定義………………………………..……60
5.3 k-Neighbors…………………………………...………63
5.4修改MST演算法 --- ModifyMST…………………64
5.5演算法流程……………………………………………70
5.6結果問題與討論………………………………………72
5.6.1 結果………………………………………….…72
5.6.2討論………………………………………….…77
第六章 區域分割(Segmentation)…………………………...79
6.1找尋分段點(Subdivide Points)…...…………...………80
6.2 B-Rep格式特性建構封閉區域…….………...………82
6.2.1起始封閉區域的判定……...……………………85
6.2.2建構封閉區域……………...……………………86
6.3建構B-Rep流程圖及PseudoCode…….……...………94
6.4範例…………………..………....................................100
6.4.1分配分段點及線段編號………..……...……..100
6.4.2不同區域的呈現……………………………...102
第七章 後續處理及實例測試……..……………………….106
7.1後續處理………………………………...……..106
7.1.1建構封閉曲線…………..…....…………….107
7.1.2編修……………..……….………...……….110
7.1.2.1自動刪除細支….……….....……….110
7.1.2.2手動刪除細支….……….....…….…111
7.2亂點模型實例測試……………………...……...112
7.2.1 Fandisk模型……………………....…….....113
7.2.2 CAD模型………..……….……...……........119
7.2.3 Stern模型………..……….……...…….......124
7.3點群自動分區域及其後續鋪設曲面…...……...128
第八章 結論及未來展望…………..……………………….137
8.1結論…..……..………………………………….137
8.2未來展望....………...…………………………….139
參考文獻……………………………………………...……..142

[1] N.Amenta, S.Choi and R.K. Kolluri, “The Power Crust,” Proceedings
sixth ACM symposium on Solid modeling and applications, pages
249-266, 2001.

[2] N.Amenta, S.Choi and R.K. Kolluri, “The Power Crust, Union of
Balls, and the Medial Axis Transform” , March 2,2001.

[3] Pauly M, Keiser R, Gross M, “Multi-scale feature extraction on
point-sampled surfaces,” Proceedings of the Eurographics 2003;
pages 281–289, 2003.

[4] Gumhold S, Wang X, MacLeod R, “ Feature extraction from point
Clouds,” Proceedings of the 10th International Meshing Roundtable
pages 293–305, 2001.

[5] Lavoue G, Dupont F, Baskurt A, “Constant curvature region
decomposition of 3D-meshes by a mixed approach vertex-triangle,”
J WSCG 2004;12(2):245–52.

[6] Lavoue G, Dupont F, Baskurt A, “A new CAD mesh segmentation
method,based on curvature tensor analysis,” Computer Aided
Geometric Design, 2005 2004;12(2):245–52.

[7] Yunjin L, Seungyong L, Ariel S, Daniel Cohen-Or, Hans-Peter
Seidel, “Mesh scissoring with minima rule and part salience,”
Computer Aided Geometric Design 22 444–465, 2005

[8] Bang Ye Wu and Kun-Mao Chao, “Minimum Spanning Trees,”
Chapman & Hall/CRC Press, USA. , 2004

[9] Hitoshi Yamauchi, Seungyong Lee, Yunjin Lee et.al,” Feature
Sensitive Mesh Segmentation with Mean Shift”,2005

[10] Ohtake Y, Belyaev AG, Seidel H-P.” Ridge-valley lines on meshes
via implicit surface fitting.” ACM Trans Graphics 2004;
23(3):609-12[Proceedings of SIGGRAPH 2004].

[11] Yoshizawa S, Belyaev AG, Seidel H-P.” Fast and robust detection of
crest lines on meshes”. Proceedings of the ACM symposium on
solid and physical modeling.

[12] Soo-Kyun Kim, Chang-Hun Kim.” Finding ridges and valleys in a
discrete surface using a modified MLS approximation”,
Computer-Aided Design 38, 173–180, 2006

[13] Joseph O`rourke “Computational Geometry in C” ,Cambridge
University Press, 2nded.

[14] http://www.cgal.org/

[15]吳勁樺,”資料結構教學範本 使用C++”

[16]郭川竹博士論文,”創新之組合方法於散亂點資料的模型重建與
應用”, 國立中正大學 機械工程研究所,2004

[17] FLOATER M.: Parameterization and smooth approximation of
surface triangulations. Computer Aided Geometric Design 14 (1997), 231–250.

[18] FLOATER M. S.: Mean-value coordinates. Computer Aided
Geometric Design 20 (2003), 19–27.

[19] FLOATER M. S., REIMERS M.: Meshless parameterization and
surface reconstruction. Computer Aided Geometric Design
18(2001), 77-92