基于Half Edge的隨機(jī)結(jié)構(gòu)面切割下三維塊體系統(tǒng)自動(dòng)生成法

陳剛，銀霞

(1.中國地質(zhì)大學(xué)工程學(xué)院，湖北武漢 430074； 2.深圳寶安國際機(jī)場擴(kuò)建工程指揮部，廣東深圳 518128；3.深圳市勘察研究院有限公司，廣東深圳 518026)

基于Half Edge的隨機(jī)結(jié)構(gòu)面切割下三維塊體系統(tǒng)自動(dòng)生成法

陳剛1，2?，銀霞3

(1.中國地質(zhì)大學(xué)工程學(xué)院，湖北武漢 430074； 2.深圳寶安國際機(jī)場擴(kuò)建工程指揮部，廣東深圳 518128；3.深圳市勘察研究院有限公司，廣東深圳 518026)

針對(duì)三維塊體系統(tǒng)自動(dòng)生成法的研究成果雖多，但主要研究過程的介紹較少的情況，本文結(jié)合Half Edge結(jié)構(gòu)對(duì)任意結(jié)構(gòu)面組合切割形成的三維塊體系統(tǒng)的自動(dòng)生成法進(jìn)行了詳細(xì)研究，研究結(jié)果表明該生成法為既有基于有向圖遍歷理論的二維塊體系統(tǒng)的三維拓展，可對(duì)任意結(jié)構(gòu)面切割組合下形成的包括凹形塊體在內(nèi)的三維塊體進(jìn)行有效搜索，顯示該方法的通用性和有效性，并可為三維結(jié)構(gòu)面連通性判定、三維不連續(xù)分析或流形元分析的前處理系統(tǒng)所應(yīng)用。

Half Edge；三維塊體系統(tǒng)

1 引 言

眾所周知巖體結(jié)構(gòu)面往往控制著巖體的強(qiáng)度、變形和穩(wěn)定性。因此自上世紀(jì)60年代以來，國內(nèi)外相繼發(fā)展了離散元(DEC)和快速拉格朗日法(FLAC)、不連續(xù)變形分析(DDA)和流形元法(NMM)等來模擬巖體的這種不連續(xù)性。

目前二維塊體系統(tǒng)的自動(dòng)生成法已非常成熟，而如何由二維擴(kuò)展至三維，Shi G H[1].發(fā)表過相關(guān)成果，但主要研究過程介紹非常少；而Y.Ikegaway、J.A.Hudson[2]提出的矢體概念；張奇華、鄔愛清[3]提出了全空間搜索的一般方法，但該方法涉及塊體正、負(fù)計(jì)算；魯軍、張楚漢[4]實(shí)現(xiàn)了用任意空間多邊形結(jié)構(gòu)面剖分三維空間巖體自動(dòng)剖分，但該剖分所涉及數(shù)據(jù)結(jié)構(gòu)非常復(fù)雜。

本文在既有二維塊體系統(tǒng)的有向圖遍歷生成算法[5]基礎(chǔ)上，拓展CAD/CAE領(lǐng)域?qū)嶓w模型空間拓?fù)潢P(guān)系的Half Edge數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)任意空間多邊形結(jié)構(gòu)面切割形成空間任意塊體的自動(dòng)生成。

2 預(yù)備知識(shí)

2.1 有向圖、平面圖、歐拉圖

有向圖、平面圖、歐拉圖的概念詳見文[6]，歐拉圖為平面圖。二維流形的拓?fù)浔硎揪瞧矫鎴D[7]，三維塊體系統(tǒng)的拓?fù)潢P(guān)系為歐拉圖[7]。

在本文中，頂點(diǎn)(Vertex)、邊(Edge)、面(Face)一般表示拓?fù)潢P(guān)系，相應(yīng)的點(diǎn)(Point)、線(段)(Line/Segment)、空間多邊形(Polygon)一般表示幾何體的空間位置。

2.2 Half Edge及其擴(kuò)展

Half Edge是一種以邊為中心(Edge－centered)用來存儲(chǔ)關(guān)于平面圖、空間多面體、可定向任意二維流形的有關(guān)頂點(diǎn)、邊、面關(guān)聯(lián)關(guān)系的數(shù)據(jù)結(jié)構(gòu)。在此之前，曾有Winged Edge Links、Loop Edge Links、Vertex Edge Links等多種表征三維模型拓?fù)潢P(guān)系的數(shù)據(jù)結(jié)構(gòu)[7]。Hlalf Edge一般定義如下:

