Automatic parameretization of rational curves and surfaces 1: conics and conicoids

Given the implicit equation for degree two curves (conics) and degree two surfaces (conicoids), algorithms are described here, which obtain their corresponding rational parametric equations (a polynomial divided by another). These rational parameterizations are considered over the fields of rationals, reals and complex numbers. In doing so, solutions are given to important subproblems of finding rational and real points on the given conic curve or conicoid surface. Further polynomial parameterizations are obtained whenever they exist for the conics or conicoids. These algorithms have been implemented on a VAX-780 using VAXIMA.     

Sparse implicitization by interpolation: Characterizing non-exactness and an application to computing discriminants

We revisit implicitization by interpolation in order to examine its properties in the context of sparse elimination theory. Based on the computation of a superset of the implicit support, implicitization is reduced to computing the nullspace of a numeric matrix. The approach is applicable to polynomial and rational parameterizations of curves and (hyper)surfaces of any dimension, including the case of parameterizations with base points. Our support prediction is based on sparse (or toric) resultant theory, in order to exploit the sparsity of the input and the output. Our method may yield a multiple of the implicit equation: we characterize and quantify this situation by relating the nullspace dimension to the predicted support and its geometry. In this case, we obtain more than one multiple of the implicit equation; the latter can be obtained via multivariate polynomial GCD (or factoring). All of the above techniques extend to the case of approximate computation, thus yielding a method of sparse approximate implicitization, which is important in tackling larger problems. We discuss our publicly available Maple implementation through several examples, including the benchmark of a bicubic surface. For a novel application, we focus on computing the discriminant of a multivariate polynomial, which characterizes the existence of multiple roots and generalizes the resultant of a polynomial system. This yields an efficient, output-sensitive algorithm for computing the discriminant polynomial.     

Trimming local and global self-intersections in offset curves/surfaces using distance maps

A robust and efficient algorithm for trimming both local and global self-intersections in offset curves and surfaces is presented. Our scheme is based on the derivation of a rational distance map between the original curve or surface and its offset. By solving a bivariate polynomial equation for an offset curve or a system of three polynomial equations for an offset surface, all local and global self-intersection regions in offset curves or surfaces can be detected. The zero-set of polynomial equation(s) corresponds to the self-intersection regions. These regions are trimmed by projecting the zero-set into an appropriate parameter space. The projection operation simplifies the analysis of the zero-set, which makes the proposed algorithm numerically stable and efficient. Furthermore, in a post-processing step, a numerical marching method is employed, which provides a highly precise scheme for self-intersection elimination in both offset curves and surfaces. The effectiveness of our approach is demonstrated using several experimental results.     

Vector elimination: A technique for the implicitization, inversion, and intersection of planar parametric rational polynomial curves

In this paper vector techniques and elimination methods are combined to help resolve some classical problems in computer aided geometric design. Vector techniques are applied to derive the Bezout resultant for two polynomials in one variable. This resultant is then used to solve the following two geometric problems: Given a planar parametric rational polynomial curve, (a) find the implicit polynomial equation of the curve (implicitization); (b) find the parameter value(s) corresponding to the coordinates of a point known to lie on the curve (inversion). The solutions to these two problems are closed form and, in general, require only the arithmetic operations of addition, subtraction, multiplication, and division. These closed form solutions lead to a simple, non-iterative, analytic algorithm for computing the intersection points of two planar parametric rational polynomial curves. Extensions of these techniques to planar rational Bezier curves are also discussed.     

Isometric Piecewise Polynomial Curves

The main preoccupations of research in computer-aided geometric design have been on shape-specification techniques for polynomial curves and surfaces, and on the continuity between segments or patches. When modelling with such techniques, curves and surfaces can be compressed or expanded arbitrarily. There has been relatively little work on interacting with direct spatial properties of curves and surfaces, such as their arc length or surface area. As a first step, we derive families of parametric piecewise polynomial curves that satisfy various positional and tangential constraints together with arc-length constraints. We call these curves isometric curves. A space curve is defined as a sequence of polynomial curve segments, each of which is defined by the familiar Hermite or Bézier constraints for cubic polynomials; as well, each segment is constrained to have a specified arc length. We demonstrate that this class of curves is attractive and stable. We also describe the numerical techniques used that are sufficient for achieving real time interaction with these curves on low-end workstations.     

