基于半边折叠的三角网格模型分片参数化与重构算法①

张 芸，王继东，赵瑞斌，庞明勇，3

(1.滁州职业技术学院信息工程系;2.滁州学院计算机与信息工程学院，安徽 滁州 239000;3.南京师范大学教育技术系，江苏 南京 210046)

三角网格是空间几何数据的主流表示方法，参数化则是三角网格模型处理的基础，不管是纹理映射、曲面拟合还是重新网格化都需要对网格进行参数化处理。1960年Tutte［1］提出了凸组合方法，该方法将三角网格边界顶点映射到一个平面凸多边形边界上，网格内部任一顶点参数值则是以其为中心的一环邻域点参数值的算术平均值，该方法保证了参数化结果的有效性，但参数化效果较差。1995年Eck［2］提出了称为调和映射的参数化方法，该方法先将三角网格的边界映射到预先定义好的多边形上，然后通过最小化整个三角网格模型的弹性势能来参数化内部空间点。1997年Floater［3］对凸组合方法进行了改进，提出了具有保形的凸线性组合参数化，该方法简单有效且网格扭曲较小。为了避免Floater和Eck的方法中边界点需要预先参数化的问题，Hormann［4］等在2000年提出了一种全局的非线性具有自由边界的MIPS(Most Isometric Parameterizations)方法，该方法参数化效果较好，但过程比较复杂。2001年Sheffer［5］等提出了一种复合的纹理映射参数化方法，该方法的效果好于凸组合和调和映射，但计算代价高且不能解决多边界问题。国内也有不少学者进行了相关研究，张磊等［6］在2008年利用保持三角形相似性建立全局线性方程组，进行网格平面参数化，该方法参数化变形较大。2010年Li等［7］根据金属成形中的一步逆成形理论求解网格参数化问题，该方法比较耗时。2012年薛娟等［8］对多种参数化方法进行了分析比较，并基于几何图像实现了模型重构及压缩重构。

MAPS(Multiresolution Adaptive Parameterization of Surfaces)方法是Lee［9］等在1998年提出的较为完善的三角网格参数化处理框架，但由于需要对局部形成的多边形孔洞进行三角化，算法效率较低。借鉴MAPS的参数化思想，使用一种新的半边折叠算法把网格模型分层简化至基网格，在简化过程中映射已删除的原始网格顶点到简化网格面上，避免了多边形空洞三角化问题，最后为了验证参数化效果，生成了质量较高的重构网格。

1 基于半边折叠的三角网格分层简化

Hoppe［10］于1993年首先提出了边折叠方法来简化网格模型，该算法生成的简化模型误差较小，但时间复杂度较高。半边折叠可以理解为一种不产生新顶点的边折叠，其简化速度较快但简化误差相对较大。如图1所示，当对边uv进行半边折叠时，删除了共用uv边的两个面，并把u点移至v点的位置，整个过程没有产生新的顶点。值得注意的是，把u点移至v点或把v点移至u点是有区别的，uv和vu可以看成边uv的两条有方向的半边。

图1 半边折叠

1.1 半边折叠代价

为了尽可能的降低简化误差，在对网格模型进行半边折叠时总是先删除折叠代价较小的边。根据近平面合并简化的思想，文献 ［11］用边曲率衡量半边折叠代价，曲率越大则折叠代价越大，具体计算公式如下:

其中Tu指所有与删除点相关的三角面集合，如图1中的三角形 uab、ubv、uve、uea;Tuv指折叠边所在的两个三角面，如图1中的三角形ubv、uve;normal指三角面的单位法向量。通过简单的数学变换，式 (1)等价为:

其中α表示三角面f与三角面n所成的夹角，当曲率值C最大时，α取的是Tu中的一个三角形与Tuv中每一个三角形夹角最小值集合中最大的一个取值。

考虑到被删除顶点u的度越大其所控制的网格模型信息就越多，被折叠边的长度越长其在模型中的重要程度就越高，为了进一步降低简化误差，定义半边折叠代价公式为:

其中D指被删除顶点u的度，‖u－v‖指折叠边的长度。

1.2 网格模型分层简化

对网格模型进行半边折叠简化时，采用了分层简化方法，具体的算法步骤如下:

1)读入原始网格模型ML，网格模型数据结构初始化。

