基于三角網格模型的剖切輪廓自動補面方法

李定林 羅茜 孫廷昌 高彥明 閆雙鍵

摘要：本文介紹了一種基于三角網格模型的剖切輪廓自動補面算法，包括：建立三維拓撲數據結構，記錄三維模型的幾何信息和拓撲信息;在三維模型的投影面上定義切割路徑和切割方向，自動生成三維模型的切割面;切割面與構成物體的三角面片進行相交運算，形成離散的線段集;對切割面上的離散線段集進行追蹤擬合，得到物體的封閉輪廓線，確定輪廓線的包含關系;對封閉輪廓線的包圍區域進行三角剖分，生成實體的剖面圖。本文的算法實現了虛擬現實環境下三維模型的實體剖面、自動補面和材質繼承，既能夠在虛擬現實環境下準確可視化的描述三維模型的實體剖面，又可相對準確的繼承材質紋理，且同時具有較好的實時性。

關鍵詞：三角網格模型;網格剖切;輪廓信息

引言

三維模型中的三角網格模型具有許多良好的幾何特性，它能夠用多個面片逼近復雜形體的表面，而且容易處理，因此三角網格模型被廣泛應用于計算機圖形學、機械仿真、科學計算可視化等領域[1]。剖面輪廓線是三維模型的一個重要特征，它代表模型在某一位置處的大致輪廓和幾何形狀[2]，并體現三維模型的基本外觀。對三維表面模型的剖切是指直接在屏幕上對三維模型進行任意方向剖切，用戶可以方便地觀察模型截面的大小形狀，以實現對模型截面的宏觀認識。

現狀分析

虛擬現實環境中的三維模型由巨大的三角網格模型重構而成，現有的虛擬現實三維模型剖切[3–5]主要利用三角網格與剖切平面的空間位置關系得到模型剖切后三角網格的空間信息，現有的剖切技術主要采用空間中的面面求交運算[6]，即三角網格的三邊都與剖切面進行計算。

通過對現有的技術進行研究分析，存在以下方面的問題：

現有方法造成的計算量相當龐大，嚴重影響剖切的實時性。

目前的剖切方法中，三角網格與剖切面相交并的剖切面并不考慮實體的閉合面，無閉合面即空心剖切，更不會有實體剖面補面。剖切后的網格模型剖切面不能自動補面，用戶不能很直觀的從剖面上分析出來哪些是實體模型，哪些是面或殼模型，給實際培訓過程會帶來一些困難。

文獻[2]中公開了一種基于三角網格模型的剖面輪廓信息提取[2]，其采用OBJ格式的三維模型數據，利用分層切面和鄰接排序算法，獲得三角網格模型的剖面輪廓信息。該方法對有拓撲錯誤的模型有較好的適用性，但是該方法在獲得封閉的剖面輪廓環的過程中，未考慮補面時材質紋理的繼承問題。

因此該問題成為了水電站三維精確模型基于虛擬現實技術的培訓系統中的一個亟待解決的重點和難點。

剖切輪廓自動補面算法

本文所采用的切割算法的原理為：將物體的三維模型投影在二維平面上并獲取物體的投影圖，在二維平面上選擇定義切割路徑和切割方向，然后自動生成一個三維物體的切割面;用切割面和三維物體進行一系列的相交運算，對三維物體進行切割，得到一組離散的線段，再對離散的線段進行追蹤擬合，形成封閉的輪廓線，從而構成一個剖面圖。其形成的封閉輪廓線結構就是三維物體在該切割面上的內部結構，從而可以觀察得到準確的三維物體的內部構成。

針對現有技術存在的問題，本文提供一種應用于虛擬現實環境下三維模型的實體剖切，首先對于虛擬現實環境下物體的三維模型，建立三維拓撲數據結構;然后在三維模型的投影面[7]上定義切割路徑和切割方向，自動生成三維模型的切割面;對切割面上的離散線段集進行追蹤擬合，得到物體的封閉輪廓線;最后對封閉輪廓線的包圍區域進行三角剖分，生成實體的剖面圖。

算法流程圖和拓撲關系圖如圖1和圖2所示。

建立三維拓撲數據結構

對于虛擬現實環境下物體的三維模型，建立三維拓撲數據結構，所述三維拓撲數據結構記錄三維模型的幾何信息和拓撲信息，包括構建三維模型的頂點、邊、面、體的數量及紋理信息;其中，頂點的信息包括頂點編號、坐標、顏色;面的信息包括構成面的頂點數量、頂點編號、面的顏色、頂點序列;體的信息包括體的面數、面編號、紋理標號、層次標號。

這樣設置的優點是：

通過建立三維拓撲數據結構，能夠高效查詢和檢索網格幾何信息，并對網格空間拓撲信息數據結構進行修改和重構。

有利于在虛擬現實環境下進行三維模型的實體剖切，并能在剖切過程中進行自動補面以及繼承原模型的材質紋理。

