摘要: 提出一种新的基于顶点删除准则的多面体模型简化算法。该算法使用局部几何和拓扑特征移去满足简化标准的顶点, 并对移去顶点后产生的空洞进行剖分区域划分, 进而分别进行局部三角化。算法实现简单、速度快,能够有效处理高斯曲率近于零而平均曲率较大的网格, 解决了以往一些算法对此根本不能进行简化的问题。实验表明, 该算法可以简化具有复杂拓扑结构的网格模型, 适用于在反求工程中获得的以重构精度为主要目标的多面体模型的简化。
关键词: 反求工程; 模型简化; 三角网格; 三角剖分
反求工程[ 1 ]是从一个已有的物理模型产生出相应的CAD 模型或实体模型的过程。在离散数据的反求工程中, 常常用三角网格模型来描述物体。近年来, 以扫描测量为基础的“点云”数据采集的发展非常迅速, 由此生成的三角形网格可多达几万甚至上百万个, 这样不仅占用了大量的存储空间, 也不利于网格的后续处理, 尤其是在快速原型制造领域的应用更是存在着很多不便之处。快速原型制造[ 2 ]以三角形面化模型为基础,经过实时切片处理并通过数控加工生成切片薄层, 这样层层叠加便形成了产品的3 维原型。在基于实物样件的产品开发中, 快速成形机接收在产品反求中获得的三角形面化模型, 如果网格过多,除非采用高效的切片算法, 否则实时切片软件在庞大的三角片群中搜索、跟踪、排序, 直至得到切片截面, 使实时操作变得非常困难, 因此在满足重构精度要求的情况下, 对产品多面体模型进行网格简化操作具有重要意义。目前, 国外对模型简化的研究已有一系列成果。Sch roeder[ 3 ]、V eron[ 4 ]提出了基于顶点删除的网格删减方法; Ham ann[ 5 ]通过曲率计算移去三角形, 从而简化模型; Hoppe[ 6 ]提出了一种整体的网格优化过程, 此后又采用渐进网格[ 7 ]的表示方法来存储和传输三角网格; Isler[ 8 ]提出了一种半实时的模型多分辨率表示方法; Eck[ 9 ]利用小波技术进行模型简化。此外,Deham er、Garland 等[ 10, 11 ]分别应用了自适应剖分和边折叠操作方法进行网格简化。国内在这方面的研究起步较晚, 但也取得了一些富有成效的研究成果[ 12～ 15 ]。作为多分辨率造型的核心技术, 当前的模型简化算法很少从反求工程中测量数据的特点出发进行简化, 一般对图1 所示的高斯曲率为零而平均曲率较大的网格均不能作出有效的简化, 而在以截面测量数据为基础的反求模型中这种情况的存在非常普遍。A lan[ 16 ]提出的一种基于区域生长的贪婪式简化算法能够处理这种情况, 但要解决超面投影轮廓线的自交问题, 算法比较复杂。
图1 高斯曲率为零的三角网格
笔者提出的算法采用一种新的简化准则进行顶点的删除, 能够保持原模型的棱角特征。与其它算法相比, 本算法不仅能够有效简化图1 所示的一类网格, 而且对顶点随机分布的任意拓扑形状的网格均能自动处理。
1 算法描述
本算法只考虑由2 维流形网格表示的3 维模型, 它是一种静态网格简化算法, 既可处理表面不连续问题, 也能进行拓扑上的简化。由于在反求中并不涉及模型简化实时生成的问题, 而且在重构误差容许的情况下, 冗余顶点的数量是有限的, 因此静态方法完全可以满足实际的需要。算法采用双重简化准则进行顶点删除, 其最终得到的简化模型的顶点为原模型顶点的子集, 避免了因引入新点而可能使重构误差超过允许范围的情况。为了便于进一步叙述, 首先引入一些基本概念。下面所提到的所有点仅限于多面体模型上的
顶点。
1. 1 基本概念
定义1 给定任意2 个三角形T i、T j , 若T i、T j 具有1 条公共边, 则称三角形T i、T j 是相邻的,
否则是不相邻的。定义2 以模型上V 点为顶点的所有三角形组成的区域定义为V 点的星形邻域, 记为Star (V )。若这些三角形彼此顺次邻接形成封闭的环形区域, 则称为完全星形邻域, 否则称为半星形邻域(见图2)。
图2 V 点的星形邻域形式
定义3 设Star (V ) 中每个三角形的法向量为n i, 中心坐标为ci, 面积为A i, 那么由式
定义的法向量n 和中心c
构造的平面定义为V 点星形邻域的平均平面。
N = ΣniA i/ΣA i n =N/|N| c = ΣciA i/A I (1)
定义4 若Star (V ) 为半星形邻域, 则定义V点为边界点, 以V 点为顶点且不为邻域中三角形的公共边的2 条线段为与V 点相邻的2 条边界线段。
定义5 令Aj ( j = 1, 2, 3) 为三角形T i 的内角, 则三角形T i 的品质评价系数Ri 由式(2) 给定。Ri 越大, T i 的品质越好。Ri = (Σ3j= 1co sAj ) - 1 øRi ∈ [0, 1 ] (2)
定义6 在Sta r (V ) 中, 设有m 个顺次邻接的三角形组成集合{T iû j = 1, 2, ⋯,m }, 对于用户给定的某个误差值H, 若该集合的平均平面的单位法向量{nx , ny , nz } 与集合中每个三角形T j 的单位法向量(njx, njy, njz) 之间的夹角满足式(3) , 则称由该集合的三角形构成的多面体为点V 的一个同心超面。arcco s (njxõ nx + njyõ ny + njzõ nz ) ≤ H (3)
1. 2 网格简化原理
目前, 对复杂模型网格的简化达到既要保持网格形状不变, 又要使网格数量少的要求是非常困难的。本算法的基本思想是根据候选去除顶点的星形邻域的局部拓扑情况, 作出顶点取舍判断。若该邻域为一超平面, 说明该处较为平坦, 当该顶不为边界点时可以删除该点, 否则, 对与该顶点相邻的2 条边界线段进行拉直操作检查; 若该邻域存在2 个同心超平面, 说明该顶点处存在几乎位于同一直线上的2 条棱边, 可以进行折线拉平操作; 若该邻域存在3 个以上同心超平面, 说明该顶点曲率较大或为角点情况不应删除。由此给出2 条准则, 按照准则就可以对模型进行简化操作。
1. 3 简化准则
一个好的简化准则不仅要使原始模型的顶点删减率高、计算量小, 而且简化后的模型要尽可能地保留原模型的拓扑性质。以往一些算法单纯根据候选去除顶点的曲率或到其星形邻域平均平面的距离等准则作出顶点取舍判断, 都不同程度上存在着边界失真和保留伪点的情况。本算法由于注重了网格局部拓扑特征的识别, 因而有效地克服了上述不足。
准则1 若Star (V i) 为完全星形邻域, 满足下列条件(1) 或条件(2) 均可执行简化操作。
Sta r (V i) 由1 个同心超面组成, 即该同心超面就是Star (V i) 本身。如图3 所示, 此时删除顶点, 并对删除顶点后的网格空洞进行约束三角剖分。
图3 按条件(1) 去除顶点后的空洞剖分边界
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 &nbs