Optimal Spline Approximation via ℓ0‐Minimization

Splines are part of the standard toolbox for the approximation of functions and curves in ?^d. Still, the problem of finding the spline that best approximates an input function or curve is ill‐posed, since in general this yields a “spline” with an infinite number of segments. The problem can be regularized by adding a penalty term for the number of spline segments. We show how this idea can be formulated as an ?₀‐regularized quadratic problem. This gives us a notion of optimal approximating splines that depend on one parameter, which weights the approximation error against the number of segments. We detail this concept for different types of splines including B‐splines and composite Bézier curves. Based on the latest development in the field of sparse approximation, we devise a solver for the resulting minimization problems and show applications to spline approximation of planar and space curves and to spline conversion of motion capture data.     

A New Class of Guided C2 Subdivision Surfaces Combining Good Shape with Nested Refinement

Converting quadrilateral meshes to smooth manifolds, guided subdivision offers a way to combine the good highlight line distribution of recent G‐spline constructions with the refinability of subdivision surfaces. This avoids the complex refinement of G‐spline constructions and the poor shape of standard subdivision. Guided subdivision can then be used both to generate the surface and hierarchically compute functions on the surface. Specifically, we present a C² subdivision algorithm of polynomial degree bi‐6 and a curvature bounded algorithm of degree bi‐5. We prove that the common eigenstructure of this class of subdivision algorithms is determined by their guide and demonstrate that their eigenspectrum (speed of contraction) can be adjusted without harming the shape. For practical implementation, a finite number of subdivision steps can be completed by a high‐quality cap. Near irregular points this allows leveraging standard polynomial tools both for rendering of the surface and for approximately integrating functions on the surface.     

Scalar multivariate subdivision schemes and box splines

We study scalar d-variate subdivision schemes, with dilation matrix 2I, satisfying the sum rules of order k. Using the results of Möller and Sauer, stated for general expanding dilation matrices, we characterize the structure of the mask symbols of such schemes by showing that they must be linear combinations of shifted box spline generators of some polynomial ideal. The directions of the corresponding box splines are columns of certain unimodular matrices. The ideal is determined by the given order of the sum rules or, equivalently, by the order of the zero conditions.The results presented in this paper open a way to a systematic study of subdivision schemes, since box spline subdivisions turn out to be the building blocks of any reasonable multivariate subdivision scheme.As in the univariate case, the characterization we give is the proper way of matching the smoothness of the box spline building blocks with the order of polynomial reproduction of the corresponding subdivision scheme. However, due to the interaction of the building blocks, convergence and smoothness properties may change, if several convergent schemes are combined.The results are illustrated with several examples.     

Subdivision algorithms for the generation of box spline surfaces

This paper proposes a general approach to subdivision algorithms used in interactive computer aided design for splines which are linear combinations of translates of any box splines. We show how these algorithms can be used for efficient generation of the corresponding spline surfaces. Our results extend several known special cases.     

Subdivision Schemes for Thin Plate Splines

Thin plate splines are a well known entity of geometric design. They are defined as the minimizer of a variational problem whose differential operators approximate a simple notion of bending energy. Therefore, thin plate splines approximate surfaces with minimal bending energy and they are widely considered as the standard "fair" surface model. Such surfaces are desired for many modeling and design applications.
Traditionally, the way to construct such surfaces is to solve the associated variational problem using finite elements or by using analytic solutions based on radial basis functions. This paper presents a novel approach for defining and computing thin plate splines using subdivision methods. We present two methods for the construction of thin plate splines based on subdivision: A globally supported subdivision scheme which exactly minimizes the energy functional as well as a family of strictly local subdivision schemes which only utilize a small, finite number of distinct subdivision rules and approximately solve the variational problem. A tradeoff between the accuracy of the approximation and the locality of the subdivision scheme is used to pick a particular member of this family of subdivision schemes.
Later, we show applications of these approximating subdivision schemes to scattered data interpolation and the design of fair surfaces. In particular we suggest an efficient methodology for finding control points for the local subdivision scheme that will lead to an interpolating limit surface and demonstrate how the schemes can be used for the effective and efficient design of fair surfaces.     

