Finding a circle from two points and a tangent in 3D

Very interesting math problem. However, why are you avoiding the projection method? it seems the simplest way to match the formulas which are only applicable for 2D space.

I’m probably going to do that, but would still like a direct solution to avoid the extra computation. Maybe it’s just as intensive to do the direct way though

1 Like

tangent cross (p2 - p1)
gives you a vector perpendicular to your circle (vert)

vert cross tangent points to your circle origin( or away from)

could conceivably ray cast for a point that delta p1 == delta p2

first jump checks to make sure you move closer to p2

These will provide your plane, origin and radius.

I’m sure some trig would help with the last step, Hmm.

1 Like

Not sure what you mean. What’s delta in this case?

Huh? Sorry, I’m really not understanding what you’re saying.

sorry, no dot was 2 crosses
delta is distance between

Great idea using cross product to find the plane normal vector.

Ill try writing down my math for the 3d method to the problem

Oh I see what you’re saying. Yes I’d found the dirs for the plane normal and tangent perpendicular already but they ended up not being super useful.

That last step is sort of what I’m asking about :slight_smile:

The angle between the perp and p2-p1 should relate to the arc but i dont know the math proof

Here you go, things to note if you go 3d the circle becomes a sphere:

This should leave you with 3 equations for the 3 unknowns for the center of the sphere/circle

Edit: Some notes on the math done
Primarily uses dot product logic where it checks if two vectors are perpendicular then the dot product is zero.
Then it just applies sphere geometry logic where:
radius vector = (origin of sphere to a point on the sphere)

  1. Radius vector is perpendicular to the tangent of the circle.

  2. Radius vector is also perpendicular to the normal vector of the plane for the sphere.

Since the unknown is a point that has three variables you will probably need to do Gaussian elimination with the three equations found and see if it works or not.

1 Like

tangent cross (p2-p1) = vert
vert cross tangent = line(p1-p0)

(p2-p1) cross vert gives line between p0 and midpoint of p1 and p2 (line(p3-p0))

(p2-p1)/2 + p1 = p3

intersect of line(p3-p0) and line(p1-p0) = p0

Cool approach! I’ll see if I can solve it tomorrow.

Edit @dthecoolest

Actually wait (1) and (3) are colinear, this system is unsolveable sadly :frowning:

Edit 2: maybe we can replace it with the bisector of p1 and p2? ((p1+p2)/2 - c):Dot(n) = 0 or something idk will pick up tomorrow that’s colinear too but we could maybe instead do like ((p1+p2)/2 - c):Dot(p2-p1) = 0

Ooof, I just noticed that however we are given that the origin point is on the plane so maybe we can subsitute the plane equation into equation 3

Edit: third equation is the equation for plane p

I feel close. Here’s where I’m at:

GetCircle
-- given two points on a circle and a tangent to p1, returns the center of
-- the circle.
-- returns: success, center
local function GetCenter(p1: Vector3, tangent: Vector3, p2: Vector3): (boolean, Vector3)
	local diff = p2 - p1
	local norm = diff:Cross(tangent)
	local len = norm.Magnitude
	local avg = p1:Lerp(p2, 0.5) -- faster than (p1 + p2)/2
	
	if len < 0.001 then
		-- basically straight line
		return false, avg
	end
	
	norm /= len
	
	-- must solve these three equations where c = the center of the circle
	--[[
	(1) (p1 - c):Dot(tangent) = 0	<-- c->p1 must be perpendicular to the tangent 
	(2) (p2 - c):Dot(norm) = 0		<-- c->p2 must be perpendicular to the normal
	(3) (avg - c):Dot(diff) = 0		<-- c->avg must be perpendicular to p1->p2 (perpendicular bisector)
	
	so
	
	A c = B
	
	where
	
	A = {
		{tangent.X, tangent.Y, tangent.Z),
		{norm.X, norm.Y, norm.Z),
		(diff.X, diff.Y, diff.Z)
	}
	
	and
	
	B = {
		{p1:Dot(tangent)},
		{p2:Dot(norm)},
		{avg:Dot(diff)}
	}
	]]
	
	-- using cframes to solve the system:
	local transform = CFrame.new(
		0, 0, 0, -- just care about the rotation matrix
		tangent.X, tangent.Y, tangent.Z, 	-- (1)
		norm.X, norm.Y, norm.Z,				-- (2)
		diff.X, diff.Y, diff.Z				-- (3)
	):Inverse()
	
	local vec = Vector3.new(
		p1:Dot(tangent),
		p2:Dot(norm),
		avg:Dot(diff)
	)
	
	return true, transform*vec
