A fast CFrame hack for finding a bounding sphere of four points

Resources Community Resources
#1

Hi everyone. A while back I was playing around with the following problem:

Given four points in 3D space, how can I find the sphere touching each of those points (if it exists)?

Since this problem isn’t always possible to solve, it may be tricky to deal with the cases cleanly.

I first wrote out a solution on paper, and then I went to implement it in Roblox.

I ended up finding a way to do it that uses CFrame in a “hacky” way.

I’ll eventually try to explain what I did here. But first let me just show you all what I did!

[working model link]

Dragging around points, showing their bounding sphere.

Watch how the code deals with singularities:

The sphere "flips between vanishing points."

ModuleScript

local module = {}

function module:InvertMatrix3D(matrix: CFrame): CFrame
	local _, _, _, a, b, c, d, e, f, g, h, i = matrix:GetComponents()
	local adjugate = CFrame.new(
		0, 0, 0,
		e * i - f * h,
		c * h - b * i,
		b * f - c * e,

		f * g - d * i,
		a * i - c * g,
		c * d - a * f,

		d * h - e * g,
		b * g - a * h,
		a * e - b * d
	)
	local det = matrix:Inverse().XVector:Dot(adjugate.XVector)
	return CFrame.fromMatrix(
		Vector3.zero,
		adjugate.XVector / det,
		adjugate.YVector / det,
		adjugate.ZVector / det
	)
end

function module:GetCircumcenter3D(point0: Vector3, point1: Vector3, point2: Vector3, point3: Vector3): Vector3
	local matrix = CFrame.fromMatrix(
		Vector3.zero, -- fourth column
		point1 - point0, -- first column
		point2 - point0, -- second column
		point3 - point0 -- third column
	)
	local inverse = module:InvertMatrix3D(matrix:Inverse()) -- get the inverse of the transpose of the matrix

	local dotProducts = Vector3.new(point1:Dot(point1), point2:Dot(point2), point3:Dot(point3))
	local vector = (dotProducts - point0:Dot(point0) * Vector3.one) / 2

	return inverse * vector
end

return module

Example use

local RunService = game:GetService("RunService")
local ReplicatedStorage = game:GetService("ReplicatedStorage")
local Utilities = require(ReplicatedStorage.Common.BoundingSphere)

local quad: {BasePart} = workspace.Quad:GetChildren()
local part0, part1, part2, part3 = unpack(quad)
local circumcenter = workspace.Circumcenter
local ball = workspace.Ball

RunService.Heartbeat:Connect(function()
	circumcenter.Position = Utilities:GetCircumcenter3D(part0.Position, part1.Position, part2.Position, part3.Position)
	ball.Position = circumcenter.Position
	ball.Size = 2 * Vector3.one * (ball.Position - part0.Position).Magnitude
end)

The original way which was even hackier and somehow slower

Click to show... 
local RunService = game:GetService("RunService")
local quad : {BasePart} = workspace.Quad:GetChildren()
local part0, part1, part2, part3 = quad[1], quad[2], quad[3], quad[4]

local function getRotation(cf: CFrame): string
	local _, __, __, r00, r01, r02, r10, r11, r12, r20, r21, r22 = cf:components()
	local str = string.format(string.rep("%.2f, ", 9), r00, r01, r02, r10, r11, r12, r20, r21, r22)
	str = string.gsub(str, "%-?%d+%.%d+, %-?%d+%.%d+, %-?%d+%.%d+, ", function(s)
		return s .. "\n"
	end)
	str = string.gsub(str, ",", "")
	return str
end

local function getTrace(matrix: CFrame)
	return matrix.XVector.X + matrix.YVector.Y + matrix.ZVector.Z
end

