Sign in to follow this  
SimonTheSorcerer

Random Vectors with angle offset

Recommended Posts

I'm trying to create a random Vector from an existing Vector and an angle Offset. (for a particle system) i found an old Topic where a user named Kurioes said: You could try this: 1) You have the vector you want to randomize, V. Normalize it. 2) Generate a new random vector, T, with length > epsilon, and normalize the vector. 3) If T and V are parallel (meaning the angle is too far away from 90 degrees, or abs(V dot T ) > 0.5 or something like that) go back to step 1. 4) Define a new vector, S, where S is the cross product of V and T (so is is perpendicular to both V and T); S = V x T 5) T = V x S (T should now be perpendicular to both V and S so that S, T and V are all perpendicular to one another) 6) Generate two random numbers; a between 0 and 2*pi and z between 0 and the maximum angle (in radians) between the input vector and the new randomized vector 7) The randomized V, V# = cos(z) * V + sin(z) * (cos(a)*S + sin(a)*T) -------------------------------------------------------------------------- and here's my code:
float r = rand() / (float)RAND_MAX;
float a = r * 2.0f * (float)M_PI;
r = rand() / (float)RAND_MAX;
Vec3 randSpeed;
if(_emitOffset > 0)
{
	float z = r * _emitOffset;
		// V# = cos(z) * V + sin(z) * (cos(a)*S + sin(a)*T)
	randSpeed =  (_emit+sin(z)) * cos(z) * (_emitS*cos(a) + _emitT*sin(a));
	}
else
	randSpeed = _emit;



