Regional hierarchical mesh simplification algorithm for feature retention

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

Abstract

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

CLC Number:

TP391.41

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.

Figures/Tables 21

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

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

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

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

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

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

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

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

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

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)

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)

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)

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)

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)

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

Fig. 12 The error distribution after 80% simplification of seat 1A and table 1A models ((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)

Fig. 14 The error distribution after 80% simplification of seat 1B and table 1B models ((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)

Fig. 16 Comparison of the four methods of mesh quality

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

References 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