保持细节几何特征的三维网格模型轻量化算法

doi:10.11772/j.issn.1001-9081.2022030434

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (4): 1226-1232.DOI: 10.11772/j.issn.1001-9081.2022030434

• 多媒体计算与计算机仿真 • 上一篇

保持细节几何特征的三维网格模型轻量化算法

张韵¹, 王淑营¹, 郑庆²(), 张海柱²

^1.西南交通大学计算机与人工智能学院，成都 611756
^2.西南交通大学机械工程学院，成都 610031

收稿日期:2022-04-06 修回日期:2022-06-14 接受日期:2022-06-22 发布日期:2023-04-11 出版日期:2023-04-10
通讯作者: 郑庆
作者简介:张韵（1997—），女，四川南充人，硕士研究生，主要研究方向：模型轻量化；
王淑营（1974—），女，天津人，研究员，博士，主要研究方向：云服务平台架构、自适应演化；
张海柱（1989—），男，天津人，助理研究员，博士，主要研究方向：数字化设计与制造。
基金资助:
国家重点研发计划项目(2020YFB1708000);四川省科技计划项目(2021YFG0039)

Lightweight algorithm of 3D mesh model for preserving detailed geometric features

Yun ZHANG¹, Shuying WANG¹, Qing ZHENG²(), Haizhu ZHANG²

^1.School of Computing and Artificial Intelligence，Southwest Jiaotong University，Chengdu Sichuan 611756，China
^2.School of Mechanical Engineering，Southwest Jiaotong University，Chengdu Sichuan 610031，China

Received:2022-04-06 Revised:2022-06-14 Accepted:2022-06-22 Online:2023-04-11 Published:2023-04-10
Contact: Qing ZHENG
About author:ZHANG Yun， born in 1997， M. S. candidate. Her research interests include model lightweighting.
WANG Shuying， born in 1974， Ph. D.， research fellow. Her research interests include cloud service platform architecture， adaptive evolution.
ZHANG Haizhu， born in 1989， Ph. D.， research assistant. His research interests include digital design and manufacturing.
Supported by:
National Key Research and Development Program of China(2020YFB1708000);Sichuan Science and Technology Program(2021YFG0039)

摘要/Abstract

摘要：

对三维模型进行轻量化的一个重要策略是利用网格简化算法减少模型表面的三角面片数量，其中广泛使用的边折叠算法相较于其他网格简化算法效率更高、简化效果更好，然而该算法存在简化过程中可能损坏或丢失部分细节几何特征的问题。为了解决上述问题，提出通过增加曲线近似曲率和模型待折叠边的一阶邻域三角形的平均面积作为惩罚因子，以优化原始算法的边折叠代价。首先，根据几何中曲线曲率的定义，提出了曲线近似曲率的计算公式；其次，在顶点法向量的计算过程中，使用面积加权和内角加权两个阶段对初始法向量进行修正，从而考虑更加丰富的模型几何信息。通过实验验证了优化后算法的性能，与经典的二次误差测度（QEM）算法、顾及角度误差的网格简化算法相比，优化算法处理后的模型的最大误差分别至少降低了73.96%和49.77%；与QEM算法相比，优化算法处理后的模型Hausdorff距离至少降低了17.69%。可见，在模型轻量化的过程中，优化算法能够减少模型的形变，更好地维持自身的细节几何特征。

关键词: 网格简化, 边折叠, 曲线近似曲率, 一阶邻域三角形面积, 模型轻量化

Abstract:

An important strategy for lightweighting a 3D model is to use the mesh simplification algorithm to reduce the number of triangular meshes on the model surface. The widely used edge collapse algorithm is more efficient and has better simplification effect than other mesh simplification algorithms， but some detailed geometric features may be damaged or lost during the simplification process of this algorithm. Therefore， the approximate curvature of curve and the average area of the first-order neighborhood triangle of the edge to be collapsed were added as penalty factors to optimize the edge collapse cost of the original algorithm. First， according to the definition of curve curvature in geometry， the calculation formula of the approximate curvature of curve was proposed. Then， in the calculation process of vertex normal vector， two stages - area weighting and interior angle weighting were used to modify the initial normal vector， thereby considering more abundant geometric information of the model. The performance of the optimized algorithm was verified by experiments. Compared with the classical Quadratic Error Metric （QEM） algorithm and the mesh simplification algorithm considering the angle error， the optimized algorithm has the maximum error reduced by 73.96% and 49.77% at least and respectively. Compared with the QEM algorithm， the optimized algorithm has the Hausdorff distance reduced by 17.69% at least. It can be seen that in the process of model lightweighting， the optimized algorithm can reduce the deformation of the model and better maintain its own detailed geometric features.

Key words: mesh simplification, edge-collapse, approximate curvature of curve, first order neighborhood triangle area, model lightweighting

