戴艷紅+崔健

摘 要： 研究并實(shí)現(xiàn)了一個(gè)交互式的三維建模系統(tǒng)，該系統(tǒng)以邊界表示法表達(dá)三維模型為理論基礎(chǔ)，同時(shí)提出一種改進(jìn)的半邊數(shù)據(jù)結(jié)構(gòu)來(lái)表達(dá)三維模型，通過(guò)歐拉算子生成各種形體。系統(tǒng)實(shí)現(xiàn)了模型切割、實(shí)體交并差的布爾運(yùn)算，以及對(duì)實(shí)體的體積、表面積的計(jì)算。在場(chǎng)景渲染方面，利用OpenGL或者Direct3D的庫(kù)函數(shù)結(jié)合系統(tǒng)所采用改進(jìn)的半邊數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)了3D模型的渲染。在仿真模塊實(shí)現(xiàn)了三維實(shí)體的體素化算法，該算法采用正四面體和長(zhǎng)方體相結(jié)合的八叉樹(shù)三維空間分割法對(duì)實(shí)體進(jìn)行空間分割，實(shí)現(xiàn)了對(duì)物體重心的計(jì)算，最后用該系統(tǒng)實(shí)現(xiàn)了一個(gè)螺紋銑削加工的仿真實(shí)例。

關(guān)鍵詞： 三維建模； 半邊數(shù)據(jù)結(jié)構(gòu)； 歐拉操作； 交互式技術(shù)

中圖分類號(hào)： TN911?34； TM417 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2017）01?0159?04

Abstract： An interactive 3D modeling system is studied and implemented， which takes the boundary representation method to represent the 3D model as the theoretical foundation. An improved half?edge data structure is proposed to represent the 3D model， and various forms are generated by means of Euler operator. The model cutting， Boolean operation of the entity intersection difference， and calculation of the entity volume and superficial area were realized in the system. The 3D model rendering was realized by means of the fusion of OpenGL or Direct3D library function with the improved half?edge structure of the system. The voxelization algorithm of the 3D entity was implemented in the simulation module， by which the octree?based 3D space segmentation method combining the regular tetrahedron with cuboid is used to segment the entity space to calculate the center of gravity of the object. A simulation example of the thread milling was realized with this system.

Keywords： 3D modeling； half?edge data structure； Euler operation； interactive technology

0 引 言

三維建模在計(jì)算機(jī)仿真領(lǐng)域占有非常重要的位置，是活躍的科學(xué)和工業(yè)研究領(lǐng)域[1]。本文對(duì)計(jì)算機(jī)仿真三維建模平臺(tái)設(shè)計(jì)的各個(gè)環(huán)節(jié)進(jìn)行了詳細(xì)的討論和分析，實(shí)現(xiàn)了基于改進(jìn)的半邊數(shù)據(jù)結(jié)構(gòu)的多面體歐拉操作算子，同時(shí)以歐拉操作算子三維實(shí)體造型高級(jí)操作實(shí)現(xiàn)了一個(gè)實(shí)時(shí)、便捷、高性能的面向計(jì)算機(jī)仿真的三維建模平臺(tái)。

1 系統(tǒng)平臺(tái)總體設(shè)計(jì)

1.1 系統(tǒng)總體結(jié)構(gòu)

本系統(tǒng)從面向?qū)ο蟮哪K化設(shè)計(jì)出發(fā)，遵循了高內(nèi)聚低耦合的原則，系統(tǒng)總體結(jié)構(gòu)圖如圖1所示。

1.2 控制模塊

控制模塊是中央樞紐，主要用于維護(hù)系統(tǒng)中各個(gè)模塊間的協(xié)同運(yùn)行，有條不紊地按照一定策略處理每個(gè)事件。由于在三維場(chǎng)景中，有大量的事件產(chǎn)生，有些事件可以并發(fā)進(jìn)行，但有些事件是互斥的。因此，需要控制模塊統(tǒng)一調(diào)度它們，以保證程序能高效、正確地運(yùn)行[2]。

首先該模塊維護(hù)一個(gè)里面存放需要處理的所有消息的消息隊(duì)列。在系統(tǒng)運(yùn)行的過(guò)程中，如果需要完成某個(gè)事件，要向控制模塊提出申請(qǐng)，然后由控制模塊生成一個(gè)消息放入消息隊(duì)列等待處理。在這個(gè)消息隊(duì)列中，每一個(gè)元素都代表一個(gè)事件，它是從系統(tǒng)其他模塊發(fā)送過(guò)來(lái)，要求執(zhí)行某種操作的消息事件，至于這件事情能否得到處理，對(duì)于發(fā)送消息端來(lái)說(shuō)，不會(huì)進(jìn)行判別。

