Archived

This topic is now archived and is closed to further replies.

random vector

This topic is 5149 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Get two random angles (known conventially as azimuth and elevation). You then convert the resulting spherical polar angle to cartesians. eg:

x=sin(phi)*cos(theta)
y=sin(phi)*sin(theta)
z=cos(phi)

That should be uniformly distributed as you require.

EDIT: Its a unit vector already btw

[edited by - dmounty on November 9, 2003 3:07:22 PM]

Share this post


Link to post
Share on other sites
or:
create a vector where all components are between [-1,1]
find its magnitude
if magnitude>1 then start over again
divide all componenst by the magnitude and voila.

Share this post


Link to post
Share on other sites
dmounty''s solution will be a much worse approximation of a uniform distribution than your (quasar3d) original method.

A better idea would be to generate a random vector in a unit cube, then throw out the vector if it''s magnitude is larger than 1. If it''s smaller, renormalize it to magnitude 1. If it''s larger, generate a new one. If you want to avoid too many regenerations, worst case scenario, limit the retries to 5 or so, and just renormalize whatever you get. The difference in distribution should be minimal.

Share this post


Link to post
Share on other sites
This is from FlipCode (COTD/TOTD). Proven to be totaly unform.


void CVector3::RandomUnit() {
z = Random.GetFloat( 1.0f, -1.0f );
const float angle = Random.GetFloat( PI * 2.0f );
const float r = Math::Sqrt( 1.0f - z*z );
Math::SinCos( angle , x, y );
x *= r;
y *= r;
}


You should never let your fears become the boundaries of your dreams.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by Geoff the Medio
dmounty''s solution will be a much worse approximation of a uniform distribution than your (quasar3d) original method.

Why do you think that?

Share this post


Link to post
Share on other sites
AP: The two-angle solution would have a much higher concentration of points at the poles, not very uniform at all.

Does any one know: If you took a random axis and angle, and rotate the vector (1,0,0) around the axis by the angle, will you get a uniform distribution?

Tom

Share this post


Link to post
Share on other sites
thanks everybody.

I think I will just use the trial and error way, because I think it''s the lessest expensive to compute. Darkwings seemed to work perfectly, but it seems very expensive to compute.

quote:
Original post by _DarkWIng_
This is from FlipCode (COTD/TOTD). Proven to be totaly unform.


void CVector3::RandomUnit() {
z = Random.GetFloat( 1.0f, -1.0f );
const float angle = Random.GetFloat( PI * 2.0f );
const float r = Math::Sqrt( 1.0f - z*z );
Math::SinCos( angle , x, y );
x *= r;
y *= r;
}


You should never let your fears become the boundaries of your dreams.


You say it''s proven to be totaly uniform. Can you tell me that proof, please? I always like to understand this sort of things

My Site

Share this post


Link to post
Share on other sites
The reason the 2 angle approach isn''t uniform is because the surface of the solid angle near the poles has a smaller area where as a solid angle near the equator has a larger surface area. Therefore the the distribution gets ''squeezed'' near the poles and ''stretched'' near the equator.

Share this post


Link to post
Share on other sites
quote:
Original post by ParadigmShift
Does any one know: If you took a random axis and angle, and rotate the vector (1,0,0) around the axis by the angle, will you get a uniform distribution?


Yes, but if you had a (uniform) random axis, you''d have already solved the main point of the problem...

_DarkWIng_: Are you sure that''s uniform? It seems to me that it would underrepresent the poles. Think of shading by dotproduct of normal with light direction vector... the parts of a sphere that have normal not close to the vector of the light sorce are less shaded. I think this algorithm would be like having a light source that''s uniform in the plane of the equator. All points at the same lattitude of a sphere would get the same distribution of random vectors, but the ratio of actual surface area to arc-area (better term?) would vary for different latitudes and the vector distribution would vary accordingly... unless I''m visualizing this incorrectly...

Share this post


Link to post
Share on other sites
I would have to agree that the method Darkwing posted doesn''t look like it would be uniform, for the same reason the 2 angle approach isn''t uniform. The z effectively picks a circle on the sphere, which is what one of the angles in the 2 angle method does. To make it uniform, you''d need z values to be biased towards 0.

