Stable fitting of 2D curves and 3D surfaces by implicit polynomials

This work deals with fitting 2D and 3D implicit polynomials (IPs) to 2D curves and 3D surfaces, respectively. The zero-set of the polynomial is determined by the IP coefficients and describes the data. The polynomial fitting algorithms proposed in this paper aim at reducing the sensitivity of the polynomial to coefficient errors. Errors in coefficient values may be the result of numerical calculations, when solving the fitting problem or due to coefficient quantization. It is demonstrated that the effect of reducing this sensitivity also improves the fitting tightness and stability of the proposed two algorithms in fitting noisy data, as compared to existing algorithms like the well-known 3L and gradient-one algorithms. The development of the proposed algorithms is based on an analysis of the sensitivity of the zero-set to small coefficient changes and on minimizing a bound on the maximal error for one algorithm and minimizing the error variance for the second. Simulation results show that the proposed algorithms provide a significant reduction in fitting errors, particularly when fitting noisy data of complex shapes with high order polynomials, as compared to the performance obtained by the above mentioned existing algorithms.     

Fitting unorganized point clouds with active implicit B-spline curves

In computer-aided geometric design and computer graphics, fitting point clouds with a smooth curve (known as curve reconstruction) is a widely investigated problem. In this paper, we propose an active model to solve the curve reconstruction problem, where the point clouds are approximated by an implicit B-spline curve, i.e., the zero set of a bivariate tensor-product B-spline function. We minimize the geometric distance between the point clouds and the implicit B-spline curve and an energy term (or smooth term) which helps to extrude the possible extra branches of the implicit curve. In each step of the iteration, the trust region algorithm in optimization theory is applied to solve the corresponding minimization problem. We also discuss the proper choice of the initial shape of the approximation curve. Examples are provided to illustrate the effectiveness and robustness of our algorithm. The examples show that the proposed algorithm is capable of handling point clouds with complicated topologies.     

Orthogonal distance fitting of implicit curves and surfaces

Dimensional model fitting finds its applications in various fields of science and engineering and is a relevant subject in computer/machine vision and coordinate metrology. In this paper, we present two new fitting algorithms, distance-based and coordinate-based algorithm, for implicit surfaces and plane curves, which minimize the square sum of the orthogonal error distances between the model feature and the given data points. Each of the two algorithms has its own advantages and is to be purposefully applied to a specific fitting task, considering the implementation and memory space cost, and possibilities of observation weighting. By the new algorithms, the model feature parameters are grouped and simultaneously estimated in terms of form, position, and rotation parameters. The form parameters determine the shape of the model feature and the position/rotation parameters describe the rigid body motion of the model feature. The proposed algorithms are applicable to any kind of implicit surface and plane curve. In this paper, we also describe algorithm implementation and show various examples of orthogonal distance fit     

Multiple degree elevation and constrained multiple degree reduction for DP curves and surfaces

In this paper, the problem of single and multiple degree elevation and reduction for DP curves and surfaces is considered and expressed in matrix representations. Using monomial matrix representations of the univariate DP polynomials, single and multiple degree elevation matrices can be derived by minor extension of this monomial matrix. Given this result, matrices of constrained single and multiple degree reduction can be readily obtained. Finally, important and sufficient conditions for degree reduction can also be found from these resulting matrices.     

Trimming implicit surfaces

Algorithms for trimming implicit surfaces yielding surface sheets and stripes are presented. These two-dimensional manifolds with boundaries result from set-theoretic operations on an implicit surface and a solid or another implicit surface. The algorithms generate adaptive polygonal approximation of the trimmed surfaces by extending our original implicit surface polygonization algorithm. The presented applications include modeling several spiral shaped surface sheets and stripes (based on M. Eschers artworks) and extraction of ridges on implicit surfaces. Another promising application of the presented algorithms is modeling heterogeneous objects as implicit complexes.     

Interactive 3D garment design with constrained contour curves and style curves

