Least-Squares B-Spline Curve Approximation with Arbitary End Derivatives

An algorithm for least-squares approximation of data with end derivative constraints is presented. The approximating curve minimises the error in the least-squares sense, while at the same time assumes the derivatives specified. For degree p approximation, up to p 2 1 derivatives may be specified, resulting in C p−1 continuous curve approximants. The method is useful to piece individual curve segments together, or to create closed curves with various degrees of smoothness.     

Cross-Sectional Design with Boundary Constraints

A method for passing a smooth surface through cross-sectional curves is presented. Cross-boundary derivatives across the first and the last cross-sections, and rail curves along which the section curves are positioned can be specified. Interpolation of the rail curves and G 1 or C 1 across the first and last cross-sections can be enforced.     

Data Approximation Using Biarcs

. An algorithm for data approximation with biarcs is presented. The method uses a specific formulation of biarcs appropriate for parametric curves in Bézier or NURBS formulation. A base curve is applied to obtain tangents and anchor points for the individual arcs joining in G 1 continuity. Data sampled from circular arcs or straight line segments is represented precisely by one biarc. The method is most useful in numerical control to drive the cutter along straight line or circular paths.     

Biarc approximation of NURBS curves

An algorithm for approximating arbitrary NURBS curves with biarcs is presented. The main idea is to approximate the NURBS curve with a polygon, and then to approximate the polygon with biarcs to within the required tolerance. The method uses a parametric formulation of biarcs appropriate in geometric design using parametric curves. The method is most useful in numerical control to drive the cutter along straight line or circular paths.     

Surface approximation to scanned data

A method to approximate scanned data points with a B-spline surface is presented. The data are assumed to be organized in the form of Q _i,j, i=0,…,n; j=0,…,m _i, i.e., in a row-wise fashion. The method produces a C ^{(p-1, q-1)} continuous surface (p and q are the required degrees) that does not deviate from the data by more than a user-specified tolerance. The parametrization of the surface is not affected negatively by the distribution of the points in each row, and it can be influenced by a user-supplied knot vector.     

关于具有几何约束的三次代数曲线插值

给定四点pi(xi,yi)(i=1,2,3,4)以逆时针方向构成一简单四边形并在两端点p1和p4处给定两直线L1和L2。张三元等人提出和研究了一种通过上述四点并与L1和L2相切的代数曲线插值并建立了一些新的结果,作者进一步研究了这些代数曲线并给出了三次曲线C(λ)具有通过四点pi(xi,yi)(i=1,2,3,4)的连续凸曲线分支的充分且必要条件,也研究了当四边形不在控制区域上的其它情形。     

隐式二次代数曲线插值

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

参数曲线曲面降阶研究

参数曲线曲面降阶是当今计算机辅助几何设计研究的热点之一,已经被广泛地应用在CAD系统之间的几何数据的传输、几何造型中的求根和求交的计算、数据的几何压缩、曲线曲面的光顺处理、字符的构造以及参数曲线段的提取和信号的滤波等。以参数Bezer曲线降阶方法为主线索,其它如B样条、广义Ball、广义C-Bezer等参数曲线曲面降阶为辅进行了综述讨论。最后给出了参数曲线曲面降阶中有待进一步解决的问题。     

光滑曲面上的G1插值曲线

在计算机图形学和计算机辅助几何设计中,限制在光滑曲面上保持几何连续的曲线插值技术显现出越来越重要的作用.文中用直纹面投影的思想研究了这一问题,给出了一种在光滑曲面上保持G1连续的样条曲线插值技术.首先构造一条插值曲面上已知点列的空间3次Bézier样条曲线,然后通过一张直纹面将这条空间插值曲线投影到已知曲面上,即可得到限制在已知光滑曲面上的G1插值曲线.理论推导和实例显示表明,该技术具有推广应用的广阔前景.     

Multiresolution Surfaces having Arbitrary Topologies by a Reverse Doo Subdivision Method

