Feature-Preserving Surface Reconstruction and Simplification from Defect-Laden Point Sets

We introduce a robust and feature-capturing surface reconstruction and simplification method that turns an input point set into a low triangle-count simplicial complex. Our approach starts with a (possibly non-manifold) simplicial complex filtered from a 3D Delaunay triangulation of the input points. This initial approximation is iteratively simplified based on an error metric that measures, through optimal transport, the distance between the input points and the current simplicial complex—both seen as mass distributions. Our approach is shown to exhibit both robustness to noise and outliers, as well as preservation of sharp features and boundaries. Our new feature-sensitive metric between point sets and triangle meshes can also be used as a post-processing tool that, from the smooth output of a reconstruction method, recovers sharp features and boundaries present in the initial point set.     

利用Voronoi协方差矩阵重建隐式曲面

目的 针对含少量离群点的噪声点云,提出了一种Voronoi协方差矩阵的曲面重建方法。方法 以隐函数梯度在Voronoi协方差矩阵形成的张量场内的投影最大化为目标,构建隐函数微分方程,采用离散外微分形式求解连续微分方程,从而将曲面重建问题转化为广义特征值求解问题。在点云空间离散化过程中,附加最短边约束条件,避免了局部空间过度剖分。并引入概率测度理论定义曲面窄带,提高了算法抵抗离群点能力,通过精细剖分曲面窄带,提高了曲面重建精度。结果 实验结果表明,该算法可以抵抗噪声点和离群点的影响,可以生成不同分辨率的曲面。通过调整拟合参数,可以区分曲面的不同部分。结论 提出了一种新的隐式曲面重建方法,无需点云法向、稳健性较强,生成的三角面纵横比好。     

Feature Preserving Mesh Generation from 3D Point Clouds

We address the problem of generating quality surface triangle meshes from 3D point clouds sampled on piecewise smooth surfaces. Using a feature detection process based on the covariance matrices of Voronoi cells, we first extract from the point cloud a set of sharp features. Our algorithm also runs on the input point cloud a reconstruction process, such as Poisson reconstruction, providing an implicit surface. A feature preserving variant of a Delaunay refinement process is then used to generate a mesh approximating the implicit surface and containing a faithful representation of the extracted sharp edges. Such a mesh provides an enhanced trade‐off between accuracy and mesh complexity. The whole process is robust to noise and made versatile through a small set of parameters which govern the mesh sizing, approximation error and shape of the elements. We demonstrate the effectiveness of our method on a variety of models including laser scanned datasets ranging from indoor to outdoor scenes.     

Localized Delaunay Refinement for Sampling and Meshing

The technique of Delaunay refinement has been recognized as a versatile tool to generate Delaunay meshes of a variety of geometries. Despite its usefulness, it suffers from one lacuna that limits its application. It does not scale well with the mesh size. As the sample point set grows, the Delaunay triangulation starts stressing the available memory space which ultimately stalls any effective progress. A natural solution to the problem is to maintain the point set in clusters and run the refinement on each individual cluster. However, this needs a careful point insertion strategy and a balanced coordination among the neighboring clusters to ensure consistency across individual meshes. We design an octtree based localized Delaunay refinement method for meshing surfaces in three dimensions which meets these goals. We prove that the algorithm terminates and provide guarantees about structural properties of the output mesh. Experimental results show that the method can avoid memory thrashing while computing large meshes and thus scales much better than the standard Delaunay refinement method.     

基于多尺度核函数的散乱点云数据过滤方法*

针对光滑曲面采样散乱点云含有噪声及异常数据的问题,提出了一种基于多尺度核函数的过滤处理方法。采用核密度估计技术及均值漂移跟踪算法对原始点云数据进行聚类,结合局部似然函数来测度一个三维点位于采样曲面上的概率,利用过滤后的极大似然点集精确地逼近采样曲面,最后结合经典网格化算法能够获得较好的曲面重构效果。处理实例证明,该方法实用性好,不仅能够很好地抑制不同幅值的噪声,同时也能够探测到异常数据并进行自动清除。     

An Optimal Transport Approach to Robust Reconstruction and Simplification of 2D Shapes