This paper presents interactive techniques to design 3D garments conveniently and precisely with constrained contour curves and style curves. Contour curves, including silhouette curves and cross section curves, are used for garment surface modeling. Style curves, including seam lines, dart lines, notch lines and grain lines, are introduced for designing patterns on the triangular garment surfaces. Contour curves are extracted automatically from the boundaries of garment sub-meshes. The definitions and resolving rules of various constraints are introduced for editing the contour curves conveniently. Style curves are generated by projecting control points onto 3D garment triangular surfaces. In order to draw the style curves validly, some constraints are also introduced according to the craft requirements of pattern design. Furthermore, the effects of style curves in pattern flattening are analyzed, which can guide the designer to draw style curves more reasonably and enhance the pattern design quality. Finally, some examples are given to show that our methods can make the 3D garment design more flexible and friendly, and style curves can be applied into design patterns on 3D triangular surface for shoes, toys and so on.     

Describing complicated objects by implicit polynomials

This paper introduces and focuses on two problems. First is the representation power of closed implicit polynomials of modest degree for curves in 2-D images and surfaces in 3-D range data. Super quadrics are a small subset of object boundaries that are well fitted by these polynomials. The second problem is the stable computationally efficient fitting of noisy data by closed implicit polynomial curves and surfaces. The attractive features of these polynomials for Vision is discussed     

Linear programming fitting of implicit polynomials

A new implicit polynomial (IP) fitting method is presented. It provides a different way of viewing the IP fitting problem from those of the nonlinear optimization approaches. It requires less computation, and can be done automatically or interactively. Linear programming is used to do the fitting. The approach can incorporate a variety of distance measures and global geometric constraints     

Using implicit equations of parametric curves and surfaces without computing them: Polynomial algebra by values

The availability of the implicit equation of a plane curve or of a 3D surface can be very useful in order to solve many geometric problems involving the considered curve or surface: for example, when dealing with the point position problem or answering intersection questions. On the other hand, it is well known that in most cases, even for moderate degrees, the implicit equation is either difficult to compute or, if computed, the high degree and the big size of the coefficients makes extremely difficult its use in practice.We will show that, for several problems involving plane curves, 3D surfaces and some of their constructions (for example, offsets), it is possible to use the implicit equation (or, more precisely, its properties) without needing to explicitly determine it. We replace the computation of the implicit equation with the evaluation of the considered parameterizations in a set of points. We then translate the geometric problem in hand, into one or several generalized eigenvalue problems on matrix pencils (depending again on several evaluations of the considered parameterizations).This is the so-called “polynomial algebra by values” approach where the huge polynomial equations coming from Elimination Theory (e.g., using resultants) are replaced by big structured and sparse numerical matrices. For these matrices there are well-known numerical techniques allowing to provide the results we need to answer the geometric questions on the considered curves and surfaces.     

Polygonization of implicit surfaces

This paper discusses a numerical technique that approximates an implicit surface with a polygonal representation. The implicit function is adaptively sampled as it is surrounded by a spatial partitioning. The partitioning is represented by an octree, which may either converge to the surface or track it. A piecewise polygonal representation is derived from the octree.

The technique is insensitive to the complexity of the implicit function, allowing the designer great latitude. With a polygonal representation of the surface available, certain computational economies result; in particular, the roots to the function need not be solved each time the surface is rendered.     

Truchet curves and surfaces

Spanning tree contours, a special class of Truchet contour based upon a random spanning tree of a Truchet tiling's underlying graph, are presented. This spanning tree method is extended to three dimensions to define a Truchet surface with properties similar to its two-dimensional counterpart. Both contour and surface are smooth, have known minimum curvature and known maximum distance to interior points, and high ratios of perimeter to area and area to volume, respectively. Expressions for calculating contour length, contour area, surface area and surface volume directly from the spanning tree are given.     

A general method to derive implicit equations of curves and surfaces using interlineation and interflation of functions

A general method is proposed to derive equations of irregular curves O _D (x, y) = 0 and of irregular surfaces O _G (x, y, z) =0 in implicit form, where the functions O _D (x, y) and O _G (x, y, z) belong to a prescribed differentiability class. The method essentially involves interlineation and interflation of functions. An example is considered.     

Plus curves and surfaces

The formulations for parametric curves and surfaces that are based on control points are revised to use control lines and control planes instead. Curves defined by control lines are called control-line curves or plus curves, and surfaces defined by control planes are called control-plane surfaces or plus surfaces; the plus implies that in addition to the control points, gradient vectors at the control points are used to design curves and surfaces. The new curve and surface formulations provide more flexibility than traditional formulations in geometric design. Properties of plus curves and surfaces are investigated and an application of plus surfaces in smooth parametric representation of polygon meshes is introduced.     

