A two-level approach to implicit surface modeling with compactly supported radial basis functions

We describe a two-level method for computing a function whose zero-level set is the surface reconstructed from given points scattered over the surface and associated with surface normal vectors. The function is defined as a linear combination of compactly supported radial basis functions (CSRBFs). The method preserves the simplicity and efficiency of implicit surface interpolation with CSRBFs and the reconstructed implicit surface owns the attributes, which are previously only associated with globally supported or globally regularized radial basis functions, such as exhibiting less extra zero-level sets, suitable for inside and outside tests. First, in the coarse scale approximation, we choose basis function centers on a grid that covers the enlarged bounding box of the given point set and compute their signed distances to the underlying surface using local quadratic approximations of the nearest surface points. Then a fitting to the residual errors on the surface points and additional off-surface points is performed with fine scale basis functions. The final function is the sum of the two intermediate functions and is a good approximation of the signed distance field to the surface in the bounding box. Examples of surface reconstruction and set operations between shapes are provided.     

Compact implicit surface reconstruction via low-rank tensor approximation

Implicit representations have gained an increasing popularity in geometric modeling and computer graphics due to their ability to represent shapes with complicated geometry and topology. However, the storage requirement, e.g. memory or disk usage, for implicit representations of complex models is relatively large. In this paper, we propose a compact representation for multilevel rational algebraic spline (MRAS) surfaces using low-rank tensor approximation technique, and exploit its applications in surface reconstruction. Given a set of 3D points equipped with oriented normals, we first fit them with an algebraic spline surface defined on a box that bounds the point cloud. We split the bounding box into eight sub-cells if the fitting error is greater than a given threshold. Then for each sub-cell over which the fitting error is greater than the threshold, an offset function represented by an algebraic spline function of low rank is computed by locally solving a convex optimization problem. An algorithm is presented to solve the optimization problem based on the alternating direction method of multipliers (ADMM) and the CANDECOMP/PARAFAC (CP) decomposition of tensors. The procedure is recursively performed until a certain accuracy is achieved. To ensure the global continuity of the MRAS surface, quadratic B-spline weight functions are used to blend the offset functions. Numerous experiments show that our approach can greatly reduce the storage of the reconstructed implicit surface while preserve the fitting accuracy compared with the state-of-the-art methods. Furthermore, our method has good adaptability and is able to produce reconstruction results with high quality.     

Surface reconstruction with higher-order smoothness

This work proposes a method to reconstruct surfaces with higher-order smoothness from noisy 3D measurements. The reconstructed surface is implicitly represented by the zero-level set of a continuous valued embedding function. The key idea is to find a function whose higher-order derivatives are regularized and whose gradient is best aligned with a vector field defined by the input point set. In contrast to methods based on the first-order variation of the function that are biased toward the constant functions and treat the extraction of the isosurface without aliasing artifacts as an afterthought, we impose a higher-order smoothness directly on the embedding function. After solving a convex optimization problem with a multiscale iterative scheme, a triangulated surface can be extracted using the marching cubes algorithm. We demonstrated the proposed method on several data sets obtained from raw laser-scanners and multiview stereo approaches. Experimental results confirm that our approach allows us to reconstruct smooth surfaces from points in the presence of noise, outliers, large missing parts, and very coarse orientation information.     

Hermite variational implicit surface reconstruction

We propose a new technique for reconstructing surfaces from a large set of unorganized 3D data points and their associated normal vectors. The surface is represented as the zero level set of an implicit vol-ume model which fits the data points and normal constraints. Compared with variational implicit sur-faces,we make use of surface normal vectors at data points directly in the implicit model and avoid of introducing manufactured off-surface points. Given n surface point/normal pairs,the proposed method only needs to solve an n×n positive definite linear system. It allows fitting large datasets effectively and robustly. We demonstrate the performance of the proposed method with both globally supported and compactly supported radial basis functions on several datasets.     

Multi-Level Partition of Unity Algebraic Point Set Surfaces

We present a multi-level partition of unity algebraic set surfaces (MPU-APSS) for surface reconstruction which can be represented by either a projection or in an implicit form. An algebraic point set surface (APSS) defines a smooth surface from a set of unorganized points using local moving least-squares (MLS) fitting of algebraic spheres. However, due to the local nature, APSS does not work well for geometry editing and modeling. Instead, our method builds an implicit approximation function for the scattered point set based on the partition of unity approach. By using an octree subdivision strategy, we first adaptively construct local algebraic spheres for the point set, and then apply weighting functions to blend together these local shape functions. Finally, we compute an error-controlled approximation of the signed distance function from the surface. In addition, we present an efficient projection operator which makes our representation suitable for point set filtering and dynamic point resampling. We demonstrate the effectiveness of our unified approach for both surface reconstruction and geometry modeling such as surface completion.     

Implicit and Nonparametric Shape Reconstruction from Unorganized Data Using a Variational Level Set Method

In this paper we consider a fundamental visualization problem: shape reconstruction from an unorganized data set. A new minimal-surface-like model and its variational and partial differential equation (PDE) formulation are introduced. In our formulation only distance to the data set is used as our input. Moreover, the distance is computed with optimal speed using a new numerical PDE algorithm. The data set can include points, curves, and surface patches. Our model has a natural scaling in the nonlinear regularization that allows flexibility close to the data set while it also minimizes oscillations between data points. To find the final shape, we continuously deform an initial surface following the gradient flow of our energy functional. An offset (an exterior contour) of the distance function to the data set is used as our initial surface. We have developed a new and efficient algorithm to find this initial surface. We use the level set method in our numerical computation in order to capture the deformation of the initial surface and to find an implicit representation (using the signed distance function) of the final shape on a fixed rectangular grid. Our variational/PDE approach using the level set method allows us to handle complicated topologies and noisy or highly nonuniform data sets quite easily. The constructed shape is smoother than any piecewise linear reconstruction. Moreover, our approach is easily scalable for different resolutions and works in any number of space dimensions.     

Hermite Radial Basis Functions Implicits

The Hermite radial basis functions (HRBF) implicits reconstruct an implicit function which interpolates or approximates scattered multivariate Hermite data (i.e. unstructured points and their corresponding normals). Experiments suggest that HRBF implicits allow the reconstruction of surfaces rich in details and behave better than previous related methods under coarse and/or non‐uniform samplings, even in the presence of close sheets. HRBF implicits theory unifies a recently introduced class of surface reconstruction methods based on radial basis functions (RBF), which incorporate normals directly in their problem formulation. Such class has the advantage of not depending on manufactured offset‐points to ensure existence of a non‐trivial implicit surface RBF interpolant. In fact, we show that HRBF implicits constitute a particular case of Hermite–Birkhoff interpolation with radial basis functions, whose main results we present here. This framework not only allows us to show connections between the present method and others but also enable us to enhance the flexibility of our method by ensuring well‐posedness of an interesting combined interpolation/regularization approach.     

一种隐式曲面多相图像分割的变分水平集模型

隐式曲面上的图像处理,与曲面的性状和特征息息相关,运用多个函数标记不同区域来进行图像分割计算量大。针对上述问题首先借助遥感图像提出了一种隐式曲面构建方式,利用图像中的高程数据来构建山体曲面模型,进而计算山体区域的曲面面积。其次将基于一个水平集函数的多相图像分割的模型推广到隐式曲面上,并设计了相应的交替方向乘子法,通过求解一个函数的极值实现对图像多个区域的分割,最后多个数值实验对该方法和模型的高效性和鲁棒性进行了验证。     

Computing minimum distance between two implicit algebraic surfaces

The minimum distance computation problem between two surfaces is very important in many applications such as robotics, CAD/CAM and computer graphics. Given two implicit algebraic surfaces, a new method based on the offset technique is presented to compute the minimum distance and a pair of points where the minimum distance occurs. The new method also works where there are an implicit algebraic surface and a parametric surface. Quadric surfaces, tori and canal surfaces are used to demonstrate our new method. When the two surfaces are a general quadric surface and a surface which is a cylinder, a cone or an elliptic paraboloid, the new method can produce two bivariate equations where the degrees are lower than those of any existing method.     

SSD: Smooth Signed Distance Surface Reconstruction

We introduce a new variational formulation for the problem of reconstructing a watertight surface defined by an implicit equation, from a finite set of oriented points; a problem which has attracted a lot of attention for more than two decades. As in the Poisson Surface Reconstruction approach, discretizations of the continuous formulation reduce to the solution of sparse linear systems of equations. But rather than forcing the implicit function to approximate the indicator function of the volume bounded by the implicit surface, in our formulation the implicit function is forced to be a smooth approximation of the signed distance function to the surface. Since an indicator function is discontinuous, its gradient does not exist exactly where it needs to be compared with the normal vector data. The smooth signed distance has approximate unit slope in the neighborhood of the data points. As a result, the normal vector data can be incorporated directly into the energy function without implicit function smoothing. In addition, rather than first extending the oriented points to a vector field within the bounding volume, and then approximating the vector field by a gradient field in the least squares sense, here the vector field is constrained to be the gradient of the implicit function, and a single variational problem is solved directly in one step. The formulation allows for a number of different efficient discretizations, reduces to a finite least squares problem for all linearly parameterized families of functions, and does not require boundary conditions. The resulting algorithms are significantly simpler and easier to implement, and produce results of quality comparable with state‐of‐the‐art algorithms. An efficient implementation based on a primal‐graph octree‐based hybrid finite element‐finite difference discretization, and the Dual Marching Cubes isosurface extraction algorithm, is shown to produce high quality crack‐free adaptive manifold polygon meshes.     

Implicit Fitting Using Radial Basis Functions with Ellipsoid Constraint

Implicit planar curve and surface fitting to a set of scattered points plays an important role in solving a wide variety of problems occurring in computer graphics modelling, computer graphics animation, and computer assisted surgery. The fitted implicit surfaces can be either algebraic or non‐algebraic. The main problem with most algebraic surface fitting algorithms is that the surface fitted to a given data set is often unbounded, multiple sheeted, and disconnected when a high degree polynomial is used, whereas a low degree polynomial is too simple to represent general shapes. Recently, there has been increasing interest in non‐algebraic implicit surface fitting. In these techniques, one popular way of representing an implicit surface has been the use of radial basis functions. This type of implicit surface can represent various shapes to a high level of accuracy. In this paper, we present an implicit surface fitting algorithm using radial basis functions with an ellipsoid constraint. This method does not need to build interior and exterior layers for the given data set or to use information on surface normal but still can fit the data accurately. Furthermore, the fitted shape can still capture the main features of the object when the data sets are extremely sparse. The algorithm involves solving a simple general eigen‐system and a computation of the inverse or psedo‐inverse of a matrix, which is straightforward to implement.     

3D scattered data interpolation and approximation with multilevel compactly supported RBFs

In this paper, we propose a hierarchical approach to 3D scattered data interpolation and approximation with compactly supported radial basis functions. Our numerical experiments suggest that the approach integrates the best aspects of scattered data fitting with locally and globally supported basis functions. Employing locally supported functions leads to an efficient computational procedure, while a coarse-to-fine hierarchy makes our method insensitive to the density of scattered data and allows us to restore large parts of missed data. Given a point cloud distributed over a surface, we first use spatial down sampling to construct a coarse-to-fine hierarchy of point sets. Then we interpolate (approximate) the sets starting from the coarsest level. We interpolate (approximate) a point set of the hierarchy, as an offsetting of the interpolating function computed at the previous level. The resulting fitting procedure is fast, memory efficient, and easy to implement.     

带法向约束的隐式T样条曲线重构

