论文****
****硕士毕业论文
简谈法线使用SVD计算顶点法线****毕业论文范文参考
当前位置:中国时代论文网 >> 论文下载 >> 计算机论文 >> 浏览文章
简谈法线使用SVD计算顶点法线****毕业论文

论文导读:

  摘要:对于大多数多边形模型,都需要计算顶点法线。尽管多边形网格在计算机图形学中广泛使用,但是计算法线的方法并不一致。大多数现有的方法都通过加权相邻面法线来实现,也有方法使用曲率计算法线。该文提出了一种不同的方式来计算顶点法线,该方法基于表面法线原始概念进行计算。该方法简单、健壮,并且借助于奇异值分解(SVD)可以在线性时间内完成。与之前的方法比较,该文的方法很容易理解,更自然且能产生很好的结果。

  关键词: 法线;奇异值分解;向量范数;切平面

  1009-3044(2013)23-5331-03

  1 背景工作

  顶点发矢计算的历史可以追溯到十九世纪七十年代,研究者们发明了很多算法。[Gouraud1971]提出了第一个法矢算法,它利用顶点所在的面的法线代表顶点法线,我们称之为MWE(Mean Weighted Equally)算法。[Overveld 1997]给出了该算法的一个扩展版本,它基于非流形曲面但是需要更长时间的计算。[Thurmer 1998]改进了权重,将等值权重转化为依赖于顶点所在的表面之间的角度进行加权。[Max1999]使用角度、边长以及顶点所在的三角区域面积来控制法线的权重。虽然他使用了不同的方式来生成这个系数,但是结合相邻面法线的基本思想没有改变。同时,[Shuangshuang Jin2005]比较了所有这些方法的速度和结果,得出的结论是这个算法[Gouraud1971]是最好的或者是最好的算法之一。因此,虽然上述算法大体上不同,但是它们有一个共同点就是平衡邻接面法线,其中一些算法非常复杂。

  [Meyer 2002 ]提出了一个统一的一套灵活的工具去估计重要的几何属性,包括任意三角形网格的法线和曲率。该方法通过Laplace_Beltrami运算[ Dierkes 92 ]得到法线,它同法线在一方向上,并使用1环邻居作为输入。这种方法计算顶点的平均Voronoi单元,并且必须特殊处理钝角三角形从而降低其可靠性。这种方法试图通过使用曲率定义顶点法线,这就意味着使用网格的二阶微分属性和整体性产生顶点法线。

  然而,我们太习惯于通过这类方式来考虑问题,以至于我们忘记了法线的本质。事实上,法线是网格的第一个差分属性,应当通过基本的方式进行定义,有一种更合理、更有效的方法来计算法线。这个方法的基础是法线的概念,即它应该是顶点所在表面的切平面的法线。这意味着表面顶点和切平面的距离应趋于零。从离散的角度看,从切线顶点v0的邻居顶点到切平面的距离应最小,这就是我们方法的主要原理。

  问题(4)是经典的问题,可以SVD(奇异值分解)解决。该问题的解n是最后一栏的3*3矩阵V的最后一列,满足A=UDVT.这是A的奇异值分解方程。在这里,U和V是正交矩阵,D是对角矩阵,其对角线条目降序排列,T代表矩阵转置。可以在[Hartley 2004]中找到其证明。

  为了减少对于稀疏网格的误差,我们首先标准化(vi-v0)以使得||vi-v0||=1。原因就是(vi-v0)可能是很长的稀疏的网格,标准化可以减少稀疏网格的副作用所带来的影响。在实验中我们发现,这一处理改善了稀疏网格的处理结果,虽然对密集网格没有明显不同。

  最后就是要确保法线有正确的方向。为了实现这一目标,我们只是检查该顶点所在的一个平面的法线,这两个法线的乘积应该不小于0,否则我们将顶点法线再乘以-1。

  我们的方法可以适用于任何由多边形表面构成的网格。简单地说,对任意一个三角形,V的最后一列就是这个三角形所在平面的法线。此外,我们的方法并不依赖于网格中三角形的数目。只要网格基本上代表了所要显示的模型,计算出的法线就非常合适,光照结果非常平滑。

  3 时间复杂度

  如果该模型有n个顶点,e条边和m个面,那么我们需要为O(n)的时间来确定顶点的信息,O(e)的时间增加顶点的相邻顶点,并需要O(m)的时间加入顶点的邻接面一个相邻顶点。对于每一个顶点,我们需要通过相邻顶点建立矩阵A,其中一些往往是相当小。我们需要使用几乎是固定的时间计算V的最后一列,所以总的时间复杂度为O(n+e+m)。对于大多数多边形模型,e=O(n),并且 m=O(n),所以时间复杂度为O(n)。

  4 实现和结果

  从图3和图4中我们可以看到,标准化(vi-v0)对于网格是必要的。图像3和4最明显的差异是在前耳部分,虽然在密集网格中这个差别非常小。对于密集网格,MWE算法和我们的算法效果差别几乎可以忽略不计,你可以从图3的图像5中看出。但是,对于图4的稀疏网格,我们的算法可以产生比MWE算法更好的结果,这一点可以参照图像1的原始模型看出。

  我们在PC机上运行了我们的算法,配置是双核2126MHz的Intel处理器和1G内存。对上面密集网所有顶点法线的计算时间是0.281秒,对稀疏网的计算时间则接近0秒。因此,我们的算法非常快。虽然这个例子仅仅显示了由三角形组成的模型的情形,我们的方法对四边形模式和其他多边形模型显然也是同样适用。

  5 结论

  本文提出了对某一多边形模型计算其顶点法线的新型算法。我们的方法是基于顶点法线的概念,使用奇异值分解规避了非

源于:论文致谢范文http://www.dfholiday.com

线性方程的计算,并且不需要对例外情况进行特殊处理。

  实验证明新算法在健壮性,快速以及产生更好的结果等方面都优于通常的方法。由于非常自然和实现简单,我们可以很容易地使用它取代目前大多数的复杂的加权法线算法。

  参考文献:

   Jonathan Cohen, Amitabh Varshney, Dinesh Manocha, GregTurk, Hans Weber, Pankaj Agarwal, Frederick Brooks, andWilliamWright. Simplification envelopes. In SIGGRAPH ’96 Proc., pages 119-128, Aug. 1996.

源于:论文********http://www.dfholiday.com

简谈法线使用SVD计算顶点法线****毕业论文

本科毕业论文**** ****硕士毕业论文 首先中国时代论文网(http://www.dfholiday.com)!