Quasi-circular Splines: A Shape-Preserving Approximation

The "quasi-circular spline" is introduced as a new method for approximating closed, smooth planar shapes from curvature information. A current application is the measurement of shapes of solid rocket booster cross-sections. Because of the efficiency of the algorithm and its desirable geometric properties, it is also particularly appropriate for computer graphics. The simplicity and efficiency of the quasi-circular spline compare well with previously proposed schemes which are important in graphical applications. It is invariant under the transformations of the Euclidean group. Furthermore, it is shape-preserving in that the quasi-circular spline approximation to a convex planar curve is also convex. Sufficient conditions for convergence are described, and O(h²) approximation to sufficiently smooth curves is demonstrated.     

Approximate General Sweep Boundary of a 2D Curved Object

This paper presents an algorithm to compute an approximation to the general sweep boundary of a 2D curved moving object which changes its shape dynamically while traversing a trajectory. In effect, we make polygonal approximations to the trajectory and to the object shape at every appropriate instance along the trajectory so that the approximated polygonal sweep boundary is within a given error bound ϵ > 0 from the exact sweep boundary. The algorithm interpolates intermediate polygonal shapes between any two consecutive instances, and constructs polygons which approximate the sweep boundary of the object. Previous algorithms on sweep boundary computation have been mainly concerned about moving objects with fixed shapes; nevertheless, they have involved a fair amount of symbolic and/or numerical computations that have limited their practical uses in graphics modeling systems as well as in many other applications which require fast sweep boundary computation. Although the algorithm presented here does not generate the exact sweep boundaries of objects, it does yield quite reasonable polygonal approximations to them, and our experimental results show that its computation is reasonably fast to be of a practical use.     

Medial axis computation for planar free-form shapes

We present a simple, efficient, and stable method for computing—with any desired precision—the medial axis of simply connected planar domains. The domain boundaries are assumed to be given as polynomial spline curves. Our approach combines known results from the field of geometric approximation theory with a new algorithm from the field of computational geometry. Challenging steps are (1) the approximation of the boundary spline such that the medial axis is geometrically stable, and (2) the efficient decomposition of the domain into base cases where the medial axis can be computed directly and exactly. We solve these problems via spiral biarc approximation and a randomized divide & conquer algorithm.     

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.     

Detecting and quantifying envelope singularities in the plane

The mathematical envelopes of families of both rigid and non-rigid moving shapes play a fundamental role in a variety of problems from very diverse application domains, from engineering design and manufacturing to computer graphics and computer assisted surgery. Geometric singularities in these envelopes are known to induce malfunctions or unintended system behavior, and the corresponding theoretical and computational difficulties induced by these singularities are not only massive, but also well documented. We describe a new approach to detect and quantify the envelope singularities induced by 2-dimensional shapes of arbitrary complexity moving according to general non-periodic and non-singular planar affine motions. Our approach, which does not require any envelope computations, is reframing the problem in terms of “fold points” and “fold regions” in the neighborhood of geometric singularities, and we show that the existence of these fold points is a necessary condition for the existence of singularities. We establish a mathematically well defined duality between the 2-dimensional Euclidean space in which the motion takes place and a 2+1 spacetime domain. Based on this duality, we recast the problem of detecting and quantifying geometric singularities into inherently parallel tests against the original geometric representation in the 2-dimensional Euclidean space. We conclude by discussing the significance of our results, and the extension of our approach to 3-dimensional moving shapes.     

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.     

A new measurement for assessing polygonal approximation of curves

This paper presents a novel method for assessing the accuracy of unsupervised polygonal approximation algorithms. This measurement relies on a polygonal approximation called the “reference approximation”. The reference approximation is obtained using the method of Perez and Vidal [11] by an iterative method that optimizes an objective function. Then, the proposed measurement is calculated by comparing the reference approximation with the approximation to be evaluated, taking into account the similarity between the polygonal approximation and the original contour, and penalizing polygonal approximations with an excessive number of points. A comparative experiment by using polygonal approximations obtained with commonly used algorithms showed that the proposed measurement is more efficient than other proposed measurements at comparing polygonal approximations with different number of points.     

Distance functions and skeletal representations of rigid and non-rigid planar shapes

Shape skeletons are fundamental concepts for describing the shape of geometric objects, and have found a variety of applications in a number of areas where geometry plays an important role. Two types of skeletons commonly used in geometric computations are the straight skeleton of a (linear) polygon, and the medial axis of a bounded set of points in the k-dimensional Euclidean space. However, exact computation of these skeletons of even fairly simple planar shapes remains an open problem.In this paper we propose a novel approach to construct exact or approximate (continuous) distance functions and the associated skeletal representations (a skeleton and the corresponding radius function) for solid 2D semi-analytic sets that can be either rigid or undergoing topological deformations. Our approach relies on computing constructive representations of shapes with R-functions that operate on real-valued halfspaces as logic operations. We use our approximate distance functions to define a new type of skeleton, i.e, the C-skeleton, which is piecewise linear for polygonal domains, generalizes naturally to planar and spatial domains with curved boundaries, and has attractive properties. We also show that the exact distance functions allow us to compute the medial axis of any closed, bounded and regular planar domain. Importantly, our approach can generate the medial axis, the straight skeleton, and the C-skeleton of possibly deformable shapes within the same formulation, extends naturally to 3D, and can be used in a variety of applications such as skeleton-based shape editing and adaptive motion planning.     

