public Vector3d[] orthonormalize(Vector3d[] vecs) {
for(int i = 0; i < vecs.length; i++) {
for(int j = 0; j < i; j++) {
Vector3d temp = new Vector3d(vecs[j]); //Sanity check to make sure nothing is being overwritten
double dot = temp.dot(vecs);
Vector3d temp2 = new Vector3d(vecs[j]); //Sanity check to make sure nothing is being overwritten
temp2.scale(dot);
vecs.sub(temp2);
vecs.normalize();
}
}
Help with Gram-Schmidt Orthonormalization code
Author
Hi everyone. I took this Orthonomalization code from the JSci library and adapted it, but I think there's wonky going on. I pass in [0, 2, 0], [0, 0, 2] and a random third vector. As I unerstand G-S orthonormalization, it should create a set of vectors with the third vector being perpendicular to the first two. So the result should be either [1, 0, 0] or [-1, 0, 0]. But instead I get [0, 0, 0]. I wonder if anybody could catch any mistakes I was making in my code:
Author
So far as I can tell. Scale just multiplies each element by a double. Sub is just vector subtraction and Normalization is just Normalization too. Hmmm...
Are you sure that's correct? I thought that you were supposed to subtract the sum of all projections to get the perpendicular, not subtract the projection, normalize, subtract the projection from the modified vector, normalize, ad infinitum. For example, the algorithm is (in pseudo-code):
Your code appears to be doing the following:
Essentially the error appears to be in the fact that you aren't projecting onto the original vector. You project onto the modified vector.
I may be incorrect in some of my assumptions, so please disagree and explain.
out[0] = normalize(orig[0])for( i = 1; i < orig.length; ++ i ){ Vector3D accum = Vector3D(0,0,0) // Calculate the sum of all projections for( j = 0; j < i - 1; ++ j ) { accum += project(vecs[j], vecs) // e.g. project vecs onto vecs[j] } // Subtract the projections from the original vector and normalize out = normalize(orig - accum);}Your code appears to be doing the following:
for( i = 0; i < orig.length; ++ i ){ for( j = 0; j < i; ++ j ) { vecs -= normalize(project(vecs[j], vecs)); }}Essentially the error appears to be in the fact that you aren't projecting onto the original vector. You project onto the modified vector.
I may be incorrect in some of my assumptions, so please disagree and explain.
Your pseudocode of adamv's method isn't quite correct, since it shows normalization before subtraction rather than after subtraction, but your description of adamv's method is correct. It doesn't really matter which you do. The important invariant is that after step (i,j), i is perpendicular to all vectors 0..j. This is maintained in either case.
Your right, it was incorrect; I wasn't sure if that invariant was maintained or not, I couldn't think it through. Given that it is maintained though and the code above is correct, then the only other guess I have is that the third vector is either linearly dependent to the first or second vector.
Author
The third vector is made up of three random numbers. My math skills are limited but I suspect that wouldn't produce a linearly dependent vector.
Author
Sneftel's first comment may have been closer to the problem. Probably because I'm assigning random doubles to the third vector when I do the first step of the normal calculation (x*x+y*y+z*z) the java debugger reports a value of "infinity." While I'm not sure the Gram-Schmidt code works, I'll take this particular issue over to the general programming forum.
Yeah, Sneftel is probably the closet. Just to test the algorithm I wrote up a small sample program for myself (I was bored anyways); you can notice in the demo vectors included the numerical instability of the gram-schmidt orthonormalization e.g. the vectors aren't fully orthogonal, the angle between them evaluates to something like 1.1E-16.
If you want to take away the numerical instabilities, then I would recommend (once you get it working) you read the wikipedia page, specifically "Numerical Stability."
At any rate, I hope you get it working!
EDIT:
I like this Pennsylvania representation. :)
If you want to take away the numerical instabilities, then I would recommend (once you get it working) you read the wikipedia page, specifically "Numerical Stability."
At any rate, I hope you get it working!
EDIT:
I like this Pennsylvania representation. :)
Keep in mind that this forum is focused on math and physics for game development. Now, of course Gram-Schmidt orthonormalization absolutely has its place in game development. It is also a common academic topic. If you are using this for game development, it would be appropriate for you to say what you are using it for. If you are not using it for game development, it is still appropriate for you to tell us what you are working on, and also to review the Forum FAQ, which outlines the forum's policies for academic discussions of math and physics.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