網格信息不僅存儲了網格的空間信息，同時還存儲了其幾何元素（如頂點、邊、三角形等）之間的連接關系的拓撲信息。在三維模型的轉化過程中，按照統一標準屬性和格式對每一個三維模型的幾何信息、拓撲信息進行記錄，獲取構建三維模型的頂點、邊、面、體的數量以及紋理信息，建立三維拓撲數據結構對這些空間拓撲信息進行查詢、修改和重構。通過這種信息處理的方式，在剖切的過程中利用切割平面對物體三維模型相交的點運算形成離散的交線，利用交線數組得到物體的封閉輪廓線。同時對交線與重構的網格拓撲信息的關系進行追蹤和檢索、檢測、計算，對得到的重構拓撲信息進行格式運算，可形成新的物體三維模型。

生成三維模型的切割面

在三維模型的投影面上定義切割路徑和切割方向，自動生成三維模型的切割面。生成三維模型的切割面的步驟具體包括：

在給定視點下，對物體的三維模型進行隱藏線、隱藏面的消除處理，得到物體的二維效果圖;

在物體的二維投影平面上，定義切割路徑和切割方向;

將切割路徑和切割方向反投影到三維空間中，形成三維模型的切割面。

這樣設置的好處是：相對于現有技術中的剖面深度緩存（Z緩存）算法或八叉樹數據結構算法來說，這里采用的基于網格的切割算法的處理效率要更好，且在此基礎上采用基于網格的拓撲信息進行離散線段的追蹤亦保證了剖面輪廓自動補面的準確性。

形成離散的線段集

切割面與構成物體的三角面片進行相交運算，形成離散的線段集。包括：首先確定切割面方程;然后利用二叉樹結構遍歷葉節點中的三角網格，判斷網格是否與切割面相交，如果相交，則求出切割面與網格的交點，得到離散的線段，對離散線段的拓撲信息進行處理，將處理后信息存入上下鏈表;如果判斷得出網格與切割面不想交，則判斷網格與切割面位置，并將原信息存入上下鏈表。

切割算法流程如圖3所示。剖切輪廓自動補面算法中切割算法包括：

確定切割面方程;

一個平面通過的空間三個點，，，平面方程為：

在根節點中尋找剖切到的子節點;

判斷該節點是否葉節點，如果是，則該節點查找完畢，繼續下一步驟;如果否，則子節點中尋找剖切到的下一層子節點，再判斷該下一層子節點是否葉節點;

遍歷葉節點中的三角網格，判斷網格是否與剖切面相交，如果是，則求出剖切面與網格的交點，對網格空間拓撲信息進行處理，將處理后信息存入上下鏈表;如果否，則判斷網格與剖切面位置，將原信息存入上下鏈表。

確定輪廓線的包含關系

對切割面上的離散線段集進行追蹤擬合，得到物體的封閉輪廓線，確定輪廓線的包含關系。包括：對離散線段的拓撲信息進行查詢、修改和重構，對離散線段與重構后的拓撲信息的關系進行格式運算，形成新的三維物體;

這樣設置的好處是：通過三維拓撲數據結構中記錄的離散線段與原三維模型關聯的拓撲信息，能夠在離散線段的追蹤擬合過程中準確的計算出原三維模型的閉合輪廓，從而準確的進行實體剖切。同時，在進行離散線段的擬合過程中，依據記錄的離散線段的材質紋理信息的標號，對擬合的離散線段進行材質紋理信息的修改和拓撲關系的重構，使得得到的實體剖切圖能夠準確的繼承原模型的材質紋理。

對封閉輪廓線的包圍區域進行三角剖分，生成實體的剖面圖。

效果與現有技術相比，本算法的有益效果是：

實現了虛擬現實環境下三維模型的實體剖面、自動補面和材質繼承，既能夠在虛擬現實環境下準確可視化的描述三維模型的實體剖面，又可相對準確的繼承材質紋理，且同時具有較好的實時性;

采用基于網格的切割算法進行切割面與三角面片的相交運算，并基于網格的拓撲信息進行離散線段的追蹤，保證了虛擬現實環境下三維模型剖切的效率和準確率;

通過建立三維拓撲數據結構，能夠高效查詢和檢索網格幾何信息，并對網格空間拓撲信息數據結構進行修改和重構，保證虛擬現實環境下三維模型實體剖切中材質紋理繼承的準確性。

結論

本算法的目的是針對現有技術存在的問題，提供一種基于三角網格模型的剖切輪廓自動補面算法。該算法實現了虛擬現實環境下三維模型的實體剖面、自動補面和材質繼承，既能夠在虛擬現實環境下準確可視化的描述三維模型的實體剖面，又可相對準確的繼承材質紋理，且同時具有較好的實時性。

參考文獻

王靜亞，方亮，郝敬賓. STL模型特征面片自適應分層算法[J].計算機應用研究，2011（6）：367–370+374.

張小青，吳坤華，黃鶴.基于三角網格模型的剖面輪廓信息提取[J].測繪通報，2012（9）26–28.

潘海鵬，周天瑞，朱根松. STL模型切片輪廓數據的生成算法研究[J].中國機械工程，2007（17）：64–67.

王泉德.任意三角網格模型體積的快速精確計算方法[J].計算機工程與應用，2009（18）：36–38+62.

謝存禧，李仲陽，成曉陽. STL文件毗鄰關系的建立與切片算法研究[J].華南理工大學學報（自然科學版），2000（3）：34–39.

張小青，朱光，侯妙樂.基于四面體的不規則表面文物體積計算[J].測繪通報，2011（10）：54–56.

袁青.基于投影面的三維物體剖面圖的自動生成算法[D].西安科技大學，2013.