Points on a sphere

October 4th, 2006 by Patrick Boucher - Viewed 54315 times -




I can think of a few reasons why you would want to evenly distribute points on the surface of a sphere. How one would go about it is another thing entirely. When I recently had to create lights on the surface of a sphere for a light rig, I had to Google around for algorithms and I thought I would share some results with you.

Defining Evenly Distributed

Some would argue that for points to be evenly distributed on a sphere the resulting polygonal object defined by the points needs to have faces that are equal as well as an equal number of faces leading into every vertex. These perfect shapes are known as Platonic Solids.

There are unfortunately only five platonic solids: the tetrahedron, cube, octahedron, dodecahedron and icosahedron each having 4, 8, 6, 20 and 12 vertices.

So unless that is exactly the number of points you wish to have around your sphere we must somehow redefine evenly distributed. There is a great discussion on this titled “Topics On Sphere Distributions” by Dave Rusin.

In our case, let’s ignore how the points would combine to create a solid and concentrate on the distance relationship to its neighbors considering the whole set. For any given number of points what we want is for the minimum distance between any two points to be as large as possible. Makes sense? If any two closest points in the whole set are as far apart as possible, all points should be equally distant from their closest neighbor. That is what we will define as evenly distributed.

How to achieve even distribution

One of the most precise ways to organize points on a sphere, given our definition, would be to simulate them repelling themselves with equal force until they settled (see this document by Simon Tatham). It would be exact but wouldn’t necessarily be quick. Then there are three algorithms that approximate the same result all the while requiring less computational power.

The first one is Dave Rusin’s Disco Ball. Although it will wield a very precise pattern the algorithm does not allow to specify an exact number of points which are then distributed.

The second one is the method of Saff and Kuijlaars. This second one packs the points much less tightly than the Disco Ball but manages to do so with any arbitrary number of points.

Finally there is an algorithm based on the greek golden ratio, the Golden Section spiral. This last stab at the problem can generate a set packed more evenly than Saff and Kuijlaars while being able to specify any number of points.

Here is a graphical comparison of the three methods.

My Golden Section Spiral

Here is a Python implementation of the Golden Section spiral:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import math
 
def pointsOnSphere(N):
    N = float(N) # in case we got an int which we surely got
    pts = []
 
    inc = math.pi * (3 - math.sqrt(5))
    off = 2 / N
    for k in range(0, N):
        y = k * off - 1 + (off / 2)
        r = math.sqrt(1 - y*y)
        phi = k * inc
        pts.append([math.cos(phi)*r, y, math.sin(phi)*r])
 
    return pts

By passing any arbitrary number of points to the function, it will return an array of points in space representing the locations of all points on a unit sphere. You can then multiply this unit vector by whatever length you wish to get the position on a sphere of any size.

Paste the above code in the script editor followed by this concrete XSI example and run it to see the results:

1
2
3
4
5
6
for pt in pointsOnSphere(80):
    n = Application.ActiveSceneRoot.AddNull()
    n.size = 0.05
    t = n.Kinematics.Global.Transform
    t.SetTranslationFromValues(pt[0], pt[1], pt[2])
    n.Kinematics.Global.Transform = t

Voilà! I hope this helps you on your way to the perfect spherical distribution. ;)
Yeah… I sometimes have a hard time remembering that our job is to make pretty pictures.

Cheers,

