Random Perpendicular 3D Vector

Starting with your forward vector, it's possible to generate a random vector and then orthogonalize it:

Vector random(rand(), rand(), rand());Velocity = random - forward * dot(random, forward) / dot(forward, forward);

Doesn't really take into account the (non-)uniformity of the random distribution or anything like that, I just wanted to demonstrate the orthogonalization code. It's possible that you generate a random vector that's parallel to the forward vector, in which case the velocity will be zero, but the odds are quite slim and in the worst case you have a particle with no sideways velocity. Also note that forward / dot(forward, forward) can be computed once and reused for each particle (until the forward direction changes of course).

So in a sense, we're creating a random vector and smashing it onto the forward vector's zero-origin plane? A perfect solution.

Is your result velocity vector normalized?

Vector random( rand(), rand(), rand() );
Velocity = random + ( forward * -dot( forward, random ) );

I'm not sure what the additional "/ dot(forward, forward);" is doing. Wouldn't dot(forward,forward) always be 1?

Thanks much for your excellent advice.

Quote:

Original post by Kest So in a sense, we're creating a random vector and smashing it onto the forward vector's zero-origin plane?

Yup.

Quote:

Is your result velocity vector normalized?

Nope.

Quote:

I'm not sure what the additional "/ dot(forward, forward);" is doing. Wouldn't dot(forward,forward) always be 1?

If your forward vector is known to be unit length, you can drop the dot(forward,forward).

I forgot to mention the scale of forward, sorry.

And thanks for the confirmation :)

Why the cross-product aversion? Any other method is simply using simplified Gram-Schmidt orthogonalisation in a different (and probably less efficient) way. Any orthogonal vector is the cross-product of the forward vector and something else, and chances are that you spend more effort calculating it than you would crossing against a quasi-random vector.

If you're worried that cross-products are slow, then they really aren't. Certainly not when compared to anything involving normalisation or rotation (which contain sqrt, sin, cos as opposed to addition and multiplication).
If you're worried that cross-products are complicated to implement without an API, then, again, think twice.

Regards
Admiral

Quote:

Original post by TheAdmiral Why the cross-product aversion?

Its an ugly hack to reach a result that was even simpler than the hack itself.

Quote:

Any other method is simply using simplified Gram-Schmidt orthogonalisation in a different (and probably less efficient) way.

I'm open to suggestions.

Quote:

..chances are that you spend more effort calculating it than you would crossing against a quasi-random vector.

It's all right here, so you tell me.

Quote:

If you're worried that cross-products are slow, then they really aren't. Certainly not when compared to anything involving normalisation or rotation (which contain sqrt, sin, cos as opposed to addition and multiplication).

I don't think cross products are slow (a*b-b*a three times). But I don't think normalization is particularly slow either. By "a bit of math", I meant a large ugly mess. I doubt either solution is much better performance-wise than the other. But the smash-to-plane solution is much more elegant. And I like smashing things.

Quote:

If you're worried that cross-products are complicated to implement without an API, then, again, think twice.

I don't understand. How does this effect the situation?

Quote:

Its an ugly hack to reach a result that was even simpler than the hack itself.

It's not an ugly hack. Many would argue that the sole purpose of the cross-product's existence is to produce perpendicular vectors. If you're prepared to start off with a vector (rand(), rand(), rand()) and you don't think that's ugly, then calling rand() once and calculating a cross-product is the picture of elegance.

Quote:

Quote: Any other method is simply using simplified Gram-Schmidt orthogonalisation in a different (and probably less efficient) way. I'm open to suggestions.

My mention of GS orthogonalisation was merely an indication that whatever route you take, you're performing the same operation, only you're likely taking the long way 'round.

Quote:

Quote: ...chances are that you spend more effort calculating it than you would crossing against a quasi-random vector. It's all right here, so you tell me.

Well I'm sure it's all right, but is it perfect? [wink].
I doubt any reasonably brief method will asymptotically outperform any other, but I think two lines of fast code are better than two of not-quite-so-fast code. You're more than welcome to use whatever method you like, considering that they're all roughly equivalent. But you appear to be under the false impression that the cross-product method is inferior to the displace-project method.

Quote:

Quote: If you're worried that cross-products are complicated to implement without an API, then, again, think twice. I don't understand. How does this effect the situation?