Error-bounded biarc approximation of planar curves

Presented in this paper is an error-bounded method for approximating a planar parametric curve with a G¹ arc spline made of biarcs. The approximated curve is not restricted in specially bounded shapes of confined degrees, and it does not have to be compatible with non-uniform rational B-splines (NURBS). The main idea of the method is to divide the curve of interest into smaller segments so that each segment can be approximated with a biarc within a specified tolerance. The biarc is obtained by polygonal approximation to the curve segment and single biarc fitting to the polygon. In this process, the Hausdorff distance is used as a criterion for approximation quality. An iterative approach is proposed for fitting an optimized biarc to a given polygon and its two end tangents. The approach is robust and acceptable in computation since the Hausdorff distance between a polygon and its fitted biarc can be computed directly and precisely. The method is simple in concept, provides reasonable accuracy control, and produces the smaller number of biarcs in the resulting arc spline. Some experimental results demonstrate its usefulness and quality.     

Approximation of Geometric Dispersion Problems

We consider problems of distributing a number of points within a polygonal region P , such that the points are ``far away' from each other. Problems of this type have been considered before for the case where the possible locations form a discrete set. Dispersion problems are closely related to packing problems. While Hochbaum and Maass [20] have given a polynomial-time approximation scheme for packing, we show that geometric dispersion problems cannot be approximated arbitrarily well in polynomial time, unless P = NP. A special case of this observation solves an open problem by Rosenkrantz et al. [31]. We give a 2/3 approximation algorithm for one version of the geometric dispersion problem. This algorithm is strongly polynomial in the size of the input, i.e., its running time does not depend on the area of P . We also discuss extensions and open problems. Received October 1, 1998; revised September 17, 1999, and April 17, 2000.     

Persistence Analysis of Multi-scale Planar Structure Graph in Point Clouds

Modern acquisition techniques generate detailed point clouds that sample complex geometries. For instance, we are able to produce millimeter-scale acquisition of whole buildings. Processing and exploring geometrical information within such point clouds requires scalability, robustness to acquisition defects and the ability to model shapes at different scales. In this work, we propose a new representation that enriches point clouds with a multi-scale planar structure graph. We define the graph nodes as regions computed with planar segmentations at increasing scales and the graph edges connect regions that are similar across scales. Connected components of the graph define the planar structures present in the point cloud within a scale interval. For instance, with this information, any point is associated to one or several planar structures existing at different scales. We then use topological data analysis to filter the graph and provide the most prominent planar structures. Our representation naturally encodes a large range of information. We show how to efficiently extract geometrical details (e.g. tiles of a roof), arrangements of simple shapes (e.g. steps and mean ramp of a staircase), and large-scale planar proxies (e.g. walls of a building) and present several interactive tools to visualize, select and reconstruct planar primitives directly from raw point clouds. The effectiveness of our approach is demonstrated by an extensive evaluation on a variety of input data, as well as by comparing against state-of-the-art techniques and by showing applications to polygonal mesh reconstruction.     

Minimal structural perturbations for controllability of a networked system: Complexities and approximations

Link additions/deletions and actuator/sensor failures are common structural perturbations for real networked systems. In this paper, we consider three related problems on determining the minimal cost structural perturbations, including link additions, link deletions, and input deletions to make a networked system structurally controllable/uncontrollable, mainly focusing on their computational complexities and approximations. Formally, given a structured system, it is proven that (i) it is NP‐hard to add the minimal cost of links, including links among state variables (ie, state links) and links from the existing inputs to state variables (ie, input links), from a given set of links to make the system structurally controllable; (ii) it is NP‐hard to determine the minimal cost of links whose deletions deteriorate structural controllability of the system, even when the removable links are restricted in either the input links or the state links. It is also proven that determining the minimal cost of inputs whose deletions cause structural uncontrollability is strongly NP‐hard even with dedicated input structure. Furthermore, some fundamental approximation results for these problems are established. These results may serve an answer to the general hardness and approximability of optimally designing (modifying) a structurally controllable network topology and of measuring controllability robustness against link/input failures. Additionally, several polynomial‐time tractable cases of the aforementioned problems are also identified.     

“Meshsweeper”: dynamic point-to-polygonal mesh distanceand applications

