Trilinear mappings appear naturally when performing spatial isogeometric discretizations of degree . Among them, birational mappings are characterized by the property that both the mapping and the associated inverse mapping are rational and thus easy to evaluate. These mappings have recently been analyzed by Busé et al. (2023) . Among other results, the authors provide a classification of these mappings over the field of complex numbers. The parameter lines of trilinear mappings form three two-parameter systems of straight lines, and thus it is promising to analyze these mappings with the tools provided by the field of line geometry, which is a classical branch of higher geometry (Pottmann and Wallner, 2001) . Indeed, in the birational case, the three systems of lines form space-filling line congruences associated with rational mappings that can be used to parameterize certain algebraic surfaces (Jüttler and Rittenschober, 2003) . Moreover, the three systems are closely related, and based on these observations we will present a geometric discussion of the results of Busé et al. (2023) together with a more detailed analysis of the classification over the field of real numbers.

Any star-shaped domain admits a polar parameterization with straight parameter lines originating from a center point in its kernel. Arc-fibrations use circular arcs instead of straight lines; specifically, an arc-fibration is a regular polar parameterization whose parameter lines are circular arcs. The existence of arc-fibrations has been studied recently for domains defined by -smooth boundary curves, and the arc-fibration kernel–the set of points that can serve as centers of an arc-fibration–has arisen in the investigation of arc-fibrations. We extend earlier results in two ways: (1) we generalize arc-fibrations to domains with boundary curves, including arc splines; and (2) we analyze the arc-fibration kernel for arc-spline domains and present an algorithm to compute it, demonstrating its performance on several examples. • Arc-Fibrations of arc-spline domains are introduced and investigated. • The arc-fibration kernel is the set of points that can serve as centers. • Arc-fibration kernels of arc-spline domains are shown to be arc-spline domains. • Algorithm AFKC computes arc-fibration kernels of arc-spline domains.

Finding parameterizations of spatial point data is a fundamental step for surface reconstruction in Computer Aided Geometric Design. Especially the case of unstructured point clouds is challenging and not widely studied. In this work, we show how to parameterize a point cloud by using barycentric coordinates in the parameter domain, with the aim of reproducing the parameterizations provided by quadratic triangular Bézier surfaces. To this end, we train an artificial neural network that predicts suitable barycentric parameters for a fixed number of data points. In a subsequent step we improve the parameterization using non-linear optimization methods. We then use a number of local parameterizations to obtain a global parameterization using a new overdetermined barycentric parameterization approach. We study the behavior of our method numerically in the zero-residual case (i.e., data sampled from quadratic polynomial surfaces) and in the non-zero residual case and observe an improvement of the accuracy in comparison to standard methods. We also compare different approaches for non-linear surface fitting such as tangent distance minimization, squared distance minimization and the Levenberg Marquardt algorithm.

We describe a new de Casteljau–type algorithm for complex rational Bézier curves. After proving that these curves exhibit the maximal possible circularity, we construct their points via a de Casteljau–type algorithm over complex numbers. Consequently, the line segments that correspond to convex linear combinations in affine spaces are replaced by circular arcs. In difference to the algorithm of Sánchez-Reyes (2009), the construction of all the points is governed by (generically complex) roots of the denominator, using one of them for each level. Moreover, one of the bi-polar coordinates is fixed at each level, independently of the parameter value. A rational curve of the complex degree n admits generically n! distinct de Casteljau–type algorithms, corresponding to the different orderings of the denominator's roots.

Unrefinement is a tool that allows to perform faster numerical simulations by controlling the level of precision in the specified area. We introduce an algorithm that creates a coarser geometry from an initial regular geometry, which is represented with respect to THB-splines, so that the coarser geometry approximates the initial geometry with a given level of the precision and is regular. The algorithm is based on the unrefinement of cells of the parameter domain, on which the geometry is defined, thus obtaining the new subdivision of the domain (the new subdomain hierarchy). The algorithm uses local linear projectors and optimization techniques in order to ensure the regularity and the approximation properties.

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.