We have shown how to construct multiresolution structures for reversing subdivision rules using global least squares models (Samavati and Bartels, Computer Graphics Forum, 18(2):97–119, June 1999). As a result, semiorthogonal wavelet systems have also been generated. To construct a multiresolution surface of an arbitrary topology, however, biorthogonal wavelets are needed. In Bartels and Samavati (Journal of Computational and Applied Mathematics, 119:29–67, 2000) we introduced local least squares models for reversing subdivision rules to construct multiresolution curves and tensor product surfaces, noticing that the resulting wavelets were biorthogonal (under an induced inner product). Here, we construct multiresolution surfaces of arbitrary topologies by locally reversing the Doo subdivision scheme. In a Doo subdivision, a coarse surface is converted into a fine one by the contraction of coarse faces and the addition of new adjoining faces. We propose a novel reversing process to convert a fine surface into a coarse one plus an error. The conversion has the property that the subdivision of the resulting coarse surface is locally closest to the original fine surface, in the least squares sense, for two important face geometries. In this process, we first find those faces of the fine surface which might have been produced by the contraction of a coarse face in a Doo subdivision scheme. Then, we expand these faces. Since the expanded faces are not necessarily joined properly, several candidates are usually at hand for a single vertex of the coarse surface. To identify the set of candidates corresponding to a vertex, we construct a graph in such a way that any set of candidates corresponds to a connected component. The connected components can easily be identified by a depth first search traversal of the graph. Finally, vertices of the coarse surface are set to be the average of their corresponding candidates, and this is shown to be equivalent to local least squares approximation for regular arrangements of triangular and quadrilateral faces.     

Optimal bounding cones of vectors in three dimensions

The problem of computing the minimum-angle bounding cone of a set of three-dimensional vectors has numerous applications in computer graphics and geometric modeling. One such application is bounding the tangents of space curves or the vectors normal to a surface in the computation of the intersection of two surfaces.No optimal-time exact solution to this problem has been yet given. This paper presents a roadmap for a few strategies that provide optimal or near-optimal (time-wise) solutions to this problem, which are also simple to implement. Specifically, if a worst-case running time is required, we provide an O(nlogn)-time Voronoi-diagram-based algorithm, where n is the number of vectors whose optimum bounding cone is sought. Otherwise, if one is willing to accept an, in average, efficient algorithm, we show that the main ingredient of the algorithm of Shirman and Abi-Ezzi [Comput. Graphics Forum 12 (1993) 261-272] can be implemented to run in optimal Θ(n) expected time. Furthermore, if the vectors (as points on the sphere of directions) are known to occupy no more than a hemisphere, we show how to simplify this ingredient (by reducing the dimension of the problem) without affecting the asymptotic expected running time. Both versions of this algorithm are based on computing (as an LP-type problem) the minimum spanning circle (respectively, ball) of a two-dimensional (respectively, three-dimensional) set of points.     

曲线插值的一种保凸细分方法

为了弥补以四点插值细分方法为代表的线性细分方法在形状控制方面的缺陷,提出一种基于几何的插值型保凸细分方法.细分过程每一步中,每条边所对应的新控制顶点由原控制顶点及其切向共同确定;每点处的切向由其邻近的点所确定,并且随细分过程逐步调整.理论分析表明,该方法的极限曲线是G1连续的保凸曲线.如果所有的初始点取自圆弧段,则极限曲线就是该圆弧段.数值实例表明,采用文中方法得到的曲线较为光顺.     

G2 Surface Interpolation Over General Topology Curve Networks

The basic idea of curve network‐based design is to construct smoothly connected surface patches, that interpolate boundaries and cross‐derivatives extracted from the curve network. While the majority of applications demands only tangent plane (G¹) continuity between the adjacent patches, curvature continuous connections (G²) may also be required. Examples include special curve network configurations with supplemented internal edges, “master‐slave” curvature constraints, and general topology surface approximations over meshes. The first step is to assign optimal surface curvatures to the nodes of the curve network; we discuss different optimization procedures for various types of nodes. Then interpolant surfaces called parabolic ribbons are created along the patch boundaries, which carry first and second derivative constraints. Our construction guarantees that the neighboring ribbons, and thus the respective transfinite patches, will be G² continuous. We extend Gregory's multi‐sided surface scheme in order to handle parabolic ribbons, involving the blending functions, and a new sweepline parameterization. A few simple examples conclude the paper.     

非均匀三次B样条曲线插值的Jacobi-PIA算法

