反求工程中复杂多面体模型的网格简化算法

摘要: 提出一种新的基于顶点删除准则的多面体模型简化算法。该算法使用局部几何和拓扑特征移去满足简化标准的顶点, 并对移去顶点后产生的空洞进行剖分区域划分, 进而分别进行局部三角化。算法实现简单、速度快,能够有效处理高斯曲率近于零而平均曲率较大的网格, 解决了以往一些算法对此根本不能进行简化的问题。实验表明, 该算法可以简化具有复杂拓扑结构的网格模型, 适用于在反求工程中获得的以重构精度为主要目标的多面体模型的简化。
关键词: 反求工程; 模型简化; 三角网格; 三角剖分

反求工程[ 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 2 3 4 5 下一页 尾页 1/5/5