Automatic parametrization of rational curves and surfaces II: cubics and cubicoids

Algorithms that can obtain rational and special parametric equations for degree three algebraic curves (cubics) and degree three algebraic surfaces (cubicoids), given their implicit equations are described. These algorithms have been implemented on a VAX8600 using VAXIMA.     

An algorithm for the interpolation of hybrid curves

Real time tool path generation consists of off-line design and real time interpolation of tool paths. An hybrid curve is the intersection of a parametric surface and an implicit surface. Previous work in tool path interpolation focused mainly in the interpolation of parametric curves. Tool paths designed by drive surface methods are hybrid curves which, in general, cannot be represented as parametric curves. An algorithm for the interpolation of hybrid curves is proposed in this paper. The algorithm is based on interpolation of the projection of the hybrid curve into the parametric domain. Each increment involves a second-order interpolation step augmented by iterative error reduction.Simulations of hybrid curve interpolation have been carried out. They are based on practical surfaces represented as NURB surfaces and implicit surfaces including a plane, a cylinder and a high order algebraic surface. They demonstrate that under typical machining conditions, interpolation error is well within the accuracy requirements of typical machining and that the use of one iteration error reduction can significantly reduce the path deviation. These show that the proposed algorithm is potentially useful for tool path interpolation for the machining of parametric surfaces.     

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.     

Symbolic parametrization of curves

If algebraic varieties like curves or surfaces are to be manipulated by computers, it is essential to be able to represent these geometric objects in an appropriate way. For some applications an implicit representation by algebraic equations is desirable, whereas for others an explicit or parametric representation is more suitable. Therefore, transformation algorithms from one representation to the other are of utmost importance.We investigate the transformation of an implicit representation of a plane algebraic curve into a parametric representation. Various methods for computing a rational parametrization, if one exists, are described. As a new idea we introduce the concept of working with classes of conjugate (singular or simple) points on curves. All the necessary operations, like determining the multiplicity and the character of the singular points or passing a linear system of curves through these points, can be applied to such classes of conjugate points. Using this idea one can parametrize a curve if one knows only one simple point on it. We do not propose any new method for finding such a simple point. By classical methods a rational point on a rational curve can be computed, if such a point exists. Otherwise, one can express the coordinates of such a point in an algebraic extension of degree 2 over the ground field.     

Algebraic pruning: a fast technique for curve and surface intersection

Computing the intersection of parametric and algebraic curves and surfaces is a fundamental problem in computer graphics and geometric modeling. This problem has been extensively studied in the literature and different techniques based on subdivision, interval analysis and algebraic formulation are known. For low degree curves and surfaces algebraic methods are considered to be the fastest, whereas techniques based on subdivision and Bézier clipping perform better for higher degree intersections. In this paper, we introduce a new technique of algebraic pruning based on the algebraic approaches and eigenvalue formulation of the problem. The resulting algorithm corresponds to computing only selected eigenvalues in the domain of intersection. This is based on matrix formulation of the intersection problem, power iterations and geometric properties of Bézier curves and surfaces. The algorithm prunes the domain and converges to the solutions rapidly. It has been applied to intersection of parametric and algebraic curves, ray tracing and curve-surface intersections. The resulting algorithm compares favorably with earlier methods in terms of performance and accuracy.     

一类四次隐式代数曲面参数化研究

隐式代数曲面的参数化是 CAGD的热点问题之一 .针对一类四次隐式代数曲面 ,提出一种基于分片的几何参数化方法 .首先对四次代数曲面进行分片 ,然后对每一个分片曲面利用一组同轴平面束与其求交线 ,通过对求得交线的参数化来完成对整个分片曲面的参数化 .该方法是一种精确的参数化方法 ,其结构直观、计算简单 ,并且具有可使分片的四次代数曲面位于 [0 ,1]× [0 ,1]参数区间内 ,以及分片曲面的边界位于等参数线上等特点 ,利用该参数曲面可以方便地实现机器作图和几何操作 .实验结果验证了文中方法的有效性 .     

Computing minimum distance between two implicit algebraic surfaces

The minimum distance computation problem between two surfaces is very important in many applications such as robotics, CAD/CAM and computer graphics. Given two implicit algebraic surfaces, a new method based on the offset technique is presented to compute the minimum distance and a pair of points where the minimum distance occurs. The new method also works where there are an implicit algebraic surface and a parametric surface. Quadric surfaces, tori and canal surfaces are used to demonstrate our new method. When the two surfaces are a general quadric surface and a surface which is a cylinder, a cone or an elliptic paraboloid, the new method can produce two bivariate equations where the degrees are lower than those of any existing method.     

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.     

Locally manipulating the geometry of curved surfaces

Interactive tools that can be used to edit a curved surface locally by altering its intrinsic geometric measures are described. The interface consists of two parts. The first uses graphic displays that illustrate specific characteristics of the surface. Users can isolate different types of curves on a surface. These curves yield unique information about the surface. The second part of the interface uses some of the specialized icons to interactively manipulate the surface itself. The methods can be used with many previously published techniques, and, because they are based on the intrinsic differential geometry of the surface, can be applied to all types of surfaces (parametric, implicit, algebraic, and so forth)     

Bézier representation for cubic surface patches

