Meshless Shapematch algorithm

Check this thread...
http://www.gamedev.net/community/forums/topic.asp?topic_id=339391
I managed to get it working somehow. :)
The last post contains a zipfile with a demo written in Basic(source included).
Perhaps you'll find it useful.

wow sweenie, you're still active here. Haha, yes I probably read that thread 40 times. Yes I've studied your demo up the wazoo, downloaded blitz basic and taught myself it's conventions even and tweeked things all over the place, tried different configurations, studied what the numbers did inside the matricies, etc..

I've gotten this technique to work in 2D, no sweat. It seems 2D is a trivial case in a sense. If I constrain the Z axis to {0,0,1} it works perfect, but that's only in 2 dims. I'm going for 3D, and I'm having a hard time getting the rotation or the result to be a decent rotation, it's usually skewed or spastic or it produces a floating point error. Have you taken your work further to 3D and gotten it to work? Has anyone here, that can offer some insight?

I've been working on this alg for the past month and then some. My math knowledge is pretty good I think, I understand derivatives and maxima, minima problems. Granted taking the derivitave of the summation that is matrix, that's a little outside my knowledge. But I have worked with matricies, up just before eigenvalues, eigenvectors, and decomposition problems. I've been learning all about those this past month. So I believe I should be able to understand the help I get offered.

I'm confident it's the orientation information that I'm not extracting properly. I take Apq*trans(Apq) this makes it symetric and diagonizable I think. I diagonalize that resulting matrix, I then take each of the values in that matrix's trace and set them to the square root of themselves, then take the inverse and multiply that times prior Apq matrix, but the result is off, I'm pretty sure that's what I need to do. I've tried diagonalizing about 3 different ways. first way was I used your diagonalizer sweenie. 2nd was stan melax's one using quaternions, and thrid I just did it by hand making up jacobi matricies no optimization and doing a matrix multiply. So I'm confident my diagonalizing is proper.

there is something I don't understand though in your stuff sweenie. but before I was gonna ask about it, I wanted to know if you'd gotten 3D this technique working. Anyhow, why do you have 2 separate routines for eigenvectors and eigenvalues? they seem identical except in one you zero the off diagonal values and in the other you just update the existing matrix...aren't they pretty much the same matrix at the end of that process? If they aren't what does having them separate do? Also when I tested and output debug values from inside the matricies of your program it seemed like it never converged, it didn't really diagonalize anything, it just seemed to work because the 2D case is so trivial. Blitz basic demo has since expired, I wanted to double check the results in it, as I am just going off of memory.

you'v been one of the few that's attempted to learn this and that's helped me so very much. I was pretty lost till I read your thread several months ago. I imagine it's been awhile since you played with this code as it's been almost a year. Thank you for replying

The truth is that I didn't and still haven't got a clue what I was doing. ;)
It's like if you had a monkey, a c++ compiler and infinite time, eventually the monkey would produce a working application. hehe.
I fiddled with the code until it worked somewhat in 2D, but all of my attempts to bring it over to the 3rd dimension has failed.
So I pretty much dropped it to avoid going insane.

You do however seem to know alot more about this kind of math so I'm sure you will solve it sooner or later.

*sigh*, haha. Thank you though. Ya that insane part...well I've taken it as far as I can for the moment. I really wanted to learn as much as I could on my own and try every angle I could find and muster the strength to. Maybe jjd or someone with more expertise will bless this thread :). Till then, thank you again sweenie, I wish I had emailed you months ago.

Well, my code is nothing special, but you are welcome to have a look at it. I read the paper you linked, and decided to try to implement it on my own so there are a few differences...mainly in how I calculate the Least Squared Error rotation matrix. (I don't use their matrix formulation at all, I just do a least squared error fit for 3 vectors, one each for x,y,z. Then I do an orthonormalization step which is a little funky, because Gram-Schmidt is order sensitive). Feel free to play with the code.

By the way, I'm not having much luck with the geometric numerical integrator staying stable. I'm not sure if it's because of some mistake in my implementation or what...if anyone has some feedback I'd appreciate it.

Wow, thank you for your reply lonesock. I've got a lot going on right now, but I hope to get into it and learn about least-squares...thingy...ya, big gaps in my knowledge here, but I learn fast, hehe.

Given a symmetric matrix A, you can find Sqrt(A) by using the matrix diagonalization:
A = V*D*Inv(V), where D is a diagonal matrix.
If we define Sqrt(D) to be a matrix where you sqrt each diagonal element, then:
Sqrt(A) = V*Sqrt(D)*Inv(V).

Proof:
Diagonalization is possible because A is symmetric (Spectral theorem).
A = (Sqrt(A))² = (V*Sqrt(D)*Inv(V))*(V*Sqrt(D)*Inv(V))
= V*(Sqrt(D)*Sqrt(D))*Inv(V)
= V*D*Inv(V) = A

Good luck.

I got it to work!! The last poster although I'm sure well intentioned, made no sense. What is 'V'? How did it relate to the process as a whole? When he posted that I didn't know where to begin. However, I found this :) !!

http://www.danielflower.com/pages/DownloadPage.aspx?pageId=2930

someone has actually implemented the algorithm and supplied source code, I have been so thrilled. I've been studying this for months, off and on. Seems the basic process is this; to get the orientation of the point configuration.

Find Apq
Find ApqT*Apq -- the T = transposed
Diagonalize that result you'll get 2 items, the eigen vectors, a 3x3 matrix and and the eigen values, a 3 component vector
Find the sqrt of each of the eigen values
Make a 3x3 matrix out of the eigen values, with them along the trace.
Compute Eigenvec*sqrt'd(3x3(Eigenval))*EvecT
Find the Inverse of that
Compute Apq*(That Inverse)
and voila the result is the orientation of the deformed points, then that can be used to just compute the new goal positions through transforming the original points with the orientation matrix :)

Just make sure your order of operations is correct, and you're gold. Sweenie, I hope you get a chance to get this to work, it's so cool :) !!

btw, to diagonalize the symmetric matrix, I ended up using the Ageia Physix SDK's utility function to diagonalize an inertial tensor...not like I really understand all this stuff, but it does work perfectly :)

Quote:

Original post by unmodify I got it to work!! The last poster although I'm sure well intentioned, made no sense. What is 'V'? How did it relate to the process as a whole?

V is the matrix composed of eigenvectors you get from eigendecomposition of A.

http://en.wikipedia.org/wiki/Eigenvalue%2C_eigenvector_and_eigenspace#Numerical_computations

Scroll down to decomposition theorem for general matrices.

btw, I think the group report they had on collision detection aspect of the system wasn't accurate, there are numerous collision detection papers that deals with point based system, some even by the same authors.

yes in the end though, I figured out what V was. The wiki link to matricies...I don't have the references to grasp all the notations. So just posting the forumla made little sense to me at the time. But now I get it, multiply Eigenvector by Eigenvalues on the diagonal by Eigenvector transpose and THAT result is the diagonalized matrix to use. After I saw that, everything else fell into place.

For collision detection, I just constrained the points to planes if they penetrate. I am just using a simple verlet system so it bounces and tumbles realistically. Didn't take any collision info from the paper.

Thank you all for your help :)
Cheers