一种基于逆Loop细分的渐进网格生成方法

摘要

本发明公开了一种基于逆Loop细分的渐进网格生成方法，它属于几何体造型技术领域，特别是涉及一种基于三角形网格的曲面简化方法。对于任意具有细分连接性的三角网格M

说明书

技术领域

本发明属于几何体造型技术领域，特别是涉及一种基于三角形网格的曲面简化方法。

背景技术

三维图形的表示通常是对三角形网格进行渲染而得到的。在几何造型中，为了使所描述的三维图形具有较强真实感和光滑度，常常需要高度复杂和高度细节化的三角网格模型。曲面细分是一种非常成熟的生成几何造型的方法，所生成的网格是重新网格化的网格(Remesh)，具有细分连通性的，并且易于网格编辑和网格分裂等操作。另一方面，随着三维扫描设备的普及，高密度任意拓扑网格数据的获取变得越来越容易。然而，这些网格数据并不具有细分连接性，需要对网格数据进行重新网格化。另外，即使网格的拓扑具有细分连接性，其网格的数据也不可能正好是某一细分模式的极值曲面，网格数据与细分曲面的差作为曲面细分数据保存，根据需要进行取舍处理。

重新网格化是任意拓扑网格多分辨率分析的重要一环。Matthias Eck最早引入细分方法重采样对任意网格进行多分辨率分析。此方法对原始网格M，选择一个适当的初始网格M0作为参数域对M进行参数化，然后对M0用细分进行重采样，得到具有细分连通性的新网格。Aaron Lee等人通过建立任意拓扑网格的多分辨率参数曲面(MAPS)给出了一种重新网格化的方法；Kobbelt等人提出了一种称为收缩包围(Shrink wrapping)的重新网格化方法，周海等提出了利用细分曲面重建网格的方法；李桂清等分析了带尖锐特性的细分曲面，给出了曲面拟合的方法。上述方法均能较好地生成具有细分连通性的Remesh。

Hoppe首先提出了渐进网格(Progressive Mesh)的概念，并用渐进网格把任意网格表示成高效、无损并具有连续分辨率的编码，同时给出了渐进网格有效的实施方法。罗笑南等提出了基于插值型逆蝶形细分的渐进网格生成算法，并渐进网格应用于移动环境下的图形传输和图形渲染，解决了移动设备上的三维图形显示问题，但是蝶形细分顶点的仿射组合相关2-邻域的顶点，且相关联的顶点数目较多，大大影响了渐进网格生成和图形渲染速度。

发明内容

本发明针对以上的不足，提出了一种基于逆Loop细分的渐进网格生成方法，首先将网格中的冗余信息分批删除；最后形成由一个基网格和一系列误差值组成的渐进网格。本发明适用于具有细分连通性的三角形网络，对于任意网格首先要做预处理。本算法将逼近型细分模式在逆细分过程中作为插值型细分模式处理，算法适用于插值型、逼近型等多种细分模式，文中以Loop逆细分为例对算法加以说明。另外，由于Loop细分模式的顶点仿射组合相关联的顶点数目少，使得网格简化和网格重建过程的运算速度相对较快，在实际应用中更为有效。

为了实现发明目的，采用的技术方案为：

在三角网格中，与六条边相连的顶点定义为正则点，所有顶点都是正则点的网格定义为正则网格，多数顶点为正则点的网格为半正则网格，通常在任意曲面的三角网格中均含有奇异点。

基于逆Loop细分的渐进网格生成方法的主要步骤包括：

1)网格分裂：将已有的三角网格的顶点分裂成奇点集ODD^j和偶点集EVEN^j；

2)奇点预测：为了三维曲面造型的网格还原和重建，在删除奇点之前，对每个奇点，采用Loop细分预测其位置ODD′，将现有的各个奇点ODD^j与预测值对应相减得到一组误差值e^j；

3)网格更新：删除掉奇点集ODD^j后，剩余的偶点集EVEN^j形成下一层的顶点P^j-1，更新这些顶点的连接信息组成新的三角形集K^j-1，生成了一个简化后的新网格；

4)循环上述步骤，直到最终网格不能分裂，生成基网格及一系列误差值。

所述步骤1)网格分裂的分裂规则为：

a、选网格上任意一个奇异点为偶点归为偶点集；

b、将与奇异点相邻的所有邻接点归为奇点集；

c、对这些奇点外围与本偶点对称位置的对称点设为偶点，归为偶点集；

d、递归调用偶点集中的偶点，首先将其相邻的所有邻接点归为奇点集，再将这些奇点外围与该偶点对称位置的对称点设为偶点，归为偶点集，直到网格中所有顶点分裂完毕。