31 Responses to “Points on a sphere”

  1. Kim Aldis says:

    there”s also the geodesic method, based on Buckminster Fuller”s geodesic dome. Geodesics are obtained by taking the last platonic solid, the icosahedron, subdividing the faces and raising the resultant new points to the sphere surface. The way you dubdivide is important and a tad tricky to explain without diagrams but there”ll be some information around somewhere I”m sure.
    It falls into the former category where you can”t define exactly the number of points and the method for increasing detail is recursive.

    Nice article.

  2. Vladimir Jankijeivc says:

    Well, that”s funny. Some time ago, I was searching for some similar algorithms and I came along this: http://mrl.nyu.edu/~perlin/experiments/repel. It”s a pretty nice visualization of how these things look like. Just wanted to shere this and by the way, this was created by Ken Perlin the creator of Perlin noise.

  3. felix says:

    The test criterion in the graphical comparison of the three methods is a bit strange. He uses the half distance of the nearest neighbor. In his test this would be a perfect packing. http://www.sukio.de/dump/notsoperfectpacking.gif

    The difference of the area of the Voronoi cell to the avarage area of all cells ( sphere area / nb points ) or something along those lines would be a better comparison if you”re interested in even distribution.

    Interesting topic, indeed.

  4. Thanks for the comments and continued interest.

    Vladimir, thanks for the link. Neat Experiment Indeed.

    Kim, yup I did omit the geodesic sphere from the article. Maybe I should have included it as it is one method to solve the issue. Francois Lord had shared this with me early in my research but I had extremely rapidly discarded it because, as you said, you can”t define exactly the number of point to be had and, like a simulation, it is iterative in its computational nature making it less appropriate for scripting in Softimage XSI.

  5. Here is an implementation of the Saff and Kuijlaars algorithm in Python:

    [python]def pointsOnSphere(N):
    N = float(N) # in case we got an int which we surely got

    s = 3.6 / math.sqrt(N)
    phi = 0
    pts = [[0, -1, 0]]
    for k in range(1, N-1):
    y = -1 + 2 * k / (N-1)
    r = math.sqrt(1 – y*y)
    phi = phi + s / r
    pts.append([math.cos(phi)*r, y, math.sin(phi)*r])
    pts.append([0, 1, 0])

    return pts[/python]

  6. Great article Patrick. I love all this sort of stuff.

    BTW, I don”t suppose you or anyone else knows of any papers or links for methods that can generate evenly spaced points on an arbitrary mesh, rather than just a sphere?

    Obviously the relaxation method is still valid and also I”ve seen various other things to do with conformal mapping and texture synthesis. Are there any other methods out there that are a little easier to implement?

  7. Andy, I googled really quickly and don”t know if this is one of the techniques you mention but this paper in the ACM”s repository seems interesting…

    http://portal.acm.org/citation.cfm?id=122749

    I gotta get me an account.

  8. Brilliant, I”ve not seen that paper. Thanks for finding it!

  9. Felix, a set of nodes spaced equally on a great circle as you have them — or indeed on any circle — would have congruent Voronoi cells, so how is the Voronoi-area measure better than the nearest-neighbor measure? (Anyway I used the nearest-neighbor distance primarily as a measure of packing efficiency, rather than evenness.)

  10. Michal says:

    Thanks, great article. Just want I needed! Really helpful, thanks again.

  11. Jeremy says:

    Hi guys, great article and discussion. I wonder does anyone have a link or comparison of the various techniques using the voronoi cell area? I am particularly interested in how close to equal area the various combinations of the Rubin’s Disco Ball area. Thanks again!

  12. Joe Wheeler says:

    Thanks Patrick, this is really useful. I’ve ported your golden spiral version to ActionScript.

    public function pointsOnSphere ( num:uint, radius:Number=1.0 ) :Array
    {
    var pts:Array, inc:Number, off:Number, i:uint, y:Number, r:Number, phi:Number;

    num = uint( num );
    pts = new Array( num );
    inc = Math.PI * ( 3 – Math.sqrt( 5 ) );
    off = 2 / num;
    i = num;
    while ( i– ) {

    y = i*off – 1 + ( off / 2 );
    r = Math.sqrt( 1 – y*y );
    phi = i*inc;
    pts[ i ] = { x:Math.cos( phi )*r*radius, y:y*radius, z:Math.sin( phi )*r*radius };
    }

    return pts;
    }

  13. a possibly useful reference page (heavily rewritten by me last September)

  14. Will says:

    Do any of you think you’d be able to expand this to higher dimensions?

    I’m looking to find a way to give me a set of the most unique vectors. This kind of thing would do it i think. the most seperated points on the 10D equivalent of a sphere should be the most unique set of vectors with 10 elements right?

  15. Neil Sloane has some info on spherical arrangements in higher dimensions.

  16. Dan says:

    wow exactly what i was looking for… now my photons are nicely uniformly distributed!

  17. Henry Bland says:

    Thanks for a great resource. Here’s the Matlab version of the Golden Section Spiral method.

    function p = spherepointsgolden(n)
    %SPHEREPOINTSGOLDEN Place points evently on a unit sphere
    % Generate a set of evenly distributed points on a unit sphere
    % using the method of the Golden Section Spiral method.
    %
    % Output is a 3xN matrix of points for X,Y,Z.
    %
    % Based on python code from Patric Boucher on http://www.xsi-blog.com

    inc = pi * (3-sqrt(5));
    off = 2/n;

    k = 0:n-1;
    y = k * off – 1 + (off/2);
    r = sqrt(1 – (y.^2));
    phi = k * inc;

    p = [cos(phi).*r; y ;sin(phi).*r]‘;
    end

  18. [...] number of points evenly. It’s therefore down to weird and wonderful geometry to sort out. This article about points on spheres saves me repeating everything here, but the summary is that there are two approximation [...]

  19. Fantasy Chen says:

    Hi! I want N points evenly distribute within a rectangle. How can I get a fast method?

  20. Chen, here’s one way, off the top of my head. Pick two numbers P,Q, such that gcd(N,P) = gcd(N,Q) = gcd(P,Q) = 1, that is, each pair of numbers is relatively prime (has no common factors).

    for 0 ≤ j < N :
    x[j] = (width/N) * (0.5 + (j*P)%N)
    y[j] = (height/N) * (0.5 + (j*Q)%N)

  21. Will: Do any of you think you’d be able to expand this to higher dimensions?

    I downloaded from somewhere-or-other a doctoral thesis (2006) by a Paul Leopardi at UNSW which gives a method for dividing any N-sphere into sectors of equal area (and reasonable compactness) by lines of latitude and longitude. I haven’t finished looking through it but I suspect that its approach can be adapted to suggest a generalization of the spiral method to N dimensions.

  22. [...] Softimage Blog » Blog Archive » Points on a sphere [...]

  23. chrelad says:

    This is a great write-up on the subject of distribution of points about the surface of a sphere. Great job and very easy to understand for beginners :)

  24. I renamed my site a few months ago from ogre.nu to bendwavy.org, because (unlike in 1998) .org is much cheaper than .nu.

  25. Flavio says:

    Thanks for the “My Golden Section Spiral” code. I have been trying to solve this problem for some time!
    You are a genius, whoever yo are! Thanks again!
    Flavio

  26. [...] Evenly distributing points on a sphere with the golden section spiral Posted on February 25, 2012 This post is based on the recent xsibase thread Golden Section Spiral in ICE, which in turn is based on Patrick Boucher’s 2006 article Points on a sphere. [...]

  27. Bo says:

    Hi,

    How do you get the XSI code to work? My python doesn’t recognize the “application” object.

  28. Jcarlos says:

    Thanks a lot. This is exactly what I needed (and it’s written in Python :)

  29. Chao Huang says:

    Hi,

    I have a question:

    why choose inc = pi*(3-sqrt(5))? What’s the relation between this value and the golden ratio?

    Thanks,
    Chao

  30. morbus cyclometricus says:

    Thanks!

    brilliant i can’t begin to say how concise and complete that text is.

    thought i would notify you of a broken link, the pictures have been taken away on the page specified HERE:

    able to specify any number of points.

    Here is a graphical comparison of the three methods.

  31. morbus cyclometricus says:

    Woah! i must be getting good at programming. i converted this to JS in 30 minutes Woot!!!!

    have to say though! it’s not very regular

    here are some images to demo the phi spiral method, which has alot of charm!
    http://www.flickr.com/photos/27974317@N05/8026304349/in/photostream