基于逆Loop细分的半正则网格简化算法

栾婉娜，刘成明

基于逆Loop细分的半正则网格简化算法

栾婉娜，刘成明

(郑州大学软件学院，河南 郑州 450002)

三维网格简化是在保留目标物体几何形状信息的前提下尽量减小精细化三维模型中的点数和面数的一种操作，对提高三维网格数据的存取和网络传输速度、编辑和渲染效率具有十分重要的作用。针对大多网格简化算法在简化过程中未考虑网格拓扑结构与视觉质量的问题，提出了一种基于逆Loop细分的半正则网格简化算法。首先根据邻域质心偏移量进行特征点检测，随后随机选取种子三角形，以边扩展方式获取正则区域并执行逆Loop细分进行简化。最后，以向内分割方式进行边缘拼接，获取最终的简化模型。与经典算法在公开数据集上进行实验对比，结果表明，该算法能够在简化的同时有效地保持网格特征，尽可能保留与原始网格一致的规则的拓扑结构，并且在视觉质量上优于边折叠以及聚类简化算法。

网格简化；逆Loop细分；网格拼接；视觉度量；半正则化

在计算机图形学和几何造型中，物体通常是由多边形网格描述，其中又以三角网格最为常见。随着如Kinect、激光扫描仪等三维数据获取设备的不断完善，人们获取的三维数据以及由此建立的网格模型往往是高度密集的，对传统的计算机硬件以及网络带宽提出了极高的要求。但在动画、游戏等具体应用场景中，人们往往并不总是需要高精度的模型。为满足各种实际场景的需求，产生了诸如网格简化、网格压缩、动态细节层次(levels of detail)和渐进传输等一系列方法来平衡人们对于模型精度、硬件限制、网络带宽以及运算速度的需求。

网格简化是图形学中一项基本而又重要的问题，是指以几何或视觉度量为评价标准，在最大程度保持模型特征的同时，通过剔除视觉冗余细节来降低模型的复杂度。目前，国内外学者提出的网格简化算法大致可以分为如下几类：

(1) 基于低级几何特征的简化算法。以几何误差为指导，通过对原始模型中的几何元素进行动态削减或重新分布达到模型简化的目的，如图元聚类/区域合并、几何元素删除和采样算法。图元聚类算法[1-4]通过顶点聚类或者聚合近似平面实现了模型几何元素的削减，具有易于实现、健壮性好、无拓扑限制、适于并行处理并且计算效率高等优点，但简化精度受聚类数目和包围盒大小的影响，无法保持一些精细特征。几何元素删除算法通过删除顶点[5]、边折叠[6]、三角形收缩[7]等方式将基本图元进行删除，执行效率高，但不能显著简化模型内部结构。采样法[8-9]通过将顶点或者体素添加到模型的表面，然后根据几何误差指导规则进行重新分布调整，生成与原模型尽可能接近的简化模型。

(2) 基于高级语义特征指导的简化算法。除了几何特征，诸如显著度[10-12]等高级视觉特征也被引入网格简化算法，使简化模型可以更多得保留人眼视觉中更为显著的部分。

(3) 结合各种实际应用场景的简化算法。如结合实时简化[13]、GPU并行计算[14]、纹理[15-16]、视点[17-18]、渐进传输[19-21]等因素的简化算法。其在简化模型的同时，能够使得算法更符合某些特定的应用需求。

(4) 其他简化算法。小波分解的方法[22]将原始模型分解成低分辨率和细节2个部分，该方法比较适合光滑的表面。一些研究也开始注重网格简化后的形态优化问题[23-24]，以获得在视觉感受上更为优质的模型。另外，最新一些研究将神经网络与传统简化算法相结合[25-26]，使得网格简化在动态参数的选择以及运算速度上得到了提升。

