三维网格模型的空间布尔运算

为了快速正确地对各种复杂程度(开放、封闭)的网格模型进行空间布尔运算,根据复式网格的可定向性建立各元素间的拓扑关系,并根据这些拓扑关系判断网格面片的最终去舍,得到布尔运算结果.算法首先对网格方向一致化,然后通过相交测试求出两两相交三角形面片之间的交线,再由相交三角形与它的交线得到多边形,并对该多边形进行三角化,得到"结果交域",最后根据这些"结果交域",以及各元素间的邻接关系判断其他网格的取舍,得到最终结果.实验表明该算法结果正确、计算量少、速度快,同时适应于封闭与开放网格模型.     

利用顶点预测方法实现三维网格的保形简化

针对产品的三维表面用三角网格来表示时,三角形数量巨大的问题,提出了一种基于顶点预测的三角形折叠简化方法。首先根据网格模型的每一个顶点与其周边元素之间的几何拓扑关系,运用投影预测方法来预测三角形折叠的折叠点坐标,然后运用线性插值算子对折叠点坐标进行调整。为进一步保证简化后模型的质量,在采用距离误差控制的同时,引入了角度误差控制方法。实验结果表明,该简化算法在减少模型的三角形数量的同时,有效地保持模型特征,保证了模型表面的光顺。     

复杂采空区激光扫描拼合散乱点云球面投影三角剖分算法

利用三维激光扫描技术对采空区进行探测以建立三维可视化模型,从而准确获取其三维空间位置和形态,是矿山采空区事故隐患综合治理工作中的重要环节.但由于采空区形态复杂,往往需要从多个方位对其进行多次探测才能准确获取采空区完整的三维形态.如何对多次探测点云数据拼合后的散乱点云构建三角网格模型,是实现复杂采空区三维探测建模的关键.本文提出了采空区激光扫描拼合散乱点云数据球面投影三角剖分生长算法,首先选定球心将原位点云投影到球面上得到投影点云,然后对投影点云进行三角剖分,最后将投影点云三角网空间拓扑关系还原到原位点云,从而构建复杂采空区三角网模型.为了有效实现算法,研究了球面投影参数设定、XYZ三向单元栅格点云搜索策略、三角形生成规则、优势顶点边界切分策略、边界闭合策略、不规则三角形优化策略等多种方法.实际应用表明,所研究的算法能够生成优质的采空区三角网模型,为实现复杂采空区三维精确建模及可视化管理提供了重要技术支持.     

三维测量数据的一种三角网格精简方法的研究

反求工程中测量所得的三维数据一般是海量和无序的,为了提高重构的计算速度,减少存储空间,同时突出建模特征,在分析了常用数据精简方法的基础上提出了利用三角网格模型,以排序函数为依据简化数据的一种三角形折叠算法.该算法先以估算曲率的大小对欲精简数据进行划分,然后对各个区域的三角面构造可调加权排序函数.以排序函数为依据由小到大进行三角形折叠,算法以到相关三角平面距离最短的点作为新点来代替被折叠的三角面,以精简前后区域内的顶点法矢标准偏差和排序函数阀值对精简进行控制.试验表明,此算法排序函数构造简单,计算方便,对较光滑的模型数据处理是有效的.     

基于空间离散化的STL模型布尔运算

针对传统STL模型布尔运算方法效率低和精度差的问题是,提出一种空间离散STL模型三角面片的算法,该算法可快速排除大量不相交的三角面片,减少三角面片求交计算次数,提高计算效率.同时采用一种规避奇异位置的算法,避免对奇异位置的复杂计算,解决了布尔运算中奇异点的问题,提高了计算精度.实验结果表明所提算法高效准确.     

基于三角剖分和轮廓分析的船舶焊缝特征识别

为了实现船舶焊接件数字模型中焊缝特征的精确识别,进而提高焊接机器人焊接工艺选择的快速性和准确性,提出了基于三角剖分和轮廓分析的焊缝特征识别算法。首先通过角系数法判断多边形的凹凸顶点,基于凹顶点和三角形旋向的Delaunay三角剖分,构造三维模型表面的三角形网格并生成STL文件;然后基于相邻三角面片的法向量夹角,提取出模型的轮廓线及点;最后根据接头空间位置和最小轮廓线距离识别出焊接接头和坡口形状。测试结果表明,基于三角形旋向的网格剖分适用于如“梳子”等复杂多边形,与其他相关方法相比,其网格平均和关联质量系数分别平均增加12.06%和12.26%,有效降低了畸形三角形的产生并提高了网格质量,而融合轮廓分析后不仅能实现4类接头及10种坡口的焊缝特征识别,而且具有高效、高准确率优势,从而验证了算法的有效性。     

