Point where a line segment intersects a sphere?

Discussions about Coding and Scripting
ExpEM
Skilled
Posts: 172
Joined: Wed Nov 09, 2016 1:48 am

Point where a line segment intersects a sphere?

Post by ExpEM » Fri Nov 27, 2020 11:03 am

Can anyone please help me out with this please?

Code: Select all

(Global) Var Vector Intersect1, Intersect2;

Function Int FindSphereIntersection(Vector LineStart, Vector LineEnd, Vector SphereOrigin, Float SphereRadius)
{
	//Math, math, math.
	//Math, math, math.
	//Math, math, math.
	
	if (Line from LineStart to LineEnd doesn't intersect with Sphere)
		Return 0;
		
	if (Line from LineStart to LineEnd intersects with Sphere once)
	{
		Intersect1 = Intersect point;
		Return 1;
	}
	
	if (Line from LineStart to LineEnd intersects with Sphere twice)
	{
		Intersect1 = Intersect point;
		Intersect1 = Other intersect point;
		Return 2;
	}
}
This sort of math is beyond my understanding unfortunately so any help would be appreciated thanks.

User avatar
Barbie
Godlike
Posts: 2069
Joined: Fri Sep 25, 2015 9:01 pm
Location: moved without proper hashing

Re: Point where a line segment intersects a sphere?

Post by Barbie » Fri Nov 27, 2020 3:49 pm

Just to understand the problem: you are looking for the "Points of Interest" as shown in the pic?
You do not have the required permissions to view the files attached to this post.
"Multiple exclamation marks," he went on, shaking his head, "are a sure sign of a diseased mind." --Terry Pratchett

ExpEM
Skilled
Posts: 172
Joined: Wed Nov 09, 2016 1:48 am

Re: Point where a line segment intersects a sphere?

Post by ExpEM » Fri Nov 27, 2020 6:41 pm

Barbie wrote:
Fri Nov 27, 2020 3:49 pm
Just to understand the problem: you are looking for the "Points of Interest" as shown in the pic?
Yep, that's what I'm after.

User avatar
Zero_khan
Average
Posts: 31
Joined: Tue Nov 24, 2020 6:54 pm

Re: Point where a line segment intersects a sphere?

Post by Zero_khan » Fri Nov 27, 2020 6:56 pm

This is analytic geometry. Equation of a line, equation of a circle. Solve the linear system.

You either solve it yourself. Or use an already existing function that does it.
Good Bye. I'm leaving UT99 behind. I won't be around for UT's 30th.

User avatar
sektor2111
Godlike
Posts: 5209
Joined: Sun May 09, 2010 6:15 pm
Location: On the roof.

Re: Point where a line segment intersects a sphere?

Post by sektor2111 » Fri Nov 27, 2020 8:23 pm

I'm not sure if this is a function INT, here we are talking about TWO vectors.
In my simple way I would trace two directions Start End End Start and figuring HitLocation(s) if I'm not mistaking.

In other hand perhaps what you want might be doable other way, some more other details would be more useful about purpose of this stuff.

ExpEM
Skilled
Posts: 172
Joined: Wed Nov 09, 2016 1:48 am

Re: Point where a line segment intersects a sphere?

Post by ExpEM » Sat Nov 28, 2020 12:28 am

sektor2111 wrote:
Fri Nov 27, 2020 8:23 pm
I'm not sure if this is a function INT, here we are talking about TWO vectors.
In my simple way I would trace two directions Start End End Start and figuring HitLocation(s) if I'm not mistaking.

In other hand perhaps what you want might be doable other way, some more other details would be more useful about purpose of this stuff.
The Function sets two global Vectors, Int is returned to indicate how many were found.

User avatar
Feralidragon
Godlike
Posts: 5300
Joined: Wed Feb 27, 2008 6:24 pm
Personal rank: Work In Progress
Location: Liandri

Re: Point where a line segment intersects a sphere?

Post by Feralidragon » Sat Nov 28, 2020 2:56 am

Usually there is more than one way to solve the same mathematical problem, and generally the best way to solve a problem is solve it in the simplest fashion with the tools you have already available.

I looked at this, and it got me thinking how you can do this, and you don't need to mess around with solving equations (it wouldn't help you much in this case either), instead this is what I came up with:
circle-line-intersection-01.png
(this may appear blurry in some browsers, I don't know why, but should still be perceptible)

The above is my process of solving this particular problem, represented visually.
Here I used a 2D circle and a 2D line, but the same applies in the exact same way for 3D, so I am just using 2D to make the explanation easier to understand.

We have the circle (your sphere) with point A as its center, and we have the line intersecting the circle between the points C and D, and this line happens to intersect the circle at points E and F.
And the key point you actually need to solve this is actually another point, the point G.

The first thing to note about this point G is that, for any given line of infinite length (imagine that C and D are just 2 points in an infinitely long line), this point is what tells you whether or not the line intersects or touches the circle at all.
Basically, if the distance between A and G is equal or shorter than the radius of the circle, then the line is intersecting the circle (either at 1 or 2 points), otherwise it isn't.

The second thing to note about this point G is that it sits exactly in the middle between E and F, meaning that the distances E to G and G to F are exactly the same, and also at this point the line CD is perpendicular to AG (the lines between C and D, and A and G, respectively, and will use this short form from here on to identify which line I am talking about), hence the green square indicating a 90º angle.

With this you have all the required ingredients to be able to solve this by using fairly straightforward trigonometry: you know points A, C and D (blue points), and from here you just have to solve for points G, E and F (the gray points, in this order).

So, first, you have to find out G, and here you will notice that due to all the aforementioned properties of this point that you have a right-angle triangle formed by the points C, G and A (or simply CGA), where you know the values of C and A already.

This means that you can find G by calculating the distance of AC, and also the angle ACG, or rather its cosine, which you can get by using the dot product between the normal of vectors of CA and CD, to then calculate the vector CG, as follows:

Code: Select all

CA_Distance = VSize(A - C);
CA_Normal = Normal(A - C);
CD_Normal = Normal(D - C);
ACG_Angle = CA_Normal dot CD_Normal;
CG = CD_Normal * CA_Distance * ACG_Angle;
and from here you can find G:

Code: Select all

G = C + CG;
And at this point you already know if the line (at infinite length) intersects the circle or not, and at how many points:

Code: Select all

GA_Distance = VSize(A - G);
if (GA_Distance < Radius) {
    //intersects at 2 points
} else if (GA_Distance == Radius) {
    //intersects at 1 point
} else {
    //does not intersect at any point
}
Now that you know G, and as long as it's inside the circle, you can then now find E and F.
Of course, if the intersection is at 1 point only, then E and F are one and the same: G itself.

As you may notice, by finding G you end up having another right-angle triangle (with the purple line), the triangle EGA, except that now in order to find E, you need to find the distance GE, so you can then use that to go up in the line and find the point you want.

At this point we not only know the points G and A of that triangle, but we also actually know the distance between E and A already, which matches the radius of the circle, since that's what an intersection point is all about: a point which resides at the edge (radius) of the circle.
Therefore that means that we know 2 sides of the right-angle triangle, and we have just have to find out the 3rd by using the basic Pythagorean theorem:

Code: Select all

EA_Distance = Radius;
GA_Distance = VSize(A - G);
GE_Distance = Sqrt(Square(EA_Distance) - Square(GA_Distance));
and from there you can then find E very easily:

Code: Select all

E = G - GE_Distance * CD_Normal;
and since G sits right between E and F, then EG and GF have the exact same distance, so you can find F immediately as well:

Code: Select all

GF_Distance = GE_Distance;
F = G + GF_Distance * CD_Normal;
and you're done. :mrgreen:


... except that you aren't quite yet. :sad2:

Remember, this was all about a line with infinite length, but the length of your line is finite, because you have set those two points C and D at specific locations, and that's what your line actually is, so you have to consider additional scenarios, such as:
circle-line-intersection-02.png

as well as other variations of the same situation, where the line may actually not intersect at some points, or at any at all, if the line is completely inside the circle, or even completely outside, such as:
circle-line-intersection-03.png

For this you can simply check where the E and F points are in relation to both C and D, and reject E or/and F depending on whether or not they are outside the CD line (and decrement the number of intersected points accordingly), by checking their distances to each point:

Code: Select all

CD_Distance = VSize(D - C);

EC_Distance = VSize(C - E);
ED_Distance = VSize(D - E);
if (EC_Distance > CD_Distance || ED_Distance > CD_Distance) {
    //then E is not a valid intersection point (decrement intersected points by one, and reject E)
}

FC_Distance = VSize(C - F);
FD_Distance = VSize(D - F);
if (FC_Distance > CD_Distance || FD_Distance > CD_Distance) {
    //then F is not a valid intersection point (decrement intersected points by one, and reject F)
}
and now you're really done. :tu:


Having that said, I am not sure if I made any mistakes or missed anything here (it's almost 2:00AM here, going to sleep after this, and my math on this type of thing is quite rusty on top of it), but I think it should all check out and work exactly like you want for you (will likely proof-read tomorrow with a clear head and edit any mistake or typo I may have made).

Furthermore, all this code can be optimized of course, I only broke it down so that each step is as clear as possible, for you and everyone understand what's going on there.
You do not have the required permissions to view the files attached to this post.

kmar
Novice
Posts: 16
Joined: Sat Jan 25, 2020 12:18 pm
Location: Czech Republic

Re: Point where a line segment intersects a sphere?

Post by kmar » Sat Nov 28, 2020 8:49 am

first, turn your linestart/lineend into ray origin and direction
then, offset ray origin so that it's relative to sphere origin and then you'll simply compute a raycast to a sphere at origin (0,0,0):
ray_direction = lineend - linestart
ray_origin = linestart - sphere_origin

now let's substitute the letters a bit:
r = sphere radius
o = ray_origin
d = ray_direction

now we have this (.=dot product):
(o + t*d)^2 = r^2;
o^2 + 2*t*(o.d) +t^2*d^2 - r^2 = 0

factoring:
t^2: d.d
t^1: 2*o.d
t^0: o.o - r*r

this gives us a,b and c, input to quadratic equation solver:
a = dot(d, d)
b = 2*dot(o, d)
c = dot(o, o) - r*r

solving quadratic equation (a,b,c):

a2 = 2*a
if (a2 == 0) => no solution
D = b*b-4*a*c
D < 0 => no solution
D = sqrt(D);
t1 = (-b + D)/a2;
t2 = (-b - D)/a2;
if (t1 > t2)
swap t1 and t2 (so that t1 is always smaller, for conveniece)

so after solving the equation we have t1 and t2 (time of impact along ray direction)

so the points on the sphere are linestart + ray_direction*t1 and linestart + ray_direction*t2

bear in mind that the ts can be negative, because this solves the hit for inifite ray, so you may want to do t1=max(0, t1) and t2=min(t2, 1) only accept the solution if t2>=t1

ExpEM
Skilled
Posts: 172
Joined: Wed Nov 09, 2016 1:48 am

Re: Point where a line segment intersects a sphere?

Post by ExpEM » Sat Nov 28, 2020 9:48 am

Thank you all for your help, especially you Feralidragon great explanation (dumbed down enough for me to read too).

This is the working function (partially tested at this point).

Code: Select all

Function Int FindSphereIntersection(Vector LineStart, Vector LineEnd, Vector SphereOrigin, Float SphereRadius, Out Vector Intersection1, Out Vector Intersection2)
{
// Key:
// A = SphereOrigin.
// C = LineStart.
// D = LineEnd.
// E,F = Intersection1,2.
// G = Median.

	//Block 1.
	Local float CA_Dist, ACG_Angle;
	Local vector CA_Normal, CD_Normal, CG;
	//Block 2.
	Local vector Median;
	//Block 3.
	Local float GA_Dist;
	//Block 4.
	Local float EA_Dist, GE_Dist;
	//Block 6.
	Local float GF_Dist;
	//Block 7.
	Local float CD_Dist, EC_Dist, ED_Dist, FC_Dist, FD_Dist;
	Local bool Reject1, Reject2;

//===================================
	//Check infinite line.
//===================================

	//Block 1.
	CA_Dist = vSize(SphereOrigin - LineStart);
	CA_Normal = Normal(SphereOrigin - LineStart);
	CD_Normal = Normal(LineEnd - LineStart);
	ACG_Angle = CA_Normal dot CD_Normal;
	CG = CD_Normal * CA_Dist * ACG_Angle;

	//Block 2.
	Median = LineStart + CG;

	//Block 3.
	GA_Dist = vSize(SphereOrigin - Median);
	if (GA_Dist > SphereRadius)
	{
		Log("Infinite line rejected");
		Return -1; //Infinite line does not hit Sphere.
	}

	//Block 4.
	EA_Dist = SphereRadius;
	GA_Dist = vSize(SphereOrigin - Median);
	GE_Dist = Sqrt(Square(EA_Dist) - Square(GA_Dist));

	//Block 5.
	Intersection1 = Median - GE_Dist * CD_Normal;

	//Block 6.
	GF_Dist = GE_Dist;
	Intersection2 = GF_Dist * CD_Normal;

//===================================
	//Check finite line.
//===================================

	//Block 7.
	CD_Dist = vSize(LineEnd - LineStart);

	EC_Dist = vSize(LineStart - Intersection1);
	ED_Dist = vSize(LineEnd - Intersection1);
	Reject1 = EC_Dist > CD_Dist || ED_Dist > CD_Dist;

	FC_Dist = vSize(LineStart - Intersection2);
	FD_Dist = vSize(LineEnd - Intersection2);
	Reject2 = FC_Dist > CD_Dist || FD_Dist > CD_Dist;

	if (Reject1 && Reject2)
	{
		Log("Both rejected");
		Return 0;
	}
	else if (Reject1 && !Reject2)
	{
		Log("Rejected #1");
		Intersection1 = Intersection2;
		Return 1;
	}
	else if (!Reject1 && Reject2)
	{
		Log("Rejected #2");
		Return 1;
	}
	else
	{
		Log("No rejection");
		Return 2;
	}
}
I haven't optimised it much, it's almost line for line what Feralidragon wrote. Notes are left in for others to follow along with the pictures.

kmar
Novice
Posts: 16
Joined: Sat Jan 25, 2020 12:18 pm
Location: Czech Republic

Re: Point where a line segment intersects a sphere?

Post by kmar » Sat Nov 28, 2020 10:55 am

just for completeness, here's my version translated to UnrealScript:

Code: Select all

function int SolveQuadraticEquation(float a, float b, float c, out float t1, out float t2)
{
	local float a2, D, tmp;

	a2 = 2.0*a;

	// this condition can be omitted if LineStart != LineEnd
	if (a2 == 0.0)
		return 0;

	D = b*b - 4.0*a*c;

	if (D < 0.0)
		return 0;

	D = sqrt(D);

	t1 = (-b + D)/a2;
	t2 = (-b - D)/a2;

	if (t1 > t2)
	{
		tmp = t1;
		t1 = t2;
		t2 = tmp;
	}

	if (t1 == t2)
		return 1;

	return 2;
}

function int FindSphereIntersection(Vector LineStart, Vector LineEnd, Vector SphereOrigin, Float SphereRadius, Out Vector Intersection1, Out Vector Intersection2)
{
	local vector o, d;
	local float r, a, b, c, t1, t2;
	local int res;

	o = LineStart - SphereOrigin;
	d = LineEnd - LineStart;
	r = SphereRadius;

	a = d dot d;
	b = 2.0*(o dot d);
	c = (o dot o) - r*r;

	res = SolveQuadraticEquation(a, b, c, t1, t2);

	if (res == 0)
		return 0;

	t1 = FMax(t1, 0.0);
	t2 = FMin(t2, 1.0);

	if (t2 < t1)
		return 0;

	// this condition can be omitted if you want to return LineStart as the first intersection point if LineStart is inside the sphere
	if (c < 0.0)
	{
		// special case: ray starts inside the sphere
		Intersection1 = LineStart + d*t2;
		return 1;
	}

	Intersection1 = LineStart + d*t1;
	Intersection2 = LineStart + d*t2;

	return res;
}
EDIT: you seem to have a bug in block 6 in your code, should be Intersection2 = Median + GF_Dist * CD_Normal

ExpEM
Skilled
Posts: 172
Joined: Wed Nov 09, 2016 1:48 am

Re: Point where a line segment intersects a sphere?

Post by ExpEM » Sat Nov 28, 2020 2:04 pm

kmar wrote:
Sat Nov 28, 2020 10:55 am
just for completeness, here's my version translated to UnrealScript:
Thank you, I have no idea who's code executes faster but Feralidragon got in first and it works in this case.
kmar wrote:
Sat Nov 28, 2020 10:55 am
EDIT: you seem to have a bug in block 6 in your code, should be Intersection2 = Median + GF_Dist * CD_Normal
Well done on spotting that, I fixed it in my code and it broke everything :facepalm: so I guess i'll leave my code wrong as it's working... :noidea
I have however added a note into the code pointing it out.

Code: Select all

	//Block 6.
	GF_Dist = GE_Dist; //This var can be stripped.
	Intersection2 = /*Median + */GF_Dist * CD_Normal; //Commented part is for correct code but when I fixed it everything broke... Noted by kmar (UT99.org).
I will probably come back and fix this at a later date.

kmar
Novice
Posts: 16
Joined: Sat Jan 25, 2020 12:18 pm
Location: Czech Republic

Re: Point where a line segment intersects a sphere?

Post by kmar » Sat Nov 28, 2020 3:01 pm

ExpEM wrote:
Sat Nov 28, 2020 2:04 pm
Thank you, I have no idea who's code executes faster but Feralidragon got in first and it works in this case.
sure, no problem.
my analytic solution should be faster. also it doesn't break in the extreme case where LineStart == SphereOrigin (even though that's most likely not your use case, assuming you want to raycast outside of the sphere)
ExpEM wrote:
Sat Nov 28, 2020 2:04 pm
Well done on spotting that, I fixed it in my code and it broke everything :facepalm: so I guess i'll leave my code wrong as it's working... :noidea
how is that possible?

let's say LineStart = vect(0, 0, 0), LineEnd = vect(0, 0, 100), SphereOrigin = vect(0, 0, 30) and SphereRadius = 10
without the fix, you get the intersection points {0, 0, 20} and {0, 0, 10}, which is clearly wrong. the corrent answer is {0, 0, 20} and {0, 0, 40}

ExpEM
Skilled
Posts: 172
Joined: Wed Nov 09, 2016 1:48 am

Re: Point where a line segment intersects a sphere?

Post by ExpEM » Sat Nov 28, 2020 3:13 pm

kmar wrote:
Sat Nov 28, 2020 3:01 pm
how is that possible?
I wrote this function:

Code: Select all

NOTE: This is called on Tick.

function UpdateBody()
{
	Local int I;
	Local rotator tRot;
	Local float vScale;
	Local vector vLocation, vDebug;
	Local vector SphereOrigin;
	Local vector Intersection1, Intersection2;
	Local int Result;
	Local int LastSegment;

	//Move Body parts here.

	//Move Head.
	vScale = vSize(CompassPoints[0] - CompassPoints[1]) - vSize(CompassPoints[0] - Location);
	vLocation = UnCompassPoints[1] + Vector(Rotator(UnCompassPoints[0] - UnCompassPoints[1])) * vScale;
	DrawDebugSphere(vLocation, 2, 4, Red);
	vDebug = vLocation;
	vDebug.z = location.z;
	DrawDebugLine(vLocation, vDebug, Red);

	TestBody[0].SetLocation(vLocation);

	//Move Tail parts.
	LastSegment = 1;
	for (I=1; I<50; I++)
	{
		SphereOrigin = TestBody[I-1].Location;

		While (FindSphereIntersection(UnCompassPoints[LastSegment+1], UnCompassPoints[LastSegment], SphereOrigin, SDist, Intersection1, Intersection2) < 1)
		{
			LastSegment++;
			Assert(LastSegment < 64); //Testing.
		}

//		DrawDebugLine(Vect(0,0,0),Intersection1, Green);
//		DrawDebugSphere(Intersection1, 2, 4, Green);

		TestBody[I].SetLocation(Intersection1);
	}

	//Fix rotation of Tail parts.
	for (I=49; I>0; I--)
		TestBody[I].SetRotation(Rotator(TestBody[I-1].Location - TestBody[I].Location));

	//Handle "Head" Seperatly here.
	tRot = Rotator(TestBody[0].Location - TestBody[1].Location); //Ghey... FixMe! //Don't notice at AirSpeed = 400.
	TestBody[0].SetRotation(tRot);
}
Specificly:

Code: Select all

	//Move Tail parts.
	LastSegment = 1;
	for (I=1; I<50; I++)
	{
		SphereOrigin = TestBody[I-1].Location;

		While (FindSphereIntersection(UnCompassPoints[LastSegment+1], UnCompassPoints[LastSegment], SphereOrigin, SDist, Intersection1, Intersection2) < 1)
		{
			LastSegment++;
			Assert(LastSegment < 64); //Testing.
		}

//		DrawDebugLine(Vect(0,0,0),Intersection1, Green);
//		DrawDebugSphere(Intersection1, 2, 4, Green);

		TestBody[I].SetLocation(Intersection1);
	}
If I fix the code I end up with a strobe effect of all tail sections smooching into the head location and back again, I expect the problem is I'm getting Intersection2 returning as a point further up the body and overriding Intersection1 as to where I want to place the next segment. As I said I'll probably get back to this but for right now. It works.

Edit: it can't be Intersection2 overriding because I never call it, Intersection1 could be intersecting old line segments which is bad... I could add a check in but lazy and currently drunk. Will look again in the morning.

User avatar
Feralidragon
Godlike
Posts: 5300
Joined: Wed Feb 27, 2008 6:24 pm
Personal rank: Work In Progress
Location: Liandri

Re: Point where a line segment intersects a sphere?

Post by Feralidragon » Sat Nov 28, 2020 3:29 pm

I think the problem is that either you may be using the second intersection point wrong later in the code, which we cannot see here, which ends up compensating perfectly the last missing step in the original function itself, or maybe you're using the second intersection when you shouldn't (when it's not a valid intersection point).


Having that said, having the analytical solution, whether used or not, also provides a lot of great insight in another way of solving the same problem, and it should also be understood.

As for performance, it's actually hard to tell.
Mathematically, kmar's solution involves less steps and is more direct, especially since the operations end up being focused in linear algebra with simple numbers, however it's also important to consider the speed of each operation in practice in this particular engine.

Namely, one has to consider that UnrealScript can be anywhere between 20 to 100 times slower to process any instruction than the native C++ counterpart.
This means that what actually ends up mattering in an algorithm implemented in UnrealScript depends mostly on the number of steps to get to the solution (instructions).

That is to say that while doing a VSize(V) alone is mathematically much more expensive than doing a simple multiplication between 2 numbers, in UnrealScript they may actually end up taking the same exact amount of time as are both virtually instant to process from the engine standpoint, as UnrealScript itself is the actual bottleneck.

A more obvious example of this is the myth that using linked lists is always faster than using a ForEach AllActors loop, since theoretically the code has to transverse a much smaller number of elements, however due to the sheer speed of UnrealScript vs native C++, I have found in the past that AllActors is actually much much faster if your linked list has even as little as a few hundred elements.

So if both solutions are optimized to the least amount possible of instructions and operations, they may be neck to neck, but it's actually very hard to tell without doing an actual benchmark (with XC_Engine you can I believe, since it has timing functions you can use to test it out).

Either way, it's likely that my solution may still be a bit more inefficient, since you may also have to account for other edge cases as kmar mentioned.
I tend to solve these kinds of problems like this, especially since it's easier to visualize what's going on in each step.

Also, the picture I posted before can be interacted with here:
https://www.geogebra.org/m/v5edz8qk

(wanted to post it yesterday, but only found this site yesterday when I was looking for a good editor to draw what I had in mind, and my registration was only accepted after I went to bed)

ExpEM
Skilled
Posts: 172
Joined: Wed Nov 09, 2016 1:48 am

Re: Point where a line segment intersects a sphere?

Post by ExpEM » Sat Nov 28, 2020 3:40 pm

@Feralidragon seeing as I view you as a god when it comes to coding (working with you would tick a check on my bucket list) and you are being most helpful, would you be happy to review the entire code and point out what I have borked?