Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

ob1

Determining the eigenvectors of a covariant matrix

This topic is 5303 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm having a little trouble finding information on extracting the eigenvectors from a covariant matrix to find the basis to use in generating an OBB. I can create the covariant matrix ok, that's no problem, its just eigenvalues and eigenvectors that have me a bit confused. Does anyone know of some good reference material on algorithms for finding the eigenvectors of symetric matrices? I've been playing around with this a bit the past few days, and I've discovered I can find a fairly decent fit with just the rows of the covariance matrix alone. I actually found this when I misunderstood the meaning of the paper I was reading, and didn't calculate the eigenvectors. What I did instead was to ortho-normalise the rows of the covariant matrix and use that as the basis for the OBB. Then I made a few sanity checks on the orthogonal-ness of the 3 rows, rebuilding vectors that were out of alignment or nearly zero length. Obviously this method is wrong, but I'm suprised to see how closely the OBB fits the object in some cases. Anyway, that's basically why I want to understand this process a little more. It seems there's quite a close relationship between the rows of the covariant matrix and the principle axes of the object - even without finding the eignenvectors. Now I just need a good eigenvector algorithm to see how close my misguided implementation came to an ideal OBB basis Thanks for any info. [edited by - ob1 on May 8, 2004 7:02:36 PM]

Share this post


Link to post
Share on other sites
Advertisement
Hehe, nothing too clever really, I''m just trying to understand how to build OBB trees for fast collision testing in a demo I''m writing at the moment. I''m finding it quite an interesting topic actually.

Of course, I could just use things like sphere and AABB trees instead, but I want to compare these against OBBs so I can better understand how things work, and the advantages of one method over the other, etc.

So probably any information on hierarchical bounding volume collision techniques, in addition to OBB related material, would be of help right now. I think the more I can learn, the better informed my decisions can be when deciding on what to use in my projects.

Share this post


Link to post
Share on other sites
for a semmetric matrix the eigenvalues are just the entries
in the diagonal of the matrix (this is a theorm from elementry linear algebra). The eigenvectors are just the solutions
to the equation A x = c x where x is the eigenvector corrosponding to the eigenvalue c. this can be rewritten in the form
(A-cI)x=0 where 0 here represents the 0 vector in whatever dimension you are working (presumably 3). Anyway, this problem bascially boils down to solving for the nul space of (A-cI) wich is an elementry problem.

Rob

Share this post


Link to post
Share on other sites
There are libraries you can download which will find eigenvalues/vectors for you. If you want an algorithm, a good place to learn these is the numerical recipes book, which can be found online, at this address:

http://www.library.cornell.edu/nr/cbookcpdf.html

Share this post


Link to post
Share on other sites
Fruny:

Actually I am in the process of searching google for information, but thanks all the same. There seems to be alot of info on solving these systems on paper, but not necessarily on the algorithms used in code.

I''m particularly interested in the breakdown of the algorithms involved. I''m still trying different combinations of words in google, and have come across something interesting by searching for "eigenvector algorithms", which seems to be my best result so far (still reading it at the moment though):

http://scholar.lib.vt.edu/theses/available/etd-62597-173629/unrestricted/chapter5a.PDF


Deusmaximus421:

Interesting, so if I understand you correctly, if I have a 3x3 matrix in the form:

A P Q
P B R
Q R C

The eigenvalues of the matrix are: A, B and C respectively?

So to find the eiganvector for A, I solve:

0 P Q
P (B-A) R
Q R (C-A)



yellowjon:

Yeah, I''ve seen some references to that book. I almost ordered it the other day actually, until I read this review:

http://www.accu.org/bookreviews/public/reviews/n/n003134.htm

I''m still undecided on if it''s anything to be concerned about, but it''s made me think twice about using information from it anyway.

Share this post


Link to post
Share on other sites
Forgive me if this is review. An eigenvalue for a matrix M is a value lambda where for a non-zero vector x:

M*x = lambda*x

We can rewrite this as:

(M-lambda*I)*x = 0

Since x is non-zero, we can take the determinant to get

det( (M-lambda*I) ) = 0

Expanding this out gives the characteristic equation for a matrix. For a square matrix this will be a polynomial, and to find the eigenvalues you just (heh) solve for all the roots. Then to find the eigenvectors you use the method Deusmaximus421 described before.

Practically, the standard numerical methods solution is to use a Householder matrix with QL or QR factorization. See http://www.magic-software.com/Numerics.html for more details and code to compute this. There's also two papers there on how to compute eigenvalues and eigenvectors for symmetric 3x3 matrices.

FYI, the eigenvalues for

A P Q
P B R
Q R C

are not necessarily A, B, and C. This is usually only true for diagonal matrices, i.e. matrices with zero entries in the non-diagonal elements, or

A 0 0
0 B 0
0 0 C

The deal with symmetric matrices is that they will always have a mutually perpendicular set of eigenvectors.


Jim Van Verth
Essential Math for Games

[edited by - jvsquare on May 12, 2004 7:54:32 PM]

Share this post


Link to post
Share on other sites
jvsquare:

Great, thanks for the information! I''ll go and check that out.

Yeah, I found shortly after my last post that the eigenvalues weren''t as simple as just the numbers in the diagonal. It would have been nice if they were though, it could have saved me solving a cubic

I''m relatively confident with the solution to these on paper now, so it''s just been a case of finding a good algorithm to solve them for my 3x3 covarient matrix (which I''m 95% sure I''m building correctly, but that''s probably a topic for a different thread hehe).

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!