Please wait a minute...
浙江大学学报(工学版)
Journal of ZheJiang University (Engineering Science)  2024, Vol. 58 Issue (2): 257-267    DOI: 10.3785/j.issn.1008-973X.2024.02.004
    
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
Download: HTML     PDF(6328KB) HTML
Export: BibTeX | EndNote (RIS)      

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     
Received: 21 July 2023      Published: 23 January 2024
CLC:  TP 391  
Fund:  国家重点研发计划资助项目(2020YFB1708900); 国家自然科学基金委优秀青年基金资助项目(12022117); 国家自然基金资助项目(2022117, 62272277, 62172415); 中国科学院稳定支持基础研究领域青年团队计划资助项目(YSBR-034); 清华大学水沙科学与水利水电工程国家重点实验室开放基金资助项目(sklhse-2022-D-04).
Corresponding Authors: Xiaohong JIA     E-mail: zengzheng14@amss.ac.cn;xhjia@amss.ac.cn
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Zheng ZENG
Xiaohong JIA
Shiqing XIN
Dongming YAN
Cite this article:

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.

URL:

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


精度可控的边界表示模型网格生成

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


关键词： 边界表示模型,  网格生成,  水密性,  精度优化,  网格分辨率优化 
Fig.1 Illustration of direct method and mapping method in reduced dimension
Fig.2 Process of mesh generation method
Fig.3 Local editing operations of mesh
算法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）.
 
Fig.4 Illustration of preliminary mesh quality optimization
算法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
Tab.1 Todel precision and quality during different stages
Fig.5 Mouse meshes with different precision requirement
图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
Tab.2 Mesh qualities of different mouse models generated with different precision requirements
模型及大小算法$|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
Tab.3 Comparision of mesh precision and quality for our algorithim with open-source software Gmsh and Netgen
Fig.6 Comparison of gears model mesh generation results
Fig.7 Comparison of pillow model mesh generation results
Fig.8 Comparison of hummingbird model mesh generation results
Fig.9 Comparison of turbo model mesh generation results
Fig.10 Comparison of turbo model mesh generation results
Fig.11 Relationship of Hausdorff distance and mesh resolution
Fig.12 Relationship of average distance and mesh resolution
[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] CAO Bing-wan, CHEN Jian-jun, ZHENG Yao, HUANG Zheng-ge, ZHEN Jian-jing. Automatic topology generation algorithm for hybrid surface models[J]. Journal of ZheJiang University (Engineering Science), 2014, 48(5): 923-933.
[2] DAI Xing, CUI Han-guo, LI Zheng-min, ZHANG Li-ping.
Hexahedral mesh generation method for swept volume based on sub-domains reconstruction
[J]. Journal of ZheJiang University (Engineering Science), 2014, 48(10): 1788-1794.
[3] CHEN Jian-jun, XIAO Zhou-fang, Cao Jian, ZHU Chao-yan, ZHENG Yao. Automatic hexahedral mesh generation for many-to-one sweep volumes[J]. Journal of ZheJiang University (Engineering Science), 2012, 46(2): 274-279.