A Novel Stretch Energy Minimization Algorithm for Equiareal Parameterizations

Abstract

Surface parameterizations have been widely applied to computer graphics and digital geometry processing. In this paper, we propose a novel stretch energy minimization (SEM) algorithm for the computation of equiareal parameterizations of simply connected open surfaces with very small area distortions and highly improved computational efficiencies. In addition, the existence of nontrivial limit points of the SEM algorithm is guaranteed under some mild assumptions of the mesh quality. Numerical experiments indicate that the accuracy, effectiveness, and robustness of the proposed SEM algorithm outperform the other state-of-the-art algorithms. Applications of the SEM on surface remeshing, registration and morphing for simply connected open surfaces are demonstrated thereafter. Thanks to the SEM algorithm, the computation for these applications can be carried out efficiently and reliably.

Appendix: Derivations of Gradients of the Stretch Energy

In this section, we derive the explicit formulas (17) and (18) for the gradients of the stretch energy.

Proposition 1

Given a mesh ${\mathcal {M}}$ of n vertices and a bijective piecewise affine mapping $f:{\mathcal {M}}\rightarrow {\mathcal {D}}\subset {\mathbb {C}}$. Let ${\mathbf {f}}=(f(v_1), \ldots , f(v_n))^\top$ and $L({\mathbf {f}})$ be defined as (14). Suppose $[{v}_j,{v}_k]\in {\mathcal {E}}({\mathcal {M}})$. Then Eq. (17) holds, for $s=1,2$.

Proof

For each edge $[{v}_j,{v}_k]\in {\mathcal {E}}({\mathcal {M}})$,

$$\begin{aligned} \left[ ({\mathbf {f}}^s)^\top \frac{\partial L({\mathbf {f}})}{\partial {\mathbf {f}}^s}\right] _{j,k}&= \sum _{\alpha =1}^n {\mathbf {f}}^s_{\alpha } \frac{\partial L_{\alpha ,j}}{\partial {\mathbf {f}}_k^s} = \sum _{\alpha \ne j, k} {\mathbf {f}}^s_{\alpha } \frac{\partial L_{\alpha ,j}}{\partial {\mathbf {f}}_k^s} + {\mathbf {f}}^s_{j} \frac{\partial L_{j,j}}{\partial {\mathbf {f}}_k^s} + {\mathbf {f}}^s_{k} \frac{\partial L_{k,j}}{\partial {\mathbf {f}}_k^s} \\&= \sum _{\alpha \ne j, k} ({\mathbf {f}}^s_{\alpha }-{\mathbf {f}}^s_j) \frac{\partial L_{\alpha ,j}}{\partial {\mathbf {f}}_k^s} + ({\mathbf {f}}^s_{k}-{\mathbf {f}}^s_j) \frac{\partial L_{k,j}}{\partial {\mathbf {f}}_k^s} \\&= -\frac{1}{2} \sum _{[{v}_\alpha , {v}_j, {v}_k]\in {\mathcal {F}}({\mathcal {M}})} ({\mathbf {f}}^s_{\alpha }-{\mathbf {f}}^s_j) \frac{2{\mathbf {f}}^s_k - {\mathbf {f}}^s_\alpha - {\mathbf {f}}^s_j}{2|[{v}_i, {v}_j, {v}_k]|} \\&~~~~~ -\frac{1}{2} ({\mathbf {f}}^s_{k}-{\mathbf {f}}^s_j) \sum _{[{v}_\alpha , {v}_j, {v}_k]\in {\mathcal {F}}({\mathcal {M}})} \frac{{\mathbf {f}}^s_j - {\mathbf {f}}^s_\alpha }{2|[{v}_\alpha , {v}_j, {v}_k]|} \\&= -\frac{1}{2} \sum _{[{v}_\alpha , {v}_j, {v}_k]\in {\mathcal {F}}({\mathcal {M}})} \frac{({\mathbf {f}}_k^s-{\mathbf {f}}_\alpha ^s)({\mathbf {f}}_\alpha ^s-{\mathbf {f}}_j^s)}{2|[{v}_\alpha , {v}_j, {v}_k]|}. \end{aligned}$$

On the other hand, the diagonal entries

$$\begin{aligned} \left[ ({\mathbf {f}}^s)^\top \frac{\partial L({\mathbf {f}})}{\partial {\mathbf {u}}^s}\right] _{j,j}&= \sum _{\alpha =1}^n {\mathbf {f}}^s_{\alpha } \frac{\partial L_{\alpha ,j}}{\partial {\mathbf {f}}_j^s} = \sum _{\alpha \ne j} {\mathbf {f}}^s_{\alpha } \frac{\partial L_{\alpha ,j}}{\partial {\mathbf {f}}_j^s} + {\mathbf {f}}^s_{j} \frac{\partial L_{j,j}}{\partial {\mathbf {f}}_j^s} = \sum _{\alpha \ne j} ({\mathbf {f}}^s_{\alpha } - {\mathbf {f}}^s_{j}) \frac{\partial L_{\alpha ,j}}{\partial {\mathbf {f}}_j^s} \\&= -\frac{1}{2} \sum _{\alpha \ne j} ({\mathbf {f}}^s_{\alpha } - {\mathbf {f}}^s_{j}) \sum _{[{v}_\alpha , {v}_j, {v}_\beta ]\in {\mathcal {F}}({\mathcal {M}})} \frac{{\mathbf {f}}^s_\alpha - {\mathbf {f}}^s_\beta }{2 |[{v}_\alpha , {v}_j, {v}_\beta ]|} \\&= -\frac{1}{2} \sum _{[{v}_\alpha , {v}_j, {v}_\beta ]\in {\mathcal {F}}({\mathcal {M}})} \frac{({\mathbf {f}}^s_\alpha - {\mathbf {f}}^s_\beta )^2}{2 |[{v}_\alpha , {v}_j, {v}_\beta ]|}. \end{aligned}$$