Rational bi‐cubic G2 splines for design with basic shapes

The paper develops a rational bi‐cubic G² (curvature continuous) analogue of the non‐uniform polynomial C² cubic B‐spline paradigm. These rational splines can exactly reproduce parts of multiple basic shapes, such as cyclides and quadrics, in one by default smoothly‐connected structure. The versatility of this new tool for processing exact geometry is illustrated by conceptual design from basic shapes.     

Analyzing a generalized Loop subdivision scheme

In this paper a class of subdivision schemes generalizing the algorithm of Loop is presented. The stencils have the same support as those from the algorithm of Loop, but allow a variety of weights. By varying the weights a class of C ¹ regular subdivision schemes is obtained. This class includes the algorithm of Loop and the midpoint schemes of order one and two for triangular nets. The proof of C ¹ regularity of the limit surface for arbitrary triangular nets is provided for any choice of feasible weights. The purpose of this generalization of the subdivision algorithm of Loop is to demonstrate the capabilities of the applied analysis technique. Since this class includes schemes that do not generalize box spline subdivision, the analysis of the characteristic map is done with a technique that does not need an explicit piecewise polynomial representation. This technique is computationally simple and can be used to analyze classes of subdivision schemes. It extends previously presented techniques based on geometric criteria.     

High quality refinable G‐splines for locally quad‐dominant meshes with T‐gons

Polyhedral modeling and re‐meshing algorithms use T‐junctions to add or remove feature lines in a quadrilateral mesh. In many ways this is akin to adaptive knot insertion in a tensor‐product spline, but differs in that the designer or meshing algorithm does not necessarily protect the consistent combinatorial structure that is required to interpret the resulting quad‐dominant mesh as the control net of a hierarchical spline – and so associate a smooth surface with the mesh as in the popular tensor‐product spline paradigm. While G‐splines for multi‐sided holes or generalized subdivision can, in principle, convert quad‐dominant meshes with T‐junctions into smooth surfaces, they do not preserve the two preferred directions and so cause visible shape artifacts. Only recently have n‐gons with T‐junctions (T‐gons) in unstructured quad‐dominant meshes been recognized as a distinct challenge for generalized splines. This paper makes precise the notion of locally quad‐dominant mesh as quad‐meshes including τ‐nets, i.e. T‐gons surrounded by quads; and presents the first high‐quality G‐spline construction that can use τ‐nets as control nets for spline surfaces suitable, e.g., for automobile outer surfaces. Remarkably, T‐gons can be neighbors, separated by only one quad, both of T‐gons and of points where many quads meet. A τ‐net surface cap consists of 16 polynomial pieces of degree (3,5) and is refinable in a way that is consistent with the surrounding surface. An alternative, everywhere bi‐3 cap is not formally smooth, but achieves the same high‐quality highlight line distribution.     

Retailoring Box Splines to Lattices for Highly Isotropic Volume Representations

3D box splines are defined by convolving a 1D box function with itself along different directions. In volume visualization, box splines are mainly used as reconstruction kernels that are easy to adapt to various sampling lattices, such as the Cartesian Cubic (CC), Body‐Centered Cubic (BCC), and Face‐Centered Cubic (FCC) lattices. The usual way of tailoring a box spline to a specific lattice is to span the box spline by exactly those principal directions that span the lattice itself. However, in this case, the preferred directions of the box spline and the lattice are the same, amplifying the anisotropic effects of each other. This leads to an anisotropic volume representation with strongly preferred directions. Therefore, in this paper, we retailor box splines to lattices such that the sets of vectors that span the box spline and the lattice are disjoint sets. As the preferred directions of the box spline and the lattice compensate each other, a more isotropic volume representation can be achieved. We demonstrate this by comparing different combinations of box splines and lattices concerning their anisotropic behavior in tomographic reconstruction and volume visualization.     

Subdivision Surfaces with Creases and Truncated Multiple Knot Lines

We deal with subdivision schemes based on arbitrary degree B‐splines. We focus on extraordinary knots which exhibit various levels of complexity in terms of both valency and multiplicity of knot lines emanating from such knots. The purpose of truncated multiple knot lines is to model creases which fair out. Our construction supports any degree and any knot line multiplicity and provides a modelling framework familiar to users used to B‐splines and NURBS systems.     