尽管存在着各种各样的简化方式，但上述算法在网格简化过程中均没有兼顾网格的原始拓扑结构与视觉效果。正则网格以及半正则网格(如分片正则网格)作为一种特殊的网格结构，具有更规则的连接、更一致的拓扑、更良好的视觉效果，往往作为一种高质量的网格来保存三维模型。但上述方法在简化过程中均会对这种规则拓扑造成破坏，由此生成的网格模型在面片形状以及顶点度方面往往不易控制。此外，虽然一些算法得到的简化模型与原始模型在形态和体积上都较为接近，但是人类的视觉感知却取决于多种因素。针对上述问题，本文提出了基于逆细分的半正则网格简化算法，可以更好地适应于正则以及半正则网格模型，并获得在视觉感受上更为优质的简化模型。

1 相关工作

1.1 半正则网格

三角网格可以表示为=(,)，其中={p=(x,y,z)|=1,2,···,}为网格顶点集合；为网格拓扑信息集合。若顶点p和六条边相连接则称p为正则点，否则为非正则点，也称为奇异点。对于网格，若所有顶点都是正则点称为正则网格，多数顶点是正则点则为半正则网格。

1.2 逆Loop细分

曲面细分是几何造型中一种常见方法，常见基于三角网格的细分方法分为逼近型细分(如Loop细分)与插值型细分(如Butterfly细分)。不同的网格细分方法按照不同的规则对原始网格进行分裂操作，逐层加细。

图1展示了Loop细分过程。Loop细分是一个逼近型的1-4分裂过程。在细分过程中，不仅计算新增顶点0(奇点)的位置，原始顶点(偶点，统一用v表示)也要根据原网格中此点和与之相邻顶点v所占权值进行相应的位置调整，顶点计算式为

其中，；n为偶点的度数。

逆Loop细分是Loop细分的逆过程，在计算时，往往需要耗费大量资源计算逆细分前后顶点坐标的对应关系。但是，在密集的网格中，顶点局部位置的调整并不会过多影响网格的形态，因此，通过将逼近型细分当作插值型细分进行处理，可以有效地简化计算过程并保持网格的基本形态。

2 算法描述

本文算法的完成步骤包括：特征点标记、选取种子三角形、正则区域扩展与边缘奇点标记、逆细分简化、边缘拼接等。首先根据邻域质心偏移量进行网格特征点检测，以便在网格简化过程中保留特征。然后随机选取种子三角形，以边扩展方式动态获取正则区域。在扩展过程中，通过构建顶点扩展队列，验证当前扩展顶点是否为特征点并利用回退机制将网格模型特征点保留在扩展区域之外。随后通过对正则区域执行逆Loop细分进行简化，最后以向内分割方式进行网格边缘拼接，从而获得最终简化模型。

2.1 标记特征点

首先进行模型特征点判断，避免在网格简化过程中损失过多原始特征。特征点一般位于网格表面发生明显变化的地方，对应较大的局部曲率。本文根据质心偏移距离进行网格特征点检测。质心偏移距离为

其中，p为当前顶点；qi为当前顶点的邻接点；n为顶点的邻域顶点个数，即顶点的度，norm为模长。由文献[27]可知，从微分坐标角度，质心偏移的方向趋近于顶点局部法向量，其大小体现了顶点的局部平均曲率，因此，通过质心偏移距离，可以方便地快速检测出模型表面变化明显的特征点。图2显示了前10%最大质心偏移距离对应的特征点。在实际简化过程中，可以通过设定特征点的数量，达到特征简化的目的。

2.2 选取种子三角形

选取一个满足条件(3个顶点的度均为6)的三角形作为种子三角形。理论上，所有满足此要求的三角形都可以作为种子三角形，本文随机选取一个初始的种子三角形。

2.3 正则区域扩展与边缘奇点标记

在种子三角形的基础上，将正则区域尽量扩展。

首先将种子三角形的3个顶点放入队列当中，然后通过共享边扩展种子三角形，扩展后的偶点将会再次放入队列。随后从队列头部取出一个顶点，若该顶点的度为6，则由该顶点定位一个与已扩展区域无邻接边但共享该顶点的三角形，作为新的奇点三角形，再次扩展逆Loop细分单元。如果扩展过程中遇到非正则点或者特征点，则回退，并跳过当前扩展点，从队列中取出下一个点来继续执行，直至队列为空。