We propose a robust 2D shape reconstruction and simplification algorithm which takes as input a defect‐laden point set with noise and outliers. We introduce an optimal‐transport driven approach where the input point set, considered as a sum of Dirac measures, is approximated by a simplicial complex considered as a sum of uniform measures on 0‐ and 1‐simplices. A fine‐to‐coarse scheme is devised to construct the resulting simplicial complex through greedy decimation of a Delaunay triangulation of the input point set. Our method performs well on a variety of examples ranging from line drawings to grayscale images, with or without noise, features, and boundaries.     

Delaunay meshing of isosurfaces

We present an isosurface meshing algorithm, DelIso, based on the Delaunay refinement paradigm. This paradigm has been successfully applied to mesh a variety of domains with guarantees for topology, geometry, mesh gradedness, and triangle shape. A restricted Delaunay triangulation, dual of the intersection between the surface and the three-dimensional Voronoi diagram, is often the main ingredient in Delaunay refinement. Computing and storing three-dimensional Voronoi/Delaunay diagrams become bottlenecks for Delaunay refinement techniques since isosurface computations generally have large input datasets and output meshes. A highlight of our algorithm is that we find a simple way to recover the restricted Delaunay triangulation of the surface without computing the full 3D structure. We employ techniques for efficient ray tracing of isosurfaces to generate surface sample points, and demonstrate the effectiveness of our implementation using a variety of volume datasets.     

三维点集Voronoi图的算法实现

对现有三维点集Voronoi图的生成算法进行深入研究,提出并实现由Delaunay三角剖分构建Voronoi图的算法．首先采用随机增量局部转换计算Delaunay三角剖分,然后再根据对偶特性构建Voronoi图．该算法健壮性很高,适用于处理各种非完全共面三维点集．     

基于曲面局平特性的散乱数据拓扑重建算法

提出了一种基于曲面局平特性的,以散乱点集及其密度指标作为输入,以三角形分片线性曲面作为输出的拓扑重建算法.算法利用曲面的局平特性,从散乱点集三维Delaunay三角剖分的邻域结构中完成每个样点周围的局部拓扑重建,并从局部重建的并集中删除不相容的三角形,最终得到一个二维流形拓扑曲面集作为重建结果.该算法适应于包括单侧曲面在内的任意不自交的拓扑曲面集,并且重建结果是相对优化的曲面三角形剖分,可以应用于科学计算可视化、雕塑曲面造型和反求工程等领域.     

Robust and Efficient Surface Reconstruction From Range Data

We describe a robust but simple algorithm to reconstruct a surface from a set of merged range scans. Our key contribution is the formulation of the surface reconstruction problem as an energy minimisation problem that explicitly models the scanning process. The adaptivity of the Delaunay triangulation is exploited by restricting the energy to inside/outside labelings of Delaunay tetrahedra. Our energy measures both the output surface quality and how well the surface agrees with soft visibility constraints. Such energy is shown to perfectly fit into the minimum s ? t cuts optimisation framework, allowing fast computation of a globally optimal tetrahedra labeling, while avoiding the “shrinking bias” that usually plagues graph cuts methods. The behaviour of our method confronted to noise, undersampling and outliers is evaluated on several data sets and compared with other methods through different experiments: its strong robustness would make our method practical not only for reconstruction from range data but also from typically more difficult dense point clouds, resulting for instance from stereo image matching. Our effective modeling of the surface acquisition inverse problem, along with the unique combination of Delaunay triangulation and minimum s ? t cuts, makes the computational requirements of the algorithm scale well with respect to the size of the input point cloud.     

Feature preserving Delaunay mesh generation from 3D multi-material images

Generating realistic geometric models from 3D segmented images is an important task in many biomedical applications. Segmented 3D images impose particular challenges for meshing algorithms because they contain multi-material junctions forming features such as surface patches, edges and corners. The resulting meshes should preserve these features to ensure the visual quality and the mechanical soundness of the models. We present a feature preserving Delaunay refinement algorithm which can be used to generate high-quality tetrahedral meshes from segmented images. The idea is to explicitly sample corners and edges from the input image and to constrain the Delaunay refinement algorithm to preserve these features in addition to the surface patches. Our experimental results on segmented medical images have shown that, within a few seconds, the algorithm outputs a tetrahedral mesh in which each material is represented as a consistent submesh without gaps and overlaps. The optimization property of the Delaunay triangulation makes these meshes suitable for the purpose of realistic visualization or finite element simulations.     

