Title

Digital Geometry Processing
Exercise 8-Parameterization II
Edward Chien, edchien@bu.edu
Computer Graphics Group

Exercise 7 Commentary

  • Ceiling and floor functions recommended for determining isolines: \([\lceil \frac{\min}{\mathrm{\_interval\_size}} \rceil, \lfloor \frac{\max} {\mathrm{\_interval\_size}} \rfloor]\)
  • System structure comprehension question: (see whiteboard)
  • Linear interpolation review: (see whiteboard)

Exercise 8 Initial Notes

  • Added some skeleton code to the start of first function (copies vertices and faces, and finds a boundary vertex)
  • Take a look at previous boundary half-edge function
  • Texture application is done in the skeleton code (DGPExercisePlugin.cc); you only need to provide texture coordinates
  • Two useful functions to recall: “calc_edge_length(HalfedgeHandle)” and “calc_edges_weights()”

Convex combination maps

  • A discrete mapping is called a convex combination mapping if it satisfies the linear equations: \[\sum_{v_j \in \set{N}_1 \of{v_i}} w_{ij}(\vec{u}(v_j) - \vec{u}(v_i)) = 0\]

subject to:

\[w_{ij} > 0, \sum_{v_j \in \set{N}_1 \of{v_i}} w_{ij} = 1\]

Boundary Initialization

  • Map the boundary vertices to a circle with \(\_radius\) in the XY plane
BdyIni0.png BdyIni1.png BdyIni2.png

Boundary Initialization

  • \(\_radius\) is the diagonal length of the bounding box divided by 20 (also note availability of \(\_origin\))

  • Distribute the boundary vertices on the circle according to the boundary edge lengths

  • Map all the interior vertices to the origin: (0,0)

  • Store the texture coordinate with the function \(mesh\_.set\_texcoord2D(vh, Vec2d(x, y))\)

Iterative Solver

  • One way to solve the linear system for texture mapping is by simply iterating the following for all vertices:

\[\forall v_i \in \set{interior} : \vec{u}(v_i) \leftarrow \frac{1}{\sum_{v_j \in \set{N}_1 \of{v_i}} w_{ij}} \sum_{v_j \in \set{N}_1 \of{v_i}} w_{ij} \vec{u}(v_j)\]

Results

  • Texture after 50 iterations with iterative solver
ExplicitFace.png

Direct Solver

  • Another way of solving the linear system \(Lu = b\) is to do the implicit solve

  • \(L\) is the matrix of non-boundary cotan weights, \(u\) is the unknown texture coordinates and \(b\) stores the boundary condition

\[\forall v_i \in \set{interior}, \sum_{v_j \in \set{N}_1 \of{v_i}} w_{ij}(\vec{u}(v_j) - \vec{u}(v_i)) = 0\]

Direct Solution

  • Assume that the vertices are partitioned/sorted into interior vertices \(v_1, \dots, v_n\) and boundary vertices \(v_{n+1}, \dots, v_{n+m}\)
  • Setup \((n+m) \times (n+m)\) system of linear equations from the conditions for interior vertices and boundary vertices \[ \matrix{ \rlap{\laplace_{n \times (n+m)}} \\ \mat{0}_{m \times n} & \mat{I}_{m \times m} } \cdot \matrix{ \vec{u}_1\T \\ \vdots \\ \vec{u}_n\T \\ \vec{u}_{n+1}\T \\ \vdots \\ \vec{u}_{n+m}\T } \;=\; \matrix{ \vec{0}\T \\ \vdots \\ \vec{0}\T \\ \bar{\vec{u}}_{n+1}\T \\ \vdots \\ \bar{\vec{u}}_{n+m}\T } \]

