第37卷
第8期
Vol.37
No.8
·博士论文·
计算机工程 ComputerEngineering
文章编号：1000—3428(2011)08—0016—03
文献标识码：A
2011年4月 April 2011
中图分类号：TP311
三维复杂地质体的布尔运算算法研究与实现
王红期“，张杏菊"，卢新明“2
(1.山东科技大学信息科学与工程学院，山东青岛266510)；
2.山东蓝光软件有限公司，山东泰安271000)
摘要：提出一种稳定快速的三维复杂地质体的布尔运算算法，该算法不需要跟踪交线，利用带折扑信息的交边对实体区域进行分类，避免面在体内的判断，提高运算速度。算法在进行布尔运算前解决了数值计算误差引起的相关分类间的冲突，保证运算的稳定性。将该方法应用于蓝光矿山数字化平台系统，实践结果证明其适合数据分败、数据密集及带孔润的实体，特别是大规模、奇异的三维支杂地质体。关健通：三维建模；布尔运算；地质体；稳定性；求交运算
ResearchandImplementationofBooleanOperationAlgorithm
for3DComplexGeologicalBody WANG Hong-juan'-, ZHANG Xing-li', LU Xin-ming"2
(1. College of Information Science and Engineering, Shandong University of Science and Technology. Qingdao 266510, China
2. Shandong Lionking Sofrware Co. Lid., Tai'an 271000, China)
[Abstract] A fast and stable algorithm of Boolean operation of complex geological bodly is proposed. The algorithm does not require tracking sauoeao iseooo saa aeansaoa inside the bodies, and improves the speed of operation, At the same time, before Boolean operations the algorithm resolves the conflict caused by the numerical calculation errors between the relevant categories, and ensures the stability of operation, This method is applied to LionKingSoft digital mining platfoms system and the bodies of data-dispersive, data-intensive and with holes, especially the massive, exotic three-dimensional complex geological bodies.
[Key words] three-dimensional modeling; Boolean operation; geological body; stability; intersection operation DO1: 10.3969/j.issn.1000-3428.2011.08.006
1
概述
实体布尔运算是CAD/CAM系统中不可缺少的组成部
分，也是三维建模和三维造型的核心技术，快速及稳定的布尔运算算法一直是人们努力追求的日标。但对于复杂地质体来说，交、并、差布尔运算的稳定性和运算速度一直是两大难题。由于三维复杂地质体的建模是按直线方式进行2个实体剖面之间的连接，因此当遇到呈曲面的陷落柱、断层或者断层破碎带时，难免会使相邻的地质体相交，这样地质体与断层实体之间的吻合关系就很难在建模实体中完整地反映出来，需要用布尔运算来解决此类间题。此外，利用布尔运算在已构建的地质模型上进行各种地质应用分析(如井巷切制、隧道开挖、土石方计算、矿体圈定、爆破效果模拟)也对布尔运算的稳定性提出了更高的要求。三维实体布尔运算比较复杂，特别是对于复杂的地质体。目前，许多商用三维软件只适用于规则儿何体的布尔运算，对复杂地质体的布尔运算会出现孔等错误。
文献[1]采用非正则精确模型作为儿何对象数据结构，基于该模型进行数据对象的层次求交，实现网格模型的布尔运算。该算法虽然避免了计算误差引起的裂纹以及拓扑生成的不一致，但非正则精确模型结构复杂，获取网格模型交线过程繁项，求交速度慢。文献2)采用邻接表作为网格模型数据结构，建立曲面模型中三角面片的包围盒，遮历包围盒获取相交的三角面片并计算其交线段，将所有交线段排序获取 2个模型的交线，根据交线创分网格模型，实现网格模型的
万方数据
布尔运算，但该算法雷要对交线进行排序并进行点在体内的判断，算法效率低。文献13提出一种三角网格模型的动念空间索引结构，通过该结构快速获取相交区域，并对求出的离散交线段进行排序获取交线，根据交线细分相交三角面片，将三角网格模型沿交线分割成2个子网格模型，实现网格模型的布尔运算。该算法虽然能提高数据密集的三角网格模型的布尔运算效率，但不适用于数据分胶、带孔带洞的复杂地质体。
以上3种算法在进行布尔运算时没有同时从算法的稳定性和运算速度2个角度进行系统分析。尤其对复杂的地质体，要求有良好的速度和稳定性。如果稳定性不够，可能导效运算失败；由于组成复杂地质体的点面数据量大，因此如果运算速度太慢，也会对系统的应用造成困难。本文算法采用体积判断和面积判断，对运算容差进行了统一，在进行布尔运算之前解决由数值计算误差所引起的相关分类之闻的冲突，提高了算法的稳定性。在求交运算过程中保存完整的点、线、面、体之间的拓扑关系，不需要跟踪交线，利用交边的拓扑 98 软件开发”(2009AA062700)；国家科技型中小企业技术创新基金资助项目“矿山安全生产综合决策支持系统”(08C26213702008）
作者简介：王红期(1974一)，女，博士研究生，主研方向：布尔算法，计算机图形学，三维建模；张否，博上研究生；卢新明，教授、
博士、博上生导师收募日期：2010-09-10
E-mail: emilywanghj@126.com