利用半边数据结构实现三维网格模型的简化方法

具体实施方式

本发明的核心思想是将半边数据结构与改进的二次误差准则(QEM)结合起来进行网格简化。由于半边结构在点、线、面邻接关系查询方面有着优良的特性，因而特别适用于网格简化操作。同时由于QEM在处理一类已知法向量信息的三维模型时效果不是太好(如用MarchingCubes重建出的三维医学模型，其视觉效果严重依赖于通过梯度计算出的法向量，直接用QEM化简这类模型效果很差)，本发明对其进行了一定的改进，将重建过程中的法向量信息融入到顶点的误差矩阵中，从而提高了简化模型的质量。

下面结合附图详细描述本发明的网格简化算法。作为一种具体的实现方案，结构框图见图1。主要包括三个步骤：构建半边结构，初始化和化简。其中第三步还包括合法性检查、边界处理等方面。下面对其逐一介绍。

构建半边结构

图2给出了半边结构的基本概念以及用其表示的网格模型。如图中所示，边e被分为两个具有相同端点但方向相反的边e1、e2，e1、e2就称为边e的两个半边，同时e1、e2构成一组邻居半边。发出半边的顶点称为半边的起点，半边指向的顶点称为半边的终点。如半边e1的起点为v2，终点为v1。边e两侧为它的两个邻面，每个邻面包含三条半边。采用半边数据结构时，我们将模型中边的信息存储在半边表中，而不是边表中。

由图2可以看出，模型中每个面的三条半边构成了一组循环，其方向既可以是顺时针也可以是逆时针，但所有的面中半边循环的方向必须一致。显然，半边结构只适用于流体结构，因为非流体结构中会出现一条边的邻面超过两个的情况，这时其半边的邻居半边不唯一。

半边数据结构的灵活性很强，可以根据不同的需要构建不同的顶点表、面表和半边表。事实上，半边结构的优点就在于它能方便的进行点、线、面之间邻接关系的查询而无需记录太多的信息。在我们将半边结构应用于面片化简当中时，采用下面几个简单的结构即可得到所需要的一切信息，同时边折叠后点、线、面之间邻接关系的更新也相当简单。

在半边表中，每条半边所要记录的信息可用如下的结构来表示：

Struct HalfEdge

{

       Vertex^*vert；∥该半边的起始点

       HalfEdge^*pair；∥该半边的邻居半边

       HalfEdge^*next；∥该半边的下一半边(在同一面内)

       Face^*face；∥该半边所在的面

}；

在顶点表中，无需记录顶点的邻边、邻面。除了必不可少的顶点坐标和法向量外，只需要记录由该顶点发出的所有半边中的任意一条即可。顶点结构如下所示：

Struct Vertex

{

    float vcoord[3]；∥顶点坐标

    float ncoord[3]；∥顶点法向量

    HalfEdge^*he；∥由该顶点发出的任意一条半边

}；

在面表中，每个面只需记录其所包含的半边循环中的任意一条半边。面结构如下所示：

Struct Face

{

       HalfEdge^*he；∥该面所包含半边循环中任意一条半边

}；

采用上述结构，我们可以很方便的查询点、边和面之间的邻接关系。如某条边的两个端点及两个邻接面可用如下方式得到：

Vertex^*vert1＝he-＞vert；       ∥端点1

Vertex^*vert2＝he-＞pair-＞vert；∥端点2

Face^*face1＝he-＞face；         ∥邻接面1

Face^*face2＝he-＞pair-＞face；  ∥邻接面2

由于一个面内的三条半边构成一组循环，因而在对一个面的边进行操作时可用如下简单的循环来完成：

HalfEdge^*the＝face-＞he；

do{

    ∥对半边进行操作

    the＝the-＞next；

}while(the！＝face-＞he)；

由图2还可知，由一个顶点发出的半边也能够构成一组循环，因而与该顶点有关的信息可用与上类似的方法来得到。如通过下面的循环就可得到该点的邻接边、邻接点和邻接面。

HalfEdge^*the＝Vert-＞he；

Vertex^*VertNb；

Face^*face；

do{

the＝the-＞pair-＞next；∥the为顶点Vert的一个邻接边

VertNb＝the-＞next-＞vert；∥VertNb为顶点Vert的一个相邻点

face＝the-＞face；∥face为顶点Vert的一个邻接面

}while(the！＝vert-＞he)；

三维网格模型一般只包含顶点表和面表，顶点表反映模型的几何信息，面表反映模型的拓扑信息。我们可以很方便的在读入数据的同时构建半边数据结构。需要说明的一点是半边表中邻居半边pair的查询，通过整个半边表进行查询显然会耗费太多的时间。这里我们首先为每个顶点开辟一块内存用于存放该顶点的邻接面，在查询pair时只在该邻域范围内进行查询，等整个半边结构构建完毕后再将这些内存释放掉以为后面的处理节省内存空间。

初始化