为了求解非均匀三次B样条曲线插值问题,基于解线性方程组的Jacobi迭代方法提出一种渐进迭代插值算法——Jacobi-PIA算法.该算法以待插值点为初始控制多边形得到第0层的三次B样条曲线,递归地求得插值给定点集的三次B样条曲线;在每个迭代过程中,定义待插值点与第k层的三次B样条曲线上对应点的差向量乘以该点对应的B样条系数的倒数为偏移向量,第k层的控制顶点加上对应的偏移向量得到第k+1层的三次B样条曲线的控制顶点.由于Jacobi-PIA算法在更新控制顶点时减少了一个减法运算,因而运算量更少.理论分析表明该算法是收敛的.数值算例结果表明,Jacobi-PIA算法的收敛速度优于经典的渐进迭代插值算法,与最优权因子对应的带权渐进迭代插值算法基本相同.     

Fair, G- and C-continuous circle splines for the interpolation of sparse data points

This paper presents a carefully chosen curve blending scheme between circles, which is based on angles, rather than point positions. The result is a class of circle splines that robustly produce fair-looking G²-continuous curves without any cusps or kinks, even through rather challenging, sparse sets of interpolation points. With a simple reparameterization the curves can also be made C²-continuous. The same method is usable in the plane, on the sphere, and in 3D space.     

Linear Time Algorithm for Approximating a Curve by a Single-Peaked Curve

Given a function y = f(x) in one variable, we consider the problem of computing the single-peaked (unimodal) curve y =φ(x) minimizing the L₂-distance between them. If the input function f is a histogram with O(n) steps or a piecewise linear function with O(n) linear pieces, we design algorithms for computing φ in linear time. We also give an algorithm to approximate f with a function consisting of the minimum number of unimodal pieces under the condition that each unimodal piece is within a fixed L₂-distance from the corresponding portion of f.     

基于三次 B 样条插值曲面的图像放大方法*

为了实现低分辨率图像的高保真放大,利用原图像中相邻四个像素点的像素值及其在放大后的图像中的位置构造出了对应的三次B样条插值曲面,从而较好地估算出了放大后图像中出现的空白像素值。鉴于彩色图的像素点有R、G、B三个分量,分别构造R曲面、G曲面、B曲面对空白像素点的三个分量进行填充。由于采用构造曲面的高度值作为像素值,使得相邻像素点的像素值不存在较大差异,故而尽可能地避免了马赛克现象的产生,实现了图像的高保真放大。通过对比实验,验证了论文方法对图像放大具有非常好的效果。     

基于Hermite曲线的机器人足球射门算法

机器人足球比赛是关于人工智能的新兴研究领域,它集数学算法、多智能体、机械设计、控制理论等多个学科于一体,是先进科学技术的发展代表。在机器人足球比赛中,射门和传球是两个最基本的动作。提高动作的速度以及准确性、连贯性是提高动作效率的关键。本文提出一种基于Hermite插值曲线的机器人足球射门算法。利用Hermite插值曲线的数学特性,可以使机器人在满足一定速度的基础上,连续、准确地完成射门或传球动作,并且能大幅度地提高射门或传球的效率。本文以FIRA5：5仿真平台为背景,结合试验证明,利用此方法可以较好地提高射门的成功率。     

一类基于三角函数的插值曲线

从三角函数出发,构造了一类插值于首、末端点及其切矢的参数样条曲线,称之为T—Ferguson,并研究了合成T—Ferguson曲线的算法。T—Ferguson曲线丰富了参数样条曲线,是一种可行的构造插值曲线方法。     

Interpolation by geometric algorithm

We present a novel geometric algorithm to construct a smooth surface that interpolates a triangular or a quadrilateral mesh of arbitrary topological type formed by n vertices. Although our method can be applied to B-spline surfaces and subdivision surfaces of all kinds, we illustrate our algorithm focusing on Loop subdivision surfaces as most of the meshes are in triangular form. We start our algorithm by assuming that the given triangular mesh is a control net of a Loop subdivision surface. The control points are iteratively updated globally by a simple local point-surface distance computation and an offsetting procedure without solving a linear system. The complexity of our algorithm is O(mn) where n is the number of vertices and m is the number of iterations. The number of iterations m depends on the fineness of the mesh and accuracy required.