[tuhopuu-devel] UV-LSCM

[bjornmose]

On Wednesday,  3. March 2004 12:33, blendix wrote:
Hi Brecht and all
> Obviously you know more about this kind of thing than I do. I figured=20
we
> could have about a 2x speed up by writing more efficient code and=20
using a
> faster library like UMFPACK. But if you can do this in milliseconds,=20
that
> would be awesome. I'm curious to see what kind of solution you'll=20
think of!
>
> Cheers,
> Brecht

well trying to do a task like this in a few milliseconds on todays=20
boxes is a little optimistic, i think, but the way it is done in=20
graphite is far from optimum . Don't get me wrong, i think Bruno Levy=20
is doing an excellent job researching this topic and i feel that=20
grahpite is kind of his experimental playground. looking at it this way=20
i have to admit it is very tidy. But when it comes to saving CPU time=20
all "a priory" knowledge must be used to it's extent, sometimes=20
sacrifing math's beauty or even the beauty of the code (which is likely=20
to hit the same spot).
You see, bubble- merge- quick- sort do the same thing in a mathematical=20
sense, but in CPU usasage differs a lot.

About the ideas i have in mind, rather thinking loud than knowing;
1. May be the Cauchy-Riemann condition for our case can be rewritten to=20
an expression like w=3DF(w) where  w is a vector of all UVs.
Then the "Banachsche Fixpunktsatz" would suggest a iterative sheme like
w[n+1} =3DF(w[n]) which i used to solve "Laplace ODE" like problems=20
successfully.

2. Implement a conjugate gradient like algo to the minimization problem=20
taylored to our sparse matrix.That means not realy building the matrix=20
but "faking" the matrix multiplication by iterating through the faces=20
or vertices which are rows / colums of the matrix, so provided proper=20
data structures are build up in the beginning it saves time otherways=20
spend by tranfering data from yin to yonder. ( this is why your=20
relaxing framework looked charming to me, it might just as well be used=20
to build up this data structures. )
Approx speed up 5x or better depending on what superLU does ( i do not=20
expect miracles in this case, just a little benefit using a hand=20
crafted instead of more general ) =20

Shedule
1. Ask Bruno Levy if he did try a CG approach, which i think is the=20
best for a 2nd order minimization problem. ( the code is prepared to do=20
so, by changing a line ) And if he did (i am almost sure he did), why=20
he does not use it in LSCM. (can you ask him brecht?)

2. I did not dive into blender's math libraries too deep to know if=20
there was a good "linear equations solver for sparse matrices". if not=20
consider superLU ( copyright ! ), which seems to be a bit clumpsy=20
interacting with GRAPHITE because of different data structures ( needs=20
data copied from yin to yonder)
Would not want to have complete superLU (graphite) code in blender=20
since it is far oversized ( think of building time, compiling all!=20
linking to some few functions ), but for a first shot i'd argee.
All the algos are available in "Numerical Recipes in C / William H.=20
Press [et al.] (ISBN 0 521 43108 5)" (  my bible for advanced math=20
algos ) So this may be the guide to slim the stuff down to our needs.

3. what is left in math sense is the "pinning" data in any case.
This could be the borders of an island as well as "stretching the data=20
to a given region in UV space" or any other user friendly defined=20
subset in the UV mapping.=20

cheers
ole (bjorn the moose)