特征保持的区域分级网格简化算法

doi:10.11996/JG.j.2095-302X.2023030570

图学学报 ›› 2023, Vol. 44 ›› Issue (3): 570-578.DOI: 10.11996/JG.j.2095-302X.2023030570

• 计算机图形学与虚拟现实 • 上一篇下一篇

特征保持的区域分级网格简化算法

朱天晓¹(), 闫丰亭¹(), 史志才²

1.上海工程技术大学电子电气工程学院，上海 201620
2.上海市信息安全综合管理技术研究重点实验室，上海 200240

收稿日期:2022-08-30 接受日期:2022-11-20 出版日期:2023-06-30 发布日期:2023-06-30
通讯作者: 闫丰亭(1980-)，男，讲师，博士。主要研究方向为计算机图形学、WebVR+AI。E-mail：yanfengting2008@163.com
作者简介:
朱天晓(1998-)，男，硕士研究生。主要研究方向为计算机图形学、深度学习。E-mail：shownztx@163.com
基金资助:
科技创新2030-“新一代人工智能”重大项目(2020AAA0109300);上海市信息安全综合管理技术研究重点实验室开放研究课题基金(AGK2019004);上海市科委高新技术基于多源信息的城市内涝应急设施智慧调度研究项目(21511103704);多维时空变数据驱动的WebVR+AI关键技术研发项目((19) DZ-015)

Regional hierarchical mesh simplification algorithm for feature retention

ZHU Tian-xiao¹(), YAN Feng-ting¹(), SHI Zhi-cai²

1. School of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China
2. Shanghai Key Laboratory of Integrated Administration Technologies for Information Security, Shanghai 200240, China

Received:2022-08-30 Accepted:2022-11-20 Online:2023-06-30 Published:2023-06-30
Contact: YAN Feng-ting (1980-), lecturer, Ph.D. His main research interests cover computer graphics, WebVR+AI. E-mail：yanfengting2008@163.com
About author:
ZHU Tian-xiao (1998-), master student. His main research interests cover computer graphics and deep learning. E-mail：shownztx@163.com
Supported by:
Scientific and Technological Innovation 2030-Major Project of New Generation Artificial Intelligence(2020AAA0109300);Shanghai Information Security Comprehensive Management Technology Research Key Laboratory Open Research Subject Fund(AGK2019004);Research on Smart Dispatching of Urban Flooding Emergency Facilities Based on Multi-source Information by Shanghai Science and Technology Commission(21511103704);Multi-Dimensional Space-Time Variable Data-Driven WebVR+AI Key Technology Development((19) DZ-015)

摘要/Abstract

摘要：

随着三维建模精度的提升，网格模型的数据量越来越大。为便于存储和计算，需要对网格模型进行简化处理。大多数网格简化算法通常对模型整体设置单一简化率，无法对模型进行不同级别的简化以保留局部特征。针对此类问题，提出了一种特征保持的区域分级网格简化算法(RH-QEM)。首先使用谱聚类算法对网格模型进行分割，并以测地线距离和余弦距离构建核函数；其次构建基于法向量的曲折度量指标，对网格模型的不同区域进行曲折程度度量，据此来设置分级简化率，不同的分割区域对应不同的简化率；最后构建改进的边折叠代价函数，对网格模型的不同区域实现分级简化。在CAD模型与扫描模型上进行实验，实验结果表明，RH-QEM算法简化误差和网格质量均优于3种对比算法，可实现分级简化，并有效保持模型细节特征。

关键词: 网格简化, 特征保持, 谱聚类, 法向量, 二次误差

Abstract:

As the accuracy of 3D modeling continues to improve, the data size of mesh models is increasing proportionally. Thus, simplifying mesh models is essential to facilitate storage and computation. However, most mesh simplification algorithms usually set a single simplification rate for the entire model, and they are unable to retain local features through different levels of simplification. To address this limitation, a hierarchical mesh simplification algorithm called regional hierarchical quadric error metric algorithm (RH-QEM) for local feature retention was proposed. First, the algorithm segmented the mesh model using spectral clustering and constructed the kernel function using geodesic and cosine distances. Then a curvature metric based on normal vectors was constructed to measure the curvature degree of different localities of the mesh model, according to which the graded grid simplification rate was set. Different regions were mapped to different simplification rates. Finally, the algorithm constructed an improved edge folding cost function to achieve graded simplification for different regions of the grid model. Experiments were conducted on CAD models and scanned models. The experimental results demonstrated that the RH-QEM algorithm outperformed three compared algorithms, as it could reduce the simplification errors and enhance the mesh quality, thus realizing graded simplification and effectively maintaining the detailed features of the model.

Key words: mesh simplification, feature retention, spectral clustering, normal vectors, quadratic error

中图分类号:

TP391.41

