Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)  2024, Vol. 58 Issue (2): 257-267    DOI: 10.3785/j.issn.1008-973X.2024.02.004
计算机技术、通信技术     
精度可控的边界表示模型网格生成
曾铮1(),贾晓红1,*(),辛士庆2,严冬明3,4
1. 中国科学院数学与系统科学研究院 系统科学研究所，北京 100190
2. 山东大学 计算机科学与技术学院，山东 青岛 250100
3. 中国科学院自动化研究所 多模态人工智能系统全国重点实验室，北京 100190
4. 清华大学 水沙科学与水利水电工程国家重点实验室，北京 100084
Precision controllable mesh generation for boundary representation model
Zheng ZENG1(),Xiaohong JIA1,*(),Shiqing XIN2,Dongming YAN3,4
1. Institute of Systems Science, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China
2. School of Computer Science and Technology, Shandong University, Qingdao 250100, China
3. State Key Laboratory of Multimodal Artificial Intelligence Systems, Institute of Automation, Chinese Academy of Sciences, Beijing 100190, China
4. State Key Laboratory of Hydroscience and Engineering, Tsinghua University, Beijing 100084, China
 全文: PDF(6328 KB)   HTML
摘要：

针对边界表示模型生成的面网格模型存在的误差大、分辨率高和不水密的问题，提出针对计算机辅助设计（CAD）实体模型的保精度网格生成算法. 算法通过同步生成对齐共边点对保证网格的水密性；利用连续表征设计网格目标边长，以生成高精度、低分辨率的网格. 与现有的开源网格生成软件相比，算法能用更少的网格面片数生成精度更高的网格，且网格质量与其相当.
关键词： 边界表示模型;  网格生成;  水密性;  精度优化;  网格分辨率优化    
Abstract:

A precision-preserving mesh generation algorithm for computer aided design (CAD) solid models was proposed aiming at the issues of large errors, high resolution and non-watertightness in the surface mesh models generated by boundary representation models. The watertightness of the mesh was ensured by synchronously generating aligned pairs of vertices on shared curves. A continuous representation was utilized to design the target edge length of the mesh, resulting in a high-precision, low-resolution mesh. The algorithm can achieve higher-precision meshes with fewer mesh faces, while maintaining comparable mesh quality compared to existing open-source mesh generation software.
Key words: boundary representation model    mesh generation    watertightness    precision optimization    mesh resolution optimization
收稿日期: 2023-07-21 出版日期: 2024-01-23
CLC:  TP 391  
基金资助: 国家重点研发计划资助项目(2020YFB1708900); 国家自然科学基金委优秀青年基金资助项目(12022117); 国家自然基金资助项目(2022117, 62272277, 62172415); 中国科学院稳定支持基础研究领域青年团队计划资助项目(YSBR-034); 清华大学水沙科学与水利水电工程国家重点实验室开放基金资助项目(sklhse-2022-D-04).
通讯作者: 贾晓红     E-mail: zengzheng14@amss.ac.cn;xhjia@amss.ac.cn
作者简介: 曾铮（1996—），女，博士，从事计算机辅助设计的研究. orcid.org/0009?0005?8693?3796. E-mail：zengzheng14@amss.ac.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章　　
曾铮
贾晓红
辛士庆
严冬明

引用本文:

曾铮,贾晓红,辛士庆,严冬明. 精度可控的边界表示模型网格生成[J]. 浙江大学学报(工学版), 2024, 58(2): 257-267.

Zheng ZENG,Xiaohong JIA,Shiqing XIN,Dongming YAN. Precision controllable mesh generation for boundary representation model. Journal of ZheJiang University (Engineering Science), 2024, 58(2): 257-267.

链接本文:

https://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2024.02.004    或    https://www.zjujournals.com/eng/CN/Y2024/V58/I2/257

