Sta r (V i) 由2 个同心超面组成, 即这2个同心超面的并集为Sta r (V i) 本身。其简化操作见图4, 找到2 个同心超面的公共边V iS 1、V iS 2, 将该折线拉直成线段S 1S 2。这样删除顶点后的空洞便被线段S 1S 2 分割成两部分, 分别对其进行约束三角剖分。
图4 按条件(2) 去除顶点后的空洞剖分边界
准则2 若Star (V i) 为半星形邻域, 设其与V i 点相邻的2 条边界线段为V iS 1 和V iS 2。完全满足下列条件(1) 和条件(2) 方可执行简化操作。
(1) Sta r (V i) 由1 个同心超面组成。
(2)V i 点到过点S 1、S 2 的直线的距离小于用户给定的某一误差值d , 即满足式(4)。
令a = -V iS 1, b =- S 2S 1, 则∣a × b/（b - a ）∣≤ d (4)
其简化过程见图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。
反求工程中复杂多面体模型的网格简化算法(三)相关范文