Generating Equidistant Points on a Sphere
In this post, I’ll be covering how to generate points in 3D space that are equally spaced on the unit sphere. The method is based on a spiral walk of the spherical surface in angular increments equal to the golden angle. At the end of this post, I’ll also briefly go over some potential uses in your games, and what I’m personally using it for.
1. The Golden Ratio
Let’s first illustrate what the golden ratio is. Say you have a line segment a, and another shorter segment b.
When the sum of both lengths, divided by the long segment, is equal to the long segment divided by the short segment then this is the golden ratio.
This is represented by the greek symbol Phi φ.
We can then find the positive solution to this equation, which will give us the value of φ.
The golden angle is the angle subtended by the small arc b. This is approximately 2.39 radians.
We will come back to this later on in the post, but for now, let’s start coding.
2. Generating points on a circle
Before we jump straight into implementing this algorithm in 3D space, let’s first consider generating the points on a 2D circle.
The approach is based on the fact that if you stand in the center of this circle, and then turn a golden ratio of whole turns, and then place a point in that direction, you will construct a spiral pattern with points that line up nicely to give us a uniform distribution.
Firstly, I’ll create a new object:
local Object = {}
Object.__index = Object
return Object
And inside of the constructor, I’ll define a table to add the Vector3 points to, so we can access them later.
function Object.new()
local self = setmetatable({}, Object)
self._points = {}
return self
end
Next, I’ll create a new method called Object:GeneratePoints(n), where n is the number of points we want to generate on the circle.
function Object:GeneratePoints(n)
end
We can express our golden ratio, φ, as 1 + math.sqrt(5) / 2, which came from our positive solution to the equation. Let’s put that into a variable.
local goldenRatio = 1 + math.sqrt(5) / 4
We now want to calculate how much we want to increment the angle for every “turn”, where we want to plot the points with even-area spacing around the circle. We’re going to use a method called sampling the inverse cumulative distribution function. This is used as a basic method for generating sample numbers at random from any probability distribution given its cumulative distribution function.
Further reading for those interested:
This gives us:
local angleIncrement = math.pi * 2 * math.random()
As we want to uniformly sample this function, as opposed to randomly sampling it, we’ll replace math.random() with our golden ratio to get equal-area spacing and avoid “lines” of points upon generation.
local angleIncrement = math.pi * 2 * goldenRatio
Lastly, we want to create a loop which will generate each point according to n, the number of points we want.
First I’ll create the loop:
for i = 0, n do
end
Then, inside the loop I’m going to define a distance, which will go from 0 to 1 over the course of the loop.
for i = 0, n do
local distance = i / n
end
I’ll then define an angle, where each iteration of the loop it will turn some fraction of the circle. In our case, we will use the angleIncrement variable we have just defined above, and multiply that with the current increment of the loop i.
for i = 0, n do
local distance = i / n
local angle = angleIncrement * i
end
Next, we want to calculate the position of the point on the circle.
We can use basic trigonometry, where we can calculate the X and Y positions using a right-angled triangle, where our hypotenuse is equal to the distance.
Therefore:
for i = 0, n do
local distance = i / n
local angle = angleIncrement * i
local x = distance * math.cos(angle)
local y = distance * math.sin(angle)
end
And lastly, we want to render this point somehow into the game world. For this example, I’m going to create a new method which will spawn a part into the workspace with a Vector3 position of (x, y, 0). The z value of the vector doesn’t matter at the moment, since we’re only creating the points in two dimensions, so for now I’ll set the value to 0.
Here’s what I’m going to use:
function Object:PlotPoints(x, y)
local point = Instance.new("Part")
point.Anchored = true
point.Material = "Neon"
point.CanCollide = false
point.Color = Color3.fromRGB(69, 99, 115)
point.Transparency = 0
point.Size = Vector3.new(0.25, 0.25, 0.25)
point.Parent = game.Workspace
point.Position = Vector3.new(x, y, 0) -- Here is where I plug in our point values
end
Let’s call PlotPoints inside of our GeneratePoints method.
for i = 0, n do
local distance = i / n
local angle = angleIncrement * i
local x = distance * math.cos(angle)
local y = distance * math.sin(angle)
self:PlotPoints(x, y)
end
Great! Let’s create a new object with the constructor and call the GeneratePoints method with 100 points to start off with. Here is the result:
That’s a great start, however, there seems to be some issues. The values returned are way too small, so all the parts are bunched up together. To fix this, I’m going to create a new variable inside of our GeneratePoints method called multiplier, which I’ll multiply with the x and y values we calculate.
function Object:GeneratePoints(n)
local goldenRatio = 1 + math.sqrt(5)
local angleIncrement = math.pi * 2 * goldenRatio
local multiplier = 10 -- 10 seems to be a reasonable number
for i = 0, n do
local distance = i / n
local angle = angleIncrement * i
-- For both x and y, I'll multplier the value by our multiplier
local x = distance * math.cos(angle) * multiplier
local y = distance * math.sin(angle) * multiplier
self:PlotPoints(x, y)
end
end
At the moment, you can see that the points follow this spiral pattern, which comes from out golden ratio. In order to space the points out a bit more, I’m going to divide the golden ratio by a factor of 4.
local goldenRatio = 1 + math.sqrt(5) / 4
On a circle, this result looks a little underwhelming, but as we convert this into a sphere, our equidistant points will fall into place nicely.
Our final result should look something like this:
3. Generating points on a sphere
In order to create the points on a sphere, we’re going to need to make some adjustments to our existing code.
We will use our method of sampling the inverse cumulative distribution function again, however, this time we’ll be using spherical coordinates as opposed to polar coordinates. As we’re on a unit sphere, the radial coordinate doesn’t matter. 0 ≤ φ ≤ π is the longitude (the lines comes down from the poles), and 0 ≤ θ ≤ 2π is the lattitude.
Let’s assign the result to a new variable called incline. Our incline is the angle between the zenith direction and the line segment from our origin to the point.
local incline = math.acos(1 - 2 * distance)
Our angle that we calculate will stay the same:
local angle = angleIncrement * i
However, as we are talking about spherical coordinates and not polar coordinates, the correct term is the azimuth, which is the angle measured from the azimuth reference direction to the projection of the line segment created from the origin to the point.
Let’s appropriately rename the variable:
local azimuth = angleIncrement * i
As with before, we want to calculate the position of the point on the sphere.
Firstly, we’ll find the spherical coordinates in terms of r, z, φ and ϱ.
The above image is an easier representation of our point, which comes from this diagram:
Now, we’ll convert from the spherical coordinates for our point into Cartesian form, which will give us the values in x, y and z.
Substituting the first set of equations into the second set:
Writing this in code:
local x = math.sin(incline) * math.cos(azimuth) * multiplier
local y = math.sin(incline) * math.sin(azimuth) * multiplier
local z = math.cos(incline) * multiplier
In our GeneratePoints method, we can now pass the z value into the PlotPoints method. Don’t forget to also change the value in the PlotPoints method.
self:PlotPoints(x, y, z)
The GeneratePoints method should look something like this:
function Object:GeneratePoints(n)
local goldenRatio = 1 + math.sqrt(5) / 4
local angleIncrement = math.pi * 2 * goldenRatio
local multiplier = 10
for i = 0, n do
local distance = i / n
local incline = math.acos(1 - 2 * distance)
local azimuth = angleIncrement * i
local x = math.sin(incline) * math.cos(azimuth) * multiplier
local y = math.sin(incline) * math.sin(azimuth) * multiplier
local z = math.cos(incline) * multiplier
self:PlotPoints(x, y, z)
end
end
Cool! Once again, I’ll call the GeneratePoints method with 400 points. Here is the result:
Lastly, I’ll put each point’s Vector3 position into a table.
self.points[i] = Vector3.new(x, y, z)
I’ll put this inside of the loop:
for i = 0, n do
local distance = i / n
local incline = math.acos(1 - 2 * distance)
local azimuth = angleIncrement * i
local x = math.sin(incline) * math.cos(azimuth) * multiplier
local y = math.sin(incline) * math.sin(azimuth) * multiplier
local z = math.cos(incline) * multiplier
self._points[i] = Vector3.new(x, y, z) -- Right here!
self:PlotPoints(x, y, z)
end
That’s all! As a closing note for this section, I’ll include some images of what happens when you change around the sines and cosines. Have a play around yourself.
4. Uses and closing notes
Other than being a visually beautiful representation of mathematics, there are a few cases where this may come in helpful in your own games that I can think of:
- Visual effects, such as spells for an RPG game.
- Can be used in tandem with raycasting to create basic character vision.
You can also generate points, as I did further up the post, at a slow rate. Perhaps you could also animate them in some way, or maybe apply a trail to one point and move that point through its positions.
Personally, I’m using this technique to implement Boids into my own game.
I’m currently working on creating basic obstacle avoidance using raycasting. I’m limiting the number of points that are generated to simulate the field of view of the Boid. The Boid will go in the best direction to avoid obstacles and other Boids. That’s the idea anyways, but it’s still in early stages.
Any way you can make the lines straight and even though
hope you can understand that.