各向同性三角形重新网格化方法综述

doi:10.11896/j.issn.1002-137X.2017.08.002

摘要/Abstract

摘要： 三维网格模型的重新网格化是计算机图形学中的重要内容,是许多几何应用的关键组成部分。近年来迅速发展的三维处理技术,如有限元模拟、计算机动画、三维打印等,对网格质量的要求不断提升,促进了三维网格模型重新网格化的持续发展,由此产生了许多新的重新网格化技术。首先介绍了三角形网格质量评估的标准,然后概述了各向同性重新网格化的最新进展,并详细研究和比较了各种重新网格化算法的优缺点,最后对未来的研究提出了新的问题与方向。

关键词: 重新网格化,质量评估,各向同性,流场,局部操作,优化,蓝噪声

Abstract: Remeshing of 3D mesh models is an important task of computer graphics,and it is a key component of many geometric algorithms.In recent years,the rapid development of 3D applications,such as finite element modeling,computer animation,3D printing,requires higher quality of mesh,and promotes the rapid development of remeshing of 3D mesh models,resulting in many new remeshing technologies.In this paper,we first introduced the evaluation criteria of meshing quality.Then,we surveyed the latest development in isotropic remeshing and discussed the advantages and disadvantages of various remeshing algorithms.Finally,we discussed some new problems and directions for future research.

Key words: Remeshing,Quality evaluation,Isotropic,Vector field,Local operation,Optimization,Blue-noise

严冬明,胡楷模,郭建伟,王逸群,张义宽,张晓鹏. 各向同性三角形重新网格化方法综述[J]. 计算机科学, 2017, 44(8): 9-17. https://doi.org/10.11896/j.issn.1002-137X.2017.08.002

YAN Dong-ming, HU Kai-mo, GUO Jian-wei, WANG Yi-qun, ZHANG Yi-kuan and ZHANG Xiao-peng. Survey of Recent Isotropic Triangular Remeshing Techniques[J]. Computer Science, 2017, 44(8): 9-17. https://doi.org/10.11896/j.issn.1002-137X.2017.08.002

参考文献

