On stochastic methods for surface reconstruction

In this article, we present and discuss three statistical methods for surface reconstruction. A typical input to a surface reconstruction technique consists of a large set of points that has been sampled from a smooth surface and contains uncertain data in the form of noise and outliers. We first present a method that filters out uncertain and redundant information yielding a more accurate and economical surface representation. Then we present two methods, each of which converts the input point data to a standard shape representation; the first produces an implicit representation while the second yields a triangle mesh.     

Building binary orientation octree for an arbitrary scattered point set

The binary orientation tree (BOT), proposed in [Chen, Y.-L., Chen, B.-Y., Lai, S.-H., and Nishita, T. (2010). Binary orientation trees for volume and surface reconstruction from unoriented point clouds. Comput. Graph. Forum, 29(7), 2011–2019.], is a useful spatial hierarchical data structure for geometric processing such as 3D reconstruction and implicit surface approximation from an input point set. BOT is an octree in which all the vertices of the leaf nodes in the tree are tagged with an ‘in/out’ label based on their spatial relationship to the underlying surface enclosed by the octree. Unfortunately, such a data structure in [Chen, Y.-L., Chen, B.-Y., Lai, S.-H., and Nishita, T. (2010). Binary orientation trees for volume and surface reconstruction from unoriented point clouds. Comput. Graph. Forum, 29(7), 2011–2019.] is only valid for watertight surfaces, which restricts its application. In this paper, we extend the ‘in/out’ relationship to ‘front/back/NA’ relationship to either a closed or an open surface, and propose a new method to build such a spatial data structure from a given arbitrary point set. We first classify the edges of the leaf nodes into two different categories based on whether their two end points are in the same side of the surface or not, and attach respective labels to the edges accordingly. A global propagation process is then applied to get the consistent labels of those end points that are in the same side of the surface. Experiments show that our BOT building method is much more robust, efficient and applicable to various input compared to existing methods, and the applications of BOT when doing RBF reconstructions and envelope surface computations of given 3D objects are shown in the experimental part.     

Feature-Based Deformable Surface Detection with Self-Occlusion Reasoning

This paper presents a method for detecting a textured deformed surface in an image. It uses (wide-baseline) point matches between a template and the input image. The main contribution of the paper is twofold. First, we propose a robust method based on local surface smoothness capable of discarding outliers from the set of point matches. Our method handles large proportions of outliers (beyond 70% with less than 15% of false positives) even when the surface self-occludes. Second, we propose a method to estimate a self-occlusion resistant warp from point matches. Our method allows us to realistically retexture the input image. A pixel-based (direct) registration approach is also proposed. Bootstrapped by our robust point-based method, it finely tunes the warp parameters using the value (intensity or color) of all the visible surface pixels. The proposed framework was tested with simulated and real data. Convincing results are shown for the detection and retexturing of deformed surfaces in challenging images.     

Feature‐Preserving Surface Reconstruction From Unoriented,Noisy Point Data

We propose a robust method for surface mesh reconstruction from unorganized, unoriented, noisy and outlier‐ridden 3D point data. A kernel‐based scale estimator is introduced to estimate the scale of inliers of the input data. The best tangent planes are computed for all points based on mean shift clustering and adaptive scale sample consensus, followed by detecting and removing outliers. Subsequently, we estimate the normals for the remaining points and smooth the noise using a surface fitting and projection strategy. As a result, the outliers and noise are removed and filtered, while the original sharp features are well preserved. We then adopt an existing method to reconstruct surface meshes from the processed point data. To preserve sharp features of the generated meshes that are often blurred during reconstruction, we describe a two‐step approach to effectively recover original sharp features. A number of examples are presented to demonstrate the effectiveness and robustness of our method.     

Extracting lines of curvature from noisy point clouds

