Recursively generated B-spline surfaces on arbitrary topological meshes

This paper describes a method for recursively generating surfaces that approximate points lying-on a mesh of arbitrary topology. The method is presented as a generalization of a recursive bicubic B-spline patch subdivision algorithm. For rectangular control-point meshes, the method generates a standard B-spline surface. For non-rectangular meshes, it generates surfaces that are shown to reduce to a standard B-spline surface except at a small number of points, called extraordinary points. Therefore, everywhere except at these points the surface is continuous in tangent and curvature. At the extraordinary points, the pictures of the surface indicate that the surface is at least continuous in tangent, but no proof of continuity is given. A similar algorithm for biquadratic B-splines is also presented.     

A practical construction of G smooth biquintic B-spline surfaces over arbitrary topology

The motivation of this paper is to develop a local scheme of constructing G¹ smooth B-spline surfaces with single interior knots over arbitrary topology. In this paper, we obtain the conditions of G¹ continuity between two adjacent biquintic B-spline surfaces with interior single knots. These conditions are directly represented by the relevant control points of the two B-spline surfaces. By utilizing these G¹ conditions, we develop the first local scheme of constructing G¹ smooth biquintic B-spline surfaces with interior single knots for arbitrary topological type. The high complexity of deriving the local G¹ scheme is well overwhelmed. The biquintic is the lowest degree for which there exists a local scheme of constructing G¹ smooth B-spline surfaces with interior single knots over arbitrary topology.     

任意散乱点集的B-样条曲面重建

为了解决工业设计中复杂形体的曲面造型问题,提出了一种张量积型的低阶B-样条曲面重建算法。先将采集到的任意拓扑形状的散乱数据点进行三次不同的参数化得到四边形控制网格,然后再采用张量积型的双二次、双三次B-样条进行拟合,在拟合的过程中采用距离函数来控制拟合误差,得到光滑的曲面。运用该方法,直接对初始散乱点集进行重建,方法简单易实施,重建效率高并且重建后的样条曲面自然满足切平面连续。与以往的方法相比,该方法在逆向工程中可以在保证连续性的情况下,得到精准的结果曲面,提高了曲面造型的质量和效率。     

基于块的任意曲面上的纹理合成

一种新的曲面纹理合成技术被提出,它采用求最小割集来解决块拼接时的礁缝走样问题。算法在预处理期对模型的三维网格进行了重建,使其规则并且建立网格点与参数化栅格采样后的图像点一一对应的关系,无论对合成的速度和质量都有很大的提高。提出了在曲面上进行纹理粘贴的算法,对于渲染存在不完整性的自然物体取得了较好的效果。     

Globally optimal surface mapping for surfaces with arbitrary topology

Computing smooth and optimal one-to-one maps between surfaces of same topology is a fundamental problem in computer graphics and such a method provides us a ubiquitous tool for geometric modeling and data visualization. Its vast variety of applications includes shape registration/matching, shape blending, material/data transfer, data fusion, information reuse, etc. The mapping quality is typically measured in terms of angular distortions among different shapes. This paper proposes and develops a novel quasi-conformal surface mapping framework to globally minimize the stretching energy inevitably introduced between two different shapes. The existing state-of-the-art inter-surface mapping techniques only afford local optimization either on surface patches via boundary cutting or on the simplified base domain, lacking rigorous mathematical foundation and analysis. We design and articulate an automatic variational algorithm that can reach the global distortion minimum for surface mapping between shapes of arbitrary topology, and our algorithm is sorely founded upon the intrinsic geometry structure of surfaces. To our best knowledge, this is the first attempt towards numerically computing globally optimal maps. Consequently, our mapping framework offers a powerful computational tool for graphics and visualization tasks such as data and texture transfer, shape morphing, and shape matching.     

Program for B-spline interpolation of surfaces with application to computer tomography

Title of program: RAMFLA Catalogue number: AARO Program obtainable from: CPC Program Library, Queen's University of Belfast, N. Ireland (see application form in this issue) Computer: VAX 11 Digital; Installation: D.K.F.Z. Heidelberg Operating system: VAX/VMS Programming language used: FORTRAN 77 High speed storage required: greater than 256x256, depends on the user choice for the number of surface elements No. of bits in a word: 32 Overlay structure: none Peripherals used: TEKTRONIX display, RAMTEK color display No. of cards in combined program and test deck: 3618 Card punching code: ANSI     

Texture mapping on surfaces of arbitrary topology using norm preserving-based optimization

A simple and yet highly efficient, high-quality texture mapping method for surfaces of arbitrary topology is presented. The new method projects the given surface from the 3D object space into the 2D texture space to identify the 2D texture structure that will be used to texture the surface. The object space to texture space projection is optimized to ensure minimum distortion of the texture mapping process. The optimization is achieved through a commonly used norm preserving minimization process on edges of the surface. The main difference here is, by using an initial value approach, the optimization problem can be set up as a quadratic programming problem and, consequently, solved by a linear least squares method. Three methods to choose a good initial value are presented. Test cases show that the new method works well on surfaces of arbitrary topology, with the exception of surfaces with exceptionally abnormal curvature distribution. Other advantages of the new method include uniformity and seamlessness of the texture mapping process. The new method is suitable for applications that do not require precise texture mapping results but demand highly efficient mapping process such as computer animation or video games.     

Interpolation over arbitrary topology meshes using a two-phase subdivision scheme

The construction of a smooth surface interpolating a mesh of arbitrary topological type is an important problem in many graphics applications. This paper presents a two-phase process, based on a topological modification of the control mesh and a subsequent Catmull-Clark subdivision, to construct a smooth surface that interpolates some or all of the vertices of a mesh with arbitrary topology. It is also possible to constrain the surface to have specified tangent planes at an arbitrary subset of the vertices to be interpolated. The method has the following features: 1) it is guaranteed to always work and the computation is numerically stable, 2) there is no need to solve a system of linear equations and the whole computation complexity is O(K) where K is the number of the vertices, and 3) each vertex can be associated with a scalar shape handle for local shape control. These features make interpolation using Catmull-Clark surfaces simple and, thus, make the new method itself suitable for interactive free-form shape design.     

Generation of high order surfaces over arbitrary polyhedral meshes

A new algorithm for generating high order surfaces over arbitrary meshes will be discussed in this paper. This technique offers more freedom to the designer for controlling the shape of free-form objects in order to meet the various constraints. It also has the advantage of being compatible with B-spline surfaces over rectangular grids of points.     

Diffusion equations over arbitrary triangulated surfaces for filtering and texture applications

In computer graphics, triangular mesh representations of surfaces have become very popular. Compared with parametric and implicit forms of surfaces, triangular mesh surfaces have many advantages, such as easy to render, convenient to store and the ability to model geometric objects with arbitrary topology. In this paper, we are interested in data processing over triangular mesh surfaces through PDEs (partial differential equations). We study several diffusion equations over triangular mesh surfaces, and present corresponding numerical schemes to solve them. Our methods work for triangular mesh surfaces with arbitrary geometry (the angles of each triangle are arbitrary) and topology (open meshes or closed meshes of arbitrary genus). Besides the flexibility, our methods are efficient due to the implicit/semi-implicit time discretization. We finally apply our methods to several filtering and texture applications such as image processing, texture generating and regularization of harmonic maps over triangular mesh surfaces. The results demonstrate the flexibility and effectiveness of our methods.     

Detection of gradual transitions in video sequences using B-spline interpolation

We present a novel technique for detecting the presence of a gradual transition in video sequences and automatically identifying its type. Our scheme focuses on analyzing the characteristics of the underlying special edit effects and estimates actual transitions by polynomial data interpolation. In particular, a B-spline interpolation curve fitting technique is used. We make use of "goodness" of fitting to determine the presence of gradual transitions. Our approach is able to recover the original transition behavior of an edit effect even if it is distorted by various post-processing stages. Our gradual transition detectors have been extensively tested on various genres of real video sequences to evaluate the performance of the proposed algorithms.     

Fine-grained cache deployment scheme for arbitrary topology in ICN

Neural Computing and Applications - Information-centric networking (ICN) is one of the promising candidates for the future network architecture. In-network caching deployed on the routers is the...     

B样条快速求值算法及其在数控插补中的应用

通过对B样条的de Boor-Cox定义式分析,给出了一种基于向量扩展的B样条基函数快速求值算法。该算法能够将k次B样条非零值计算效率提高2k+1倍。该算法用于数控实时插补中的B样条曲线求值求导运算时,可获得比de Boor算法更高的计算效率。     

Modeling connected regions in arbitrary planar point clouds by robust B-spline approximation

This paper presents an algorithm for robustly approximating the boundary of a domain, latent in a planar set of scattered points, by a B-spline curve. The algorithm is characterized by three key features: First, we propose a distance measure, called the Asymmetric Distance (AD), which allows for handling outliers inside the curve and finding the outer boundary or concave hull by specifying very natural parameters like smoothness and accuracy. Second, we provide a solution to the problem of unknown required degrees of freedom by Error-Adaptive Knot Insertion (EAKI). During the iterations of our re-weighted least-squares formulation, we check for regions of high error on the curve and locally increase the degrees of freedom if necessary. Third, we present a method to handle deep and narrow concavities, called Concavity Filling (CF). The curve is examined for areas of large distances to the closest data points. In these regions, we explicitly strap the curve to internal points to force it to bend inwards and fill the concavity. Compared with the state of the art, our method shows fundamental improvement in terms of robustness and applicability to real-world data. For 3D reconstruction of organized and unorganized point clouds, prevalent in robotic RGBD perception, we achieve higher robustness compared to state-of-the-art methods and compression rates up to a factor of 300. We have integrated our code into the Point Cloud Library (PCL) and created a tutorial that guides through the steps of the algorithm (see footnote 1).     

Cubic B-spline curves and surfaces in computer aided geometric design

Representations of cubic and bicubic splines are given, combining the advantages of B-splines with the handiness of Bézier technique. The Bézier points of spline curves and surfaces are found by forming convex combinations of nodes. The given algorithms are suited especially for computer aided geometric design.     

Reducing control points in lofted B-spline surface interpolation using common knot vector determination

A new algorithm for reducing control points in lofted surface interpolation to rows of data points is presented in this paper. The key step of surface lofting is to obtain a set of compatible B-spline curves interpolating each row. Given a set of points and their parameterization, a necessary and sufficient condition is proposed to determine the existence of interpolating B-spline curves defined on a given knot vector. Based on this condition, we first properly construct a common knot vector that guarantees the existence of interpolating B-spline curves to each row of points. Then we calculate a set of interpolating B-spline curves defined on the common knot vector by energy minimization. Using this method, fewer control points are employed while maintaining a visually pleasing shape of the lofted surface. Several experimental results demonstrate the usability and quality of the proposed method.     

Correctness of belief propagation in Gaussian graphical models of arbitrary topology

Graphical models, such as Bayesian networks and Markov random fields, represent statistical dependencies of variables by a graph. Local "belief propagation" rules of the sort proposed by Pearl (1988) are guaranteed to converge to the correct posterior probabilities in singly connected graphs. Recently, good performance has been obtained by using these same rules on graphs with loops, a method we refer to as loopy belief propagation. Perhaps the most dramatic instance is the near Shannon-limit performance of "Turbo codes," whose decoding algorithm is equivalent to loopy propagation. Except for the case of graphs with a single loop, there has been little theoretical understanding of loopy propagation. Here we analyze belief propagation in networks with arbitrary topologies when the nodes in the graph describe jointly gaussian random variables. We give an analytical formula relating the true posterior probabilities with those calculated using loopy propagation. We give sufficient conditions for convergence and show that when belief propagation converges, it gives the correct posterior means for all graph topologies, not just networks with a single loop. These results motivate using the powerful belief propagation algorithm in a broader class of networks and help clarify the empirical performance results.     

图像配准中B样条滤波和GPVE的融合插值算法

针对B样条GPVE插值法和B样条滤波法产生归一化互信息(NMI)测度伪极值点的原因,结合它们导致联合直方图聚散程度的互补效果,提出了各阶B样条滤波和GPVE的融合插值算法。通过图像之间的刚体配准实验,从测度曲线光滑性能和极值点数目方面,对比分析了一阶、三阶、五阶B样条滤波法,B样条GPVE插值法和新提出的融合插值算法。实验结果表明,提出的各阶B样条融合插值算法的配准性能都优于对应阶次B样条滤波法和B样条GPVE插值法。