图 1  直接法与映射法的降维示意图
图 2  网格生成算法的流程
图 3  网格的局部编辑操作
算法1　边界采样点生成算法
输入：用户给定的距离误差$e$，CAD模型一片曲面$S$上的一条边界线$C$以及在初始化所得网格$M$上$C$对应的网格边集${E_C}$.
输出：优化后的网格边集${E_C}$.
1）初始化迭代次数$i = 0\;\;.$
2）while $i < 20$ do
3）计算${E_C}$中的每条边的目标边长（步骤1.1）.
4）对${E_C}$中的每条边进行边分裂优化（步骤1.2）.
5）对${E_C}$中端点外的顶点进行位置优化（步骤1.4）.
6）计算${E_C}$中的每条边的目标边长（步骤1.1）.
7）对${E_C}$中的每条边进行边合并优化（步骤1.3）.
8）对${E_C}$中端点外的顶点进行位置优化（步骤1.4）.
9）$i: = i+1$
10）end while
  
算法2　网格精度优化算法
输入：用户给定的距离误差$e$、CAD模型中的曲面片$S$及边界采样点优化后的网格$M$.
输出：误差优化后的网格$M$.
1） 初始化收敛距离$d = L$，$L$为模型包围盒对角线长度.
2） 循环执行40次以下步骤2）~10），直到$d > 0.1e$.
3） 计算网格$M$每点处的目标边长（步骤2.1）.
4） 对网格$M$中的每条边进行边分裂优化（步骤2.2）.
5） 对网格$M$中的每条边进行顶点度优化（步骤2.4）.
6） 对网格$M$中的内部网格点进行位置优化（步骤2.5）.
7） 计算网格$M$每点处的目标边长（步骤2.1）.
8） 对网格$M$中的每条边进行边合并优化（步骤2.3）.
9） 对网格$M$中的每条边进行顶点度优化（步骤2.4）.
10）对网格$M$中的内部网格点进行位置优化（步骤2.5），更新$d$为所有网格点位置偏移长度的最大值.
11） 对网格$M$中的每条边进行角度优化（步骤2.6）.
  
图 4  网格质量初步优化的示意图
算法3　确定网格顶点数算法
输入：CAD模型中的曲面片$S$及误差优化后的网格$M$.
输出：顶点数优化后的网格$M$.
1）循环执行4次步骤2）~7）.
2）对$M$进行边分裂优化（步骤3.1）并标记新增顶点.
3）对$M$的每条边进行角度优化（步骤2.6）并标记翻转网格边的顶点.
4）对$M$中标记网格点的2-邻域内的内部网格点进行位置优化（步骤2.5）并清除标记.
5）对$M$进行边合并优化（步骤3.2），标记合并后的顶点.
6）对$M$的每条边进行角度优化（步骤2.6），标记翻转网格边的顶点.
7）对$M$中标记网格点的2-邻域内的内部网格点进行位置优化（步骤2.5），清除标记.
  
算法4　网格全局优化算法
输入：CAD模型及对应的水密网格${M_{\mathrm{w}}}$.
输出：全局优化后的水密网格${M_{\mathrm{w}}}$.
1）循环执行20次步骤2）~9）.
2）对${M_{\mathrm{w}}}$进行边分裂优化（步骤4.2）并标记新增点.
3）对${M_{\mathrm{w}}}$进行顶点度优化（步骤2.4）并标记翻边的顶点.
4）计算${M_{\mathrm{w}}}$的目标边长（步骤4.1）.
5）对${M_{\mathrm{w}}}$中所有标记网格点的2-环邻域内的网格点进行位置优化和更新目标边长（步骤4.4），清除标记.
6）对${M_{\mathrm{w}}}$进行边合并优化（步骤4.3），标记合并后的顶点.
7）对${M_{\mathrm{w}}}$进行顶点度优化（步骤2.4），标记翻转边的顶点.
8）计算${M_{\mathrm{w}}}$的目标边长（步骤4.1）.
9）对${M_{\mathrm{w}}}$中所有标记网格点的2-环邻域内的网格点进行位置优化（步骤4.4），清除标记.
  
