• Create Account

## Random Perpendicular 3D Vector

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

18 replies to this topic

### #1Kest  Members

547
Like
0Likes
Like

Posted 06 November 2006 - 09:36 PM

Is there a way to compute a random perp vector to an original 3D vector without crossing? I want to apply random outward velocity to particles in a situation where I only have a forward vector. Any advice? My instinct tells me to obtain a right and up vector and multiply them with a random scaler (-1 to +1). Vector forward = original_vector; Vector whacko( -forward.z, -forward.y, forward.x ); Vector right = Cross( forward, whacko ); Vector up = Cross( forward, right ); Velocity += right * random_x_scaler; Velocity += up * random_y_scaler; But that's a bit of math to pound onto hundreds of individual particles. And since the result will be random anyway, I was wondering if there wouldn't be a quick and dirty way to reach the same conclusion?

### #2Zipster  Members

1711
Like
0Likes
Like

Posted 06 November 2006 - 10:24 PM

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).

### #3Kest  Members

547
Like
0Likes
Like

Posted 06 November 2006 - 10:53 PM

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?

### #4scgames  Members

2082
Like
0Likes
Like

Posted 06 November 2006 - 11:24 PM

Quote:
 Original post by KestSo 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).

### #5Kest  Members

547
Like
0Likes
Like

Posted 07 November 2006 - 12:05 AM

I forgot to mention the scale of forward, sorry.

And thanks for the confirmation :)

1122
Like
0Likes
Like

Posted 07 November 2006 - 05:10 AM

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

### #7Kest  Members

547
Like
0Likes
Like

Posted 07 November 2006 - 01:33 PM

Quote:
 Original post by TheAdmiralWhy 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?

1122
Like
0Likes
Like

Posted 07 November 2006 - 02:12 PM

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

### #9mooserman352  Members

168
Like
0Likes
Like

Posted 07 November 2006 - 02:24 PM

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.

### #10Kest  Members

547
Like
0Likes
Like

Posted 07 November 2006 - 02:47 PM

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.

### #11Kest  Members

547
Like
0Likes
Like

Posted 07 November 2006 - 02:53 PM

Quote:
 Original post by mooserman352depending 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?

### #12mooserman352  Members

168
Like
0Likes
Like

Posted 07 November 2006 - 03:24 PM

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]

### #13Wasting Time  Members

411
Like
0Likes
Like

Posted 07 November 2006 - 05:23 PM

Quote:
 Original post by KestIs 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);}

### #14erissian  Members

727
Like
0Likes
Like

Posted 07 November 2006 - 06:02 PM

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.

### #15Zipster  Members

1711
Like
0Likes
Like

Posted 07 November 2006 - 06:27 PM

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.

1122
Like
0Likes
Like

Posted 08 November 2006 - 08:29 AM

Quote:
 Original post by erissianAssuming 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 ZipsterVector 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

### #17Zipster  Members

1711
Like
0Likes
Like

Posted 08 November 2006 - 09:14 AM

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.

### #18mooserman352  Members

168
Like
0Likes
Like

Posted 08 November 2006 - 11:26 AM

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
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.

### #19Kest  Members

547
Like
0Likes
Like

Posted 08 November 2006 - 01:43 PM

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 erissianAssuming 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 erissianEven 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 ZipsterTechnically, 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.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.