改进的Seifert算法的纽结可视化

纽结或链环的Seifert曲面是可定向曲面,关于该曲面的原理图可以在纽结理论的教材上查阅到,但是仅知道这些,想要去了解它们的形状和结构,仍然是很困难的.将讨论纽结和链环的可视化算法,包括Seifert算法和基于编织命名法的可视化算法,最后,给出了改进后的Seifert算法,另外,对纽结和链环生成的可定向闭曲面的亏格也做了进一步地研究.     

一种B样条表面插值控制点的缩减方法

研究了从给定节点向量中选择节点进行B样条曲线插值的方法，并将此方法应用到行数据点不相同的B样条曲面插值，得到了一个通过对行节点矢量调整传递的曲面插值方法，理论分析和实验表明该方法可大量减少曲面控制点的数目．     

Iterative two-step genetic-algorithm-based method for efficient polynomial B-spline surface reconstruction

Surface reconstruction is a very challenging problem arising in a wide variety of applications such as CAD design, data visualization, virtual reality, medical imaging, computer animation, reverse engineering and so on. Given partial information about an unknown surface, its goal is to construct, to the extent possible, a compact representation of the surface model. In most cases, available information about the surface consists of a dense set of (either organized or scattered) 3D data points obtained by using scanner devices, a today’s prevalent technology in many reverse engineering applications. In such a case, surface reconstruction consists of two main stages: (1) surface parameterization and (2) surface fitting. Both tasks are critical in order to recover surface geometry and topology and to obtain a proper fitting to data points. They are also pretty troublesome, leading to a high-dimensional nonlinear optimization problem. In this context, present paper introduces a new method for surface reconstruction from clouds of noisy 3D data points. Our method applies the genetic algorithm paradigm iteratively to fit a given cloud of data points by using strictly polynomial B-spline surfaces. Genetic algorithms are applied in two steps: the first one determines the parametric values of data points; the later computes surface knot vectors. Then, the fitting surface is calculated by least-squares through either SVD (singular value decomposition) or LU methods. The method yields very accurate results even for surfaces with singularities, concavities, complicated shapes or nonzero genus. Six examples including open, semi-closed and closed surfaces with singular points illustrate the good performance of our approach. Our experiments show that our proposal outperforms all previous approaches in terms of accuracy and flexibility.     

Lofted B-spline surface interpolation by linearly constrained energy minimization

This paper proposes a new approach for lofted B-spline surface interpolation to serial contours, where the number of points varies from contour to contour. The approach first finds a common knot vector consisting of fewer knots that contain enough degrees of freedom to guarantee the existence of a B-spline curve interpolating each contour. Then, it computes from the contours a set of compatible B-spline curves defined on the knot vector by adopting B-spline curve interpolation based on linearly constrained energy minimization. Finally, it generates a B-spline surface interpolating the curves via B-spline surface lofting. As the energy functional is quadratic, the energy minimization problem leads to that of solving a linear system. The proposed approach is efficient in computation and can realize more efficient data reduction than previous approaches while providing visually pleasing B-spline surfaces. Moreover, the approach works well on measured data with noise. Some experimental results demonstrate its usefulness and quality.     

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.     

The parametrized complexity of knot polynomials

We study the parametrized complexity of the knot (and link) polynomials known as Jones polynomials, Kauffman polynomials and HOMFLY polynomials. It is known that computing these polynomials is hard in general. We look for parameters of the combinatorial presentation of knots and links which make the computation of these polynomials to be fixed parameter tractable, i.e., in the complexity class FPT. If the link is explicitly presented as a closed braid, the number of its strands is known to be such a parameter. In a generalization thereof, if the link is explicitly presented as a combination of compositions and rotations of k-tangles the link is called k-algebraic, and its algebraicity k is such a parameter. The previously known proofs that, for this parameter, the link polynomials are in FPT uses the so called skein modules, and is algebraic in its nature. Furthermore, it is not clear how to find such an algebraic presentation from a given link diagram. We look at the treewidth of two combinatorial presentation of links: the crossing diagram and its shading diagram, a signed graph. We show that the treewidth of these two presentations and the algebraicity of links are all linearly related to each other. Furthermore, we characterize the k-algebraic links using the pathwidth of the crossing diagram. Using this, we can apply algorithms for testing fixed treewidth to find k-algebraic presentations in polynomial time. From this we can conclude that also treewidth and pathwidth are parameters of link diagrams for which the knot polynomials are FPT. For the Kauffman and Jones polynomials (but not for the HOMFLY polynomials) we get also a different proof for FPT via the corresponding result for signed Tutte polynomials.     

Single-knot wavelets for non-uniform B-splines

We propose a flexible and efficient wavelet construction for non-uniform B-spline curves and surfaces. The method allows to remove knots in arbitrary order minimizing the displacement of control points when a knot is re-inserted. Geometric detail subtracted from a shape by knot removal is represented by an associated wavelet coefficient replacing one of the control points at a coarser level of detail. From the hierarchy of wavelet coefficients, perfect reconstruction of the original shape is obtained. Both knot removal and insertion have local impact. Wavelet synthesis and analysis are both computed in linear time, based on the lifting scheme for biorthogonal wavelets. The method is perfectly suited for multiresolution surface editing, progressive transmission, and compression of spline curves and surfaces.     

B样条曲面的双向插值造型算法

基于Coons-Gordon造型原理,研究了插值两族相交截面线采样点的B样条曲面双向插值造型算法。参数化各采样点并计算每条截面线的节点矢量,估算每条截面线对应的曲面参数,根据每条截面线的节点分布以及另一族截面线对应的曲面参数统一节点矢量。分别插值两族截面线采样点及其公共点得到三张B样条曲面,其布尔和即为插值两族截面线采样点的B样条插值曲面。实例表明,得到的双向插值曲面控制顶点数少,光顺性好。     

基于极小化二阶导矢确定节点

构造参数拟合曲线的关键问题之一是为每个数据点指定一个参数值（节点）。提出了一种确定节点的新方法。对于每个数据点,新方法由相邻的三个数据点构造一条二次多项式曲线,二次曲线的节点通过极小化其二阶导矢的平方确定。两个相邻数据点间的节点区间由两条二次曲线确定。为使节点计算公式能有效反映出相邻数据点的变化情况,新方法改进了修正弦长方法并应用于节点计算。新方法是一个局部化方法,因此适合于曲线曲面的交互设计。实验结果说明,新方法比其他节点计算方法有效。     

Image surface approximation with irregular samples

A method to approximate image surfaces using irregular samples is proposed. Experimental results show that a high compression ratio can be achieved for simple or complicated images. A method accounting for the three-dimensional effects is proposed as a way of selecting the irregular samples from the image. Approximation spline knots are chosen along the contours, and the knot replacement is sensitive to the curvature along contours and the density of contours in the near neighborhood. In general, the proposed method was shown to reduce the reconstruction error both qualitatively and quantitatively, and can be used to model the image surface for the purpose of data compression and representation. This approach retains key features in images and throws away redundant data     

Smooth surface approximation to serial cross-sections

The reconstruction of the surface model of an object from 2D cross-sections plays an important role in many applications. In this paper, we present a method for surface approximation to a given set of 2D contours. The resulting surface is represented by a bicubic closed B-spline surface with C² continuity. The method performs the skinning of intermediate contour curves represented by cubic B-spline curves on a common knot vector, each of which is fitted to its contour points within a given accuracy. In order to acquire more compact representation for the surface, the method includes an algorithm for reducing the number of knots in the common knot vector. The proposed method provides a smooth and accurate surface model, yet realizes efficient data reduction. Some experimental results are given using synthetic and MRI data.     

Elitist clonal selection algorithm for optimal choice of free knots in B-spline data fitting

Data fitting with B-splines is a challenging problem in reverse engineering for CAD/CAM, virtual reality, data visualization, and many other fields. It is well-known that the fitting improves greatly if knots are considered as free variables. This leads, however, to a very difficult multimodal and multivariate continuous nonlinear optimization problem, the so-called knot adjustment problem. In this context, the present paper introduces an adapted elitist clonal selection algorithm for automatic knot adjustment of B-spline curves. Given a set of noisy data points, our method determines the number and location of knots automatically in order to obtain an extremely accurate fitting of data. In addition, our method minimizes the number of parameters required for this task. Our approach performs very well and in a fully automatic way even for the cases of underlying functions requiring identical multiple knots, such as functions with discontinuities and cusps. To evaluate its performance, it has been applied to three challenging test functions, and results have been compared with those from other alternative methods based on AIS and genetic algorithms. Our experimental results show that our proposal outperforms previous approaches in terms of accuracy and flexibility. Some other issues such as the parameter tuning, the complexity of the algorithm, and the CPU runtime are also discussed.     

Detection of loops and singularities of surface intersections

Two surface patches intersecting each other generally at a set of points (singularities), form open curves or closed loops. While open curves are easily located by following the boundary curves of the two patches, closed loops and singularities pose a robustness challenge since such points or loops can easily be missed by any subdivision or marching-based intersection algorithms, especially when the intersecting patches are flat and ill-positioned. This paper presents a topological method to detect the existence of closed loops or singularities when two flat surface patches intersect each other. The algorithm is based on an oriented distance function defined between two intersecting surfaces. The distance function is evaluated in a vector field to identify the existence of singular points of the distance function since these singular points indicate possible existence of closed intersection loops. The algorithm detects the existence rather than the absence of closed loops and singularities. This algorithm requires general C² parametric surfaces.     

基于差分进化算法的B 样条曲线曲面拟合