细分曲面造型中的框架级布尔运算

提出一种对实体初始三角网格进行操作的布尔运算，称之为框架级布尔运算．通过该运算可以构造出一个新实体的初始网格，然后采用Loop细分算法完成该实体的光滑曲面造型．在初始三角网格的求交过程中使用注册机制对所得交点的拓扑约束关系进行分类推理，从而对浮点数值容差导致的失误进行了有效控制和纠错．     

基于CDT与布尔运算的露天矿三维建模

为了准确实现露天矿三维建模,实现矿坑模型与矿坑周围的DTM模型无缝连接,以及建立量算模型,将露天矿坑的坡顶线、坡底线与线上的点分别作为约束线与离散点进行约束Delaunay三角剖分(CDT)建立露天矿矿坑模型,用等高线上的点进行Delaunay三角角剖分(DT)形成数字地面模型(DAM),并利用提出的一种新的三维网格模型的空间布尔运算算法对地面模型与矿坑模型作空间布尔运算,使它们在相交处无缝衔接形成同一模型;并选择不同的网格方向实现模型的交、并、差等运算结果,建立方量计算模型,利用"散度定理"实现采剥量计算.这种建模方式方便、快捷,动态更新容易实现、用户干预少.     

三维地质界面建模关键算法研究

采用露头,钻孔以及地震等数据进行三维复杂地质界面建模,关键问题包括三维地质界面模型确定方法,地质界面接触关系处理方法。根据区块地质数据建立地质界面三角网格模型,处理地质界面之间复杂位置关系,为三维地质体建模提供约束面,清晰地描述并恢复地下构造。本文就三维复杂地质界面建模中的关键问题,提出基于几何拓扑关系的地质界面三角网格模型生成算法,地质界面空间位置判断算法。在算法中引入几何拓扑关系,降低算法实现的复杂性,增加算法实现效率。     

三维地质界面曲面建模关键算法

采用露头,钻孔以及地震等数据进行三维复杂地质界面建模,关键问题包括三维地质界面模型确定方法、地质界面接触关系处理方法。根据区块地质数据建立地质界面三角网格模型,处理地质界面之间复杂位置关系,为三维地质体建模提供约束面,清晰地描述并恢复地下构造。就三维复杂地质界面建模中的关键问题,提出基于几何拓扑关系的地质界面三角网格模型生成算法、地质界面空间位置判断算法。在算法中引入几何拓扑关系,降低算法实现的复杂性,增加算法实现效率。     

基于Laplace调和方程的网格重构算法

针对三角形网格向四边形网格的转化问题,基于调和方程构建模型梯度场,追踪表面流线,实现了参数化网格重构。首先,建立了基于离散Laplace方程的三角网格梯度场理论模型、数据结构模型和稀疏矩阵求解方案;其次,提出了局部坐标变换和参数方程相结合求解流线节点的统一算法,并针对流线跟踪无交点、有多个交点等特殊情况,提出了梯度收敛、最短距离和参数极值等优选策略;最后,通过模型实验验证了算法。结果表明,流线网格具有等参、闭合特点,复杂模型网格划分没有歧义,而且网格质量随网格密度增加而提高。因此,相对于传统几何重构算法,数学方法对网格重构表达具有鲁棒性和唯一性,且应用场景更广泛。     

细分自由曲面在工业造型中的应用

介绍了Catmull—Clark细分算法、细分曲面性质和算法特点．给出了一种基于Catmull—Clark细分算法和实体布尔运算的工业造型方法．该方法首先利用布尔运算构造实体，然后从实体提取初始网格，最后采用Catmull—Clark细分算法对初始网格进行计算，从而求出自由曲面．     

DEM快速构建及地形裁剪算法的研究

