From Point Cloud to Surface

Local reonstruction

Estimate Surface Normal from Points

1. Find \(k\) nearest neighbors of each point.
2. Covariance analysis (PCA) to find the normal vector. $$ \mathbf{C} = \frac{1}{k-1} \sum_{i=1}^{k} (\mathbf{x}_i - \bar{\mathbf{x}})(\mathbf{x}_i - \bar{\mathbf{x}})^T $$ where \(\bar{\mathbf{x}}\) is the mean of the \(k\) neighbors.

3. Eigenvalue decomposition of the covariance matrix \(\mathbf{C}\). The eigenvector \(\vect{n}_i\) corresponding to the smallest eigenvalue is the normal vector. (Intuition: This eigenvector represents the direction of least variance, which should be orthogonal to the surface.)

4. Determine the normal orientation by minimal spanning tree (MST) propagation.

Signed Distance from tangent plane

1. For the given oriented point cloud, each pair of points \(\vect{x}_i\) and corresponding normal \(\vect{n}_i\) defines a local tangent plane, i.e., first-order approximation of the underlying surface at \(\vect{x}_i\). We can calculate the signed distance of a query point \(\vect{q}\) to the tangent plane at \(\vect{x}_i\): $$ d(\vect{q}) = (\vect{q} - \vect{x}_i) \cdot \vect{n}_i $$ This is just the dot product of the vector from \(\vect{x}_i\) to \(\vect{q}\) and the normal vector \(\vect{n}_i\) -- Project \(\vect{q}\) onto the normal direction.

2. We can average the signed distances from nearby planes: $$ d(\vect{q}) = \frac{\sum_{i=1}^{k} w(\vect{x}i, \vect{q}) \cdot d(\vect{q})}{\sum $$ where }^{k} w(\vect{x}_i, \vect{q})\(w(\vect{x}_i, \vect{q})\) is a weight function, e.g., Gaussian kernel.

Global reconstruction

RBF interpolation

Interpolate the surface using radial basis functions (RBFs):

\[ d(\vect{x_j}) = \sum_{i=1}^{N} w_i \cdot \phi(\|\vect{x}_j - \vect{x}_i\|) \overset{!}{=} d_j \]

where \(\phi\) is a radial basis function, and we can solve the symmetric linear system for weights \(w_i\).

\[ \begin{bmatrix} \phi(\|\vect{x}_1 - \vect{x}_1\|) & \dots & \phi(\|\vect{x}_1 - \vect{x}_n\|) \\ \vdots & \ddots & \vdots \\ \phi(\|\vect{x}_n - \vect{x}_1\|) & \dots & \phi(\|\vect{x}_n - \vect{x}_n\|) \end{bmatrix} \begin{bmatrix} w_1 \\ \vdots \\ w_n \end{bmatrix} = \begin{bmatrix} d(\vect{q}_1) \\ \vdots \\ d(\vect{q}_n) \end{bmatrix} \]

RBF fucnctions

Wendland Basis Functions

Properties: - Go to zero beyond a radius \(\sigma\), good for sparse systems. - Positive definite - Their smoothness can be controlled, e.g., \(C^0\), \(C^2\), \(C^4\), etc.

For instance, a \(C^2\) Wendland function is defined as:

\[ \phi(r) = (1-\frac{r}{\sigma})^4_{+}(4\frac{r}{\sigma} + 1) \]

where \(r = \|\vect{x}_j - \vect{x}_i\|\) and \([x]_+ = \max(0, x)\).

Triharmonic Basis Functions

Triharmonic functions are defined as:

\[ \phi(r) = r^3 \]

It is very simple, but does not have compact support, meaning it does not go to zero beyond a certain radius.