An on-line algorithm for constrained Delaunay triangulation

A constrained Delaunay triangulation is a Delaunay triangulation of a set of points and straight-line segments. A constrained Delaunay triangulation is a basic tool for describing a topographic surface in several applications. In this paper, the definition of constrained Delaunay triangulation is introduced and its basic properties are discussed. Existing algorithms for constrained Delaunay triangulation are briefly analyzed. A new on-line algorithm for constrained Delaunay triangulation that is based on the stepwise refinement of an existing triangulation by the incremental insertion of points and constraint segments is proposed.     

An adaptive edge-based smoothed point interpolation method for mechanics problems

This paper develops a smoothing domain-based energy (SDE) error indicator and an efficient adaptive procedure using edge-based smoothed point interpolation methods (ES-PIM), in which the strain field is constructed via the generalized smoothing operation over smoothing domains associated with edges of three-node triangular background cells. Because the ES-PIM can produce a close-to-exact stiffness and achieve ‘super-convergence’ and ‘ultra-accurate’ solutions, it is an ideal candidate for adaptive analysis. A SDE error indicator is first devised to make use of the features of the ES-PIM. A local refinement technique based on the Delaunay algorithm is then implemented to achieve high efficiency. The refinement of nodal neighbourhood is accomplished simply by adjusting a scaling factor assigned to control local nodal density. Intensive numerical studies, including the problems with stress concentration and solution singularity, demonstrate that the proposed adaptive procedure is effective and efficient in producing solutions with desired accuracy.     

以优先点为中心的Delaunay三角网生长算法

目的 Delaunay三角网具备的优良性质使其得到广泛的应用,构建Delaunay三角网是计算几何的基础问题之一,为了高效、准确地构建大规模点集的Delaunay三角网,提出一种基于优先点的改进三角网生长算法.方法 算法以逆时针次序的一条凸包边为初始基边,使用基边对角最大化并按照逆时针次序选定第3点构建一个Delaunay三角形,通过待扩展边列表中的数据判断新生成的两条边是否需要扩展,采用先进先出的方式从待扩展边列表中取边作为基边,以优先点为中心构建局部Delaunay三角网使优先点尽快成为封闭点,再从点集中删除此封闭点.结果 对于同一测试点集,改进算法运行时间与经典算法运行时间的比率不超过1/3,且此比率随点集规模增长逐步下降.相比经典算法,改进算法在时间效率上有较大提升.结论 本文改进算法对点集规模具有较好的自适应性与较高的构网效率,可用于大规模场景下Delaunay三角网的构建.     

Reconstruction of 2D polygonal curves and 3D triangular surfaces via clustering of Delaunay circles/spheres

A simple and efficient method is presented in this paper to reliably reconstruct 2D polygonal curves and 3D triangular surfaces from discrete points based on the respective clustering of Delaunay circles and spheres. A Delaunay circle is the circumcircle of a Delaunay triangle in the 2D space, and a Delaunay sphere is the circumsphere of a Delaunay tetrahedron in the 3D space. The basic concept of the presented method is that all the incident Delaunay circles/spheres of a point are supposed to be clustered into two groups along the original curve/surface with satisfactory point density. The required point density is considered equivalent to that of meeting the well-documented r-sampling condition. With the clustering of Delaunay circles/spheres at each point, an initial partial mesh can be generated. An extrapolation heuristic is then applied to reconstructing the remainder mesh, often around sharp corners. This leads to the unique benefit of the presented method that point density around sharp corners does not have to be infinite. Implementation results have shown that the presented method can correctly reconstruct 2D curves and 3D surfaces for known point cloud data sets employed in the literature.     

A highly solid model boundary preserving method for large-scale parallel 3D Delaunay meshing on parallel computers

