布尔运算算法研究及其在地质体建模中的应用*

针对三维复杂地质体建模中存在的问题,提出了布尔运算算法。算法的实现采用四步法,即通过测试、求交、剖分和标记实现了区域划分,选择不同标记的三角面片即可得到不同的布尔运算结果。为解决数值计算误差对运算结果的影响,算法在求交运算前先进行逻辑判断,对共面求交的特殊情况进行处理。该方法已应用到蓝光矿山数字化平台系统中,能够实现任意复杂地质体的建模。     

三维网格模型的布尔运算方法

提出了一种基于三维网格模型的布尔运算方法。首先通过基于方向包围盒（OBB）层次包围盒树的碰撞检测算法,得到实体的相交三角形对;接下来求出两相交三角形之间的交线,建立与三角形的交线拓扑关系;通过分类处理三种交线类型来对相交三角形进行区域划分,得到一系列多边形,并对多边形进行三角剖分形成结果区域;最后根据体的包含关系构建关系邻接表,判断多边形区域的相对于其他实体的内外关系并通过网格模型的拓扑关系,定位表面三角网格区域;同时根据交、并、差等布尔操作,对结果区域进行取舍,得到最终结果。实验结果表明相交部分的岩性与实体的岩性相吻合,验证了该算法的正确性以及可行性。     

三维网格模型的稳定布尔运算算法

给出一种稳定、高效的三维网格模型的布尔运算算法。该算法首先,基于网格模型原始的拓扑关系,结合层次包围盒相交检测实现网格模型相交区域快速定位;然后,采用改进的空间三角形求交算法求解离散交线段数据,并对单个三角形重新进行Delaunay三角剖分;最后,通过建立交线段与相交三角形间的拓扑关系对交线快速跟踪提取,通过局部区域快速分类组合,实现三角网格模型的精确布尔运算。该算法能有效地处理各种特殊情况且运行稳定;程序实现简单,实例证明符合工程需求。     

基于pillar grid三维地质体表面模型提取算法

在油气勘探开发过程中,三维地质建模技术应用越来越广泛。pillar grid是目前主流三维地质建模软件应用的结构化网格,提供储层流体流动的描述方法。如何更加直观地展示地质体构造形态,将地质体网格数据中三维地质体表面模型提取出来在地质建模中具有较高的应用价值。因此,提出一种三维地质体表面提取算法,对基于pillar grid三维地质体数据进行解析,提出其表面模型来辅助计算机可视化展示。该算法主要包含基于pillar grid无断层三维地质体表面模型提取算法和带有复杂断层三维地质体表面模型提取算法两部分。通过实际的三维地质体模型数据进行算法验证,证实该算法能够较好地实现基于pillar grid复杂三维地质体表面模型提取功能,满足实际需求,具有应用价值。     

直接体绘制技术在地质体三维可视化中的应用研究

将直接体绘制技术应用于地质体三维可视化,首先对原始钻孔数据进行插值、网格化等预处理得到满足直接体绘制需要的规则体数据,从而建立反映地层分布的地质体三维标量数据场;然后用直接体绘制技术绘制三维地质体,避免了体元建模方法中在对地质体进行剖切等操作时必须要解决的剖面与体元之间复杂的判断求交等过程。采用该方法实现了对某地区地质体的三维可视化。     

巧用AutoCAD的布尔运算简化复杂实体造型

布尔运算本是布尔代数中的一种运算，现在流行的各种针对光栅图和矢量图的软件（Photoshop、CorelDraw、３Dmax等）几乎无一例外引入布尔运算作为一种辅助绘图手段，AutoCAD中的布尔运算对二维及三维图形都可应用，而且在应用于复杂三维实体造型时比常规方法更显简化。此时可用简单实体构建出复杂的三维实体模型。AutoCAD的布尔运算：并（UNION）、交（INTERSECT）、差（SUBTRACT）。并：UNION命令将两个或两个以上实体合并成单一实体，不论操作对象是否有公共部分；差：SUBTRACT命令将若干被减实体对象减去另外若干要减…     

NURBS体的DEXEL化与布尔运算

NURBS曲面与NURBS体造型技术是目前复杂体造型的重要工具,但复杂体之间的布尔运算求交困难。将NURBS曲面围成的体与NURBS体体素化(VOXEL化)为由一系列平面凸四边形或三角形表示的体,通过DEXEL射线组群与四边形或三角形求交,实现NURBS体的DEXEL化。在同一DEXEL模型空间实现复杂NURBS体之间的布尔运算,所有运算是线性的。该方法可推广到在逆向工程中生成的由三角面表示的体。在Java2.0与Java3D环境下编程实现并验证了该算法,给出了一个机械零件设计实例。     

基于DEXEL体造型技术在飞机复合材料零件设计中应用

飞机复合材料零件结构分为蜂窝结构、夹心结构、空心结构、夹层结构等。在以边界面表示的体造型系统中,难以设计这些复杂结构。在提出的基于DEXEL体造型系统中,通过布尔运算可很容易设计这些复杂结构。通过射线组群与多边形的求交算法实现体的DEXEL化。通过基于DEXEL模型的布尔运算实现复杂体设计。通过大体素可显示体的颜色与材质等属性。该系统在Java2.0与Java3D环境下编程实现。为验证该算法,给出了一个飞机水平安定面翼肋设计实例。     

一种有效的复杂地质体剖面图自动生成方法*