Industrial geometry: recent advances and applications in CAD

Industrial Geometry aims at unifying existing and developing new methods and algorithms for a variety of application areas with a strong geometric component. These include CAD, CAM, Geometric Modelling, Robotics, Computer Vision and Image Processing, Computer Graphics and Scientific Visualization. In this paper, Industrial Geometry is illustrated via the fruitful interplay of the areas indicated above in the context of novel solutions of CAD related, geometric optimization problems involving distance functions: approximation with general B-spline curves and surfaces or with subdivision surfaces, approximation with special surfaces for applications in architecture or manufacturing, approximate conversion from implicit to parametric (NURBS) representation, and registration problems for industrial inspection and 3D model generation from measurement data. Moreover, we describe a ‘feature sensitive’ metric on surfaces, whose definition relies on the concept of an image manifold, introduced into Computer Vision and Image Processing by Kimmel, Malladi and Sochen. This metric is sensitive to features such as smoothed edges, which are characterized by a significant deviation of the two principal curvatures. We illustrate its applications at hand of feature sensitive curve design on surfaces and local neighborhood definition and region growing as an aid in the segmentation process for reverse engineering of geometric objects.     

On the Existence and the Coefficients of the Implicit Equation of Rational Surfaces

The existence of the implicit equation of rational surfaces can be proved by three techniques: elimination theory, undetermined coefficients, and the theory of field extensions. The methods of elimination theory and undetermined coefficients also reveal that the implicit equation can be written with coefficients from the coefficient field of the parametric polynomials. All three techniques can be implemented as implicitization algorithms. For each method, the theoretical limitations of the proof and the practical advantages and disadvantages of the algorithm are discussed. Our results are important for two reasons. First, we caution that elimination theory cannot be generalized in a straightforward manner from rational plane curves to rational surfaces to show the existence of the implicit equation; thus other rigorous methods are necessary to bypass the vanishing of the resultant in the presence of base points. Second, as an immediate consequence of the coefficient relationship, we see that the implicit representation involves only rational (or real) coefficients if a parametric representation involves only rational (or real) coefficients. The existence of the implicit equation means every rational surface is a subset of an irreducible algebraic surface. The subset relation can be proper and this may cause problems in certain applications in computer aided geometric design. This anomaly is illustrated by an example.     

Limitations of nonlinear PCA as performed with generic neuralnetworks

Kramer's (1991) nonlinear principal components analysis (NLPCA) neural networks are feedforward autoassociative networks with five layers. The third layer has fewer nodes than the input or output layers. This paper proposes a geometric interpretation for Kramer's method by showing that NLPCA fits a lower-dimensional curve or surface through the training data. The first three layers project observations onto the curve or surface giving scores. The last three layers define the curve or surface. The first three layers are a continuous function, which we show has several implications: NLPCA "projections" are suboptimal producing larger approximation error, NLPCA is unable to model curves and surfaces that intersect themselves, and NLPCA cannot parameterize curves with parameterizations having discontinuous jumps. We establish results on the identification of score values and discuss their implications on interpreting score values. We discuss the relationship between NLPCA and principal curves and surfaces, another nonlinear feature extraction method.     

Parameterization in Finite Precision

Certain classes of algebraic curves and surfaces admit both parametric and implicit representations. Such dual forms are highly useful in geometric modeling since they combine the strengths of the two representations. We consider the problem of computing the rational parameterization of an implicit curve or surface in a finite precision domain. Known algorithms for this problem are based on classical algebraic geometry, and assume exact arithmetic involving algebraic numbers. In this work we investigate the behavior of published parameterization algorithms in a finite precision domain and derive succinct algebraic and geometric error characterizations. We then indicate numerically robust methods for parameterizing curves and surfaces which yield no error in extended finite precision arithmetic and, alternatively, minimize the output error under fixed finite precision calculations. Received January 8, 1997; revised August 27, 1998.     

On the numerical condition of algebraic curves and surfaces 1. Implicit equations