中图分类号:

TP391.9

张韵, 王淑营, 郑庆, 张海柱. 保持细节几何特征的三维网格模型轻量化算法[J]. 计算机应用, 2023, 43(4): 1226-1232.

Yun ZHANG, Shuying WANG, Qing ZHENG, Haizhu ZHANG. Lightweight algorithm of 3D mesh model for preserving detailed geometric features[J]. Journal of Computer Applications, 2023, 43(4): 1226-1232.

图/表 11

图 1 边折叠操作

Fig. 1 Edge collapse operation

图 2 一阶邻域三角形

Fig. 2 First-order neighborhood triangles

图3 按逆时针顺序排列的顶点和法向量指向

Fig. 3 Vertices in counterclockwise order and normal vector pointing

图4 内角差异

Fig. 4 Interior angle difference

图5 各简化率下车轮模型的简化结果

Fig. 5 Simplification results of wheel model under different simplification rates

图6 各简化率下Arma模型的简化结果

Fig. 6 Simplification results of Arma model under different simplification rates

图7 原始模型（209 227个面片）

Fig. 7 Original model （209 227 meshes）

图8 使用3种算法对Dragon模型在不同简化率下的简化结果对比

Fig. 8 Comparison of simplification results of Dragon model under different simplification rates by using three algorithms

表 1 Hausdorff距离比较结果

Tab. 1 Hausdorff distance comparison results

简化率/%	Hausdorff距离
简化率/%	QEM算法	文献［9］算法	本文算法
30	0.008 173	0.008 131	0.006 727
50	0.011 901	0.008 131	0.006 548
70	0.028 494	0.009 094	0.009 620
90	0.102 853	0.009 162	0.010 424
95	0.105 860	0.033 499	0.014 016

表2 Metro工具比较结果

Tab. 2 Metro tool comparison results

算法	简化率/%	最大误差	平均误差	均方差
QEM算法	30	0.008 023	0.000 024	0.000 086
	50	0.007 552	0.000 075	0.000 197
	70	0.013 870	0.000 196	0.000 429
	90	0.021 714	0.000 557	0.001 128
	95	0.026 602	0.001 029	0.001 937
文献［9］算法	30	0.007 442	0.000 020	0.000 057
	50	0.007 399	0.000 053	0.000 093
	70	0.008 008	0.000 114	0.000 166
	90	0.007 779	0.000 318	0.000 453
	95	0.013 791	0.000 616	0.000 900
本文算法	30	0.001 487	0.000 029	0.000 051
	50	0.001 487	0.000 075	0.000 100
	70	0.003 531	0.000 137	0.000 171
	90	0.002 988	0.000 337	0.000 429
	95	0.006 927	0.000 620	0.000 793

表 3 Dragon模型的简化时间 (min)

Tab. 3 Simplification time of Dragon model

简化率/%	简化时间
简化率/%	QEM算法	文献［9］算法	本文算法
30	10.78	228.65	178.96
50	14.98	258.17	182.23
70	16.15	293.82	213.08
90	20.03	324.27	235.63
95	21.35	330.04	237.39

参考文献 15

1	CAO H R， HOU X G， FENG Y. WebGL-based research on virtual visualization simulation display platform of ship［C］// Proceedings of the 2nd IEEE Advanced Information Management， Communicates， Electronic and Automation Control Conference. Piscataway： IEEE， 2018：895-899. 10.1109/imcec.2018.8469529
2	陈博，佘江峰，谈俊忠，等. 三维场景中建筑物模型简化研究进展［J］.武汉大学学报（信息科学版）， 2020， 45（9）：1429-1437.
	CHEN B， SHE J F， TAN J Z， et al. Research progress on simplification of building models in 3D scenes［J］. Geomatics and Information Science of Wuhan University， 2020， 45（9）：1429-1437.
3	ZHOU G Y， YUAN S D， LUO S M. Mesh simplification algorithm based on the quadratic error metric and triangle collapse［J］. IEEE Access， 2020， 8：196341-196350. 10.1109/access.2020.3034075
4	GARLAND M， HECKBERT P S. Surface simplification using quadric error metrics［C］// Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques. New York： ACM， 1997：209-216. 10.1145/258734.258849
5	邹志文，张立强，陈继明，等. 结合网格分割和边折叠的网格简化算法［J］. 计算机工程， 2012， 38（17）：245-248. 10.3969/j.issn.1000-3428.2012.17.066
	ZOU Z W， ZHANG L Q， CHEN J M， et al. Mesh simplification algorithm combined with mesh segmentation and edge collapse［J］. Computer Engineering， 2012， 38（17）：245-248. 10.3969/j.issn.1000-3428.2012.17.066