Share this post


Link to post
Share on other sites
use a customised rand function for the Z aspect (-90 to 90).
quadratic distribution should do it perfectly.


after you get the Z, then all you need is a random rotation around the axis on the XY plane (Z axis) between 0 and 360.


Bingo.

Share this post


Link to post
Share on other sites
quote:
Original post by Geoff the Medio
quote:
Original post by ParadigmShift
Does any one know: If you took a random axis and angle, and rotate the vector (1,0,0) around the axis by the angle, will you get a uniform distribution?


Yes, but if you had a (uniform) random axis, you'd have already solved the main point of the problem...

_DarkWIng_: Are you sure that's uniform? It seems to me that it would underrepresent the poles. Think of shading by dotproduct of normal with light direction vector... the parts of a sphere that have normal not close to the vector of the light sorce are less shaded. I think this algorithm would be like having a light source that's uniform in the plane of the equator. All points at the same lattitude of a sphere would get the same distribution of random vectors, but the ratio of actual surface area to arc-area (better term?) would vary for different latitudes and the vector distribution would vary accordingly... unless I'm visualizing this incorrectly...



I've thought about that too, but I tried it out, and it looks very uniform



I guess two things are compensating each other. The Dot product of the normal and the incidence angle is a cosine, but the radius of the circle (a slice of the sphere) at that height is also a cosine (well a cosine * 2 * PI, but PI doesn't change, so that doesn't make a difference)
He, did I just prove that function?

[edited by - Quasar3D on November 9, 2003 6:54:16 PM]

[edited by - Quasar3D on November 9, 2003 6:56:11 PM]

[edited by - Quasar3D on November 9, 2003 8:58:41 PM]

Share this post


Link to post
Share on other sites
I was going to say that i didn''t think _DarkWIng_''s solution is uniform... But after thinking about it a bit, this method i don''t think is uniform:

x=sin(phi)*cos(theta)
y=sin(phi)*sin(theta)
z=cos(phi)

because your are going to get more vectors than you should do tending towards z = 1 and z = -1...

However with DarkWIng''s method:

void CVector3::RandomUnit() {
z = Random.GetFloat( 1.0f, -1.0f );
const float angle = Random.GetFloat( PI * 2.0f );
const float r = Math::Sqrt( 1.0f - z*z );
Math::SinCos( angle , x, y );
x *= r;
y *= r;
}

z is chosen at random between 1 and -1, not using cosine function... which is effectively biasing z towards 0 as Mastaba was saying...

Whether it is biasing z towards to 0 by the right amount, i don''t have a clue But i have a feeling it works out just right.

Share this post


Link to post
Share on other sites
Yeah.. just confirmining, my method is not uniform. As people have noted... high concentration around the poles. The original method is not uniform either though... since its mapping a cubic probability space to a spherical one. The cubic values, and retrying if they lie outside the sphere is probably the best method. This is very close to uniformly distributed (only rounding errors for small values cause very minor skew in distribution, but thats nothing to worry about).

Share this post


Link to post
Share on other sites
quote:
Original post by quasar3d
I''ve thought about that too, but I tried it out, and it looks very uniform


Did you try plotting the simple point-in-a-cube and normalize method? Was there a noticable concentration of points corresponding to corners of the cube? I''m just wondering if you have enough points to notice the difference...



Share this post


Link to post
Share on other sites
Darkwing's method is correct. It is fairly easy to prove. First, what does uniform distribution mean when speaking of a distribution across a surface? It means the probability of a point being within any given region is equal to the area of that region divided by the total surface area. So the probability that you get a point with a z in the interval [z1,z2] where -1 <= z1 < z2 <= 1 has to be the surface area of the sphere between z=z1 and z=z2 divided by the total surface area. With a unit sphere that is 2*pi*(z2-z1)/(4*pi) = 1/2(z2-z1). With a uniform distribution between -1 and 1 the chance of getting a value between z1 and z2 is (z2-z1)/(1-(-1)) = 1/2(z2-z1). So the chance of getting a given z within some interval is correct. Given a z it is fairly intuitive that the distribution around that circle is uniform since the arc length of a unit circle from t1 to t2 is t2-t1 and the circumferance is 2*pi.

