Distributing empty GameObjects evenly on a sphere

Is there an easy way to distribute a number of empty GameObjects on a sphere's surface so that every GO has the same distance to its neighbours? I'd like to use these as snapping points to place other objects around it. A subdivided icosphere looks like the way to go, but maybe somebody has a better suggestion?

 

Short answer: Your subdivided icosphere sounds like a great solution. I could not find a ready-to-go algorithm to implement in Unity.

Mathematically, there are only nine exact solutions and their subdivisions. Eg: Some are your standard Dungeons and Dragons dice (d4, d6, d8, d12, d20), with the corners of each die lying on the surface of a sphere.

This question is interesting to me so I actually spent like 5 minutes trying to find some code that can approximate good solutions.

There was this StackOverflow question which had a solution similar to drawing longitude and latitude lines on a globe. This isn't quite what you're looking for because points are closer together towards the poles.

Then I found this long and complex report on various approximation methods created to solve this problem. I think just looking at that page will convince anyone that this is a non-trivial problem.

I don't have time myself to implement and optimize a solution even though this is an interesting topic. Thanks for asking this question!

 

http://www.xsi-blog.com/archives/115

 

If you dig through the links Garth posted above, you'll come across some fairly simple-to-implement methods such as the stepped "longitude" via golden ratio method, which produces something like so (here, 256 primitive spheres are packed on the surface of a sphere of size 3):




Using methods found here:

Code (csharp):

1. dlong := pi*(3-sqrt(5))  /* ~2.39996323 */
2. dz    := 2.0/N
3. long := 0
4. z    := 1 - dz/2
5. for k := 0 .. N-1
6.     r    := sqrt(1-z*z)
7.     node[k] := (cos(long)*r, sin(long)*r, z)
8.     z    := z - dz
9.     long := long + dlong

 

Wow, that was pretty straightforward. Thanks for all the links, guys. Now let's see where I can take this from here.

Code (csharp):

1. using UnityEngine;
2. using System.Collections;
3.  
4. public class SphereMaker : MonoBehaviour {
5.  
6.     public int numberOfPoints = 80;
7.     public float scale = 3.0f;
8.  
9.     // Use this for initialization
10.     void Start () {
11.  
12.         GameObject innerSphere = GameObject.CreatePrimitive(PrimitiveType.Sphere);
13.         innerSphere.transform.localScale = innerSphere.transform.localScale * (scale * 2);
14.         innerSphere.transform.name = "Inner Sphere";
15.  
16.         Vector3[] myPoints = GetPointsOnSphere(numberOfPoints);
17.  
18.         foreach (Vector3 point in myPoints)
19.         {
20.             GameObject outerSphere = GameObject.CreatePrimitive(PrimitiveType.Sphere);
21.             outerSphere.transform.position = point * scale;
22.         }
23.    
24.     }
25.  
26.     Vector3[] GetPointsOnSphere(int nPoints)
27.     {
28.         float fPoints = (float)nPoints;
29.  
30.         Vector3[] points = new Vector3[nPoints];
31.  
32.         float inc = Mathf.PI * (3 - Mathf.Sqrt(5));
33.         float off = 2 / fPoints;
34.  
35.         for (int k = 0; k < nPoints; k++)
36.         {
37.             float y = k * off - 1 + (off / 2);
38.             float r = Mathf.Sqrt(1 - y * y);
39.             float phi = k * inc;
40.  
41.             points[k] = new Vector3(Mathf.Cos(phi) * r, y, Mathf.Sin(phi) * r);
42.         }
43.  
44.         return points;
45.     }
46.  
47. }

 

Ive been following this, thanks everyone who contributed, very interesting!

 

definitely pretty cool

 

Thanks c-Row, exiguous, and mhtraylor for the solution!

 

One thing I noticed is that in some places (mostly the poles it seems) the objects seem to have an even distance to those that - on an imaginary string traveling around the inner sphere - come before and after it, but not those above and below. Most of them seem fine, though. I'll see if I can get the icosphere approach working to do a comparison.

 

You could run a couple of passes of a spreading algorithm afterwards, if you can afford the processing time. The organized layering suggests a pretty efficient algorithm for finding neighbours.

 

Here is another packing techinque I've used before. The parameter is only approximately the number of points.

The technique is to divide the latitude range (per hemisphere) into some number of divisions, and for each slice, divide the circle of latitude into segments with the same arc length as the distance between slices. Through the use of radians this is the same as the angle between latitude layers. Each slice is offset by half of the angle to make them pack better.

With high numbers of divisions the packing "looks" better at the poles than around the equator, but even though portions of the equator are ugly I think it works better than the golden ratio algorithm for these large numbers. The golden ratio algorithm looks ugly around the poles and I think has more proximity problems near the equator, with large point counts.

Code (csharp):

1.  
2.     Vector3[] GetPointsOnSphere2(int nPoints)
3.     {
4.         int divisions = (int)(Mathf.Sqrt(nPoints / 5.0f) + 0.5f);
5.  
6.         var points = new List<Vector3>();
7.  
8.         points.Add(new Vector3(0, -1, 0));
9.  
10.         float angle = Mathf.PI / 2 / divisions;
11.        
12.         for (int iLat = -divisions+1; iLat < divisions; ++iLat)
13.         {
14.             float lat = iLat*angle;
15.            
16.             float circumference = 2 * Mathf.PI * Mathf.Cos(lat);
17.             int steps = (int) (circumference/angle);
18.            
19.             float baseAngle = lat / 2;
20.            
21.             for (int iLon = 0; iLon < steps; ++iLon)
22.             {
23.                 float lon = baseAngle + iLon*2*Mathf.PI/steps;
24.                 points.Add(new Vector3(Mathf.Sin(lon)*Mathf.Cos(lat), Mathf.Sin(lat), Mathf.Cos(lon)*Mathf.Cos(lat)));
25.             }
26.         }
27.  
28.         points.Add(new Vector3(0, 1, 0));
29.  
30.         return points.ToArray();
31.     }
32.  

 

Nice - from a first test the poles really look better than those from the golden ratio version. I had to change two lines to get it working in my C# script, but everything else worked out of the box.

Code (csharp):

1.  
2. ArrayList points = new ArrayList();
3. ...
4. return points.ToArray(typeof(Vector3)) as Vector3[];
5.  

From a game design point of view I also prefer yours over mine.

 

Ah, it needed "using System.Collections.Generic". Resharper just added it for me so I didn't notice.

An interesting alternative is to remove the top and bottom points (lines 7 and 27 in my code above) and change line 9 to use a slightly larger angle, so the circular slices go nearer the pole:

Code (csharp):

1.  
2.         float angle = Mathf.PI / 2 / (divisions - 1 + 1 / Mathf.Sqrt(3));
3.  

It gives a different effect, and may be better for smaller numbers of points? I'm not sure really.