typora-root-url |
---|
./ |
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/
$\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
The distance of a a given point
- Less memory than SDF
Singed distance field is also an implicit function
- 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
-
paper
-
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.
- For any octree
- 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}}$
- Discrete vertices :
- Topological component
- Triangle:
$F={f_1,...,f_{N_F}}$ - Edge:
$E={e_1,...,e_{N_E}}$
- Triangle:
Implementation thinking
- Code: halfedge data implementation
- structure
- std::vector
index begin from 1 not 0
- 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}$
- For each pair of terminal points