Fast uniformly distributed random points on the su

问题:

I am trying to generate uniform random points on the surface of a unit sphere for a Monte Carlo ray tracing program. When I say uniform I mean the points are uniformly distributed with respect to surface area. My current methodology is to calculate uniform random points on a hemisphere pointing in the positive z axis and base in the x-y plane.

The random point on the hemisphere represents the direction of emission of thermal radiation for a diffuse grey emitter.

I achieve the correct result when I use the following calculation :

Note : dsfmt* is will return a random number between 0 and 1.

azimuthal = 2*PI*dsfmt_genrand_close_open(&dsfmtt);
zenith = asin(sqrt(dsfmt_genrand_close_open(&dsfmtt)));

// Calculate the cartesian point
osRay.c._x = sin(zenith)*cos(azimuthal); 
osRay.c._y = sin(zenith)*sin(azimuthal);
osRay.c._z = cos(zenith);

However this is quite slow and profiling suggests that it takes up a large proportion of run time. Therefore I sought out some alternative methods:

The Marsaglia 1972 rejection method

do {
   x1 = 2.0*dsfmt_genrand_open_open(&dsfmtt)-1.0;
   x2 = 2.0*dsfmt_genrand_open_open(&dsfmtt)-1.0;
   S = x1*x1 + x2*x2;
} while(S > 1.0f);


osRay.c._x = 2.0*x1*sqrt(1.0-S);
osRay.c._y = 2.0*x2*sqrt(1.0-S);
osRay.c._z = abs(1.0-2.0*S);

Analytical cartesian coordinate calculation

azimuthal = 2*PI*dsfmt_genrand_close_open(&dsfmtt);
u = 2*dsfmt_genrand_close_open(&dsfmtt) -1;
w = sqrt(1-u*u);

osRay.c._x = w*cos(azimuthal);
osRay.c._y = w*sin(azimuthal);
osRay.c._z = abs(u);

While these last two methods run serval times faster than the first, when I use them I get results which indicate that they are not generating uniform random points on the surface of a sphere but rather are giving a distribution which favours the equator.

Additionally the last two methods give identical final results however I am certain that they are incorrect as I am comparing against an analytical solution.

Every reference I have found indicates that these methods do produce uniform distributions however I do not achieve the correct result.

Is there an error in my implementation or have I missed a fundamental idea in the second and third methods?

回答1:

The simplest way to generate a uniform distribution on the unit sphere (whatever its dimension is) is to draw independent normal distributions and normalize the resulting vector.

Indeed, for example in dimension 3, e^(-x^2/2) e^(-y^2/2) e^(-z^2/2) = e^(-(x^2 + y^2 + z^2)/2) so the joint distribution is invariant by rotations.

This is fast if you use a fast normal distribution generator (either Ziggurat or Ratio-Of-Uniforms) and a fast normalization routine (google for "fast inverse square root). No transcendental function call is required.

Also, the Marsaglia is not uniform on the half sphere. You'll have more points near the equator since the correspondence point on the 2D disc <-> point on the half sphere is not isometric. The last one seems correct though (however I didn't make the calculation to ensure this).

回答2:

If you take a horizontal slice of the unit sphere, of height h, its surface area is just 2 pi h. (This is how Archimedes calculated the surface area of a sphere.) So the z-coordinate is uniformly distributed in [0,1]:

azimuthal = 2*PI*dsfmt_genrand_close_open(&dsfmtt);
osRay.c._z = dsfmt_genrand_close_open(&dsfmtt);

xyproj = sqrt(1 - osRay.c._z*osRay.c._z);
osRay.c._x = xyproj*cos(azimuthal); 
osRay.c._y = xyproj*sin(azimuthal);

Also you might be able to save some time by calculating cos(azimuthal) and sin(azimuthal) together -- see this stackoverflow question for discussion.

Edited to add: OK, I see now that this is just a slight tweak of your third method. But it cuts out a step.

回答3:

Have you tried getting rid of asin?

azimuthal = 2*PI*dsfmt_genrand_close_open(&dsfmtt);
sin2_zenith = dsfmt_genrand_close_open(&dsfmtt);
sin_zenith = sqrt(sin2_zenith);

// Calculate the cartesian point
osRay.c._x = sin_zenith*cos(azimuthal); 
osRay.c._y = sin_zenith*sin(azimuthal);
osRay.c._z = sqrt(1 - sin2_zenith);

回答4:

This should be quick if you have a fast RNG:

// RNG::draw() returns a uniformly distributed number between -1 and 1.

void drawSphereSurface(RNG& rng, double& x1, double& x2, double& x3)
{
    while (true) {
        x1 = rng.draw();
        x2 = rng.draw();
        x3 = rng.draw();
        const double radius = sqrt(x1*x1 + x2*x2 + x3*x3);
        if (radius > 0 && radius < 1) {
            x1 /= radius;
            x2 /= radius;
            x3 /= radius;
            return;
        }
    }   
}

To speed it up, you can move the sqrt call inside the if block.

回答5:

I think the problem you are having with non-uniform results is because in polar coordinates, a random point on the circle is not uniformly distributed on the radial axis. If you look at the area on [theta, theta+dtheta]x[r,r+dr], for fixed theta and dtheta, the area will be different of different values of r. Intuitivly, there is "more area" further out from the center. Thus, you need to scale your random radius to account for this. I haven't got the proof lying around, but the scaling is r=R*sqrt(rand), with R being the radius of the circle and rand begin the random number.

回答6:

The second and third methods do in fact produce uniformly distributed random points on the surface of a sphere with the second method (Marsaglia 1972) producing the fastest run times at around twice the speed on an Intel Xeon 2.8 GHz Quad-Core.

As noted by Alexandre C there is an additional method using the normal distribution which expands to n-spheres better than the methods I have presented.

This link will give you further information on selecting uniformly distributed random points on the surface of a sphere.

My initial method as pointed out by TonyK does not produce uniformly distributed points and rather bias's the poles when generating the random points. This is required by the problem I am trying to solve however I simply assumed it would generate uniformly random points. As suggested by Pablo this method can be optimised by removing the asin() call to reduce run time by around 20%.

回答7:

1st try (wrong)

point=[rand(-1,1),rand(-1,1),rand(-1,1)];
len = length_of_vector(point);

EDITED:

What about?

while(1)
 point=[rand(-1,1),rand(-1,1),rand(-1,1)];
 len = length_of_vector(point);
 if( len > 1 )
     continue;
 point = point / len
     break

Acception is here approx 0.4. Than mean that you will reject 60% of solutions.