步骤4: 若链表中存在4 个以上的节点, 保存该三角形△PQR , 并从链表中删除节点Q , 转步
骤2。否则, 判断△PQR 与除Q 点外的余下三点构成的三角形是否构成凸四边形, 如能构成凸四边形, 则按最小内角最大准则进行优化, 并保存优化后的2 个三角形, 转步骤6; 如果不能构成凸四边形, 保存△PQR , 转步骤5。
步骤5: 由链表中最后3 个节点构成1 个三角形。
步骤6: 结束。
在算法2 中, 每一顶点的凸凹性由下面的公式进行判定, 按逆时针顺序从链表中取出三点P、Q、R , 令r = PQ ,w = QR , e = r ×w, n 为平均平面的法向量, 则有: 若e* n > 0, 则Q 为凸点; 若e* n < 0, 则Q 为凹点。
2 数据结构与实例
2. 1 数据结构
本算法不需给定初始网格模型的拓扑信息,就能自动识别网格局部拓扑结构并作出正确的判断处理。由于在算法中要处理大量的三角形, 而且要确定每个候选去除顶点的星形邻域, 因此必须设计一个高效合理的数据结构, 使得算法能够处理数据量大的模型。本算法在数据存储与处理过程中使用的数据结构如下:
(1) 三角形顶点集 以链表形式存储, 链上每个节点记录顶点的x、y、z 坐标值以及指向前一节点和后一节点的指针, 实际应用中还可记录对应的物理属性值。
(2) 三角形表 链表的每个节点记录三角形顶点指针、三角形单位法向量等信息。
(3) 确定每个顶点星形邻域的相关三角形表链表的每个节点记录其星形邻域的三角形指针,且链表中三角形应按该点星形邻域中三角形的顺次邻接情况逆序排列。
2. 2 实验结果
采用本算法进行了2 种不同类型的三角面片模型的简化实验。图6a 是采用基于物理的三角剖分方法生成的原始模型, 图6b、图6c、图6d 是其超面法向量和直线度允差分别为215°、315°、615°和018°、112°、118°时的简化模型。可以看出, 简化后的模型较好地保持了初始网格的形状, 当其简化率达到95% 时, 曲面的边界特征仍然保持得很
(a) 原始模型 (b) 简化模型1
(5704 个三角形) (1996 个三角形, 简化65à )
(c) 简化模型2 (d) 简化模型3
(1152 个三角形, 简化80% ) (314 个三角形, 简化95% )
图6 曲面模型的简化
好。图7a 是由空间剖分方法生成的高斯曲率为零的原始柱状模型; 图7b 是其简化模型, 尽管网格简化率已达到90% , 但网格精度和拓扑特征却没有改变。
(a) 原始模型 (b) 简化模型
(2315 个三角形) (228 个三角形, 简化90% )
图7 柱状模型的简化
3 结论
本算法是针对实体的反求和自由曲面重构开发的, 由于在简化准则中引入了局部拓扑结构的识别, 因而弥补了其它方法存在的不足。算法中的各种参数与网格的形状和结构无关, 可以根据应用的要求设定或在运行过程中动态标定, 对顶点随机分布的任意拓扑形状的2 维流形网格均能自动处理, 尤其对由扫描测量方式获得的数字化点集重构的网格模型更为适用。实验表明本算法简单实用, 所得简化模型效果很好, 可以根据实体重构的不同精度要求, 进行多细节层次模型的自动生成。在算法实现时, 可根据网格顶点的重要度对顶点进行排序, 优先去除那些重要度最低的顶点,从而提高网格简化的质量和速度。进一步的研究包括① 对高维流形和非流形网格的处理; ② 能够进行高效处理的更为适宜的数据结构形式。
反求工程中复杂多面体模型的网格简化算法(四)相关范文