基于Half Edge的隨機結構面切割下三維塊體系統自動生成法

陳剛，銀霞

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

基于Half Edge的隨機結構面切割下三維塊體系統自動生成法

陳剛1，2?，銀霞3

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

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

Half Edge；三維塊體系統

1 引 言

眾所周知巖體結構面往往控制著巖體的強度、變形和穩定性。因此自上世紀60年代以來，國內外相繼發展了離散元(DEC)和快速拉格朗日法(FLAC)、不連續變形分析(DDA)和流形元法(NMM)等來模擬巖體的這種不連續性。

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

本文在既有二維塊體系統的有向圖遍歷生成算法[5]基礎上，拓展CAD/CAE領域實體模型空間拓撲關系的Half Edge數據結構來實現任意空間多邊形結構面切割形成空間任意塊體的自動生成。

2 預備知識

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

有向圖、平面圖、歐拉圖的概念詳見文[6]，歐拉圖為平面圖。二維流形的拓撲表示均是平面圖[7]，三維塊體系統的拓撲關系為歐拉圖[7]。

在本文中，頂點(Vertex)、邊(Edge)、面(Face)一般表示拓撲關系，相應的點(Point)、線(段)(Line/Segment)、空間多邊形(Polygon)一般表示幾何體的空間位置。

2.2 Half Edge及其擴展

Half Edge是一種以邊為中心(Edge－centered)用來存儲關于平面圖、空間多面體、可定向任意二維流形的有關頂點、邊、面關聯關系的數據結構。在此之前，曾有Winged Edge Links、Loop Edge Links、Vertex Edge Links等多種表征三維模型拓撲關系的數據結構[7]。Hlalf Edge一般定義如下:

就三維塊體的搜索對Half Edge進行必要的擴展。涉及有向邊、空間多邊形的定向時以右手螺旋法則為準，即空間多邊形法向向量以符合右手螺旋為正，反之為負。擴展Half Edge如下:

圖1 Half Edge擴展示例圖

圖1 、表1分別給出了一個Half Edge擴展對應的示例圖和對應的關聯表。其中右圖F3表示該面作為邊界面時對應的Half Edge擴展情況。有向邊關聯的所有面已依據其法向矢量與矢量的關系進行“空間左右”排序。

2.3 塊體有效性校核

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

對應ExtendedHalf Edge關聯表 表1

其中:V為頂點個數(Vertex)；E為邊的個數(Edge)；F為面的個數(Face)；L為面上的內部環的個數(Loop)；H為穿透體的洞的個數(Hole)；G為體的虧格(Genus)。

3 三維塊體自動生成法

對隨機結構面切割下的三維塊體自動生成法，假設所有結構面空間數據均已知，其形態為空間多邊形，對只關聯一個邊的頂點、只關聯一個面的邊等“樹枝”均已刪除。則三維塊體自動生成法如下:

(1)初始化結構面為Half Edge數據；

(2)結構面對應空間多邊形兩兩求交，并根據求交結果動態修改其Half Edge對應的Vertex、Edge、Face數據；生成有向邊的Extended Half Edge數據(對任意頂點i、j關聯的邊只需生成一個有向邊的數據)；

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

并置該邊＜LeftFace、RightFace〉已搜索標志；DCL.head()表示雙向循環鏈表的頭元素、DCL.suc()表示雙向循環鏈表當前元素的后繼，DCL.pre()表示雙向循環鏈表當前元素的前驅；

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

設置一待搜索有向邊的集合為:

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

設置一已搜索過的有向面的集合為:

實際程序設計中ListA、ListB可合并為一個集合。

(5)對ListB的所有待搜索有向邊進行搜索，設其中一為e(vm，vn)，其 ExtendedHalfEdge記為 Current EHEDS，對應面的編號為F，則新增一已搜索面FNew至ListC，將面FNew的相關有向邊添加至ListA，動態修改ListB的元素，并設置＜FNew，F〉已搜索標志。其中:

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

(7)LeftFace＝RightFace；

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

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

(9)對(1)～(8)中自動生成的塊體進行規整化，主要是對共面的過個Face和Edge進行合并。

4 實例分析

本文給出一共由21個矩形結構面切割生成塊體系統的實例，相關幾何數據如圖2所示，面－頂點拓撲關系如表2所示。

實例分析面－定點關系表 表2

圖2 實例分析結構面空間位置圖

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

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

部分Extended Half Ege結果 表3

圖3 m8邊關聯圖

圖4 m8搜索塊體線框圖對應的實體圖

5 結 語

基于Half Edge的隨機結構面切割下三維塊體系統自動生成法能有效生成三維不連續變形分析所需的各種塊體，能統一處理凸性塊體與凹形塊體、有限塊體與無限塊體，并將在后續接觸分析與求解中發揮重要作用。基于該生成法生成塊體系統的塊體理論分析與不連續變形分析等將在其他論文中予以闡述。

[1]Shi G H.Producing joint polygons，cutting joint blocks and finding key blocks for general free surfaces[J].巖石力學與工程學報，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].巖石力學與工程學報，2007，26(10)，2043～2048

[4]魯軍.離散單元法的數值模擬及其工程應用.北京，清華大學水利水電工程系，1996

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

[6]徐俊明.圖論及其應用用[M].合肥:中國科學技術出版社，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—)，男，碩士，主要從事巖土工程設計及治理工程研究。