2)根据半边折叠代价公式 (3)，计算所有半边的折叠代价，按折叠代价由小到大的顺序对半边进行排序。

3)对半边进行折叠，操作如下:

i.取出折叠代价排在最前面的半边h0(第一次为折叠代价最小的半边)，检查h0所在边e0是否被锁定或删除。如果e0已被锁定或删除，跳到步骤ii执行，否则跳到步骤iii执行。

ii.按顺序取出下一条折叠代价次小的半边，检查其所在边是否也被锁定或删除，直到取出的半边hi所对应的边ei没有被锁定为止。

iii.检查当前取出的半边hi的折叠代价是否小于设定的阈值，如果小于则结束步骤3，如果大于则进行半边折叠操作并锁定所有与hi有邻接关系的边。

iv.跳到步骤ii执行，直到取完所有半边。

4)步骤3执行完成后得到简化的网格模型ML－1，解锁所有边，再对网格模型ML－1进行步骤2、3操作，可以得到简化模型ML－2;依此循环，当网格模型简化到没有符合条件的半边能够折叠时，就得到了基网格M0。

通过上述分层简化步骤既能够得到多分辨率简化模型，又为下一步实现分片参数化提供了基础。

2 三角网格分片参数化

三角网格分片参数化方法完全在网格分层简化的过程中完成，每次半边折叠操作将删除一个顶点、两个三角面，只需把被删除顶点参数化到新的三角面片上并更新已有参数化顶点的位置即完成了参数化工作。

图2 三角网格分层简化与参数化

如图 2 所示，当模型 ML－i简化到 ML－i－1时，半边u1u2和顶点 u1都被删除，u1被参数化到ML－i－1中的三角形 abu2上 (记为 u'1);当模型ML－i－1简化到 ML－i－2时，半边 u2v 和顶点 u2被删除，u2被参数化到 ML－i－2中的三角形 avg上 (记为u'2)，此时由于三角形的变形导致u'1的参数化位置发生了变化，被更新到三角形avg中。这样，当模型简化为基网格M0时，所有被删除顶点都参数化到了基网格的三角面片上。以图2中u2为例，把被删除顶点参数化过程分为三个步骤:首先，把ML－i－1和 ML－i－2中所有与 u2相关联的三角面集合展平到同一个平面P上，使空间问题转化为平面问题;其次，在平面P上确定u2应该映射到下一层简化模型ML－i－2的那个三角面上，并计算映射点u'2在该三角面上的重心坐标;最后，把与u2相关联的三角面集合上所有已存在的映射点 (如:u'1)的重心坐标更新到ML－i－2中对应的三角面上。针对以上步骤的处理，下面给出详细描述。

2.1 删除点关联三角面集合的展平

当与删除点相关联的三角面集合被展平到二维平面后，所有相关的角和边都会相应地变形和拉伸，这里使用文献 ［12］中的方法进行操作。如图3所示，虚线部分是uv折叠前删除点u的拓扑关系，在三维空间中 (图3a)定义(其中θi是与u点相关联的角集合，包括∠aub、令展平后的角为αθi且边长度为，则可得到相应的二维平面 (图3b)。以此平面建立以u为原点且b点在x轴上的二维直角坐标系，通过αθi和就能够计算出u点一环邻域中各顶点 (a，b，c，d，v)的相对二维坐标，这里不再给出详细步骤。

图3 删除点u关联三角面集合的展平

2.2 删除点与三角面位置关系的判定和计算

共面的点和线段相对位置关系可以由几何公式(4)判定，其中 (x，y)是任意点的坐标，(x1，y1)和 (x2，y2)是任意线段的两端点坐标。若点在线段上，则N等于0;若点在线段两侧，则N为正值或负值。

对公式 (4)进行扩展即可用于判断删除点是否在一个三角形内。如图4所示，二维平面上有三角形v0v1v2和删除点u。使用公式 (4)，检测u点和v0点是否在线段v1v2的同一侧，检测u点和v1点是否在线段v0v2的同一侧，检测u点和v2点是否在线段v0v1的同一侧。若以上全部在同一侧，则说明u点在三角形v0v1v2内 (把P点在三角形任意一条边上的情况也认为是在三角形内);否则，就说明u点不在三角形v0v1v2内。

图4 删除点的位置判定

通过上述方法，可以较快捷地确定包含删除点的三角形。再根据2.1节中得到的删除点及其一环邻域点的相对二维坐标，可以算出删除点在包含三角形的重心坐标。如图4所示，u点在三角形v0v1v2中的重心坐标为 (α，β，γ)，其中α是与v0点相对的三角形uv1v2的面积，β是与v1点相对的三角形uv2v0的面积，γ是与v2点相对的三角形u v0v1的面积。为了计算的方便，可以对α，β，γ进行规格化，使即α+β+γ=1。由于重心坐标是使用面积比衡量点在三角形的位置，所以其不会随三角形的变形而变化，因此，删除点在二维平面中的重心坐标即是其在三维空间中参数化点的位置坐标。

2.3 参数化点的位置更新

如前所述，半边折叠将会导致删除点相关联的三角面集合发生形变，这样已存在的参数化点就需要重新映射。以图2为例，当模型 ML－i－1简化到ML－i－2时，三角面abu2被拉伸，参数化点u'1位置的需要更新，具体步骤如下:

1)使用2.1节的方法，展平u2点相关联的三角面集合并建立平面直角坐标系，再把u'1在三角面abu2中的重心坐标代入到公式 (5)可得u'1的二维坐标。

其中，v0、v1、v2是三角面的三个顶点，v0［x］、v1［x］、v2［x］ 分别是 v0、v1、v2的 x 轴坐标，v0［y］、v1［y］、v2［y］ 分别是 v0、v1、v2的 y轴坐标，v0［z］、v1［z］、v2［z］ 分别是 v0、v1、v2的z轴坐标，(α，β，γ)是参数化点在三角面v0v1v2中的重心坐标。当然，这里仅考虑平面坐标，z轴坐标无需计算。

2)根据u'1点的二维坐标，使用2.2节的方法确定u'1新的包含三角面和对应的重心坐标，这样就完成了参数化点的位置更新。