local function invertMatrix3D(matrix: CFrame): CFrame
	local squared = matrix * matrix
	local trace = getTrace(matrix)
	local diff = 0.5 * (trace^2 - getTrace(squared))
	local adjugate = CFrame.fromMatrix(
		Vector3.zero,
		Vector3.xAxis * diff - trace * matrix.XVector + squared.XVector,
		Vector3.yAxis * diff - trace * matrix.YVector + squared.YVector,
		Vector3.zAxis * diff - trace * matrix.ZVector + squared.ZVector
	)
	local det = matrix.XVector.X * adjugate.XVector.X
	det += matrix.YVector.X * adjugate.XVector.Y
	det += matrix.ZVector.X * adjugate.XVector.Z
	return CFrame.fromMatrix(
		Vector3.zero,
		adjugate.XVector / det,
		adjugate.YVector / det,
		adjugate.ZVector / det
	)
end

local function getCircumcenter3D(point0: Vector3, point1: Vector3, point2: Vector3, point3: Vector3): Vector3
	local matrix = CFrame.fromMatrix(
		Vector3.zero, -- fourth column
		2 * (point1 - point0), -- first column
		2 * (point2 - point0), -- second column
		2 * (point3 - point0) -- third column
	)
	local inverse = invertMatrix3D(matrix:Inverse()) -- :Inverse() transposes the matrix

	local dotProducts = Vector3.new(
		point1:Dot(point1),
		point2:Dot(point2),
		point3:Dot(point3)
	)
	local vector = dotProducts - point0:Dot(point0) * Vector3.one

	print("Matrix\n", getRotation(matrix))
	print("Inverse\n", getRotation(inverse))
	print("Vector", vector)
	return inverse * vector
end

local circumcenter = workspace.Circumcenter
local ball = workspace.Ball

RunService.Heartbeat:Connect(function()
	circumcenter.Position = circumcenter.Position:Lerp(getCircumcenter3D(part0.Position, part1.Position, part2.Position, part3.Position), 0.05)
	ball.Position = ball.Position:Lerp(circumcenter.Position, 0.05)
	ball.Size = ball.Size:Lerp(2 * Vector3.one * (ball.Position - part0.Position).Magnitude, 0.05)
end)

The 2D solution

I also wrote some (less optimized) code to solve for the circumcenter of a triangle (three points).

Click to show... 
local RunService = game:GetService("RunService")
local triangle: {BasePart} = workspace.Triangle:GetChildren()
local part0, part1, part2 = triangle[1], triangle[2], triangle[3]

local projectXZ = CFrame.fromMatrix(
	Vector3.zero,
	Vector3.xAxis,
	Vector3.zero,
	Vector3.yAxis
)
local permuteYZ = CFrame.fromMatrix(
	Vector3.zero,
	Vector3.xAxis,
	Vector3.zAxis,
	Vector3.yAxis
)

local function invertXYMatrix(matrix: CFrame)
	local matrixX, matrixY = matrix.XVector, matrix.YVector
	local a, b, c, d = matrixX.X, matrixY.X, matrixX.Y, matrixY.Y
	local det = a * d - b * c
	return CFrame.fromMatrix(
		Vector3.zero,
		Vector3.new(d, -c, 0) / det,
		Vector3.new(-b, a, 0) / det,
		Vector3.zero
	)
end

local function getCircumcenter2D(point0: Vector3, point1: Vector3, point2: Vector3)
	local projected = projectXZ * CFrame.fromMatrix(Vector3.zero, point0, point1, point2)
	local projX, projY, projZ = projected.XVector, projected.YVector, projected.ZVector

	local matrix = CFrame.fromMatrix(
		Vector3.zero, -- fourth column
		2 * (projY - projX), -- first column
		2 * (projZ - projX), -- second column
		Vector3.zero -- third column
	)
	local inverse = invertXYMatrix(matrix:Inverse())

	local dotX = projX:Dot(projX)
	local dotYZ = Vector3.new(
		projY:Dot(projY),
		projZ:Dot(projZ),
		dotX
	)
	local vector = dotYZ - dotX * Vector3.one

	return inverse * vector
end

local circumcenter = workspace.Circumcenter
RunService.Heartbeat:Connect(function()
	circumcenter.Position = permuteYZ * getCircumcenter2D(part0.Position, part1.Position, part2.Position) + Vector3.yAxis
end)

Let me know what you think! Especially if you have any ways it could be improved. :slight_smile:

12 Likes