Polar parameterizations of star-shaped domains are based on the line segments that connect a suitably chosen center point with the points on the domain's boundary. Valid (i.e., regular everywhere except at the center point) polar parameterizations are obtained when choosing a center from the kernel of the domain. Recently, the flexibility of these polar parameterizations has been enhanced by considering so-called arc fibrations (Jüttler et al., 2019), which are polar parameterizations that use circular arcs in order to connect the center with the boundary points. We propose and analyze another generalization of polar parameterizations, which uses parabolic arcs instead of lines or circular arcs. This class of curves is simultaneously simpler (since admitting polynomial parameterizations) and more flexible.

We consider the Euclidean Voronoi diagram for a set of $n$ parallel halflines in 3-space. A relation of this diagram to planar power diagrams is shown, and is used to analyze its geometric and topological properties. Moreover, an easy-to-implement space sweep algorithm is proposed that computes the Voronoi diagram for parallel halflines at logarithmic cost per face. Previously only an approximation algorithm for this problem was known. Our method of construction generalizes to Voronoi diagrams for parallel line segments, and to higher dimensions.

The coefficients of a tensor-product spline surface in R d with m × n control points form a tensor of order 3 and dimension ( m , n , d ) . Motivated by applications in isogeometric analysis we analyze the rank of this tensor. In particular, we propose a new construction for low rank tensor-product spline surfaces from given boundary curves. While the results of this construction are generally not affinely invariant, we propose a simple standardization procedure that guarantees affine invariance for d = 2 . In addition we provide a detailed comparison with existing constructions of spline surfaces from boundary data.

Existing methods for surface quadrangulation cannot ensure accurate alignment with feature or boundary curves and tight control of local element size, which are important requirements in many numerical applications (e.g., FEA). Some methods rely on a prescribed direction field to guide quadrangulation for feature alignment, but such a direction field may conflict with a desired density field, thus making it difficult to control the element size. We propose a new spectral method that achieves both accurate feature curve alignment and tight control of local element size according to a given density field. Specifically, the following three technical contributions are made. First, to make the quadrangulation align accurately with feature curves or surface boundary curves, we introduce novel boundary conditions for wave-like functions that satisfy the Helmholtz equation approximately in the least squares sense. Such functions, called quasi-eigenfunctions , are computed efficiently as the solutions to a variational problem. Second, the mesh element size is effectively controlled by locally modulating the Laplace operator in the Helmholtz equation according to a given density field. Third, to improve robustness, we propose a novel scheme to minimize the vibration difference of the quasi-eigenfunction in two orthogonal directions. It is demonstrated by extensive experiments that our method outperforms previous methods in generating feature-aligned quadrilateral meshes with tight control of local elememt size. We further present some preliminary results to show that our method can be extended to generating hex-dominant volume meshes.

Isogeometric analysis (IGA) is a numerical simulation method which is directly based on the NURBS-based representation of CAD models. It exploits the tensor-product structure of 2- or 3-dimensional NURBS objects to parameterize the physical domain. Hence the physical domain is parameterized with respect to a rectangle or to a cube. Consequently, singularly parameterized NURBS surfaces and NURBS volumes are needed in order to represent non-quadrangular or non-hexahedral domains without splitting, thereby producing a very compact and convenient representation. The Galerkin projection introduces finite-dimensional spaces of test functions in the weak formulation of partial differential equations. In particular, the test functions used in isogeometric analysis are obtained by composing the inverse of the domain parameterization with the NURBS basis functions. In the case of singular parameterizations, however, some of the resulting test functions do not necessarily fulfill the required regularity properties. Consequently, numerical methods for the solution of partial differential equations cannot be applied properly. We discuss the regularity properties of the test functions. For one- and two-dimensional domains we consider several important classes of singularities of NURBS parameterizations. For specific cases we derive additional conditions which guarantee the regularity of the test functions. In addition we present a modification scheme for the discretized function space in case of insufficient regularity. It is also shown how these results can be applied for computational domains in higher dimensions that can be parameterized via sweeping.

We present a new method for constructing [Formula: see text] blending surfaces between an arbitrary number of canal surfaces. The topological relation of the canal surfaces is specified via a convex polyhedron and the design technique is based on a generalization of the medial surface transform. The resulting blend surface consists of trimmed envelopes of one- and two-parameter families of spheres. Blending the medial surface transform instead of the surface itself is shown to be a powerful and elegant approach for blend surface generation. The performance of our approach is demonstrated by several examples.