[edited by - LilBudyWizer on November 9, 2003 11:28:49 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by LilBudyWizer
With a unit sphere that is 2*pi*(z2-z1)/(4*pi) = 1/2(z2-z1).


The area of a cylinder of radius 1 and height (z2 - z1) would be 2*Pi*(z2 - z1), yes, but we''re talking about a sphere here... the local radius varies as you vary z. You can''t assume that you can just multiply the length of the circumference of the equator by the height of the sphere to get the area. You need to show that the loss of circumference at higher lattitudes is exactly compensated for by the increase in area due to the surface being tilted from the direction of measure (z).

That said, surface area of a sphere A = 4*Pi*R^2 = (2*Pi*R)*(2*R)

so I''m inclined to believe, but your proof is incomplete...

Share this post


Link to post
Share on other sites
Spherical cap is what I used, what would you use?

Maybe a little more explaination would help. While the radius is decreasing the arc length for a given z increment is increasing. You can't look at just the radius, but also have to consider that arc length because you are dealing with an area, not a length. Given a parametric equation (x,y,z)=r(u,v) you have to consider the rate of change with respect to both u and v. dr/du and dr/dv are those rates of change. The magnitude of the cross product of those is the incremental area. You then integrate that varying u and v. When it is all done and said you have 2*pi*cos(phi). What is phi? acos(z1) and acos(z2). So you end up with 2*pi*(z2-z1).

[edited by - LilBudyWizer on November 10, 2003 3:51:51 AM]

Share this post


Link to post
Share on other sites
Ok, I plugged DarkWing's algorithm into Maple and I have to stand corrected. Its results are indeed uniform. The Maple 7 source is here if anyone wants it.

And I can now see why it is uniform. While it is very similar to the two angle method, there is a critical difference. In this method the z is chosen uniformly. In the two angle method, an angle phi is chosen uniformly, and from it you get z=cos(phi), so that z is clearly not uniform.



[edited by - Mastaba on November 10, 2003 9:40:41 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by Geoff the Medio
quote:
Original post by quasar3d
I''ve thought about that too, but I tried it out, and it looks very uniform


Did you try plotting the simple point-in-a-cube and normalize method? Was there a noticable concentration of points corresponding to corners of the cube? I''m just wondering if you have enough points to notice the difference...



Yes, I''ve tried that too, and you can really notice concentrations around the corners and edges

My Site

Share this post


Link to post
Share on other sites
I was thinking though the implications of darkwing's method being uniform is. If z is just a random number, then it implies that the SA of a spherical cap is independant of its position (a & b) in the sphere, it is just dependant on the radius of the sphere and the width of the gap!
If you scroll down to the bottom of the link, it states just that. Am I the only one who finds this striking?

EDIT: Wow, this is even more surprising. I am kicking myself I have not already heard it:http://mathworld.wolfram.com/ArchimedesHat-BoxTheorem.html

[edited by - sadwanmage on November 10, 2003 2:16:17 PM]

Share this post


Link to post
Share on other sites
I got my function from here : http://www.flipcode.com/cgi-bin/msg.cgi?showThread=COTD-RandomUnitVectors&forum=cotd&id=-1

There is a (long) discussion why and how it works.

You should never let your fears become the boundaries of your dreams.

Share this post


Link to post
Share on other sites
i see you guys have almost totally dissed the first method for plotting random points on a sphere. if you forgot what the first method was, it was this:
x = rand();
y = rand();
z = rand();

then normalize, then multiply by radius. Here's a screenshot of an old space game I made . you are inside a sphere, the stars were generated almost exactly the same as above, except I did:
x = rand() - rand();
y = rand() - rand();
z = rand() - rand();
then nromalize, and mult by radius. this gives aesthetically pleasing, and it's easier than the spherical coordinates based on the two angles.

http://cboard.cprogramming.com/showthread.php?s=&threadid=37664


and here's another picture that gives you an outside of the sphere view, it's a little dimmer


http://cboard.cprogramming.com/showthread.php?s=&threadid=36607




[edited by - Shadow12345 on November 13, 2003 6:15:54 PM]

Share this post


Link to post
Share on other sites