提出了一种快速构建DEM的算法。它先产生一个包含插值点在内的内插三角形，然后利用此三角形来内插插值点高程；为提高算法对复杂地形的适应能力，利用离散点及地性线对地形进行描述，并保证生成的三角形不跨越地性线。其次，提出了一种基于DEM的对三维地面进行裁剪的分治方法，该方法利用DEM数据生成一个规则的三角网并将裁剪边界插入到三角网中重新构建三角网，通过删除裁剪边界内的三角形来达到对地形裁剪的目的。     

基于最小化最大类内距离的面聚类网格分割算法

介绍了一种简单、有效的三维网格分割算法．该算法是基于最小化最大类内误差的聚类方法．先将表面网格转换成连接图,通过最短路径定义任意两个三角形之间的“距离”,然后利用新的距离度量将传统的聚类算法应用到网格表面分割问题．提出的算法不仅确保使最大类内距离实现最小,而且可以确保每个类别的所有三角形都构成网格表面上单独的一片．提出了一种受限边界直化算法,极大改善了分割后的区域形状．实验表明,这种两步(最小化最大类内距离聚类和受限边界直化)的网格分割算法在区域平面性和区域形状方面都表现出了良好效果．     

基于三角形二叉树的地表模型动态简化算法

多分辨率模型简化技术是实现复杂模型交互式可视化的有效手段。为实现地形漫游 ,提出基于三角形二叉树的地形网格模型动态简化算法 ,实现了与视点相关的连续多分辨率简化及快速动态绘制。算法利用三角形二叉树结构记录三角形的分裂和合并关系 ,在预处理中计算出数据点的误差值 ,绘制时根据与视点相关的各参数确定需保留的数据点集 ,基于二叉树进行三角形的分裂和合并操作 ,动态修改需要绘制的三角形链表 ,得到所需分辨率下的近似网格模型。实验表明该简化算法简单有效、易于实现 ,支持对地形模型的交互式快速绘制     

基于超平面及遗传算法优化的网格简化

基于对目前反求工程中已有方法的分析，引入超平面的概念；通过对三角网格曲率的离散化计算，经过种子点的生长以及区域合并形成超平面。在对超平面删除后留下的空洞进行重新三角化时，利用遗传算法生成具有空间形状优化的简化模型。在此过程中以一种新的编码方式使遗传算法能够适应网格优化的特殊性；通过对变异算子的修改，保证遗传进化的有效性；将交叉算子放弃，避免了新产生的三角网格和已经存在的网格重叠和相交。通过这种方法可以调节形状的优化程度和侧重度。     

复杂地质构造的等值线填充及实现

本文实现了一种基于局部多边形的复杂地质构造等值线图的填充算法.算法基本思想是:先对矩形网格的顶点值采用两段法估计,然后把断层线作为约束条件,将矩形网格划分为若干个的三角形网格,最后在三角形网格内完成等值线的追踪和填充.研究实例表明,该算法在油藏描述可视化中有很好的显示与应用效果.     

Robust Boolean Operation for Sculptured Models

To enhance the ability of current modeling system, an uniformed representation is designed to represent wire-frame, solid, surface models. We present an algorithm for Boolean operation between the models under this representation. Accuracy, efficiency and robustness are the main consideration. The geometric information is represented with trimmed parametric patches and trimmed parametric splines. The topological information is represented with an extended half-edge data structure. In the process of intersection calculation, hierarchy intersection method is applied for unified classification. Tracing the intersection curve to overcome degenerate cases that occur frequently in practice. The algorithm has been implemented as the modeling kernel of a feature based modeling system named GS-CAD98, which was developed on Windows/NT platform.     

Robust Boolean Operation for Sculptured Models

To enhance the ability of current modeling system, an uniformed representation is designed to represent wire-frame, solid, surface models. We present an algorithm for Boolean operation between the models under this representation. Accuracy, efficiency and robustness are the main consideration. The geometric information is represented with trimmed parametric patches and trimmed parametric splines. The topological information is represented with an extended half-edge data structure. In the process of intersection calculation, hierarchy intersection method is applied for unified classification. Tracing the intersection curve to overcome degenerate cases that occur frequently in practice. The algorithm has been implemented as the modeling kernel of a feature based modeling system named GS-CAD98, which was developed on Windows/NT platform.