使用SVD计算顶点法线

开篇：润墨网以专业的文秘视角，为您筛选了一篇使用SVD计算顶点法线范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

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

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

中图分类号：TP18 文献标识码：A 文章编号：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 结论

本文提出了对某一多边形模型计算其顶点法线的新型算法。我们的方法是基于顶点法线的概念，使用奇异值分解规避了非线性方程的计算，并且不需要对例外情况进行特殊处理。

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

参考文献：

[1] 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.

[2] Ulrich Dierkes， Stefan Hildebrandt， Albrecht K¨uster， and Ortwin Wohlrab. Minimal Surfaces （I）. Springer-Verlag， 1992.

[3] Garland M， Heckbert P. Surface simplification using quadric error metrics[A].In： Proceedings of SIGGRAPH '97[C]， 1997.

[4] Gouraud， H.， Continuous Shading of Curved Surfaces，IEEE Trans. on Computers， C-20（6）， 1971：623-629.

[5] [Guéziec.1995] André Guéziec. Surface simplificationwith variable tolerance. In Second Annual Intl. Symp. on Medical Robotics and Computer Assisted Surgery （MRCAS ’95）， 1995：132-139.

[6] Multiple View Geometry in Computer VisionSecond Edition Richard Hartley and Andrew Zisserman， Cambridge University Press， 2004： 588-596.

[7] Hugues Hoppe， Tony DeRose， Tom Duchamp， John Mc-Donald， and Werner Stuetzle. Mesh optimization. InSIGGRAPH ’93 Proc.， 1993：19–26.

[8] Hugues Hoppe. Progressive meshes. In SIGGRAPH ’96 Proc.， 1996：99-108.

[9] David Luebke and Carl Erikson. View-dependent simplification of arbitrary polygonal environments. In SIGGRAPH 97 Proc.， 1997.

[10] [Max1999]Max， N.， Weights for Computing Vertex Normals from Facet Normals， Journal of Graphics Tools， 1999， 4（2）：1-6.

[11] Meyer， M.， Desbrun， M.， Schr?der， P.， and Barr， A. H. 2002. Discrete Differential-Geometry Operators for Triangulated 2-Manifolds. In Proceedings of VisMath，2002.

[12] Overveld， C.， Wyvill， B.， Phong Normal Interpolation Re-visited， ACM Trans. on Graphics， 1997，16（4）：379-419.

[13] Rémi Ronfard and Jarek Rossignac. Full-range approximation of triangulated polyhedra. Computer Graphics Forum， . Proc. Eurographics ’96.， 1996，15（3）.

[14] Jarek Rossignac and Paul Borrel. Multi-resolution 3D approximations for rendering complex scenes. In B. Falcidieno and T. Kunii， editors， Modeling in Computer Graphics： Methods and Applications， 1993：455–465.

[15] William J. Schroeder， Jonathan A. Zarge， and William E. Lorensen. Decimation of triangle meshes. Computer Graphics （SIGGRAPH ’92 Proc.）， 1992，26（2）：65–70.

[16] Shuangshuang Jin， Robert R. Lewis， David West： A comparison of algorithms for vertex normal computation. The Visual Computer ， 2005，21（1-2）： 71-82.

[17] Marc Soucy and Denis Laurendeau. Multiresolution surface modeling based on hierarchical triangulation. Computer Vision and Image Understanding， 1996， 63（1）：1–14.

[18] Thurmer， G.， Wuthrich， C.， Computing Vertex Normals from Polygonal Facets， Journal of Graphics Tools， 1998，3（1）：43-46.