We present a robust framework for extracting lines of curvature from point clouds. First, we show a novel approach to denoising the input point cloud using robust statistical estimates of surface normal and curvature which automatically rejects outliers and corrects points by energy minimization. Then the lines of curvature are constructed on the point cloud with controllable density. Our approach is applicable to surfaces of arbitrary genus, with or without boundaries, and is statistically robust to noise and outliers while preserving sharp surface features. We show our approach to be effective over a range of synthetic and real-world input datasets with varying amounts of noise and outliers. The extraction of curvature information can benefit many applications in CAD, computer vision and graphics for point cloud shape analysis, recognition and segmentation. Here, we show the possibility of using the lines of curvature for feature-preserving mesh construction directly from noisy point clouds.     

Splat-based surface reconstruction from defect-laden point sets

We introduce a method for surface reconstruction from point sets that is able to cope with noise and outliers. First, a splat-based representation is computed from the point set. A robust local 3D RANSAC-based procedure is used to filter the point set for outliers, then a local jet surface – a low-degree surface approximation – is fitted to the inliers. Second, we extract the reconstructed surface in the form of a surface triangle mesh through Delaunay refinement. The Delaunay refinement meshing approach requires computing intersections between line segment queries and the surface to be meshed. In the present case, intersection queries are solved from the set of splats through a 1D RANSAC procedure.     

A variational model for normal computation of point clouds

In this paper we present a novel model for computing the oriented normal field on a point cloud. Differently from previous two-stage approaches, our method integrates the unoriented normal estimation and the consistent normal orientation into one variational framework. The normal field with consistent orientation is obtained by minimizing a combination of the Dirichlet energy and the coupled-orthogonality deviation, which controls the normals perpendicular to and continuously varying on the underlying shape. The variational model leads to solving an eigenvalue problem. If unoriented normal field is provided, the model can be modified for consistent normal orientation. We also present experiments which demonstrate that our estimates of oriented normal vectors are accurate for smooth point clouds, and robust in the presence of noise, and reliable for surfaces with sharp features, e.g., corners, ridges, close-by sheets and thin structures.     

Efficient RANSAC for Point-Cloud Shape Detection

In this paper we present an automatic algorithm to detect basic shapes in unorganized point clouds. The algorithm decomposes the point cloud into a concise, hybrid structure of inherent shapes and a set of remaining points. Each detected shape serves as a proxy for a set of corresponding points. Our method is based on random sampling and detects planes, spheres, cylinders, cones and tori. For models with surfaces composed of these basic shapes only, for example, CAD models, we automatically obtain a representation solely consisting of shape proxies. We demonstrate that the algorithm is robust even in the presence of many outliers and a high degree of noise. The proposed method scales well with respect to the size of the input point cloud and the number and size of the shapes within the data. Even point sets with several millions of samples are robustly decomposed within less than a minute. Moreover, the algorithm is conceptually simple and easy to implement. Application areas include measurement of physical parameters, scan registration, surface compression, hybrid rendering, shape classification, meshing, simplification, approximation and reverse engineering.     

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.     

PointProNets: Consolidation of Point Clouds with Convolutional Neural Networks

With the widespread use of 3D acquisition devices, there is an increasing need of consolidating captured noisy and sparse point cloud data for accurate representation of the underlying structures. There are numerous algorithms that rely on a variety of assumptions such as local smoothness to tackle this ill‐posed problem. However, such priors lead to loss of important features and geometric detail. Instead, we propose a novel data‐driven approach for point cloud consolidation via a convolutional neural network based technique. Our method takes a sparse and noisy point cloud as input, and produces a dense point cloud accurately representing the underlying surface by resolving ambiguities in geometry. The resulting point set can then be used to reconstruct accurate manifold surfaces and estimate surface properties. To achieve this, we propose a generative neural network architecture that can input and output point clouds, unlocking a powerful set of tools from the deep learning literature. We use this architecture to apply convolutional neural networks to local patches of geometry for high quality and efficient point cloud consolidation. This results in significantly more accurate surfaces, as we illustrate with a diversity of examples and comparisons to the state‐of‐the‐art.     

