Variational reconstruction using subdivision surfaces with continuous sharpness control

Combining both terms gives our variational optimization model:

$$\underset{\text{𝒑},\text{𝒉}}{\min }\{\Vert \text{𝑳}\text{𝒑}\Vert +\lambda \Vert \text{𝒗}-\text{𝑴}\text{𝒑}\Vert \}$$

p and h are values to be determined.

This variational optimization problem is highly non-linear, and also non-differentiable due to the use of the $L_1$ norm. To solve it, we let $\text{𝒒}=\text{𝑳}\text{𝒑}$ and $\text{𝒛}=\text{𝒗}-\text{𝑴}\text{𝒑}$ . The optimization model becomes a constrained problem:

$$\begin{array}{c}\underset{\mathit{p},\mathit{h}}{\min }\\ \text{subject to}\end{array}\begin{array}{ll}\hfill & \left|\right|\mathit{q}\left|\right|+\lambda \left|\right|\mathit{z}\left|\right|\hfill \\ \hfill & \mathit{q}=\mathit{L}\mathit{p},\mathit{z}=\mathit{v}-\mathit{M}\mathit{p}\hfill \end{array}$$

We construct the following augmented Lagrangian functional:

$$\begin{array}{c}L(\mathit{p},\mathit{h},\mathit{q},\mathit{z};{\lambda }_q,{\lambda }_z)=\left|\right|\mathit{q}\left|\right|+\lambda \left|\right|\mathit{z}\left|\right|+\langle {\lambda }_q,\mathit{q}-\mathit{L}\mathit{p}\rangle \\ +\frac{a_q}{2}\left|\right|\mathit{q}-\mathit{L}\mathit{p}|{|}^2+\langle {\lambda }_z,\mathit{z}-(\mathit{v}-\mathit{M}\mathit{p})\rangle \\ +\frac{a_z}{2}\left|\right|\mathit{z}-(\mathit{v}-\mathit{M}\mathit{p})|{|}^2\end{array}$$

where ${\lambda }_q$ and ${\lambda }_z$ are the Lagrangian multipliers, $⟨,⟩$ is the vector dot product operator, and $a_q$ and $a_z$ are two positive numbers. We now seek a solution to the saddle-point problem:

$$\underset{\text{𝒑},\text{𝒉},\text{𝒒},\text{𝒛}}{\min }\underset{{\lambda }_q,{\lambda }_z}{\max }L(\text{𝒑},\text{𝒉},\text{𝒒},\text{𝒛};{\lambda }_q,{\lambda }_z)$$

by using Algorithm 1. Algorithm 1 involves solving several sub-problems, whose details are now described.

Initialization of h. The initial sharpness is set based on coarse detection of sharp features. Specifically, for each edge $e$ of the initial control mesh $S_{\text{c}}^0$ , we use a threshold ${\theta }_0$ to detect whether $e$ is a candidate crease edge. Let ${\theta }_e$ be the angle between the normals of the two faces containing $e$ . If ${\theta }_e>{\theta }_0$ , $h_e=1$ ; otherwise, $h_e=0$ .

p subproblem. Fixing $\text{𝒉},\text{𝒒},\text{𝒛}$ , we solve the following quadratic equation:

$$\begin{array}{c}\underset{\text{𝒑}}{\min }⟨{\lambda }_q,\text{𝒒}-\text{𝑳}\text{𝒑}⟩+\frac{a_q}{2}{||\text{𝒒}-\text{𝑳𝒑}||}^2\hfill \\ +⟨{\lambda }_z,\text{𝒛}-(\text{𝒗}-\text{𝑴}\text{𝒑})⟩+\frac{a_z}{2}{||\text{𝒛}-(\text{𝒗}-\text{𝑴𝒑})||}^2\hfill \end{array}$$

This can be converted into a linear system.

h subproblem. Fixing $\text{𝒑},\text{𝒒},\text{𝒛}$ , we find the sharpness h which only affects the subdivision rule. Hence, the h-sub problem is

$$\underset{\text{𝒉}}{\min }⟨{\lambda }_z,\text{𝒛}-(\text{𝒗}-M(\text{𝒉})\text{𝒑})⟩+\frac{a_z}{2}{\Vert \text{𝒛}-(\text{𝒗}-M(\text{𝒉})\text{𝒑})\Vert }^2$$

To solve this minimization problem, we adopt particle swarm optimization (PSO) [ 31 ], an evolutionary procedure. It starts from many random initialization seeds. At each iteration a set of candidate solutions is sought, the score of each solution is calculated, and the solutions are updated in the search space by shifting them towards the best current solution.

q subproblem. Fixing $\text{𝒑},\text{𝒉},\text{𝒛}$ , we find q by solving:

$$\underset{\text{𝒒}}{\min }\{\Vert \text{𝒒}\Vert +⟨{\lambda }_q,\text{𝒒}-\text{𝑳}\text{𝒑}⟩+\frac{a_q}{2}{\Vert \text{𝒒}-\text{𝑳}\text{𝒑}\Vert }^2\}$$

After reformulation, we have

$$\underset{\text{𝒒}}{\min }\{\underset{i=0}{\overset{m}{\sum }}(\Vert q_i\Vert +\frac{a_q}{2}{\Vert q_i-{(\text{𝑳}\text{𝒑}-\frac{{\lambda }_q}{a_q})}_i\Vert }^2+c)\}$$

This problem is decomposable and has the closed form solution:

$$\text{𝒒}=\max \{0,1-\frac{1}{a_q\Vert w_q\Vert }\}{w}_q$$

where $w_q=\text{𝑳}\text{𝒑}-{\lambda }_q/a_q.$

z subproblem. Fixing $\text{𝒑},\text{𝒉},\text{𝒒}$ , we find z by solving:

$$\underset{\text{𝒛}}{\min }\{\lambda \Vert \text{𝒛}\Vert +⟨{\lambda }_z,\text{𝒛}-(\text{𝒗}-\text{𝑴}\text{𝒑})⟩+\frac{a_z}{2}{\Vert \text{𝒛}-(\text{𝒗}-\text{𝑴}\text{𝒑})\Vert }^2\}$$

which also has a closed form solution:

$$\text{𝒛}=\max \{0,1-\frac{\lambda }{a_z\Vert w_z\Vert }\}{w}_z$$

where $w_z=\text{𝒗}-\text{𝑴}\text{𝒑}-{\lambda }_z/a_z.$