每個(gè)規(guī)定的時(shí)間片內(nèi)，控制模塊掃描整個(gè)消息隊(duì)列，查看有沒(méi)有滿足觸發(fā)條件的消息，如果有則建立事件處理列表，按照優(yōu)先級(jí)將需要處理的事件按順序排好，然后依次執(zhí)行。

1.3 場(chǎng)景管理模塊的設(shè)計(jì)

場(chǎng)景管理模塊是一個(gè)核心模塊，它負(fù)責(zé)對(duì)系統(tǒng)內(nèi)部所有對(duì)象的管理，包括生成對(duì)象、改變對(duì)象屬性、刪除對(duì)象等一系列管理操作，同時(shí)管理場(chǎng)景內(nèi)的燈光，場(chǎng)景觀察矩陣的設(shè)置等[3]。

（1） 對(duì)象類的設(shè)計(jì)

本系統(tǒng)的所有對(duì)象都必須接受場(chǎng)景管理系統(tǒng)的管理，因此需要設(shè)計(jì)一個(gè)完整的類層次。本系統(tǒng)所有的類都繼承自節(jié)點(diǎn)類，這個(gè)基類派生出來(lái)的所有類組成了以這個(gè)基類為根的一個(gè)類繼承樹(shù)。

（2） 場(chǎng)景管理

在物體類的繼承關(guān)系中，所有物體都派生于同一個(gè)基類，即節(jié)點(diǎn)類，這樣便于場(chǎng)景統(tǒng)一管理。在節(jié)點(diǎn)類中，不但包含了自身的相關(guān)屬性，還包括了一個(gè)指向孩子節(jié)點(diǎn)的指針數(shù)組和指向父親節(jié)點(diǎn)的指針。整個(gè)場(chǎng)景里的所有物體形成一棵場(chǎng)景樹(shù)，場(chǎng)景樹(shù)的根節(jié)點(diǎn)就是一個(gè)三維場(chǎng)景的根節(jié)點(diǎn)，在一個(gè)三維場(chǎng)景中只有一個(gè)根節(jié)點(diǎn)，如圖2所示。

1.4 幾何造型模塊的設(shè)計(jì)

（1） 本系統(tǒng)采用的三維模型表示方法以及數(shù)據(jù)結(jié)構(gòu)

在本系統(tǒng)中，設(shè)計(jì)了一種新的模型數(shù)據(jù)結(jié)構(gòu)，是一種改進(jìn)的半邊數(shù)據(jù)結(jié)構(gòu)。本系統(tǒng)采用的幾何模型數(shù)據(jù)結(jié)構(gòu)在半邊結(jié)構(gòu)原有的拓?fù)浣Y(jié)構(gòu)上增加了一個(gè)節(jié)點(diǎn)類型——三角片節(jié)點(diǎn)，這類節(jié)點(diǎn)描述面上的一個(gè)小三角片，它有1個(gè)指向其父面的指針，3個(gè)指向頂點(diǎn)節(jié)點(diǎn)的指針，1個(gè)指向后繼三角片節(jié)點(diǎn)和前驅(qū)三角片節(jié)點(diǎn)的指針構(gòu)成一個(gè)小平面的所有三角片的雙向鏈表[4]。

（2） 基于歐拉算子的邊界幾何造型技術(shù)

在本系統(tǒng)中，對(duì)于生成的實(shí)體是否合法也采用該公式進(jìn)行檢查，以保證所有參與幾何造型的形體都符合歐拉不變性原理。

歐拉操作用于對(duì)等數(shù)據(jù)的增、刪過(guò)程，也就是對(duì)實(shí)體進(jìn)行造型過(guò)程。這種造型步驟是低層次的、繁瑣的，不適用于人機(jī)交互，但卻是實(shí)體造型系統(tǒng)中高層次的幾何造型操作（如實(shí)體切割、掃掠技術(shù)、實(shí)體貼合等）的構(gòu)成基礎(chǔ)。

1.5 建模系統(tǒng)統(tǒng)一接口的設(shè)計(jì)

在本系統(tǒng)中，為了提供二次應(yīng)用開(kāi)發(fā)的功能，本系統(tǒng)將所有的建模功能、場(chǎng)景對(duì)象管理的功能都封裝在一個(gè)動(dòng)態(tài)鏈接庫(kù)內(nèi)執(zhí)行，如圖3所示。

為了實(shí)現(xiàn)對(duì)模型數(shù)據(jù)結(jié)構(gòu)的支持，統(tǒng)一接口的設(shè)計(jì)中必須包含對(duì)數(shù)據(jù)結(jié)構(gòu)的處理。當(dāng)使用三角片網(wǎng)格模型時(shí)，統(tǒng)一接口模塊將對(duì)這些三角片網(wǎng)格模型進(jìn)行半邊結(jié)構(gòu)的轉(zhuǎn)換。內(nèi)部建模系統(tǒng)完成建模操作之后，統(tǒng)一接口模塊還必須提供兩種數(shù)據(jù)結(jié)構(gòu)類型的處理結(jié)果給用戶，讓用戶根據(jù)需要進(jìn)行選擇。統(tǒng)一接口模塊的操作流程如圖4所示。

通過(guò)統(tǒng)一接口標(biāo)準(zhǔn)向外提供功能，可以很好地實(shí)現(xiàn)操作的穩(wěn)定性和安全性，同時(shí)也讓系統(tǒng)可以很快速地進(jìn)行二次開(kāi)發(fā)，并且實(shí)現(xiàn)平臺(tái)的移植。

2 三維建模平臺(tái)關(guān)鍵技術(shù)的研究與實(shí)現(xiàn)

2.1 基于掃掠算法的基本幾何圖元的生成實(shí)現(xiàn)

在本系統(tǒng)中，利用歐拉操作和掃掠操作以生成若干基本三維實(shí)體[5]。

長(zhǎng)方體：一次mvfs生成空元體；三次mev算子生成底部矩形的三條連續(xù)邊；一次mef生成底部的長(zhǎng)方形面；以底部的長(zhǎng)方形面為基，沿高度方向做一次平移掃掠。

圓柱體（假設(shè)圓柱體底面圓的分割條數(shù)為n）：一次mvfs生成空元體；次mev生成逼近底部圓的條連續(xù)邊（未封閉）；一次mef生成封閉的底部圓面；以底部的圓面為基，沿高度方向做一次平移掃掠。

球體：一次mvfs生成空元體；次mev生成逼近半圓弧的條連續(xù)邊；以連續(xù)邊兩個(gè)端點(diǎn)的連線為旋轉(zhuǎn)軸，以連續(xù)邊為基做一次以線為基的旋轉(zhuǎn)掃掠。

圓錐體：一次mvfs生成空元體；一次mev生成一條邊，這條邊將作為圓錐體側(cè)面的母線；以上一步生成的邊為基，這條邊的一個(gè)端點(diǎn)在圓錐體的頂點(diǎn)上，另一端在底部的圓上，以圓錐頂點(diǎn)和底部圓心的連線為轉(zhuǎn)軸，做一次旋轉(zhuǎn)掃描。

圓環(huán)體：一次mvfs生成空元體；次mev生成一個(gè)未封閉的平面區(qū)域；一次mef生成封閉的平面區(qū)域；以該平面區(qū)域?yàn)榛?，以指定的轉(zhuǎn)軸做一次旋轉(zhuǎn)掃描。

2.2 特征造型技術(shù)的研究與實(shí)現(xiàn)

孔洞的特征即在實(shí)體表面，朝著面法向量的反方向“挖”出一個(gè)凹陷的部分。一般的孔洞特征有方形孔洞，圓形孔洞等。

凸臺(tái)的特征即在實(shí)體表面，朝著面法向量的正方向“拔”出一個(gè)凸起的部分來(lái)。一般的凸臺(tái)特征有方形凸臺(tái)、圓形凸臺(tái)等。

倒角造型是對(duì)實(shí)體中過(guò)渡劇烈的邊進(jìn)行鈍化，使實(shí)體表面更為平滑過(guò)渡。

腔體造型在生成帶有內(nèi)腔特征的幾何形體時(shí)，可以非常方便地實(shí)現(xiàn)。本文以腔體為例具體介紹其設(shè)計(jì)與實(shí)現(xiàn)。

通過(guò)一個(gè)簡(jiǎn)單的腔體模型來(lái)說(shuō)明腔體構(gòu)造（見(jiàn)圖5）的生成算法，以在六面體內(nèi)部產(chǎn)生一個(gè)圓錐體空腔。具體操作步驟如下：

（1） 首先選擇主模型和空腔模型，即選擇六面體為主模型，圓錐體為空腔模型；

（2） 選擇主模型開(kāi)孔面，即六面體中的頂面；

（3） 選擇空腔模型的開(kāi)孔面，即圓錐體的底面；

（4） 對(duì)空腔模型世界位置的位置矩陣進(jìn)行變換，使它的下底面能夠和正方體頂面重合；

（5） 對(duì)空腔模型所有面的法向量置反；

（6） 合并主模型和空腔模型，即合并兩個(gè)實(shí)體的半邊數(shù)據(jù)結(jié)構(gòu)，形成一個(gè)具有兩個(gè)殼體的數(shù)據(jù)結(jié)構(gòu)；

（7） 連接這兩個(gè)殼。在兩個(gè)開(kāi)孔面上，以六面體模型的頂面為主面，以圓錐體的底面為輔面，使用kfmrh算子將圓錐體底面的外環(huán)變成六面體頂面的內(nèi)環(huán)邊界[6]，便形成了帶有圓錐腔體特征的六面體模型。

2.3 實(shí)體分析計(jì)算

（1） 半邊結(jié)構(gòu)實(shí)體的歐拉不變性檢查和結(jié)構(gòu)合法性檢查計(jì)算

半邊結(jié)構(gòu)實(shí)體的歐拉不變形檢查是根據(jù)歐拉公式和來(lái)判斷一個(gè)實(shí)體是否符合歐拉原理。

在半邊數(shù)據(jù)結(jié)構(gòu)中有大量的指針，這些指針在歐拉操作中要保證它們是合法的，例如一條邊必須擁有兩個(gè)半邊節(jié)點(diǎn)的指針he1和he2，否則就是一個(gè)不合法的數(shù)據(jù)結(jié)構(gòu)，父子關(guān)系的指針也必須保證是正確的。

在進(jìn)行幾何造型編輯操作之前，首先檢查半邊結(jié)構(gòu)是否合法，是否符合歐拉公式，如果不合法，則不進(jìn)行操作，以保證程序能正確執(zhí)行。

（2） 實(shí)體表面積計(jì)算

求多面體的表面積就是求全部小平面的面積之和。因?yàn)橐粋€(gè)平面可能是復(fù)連通的，所以計(jì)算一個(gè)小平面的面積就歸結(jié)為計(jì)算若干個(gè)平面單環(huán)的面積，用外環(huán)的面積減去全部?jī)?nèi)環(huán)的面積。

由矢量代數(shù)可知，兩矢量與的矢量積的模為sin（angle），angle為與之間的夾角。它恰好等于以和為邊的平行四邊形的面積。

因此可以采用如下方法計(jì)算多邊形的面積：將環(huán)的第一個(gè)頂點(diǎn)作為參考點(diǎn)，環(huán)所圍的面積area為多邊形法向量normal和矢量的點(diǎn)積之和：，其中為邊對(duì)多邊形面積的作用。等于矢量和的叉積：由于normal與同向，所以。

2.4 實(shí)體的顯示與場(chǎng)景渲染優(yōu)化

（1） 基于半邊結(jié)構(gòu)的小平面三角剖分實(shí)現(xiàn)

本系統(tǒng)采用多邊形的梯形三角剖分法，算法如下[7]：

步驟1：將多邊形的頂點(diǎn)按照某一方向進(jìn)行排序。

步驟2：依次從頂點(diǎn)作掃描線，同時(shí)記錄交點(diǎn)，將多邊形劃分成梯形。

步驟3：將梯形劃分成三角形。

（2） 場(chǎng)景渲染優(yōu)化

本系統(tǒng)實(shí)現(xiàn)了基于視錐體原理的場(chǎng)景渲染優(yōu)化。判別物體是否進(jìn)入視錐體的空間采用將實(shí)體包圍盒與場(chǎng)景視錐體進(jìn)行求交計(jì)算，如果相交了，則認(rèn)為這個(gè)實(shí)體進(jìn)入了視錐體空間。這個(gè)方法可以簡(jiǎn)單快速地實(shí)現(xiàn)場(chǎng)景渲染的優(yōu)化。

2.5 三角片網(wǎng)格模型向半邊結(jié)構(gòu)的轉(zhuǎn)化研究與實(shí)現(xiàn)

三角片網(wǎng)格模型半邊數(shù)據(jù)結(jié)構(gòu)進(jìn)行轉(zhuǎn)換的算法如下[8]：