应用B 样条曲线曲面拟合内在形状带有间断或者尖点的数据时,最小二乘法得到的 拟合结果往往在间断和尖点处误差较大,原因在于最小二乘法将拟合函数B 样条的节点固定。本 文在利用3 次B 样条曲线和曲面拟合数据时,应用差分进化算法设计出一种能够自适应地设置B 样条节点的方法,同时对节点的数量和位置进行优化,使得B 样条拟合曲线曲面在间断和尖点处 产生拟多重节点,实现高精度地拟合采样于带有间断或尖点的曲线和曲面数据。     

B样条曲线的节点插入问题及两个新算法

Ｂｏｅｈｍ算法和Ｏｓｌｏ算法是Ｂ产条曲线的节点插入的经典算法，它们可以有效地将节眯插入到端点插值（Ｅｎｄｏｐｏｉｎｔ－ｉｎｔｅｒｏｌａｔｉｎｇ）Ｂ样条曲线，但是，对于其它的Ｂ样条曲线而言，当插入靠近节眯矢量两端附近的节点时，所有的经典算法都将出错，本文提出了两个节点插入新算法，它们可以解决节插入的经典算法中的问题，能够将任意节点插入到各种Ｂ样条曲线之中，它们的另一个重要用途是可以用于各种Ｂ样条曲线     

Shadow-driven 4D haptic visualization

Just as we can work with two-dimensional floor plans to communicate 3D architectural design, we can exploit reduced-dimension shadows to manipulate the higher-dimensional objects generating the shadows. In particular, by taking advantage of physically reactive 3D shadow-space controllers, we can transform the task of interacting with 4D objects to a new level of physical reality. We begin with a teaching tool that uses 2D knot diagrams to manipulate the geometry of 3D mathematical knots via their projections; our unique 2D haptic interface allows the user to become familiar with sketching, editing, exploration, and manipulation of 3D knots rendered as projected imageson a 2D shadow space. By combining graphics and collision-sensing haptics, we can enhance the 2D shadow-driven editing protocol to successfully leverage 2D pen-and-paper or blackboard skills. Building on the reduced-dimension 2D editing tool for manipulating 3D shapes, we develop the natural analogy to produce a reduced-dimension 3D tool for manipulating 4D shapes. By physically modeling the correct properties of 4D surfaces, their bending forces, and their collisions in the 3D haptic controller interface, we can support full-featured physical exploration of 4D mathematical objects in a manner that is otherwise far beyond the experience accessible to human beings. As far as we are aware, this paper reports the first interactive system with force-feedback that provides "4D haptic visualization" permitting the user to model and interact with 4D cloth-like objects.     

Knot calculation for spline fitting via sparse optimization

Curve fitting with splines is a fundamental problem in computer-aided design and engineering. However, how to choose the number of knots and how to place the knots in spline fitting remain a difficult issue. This paper presents a framework for computing knots (including the number and positions) in curve fitting based on a sparse optimization model. The framework consists of two steps: first, from a dense initial knot vector, a set of active knots is selected at which certain order derivative of the spline is discontinuous by solving a sparse optimization problem; second, we further remove redundant knots and adjust the positions of active knots to obtain the final knot vector. Our experiments show that the approximation spline curve obtained by our approach has less number of knots compared to existing methods. Particularly, when the data points are sampled dense enough from a spline, our algorithm can recover the ground truth knot vector and reproduce the spline.     

Adaptive knot placement using a GMM-based continuous optimization algorithm in B-spline curve approximation

One of the key problems in using B-splines successfully to approximate an object contour is to determine good knots. In this paper, the knots of a parametric B-spline curve were treated as variables, and the initial location of every knot was generated using the Monte Carlo method in its solution domain. The best km knot vectors among the initial candidates were searched according to the fitness. Based on the initial parameters estimated by an improved k-means algorithm, the Gaussian Mixture Model (GMM) for every knot was built according to the best km knot vectors. Then, the new generation of the population was generated according to the Gaussian mixture probabilistic models. An iterative procedure repeating these steps was carried out until a termination criterion was met. The GMM-based continuous optimization algorithm could determine the appropriate location of knots automatically. A set of experiments was then implemented to evaluate the performance of the new algorithm. The results show that the proposed method achieves better approximation accuracy than methods based on artificial immune system, genetic algorithm or squared distance minimization (SDM).     

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.     

Subdivision Surfaces with Creases and Truncated Multiple Knot Lines

We deal with subdivision schemes based on arbitrary degree B‐splines. We focus on extraordinary knots which exhibit various levels of complexity in terms of both valency and multiplicity of knot lines emanating from such knots. The purpose of truncated multiple knot lines is to model creases which fair out. Our construction supports any degree and any knot line multiplicity and provides a modelling framework familiar to users used to B‐splines and NURBS systems.