The numerical stability of algebraic curves and surfaces represented by implicit equations is investigated. The condition number at a point of a curve or surface is defined as the ratio of the maximum normal displacement of that point to the relative magnitude ϵ of the random perturbations in the curve or surface coefficients, in the limit ϵ → 0. Closed-form expressions for such condition numbers are presented, and the singular points of implicitly defined curves and surfaces are shown to be inherently ill-conditioned. Condition numbers for curve and surface intersections may be expressed in terms of those of the participant entities at the given point and certain geometric factors determined by the normal directions there. Tangential intersections are also seen to be inherently ill-conditioned. The dependence of condition numbers on the chosen multivariate polynomial basis is then examined. In particular, we compare power expansions about a given center, barycentric Bernstein bases over simplicial domains, and tensor-product Bernstein bases over rectangular domains. Configurations are enumerated in which one of these bases provides better conditioning than another at each point of every curve or surface in a given domain. The subdivision and degree elevation of multivariate Bernstein forms (barycentric or tensor-product) exhibit such behavior.     

NURBS曲线曲面的显式矩阵表示及其算法

从 B样条的差商定义出发 ,提出差商展开系数的概念 ,通过差商展开系数显式解析表示式的导出 ,得到任意次 NU RBS曲线曲面系数矩阵的显式解析表示式 ,并给出了求差商展开系数和 NURBS曲线曲面系数矩阵的数值算法 .文中给出的方法适用于一切 NU RBS曲线曲面 ,包括有理和非有理的 Bézier、均匀和非均匀的 B样条曲线曲面 .相应的数值算法计算简单 ,易于实现 .差商展开系数解析表示式为 NU RBS曲线曲面的表示、转换和节点插入、升阶等基本运算以及与差商相关的问题的研究提供了一个统一的构造性工具和应用方法 .     

3D object recognition using invariants of 2D projection curves

This paper presents a new method for recognizing 3D objects based on the comparison of invariants of their 2D projection curves. We show that Euclidean equivalent 3D surfaces imply affine equivalent 2D projection curves that are obtained from the projection of cross-section curves of the surfaces onto the coordinate planes. Planes used to extract cross-section curves are chosen to be orthogonal to the principal axes of the defining surfaces. Projection curves are represented using implicit polynomial equations. Affine algebraic and geometric invariants of projection curves are constructed and compared under a variety of distance measures. Results are verified by several experiments with objects from different classes and within the same class.     

Computing the intersection of two ruled surfaces by using a new algebraic approach

In this paper a new algorithm for computing the intersection of two rational ruled surfaces, given in parametric/parametric or implicit/parametric form, is presented. This problem can be considered as a quantifier elimination problem over the reals with an additional geometric flavor which is one of the central themes in V. Weispfenning research. After the implicitization of one of the surfaces, the intersection problem is reduced to finding the zero set of a bivariate equation which represents the parameter values of the intersection curve, as a subset of the other surface. The algorithm, which involves both symbolic and numerical computations, determines the topology of the intersection curve as an intermediate step and eliminates extraneous solutions that might arise in the implicitization process.     

Stability crossing surfaces for linear time-delay systems with three delays

In this article, the stability of linear systems with time-delays is studied. The cases where the characteristic equations of the system include three delays are investigated. Using the geometrical relations in a normalised polynomial plane, a graphical method is presented to visualise the stability domains in the space of the time-delays. In this space, the points at which the characteristic equation has a zero on the imaginary axis (the border between stability and instability regions) are identified. These points form several surfaces called the ‘stability crossing surfaces’. This work extends the results of the previous works on the ‘stability crossing curves’ defined in the two-dimensional space (plane) of delays to a higher dimension and provides new geometric interpretations for the stability crossing conditions.     

多项式混合曲线曲面方法构造

针对混合曲线表示及其求导和求积困难的问题,通过计算构造出一种多项式混合曲线曲面形式.当待混合曲线是多项式时,混合曲线也为多项式形式.该多项式混合公式可以推广得到任意参数连续C(n)和几何连续G(n)的混合曲线曲面.另外,在得到的混合曲线曲面族中构造出了新的更优能量光顺方程,通过设置参数可得到合适的混合曲线曲面.实验结果表明,文中提出的混合曲线曲面造型方法稳定、有效.     

