4. Reconstruction

Surface Reconstruction

把3D点重建成连续的或非连续的曲面

  • Input: A set of points in 3D that sampled from a model surface
  • Output: A 2D manifold mesh surface that closely approximates the surface of the original model

难点：Desirable Properties

  • No restriction on topological type

  • Representation of range uncertainty
  • Utilization of all range data
  • Incremental and order independent updating
  • Time and space efficiency
  • Robustness
  • Ability to fill holes in the reconstruction

Solutions

  • Approximation methods: Constructing continuous functions (Scattered data interpolation schemes)
    • NURBS surfaces
    • Signed distances [Hoppe et al. 1992]
    • Radial basis function reconstruction [Carr et al. 2001] 
    • Poisson reconstruction [Kazhdan et al. 2006] 
  • Discrete methods: Constructing triangle meshes directly 
    • [Amenta & Bern 1998]
    • Power‐crust [Amenda et al. 2001]
    • Cocone [Dey & Giesen 2001]
    • [Cazals & Giesen 2006] 
    • …

Approximation methods

NURBS surfaces

[59:30] NURBS 逼近法:用一个函数逼近点云

Implicit Approximation Methods (similar to GAMES 102‐9)

第一步： Convert point cloud into a signed distance field

For every point, add two off‐surface points, one inside and one outside the surface in the direction of the normal
Add a point only if it is closest to its source
N≈3n points

[1:01:26] \(n\)个点产生了\(3n\)个点，分别是(-1,0，1)

第二步：Construct an implicit function whose iso‐surface with iso‐value 0 to approximate the field

构造高维（4D）曲面，使得函数的0整面经过这些点

第三步： Extract the mesh surfaces from the implicit function

Marching cube methods

Complexity

  • Storage O(\(N^2\))
  • Solving the \(W_i O(N^3)\)
  • Evaluating f(x) O(N)

Carr et al. Reconstruction and representation of 3D objects with Radial Basis Functions, SIGGRAPH 2001.

(2) MPU Implicits

根据距离场自适应地剖分，一种自适应版本的Marching Cube

MPU = Multi‐level partition of unity implicits:

  • Given: data points with normal
  • Computes: hierarchical approximation of the signed distance function

Ohtake et al. Multi‐level Partition of Unity Implicits, SIGGRAPH 2003

(3) Possion reconstruction

Idea: fitting an indicator function

$$ \chi M(x)=\begin{cases} 1 & \text{ } x\in M \\ 0 & \text{ } x\notin M \end{cases} $$

Kazhdan et al. Poisson surface reconstruction. SGP 2006.

隐函数方法对法向非常敏感
不仅逼近函数，还逼近梯度本身
把重建问题变成方程求解隐函数的问题
[1:08:39]隐函数求解后要找到上面的点，用 Marching Cube

(4) Marching Cube

method for approximating surface defined by isovalue \(\alpha\), given by grid data

  • Input:
    • Grid data (set of 2D images)
    • Threshold value (isovalue) \(\alpha\)
  • Output:
    • Triangulated surface that matches isovalue surface of \(\alpha\)

具体步骤：

  • First pass
    • Identify voxels which intersect isovalue
  • Second pass
    • Examine those voxels，For each voxel produce set of triangles，approximate surface inside voxel

Discrete methods

Curve from Points

第一步：Connect the Dots

Can be ambiguous

  • Use Voronoi Diagram
  • Construct Delaunay triangulation

第二步：基于字典学习的曲面重建

Xiong et al. Robust Surface Reconstruction via Dictionary Learning. Siggraph Asia 2014.

  • 输入：三维点集（蓝色点）P
  • 输出
    • 采样点集（红色点）V
    • V构成的三角网格M，使得M逼近P

问题

  • 误差度量：如何度量点集P与网格M之间的误差？
    答：某个点到三角形的距离

难点:红点的位置和连接关系未知
度量:蓝点到三角形面片的距离最小
用交替法求解V和B,稀疏优化中的字典学习问题

$$ d(\mathbf{p}_i,f) =|| \mathbf{p}_i-\mathbf{p}_i^{\prime} || $$

$$ \begin{aligned} =\min _{\substack{\alpha+\beta+\gamma=1 \\ \alpha, \beta, \gamma \geq 0}}||\mathbf{p}_i-(\alpha \mathbf{v}_r+\beta \mathbf{v}_s+\gamma \mathbf{v}_t)|| \end{aligned} $$

\({P}' _i=\alpha ^{\ast}V_r+\beta ^{\ast}V_s+\gamma ^{\ast}V_t\)

\((\alpha ^{\ast},\beta ^{\ast},\gamma ^{\ast})\):\({P}' _i\)相对与\(f\)的重心坐标

某个点到三角形的距离

$$ d(\mathbf{p}_i,f) =|| \mathbf{p}_i-\mathbf{p}_i^{\prime} || $$

$$ \begin{aligned} =\min _{\substack{\alpha+\beta+\gamma=1 \\ \alpha, \beta, \gamma \geq 0}}||\mathbf{p}_i-(\alpha \mathbf{v}_r+\beta \mathbf{v}_s+\gamma \mathbf{v}_t)|| \end{aligned} $$

\(\mathbf{Ｖ}=[\mathbf{Ｖ}_1,\mathbf{Ｖ}_2,\cdots ,\mathbf{Ｖ}_m] \in \mathbb{R }^{3\times m}\)

Vertex matrix of M

特点

  • Iterative Refinement

  • Resistant to Noise

  • Feature Preserving

Implicit methods need normal information, while normal estimation is another challenging problem.

Conclusion

Model the surface reconstruction problem via dictionary learning

  • VS Implicit method
    • Straightforward
    • Approximation error is considered
  • VS Existing Explicit method
    • Denoising the input point cloud
    • Global approximation error

dictionary learning是一种半显式的方法。

Hybrid Methods

(1) Competing Fronts

[1:21:10] 假设物体是封闭曲面。
物体内的距离场不断膨胀，形成 mesh

Sharf et al. Competing Fronts for Coarse–to–Fine Surface Reconstruction. Eurographics 2006.

(2) Cooperative Evolutions 

  • Two deformable models 
    • One from interior
    • The other from exterior
  • Alternative evolutions

[1:23:02] 改进版:里面的球不断膨胀。外面的球不断收缩，直到两个曲面靠近,适用于有大的空洞的物体。

Lu and Liu. Surface Reconstruction via Cooperative Evolutions. CAGD 2020.

本文出自CaterpillarStudyGroup，转载请注明出处。 https://caterpillarstudygroup.github.io/GAMES102_mdbook/