基于近平面合并的三角网格简化算法
时间：2020-03-11 07:17:56 来源：雅意学习网 本文已影响 人 
摘要：提出一种基于近平面合并的三角网格简化算法，针对三维重建Marching Cubes 算法中产生的大量三角片进行简化。首先依据近平面判断条件将近似共面的三角形合并成一个大的多边形，然后按相应的准则将其重新进行三角化得到更少的三角形面片，以达到简化的目的。该算法在最大化的保留图像细节的前提下，精简了三角片的数目，提高了重建后图像绘制和传输的速率，节省了存储空间和处理时间。
关键词：Marching Cubes 算法；网格简化；超面；三角化
中图分类号：TP391.41 文献标识码：A
Triangular Mesh Simplification Algorithm
Based on Approximate Coplanar Triangles Merging
YANG Jiao, LI Guang, LUO Shouhua
(School of Biological Science & Medical Engineering，Southeast University，Nanjing Jiangsu 210096，China )
【Abstract】 In order to simplify the enormous triangles generated by the Marching Cubes algorithm，an algorithm proposed in this paper presents the triangular mesh model simplification based on approximate coplanar triangles merging．At first，approximate coplanar triangles are merged into one big polygon according to the merge conditions．Then，fewer triangles are obtained through the new triangulation in accordance to certain rules to reach the purpose of simplification．On the premise of maximizing the image detail reservation, the algorithm can reduce the amount of triangles，improve the rendering and transmission efficiency of the image from reconstruction and save the storage space and the time for data processing．
【Key words】Marching Cubes algorithm; mesh simplification; superface; triangularization
0 引言
在三维体数据重建的面绘制方法中，由规则立方体栅格中提取等值面的一个经典算法是Marching Cubes（MC）算法[1]。MC算法通过线性插值的方法确定三角片顶点的位置，用大量的三角片表示等值面，然后用三角形网格来重建三维表面。采用这种方法的计算量和所占计算机存储空间都比较大，而且医学图像的数据量本身就十分巨大,现在螺旋CT图像的分辨率达到512×512,甚至是1024×1024[2]。庞大精细的网格固然可以保证显示对象的逼真度，但由于绘制时间和存储量与三角网格中三角形数量成正比，因此为了更好地实现医学应用上的重建和实时交互,在不降低图像质量的前期下，采用简化的网格模型，可以对三维重建后的图像实行实时显示和人机交互操作。
网格简化的本质是：在尽可能保持原始模型特征的情况下，最大限度地减少原始模型的三角形和顶点的数目。它通常包括两个原则：顶点最少原则，即在给定误差上界的情况下，使得简化模型的顶点数最少；误差最小原则，即给定简化模型的顶点个数，使得简化模型与原始模型之间的误差最小。网格简化主要分为三种典型算法[3]：自适应细分型算法、采样型算法和几何元素删除型算法。DeHaemer[4]提出的算法是自适应细分算法的典型代表, 它利用了输入数据的规整性，根据用户指定的误差容限,通过多次细分来自动生成一个简化模型。该算法具有拓扑结构保持特征,它的缺点在于仅适用于正规网格(如高度场),另外,计算初始供细分用的简化模型比较困难。1992年,Schroeder[5]提出了基于顶点移去的网格简化算法。算法的思想是评价顶点或三角形的重要性，如果顶点或三角形不重要，就直接删除，并对空洞三角化。这个算法的计算量小,时间复杂度为线性,有很好的保细节特性,能保持拓扑结构。由于算法采用局部近似误差质量,在多次迭代后误差会积累,从而影响简化模型的质量,另外
这个算法仅适用于流形物体。Hoppe[6]在1993年提出的网格优化算法是最早引进边折叠简化元操作的算法,它源于一个表面重构算法,通过使一个全局能量函数最小化来简化模型。该算法由于要建立和求解复杂的全局能量优化方程,因而计算复杂性高,很难达到实时。Rossignac[7]给出的算法描述了所谓顶点聚类的算法，这类算法的思想是投影到图像空间中的足够小的区域内的一组顶点可以用一个代表性的顶点来取代。该算法不能保持拓扑结构和小范围的图形细节，但其具有很高的计算效率，还可以简化断开的或非流型的网格。
本文研究基于近平面合并的简化算法，是基于区域生长的贪婪式简化算法[8]的改进。首先利用种子生长的方法把近平面上的三角形进行合并形成多个更大的面（简称超面）；然后对这个超面用较少的三角形网格进行表示。 该改进算法计算量小，简化速度快，能较好的保持输入模型的拓扑结构和细节特征，并且简化模型的顶点为原始模型顶点集的子集，不仅适用于任意三角片表示的复杂模型，而且还可以适用于其它多边形网格表示的模型。
1 超面的生成
近平面合并算法的基本思想是把位于同一平面上的相邻三角形进行合并，形成一个超面，再用数目较少的三角形网格来表示这个多边形。该算法利用类似于种子生长的方法，首先需要选择一个初始的“种子”三角形；然后对该种子三角形相邻的其他三角形进行近平面判断，如果满足条件则融入到超面中，如果不满足就停止生长；最后提取该超面的边界，对其重新进行三角化。
1.1 近平面的判断
如图1所示， ， 分别为相邻两个三角形的法向量。定义近平面参数 ，若满足 ，即 ， 的夹角 为一个很小的值，也就是相邻两个三角面片近似共面。
1.2 种子生长算法
我们将所有体元保存在一容器中，如果小立方体中没有三角面片则不进行处理，从而提高了处理效率。进行种子生长的算法可描述为：
步骤1：首先选择第一个小立方体中的一个三角片作为“种子”三角形，将其压入堆栈并做标记；
步骤2：判断“种子”三角形与该立方体内的其他三角片若满足种子生长的条件，则将其压入堆栈并进行标记；
步骤3：从堆栈中依次取出标记的三角片判断其所在的立方体与它上下、前后、左右的立方体中有无满足种子生长条件的三角片，若有则将其压入堆栈，并进行标记；
步骤4：当堆栈为空时，种子生长完毕，生成一个超平面；
步骤5：返回步骤1，重新寻找能成为新的超平面的种子三角形；
步骤6：重复步骤1到4，遍历完所有的三角面片，找到满足给定条件的所有的超面，则种子生长完毕。
2 超面重新三角化
2.1 超面优化
为了进一步得到更少的三角面片，我们将生成的超面进行下面的优化处理。已知向量 、 ，现定义近似共线参数 ，若满足 ，则认为向量 和 近似共线。如图2所示，组成该超面的其中三条线段 、 、 ，在给定的近似共线参数 下可以用线段 来表示，则超面的顶点数目就减少了， 值设定越大，顶点数目越少，从而可以生成的数目更少的三角形网格。
2.2 超面重新三角化
有几何定理可知，所有内角都小于 的多边形称为凸多边形。有一个内角大于 则为凹多边形。由种子生长生成的超面既有凹多边形又有凸多边形，如图3所示。在三角形重建过程中,不仅要注意新生成的三角形一定要位于多边形内部,而且还要避免三角化产生的网格边与其他边有交错,以及避免填补后造成的曲面突出现象,如三角片与三角片之间有相互交错或区块重复填补的情况。
如图4(a)所示，我们将优化后的超面的各个点按顺序存储起来，然后判断出凸点和凹点。首先对凹点进行处理，使其三角化成为凸顶点。如果是凹顶点，判断凹顶点相邻的前后两个顶点如果是凸顶点，则将凸顶点与与其相邻的两个顶点相连组成三角网格，依次判断直到没有凹顶点为止。然后将最后形成的凸多边形重新保存起来，进行重新三角化，如图4(a)所示按 、 、 、 ．．．．．．交替连接成新的三角形网络。
图4(b)是按照从一个点出发，隔一个点组成一个三角形的连接方式进行重新三角化。在相同顶点数目的情况下，图4(ｂ)中的凸多边形与图4(ａ)中凸多边形的连接方式所得到的三角形数目一样，但是前者在多边形边数较多时，或者多边形成带状时产生的三角形会成细长放射状，效果不好，所以我们采用图4(a)的连接方法。
当共面参数 取值越大时，生成的超面数目越少，从而一个超面所包含的三角片的数目增多。若原图像中存在突出或者凹陷的部分且它们周围的三角片组成一个超面时，则提取超面的轮廓时就会出现几条边界，也就是形成了空洞超面。如图4(c)所示，该超面有两条边界，内部较小的边界就形成了超面的一个小空洞，此时，当再用4(a)的方法重新三角化时就会与原图像存在误差, 取值越大，误差越大。空洞超面的产生是本算法不可避免的一个难点问题。
3 实验结果与分析
在DELL OptiPlex 755，1G内存的PC机上，以Visual C++ 6.0和OpenGL为编程平台，对人体部分头骨的一组螺旋CT扫描数据进行三维重建，CT数据的规模为501×248×121，将改进后的MC算法和标准MC算法进行对照（图5、图6）。表1分别给出了改进前后图像所包含的顶点数目、三角片数目、简化程度以及重建时间。
由实验对照结果可以看出：在给定的近平面参数 和共线参数 下，图像质量基本没有变化，与此同时，三角片的数目却大大减少，三维重建时间有所增加；当近平面参数
推荐访问:网格 简化 算法 基于近平面合并的三角网格简化算法 三角网格简化的一种新方法 模型子集到单一三角形带
