[tuhopuu-devel] /* A (half baked) attempt at a Relax UV tool.

[Brecht Van Lommel]

Hi,

On Fri, 2004-02-27 at 20:46, Bjornmose wrote: 
> the least sqaure conform mapping algo
> states an square objective function avioding the scaling (linear
> problem)
> i am working an a geometric interpretation. sigh... says i have an idea
> how it works, but did not understand completly.
> they say the redefine the optimization with consrtaints to a nonlinear
> problem without and i don't get the leap yet.
> hmm.. i'v got a masters degree in physics some years ago. may be i
> should give it back.

I've been reading and trying to understand LSCM for quite some time this
weekend. I can't say I completely understand the underlying math as
explained in the paper (I don't have any university degree yet, still
studying, so you can imagine). But by looking at the code, some things
got more clear to me. The code from Graphite (mostly in lscm.cpp) is
actually fairly simple. In the comments the LSCM equation is written
down in geometric form like this:

// LSCM equation, geometric form :
// (Z1 - Z0)(U2 - U0) = (Z2 - Z0)(U1 - U0)
// Where Uk = uk + i.vk is the complex number
//                       corresponding to (u,v) coords
//       Zk = xk + i.yk is the complex number
//                       corresponding to local (x,y) coords

So that's a nice and simple equation, and the Z0's can be left out as it
is set to 0 in the algorithm. I've written a little overview of the
algorithm to get a better understanding of how it all works myself, but
maybe you're interested in it too. The actual algorithm (over
simplified) as in Graphite:

- number the u's en v's, so we now were they are in the matrix
- construct a solver / matrix with (2 * (number of distinct vertices))
  columns
- find two vertices, at the extrema of the principal axis
- pin these two vertices to (0, 0) and (0, 1)
- for each triangle
  - project it onto a 2d surface, to get rid of the z coordinate
  - the coords will look like: (x0, y0) = (0, 0),
    (x1, y1) = (something, 0) and (x2, y2) = (something, something)
  - work out the LSCM equation for the triangle, with the new vertex
    coords
  - split the equation in a real and imaginary part
  - add to the matrix one row for the real part, and one for the
    imaginary part, and put the coefficients in the right positions
    in the matrix
- solve it, with the solver set to 'least squares'. the superlu library
  is used.
- get the fresh u's an v's back from the solver

That's like a really simple algorithm in my eyes. Maybe I should go back
to the paper and find out why it actually works :), but anyway, this
seems like something we can code in the short term.

Cheers,
Brecht