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.     

Convolution surfaces for arcs and quadratic curves with a varying kernel

A convolution surface is an isosurface in a scalar field defined by convolving a skeleton, comprising of points, curves, surfaces, or volumes, with a potential function. While convolution surfaces are attractive for modeling natural phenomena and objects of complex evolving topology, the analytical evaluation of integrals of convolution models still poses some open problems. This paper presents some novel analytical convolution solutions for arcs and quadratic spline curves with a varying kernel. In addition, we approximate planar higher-degree polynomial spline curves by optimal arc splines within a prescribed tolerance and sum the potential functions of all the arc primitives to approximate the field for the entire spline curve. Published online: November 20, 2002     

一种参数多项式曲面片的逐点生成算法

在计算机绘图中，一般来说，曲线实际上是由折线代替，而曲面实为小平面拼接而成，在使计算量降到最低的情况下画出真正的曲线方面，已有许多文章研究了曲线的逐点生成方法，并取得了一定的进展，但是尚无有效的快速逐点生成曲面的方法，为了快速逐点生成曲面，在建立多项式函数递推计算公式和算法的基础上，给出了一种逐点生成参数多项式曲面片的算法，由于此算法中只用到整数加法运算，且点数的适当选取可使计算量达到极小，因此是一种很有效的算法，该方法还可以加以改进，而用于有理函数，这无疑对有理曲线曲面（如NURBS曲线曲面）的快速生成以及对计算机图形学的其他一些领域都是有意义的。     

Sketching piecewise clothoid curves

We present a novel approach to sketching 2D curves with minimally varying curvature as piecewise clothoids. A stable and efficient algorithm fits a sketched piecewise linear curve using a number of clothoid segments with G² continuity based on a specified error tolerance. Further, adjacent clothoid segments can be locally blended to result in a G³ curve with curvature that predominantly varies linearly with arc length. We also handle intended sharp corners or G¹ discontinuities, as independent rotations of clothoid pieces. Our formulation is ideally suited to conceptual design applications where aesthetic fairness of the sketched curve takes precedence over the precise interpolation of geometric constraints. We show the effectiveness of our results within a system for sketch-based road and robot-vehicle path design, where clothoids are already widely used.     

Computing the arc length of parametric curves

Specifying constraints on motion is simpler if the curve is parameterized by arc length, but many parametric curves of practical interest cannot be parameterized by arc length. An approximate numerical reparameterization technique that improves on a previous algorithm by using a different numerical integration procedure that recursively subdivides the curve and creates a table of the subdivision points is presented. The use of the table greatly reduces the computation required for subsequent arc length calculations. After table construction, the algorithm takes nearly constant time for each arc length calculation. A linear increase in the number of control points can result in a more than linear increase in computation. Examples of this type of behavior are shown     

Algebraically rectifiable parametric curves

Sufficient and necessary conditions for the arc length of a polynomial parametric curve to be an algebraic function of the parameter are formulated. It is shown that if the arc length is algebraic, it is no more complicated than the square root of a polynomial. Polynomial curves that have this property encompass the Pythagorean-hodograph curves—for which the arc length is just a polynomial in the parameter—as a proper subset. The algebraically rectifiable cubics, other than Pythagorean-hodograph curves, constitute a single-parameter family of cuspidal curves. The implications of the general algebraic rectifiability criterion are also completely enumerated in the case of quartics, in terms of their cusps and intrinsic shape freedoms. Finally, the characterization and construction of algebraically rectifiable quintics is briefly sketched. These forms offer a rich repertoire of curvilinear profiles, whose lengths are readily determined without numerical quadrature, for practical design problems.     

Determining interference between pairs of solids defined constructively in computer animation

This paper presents theory and implementation of a method for detecting interference between a pair of solid objects. Often at times, when performing simulations, two solids may unwittingly interpenetrate each other. The two components of the system presented in this paper are: (1) a surface representation method to model solid objects; and (2) a method for detecting interference. Body representation of a solid in this system is based upon enveloping each solid with surfaces (called positive entities). Most computer aided design (CAD) systems use solid modeling techniques to represent solid objects. Since most solid models use Boolean operations to model complex objects, a method is presented to envelop complex objects with parametric surfaces. A method for tracing intersection curves between two surfaces is also presented. Discontinuities on surfaces are defined as negative entitics in order to extend the method to complex solids. Determining interference is based upon a numerical algorithm for computing points of intersection between boundary curves and parametrized entities. The existence of segments of these curves inside the boundary of positive and negative entities is established by computing the circulation of a function around the boundary curve. Interference between two solids is then detected. No limitations are imposed on the convexity or simplicity of the boundary curves treated.     