[1] TANG M,LEE M,KIM Y J.Interactive Hausdorff distancecomputation for general polygonal models[J].ACM Transactions on Graphics (TOG),2009,28(3):74.
[2] CIGNONI P,ROCCHINI C,SCOPIGNO R.Metro:measuringerror on simplified surfaces[C]∥Computer Graphics Forum.1998:167-174.
[3] FREY P J,BOROUCHAKI H.Surface mesh evaluation[C]∥6th International Meshing Roundtable.1997:363-374.
[4] SHEWCHUK J.What is a good linear finite element? interpolation,conditioning,anisotropy,and quality measures (preprint)[D].University of California at Berkeley,2002.
[5] FARIN G.Shape measures for triangles[J].IEEE Transactions on Visualization and Computer Graphics,2012,18(1):43-46.
[6] GUSKOV I,VIDIMˇE K,S WELDENS W,et al.Normal meshes[C]∥Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques.ACM Press/Addison-Wesley Publishing Co.,2000:95-102.
[7] LU L,SUN F,PAN H,et al.Global optimization of centroidal voronoi tessellation with monte carlo approach[J].IEEE Tran-sactions on Visualization and Computer Graphics,2012,18(11):1880-1890.
[8] BOTSCH M,KOBBELT L,PAULY M,et al.Polygon meshprocessing[M].CRC Press,2010.
[9] MANDAD M,COHEN-STEINER D,ALLIEZ P.Isotopic approximation within a tolerance volume[J].ACM Transactions on Graphics (TOG),2015,34(4):64.
[10] ALLIEZ P,UCELLI G,GOTSMAN C,et al.Recent advances in remeshing of surfaces[M]∥Shape Analysis and Structuring.Springer Berlin Heidelberg,2008:53-82.
[11] HECKBERT P S,GARLAND M.Survey of polygonal surface simplification algorithms[R].DTIC Document,1997.
[12] PAYAN F,ROUDET C,SAUVAGE B.Semi-Regular Triangle Remeshing:A Comprehensive Study[J].Computer Graphics Forum,2015,34(1):86-102.
[13] BOMMES D,LVY B,PIETRONI N,et al.Quad-Mesh Gene-ration and Processing:A Survey[J].Computer Graphics Forum,2013,32(6):51-76.
[14] TURK G.Re-tiling polygonal surfaces[J].Conference on Computer Graphics and Internative Techniques,1992,26(2):55-64.
[15] FUHRMANN S,ACKERMANN J,KALBE T,et al.Direct Resampling for Isotropic Surface Remeshing[C]∥VMV.2010:9-16.
[16] HOPPE H,DEROSE T,DUCHAMP T,et al.Mesh optimization[C]∥Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques.ACM,1993:19-26.
[17] BOTSCH M,KOBBELT L.Resampling Feature and Blend Regions in Polygonal Meshes for Surface Anti-Aliasing[J].Computer Graphics Forum,2001,20(3):402-410.
[18] BISCHOFF B S,BOTSCH M,S TEINBERG S,et al.OpenMesh:a generic and efficient polygon mesh data structure[C]∥OpenSGSymposium.2002.
[19] KOBBELT M B C R L.Feature Sensitive Sampling for Interactive Remeshing[C]∥Vision,Modeling,and Visualization 2000.Saarbrücken,Germany,2000:129-136.
[20] SURAZHSKY V,GOTSMAN C.Explicit surface remeshing[C]∥Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing.Eurographics Association,2003:20-30.
[21] BOTSCH M,KOBBELT L.A remeshing approach to multiresolution modeling[C]∥Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing.ACM,2004:185-192.
[22] DUNYACH M,VANDERHAEGHE D,BARTHE L,et al.Adaptive Remeshing for Real-Time Mesh Deformation[C]∥Eurographics (Short Papers).2013:29-32.
[23] LI J Y S,ZHANG H.Nonobtuse remeshing and mesh decimation[C]∥Symposium on Geometry Processing.2006:235-238.
[24] LAI Y K,MARTIN R R.Vertex location optimisation for improved remeshing[J].Graphical Models,2012,74(4):233-243.
[25] LI Y,ZHANG E,KOBAYASHI Y,et al.Editing operations for irregular vertices in triangle meshes[J].ACM Transactions on Graphics (TOG),2010,29(6):153.
[26] AGHDAII N,YOUNESY H,ZHANG H.5-6-7 Meshes:Re-meshing and analysis[J].Computers & Graphics,2012,36(8):1072-1083.
[27] CHEW L P.Guaranteed-quality mesh generation for curved surfaces[C]∥Proceedings of the Ninth Annual Symposium on Computational Geometry.ACM,1993:274-280.
[28] CHENG S W,DEY T K,LEVINE J A.A practical Delaunay meshing algorithm for a large class of domains[C]∥Proceedings of the 16th International Meshing Roundtable.Springer Berlin Heidelberg,2008:477-494.
[29] OUDOT S,BOISSONNAT J D.Provably Good Surface Sam-pling and Approximation[C]∥Symposium on Geometry Processing.2003:9-18.
[30] BOISSONNAT J D,SHI K L,T OURNOIS J,et al.Anisotropic Delaunay meshes of surfaces[J].ACM Transactions on Graphics (TOG),2015,34(2):14.
[31] DYER R,ZHANG H,MLER T.Delaunay mesh construction[C]∥Symposium on Geometry Processing.2007:273-282.
[32] DYER R,ZHANG H,MLER T.Gabriel meshes and Delaunay edge flips[C]∥2009 SIAM/ACM Joint Conference on Geome-tric and Physical Modeling.ACM,2009:295-300.
[33] DEY T K,LEVINE J A.Delaunay meshing of piecewise smooth complexes without expensive predicates[J].Algorithms,2009,2(4):1327-1349.
[34] CHENG S W,DEY T K,RAMOS E A.Delaunay refinement for piecewise smooth complexes[J].Discrete & Computational Geometry,2010,43(1):121-166.
[35] DEY T K,LEVINE J A.DelPSC:a Delaunay mesher for piecewise smooth complexes[C]∥Proceedings of the twenty-fourth annual symposium on Computational geometry.ACM,2008:220-221.
[36] CHENG S W,DEY T K,SHEWCHUK J.Delaunay mesh ge-neration[M].CRC Press,2012.
[37] GU X,GORTLER S J,HOPPE H.Geometry images[J].ACM Transactions on Graphics (TOG),2002,21(3):355-361.
[38] SANDER P V,WOOD Z J,GORTLER S J,et al.Multi-chart geometry images[C]∥Symposium on Geometry Processing Proceedings.Aachen,Germany,2003:146-155.
[39] ALIEZ P,MEYER M,DESBRUN M.Interactive geometryremeshing[J].ACM Transactions on Graphics (TOG),2002,21(3):347-354.
[40] SURAZHSKY V,ALLIEZ P,GOTSMAN C.Isotropic reme-shing of surfaces:a local parameterization approach[C]∥INRIA.2006:215-224.
[41] ALLIEZ P,DE VERDIRE E C,D EVILLERS O,et al.Isotropic surface remeshing[C]∥Shape Modeling International,2003.IEEE,2003:49-58.
[42] ALLIEZ P,DE VERDIRE C,DEVILLERS O,et al.Centroidal Voronoi diagrams for isotropic surface remeshing[J].Graphi-cal Models,2005,67(3):204-231.
[43] DU Q,FABER V,GUNZBURGER M.Centroidal Voronoi tessellations:applications and algorithms[J].SIAM review,1999,41(4):637-676.
[44] RONG G,JIN M,SHUAI L,et al.Centroidal Voronoi tessellation in universal covering space of manifold surfaces[J].Computer Aided Geometric Design,2011,28(8):475-496.
[45] RONG G,LIU Y,WANG W,et al.GPU-assisted computation ofcentroidal Voronoi tessellation[J].IEEE Transactions on Visua-lization and Computer Graphics,2011,17(3):345-356.
[46] LIU Y,WANG W,LVY B,et al.On centroidal voronoi tessellation—energy smoothness and fast computation[J].ACM Transactions on Graphics (ToG),2009,28(4):101.
[47] LAI Y K,JIN M,XIE X,et al.Metric-driven rosy field design and remeshing[J].IEEE Transactions on Visualization and Computer Graphics,2010,16(1):95-108.
[48] HUANG J,ZHANG M Y,PEI W J,et al.Controllable highlyregular triangulation[J].Science China Information Sciences,2011,54(6):1172-1183.
[49] RAY N,LI W C,LVY B,et al.Periodic global parameterization[J].ACM Transactions on Graphics (TOG),2006,25(4):1460-1485.
[50] NIESER M,PALACIOS J,POLTHIER K,et al.Hexagonal glo-bal parameterization of arbitrary surfaces[J].IEEE Transactions on Visualization and Computer Graphics,2012,18(6):865-878.
[51] JAKOB W,TARINI M,PANOZZO D,et al.Instant field-aligned meshes[J].ACM Transactions on Graphics,2015,34(6):1-15.
[52] LLOYD S.Least squares quantization in PCM[J].IEEE Tran-sactions on Information Theory,1982,28(2):129-137.
[53] EDELSBRUNNER H,SHAH N R.Triangulating Topological Spaces[J].International Journal of Computational Geometry & Applications,1997,7(4):365-378.
[54] ALLIEZ P,COHEN-STEINER D,YVINEC M,et al.Variatio-nal tetrahedral meshing[C]∥ACM Siggraph Courses.2005:617-625.
[55] SBASTIEN V,JEAN-M C.Approximated Centroidal Voro-noi Diagrams for Uniform Polygonal Mesh Coarsening[J].Computer Graphics Forum,2004,23(3):381-389.
[56] VALETTE S,CHASSERY J M,PROST R.Generic Remeshing of 3D Triangular Meshes with Metric-Dependent Discrete Voronoi Diagrams[J].IEEE Transactions on Visualization & Computer Graphics,2007,14(2):369-381.
[57] YAN D,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.
[58] YAN D M,WONKA P.Non-obtuse Remeshing with Centroidal Voronoi Tessellation[J].IEEE Transactions on Visualization &Computer Graphics,2015,22(9):2136-2144.
[59] LVY B,BONNELLY N.Variational Anisotropic Surface Meshing with Voronoi Parallel Linear Enumeration[C]∥Procee-dings of the 21st International Meshing Roundtable.Springer Berlin Heidelberg,2013:349-366.
[60] LVY B.Goodshape:Towards flexible mesh generation[N].ERCIM News,2012.
[61] YAN D M,BAO G,ZHANG X,et al.Low-Resolution Reme-shing Using the Localized Restricted Voronoi Diagram[J].IEEE Transactions on Visualization & Computer Graphics,2014,20(10):418-1427.
[62] COEH-STEINER D,ALLIEZ P,DESBRUN M.Variational sha-pe approximation[J].ACM Transactions on Graphics,2004,23(3):905-914.
[63] SIFRI O,SHEFFER A,GOTSMAN C.Geodesic-based surface remeshing[C]∥Proceedings of the 12th International Meshing Roundtable(IMR 2003).2003:189-199.
[64] KIMMEL R,SETHIAN J A.Computing geodesic paths on ma-nifolds[J].Proceedings of the National Academy of Sciences of the United States of America,1998,95(15):8431-8435.
[65] PEYR G,COHEN L.Geodesic Computations for Fast and Accurate Surface Remeshing and Parameterization[M]∥Elliptic and Parabolic Problems.Birkhuser Basel,2005:157-171.
[66] PEYR G,COHEN L.Geodesic Computation for Adaptive Reme-shing[C]∥2013 IEEE Conference on Computer Vision and Pattern Recognition.2005:3048-3052.
[67] PEYR G,COHEN L D.Geodesic Remeshing Using FrontPropagation[J].International Journal of Computer Vision,2006,69(1):145-156.
[68] PEYR G,PECHAUD M,KERIVEN R,et al.Geodesic Me-thods in Computer Vision and Graphics[J].Foundations & Trends in Computer Graphics & Vision,2010,5(3/4):197-397.
[69] FU Y,ZHOU B.Direct sampling on surfaces for high quality remeshing[C]∥Proceedings of the 2008 ACM Symposium on Solid and Physical Modeling.ACM,2008:115-124.
[70] FU Y,ZHOU B.Direct sampling on surfaces for high qualityremeshing[J].Computer Aided Geometric Design,2009,26(6):711-723.
[71] SURAZHSKY V,SURAZHSKY T,KiIRSANOV D,et al.Fast exact and approximate geodesics on meshes[J].ACM Transactions on Graphics (TOG),2005,24(3):553-560.
[72] YING X,XIN S Q,HE Y.Parallel Chen-Han (PCH) algorithm for discrete geodesics[J].ACM Transactions on Graphics (TOG),2014,33(1):9.
[73] XU C,WANG T Y,LIU Y J,et al.Fast wavefront propagation (FWP) for computing exact geodesic distances on meshes[J].IEEE Transactions on Visualization and Computer Graphics,2015,21(7):822-834.
[74] WANG X,YING X,LIU Y J,et al.Intrinsic computation of centroidal Voronoi tessellation (CVT) on meshes[J].Computer-Aided Design,2015,58:51-61.
[75] PAN H,CHOI Y K,LIU Y,et al.Robust modeling of constant mean curvature surfaces[J].ACM Transactions on Graphics (TOG),2012,31(4):85.
[76] CHEN Z,CAO J,WANG W.Isotropic surface remeshing using constrained centroidal Delaunay mesh[M].John Wiley & Sons,Inc.2012.
[77] NIVOLIERS V,YAN D M,LVY B.Fitting polynomial surfaces to triangular meshes with voronoi squared distance minimization[J].Engineering with Computers,2014,30(3):289-300.
[78] MULLEN P,MEMARI P,DE GOES F,et al.HOT:Hodge-optimized triangulations[J].ACM Transactions on Graphics (TOG),2011,30(4):103.
[79] DE GOES F,WALLEZ C,HUANG J,et al.Power particles:an incompressible fluid solver based on power diagrams[J].ACM Transactions on Graphics (TOG),2015,34(4):50.
[80] GOES F,MEMARI P,MULLEN P,et al.Weighted triangulations for geometry processing[J].ACM Transactions on Graphi-cs (TOG),2014,33(3):28.
[81] LAGAE A,DUTR P.A comparison of methods for generating Poisson disk distributions[J].Computer Gra-phics Forum,2008,27(1):114-129.
[82] EBEIDA M S,MITCHELL S A,D AVIDSON A A,et al.Efficient and good Delaunay meshes from random points[J].Computer-Aided Design,2011,43(11):1506-1515.
[83] CHEW L P.Guaranteed-quality triangular meshes[R].Cornell University,1989.
[84] YAN D M,WONKA P.Adaptive maximal Poisson-disk sampling on surfaces[C]∥SIGGRAPH Asia 2012 Technical Briefs.ACM,2012:1-4.
[85] YAN D M,WONKA P.Gap processing for adaptive maximal Poisson-disk sampling[J].ACM Transactions on Graphics (TOG),2013,32(5):148.
[86] GUO J,YAN D M,JIA X,et al.Efficient maximal Poisson-disk sampling and remeshing on surfaces[J].Computers & Graphics,2015,46(C):72-79.
[87] YAN D M,GUO J,JIA X,et al.Blue-Noise Remeshing with Farthest Point Optimization[J].Computer Graphics Forum,2014,33(5):167-176.
[88] YAN D M,WALLNER J,WONKA P.Unbiased sampling and meshing of isosurfaces[J].IEEE transactions on Visualization and Computer Graphics,2014,20(11):1579-1589.
[89] BOWERS J,WANG R,WEI L Y,et al.Parallel Poisson disksampling with spectrum analysis on surfaces[J].ACM Transactions on Graphics (TOG),2010,29(6):166.
[90] CORSINI M,CIGNONI P,SCOPIGNO R.Efficient and flexible sampling with blue noise properties of triangular meshes[J].IEEE Transactions on Visualization and Computer Graphics,2012,18(6):914-924.
[91] XU Y,HU R,GOTSMAN C,et al.Blue noise sampling of surfaces[J].Computers & Graphics,2012,36(4):232-240.
[92] CHEN Z,YUAN Z,CHOI Y K,et al.Variational blue noisesampling[J].IEEE Transactions on Visualization and Computer Graphics,2012,18(10):1784-1796.
[93] CHEN J,GE X,WEI L Y,et al.Bilateral blue noise sampling[J].ACM Transactions on Graphics (TOG),2013,32(6):216.
[94] MEDEIROS E,INGRID L,PESCO S,et al.Fast adaptive blue noise on polygonal surfaces[J].Graphical Models,2014,76(1):17-29.
[95] JIANG M,ZHOU Y,WANG R,et al.Blue noise sampling using an sph-based method[J].ACM Transactions on Graphics (TOG),2015,34(6):211.
[96] ZHANG S,GUO J,ZHANG H,et al.Capacity constrained blue-noise sampling on surfaces[J].Computers & Graphics,2016,55(C):44-54.
[97] YAN D M,GUO J W,WANG B,et al.A survey of blue-noise sampling and its applications[J].Journal of Computer Science and Technology,2015,30(3):439-452.
[98] WOJTAN C,THREY N,GROSS M,et al.Deforming meshes that split and merge[J].ACM Transactions on Graphics (TOG),2009,28(3):1-10.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed