Progressive iterative approximation for triangular Bézier surfaces

Recently, for the sake of fitting scattered data points, an important method based on the PIA (progressive iterative approximation) property of the univariate NTP (normalized totally positive) bases has been effectively adopted. We extend this property to the bivariate Bernstein basis over a triangle domain for constructing triangular Bézier surfaces, and prove that this good property is satisfied with the triangular Bernstein basis in the case of uniform parameters. Due to the particular advantages of triangular Bézier surfaces or rational triangular Bézier surfaces in CAD (computer aided design), it has wide application prospects in reverse engineering.     

High-quality rendering of quartic spline surfaces on the GPU

We present a novel GPU-based algorithm for high-quality rendering of bivariate spline surfaces. An essential difference to the known methods for rendering graph surfaces is that we use quartic smooth splines on triangulations rather than triangular meshes. Our rendering approach is direct in the sense that since we do not use an intermediate tessellation but rather compute ray-surface intersections (by solving quartic equations numerically) as well as surface normals (by using Bernstein-Bézier techniques) for Phong illumination on the GPU. Inaccurate shading and artifacts appearing for triangular tesselated surfaces are completely avoided. Level of detail is automatic since all computations are done on a per fragment basis. We compare three different (quasi-) interpolating schemes for uniformly sampled gridded data, which differ in the smoothness and the approximation properties of the splines. The results show that our hardware based renderer leads to visualizations (including texturing, multiple light sources, environment mapping, etc.) of highest quality.     

Polycube splines

This paper proposes a new concept of polycube splines and develops novel modeling techniques for using the polycube splines in solid modeling and shape computing. Polycube splines are essentially a novel variant of manifold splines which are built upon the polycube map, serving as its parametric domain. Our rationale for defining spline surfaces over polycubes is that polycubes have rectangular structures everywhere over their domains, except a very small number of corner points. The boundary of polycubes can be naturally decomposed into a set of regular structures, which facilitate tensor-product surface definition, GPU-centric geometric computing, and image-based geometric processing. We develop algorithms to construct polycube maps, and show that the introduced polycube map naturally induces the affine structure with a finite number of extraordinary points. Besides its intrinsic rectangular structure, the polycube map may approximate any original scanned data-set with a very low geometric distortion, so our method for building polycube splines is both natural and necessary, as its parametric domain can mimic the geometry of modeled objects in a topologically correct and geometrically meaningful manner. We design a new data structure that facilitates the intuitive and rapid construction of polycube splines in this paper. We demonstrate the polycube splines with applications in surface reconstruction and shape computing.     

三角域上双变量Chebyshev 多项式及其与Bernstein 基的转换

为了更好的解决三角域上的Bézier 曲面在CAGD 中的最佳一致逼近问题, 构造出了三角域上的双变量Chebyshev 正交多项式,研究了与单变量Chebyshev 多项式相类 似的性质,并且给出了三角域上双变量Chebyshev 基和Bernstein 基的相互转换矩阵。通过 实例比较双变量Chebyshev 多项式与双变量Bernstein 多项式以及双变量Jacobi 多项式的最 小零偏差的大小,阐述了双变量Chebyshev 多项式的最小零偏差性。     

Some smoothness conditions and conformality conditions for bivariate quartic and quintic splines

This paper is concerned with a study of some new formulations of smoothness conditions and conformality conditions for multivariate splines in terms of B-net representation. In the bivariate setting, a group of new parameters of bivariate quartic and quintic polynomials over a planar simplex is introduced, new formulations of smoothness conditions of bivariate quartic C ¹ splines and quintic C ² splines are given, and the conformality conditions of bivariate quartic C ¹ splines are simplified. Received: February 1998 / Accepted: August 1998     

A geometric programming approach for bivariate cubic L1 splines

Bivariate cubic L₁ splines provide C¹-smooth, shape-preserving interpolation of arbitrary data, including data with abrupt changes in spacing and magnitude. The minimization principle for bivariate cubic L₁ splines results in a nondifferentiable convex optimization problem. This problem is reformulated as a generalized geometric programming problem. A geometric dual with a linear objective function and convex cubic constraints is derived. A linear system for dual-to-primal conversion is established. The results of computational experiments are presented.     

Bivariate splines for fluid flows

We discuss numerical approximations of the 2D steady-state Navier-Stokes equations in stream function formulation using bivariate splines of arbitrary degree d and arbitrary smoothness r with r<d. We derive the discrete Navier-Stokes equations in terms of B-coefficients of bivariate splines over a triangulation, with curved boundary edges, of any given domain. Smoothness conditions and boundary conditions are enforced through Lagrange multipliers. The pressure is computed by solving a Poisson equation with Neumann boundary conditions. We have implemented this approach in MATLAB and our numerical experiments show that our method is effective. Numerical simulations of several fluid flows will be included to demonstrate the effectiveness of the bivariate spline method.     

Surface reconstruction using bivariate simplex splines on Delaunay configurations

Recently, a new bivariate simplex spline scheme based on Delaunay configuration has been introduced into the geometric computing community, and it defines a complete spline space that retains many attractive theoretic and computational properties. In this paper, we develop a novel shape modeling framework to reconstruct a closed surface of arbitrary topology based on this new spline scheme. Our framework takes a triangulated set of points, and by solving a linear least-square problem and iteratively refining parameter domains with newly added knots, we can finally obtain a continuous spline surface satisfying the requirement of a user-specified error tolerance. Unlike existing surface reconstruction methods based on triangular B-splines (or DMS splines), in which auxiliary knots must be explicitly added in advance to form a knot sequence for construction of each basis function, our new algorithm completely avoids this less-intuitive and labor-intensive knot generating procedure. We demonstrate the efficacy and effectiveness of our algorithm on real-world, scattered datasets for shape representation and computing.     

Urn Models and Beta-Splines

Splines were originally studied in approximation theory where the focus is on approximating explicit functions of the form y = f(x) or z = f(x,y). These splines were later adopted by mathematicians and computer sicentists for use in computer-aided geometric design (CAGD) where the emphasis was shifted to parametric curves and surfaces. Initially the continuity conditions for splines developed in approximation theory were retained in CAGD, but it was soon realized that the old constraints were unnecessarily restrictive in this new context and that they could be relaxed without losing the essential property of smoothness. Beta-splines were developed to take advantage of this new freedom by introducing shape parameters into the constraint equations. These parameters could then be manipulated by a designer to change the shape of a curve of surface in an intuitively meaningful and useful way. Another seemingly unrelated context in which shape parameters appear is in blending functions constructed from discrete urn models. The purpose of this article is to begin to unify these two independent approaches to shape parameters, and in the process apply the techniques of urn models to gain some insight into the properties of Beta-splines.     

A novel algorithm for explicit optimal multi-degree reduction of triangular surfaces

This paper introduces the algebraic property of bivariate orthonormal Jacobi polynomials into geometric approximation. Based on the latest results on the transformation formulae between bivariate Bernstein polynomials and Jacobi polynomials, we naturally deduce a novel algorithm for multi-degree reduction of triangular B~zier surfaces. This algorithm possesses four characteristics： ability of error forecast, explicit expression, less time consumption, and best precision. That is, firstly, whether there exists a multi-degree reduced surface within a prescribed tolerance is judged beforehand; secondly, all the operations of multi-degree reduction are just to multiply the column vector generated by sorting the series of the control points of the original surface in lexicographic order by a matrix; thirdly, this matrix can be computed at one time and stored in an array before processing degree reduction; fourthly, the multi-degree reduced surface achieves an optimal approximation in the norm L2. Some numerical experiments are presented to validate the effectiveness of this algorithm, and to show that the algorithm is applicable to information processing of products in CAD system.     

带形状参数的Bernstein-Bézier曲面

虽然三角域上的曲面造型方法能有效解决不规则产品的几何造型问题, 在实际工程中有着广泛的应用, 但由于其结构的特殊性和复杂性, 目前对三角域曲面的扩展研究并不多。为了丰富三角域曲面的理论, 针对如何增强三角域曲面形状表示的灵活性进行了专门的研究。首先构造了一组三角域上含一个参数的四次多项式基函数, 它是三角域上二次Bernstein基函数的扩展。然后用递推的方式定义了三角域上含一个参数的n+2次多项式基函数, 它是三角域上n次Bernstein基函数的扩展。基于新的n+2次多项式基函数, 定义了相应的n阶三角域曲面。分析了基函数和曲面的性质, 新曲面不仅具备三角域上Bernstein Bézier曲面的基本性质, 而且还可以在不改变控制顶点的情况下, 通过改变参数的值来自由调整曲面的形状。     

Approximation and estimation bounds for free knot splines

The fitting to data by splines has long been known to improve dramatically if the knots can be adjusted adaptively. To demonstrate the quality of the obtained free knot spline, it is essential to characterize its generalization ability. By utilizing the powerful techniques of the empirical process and approximation theory to address the estimation and approximation error bounds, respectively, the generalization ability of the free knot spline learning strategy is successfully characterized. We show that the Pseudo-dimension of free knot splines is essentially a linear function of the number of knots. A class of rather general loss functions is considered here and the squared loss is specially treated for its excellent property. We also provide some numerical results to demonstrate the utility of these theoretical results in guiding the process of choosing the appropriate knot numbers through the training data to avoid the overfitting/underfitting problem.     

双变量Box样条小波在图像处理中的应用

将单变量样条扩展到双变量Box样条,并给出Box样条在图像处理中极为有用的几条性质,然后,提出了一个使用一类双变量Box样条来计算滤波器库的方法,这样得到的滤波器库在4频带分析/综合框架中具有完全重构的性质,可用来十分有效地分解合成图像。最后,给出应用此方法的一个实例。     

A Bivariate Spline Method for Second Order Elliptic Equations in Non-divergence Form

A bivariate spline method is developed to numerically solve second order elliptic partial differential equations in non-divergence form. The existence, uniqueness, stability as well as approximation properties of the discretized solution will be established by using the well-known Ladyzhenskaya–Babuska–Brezzi condition. Bivariate splines, discontinuous splines with smoothness constraints are used to implement the method. Computational results based on splines of various degrees are presented to demonstrate the effectiveness and efficiency of our method.     

拥有指数参数的新三角基

目的 为了使构造的曲线拥有传统Bézier曲线的良好性质,同时还具备形状可调性、逼近性、保形性以及实用性。方法 首先在拟扩展切比雪夫空间的框架下,构造了一类具有全正性的拟三次三角Bernstein基函数,并给出了该基函数的性质;基于此基函数,构造了相应的拟三次三角Bézier曲线,分析了其曲线的性质,得到了生成曲线的割角算法以及C¹,C²光滑拼接条件,同时还提出了一种估计曲线逼近控制多边形程度的三角Bernstein算子;接着在拟三次三角Bernstein基函数的基础上提出一种三角域上带3个指数参数的拟三次三角Bernstein-Bézier基,基于此基生成了一种三角域上的拟三次三角Bernstein-Bézier曲面,该曲面可以构建边界为椭圆弧、抛物线弧以及圆弧的曲面,此外,还提出一种实用的de-Casteljau-type算法,同时还给出了连接两个曲面的G¹连续条件。结果 实验表明,本文在拟扩展切比雪夫空间中构造的具有全正性的曲线曲面,能够灵活地进行形状调整,而且具有良好的逼近性以及适用性。结论 本文在拟扩展切比雪夫空间的框架下构造了一类具有全正性的基函数,并以此基函数进行曲线曲面构造。实验表明本文构造的曲线具备传统三次Bézier曲线的所有优良性质,而且具有灵活的形状可调性。随着参数的增大,所生成的曲线能够更加逼近控制多边形,模拟控制多边形的行为。此外,本文在三角域上构造的曲面能够生成边界为椭圆弧的曲面。综上,本文提出的基函数满足几何工业的需要,是一种实用的方法。     

