Surface reconstruction

Please refresh the page if equations are not rendered correctly.
---------------------------------------------------------------

Surface reconstruction¹

At present, acquiring a digitized surface of an object is getting easier with 3D surface scanning systems, such as 3D optical scanners. With this technological improvement, the application of digitized surface is expanding in a variety of fields. For instance, engineering, medical science and fine art, to name a few. In response to such high demand, a large number of surface reconstruction algorithms have been proposed over the last few decades. Coverage of the wide variety of surface reconstruction algorithms is outside the scope of this paper. The readers interested in are recommended to refer to a comprehensive surveys [1], [2]. Algorithms with point cloud input are roughly classified as explicit or implicit based on the strategies involved.

1. Explicit methods

Explicit surface reconstruction creates surface meshes with vertices that are essentially part of the input points. The key to these types of algorithms is the method of determination of the connectivity of points. Many algorithms in this category determine the connectivity by Delaunay triangulation and related algorithms [3], [4], [5], [6].

This approach is time consuming and relatively sensitive to the issues often seen with scanned geometry **, such as noise, missing data, and non-uniform sampling density**. Regardless of these practical shortcomings, explicit methods are favorable because the quality of the resulting meshes is guaranteed in terms of conditions concerning sampling density. To overcome the issues, a number of studies have been proposed. In the method outlined by [7], noisy data are dealt with by interpolating input points. Amenta et al. [8] proposed a technique for watertight surface reconstruction and demonstrated the necessary conditions for sampling density.

Explicit method of surface reconstruction:

点云表面重建按重建得到的表面形式可分为显式重建和隐式重建两类,显式表面精确描述表面的位置,隐式表面重建方法通过标量函数的等值面来表达。常用的显式重建方法有参数曲面和三角化表面，隐式方法中场函数法和径向基函数方法应用广泛。

Output: surface meshes created with vertices that are essentially part of the input point cloud

• determination of the connectivity of points by Delaunay triangulation and related algorithms (local surface connectivity estimation).
  

  通常认为输入点云中的每个点都是重构网格的顶点，计算输入点云的德洛奈三角网（Delaunay triangulation network）或其对偶的沃罗诺伊图（Voronoi diagram），然后利用这些图结构构造出点云中点的连接关系；

• Computation geometry
  

  • 可以最大程度地保持重建网格和输入点云几何特征的一致性；
  • 非常依赖于输入的质量，对于含噪声的点云需要去噪后再重构；

2. Implicit methods

While the explicit method has difficulty in dealing with artifacts of a point cloud, the best advantages of implicit surface reconstruction are its abilities to generate a smooth surface and to smoothly fill a hole. Unlike explicit methods, implicit algorithms:

• first generate a scalar field of a function whose isosurface approximates the surface of the scanned objects (for instance, signed distance function),

• and then extract and polygonize the isosurface (mesh approximation). The polygonization is usually performed with the assistance of other algorithms, such as [9], [10].

• In addition, a user can carefully design the approximation function so the resulting isosurface has the desired level of smoothness.

Although not discussed in detail here, implicit algorithms are classified into two subgroups on the basis of the type of approximation function involved.

• Those based on a global function, such as [11], [12], [13], [14], [15], provide advantages in their robustness and ability to handle low-quality data. However, approximation function generation tends to be time-consuming.

• The algorithms in other subgroup construct approximation functions with locally supported functions. Typical examples include [16], [17], [18], [19], [20]. The main advantage of such methods lies in their high-quality representation of fine surface details, which cannot be achieved by other algorithms. Their local nature also facilitates speedy computation, and enables processing of large data sets.

Tomographic surface reconstruction, newly proposed in this paper, is categorized to the global implicit approach since a discretized scalar field, a CT volume, is obtained by global computations on the entire volume. While most implicit algorithms generate their scalar fields by constructing approximation functions, tomographic surface reconstruction obtains the one from CT reconstruction which has not been used for this purpose before.

Implicit functions are usually sampled on an underlying grid, where the reconstructed surface is found via isocontouring for an appropriate isovalue. 认为输入点云是三维空间在隐式函数零水平集（zero level set）的采样，首先根据点云位置拟合出光滑的隐式函数，然后构造轮廓面，将隐式函数的零水平集离散化为三角网格；

• 主流，和显式方法相比更高效一些，对于输入噪声也稍微更稳定一些 (Fast and efficient)；
• 可以确保是流形（manifold），这里可以简单地理解为输出网格中的三角面片的每条边，除了边界，都连接了两个面；
• 不能控制输出三角面片的形状，可能有大量狭长的三角面片，需要重网格化，让面片的形状更规则；

Reference:

[1] Nagai Y, Ohtake Y, Suzuki H. Tomographic surface reconstruction from point cloud[J]. Computers & Graphics, 2015, 46: 55-63.

[2] Berger M, Tagliasacchi A, Seversky L, et al. State of the art in surface reconstruction from point clouds[J]. Eurographics 2014-State of the Art Reports, 2014, 1(1): 161-185.

[3] 《GAMES203：三维重建和理解》3 曲面重建（Surface Reconstruction） - 知乎