在扩展过程中，为了减少搜索范围和避免扩展区域的交叠重合，每个扩展过后的三角形将会从原始模型的面片集合中去除。由于在逆细分简化过程中，将会消除当前层的奇点，并将偶点连接成新的面片，所以，通过标记所有扩展边缘的奇点，可以定位拼接过程中需要调整的顶点。扩展过程如图3所示。

图3 正则区域扩展

重复选取种子三角形和正则区域扩展与边缘奇点标记，搜寻所有的可逆细分区域，并标记边缘。

2.4 逆细分简化

在扩展众多正则区域后，所有的特征点以及奇异点均被保留下来，由此保留了原始网格的绝大部分特征。本文将Loop细分视作插值型细分，删除每个正则区域内部的奇点，保留偶点，更新网格拓扑结构，实现区域内部的简化。

2.5 边缘拼接

在对区域内部进行简化过后，不同的正则区域的边缘形态是极其不规则的，对网格边缘的直接拼接造成极大困难。因此，本文采取向内分割方式来拼接不同的扩展区域。在正则区域扩展过程中，经常出现图4所示情况，对奇点所在可逆细分单元进行重新分割和边缘拼接。从左到右分别为正则区域扩展，逆细分以及边缘拼接结果。蓝色部分代表正则区域，红色顶点为边缘奇点，绿色部分为待扩展区域，青色部分为重分割结果。

图4 向内分割和边缘拼接

至此完成一轮完整的逆细分简化过程。重复本文算法步骤可反复进行网格简化，直到模型满足要求，或模型中不存在满足条件的正则区域。通过这种拼接与简化方式，避免了直接对复杂边缘形态进行调整，将各种情况下的边缘拼接简化为2种分割方式，且特征点被保留在简化区域外部，待简化正则区域在简化过后仍为正则区域。简化完成后，特征点附近的网格由于重分割较为细密，非特征处网格较为稀疏，在保留一致拓扑的同时，实现了自适应简化。

3 实验结果分析

本文算法在Windows环境下采用MatLab实现，实验环境配置为：i5-8250U，1.60 GHz，16 G内存。将本文算法(边扩展)与基于顶点分裂[20]方式的逆细分算法以及边折叠[6]和顶点聚类[28]算法的源码实验结果进行了对比。采用的数据模型为网格编辑中常用的几何模型，如chain，cat head，knot，casting和rocker-arm等。

3.1 几何误差度量与评价

本文采用Hausdorff 距离作为简化前后模型的几何误差度量评价。表1展示了本文算法与顶点分裂算法的对比结果，可以看出，两者的Hausdorff 距离极为接近。但是，顶点分裂算法一般需要对网格模型进行预处理获取基网格，并且非正则点数量达到一定程度，会终止顶点的递归分裂。表2展示了本文算法与边折叠以及顶点聚类方法的对比结果。可以看出，在几何误差上，本文算法优于边折叠算法，并在部分模型上优于顶点聚类方法。

表1 边扩展与点分裂简化误差对比

表2 边扩展与边折叠，聚类简化误差对比

3.2 视觉质量度量与评价

图5显示了点分裂以及本文算法对正则网格模型的简化结果。点分裂和本文算法的区别主要在于逆细分单元的获取方式不同，但随着非正则点的增多，点分裂方法将不再适用。

图5 Chain (简化38%，94%)

图6~9显示了本文算法与边折叠以及顶点聚类方法在不同简化率上的简化结果。从主观感受上可以看出，在图6 casting模型中，聚类算法无法保持诸如孔洞等细微结构，边折叠算法中，某些折叠过后的面片也对孔洞造成了覆盖，且产生了大量的狭长三角形，而本文算法对模型边缘、孔洞部分影响较小。在图7 rocker-arm模型中，本文算法保留了更多细节。这是因为奇异点以及特征点在边扩展过程中被保留下来，且网格拼接部分往往发生在平坦区域与特征区域的交界处，因此模型特征保存较为完好。此外，由于逆细分算法采用逐层简化方式，简化后的面片往往在视觉上较为均匀，狭长三角形较少，从而拥有比较好的视觉效果，且保留了大部分正则点，如图8和图9所示。

