其简化过程见图5, 以线段S 1S 2 作为模型的边界线段, 并对去除V i 点后的封闭空洞进行约束三角剖分。
1. 4 三角形网格简化算法
基于准则1、2 的网格简化算法包括3 个主要
图5 按准则2 去除顶点后的空洞剖分边界
步骤: ① 计算可移去顶点; ② 移去顶点; ③ 按准则1、2 进行局部三角化。具体过程可用算法1 和算法2 来描述。
算法1 三角形网格简化步骤1: 对顶点集V = {V 1,V 2, ⋯,V n} 中每一点V i, 求出Sta r (V i) , 执行步骤2 到步骤5。
步骤2: 根据Sta r (V i) 中每个三角形的单位法矢, 计算Star (V i) 的同心超面个数, 判断Star (V i) 是完全星形邻域还是半星形邻域。
步骤3: 根据同心超面个数和Star (V i) 特点判断是否符合简化准则1、2, 若符合, 置该点移去标志为真; 否则, 置该点移去标志为假。
步骤4: 对移去标志为真的顶点, 按其符合的准则进行空洞剖分区域划分并分别进行约束三角剖分(参见算法2)。
步骤5: 根据剖分结果修正相关数据结构。
步骤6: 重复以上步骤, 直到顶点集中, 每个顶点均不满足简化准则为止。
算法2 带约束的平面多边形优化三角剖分
步骤1: 计算Sta r (V i) 的平均平面P 的方程,并在该平面P 上建立一个局部坐标系。求出边界多边形中每一顶点在平面P 上的投影, 并用单向循环链表保存顶点, 顺序连接投影点得到一平面多边形。具体过程如下:设平均平面P 的单位法矢为n, 中心坐标为c, x 为P 上一点, 则平面P 的方程为n* (x - c) = A x + B y + Cz + D = 0 (5)
则边界多边形的每个顶点(S j = (x j , y j , z j ) T |j =1, 2, ⋯, ni) 到平面P 的有向距离
d j = A x j + B y j + Cz j + D (6)
由此得S j 在P 上的投影坐标为SPj= S j - d j* n,
令g = SP1- c, 则取P 上的两正交单位向量
b1 = g/︱g︱ b2 = n × b1 (7)
于是可得多边形上任意顶点S j 的投影点SPj的局部坐标为
(uj , v j ) = ( (SPj- c) * b1, (SPj- c) * b2) (8)
步骤2: 计算出多边形顶点链表中每一节点的凸凹性。
步骤3: 在循环链表中顺序取3 个节点P、Q、R , 若Q 点为凸点, 并且由P、Q、R 构成的三角形内不包含其它顶点, 则按式(2) 计算△PQR 的品质系数。求出所有这样的三角形, 并从中选择品质系数值最大的三角形△PQR。
步骤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 维流形网格均能自动处理, 尤其对由扫描测量方式获得的数字化点集重构的网格模型更为适用。实验表明本算法简单实用, 所得简化模型效果很好, 可以根据实体重构的不同精度要求, 进行多细节层次模型的自动生成。在算法实现时, 可根据网格顶点的重要度对顶点进行排序, 优先去除那些重要度最低的顶点,从而提高网格简化的质量和速度。进一步的研究包括① 对高维流形和非流形网格的处理; ② 能够进行高效处理的更为适宜的数据结构形式。
参考文献:
[ 1 ] Tamas V arady, Ralph R M art in. ReverseEngineering of Geomet ric Models - anInt roduct ion. Computer A ided Design, 1997, 29(4) : 255～ 268
[ 2 ] 刘斌, 黄树槐. 快速原型制造技术中实时切片算法的研究与实现. 计算机辅助设计与图形学学报,
1997, 9 (6) : 488～ 493
[3 ] Sch roederW J , Zarge J A. Decimat ion of T riangleM eshes. Computer Graph ics, 1992, 26 (2) : 65～70
[