Heuristic Search for the Application of Feature Line Extraction on Triangular Meshes

利用三角網格進行曲面重建時，分割網格邊線得依循網格邊移動，往往會有邊界震盪的現象產生，使得曲面建立後的邊界表現不佳，因此本研究提出新的網格重新分割法則，藉由修改三角網格，使其邊界能貼合需求的曲線，並改善原有的分割法則，避免原法則可能出現的錯誤。 在曲面重建以前，三角網格檔案十分龐大且雜亂，若直接以整塊鈑件進行建面，則鈑件的內部特徵將會因為建面法則的緣故而失真，使誤差變大，本研究提出多數值啟發搜尋，藉由點選特徵點以及計算路徑成本，能讓網格塊邊界沿著特徵線移動，降低曲面重建的誤差。 本研究以簡單鈑件、環狀鈑件、引擎蓋鈑、葉子鈑鈑件，比對多數值啟發搜尋與曲面分割法則以及原啟發搜尋之分割結果，並進行曲面重建，比較其誤差，證實多數值啟發搜尋能得到較佳的結果。When using triangular meshes for reconstructing surface, the edges of surface should along the edges of meshes. The performance of surface’s edge is not good enough for presenting the correctness of surface patch. This research presents a new method of mesh resubdivision method by editing the triangular meshes, then the patch edge could fit the curve demand, and avoid the error during the surface reconstruction process. Before the surface reconstruction, the triangular meshes is huge and mess. If the meshes is reconstructed directly, the feature of meshes would be distorted. This research presented a multi-value heuristic search by picking the characteristic points and calculating the path costs, patch edges could along the feature edges. The error of surface could be reduced. The simple sheet, circular sheet, engine hood sheet, and leaf sheet are used for comparing the result of multi-value heuristic search with curve-subdivision method and heuristic search. The results show that the multi-value heuristic method get the better performance than others.摘要 I Abstract III 目錄 IV 圖目錄 VII 表目錄 XI 第一章 緒論 1 1.1 前言 1 1.2 文獻回顧 2 1.2.1 網格重新分割 2 1.2.2 二次分割與特徵線萃取 3 1.3 研究動機 7 1.4 研究內容 10 1.5 開發環境 12 1.6 論文架構 13 第二章 資料前處理 15 2.1 三角網格資料結構 15 2.1.1 網路拓樸結構與半邊結構 15 2.1.2 點資料建立 16 2.1.3 邊資料建立 16 2.1.4 面資料建立 17 2.2 搜尋方法 17 第三章 網格重新分割 19 3.1 舊網格分割法 20 3.2 新網格分割法 25 3.2.1 搜尋交點 25 3.2.2 交點群與網格點群排序 29 3.2.3 網格點群分群 32 3.2.4 建立三角網格 35 第四章 二次分割與特徵線萃取 41 4.1 搜尋結構介紹 41 4.2 傳統啟發搜尋 44 4.3 搜尋方法介紹 45 4.4 路徑節點選擇 48 4.5 多數值啟發搜尋 50 第五章 實例驗證 57 5.1 本研究與原啟發搜尋比較結果 57 5.1.1 環狀鈑件 57 5.1.2 引擎蓋外鈑 59 5.1.3 葉子鈑 59 5.2 本研究與曲面分割比較結果 61 5.2.1 簡單鈑件 61 5.2.2 引擎蓋外鈑I 65 5.2.3 引擎蓋外鈑II 69 5.2.4 葉子鈑 72 第六章 結論與未來展望 75 6.1 結論 75 6.2 未來展望 76 參考文獻 77 作者簡歷 7