图6 Casting (简化78%)

图7 Rocker_arm (简化76%)

图8 Ball (简化98%)

图9 Chair (简化60%)

文献[29-30]表明Hausdorff距离、均方根误差法等几何距离测量方法与人眼视觉系统的质量感知之间的相关性较差，文献[24]使用了三角形狭长度来评价网格质量，定义三角形狭长度为

其中，l1，l2，l3分别为三角形的3条边长；S为三角形的面积，0≤Q≤1，且Q的值越大，面片质量越好。当Q=1时，三角形为正三角形。

图10~11显示了在相同的简化程度下，不同算法简化模型的三角形Q分布。从中可以看出，本文算法产生的狭长三角形较少，而形态良好的三角形数量较多。且本文算法尽可能保留了原始网格中的正则点，因而产生更规则的拓扑结构。虽然聚类算法在Q较大时拥有最多的面片数量，但是其对网格精细结构破坏较大。本文算法在较好的保持原始特征的情况下拥有比较良好的网格形态。

图10 Casting模型Qk分布

图11 Rocker_arm模型Qk分布

4 结 论

本文提出了一种结合逆细分与拼接策略的网格模型简化算法，在保持模型基本特征的同时，获取了视觉上更加均匀的网格模型。该算法通过正则区域的选择性递归扩展，保留了奇异点与特征点，并利用逆插值型Loop细分进行简化。最后，以分割策略实现了区域间复杂边缘的拼接，得到完整的简化模型。实验结果表明，该算法获取到的简化模型可以得到视觉上更为均匀的简化结果，并能保留特征区域。

[1] 周昆, 潘志庚, 石教英. 一种新的基于顶点聚类的网格简化算法[J]. 自动化学报, 1999(1): 4-11. ZHOU K, PAN Z G, SHI J Y. A new mesh simplification algorithm based on vertex clustering[J]. Acta Automatica Sinica, 1999(1): 4-11 (in Chinese).

[2] 王家腾, 殷宏, 解文彬, 等. 基于顶点重要度和层次聚类树的地形网格简化[J].计算机工程与设计, 2016, 37(6): 1543-1548. WANG J T, YIN H, XIE W B, et al. Terrain mesh simplification based on vertex importance and hierarchical clustering tree[J]. Computer Engineering and Design, 2016, 37(6): 1543-1548 (in Chinese).

[3] HINKER P, HANSEN C. Geometric optimization[C]// Proceedings Visualization'93. NewYork: IEEE Press, 1993: 189-195.

[4] ROSSIGNAC J, BORREL P. Multi-resolution 3D approximations for rendering complex scenes[M]// Modeling in Computer Graphics. Heidelberg: Springer, 1993: 455-465.

[5] SCHROEDER W J. Decimation of triangle meshes[J]. Computer Graphics, 1992, 26(2): 65-70.

[6] GARLAND M, HECKBERT P S. Surface simplification using quadric error metrics[C]//Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM Press, 1997: 209-216.

[7] GIENG T S, HAMANN B, Joy K I, et al. Constructing hierarchies for triangle meshes[J]. IEEE Transactions on Visualization and Computer Graphics, 1998, 4(2): 145-161.

[8] TURK G. Re-tiling polygonal surfaces[C]//Proceedings of the 19th Annual Conference on Computer Graphics and Interactive Techniques.New York: ACM Press, 1992: 55-64.

[9] HE T, HONG L, VARSHNEY A, et al. Controlled topology simplification[J]. IEEE Transactions on Visualization and Computer Graphics, 1996, 2(2): 171-184.

[10] LEE C, VARSHNEY A, JACOBS D. Mesh saliency[J]. ACM Transactions on Graphics, 2005, 24(3): 659-666.

[11] ZHAO Y T, LIU Y H, SONG R, et al. A saliency detection based method for 3D surface simplification[C]// IEEE International Conference on Acoustics, Speech and Signal Processing. New York: IEEE Press, 2012: 889-892.