初始化的目的一是计算每条边折叠后的代价，二是计算边折叠后新点的位置。对于第一点，下面有详细的描述；而对于第二点，由于我们采用无需计算新点位置的半边折叠作为拓扑操作，因而这一步可以忽略。图3为半边折叠的示意图。由图可知，半边折叠类似于边折叠，所不同的只是在半边折叠中，终点即是新点，起点被“拉”到终点的位置。它可以看成是无需计算新点位置的边折叠操作，同时也可以看成是不用重新三角化的顶点删除操作。

为了计算边折叠的代价，我们采用Garland于1997年提出的二次误差准则并对其进行了一些改进。在读入网格数据时，我们首先判断原始数据中有无法向量信息。如果没有，则直接采用Garland提出的二次误差准则；如果有，则采用我们改进的二次误差准则。下面分别对其进行描述。1.二次误差准则

根据解析几何理论，平面方程可表示为：n^Tv+d＝0，其中n＝[abc]^T为平面的法向量。如果n为归一化的法向量(a²+b²+c²＝1)，则空间中任意点v＝[xyz]^T到该平面的距离平方可表示为：

             D²(v)＝(n^Tv+d)²＝v^T(nn^T)v+2(dn)^Tv+d²(1)

定义一个4×4的误差矩阵 $>>Q>=>\begin{array}{}>>>>b>T>>>>c>>>>>,>>>其中A＝nnT为一3\times 3矩阵，b＝dn为一3维列矢量，c＝d2为常数。如果点的坐标采用齐次表示v＝[xyz1]T，则(1)式等价为：\end{array}$

                       D²(v)＝v^TQv＝Q(v)

这种表示方法可以很容易推广到点到一组平面的距离： $>>>E>Q>>>(>v>)>>=>>\Sigma >i>sup>>D>i>2sup>>>(>v>)>>=>>\Sigma >i>>>Q>i>>>(>v>)>>=>Q>>(>v>)>>->->->>(>2>)>>>>$

由于Q_i(v)+Q_j(v)＝(Q_i+Q_j)(v)，其中 $>>>Q>i>>+>>Q>j>>=>\begin{array}{}>>>>A>i>>+>>A>j>>>>>b>i>>+>>b>j>>>>>sup>>b>i>Tsup>>>+sup>>b>j>Tsup>>>>>>c>i>>+>>c>j>>>>>>>>，因而(2)式中最右端的Q可表示为$ >>Q>=>>\Sigma >i>>>Q>i>>>>。也就是说，如果要计算某个点到一组平面的距离，只需要先计算出每个平面的误差矩阵Q，相加得到该点的误差矩阵Q，再代入(2)式即可。对于要折叠的边(v$\end{array}$_i，v_j)，可先通过v_i、v_j各自周围的邻面计算出Q_i、Q_j，而折叠后新点v_new对应的Q_new只需将Q_i与Q_j相加，即Q_new＝Q_i+Q_j。Q_new(v_new)就是将边(v_i，v_j)折叠到点v_new的代价。2.改进的二次误差准则

我们对二次误差准则进行改进主要是针对一类已知精确法向量信息的三维模型。这类模型中顶点法向量的方向通常对模型的视觉效果起着重要的作用，且一般不是通过计算顶点周围邻面法向量的加权和来得到。例如通过Marching Cubes重建出的三维医学模型，其法向量是在重建过程中通过计算体素梯度来得到。在我们将QEM算法直接应用到这类模型时，效果不是太好。为此我们进行了下面的改进：

假设v＝(x，y，z)^T是模型中的一个顶点，n＝(a，b，c)^T是顶点v归一化的法向量。我们可以假想有一个平面P，它过顶点v且以n为法向量。也就是说，P是最能代表顶点v方向的平面。在构造顶点v的误差矩阵Q_v时，我们不仅仅要考虑顶点v周围的邻面，还要将最能代表其方向的虚拟平面P所提供的信息考虑进去，即： $>>>Q>v>>=>>\Sigma >i>>>Q>i>>+>w>>Q>P>>>>$

其中Q_i为顶点v周围第i个邻面所对应的误差矩阵，Q_p为虚拟平面P对应的误差矩阵，w为加权系数。

由公式(1)可知，一个平面的误差矩阵只和其平面方程有关(法向量必须归一化)。对于虚拟平面P，我们知道其归一化的法向量n以及该平面上的一个顶点v，因而很容易求出其平面方程中的第四个系数d＝-ax-by-cz。然后就能构建出虚拟平面P对应的误差矩阵Q_p，既而得到顶点v的误差矩阵Q_v。这种方法虽然简单，但却能较好的提高这一类三维医学模型在简化后的质量。图9(c)说明了这一点。

在这种方法中，加权系数w可以由用户自己调节，实验证明w取得过小，对结果很难有影响；过大，在提高平坦区域化简效果的同时又可能降低模型的整体效果。我们在实际过程中取点v周围邻面的个数作为加权系数w，w的取值范围为1至10，结果证明这时的效果相对较好。

计算完每条边的代价后，还要将其按照代价值从小到大的顺序进行堆排序。在化简过程中，每次从堆中取出代价最小的边进行折叠。这里需要说明的一点是：由于一条半边被折叠后，其邻居半边也必将被折叠掉，因而没有必要把每条半边都放进代价堆中。只需按边的个数来设定堆的大小，每条边的折叠代价为构成该边的两个半边折叠代价中较小的值，而新点为折叠代价较小的半边的终点。

