×

zbMATH — the first resource for mathematics

27 variants of Tutte’s theorem for plane near-triangulations and an application to periodic spline surface fitting. (English) Zbl 07337223
Summary: The theoretical basis of Floater’s parameterization technique for triangulated surfaces is simultaneously a generalization (to non-barycentric weights) and a specialization (to a plane near-triangulation, which is an embedding of a planar graph with the property that all bounded faces are – possibly curved – triangles) of Tutte’s Spring Embedding Theorem. Extensions of this technique cover surfaces with holes and periodic surfaces. The proofs presented previously need advanced concepts, such as rather involved results from graph theory or the theory of discrete 1-forms and consistent perturbations, or are not directly applicable to the above-mentioned extensions. We present a particularly simple geometric derivation of Tutte’s theorem for plane near-triangulations and various extensions thereof, using solely the Euler formula for planar graphs. In particular, we include the case of meshes possessing a cylindrical topology – which has not yet been addressed explicitly but possesses important applications to periodic spline surface fitting – and we correct a minor inaccuracy in a previous result concerning Floater-type parameterizations for genus-1 meshes.
MSC:
65Dxx Numerical approximation and computational geometry (primarily algorithms)
Software:
CGAL; G+Smo
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aigerman, N.; Lipman, Y., Orbifold Tutte embeddings, ACM Trans. Graph., 34, 190-191 (2015)
[2] Bracco, C.; Giannelli, C.; Großmann, D.; Sestini, A., Adaptive fitting with THB-splines: error analysis and industrial applications, Comput. Aided Geom. Des., 62, 239-252 (2018) · Zbl 06892792
[3] Campen, M.; Shen, H.; Zhou, J.; Zorin, D., Seamless parametrization with arbitrary cones for arbitrary genus, ACM Trans. Graph., 39 (2019)
[4] Deng, C.; Chang, Q.; Hormann, K., Iterative coordinates, Comput. Aided Geom. Des., 79, Article 101861 pp. (2020) · Zbl 07200774
[5] DeRose, T.; Meyer, M., Harmonic Coordinates (2006), Pixar Animation Studios, Pixar Technical Memo 06-02
[6] Floater, M., Parametrization and smooth approximation of surface triangulations, Comput. Aided Geom. Des., 14, 231-250 (1997) · Zbl 0906.68162
[7] Floater, M., One-to-one piecewise linear mappings over triangulations, Math. Comput., 72, 685-696 (2003) · Zbl 1014.65128
[8] Floater, M.; Hormann, K., Surface parameterization: a tutorial and survey, (Advances in Multiresolution for Geometric Modelling (2005), Springer), 157-186 · Zbl 1065.65030
[9] Floater, M. S.; Pham-Trong, V., Convex combination maps over triangulations, tilings, and tetrahedral meshes, Adv. Comput. Math., 25, 347-356 (2006) · Zbl 1101.05028
[10] Gortler, S. J.; Gotsman, C.; Thurston, D., Discrete one-forms on meshes and applications to 3D mesh parameterization, Comput. Aided Geom. Des., 23, 83-112 (2006) · Zbl 1088.65015
[11] Gotsman, C.; Gu, X.; Sheffer, A., Fundamentals of spherical parameterization for 3D meshes, ACM Trans. Graph., 22, 358-363 (2003)
[12] Gu, X.; Yau, S. T., Global conformal surface parameterization, (Proc. Symposium on Geometry Processing, Eurographics (2003)), 127-137
[13] Hochberg, R.; McDiarmid, C.; Saks, M., On the bandwidth of triangulated triangles, Discrete Math., 138, 261-265 (1995) · Zbl 0823.05048
[14] Hoschek, J.; Lasser, D., Fundamentals of Computer Aided Geometric Design (1993), AK Peters · Zbl 0788.68002
[15] Jiang, Z.; Schneider, T.; Zorin, D.; Panozzo, D., Bijective projection in a shell, ACM Trans. Graph., 39, Article 247 pp. (2020)
[16] Jüttler, B.; Langer, U.; Mantzaflaris, A.; Moore, S. E.; Zulehner, W., Geometry + simulation modules: implementing isogeometric analysis, Proc. Appl. Math. Mech., 14, 961-962 (2014)
[17] Richter-Gebert, J., Realization Spaces of Polytopes, Lecture Notes in Math., vol. 1643 (1996), Springer: Springer Berlin Heidelberg · Zbl 0866.52009
[18] Saboret, L.; Alliez, P.; Lévy, B.; Rouxel-Labbé, M.; Fabri, A., Triangulated surface mesh parameterization, CGAL User and Reference Manual 4.14 Edition (2019), CGAL Editorial Board
[19] Shivakumar, P.; Chew, K. H., A sufficient condition for nonvanishing of determinants, Proc. Am. Math. Soc., 43, 63-66 (1974) · Zbl 0262.15008
[20] Taussky, O., A recurring theorem on determinants, Am. Math. Mon., 56, 672-676 (1949) · Zbl 0036.01301
[21] Tong, Y.; Alliez, P.; Cohen-Steiner, D.; Desbrun, M., Designing quadrangulations with discrete harmonic forms, (Sheffer, A.; Polthier, K., Symposium on Geometry Processing, Eurographics (2006)), 201-210
[22] Tutte, W. T., How to draw a graph, Proc. Lond. Math. Soc., 3, 743-767 (1963) · Zbl 0115.40805
[23] Vaitkus, M.; Várady, T., Parameterizing and extending trimmed regions for tensor-product surface fitting, Comput. Aided Des., 104, 125-140 (2018)
[24] Weiss, V.; Andor, L.; Renner, G.; Várady, T., Advanced surface fitting techniques, Comput. Aided Geom. Des., 19, 19-42 (2002) · Zbl 0984.68166
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.