平面NURBS曲线及其Offset的双圆弧逼近

除直线、圆弧、速端曲线等少数几种曲线外,平面参数曲线的offset曲线通常不能表示成有 理参数形式,因此在实际应用中,为了方便造型系统中数据结构和几何算法的统一表示,offse t曲线通常用低次曲线逼近来表示.通过用双圆弧逼近表示NURBS(non-uniform rational B -spline)曲线及其offset,并利用双圆弧逼近的特有性质,把offset的双圆弧逼近转化为原 曲线的双圆弧逼近,简化了问题的求解.同时考虑了双圆弧逼近算法中分割点的选取、公切点 的确定以及误差估计等主要问题.具体算     

Bounding the Distance between 2D Parametric Bézier Curves and their Control Polygon

Employing the techniques presented by Nairn, Peters and Lutterkort in [1], sharp bounds are firstly derived for the distance between a planar parametric Bézier curve and a parameterization of its control polygon based on the Greville abscissae. Several of the norms appearing in these bounds are orientation dependent. We next present algorithms for finding the optimal orientation angle for which two of these norms become minimal. The use of these bounds and algorithms for constructing polygonal envelopes of planar polynomial curves, is illustrated for an open and a closed composite Bézier curve.     

Planar piecewise algebraic curves

An approach is described for piecing together segments of planar algebraic curves with derivative continuity. The application of piecewise algebraic curves to area modelling (the two-dimensional analogue of solid modelling) is discussed. A technique is presented for expressing a planar rational parametric curve as an algebraic curve segment. An upper bound is derived for the farthest distance between two algebraic curves (one of which may also be a parametric curve) within a specified region.     

Dual representation of spatial rational Pythagorean-hodograph curves

In this paper, the dual representation of spatial parametric curves and its properties are studied. In particular, rational curves have a polynomial dual representation, which turns out to be both theoretically and computationally appropriate to tackle the main goal of the paper: spatial rational Pythagorean-hodograph curves (PH curves). The dual representation of a rational PH curve is generated here by a quaternion polynomial which defines the Euler–Rodrigues frame of a curve. Conditions which imply low degree dual form representation are considered in detail. In particular, a linear quaternion polynomial leads to cubic or reparameterized cubic polynomial PH curves. A quadratic quaternion polynomial generates a wider class of rational PH curves, and perhaps the most useful is the ten-parameter family of cubic rational PH curves, determined here in the closed form.     

The method of resolvents: A technique for the implicitization, inversion, and intersection of non-planar, parametric, rational cubic curves

Let P(t) be a non-planar, parametric, rational cubic curve. The method of resolvents is applied to: (1) construct three quadric surfaces whose intersection is equal to P(t) (implicitization); (2) solve for the parameter t as the ratio of two linear expressions in the coordinates x, y, z (inversion). The results of these two operations are then applied to construct an optimal, robust, intersection algorithm for any two non-planar rational cubic curves, and it is shown that two such curves can intersect in at most five points. Specializations of these results for non-planar, integral, cubic curves are derived, and extensions of these techniques to non-planar, rational cubic, Bézier curves are also discussed.     

A locally controllable spline with tension for interactive curve design

We describe a new type of parametrically defined space curve. The parameters which define these curves allow for the convenient control over local shape attributes while maintaining global second order geometric continuity. The coordinate functions are defined by piecewise segments of rational functions, each segment being the ratio of cubic polynomials and a common quadratic polynomial. Each curve segment is a planar curve and where two segments meet the curvature is zero. This simple mathematical representation permits these curves to be efficiently manipulated and displayed.     

参数多项式曲线的快速逐点生成算法

给出了参数多项曲线（包括Ｂｅｚｉｅｒ曲线、Ｂ样条曲线等）的一种快速逐点生成算法．在曲线的逐点生成过程中,只用到加减法,故效率极高．而且,此方法可在两３方面加以推广,一是推广到有理参数曲线（包括非均匀有理Ｂ样条曲线）,一是推广到多项式参数曲面以及更高维的多项式参数函数．     

平面三次混合双曲多项式曲线的特征图判别

根据文献[9](Wang G Z,Yang Q M.Planar cubic hybrid hyperbolic polynomial curve and its shape classification.Progress in Natural Science,2004,14(1):41-46)中提出的H-曲线带奇点或拐点的条件,利用H-曲线奇点、拐点的仿射不变性,给出H-曲线几何特征图的判别法,并找到了不同特征图在三维空间中的关系.该判别法完善了H-曲线的奇异点检测理论,提升了几何特征图维数.     

A Direct Approach to Computing theμ-basis of Planar Rational Curves

This paper presents an O(n²) algorithm, based on Gröbner basis techniques, to compute the μ -basis of a degree n planar rational curve. The prior method involved solving a set of linear equations whose complexity by standard numerical methods was O(n³). The μ -basis is useful in computing the implicit equation of a parametric curve and can express the implicit equation in the form of a determinant that is smaller than that obtained by taking the resultant of the parametric equations.     