朱天晓, 闫丰亭, 史志才. 特征保持的区域分级网格简化算法[J]. 图学学报, 2023, 44(3): 570-578.

ZHU Tian-xiao, YAN Feng-ting, SHI Zhi-cai. Regional hierarchical mesh simplification algorithm for feature retention[J]. Journal of Graphics, 2023, 44(3): 570-578.

图/表 21

图1 边折叠简化原理平面图((a)折叠前；(b)折叠后)

Fig. 1 The principle of edge collapse simplification ((a) Before collapse; (b) After collapse)

图2 RH-QEM算法流程图

Fig. 2 The flow chart of the RH-QEM algorithm

图3 2种算法分割结果对比((a)初始模型；(b) K-Means；(c)谱聚类)

Fig. 3 Segmentation results of the two algorithms ((a) Initial model; (b) K-Means; (c) Spectral clustering)

图4 测地线距离和余弦距离((a)测地线距离；(b)余弦距离)

Fig. 4 Geodesic distance and cosine distance ((a) Geodesic distance; (b) Cosine distance)

图5 座椅模型法向量((a)背部；(b)前部)

Fig. 5 Normal vectors of the seat model ((a) Back part; (b) Front part)

表1 曲折度量指标与分级简化率对应关系

Table 1 Correspondence between the curvature metric and the graded simplification rate

曲折度量指标范围	分级简化率
[0.8, 1.0]	1.0
[0.6, 0.8)	0.9
[0.4, 0.6)	0.4
[0.2, 0.4)	0.2
[0.0, 0.2)	0.1

表2 分割参数

Table 2 Segmentation parameters

参数名称	参数值
a	δ=0.01, η=0.1
b	δ=0.01, η=0.2
c	δ=0.05, η=0.1
d	δ=0.05, η=0.2
e	δ=0.03, η=0.15

图6 不同参数的分割结果((a)参数a；(b)参数b；(c)参数c；(d)参数d；(e)参数e)

Fig. 6 Segmentation results for different parameters ((a) Parameter a; (b) Parameter b; (c) Parameter c; (d) Parameter d; (e) Parameter e)

表3 模型面片数和分割数目

Table 3 The number of faces and the number of segments

模型	面片数	分割数目
座椅1A	3 808	8
座椅2A	3 660	9
桌子1A	3 250	7
桌子2A	8 049	7
座椅1B	19 942	3
座椅2B	20 089	9
桌子1B	20 320	7
桌子2B	19 425	4

图7 谱聚类对模型分割结果((a)座椅1A；(b)座椅2A；(c)桌子1A；(d)桌子2A；(e)座椅1B；(f)座椅2B；(g)桌子1B；(h)桌子2B)

Fig. 7 Segmentation results of spectral clustering ((a) Seat 1A; (b) Seat 2A; (c) Table 1A; (d) Table 2A; (e) Seat 1B; (f) Seat 2B; (g) Table 1B; (h) Table 2B)

图8 座椅1A和桌子1A模型简化80%后的结果((a)初始模型；(b) Melax算法；(c) Web算法；(d) QEM算法；(e) RH-QEM算法)

Fig. 8 Results after 80% simplification of seat 1A and table 1A models ((a) Initial model; (b) Melax; (c) Web; (d) QEM; (e) RH-QEM)

图9 座椅2A和桌子2A模型简化90%后的结果((a)初始模型；(b) Melax算法；(c) Web算法；(d) QEM算法；(e) RH-QEM算法)

Fig. 9 Results after 90% simplification of seat 2A and table 2A models ((a) Initial model; (b) Melax; (c) Web; (d) QEM; (e) RH-QEM)

图10 座椅1B和桌子1B模型简化80%后的结果((a)初始模型；(b) Melax算法；(c) Web算法；(d) QEM算法；(e) RH-QEM算法)

Fig. 10 Results after 80% simplification of seat 1B and table 1B models ((a) Initial model; (b) Melax; (c) Web; (d) QEM; (e) RH-QEM)

图11 座椅2B和桌子2B模型简化90%后的结果((a)初始模型；(b) Melax算法；(c) Web算法；(d) QEM算法；(e) RH-QEM算法)

Fig. 11 Results after 90% simplification of seat 2B and table 2B models ((a) Initial model; (b) Melax; (c) Web; (d) QEM; (e) RH-QEM)

表4 4种简化算法Hausdorff距离对比

Table 4 Comparison of Hausdorff distance of four methods

模型名称	简化率 (%)	Melax 算法	Web 算法	QEM 算法	RH-QEM 算法
座椅1A	80	0.032	0.045	0.027	0.026 0
桌子1A	80	0.066	0.047	0.053	0.046 0
座椅2A	90	0.075	0.323	0.070	0.063 0
桌子2A	90	0.038	0.023	0.015	0.016 0
座椅1B	80	0.115	0.127	0.079	0.075 0
桌子1B	80	0.011	0.093	0.095	0.086 7
座椅2B	90	0.119	0.110	0.108	0.089 0
桌子2B	90	0.197	0.153	0.124	0.100 0