We introduce a new algorithm for computing the distance from a point to an arbitrary polygonal mesh. Our algorithm uses a multiresolution hierarchy of bounding volumes generated by geometric simplification. Our algorithm is dynamic, exploiting coherence between subsequent queries using a priority process and achieving constant time queries in some cases. It can be applied to meshes that transform rigidly or deform nonrigidly. We illustrate our algorithm with a simulation of particle dynamics and collisions with a deformable mesh, the computation of distance maps and offset surfaces, the computation of an approximation to the expensive Hausdorff distance between two shapes, and the detection of self-intersections. We also report comparison results between our algorithm and an alternative algorithm using an octree, upon which our method permits an order-of-magnitude speed-up     

基于曲线和曲面控制的多边形物体变形反走样

基于参数曲线和曲面控制的空间变形是重要的几何外形编辑和柔性物体动画实现手段．当这两类变形方法的对象是多边形物体时,如何对变形物体进行重采样以得到高质量结果,是计算机动画和几何造型领域中的一个重要问题．该文针对B-样条曲线和曲面控制的空间变形方法,提出了面向多边形物体的空间变形反走样方法．在该方法中,利用等距技术将B-样条曲线或曲面所张成的变形空间近似表示为张量积B-样条参数体,结合作者提出的多边形物体精确B-样条自由变形方法,实现了参数曲线和曲面控制的多边形物体变形反走样．     

Fast computation of optimal polygonal approximations of digital planar closed curves

We face the problem of obtaining the optimal polygonal approximation of a digital planar curve. Given an ordered set of points on the Euclidean plane, an efficient method to obtain a polygonal approximation with the minimum number of segments, such that, the distortion error does not excess a threshold, is proposed. We present a novel algorithm to determine the optimal solution for the min-# polygonal approximation problem using the sum of square deviations criterion on closed curves.Our proposal, which is based on Mixed Integer Programming, has been tested using a set of contours of real images, obtaining significant differences in the computation time needed in comparison to the state-of-the-art methods.     

Real Time Fitting of Hand-Sketched Pressure Brushstrokes

A method is described for fitting the outline of hand-sketched pressure brushstrokes with Bézier curves. It combines the brush-trajectory model, in which a stroke is generated by dragging a brush along a given trajectory, with a fast curve fitting algorithm. The method has been implemented for a vector-based drawing program in which the user draws with a cordless pressure-sensitive stylus on a digitizing tablet. From the trajectory followed by the stylus, its associated pressure data, and a specified brush, a stroke of variable width is computed and displayed in real time. First, the digitized trajectory is fitted, thus removing noise. Then, from polygonal approximations of the fitted trajectory and the brush outline, a polygonal approximation of the stroke outline is computed. Working with polygonal approximations reduces computations to simple geometric operations and greatly simplifies the treatment of dynamic, pressure-controlled brushes. Last, the polygonal approximation of the stroke outline is fitted. The result is a closed piecewise Bézier curve approximating the brushstroke outline to within an arbitrary error tolerance. Several examples of hand-sketched drawings realized with this method are presented.     

应用遗传算法的平面曲线最优多边形拟合

平面曲线的多边形拟合是模式识别和计算机视觉研究中非常重要的一类算法。该文提出了一种利用遗传算法（GA）的最优多边形拟合算法。曲线的分段拟合操作被方便地编码为基因串。一种基于面积和模型简单度的全局拟合度量用作GA的适值函数。该文算法可以在无需事先给定分段数目及最大允许偏洋的条件下自动确定这些参量进行多边形拟合。文中给出的实验结果表明了算法的可行性和有效性。     

Computing a compact spline representation of the medial axis transform of a 2D shape

We present a full pipeline for computing the medial axis transform of an arbitrary 2D shape. The instability of the medial axis transform is overcome by a pruning algorithm guided by a user-defined Hausdorff distance threshold. The stable medial axis transform is then approximated by spline curves in 3D to produce a smooth and compact representation. These spline curves are computed by minimizing the approximation error between the input shape and the shape represented by the medial axis transform. Our results on various 2D shapes suggest that our method is practical and effective, and yields faithful and compact representations of medial axis transforms of 2D shapes.     

Numerische Lösung gewöhnlicher Differentialgleichungen mit Splinefunktionen

In this paper a general procedure to obtain spline approximations for the solutions of initial value problems for ordinary differential equations is presented. Several well-known spline approximation methods are included as special cases. It is common practice to partition the interval for which the initial value problem is defined into equidistant subintervals and to construct successively the spline approximation; thereby the spline function has to satisfy certain conditions at the knots. In the general procedure presented here additional knots are admitted in every subinterval. At these points which need not be equally spaced the spline approximation has to fulfill analogous conditions as at the original knots. Convergence and divergence theorems are proved; especially the influence of the additional knots on convergence and divergence of the method is investigated.