[12] 魏宁, 徐婷婷, 高开源, 等. 基于Voronoi极点特征值显著度加权的网格简化算法[J].图学学报, 2017, 38(3): 314-319. WEI N, XU T T, GAO K Y, et al. Mesh simplification weighted by voronoi poles feature computed saliency[J]. Journal of Graphics, 2017, 38(3): 314-319 (in Chinese).

[13] BAHIRAT K, RAGHURAMAN S, PRABHAKARAN B. Real-time, curvature-sensitive surface simplification using depth images[J]. IEEE Transactions on Multimedia, 2018, 20(6): 1489-1498.

[14] 范豪, 刘峻, 孙宇, 等. GPU并行加速的边折叠简化算法[J]. 计算机工程与设计, 2016, 37(11): 3051-3057. FAN H, LIU J, SUN Y, et al. Parallel processing for accelerated edge collapse simplification algorithm with GPU[J]. Computer Engineering and Design, 2016, 37(11): 3051-3057 (in Chinese).

[15] 李世俊, 姜晓彤, 唐慧. 保持细节特征的带纹理模型的高质量简化算法[J]. 计算机应用研究, 2020, 37(1): 300-303, 312. LI S J, JIANG X T, TANG H. High-quality simplified algorithm of texture model for detailed features preserving[J]. Application Research of Computers, 2020, 37(1): 300-303, 312 (in Chinese).

[16] 冯翔, 周明全. 带纹理的三维模型简化算法[J]. 计算机辅助设计与图形学学报, 2009, 21(6): 842-846, 852. FENG X, ZHOU M Q. An algorithm for simplification of 3D models with texture[J]. Journal of Computer-Aided Design & Computer Graphics, 2009, 21(6): 842-846, 852 (in Chinese).

[17] 马军, 郁永珍, 郑宪, 等. 基于视点的网格模型快速简化算法[J]. 计算机工程, 2006(9): 211-213. MA J, YU Y Z, ZHENG X, et al. An algorithm of viewpoint-based mesh model simplification[J]. Computer Engineering, 2006(9): 211-213 (in Chinese).

[18] 冯洁, 查红彬. 大型三维网格模型的简化及基于视点的LOD控制[J]. 计算机辅助设计与图形学学报, 2006(2): 186-193. FENG J, ZHA H B. Simplification and view-dependent LOD control for large 3D mesh models[J]. Journal of Computer-Aided Design & Computer Graphics, 2006(2): 186-193 (in Chinese).

[19] 马建平, 罗笑南, 陈渤, 等. 面向移动终端的三角网格逆细分压缩算法[J]. 软件学报, 2009, 20(9): 2607-2615.MA J P, LUO X N, CHEN B, et al. Triangle mesh compression based on reverse subdivision for mobile terminals[J]. Journal of software engineering, 2009, 20(9): 2607-2615 (in Chinese).

[20] 史卓, 孔谦, 玉珂, 等. 基于二面角逆插值Loop细分的渐进传输方法[J]. 图学学报, 2019, 40(1): 92-98. SHI Z, KONG Q, YU K, et al. Progressive transmission method based on dihedral reverse interpolation loop subdivision[J]. Journal of Graphics, 2019, 40(1): 92-98 (in Chinese).

[21] SHI Z, AN Y, XU S, et al. Mesh simplification method based on reverse interpolation loop subdivision[C]// Proceedings of the 8th International Conference on Computer Modeling and Simulation .New York: ACM Press, 2017: 141-145.

[22] LOUNSBERY M, DEROSE T D, WARREN J. Multiresolution analysis for surfaces of arbitrary topological type[J]. ACM Transactions on Graphics (TOG), 1997, 16(1): 34-73.

[23] YI R, LIU Y J, HE Y. Delaunay mesh simplification with differential evolution[J]. ACM Transactions on Graphics (TOG), 2018, 37(6): 1-12.