It doesn't. I was just guessing as to why you didn't want to use cross-products.

Anyway, this disagreement is completely moot. You've found a solution you're happy with, so let's all go to the pub [grin].

Regards
Admiral

depending on how many such particles you want, it might be faster for you to generate a basis for the orthogonal plane first. then you only need to call rand twice and do very little arithmetic.

Quote:

Quote: Its an ugly hack to reach a result that was even simpler than the hack itself. It's not an ugly hack. Many would argue that the sole purpose of the cross-product's existence is to produce perpendicular vectors. If you're prepared to start off with a vector (rand(), rand(), rand()) and you don't think that's ugly, then calling rand() once and calculating a cross-product is the picture of elegance.

A cross product between two vectors to obtain a perp vector is straight to the point. But I only have one. So I need to generate my whacko vector and cross twice to create two vectors to be randomly scaled. That seems to me like a mess. If there's another way to get the result, I'm in need of it to make a proper choice between the two routines.

I'm not even sure if my original operation will work. Does it? Even then, is the result circular? If I use -1 to +1 scaling of up and right, would the random result be round or square? Should I be scaling by 0.707? Or possibly combine the two after scaling and renormalize?

Quote:

Quote: Quote: Any other method is simply using simplified Gram-Schmidt orthogonalisation in a different (and probably less efficient) way. I'm open to suggestions. My mention of GS orthogonalisation was merely an indication that whatever route you take, you're performing the same operation, only you're likely taking the long way 'round.

My mention of being open for suggestions was asking for the short way [smile]

Quote:

I doubt any reasonably brief method will asymptotically outperform any other, but I think two lines of fast code are better than two of not-quite-so-fast code. You're more than welcome to use whatever method you like, considering that they're all roughly equivalent. But you appear to be under the false impression that the cross-product method is inferior to the displace-project method.