Implicit polynomials, orthogonal distance regression, and the closest point on a curve

Implicit polynomials (i.e., multinomials) have a number of properties that make them attractive for modeling curves and surfaces in computer vision. The paper considers the problem of finding the best fitting implicit polynomial (or algebraic curve) to a collection of points in the plane using an orthogonal distance metric. Approximate methods for orthogonal distance regression have been shown by others to be prone to the problem of cusps in the solution and this is confirmed here. Consequently, this work focuses on exact methods for orthogonal distance regression. The most difficult and costly part of exact methods is computing the closest point on the algebraic curve to an arbitrary point in the plane. The paper considers three methods for achieving this in detail. The first is the standard Newton's method, the second is based on resultants which are making a resurgence in computer graphics, and the third is a novel technique based on successive circular approximations to the curve. It is shown that Newton's method is the quickest, but that it can fail sometimes even with a good initial guess. The successive circular approximation algorithm is not as fast, but is robust. The resultant method is the slowest of the three, but does not require an initial guess. The driving application of this work was the fitting of implicit quartics in two variables to thinned oblique ionogram traces.     

The 3L algorithm for fitting implicit polynomial curves andsurfaces to data

We introduce a completely new approach to fitting implicit polynomial geometric shape models to data and to studying these polynomials. The power of these models is in their ability to represent nonstar complex shapes in two(2D) and three-dimensional (3D) data to permit fast, repeatable fitting to unorganized data which may not be uniformly sampled and which may contain gaps, to permit position-invariant shape recognition based on new complete sets of Euclidean and affine invariants and to permit fast, stable single-computation pose estimation. The algorithm represents a significant advancement of implicit polynomial technology for four important reasons. First, it is orders of magnitude taster than existing fitting methods for implicit polynomial 2D curves and 3D surfaces, and the algorithms for 2D and 3D are essentially the same. Second, it has significantly better repeatability, numerical stability, and robustness than current methods in dealing with noisy, deformed, or missing data. Third, it can easily fit polynomials of high, such as 14th or 16th, degree. Fourth, additional linear constraints can be easily incorporated into the fitting process, and general linear vector space concepts apply     

Algorithms for Trigonometric Curves (Simplification,Implicitization, Parameterization)

A trigonometric curve is a real plane curve where each coordinate is given parametrically by a truncated Fourier series. The trigonometric curves frequently arise in various areas of mathematics, physics, and engineering. Some trigonometric curves can also be represented implicitly by bivariate polynomial equations. In this paper, we give algorithms for (a) simplifying a given parametric representation, (b) computing an implicit representation from a given parametric representation, and (c) computing a parametric representation from a given implicit representation.     

插值给定数据点的四次PH曲线构造

目的 PH （Pythagorean hodograph）曲线由于具备有理等距曲线、弧长可精确计算等优良的几何性质,广泛应用于数控加工和路径规划等方面。曲线插值是曲线构造的主要手段之一,虽然对PH曲线的Hermite插值方法进行了广泛研究,但插值给定数据点的构造方法仍有待突破,为推广四次PH曲线的应用范围,提出了一种新的四次PH曲线的3点插值问题解决方法。方法 从四次PH曲线的代数充分必要条件出发,在该曲线的Bézier控制多边形中引入辅助控制顶点,指出其中实参数的几何意义,该实参数可作为形状调节因子对构造曲线进行交互。对给定的3个平面型值点进行参数化确定相应的参数值;通过对四次PH曲线一阶导数积分得到曲线的显式表达,其中包含一个待定复常量,将给定的约束点代入曲线的显式表达式得到关于待定复常量的一元二次复方程,求解该复方程并反求Bézier控制顶点得到符合约束条件的四次PH曲线。结果 实验对通过构造插值给定数据点的四次PH曲线进行比较,当形状调节因此改变时,曲线形状可进行有效交互。每次交互得到两条四次PH曲线,通过弧长、弯曲能量、绝对旋转数的计算得到最优曲线,并构造得到PH曲线的等距线。结论 本文方法给定的形状调节参数具有明确的代数意义和几何意义,本文方法易于实现,可有效进行交互。