Uniform random (Monte-Carlo) distribution on unit sphere

Question

I need a clarification with algorithm generating random values for my pet ray-tracer.
I emit rays from one point. And I have the problem with distribution of these rays: I need the distribution to be uniform, but it isn't...

The problem I face now is that the distribution being uniform initially is not uniform after my distortions of the space of results.

So for example, I generate r and t angles if the polar coordinate system. The distribution is not uniform and it cannot be uniform: space close to each pole has much more density of results than, say, close to equator. The reason is pretty clear: I convert uniformly distributed points from cylindrical space to the spherical. And I distort results. The same problem is if I normalize points generated randomly in the cube.

My idea now is this: I want to create a tetrahedron, normalize its vertexes, split each face (triangle) with the point in the middle, normalize it and repeat recursively until I have enough points. Then I "distort" these points a little bit. Then I normalize them again. That's it.

I understand that this method is not pure mathematical Monte-Carlo method itself, because I do not use random distribution in any step except for the last one. And I do not like this solution for this complexity.

Can anyone suggest anything more simple yet still

• random
• uniform
• fast
• simple

Thanks!

EDIT:
I need a fast method, not just the correct one. That's why I'm asking about Monte-Carlo. Answers provided are correct, but not fast. The method with tetrahedron is fast, but not very "random" => incorrect.
I really need something more suitable.

Answer 1

For a spherical sections generate your angle uniformly in phi (the polar angle) and cos(theta) (for theta the azimuthal angle) between your limits.

In pseudo code:

phi = phi_low_limit        + rand()*(phi_high_limit       - phi_low_limit)
ct = cos(theta_high_limit) + rand()*(cos(theta_low_limit) - cos(theta_high_limit))
// The order is inverted here because cos heads down for increasing theta
theta = arccos(ct)

This is a special case of the rule that says invert the Jacobian and generate uniformly in that space of those coordinates.

Note: Note that I'm using the opposite convention for phi and theta from David Norman line.

Note also: This isn't actually the fastest method, but rather one that illustrates the general principle.

Answer 2

Do you really need random distribution or an even distribution over the sphere?

Then I would suggest ZCW angles, which are equally distributed all over the sphere and fast to calculate. Other methods are TheSydneyOperaHouse(SOPHE) and Repulsion. (search for repulsion.c) The repulsion method is quite good but slow: It iteratively distributes points evenly over a sphere. Fortunately it has to be done only once.

This is used in crystallography and NMR, because for powder patterns it is faster to use an even distribution versus random distribution (you need less points).

Here is a Python implementation for ZCW.

More details in these papers:

• Investigations of a nonrandom numerical method for multidimensional integration, Cheng, Vera B. and Henry H. Suzukawa, Jr. and Wolfsberg, Max

• Computer simulations in solid-state NMR. III. Powder averaging, Matthias Edén