A Method for Constructing Interpolatory Subdivision Schemes and Blending Subdivisions

This paper presents a universal method for constructing interpolatory subdivision schemes from known approximatory subdivisions. The method establishes geometric rules of the associated interpolatory subdivision through addition of further weighted averaging operations to the approximatory subdivision. The paper thus provides a novel approach for designing new interpolatory subdivision schemes. In addition, a family of subdivision surfaces varying from the given approximatory scheme to its associated interpolatory scheme, namely the blending subdivisions, can also be established. Based on the proposed method, variants of several known interpolatory subdivision schemes are constructed. A new interpolatory subdivision scheme is also developed using the same technique. Brief analysis of a family of blending subdivisions associated with the Loop subdivision scheme demonstrates that this particular family of subdivisions are globally C¹ continuous while maintaining bounded curvature for regular meshes. As a further extension of the blending subdivisions, a volume‐preserving subdivision strategy is also proposed in the paper.     

Manifold-valued Thin-Plate Splines with Applications in Computer Graphics

We present a generalization of thin‐plate splines for interpolation and approximation of manifold‐valued data, and demonstrate its usefulness in computer graphics with several applications from different fields. The cornerstone of our theoretical framework is an energy functional for mappings between two Riemannian manifolds which is independent of parametrization and respects the geometry of both manifolds. If the manifolds are Euclidean, the energy functional reduces to the classical thin‐plate spline energy. We show how the resulting optimization problems can be solved efficiently in many cases. Our example applications range from orientation interpolation and motion planning in animation over geometric modelling tasks to color interpolation.     

Can bi‐cubic surfaces be class A?

'Class A surface’ is a term in the automotive design industry, describing spline surfaces with aesthetic, non‐oscillating highlight lines. Tensor‐product B‐splines of degree bi‐3 (bicubic) are routinely used to generate smooth design surfaces and are often the de facto standard for downstream processing. To bridge the gap, this paper explores and gives a concrete suggestion, how to achieve good highlight line distributions for irregular bi‐3 tensor‐product patch layout by allowing, along some seams, a slight mismatch of normals below the industry‐accepted tolerance of one tenth of a degree. Near the irregularities, the solution can be viewed as transforming a higher‐degree, high‐quality formally smooth surface into a bi‐3 spline surface with few pieces, sacrificing formal smoothness but qualitatively retaining the shape.     

Subdivision surfaces for CAD—an overview

Subdivision surfaces refer to a class of modelling schemes that define an object through recursive subdivision starting from an initial control mesh. Similar to B-splines, the final surface is defined by the vertices of the initial control mesh. These surfaces were initially conceived as an extension of splines in modelling objects with a control mesh of arbitrary topology. They exhibit a number of advantages over traditional splines. Today one can find a variety of subdivision schemes for geometric design and graphics applications. This paper provides an overview of subdivision surfaces with a particular emphasis on schemes generalizing splines. Some common issues on subdivision surface modelling are addressed. Several key topics, such as scheme construction, property analysis, parametric evaluation and subdivision surface fitting, are discussed. Some other important topics are also summarized for potential future research and development. Several examples are provided to highlight the modelling capability of subdivision surfaces for CAD applications.     

Least Squares Subdivision Surfaces

The usual approach to design subdivision schemes for curves and surfaces basically consists in combining proper rules for regular configurations, with some specific heuristics to handle extraordinary vertices. In this paper, we introduce an alternative approach, called Least Squares Subdivision Surfaces (LS), where the key idea is to iteratively project each vertex onto a local approximation of the current polygonal mesh. While the resulting procedure haves the same complexity as simpler subdivision schemes, our method offers much higher visual quality, especially in the vicinity of extraordinary vertices. Moreover, we show it can be easily generalized to support boundaries and creases. The fitting procedure allows for a local control of the surface from the normals, making LS³ very well suited for interactive freeform modeling applications. We demonstrate our approach on diadic triangular and quadrangular refinement schemes, though it can be applied to any splitting strategies.     

A class of general quartic spline curves with shape parameters