不难看出，分片参数化方法能够很好地嵌入到1.2节网格模型分层简化算法中，即每次半边折叠时可以把删除点使用本节方法映射到下层简化模型的三角面上，当模型简化为基网格时，就可以得到所有删除点的参数化结果。

3 三角网格重构

参数化的一个重要用途就是三角网格重构，利用分片参数化结果能够得到比原始模型质量更高的半正规化三角网格。首先，使用平面细分方法对基网格进行细分，增加网格顶点数以满足需求;其次，根据参数化点的位置对细分点进行扰动实现重构。

3.1 基网格的平面细分

Loop细分［13］是一种简单有效的三角网格细分模式，其把每次细分过程中新插入的点称为奇点，而从上层网格继承的点称为偶点，具体的细分方法这里就不再赘述。针对重构算法，对Loop细分模型作了部分修改:每次细分时，无论是内部点还是边界点，都令奇点坐标等于其所在边的中点坐标，偶点三维坐标不变。这样，对三角面进行细分而产生的细分点就仍然与这个三角面共面，得到的细分网格在外观上始终与基网格保持一致，如图5所示。

3.2 细分网格的重构

当基网格平面细分产生的顶点数达到了实际需求，就可以通过参数化点与原始网格顶点的对应关系以及细分点与参数化点的位置关系对细分模型重新网格化。由于半边折叠不会产生新顶点，基网格的顶点就是原始网格顶点，因此整个重构过程只需扰动细分点，这也是半边折叠简化方法用于分片参数化的一个重要优点。

如图5所示，左侧是基网格和对应的细分网格，右侧是对应于基网格中一个三角面的细分网格面 (设为T面)，其中圆点为细分点，圆圈为参数化点，则扰动T面上细分点的步骤如下:

图5 基网格平面细分与点扰动

1)由公式 (5)反推出T面上所有参数化点的三维坐标，显然参数化点和细分点共面。

2)取一个细分点pi，假如是T面的内部点 (如p0)，则使用2.2节的方法为其找到一个由参数化点构成的最小面积的包含三角形 (如三角形u'1u'2u'3);假如细分点为T面的边缘点 (如p1)，则把边缘点在基网格中所位于的两个面投影到法向为这两个面法向之和的平面上，然后再根据这两个面上的参数化点投影坐标找到边缘点的最小面积包含三角形。

3)设pi的包含三角形顶点为u'i、u'j、u'k，则可以算出pi在包含三角形中的重心坐标;由原始网格顶点与基网格上参数化点的对应关系，可以得到u'i、u'j、u'k所对应的原始网格顶点ui、uj、uk的三维坐标。把pi的重心坐标和ui、uj、uk的三维坐标代入到公式 (5)，即可得到扰动后的pi坐标npi，如图6所示。