In this paper, we propose a novel parallel 3D Delaunay triangulation algorithm for large-scale simulations on parallel computers. Our method keeps the 3D boundary representation model information during the whole parallel 3D Delaunay triangulation process running on parallel computers so that the solid model information can be accessed dynamically and the meshing results can be very approaching to the model boundary with the increase of meshing scale. The model is coarsely meshed at first and distributed on CPUs with consistent partitioned shared interfaces and partitioned model boundary meshes across processors. The domain partition aims at minimizing the edge-cuts across different processors for minimum communication cost and distributing roughly equal number of mesh vertices for load balance. Then a parallel multi-scale surface mesh refinement phase is iteratively performed to meet the mesh density criteria followed by a parallel surface mesh optimization phase moving vertices to the model boundary so as to fit model geometry feature dynamically. A dynamic load balancing algorithm is performed to change the partition interfaces if necessary. A 3D local non-Delaunay mesh repair algorithm is finally done on the shared interfaces across processors and model boundaries. The experimental results demonstrate our method can achieve high parallel performance and perfect scalability, at the same time preserve model boundary feature and generate high quality 3D Delaunay mesh as well.     

PointCleanNet: Learning to Denoise and Remove Outliers from Dense Point Clouds

Point clouds obtained with 3D scanners or by image-based reconstruction techniques are often corrupted with significant amount of noise and outliers. Traditional methods for point cloud denoising largely rely on local surface fitting (e.g. jets or MLS surfaces), local or non-local averaging or on statistical assumptions about the underlying noise model. In contrast, we develop a simple data-driven method for removing outliers and reducing noise in unordered point clouds. We base our approach on a deep learning architecture adapted from PCPNet, which was recently proposed for estimating local 3D shape properties in point clouds. Our method first classifies and discards outlier samples, and then estimates correction vectors that project noisy points onto the original clean surfaces. The approach is efficient and robust to varying amounts of noise and outliers, while being able to handle large densely sampled point clouds. In our extensive evaluation, both on synthetic and real data, we show an increased robustness to strong noise levels compared to various state-of-the-art methods, enabling accurate surface reconstruction from extremely noisy real data obtained by range scans. Finally, the simplicity and universality of our approach makes it very easy to integrate in any existing geometry processing pipeline. Both the code and pre-trained networks can be found on the project page ( https://github.com/mrakotosaon/pointcleannet ).     

一种基于三维Delaunay三角化的曲面重建算法

提出一种基于三维Delaunay三角化的区域增长式曲面重建方法。该方法以空间点云的Delaunay三角化为基础,结合局部区域增长的曲面构造,较以往方法具有人为参与更少、适用范围更广的优点。算法采用增量式插入点的方式构建空间Delaunay划分,采用广度优先算法,以外接圆最小为准则从Delaunay三角化得到的四面体中抽取出合适的三角片构成曲面。该算法的设计无须计算原始点集的法矢,且孔洞系数对重建的结果影响很小,重建出的三角网格面更符合原始曲面的几何特征。无论待建曲面是否是封闭曲面,本算法均可获得较好的重建效果。     

Crawl through Neighbors: A Simple Curve Reconstruction Algorithm

Given a planar point set sampled from an object boundary, the process of approximating the original shape is called curve reconstruction. In this paper, a novel non‐parametric curve reconstruction algorithm based on Delaunay triangulation has been proposed and it has been theoretically proved that the proposed method reconstructs the original curve under ε‐sampling. Starting from an initial Delaunay seed edge, the algorithm proceeds by finding an appropriate neighbouring point and adding an edge between them. Experimental results show that the proposed algorithm is capable of reconstructing curves with different features like sharp corners, outliers, multiple objects, objects with holes, etc. The proposed method also works for open curves. Based on a study by a few users, the paper also discusses an application of the proposed algorithm for reconstructing hand drawn skip stroke sketches, which will be useful in various sketch based interfaces.     

A Correntropy-based Affine Iterative Closest Point Algorithm for Robust Point Set Registration

The iterative closest point (ICP) algorithm has the advantages of high accuracy and fast speed for point set registration, but it performs poorly when the point set has a large number of noisy outliers. To solve this problem, we propose a new affine registration algorithm based on correntropy which works well in the affine registration of point sets with outliers. Firstly, we substitute the traditional measure of least squares with a maximum correntropy criterion to build a new registration model, which can avoid the influence of outliers. To maximize the objective function, we then propose a robust affine ICP algorithm. At each iteration of this new algorithm, we set up the index mapping of two point sets according to the known transformation, and then compute the closed-form solution of the new transformation according to the known index mapping. Similar to the traditional ICP algorithm, our algorithm converges to a local maximum monotonously for any given initial value. Finally, the robustness and high efficiency of affine ICP algorithm based on correntropy are demonstrated by 2D and 3D point set registration experiments.