化简

化简过程主要包括以下几个步骤：

1.从代价堆中取出代价最小的边，进行合法性检查。如果不合法，则不进行折叠。

2.对于一条合法的边，判断其是否满足边界条件。如果满足，则要进行特殊处理。否则，按正常情况进行化简。

3.边折叠后，更新相应的点、边、面的邻接关系，重新计算相关的折叠代价，重新进行堆排序。

4.重复以上步骤，直至达到要求。

合法性检查

通常情况下，一次边折叠前后相邻平面的方向不会相差太多，因而对模型几何形状的影响也不会太大，但有时也会出现例外。如图4所示。当点v5折叠到v1时，边(v3，v5)变为(v3，v1)，与(v2，v4)发生了交叉。这时将模型投影到屏幕上则有可能产生多边形空洞。

为了避免在折叠过程中出现这种情况，通常采用的方法是比较需要改变连接关系的平面在折叠前后法向量之间的差异，如果大于某个阈值，则认为不合法，不进行折叠。但这种方法的一个主要问题是很难选择合适的阈值。这里我们采用了一种更为有效的方法。

如图5所示，如果要折叠半边v0-＞v1，也就是说将v0折叠到v1，我们采用下面几个步骤进行合法性检查：

1.从v1开始找到v0周围所有的相邻点v1，v2，...，vn(如图5中(a)，n＝5)，然后计算出v1，v2，...，vn的平均平面(图中没有画出)。

2.过线(v1，vi)(3≤i≤n-1)分别做n-3个垂直于平均平面的平面，记为Pi，如图5中(b)与(c)所示。

3.平面Pi将点集(v2，...vi-1，vi+1，...，vn)分为两部分：(v2，...vi-1)和(vi+1，...，vn)。如果每一部分的所有点都位于平面Pi的同一侧，并且这两部分的点位于平面的两侧，则认为是合法的折叠，否则是非法的。

边界处理

模型中的边分为两类，内部边和边界边。内部边有两个邻接面，并且对应着两条互为邻居的半边。边界边有一个邻接面，只对应一条半边，该半边没有邻居半边，表现在数据结构中就是其pair属性为空。相应的，模型中的顶点也可分为两类，内部点和边界点。内部点的所有邻边均为内部边，而边界点的邻边中至少有一条是边界边。

对于半边折叠，根据半边起点和终点的特性可分为四种情况：

      1)两个点都是内部点；

      2)起点是内部点，终点是边界点；

      3)起点是边界点，终点是内部点；

      4)两个点都是边界点；

其中前两种情况均可以按照正常的过程进行化简。第三种情况我们不化简，因为这种情况是将边界点折叠到内部点，对边界形状的影响较大。对于第四种情况，我们允许化简，这是由于当化简掉的三角片数目较多时，边界边占的比例会增大，如果完全禁止化简边界边，那么在进行进一步简化时，就只能化简模型中的其他部分，这样边界虽然保持较好，但其他部分效果就会差许多。我们在初始化的时候在边界边上作一个通过该边界边并与其所在三角形垂直的平面，在计算误差矩阵时把这些平面也考虑在内，这样能够有效的保证边界边不至于很快就被化简掉。而当面片数量较少时，则会适当的自动合并一些边界边。由于只是边界点之间的相互合并，而且数目不会太多，因而也可以较好的保持边界特征。这里需要注意的一点是，边界点发出的所有半边无法构成一个像内部点那样的循环，因此在程序实现时需要做特殊处理。

实现

每一次边折叠后邻接关系的更新，折叠代价的重新计算以及堆排序与其他方法相差不大，这里无需重复。所不同的一点采用半边数据结构在边折叠后对于面表的更新仅仅是将折叠掉的面从面表中去除而无需其他操作，同时顶点表和半边表的更新也相当简单，因而能够大大提高简化速度。

我们用C++语言实现了本发明所描述的算法，并且在几个不同的数据集上作了实验。所有的实验都是在一台PIII 800，128MB内存，操作系统为Windows 2000的PC机上完成的，显示部分使用了标准的OpenGL图形函数库，所用显卡为GeForce 2 MX-400/32MB。

图6、7、8、9为几组实例。图6中的原始地形模型有将近200,000万个三角片，在化简了将近99％后(3,000个三角片)仍能保持较好的特征，并且边界保持的也很好。图7(b)，(c)分别为将原始兔子模型简化96％，99％后的模型。图8为不含任何边界的流体模型，在简化了90％后仍然具有较好的效果。图9中(a)为重建后的人体膝盖模型，其法向量在重建过程中通过计算梯度来得到，(b)、(c)分别为用Garland的原始QEM算法及本文改进的QEM算法进行化简的结果，可以看出本发明的改进后的效果明显好于改进前的效果。

表1给出了Garland算法与我们的算法运行速度对比。由表中数据可以看出，我们算法的速度明显快于Garland算法的速度。

                                    表1