Optimizer¶

smooth.optimize lowers a shape objective plus an inversion penalty by nonlinear conjugate gradients, every step projected onto the vertex’s target. The objective per accepted iteration, from two real runs:

F/quad, the exact objective the stage log records after each accepted iteration (log scale on the right). Annulus: 1.77 → 0.38 in 114 iterations (stopped: relative drop 9.2e-07 below 1e-06). Tangled square: 4 inverted at the start; one stage per delta, shaded in turn, widest first: 1 (6), 0.3 (58), 0.1 (1), 0.03 (1), 0.01 (1) iterations; no inverted quad from iteration 8. The exact F can rise while the descent lowers the barrier-free one it actually minimises. The optimizer alone at delta=0.01 gets 1 iteration and stops: no step lowers the objective (stalled at 9.877e+07).

Key points¶

It minimises \(\varphi\), which is 1 only for a square: angles and edge ratio, not size, so it undoes designed grading (Boundary layers and grading).
It untangles only with a wide \(\delta\): the exact \(\varphi\) is a wall at a folded corner (plot below).

The metric¶

On a quad corner let \(a\), \(b\) be the edges to the next and previous corner (counter-clockwise), \(J=[a\ b]\), and \(n\) the reference normal (the surface’s, see Constraints and projection):

\[s=\frac{(a\times b)\cdot n}{|a|\,|b|}, \qquad \varphi=\frac{\|J\|_F^2\,\|J^{+}\|_F^2}{d^2}=\frac{(|a|^2+|b|^2)^2}{4\,|a\times b|^2}\ \ge 1,\quad d=2 .\]

\(s\) is the signed sine of the corner angle; \(\varphi\) the squared condition number of \(J\) over \(d^2\). Both are dimensionless; \(\varphi\) is blind to orientation, hence a separate penalty:

\[F(x)=\sum_{q}\frac14\sum_{c\in q}\Bigl[\,w_q\,(\varphi_c-1)+\kappa\,\max(0,\ \varepsilon-s_c)\Bigr].\]

The barrier and the width delta¶

With \(K=(|a|^2+|b|^2)^2/(4|a|^2|b|^2)\), \(\varphi=K/s^2\). The descent uses a regularised sine:

\[s_\delta=\tfrac12\bigl(s+\sqrt{s^2+4\delta^2}\bigr)>0, \qquad \varphi_\delta=\frac{c\,K}{s_\delta^{2}},\quad c=s_\delta(1)^2 .\]

in the plot	meaning
x axis	\(s\) of one corner: 1 at a right angle, \(\le 0\) when folded
y axis	that corner’s term of \(F\), log scale, for equal edges (\(K=1\))
dashed grey, exact \(\varphi=1/s^2\)	the shape term; infinite at \(s=0\), so a folded corner can never be pulled across
blue, \(\varphi_\delta\)	what the descent minimises: finite everywhere and still falling through \(s=0\), so a fold can be undone; 1 at \(s=1\), like \(\varphi\)
red (box ticked), \(\varphi_\delta-1+\kappa\max(0,\varepsilon-s)\)	adds the inversion penalty: a steep slope \(\kappa\) for any corner below \(\varepsilon\)
slider	\(\delta\): wide flattens \(\varphi_\delta\) below zero (untangles, but loose shape); narrow approaches \(\varphi\) (sharp shape, a wall again)

Here eps = 0.05, kappa = 1000 and the default delta = 0.01. untangle_schedule() is a delta-continuation preset of optimize, not a separate method: one stage of 60 iterations per delta in 1, 0.3, 0.1, 0.03, 0.01, widest first; suggest_schedule puts it in front when a quad starts inverted. The logs always report the exact phi.

The step and its scale¶

Direction: Fletcher-Reeves conjugate gradients on the projected analytic gradient.
Line search: doubling, then golden section on \(F(\mathrm{snap}(x+\alpha d))\); a trial adding an inverted quad is refused.
Scale: the unit is the local edge length \(\ell_v\): the largest move per unit \(\alpha\) is one \(\ell_v\), and the tolerances count edge lengths. So units do not matter, and a constant factor on \(F\) cancels:

On the annulus, 50 iterations: scaling the objective (weights and kappa) by 10⁻³ or 10³ moves no vertex more than 5e-08 shortest edges; scaling the coordinates, 3e-07.

Parameters¶

