We present an efficient, globally G 1 –continuous scheme for extracting Bézier patches from any mesh with valence-four vertices and polygonal faces, that is, the mesh topology that arises in Doo-Sabin subdivision. The Bézier points are given explicitly as local, weighted averages in the vicinity of each vertex of the mesh, yielding bi-quadratic patches in regular regions and bi-quartic or bi-quintic patches in the vicinity of irregular regions. In particular, we first derive simple bi-quadratic averaging masks that produce quadratic patches that join with C 1 continuity in regular regions. In the vicinity of irregular faces, we elevate the degree, then impose certain symmetric gluing data of degree two on the patch interfaces, and compute explicitly masks as solution of the G 1 constraints. The resulting scheme, named G 1 ADS, ensures machine precision adherence to the G 1 conditions, reproduces quadratic C 1 B-splines at the regular regions, and enjoys a minimal number of degree elevated patches in the vicinity of irregular regions. We evaluate the performance of G 1 ADS quantitatively and qualitatively on several challenging benchmarks, in terms of accuracy, curvature and isophote analysis, and we compare with the state-of-the-art method. Our results demonstrate that G 1 ADS is efficient, robust and more accurate, producing high quality surfaces that converge to the respective Doo-Sabin limit surface.

We propose a new paradigm for scattered data fitting with adaptive spline constructions based on the key interplay between parameterization and adaptivity. Specifically, we introduce two novel adaptive fitting schemes that combine moving parameterizations with adaptive spline refinement for highly accurate CAD models reconstruction from real-world scattered point clouds. The first scheme alternates surface fitting and data parameter optimization. The second scheme jointly optimizes the parameters and the surface control points. To combine the proposed fitting methods with adaptive spline constructions, we present a key treatment of boundary points. Industrial examples show that updating the parameterization, within an adaptive spline approximation framework, significantly reduces the number of degrees of freedom needed for a certain accuracy, especially if spline adaptivity is driven by suitably graded hierarchical meshes. The numerical experiments employ THB-splines, thus exploiting the existing CAD integration within the considered industrial setting, nevertheless, any adaptive spline construction can be chosen.

Abstract Surface reconstruction from scattered point clouds is the process of generating surfaces from unstructured data configurations retrieved using an acquisition device such as a laser scanner. Smooth surfaces are possible with the use of spline representations, an established mathematical tool in computer-aided design and related application areas. One key step in the surface reconstruction process is the parameterization of the points, that is, the construction of a proper mapping of the 3D point cloud to a planar domain that preserves surface boundary and interior points. Despite achieving a remarkable progress, existing heuristics for generating a suitable parameterization face challenges related to the accuracy, the robustness with respect to noise, and the computational efficiency of the results. In this work, we propose a boundary-informed dynamic graph convolutional network (BIDGCN) characterized by a novel boundary-informed input layer, with special focus on applications related to adaptive spline approximation of scattered data. The newly introduced layer propagates given boundary information to the interior of the point cloud, in order to let the input data be suitably processed by successive graph convolutional network layers. We apply our BIDGCN model to the problem of parameterizing three-dimensional unstructured data sets over a planar domain. A selection of numerical examples shows the effectiveness of the proposed approach for adaptive spline fitting with (truncated) hierarchical B-spline constructions. In our experiments, improved accuracy is obtained, e.g., from 60% up to 80% for noisy data, while speedups ranging from 4 up to 180 times are observed with respect to classical algorithms. Moreover, our method automatically predicts the local neighborhood graph, leading to much more robust results without the need for delicate free parameter selection.

Modelling nonlinear phenomena in thin rubber shells calls for stretch-based material models, such as the Ogden model which conveniently utilizes eigenvalues of the deformation tensor. Derivation and implementation of such models have been already made in Finite Element Methods. This is, however, still lacking in shell formulations based on Isogeometric Analysis, where higher-order continuity of the spline basis is employed for improved accuracy. This paper fills this gap by presenting formulations of stretch-based material models for isogeometric Kirchhoff–Love shells. We derive general formulations based on explicit treatment in terms of derivatives of the strain energy density functions with respect to principal stretches for (in)compressible material models where determination of eigenvalues as well as the spectral basis transformations is required. Using several numerical benchmarks, we verify our formulations on invariant-based Neo-Hookean and Mooney–Rivlin models and with a stretch-based Ogden model. In addition, the model is applied to simulate collapsing behaviour of a truncated cone and it is used to simulate tension wrinkling of a thin sheet.

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) ∈ C[x1, ..., xn]N, 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.