散乱点云近离群点识别算法

针对原始曲面变化度的局部离群系数(SVLOF)无法有效滤除三维实体的棱边或棱角处的离群点问题,提出了一种散乱点云近离群点的滤除算法。该算法首先将SVLOF定义在类k邻域上,并将SVLOF的定义内容进行了扩展,使其既能滤除平滑曲面上的离群点,又能滤除三维实体的棱边或棱角点处的离群点,同时仍然保留SVLOF原有的足够宽泛的阈值选取空间。仿真数据和实际数据的实验结果均表明,在效率基本保持不变的情况下,所提算法能比原始SVLOF算法更有效地检测出距离主体点云近的离群点。     

The Robust Sequential Estimator: a general approach and itsapplication to surface organization in range data

Presents an autonomous, statistically robust, sequential function approximation approach to simultaneous parameterization and organization of (possibly partially occluded) surfaces in noisy, outlier-ridden (not Gaussian), functional range data. At the core of this approach is the Robust Sequential Estimator, a robust extension to the method of sequential least squares. Unlike most existing surface characterization techniques, the authors' method generates complete surface hypotheses in parameter space. Given a noisy depth map of an unknown 3-D scene, the algorithm first selects appropriate seed points representing possible surfaces. For each nonredundant seed it chooses the best approximating model from a given set of competing models using a modified Akaike Information Criterion. With this best model, each surface is expanded from its seed over the entire image, and this step is repeated for all seeds. Those points which appear to be outliers with respect to the model in growth are not included in the (possibly disconnected) surface. Point regions are deleted from each newly grown surface in the prune stage. Noise, outliers, or coincidental surface alignment may cause some points to appear to belong to more than one surface. These ambiguities are resolved by a weighted voting scheme within a 5×5 decision window centered around the ambiguous point. The isolated point regions left after the resolve stage are removed and any missing points in the data are filled by the surface having a majority consensus in an 8-neighborhood     

Feature Preserving Point Set Surfaces based on Non-Linear Kernel Regression

Moving least squares (MLS) is a very attractive tool to design effective meshless surface representations. However, as long as approximations are performed in a least square sense, the resulting definitions remain sensitive to outliers, and smooth-out small or sharp features. In this paper, we address these major issues, and present a novel point based surface definition combining the simplicity of implicit MLS surfaces [ SOS04 , Kol05 ] with the strength of robust statistics. To reach this new definition, we review MLS surfaces in terms of local kernel regression, opening the doors to a vast and well established literature from which we utilize robust kernel regression. Our novel representation can handle sparse sampling, generates a continuous surface better preserving fine details, and can naturally handle any kind of sharp features with controllable sharpness. Finally, it combines ease of implementation with performance competing with other non-robust approaches.     

Surface meshing of underwater maps from highly defective point sets

Owing to the many possible errors that may occur during real‐world mapping, point set maps often present a huge amount of outliers and large levels of noise. We present two robust surface reconstruction techniques dealing with corrupted point sets without resorting to any prefiltering step. They are based on building an unsigned distance function, discretely evaluated on an adaptive tetrahedral grid, and defined from an outlier‐robust splat representation. To extract the surface from this volumetric view, the space is partitioned into two subsets, the surface of interest being at the boundary separating them. While both methods are based on a similar graph definition derived from the above‐mentioned grid, they differ in the partitioning procedure. First, we propose a method using S‐T cuts to separate the inside and outside of the mapped area. Second, we use a normalized cut approach to partition the volume using only the values of the unsigned distance function. We prove the validity of our methods by applying them to challenging underwater data sets (sonar and image based), and we benchmark their results against the approaches in the state of the art.     

Multi-scale geometric detail enhancement for time-varying surfaces

