Splines for Meshes with Irregularities
The SMAI journal of computational mathematics, Volume S5 (2019) , pp. 161-183.

Splines form an elegant bridge between the continuous real world and the discrete computational world. Their tensor-product form lifts many univariate properties effortlessly to the surfaces, volumes and beyond. Irregularities, where the tensor-structure breaks down, therefore deserve attention – and provide a rich source of mathematical challenges and insights.

This paper reviews and categorizes techniques for splines on meshes with irregularities. Of particular interest are quad-dominant meshes that can have $n\ne 4$ valent interior points and T-junctions where quad-strips end. “Generalized” splines can use quad-dominant meshes as control nets both for modeling geometry and to support engineering analysis without additional meshing.

Published online: 2020-01-29
DOI: https://doi.org/10.5802/smai-jcm.57
Classification: 65N35,  15A15
Keywords: splines, irregular, classification
@article{SMAI-JCM_2019__S5__161_0,
author = {J\"org Peters},
title = {Splines for Meshes with Irregularities},
journal = {The SMAI journal of computational mathematics},
publisher = {Soci\'et\'e de Math\'ematiques Appliqu\'ees et Industrielles},
volume = {S5},
year = {2019},
pages = {161-183},
doi = {10.5802/smai-jcm.57},
language = {en},
url = {smai-jcm.centre-mersenne.org/item/SMAI-JCM_2019__S5__161_0/}
}
Peters, Jörg. Splines for Meshes with Irregularities. The SMAI journal of computational mathematics, Volume S5 (2019) , pp. 161-183. doi : 10.5802/smai-jcm.57. https://smai-jcm.centre-mersenne.org/item/SMAI-JCM_2019__S5__161_0/

[1] Z. Andjelic What is the definition of a class A surface? (https://grabcad.com/questions/what-is-definition-of-class-a-surface, accessed May 2015)

[2] F. T. K. Au; Y. K. Cheung Spline Finite Elements for beam and plate, Computers & Structures, Volume 37 (1990), pp. 717-729

[3] F. T. K. Au; Y. K. Cheung Isoparametric Spline Finite Strip for Plane Structures, Computers & Structures, Volume 48 (1993), pp. 22-32 | Zbl 0779.73081

[4] P. J. Barendrecht IsoGeometric Analysis for Subdivision Surfaces (2013) (Masters thesis)

[5] P. J. Barendrecht; M. Bartoň; J. Kosinka Efficient quadrature rules for subdivision surfaces in isogeometric analysis, Comput. Methods Appl. Mech. Eng., Volume 340 (2018), pp. 1-23 | Article | MR 3845201

[6] K.-P. Beier; Y. Chen Highlight-line algorithm for realtime surface-quality assessment, Comput.-Aided Des., Volume 26 (1994) no. 4, pp. 268-277 | Article | Zbl 0802.65149

[7] T. Belytschko; H. Stolarski; W. K. Liu; N. Carpenter; J. SJ Ong Stress projection for membrane and shear locking in shell finite elements, Comput. Methods Appl. Mech. Eng., Volume 51 (1985) no. 1, pp. 221-258 | Article | MR 822746

[8] D. Bommes; B. Lévy; N. Pietroni; E. Puppo; C. Silva; M. Tarini; D. Zorin State of the Art in Quad Meshing, Eurographics STARS (2012)

[9] V. Braibant; C. Fleury Shape Optimal Design using B-splines, Comput. Methods Appl. Mech. Eng., Volume 44 (1984), pp. 247-267 | Article | Zbl 0525.73104

[10] E. Catmull; J. Clark Recursively generated B-spline surfaces on arbitrary topological meshes, Comput.-Aided Des., Volume 10 (1978), pp. 350-355 | Article

[11] P. Charrot; J. A. Gregory A pentagonal surface patch for computer aided geometric design, Comput. Aided Geom. Des., Volume 1 (1984) no. 1 | Article | Zbl 0568.65007

[12] F. Cirak; M. Ortiz; P. Schröder Subdivision surfaces: a new paradigm for thin-shell finite-element analysis, Int. J. Numer. Meth. Engng., Volume 47 (2000), pp. 2039-2072 | Article | Zbl 0983.74063

[13] CNN Inside VW’s high-tech transparent factory, 2014 (https://edition.cnn.com/2014/10/28/tech/gallery/industrial-art-inside-volkswagens-transparent-factory/index.html)

[14] C. de Boor B-form basics, Geometric Modeling: Algorithms and New Trends (1987), pp. 131-148

[15] T. DeRose; M. Kass; T. Truong Subdivision Surfaces in Character Animation, Proceedings of the ACM Conference on Computer Graphics (SIGGRAPH-98) (1998), pp. 85-94

[16] T. Dokken; T. Lyche; K. F. Pettersen Polynomial splines over locally refined box-partitions, Comput. Aided Geom. Des., Volume 30 (2013) no. 3, pp. 331-356 | Article | MR 3019748 | Zbl 1264.41011

[17] D. Doo; M. Sabin Behaviour of recursive division surfaces near extraordinary points, Comput.-Aided Des., Volume 10 (1978), pp. 356-360 | Article

[18] G. Farin Curves and Surfaces for Computer Aided Geometric Design: A Practical Guide, Academic Press Inc., 1988 | Zbl 0694.68004

[19] Foundation Blender Elephants Dream, http://orange.blender.org, 2006

[20] C. Giannelli; B. Jüttler; H. Speleers THB-splines: The truncated basis for hierarchical splines, Comput. Aided Geom. Des., Volume 29 (2012) no. 7, pp. 485-498 | Article | MR 2925951 | Zbl 1252.65030

[21] C. Gotsma Rolling up our SLEFEs: Reflections on Putting an Academic Rendering Algorithm to Work, 2019 (SIAM/GD 19)

[22] J. A. Gregory Smooth interpolation without twist constraints, Computer Aided Geometric Design (1974), pp. 71-88 | Article

[23] J. A. Gregory; J. M. Hahn Geometric continuity and convex combination patches, Comput. Aided Geom. Des., Volume 4 (1987) no. 1-2, pp. 79-89 | Article | MR 898025 | Zbl 0656.41010

[24] J. A. Gregory; J. M. Hahn A C${}^{2}$ polygonal surface patch, Comput. Aided Geom. Des., Volume 6 (1989) no. 1, pp. 69-75 | Article | MR 983472 | Zbl 0664.65016

[25] J. A. Gregory; J. Zhou Filling polygonal holes with bicubic patches, Comput. Aided Geom. Des., Volume 11 (1994) no. 4, pp. 391-410 | Article | MR 1287496 | Zbl 0805.65019

[26] D. Groisser; J. Peters Matched ${G}^{k}$-constructions always yield ${C}^{k}$-continuous isogeometric elements, Comput. Aided Geom. Des., Volume 34 (2015), pp. 67-72 | Article | MR 3341849 | Zbl 1375.65026

[27] G. J. Hettinga; P. J. Barendrecht; J. Kosinka A Comparison of GPU Tessellation Strategies for Multisided Patches, EG 2018 - Short Papers (2018) | Article

[28] G. J. Hettinga; J. Kosinka Phong Tessellation and PN Polygons for Polygonal Models, EG 2017 - Short Papers (2017) | Article

[29] G. J. Hettinga; J. Kosinka Multisided generalisations of Gregory patches, Comput. Aided Geom. Des., Volume 62 (2018), pp. 166-180 | Article | MR 3802210 | Zbl 06892786

[30] T. J. R. Hughes; J. A. Cottrell; Y. Bazilevs Isogeometric Analysis: CAD, Finite Elements, NURBS, Exact Geometry and Mesh Refinement, Comput. Methods Appl. Mech. Eng., Volume 194 (2005), pp. 4135-4195 | Article | MR 2152382 | Zbl 1151.74419

[31] W. Jakob; M. Tarini; D. Panozzo; O. Sorkine-Hornung Instant field-aligned meshes, ACM Trans. Graph., Volume 34 (2015) no. 6, 189 pages | Article

[32] N. Jaxon; X. Qian Isogeometric analysis on triangulations, Comput.-Aided Des., Volume 46 (2014), pp. 45-57 | Article | MR 3124175

[33] H. Kang; J. Xu; F. Chen; J. Deng A new basis for PHT-splines, Graph. Models, Volume 82 (2015), pp. 149-159 | Article

[34] K. Karčiauskas; A. Myles; J. Peters A ${C}^{2}$ Polar Jet Subdivision, Proceedings of Symposium of Graphics Processing (SGP), June 26-28 2006, Cagliari, Italy (2006), pp. 173-180

[35] K. Karčiauskas; T. Nguyen; J. Peters Generalizing bicubic splines for modelling and IGA with irregular layout, GDSPM 2015 in Salt Lake City, Utah October 12-14 (2015)

[36] K. Karčiauskas; T. Nguyen; J. Peters Generalizing bicubic splines for modelling and IGA with irregular layout, Comput.-Aided Des., Volume 70 (2016), pp. 23-35 | Article

[37] K. Karčiauskas; D. Panozzo; J. Peters T-junctions in spline surfaces, ACM Trans. Graph., Volume 36 (2017) no. 5, pp. 170:1-9 | Article

[38] K. Karčiauskas; J. Peters Quad-net obstacle course (http://www.cise.ufl.edu/research/SurfLab/shape_gallery.shtml, accessed 2017-09-05)

[39] K. Karčiauskas; J. Peters Bicubic polar subdivision, ACM Trans. Graph., Volume 26 (2007) no. 4, 14 pages | Article | Zbl 1118.41004

[40] K. Karčiauskas; J. Peters Concentric Tesselation Maps and Curvature Continuous Guided Surfaces, Comput. Aided Geom. Des., Volume 24 (2007) no. 2, pp. 99-111 | Article | Zbl 1171.65338

[41] K. Karčiauskas; J. Peters Surfaces with Polar Structure, Computing, Volume 79 (2007), pp. 309-315 | Article | MR 2295531 | Zbl 1118.41004

[42] K. Karčiauskas; J. Peters Finite Curvature Continuous Polar Patchworks, IMA Mathematics of Surfaces XIII Conference (2009), pp. 222-234 | Article | Zbl 1258.65017

[43] K. Karčiauskas; J. Peters Lens-shaped surfaces and ${C}^{2}$ subdivision, Computing, Volume 86 (2009) no. 2, pp. 171-183 | Article | MR 2551624 | Zbl 1176.65018

[44] K. Karčiauskas; J. Peters Biquintic ${G}^{2}$ surfaces via functionals, Comput. Aided Geom. Des. (2015), pp. 17-29 | Article | Zbl 1375.65028

[45] K. Karčiauskas; J. Peters Can bi-cubic surfaces be class A?, Comput. Graph. Forum, Volume 34 (2015) no. 5, pp. 229-238 | Article

[46] K. Karčiauskas; J. Peters Improved shape for multi-surface blends, Graph. Models, Volume 8 (2015), pp. 87-98 | Article

[47] K. Karčiauskas; J. Peters Smooth multi-sided blending of biquadratic splines, Computers & Graphics, Volume 46 (2015), pp. 172-185 | Article

[48] K. Karčiauskas; J. Peters Curvature continuous bi-4 constructions for scaffold- and sphere-like surfaces, Comput.-Aided Des., Volume 78 (2016), pp. 48-59 | Article

[49] K. Karčiauskas; J. Peters Minimal bi-6 ${G}^{2}$ completion of bicubic spline surfaces, Comput. Aided Geom. Des., Volume 41 (2016), pp. 10-22 | Article | MR 3452035 | Zbl 1417.65082

[50] K. Karčiauskas; J. Peters Improved shape for refinable surfaces with singularly parameterized irregularities, Comput.-Aided Des., Volume 90 (2017), pp. 191-198 | Article

[51] K. Karčiauskas; J. Peters Refinable ${G}^{1}$ functions on ${G}^{1}$ free-form surfaces, Comput. Aided Geom. Des., Volume 54 (2017), pp. 61-73 | Article | MR 3659404 | Zbl 1366.65024

[52] K. Karčiauskas; J. Peters Fair free-form surfaces that are almost everywhere parametrically ${C}^{2}$, J. Comput. Appl. Math. (2018), pp. 1-10 | Article | Zbl 07006444

[53] K. Karčiauskas; J. Peters Rapidly contracting subdivision yields finite, effectively ${C}^{2}$ surfaces, Computers & Graphics (2018), pp. 1-10 | Article

[54] K. Karčiauskas; J. Peters Refinable bi-quartics for design and analysis, Comput.-Aided Des. (2018), pp. 1-10 | Article

[55] K. Karčiauskas; J. Peters High quality refinable $G$-splines for locally quad-dominant meshes with $T$-gons, Comput. Graph. Forum, Volume 38 (2019) no. 5, pp. 151-161 | Article

[56] K. Karčiauskas; J. Peters Localized G-splines for quad & T-gon meshes, Comput. Aided Geom. Des., Volume 71 (2019), pp. 244-254 | Article | MR 3947702 | Zbl 07137403

[57] K. Karčiauskas; J. Peters Refinable smooth surfaces for locally quad-dominant meshes with T-gons, Computers & Graphics, Volume 82 (2019), pp. 193-202 | Article

[58] K. Karciauskas; J. Peters; U. Reif Shape Characterization of Subdivision Surfaces – Case Studies, Comput. Aided Geom. Des., Volume 21 (2004) no. 6, pp. 601-614 | Article | MR 2071825 | Zbl 1069.65522

[59] P. Kiciak Spline surfaces of arbitrary topology with continuous curvature and optimized shape, Comput.-Aided Des., Volume 45 (2013) no. 2, pp. 154-167 | Article | MR 3041192

[60] R. Kraft Adaptive und linear unabhängige Multilevel B-Splines und ihre Anwendungen (1998) (Ph. D. Thesis) | MR 1641654 | Zbl 0903.68195

[61] K. Li; X. Qian Isogeometric analysis and shape optimization via boundary integral, Comput.-Aided Des., Volume 43 (2011) no. 11, pp. 1427-1437 | Article

[62] C. Loop Second Order Smoothness over Extraordinary Vertices, SGP ’04: Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing (2004), pp. 169-178 | Article

[63] C. Loop; S. Schaefer Approximating Catmull–Clark subdivision surfaces with bicubic patches, ACM Trans. Graph., Volume 27 (2008) no. 1, p. 8:1-8:11 | Article

[64] C. T. Loop; T. D. DeRose A Multisided Generalization of Bézier Surfaces, ACM Trans. Graph., Volume 8 (1989) no. 3, pp. 204-234 | Article | Zbl 0746.68097

[65] C. T. Loop; S. Schaefer ${G}^{2}$ Tensor Product Splines over Extraordinary Vertices, Comput. Graph. Forum, Volume 27 (2008) no. 5, pp. 1373-1382 | Article

[66] C. T. Loop; S. Schaefer; T. Ni; I. Castaño Approximating subdivision surfaces with Gregory patches for hardware tessellation, ACM Trans. Graph., Volume 28 (2009) no. 5

[67] D. Lutterkort; J. Peters Optimized Refinable Enclosures of Multivariate Polynomial Pieces, Comput. Aided Geom. Des., Volume 18 (2002) no. 9, pp. 851-863 | Article | MR 1866817 | Zbl 0984.68164

[68] B. Marussig; T. J. R. Hughes A Review of Trimming in Isogeometric Analysis: Challenges, Data Exchange and Simulation Aspects, Arch. Comput. Methods Eng., Volume 25 (2018) no. 4, pp. 1059-1127 | Article | MR 3867694

[69] A. Myles; K. Karčiauskas; J. Peters Extending Catmull–Clark Subdivision and PCCM with Polar Structures, PG ’07: Proceedings of the 15th Pacific Conference on Computer Graphics and Applications (2007), pp. 313-320 | Article

[70] A. Myles; K. Karčiauskas; J. Peters Pairs of bi-cubic surface constructions supporting polar connectivity, Comput. Aided Geom. Des., Volume 25 (2008) no. 8, pp. 621-630 | Article | MR 2463375 | Zbl 1172.65342

[71] A. Myles; J. Peters Bi-3 ${C}^{2}$ Polar Subdivision, ACM Trans. Graph., Volume 28 (2009) no. 3 | Article

[72] A. Myles; J. Peters ${C}^{2}$ Splines Covering Polar Configurations, Comput.-Aided Des., Volume 43 (2011) no. 11, pp. 1322-1329 | Article

[73] T. Nguyen; K. Karčiauskas; J. Peters A comparative study of several classical, discrete differential and isogeometric methods for solving Poisson’s equation on the disk, Axioms, Volume 3 (2014) no. 2, pp. 280-299 | Article | Zbl 1311.68175

[74] T. Nguyen; K. Karčiauskas; J. Peters ${C}^{1}$ finite elements on non-tensor-product 2d and 3d manifolds, Appl. Math. Comput., Volume 272 (2016) no. 1, pp. 148-158 | Article | MR 3418120 | Zbl 1410.65458

[75] T. Nguyen; J. Peters Refinable ${C}^{1}$ spline elements for irregular quad layout, Comput. Aided Geom. Des., Volume 43 (2016), pp. 123-130 | Article | MR 3478901 | Zbl 1418.65026

[76] S. J. Owen A Survey of Unstructured Mesh Generation Technology, Proceedings of the 7th International Meshing Roundtable, IMR 1998, Dearborn, Michigan, USA, October 26-28, 1998 (1998), pp. 239-267

[77] J. Peters Parametrizing singularly to enclose vertices by a smooth parametric surface, Proceedings of Graphics Interface ’91 (1991), pp. 1-7 | Article

[78] J. Peters Smooth interpolation of a mesh of curves, Computing, Volume 7 (1991), pp. 221-247 | MR 1101064 | Zbl 0726.41011

[79] J. Peters Smooth free-form surfaces over irregular meshes generalizing quadratic splines, Comput. Aided Geom. Des., Volume 10 (1993), pp. 347-361 | Article | MR 1235162 | Zbl 0780.65010

[80] J. Peters PN Quads (2000), p. 1-2 (Technical report)

[81] J. Peters Geometric Continuity, Handbook of Computer Aided Geometric Design (2002), pp. 193-229 | Article

[82] J. Peters On refinable tri-variate ${C}^{1}$ splines for box-complexes including irregular points and irregular edges, Mathematical Foundations of Isogeometric Analysis, Volume 33 (2019), pp. 33-35

[83] J. Peters; K. Karčiauskas An introduction to guided and polar surfacing, Mathematical Methods for Curves and Surfaces. 7th International Conference on Mathematical Methods for Curves and Surfaces (Toensberg, 2008) (Lecture Notes in Computer Science) Volume 5862 (2010), pp. 299-315 | MR 3193324 | Zbl 1274.65049

[84] J. Peters; U. Reif Subdivision Surfaces, Geometry and Computing, Volume 3, Springer, 2008, i+204 pages | MR 2415757 | Zbl 1148.65014

[85] J. Peters; X. Wu On the optimality of piecewise linear max-norm enclosures based on slefes, Curve and surface design: Saint Malo 2002 (Modern Methods in Mathematics) (2003) | Zbl 1043.65042

[86] J. Peters; X. Wu SLEVEs for planar spline curves, Comput. Aided Geom. Des., Volume 21 (2004) no. 6, pp. 615-635 | Article | MR 2071826 | Zbl 1069.41506

[87] Pia R. Pfluger; Marian Neamtu On degenerate surface patches, Numer. Algorithms, Volume 5 (1993) no. 11, pp. 569-575 | Article | MR 1258619 | Zbl 0789.65006

[88] H. Prautzsch Freeform splines, Comput. Aided Geom. Des., Volume 14 (1997) no. 3, pp. 201-206 | Article | MR 1441190 | Zbl 0906.68158

[89] N. Ray; W. C. Li; B. Lévy; A. Sheffer; P. Alliez Periodic Global Parameterization, ACM Trans. Graph., Volume 25 (2006) no. 4, pp. 1460-1485 | Article

[90] U. Reif TURBS—topologically unrestricted rational $B$-splines, Constr. Approx., Volume 14 (1998) no. 1, pp. 57-77 | Article | MR 1486390 | Zbl 0891.65012

[91] M. Sabin Transfinite Surface Interpolation, Mathematics of Surfaces, Volume VI (1996), pp. 517-534

[92] P. Salvi; T. Várady Multi-sided Bézier surfaces over concave polygonal domains, Computers & Graphics, Volume 74 (2018), pp. 56-65 | Article

[93] G. Sangalli; T. Takacs; R. Vazquez Unstructured spline spaces for isogeometric analysis based on spline manifolds, Comput. Aided Geom. Des., Volume 47 (2016), pp. 61-82 | Article | MR 3545983 | Zbl 1418.41011

[94] U. Schramm; W. D. Pilkey The coupling of geometric descriptions and finite elements usin+++g NURBS - A study in shape optimization, Finite Elem. Anal. Des., Volume 340 (1993), pp. 11-34 | Article | Zbl 0801.73074

[95] L. L. Schumaker; M.-J. Lai Spline Functions on Triangulations, Cambridge University Press, 2007, pp. 1-677 | Zbl 1185.41001

[96] T. W. Sederberg; J. Zheng; A. Bakenov; A. Nasri T-splines and T-NURCCs, Proceedings of ACM SIGGRAPH 2003 (2003), pp. 477-484 | Article

[97] K.-L. Shi; J.-H. Yong; L. Tang; J.-G. Sun; J.-C. Paul Polar NURBS Surface with Curvature Continuity, Comput. Graph. Forum, Volume 32 (2013) no. 7, pp. 363-370 | Article

[98] Y. K. Shyy; C. Fleury; K. Izadpanah Shape Optimal Design using higher-order elements, Comput. Methods Appl. Mech. Eng., Volume 71 (1988), pp. 99-116 | Article | Zbl 0658.73064

[99] J. Smith; S. Schaefer Selective Degree Elevation for Multi-Sided Bézier Patches, Comput. Graph. Forum, Volume 34 (2015) no. 2, pp. 609-615 | Article

[100] T. Várady; A. P. Rockwood; P. Salvi Transfinite surface interpolation over irregular n-sided domains, Comput.-Aided Des., Volume 43 (2011) no. 11, pp. 1330-1340 | Article

[101] T. Várady; P. Salvi; G. Karikó A Multi-sided Bézier Patch with a Simple Control Structure, Comput. Graph. Forum, Volume 35 (2016) no. 2, pp. 307-317 | Article

[102] A. Vaxman; M. Campen; O. Diamanti; D. Panozzo; D. Bommes; K. Hildebrandt; M. Ben-Chen Directional Field Synthesis, Design, and Processing, SIGGRAPH ’17: ACM SIGGRAPH 2017 Courses (2016) | Article

[103] A. Vlachos; J. Peters; C. Boyd; Jason L. Mitchell Curved PN Triangles, Symposium on Interactive 3D Graphics (Bi-Annual Conference Series) (2001), pp. 159-166

[104] X. Wang; X. Qian An optimization approach for constructing trivariate B-spline solids, Comput.-Aided Des., Volume 46 (2014), pp. 179-191 | Article | MR 3124188

[105] Wikipedia contributors Class_A_surfaces (http://en.wikipedia.org/wiki/Class_A_surfaces, accessed Jan 2017)

[106] Wikipedia contributors Freeform surface modelling — Wikipedia, The Free Encyclopedia, 2018 (https://en.wikipedia.org/w/index.php?title=Freeform_surface_modelling&oldid=871471382, accessed 2018-12-31)

[107] Y. Yamada Clay Modeling: Techniques for giving three-dimensional form to idea, Nissan Design Center, Kaneko Enterprises, 1997

[108] P. Yang; X. Qian A B-spline-based approach to heterogeneous objects design and analysis, Comput.-Aided Des., Volume 39 (2007) no. 2, pp. 95-111 | Article

[109] X. Ye Curvature continuous interpolation of curve meshes, Comput. Aided Geom. Des., Volume 14 (1997) no. 2, pp. 169-190 | Article | MR 1436753 | Zbl 0906.68154

[110] Y. In Yeo; S. Bhandare; J. Peters Efficient Pixel-accurate Rendering of Animated Curved Surfaces, 8th International Conference on Mathematical Methods for Curves and Surfaces, Oslo June 2012 (Lecture Notes in Computer Science) Volume 8177 (2014), pp. 491-509 | MR 3193286