Appearance-Mimicking Surfaces

Inspired by bas-reliefs, appearance-mimicking surfaces are thin surfaces, or 2.5D images whose normals approximate the normals of a 3D shape. Given a viewpoint and per-vertex depth bounds, the algorithm proposed ¹ finds a globally optimal surface that preserves the appearance of the target shape when observed from the designated viewpoint, while satisfying the depth constraints.

Problem Formulation

$S^{o}$ $S$ $\bold{o}$ $\bold{p}'$ $\bold{p}$ $\bold{op}$ ).

$d(S, S^{o}, \bold{o})$ $S^{o}$ $S$ is measured by the sum of the L2 norm of their normals at each point:

d(S, S^{o}, \bold{o}) = \int_{S} \Vert \bold{n}^{S}_{\phi(\bold{p}, \bold{o})} - \bold{n}^{S^{o}}_\bold{p} \Vert^{2} d\bold{p}

$\phi(\bold{p}, \bold{o}) = \bold{p}'$ $S$ $\bold{n}^{S^{o}}_\bold{p}$ $S^{o}$ $\bold{p}$ $d(S, S^{o}, \bold{o})$ .

Discretization

Preserving Surface Similarity

$S$ $M$ $p'$ $S$ $\bold{v}_i$ $\bold{v}_i$ can be written as:

\bold{v}_i = \bold{o} + \Vert \bold{v}_i - \bold{o} \Vert \frac{\bold{v}_i - \bold{o}}{\Vert \bold{v}_i - \bold{o} \Vert} = \bold{o} + \lambda_i \bold{\hat{v}}_i

$\bold{\hat{v}}_i$ $\bold{ov_i}$ $\lambda_i$ $\bold{o}$ $\bold{v}_i$ $M$ $M^o$ $\bold{\hat{v}}_i$ $\lambda_i$ $\lambda_i^o$ $M$ $\lambda_i$ :

\lambda^{min}_i \leq \lambda_i \leq \lambda^{max}_i

Using this representation, Eq. (1) can be discretized and linearized as:

\begin{align*} d(M, M^o, \bold{o}) = \sum_{i \in \bold{V}} w_i^2 A_i \Vert\bold{n}_i - \bold{n}_i^o \Vert^2 \\ &= \sum_{i \in \bold{V}} w_i^2 A_i \Vert\frac{(\bold{L} \bold{V})_i}{H_i} - \frac{(\bold{L}^o \bold{V}^o)_i}{H_i^o} \Vert^2 \\ &= \sum_{i \in \bold{V}} w_i^2 A_i \Vert\frac{(\bold{L} \bold{D}_\lambda \bold{\hat{V}})_i}{H_i} - \frac{(\bold{L}^o \bold{D}_{\lambda^o} \bold{\hat{V}})_i}{H_i^o} \Vert^2 \\ &= \sum_{i \in \bold{V}} w_i^2 A_i^o \Vert\frac{(\bold{L}^o \bold{D}_\lambda \bold{\hat{V}})_i}{H_i^o} - \frac{(\bold{L}^o \bold{D}_{\lambda^o} \bold{\hat{V}})_i}{H_i^o} \frac{\lambda_i}{\lambda_i^o}\Vert^2 \\ &= \sum_{i \in \bold{V}} w_i^2 A_i^o \Vert(\bold{L}^o \bold{D}_\lambda \bold{\hat{V}})_i - (\bold{L}^o \bold{D}_{\lambda^o} \bold{\hat{V}})_i \frac{\lambda_i}{\lambda_i^o}\Vert^2 \\ \end{align*}

$A_i$ $\bold{v}_i$ $w_i$ $\bold{v}_i$ $w_i$ $\bold{L}$ $M$ $\bold{D}_\lambda$ $\lambda_i$ on the diagonal.

We follow these conventions for notations:
$\bold{X}$ $M$ $\bold{X}^o$ $M^o$ .
$\bold{x}$ $\bold{D_x}$ $\bold{x}$ on the diagonal.

$\lambda$ $d(M, M^o, \bold{o})$ $\bold{\lambda}$ $\bold{D}_\lambda$ . The above equation can be further vectorized as:

d(M, M^o, \bold{o}) = \Vert \bold{D}_\sqrt{A^o} \bold{D}_w (\bold{\tilde{L}}^o \bold{D_\hat{V}} - \bold{D}_{\bold{L}_\theta}) \bold{S} \bold{\lambda} \Vert^2 = \Vert \bold{Q} \bold{\lambda} \Vert^2

\bold{L}_\theta = \bold{D_{(S \lambda_o)}}^{-1} \bold{\tilde{L}}^o \bold{D_\hat{V}} \bold{S} \bold{\lambda}^o

$\bold{Q} = \bold{D}_\sqrt{A^o} \bold{D}_w (\bold{\tilde{L}}^o \bold{D_\hat{V}} - \bold{D}_{\bold{L}_\theta}) \bold{S}$ .

$n = |\bold{V}^o|$ ,