With a support on four consecutive subintervals, a class of general quartic splines are presented for a non-uniform knot vector. The splines have C² continuity at simple knots and include the cubic non-uniform B-spline as a special case. Based on the given splines, piecewise quartic spline curves with three local shape parameters are given. The given spline curves can be C²∩G³ continuous by fixing some values of the curve?s parameters. Without solving a linear system, the spline curves can also be used to interpolate sets of points with C² continuity. The effects of varying the three shape parameters on the shape of the quartic spline curves are determined and illustrated.     

Hardware-Accelerated, High-Quality Rendering Based on Trivariate Splines Approximating Volume Data

We develop an approach for hardware‐accelerated, high‐quality rendering of volume data using trivariate splines. The proposed quasi‐interpolating schemes are realtime reconstructions. The low total degrees provide several advantages for our GPU implementation. In particular, intersecting rays with spline isosurfaces for direct Phong illumination is performed by simple root finding algorithms (analytic and iterative), while the necessary normals result from blossoming. Since visualizations are on a fragment base, our renderer for isosurfaces includes an automatic level of detail. While we use well‐known spatial data structures in the CPU part of the algorithm for hierarchical view frustum culling and memory reduction, our GPU implementations have to take the highly complex structure of the splines into account. These include an appropriate organization of the data streams, i.e. we develop an advanced encoding scheme for the spline coefficients, as well as an implicit scheme for bounding geometry retrieval. In addition, we propose an elaborated clipping procedure to be performed in the fragment shader. These features essentially reduce bus traffic, memory consumption, and data access on the GPU leading to interactive frame rates for renderings of high visual quality. Compared with pure CPU implementations and existing GPU implementations for trivariate polynomials frame rates increase by factors between 10 and 100.     

Improving the Parameterization of Approximate Subdivision Surfaces

We provide a method for improving the parameterization of patching schemes that approximate Catmull‐Clark subdivision surfaces, such that the new parameterization conforms better to that of the original subdivision surface. We create this reparameterization in real‐time using a method that only depends on the topology of the surface and is independent of the surface's geometry. Our method can handle patches with more than one extraordinary vertex and avoids the combinatorial increase in both complexity and storage associated with multiple extraordinary vertices. Moreover, the reparameterization function is easy to implement and fast.     

A Unified Subdivision Scheme for Polygonal Modeling

Subdivision rules have traditionally been designed to generate smooth surfaces from polygonal meshes. In this paper we propose to employ subdivision rules as a polygonal modeling tool, specifically to add additional level of detail to meshes. However, existing subdivision schemes have several undesirable properties making them ill suited for polygonal modeling. In this paper we propose a general set of subdivision rules which provides users with more control over the subdivision process. Most existing subdivision schemes are special cases. In particular, we provide subdivision rules which blend approximating spline based schemes with interpolatory ones. Also, we generalize subdivision to allow any number of refinements to be performed in a single step.     

A unified subdivision approach for multi-dimensional non-manifold modeling

This paper presents a new unified subdivision scheme that is defined over a k-simplicial complex in n-D space with k≤3. We first present a series of definitions to facilitate topological inquiries during the subdivision process. The scheme is derived from the double (k+1)-directional box splines over k-simplicial domains. Thus, it guarantees a certain level of smoothness in the limit on a regular mesh. The subdivision rules are modified by spatial averaging to guarantee C¹ smoothness near extraordinary cases. Within a single framework, we combine the subdivision rules that can produce 1-, 2-, and 3-manifolds in arbitrary n-D space. Possible solutions for non-manifold regions between the manifolds with different dimensions are suggested as a form of selective subdivision rules according to user preference. We briefly describe the subdivision matrix analysis to ensure a reasonable smoothness across extraordinary topologies, and empirical results support our assumption. In addition, through modifications, we show that the scheme can easily represent objects with singularities, such as cusps, creases, or corners. We further develop local adaptive refinement rules that can achieve level-of-detail control for hierarchical modeling. Our implementation is based on the topological properties of a simplicial domain. Therefore, it is flexible and extendable. We also develop a solid modeling system founded on our subdivision schemes to show potential benefits of our work in industrial design, geometric processing, and other applications.