基于边优化的三角网格简化算法.pdf

基于边优化的三角网格简化算法*) 陈振华1 王永皎2 李际军1 (浙江大学计算机学院杭州310058)1 (平顶山工学院平顶山467000)2 摘要本文在渐进网格算法的基础上,提出了一种新的基于边优化的三角网格简化算法。在基于该方法重建出的多分辨率模型表面上,模型的细节层次(Levels ofDetails,LOD)呈连续分布,并且能够跟随视点位置的变化发生动态变化。实验结果表明本算法运算速度快,显示效果也较好,能有效地支持细节层次模型的表示。关键词网格简化,边折叠,渐进网格,LOD 引言三维网格模型作为一种新的媒体形式,在虚拟现实、生产制造等各个方面的应用越来越广泛。随着三维激光测量和建模技术的不断发展,三维模型测量的精度越来越高,数据量也随之飞速增长,给计算机的绘制、传输、编辑等带来了巨大的压力。解决这些问题的途径之一就是对复杂的三维模型进行简化,用比较简单的几何模型来代替复杂的原始模型,以减少数据量,加快处理速度,节约存储空间。网格简化算法的实质就是减少模型的点和面,但又要逼近原始网格。近年来提出了很多网格简化算法。比如:基于顶点删除、边折叠、三角形删除、三角形折叠、顶点聚类和网格重新划分等简化算法。边折叠算法是Hoppe等人首先提出来的[1],它采用能量函数最优化方法来简化模型,通过引入距离能量、表示能量和弹簧能量,使简化模型是原模型的整体优化逼近。由于优化过程是非线性的。计算量很大,因此该算法的缺点是效率低下。Garland等人[2]用局部二次误差来衡量边折叠的代价,以新顶点到被折叠边的两个顶点相关联平面的距离平方和作为误差量,计算简单并且运行速度较快,简化效果也不错,被广泛应用于模型简化领域。Turk跚提出基于网格重新划分的多边形模型简化方法,该算法产生的网格三角形分布非常均匀,但是牺牲了对原网格的逼近度。本文采用对渐进网格算法进行了研究并进行了改进和优化。 2渐进网格算法渐进网格(ProgressiveMesh:PM) 1996年在SlGGRAPH会议上提出的,在对其研究中发现,在网格优化过程中所定义的三种几何操作中,只有~种边删除操作对最后的网格简化有贡献,因此,他定义了一种新的表示结构一渐进网格来记录边删除过程。这种渐进网格把任意网格表示成一个简化网格和一组记录了网格细化信息的序列, 因此渐进网格模型的原理是每次从原始网格M中删除一条边,逐步将分辨率降低,最后得到一个简化的粗糙网格坛和一系列细节信息记录。根据这一系列的细节信息记录,重新向网格中插入节点和三角形,就可以恢复出具有原始分辨率的模型。同时,PM模型也达到了数据压缩的目的。 3网格简化算法 : Step1输入误差条件 Step2对网格中的每个顶点进行分类,区分边界点和内部点。Step3取点,是否为最终点。 Step4非边界点,获取该点周围的拓扑结构。 Step5对网格进行边折叠操作,折叠误差度量最小的边, 含有边界点的边不进行边折叠操作。如果边的两端点的折叠误差大于给定的值,返回St印3,否则运行Step Step6点在同一群内,删除该点,并重新三角化该点周围的点集。返回Step Step7算法终止。本文的简化算法是基于边的误差度量进行的,将边按误差度量从小到大的顺序进