[24] 王武礼, 段黎明, 王浩宇, 等.基于动态误差控制和PSO的三角网格模型简化优化方法[J].计算机集成制造系统, 2018, 24(1): 63-71. WANG W L, DUAN L M, WANG H Y, et al. Simplification and optimization of Triangular mesh Model based on dynamic error control and PSO [J]. Computer Integrated Manufacturing Systems, 2016, 24(1): 63-71 (in Chinese).

[25] 褚苏荣, 牛之贤, 宋春花, 等. 面向移动端的渐进网格简化算法[J]. 计算机应用, 2020, 40(3): 806-811. CHU S R, NIU Z X, SONG C H, et al. Progressive mesh simplification algorithm for mobile devices[J]. Journal of Computer Applications, 2020, 40(3): 806-811 (in Chinese).

[26] 杨煜, 冼楚华, 李桂清. 结合局部区域特征的自适应简化率网格简化算法[J]. 计算机辅助设计与图形学学报, 2020, 32(6): 857-864. YANG Y, XIAN C H, LI G Q. Mesh simplification with adaptive simplified ratio based on local region features[J]. Journal of Computer-Aided Design & Computer Graphics, 2020, 32(6): 857-864. (in Chinese).

[27] SORKINE O. Laplacian mesh processing[C]//26th Annual Conference of the European Association for Computer Graphics. Goslar: Eurographics Association, 2005: 53-70.

[28] LINDSTROM P. Out-of-core simplification of large polygonal models[C]//Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM Press, 2000: 259-262.

[29] CORSINI M, LARABI M C, LAVOUÉ G, et al. Perceptual metrics for static and dynamic triangle meshes[J]. Computer Graphics Forum, 2013, 32(1): 101-125.

[30] LAVOUÉ G, CORSINI M. A comparison of perceptually-based metrics for objective evaluation of geometry processing[J]. IEEE Transactions on Multimedia, 2010, 12(7): 636-649.

A semi-regular mesh simplification algorithm based on inverse Loop subdivision

LUAN Wan-na, LIU Cheng-ming

(School of Software, Zhengzhou University, Zhengzhou Henan 450002, China)

3D mesh simplification is an operation to minimize the number of vertices and faces in the refined 3D model while preserving the geometric information of the target object. It plays a significant role in improving the access and network transmission speed of the 3D mesh data, and the efficiency of editing and rendering. To address the problem of most mesh simplification algorithms neglecting the mesh topology and visual quality during simplification, a semi-regular mesh simplification algorithm was proposed based on the inverse Loop subdivision. The algorithm first detected the feature points according to the neighborhood centroid offset. Then a seed triangle was randomly selected to obtain the regular region by edge extension, and the inverse Loop subdivision was performed to simplify the mesh. Finally, the simplified model was gained by edge splicing in the way of inwards segmentation. Regarding the open testing data, comparisons were made between the algorithm and the classical ones. The experimental results show that the proposed algorithm can preserve the features effectively and keep the regular topology structure as much as possible during simplification, and that it is superior to the edge collapse and clustering algorithm in visual quality.

mesh simplification; inverse Loop subdivision; mesh splicing; visual metrics; semi-regular

TP 391

10.11996/JG.j.2095-302X.2020060980

A

2095-302X(2020)06-0980-07

2020-05-05；

2020-07-06

5 May，2020；

6 July，2020

河南省科技攻关项目(192102210107)；郑州市重大科技创新专项

Key Scientific and Technological Project of Henan Province (192102210107); Major Technological Innovation Project of Zhengzhou

栾婉娜(1996-)，女，河南鹿邑人，硕士研究生。主要研究方向为图形图像处理。E-mail：wnluan@qq.com

LUAN Wan-na (1996–), female, master student. Her main research interests cover graphics and image processing. E-mail：wnluan@qq.com

刘成明(1979-)，男，山东沂源人，副教授，博士，硕士生导师。主要研究方向为图形图像与视觉计算等。E-mail：cmliu@zzu.edu.cn

LIU Cheng-ming (1979–), male, associate professor, Ph.D. His main research interests cover graphics, image processing and visual computing. E-mail：cmliu@zzu.edu.cn