Generating Equidistant Points on a Sphere

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.

image

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.

image

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.

image

We will come back to this later on in the post, but for now, let’s start coding.

2. Generating points on a circle

image

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.

image

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

Screenshot_234

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 ϱ.

image

The above image is an easier representation of our point, which comes from this diagram:

image

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.

image

Substituting the first set of equations into the second set:

image

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.

image

image

image

image

image

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.

Screenshot_230

75 Likes

Maths… I love them, especially when they’re used in such an amazing tutorial like this.

Imo it is hard to read your handwritten notes, but it is kind of understandable.

Definitely will be using this!

3 Likes

Thanks for this. I never knew I could do this, and now that I can, it creates so many use cases, such as being able to do hitbox detection with rays for spherical shapes, which is very useful. Bookmarked for later.

4 Likes

Thanks a lot. I was trying to learn sphere generation but I couldn’t figure out how. I’ll bookmark it for future needs. :grinning: Any way you can make the lines straight and even though
?

1 Like

Hi, I’m glad you found the post helpful! Could you elaborate on what you mean, and I can try my best to help you out.

1 Like

I’m awful at geometry so forgive me if this is a stupid question, but would you use this basic premise to generate a spiral galaxy sort of shape dotted with star systems (+planets)? The shape looks kind of similar if not for the frequency of the arms.

2 Likes

Definitely not a stupid question - it’s a good observation! I’ve just increased the multiplier so it’s easier to tell, but you can see how golden spiral forms and creates the arms.

function Object:GeneratePoints(n)
	local goldenRatio = 1 + math.sqrt(5)
	local angleIncrement = math.pi * 2 * goldenRatio
	local multiplier = 40

	for i = 0, n do
		local distance = i / n
		local angle = angleIncrement * i

		local x = distance * math.cos(angle) * multiplier 
		local y = distance * math.sin(angle) * multiplier

		self:PlotPoints(x, y)
	end
end

Here you can see the ratio visualised on-top of a galaxy:

image

As far as I know, the shape of spiral galaxies follow a logarithmic spiral. However, the golden spiral (or the Fibonacci spiral, which is an approximation of the golden spiral) does a good job in more or less getting that shape. I’m sure someone else will know a lot more than I do about that. I would love to see a galaxy created using this method, that’ll be super cool.

4 Likes

Very detailed and informative resource here. First thing that popped in my head was Sebastian Lague’s tutorial on Boids, which I’m always a fan of studying.

1 Like

Like right now the sphere generates as a spiral. Any way I can make it generate as a circle? Because we started from a base of a spiral.

Hello,

could you make one full script, where we can easily see everything?
I cant see the full script of yours because right now I can just see script parts. Thanks if thats possible!

Yes I know this is a tutorial, but it is really hard to scroll up down each time :confused: hope you can understand that.

1 Like

This is an amazing tutorial, very few can actually go as deep as you in mathematics; I’m almost certain this will be really useful outside of Roblox too.

1 Like

Looking at the graphics. This will be a mathematical master piece. Thanks for the tutorial !

1 Like

Hi. This is the function~

function pointsOnSphere(n: number) -- where `n` is number of points
	local MULTIPLIER = 10
	
	local vectors = {}

	for i = 0, n do
		local incline = math.acos(1 - 2 * (i / n))
		local azimuth = (math.pi * 2 * (1 + math.sqrt(5) / 4)) * 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 
		
		table.insert(vectors, Vector3.new(x, y, z))
	end
	
	return vectors
end
1 Like

Hey, I just created a module for this.
You can get it the module here → https://web.roblox.com/library/6390346767/SphereModule

The module will create the spheres around base parts, changing multiplier and n based off the size of the part you attach it to.

Here’s the source code if you’re interested:

Summary
local sphere: (table) = {}
sphere.__index = sphere

local baseVector: (Vector3) = Vector3.new(1, 1, 1)

-- [[ Settings ]] --

local AmountOffset = 4 -- Recommended
local SizeOffset = 6 -- Recommended

--⋅--------------⋅--

type newSphereInstance = {
	_instance : Instance,
	_pointPositions: table,
	_points: table,
}

function sphere.new(instance: Instance)
	local self: newSphereInstance = {
		_instance = instance,
		_pointPositions = {},
		_points = {},
	}

	local newSphere: table do
		sphere[instance] = setmetatable(self, sphere)
		newSphere = sphere[instance]
	end

	return newSphere
end

function sphere:GeneratePoints(n: number, props: table)
	type vector = {
		x: number,
		y: number,
		z: number,
	}

	type properties = {
		Parent: Instance,
		CanCollide: boolean,
		BrickColor: BrickColor,
		Material: Enum.Material,
		Transparency: number,
	}

	local props: (properties) = props or {
		Parent = workspace,
		CanCollide = false,
		BrickColor = BrickColor.Red(),
		Material = Enum.Material.Neon,
		Transparency = 0.75,
	}

	local part: (BasePart) = self._instance
	local size: (Vector3) = part.Size

	local goldenRatio: (number) = 1 + math.sqrt(5) / 4
	local angleIncrement: (number) = math.pi * 2 * goldenRatio
	local multiplier: (number) = (size.x + size. y + size.z) / SizeOffset
	local n: (number) = n or math.abs(multiplier * 24) * AmountOffset

	for i: (number) = 0, n do
		local distance: (number) = i / n
		local incline: (number) = math.acos(1 - 2 * distance)
		local azimuth: (number) = angleIncrement * i

		local plotPosition: (vector) = {
			x = math.sin(incline) * math.cos(azimuth) * multiplier,
			y = math.sin(incline) * math.sin(azimuth) * multiplier,
			z = math.cos(incline) * multiplier
		}

		table.insert(self._pointPositions, plotPosition)
	end

	self:PlotPoints(props)
end

function sphere:PlotPoints(properties: table)
	for _, position: (table) in pairs(self._pointPositions) do
		local part: (BasePart) = Instance.new("Part")
		part.Anchored = true

		for property: (string), value: (any) in pairs(properties) do
			part[property] = value
		end

		part.Size = baseVector * 0.25
		part.Position = self._instance.Position + Vector3.new(position.x, position.y, position.z)

		table.insert(self._points, part)
	end
end

function sphere:ClearPoints()
	for index: (number), point: (Instance) in pairs(self._points) do
		point:Destroy()
		self._points[index] = nil
	end
end

function sphere:GetPoints()
	return self._points
end

return sphere

Here’s how it’s used:

-- Script inside a part
local ServerStorage = game:GetService("ServerStorage")
local SphereModule = require(ServerStorage:WaitForChild("SphereModule")) -- Just assuming you put the module in ServerStorage

local part = script.Parent

local sphere = SphereModule.new(part)
sphere:GeneratePoints() -- Generates the points
-- You can also manually set the amount of points by doing sphere:GeneratePoints(100)
-- Or set the properties of the points:
-- sphere:GeneratePoints(nil, {
--	Parent = workspace,
--	CanCollide = false,
--	BrickColor = BrickColor.Red()
--	Material = Enum.Material.Neon,
--	Transparency = 0.75,
--}

wait(5)
sphere:ClearPoints() -- Destroys all the points

I encourage people to still read the tutorial as it’s full of useful information

1 Like

How would I calculate points in a hemisphere?

When calculating the incline, instead of using twice the distance, you can do 1 minus the distance to get half a sphere~

math.acos(1 - distance)

image

1 Like