Generation of three-dimensional delaunay meshes from weakly structured and inconsistent data

V. A. Garanzha   ; L. N. Kudryavtseva

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 52 (2012) no. 3, pp. 499-520

Résumé

A method is proposed for the generation of three-dimensional tetrahedral meshes from incomplete, weakly structured, and inconsistent data describing a geometric model. The method is based on the construction of a piecewise smooth scalar function defining the body so that its boundary is the zero isosurface of the function. Such implicit description of three-dimensional domains can be defined analytically or can be constructed from a cloud of points, a set of cross sections, or a “soup” of individual vertices, edges, and faces. By applying Boolean operations over domains, simple primitives can be combined with reconstruction results to produce complex geometric models without resorting to specialized software. Sharp edges and conical vertices on the domain boundary are reproduced automatically without using special algorithms. Refs. 42. Figs. 25.

Bibliographie

[1] Frey J.L., George P.L., Mesh generation: applications to finite elements, Herm'es, Paris, 2000 | MR | Zbl

[2] Carey G.F., Computational Grids: generation, adaptation, and solution strategies, Taylor Francis, Levittown, Pennsylvania, 1997 | MR | Zbl

[3] Teng S.-H., Wong S.W., Lee D.T, “2000. Unstructured mesh generation: theory, practice, and perspectives”, Internat. J. Comput. Geometry and Applic., 10:3 (2000), 227–266 | DOI | MR | Zbl

[4] Liseikin V.D., Grid generation methods, Springer, Berlin, Heidelberg, New York, 2010 | MR | Zbl

[5] Medvedev N.N., Metod Voronogo–Delone v issledovanii struktury nekristallicheskikh sistem, izd-vo SO RAN, Novosibirsk, 2000

[6] Edelsbrunner H., Geometry and topology for mesh generation, Cambridge monographs on appl. and comput. math., 6, Cambridge Univ. Press, New York, 2001 | MR

[7] George P.L., Saltel E., ““Ultimate” robustness in meshing an arbitrary polyhedron”, Internat. Ofumer. Meth. Engr., 58 (2003), 1061–1089 | DOI | MR | Zbl

[8] Marcum D.L., Weatherill N.P., “Unstructured grid generation using iterative point insertion and local reconnection”, AIAA Journal, 33:9 (1995), 1619–1625 | DOI | Zbl

[9] Lorensen W.E., Cline H.E., “Marching cubes: a high resolution 3D surface construction algorithm”, Computer Graphics, 21:4 (1987), 163–170 | DOI

[10] Levoy M., Pulli K., Curless V. et al., “The digital michelangelo project: 3D scanning of large statues”, Proc. SIGGRAPH, 2000, 131–144 | DOI

[11] Blum H., “A transformation for extracting new descriptors of shape”, Models Perception of Speech and Visual Form, M.I.T. Press, Cambridge, MA, 1967, 362–380

[12] Amenta N., Bern M., “Surface reconstruction by Voronoi filtering”, Discrete Comput. Geometry, 22:4 (1999), 481–504 | DOI | MR | Zbl

[13] Amenta N., Choi S., Dey T., Leekha N., “A simple algorithm for homeomorphic surface reconstruction”, Proc. 16th Ann. ACM Symp. Comput. Geometry, 2000, 213–222 | MR

[14] Danilov A.A., “Tekhnologiya postroeniya nestrukturirovannykh tetraedralnykh setok”, Zh. vychisl. matem. i matem. fiz., 50:1 (2010), 146–163 | MR | Zbl

[15] Labelle F., Shewchuk J.R., “Isosurface stuffing: fast tetrahedral meshes with good dihedral angles”, ACM Trans. Graphics, 26:3, Special Issue on the Proc. ACM SIGGRAPH 2007, 57 | DOI

[16] Boissonat J.-D., Cohen-Steiner D., Mourrain B. et al., “Meshing of surfaces”, Effective Comput. Geometry for Curves and Surfaces, 2006, 181–229 | DOI

[17] Tournois J., Wormser C., Alliez P., Desbrun M., “Interleaving Delaunay refinement and optimization for practical isotropic tetrahedron mesh generation”, ACM Trans. Graphics, 28:3 (2009), 75:l–75:9 | DOI

[18] Persson P.-O., Strang G., “A simple mesh generator in MATLAB”, SIAM Rev., 46:2 (2004), 329–345 | DOI | MR | Zbl

[19] Belousova L.N., Garanzha V.A., “Sravnenie algoritmov globalnoi optimizatsii raschetnykh setok”, Tr. XIV Mezhdunar. Baikalskoi shkoly-seminara “Metody optimizatsii i ikh prilozheniya”, v. 3, ISEM SO RAN, Irkutsk, Severobaikalsk, 2008, 21–26