We present a new method for generating a [Formula: see text]-surface from a triangular network of compatible surface strips. The compatible surface strips are given by a network of polynomial curves with an associated implicitly defined surface, which fulfill certain compatibility conditions. Our construction is based on a new concept, called bubble patches, to represent the single surface patches. The compatible surface strips provide a simple [Formula: see text]-condition between two neighboring bubble patches, which are used to construct surface patches, connected with [Formula: see text]-continuity. For [Formula: see text], we describe the obtained [Formula: see text]-condition in detail. It can be generalized to any [Formula: see text]. The construction of a single surface patch is based on Gordon-Coons interpolation for triangles.Our method is a simple local construction scheme, which works uniformly for vertices of arbitrary valency. The resulting surface is a piecewise rational surface, which interpolates the given network of polynomial curves. Several examples of [Formula: see text], [Formula: see text] and [Formula: see text]-surfaces are presented, which have been generated by using our method. The obtained surfaces are visualized with reflection lines to demonstrate the order of smoothness.

We present a method to approximate the signed distance function of a smooth curve or surface by using polynomial splines over hierarchical T-meshes (PHT splines). In particular, we focus on closed parametric curves in the plane and implicitly defined surfaces in space.

We show how to divide the edge graph of a Voronoi diagram into a tree that corresponds to the medial axis of an (augmented) planar domain. Division into base cases is then possible, which, in the bottom-up phase, can be merged by trivial concatenation. The resulting construction algorithm--similar to Delaunay triangulation methods--is not bisector-based and merely computes dual links between the sites, its atomic steps being inclusion tests for sites in circles. This guarantees computational simplicity and numerical stability. Moreover, no part of the Voronoi diagram, once constructed, has to be discarded again. The algorithm works for polygonal and curved objects as sites and, in particular, for circular arcs which allows its extension to general free-form objects by Voronoi diagram preserving and data saving biarc approximations. The algorithm is randomized, with expected runtime O(n log n) under certain assumptions on the input data. Experiments substantiate an efficient behavior even when these assumptions are not met. Applications to offset computations and motion planning for general objects are described.

We present a new type of oriented bounding surfaces, which is particularly well suited for shortest distance computations. The bounding surfaces are obtained by considering surfaces whose support functions are restrictions of quadratic polynomials to the unit sphere. We show that the common normals of two surfaces of this type - and hence their shortest distance - can be computed by solving a polynomial of degree six. This compares favorably with other existing bounding surfaces, such as quadric surfaces, where the computation of the common normals is known to lead to a polynomial of degree 24.

We describe Gauss-Newton type methods for fitting implicitly defined curves and surfaces to given unorganized data points. The methods can deal with general error functions, such as approximations to the l1or linfinnorm of the vector of residuals. Depending on the definition of the residuals, we distinguish between direct and data-based methods. In addition, we show that these methods can either be seen as (discrete) iterative methods, where an update of the unknown shape parameters is computed in each step, or as continuous evolution processes, that generate a time-dependent family of curves or surfaces, which converges towards the final result. It is shown that the data-based methods - which are less costly, as they work without the need of computing the closest points - can efficiently deal with error functions that are adapted to noisy and uncertain data. In addition, we observe that the interpretation as evolution process allows to deal with the issues of regularization and with additional constraints.

Due to its minimal twist, the rotation minimizing frame (RMF) is widely used in computer graphics, including sweep or blending surface modeling, motion design and control in computer animation and robotics, streamline visualization, and tool path planning in CAD/CAM. We present a novel simple and efficient method for accurate and stable computation of RMF of a curve in 3D. This method, called the double reflection method , uses two reflections to compute each frame from its preceding one to yield a sequence of frames to approximate an exact RMF. The double reflection method has the fourth order global approximation error, thus it is much more accurate than the two currently prevailing methods with the second order approximation error—the projection method by Klok and the rotation method by Bloomenthal, while all these methods have nearly the same per-frame computational cost. Furthermore, the double reflection method is much simpler and faster than using the standard fourth order Runge-Kutta method to integrate the defining ODE of the RMF, though they have the same accuracy. We also investigate further properties and extensions of the double reflection method, and discuss the variational principles in design moving frames with boundary conditions, based on RMF.

