有理B样条曲线的区间隐式化

研究有理B样条曲线的区间隐式化问题，即对给定的一条有理B样条曲线，寻求低次的区间隐式B样条包含给定的曲线，要求区间隐式B样条曲线的宽度尽量小，并且尽量避免多余分支的出现．将该问题分为求解近似隐式曲线和边界曲线两步，并将问题转化为求解局部的线性最优化问题．最后给出几个算例．     

有理曲线的均匀区间隐式化

参数式曲线与隐式曲线是CAGD中常用的两种曲线形式,因此需要建立起二者之间相互转换的体制.长期以来,许多工作都集中在利用结式思想,将一个参数式曲线精确转化为一个隐式曲线上,而事实上用隐式曲线精确表示一条参数式曲线不仅非常麻烦,而且往往也没有必要.故此提出了参数式有理曲线均匀区间隐式化的一种新方法,利用区间算术和空间重心坐标的定义,可以用一个低阶区间多项式隐式曲线来逼近所给的参数式有理曲线,同时使一些目标函数最小化,达到用隐式多项式曲线来逼近参数式有理曲线的很好效果,并提供了一些算法和实例.     

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

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

有理Bézier曲线的近似弦长参数化算法

只有圆弧、等轴双曲线、伯努利双纽线和帕斯卡蚶线等曲线是可弦长参数化曲线,一般形式的Bézier曲线不满足可弦长参数化条件.为了生成有理n次Bézier曲线的近似弦长参数化,提出一种基于数值优化的弦长参数优化算法.首先推导了有理2次、3次和4次Bézier曲线满足弦长参数化的条件;然后对一般形式的有理n次Bézier曲线作M?bius变换,根据可弦长参数化条件推导出曲线与标准弦长参数化的偏差公式;最后通过优化方法计算曲线的最优参数表示.多个数值实例结果表明,该算法是有效的.     

有理Bézier曲面的区间隐式化

本文依据以往的研究引入了有理Bézier曲面的区间隐式化的概念,即找到一条较低次的区间代数曲面使得给出的有理Bézier曲面落在该区间代数曲面内,并使得该区间代数曲面的宽度达到最小．文中给出了一个通过解一个带有线性限制条件的二次优化问题来计算一有理Bézier曲面的区间代数曲面的算法,并用实例演示了该算法．     

有理曲线的近似隐式化表示

本文首次提出了曲线近似隐式化的概念，给出了求曲线的近似隐式化表示的有效算法，并以实例说明了算法有效性以及研究这一问题的重要意义。     

有理Bézier曲面的区间隐式化

本文依据以往的研究引入了有理Bézier曲面的区间隐式化的概念,即找到一条较低次的区间代数曲面使得给出的有理Bézier曲面落在该区间代数曲面内,并使得该区间代数曲面的宽度达到最小.文中给出了一个通过解一个带有线性限制条件的二次优化问题来计算一有理Bézier曲面的区间代数曲面的算法,并用实例演示了该算法.     

NURBS曲线C~1连续参数优化算法

曲线的参数特性直接决定基于自由曲线的路径规划、运动控制等算法的质量.为了生成满足C1连续的近似弧长参数化,提出一种基于分段三次重新参数化的参数优化算法.首先利用Simpson方法离散积分能量,然后使用极值求解法求得初始解,最后通过LM(Levenberg-Marquardt)优化算法计算出曲线的最优参数表示.与C1连续的分段有理重新参数化方法相比,该算法能够在分段数量很少的情况下达到局部最优.最后通过实例说明了文中算法的有效性.     

C1五次Pythagorean Bézier样条曲线的构造

构造了Ｂｅｚｉｅｒ形式的Ｐｙｔｈａｇｏｒｅａｎ速端曲线（ＰＨ曲线）,亦称之为Ｐｙｔｈａｇｏｒｅａｎ Ｂｅｚｉｅｒ速端曲线（ＰＢ曲线）,对于ｎ次（ｎ为奇数）ＰＢ曲线,得到了以（２ｎ－１）次有理曲线精确表示的等距线和多项式形式的弧长表达式,特别地,研究了五次ＰＢ曲线的特征性质及产生拐点的条件,构造了它的一阶Ｈｅｒｍｉｔｅ插值曲线,得到了Ｃ＾１的五次ＰＢ样条曲线。     

圆弧曲线的三次NURBS表示