Just that my own version was inferior (like I said, I'm not even sure it will work). And that I'm unable to write anything better at the moment.

Quote:

Anyway, this disagreement is completely moot. You've found a solution you're happy with, so let's all go to the pub [grin].

If I can be further educated, it's not so moot.

Quote:

Original post by mooserman352 depending on how many such particles you want, it might be faster for you to generate a basis for the orthogonal plane first. then you only need to call rand twice and do very little arithmetic.

You mean to obtain the right and up vectors and then simply randomly scale them for each particle?

That's a great idea. But I'm not sure if my original code accurately obtains those vectors. Can anyone confirm that?

I could also use some help with accurately scaling the two and using them together without breaking the unit scale value of the whole operation. For example, I'm pretty sure that right * 1.0 + up * 1.0 will be the top right corner of a square shape, not a circle. Is that incorrect?

You code for finding the up and right vectors looks a-okay to me, though it is somewhat unnecessarily complex. you need to be careful for special cases, when forward.y^2 = 1 or -1. you might as well choose between <1,0,0> and <0,1,0> for whacko.

I gather that you also want the random outward velocity to be 1. If this is the case, then all you need to do is generate a random angle between 0 and 2*pi. then you have x = cos(theta) y = sin(theta), and so your final vector is x*up + y*right.

Note, just for principle, that you can also adapt "smashing into planes" algorithm with this, except you would want to use spherical coordinates to generate vectors only on the unit sphere.

[Edited by - mooserman352 on November 7, 2006 11:24:28 PM]

Quote:

Original post by Kest Is there a way to compute a random perp vector to an original 3D vector without crossing?

Vector3 forward = (x,y,z), perp;float angle = random_angle, cs = cos(angle), sn = sin(angle);if (|x| >= |y|){    perp = (cs*(-z,0,x)+sn*(x*y,-x*x-z*z,y*z))/sqrt(x*x+z*z);}else{    perp = (cs*(0,z,-y)+sn*(-y*y-z*z,x*y,x*z)/sqrt(y*y+z*z);}

Assuming m is the desired magnitude of the random vector,
r = 1-2*rand();
s = 1-2*rand();
t = sqrt(m*m-r*r-s*s) * -rand()%2;

Vector perp(y*t-z*s,z*r-x*t,x*s-y*r);

It's still the cross product, but in four lines and normalized.

Overall:
3 random numbers,
1 square root
1 modulus
12 multiplications
1 unary minus
7 subtractions
1 Vector constructor

Even for hundreds of particles, I'm sure it pales in comparison to the number of flops you're doing updating the rest of the system.

Edit: Seriously, Admiral isn't just making this up as he goes along.

Technically, the following is an equivalent solution using cross-products:

Vector random(rand(), rand(), rand());Velocity = Cross(forward, random);

The cross-product of any two vectors always produces a vector that is orthogonal to two input vectors, and since one of these vectors is random the orthogonal vector is random, and just as good as any other orthogonal random vector you could produce via other means (again ignoring the specifics of the distribution, which can be fixed/modified using other PRNGs). I actually prefer this solution to orthogonalization, since it's always less operations regardless of vector length. And it's quite clear to anyone looking at this code exactly what's going on.

Quote:

Original post by erissian Assuming m is the desired magnitude of the random vector, r = 1-2*rand(); s = 1-2*rand(); t = sqrt(m*m-r*r-s*s) * -rand()%2; Vector perp(y*t-z*s,z*r-x*t,x*s-y*r);

Beautiful [smile].

Quote:

Original post by Zipster Vector random(rand(), rand(), rand()); Velocity = Cross(forward, random);

Very concise, but doesn't produce a normalised result. If you throw a normalise & scale operation onto the end of this, it would probably be fractionally slower than erissian's method, but it looks bug-proof.

Two excellent answers. Can we go to the pub now?

Regards
Admiral

Yeah I just made the assumption that the magnitude should be random too, since that appears to be what Kest wanted judging by his original post.

And you're buying [smile]

I normally refrain from these efficiency related discussions, but, with all due respect, I can't see how the cross product method could possibly be faster than the alternate method.

the OP's initial method (after being cleaned up a bit) has, for each particle past the first one, approximately:

1 random numbers
0 square roots
0 modulus
5-6 explicit multiplactions at max
5-6 explicit additions as max
1 cosine (evaluating a polynomail at worse, a look-up table at best)
1 sine
1 vector constructor

I honestly have no idea about the cost of each operation, but I would think that generating a random number, or computing a square root, is more costly than evaluating a cosine. If elegance is a concern, then there should be no need to call rand() any more than once, as there is only one degree of freedom here.

Even though I was curious to hear of both, I probably should have mentioned from the beginning that the forward vector doesn't change for each particle. It is generated when a projectile (bullet) makes contact with another object. The particles spew off of the collision surface. In this case, when a bullet smashes into marble tiling, pieces of marble and dust go flying.

Quote:

Original post by mooserman352 ..then all you need to do is generate a random angle between 0 and 2*pi. then you have x = cos(theta) y = sin(theta), and so your final vector is x*up + y*right.

This is the solution I'm looking for. And this little bit of math is the only math needed for each particle. Just generate the vectors and randomly rotate around them. Perfect.

Quote:

Note, just for principle, that you can also adapt "smashing into planes" algorithm with this, except you would want to use spherical coordinates to generate vectors only on the unit sphere.

If you mean to smash the velocity vector to a half-unit sphere facing the forward vector, then that would introduce some forward velocity (if I understand correctly). The scaling for velocity is plugged in from an outside source, and the forward velocity is a seperate scaler value from the outward velocity. So I don't want to introduce any of one through the other's scale.

Quote:

Original post by erissian Assuming m is the desired magnitude of the random vector, r = 1-2*rand(); s = 1-2*rand(); t = sqrt(m*m-r*r-s*s) * -rand()%2; Vector perp(y*t-z*s,z*r-x*t,x*s-y*r); It's still the cross product, but in four lines and normalized.

I appreciate the time you spent on this, but the math envolved is pretty much the same that's been previously posted. Just yanked out of explicit functions. As I've stated, I'm not trying to optimize. I'm looking for a simpler operation. This doesn't seem to be moving in that direction.

Quote:

Original post by erissian Even for hundreds of particles, I'm sure it pales in comparison to the number of flops you're doing updating the rest of the system.

Your assumptions are irrelevant to the topic, Mr. Negative [grin]

Quote:

Original post by Zipster Technically, the following is an equivalent solution using cross-products: Vector random(rand(), rand(), rand());Velocity = Cross(forward, random);

This is nice as well. Just a normalize at the end and it's all good.

I appreciate all of the help. I think I'll try the clock-face spin-on-the-plane-dot approach.