The Convex Hull of Rational Plane Curves

We present an algorithm that computes the convex hull of multiple rational curves in the plane. The problem is reformulated as one of finding the zero-sets of polynomial equations in one or two variables; using these zero-sets we characterize curve segments that belong to the boundary of the convex hull. We also present a preprocessing step that can eliminate many redundant curve segments.     

高精度三次参数样条曲线的构造

构造参数样条曲线的关键是选取节点，该文讨论了GC^2三次参数样条曲线需满足的连续性方程，提出了构造GC^2三次参数样条曲线的新方法，在讨论了平面有序五点确定一组三次多项式函数曲线，平面有序六点唯一确定一条三次多项式函数曲线的基础上，提出了计算相邻两区间上的节点的算法，构造的插值曲线具有三次多项式函数精,该文还以实例对新方法与其它方法构造的插值曲线的精度进行了比较。     

Curve length estimation based on cubic spline interpolation in gray-scale images

This paper deals with a novel local arc length estimator for curves in gray-scale images.The method first estimates a cubic spline curve fit for the boundary points using the gray-level information of the nearby pixels,and then computes the sum of the spline segments’lengths.In this model,the second derivatives and y coordinates at the knots are required in the computation;the spline polynomial coefficients need not be computed explicitly.We provide the algorithm pseudo code for estimation and preprocessing,both taking linear time.Implementation shows that the proposed model gains a smaller relative error than other state-of-the-art methods.     

Intersecting a freeform surface with a general swept surface

We present efficient and robust algorithms for intersecting a rational parametric freeform surface with a general swept surface. A swept surface is given as a one-parameter family of cross-sectional curves. By computing the intersection between a freeform surface and each cross-sectional curve in the family, we can solve the intersection problem. We propose two approaches, which are closely related to each other. The first approach detects certain critical points on the intersection curve, and then connects them in a correct topology. The second approach converts the intersection problem to that of finding the zero-set of polynomial equations in the parameter space. We first present these algorithms for the special case of intersecting a freeform surface with a ruled surface or a ringed surface. We then consider the intersection with a general swept surface, where each cross-sectional curve may be defined as a rational parametric curve or as an implicit algebraic curve.     

基于最佳圆弧样条逼近的快速距离曲面计算

距离曲面是一种常用的隐式曲面,它在几何造型和计算机动画中具有重要的应用价值,但以往往在对距离曲面进行多边形化时速较慢,为了提高点到曲线最近距离计算的效率,提出了一种基于最佳圆弧样条逼近的快速线骨架距离曲面计算方法,该算法对于一条任意的二维NURBS曲线,在用户给定的误差范围内,先用最少量的圆弧样条来逼近给定的曲线,从而把点到NURBS曲线最近距离的计算问题转化为点到圆弧样条最近距离的计算问题,由于在对曲面进行多边形化时,需要大量的点到曲线最近距离的计算,而该处可以将点到圆弧样条最近距离很少的计算量来解析求得,故该算法效率很高,该实验表明,算法简单实用,具有很大的应用价值。     

Offset of curves on tessellated surfaces

Geodesic offset of curves on surfaces is an important and useful tool of computer aided design for applications such as generation of tool paths for NC machining and simulation of fibre path on tool surfaces in composites manufacturing. For many industrial and graphic applications, tessellation representation is used for curves and surfaces because of its simplicity in representation and for simpler and faster geometric operations. The paper presents an algorithm for computing offset of curves on tessellated surfaces. A curve on tessellation (COT) is represented as a sequence of 3D points, with each line segment of every two consecutive points lying exactly on the tessellation. With an incremental approach of the algorithm to compute offset COT, the final offset curve position is obtained through several intermediate offset curve positions. Each offset curve position is obtained by offsetting all the points of COT along the tessellation in such a way that all the line segments gets offset exactly along the faces of tessellation in which the line segments are contained. The algorithm, based entirely on tessellation representation, completely eliminates the formation of local self-intersections. Global self-intersections if any, are detected and corrected explicitly. Offset of both open and closed tessellated curves, either in a plane or on a tessellated surface, can be generated using the proposed approach. The computation of offset COT is very accurate within the tessellation tolerance.     

Markov Processes on Curves