Summary form only given. We propose a new method for 3D shape metamorphosis, where the in-between objects are constructed by using T-spline scalar functions. The use of T-spline level sets offers several advantages: First, it is convenient to handle complex topology changes without the need of model parameterization. Second, the constructed objects are smooth (C2 in our case). Third, high quality meshes can be easily obtained by using the marching triangulation method. Fourth, the distribution of the degrees of freedom can be adapted to the geometry of the object. Given one source object and one target object, we firstly find a global coordinate transformation to approximately align the two objects. The T-spline control grid is adoptively generated according to the geometry of the aligned objects, and the initial T-spline level set is found by approximating the signed distance function of the source object. Then we use an evolution process, which is governed by a combination of the signed distance function of the target object and a curvature-dependent speed function, to deform the T-spline level set until it converges to the target shape. Additional intermediate objects are inserted at the beginning/end of the sequence of generated T-spline level sets, by gradually projecting the source/target object to the initial/final T-spline level set. A fully automatic algorithm is developed for the above procedures. Experimental results are presented to demonstrate the effectiveness of our method.

We propose a new method for constructing a piecewise smooth mesh from a set of unorganized data points, which may be non-uniformly sampled, noisy, and even containing holes. The method is based on the construction of an implicit representation of the surface, by using smooth (C2in our case) T-spline scalar functions. We first generate the T- spline control grid, and use an evolution process such that the resulting T-spline level sets capture the topology and outline of the object to be reconstructed. The initial mesh with high quality is obtained from the implicit T-spline function through the marching triangulation method. Then we project each data point to the initial mesh, and get a scalar displacement field. Detailed features will be captured by the displaced mesh. We also propose an additional evolution process, which combines data-driven velocities and feature- preserving bilateral filters, in order to reproduce sharp features.

We study the evolution of T-spline level sets (i.e, implicitly defined T-spline curves and surfaces). The use of T-splines leads to a sparse representation of the geometry and allows for an adaptation to the given data, which can be unorganized points or images. The evolution process is governed by a combination of prescribed, data-driven normal velocities, and additional distance field constraints. By incorporating the distance field constraints we are able to avoid additional branches and singularities of the T-spline level sets without having to use re-initialization steps. Experimental examples are presented to demonstrate the effectiveness of our approach.

We introduce a robustness measure which allows to analyze implicitly defined curves and surfaces with respect to their stability. It can be used to bound the maximal position error, which is introduced by small perturbations of the coefficients of a curve or surface. It is shown that the robustness of an implicitly defined curve or surface can be enhanced by multiplying it with auxiliary factors.

We present a new approach to the modeling and deformation of a human or virtual character's arm and legs. Each limb is represented as a set of ellipsoids of varying size interpolated along a skeleton curve. A base surface is generated by approximating these ellipsoids with a swept ellipse, and the difference between that and the detailed shape of the arm or leg is represented as a displacement map. We demonstrate that the natural bending of arms and legs can be emulated using this approach, and show its effectiveness by articulating the limbs of a scanned human body and those of a virtual character.

We present an algorithm for computing the distance between two free-form surfaces. Using line geometry, the distance computation is reformulated as a simple instance of a surface-surface intersection problem, which leads to low-dimensional root finding in a system of equations. This approach produces an efficient algorithm for computing the distance between two ellipsoids, where the problem is reduced to finding a specific solution in a system of two equations in two variables. Similar algorithms can be designed for computing the distance between an ellipsoid and a simple surface (such as cylinder cone, or torus). In an experimental implementation (on a 500 MHz Windows PC), the distance between two ellipsoids was computed in less than 0.3 msec on average; and the distance between an ellipsoid and a simple convex surface was computed in less than 0.15 msec on average.

The paper proposes a simple approach to the affine motion interpolation problem, where an affine spline motion is generated that interpolates a given sequence of affine keyframes and approximately satisfies rigidity constraints and certain optimization criteria. An affine spline motion is first generated so as to interpolate the given keyframes; after that, it is progressively refined via knot insertion and degree elevation into an optimal affine motion by an iterative optimization procedure.