A fundamental problem in computational algebraic geometry is the computation of the resultant. A central question is when and how to compute it as the determinant of a matrix whose elements are the coefficients of the input polynomials up-to sign. This problem is well understood for unmixed multihomogeneous systems, that is for systems consisting of multihomogeneous polynomials with the same support. However, little is known for mixed systems, that is for systems consisting of polynomials with different supports. We consider the computation of the multihomogeneous resultant of bilinear systems involving two different supports. We present a constructive approach that expresses the resultant as the exact determinant of a Koszul resultant matrix, that is a matrix constructed from maps in the Koszul complex. % We exploit the resultant matrix to propose an algorithm to solve such systems. In the process we extend the classical eigenvalues and eigenvectors criterion to a more general setting. Our extension of the eigenvalues criterion applies to a general class of matrices, including the Sylvester-type and the Koszul-type ones.

We present explicit worst case degree and height bounds for the rational univariate representation of the isolated roots of polynomial systems based on mixed volume. We base our estimations on height bounds of resultants and we consider the case of 0-dimensional, positive dimensional, and parametric polynomial systems.

Optimal resultant formulas have been systematically constructed mostly for unmixed polynomial systems, that is, systems of polynomials which all have the same support. However, such a condition is restrictive, since mixed systems of equations arise frequently in practical problems.

We bound the Boolean complexity of computing isolating hyperboxes for all complex roots of systems of bilinear polynomials. The resultant of such systems admits a family of determinantal Sylvester-type formulas, which we make explicit by means of homological complexes. The computation of the determinant of the resultant matrix is a bottleneck for the overall complexity. We exploit the quasi-Toeplitz structure to reduce the problem to efficient matrix-vector products, corresponding to multivariate polynomial multiplication. For zero-dimensional systems, we arrive at a primitive element and a rational univariate representation of the roots. The overall bit complexity of our probabilistic algorithm is OB(n4 D4 + n2D4 τ), where n is the number of variables, D equals the bilinear Bezout bound, and τ is the maximum coefficient bitsize. Finally, a careful infinitesimal symbolic perturbation of the system allows us to treat degenerate and positive dimensional systems, thus making our algorithms and complexity analysis applicable to the general case.

Constructive methods for matrices of multihomogeneous (or multigraded) resultants for unmixed systems have been studied by Weyman, Zelevinsky, Sturmfels, Dickenstein and Emiris. We generalize these constructions to mixed systems, whose Newton polytopes are scaled copies of one polytope, thus taking a step towards systems with arbitrary supports. First, we specify matrices whose determinant equals the resultant and characterize the systems that admit such formulae. Bézout-type determinantal formulae do not exist, but we describe all possible Sylvester-type and hybrid formulae. We establish tight bounds for all corresponding degree vectors, and specify domains that will surely contain such vectors; the latter are new even for the unmixed case. Second, we make use of multiplication tables and strong duality theory to specify resultant matrices explicitly, for a general scaled system, thus including unmixed systems. The encountered matrices are classified; these include a new type of Sylvester-type matrix as well as Bézout-type matrices, known as partial Bezoutians. Our public-domain Maple implementation includes efficient storage of complexes in memory, and construction of resultant matrices.

We develop a new symbolic-numeric algorithm for the certification of singular isolated points, using their associated local ring structure and certified numerical computations. An improvement of an existing method to compute inverse systems is presented, which avoids redundant computation and reduces the size of the intermediate linear systems to solve. We derive a one-step deflation technique, from the description of the multiplicity structure in terms of differentials. The deflated system can be used in Newton-based iterative schemes with quadratic convergence. Starting from a polynomial system and a sufficiently small neighborhood, we obtain a criterion for the existence and uniqueness of a singular root of a given multiplicity structure, applying a well-chosen symbolic perturbation. Standard verification methods, based e.g. on interval arithmetic and a fixed point theorem, are employed to certify that there exists a unique perturbed system with a singular root in the domain. Applications to topological degree computation and to the analysis of real branches of an implicit curve illustrate the method.

Constructive methods for matrices of multihomogeneous resultants for unmixed systems have been studied in [7, 13, 15]. We generalize these constructions to mixed systems, whose Newton polytopes are scaled copies of one polytope, thus taking a step towards systems with arbitrary supports. First, we specify matrices whose determinant equals the resultant and characterize the systems that admit such formulae. Bézout-type determinantal formulae do not exist, but we describe all possible Sylvester-type and hybrid formulae. We establish tight bounds for the corresponding degree vectors, as well as precise domains where these concentrate; the latter are new even for the unmixed case. Second, we make use of multiplication tables and strong duality theory to specify resultant matrices explicitly, in the general case. The encountered matrices are classified; these include a new type of Sylvester-type matrix as well as Bézout-type matrices, which we call partial Bezoutians. Our public-domain Maple implementation includes efficient storage of complexes in memory, and construction of resultant matrices.