typora-root-url
./

Digital_Geometry_Processing

Official Page: DGP_2020_spring

Video: bilibli

Code: github

All slides: slides

Goal: Basic knowledge about polygon mesh processing

Reference:

• Book: Polygon Mesh Processing
• Paper: http://kesen.realtimerendering.com/

Geometry Representations

Point cloud

$\mathcal{p}={p_1,...,p_{N_v}},p_i=\begin{pmatrix}x_i\y_i\z_i\end{pmatrix}\in \mathcal{R}^3$

A set of data point in some coordinate system

Scanner

Depth camera

Signed distance field (SDF)

The distance of a a given point $x$ from the boundary of $\Omega$:

$$d(x,\partial\Omega)=\mathrm{min}_{y\in \partial\Omega}d(x,y)$$

$$f(x)=\left{\begin{matrix}-d(x,\partial \Omega)&\text{if }x\in \Omega\d(x,\partial \Omega)&\text{if }x\in \Omega^c\end{matrix}\right.$$

Truncated signed distance field (TSDF)

• Less memory than SDF

Implicit function

Singed distance field is also an implicit function

Grid

Pixel, Voxel

• Image
  • 
• Voxel
  • 
• Quad mesh
  • 
• All-Hex mesh
  • 

Quad-tree, Octree

Partitioning rule

• The commonly-used octant partitioning depends on:
  • the existence of the shape inside the octant
  • the partitioning is performed until the max tree depth is reached

Patch-based octree

• paper

  • O-CNN: Octree-based Convolutional Neural Networks for 3D Shape Analysis
  • Adaptive O-CNN: A Patch-based Deep Representation of 3D Shapes

• The partitioning rule of the octree

  • For any octree $O$ which is not at the max depth level, subdivide it if the local surface $S_O$ restricted by it is not empty and the Hausdorff distance $d_H(S_O,P_O)$ larger than a predefined threshold.

Mesh

Triangle Mesh

• A collection of triangles
  • without any particular mathematical structure
• Each triangle: a segment of a piecewise linear surface representation
• Geometric component
  • Discrete vertices : $V={v_1,...,v_{N_V}}$
• Topological component
  • Triangle: $F={f_1,...,f_{N_F}}$
  • Edge: $E={e_1,...,e_{N_E}}$

2-manifold

Euler formula

$g$ = genus

Barycentric coordinate

Tetrahedral Mesh

Data structure

Halfedge

Implementation thinking

• Code: halfedge data implementation
  • structure
  • std::vector

File format

Obj

index begin from 1 not 0

Off

Homework 1

• shortest path
  • Input: two vertices
  • Output: a edge path connecting the input two vertices with shortest length
  • How about the geodesic path?
• Minimal spanning tree
  • Input: some (>2) vertices
  • Output: a tree passing through all input vertices with minimum length
  • algorithm
    • For each pair of terminal points $V_a\in \mathcal{P}$ and $V_b\in \mathcal{P}$, compute the shortest path $\mathcal{C}_{a,b}$ between $V_a$ and $V_b$ on $\mathcal{g}$
    • Construct a complete graph with the node set $\mathcal{P}$. The weight of each edge $\bar{V_a V_b}$ is equal to the length of $\mathcal{C}_{a,b}$
    • Construct an MST for this shortest distance graph
    • All mesh edges in the shortest paths that correspond to edges in the MST form an approximate Steiner tree for $\mathcal{g}$

Discrete Differential Geometry

Mesh Smoothing

Mesh Parameterizations

Deformation

Coordinates

Repairing

Mapping

Polycube

Surface Mapping

Morphing

Atlas Generation

Simplification

Spherical Parameterizations

Directional Field

Remeshing

Delaunay Triangulation