Combi2k2

Differential Geometry of Surfaces

Consider a continuous surface:

\textbf{x}(u,v) = \begin{pmatrix} x(u,v)\\ y(u,v)\\ z(u,v) \end{pmatrix}, (u,v) \in \Omega \subset \mathbb{R}^2

Normal vector: $\textbf{n}(p) = \frac{\textbf{x}_u\times\textbf{x}_v}{\|\textbf{x}_u\times\textbf{x}_v\|}$
Normal curvature: pick a tangent direction $t$

\textbf{t} = \cos(\theta)\frac{\textbf{x}_u}{\|\textbf{x}_u\|} + \sin(\theta)\frac{\textbf{x}_v}{\|\textbf{x}_v\|}

curve $\gamma$ is the intersection of surface with the plane containing $\textbf{n}$ and tangent $\textbf{t}$ .

\kappa_n(\theta) = \textbf{K}(\gamma(\textbf{p}))

Principle directions

Euler's Theorem:

Directions of principal curvature are orthogonal and independent of parameterization

Principal curvatures:

maximum curvature: $\kappa_1 = \kappa_{\max} = \max_\varphi \kappa_n(\varphi)$
minimum curvature: $\kappa_2 = \kappa_{\min} = \min_\varphi \kappa_n(\varphi)$

Mean curvature:

H = \frac{\kappa_1+\kappa_2}{2} = \frac{1}{2\pi}\int_0^{2\pi}\kappa_n(\varphi)d\varphi

Gaussian curvature:

K = \kappa_1\cdot\kappa_2

Design: From Curves to Surfaces

Tensor product idea:

a surface is formed by sweeping (while potentially deforming) a curve. E.g:
- ruled surface (swept line)
- surface of revolution (circle is swept along line, grows and shrinks)
generalization: tensor product splines

\textbf{x}(u,v) = \sum_{i=0\dots m}\sum_{j=0\dots n} \textbf{b}_{ij} B_i^m(u)B_j^n(v)

But this method has few limitation:

patches need to be glued together for a more involved surface
- condition for maintaining tangent plane continuity can be tedious
- user cannot arbitrary move control vertices and maintain continuity
intricate constraints of tensor product constructs. E.g: spline order of 2 connected patches may have to match.
Also, inherent rectangular nature

Point Clouds

Why?:

Sometimes, easier to handle (esp. in hardware)
Typically, it is the original (or only) thing that’s available (nearly all 3d scanning devices produce point clouds)

Typical Scanning Pipeline

physical model $\to$ acquire point clouds $\to$ register point cloud

Why registration?

Fundamental problem in geometric data processing

appears in many shape analysis applications
detect manufacturing defects, or correspondences with templates

One of the best-known algorithms in computer graphics and computational geometry is mixing linear algebra & iterations.

Alignment of Scans

Given a pair of shapes, find the optimal rigid alignment (composition of translation & rotation) between them.

Intuition: want corresponding points to fit after transformation
Problem: we dont know what points actually match!

Iterative Closest Point (ICP)

Idea: iterate between finding correspondences and finding the transformation:

Given a pair of shapes, X and Y, iterate:

Step 1: for each $x_i\in X$ , find nearest neighbor $y_i\in Y$ ;
Step 2: find global deformation $R, t$ minimizing:

\sum_{i=1}^N \|\textbf{R}x_i+t-y_i\|_2^2

For the 1st step, there are some approaches for it. Logically, it is more or less like building Voronoi cell for the point set Y. Programmatically, I think people are using kd-tree to approximate this algorithm.

For the 2nd step, to find optimal rigid motion:

R_{opt}, t_{opt} = \argmin_{\textbf{R}, t} \sum_{i=1}^N\|\textbf{R}x_i+t-y_i\|_2^2

Good news: we have a closed form solution (called Kabsch algorithm)

\begin{align*} t_{opt} &= \bar{y} - \bar{x} \text{ where } \bar{x} = \frac{1}{N}\sum_{i=1}^N x_i, \bar{y} = \sum_{i=1}^N y_i\\ R_{opt} &= VU^T \text{ where } \sum_i (x_i-\bar{x})(y_i-\bar{y})^T = U\Sigma V^T \end{align*}

If $\det(R_{opt}) < 0$ (meaning $R_{opt}$ is a reflection) then $R_{opt} = V\text{diag}(1,1,-1)U^T$

Convergence: Intuition is the distance from each point in transformed mesh to the target mesh get closer and closer after each iteration. I am not sure if this distance sum is convex or not, but it is a good idea to know it is going down the hill toward minimum point.

Some variants:

Szymon Rusinkiewicz and Marc Levoy. "Efficient variants of the ICP algorithm." 3D Digital Imaging and Modeling. Vol. 1., 2001.
Helmut Pottmann et al. "Geometry and convergence analysis of algorithms for registration of 3D shapes." IJCV, 2006.
Szymon Rusinkiewicz, A Symmetric Objective Function for ICP, SIGGRAPH 2019

Normal Estimation & Outlier Removal

These are 2 fundamental problems in point cloud processing.

For normal estimation for a point $p$ $p$ :
- Find $k$ nearest neighbor of point $p$
- Calculate $n_{opt}=\argmin_{\|n\|=1}\sum_{i=1}^k((p_i-P)^Tn)^2$
- How to calculate this min argument is kind of a spectral problem

Outlier Removal

In 2D world:

If all points aligned, $\lambda_{\min}(C)=0$ and $\lambda_{\max}(C)$ is large in comparison.
If points are scattered randomly, then $\lambda_{\max}(C)\approx\lambda_{\min}(C)$
So point would not be close to a curve if $\frac{\lambda_1}{\lambda_2} > \epsilon$ for some threshold (this is often found through statistics).

Extension to 3D?

We expect 2 non-zero eigenvalues, so we can set threshold to $\frac{\lambda_1}{\lambda_2+\lambda_3}$
robust statistics can be leveraged as well

Implicit Surface

Definition:

\mathcal{S} = \{(x,y,z) | F(x,y,z)=c\}

i.e: the set of all points sharing the same value of a density function $f$ .
sometimes referred to as $F^{-1}(c)$

Property:

Normal: obviously, $\textbf{n} = \frac{\nabla F}{\|\nabla F\|}$
Curvatures: deduced by considering Frenet frame. The formula is quite complicated though.

Implicit Surfaces Visualization

Various approaches exist:

Ray Tracing
Marching Cubes
Voxel based ...

Idea: sample the function & locally approximate surface:

from inside/outside nodes...
guess local connectivity per cell
"march" along each intead of treating each cell

Implicit Processing

Level Set Method:

approach from computational science
with additional efficient data structures
based on Hamilton-Jacobi equation:

\frac{\partial f}{\partial t} + \frac{\partial x}{\partial t} \cdot \nabla f = 0

However, this also brings new drawbacks:

inherent volume loss
rarely variational/conservative

Duc Nguyen

Shape Analysis #3: Surface Representation