Uniform random (Monte-Carlo) distribution on unit sphere.

Question

Hi!
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

I'm not sure if this make any sense at all, but here you go:

Uniform Fractional Part: A Simple Fast Method for Generating Continuous Random Variates

Answer 2

Here's an algorithm that allows you to generate points randomly distributed on the unit sphere.

Answer 3

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 4

Unless you are raytracing only trivial scenes, will your render time really be dominated by sample picking time? If not, it's probably not worth optimizing yet, though it is worth reading and understanding the uniform sampling techniques given in the other answers.

Also, your samples need not be very random to produce a good estimate of whatever function you're sampling. You may want to investigate using a quasirandom number sequence such as the Halton sequence. Your tetrahedron subdivision idea is not bad. It should result in nice well-distributed points that should be better than uniform pseudorandom samples for most scenes, though could result in horrifying artifacts in some circumstances.

Anyway really you should consult the forums at ompf.org. Got some super hardcore raytracing nerds over there.