就三維塊體的搜索對(duì)Half Edge進(jìn)行必要的擴(kuò)展。涉及有向邊、空間多邊形的定向時(shí)以右手螺旋法則為準(zhǔn)，即空間多邊形法向向量以符合右手螺旋為正，反之為負(fù)。擴(kuò)展Half Edge如下:

圖1 Half Edge擴(kuò)展示例圖

圖1 、表1分別給出了一個(gè)Half Edge擴(kuò)展對(duì)應(yīng)的示例圖和對(duì)應(yīng)的關(guān)聯(lián)表。其中右圖F3表示該面作為邊界面時(shí)對(duì)應(yīng)的Half Edge擴(kuò)展情況。有向邊關(guān)聯(lián)的所有面已依據(jù)其法向矢量與矢量的關(guān)系進(jìn)行“空間左右”排序。

2.3 塊體有效性校核

塊體數(shù)學(xué)意義上屬于二維可定向流形，因此其有效性首先需滿足歐拉－龐加萊公式，即:

對(duì)應(yīng)ExtendedHalf Edge關(guān)聯(lián)表 表1

其中:V為頂點(diǎn)個(gè)數(shù)(Vertex)；E為邊的個(gè)數(shù)(Edge)；F為面的個(gè)數(shù)(Face)；L為面上的內(nèi)部環(huán)的個(gè)數(shù)(Loop)；H為穿透體的洞的個(gè)數(shù)(Hole)；G為體的虧格(Genus)。

3 三維塊體自動(dòng)生成法

對(duì)隨機(jī)結(jié)構(gòu)面切割下的三維塊體自動(dòng)生成法，假設(shè)所有結(jié)構(gòu)面空間數(shù)據(jù)均已知，其形態(tài)為空間多邊形，對(duì)只關(guān)聯(lián)一個(gè)邊的頂點(diǎn)、只關(guān)聯(lián)一個(gè)面的邊等“樹枝”均已刪除。則三維塊體自動(dòng)生成法如下:

(1)初始化結(jié)構(gòu)面為Half Edge數(shù)據(jù)；

(2)結(jié)構(gòu)面對(duì)應(yīng)空間多邊形兩兩求交，并根據(jù)求交結(jié)果動(dòng)態(tài)修改其Half Edge對(duì)應(yīng)的Vertex、Edge、Face數(shù)據(jù)；生成有向邊的Extended Half Edge數(shù)據(jù)(對(duì)任意頂點(diǎn)i、j關(guān)聯(lián)的邊只需生成一個(gè)有向邊的數(shù)據(jù))；

(3)任選一條有向邊，其ExtendedHalfEdge記為EHEDS，初始化:

并置該邊＜LeftFace、RightFace〉已搜索標(biāo)志；DCL.head()表示雙向循環(huán)鏈表的頭元素、DCL.suc()表示雙向循環(huán)鏈表當(dāng)前元素的后繼，DCL.pre()表示雙向循環(huán)鏈表當(dāng)前元素的前驅(qū)；

(4)設(shè)置已搜索有向邊的集合為:

設(shè)置一待搜索有向邊的集合為:

其中e(vm，vn)表示頂點(diǎn)vm、vn組成的有向邊，F(xiàn)ace (e)表示邊e所屬面的編號(hào)，且e(vi，vj)與－e(vi，vj)同時(shí)作為ListA元素時(shí)意味著vm、vn組成邊的雙方向已搜索完畢，將不再作為ListB的元素。

設(shè)置一已搜索過的有向面的集合為:

實(shí)際程序設(shè)計(jì)中ListA、ListB可合并為一個(gè)集合。

(5)對(duì)ListB的所有待搜索有向邊進(jìn)行搜索，設(shè)其中一為e(vm，vn)，其 ExtendedHalfEdge記為 Current EHEDS，對(duì)應(yīng)面的編號(hào)為F，則新增一已搜索面FNew至ListC，將面FNew的相關(guān)有向邊添加至ListA，動(dòng)態(tài)修改ListB的元素，并設(shè)置＜FNew，F(xiàn)〉已搜索標(biāo)志。其中:

(6)重復(fù)(5)直至ListB中元素搜索完畢；

(7)LeftFace＝RightFace；

重復(fù)(3)直至有向邊對(duì)應(yīng) ExtendedHalfEdge中DCL的所有＜LeftFace，RightFace〉均已搜索完畢。