图6 细分点的扰动

4)重复步骤2、3可以算出T面上所有细分点扰动后的三维坐标，也即实现了网格的重构。

图7 分片参数化和重构效果图

4 实验结果

在PC机 (英特尔酷睿双核 i5－3230M@2.60GHz、4G内存、Windows 7)的VS2010开发平台上使用C++实现了分片参数化与重构算法。图7是三角网格模型分层简化、分片参数化、两次平面细分以及网格重构的效果图，其中Bunny、Frog、Pig的半边折叠代价阈值分别为0.1、0.025、0.01，从图中的光照和图形效果可以看出:简化算法能够较好地保持原始模型的形状轮廓，如Bunny的基网格三角面数仅占原始模型的3.1%，但仍然能够清晰地分辨出耳朵、头部、前蹄、尾巴等;模型简化为基网格时，所有删除点能够被合理地映射;两次平面细分后，网格三角面数增加了16倍，但在几何外观上没有发生任何变化，为网格重构提供了基础;对细分网格顶点进行扰动得到的重构网格，其三角面更加接近正三角形，即使是构造较为复杂的模型Pig和Frog也能够较好地还原模型形状。

5 结束语

文章提出了一种新的三角网格分片参数化与重构算法。首先，实现了考虑顶点度数和边长因素的半边折叠分层简化算法;其次，在分层简化的过程中，利用网格展平和重心坐标计算等方法实现了原始网格顶点的分片参数化;最后，提出了平面细分方法并使用参数化结果实现了网格重构。实验结果表明，算法既能够得到质量较好的多分辨率网格模型，又能够在分片参数化基础上得到三角面接近正三角形的重构网格。

［1］ TUTTE WT.Convex representations of graphs［C］.In Proceedings of the London Mathematical Society，London，1960:304－320

［2］ ECK M，DEROSE T，DUCHAMP T，et al.Multiresolution analysis of arbitrary meshes［A］.Computer Graphics(SIGGRAPH’95 Proceedings)，1995:173 －182

［3］ FLOATER M.Parameterization and smooth approximation of surface triangulations ［J］.Computer Aided Geometric Design，1997，14(3):231 －250

［4］ HORMANN K，GREINER G.MIPS:An efficient global parameterization method［M］.In:Laurent P J，Sablonnière P，Schumaker L，eds.Curve and Surface Design.Nashville:Vanderbilt University Press，2000:153 －162

［5］ SHEFFER A，STURLER E.Parameterization of faceted surfaces for meshing using angle based flattening［J］.Engineering with Computers，2001，17(3):326 －337

［6］张磊，刘利刚，王国瑾.保相似的网格参数化［J］.中国图象图形学报，2008，13(12):2383 －2387

［7］ LI Baojun，ZHANG Xiangkui，ZHOU Ping，et al.Mesh Parameterization Based on One － step Inverse Forming［J］.Computer Aided Design，2010，42(7):633 －640

［8］薛娟，张勇，孔德慧，等.网格参数化与几何图像［J］.系统仿真学报，2012，24(9):1780 －1784

［9］ LEE A，SWELDENS W，SCHRDER P，et al.MAPS:Multiresolution adaptive parameterization of surfaces［A］.Computer Graphics Proceedings(SIGGRAPH98)，1998:95 －104

［10］HOPPE H，DEROSE T，DUCHAMP T，et al.Mesh optimization［J］.Computer Graphics，1993，27(1):19 －26

［11］MELXA S.A simple，fast，effective polygon reduction algorithm［J］.Game Developer，1998，10:44 －49

［12］LEE A.Building you own subdivision surfaces［EB/OL］.http://www.gamasutra.com/view/feature/131544/building_your_own_subdivision_.php?print=1，2013 －06 －04

［13］LOOP C.Smooth subdivision surfaces based on triangles［D］.Salt Lake City:University of Utah，Department of Mathematics，1987