网格模型$L$$e$$|V|$$h$$d$${\theta _{{\text{min}}}/{\rm{(^\circ )}}}$${\theta _{{\text{max}}}/{\rm{(^\circ )}}}$${\theta _{{\text{avg}}}/{\rm{(^\circ )}}}$$T$/s
椭球（阶段1）107.490.3744770.350.0123.43125.9950.3315.6
椭球（阶段2）107.490.3744770.350.0138.2289.9752.072.3
鼠标（阶段1）299.360.6020830.550.066.03133.3943.6126.3
鼠标（阶段2）299.360.6023851.670.1017.83121.5549.451.8
鼠标（阶段3）299.360.6025710.580.0617.88120.3149.301.1
表 1  算法各阶段的模型精度与质量
图 5  不同精度指标下的鼠标网格
图5$e$$|V|$$h$$d$${\theta _{{\text{min}}}/{\rm{(^\circ )}}}$${\theta _{{\text{max}}}/{\rm{(^\circ )}}}$${\theta _{{\text{avg}}}/{\rm{(^\circ )}}}$${\theta _{{\text{small}}}/{\rm{(^\circ )}}}$$T/{\mathrm{s}}$
图5(a)0.03304670.0280.00320.83134.1551.170.13368.3
图5(b)0.1288990.120.01421.17117.9050.050.07120.7
图5(c)0.3041520.260.03118.39134.3249.800.5048.7
图5(d)0.6025710.580.06017.88120.3149.300.6029.2
表 2  不同精度要求的鼠标网格模型质量指标
模型及大小算法$|V|$$h$$d$${\theta _{{\text{min}}}/{\rm{(^\circ )}}}$${\theta _{{\text{max}}}/{\rm{(^\circ )}}}$${\theta _{{\text{avg}}}/{\rm{(^\circ )}}}$${\theta _{{\text{small}}}/{\rm{(^\circ )}}}$
齿轮Gmsh130620.680.0571.13171.7146.1416.57
$ L = 103.00 $Netgen171610.610.0426.22159.3846.025.18
$ P = 229 $本算法（$e = 0.2$）79210.190.0395.91171.8242.6410.73
蜂鸟Gmsh878373.630.3835.41169.1650.990.86
$ L = 8\;246.02 $Netgen684222.280.16418.24117.7352.500.03
$ P = 312 $本算法（$e = 1.0$）611800.990.09317.56137.9650.310.05
涡轮Gmsh581930.330.0150.21178.7553.631.48
$ L = 226.28 $Netgen434990.240.0113.17156.9750.940.26
$ P = 138 $本算法（$e = 0.06$）406430.060.0062.74159.2948.380.42
鼠标Gmsh402450.310.0333.35119.6247.720.07
$L = 229.36$Netgen582990.570.02820.50118.9050.040.09
$P = 38$本算法（$e = 0.12$）88990.120.01421.17117.9050.050.07
枕头Gmsh30300.370.06320.24134.3748.781.91
$L = 104.62$Netgen22460.930.14529.45107.4950.590.04
$P = 8$本算法（$e = 0.4$）1 8350.310.04835.0291.7951.190.00
表 3  本算法与开源网格生成软件Gmsh和Netgen在网格精度和质量上的比较
图 6  齿轮模型网格生成结果的对比
图 7  枕头模型网格生成结果的对比
图 8  蜂鸟模型网格生成结果的对比
图 9  涡轮模型网格生成结果的对比
图 10  鼠标模型网格生成结果的对比
图 11  Hausdorff距离与网格分辨率的关系
图 12  平均距离与网格分辨率的关系
1 Open Cascade SAS. Open cascade technology [EB/OL]. (2023-01-01)[2023-04-15]. https://www.opencascade.com/.
2 SCHÖBERL J NETGEN An advancing front 2D/3D-mesh generator based on abstract rules[J]. Computing and Visualization in Science, 1997, 1 (1): 41- 52
doi: 10.1007/s007910050004
3 GEUZAINE C, REMACLE J F Gmsh: a 3-D finite element mesh generator with built-in pre-and post-processing facilities[J]. International Journal for Numerical Methods in Engineering, 2009, 79 (11): 1309- 1331
doi: 10.1002/nme.2579
4 ATTENE M A lightweight approach to repairing digitized polygon meshes[J]. The Visual Computer, 2010, 26 (11): 1393- 1406
doi: 10.1007/s00371-010-0416-3
5 JU T Robust repair of polygonal models[J]. ACM Transactions on Graphics, 2004, 23 (3): 888- 895
doi: 10.1145/1015706.1015815
6 王骁, 雷娜, 罗钟铉 基于局部的全自动网格修复算法[J]. 计算机辅助设计与图形学学报, 2022, 34 (19179): 1391- 1401
WANG Xiao, LEI Na, LUO Zhongxuan An automatic surface-based mesh repairing algorithm[J]. Journal of Computer-Aided Design and Computer Graphics, 2022, 34 (19179): 1391- 1401
7 CENTIN M, PEZZOTTI N, SIGNORONI A Poisson-driven seamless completion of triangular meshes[J]. Computer Aided Geometric Design, 2015, 35: 42- 55
8 ALLIEZ P, UCELLI G, GOTSMAN C, et al. Recent advances in remeshing of surfaces [M]// DE FLORIANI L, SPAGNUOLO M. Shape analysis and structuring . Berlin: Springer , 2008: 53-82.
9 BOTSCH M, KOBBELT L, PAULY M, et al. Polygon mesh processing [M]. Boca Raton: CRC Press, 2010: 85-150.
10 KHAN D, PLOPSKI A, FUJIMOTO Y, et al Surface remeshing: a systematic literature review of methods and research directions[J]. IEEE Transactions on Visualization and Computer Graphics, 2020, 28 (3): 1680- 1713
11 HARTMANN E A marching method for the triangulation of surfaces[J]. The Visual Computer, 1998, 14 (3): 95- 108
doi: 10.1007/s003710050126
12 CUILLIÉRE J An adaptive method for the automatic triangulation of 3D parametric surfaces[J]. Computer-Aided Design, 1998, 30 (2): 139- 149
doi: 10.1016/S0010-4485(97)00085-7
13 ZHONG Z, GUO X, WANG W, et al Particle-based anisotropic surface meshing[J]. ACM Transactions on Graphics, 2013, 32 (4): 1- 14
14 SHIMADA K, GOSSARD D C Automatic triangular mesh generation of trimmed parametric surfaces for finite element analysis[J]. Computer Aided Geometric Design, 1998, 15 (3): 199- 222
doi: 10.1016/S0167-8396(97)00037-X
15 PEYRÉ G, COHEN L. Surface segmentation using geodesic centroidal tessellation [C]// Proceedings of 2nd International Symposium on 3D Data Processing, Visualization and Transmission . Thessaloniki: IEEE, 2004: 995-1002.
16 VALETTE S, CHASSERY J M, PROST R Generic remeshing of 3D triangular meshes with metric-dependent discrete Voronoi diagrams[J]. IEEE Transactions on Visualization and Computer Graphics, 2008, 14 (2): 369- 381
doi: 10.1109/TVCG.2007.70430
17 YAN D M, LÉVY B, LIU Y, et al Isotropic remeshing with fast and exact computation of restricted Voronoi diagram[J]. Computer Graphics Forum, 2009, 28 (5): 1445- 1454
doi: 10.1111/j.1467-8659.2009.01521.x
18 DU Q, WANG D Anisotropic centroidal Voronoi tessellations and their applications[J]. SIAM Journal on Scientific Computing, 2005, 26 (3): 737- 761
doi: 10.1137/S1064827503428527
19 LABELLE F, SHEWCHUK J R. Anisotropic Voronoi diagrams and guaranteed-quality anisotropic mesh generation [C]// Proceedings of the 19th Annual Symposium on Computational Geometry . New York: ACM, 2003: 191- 200.
20 SHENG X, HIRSCH B E Triangulation of trimmed surfaces in parametric space[J]. Computer-Aided Design, 1992, 24 (8): 437- 444
doi: 10.1016/0010-4485(92)90011-X
21 GU X, YAU S T. Global conformal surface parameterization [C]// Proceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing . Goslar: ACM, 2003: 127-137.
22 LIU L, YE C, NI R, et al Progressive parameterizations[J]. ACM Transactions on Graphics, 2018, 37 (4): 1- 12
23 SU K, LEI N, CHEN W, et al Curvature adaptive surface remeshing by sampling normal cycle[J]. Computer-Aided Design, 2019, 111: 1- 12
doi: 10.1016/j.cad.2019.01.004
24 BÉCHET E, CUILLIERE J C, TROCHU F Generation of a finite element MESH from stereolithography (STL) files[J]. Computer-Aided Design, 2002, 34 (1): 1- 17
doi: 10.1016/S0010-4485(00)00146-9
25 AUBRY R, KARAMETE B K, MESTREAU E L, et al A three-dimensional parametric mesher with surface boundary-layer capability[J]. Journal of Computational Physics, 2014, 270: 161- 181
doi: 10.1016/j.jcp.2014.03.057
26 GUO J, DING F, JIA X, et al Automatic and high-quality surface mesh generation for CAD models[J]. Computer-Aided Design, 2019, 109: 49- 59
doi: 10.1016/j.cad.2018.12.005
27 尤磊, 申则宇, 张立强, 等 CAD 模型三角网格优化算 法[J]. 计算机辅助设计与图形学学报, 2019, 31 (6): 878- 885
YOU Lei, SHEN Zeyu, ZHANG Liqiang, et al A mesh optimization algorithm for CAD models[J]. Journal of Computer-Aided Design and Computer Graphics, 2019, 31 (6): 878- 885
doi: 10.3724/SP.J.1089.2019.17393
28 SHEWCHUK J R. What is a good linear element? interpolation, conditioning, and quality measures [C]// Proceedings of the International Meshing Roundtable . Ithaca: SIAM, 2002: 115-126.
29 FREY P J, BOROUCHAKI H Geometric surface mesh optimization[J]. Computing and Visualization in Science, 1998, 1 (3): 113- 121
doi: 10.1007/s007910050011
30 BOTSCH M, BOMMES D, VOGEL C, et al. GPU-based tolerance volumes for mesh processing [C]// Proceedings of the Pacific Conference on Computer Graphics and Applications . Goslar: IEEE, 2004: 237-243.
31 MANDAD M, COHEN-STEINER D, ALLIEZ P Isotopic approximation within a tolerance volume[J]. ACM Transactions on Graphics, 2015, 34 (4): 1- 12
32 WANG B, SCHNEIDER T, HU Y, et al Exact and efficient polyhedral envelope containment check[J]. ACM Transactions on Graphics, 2020, 39 (4): 114
33 HU K, YAN D M, BOMMES D, et al Error-bounded and feature preserving surface remeshing with minimal angle improvement[J]. IEEE Transactions on Visualization and Computer Graphics, 2016, 23 (12): 2560- 2573
34 YANG Y, ZHANG W X, LIU Y, et al Error-bounded compatible remeshing[J]. ACM Transactions on Graphics, 2020, 39 (4): 1- 15
35 ZHANG W X, WANG Q, GUO J P, et al Constrained remeshing using evolutionary vertex optimization[J]. Computer Graphics Forum, 2022, 41 (2): 237- 247
doi: 10.1111/cgf.14471
[1] 余翔,赖远平,王钰轲,屈永倩,郑浩然. 跨尺度网格识别方法及在防渗墙分析中的应用[J]. 浙江大学学报(工学版), 2023, 57(10): 2116-2125.
[2] 张子新, 孙杰, 朱雁飞, 黄昕, 袁玮皓. 深埋排蓄水隧道接缝密封垫防水性能试验研究[J]. 浙江大学学报(工学版), 2018, 52(3): 431-439.
[3] 潘炜, 吴慧, 李铁瑞, 高博青. 基于曲面展开的自由曲面网格划分[J]. 浙江大学学报(工学版), 2016, 50(10): 1973-1979.
[4] 曹秉万,陈建军,郑耀,黄争舸,郑建靖. 面向混合曲面模型的自动拓扑生成算法[J]. 浙江大学学报(工学版), 2014, 48(5): 923-933.
[5] 丁慧, 罗尧治. 自由形态网壳结构网格生成的等参线分割法[J]. 浙江大学学报(工学版), 2014, 48(10): 1795-1801.
[6] 陈建军, 肖周芳, 曹建, 朱朝艳, 郑耀. 多源扫掠体全六面体网格自动生成算法[J]. J4, 2012, 46(2): 274-279.
[7] 黄争舸, 陈建军, 郑耀. 基于不规则三角网的分块地形网格生成算法[J]. J4, 2009, 43(10): 1939-1943.
[8] 梁义 陈建军 陈立岗 郑耀. 并行平面Delaunay网格生成[J]. J4, 2008, 42(4): 558-564.
[9] 毕运波 柯映林 董辉跃. 扫掠体六面体网格生成算法研究[J]. J4, 2007, 41(5): 723-731.