Jump to content
  • Advertisement
Sign in to follow this  
ATC

Need help with Matrix decomposition algorithm...

This topic is 2120 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

Hello again my noble Lords and Ladies, lol...

I'm running through all of the essential data types of my engine (Vector2, Vector3, Vector4, ColorF, Quaternion, Matrix, etc...). I've just fixed all the bugs in my math API and added some optimizations for speed/efficiency. But now I'm left with one last problem... This dreaded Matrix.Decompose method!

I really just don't know wtf I'm doing on this one, which feels unusual and frustrating for a figure-it-out-guy like me... I was able to handle everything else in the API, but this one just escapes me for some reason. I'm a college dropout and self-taught programmer (and self-taught at almost everything else lol...always learned better on my own). I only had a year and one semester of college, so I lack formal education in complex mathematics. So when I look up matrix decomposition, on Wikipedia for instance, it's all a bunch of "junk" and symbols that have no meaning to me... For example, I have no clue wtf this is supposed to be/mean:


5b382df47b3fe37fcd8ce6db40bc9a9e.png


I tried implementing this several different times and could never get it to work and yield proper results... it's a very big, mind-numbing operation. Since it would never work I ended up scrapping the code I wrote, so I don't even have code to post. I'm very sorry for that, as I know it's frowned upon to come here with no code because it shows no effort. But believe me, I've tried and tried and tried to figure this out. If you've seen any of my other posts over the past few years you'll know I'm not the type of guy who comes here and asks others to do my work for me!

But I really need some help with this... a pseudo-code example, a link to a working implementation in C/C++/C#, an actual implementation of it one of you have done, the implementation from SlimDX/OpenTK/etc... something! I need some way to understand and/or just get it working. What I understand is code and the practical application of mathematics... What I don't understand are these complex, "high-level" theoretical math concepts and funny symbols, formulas and diagrams.

So is there anyone who can help me with this? At this point I'm lost for ideas... :-\

I was always a poor math student... I simply suck at math when I'm not applying it to something useful. When I'm using mathematical concepts in code, however, I'm quite good at it. It's just the odd way my brain works... I hated all my math lessons from Kindergarten to college, but I actually enjoy solving math challenges in programming. That might sound weird or stupid but that's just me lol..

Anyhow, thank you for your valuable time and best regards,

ATC

EDIT:

It appears SlimDX doesn't even implement their own algorithm! It looks like they're DllImporting it from DirectX... Perhaps that speaks to the mind-numbing complexity of the algorithm, lol? I suspect its really for performance reasons, but maybe it's a bit of both lol

EDIT 2:

Running through the OpenTK source now too... Apparently it doesn't even have a Decompose method... Edited by ATC

Share this post


Link to post
Share on other sites
Advertisement
Alright, I am assuming that you are referring to this particular type of matrix decomposition. The equation you posted equates the matrix A to the product of L and L[sup]T[/sup] and shows what each element of the resultant matrix is. The article I linked to also gives equations for the various elements of L. I believe the main stumbling block for your understanding of this method is the sigma notation used in the equations. When you see a capital sigma in a mathematical equation, it means that you are to sum the term to the right of the sigma up to the limit on the top. I should probably try to give an example:
c44ded964a8098fdd9e0fbe482c88db8.png This is one of the equations from the linked page, and what the sigma notation is representing here is "sum L(j,k) squared over k from 1 to j-1". So if j is 3 for example, then L(3,3) would be equal to sqrt( A(3,3)-(L(3,1)*L(3,1)+L(3,2)*L(3,2)) ). In my opinion at least, this is a rather simple method once you get past the notation, so I am not sure why OpenTK doesn't implement this method. I also note that this method only works for symmetric matrices, i.e. matrices where the elements on one side of the central diagonal are equal to the corresponding elements on the other side. I hope that my explanation has been sufficiently clear to be of help to you, and will be happy to help explain anything else you are having trouble with (or provide some implementation help if it comes to that).

Share this post


Link to post
Share on other sites
I'm still totally lost lol... Remember, I have no mathematics foundation to help me here, and I'm not even sure what all these "A"s and "L"s are standing in for.

I'm aware there are different types of decomposition algorithms. And I'm not exactly sure which one I need to use? I need to mirror the functionality of Matrix.Decompose found in DirectX and XNA.

Share this post


Link to post
Share on other sites
Sigh... Lol I'm feeling hopeless. I keep scouring Google to try to find some sort of working implementation or something to help me understand it and come back empty-handed each time.

However, I'm having a discussion in another thread on micro-optimization of math routines for my engine's math API, and I'm curious about Intel's Math Kernel Library; which can indeed interface/interop with C#. It appears that Intel actual implements Matrix decomposition in their library. So perhaps I might be able to just defer the work to their implementation if using the MKL would be beneficial to my project? However, I hate to have to give up on something like that... It will, literally, haunt me all the rest of my days if I give up lol.

Share this post


Link to post
Share on other sites
I was once in the same boat as you somewhat, I wanted an algorithm to do LU decomposition because I had heard that you can compute the inverse of a matrix with the decomposition though I never was able to find any information on exactly how to go about that. I did however write a working algorithm to do the decomposition and it should still be here on gamedev somewhere.. (I'll check my posts and then get back to you) though I was told it was lacking "pivoting" or something.. I'm no math genius I just learn enough to get by in programming (and possibly a little extra if it peaks my interest which is more often than not).

hold on let me find that post for you..

EDIT: Sorry, seems my old posts/topics have been deleted =/ .. blows.. well I'm not that great at math and it took me a good few hours to read about LU decomposition and how it is done, to come up with an algorithm. I'm sure if you keep at it you will come up with the algorithm as well it wasn't complex at all if I remember correctly just a few for loops.

It might be around somewhere, I used to go by CodeCriminal around here but have since changed my handle.

EDIT2: Woo found it http://www.gamedev.net/topic/562662-lu-decomposition-and-computing-the-determinant-of-an-nxn-matrixsolved/ Edited by roadysix

Share this post


Link to post
Share on other sites

I'm no math genius I just learn enough to get by in programming (and possibly a little extra if it peaks my interest which is more often than not).


Bingo. You couldn't have described my math skills better lol.

Thank you, I will be awaiting your reply to see the algorithm.

Share this post


Link to post
Share on other sites
Above post

I'm actually working on a small library of random items that include math related things such as vectors and matrices.
if you want id be willing to share code, or give feedback over skype or something though I don't have a mic. I don't yet have a
class for quaternions so I'd be interested to see your implementation. Edited by roadysix

Share this post


Link to post
Share on other sites

Above post

I'm actually working on a small library of random items that include math related things such as vectors and matrices.
if you want id be willing to share code, or give feedback over skype or something though I don't have a mic. I don't yet have a
class for quaternions so I'd be interested to see your implementation.


Sure, you share with me and I'll share with you. You certainly can have/use my Quaternion implementation. :-)

Send me a pm and we can connect on Skype.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • 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!