_emit (the emit-vector), _emitS and _emitT are perpendicular to eachother. (atleast 99.9% perpendicular anyways, couldn't get 100% for some reason, perhaps round-off errors) but, when i have _emit(0,-1,0) and _emitOffset = M_PI/4 i get results like {-0.14, 0, 0 } , which isn't right. What's wrong here?

Share this post


Link to post
Share on other sites
It might just be a calculations error. If I understand this correctly, you're simply performing two rotations on a basis defined by V x T = S. One rotation has to be an X rotation over [0, 2PI], however the second rotation can be either a Y or Z rotation over [0, maxRadians]. So expanding the follow XZ transformation:

[ 1 0 0 ] [ cos(z) -sin(z) 0 ] [ V.x T.x S.x ] [ V'.x T'.x S'.x ]
[ 0 cos(x) -sin(x) ] * [ sin(z) cos(z) 0 ] * [ V.y T.y S.y ] = [ V'.y T'.y S'.y ]
[ 0 sin(x) cos(x) ] [ 0 0 1 ] [ V.z T.z S.z ] = [ V'.z T'.z S'.z ]

Should give you an analytic solution. However as Kurioes mentioned the random solution is only going to be uniform (or whatever distribution your RNG generates) over the input parameters, which are angles in angular space. I wouldn't worry about it though.

Also, if V x T = S, then V x S = -T. Shouldn't matter in the end, but it was bugging me.

Share this post


Link to post
Share on other sites
why dont you just use rejection sampling? I don't even think this thing is uniform.

do{
pick 3 random numbers r1,r2,r3 in [0,1]
while(r1^2 + r2^2 + r3^2 > 1)

vector(v1,v2,v3)


or you can use shirley's mapping I can't remember. it's an analitical function with a sin and a cos and a sqrt(maybe not sqrt, can't remember) or something. the advantage is stratification is simple. s,t s+ds,s+dt is equal area for any s,t provided dt and ds are the same of course.


Tim

Share this post


Link to post
Share on other sites
timw: by rejection sampling, you mean this, right?

Quote:
Original post by SiCrane
The simplest to explain method I can think of to do something like this would be:

1. generate three random numbers x, y, z each in the range [-1, 1]
2. create a vector out of those three numbers
3. if the magnitude of the vector is greater than 1, or smaller than some epsilon value, repeat from step 1.
4. if the angle between the given vector and the generated vector is greater than the given angle go back to step 1.
5. adjust the magntiude of the generated vector to be equal to the magnitude of the given vector.


(taken from the old thread i mentioned)

i COULD use this. However, it is far from optimal, especially when using small offsets.
Let's say i have a particle-emitter with a narrow "cone" (vector with maybe 5 degrees offset). To randomly generate a vector that is offset no more than 5 degrees from a given vector will probably take quite a few attempts.
Considering that emitters might want to emit perticles at rates about 100 particles/second, this doesn't sound very good.

This "Shirley's Mapping" you're talking about could be interesting though. Anyone got any more info on this?

Share this post


Link to post
Share on other sites
Quote:
Original quote by SimonTheSorcerer
This "Shirley's Mapping" you're talking about could be interesting though. Anyone got any more info on this?

I too went in search of some more information on this mapping but the best I came across was this, which at least contains some source code to follow. All it does is map a square to a circle (and vice versa) using concentric squares and circles.

Share this post


Link to post
Share on other sites
hmm, if I'm getting this, you have an arrow that represents the axis of the emitter-cone and you want to slightly offset in order to shoot your particle in that direction. Check this:

Let v=(v1,v2,v3) be the normalized vector that represents the axis of the emitter. (be careful: not the position, the axis) If it's not normalized you can divide all its components by its magnitude sqrt(v1*v1+v2*v2+v3*v3). This makes it unit vector. Then you can use the following expressions to find it's longitude (east-west orientation) and latitude (north-south of the equator) in a hypothetical spherical coordinates system.

longitude = phi = atan(v2/v1);
latitude = theta = atan( v3/(sqrt(v1*v1+v2*v2)) );

Now you have the orientation (in angles counted in radians) of the emitter's axis. All you need to do now, is add a random offset, i.e. corresponding to +/- 5degrees to these angles and reproject them back to cartesian coordinates using these:

v1' = mag*cos(phi)*cos(theta);
v2' = mag*sin(phi)*cos(theta);
v3' = mag*sin(theta);

where 'mag' should be the desired magnitude of the resulting vector. I suggest you keep this set to 1, since unit vectors are the most useful to work with (when it comes to representing directions)

I hope this has been helpful.

Share this post


Link to post
Share on other sites
I guess I should also mention that the longitude 'phi' should be in the range of 0 to 2pi radians, and the latitude 'theta' in the range -pi/2,...,pi/2. I'm mentioning this because there's a bunch of implementations of tan() and atan() out there and they can get a little tricky when you're trying to copy/paste formulas.
I'm also assuming that a right-handed world coord. system is used...

Share this post


Link to post
Share on other sites
Quote:
I hope this has been helpful.


YES! this has been very helpful indeed.
it certainly lets me offset my vectors with ease!

However, if i am to be picky (and i am :P) there's a small flaw here.
Let's say my offset is PI/2 (90 Degrees).
Then i would only have to offset one of theta OR phi by PI/2 to get a new vector that is perpendicular to the original vector.

so i would have to divide the offset-value between the two. (which i'm not doing just yet)

e.g Offset-value is 10 Degrees. Then i might offset phi by [0,3] and phi by [0,7] (totally random ofcourse, however the sum should always be 10)
am i right?

Anyways, here's my source. (as you can see i made a little test in my code)


//TEST
_emit = Vec3(0,1,0);
//_emit = _emit.Normalize();
_emitOffset = 10 * float(DEG_TO_RAD);

//Longitude
float phi = atan2( _emit.GetY() , _emit.GetX() );
//Latitude
float theta = atan( _emit.GetZ()/(sqrt(_emit.GetX()*_emit.GetX()+_emit.GetY()*_emit.GetY())) );

//r is between [0,1]
r = rand() / (float)RAND_MAX;

//phi is OffSet by [0,_emitOffset]
phi += (-_emitOffset + r*2*_emitOffset);
//same for theta
r = rand() / (float)RAND_MAX;
theta += (-_emitOffset + r*2*_emitOffset);

/*
//phi is OffSet by M_PI/2 radians
phi += float(M_PI/2);
//Theta is not offset at all
*/


randSpeed.SetX(cos(phi)*cos(theta));
randSpeed.SetY((sin(phi)*cos(theta)));
randSpeed.SetZ(sin(theta));

//float dot = randSpeed.Dot(_emit);





thanks alot someusername!

Share this post


Link to post
Share on other sites
If you already have a transform for the particle system you can use the following method to emit particles within the specified cone half-angle around the z axis of the particle system:


// m = world transform of particle system
// halfangle = half cone angle for spread

void RandVec(const mat44& m, float halfangle, vec3& v)
{
float z = Random(cosf(halfangle), 1.0f);
float t = Random(0.0f, 2.0f*pi);
float r = sqrtf(1.0f - z*z);

float x = r*cosf(t);
float y = r*sinf(t);

v = z*m.getZ() + x*m.getX() + y*m.getY();
}




For a description of why this works and produces a random distribution have a look at:

http://www.faqs.org/faqs/graphics/algorithms-faq/ (6.08)

There are also a couple of easy optimizations you can make. The cosf(halfangle) can be precomputed and stored for the system and you can take advantage of the fsincos instruction if available to compute the cos and sin. This brings it down to 1 sqrt and 1 fsincos only.

HTH

[edit: missed the m. before getX() and getY() :)]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by SimonTheSorcerer
Let's say my offset is PI/2 (90 Degrees).
Then i would only have to offset one of theta OR phi by PI/2 to get a new vector that is perpendicular to the original vector.


hmm, you mean you have to offset 'theta XOR phi' by PI/2 to get a perpendicular vector? I'm not quite sure... First glance, I think you'll get perpendicular vectors if you offset either any single one or both of them. I don't think I can proove this within this reply, but there's a very easy way to see if this holds true on not.
2 vectors are perpendicular (in any number of dimensions) if and only if their dot product is zero. So you can feed your algorithm a random vector and try offseting just phi first, then just theta, and then both phi and theta by PI/2 and each time test the dot product of the initial and final vector to see if it's zero.

I guess it wouldn't hurt mentioning that the dot product of two vectors is the sum of the products of their respective components (it's just a number, not a vector)

If you need anything else just shoot, I can provide all the info you want on the theoretical side but I can't help that much on the actual implementation...
Btw, how do you guys post source code snippets in your replies?

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
Quote:
Original post by SimonTheSorcerer
Let's say my offset is PI/2 (90 Degrees).
Then i would only have to offset one of theta OR phi by PI/2 to get a new vector that is perpendicular to the original vector.


hmm, you mean you have to offset 'theta XOR phi' by PI/2 to get a perpendicular vector? I'm not quite sure... First glance, I think you'll get perpendicular vectors if you offset either any single one or both of them. I don't think I can proove this within this reply, but there's a very easy way to see if this holds true on not.
2 vectors are perpendicular (in any number of dimensions) if and only if their dot product is zero. So you can feed your algorithm a random vector and try offseting just phi first, then just theta, and then both phi and theta by PI/2 and each time test the dot product of the initial and final vector to see if it's zero.

I guess it wouldn't hurt mentioning that the dot product of two vectors is the sum of the products of their respective components (it's just a number, not a vector)

If you need anything else just shoot, I can provide all the info you want on the theoretical side but I can't help that much on the actual implementation...
Btw, how do you guys post source code snippets in your replies?


Yes that's exactly what i meant.

And i did test that in my code (see above). I just wanted to tell you. The dot product was zero. (or like 8e^-18 or some REALLY small value atleast)

Regarding code snippets... check out the FAQ.
for code, the tag is ["source"] and ["/source"] (without the "")

Quote:
Original post by d00fus
If you already have a transform for the particle system you can use the following method to emit particles within the specified cone half-angle around the z axis of the particle system:


That looks really interesting and efficient. However, i'm still a bit of a noob in OpenGL, and i'm not sure how to get from the Identity Matrix to a matrix whose Z-Axis is aligned with a Vector.

glLoadIdentity();
Vec3 _emit = Vec3(3,4,5);
//Do some rotations or matrix-operations here i guess.
glRotate() etc..

//When i then do
glTranslate(0,0,1) i wanna go along the direction of _emit.

Because thats the matrix that is required in your Function, am i right?

[Edited by - SimonTheSorcerer on November 15, 2005 11:34:34 AM]

Share this post


Link to post
Share on other sites
If you don't already have a matrix hanging around it'll be a bit more work. In our engine our scene nodes all have a world transform so the particle system can just use this. You can can generate a matrix to rotate a vector onto another (in your case the identity Z vector onto your emit direction) reasonably easily though, you can either generate the matrix directly (see for example http://www.cs.lth.se/home/Tomas_Akenine_Moller/code/fromtorot.txt) or produce a quaternion and generate a matrix from that.

Share this post


Link to post
Share on other sites
Quote:
Original post by d00fus
If you don't already have a matrix hanging around it'll be a bit more work. In our engine our scene nodes all have a world transform so the particle system can just use this. You can can generate a matrix to rotate a vector onto another (in your case the identity Z vector onto your emit direction) reasonably easily though, you can either generate the matrix directly (see for example http://www.cs.lth.se/home/Tomas_Akenine_Moller/code/fromtorot.txt) or produce a quaternion and generate a matrix from that.


I don't have world transforms for my scenenodes, with the exception of my emitternodes, where the world transform is calculated with every render, using the ModelView Matrix.
Unfortunately that link doesn't seem to work. However i do own the book "Real-Time Rendering, Second Edition" by Akenine_Moller. Perhaps it can give some insight. (havn't read too much from it really... [embarrass])
Quaternions are, at this stage of my engine, not an option [smile]. Perhaps i'll implement quats later. But thanks for the info!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this