所述步骤2)奇点预测过程中的误差值e^j的计算方法为：

$>>>e>i>j>>=>OD>>D>i>j>>->OD>>D>I>\prime >\; >s>$

其中，j表示网格层数，i表示第j层网格的奇点数。

附图说明

图1为基于逆Loop细分的渐进网格生成方法流程图；

图2为半正则网格简化示意图；

图3为顶点关系示意图；

图4为预测与更新示意；

图5为头像模型渐进网格(顶点数/三角面数)示意图；

图6为e-Sphere模型渐进网格(顶点数/三角面数)示意图。

具体实施方式

下面结合附图对本方法进行进一步阐述。

如图1所示为基于逆Loop细分的渐进网格生成方法流程图。

设三角网格M＝(P，K)，其中P表示三角网格顶点坐标的集合，P_i＝(x_i，y_i，z_i)(1≤i≤n)，K表示含有网格拓扑信息的所有三角形集合。

本算法的主要目标就是将原始网格Mⁿ(Pⁿ，Kⁿ)生成为同构的M^j(P^j，K^j)(1≤j≤n)，其中M⁰＝(P⁰，K⁰)为基网格。

设初始曲面网格为Mⁿ，经过一次简化后得到M^n-1，对于第j层网格为M^j，每次网格简化包括以下三个过程。

(1)网格分裂：将已有的三角网格的顶点分裂成奇点集ODD^j和偶点集EVEN^j。由于三维图形网格都存在奇异点，而奇异点通常表示曲面的尖锐特性，需要全部保留下来。故在实施时首先选网格上任意一个奇异点为偶点v归为偶点集，然后将与奇异点相邻的所有邻接点va归为奇点集，对这些奇点外围与本偶点对称位置的对称点vs设为偶点，归为偶点集，各顶点位置的关系见图3所示。设置偶点是利用递归调用，直到网格中所有顶点分裂完毕，算法如下：

找任意奇异点v；

{如果v已经在偶点集中，返回成功；

如果v已经在奇点集中，返回失败；

设置v到偶点集SetEvenVertex(v)；

对于v的每一个相邻点va

{如果va是奇异点或者va已经在偶点集中，返回失败；

设置va到奇点集SetOddVertex(va)；

找到va和v的对称点vs；

设置vs到偶点集SetEvenVertex(vs)；

}

返回成功

}

图2是半正则网格经过二次简化的示意。阴影三角形的顶点是各层网格的奇点ODD，其余点为偶点EVEN。所有的奇点是冗余的信息，可以删除，而保留所有的偶点，以达到网格的简化。观察图2(a)可以发现，奇点、偶点有规律地分布在三角网格中。图中阴影的三角形是由奇点组成的三角形，可以删除。

(2)奇点预测：为了三维曲面造型的网格还原和重建，在删除奇点之前，对每个奇点，采用Loop细分预测其位置ODD′，如图4所示。将现有的各个奇点ODDⁱ与预测值对应相减得到一组误差值e^j。

$>>>e>i>j>>=>OD>>D>i>j>>->OD>>D>i>\prime >\; >s>$

其中，j表示网格层数，i表示第j层网格的奇点数。图4(a)中O点为奇点，E点为偶点，图4(b)是删除O点前，用细分模式预测得到点O’，每个奇点O与其相应的预测点O’的差值即得到误差值e^j集。

(3)网格更新：删除掉奇点集ODD^j后，剩余的偶点集EVEN^j形成下一层的顶点P^j-1，更新这些顶点的连接信息组成新的三角形集K^j-1，生成了一个简化后的新网格M^j-1＝(P^j-1，K^j-1)。图4(c)示意删除奇点后重建的网格。

重复上述三步，将复杂的初始网格数据Mⁿ简化到网格M⁰。每一层次的网格简化，奇点的坐标并不需要改变。简化后的数据得到一个基网格和一系列误差集e^j的数据，构成多个层次的数据：M⁰→e¹→e²→...→e^n-2→e^-1，生成了渐进网格，即(M⁰，e⁰)生成M¹，(M¹，e¹)构成M²，...，(M^n-1，e^n-1)可还原Mⁿ，渐进网格见表1。

             表1由基网格和误差组成的渐进网格

   渐进网格  Mⁿ   M^n-1 ...   M¹   M⁰   误差值   e^n-1 ...   e¹   e⁰ 

如图5、图6所示为头像模型渐进网格(顶点数/三角面数)示意图和e-Sphere模型渐进网格(顶点数/三角面数)示意图，实验表明，本算法效率高，与以往的算法相比，速度快，更易于在实际应用中使用。