6	褚苏荣，牛之贤，宋春花，等. 面向移动端的渐进网格简化算法［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.
7	OZAKI H， KYOTA F， KANAI T. Out-of-core framework for QEM-based mesh simplification［C］// Proceedings of the 15th Eurographics Symposium on Parallel Graphics and Visualization. Goslar： Eurographics Association， 2015：87-96.
8	刘峻，范豪，孙宇，等. 结合边折叠和局部优化的网格简化算法［J］. 计算机应用， 2016， 36（2）：535-540. 10.11772/j.issn.1001-9081.2016.02.0535
	LIU J， FAN H， SUN Y， et al. Mesh simplification algorithm combined with edge collapse and local optimization［J］. Journal of Computer Applications， 2016， 36（2）：535-540. 10.11772/j.issn.1001-9081.2016.02.0535
9	李少卿，霍亮，沈涛，等. 顾及角度误差的三维建筑模型边折叠简化算法［J］. 武汉大学学报（信息科学版）， 2021， 46（8）：1209-1215.
	LI S Q， HUO L， SHEN T， et al. A simplification algorithm for edge collapse of 3D building model considering angle error［J］. Geomatics and Information Science of Wuhan University， 2021， 46（8）：1209-1215.
10	魏宁，徐婷婷，高开源，等. 基于Voronoi极点特征值显著度加权的网格简化算法［J］. 图学学报， 2017， 38（3）：314-319. 10.11996/JG.j.2095-302X.2017030314
	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. 10.11996/JG.j.2095-302X.2017030314
11	张春森，张会，郭丙轩，等. 城市场景结构感知的网格模型简化算法［J］. 测绘学报， 2020， 49（3）：334-342.
	ZHANG C S， ZHANG H， GUO B X， et al. Structure-aware simplified algorithm of mesh model for urban scene［J］. Acta Geodaetica et Cartographica Sinica， 2020， 49（3）：334-342.
12	陈雨，张建伟，谭诗瀚. 顾及局部特征的机场三维模型边折叠算法［J］.现代计算机， 2021（14）：38-41， 53. 10.3969/j.issn.1007-1423.2021.14.007
	CHEN Y， ZHANG J W， TAN S H. A simplification algorithm for edge collapse of 3D airport model considering local characteristics［J］. Modern Computer， 2021（14）：38-41， 53. 10.3969/j.issn.1007-1423.2021.14.007
13	HOPPE H， DeROSE T， DUCHAMP T， et al. Mesh optimization［C］// Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques. New York： ACM， 1993：19-26. 10.1145/166117.166119
14	同济大学数学系. 高等数学；上册［M］. 6版. 北京：高等教育出版社， 2007：170-174.
	School of Mathematical Sciences of Tongji University. Higher Mathematics；Volume I［M］. 6th ed. Beijing： Higher Education Press， 2007：170-174.
15	ARIGE A， LAVRIC T， PREDA M， et al. Analysis of 3D CAD MESH simplification approaches within the framework of AR applications for industrial assembly lines［C］// Proceedings of the IEEE 30th International Symposium on Industrial Electronics. Piscataway： IEEE， 2021：1-6. 10.1109/isie45552.2021.9576475

[1]	褚苏荣, 牛之贤, 宋春花, 牛保宁. 面向移动端的渐进网格简化算法[J]. 计算机应用, 2020, 40(3): 806-811.
[2]	任帅, 张弢, 徐振超, 王震, 贺媛, 柳雨农. 特征点标注与聚类的三维模型信息隐藏算法[J]. 计算机应用, 2018, 38(4): 1017-1022.
[3]	刘峻, 范豪, 孙宇, 陆向艳, 刘艳. 结合边折叠和局部优化的网格简化算法[J]. 计算机应用, 2016, 36(2): 535-540.
[4]	陈燕薛原杨若瑜. 任意衣物和人体的3D试穿实时仿真[J]. 计算机应用, 2014, 34(1): 124-128.
[5]	殷明强李世其. 保持外观的CAD模型轻量化技术[J]. 计算机应用, 2013, 33(06): 1719-1722.
[6]	薛峰袁成凤. 保持外形特征的网格简化算法[J]. 计算机应用, 2010, 30(9): 2431-2433.
[7]	张果刘旭敏关永. 一种基于曲率的边折叠简化算法[J]. 计算机应用, 2009, 29(3): 729-731.
[8]	陈华鸿周莎曹顺艇. 基于移动终端屏幕分辨精度的网格简化算法[J]. 计算机应用, 2008, 28(5): 1225-1228.
[9]	童晶关华勇. 面向影视动画的真实感三维人脸快速建模算法[J]. 计算机应用, 2007, 27(4): 1013-1016.

保持细节几何特征的三维网格模型轻量化算法

Lightweight algorithm of 3D mesh model for preserving detailed geometric features

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 15

相关文章 9

编辑推荐

Metrics