end

And if you want to try to test it you can throw this in a script and move the balls around:

Test Script

local function CreateBall(name, color, pos, shape)
shape = shape or Enum.PartType.Ball
local ball = Instance.new(“Part”)
ball.Name = name
ball.Shape = shape
ball.Massless = true
ball.Anchored = true
ball.BrickColor = color
ball.Size = Vector3.new(3, 3, 3)
ball.Position = pos
ball.Parent = workspace
return ball
end

local circlePart = CreateBall(“Circle”, BrickColor.new(“White”), Vector3.new(), Enum.PartType.Cylinder)
local originPart = CreateBall(“Origin”, BrickColor.new(“Really red”), Vector3.new(0, 0, 0)) – p1
local tangentPart = CreateBall(“Tangent”, BrickColor.new(“Bright yellow”), Vector3.new(0, 10, 10)) – tangent dir relative to p1
local targetPart = CreateBall(“Target”, BrickColor.new(“Bright green”), Vector3.new(10, 10, 0)) – p2

– given two points on a circle and a tangent to p1, returns the center of
– the circle.
– returns: success, center
local function GetCenter(p1: Vector3, tangent: Vector3, p2: Vector3): (boolean, Vector3)
local diff = p2 - p1
local norm = diff:Cross(tangent)
local len = norm.Magnitude
local avg = p1:Lerp(p2, 0.5) – faster than (p1 + p2)/2

if len < 0.001 then
	-- basically straight line
	return false, avg
end

norm /= len

-- must solve these three equations where c = the center of the circle
--[[
(1) (p1 - c):Dot(tangent) = 0	<-- c->p1 must be perpendicular to the tangent 
(2) (p2 - c):Dot(norm) = 0		<-- c->p2 must be perpendicular to the normal
(3) (avg - c):Dot(diff) = 0		<-- c->avg must be perpendicular to p1->p2 (perpendicular bisector)

so

A c = B

where

A = {
	{tangent.X, tangent.Y, tangent.Z),
	{norm.X, norm.Y, norm.Z),
	(diff.X, diff.Y, diff.Z)
}

and

B = {
	{p1:Dot(tangent)},
	{p2:Dot(norm)},
	{avg:Dot(diff)}
}
]]

-- using cframes to solve the system:
local transform = CFrame.new(
	0, 0, 0, -- just care about the rotation matrix
	tangent.X, tangent.Y, tangent.Z, 	-- (1)
	norm.X, norm.Y, norm.Z,				-- (2)
	diff.X, diff.Y, diff.Z				-- (3)
):Inverse()

local vec = Vector3.new(
	p1:Dot(tangent),
	p2:Dot(norm),
	avg:Dot(diff)
)

return true, transform*vec

end

– given a point on a circle, a tangent, and a center, stretches a given Cylinder Part to match that circle
– note: (point-center) and tangent must be orthogonal
local function RenderCircle(part, point, tangent, center)
local diff = point - center
local radius = diff.Magnitude
local radius2 = radius*2
local forward = diff / radius;
local right = forward:Cross(tangent)

circlePart.Size = Vector3.new(1, radius2, radius2)
circlePart.CFrame = CFrame.fromMatrix(
	center,
	right,
	tangent,
	-forward
)

end