Surface-to-surface intersections

Techniques for computing intersections of algebraic surfaces with piecewise rational polynomial parametric surface patches and intersections of two piecewise rational polynomial parametric surface patches are discussed. The techniques are classified using four categories-lattice evolution methods, marching methods, subdivision methods, and analytic methods-and their principal features are discussed. It is shown that some of these methods also apply to the general parametric surface-intersection problem     

平面四点确定一条抛物线及其在参数插值中的应用

本文讨论了用平面有序四点确定一条抛物线及其在参数插值中的应用。提出了有用四点确定一条抛物线的算法，讨论了确定抛物线的四点相互间要满足的位置。对平面给定的一组数据点，提出了构造参数插值曲线的新方法。所构造的插值曲线是ＧＣ＾１连续的分片三次参数曲线，其插值精度为二次参数多项式。本文还以计算实例对新方法与其它方法的插值精度进行了比较。     

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

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

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.     

Efficient Parallel Algorithms for Planar st-Graphs

Planar st -graphs find applications in a number of areas. In this paper we present efficient parallel algorithms for solving several fundamental problems on planar st -graphs. The problems we consider include all-pairs shortest paths in weighted planar st -graphs, single-source shortest paths in weighted planar layered digraphs (which can be reduced to single-source shortest paths in certain special planar st -graphs), and depth-first search in planar st -graphs. Our parallel shortest path techniques exploit the specific geometric and graphic structures of planar st -graphs, and involve schemes for partitioning planar st -graphs into subgraphs in a way that ensures that the resulting path length matrices have a monotonicity property [1], [2]. The parallel algorithms we obtain are a considerable improvement over the previously best known solutions (when they are applied to these st -graph problems), and are in fact relatively simple. The parallel computational models we use are the CREW PRAM and EREW PRAM.     

Degenerate parametric curves

This paper discusses two degenerate cases of polynomial parametric curves for which the degrees of the defining polynomials can be reduced without altering the curve. The first case is the improperly parametrized curve for which each point on the curve corresponds to several parameter values. The second case, which can only occur for rational polynomial parametric curves, exists when the defining polynomials all have a common factor.

This paper describes how to detect and correct each type of degeneracy. Examples are given which demonstrate that seemingly innocuous Bézier curves may suffer from either of these degeneracies.     

The shortest path in a simply-connected domain having a curved boundary

Given two distinct points S and E on a closed parametric curve forming the boundary of a simply-connected domain (without holes), this paper provides an algorithm to find the shortest interior path (SIP) between the two points in the domain. The SIP consists of portions of curves along with straight line segments that are tangential to the curve. The algorithm initially computes point-curve tangents and bitangents using their respective constraints. They are then analyzed further to identify potential tangents. A region check is performed to determine the tangent that will form part of the SIP. Portions of the curve that belong to the SIP are also identified during the process. The SIP is identified without explicitly computing the length of the curves/tangents. The curve is represented using non-uniform rational B-splines (NURBS). Results of the implementation are provided.     

A basis for the implicit representation of planar rational cubic Bézier curves

We present an approach to finding the implicit equation of a planar rational parametric cubic curve, by defining a new basis for the representation. The basis, which contains only four cubic bivariate polynomials, is defined in terms of the Bézier control points of the curve. An explicit formula for the coefficients of the implicit curve is given. Moreover, these coefficients lead to simple expressions which describe aspects of the geometric behaviour of the curve. In particular, we present an explicit barycentric formula for the position of the double point, in terms of the Bézier control points of the curve. We also give conditions for when an unwanted singularity occurs in the region of interest. Special cases in which the method fails, such as when three of the control points are collinear, or when two points coincide, will be discussed separately.     

Efficient Parallel Algorithms for Planar st -Graphs

   Abstract. Planar st -graphs find applications in a number of areas. In this paper we present efficient parallel algorithms for solving several fundamental problems on planar st -graphs. The problems we consider include all-pairs shortest paths in weighted planar st -graphs, single-source shortest paths in weighted planar layered digraphs (which can be reduced to single-source shortest paths in certain special planar st -graphs), and depth-first search in planar st -graphs. Our parallel shortest path techniques exploit the specific geometric and graphic structures of planar st -graphs, and involve schemes for partitioning planar st -graphs into subgraphs in a way that ensures that the resulting path length matrices have a monotonicity property [1], [2]. The parallel algorithms we obtain are a considerable improvement over the previously best known solutions (when they are applied to these st -graph problems), and are in fact relatively simple. The parallel computational models we use are the CREW PRAM and EREW PRAM.     

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.     

二次参数曲线拟合平面点的一种新方法

对平面上给定的一组数据点进行了研究,提出了构造参数曲线拟合数据点的一种新方法。所构造的拟合参数曲线是C′连续的分段二次参数曲线。本文以实例对新方法与二次插值样条曲线进行了比较。