图12 座椅1A和桌子1A模型简化80%后的误差分布((a) Melax算法；(b) Web算法；(c) QEM算法；(d) RH-QEM算法)

Fig. 12 The error distribution after 80% simplification of seat 1A and table 1A models ((a) Melax; (b) Web; (c) QEM; (d) RH-QEM)

图13 座椅2A和桌子2A模型简化90%后的误差分布((a) Melax算法；(b) Web算法；(c) QEM算法；(d) RH-QEM算法)

Fig. 13 The error distribution after 90% simplification of seat 2A and table 2A models ((a) Melax; (b) Web; (c) QEM; (d) RH-QEM)

图14 座椅1B和桌子1B模型简化80%后的误差分布((a) Melax算法；(b) Web算法；(c) QEM算法；(d) RH-QEM算法)

Fig. 14 The error distribution after 80% simplification of seat 1B and table 1B models ((a) Melax; (b) Web; (c) QEM; (d) RH-QEM)

图15 座椅2B和桌子2B模型简化90%后的误差分布((a) Melax算法；(b) Web算法；(c) QEM算法；(d) RH-QEM算法)

Fig. 15 The error distribution after 90% simplification of seat 2B and table 2B models ((a) Melax; (b) Web; (c) QEM; (d) RH-QEM)

图16 4种算法的三角网格质量对比

Fig. 16 Comparison of the four methods of mesh quality

图17 4种算法的三角网格质量与面片数

Fig. 17 The mesh quality of the four methods and model faces

参考文献 22

[1]	林莹莹, 蔡睿凡, 朱雨真, 等. 基于Leap Motion的虚拟现实陶艺体验系统[J]. 图学学报, 2020, 41(1): 57-65.
	LIN Y Y, CAI R F, ZHU Y Z, et al. Virtual reality pottery modeling system based on leap motion[J]. Journal of Graphics, 2020, 41(1): 57-65. (in Chinese)
[2]	李柯, 张乾, 贾金原. 云边页协同的WebBIM大场景多粒度兴趣加载调度算法[J]. 计算机辅助设计与图形学学报, 2021, 33(9): 1388-1397.
	LI K, ZHANG Q, JIA J Y. CEB-collaboratively multi-granularity interest scheduling algorithm for loading large WebBIM scene[J]. Journal of Computer-Aided Design & Computer Graphics, 2021, 33(9): 1388-1397. (in Chinese)
[3]	LYU W, WU W, ZHANG L, et al. Laplacian-based 3D mesh simplification with feature preservation[J]. International Journal of Modeling, Simulation, and Scientific Computing, 2019, 10(2): 1950002. DOI URL
[4]	YI R, LIU Y J, HE Y. Delaunay mesh simplification with differential evolution[J]. ACM Transactions on Graphics, 2018, 37(6): 263.
[5]	LIU X P, et al. Generating sparse self-supporting wireframe models for 3D printing using mesh simplification[J]. Graphical Models, 2018, 98: 14-23. DOI URL
[6]	栾婉娜, 刘成明. 基于逆Loop细分的半正则网格简化算法[J]. 图学学报, 2020, 41(6): 980-986.
	LUAN W N, LIU C M. A semi-regular mesh simplification algorithm based on inverse Loop subdivision[J]. Journal of Graphics, 2020, 41(6): 980-986. (in Chinese)
[7]	GARLAND M, HECKBERT P S. Surface simplification using quadric error metrics[C]// The 24th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 1997: 209-216.
[8]	车力, 唐德军, 李世民, 等. 一种视觉特征保持的网格模型简化方法[J]. 系统仿真学报, 2019, 31(11): 2247-2254. DOI
	CHE L, TANG D J, LI S M, et al. A mesh model simplification method based on visual feature preservation[J]. Journal of System Simulation, 2019, 31(11): 2247-2254. (in Chinese) DOI
[9]	褚苏荣, 牛之贤, 宋春花, 等. 面向移动端的渐进网格简化算法[J]. 计算机应用, 2020, 40(3): 806-811. DOI
	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) DOI
[10]	杨煜, 冼楚华, 李桂清. 结合局部区域特征的自适应简化率网格简化算法[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)
[11]	NG A Y, JORDAN M I, WEISS Y. On spectral clustering: analysis and an algorithm[C]// The 14th International Conference on Neural Information Processing Systems:Natural and Synthetic. New York: ACM, 2001: 849-856.
[12]	LIU R, ZHANG H. Segmentation of 3D meshes through spectral clustering[C]// The 12th Pacific Conference on Computer Graphics and Applications. New York: IEEE Press, 2004: 298-305.
[13]	梁楚萍, 印杰, 伍静, 等. 三维网格分割中聚类分析技术综述[J]. 计算机辅助设计与图形学学报, 2020, 32(4): 680-692.
	LIANG C P, YIN J, WU J, et al. A survey of 3D mesh segmentation based on clustering analysis[J]. Journal of Computer-Aided Design & Computer Graphics, 2020, 32(4): 680-692. (in Chinese)
