Started by Nov 06 2006 09:36 PM

,
18 replies to this topic

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?

Posted 06 November 2006 - 10:24 PM

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

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

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

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?

Thanks much for your excellent advice.

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.

Posted 06 November 2006 - 11:24 PM

Quote:Yup.

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?

Quote:Nope.

Is your result velocity vector normalized?

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

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

Posted 07 November 2006 - 12:05 AM

I forgot to mention the scale of forward, sorry.

And thanks for the confirmation :)

And thanks for the confirmation :)

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

Admiral

If you're worried that cross-products are slow, then

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

Regards

Admiral

Posted 07 November 2006 - 01:33 PM

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?

Posted 07 November 2006 - 02:12 PM

Quote: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()

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

Quote: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:I'm open to suggestions.

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

Quote:Well I'm sure it's all right, but is it

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

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

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:It doesn't. I was just guessing as to why you didn't want to use cross-products.

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

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

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

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.

Posted 07 November 2006 - 02:47 PM

Quote:

Quote: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()

Its an ugly hack to reach a result that was even simpler than the hack itself. onceand 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: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:I'm open to suggestions.

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

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.

Posted 07 November 2006 - 02:53 PM

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?

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]

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]

Posted 07 November 2006 - 05:23 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);

}

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

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.

Posted 07 November 2006 - 06:27 PM

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

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.

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.

Posted 08 November 2006 - 08:29 AM

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

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.

And you're buying [smile]

And you're buying [smile]

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

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.

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.

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.

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.

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.

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.

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

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.

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.