2020年 12月图 学 学 报 December2020第41卷第6期JOURNAL OF GRAPHICS V ol.41No.6基于逆Loop细分的半正则网格简化算法
栾婉娜，刘成明
(郑州大学软件学院，河南郑州 450002)
摘要：三维网格简化是在保留目标物体几何形状信息的前提下尽量减小精细化三维模型中的点数和面数的一种操作，对提高三维网格数据的存取和网络传输速度、编辑和渲染效率具有十分重要的作用。针对大多网格简化算法在简化过程中未考虑网格拓扑结构与视觉质量的问题，提出了一种基于逆Loop细分的半正则网格简化算法。首先根据邻域质心偏移量进行特征点检测，随后随机选取种子三角形，以边扩展方式获取正则区域并执行逆Loop细分进行简化。
最后，以向内分割方式进行边缘拼接，获取最终的简化模型。与经典算法在公开数据集上进行实验对比，结果表明，该算法能够在简化的同时有效地保持网格特征，尽可能保留与原始网格一致的规则的拓扑结构，并且在视觉质量上优于边折叠以及聚类简化算法。
关键词：网格简化；逆Loop细分；网格拼接；视觉度量；半正则化
中图分类号：TP 391 DOI：10.11996/JG.j.2095-302X.2020060980
文献标识码：A 文章编号：2095-302X(2020)06-0980-07
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)
Abstract: 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. R
egarding 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
收稿日期：2020-05-05；定稿日期：2020-07-06
Received：5 May，2020；Finalized：6 July，2020
基金项目：河南省科技攻关项目(192102210107)；郑州市重大科技创新专项
Foundation items：Key Scientific and Technological Project of Henan Province (192102210107); Major Technological Innovation Project of Zhengzhou
第一作者：栾婉娜(1996-)，女，河南鹿邑人，硕士研究生。主要研究方向为图形图像处理。E-mail：*************
First author：LUAN Wan-na (1996–), female, master student. Her main research interests cover graphics and image processing. E-mail：*************
通信作者：刘成明(1979-)，男，山东沂源人，副教授，博士，硕士生导师。主要研究方向为图形图像与
视觉计算等。E-mail：************* Corresponding author：LIU Cheng-ming (1979–), male, associate professor, Ph.D. His main research interests cover graphics, image processing and visual computing. E-mail：*************
第6期栾婉娜，等：基于逆Loop细分的半正则网格简化算法981 simplification, and that it is superior to the edge collapse and clustering algorithm in visual quality.
Keywords: mesh simplification; inverse Loop subdivision; mesh splicing; visual metrics; semi-regular
在计算机图形学和几何造型中，物体通常是由多边形网格描述，其中又以三角网格最为常见。随着如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  半正则网格
三角网格可以表示为M=(P, K)，其中P={p
i
=(x i,y i,z i)|i=1,2,···,n}为网格顶点集合；K为网
格拓扑信息集合。若顶点p i和六条边相连接则称p
i 为正则点，否则为非正则点，也称为奇异点。对于网格M，若所有顶点都是正则点称为正则网格，多数顶点是正则点则为半正则网格。
1.2  逆Loop细分
曲面细分是几何造型中一种常见方法，常见基于三角网格的细分方法分为逼近型细分(如Loop细分)与插值型细分(如Butterfly细分)。不同的网格细分方法按照不同的规则对原始网格进行分裂操作，逐层加细。
图1展示了Loop细分过程。Loop细分是一个逼近型的1-4分裂过程。在细分过程中，不仅计算
新增顶点v
(奇点)的位置，原始顶点(偶点，统一用v e表示)也要根据原网格中此点v和与之相邻顶点v i 所占权值进行相应的位置调整，顶点计算式为
982 计算机图形学与虚拟现实
2020年
012341
031()()88(1),3
n e n n i i v v v v v v n v v n ββ-=⎧
=+++⎪⎪⎨⎪=-+⎪⎩∑≥ (1) 其中，2
15312πcos 884n n n β⎛⎫⎛⎫=-+ ⎪ ⎪ ⎪⎝⎭⎝⎭；n 为偶点的度数。
图1  Loop 细分
Fig. 1  Loop subdivision
逆Loop 细分是Loop 细分的逆过程，在计算时，往往需要耗费大量资源计算逆细分前后顶点坐标的对应关系。但是，在密集的网格中，顶点局部位置的调整并不会过多影响网格的形态，因此，通过将逼近型细分当作插值型细分进行处理，可以有效地简化计算过程并保持网格的基本形态。
2  算法描述
本文算法的完成步骤包括：特征点标记、选取种子三角形、正则区域扩展与边缘奇点标记、逆细分简化、边缘拼接等。首先根据邻域质心偏移量进行网格特征点检测，以便在网格简化过程中保留特征。然后随机选取种子三角形，以边扩展方式动态获取正则区域。在扩展过程中，通过构建顶点扩展队列，验证当前扩展顶点是否为特征点并利用回退机制将网格模型特征点保留在扩展区域之外。随后通过对正则区域执行逆Loop 细分进行简化，最后以向内分割方式进行网格边缘拼接，从而获得最终简化模型。 2.1  标记特征点正则化的具体做法
首先进行模型特征点判断，避免在网格简化过程中损失过多原始特征。特征点一般位于网格表面发生明显变化的地方，对应较大的局部曲率。本文根据质心偏移距离进行网格特征点检测。质心偏移距离为
11n
i i d norm p q n =⎛⎫=- ⎪⎝⎭∑ (2)
其中，p 为当前顶点；q i 为当前顶点的邻接点；n 为顶点的邻域顶点个数，即顶点的度，norm 为模长。由文献[27]可知，从微分坐标角度，质心偏移11n
i i p q n =-∑的方向趋近于顶点局部法向量，其大小体现了顶点的局部平均曲率，因此，通过质心偏移
距离，可以方便地快速检测出模型表面变化明显的特征点。图2显示了前10%最大质心偏移距离对应的特征点。在实际简化过程中，可以通过设定特征点的数量，达到特征简化的目的。
图2  质心偏移特征点检测
Fig. 2  Feature point detection by centroid offset
2.2  选取种子三角形
选取一个满足条件(3个顶点的度均为6)的三角形作为种子三角形。理论上，所有满足此要求的三角形都可以作为种子三角形，本文随机选取一个初始的种子三角形。
2.3  正则区域扩展与边缘奇点标记
在种子三角形的基础上，将正则区域尽量扩展。 首先将种子三角形的3个顶点放入队列当中，然后通过共享边扩展种子三角形，扩展后的偶点将会再次放入队列。随后从队列头部取出一个顶点，若该顶点的度为6，则由该顶点定位一个与已扩展区域无邻接边但共享该顶点的三角形，作为新的奇点三角形，再次扩展逆Loop 细分单元。如果扩展过程中遇到非正则点或者特征点，则回退，并跳过当前扩展点，从队列中取出下一个点来继续执行，直至队列为空。
在扩展过程中，为了减少搜索范围和避免扩展区域的交叠重合，每个扩展过后的三角形将会从原始模型的面片集合中去除。由于在逆细分简化过程中，将会消除当前层的奇点，并将偶点连接成新的面片，所以，通过标记所有扩展边缘的奇点，可以
定位拼接过程中需要调整的顶点。扩展过程如图3所示。
第6期 栾婉娜，等：基于逆Loop 细分的半正则网格简化算法 983
图3  正则区域扩展 Fig. 3  Regular region extension
重复选取种子三角形和正则区域扩展与边缘奇点标记，搜寻所有的可逆细分区域，并标记边缘。
2.4  逆细分简化
在扩展众多正则区域后，所有的特征点以及奇异点均被保留下来，由此保留了原始网格的绝大部分特征。本文将Loop 细分视作插值型细分，删除每个正则区域内部的奇点，保留偶点，更新网格拓扑结构，实现区域内部的简化。
2.5  边缘拼接
在对区域内部进行简化过后，不同的正则区域的边缘形态是极其不规则的，对网格边缘的直接拼接造成极大困难。因此，本文采取向内分割方式来拼接不同的扩展区域。在正则区域扩展过程中，经常出现图
4所示情况，对奇点所在可逆细分单元进行重新分割和边缘拼接。从左到右分别为正则区域扩展，逆细分以及边缘拼接结果。蓝部分代表正则区域，红顶点为边缘奇点，绿部分为待扩展区域，青部分为重分割结果。
图4  向内分割和边缘拼接
Fig. 4  Inwards segmentation and edge splicing
至此完成一轮完整的逆细分简化过程。重复本文算法步骤可反复进行网格简化，直到模型满足要求，或模型中不存在满足条件的正则区域。通过这种拼接与简化方式，避免了直接对复杂边缘形态进行调整，
将各种情况下的边缘拼接简化为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  边扩展与点分裂简化误差对比
Table 1  Comparison of edge extension and vertex
splitting in simplification errors
模型 顶点 面片 简化率 Hausdorff 距离 点分裂 边扩展chain    3 8407 6800.378 1 0.174 3 0.173 90.937 5 0.235 8 0.234 7cat head 32 98565 7920.493 2 0.769 4 0.748 20.937 0 0.154 6 0.158 2knot
15 407
30 720
0.573 6 0.437 2 0.430 70.981 3
1.833 2
1.832 0
984 计算机图形学与虚拟现实 2020年
表2  边扩展与边折叠，聚类简化误差对比
Table 2  Comparison of edge extension, edge collapse
and clustering in simplification errors
模型
顶点
面片
简化率Hausdorff 距离 点聚类 边折叠 边扩展casting    5 096 10 224
0.321 90.014 1 0.065 3 0.038 40.534 20.027 3 0.217 4 0.074 50.780 20.058 3 0.293 8 0.114 4chair 13 628 27 256
0.210 90.032 6 0.083 2 0.037 40.437 20.010 3 0.176 9 0.058 60.603 90.019 7 0.318 8 0.080 8rocker
-arm 10 000 20 000
0.321 70.210 7 0.659 2 0.478 20.573 00.464 5    1.370 1    1.039 50.756 30.862 5    2.474 7    2.170 7ball
10 242 20 480
0.568 30.087 4 0.084 2 0.073 90.713 40.175 3 0.179 4 0.153 20.984 20.304 8 0.388 9 0.274 0cow 9 065 18 128
0.413 00.237 5 0.439 7 0.273 60.630 50.356 8 0.631 7 0.369 20.760 30.468 5 0.768 6 0.513 9teapot 21 022 42 044
0.604 90.062 5 0.128 9 0.084 10.895 40.139 6 0.241 6 0.173 40.957 2
0.207 3
0.337 3
0.248 2
3.2  视觉质量度量与评价
图5显示了点分裂以及本文算法对正则网格模型的简化结果。点分裂和本文算法的区别主要在于逆细分单元的获取方式不同，但随着非正则点的增多，点分裂方法将不再适用。
(a) 原始模型 (a) Original model (b) 点分裂 (b) Vertex splitting (c) 本文算法 (c) Our algorithm
图5  Chain (简化38%，94%) Fig. 5  Chain (simplified 38%, 94%)
图6~9显示了本文算法与边折叠以及顶点聚类方法在不同简化率上的简化结果。从主观感受上可以看出，
在图6 casting 模型中，聚类算法无法保持诸如孔洞等细微结构，边折叠算法中，某些折叠过后的面片也对孔洞造成了覆盖，且产生了大量的狭长三角形，而本文算法对模型边缘、孔洞部分影响较小。在图7 rocker-arm 模型中，本文算法保留了更多细节。这是因为奇异点以及特征点在边扩展过程中被保留下来，且网格拼接部分往往发生在平坦区域与特征区域的交界处，因此模型特征保存较为完好。此外，由于逆细分算法采用逐层简化方式，简化后的面片往往在视觉上较为均匀，狭长三角形较少，从而拥有比较好的视觉效果，且保留了大部分正则点，如图8和图9所示。
(a) 原始
模型 (a) Original model (b) 聚类
(b) Clustering (c) 边折叠
(c) Edge  collapse (d) 本文
算法 (d) Our
algorithm
图6  Casting (简化78%) Fig. 6  Casting (simplified 78%)
(a) 原始
模型 (a) Original model
(b) 聚类
(b) Clustering (c) 边折叠
(c) Edge  collapse (d) 本文
算法 (d) Our
algorithm 图7  Rocker_arm (简化76%) Fig. 7  Rocker_arm (simplified 76%)
(a) 原始
模型 (a) Original model (b) 聚类
(b) Clustering (c) 边折叠
(c) Edge  collapse (d) 本文
算法 (d) Our
algorithm
图8  Ball (简化98%) Fig. 8  Ball (simplified 98%)
(a) 原始
模型 (b) 聚类 (c) 边折叠 (d) 本文
算法
(a) Original model (b) Clustering (c) Edge  collapse (d) Our algorithm
图9  Chair (简化60%) Fig. 9  Chair (simplified 60%)
文献[29-30]表明Hausdorff 距离、均方根误差法等几何距离测量方法与人眼视觉系统的质量感知之间的相关性较差，文献[24]使用了三角形狭长度来评价网格质量，定义三角形狭长度为
222123()k k k k k Q l l l =++ (3)
其中，l k 1，l k 2，l k 3分别为三角形的3条边长；S k
为

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。