“TriWild: robust triangulation with curve constraints” by Hu, Schneider, Gao, Zhou, Jacobson, et al. …
Conference:
Type:
Title:
- TriWild: robust triangulation with curve constraints
Session/Category Title: Meshing
Presenter(s)/Author(s):
Abstract:
We propose a robust 2D meshing algorithm, TriWild, to generate curved triangles reproducing smooth feature curves, leading to coarse meshes designed to match the simulation requirements necessary by applications and avoiding the geometrical errors introduced by linear meshes. The robustness and effectiveness of our technique are demonstrated by batch processing an SVG collection of 20k images, and by comparing our results against state of the art linear and curvilinear meshing algorithms. We demonstrate for our algorithm the practical utility of computing diffusion curves, fluid simulations, elastic deformations, and shape inflation on complex 2D geometries.
References:
1. 2015 Nektar++: An open-source spectral/hp element framework. Computer Physics Communications 192 (2015), 205 — 219.Google ScholarCross Ref
2. 2018 Curvilinear mesh generation using a variational framework. Computer-Aided Design 103 (2018), 73 — 91. 25th International Meshing Roundtable Special Issue: Advances in Mesh Generation.Google ScholarCross Ref
3. Abaqus. 2018. Abaqus. http://www.feasol.comGoogle Scholar
4. Remi Abgrall, Cécile Dobrzynski, and Algiane Froehly. 2012. A method for computing curved 2D and 3D meshes via the linear elasticity analogy: preliminary results. Research Report RR-8061. INRIA. 15 pages. https://hal.inria.fr/hal-00728850Google Scholar
5. R. Abgrall, C. Dobrzynski, and A. Froehly. 2014. A method for computing curved meshes via the linear elasticity analogy, application to fluid dynamics problems. International Journal for Numerical Methods in Fluids 76, 4 (2014), 246–266.Google ScholarCross Ref
6. Pierre Alliez, David Cohen-Steiner, Mariette Yvinec, and Mathieu Desbrun. 2005. Variational Tetrahedral Meshing. ACM Trans. Graph. 24, 3 (July 2005), 617–625. Google ScholarDigital Library
7. Ansys. 2018. Ansys. https://www.ansys.comGoogle Scholar
8. Franz Aurenhammer. 1991. Voronoi Diagrams-a Survey of a Fundamental Geometric Data Structure. ACM Comput. Surv. 23, 3 (Sept. 1991), 345–405. Google ScholarDigital Library
9. Franz Aurenhammer, Rolf Klein, and Der-Tsai Lee. 2013. Voronoi Diagrams and Delaunay Triangulations. WORLD SCIENTIFIC. Google ScholarDigital Library
10. I. Babuška and B.Q. Guo. 1992. The h, p and h-p version of the finite element method; basis theory and applications. Advances in Engineering Software 15, 3 (1992), 159 — 174. Google ScholarDigital Library
11. I. Babuška and B. Q. Guo. 1988. The h-p Version of the Finite Element Method for Domains with Curved Boundaries. SIAM J. Numer. Anal. 25, 4 (1988), 837–861. http://www.jstor.org/stable/2157607Google ScholarCross Ref
12. Brenda S. Baker, Eric Grosse, and Conor S. Rafferty. 1988. Nonobtuse triangulation of polygons. Discrete & Computational Geometry 3, 2 (01 Jun 1988), 147–168. Google ScholarDigital Library
13. Adam W. Bargteil and Elaine Cohen. 2014. Animation of Deformable Bodies with Quadratic Bézier Finite Elements. ACM Trans. Graph. 33, 3, Article 27 (June 2014), 10 pages. Google ScholarDigital Library
14. F. Bassi and S. Rebay. 1997. High-Order Accurate Discontinuous Finite Element Solution of the 2D Euler Equations. J. Comput. Phys. 138, 2 (1997), 251 — 285. Google ScholarDigital Library
15. Mark W Beall, Joe Walsh, and Mark S Shephard. 2003. Accessing CAD Geometry for Mesh Generation. In Proceedings of the 12th International Meshing Roundtable. 33–42.Google Scholar
16. Marshall Bern, David Eppstein, and John Gilbert. 1994. Provably good mesh generation. J. Comput. System Sci. 48, 3 (1994), 384–409. Google ScholarDigital Library
17. Fleurianne Bertrand, Steffen Munzenmaier, and Gerhard Starke. 2014a. First-order System Least Squares on Curved Boundaries: Higher-order Raviart-Thomas Elements. SIAM J. Numer. Anal. 52, 6 (2014), 3165–3180.Google ScholarCross Ref
18. Fleurianne Bertrand, Steffen Munzenmaier, and Gerhard Starke. 2014b. First-Order System Least Squares on Curved Boundaries: Lowest-Order Raviart-Thomas Elements. SIAM J. Numer. Anal. 52, 2 (2014), 880–894.Google ScholarCross Ref
19. Christopher J. Bishop. 2016. Nonobtuse Triangulations of PSLGs. Discrete & Computational Geometry 56, 1 (2016). Google ScholarDigital Library
20. Jean-Daniel Boissonnat, Olivier Devillers, Sylvain Pion, Monique Teillaud, and Mariette Yvinec. 2002. Triangulations in CGAL. Computational Geometry 22 (2002), 5–19. Google ScholarDigital Library
21. Simon Boyé, Pascal Barla, and Gaël Guennebaud. 2012. A Vectorial Solver for Free-form Vector Gradients. ACM Trans. Graph. 31, 6, Article 173 (Nov. 2012), 9 pages. Google ScholarDigital Library
22. Dietrich Braess. 2007. Finite Elements (third ed.). Cambridge University Press. Cambridge Books Online.Google Scholar
23. Oscar P Bruno and Matthew M Pohlman. 2003. High order surface representation. Topics in Computational Wave Propagation, Direct and Inverse Problems (2003).Google Scholar
24. Oleksiy Busaryev, Tamal K. Dey, and Joshua A. Levine. 2009. Repairing and Meshing Imperfect Shapes with Delaunay Refinement. In 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling (SPM ’09). ACM, New York, NY, USA, 25–33. Google ScholarDigital Library
25. S. A. Canann, S. N. Muthukrishnan, and R. K. Phillips. 1996. Topological refinement procedures for triangular finite element meshes. Engineering with Computers 12, 3 (01 Sep 1996), 243–255.Google Scholar
26. Scott A. Canann, Michael B. Stephenson, and Ted Blacker. 1993. Optismoothing: An optimization-driven approach to mesh smoothing. Finite Elements in Analysis and Design 13, 2 (1993), 185 — 190. Google ScholarDigital Library
27. David Cardoze, Alexandre Cunha, Gary L. Miller, Todd Phillips, and Noel Walkington. 2004. A Bézier-based Approach to Unstructured Moving Meshes. In Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG ’04). ACM, New York, NY, USA, 310–319. Google ScholarDigital Library
28. Long Chen and Jin-chao Xu. 2004. Optimal delaunay triangulations. Journal of Computational Mathematics (2004), 299–308.Google Scholar
29. Siu-Wing Cheng, Tamal K. Dey, and Jonathan Shewchuk. 2012. Delaunay Mesh Generation.Google Scholar
30. Philippe G Ciarlet and P-A Raviart. 1972. Interpolation theory over curved elements, with applications to finite element methods. Comput. Meth. Appl. Mech. Eng. 1, 2 (1972), 217–249.Google ScholarCross Ref
31. Saikat Dey, Robert M. O’Bara, and Mark S. Shephard. 1999. Curvilinear Mesh Generation In 3D. In IMR. John Wiley & Sons, 407–417.Google Scholar
32. Cecile Dobrzynski and Ghina El Jannoun. 2017. High order mesh untangling for complex curved geometries. Research Report RR-9120. INRIA Bordeaux, équipe CARDAMOM. https://hal.inria.fr/hal-01632388Google Scholar
33. Luke Engvall and John A. Evans. 2017. Isogeometric unstructured tetrahedral and mixed-element Bernstein-Bézier discretizations. Computer Methods in Applied Mechanics and Engineering 319 (2017), 83 — 123.Google ScholarCross Ref
34. Luke Engvall and John A. Evans. 2018. Mesh Quality Metrics for Isogeometric Bernstein-Bézier Discretizations. arXiv:1810.06975 (2018).Google Scholar
35. Leman Feng, Pierre Alliez, Laurent Busé, Hervé Delingette, and Mathieu Desbrun. 2018. Curved Optimal Delaunay Triangulation. ACM Trans. Graph. 37, 4 (2018). Google ScholarDigital Library
36. C. O. Frederick, Y. C. Wong, and F. W. Edge. 1970. Two-dimensional automatic mesh generation for structural analysis. Internat. J. Numer. Methods Engrg. 2, 1 (1970), 133–144.Google ScholarCross Ref
37. Xiao-Ming Fu, Yang Liu, and Baining Guo. 2015. Computing Locally Injective Mappings by Advanced MIPS. ACM Trans. Graph. 34, 4, Article 71 (July 2015), 12 pages. Google ScholarDigital Library
38. Abel Gargallo Peiró, Francisco Javier Roca Navarro, Jaume Peraire Guitart, and Josep Sarrate Ramos. 2013. High-order mesh generation on CAD geometries. In Adaptive Modeling and Simulation 2013. Centre Internacional de Mètodes Numèrics en Enginyeria (CIMNE), 301–312.Google Scholar
39. John Alan George. 1971. Computer Implementation of the Finite Element Method. Ph.D. Dissertation. Stanford, CA, USA. AAI7205916.Google Scholar
40. P.L. George and H. Borouchaki. 2012. Construction of tetrahedral meshes of degree two. Internat. J. Numer. Methods Engrg. 90, 9 (2012), 1156–1182.Google ScholarCross Ref
41. Christophe Geuzaine, Amaury Johnen, Jonathan Lambrechts, Jean-François Remacle, and Thomas Toulorge. 2015. The Generation of Valid Curvilinear Meshes. Springer International Publishing, Cham, 15–39.Google Scholar
42. Christophe Geuzaine and Jean-François Remacle. 2009. Gmsh: A 3-D finite element mesh generator with built-in pre- and post-processing facilities. Internat. J. Numer. Methods Engrg. 79, 11 (2009), 1309–1331.Google ScholarCross Ref
43. Arash Ghasemi, Lafayette K. Taylor, and James C. Newman, III. 2016. Massively Parallel Curved Spectral/Finite Element Mesh Generation of Industrial CAD Geometries in Two and Three Dimensions. Fluids Engineering Division Summer Meeting 50299 (2016).Google Scholar
44. Michael T Goodrich, Leonidas J Guibas, John Hershberger, and Paul J Tanenbaum. 1997. Snap rounding line segments efficiently in two and three dimensions. In Proceedings of the thirteenth annual symposium on Computational geometry. ACM, 284–293. Google ScholarDigital Library
45. Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3.Google Scholar
46. Yixin Hu, Qingnan Zhou, Xifeng Gao, Alec Jacobson, Denis Zorin, and Daniele Panozzo. 2018. Tetrahedral Meshing in the Wild. ACM Trans. Graph. 37, 4, Article 60 (July 2018), 14 pages. Google ScholarDigital Library
47. Thomas JR Hughes, John A Cottrell, and Yuri Bazilevs. 2005. Isogeometric analysis: CAD, finite elements, NURBS, exact geometry and mesh refinement. Comput. Meth. Appl. Mech. Eng. 194, 39 (2005), 4135–4195.Google ScholarCross Ref
48. Amaury Johnen, Jean François Remacle, and Christophe A. Geuzaine. 2013. Geometrical validity of curvilinear finite elements. J. Comput. Phys. 233 (2013), 359 — 372. Google ScholarDigital Library
49. Pushkar Joshi and Nathan A. Carr. 2008. Repoussé: Automatic Inflation of 2D Artwork. In Proceedings of the Fifth Eurographics Conference on Sketch-Based Interfaces and Modeling (SBM’08). Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 49–55. Google ScholarDigital Library
50. Steve L. Karman, J T. Erwin, Ryan S. Glasby, and Douglas Stefanski. 2016. High-Order Mesh Curving Using WCN Mesh Optimization. In 46th AIAA Fluid Dynamics Conference, AIAA AVIATION Forum.Google Scholar
51. Patrick M. Knupp. 2000. Achieving finite element mesh quality via optimization of the Jacobian matrix norm and associated quantities. Part II, A framework for volume mesh optimization and the condition number of the Jacobian matrix. Internat. J. Numer. Methods Engrg. 48, 8 (2000), 1165–1185. <1165::AID-NME940>3.0.CO;2-YGoogle ScholarCross Ref
52. Yaron Lipman. 2012. Bounded Distortion Mapping Spaces for Triangular Meshes. ACM Trans. Graph. 31, 4 (2012). Google ScholarDigital Library
53. Qiukai Lu, Mark S. Shephard, Saurabh Tendulkar, and Mark W. Beall. 2013. Parallel Curved Mesh Adaptation for Large Scale High-Order Finite Element Simulations. In Proceedings of the 21st International Meshing Roundtable, Xiangmin Jiao and Jean-Christophe Weill (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 419–436.Google Scholar
54. Xiaojuan Luo, Mark S Shephard, and Jean-Francois Remacle. 2001. The influence of geometric approximation on the accuracy of high order methods. Rensselaer SCOREC report 1 (2001).Google Scholar
55. Xiaojuan Luo, Mark S. Shephard, Jean-François Remacle, Robert M. O’Bara, Mark W. Beall, Barna A. Szabó, and Ricardo Actis. 2002. p-Version Mesh Generation Issues. In IMR.Google Scholar
56. Richard H. MacNeal. 1949. The solution of partial differential equations by means of electrical networks. Ph.D. Dissertation. CalTech.Google Scholar
57. Manish Mandad, David Cohen-Steiner, and Pierre Alliez. 2015. Isotopic Approximation Within a Tolerance Volume. ACM Trans. Graph. 34, 4, Article 64 (July 2015), 12 pages. Google ScholarDigital Library
58. MATLAB Partial Differential Equation Toolbox 2018. MATLAB Partial Differential Equation Toolbox. The MathWorks, Natick, MA, USA.Google Scholar
59. Johannes Mezger, Bernhard Thomaszewski, Simon Pabst, and Wolfgang Straśer. 2009. Interactive physically-based shape editing. Computer Aided Geometric Design 26, 6 (2009), 680 — 694. Solid and Physical Modeling 2008. Google ScholarDigital Library
60. P. Monk. 1987. A Mixed Finite Element Method for the Biharmonic Equation. SIAM J. Numer. Anal. 24, 4 (1987), 737–749. Google ScholarDigital Library
61. D. Moxey, D. Ekelschot, Ü. Keskin, S.J. Sherwin, and J. Peiró. 2016. High-order curvilinear meshing using a thermo-elastic analogy. Computer-Aided Design 72 (2016), 130–139. 23rd International Meshing Roundtable Special Issue: Advances in Mesh Generation. Google ScholarDigital Library
62. J. Tinsley Oden. 1994. Optimal h-p finite element methods. Computer Methods in Applied Mechanics and Engineering 112, 1 (1994), 309 — 331.Google ScholarCross Ref
63. Alexandrina Orzan, Adrien Bousseau, Holger Winnemöller, Pascal Barla, Joëlle Thollot, and David Salesin. 2008. Diffusion Curves: A Vector Representation for Smooth-Shaded Images. In ACM Transactions on Graphics (Proceedings of SIGGRAPH 2008), Vol. 27. http://maverick.inria.fr/Publications/2008/OBWBTS08 Google ScholarDigital Library
64. Magdalini Panagiotakopoulou, Martin Bergert, Anna Taubenberger, Jochen Guck, Dimos Poulikakos, and Aldo Ferrari. 2016. A Nanoprinted Model of Interstitial Cancer Migration Reveals a Link between Cell Deformability and Proliferation. ACS Nano 10, 7 (2016), 6437–6448. PMID: 27268411.Google ScholarCross Ref
65. Joaquim Peiró, Spencer J. Sherwin, and Sergio Giordana. 2008. Automatic reconstruction of a patient-specific high-order surface representation and its application to mesh generation for CFD calculations. Medical & Biological Engineering & Computing 46, 11 (01 Nov 2008), 1069–1083.Google Scholar
66. J. Peraire, M. Vahdati, K Morgan, and O. C. Zienkiewicz. 1987. Adaptive Remeshing for Compressible Flow Computations. J. Comput. Phys. 72, 2 (Oct. 1987), 449–466. Google ScholarDigital Library
67. Per-Olof Persson and Jaime Peraire. 2009. Curved Mesh Generation and Mesh Refinement using Lagrangian Solid Mechanics. In 47th AIAA Aerospace Sciences Meeting including The New Horizons Forum and Aerospace Exposition.Google ScholarCross Ref
68. Roman Poya, Ruben Sevilla, and Antonio J. Gil. 2016. A unified approach for a posteriori high-order curved mesh generation using solid mechanics. Computational Mechanics 58, 3 (01 Sep 2016), 457–490. Google ScholarDigital Library
69. Michael Rabinovich, Roi Poranne, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Scalable Locally Injective Mappings. ACM Trans. Graph. 36, 2, Article 37a (April 2017). Google ScholarDigital Library
70. Xevi Roca, Abel Gargallo-Peiró, and Josep Sarrate. 2012. Defining Quality Measures for High-Order Planar Triangles and Curved Mesh Generation. In Proceedings of the 20th International Meshing Roundtable, William Roshan Quadros (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 365–383.Google Scholar
71. Eloi Ruiz-Gironés, Abel Gargallo-Peiró, Josep Sarrate, and Xevi Roca. 2017. An augmented Lagrangian formulation to impose boundary conditions for distortion based mesh moving and curving. Procedia Engineering 203 (2017), 362 — 374. 26thInternationalMeshingRoundtable, IMR26, 18–21 September 2017, Barcelona, Spain.Google ScholarCross Ref
72. Eloi Ruiz-Gironés, Xevi Roca, and Jose Sarrate. 2016a. High-order mesh curving by distortion minimization with boundary nodes free to slide on a 3D CAD representation. Computer-Aided Design 72 (2016), 52 — 64. 23rd International Meshing Roundtable Special Issue: Advances in Mesh Generation. Google ScholarDigital Library
73. Eloi Ruiz-Gironés, Josep Sarrate, and Xevi Roca. 2016b. Generation of Curved High-order Meshes with Optimal Quality and Geometric Accuracy. Procedia Engineering 163 (2016), 315–327. 25th International Meshing Roundtable.Google ScholarCross Ref
74. Edward A. Sadek. 1980. A scheme for the automatic generation of triangular finite elements. Internat. J. Numer. Methods Engrg. 15, 12 (1980), 1813–1822.Google ScholarCross Ref
75. L Ridgway Scott. 1973. Finite element techniques for curved boundaries. Ph.D. Dissertation. Massachusetts Institute of Technology.Google Scholar
76. Ridgway Scott. 1975. Interpolated boundary conditions in the finite element method. SIAM J. Numer. Anal. 12, 3 (1975), 404–427.Google ScholarDigital Library
77. T.W. Sederberg and T. Nishita. 1990. Curve intersection using Bézier clipping. Computer-Aided Design 22, 9 (1990), 538 — 549. Google ScholarDigital Library
78. Ruben Sevilla, Sonia Fernández-Méndez, and Antonio Huerta. 2011. NURBS-Enhanced Finite Element Method (NEFEM). Arch. Comput. Methods Eng. 18, 4 (2011), 441–484.Google ScholarCross Ref
79. Mark S. Shephard, Joseph E. Flaherty, Kenneth E. Jansen, Xiangrong Li, Xiaojuan Luo, Nicolas Chevaugeon, Jean-François Remacle, Mark W. Beall, and Robert M. O’Bara. 2005. Adaptive mesh generation for curved domains. Applied Numerical Mathematics 52, 2 (2005), 251 — 271. ADAPT ’03: Conference on Adaptive Methods for Partial Differential Equations and Large-Scale Computation. Google ScholarDigital Library
80. SJ Sherwin and J Peiró. 2002. Mesh generation in curvilinear domains using high-order elements. Internat. J. Numer. Methods Engrg. 53, 1 (2002), 207–223.Google ScholarCross Ref
81. J Shewchuk. 2012. Unstructured Mesh Generation. In Combinatorial Scientific Computing.Google Scholar
82. Jonathan Richard Shewchuk. 1996. Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator. In Applied Computational Geometry Towards Geometric Engineering, Ming C. Lin and Dinesh Manocha (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 203–222. Google ScholarDigital Library
83. Jonathan Richard Shewchuk. 1997. Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates. Discrete & Computational Geometry 18, 3 (Oct. 1997), 305–363.Google Scholar
84. Jonathan Richard Shewchuk. 1999. Lecture Notes on Delaunay Mesh Generation. Technical Report.Google Scholar
85. Jonathan Richard Shewchuk. 2002. What is a Good Linear Element? Interpolation, Conditioning, and Quality Measures. In Proceedings of the 11th International Meshing Roundtable, IMR 2002, Ithaca, New York, USA, September 15-18, 2002. 115–126. http://imr.sandia.gov/papers/abstracts/Sh247.htmlGoogle Scholar
86. Mike Stees and Suzanne M. Shontz. 2017. A high-order log barrier-based mesh generation and warping method. Procedia Engineering 203 (2017), 180 — 192. 26th International Meshing Roundtable, IMR26, 18–21 September 2017, Barcelona, Spain.Google ScholarCross Ref
87. Rolf Stenberg. 1984. Analysis of Mixed Finite Element Methods for the Stokes Problem: A Unified Approach. Math. Comp. 42, 165 (1984), 9–23. http://www.jstor.org/stable/2007557Google Scholar
88. Daniel Sýkora, Ladislav Kavan, Martin Čadík, Ondřej Jamriška, Alec Jacobson, Brian Whited, Maryann Simmons, and Olga Sorkine-Hornung. 2014. Ink-and-ray: Bas-relief Meshes for Adding Global Illumination Effects to Hand-drawn Characters. ACM Trans. Graph. 33, 2, Article 16 (April 2014), 15 pages. Google ScholarDigital Library
89. Thomas Toulorge, Christophe Geuzaine, Jean-François Remacle, and Jonathan Lambrechts. 2013. Robust untangling of curvilinear meshes. J. Comput. Phys. 254 (2013), 8 — 26. Google ScholarDigital Library
90. Thomas Toulorge, Jonathan Lambrechts, and Jean-François Remacle. 2016. Optimizing the geometrical accuracy of curvilinear meshes. J. Comput. Phys. 310 (2016), 361 — 380. Google ScholarDigital Library
91. Ron Wein, Eric Berberich, Efi Fogel, Dan Halperin, Michael Hemmer, Oren Salzman, and Baruch Zukerman. 2018. 2D Arrangements. In CGAL User and Reference Manual (4.13 ed.). CGAL Editorial Board. https://doc.cgal.org/4.13/Manual/packages.html#PkgArrangement2SummaryGoogle Scholar
92. Dong Xue, Leszek Demkowicz, et al. 2005. Control of geometry induced error in hp finite element (FE) simulations. I. Evaluation of FE error for curvilinear geometries. Int. J. Numer. Anal. Model 2, 3 (2005), 283–300.Google Scholar
93. M. A. Yerry and M. S. Shephard. 1983. A Modified Quadtree Approach To Finite Element Mesh Generation. IEEE Computer Graphics and Applications 3, 1 (Jan 1983), 39–46. Google ScholarDigital Library
94. V.S. Ziel, H. Bériot, O. Atak, and G. Gabard. 2017. Comparison of 2D boundary curving methods with modal shape functions and a piecewise linear target mesh. Procedia Engineering 203 (2017), 91 — 101. 26th International Meshing Roundtable, IMR26, 18–21 September 2017, Barcelona, Spain.Google ScholarCross Ref
95. Patrick Zulian, Teseo Schneider, Hormann Kai, and Krause Rolf. 2017. Parametric finite elements with bijective mappings. BIT Numerical Mathematics (2017), 1–19.Google Scholar
