基于改進半邊數(shù)據(jù)結構的計算機仿真3D建模平臺研究

戴艷紅+崔健

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

關鍵詞： 三維建模； 半邊數(shù)據(jù)結構； 歐拉操作； 交互式技術

中圖分類號： TN911?34； TM417 文獻標識碼： A 文章編號： 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 引 言

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

1 系統(tǒng)平臺總體設計

1.1 系統(tǒng)總體結構

本系統(tǒng)從面向對象的模塊化設計出發(fā)，遵循了高內聚低耦合的原則，系統(tǒng)總體結構圖如圖1所示。

1.2 控制模塊

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

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

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

1.3 場景管理模塊的設計

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

（1） 對象類的設計

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

（2） 場景管理

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

1.4 幾何造型模塊的設計

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

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

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

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

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

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

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

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

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

2 三維建模平臺關鍵技術的研究與實現(xiàn)

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

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

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

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

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

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

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

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

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

凸臺的特征即在實體表面，朝著面法向量的正方向“拔”出一個凸起的部分來。一般的凸臺特征有方形凸臺、圓形凸臺等。

倒角造型是對實體中過渡劇烈的邊進行鈍化，使實體表面更為平滑過渡。

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

通過一個簡單的腔體模型來說明腔體構造（見圖5）的生成算法，以在六面體內部產生一個圓錐體空腔。具體操作步驟如下：

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

（2） 選擇主模型開孔面，即六面體中的頂面；

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

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

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

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

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

2.3 實體分析計算

（1） 半邊結構實體的歐拉不變性檢查和結構合法性檢查計算

半邊結構實體的歐拉不變形檢查是根據(jù)歐拉公式和來判斷一個實體是否符合歐拉原理。

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

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

（2） 實體表面積計算

求多面體的表面積就是求全部小平面的面積之和。因為一個平面可能是復連通的，所以計算一個小平面的面積就歸結為計算若干個平面單環(huán)的面積，用外環(huán)的面積減去全部內環(huán)的面積。

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

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

2.4 實體的顯示與場景渲染優(yōu)化

（1） 基于半邊結構的小平面三角剖分實現(xiàn)

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

步驟1：將多邊形的頂點按照某一方向進行排序。

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

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

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

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

2.5 三角片網格模型向半邊結構的轉化研究與實現(xiàn)

三角片網格模型半邊數(shù)據(jù)結構進行轉換的算法如下[8]：

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

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

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

步驟4：步驟3完成時，此時半邊結構已經形成，但是此時不是一個合理的半邊結構，因為還有大量共面相連的三角片存在。在這一步中，通過kef算子將共面相連的三角片連接，形成小平面。

3 平臺試驗結果展示

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

從實驗結果可以看出，當空間分割次數(shù)逐漸增加時，體素化的結果逐漸接近原邊界模型，體積誤差越來越小，體素模型逐漸接近原表面模型，但是計算時間也將增加。

4 結 論

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

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

參考文獻

[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設計方法研究[J].計算機輔助設計與圖形學學報，1999（4）：296?299.

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

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

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

[7] 李新友，唐澤圣，孫家廣.正則幾何形體及正則集合運算[J].計算機學報，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.