基于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—)，男，硕士，主要从事岩土工程设计及治理工程研究。