# How to numerically optimize affine transformations?

I need to optimize affine transformations for of a set of triangles using energy function based on the connectivity.

The energy of an edge $$e_j$$ between triangles $$T_a, T_b$$ is given by $$E_j = \left[(A_a v_{a,1} + t_a) - (A_b v_{1,b} + t_b) \right]+ \left[(A_a v_{a,2} + t_a) - (A_b v_{2,b} + t_b) \right]$$

where $$(A_a, t_a)$$ and $$(A_b, t_b)$$ are affine transformations on the triangles adjacent to the edge and $$v_1$$ and $$v_2$$ are the vertices of the edge. The solution $$v_i \equiv 0$$ is prevented by an additional deformation energy on the triangles, like the conformal energy.

After the optimization, we want to have

$$v_{a,1}=v_{b,1}, \quad v_{a,2}=v_{b,2} \quad \Rightarrow E_j = 0$$

My problem is, that this is a non-linear problem, which is hard for solvers. I am using Google Ceres with line-search, but it often fails to find a valid line-search stepsize when optimizing

$$\begin{pmatrix} a_1 & a_2 \\ a_3 & a_4 \end{pmatrix}, \begin{pmatrix}t_1 \\ t_2\end{pmatrix}$$

as a vector $$(a_1, a_2, a_3, a_4, \dots, t_1, t_2, \dots)$$.

For some transformations, there are more favorable parameterizations, e.g.

Rotation can be parameterizized as

$$\begin{pmatrix} \cos \alpha & -\sin\alpha \\ \sin \alpha & \cos \alpha \end{pmatrix}, \begin{pmatrix}t_1 \\ t_2\end{pmatrix}$$

optimizing the vector $$(\alpha, \dots, t_1, t_2, \dots)$$.

Shearing can be optimized using

$$\begin{pmatrix} 1 & s_1 \\ s_2 & 1 \end{pmatrix}, \begin{pmatrix}t_1 \\ t_2\end{pmatrix}$$

optimizing the vector $$(s_1, s_2, \dots, t_1, t_2, \dots)$$.

But for general deformations, I do not see which parameterization of the transformation matrix would fit and optimizing the coefficients directly probably lets the solver fail (or not converge) because it yields no good gradient.

So what is the best way to optimize affine transformations to find triangle deformations?

Here a graphic what should be optimized:

The final optimization objective is:

Given a set of Triangles

$$T=\{t_1=[v_1, v_2, v_3], t_2=[v_4, v_5, v_6], ßdots\}$$

without shared vertices in the set and the information about the shared vertices of common edges as a separate set

$$E=\{[a,b,c,d], \dots|a\sim c, b\sim d\}$$

where $$\overline{ab}$$ and $$\overline{cd}$$ are the same edges, when all triangles are re-assembled to a mesh.

Find affine transformations $$A_i+t_i$$ for all triangles, such that for two adjacent triangles $$t_1=[a,b,x]$$ and $$t_2=[c,d,y]$$ holds

$$A_1 a + t_1 = A_2 c + t_2 \quad\wedge\quad A_1 c + t_1 = A_2 d + t_2$$ and for all transformations $$A_i$$: $$\text{trace} \frac{(A_i^T+A_i)}{2 \det A_i} \to \min$$

The first condition ensures that common edges are merged and the second condition minimizes the conformal deformation, what e.g. prevents the mesh form collapsing to a single vertex.

When I for example optimize the triangles of a cut cube, then the only transformations I need are rotation and translation to arrange the triangles in the plane. Optimzing $$(\alpha, t_1, t_2, \dots)$$ using line-search finds a good solution without problem.s

But for example a sphere requires quite a bit of deformation to be embedded in the plane. And to optimize the deformation needed to assemble the triangles into a planar patch, the optimization of the raw values $$(a_1, a_2, a_3, a_4, t_1, t_2)$$ seems not to work very well, especially line-search with Google ceres fails to find a valid stepsize for which the wolfe condition holds.

I suspect that in contrast to e.g. the gradient of the rotation, the gradient of this vector is not well-suited for finding the optimal transformation and it would need another local parameterization, which better suits the search space, just like the rotation/translation for rigid embeddings.

• Is this problem well-defined? In the expression for $E_j$ you seem to have a product of two vectors (in the square brackets), it doesn't look right. Second, unless I'm mistaken, any 2d triangle can be mapped to any 2d triangle by an affine transformation—there are 6 unknown parameters in the transformation, 6 known coordinates in the starting vertices, and 6 known coordinates in the final vertices, and it's a linear system in the unknown parameters. Could you write down your question in a more mathematically precise way? I think it would make it substantially clearer and easier to answer. – Kirill Oct 7 '18 at 11:49
• Also, in one place you say the "solution" is $v_j$, but in another place the unknown variables you're optimizing are the parameters of the transformations. It's slightly hard to tell what you are given as inputs and what are the unknowns. – Kirill Oct 7 '18 at 11:51
• There was a "+" missing in the energy term. What I am optimizing are affine transformations ($(A+t)$) on triangles. They are then applied to the vertices of the triangles (e.g. $v_{a,1}$) and the distance between vertices shared between two triangles in a mesh (e.g. $\|v_{a,1}-v_{b,1}\|$ should be zero. The optimization is not to find the transformation from triangle A to B, but to find the shape of triangle B, such that the edge energy (and an addidtional deformation energy like symmetric dirichlet or conformal energy) are minimized, to find a 2D parameterization of a 3D mesh. – allo Oct 7 '18 at 14:09
• I still think it would still help to write all of that down in full, including what you just said, using proper mathematical notation. – Kirill Oct 7 '18 at 14:25
• I added more details, I hope it gets more clear. I think it boils down to the main question: What is the correct parameterization of a transformation, which yields a gradient which is well-suited to find a deformation which minimizes the given deformating energy under the edge constraints. – allo Oct 7 '18 at 14:48