本文首次提出三次ＮＵＲＢＳ曲线精确地表示圆弧的充要条件，解决了两方面的问题：一是已知三次ＮＵＲＢＳ曲线，如何判断它是否是圆弧，二是已知一圆弧曲线，怎样用三次ＮＵＲＢＳ曲线精确地表示，给出了圆弧曲线的三次ＮＵＲＢＳ表示的几何构造算法，均匀有理Ｂ样条曲线和有理Ｂｅｚｉｅｒ曲线精确地表示圆弧曲线的充要条件可作为ＮＵＲＢＳ曲线的特殊情形得到，这些研究结果为ＮＵＲＢＳ应用于ＣＡＧＤ，ＣＡＤ／ＣＡＭ提供了一个     

有理曲面的区间隐式化

利用一个低阶多项式区间隐式曲面来包围所给的参数式有理曲面,并构造了一些关于区间隐式曲面厚度和微分张量的目标函数.在最小化这些目标函数的条件下,该区间隐式曲面的中心曲面可以近似地逼近有理曲面,其逼近的误差可以利用区间隐式曲面的区间宽度进行估计.最后提供了具体的算法和一些实例.     

Implicitization of rational parametric equations

Based on the Gröbner basis method, we present algorithms for a complete solution to the following problems in the implicitization of a set of rational parametric equations. (1) Find a basis of the implicit prime ideal determined by a set of rational parametric equations. (2) Decide whether the parameters of a set of rational parametric equations are independent. (3) If the parameters of a set of rational parametric equations are not independent, reparameterize the parametric equations so that the new parametric equations have independent parameters. (4) Compute the inversion maps of parametric equations, and as a consequence, give a method to decide whether a set of parametric equations is proper. (5) In the case of algebraic curves, find a proper reparameterization for a set of improper parametric equations.     

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.     

Efficient Groebner walk conversion for implicitization of geometric objects

In this paper, the author uses recent theoretical results from the method of Groebner bases to improve the efficiency of algorithms for implicitization. The method of Groebner bases has some important advantages, namely it is reliable and it can solve the implicitization problem in full generality.

The main result of this paper is that we can significantly improve the efficiency of implicitization algorithms using the deterministic Groebner walk conversion while maintaining the reliability of the algorithms. More precisely, the calculation of the implicit equations will be partitioned into several smaller computations following a path in the Groebner fan of the ideal generated by the system of equations. This method works with ideals of zero-dimension as well as positive dimension. The author uses a deterministic method to vary the weight vectors in order to ensure that the computation involves polynomials with just a few terms. A new concept of ideal-specified term orders for elimination is introduced to further improve the efficiency. As the result, the improved algorithms overcome the bottle-neck of the traditional implicitization algorithms by avoiding unnecessary zero-reductions and coefficient swell. Furthermore, the improved algorithms are able to avoid many unnecessary walking steps during the calculation of the implicit equations.

Several test-suites such as the Newell's teapot are used to test the new approach. The average performance is many times faster than traditional Groebner basis based algorithms for implicitization.     

有理B样条曲面的区间隐式化

提出有理B样条曲面的区间隐式化方法,即对一个有理B样条曲面,寻求包含给定的曲面的区间隐式B样条曲面,使得区间隐式B样条曲面的"厚度"尽量小,同时尽量避免出现多余分支.该问题等价于求区间隐式B样条曲面的2个边界曲面.针对该问题建立一个最优化模型并求解.     

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.     

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.     

Quaternion rational surfaces: Rational surfaces generated from the quaternion product of two rational space curves

A quaternion rational surface is a surface generated from two rational space curves by quaternion multiplication. The goal of this paper is to demonstrate how to apply syzygies to analyze quaternion rational surfaces. We show that we can easily construct three special syzygies for a quaternion rational surface from a μ-basis for one of the generating rational space curves. The implicit equation of any quaternion rational surface can be computed from these three special syzygies and inversion formulas for the non-singular points on quaternion rational surfaces can be constructed. Quaternion rational ruled surfaces are generated from the quaternion product of a straight line and a rational space curve. We investigate special μ-bases for quaternion rational ruled surfaces and use these special μ-bases to provide implicitization and inversion formulas for quaternion rational ruled surfaces. Finally, we show how to determine if a real rational surface is also a quaternion rational surface.     

Curve implicitization using moving lines

It is a classical result that two corresponding pencils of lines intersect in a conic section, and likewise any conic section can be expressed as the intersection of two pencils of lines. We here extend the idea of pencils to higher degree families lines, and show that any planar rational curve can be expressed as the intersection of two families of lines. This extension leads to a more efficient implicitization algorithm for curves, in which, for example, the implicit equation of a degree four rational curve can generally be expressed as the determinant of a 2 × 2 matrix (Bezout's resultant produces a 4 × 4 matrix and Sylvester's resultant an 8 × 8 matrix).