利用Box样条构造完全重构模型的研究

针对图象处理中的图象重构问题,结合多频带DFT滤波器库和双变量Box样条构造了一个完全重构模型,在介绍了DFT滤波器库后,给出了形成完全重构模型的条件,通过双变量Box样条及其在图象处理极为有用的几条性质的分析,提出了一类双变量Box样条,使用该样条即可构造分解/重构模型,实验证明,该模型能满足完全重构条件,并可有效分解合成图象,最后,给出了应用此模型的实验结果。     

三向四次箱样条曲面与Bezier曲面的光滑拼接

以二元四次多项式在三角域和矩形域上的Bezier形式的Blossom为工具,给出了当给定一张三向四次箱样条曲面时,能与之C^0、C^1、C^2拼接的三边或矩形Bezier曲面的控制顶点所要满足的一个显式表示的充分条件。这一结果在使用三向四次箱样条曲面或Loop细分曲面造型,而又需要构造Bezier曲面与之拼接或补洞时,具有理论和实际应用价值。     

图像插值的多结点样条技术

为了获得质量更好的插值图像,提出了用具有紧支集的多结点样条基函数来进行图像插值的新技术,并首先将1维的多结点样条插值算法推广到2维,建立了用于图像数据的插值公式;然后分析了多结点样条插值方法的逼近精度、正则性、插值核函数的频域特性.对逼近精度、正则性、插值核函数频域特性的比较表明,该插值方法优于传统的三次卷积插值方法,实验结果也证实了用多结点样条插值算法重建的图像具有更高的质量.     

三角域上Said-Ball基的推广渐近迭代逼近

目的：如果一组基函数是规范全正（Normalized Totally Positive, abbr. NTP）的,并且对应的配置矩阵是非奇异的,那么由它所生成的参数曲线或张量积曲面具有渐近迭代逼近（progressive iteration approximation, abbr. PIA）性质。为了进一步推广渐近迭代逼近性质的适用范围,本文提出对于一组基函数,如果其对应的配置矩阵不是全正的,那么该基函数也可能具有渐近迭代逼近性质。方法：提出的定理是以基函数具有渐近迭代逼近性质时其对应的配置矩阵所需满足的条件作为理论基础,建立了配置矩阵为严格对角占优或者广义严格对角占优矩阵与基函数具有渐近迭代逼近性质之间的联系。结果：配置矩阵为严格对角占优或者广义严格对角占优矩阵,则相应的三角曲面具有PIA性质或带权PIA性质,即广义PIA性质。数值试验验证了上述理论,并细致地分析了三角域上的低次Said-Ball基,指出了它们具有相应的广义PIA性质。结论：本文将渐近迭代逼近的适用范围推广到三角域上的一般混合基函数。类似三角域上Said-Ball基,本文算法亦可用于研究三角域上的其他各类广义Ball基的PIA性质。     

Degree elevation of unified and extended spline curves

Unified and extended splines （UE-splines）, which unifl and extend polynomial, trigonometric, and hyperbolic B-splines, inherit most properties of B-splines and have some advantages over B-splines. The interest of this paper is the degree elevation algorithm of UE-spline curves and its geometric meaning. Our main idea is to elevate the degree of UE-spline curves one knot interval by one knot interval. First, we construct a new class of basis functions, called bi-order UE-spline basis flmctions which are defined by the integral definition of splines. Then some important properties of bi-order UE-splines are given, especially for tile transformation formulae of the basis functions before and after inserting a knot into the knot vector. Finally, we prove that the degree elevation of UE-spline curves can be interpreted as a process of corner cutting on the control polygons, just as in the manner of B-splines. This degree elevation algorithm possesses strong geometric intuition.