G1 spline functions for point cloud fitting Marsala, Michelangelo; Mantzaflaris, Angelos; Mourrain, Bernard
Applied mathematics and computation,
01/2024, Letnik:
460
Journal Article
Recenzirano
Odprti dostop
In this work we present a new construction of basis functions that generate the space of geometrically smooth splines on an unstructured quadrilateral mesh. The basis is represented in terms of ...biquintic Bézier polynomials on each quadrilateral face. The gluing along the face boundaries is achieved using quadratic gluing data functions, leading to globally G1–smooth spaces. We analyze the latter space and provide a combinatorial formula for its dimension as well as an explicit basis construction. Moreover, we assess the use of this basis in point cloud fitting problems. To apply G1 least squares fitting, a quadrilateral structure as well as parameters in each quadrilateral is required. Even though the general problem of segmenting and parametrizing point clouds is beyond the focus of the present work, we describe a procedure that produces such a structure as well as patch-local parameters. Our experiments demonstrate the accuracy and smoothness of the obtained reconstructed models in several challenging instances.
•We propose a new construction of G1 smooth basis functions on a quadrangular mesh.•We use quadratic gluing data functions and provide general, closed form solutions to the G1 constraint system returning the coefficients defining the basis functions.•We solved the fitting problem using least square approach in the space spanned by the proposed G1 spline bases defined on the quad mesh.•We show the quality of these basis functions in fitting problems, presenting several numerical experiments.
In this paper a construction of a globally G1 family of Bézier surfaces, defined by smoothing masks approximating the well-known Catmull-Clark (CC) subdivision surface is presented. The resulting ...surface is a collection of Bézier patches, which are biquintic G1 around extraordinary vertices and bicubic elsewhere; the smoothness around regular vertices neighboring EV with even valence will be C1, while it results to be C2 in the other occurrences of regular vertices. Each Bézier point is computed using a locally defined mask around the neighboring mesh vertices. To define G1 conditions, we assign quadratic gluing data around extraordinary vertices that depend solely on their valence and we use degree five patches to satisfy these G1 constraints. We explore the space of possible solutions, considering several projections on the solution space leading to different explicit formulas for the masks. Certain control points are computed by means of degree elevation of the C0 scheme of Loop and Schaefer (2008), while for others, explicit masks are deduced by providing closed-form solutions of the G1 conditions, expressed in terms of the masks. We come up with four different schemes and conduct curvature analysis on an extensive benchmark in order to assert the quality of the resulting surfaces and identify the ones that lead to the best result, both visually and numerically. We demonstrate numerically that the resulting surfaces converge quadratically to the CC limit when the mesh is subdivided.
•We propose geometrically smooth approximation schemes for Catmull-Clark limit surfaces by means of biquintic Bézier patches•We assign quadratic gluing data to the mesh edges and provide general, closed form solutions to the G1 constraint system•We develop explicit masks for the Bézier control points that involve the 2-ring of the mesh vertices.•The resulting surfaces are globally G1 and converge quadratically to the Catmull-Clark limit surface.
In this paper we provide a new method to certify that a nearby polynomial system has a singular isolated root and we compute its multiplicity structure. More precisely, given a polynomial system ...f=(f1,…,fN)∈Cx1,…,xnN, we present a Newton iteration on an extended deflated system that locally converges, under regularity conditions, to a small deformation of f such that this deformed system has an exact singular root. The iteration simultaneously converges to the coordinates of the singular root and the coefficients of the so-called inverse system that describes the multiplicity structure at the root. We use α-theory test to certify the quadratic convergence, and to give bounds on the size of the deformation and on the approximation error. The approach relies on an analysis of the punctual Hilbert scheme, for which we provide a new description. We show in particular that some of its strata can be rationally parametrized and exploit these parametrizations in the certification. We show in numerical experimentation how the approximate inverse system can be computed as a starting point of the Newton iterations and the fast numerical convergence to the singular root with its multiplicity structure, certified by our criteria.
System matrix assembly for isogeometric (i.e., spline-based) discretizations of partial differential equations is more challenging than for classical finite elements, due to the increased polynomial ...degrees and the larger (and hence more overlapping) supports of the basis functions. The global tensor-product structure of the discrete spaces employed in isogeometric analysis can be exploited to accelerate the computations, using sum factorization, precomputed look-up tables, and tensor decomposition. We generalize the third approach by considering partial tensor decompositions. We show that the resulting new method preserves the global discretization error and that its computational complexity compares favorably to the existing approaches. Moreover, the numerical realization simplifies considerably since it relies on standard techniques from numerical linear algebra.
A spline space suitable for Isogeometric Analysis (IgA) on multi-patch domains is presented. Our construction is motivated by emerging requirements in isogeometric simulations. In particular, IgA ...spaces should allow for adaptive mesh refinement and they should guarantee the optimal smoothness of the discretized solution, even across interfaces of adjacent patches.
Given a domain manifold M consisting of individual patches (isomorphic to the unit square or cube) that are glued together along interfaces, we present a construction of multi-patch B-splines defined on them. Their smoothness is enhanced by locally modifying or merging basis functions around the boundary of each patch. The resulting multi-patch B-splines with enhanced smoothness (MPBES) possess the property of local linear independence and form a non-negative partition of unity. Moreover, their span can be characterized as the linear space of all piecewise polynomial functions on the domain manifold that possess certain smoothness properties.
Subsequently, adaptively refined MPBES are obtained by generalizing the construction of truncated hierarchical (TH) B-splines. More precisely, a nested sequence of spaces spanned by MPBES is considered, corresponding to steps of local enrichment. In addition, an inversely nested sequence of subdomains (which are submanifolds of M) is used to specify the local refinement level of functions in these spaces. Finally, truncated hierarchical MPBES are obtained by means of the selection and truncation mechanism of THB-splines. The desired properties of linear independence and convex partition of unity are maintained.
The paper presents several numerical examples which demonstrate potential applications of the new basis in isogeometric analysis.
The global (patch-wise) geometry map, which describes the computational domain, is a new feature in isogeometric analysis. This map has a global tensor structure, inherited from the parametric spline ...geometry representation. The use of this global structure in the discretization of partial differential equations may be regarded as a drawback at first glance, as opposed to the purely local nature of (high-order) classical finite elements. In this work we demonstrate that it is possible to exploit the regularity of this structure and to identify the great potential for the efficient implementation of isogeometric discretizations. First, we formulate tensor-product B-spline bases as well as the corresponding mass and stiffness matrices as tensors in order to reveal their intrinsic structure. Second, we derive an algorithm for the separation of variables in the integrands arising in the discretization. This is possible by means of low rank approximation of the integral kernels. We arrive at a compact, separated representation of the integrals. The separated form implies an expression of Galerkin matrices as Kronecker products of matrix factors with small dimensions. This representation is very appealing, due to the reduction in both memory consumption and computation times. Our benchmarks, performed using the C++ library G+Smo, demonstrate that the use of tensor methods in isogeometric analysis possesses significant advantages.
•We employ tensor decomposition to drastically reduce computation times for Galerkin-based isogeometric analysis.•We introduce a compact Kronecker format of Galerkin matrices which minimizes storage requirements.•We reduce demanding multi-dimensional quadrature operations on tensor-product B-splines to inexpensive one-dimensional operations on univariate B-splines.•Computation cost is proportional to the geometric complexity of the input isogeometric domain.•We control the approximation error and obtain full convergence rates.
Hierarchical B-splines that allow local refinement have become a promising tool for developing adaptive isogeometric methods. Unfortunately, similar to tensor-product B-splines, the computational ...cost required for assembling the system matrices in isogeometric analysis with hierarchical B-splines is also high, particularly if the spline degree is increased. To address this issue, we propose an efficient matrix assembly approach for bivariate hierarchical B-splines based on the previous work (Pan, Jüttler and Giust, 2020). The new algorithm consists of three stages: approximating the integrals by quasi-interpolation, building three compact look-up tables and assembling the matrices via sum-factorization. A detailed analysis shows that the complexity of our method has the order O(Np3) under a mild assumption about mesh admissibility, where N and p denote the number of degrees of freedom and spline degree respectively. Finally, several experimental results are demonstrated to verify the theoretical results and to show the performance of the proposed method.
Local refinement with hierarchical B-spline structures is an active topic of research in the context of geometric modeling and isogeometric analysis. By exploiting a multilevel control structure, we ...show that truncated hierarchical B-spline (THB-spline) representations support interactive modeling tools, while simultaneously providing effective approximation schemes for the manipulation of complex data sets and the solution of partial differential equations via isogeometric analysis. A selection of illustrative 2D and 3D numerical examples demonstrates the potential of the hierarchical framework.
Even though isogeometric analysis has a clear advantage regarding the number of degrees of freedom needed to achieve a certain level of accuracy, the time needed for matrix assembly (by means of ...numerical integration of stiffness or mass matrix entries) constitutes a severe bottleneck in the process. In order to overcome this difficulty, we propose the new approach of Integration by Interpolation and Lookup (IIL). Firstly, applying spline interpolation to the common factors in the occurring integrals approximately transforms them into integrals of piecewise polynomial functions, whose integrands are expressed in tensor-product B-spline form. The common factors represent the influence of the geometry mapping (i.e., the NURBS domain parameterization) and the contributions of possibly non-constant material coefficients. Secondly, these integrals are evaluated exactly using pre-computed look-up tables for integrals of tri-products of univariate B-splines and their derivatives. For the model case of elliptic problems, we perform a theoretical analysis to demonstrate that the IIL method maintains the overall approximation order of the Galerkin discretization, provided that the spline interpolation is sufficiently accurate. Moreover, we provide a comparison of the computational complexity of our method with that of a standard Gauss quadrature method. Finally, we present experimental results to illustrate the performance of the IIL method and to support our theoretical results.
•We propose the new approach of Integration by Interpolation and Lookup (IIL) for matrix assembly in isogeometric analysis.•The IIL method has a firm theoretical basis: Optimal order of convergence is guaranteed by Strang’s Lemma.•The method circumvents the element-wise assembly that is used in classical FEA.•The method reduces the overall number of evaluations to one evaluation per physical element, without sacrificing the convergence rate.
PDF
