Uniform random (Monte-Carlo) distribution on unit sphere

StackOverflow https://stackoverflow.com/questions/1841014

  •  12-09-2019
  •  | 
  •  

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.

Was it helpful?

Solution

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

OTHER TIPS

Here's a Java implementation I've used in the past:

public static double[] randomPointOnSphere(Random rnd)
{
    double x, y, z, d2;
    do {
        x = rnd.nextGaussian();
        y = rnd.nextGaussian();
        z = rnd.nextGaussian();
        d2 = x*x + y*y + z*z;
    } while (d2 <= Double.MIN_NORMAL);
    double s = Math.sqrt(1.0 / d2);
    return new double[] {x*s, y*s, z*s};
}

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:

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.

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.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top