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

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

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

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

大规模网格模型间的快速视觉布尔运算

为了解决产品设计阶段中大规模网格模型间的布尔运算无法实现立等可得的速度瓶颈,提出了一种新算法。该算法利用离散化采样获得射线段点云模型,将三角面片间的3D布尔运算转换为射线段间的1D布尔运算,对相交处的交点进行高精度的求解和插值处理,使得布尔运算速度大为提高,从而大大提升复杂拓扑结构的产品设计效率。通过该算法所获得射线段点云模型可获得等同于基于三角网格的渲染效果,该方法可进行工程应用。     

多边形网格的非流形封闭三角形网格正则化

为了提高基于网格模型的算法与应用的效率和稳定性,提出一种将任意多边形网格模型转化为正则三角网格模型的算法.首先对输入多边形网格模型中非三角形的面片进行三角剖分,然后查找并移除模型中的重合或重叠元素,再通过模型内部三角形求交对模型进行边和面的分割,从而修正模型的拓扑结构;在求交的过程中,根据边和三角形的位置关系对共面求交进行细致的分类处理,减少了求交次数,提高了算法的稳定性;最后循环搜索在网格模型中可以确定法向的种子三角形,通过拓扑结构调整与之相邻的三角形的法向,最终构成一个或多个法向确定的闭合曲面.实验结果表明,该算法能够将多边形网格转化为正则三角形网格模型.     

模型体结构可控装配方法

为在模型内部生成可控的多孔隙结构,提出一种针对三角网格模型的内部结构装配方法.首先对模型对象内部空间进行划分,确定目标装配区域;然后根据设计要求,采用隐函数表达的参数化结构作为模型单元填充装配区域,并通过优化局部区域的性能实现整体设计目标;最后从参数化表达的体结构模型中提取等势面,将其直接转化为三角网格体模型.实验结果表明:该方法能够构建密度、连通性和梯度可控的复杂结构,保证内部结构单元之间的平滑过渡,同时避免因大量布尔运算操作产生的错误.     

基于Catmull-Clark细分的曲面布尔运算基础研究

基于Catmull-Clark细分,提出一种对平面四边型网格进行操作的基础布尔运算,包括曲面求交、裁剪和网格级基础布尔运算,首先将细分曲面的求交转换为对一定细分层次的细分控制网格求交,得到满足一定精度要求的交线;采用局部修改交点处的控制网格拓扑结构和控制网格顶点位置的方法,实现了对细分曲面的裁剪;最后提出一种对一定细分层次的四边形控制网格进行操作的布尔运算,称之为细分曲面网格级布尔运算,包括布尔交、布尔并和布尔差3种运算,并给出了运算的基本原则与应用实例.     

基于空间分解的三角网格模型求交方法

三角网格模型间的求交问题是计算机辅助设计与制造领域的关键问题之一.分析了已有空间分解技术和包围盒方法等的优缺点,并在此基础上提出了改进的空间分解求交方法. 该算法能够精确定位三角形所占的空间网格,一定程度上减少了需要求交的三角形的数量.实验的结果表明,改进的算法提高了采用空间分解进行三角网格求交的计算效率.     

一种提高三角网格模型求交效率的算法

层次包围盒求交算法在求交过程中需要不断分裂包围盒,从而降低了求交效率。针对上述问题,利用该算法可以快速排除不相交三角面片的优点,提出一种更高效的求交算法,通过直接定位2个求交模型可能相交的部位,高效地排除大量不相交的三角面片,得到 2个模型的交线。     

细分曲面求交交线计算方法的研究

主要针对三角网格的细分曲面求交提出了一种有效的交线计算的方法,该方法适用于任意三角网格的细分曲面中.在利用AABB和二部图进行初始控制网格相交性检测后,利用该方法快速有效地求出细分曲面的交线.     

采用图形加速的三角网格实时切分

提出一种采用图形加速的三角网格模型实时切分的方法。针对传统的三角网格实时切分方法普遍效率不高的问题,提出利用Open GL的拾取机制的快速、有效,将屏幕曲线映射到模型上,得到切分边缘的三角面片。并利用网格的AIF(Adjacency and Incidence Framework)数据结构和当前图像场景的视角矩阵优化网格模型交线生成追踪过程。然后将相交的三角面片重新三角化,构建新的拓扑结构。最后分离模型,实现模型的快速切分。实验结果表明,该方法能够快速有效地完成模型的实时切分。     

岩石三维图像裂缝提取方法

提出一种新的岩石三维图像裂缝提取算法。首先对三维岩石孔隙模型的每个连通分量执行表面重建、拉普拉斯网格平滑、网格简化等操作。根据三角网格面积和网格单位法向量方向特征,将三角网格划分为不同类别。利用形状因子判定每个三角网格类构成的三维空间结构是否具有裂缝特征。对具有裂缝特征的三维空间结构所包含的体素点集执行形态学膨胀操作,并与原始三维岩石孔隙模型连通分量的体素点集进行逻辑与操作,与操作结果即岩石裂缝。实验结果表明,该方法具有较好的裂缝提取效果。     