步驟1：構(gòu)建一個(gè)半邊結(jié)構(gòu)的三維實(shí)體，將三角片網(wǎng)格模型中所有的頂點(diǎn)加入該半邊結(jié)構(gòu)中。此時(shí)面片信息為空，邊節(jié)點(diǎn)信息也為空。

步驟2：將所有三角片看成是一個(gè)獨(dú)立的小平面，加入半邊結(jié)構(gòu)。此時(shí)面與面之間不包含邊節(jié)點(diǎn)信息。

步驟3：構(gòu)建邊節(jié)點(diǎn)信息。構(gòu)建邊節(jié)點(diǎn)的過(guò)程是遍歷上一步中所有的小平面，假如在一個(gè)小平面中存在一個(gè)半邊，那么搜索所有的小平面，查找到一個(gè)的半邊，構(gòu)建一個(gè)邊節(jié)點(diǎn)，同時(shí)將半邊和半邊作為這個(gè)邊節(jié)點(diǎn)的兩個(gè)半邊。依次構(gòu)建出所有的邊節(jié)點(diǎn)。

步驟4：步驟3完成時(shí)，此時(shí)半邊結(jié)構(gòu)已經(jīng)形成，但是此時(shí)不是一個(gè)合理的半邊結(jié)構(gòu)，因?yàn)檫€有大量共面相連的三角片存在。在這一步中，通過(guò)kef算子將共面相連的三角片連接，形成小平面。

3 平臺(tái)試驗(yàn)結(jié)果展示

圖6～圖9分別展示了掃掠算法的實(shí)現(xiàn)演示，包括平移掃掠算法、以面為基旋轉(zhuǎn)掃掠算法、以線為基旋轉(zhuǎn)掃掠算法以及軌道掃掠算法。

從實(shí)驗(yàn)結(jié)果可以看出，當(dāng)空間分割次數(shù)逐漸增加時(shí)，體素化的結(jié)果逐漸接近原邊界模型，體積誤差越來(lái)越小，體素模型逐漸接近原表面模型，但是計(jì)算時(shí)間也將增加。

4 結(jié) 論

本文設(shè)計(jì)了一個(gè)基于歐拉算子的幾何造型平臺(tái)。在歐拉算子的基礎(chǔ)上，研究了基于歐拉算子的掃掠算法和幾何造型算法。為了提高建模的效率，還研究了基于特征的造型算法，實(shí)現(xiàn)將零維、一維和二維形體合理地納入到三維造型系統(tǒng)中，而且通過(guò)半邊結(jié)構(gòu)將它們正確地表達(dá)出來(lái)。

同時(shí)，針對(duì)半邊結(jié)構(gòu)特點(diǎn)的層次化存儲(chǔ)方案，將幾何模型的數(shù)據(jù)合理地保存與讀取。實(shí)現(xiàn)了基于半邊結(jié)構(gòu)模型的體素化算法，并且分析傳統(tǒng)長(zhǎng)方體八叉樹(shù)空間分割算法異常點(diǎn)的情況，結(jié)合正四面體八叉樹(shù)空間分割算法的穩(wěn)定性，提出了將長(zhǎng)方體和正四面體相結(jié)合的實(shí)體空間體素化，通過(guò)本系統(tǒng)驗(yàn)證表明，這是一種有效的體素化方案，可以盡可能地逼近原邊界模型。

參考文獻(xiàn)

[1] EDELSBRUNNER H. Key problems and key methods in computational geometry [M]. Berlin： Springer， 2005： 1?13.

[2] BARNHILL R E， BOEHM W. Surfaces in computer aided geometric design [M]. New York： North?Holland Publishing Co.， 1995： 1?17.

[3] 劉曉平，田景成.基于模板的工程CAD設(shè)計(jì)方法研究[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，1999（4）：296?299.

[4] 唐良紅，孫立鐫，宋雙柱.CAID系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)[J].哈爾濱理工大學(xué)學(xué)報(bào)，1998，3（3）：1?5.

[5] 唐榮錫.三維幾何造型[J].浙江大學(xué)學(xué)報(bào)，1982（4）：22?25.

[6] MANTYLA M. An introduction to solid modeling [M]. New York： Computer Science Press， 2003： 27?66.

[7] 李新友，唐澤圣，孫家廣.正則幾何形體及正則集合運(yùn)算[J].計(jì)算機(jī)學(xué)報(bào)，1989（3）：162?171.

[8] CHAZELLE B， EDELSBRUNNER H. An optimal algorithm for intersecting line segments in the plane [J]. Journal of ACM， 1992， 39（1）： 1?54.