This paper presents a new multi-scale geometric detail enhancement approach for time-varying surfaces. We first develop an adaptive spatio-temporal bilateral filter, which produces temporally-coherent and feature-preserving multi-scale representation for the time-varying surfaces. We then extract the geometric details from the time-varying surfaces, and enhance geometric details by exaggerating detail information at each scale across the time-varying surfaces. Our approach can process mesh sequences with consistent connections or point sequences with unconstructed point set. In addition, as applications, based on the developed multi-scale surface representation and detail enhancement operators, we present geometric detail transfer, space–time morphing, and local regions detail enhancement for the time-varying surface.     

Curve evolution models for real-time identification withapplication to plasma etching

It is desirable, in constructing an algorithm for real-time control or identification of free surfaces, to avoid representations of the surface requiring mesh refinement at corners or special logic for topological transitions. Level set methods provide a promising framework for such algorithms. In this paper we present: 1) a mathematical representation of free surface motion that is particularly well-suited to real-time implementation; 2) a technique for estimating an isotropic and homogeneous normal velocity based on a simple measurement; and 3) an application to a semiconductor etching problem     

多视点距离图像的对准算法

提出一种多视点距离图像的对准算法.该算法将有拒绝的随机抽样和迭代最近点 (ICP: Iterative Closest Point)算法结合起来,采用粗、精对准时不同的评价函数,利用最小二 乘进行多视点之间运动参数的估计.为了快速进行3D点到物体表面的最近距离和最近点的 计算,采用了物体表面的八叉树样条表示.实验结果表明,该对准算法收敛速度较快,抗噪声 能力较强,并且有较高的对准精度.     

Particle-based sampling and meshing of surfaces in multimaterial volumes

Methods that faithfully and robustly capture the geometry of complex material interfaces in labeled volume data are important for generating realistic and accurate visualizations and simulations of real-world objects. The generation of such multimaterial models from measured data poses two unique challenges: first, the surfaces must be well-sampled with regular, efficient tessellations that are consistent across material boundaries; and second, the resulting meshes must respect the nonmanifold geometry of the multimaterial interfaces. This paper proposes a strategy for sampling and meshing multimaterial volumes using dynamic particle systems, including a novel, differentiable representation of the material junctions that allows the particle system to explicitly sample corners, edges, and surfaces of material intersections. The distributions of particles are controlled by fundamental sampling constraints, allowing Delaunay-based meshing algorithms to reliably extract watertight meshes of consistently high-quality.     

基于投影法的圆角和倒角操作

实体造型系统一般只使用少数几类基本曲面,但是它们之间的融接却需要相当复杂的曲面来表示.一个解决办法是采用适当的融接曲面,并最后用基本曲面来拟合.本文据此提出一个在多面体上构造融接曲面的方法.该方法能够对绝大部分棱边进行圆角和倒角处理,而描述却很直观.基于这个方法的圆角和倒角操作己经在我们开发的实体造型系统TORVS上实现.     

Real‐Time Fluid Effects on Surfaces using the Closest Point Method

The Closest Point Method (CPM) is a method for numerically solving partial differential equations (PDEs) on arbitrary surfaces, independent of the existence of a surface parametrization. The CPM uses a closest point representation of the surface, to solve the unmodified Cartesian version of a surface PDE in a 3D volume embedding, using simple and well‐understood techniques. In this paper, we present the numerical solution of the wave equation and the incompressible Navier‐Stokes equations on surfaces via the CPM, and we demonstrate surface appearance and shape variations in real‐time using this method. To fully exploit the potential of the CPM, we present a novel GPU realization of the entire CPM pipeline. We propose a surface‐embedding adaptive 3D spatial grid for efficient representation of the surface, and present a high‐performance approach using CUDA for converting surfaces given by triangulations into this representation. For real‐time performance, CUDA is also used for the numerical procedures of the CPM. For rendering the surface (and the PDE solution) directly from the closest point representation without the need to reconstruct a triangulated surface, we present a GPU ray‐casting method that works on the adaptive 3D grid.