$\bold{D}_\sqrt{A^o}$ is a 3n x 3n matrix with the square root of mass matrix coefficients repeated 3 times (1 for each dimension) on the diagonal.
$\bold{D}_w$ $\bold{w}$ repeated 3 times on the diagonal.
$\bold{\tilde{L}}^o$ $\bold{\tilde{L}}^o = \bold{L}^o \otimes \bold{I}_3$
$\bold{S}$ $\lambda_i$ $\bold{v}_i$ $\bold{I}_n \otimes [1,1,1]^T$

Allowing Disconnected Pieces

$\bold{\lambda}$ $\bold{\lambda}$ bounds could be:

$\bold{\lambda}_{min}$ : 10, 10, 10, 10
$\bold{\lambda}_{max}$ : 11, 11, 11, 11

$\bold{\lambda}$ bounds could be:

$\bold{\lambda}_{min}$ : 10, 10, 11, 11
$\bold{\lambda}_{max}$ : 11, 11, 12, 12

$\bold{\mu}$ $\mu_g$ $\mu_g \lambda^{min}_i \leq \lambda_i \leq \mu_g \lambda^{max}_i$ $i$ $g$ $|\bold{\mu}| =$ number of groups.

$\mu_g$ $g$ $\lambda_{gk}$ $\bold{v}_{gk}$ $\lambda_{gk}$ $\mu_g$ .

Optimization

$\lambda$ $\mu$ :

\begin{align*} & \min_{\bold{\lambda}, \bold{\mu}} \Vert \bold{Q} \bold{\lambda} \Vert^2 + \alpha \Vert \bold{\mu} \Vert^2 \\ \\ & \text{subject to } \\ & \bold{C}_I [\lambda \;\; \mu]^T \le \bold{d} \\ & \bold{C}_E [\lambda \;\; \mu]^T = \bold{b} \\ \end{align*}

$\alpha$ $10^{-7}$ $\bold{C}_I$ $\mu_g \lambda^{min}_i \leq \lambda_i \leq \mu_g \lambda^{max}_i$ $\bold{C}_E$ $\lambda_{gk}$ .

$\bold{\lambda}$ $\bold{\mu}$ $\bold{x}$ , we now have quadratic programming problem that can be solved using the libigl active set solver:


igl::active_set_params as;
Eigen::VectorXd x; // (n + |mu|) x 1
// B - linear coefficients, set to 0
// b - index of lambdas to be fixed
// Y - value of the fixed lambdas
// Aeq, Beq - empty matrices
// Aieq - inequality constraint matrix C_I
// Bieq - inequality constraint d, set to a 0 vector with dimension (n + |mu|) x 1
// lx, ux - empty vectors
// x - [lambda; mu]
igl::active_set(F.transpose() * F, B, b, Y, Aeq, Beq, Aieq, Bieq, lx, ux, as, x);

where F is:

F = \begin{bmatrix} \bold{Q} & \bold{0} \\ \bold{0} & \sqrt{\alpha} \cdot \bold{I} \end{bmatrix}

$\lambda_i$ $\mu_g$ .

Demo

The example main.cpp deforms a mesh along the z-axis (front view).

Implementation Details

$\bold{D}_\sqrt{A^o}$

Dimension: 3n x 3n

$\bold{M}$ :


Eigen::SparseMatrix<double> M;
igl::massmatrix(V, F, igl::MASSMATRIX_TYPE_VORONOI, M);

$\bold{M}$ $M_{ii}$ $\bold{v}_i$ ² $\bold{D}_\sqrt{A^o}$ should look like this:

\bold{D}_\sqrt{A^o} = \begin{bmatrix} \sqrt{M_{00}} & 0 & \dots & & & & & 0\\ 0 & \sqrt{M_{00}} & & & & & &\vdots \\ & & \sqrt{M_{00}} \\ & & & \sqrt{M_{11}} \\ & & & & \sqrt{M_{11}} \\ & & & & & \sqrt{M_{11}} \\ \vdots & & & & & & \ddots \\ 0 & 0 & \dots & & & 0 & \dots & \sqrt{M_{n-1,n-1}} \end{bmatrix}

$\bold{D}_w$

Dimension: 3n x 3n

$\bold{D}_\sqrt{A^o}$ $w$ of size n x 1 and repeat it along the diagonal:

\bold{D}_w = \begin{bmatrix} w_0 & 0 & \dots & & & & & 0\\ 0 & w_0 & & & & & &\vdots \\ & & w_0 \\ & & & w_1 \\ & & & & w_1 \\ & & & & & w_1 \\ \vdots & & & & & & \ddots \\ 0 & 0 & \dots & & & 0 & \dots & w_{n-1} \end{bmatrix}

$\bold{\tilde{L}}^o$

Dimension: 3n x 3n

$\bold{L}^o$ :


Eigen::SparseMatrix<double> cot, M_inv, L;
igl::cotmatrix(V, F, cot);
igl::invert_diag(M, M_inv);
L = M_inv * cot;

$\bold{\tilde{L}}^o$ is the Kronecker product between the cotangent matrix and 3 x 3 identity matrix:

\bold{\tilde{L}}^o = \bold{L}^o \otimes \bold{I}_3

\bold{\tilde{L}}^o = \begin{bmatrix} \begin{bmatrix} \textbf{L}^o_{00} && \\ &\textbf{L}^o_{00}& \\ &&\textbf{L}^o_{00} \\ \end{bmatrix} & \dots & \begin{bmatrix} \textbf{L}^o_{0,n-1} && \\ &\textbf{L}^o_{0,n-1}& \\ &&\textbf{L}^o_{0,n-1} \\ \end{bmatrix}\\ \vdots & \ddots &\vdots \\ \begin{bmatrix} \textbf{L}^o_{n-1,0} && \\ &\textbf{L}^o_{n-1,0}& \\ &&\textbf{L}^o_{n-1,0} \\ \end{bmatrix} & & \begin{bmatrix} \textbf{L}^o_{n-1,n-1} && \\ &\textbf{L}^o_{n-1,n-1}& \\ &&\textbf{L}^o_{n-1,n-1} \\ \end{bmatrix} \\ \end{bmatrix}

$\bold{S}$

Dimension: 3n x n
$\bold{S}$ $\lambda_i$ $\bold{v}_i$ $\bold{I}_n \otimes [1,1,1]^T$

\begin{bmatrix} \begin{bmatrix} 1 \\ 1\\ 1 \\ \end{bmatrix} & \dots & 0 \\ \vdots & \ddots &\vdots \\ 0 & \dots & \begin{bmatrix} 1\\ 1\\ 1\\ \end{bmatrix} \\ \end{bmatrix}

$\bold{C}_I$

$|\mu|$ )

$\bold{C}_I$ $\mu_g \lambda^{min}_i \leq \lambda_i \leq \mu_g \lambda^{max}_i$ $\bold{C}_I [\lambda \;\; \mu]^T \le \bold{0}$ . Below is an example of an inequality constraint for a mesh with 4 vertices and 2 groups.

\begin{bmatrix} -1 & 0 & 0 & 0 & \lambda_{min,00} & 0 \\ 0 & -1 & 0 & 0 & \lambda_{min,01} & 0 \\ 0 & 0 & -1 & 0 & 0 & \lambda_{min,10} \\ 0 & 0 & 0 & -1 & 0 & \lambda_{min,11} \\ 1 & 0 & 0 & 0 & -\lambda_{max,00} & 0 \\ 0 & 1 & 0 & 0 & -\lambda_{max,01} & 0 \\ 0 & 0 & 1 & 0 & 0 & -\lambda_{max,10} \\ 0 & 0 & 0 & 1 & 0 & -\lambda_{max,11} \\ \end{bmatrix} \begin{bmatrix} \lambda_0 \\ \lambda_1 \\ \lambda_2 \\ \lambda_3 \\ \mu_0 \\ \mu_1 \\ \end{bmatrix} \le \bold{0}

$\bold{\lambda}$

bounding box

$\lambda_i$ ³ $\lambda$ bounds.

bounding box

The above figure shows how main.cpp deforms a mesh from a left viewpoint. We assume the mesh faces the positive z-axis and the bounding box is roughly square.

\begin{align*} & \lambda_{max} = |OG|\\ & \lambda_{min} = |OE|\\ & (\lambda_i \bold{\hat{v}}_i) \; \cdot \; \bold{\hat{n}}_i \le \lambda_{max} \rightarrow \lambda_i \le \lambda_{max} / (\bold{\hat{v}}_i \; \cdot \; \bold{\hat{n}}_i)\\ & (\lambda_i \bold{\hat{v}}_i) \; \cdot \; \bold{\hat{n}}_i \ge \lambda_{min} \rightarrow \lambda_i \ge \lambda_{min} / (\bold{\hat{v}}_i \; \cdot \; \bold{\hat{n}}_i)\\ & lowerbound = \lambda_{max} / (\bold{\hat{v}}_i \; \cdot \; \bold{\hat{n}}_i) \\ & upperbound = \lambda_{min} / (\bold{\hat{v}}_i \; \cdot \; \bold{\hat{n}}_i) \end{align*}

Future Directions & Challenges

$\bold{\mu}$ frees the user from specifying individual depth constraints for each disconnected piece, I am still having trouble producing disconnected appearance mimicking surfaces. If the input mesh is all connected (like the bunny), I am not sure how to break up the faces after breaking the vertices into mulitple groups. If the input mesh has disconnected pieces, I am not sure how to determine which vertices belong to the same group, other than manually inspecting the mesh file.

References

1 Christian Schuller, Daniele Panozzo, Olga Sorkine-Hornung, Appearance-Mimicking Surfaces, 2014 ↩

2 Mark Meyer, Mathieu Desbrun, Peter Schröder and Alan H. Barr, Discrete Differential-Geometry Operators for Triangulated 2-Manifolds, 2003. ↩

3 Libigl tutorial on bounding boxes: https://github.com/libigl/libigl/blob/master/tutorial/105_Overlays/main.cpp ↩