Direct Solution

  • Simplify this \((n+m) \times (n+m)\) linear system \[ \matrix{ \laplace_{n \times n} & \laplace_{n \times m} \\ \mat{0}_{m \times n} & \mat{I}_{m \times m} } \cdot \matrix{ \vec{u}_1\T \\ \vdots \\ \vec{u}_n\T \\ \vec{u}_{n+1}\T \\ \vdots \\ \vec{u}_{n+m}\T } \;=\; \matrix{ \vec{0}\T \\ \vdots \\ \vec{0}\T \\ \bar{\vec{u}}_{n+1}\T \\ \vdots \\ \bar{\vec{u}}_{n+m}\T } \]
  • Move the \(m\) known boundary vertices to right hand side
    (then we don’t need the bottom \(m\) rows anymore) \[ \laplace_{n \times n} \cdot \matrix{ \vec{u}_1\T \\ \vdots \\ \vec{u}_n\T } \;=\; \matrix{ \vec{0}\T \\ \vdots \\ \vec{0}\T } -\laplace_{n \times m} \matrix{ \bar{\vec{u}}_{n+1}\T \\ \vdots \\ \bar{\vec{u}}_{n+m}\T } \]

Direct Solution

  • This yields an \(n \times n\) linear system to solve for \(u\) and \(v\) coordinates. \[ \mat{D}\mat{M} \cdot \matrix{ \vec{u}_1\T \\ \vdots \\ \vec{u}_n\T } \;=\; \mat{D}\matrix{ \vec{b}_1\T \\ \vdots \\ \vec{b}_n\T } \]

\[ \begin{align} \mat{M}_{ij} \;&=\; \begin{cases} \func{cot}\alpha_{ij} + \func{cot}\beta_{ij}, & i \ne j \,,\; j \in \set{N}_1\of{v_i} \setminus \partial\set{S} \\ -\sum_{v_j \in \set{N}_1\of{v_i}} \left( \func{cot}\alpha_{ij} + \func{cot}\beta_{ij} \right) & i=j \\ 0 & \text{otherwise} \end{cases} \\[2mm] \mat{D} \;&=\; \func{diag}\of{ \dots, \frac{1}{2A_i}, \dots} \\[2mm] \vec{b}_i \;&=\; -\sum_{v_j \in \set{N}_1\of{v_i} \cap \partial\set{S} } \left( \func{cot}\alpha_{ij} + \func{cot}\beta_{ij} \right) \bar{\vec{u}}_j \end{align} \]

cotanLaplace.png

Direct Solution

  • Let’s make the system symmetric by removing \(\mat{D}\).
    And let’s negate it to make the matrix positive definite. \[ -\mat{M} \cdot \matrix{ \vec{u}_1\T \\ \vdots \\ \vec{u}_n\T } \;=\; -\matrix{ \vec{b}_1\T \\ \vdots \\ \vec{b}_n\T } \]

\[ \begin{align} \mat{M}_{ij} \;&=\; \begin{cases} \func{cot}\alpha_{ij} + \func{cot}\beta_{ij}, & i \ne j \,,\; j \in \set{N}_1\of{v_i} \setminus \partial\set{S} \\ -\sum_{v_j \in \set{N}_1\of{v_i}} \left( \func{cot}\alpha_{ij} + \func{cot}\beta_{ij} \right) & i=j \\ 0 & \text{otherwise} \end{cases} \\[2mm] \vec{b}_i \;&=\; -\sum_{v_j \in \set{N}_1\of{v_i} \cap \partial\set{S} } \left( \func{cot}\alpha_{ij} + \func{cot}\beta_{ij} \right) \bar{\vec{u}}_j \end{align} \]

cotanLaplace.png

Results

  • The result of direct solver
implicitFace.png

Minimal Surfaces

  • Given an initial mesh and boundary constraints, we want to get the minimal surface

  • The minimal surface is the solution to the \(LX = 0\) equation

  • Fix the boundary vertex coordinates such that they satisfy the boundary condition

  • Question: How many coordinate functions are we solving for here? How many in the texture mapping case?

Results

  • The initial cylinder1 model and its minimal surface variant when keeping the lower and upper circle boundaries fixed
cylinder_minimal.png