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

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

關(guān)鍵詞：三角網(wǎng)格模型;網(wǎng)格剖切;輪廓信息

引言

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

現(xiàn)狀分析

虛擬現(xiàn)實環(huán)境中的三維模型由巨大的三角網(wǎng)格模型重構(gòu)而成，現(xiàn)有的虛擬現(xiàn)實三維模型剖切[3–5]主要利用三角網(wǎng)格與剖切平面的空間位置關(guān)系得到模型剖切后三角網(wǎng)格的空間信息，現(xiàn)有的剖切技術(shù)主要采用空間中的面面求交運算[6]，即三角網(wǎng)格的三邊都與剖切面進行計算。

通過對現(xiàn)有的技術(shù)進行研究分析，存在以下方面的問題：

現(xiàn)有方法造成的計算量相當(dāng)龐大，嚴重影響剖切的實時性。

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

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

因此該問題成為了水電站三維精確模型基于虛擬現(xiàn)實技術(shù)的培訓(xùn)系統(tǒng)中的一個亟待解決的重點和難點。

剖切輪廓自動補面算法

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

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

算法流程圖和拓撲關(guān)系圖如圖1和圖2所示。

建立三維拓撲數(shù)據(jù)結(jié)構(gòu)

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

這樣設(shè)置的優(yōu)點是：

通過建立三維拓撲數(shù)據(jù)結(jié)構(gòu)，能夠高效查詢和檢索網(wǎng)格幾何信息，并對網(wǎng)格空間拓撲信息數(shù)據(jù)結(jié)構(gòu)進行修改和重構(gòu)。

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

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

生成三維模型的切割面

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

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

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

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

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

形成離散的線段集

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

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

確定切割面方程;

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

在根節(jié)點中尋找剖切到的子節(jié)點;

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

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

確定輪廓線的包含關(guān)系

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

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

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

效果與現(xiàn)有技術(shù)相比，本算法的有益效果是：

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

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

通過建立三維拓撲數(shù)據(jù)結(jié)構(gòu)，能夠高效查詢和檢索網(wǎng)格幾何信息，并對網(wǎng)格空間拓撲信息數(shù)據(jù)結(jié)構(gòu)進行修改和重構(gòu)，保證虛擬現(xiàn)實環(huán)境下三維模型實體剖切中材質(zhì)紋理繼承的準確性。

結(jié)論

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

參考文獻

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

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

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

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

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

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

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