game:GetService(“RunService”).Heartbeat:Connect(function()
local origin = originPart.Position
local tangentDir = (tangentPart.Position - origin).Unit
local target = targetPart.Position

local straight, center = GetCenter(origin, tangentDir, target)	

RenderCircle(circlePart, origin, tangentDir, center)

end)

It’s not quite working, though. The circle is aligned to the right plane at least, but the size and center are wayyyy off.

Current theory is that that matrix is still singular. I’ll need to figure that out, though.

1 Like

norm as an intermediate variable is sort of throwing me off. I feel like it’s unnecessary somehow, since it’s just a combination of tangent and p2-p1.

Edit: actually maybe it’s fine I don’t think (2) is a linear combination of either of the others

Got it. To display I have 4 balls (p0,p1,p2,t0) as initial values and an origin marker for solution.

Find Circle Repro
--start points
local origin = script.Parent:FindFirstChild("p0")
local p1 = script.Parent:FindFirstChild("p1").Position
local p2 = script.Parent:FindFirstChild("p2").Position
local t0 = script.Parent:FindFirstChild("t0").Position

--lines
local t1 = (t0-p1)
local arc1 = p2-p1
local vert = t1:Cross(arc1)
local r1 = t1:Cross(vert)

--redefine space using circle plane as XY and p1 as origin
local radius1 = CFrame.fromMatrix(p1,t1.Unit,r1.Unit)
--p1 is now (0,0,0)

--fine obj space equivalent of points
t1 = radius1:VectorToObjectSpace(t1)
p2 = radius1:PointToObjectSpace(p2)
local p3 = p2/2 -- it is (p2-p1)/2 but p1 is origin

-- p1 and p2 are equal distant from origin, midpoint(p3)-> origin is perp to p1->p2

local r2 = p3:Cross(Vector3.new(0,0,1))
--second radial, first is your Y axis

--find slope of r2 and solve for b in Y=mX+b. aka y-intercept
local slope = r2.Y/r2.X
p0y = p3.Y-(slope*p3.X) --y intercept


local originInObjSpace = Vector3.new(0,p0y,0)
local originInWorld = radius1:PointToWorldSpace(originInObjSpace)

origin.Position = originInWorld

This solution uses CFrame methods to turn a 3D problem into a 2D problem. This (just below) uses geometry (Trig) to directly solve the problem.

2 Likes

Cool solution :slight_smile: I’m gonna keep trying to find a direct solution but I’ll mark this as the answer!

Made it a function:

local function GetCenter(p1, t0, p2)
	--lines
	local t1 = (t0-p1)
	local arc1 = p2-p1
	local vert = t1:Cross(arc1)
	local r1 = t1:Cross(vert)
	
	--redefine space using circle plane as XY and p1 as origin
	local radius1 = CFrame.fromMatrix(p1,t1.Unit,r1.Unit)
	--p1 is now (0,0,0)
	
	--fine obj space equivalent of points
	local transform = radius1:Inverse()
	t1 = transform*t1
	p2 = transform*p2
	local p3 = p2/2 -- it is (p2-p1)/2 but p1 is origin
	
	-- p1 and p2 are equal distant from origin, midpoint(p3)-> origin is perp to p1->p2
	
	local r2 = p3:Cross(Vector3.new(0,0,1))
	--second radial, first is your Y axis
	
	--find slope of r2 and solve for b in Y=mX+b. aka y-intercept
	local slope = r2.Y/r2.X
	local p0y = p3.Y-(slope*p3.X) --y intercept
	
	
	local originInObjSpace = Vector3.new(0,p0y,0)
	local originInWorld = radius1*originInObjSpace
	
	return originInWorld
end

I made a math.stackexchange question here: linear algebra - Finding circle in 3D space from two points and a tangent from one of the points - Mathematics Stack Exchange

My implementation still doesn't work for some reason though