[14]	赵俊莉, 辛士庆, 刘永进, 等. 网格模型上的离散测地线[J]. 中国科学: 信息科学, 2015, 45(3): 313-335.
	ZHAO J L, XIN S Q, LIU Y J, et al. A survey on the computing of geodesic distances on meshes[J]. Scientia Sinica Informationis, 2015, 45(3): 313-335. (in Chinese) DOI URL
[15]	LI M L. Feature-preserving 3D mesh simplification for urban buildings[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2021, 173: 135-150. DOI URL
[16]	FU H, JIA R F, GAO L, et al. 3D-FUTURE: 3D furniture shape with TextURE[J]. International Journal of Computer Vision, 2021, 129(12): 3313-3337. DOI
[17]	CHOI S, ZHOU Q Y, MILLER S, et al. A large dataset of object scans[EB/OL]. (2016-05-05) [2022-08-30]. https://arxiv.org/abs/1602.02481.
[18]	MELAX S. A simple, fast, and effective polygon reduction algorithm[EB/OL]. [2022-08-17]. https://ubm-twvideo01.s3.amazonaws.com/o1/vault/GD_Mag_Archives/GDM_November_1998.pdf.
[19]	齐洪方, 汪耀. 面向Web的机械产品三维模型简化算法研究[J]. 计算机仿真, 2021, 38(11): 280-283, 289.
	QI H F, WANG Y. Research of web-oriented simplifying mechanical productsʹs 3D model[J]. Computer Simulation, 2021, 38(11): 280-283, 289. (in Chinese)
[20]	CIGNONI P, ROCCHINI C, SCOPIGNO R. Metro: measuring error on simplified surfaces[J]. Computer Graphics Forum, 1998, 17(2): 167-174. DOI URL
[21]	段黎明, 邵辉, 李中明, 等. 高效率的三角网格模型保特征简化方法[J]. 光学精密工程, 2017, 25(2): 460-468.
	DUAN L M, SHAO H, LI Z M, et al. Simplification method for feature preserving of efficient triangular mesh model[J]. Optics and Precision Engineering, 2017, 25(2): 460-468. (in Chinese) DOI URL
[22]	LIANG Y Q, HE F Z, ZENG X T. 3D mesh simplification with feature preservation based on whale optimization algorithm and differential evolution[J]. Integrated Computer-Aided Engineering, 2020, 27(4): 417-435. DOI URL

特征保持的区域分级网格简化算法

Regional hierarchical mesh simplification algorithm for feature retention

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 21

参考文献 22

相关文章 10

编辑推荐

Metrics

本文评价

[1]	岳明宇 , 高希峰 , 毕重科 . 三维建筑模型的低模网格生成[J]. 图学学报, 2023, 44(4): 764-774.
[2]	栾婉娜, 刘成明. 基于逆 Loop 细分的半正则网格简化算法 [J]. 图学学报, 2020, 41(6): 980-986.
[3]	唐科威, 穆梦娇, 李缙红, 张杰, 姜伟, 彭兴璇. 基于快速凸无穷范数极小化的大量子空间的子空间分割[J]. 图学学报, 2020, 41(6): 954-961.
[4]	苏鹏 1，尹梦晓 1,2，王宇攀 3，韩艳茹 1，杨锋 1,2，李桂清 3 . 基于变形图的谱姿态迁移[J]. 图学学报, 2019, 40(2): 282-289.
[5]	陈媛 1，赵凌君 1，匡纲要 1，赵力文 2 . 基于边缘强度特征和线性谱聚类的 SAR 图像超像素生成方法[J]. 图学学报, 2018, 39(6): 1022-1027.
[6]	郭思怡，陈永锋. 建筑运维阶段信息模型的轻量化方法[J]. 图学学报, 2018, 39(1): 123-128.
[7]	魏宁，徐婷婷，高开源，董方敏. 基于Voronoi 极点特征值显著度加权的网格简化算法[J]. 图学学报, 2017, 38(3): 314-319.
[8]	杨大光，胡维多，常波，魏青. 视觉特征保持的网格模型简化算法[J]. 图学学报, 2013, 34(4): 35-40.
[9]	范然，金小刚. 大规模点云选择及精简[J]. 图学学报, 2013, 34(3): 12-19.
[10]	李旭，周卓，时艳茹，尹鹏举. 基于二次误差测度的车身网格简化算法研究[J]. 图学学报, 2010, 31(4): 7-11.