多边形网格的保形除噪声算法

《多边形网格的保形除噪声算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、多边形网格的保形除噪声算法刘新国鲍虎军彭群生浙江大学CAD&CG国家重点实验室摘　要　本文给出了一个高效的无收缩磨光算法，用于消除多边形网格表示的几何模型表面上的粗糙的噪声，生成光滑的几何模型。我们首先将磨光问题转化为一个能量泛函的极小化问题。但是直接迭代求解该极值问题将产生原多边形网格的极度收缩，从而导致磨光的失败。因此，我们又引入面片重心不变的约束条件，将问题转化为条件极值问题，并给出了一个新的高效迭代求解方法。实验结果表明，本算法不仅能快速地除掉表面上粗糙的噪声，同时保持其形状特征，而且具有运算量少，计算稳定

2、，收敛快等诸多好性质。关键词：　多边形网格，能量泛函，Laplacian算子，曲面光顺一、引　言多边形网格表示几何模型在计算机图形学各个领域得到越来越广泛的应用，这不仅仅因为它简单、实用，能够表示任意拓扑、形状的几何，适合图形硬件处理，还因为人们能够通过很多各种各样的手段获得它。过去大多使用造型软件进行人工搭建，现在人们更喜欢通过对实物模型测量的方法，采用多边形网格（尤其是三角片网格），重建它的几何[4,7,11]。因为实物测量重建的方法不仅简单、快捷，而且能够生成非常逼真、精细的模型。然而，实物测量技术不可避免地

3、带来测量噪声和误差，所以重建后的多边形网格模型的表面总是有凹凸不平的细小噪声，这需要我们有一套平滑算法，对重建几何的表面进行磨光，去除那些噪声。在许多的曲面光顺的文献中[12,13]，最常用的工具是带约束的能量最小化方法。一般地，对参数化的曲面进行磨光的方法都是考虑一种定义曲面上的能量，然后通过求解一组能量最小化方程组以达到磨光的目的。设有一被磨光曲面S=X(u,v)，最基本的一种能量泛函为曲率能量，即两个主曲率的平方和在曲面上的积分：()()22ES=k+kdSò12S由微分几何知识我们知道，一般形式曲面主曲率的

4、求取和估计是非常困难的，因此在实际的曲面光顺算法中，人们通常采用薄膜(membrane)能量：()1()22EmembS=òXu+Xvdudv2S和薄板(thin-plate)能量：()1()222EthinS=òXuu+2Xuv+Xvvdudv2S然而，即使作上述简化，求解能量最小化问题还是一个非常复杂、费时的计算过程，而且结果和所使用的参数有很大关系。为了能够磨光大型的任意多边形网格数据，1995年，Taubin[8]把经典的傅立叶分析推广到离散的二维曲面上去，将二维曲面解释为定义在多边形网格上的函数（或信号）

5、，通过一种对Laplacian算子的线性逼近表示，从而将离散曲面的磨光整形转化为曲面信号的低通1滤波问题。其实早在1994年，Willian等人[10]就使用了一种离散的Laplacian算子进行基于三角形网格的光顺自由曲面造型。另一个与此相关的工作是Kobelt方法[6]，他在一种特殊的局部参数化条件下推导出与Taubin一样的离散Laplacian算子，用于光顺细分插值曲面造型。各种形式的离散Laplacian算子的成功之处在于它们能够光顺大型的多边形网格，因为它们不需要求解复杂的优化方程组，而只是对网格不断地

6、施以Laplacian算子进行磨光迭代，在时间和空间上仅具有线性复杂度。但是，正是这种对Laplacian算子简单的逼近，使得Laplacian算子在处理一些不规则的网格的磨光过程中，会引起几何收缩和变形等不好的结果。对于噪声处理来说，这些收缩和变形是不可接受的。为了防止磨光过程的这种收缩和变形现象，Taubin[8]利用一阶、二阶Laplacian算子的线性组合方法来减少收缩和变形的幅度。然而如何选择组合系数并没有统一的准则，非常依赖于具体被磨光模型本身的性质。Mathieu等人[1]通过保持模型的体积不变的方法

7、来防止收缩现象，即在每一步磨光迭代之后，对所有的顶点位置作一个统一的伸缩变换，使得变换后的模型与原始模型具有相同的体积。Vollmer等人[2]则在磨光过程中，考虑顶点的原始位置，将每一次磨光迭代得到的新点位置朝着原始位置方向拉回一些，以减少收缩和变形。这些算法均是经验的，实际上它们只减少了原始网格的收缩程度。本文将从另一个完全不同的角度来处理磨光过程中的收缩和变形问题，提出了一个无收缩的去噪声算法。该算法的基本思想是在磨光的过程中尽量保持面片的重心不动。这种松弛的约束既保证了模型不会变形收缩，又允许顶点位置有活动

8、的自由度，参与磨光过程。下面我们首先介绍一些基本概念、有关记号和传统的Laplacian磨光算法，然后从能量泛函和约束条件入手推导出我们的磨光算法。最后我们给出算法的一些执行结果和结论。二、基本概念和记号三角形网格是最为常见的一种多边形网格模型，为了方便，在这篇文章中我们将仅仅讨论三角形网格，当然本文中的算法并不局限于此，它适用于一般的多边形网格。一个三角形