基于八叉树和混合搜索树的地质曲面快速求交方法

为处理地质界面之间的空间相交关系,提出一种新的针对三角地质曲面的快速求交方法。该方法融合优化八叉树法和OBB搜索树方法,可以更快速准确地剔除远离交线的其他三角形。求交剩余的三角形得到交线,应用三角网局部重构和网格优化算法修正交线附近的三角网,最终分割交线两侧的地质曲面,完成2个地质曲面的离散化求交过程。与AABB、OBB和空间分解法相比,该方法在大数据量三角曲面求交中效率优势明显,可以快速准确处理地质模型构建和分析中的曲面求交问题,为三维地质模型自动化构建的实现提供有效支撑。     

三维地质界面网格模型构建算法研究

三维地质模型主要包含地质构造模型和地质属性模型。提出一种局部映射-边界控制的曲面三角化网格模型构建算法,与映射法相比,减少三维空间点映射到二维平面的计算过程,避免因多点到一点的映射关系而生成错误的三角化网格模型。基于地质测量数据特点,原始地质数据经处理后采用点集合形式表示,基于点集数据构建三维三角化网格模型,模拟地质界面的展布形态,控制三角网格质量。采用两种网格边界控制方法,在有边界约束数据和无边界约束数据条件下均能自动更新地质界面三角化网格模型边界。基于断层点数据集测试并展示算法构建的三维三角化网格模型可视化效果,通过断层面三角化网格模型能够反映断层面之间空间位置关系。     

A reliable triangular mesh intersection algorithm and its application in geological modelling

We introduce a reliable intersection algorithm for manifold surface meshes. The proposed algorithm builds conforming surface meshes from a set of intersecting triangulated surfaces. This algorithm effectively handles all degenerate triangle–triangle intersection cases. The key idea of the algorithm is based on an extensive set of triangle–edge intersection cases, combined with an intersection curve tracking method. The intersection operations do not rely on global spatial search operations and no remeshing steps are needed. The intersection curves are introduced into each surface mesh using a unique curve imprinting algorithm. The imprinting algorithm naturally handles degenerate intersection cases of many surfaces at an edge or at a point. The algorithm produces a consistent mesh data structure for subsequent mesh optimization operations. The mesh intersection algorithm is used within a general framework for modelling and meshing of geological formations, which are essential for reliable mathematical modelling of oil reservoirs.     

基于数字地面模型的公路实时三维动画

研究了一种用数字地面模型和公路设计数据实现实时三维动画的方法。首先利用Delauany三角化方法构造数字地面模型，然后将公路设计数据与数字地面模型进行叠加。为解决叠加过程中的相容性问题，提出了先将地界约束边界线插入Delauany三角形网格，然后重新三角化的方法。为加快渲染速度，提出了多分辨率显示和网格数据结构相结合的加速措施。文中的方法在实践中得到了验证。     

三角网格模型分治加工中区域分割算法的研究

提出分治加工策略以保证复杂三角网格模型数控加工同时具有较高的加工效率和加工精度;针对分治加工的需求,提出一种将机械零件三角网格模型分割成具有加工意义区域的算法。算法采用半边数据结构,基于区域生长原理,以二面角结合刀轴矢量为区域生长的驱动信号,实现了三角网格模型内子加工区域的快速分割。为了避免过分割现象,实现了小区域或误判区域的优化合并处理算法。运行实例表明了该算法能够有效实现加工模型的区域分割。     

网格曲面近似“最直路径”的快速计算

为实现网格模型两点间最短路径的近似逼近,提出一种网格曲面上近似"最直路径"的计算方法.利用起点与终点邻域特征获得初始切割面,对网格曲面上的三角片逐步切割求交,扩展"最直路径";在求交过程中逐步调整切割平面的方向,直至终点.实验结果表明,文中方法快速、有效.     

Triangular mesh intersection

This paper proposes an efficient algorithm for finding self-intersections of a triangular mesh. It is very important to restrict, as much as possible, when and where the basic triangle-to-triangle intersection (TTI) algorithm is applied by taking advantage of the geometry and topology of a triangular mesh. To reduce the number of triangle pairs to be checked for intersection, the suggested algorithm employs the visibility information of triangles together with a conventional space-partitioning method. The visibility method works by topology, while the space-partitioning method works by geometry. The complementary nature of the two techniques enables additional improvement of the triangular mesh intersection process. The proposed algorithm has been implemented and tested with various examples. Some examples have been provided to illustrate the efficiency of the algorithm.