-- given two points on a circle and a tangent to p1, returns the center of
-- the circle.
-- returns: success, center
local function GetCenter(p1: Vector3, tangent: Vector3, p2: Vector3): (boolean, Vector3)
	DrawVector("Tangent", p1, tangent*5, BrickColor.new("Bright yellow"))
	local diff = p2 - p1
	DrawVector("Diff", p1, (p2-p1), BrickColor.White())
	local norm = diff:Cross(tangent)
	DrawVector("Normal", p1, norm, BrickColor.Red())
	local len = norm.Magnitude
	local avg = p1:Lerp(p2, 0.5) -- faster than (p1 + p2)/2
	
	if len < 0.001 then
		-- basically straight line
		return false, avg
	end
	
	-- using cframes to solve the system:
	local transform = CFrame.new(
		0, 0, 0, -- just care about the rotation matrix
		tangent.X, tangent.Y, tangent.Z, 	-- (1)
		norm.X, norm.Y, norm.Z,				-- (2)
		diff.X, diff.Y, diff.Z				-- (3)
	):Inverse()
	
	local vec = Vector3.new(
		p1:Dot(tangent),
		p1:Dot(norm),
		avg:Dot(diff)
	)
	
	return true, transform*vec
end

This uses my original thought of angle between tangent and arc to find the center.
A simpler method

Code
--start points
local origin = script.Parent:FindFirstChild("p0")
local p1 = script.Parent:FindFirstChild("p1").Position
local p2 = script.Parent:FindFirstChild("p2").Position
local t0 = script.Parent:FindFirstChild("t0").Position

--lines
local t1 = t0-p1
local arc1 = p2-p1
local vert = t1:Cross(arc1)
local r1 = -t1:Cross(vert)

local theta = arc1.Unit:Dot(t1.Unit)
theta = math.acos(theta)

radius = (arc1.Magnitude/2)/math.sin(theta)

origin.Position = p1+radius*r1.Unit
Edit: Picture and Explanation :slight_smile:

circlePic
Given: p1, p2, t0
(t1 the line is given in the OP but I made it a point so I can just move the block around to test)
arc1 is straight forward, it is the line between our two points.
origin is the point we need to find.

What we can know:
p1 and p2 are equidistant to origin, because it is a circle.
r1, arc1 and r2(line from p2-origin) make an isosceles triangle.
The midpoint between p1 and p2 therefore makes a nice right triangle with p1 and origin.
t1 makes a right angle with r1

Solving:
Getting the axis for r1 is simple with the built-in :Cross functions (right hand rule)
t1:Cross(arc1) gives a line(vert) that goes perpendicular to the drawing of our circle.
It is the axis perpendicular to the plane shared by the two lines.
So t1:cross(vert) gives us the line that is perpendicular to tangent and goes through our circle.

theta is the angle between arc1 and t1 and is congruent to the angle between 1. our radius and 2. the line from the origin to the middle of arc1.
A triangle’s angles add up to be 180, we know one is 90. So theta = 90 - (angle r1|arc1) which is conveniently the same as t1|arc1 since t1|r1 is a right angle

Sin gives use the ratio of the opposite side of the triangle over the hypotenuse
sin(theta) = 0.5arc1 / r1
r1 = 0.5arc1 / sin(theta)

so we now have direction, magnitude and a starting point.
From p1 go radius distance in direction r1.

1 Like

I definitely like that one better :slight_smile: I’ll benchmark them later!

I believe this is the direct method you were looking for, but it’s a lot harder than just projecting vectors. Here it is anyway. Consider this:

Center of circle given two pointsa and a tangent

  • Point A is the first point.
  • Point B is the second point
  • Vector ℓ is the tangent vector of the sphere at point A.
  • The red vector is the normal vector of the sphere at the tangent point.
  • The green point is the midpoint between A and B.
  • The green vector is the vector pointing from the tangent line to the midpoint of A and B and extending to the center of the circle.
  • The black point at the center is the center of the sphere.

In order to get the center of the sphere, you need to find the intersection between the red vector (normal vector) and the green vector (midpoint vector). In code, this looks like this:

local function GetCenter(p1, p2, t)
	local m = (p2 + p1) * 0.5; -- midpoint between p1 and p2
	local d = (p2 - p1).Magnitude -- distance between p1 and p2
	local s = (p2 - p1).Unit; -- the vector going from p1 to p2
	local v = t:Cross(s).Unit; -- a vector used to get the normal vector at the tangent point

	local n = t:Cross(v).Unit; -- normal vector at the tangent point

	local a = s:Cross(n).Unit; -- a vector orthogonal to the normal vector and midvector used to get the vector perpendicular to the mid vector
	local b = s:Cross(a).Unit; -- the vector perpendicular to the midvector

	local center = GetIntersection(p1, -n, m, b); -- the center of the sphere is at the intersection of these two vectors
	local radius = (center - p1).Magnitude; -- the radius of the sphere

	return center, radius;
end

If you’re interested in the intersection function I used, I’ll add it here as well.

local Huge = 10000000000000000000;

--[[ an intersection function i found here in the dev forum that i editted to give
a y coordinate, props to @PlaasBoer]]
local function GetIntersection(startPoint1, dir1, startPoint2, dir2)
	local endPoint1 = startPoint1 + dir1 * Huge;
	local endPoint2 = startPoint2 + dir2 * Huge;

	local point_1_x1 = startPoint1.X;
	local point_1_y1 = startPoint1.Z;
	local point_1_x2 = endPoint1.X;
	local point_1_y2 = endPoint1.Z;
	local point_2_x1 = startPoint2.X;
	local point_2_y1 = startPoint2.Z;
	local point_2_x2 = endPoint2.X;
	local point_2_y2 = endPoint2.Z;
	-- m = (y1 - y2) / (x1 - x2)
	local line_1_m = 0;
	local line_2_m = 0;
	-- b = -(mx1) + y1
	local line_1_b = 0;
	local line_2_b = 0;
	local intersect_x = 0;
	local intersect_z = 0;
	local isLineOneVertical = ((point_1_x1 / point_1_x2) % 2) == 1;
	local isLineTwoVertical = ((point_2_x1 / point_2_x2) % 2) == 1;
	if isLineOneVertical and isLineTwoVertical then
		error("There is no cross point, both vertical");
	end
	-- Line 1
	if isLineOneVertical then
		line_2_m = (point_2_y1 - point_2_y2) / (point_2_x1 - point_2_x2);
		line_2_b = -(line_2_m * point_2_x1) + point_2_y1;
		intersect_x = point_1_x1;
		intersect_z = (line_2_m * intersect_x) + line_2_b;
		-- Line 2
	elseif isLineTwoVertical then
		line_1_m = (point_1_y1 - point_1_y2) / (point_1_x1 - point_1_x2);
		line_1_b = -(line_1_m * point_1_x1) + point_1_y1;
		intersect_x = point_2_x1;
		intersect_z = (line_1_m * intersect_x) + line_1_b;
	else
		line_1_m = (point_1_y1 - point_1_y2) / (point_1_x1 - point_1_x2);
		line_2_m = (point_2_y1 - point_2_y2) / (point_2_x1 - point_2_x2);

		if line_1_m == line_2_m then
			error("There is no cross point, both same slope")
		end
		line_1_b = -(line_1_m * point_1_x1) + point_1_y1;
		line_2_b = -(line_2_m * point_2_x1) + point_2_y1;
		intersect_x = (line_2_b - line_1_b) / (line_1_m - line_2_m);
		intersect_z = (line_1_m * intersect_x) + line_1_b;

	end

	local u = (intersect_x - point_1_x1) / dir1.X
	return Vector3.new(intersect_x, startPoint1.Y + dir1.Y * u, intersect_z);
end

Testing this in game results in a very nice looking sphere manipulation show. I added the multiple vectors that are created by the code.

Watch the sphere manipulation show here

I know this thread is old, but I couldn’t help but offer this solution!

2 Likes