In-depth: Generating uniformly distributed points on a sphere

[In this reprinted #altdevblogaday in-depth piece, Crytek's technical lead Jaewon Jung shares what he believes is the ideal way for generating uniformly distributed points on a sphere.] Recently, while I was working on a screen-space shader effect, I had to do some random sampling over the surface of a sphere. An effective sampling requires a uniform distribution of samples. After a quick Googling, I found out a way to generate uniformly distributed samples [1], and it showed a decent result for my application. But, still unsure if that was an ideal way, I performed due research about it later. Following is the result of that short research. Usually, in graphics application, one can limit it to the three-dimensional space. In that case, there are four possible approaches, all of which guarantee a uniform distribution (by the way, as for what the 'uniform distribution' exactly means, [6] has some explanations). If n-dimension support is required, one is out, so three remain. Let's take stock of each. Rejection sampling ([2][4][5]) One simple way is something called 'rejection sampling'. For each x, y, z coordinates, choose a random value of a uniform distribution between [-1, 1]. If the length of the resulting vector is greater than one, reject it and try again. Obviously, this method can be generalized to n-dimension. But the bigger the dimension gets, the higher the rejection rate gets, so the less efficient the technique becomes. Normal deviate ([2][5]) This technique chooses x, y and z from a normal distribution of mean 0 and variance 1. Then normalize the resulting vector and that's it. [2] shows why this method can generate a uniform distribution over a sphere. In short,

It works because the vector chosen (before normalization) has a density that depends only on the distance from the origin.

as [5] explains. This also generalizes to n-dimension without a hassle. Trigonometry method ([1][3][4][5]) This one works only for a three-dimensional sphere(called 2-sphere in literatures, which means it has two degrees of freedom), but is an easiest one to intuitively grab how it works. [1] nicely explains why it works from Archimedes' theorem:

The area of a sphere equals the area of every right circular cylinder circumscribed about the sphere excluding the bases.

The exact steps are as below:

• Choose z uniformly distributed in [-1,1].
• Choose t uniformly distributed on [0, 2*pi).
• Let r = sqrt(1-z^2).
• Let x = r * cos(t).
• Let y = r * sin(t).

This is the one I used for my shader effect. Since I had to use a very small number of samples for the sake of performance, I did a stratified sampling with this method. A straightforward extension to a stratified sampling is another advantage of this technique. Coordinate approach ([2][3][5]) The last one is applicable to general n-dimensions and [2] explains its quite math-heavy derivation in detail. This technique first gets the distribution of a single coordinate of a uniformly distributed point on the N-sphere. Then, it recursively gets the distribution of the next coordinate over (N-1)-sphere, and so on. Fortunately, for the usual 3D space (i.e. 2-sphere), the distribution of a coordinate is uniform and one can do a rejection sampling on 2D for the remaining 1-sphere( i.e. a circle). The exact way is explained in [5] as a variation of the trigonometry method. Codes and Pictures Even if you haven't got it all fully up to this point, don't worry. The source code will fill up the gaps in your understanding. You can find my naive C++ implementations of techniques above here: http://ideone.com/oYEVR And some pretty pictures of random points generated by each method: By the way, all of the images above were plotted by Winplot. TL;DR Just use the trigonometry method above and add a stratified sampling, if necessary. That'll be enough for the most of cases. ;) References

1. http://repository.upenn.edu/cgi/viewcontent.cgi?article=1188&context=cis_reports
2. http://www-alg.ist.hokudai.ac.jp/~jan/randsphere.pdf
3. http://mathworld.wolfram.com/SpherePointPicking.html
4. http://cgafaq.info/wiki/Uniform_random_points_on_sphere
5. http://www.math.niu.edu/~rusin/known-math/96/sph.rand
6. http://www.math.niu.edu/~rusin/known-math/95/sphere.faq

[This piece was reprinted from #AltDevBlogADay, a shared blog initiative started by @mike_acton devoted to giving game developers of all disciplines a place to motivate each other to write regularly about their personal game development passions.]