(8)選擇下一條 ExtendedHalfEdge中 DCL的＜LeftFace，RightFace〉尚未搜索完畢的有向邊，重復(fù)(3)～(7)至所有有向邊的所有ExtendedHalfEdge均搜索完畢。

(9)對(duì)(1)～(8)中自動(dòng)生成的塊體進(jìn)行規(guī)整化，主要是對(duì)共面的過個(gè)Face和Edge進(jìn)行合并。

4 實(shí)例分析

本文給出一共由21個(gè)矩形結(jié)構(gòu)面切割生成塊體系統(tǒng)的實(shí)例，相關(guān)幾何數(shù)據(jù)如圖2所示，面－頂點(diǎn)拓?fù)潢P(guān)系如表2所示。

實(shí)例分析面－定點(diǎn)關(guān)系表 表2

圖2 實(shí)例分析結(jié)構(gòu)面空間位置圖

按三維塊體自動(dòng)生成法(2)后形成的各邊Extended Half Edge及結(jié)構(gòu)面兩兩求交結(jié)果見表3、圖3(因篇幅所限只列出部分結(jié)果)。

最終共有87個(gè)頂點(diǎn)、170個(gè)面、232條邊。按自動(dòng)生成法(3)～(4)選有向邊m8開始搜索，初始化Left-Face＝L11，RightFace＝M5；按自動(dòng)生成法(5)～(7)繼續(xù)搜索，對(duì)應(yīng)的結(jié)果塊體如圖4所示。按(8)搜索剩余邊直至所有有向邊搜索完畢。

部分Extended Half Ege結(jié)果 表3

圖3 m8邊關(guān)聯(lián)圖

圖4 m8搜索塊體線框圖對(duì)應(yīng)的實(shí)體圖

5 結(jié) 語

基于Half Edge的隨機(jī)結(jié)構(gòu)面切割下三維塊體系統(tǒng)自動(dòng)生成法能有效生成三維不連續(xù)變形分析所需的各種塊體，能統(tǒng)一處理凸性塊體與凹形塊體、有限塊體與無限塊體，并將在后續(xù)接觸分析與求解中發(fā)揮重要作用?；谠撋煞ㄉ蓧K體系統(tǒng)的塊體理論分析與不連續(xù)變形分析等將在其他論文中予以闡述。

[1]Shi G H.Producing joint polygons，cutting joint blocks and finding key blocks for general free surfaces[J].巖石力學(xué)與工程學(xué)報(bào)，2007，25(11)，2161～2170

[2]IKEGAWAY，HUDSON J.A A novel automatic identification system for three－dimension multi－block system[J].Engineering Computations，1992，9(2):169～179

[3]張奇華，鄔愛清.隨機(jī)結(jié)構(gòu)面切割下的全空間塊體拓?fù)渌阉鞯囊话惴椒╗J].巖石力學(xué)與工程學(xué)報(bào)，2007，26(10)，2043～2048

[4]魯軍.離散單元法的數(shù)值模擬及其工程應(yīng)用.北京，清華大學(xué)水利水電工程系，1996

[5]陳剛，劉佑容.流形元覆蓋系統(tǒng)的有向圖遍歷生成算法研究[J].巖石力學(xué)與工程學(xué)報(bào)，2003，22(5)711～716

[6]徐俊明.圖論及其應(yīng)用用[M].合肥:中國科學(xué)技術(shù)出版社，1998

[7]Ian Stroud.Boundary Representation Modelling Techniques. Lausanne.Springer，2005

Automatic Generation Method of 3D Block System Based on Half Edge With Stochastic Jonts Cutting

Chen Gang1，2，Yin Xia3
(1.Faculty of Engineering，China University of Geoscience，Wuhan 430074，China；2.Shenzhen Airport Expansion Project Headquaters，Shenzhen 518128，China；3.Shenzhen Investigation＆Research Institute Co.，Ltd.Shenzhen 518026，China)

This paper describes an automatic generation method of 3D block system based on Half Edge with stochastic joints group，whereas the absence of detailed introduction for substantial research papers for 3D block system’s automatic generation.The research findings demonstrate the generalization and validity for this method，and indicate it is a natural extension of 2D block system’s generation based on oriented graph traversal.This method can also be applied to the determination of connectivity，3D DDA and numerical manifold method for stochastic joints group.

Half Edge；3D Block System

1672－8262(2010)03－166－04

P628.3

A

2009—10—28

陳剛(1978—)，男，碩士，主要從事巖土工程設(shè)計(jì)及治理工程研究。