The paper describes a new method for creating rectangular Bézier surface patches on an implicit cubic surface. Traditional techniques for representing surfaces have relied on parametric representations of surfaces, which, in general, generate surfaces of implicit degree 8 in the case of rectangular Bézier surfaces with rational biquadratic parameterization. The method constructs low-degree algebraic surface patches by reducing the implicit degree from 8 to 3. The construction uses a rectangular biquadratic Bézier control polyhedron that is embedded within a tetrahedron and satisfies a projective constraint. The control polyhedron and the resulting cubic surface patch satisfy all of the standard properties of parametric Bézier surfaces, including interpolation of the corners of the control polyhedron and the convex-hull property.     

Multiresolution for Algebraic Curves and Surfaces using Wavelets

This paper describes a multiresolution method for implicit curves and surfaces. The method is based on wavelets, and is able to simplify the topology. The implicit curves and surfaces are defined as the zero-valued piece-wise algebraic isosurface of a tensor-product uniform cubic B-spline. A wavelet multiresolution method that deals with uniform cubic B-splines on bounded domains is proposed. In order to handle arbitrary domains the proposed algorithm dynamically adds appropriate control points and deletes them in the synthesis phase.     

隐式二次代数曲线插值

目前,二次参数曲线在曲线曲面造型中应用非常广泛,起着至关重要的作用,因此对二次曲线的性质和应用的研究仍十分有意义。本文首先综述近年来有关二次曲线的研究,对各种方法的优缺点进行了客观的评价。然后根据三次代数曲线的构造方法,提出一种新的二次曲线的构造方法,该方法通过几何量如控制点和切线来控制二次代数曲线的形状。文章在理论上对曲线的一系列性质进行了详细说明。     

一类三次隐式代数曲面参数化研究

在CAGD中隐式曲面和参数曲面作为曲面的两种表示形式各有其内在的优点 ,多年来如何有效地实现二者的相互转换一直是CAGD的一个热点问题 对一类GC1拼接两个二次曲面的三次混合代数曲面进行了研究 ,提出一种基于同轴平面束与代数曲面相交的几何化参数化方法 与传统参数化方法相比 ,该方法结构直观且具有可使三次代数曲面位于 [0 ,1]× [0 ,1]参数区间内 ,以及曲面的边界位于等参数线上等特点 ,利用这种参数曲面可以方便地实现机器作图和各种操作 实验结果验证了方法的有效性     

Fairness Criteria for Algebraic Curves

We develop methods for the variational design of algebraic curves. Our approach is based on truly geometric fairness criteria, such as the elastic bending energy. In addition, we take certain feasibility criteria for the algebraic curve segment into account. We describe a computational technique for the variational design of algebraic curves, using an SQP (sequential quadratic programming) – type method for constrained optimization. As demonstrated in this paper, the powerful techniques of variational design can be used not only for parametric representations, but also for curves in implicit form.     

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.     

The Classical Theory of Invariants and Object Recognition Using Algebraic Curve and Surfaces

Combining implicit polynomials and algebraic invariants for representing and recognizing complicated objects proves to be a powerful technique. In this paper, we explore the findings of the classical theory of invariants for the calculation of algebraic invariants of implicit curves and surfaces, a theory largely disregarded in the computer vision community by a shadow of skepticism. Here, the symbolic method of the classical theory is described, and its results are extended and implemented as an algorithm for computing algebraic invariants of projective, affine, and Euclidean transformations. A list of some affine invariants of 4th degree implicit polynomials generated by the proposed algorithm is presented along with the corresponding symbolic representations, and their use in recognizing objects represented by implicit polynomials is illustrated through experiments. An affine invariant fitting algorithm is also proposed and the performance is studied.     

Corner blending of free-form N-sided holes

Geometric modeling requires constructing blends between surfaces to meet manufacturing specifications, reduce stress concentrations in designs, and enhance aesthetics. Industrial engineers may design parts using different surface types to satisfy design requirements. Surface blending integrates the diverse representations. Because most CAD/CAM software uses parametric representations for curves and surfaces, blending techniques for parametric surfaces are more urgently needed than methods for implicit surfaces. The authors discuss a new method for parametric surface blending. They apply their corner blending technique to three- to six-sided holes and discuss corner blending of three sided holes for three different cases, each presenting different blending challenges     

空间有理曲线的μ基及曲线隐式化

空间有理曲线是计算机辅助几何设计中常用曲线,以空间曲线为研究对象,讨论其μ基形式,并用μ基方法快速隐式化一类曲线.首先给出μ基定义和一些基本性质,之后基于μ基方法分析给出空间曲线μ基的符号公式,进一步讨论了用μ基方法隐式化空间有理曲线.通过对结式性质的细致分析,得出一类空间曲线快速隐式化的结果,这类曲线隐式的仿射簇可以用μ基的两两单变量结式表示,对不满足条件的情况给出了反例.     

Parametric cubics as algebraic curves

This paper provides first a general background in the algebraic curve theory of cubics. The specific topics covered are double points, inflection points, tangent lines, three standard curves and the slope parameterization. Then parametric cubics are discussed in this context. Specific topics covered are double points, inflection points, tangent lines, degenerate cubic parameterizations, the inverse problem, and finding the implicit equation. All of these topics are presented so as to be easily translatable into computer algorithms.