$\square$

Proposition 2

Given a mesh ${\mathcal {M}}$ of n vertices and a bijective piecewise affine mapping $f:{\mathcal {M}}\rightarrow {\mathcal {D}}\subset {\mathbb {C}}$. Let ${\mathbf {f}}=(f(v_1), \ldots , f(v_n))^\top$ and $L({\mathbf {f}})$ be defined as (14). Suppose $[{v}_j,{v}_k]\in {\mathcal {E}}({\mathcal {M}})$. Then Eq. (18) holds, for $(s,t)=(1,2), (2,1)$.

Proof

For each edge $[{v}_j,{v}_k]\in {\mathcal {E}}({\mathcal {M}})$,

$$\begin{aligned} \left[ ({\mathbf {f}}^s)^\top \frac{\partial L({\mathbf {f}})}{\partial {\mathbf {f}}^t}\right] _{j,k}&= \sum _{\alpha =1}^n {\mathbf {f}}^s_{\alpha } \frac{\partial L_{\alpha ,j}}{\partial {\mathbf {f}}_k^t} = \sum _{\alpha \ne j, k} {\mathbf {f}}^s_{\alpha } \frac{\partial L_{\alpha ,j}}{\partial {\mathbf {f}}_k^t} + {\mathbf {f}}^s_{j} \frac{\partial L_{j,j}}{\partial {\mathbf {f}}_k^t} + {\mathbf {f}}^s_{k} \frac{\partial L_{k,j}}{\partial {\mathbf {f}}_k^t} \\&= \sum _{\alpha \ne j, k} ({\mathbf {f}}^s_{\alpha }-{\mathbf {f}}^s_j) \frac{\partial L_{\alpha ,j}}{\partial {\mathbf {f}}_k^s} + ({\mathbf {f}}^s_{k}-{\mathbf {f}}^s_j) \frac{\partial L_{k,j}}{\partial {\mathbf {f}}_k^s} \\&= -\frac{1}{2} \sum _{[{v}_\alpha , {v}_j, {v}_k]\in {\mathcal {F}}({\mathcal {M}})} ({\mathbf {f}}^s_{\alpha }-{\mathbf {f}}^s_j) \frac{2{\mathbf {f}}^t_k - {\mathbf {f}}^t_\alpha - {\mathbf {f}}^t_j}{2|[{v}_i, {v}_j, {v}_k]|} \\&~~~~~ -\frac{1}{2} ({\mathbf {f}}^s_{k}-{\mathbf {f}}^s_j) \sum _{[{v}_\alpha , {v}_j, {v}_k]\in {\mathcal {F}}({\mathcal {M}})} \frac{{\mathbf {f}}^t_j - {\mathbf {f}}^t_\alpha }{2|[{v}_\alpha , {v}_j, {v}_k]|} \\&= -\frac{1}{2} \sum _{[{v}_\alpha , {v}_j, {v}_k]\in {\mathcal {F}}({\mathcal {M}})} \frac{2({\mathbf {f}}_k^s-{\mathbf {f}}_\alpha ^s)({\mathbf {f}}_\alpha ^t-{\mathbf {f}}_j^t) - ({\mathbf {f}}_j^s-{\mathbf {f}}_\alpha ^s)({\mathbf {f}}_\alpha ^t-{\mathbf {f}}_k^t)}{2 |[{v}_\alpha , {v}_j, {v}_k]|}. \end{aligned}$$

On the other hand, the diagonal entries

$$\begin{aligned} \left[ ({\mathbf {f}}^s)^\top \frac{\partial L({\mathbf {f}})}{\partial {\mathbf {f}}^t}\right] _{j,j}&= \sum _{\alpha =1}^n {\mathbf {f}}^s_{\alpha } \frac{\partial L_{\alpha ,j}}{\partial {\mathbf {f}}_j^t} = \sum _{\alpha \ne j} {\mathbf {f}}^s_{\alpha } \frac{\partial L_{\alpha ,j}}{\partial {\mathbf {f}}_j^t} + {\mathbf {f}}^s_{j} \frac{\partial L_{j,j}}{\partial {\mathbf {f}}_j^t} = \sum _{\alpha \ne j} ({\mathbf {f}}^s_{\alpha } - {\mathbf {f}}^s_{j}) \frac{\partial L_{\alpha ,j}}{\partial {\mathbf {f}}_j^t} \\&= -\frac{1}{2} \sum _{\alpha \ne j} ({\mathbf {f}}^s_{\alpha } - {\mathbf {f}}^s_{j}) \sum _{[{v}_\alpha , {v}_j, {v}_\beta ]\in {\mathcal {F}}({\mathcal {M}})} \frac{{\mathbf {f}}^t_\alpha - {\mathbf {f}}^t_\beta }{2 |[{v}_\alpha , {v}_j, {v}_\beta ]|} \\&= -\frac{1}{2} \sum _{[{v}_\alpha , {v}_j, {v}_\beta ]\in {\mathcal {F}}({\mathcal {M}})} \frac{({\mathbf {f}}^s_\alpha - {\mathbf {f}}^s_\beta )({\mathbf {f}}^t_\alpha - {\mathbf {f}}^t_\beta )}{2 |[{v}_\alpha , {v}_j, {v}_\beta ]|}. \end{aligned}$$

$\square$