We study the classification problem that arises when two variables—one continuous (x), one discrete (s)—evolve jointly in time. We suppose that the vector x traces out a smooth multidimensional curve, to each point of which the variable s attaches a discrete label. The trace of s thus partitions the curve into different segments whose boundaries occur where s changes value. We consider how to learn the mapping between the trace of x and the trace of s from examples of segmented curves. Our approach is to model the conditional random process that generates segments of constant s along the curve of x. We suppose that the variable s evolves stochastically as a function of the arc length traversed by x. Since arc length does not depend on the rate at which a curve is traversed, this gives rise to a family of Markov processes whose predictions are invariant to nonlinear warpings (or reparameterizations) of time. We show how to estimate the parameters of these models—known as Markov processes on curves (MPCs)—from labeled and unlabeled data. We then apply these models to two problems in automatic speech recognition, where x are acoustic feature trajectories and s are phonetic alignments.     

A Geometric Approach for Multi-Degree Spline

Multi-degree spline (MD-spline for short) is a generalization of B-spline which comprises of polynomial segments of various degrees.The present paper provides a new definition for MD-spline curves in a geometric intuitive way based on an efficient and simple evaluation algorithm.MD-spline curves maintain various desirable properties of B-spline curves,such as convex hull,local support and variation diminishing properties.They can also be refined exactly with knot insertion.The continuity between two adjacent segments with different degrees is at least C1 and that between two adjacent segments of same degrees d is Cd 1.Benefited by the exact refinement algorithm,we also provide several operators for MD-spline curves,such as converting each curve segment into B′ezier form,an efficient merging algorithm and a new curve subdivision scheme which allows different degrees for each segment.     

一种构造任意类三次三角曲线的方法

在自由曲线曲面造型中,一般多以多项式为基函数构造参数曲线曲面,而在三角函数空间中也能构造参数曲线曲面.给出了一种构造任意类三次三角参数曲线的方法,该法以三次多项式曲线的基本性质为基础,从而构造出的曲线与对应的三次多项式曲线具有几乎完全相似的性质,而且所构造的曲线能精确表示圆弧、椭圆弧、抛物线弧等二次曲线,为曲线曲面造型提供了一种新方法.     

二次均匀TC-B样条曲线的扩展

构造了一种新的三角多项式基函数--带参数的均匀二次TC-B样条基,并由此定义了曲线--带参数的均匀二次TC-B样条曲线.该曲线继承了均匀TC-B样条曲线的优点,有着与其相类似的性质,例如凸包性、几何不变性、变差缩减性等.同时它还能精确表示圆弧、椭圆弧等二次曲线,推广到空间即可以表示旋转曲面.此外,由于引入了形状控制参数,使其在工业设计中具有更大的灵活性和更广的应用范围.     

A Recursive Subdivision Algorithm for Piecewise Circular Spline

We present an algorithm for generating a piecewise G ¹ circular spline curve from an arbitrary given control polygon. For every corner, a circular biarc is generated with each piece being parameterized by its arc length. This is the first subdivision scheme that produces a piecewise biarc curve that can interpolate an arbitrary set of points. It is easily adopted in a recursive subdivision surface scheme to generate surfaces with circular boundaries with pieces parameterized by arc length, a property not previously available. As an application, a modified version of Doo–Sabin subdivision algorithm is outlined making it possible to blend a subdivision surface with other surfaces having circular boundaries such as cylinders.     

带形状参数的四次Bezier曲线曲面

提出一种新的含参数的四次多项式基函数,四次Bemstein基函数是它的特例,给出其与四次Bemstein基的转换矩阵。分析了该组基函数的性质,定义了带有形状参数的四次Bezier曲线曲面,它们具有四次Bezier曲线曲面的特性,且当参数均取1时即为四次Bezier曲线曲面。对于给定的控制顶点,可以通过改变形状参数的值整体或局部调控曲线曲面的形状。实例表明,该方法应用于曲线曲面设计是有效的。     

带形状参数的四次Bézier曲线曲面

提出一种新的含参数的四次多项式基函数,四次Bernstein基函数是它的特例,给出其与四次Bernstein基的转换矩阵。分析了该组基函数的性质,定义了带有形状参数的四次Bézier曲线曲面,它们具有四次Bézier曲线曲面的特性,且当参数均取1时即为四次Bézier曲线曲面。对于给定的控制顶点,可以通过改变形状参数的值整体或局部调控曲线曲面的形状。实例表明,该方法应用于曲线曲面设计是有效的。