目的 隐式曲线能够描述复杂的几何形状和拓扑结构,而传统的隐式B样条曲线的控制网格需要大量多余的控制点满足拓扑约束。有些情况下,获取的数据点不仅包含坐标信息,还包含相应的法向约束条件。针对这个问题,提出了一种带法向约束的隐式T样条曲线重建算法。方法 结合曲率自适应地调整采样点的疏密,利用二叉树及其细分过程从散乱数据点集构造2维T网格;基于隐式T样条函数提出了一种有效的曲线拟合模型。通过加入偏移数据点和光滑项消除额外零水平集,同时加入法向项减小曲线的法向误差,并依据最优化原理将问题转化为线性方程组求解得到控制系数,从而实现隐式曲线的重构。在误差较大的区域进行T网格局部细分,提高重建隐式曲线的精度。结果 实验在3个数据集上与两种方法进行比较,实验结果表明,本文算法的法向误差显著减小,法向平均误差由10^-3数量级缩小为10^-4数量级,法向最大误差由10^-2数量级缩小为10^-3数量级。在重构曲线质量上,消除了额外零水平集。与隐式B样条控制网格相比,3个数据集的T网格的控制点数量只有B样条网格的55.88%、39.80%和47.06%。结论 本文算法能在保证数据点精度的前提下,有效降低法向误差,消除了额外的零水平集。与隐式B样条曲线相比,本文方法减少了控制系数的数量,提高了运算速度。     

Tetrahedra Based Adaptive Polygonization of Implicit Surface Patches

This paper presents a tetrahedra based adaptive polygonization technique for tessellating implicit surface patches. An implicit surface patch is defined as an implicit surface bounded by its intersections with a set of clipping surfaces and which lies within an enclosing tetrahedron. To obtain the polygonization of an implicit surface patch, the tetrahedron containing the patch is adaptively subdivided into smaller tetrahedra according to the criteria introduced in the paper. The result is a set of tetrahedra each containing a facet approximating the surface. The intersections between the facets and the clipping surfaces are used to locate the surface patch boundary. Ambiguous results in generating the facets for highly curved surfaces or surfaces with singular points are also addressed. The result of the polygonization is a set of triangular facets that can be used for visualization and numerical analysis. The proposed method is also suitable for locating the intersection of two implicit surfaces.     

Trimming local and global self-intersections in offset curves/surfaces using distance maps

A robust and efficient algorithm for trimming both local and global self-intersections in offset curves and surfaces is presented. Our scheme is based on the derivation of a rational distance map between the original curve or surface and its offset. By solving a bivariate polynomial equation for an offset curve or a system of three polynomial equations for an offset surface, all local and global self-intersection regions in offset curves or surfaces can be detected. The zero-set of polynomial equation(s) corresponds to the self-intersection regions. These regions are trimmed by projecting the zero-set into an appropriate parameter space. The projection operation simplifies the analysis of the zero-set, which makes the proposed algorithm numerically stable and efficient. Furthermore, in a post-processing step, a numerical marching method is employed, which provides a highly precise scheme for self-intersection elimination in both offset curves and surfaces. The effectiveness of our approach is demonstrated using several experimental results.     

隐式曲面的多分辨率法向网格逼近

法向网格是一种新型的曲面多分辨率描述方式，其中每个层次都可以表示为其前一个粗糙层次的法向偏移．文中提出一种基于法向网格表示的隐式曲面多分辨率网格逼近算法．首先通过基于空间剖分技术的多边形化算法获得隐式曲面的粗糙逼近网格，并利用网格均衡化方法对粗糙网格进行优化，消除其中的狭长三角形；然后利用法向细分规则迭代地对网格中的三角面片进行细分，并利用区间算术技术沿法向方向对隐式曲面进行逼近．最终生成的隐式曲面分片线性逼近网格为法向网格．该逼近网格为隐式曲面提供了一种多分辨率表示，网格具有细分连通性，其数据量较传统的多边形化算法所生成的网格有大幅度的压缩．该算法可用于隐式曲面的多级绘制、累进传输及相关数字几何处理．     

Higher-Order Level-Set Method and Its Application in Biomolecular Surfaces Construction

We present a general framework for a higher-order spline level-set(HLS) method and apply this to biomolecule surfaces construction. Starting from a first order energy functional,we obtain a general level set formulation of geometric partial differential equation,and provide an efficient approach to solving this partial differential equation using a C2 spline basis. We also present a fast cubic spline interpolation algorithm based on convolution and the Z-transform,which exploits the local relationship of interpolatory cubic spline coefficients with respect to given function data values. One example of our HLS method is demonstrated,which is the construction of biomolecule surfaces(an implicit solvation interface) with their individual atomic coordinates and solvated radii as prerequisites.     

Reconstructing Animated Meshes from Time‐Varying Point Clouds

In this paper, we describe a novel approach for the reconstruction of animated meshes from a series of time‐deforming point clouds. Given a set of unordered point clouds that have been captured by a fast 3‐D scanner, our algorithm is able to compute coherent meshes which approximate the input data at arbitrary time instances. Our method is based on the computation of an implicit function in ?⁴ that approximates the time‐space surface of the time‐varying point cloud. We then use the four‐dimensional implicit function to reconstruct a polygonal model for the first time‐step. By sliding this template mesh along the time‐space surface in an as‐rigid‐as‐possible manner, we obtain reconstructions for further time‐steps which have the same connectivity as the previously extracted mesh while recovering rigid motion exactly. The resulting animated meshes allow accurate motion tracking of arbitrary points and are well suited for animation compression. We demonstrate the qualities of the proposed method by applying it to several data sets acquired by real‐time 3‐D scanners.     

Evolution of T-spline level sets for meshing non-uniformly sampled and incomplete data

Given a large set of unorganized point sample data, we propose a new framework for computing a triangular mesh representing an approximating piecewise smooth surface. The data may be non-uniformly distributed, noisy, and may contain holes. This framework is based on the combination of two types of surface representations, triangular meshes and T-spline level sets, which are implicit surfaces defined by refinable spline functions allowing T-junctions. Our method contains three main steps. Firstly, we construct an implicit representation of a smooth (C ² in our case) surface, by using an evolution process of T-spline level sets, such that the implicit surface captures the topology and outline of the object to be reconstructed. The initial mesh with high quality is obtained through the marching triangulation of the implicit surface. Secondly, we project each data point to the initial mesh, and get a scalar displacement field. Detailed features will be captured by the displaced mesh. Finally, we present an additional evolution process, which combines data-driven velocities and feature-preserving bilateral filters, in order to reproduce sharp features. We also show that various shape constraints, such as distance field constraints, range constraints and volume constraints can be naturally added to our framework, which is helpful to obtain a desired reconstruction result, especially when the given data contains noise and inaccuracies.     

An analytical representation of conformal mapping for genus-zero implicit surfaces and its application to surface shape similarity assessment

This paper develops an analytical representation of conformal mapping for genus-zero implicit surfaces based on algebraic polynomial functions, and its application to surface shape similarity assessment. Generally, the conformal mapping often works as a tool of planar or spherical parameterization for triangle mesh surfaces. It is further exploited for implicit surface matching in this study. The method begins with discretizing one implicit surface by triangle mesh, where a discrete harmonic energy model related to both the mesh and the other implicit surface is established based on a polynomial-function mapping. Then both the zero-center constraint and the landmark constraints are added to the model to ensure the uniqueness of mapping result with the Möbius transformation. By searching optimal polynomial coefficients with the Lagrange–Newton method, the analytical representation of conformal mapping is obtained, which reveals all global and continuous one-to-one correspondent point pairs between two implicit surfaces. Finally, a shape similarity assessment index for (two) implicit surfaces is proposed through calculating the differences of all the shape index values among those corresponding points. The proposed analytical representation method of conformal mapping and the shape assessment index are both verified by the simulation cases for the closed genus-zero implicit surfaces. Experimental results show that the method is effective for genus-zero implicit surfaces, which will offer a new way for object retrieval and manufactured surface inspection.