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.     

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.     

From laser point clouds to surfaces: Statistical nonparametric methods for three-dimensional reconstruction

This paper presents a new method for the reconstruction of three-dimensional objects surveyed with a terrestrial laser scanner. The method is a 2.5D surface modelling technique which is based on the application of statistical nonparametric regression methods for point cloud regularization and mesh smoothing, specifically the kernel-smoothing techniques. The proposed algorithm was tested in a theoretical model-simulations being carried out with the aim of evaluating the ability of the method to filter random noise and oscillations related to the acquisition of data during the fieldwork-and the results were satisfactory. The method was then applied, as a reverse engineering tool, to real-world data in the field of naval construction. A precise solution to the problem of obtaining realistic surfaces and sections of large industrial objects from laser 3D point clouds is provided, which has proved to be efficient in terms of computational time.     

An algorithm for calculating the similarity measures of surfaces represented as point clouds

The problem of estimating the similarity of surfaces represented as point clouds is studied. An approach is suggested to the comparison of such surfaces based on the surface approximation by piecewise-linear functions of two variables in the Delaunay triangulations. The approach is based on the developed algorithm for comparison of the functions of two variables specified on various irregular sets of points. Possible applications of this algorithm were considered such as the problems of 3D portraits comparison, e.g., problems of estimation of facial asymmetry and dynamics of lower jaw movements on the basis of a 3D video sequence of models. The performed experiments confirmed the correctness, validity, and computational efficiency of the proposed algorithm.     

Visualizing soil surfaces and crop residues

A test case for visualizing field and laboratory data pertaining to soil erosion and infiltration is examined. Several visualization techniques were used to derive image data from an experiment in which the effect of a sequence of five rainfalls on a laboratory-formed soil surface was measured. The base data are millimeter-resolution elevation models generated using a laser-scanning device. The surfaces generated by the laser scanner are visualized as perspective views. Changes in the soil surface with cumulative rainfall are examined by visualizing differences between successive laser-scanned surfaces. The modeling of straw coverage, which can influence infiltration, overland flow, and erosion, using a random process model is discussed     

Fitting curves and surfaces with constrained implicit polynomials

A problem which often arises while fitting implicit polynomials to 2D and 3D data sets is the following: although the data set is simple, the fit exhibits undesired phenomena, such as loops, holes, extraneous components, etc. Previous work tackled these problems by optimizing heuristic cost functions, which penalize some of these topological problems in the fit. The paper suggests a different approach-to design parameterized families of polynomials whose zero-sets are guaranteed to satisfy certain topological properties. Namely, we construct families of polynomials with star-shaped zero-sets, as well as polynomials whose zero-sets are guaranteed not to intersect an ellipse circumscribing the data or to be entirely contained in such an ellipse. This is more rigorous than using heuristics which may fail and result in pathological zero-sets. The ability to parameterize these families depends heavily on the ability to parameterize positive polynomials. To achieve this, we use some powerful results from real algebraic geometry     

Graph-based representations of point clouds

This paper introduces a skeletal representation, called Point Cloud Graph, that generalizes the definition of the Reeb graph to arbitrary point clouds sampled from m-dimensional manifolds embedded in the d-dimensional space. The proposed algorithm is easy to implement and the graph representation yields to an effective abstraction of the data. Finally, we present experimental results on point-sampled surfaces and volumetric data that show the robustness of the Point Cloud Graph to non-uniform point distributions and its usefulness for shape comparison.     

Visualizing chaos: Lyapunov surfaces and volumes

The use of a graphic technique to visualize chaos for a dual-parameter one-dimensional map is described. It involves plotting the Lyapunov exponent with both height and color in a three-dimensional map, as a function of the two parameters. Color is determined using a geographic lookup table. A graphics supercomputer can rotate the map in real time. The technique demonstrates graphically interesting behavior in chaotic systems     

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.     

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

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

含噪点云预处理技术研究

用三维光学测量系统进行测量时,由于周围环境、人、设备等各方面的影响,测量数据中常常会掺入噪声。针对体外飞点和离群成簇噪声分别采取基于K_近邻搜索的平均距离去噪算法和改进的基于近邻点距传播的去噪算法进行处理,取得了较好的去噪效果。针对直接测量或者多次测量拼接获取的点云存在"粗糙毛刺"和点云多层重叠的状况,采用基于MLS的拟合平面投影光顺算法进行光滑处理,去除"粗糙毛刺"和打薄重叠区域。该光顺去噪预处理算法已经成功运用到三维测量系统的点云处理模块中。     

Isotopic meshing of implicit surfaces

Implicit surfaces are given as the zero set of a function F:ℝ³→ℝ. Although several algorithms exist for generating piecewise linear approximations, most of these are based on a user-defined stepsize or bounds to indicate the precision, and therefore cannot guarantee topological correctness. Interval arithmetic provides a mechanism to determine global properties of the implicit function. In this paper we present an algorithm that uses these properties to generate a piecewise linear approximation of implicit curves and surfaces, that is isotopic to the curve or surface itself. The algorithm is simple and fast, and is among the first to guarantee isotopy for implicit surface meshing.     

Field functions for implicit surfaces

The use of 3D computer generated models is a rapidly growing part of the animation industry. But the established modelling techniques, using polygons or parametric patches, are not the best to define characters which can change their shape as they move. A newer method, using iso-surfaces in a scalar field, enables us to create models that can make the dynamic shape changes seen in hand animation. We call such modelsSoft Objects.From the user's point of view, a soft object is built from primitive key objects that blend to form a compound shape. In this paper, we examine some of the problems of choosing suitable keys and introduce some new field functions that increase the range of shapes available as keys.     

Curvature-dependent triangulation of implicit surfaces

Implicit surfaces appear in many applications, including medical imaging, molecular modeling, computer aided design, computer graphics and finite element analysis. Despite their many advantages, implicit surfaces are difficult to render efficiently. Today's real-time graphics systems are heavily optimized for rendering triangles, so an implicit surface should be converted to a mesh of triangles before rendering. Our algorithm polyonalizes an implicit surface. The algorithm generates a mesh of close-to-equilateral triangles with sizes dependent on the local surface curvature. We assume that the implicit surface is connected and G¹ is smooth (that is, the tangent plane varies continuously over the surface). The algorithm requires an evaluator for the implicit function defined at all points in space, an evaluator for the function gradient defined at points near the surface, and a bounding box around the surface. The output of the algorithm is good for applications requiring a well-behaved triangulation, such as rendering systems and finite element partial differential equation (PDE) solvers     

Visible neighborhood graph of point clouds

In this paper we present a new neighborhood graph definition of point clouds, called visible neighborhood graph. A local construction scheme using visibility information near each sample point is developed, and the neighbors are defined based on a convex hull computation in a dual space. Our method is able to approximate the underlying surface on which the point cloud was sampled, and can provide accurate neighborhoods in regions of close-by surface sheets. The theoretical guarantees of our method are proved, and the accuracy and efficiency of the graph are verified by experimental results. Its usefulness for applications such as geodesic computation and point cloud segmentation is also demonstrated.     

Iso-parametric tool-path planning for point clouds

Due to the compute-intensiveness and the lack of robustness of the algorithms for reconstruction of meshes and spline surfaces from point clouds, there is a need for further research in the topic of direct tool-path planning based on point clouds. In this paper, a novel approach for planning iso-parametric tool-path from a point cloud is presented. Since such planning falls into the iso-parametric category, it intrinsically depends on the parameterization of point clouds. Accordingly, a point-based conformal map is employed to build the parameterization. Based on it, formulas of computing path parameters are derived, which are much simpler than the conventional ones. By regularizing parameter domain and on the basis of the previous formulas, boundary conformed tool-path can be generated with forward and side step calculated against specified chord deviation and scallop height, respectively. Experimental results are given to illustrate the effectiveness of the proposed methods.     

Moving parabolic approximation of point clouds

Using moving parabolic approximations (MPA), we reconstruct an improved point-based model of curve or surface represented as an unorganized point cloud, while also estimating the differential properties of the underlying smooth manifold. We present optimization algorithms to solve these MPA models, and examples which show that our reconstructions of the curve or surface, and estimates of the normals and curvature information, are accurate for precise point clouds and robust in the presence of noise.     

Shape and tone depiction for implicit surfaces

We present techniques for rendering implicit surfaces in different pen-and-ink styles. The implicit models are rendered using point-based primitives to depict shape and tone using silhouettes with hidden-line attenuation, drawing directions, and stippling. We present sample renderings obtained for a variety of models. Furthermore, we describe simple and novel methods to control point placement and rendering style. Our approach is implemented using HRBF Implicits, a simple and compact representation, that has three fundamental qualities: a small number of point-normal samples as input for surface reconstruction, good projection of points near the surface, and smoothness of the gradient field. These qualities of HRBF Implicits are used to generate a robust distribution of points to position the drawing primitives.     

Polygonization of implicit surfaces with sharp features by edge-spinning

This paper presents an adaptive approach for polygonization of implicit surfaces. The algorithm generates a well-shaped triangular mesh with respect to a given approximation error. The error is proportional to a local surface curvature estimation. Polygonization of surfaces of high curvature, as well as surfaces with sharp features, is possible using a simple technique combined with a particle system approach. The algorithm is based on a surface tracking scheme, and it is compared with other algorithms based on a similar principle, such as the marching cube and the marching triangle algorithms.