parameter	default	meaning
`iters`	`20`	maximum conjugate-gradient iterations
`normals`	`None`	reference normals (default: the input’s winding; pass the surface’s)
`elements`	`None`	boolean mask of quads: only their vertices move, plus the quads they touch count (the local variant)
`alpha_max`	`1.0`	cap on a step, in local edge lengths
`restart`	`'halve'`	`'halve'` halves the Fletcher-Reeves beta on every second iteration, `'none'` is plain Fletcher-Reeves
`kappa`	`1000.0`	inversion-penalty weight per corner on the sum objective
`eps`	`0.05`	scaled-J threshold below which a corner is penalised
`delta`	`0.01`	barrier-removal width of the descent metric; 0 descends on the exact phi
`tol_step`	`0.0001`	stop when the accepted step is below this many local edge lengths
`tol_rel`	`1e-06`	stop when the relative drop of F in one iteration is below this
`weights`	`None`	per-quad weights on the shape term (0: that quad’s shape is irrelevant; the penalty still applies)

The gradient

With \(A=|a|^2\), \(B=|b|^2\), \(\mathrm{d}=a\cdot b\), \(C=|a\times b|^2=AB-\mathrm d^2\), \(g=(a\times b)\cdot n\) and the reference normals held fixed:

\[\frac{\partial\varphi}{\partial a}=\frac{(A+B)\,a}{C}-\frac{(A+B)^2\,(B\,a-\mathrm d\,b)}{2\,C^2}, \qquad \frac{\partial s}{\partial a}=\frac{b\times n}{\sqrt{AB}}-\frac{g\,a}{A\sqrt{AB}}, \quad \frac{\partial s}{\partial b}=\frac{n\times a}{\sqrt{AB}}-\frac{g\,b}{B\sqrt{AB}},\]

(\(b\): swap \(a\leftrightarrow b\), \(A\leftrightarrow B\)); a corner’s vertex receives \(-(\partial_a+\partial_b)\), its neighbours \(\partial_a\), \(\partial_b\). With \(\delta>0\): \(\partial\varphi_\delta/\partial a=c\,[\,\partial_aK/s_\delta^2-2K\,s_\delta'\,\partial_a s/s_\delta^3\,]\).

References¶

P. M. Knupp, “Algebraic mesh quality metrics”, SIAM J. Sci. Comput. 23(1), 193-218 (2001), doi:10.1137/S1064827500371499. Used for: An algebraic theory of mesh quality metrics built on the Jacobian; the element condition number measures the distance of an element to the set of degenerate elements. Here \(\varphi\) is the square of the Frobenius condition number of \(J\), scaled by \(d^2\).
L. A. Freitag, P. M. Knupp, “Tetrahedral mesh improvement via optimization of the element condition number”, Int. J. Numer. Meth. Engng 53(6), 1377-1391 (2002), doi:10.1002/nme.341. Used for: A condition-number shape measure for tetrahedra that gives the distance of a tetrahedron from the set of inverted elements, optimised with a mean-quality and a worst-element objective.
J. M. Escobar, E. Rodriguez, R. Montenegro, G. Montero, J. M. Gonzalez-Yuste, “Simultaneous untangling and smoothing of tetrahedral meshes”, Comput. Methods Appl. Mech. Engrg. 192(25), 2775-2787 (2003), doi:10.1016/S0045-7825(03)00299-8. Used for: Untangling and smoothing treated together, for tetrahedra (as its title says). The barrier-free \(\varphi_\delta\) above is this implementation’s own formulation; no formula of that paper is claimed here.
K. Mittal, P. Fischer, “Mesh smoothing for the spectral element method”, J. Sci. Comput. 78(2), 1152-1173 (2019), doi:10.1007/s10915-018-0812-9. Used for: The approach this smoother follows for spectral-element meshes. Cited as a record; its method is not summarised here.
K. Mittal, “Spectral element mesh generation and improvement methods”, M.S. thesis, University of Illinois at Urbana-Champaign (2016), hdl:2142/95509. Used for: With the paper above, the mesh-improvement approach this smoother follows for spectral-element meshes.
R. Fletcher, C. M. Reeves, “Function minimization by conjugate gradients”, The Computer Journal 7(2), 149-154 (1964), doi:10.1093/comjnl/7.2.149. Used for: A conjugate-gradient method for unconstrained minimisation.
J. Nocedal, S. J. Wright, Numerical Optimization, 2nd ed., Springer (2006), doi:10.1007/978-0-387-40065-5. Used for: A textbook on the optimization methods named here (line search, conjugate gradients).