Sign in to follow this  
BlindSide

Generate a random unit vector.

Recommended Posts

Are there any well-known ways to quickly generate a random unit vector in 3D space? Heres what I'm doing now: (In C++)
Vector(rand()%100 - 50,rand()%100 - 50,rand()%100 - 50); // I could exchange the rand for a mersenne twister I suppose.
Vector.normalize();
The problem is the normalization, does anyone know of a way to get around that?

Share this post


Link to post
Share on other sites
Why is normalize a problem? Too slow? Here;s some code used to generate random unit vectors, without normalize, well not 100%. But I doubt if its any faster. If you have bad luck, you'll have to try alot of time before a proper vector comes out.

repeat
v[0] := (random(1000)*0.001) * 2 - 1; // -1 .. +1
v[1] := (random(1000)*0.001) * 2 - 1;
v[2] := (random(1000)*0.001) * 2 - 1;
len := vectorDotProduct(v, v);
until not ((len < 0.9 * 0.9) or (len > 1.1 * 1.1));

result := vectorScale( v, 1.0 / sqrt(len) );


Greetings,
Rick

Share this post


Link to post
Share on other sites
Quote:
Original post by spek

repeat
v[0] := (random(1000)*0.001) * 2 - 1; // -1 .. +1
v[1] := (random(1000)*0.001) * 2 - 1;
v[2] := (random(1000)*0.001) * 2 - 1;
len := vectorDotProduct(v, v);
until not ((len < 0.9 * 0.9) or (len > 1.1 * 1.1));

result := vectorScale( v, 1.0 / sqrt(len) );



This method is worse than the originally suggested one.

The last step normalises the vector, like in the original method.
The loop before that is just a waste of time and does not even have a predictable runtime.

edit: fixed typo

Share this post


Link to post
Share on other sites
Quote:
Original post by Rattenhirn
Start with a unit vector and rotate it randomly.

I'd recommend this too. Your current method won't distribute the unit vectors uniformly as you're sampling within a cube (there's more possibilities along the diagonals than the cardinal axes), and there's the slim chance you'll end up with a zero vector. Rotating a unit vector will result in a more uniform distribution.

Alternatively you can convert spherical coordinates to cartesian, which should be the same. But now I think of it, it will be tricky to get a uniform spherical distribution from rotations and spherical coordinates as well...

Share this post


Link to post
Share on other sites
If you need to uniformly generate a unit vector you can do something like this.

Vector3 UniformUnitVector()
{
float theta = RandomRange( 0.0f, 2.0f * Pi );
float r = sqrt( RandomRange( 0.0f, 1.0f ) );
float z = sqrt( 1.0f - r*r ) * RandomChooseOneArgument( -1.0f, 1.0f );
return Vector3( r * cos(theta), r * sin(theta), z );
}

That way you don't have higher chances of choosing one vector over others. This assumes that RandomRange will uniformly choose a float between the two arguments and RandomChooseOneArgument will return one of the two arguments uniformly.

Basically all this does is find a random point on the unit disc in the xy-plane and then finds the z-height of the sphere at that point. It will choose either positive or negative height to choose either the top or bottom half of the sphere.

Share this post


Link to post
Share on other sites
Thanks guys for the replies, they were all very informative. It seems that rotating a unit vector randomly is the best method, however, I am not overly concerned with the accuracy of the result, rather the speed.

I think putting my problem into context is a good idea here. I am using the random unit vector to help generate a random position to sample a ray occlusion test from a volume light source in a ray tracer (To produce soft-shadows). When the unit vector is generated, I would multiply it by the radius of the light (Which can vary) and use that as the position.

I tried another method like so:


float halfLightRadius = lightRadius * 0.5f;
Vector(rand()%lightRadius - halfLightRadius, rand()%lightRadius - halfLightRadius, rand()%lightRadius - halfLightRadius);


Which is slightly faster, but offcourse generates a volume cube. Does it matter that much for a raytracer though? Do volume lightsources look better in the shape of a cube or a sphere? I realise I've gone waaay off the original point of this post, but I'm hoping that someone could direct me to a whole new method of generating volume light positions for ray tracing soft shadows.

Share this post


Link to post
Share on other sites
From my random vector library:



// the function Random() returns a float in the range [0,1]

float2 RandomDirection2D()
{
float azimuth = Random() * 2 * pi;
return float2(cos(azimuth), sin(azimuth);
}

float3 RandomDirection3D()
{
float z = (2*Random()) - 1; // z is in the range [-1,1]
float2 planar = RandomDirection2D() * sqrt(1-z*z);
return float3(planar.x, planar.y, z);
}


These were well researched, and will give uniform distributions over 2- and 3-spheres.

As for your theory question, you will need to have a unit vector, and for lights in a ray-tracer it is best to have a uniform distribution.

Share this post


Link to post
Share on other sites
BlindSide's original method creates a higher density in the corners.
Spek's method rejects a lot of vectors and also creates slightly higher density in the corners, but not as bad.
It would work and be more efficient if
until not ((len < 0.9 * 0.9) or (len > 1.1 * 1.1));
is deplaced by
until (len > 0.001 and len < 1);
(len > 0.001 is used to prevent division by zero later on).
Rattenhirn: How do you randomly rotate a vector? I'm not sure if for instance using a random yaw, pitch and roll creates a uniform distribution.
I think Lexdysic's and Symphonic's methods are exactly the same, but Symphonic's doesn't use the "choose -1 or 1 randomly" thing, so it should be faster. Both produce very nice results, though.

- Lutz

Share this post


Link to post
Share on other sites
Quote:
Original post by Lutz
How do you randomly rotate a vector? I'm not sure if for instance using a random yaw, pitch and roll creates a uniform distribution.

It really wouldn't -- it wouldn't be far from just generating random spherical angles and converting to Cartesian. And that would clump at the poles. The link that Trapper Zoid linked to tried to combat this by at least having one of the angles generated by using inverse trig functions on positions on a linear axis.

I also question if these really fit for his purposes considering that if he's so concerned about the cost of normalization, that trig functions and such would be just as big a concern. Sure you could use trig tables, but it's hardly worth it these days considering the comparative cost of cache misses.

About the only advantage I can name for using random rotation is that he could construct a rotation matrix and just pull out the vectors -- he'll get 6 already normalized vectors for his troubles, so it may average out a lower cost overall. Sure they'd be orthogonal to each other, but if he's only concerned about getting a suitable set of directions, and isn't particularly concerned with accuracy as he says, it might be acceptable.

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