[20] Lloyd S.P., “Least squares quantization in PCM”, IEEE Trans. Inform. Theory, 28:2 (1982), 129–137 | DOI | MR | Zbl

[21] Du Q., Wang D., “Tetrahedral mesh generation and optimization based on centroidal Voronoi tessellations”, Internat. J. Numer. Meth. in Engr., 56:9 (2003), 1355–1373 | DOI | MR | Zbl

[22] Alliez P., Cohen-Steiner D., Yvinec M., Desbrun M., “Variational tetrahedral meshing”, ACM Trans. Graphics, 24 (2005), 617–625 | DOI

[23] Belousova L.N., Garanzha V.A., “Postroenie setok Delone v neyavno zadannykh oblastyakh s negladkoi granitsei”, Tr. 51-i nauchnoi konferentsii MFTI “Sovrem. probl. fundamentalnykh i prikl. nauk”. VII. Upravlenie i prikl. matematika, v. 2, 2008, 98–101

[24] Voronoi G.F., “Nouveles applications des parametres continus a la theorie de formes quadratiques”, J. Heine Angew. Math., 134 (1908), 198–287 | Zbl

[25] Voronoi G.F., “Issledovaniya o primitivnykh paralleloedrakh”, Sobr. soch., v. 2, Izd-vo AN USSR, Kiev, 1952, 239–368

[26] Delone B.N., “O pustote sfery”, Izv. AN SSSR, 1934, no. 6, 793–800 | Zbl

[27] Ohtake Y., Belyaev A., Pasko A., “Dynamic mesh optimization for polygonized implicit surfaces with sharp features”, The Visual Computer, 19:2 (2003) | Zbl

[28] Barber C.B., Dobkin D.P., Huhdanpaa H., “The Quickhull algorithm for convex hulls”, ACM Trans. Math. Software, 22:4 (1996), 469–483 | DOI | MR | Zbl

[29] Joe B., “Construction of three-dimensional improved-quality triangulations using local transformations”, SIAM J. Sci. Comput., 16:6 (1995), 1292–1307 | DOI | MR | Zbl

[30] Freitag L., Ollivier-Gooch C., “A comparison of tetrahedral mesh improvement techniques”, Proc. 6th Int. Meshing Roundtable, 1996, 87–100

[31] Garanzha V.A., “Barernyi metod postroeniya kvaziizometrichnykh setok”, Zh. vychisl. matem. i matem. fiz., 40:11 (2000), 1685–1705 | MR | Zbl

[32] Orenstein J.A., “Multidimensional tries used for associative data searching”, Inform. Proc. Lett., 14:4 (1982), 150–157 | DOI

[33] Samet H., The design and analysis of spatial data structures, Addison-Wesley, Reading, 1990

[34] Armijo L., “Minimization of functions having Lipschitz continuous first partial derivatives”, Pacific J. Math., 16:1 (1966), 1–3 | DOI | MR | Zbl

[35] Ivanenko S.A., Charakhchyan A.A., “Krivolineinye setki iz vypuklykh chetyrekhugolnikov”, Zh. vychisl. matem. i matem. fiz., 28:4 (1988), 503–514 | MR

[36] Garanzha V.A., Kaporin I.E., “Regulyarizatsiya barernogo variatsionnogo metoda postroeniya raschetnykh setok”, Zh. vychisl. matem. i matem. fiz., 39:9 (1999), 1489–1503 | MR | Zbl

[37] Shen S., O'Brien J.F., Shewchuk J.R., “Interpolating and approximating implicit surfaces from polygon soup”, Proc. ACM SIGGRAPH, 2004, 8–12 | Zbl

[38] Kansa E.J., “Multiquadrics-a scattered data approximation scheme with applications to computational fluid-dynamics. II. Solutions to parabolic, hyperbolic and elliptic partial differential equations”, Comput. Math. Appl., 19:8-9 (1990), 147–161 | DOI | MR | Zbl

[39] Kansa E.J., Carlson R.C., “Radial basis functions: a class of grid-free, scattered data approximations”, CFD Journal, 3:4 (1995), 479

[40] Powell M.J.D., “Radial basis functions for multivariable interpolation: a review”, Numer. Analysis, Longman Scient. Techn., Harlow, 1987, 223–241 | MR

[41] Beatson R.K., Light W.A., “Fast evaluation of radial basis functions: methods for two-dimensional polyharmonic splines”, IMA J. Numer. Analysis, 17 (1997), 343–372 | DOI | MR | Zbl

[42] Ohtake Y., Belyaev A., Alexa M. et al., “Multi-level partition of unity implicits”, ACM Trans. on Graphics, 22:3 (2003), 463–470 | DOI