Visualizing nonmanifold and singular implicit surfaces with point clouds

We use octree spatial subdivision to generate point clouds on complex nonmanifold implicit surfaces in order to visualize them. The new spatial subdivision scheme only uses point sampling and an interval exclusion test. The algorithm includes a test for pruning the resulting plotting nodes so that only points in the closest nodes to the surface are used in rendering. This algorithm results in improved image quality compared to the naive use of intervals or affine arithmetic when rendering implicit surfaces, particularly in regions of high curvature. We discuss and compare CPU and GPU versions of the algorithm. We can now render nonmanifold features such as rays, ray-like tubes, cusps, ridges, thin sections that are at arbitrary angles to the octree node edges, and singular points located within plot nodes, all without artifacts. Our previous algorithm could not render these without severe aliasing. The algorithm can render the self-intersection curves of implicit surfaces by exploiting the fact that surfaces are singular where they self-intersect. It can also render the intersection curves of two implicit surfaces. We present new image space and object space algorithms for rendering these intersection curves as contours on one of the surfaces. These algorithms are better at rendering high curvature contours than our previous algorithms. To demonstrate the robustness of the node pruning algorithm we render a number of complex implicit surfaces such as high order polynomial surfaces and Gaussian curvature surfaces. We also compare the algorithm with ray casting interms of speed and image quality. For the surfaces presented here, the point clouds can be computed in seconds to minutes on atypical Intel based PC. Once this is done, the surfaces can be rendered at much higher frame rates to allow some degree of interactive visualization.     

Estimation of planar curves, surfaces, and nonplanar space curvesdefined by implicit equations with applications to edge and range imagesegmentation

The author addresses the problem of parametric representation and estimation of complex planar curves in 2-D surfaces in 3-D, and nonplanar space curves in 3-D. Curves and surfaces can be defined either parametrically or implicitly, with the latter representation used here. A planar curve is the set of zeros of a smooth function of two variables x-y, a surface is the set of zeros of a smooth function of three variables x-y-z, and a space curve is the intersection of two surfaces, which are the set of zeros of two linearly independent smooth functions of three variables x-y-z For example, the surface of a complex object in 3-D can be represented as a subset of a single implicit surface, with similar results for planar and space curves. It is shown how this unified representation can be used for object recognition, object position estimation, and segmentation of objects into meaningful subobjects, that is, the detection of `interest regions' that are more complex than high curvature regions and, hence, more useful as features for object recognition     

Technologies for implicit surfaces sampling with particle systems

Point-based surface has been widely used in computer graphics for modeling,animation,visualization,simulation of liquid and so on.Furthermore,particle-based approach can distribute the surface sampling points and control its parameters according to the needs of the application.In this paper,we examine several kinds of algorithms presented over the last decades,with the main focus on particle sampling technologies for implicit surface.Therefore,we classify various algorithms into categories,describe main ideas behind each categories,and compare the advantages and shortcomings of the algorithms in each category.     

曲率约束的隐式曲面三角网格化

提出一种有效的隐式曲面三角网格化算法。从隐式曲面上的一个种子点开始,生成网格的边界作为扩张多边形,且该多边形最小角对应的顶点为扩张点,计算从扩张点处欲生成的三角网格,为了防止新生成的三角网格和已经存在的三角网格重叠,要进行冲突检测。在隐式曲面三角网格化的过程中,扩张多边形是不断变化的,需要重复上述步骤,直至没有扩张多边形时结束。该算法分别应用于解析隐式曲面和变分隐式曲面的三角网格化。实验结果表明,该算法不需要重新网格化的步骤,生成的三角网格具有较高的质量,且三角网格随曲率适应性变化,因此说明了该算法的有效性。     

带形状参数的四次Bezier曲线曲面

提出一种新的含参数的四次多项式基函数,四次Bemstein基函数是它的特例,给出其与四次Bemstein基的转换矩阵。分析了该组基函数的性质,定义了带有形状参数的四次Bezier曲线曲面,它们具有四次Bezier曲线曲面的特性,且当参数均取1时即为四次Bezier曲线曲面。对于给定的控制顶点,可以通过改变形状参数的值整体或局部调控曲线曲面的形状。实例表明,该方法应用于曲线曲面设计是有效的。