提出了一种基于平面隐函数的实体切割思想和区域自动识别技术的地质体剖面图生成方法。其主要步骤包括：采用平面隐函数实现平面和地质实体的求交运算,生成离散的交线;采用基于KD树的空间索引方法,确定交线的邻接关系,生成地质体轮廓线;封闭的轮廓线将平面划分为多个复杂的区域(内含孔、岛),采用图论的多叉树形式化表达区域存储和组织;最后对多叉树表示的区域进行矢量图案的填充。实验结果表明,该算法有较好的计算效率,是一种比较实用的地质体剖切方法。     

硬件加速的渐进式多边形模型布尔运算

多边形模型的布尔运算中包含复杂的求交计算以及多边形重建过程,精度控制和处理效率是其中的关键.为了降低布尔运算复杂度,提出一种适合硬件加速的基于渐进式布尔运算的多层次细节网格模型生成方法.该方法采用分层深度图像来近似表示多边形实体的封闭边界,将多边形的求交计算简化为坐标轴平行的采样点的实体内外部判断;为了免去各层次细节模型的重复采样过程,渐进式地将边界采样点归并到低分辨率下的立方体中;运用特征保持的多边形重建算法将相同立方体内的边界采样点转换成多边形顶点,根据邻接关系生成网格模型.上述算法使用支持图形硬件加速的CUDA编程并行实现.实验结果表明了算法的可行性.     

二维轮廓布尔运算干涉标志算法研究

提出了一个基于干涉标志的计算二维几何轮廓布尔运算的新算法。该算法采用干涉标志计算二维几何轮廓的干涉索引,根据干涉索引值拾取不同的轮廓段分别得到二维几何轮廓的交集、差集和并集。此算法只通过一次计算就可以得到不同的布尔运算结果集,具有较高的算法效率。     

二维布尔运算中的奇异问题

图形布尔运算的关键是如何处理点、线重合等的奇异情况,详尽列举了布尔运算过程中的各种奇异情况,用一种重叠的思想来描述奇异状态的来源,分析了在各种情况下的交点取舍方法和特征值计算方法,同时提出一种奇异处理算法,使其能够对各种奇异情况进行正确处理,从而提高了二维布尔运算算法的鲁棒性.算法在实验室的自主CAD软件上进行了实现,并进行了大量实验,在重边、重点等多种复杂的情况下均能产生正确结果.     

基于“内点”识别的多边形布尔运算

在多边形内、外侧边界识别的基础上，充分利用多边形本身是一个整体的事实，我们提出了一种基于“内点”(多边形内的点)识别的布尔运算算法，简化了布尔运算的复杂性，从根本上解决了由于多边形问可能存在重合点、重合线而造成的布尔运算不稳定问题。     

一种基于特征几何元素永久命名的快速相交特征检查与判别方法及其应用

相交特征的检查与判别是特征造型领域的一个重要问题,通常的方法是通过在特征体间作布尔运算进行相交特征的检查与判别,但这种方法存在复杂、耗时的缺点,为避免大量的求交运算,提高相交特征检查与判别的效率,文中提出了一种新的相交特征的检查与判别方法,该方法以一系列的面标号查找代替了特征之间的求交运算,从而有效地提高了相交特征的检查速度。     

实体模型的三轴数控粗加工刀轨生成算法

提出一种适合实体模型的三轴数控粗加工刀位轨迹生成算法。首先根据加工行距作一组平行于刀轴的平面，与模型的待加工表面求交，得到一系列交线；再根据精度规划一组垂直于刀轴的分层平面，与上述交线求交，在每一分层平面上判断加工区域，规划出加工刀位轨迹，将每一分层平面上的刀位轨迹较适当的方式连接起来，就构成零件的整体加工轨迹。该算法避免了轮廓环等距、自交处理和布尔运算等复杂的计算过程；同时，对生成开型腔的加工刀位轨迹也是有效的。     

海量数据多边形布尔运算的区域分割算法

研究了一种大数据量的2维多边形,称为海量数据多边形,其边界由直线段和圆弧段组成,顶点很多,形状复杂。本文设计并实现了海量数据多边形之间的布尔运算算法。首先用区域划分的方法快速求解出两多边形的交点,然后判断各交点的出点、入点性质,最后沿着多边形的边界跟踪,并根据并、交、差的不同要求切换跟踪路线,直到形成封闭的回路。运算结果仍为2维多边形。该算法从实用的角度出发,避开繁琐的数学推理,易于程序实现,在实际应用中显著提高了布尔运算的效率。     

一个雕塑实体的布尔操作算法

给出了一个雕塑实体布尔操作的现实算法,在保证效率和精确性的同时确保鲁棒性是算法的目标,实体模型通过裁剪曲面片和半边数据结构来表达几何和拓扑信息。采用了层次求交和交线跟踪的方法来保证曲面片分割和区域分类的一致性,从而克服实践中常见的退化情况。该算法也可以方便地扩展到非流形模型的布尔操作。作为一个实体造型系统的一部分,该算法已经在ＳＧＩ工作站上实现。     

Boolean set operations on non-manifold boundary representation objects

For Boolean operations on geometric models, we have developed an intersection algorithm for non-manifold boundary models with vertices, linear edges, planar faces, and volumetric regions. The algorithm operates by intersecting entities in an ordered manner, from vertex to edge, then to face elements. Singular intersections are systematically handled by determining if an entity in one object is within a tolerance region of the entity in the other object. The algorithm performs Boolean operations between objects of different dimensionality as well as solids. An implementation of the proposed algorithm and the experimental results are briefly discussed.