Point where a line segment intersects a sphere?

Discussions about Coding and Scripting
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:50 pm

ExpEM wrote:
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?
I'm flattered, but I am not such a thing, and it would perhaps be more beneficial to you for you to share it here with everyone, if you can, as that way anyone may spot what you did wrong (or what I did wrong in my original definition, which is not completely off the table either). :)

For instance, it could also be the case that when corrected the second intersection point is now rejected when it wasn't before, also leading to problems.

Although I do find it weird that something that apparently you do not use breaks your code as so when corrected.
So, if you don't really feel comfortable of sharing the rest of the code with everyone, I can try to take a look privately this one time, even if a quick look to check if anything stands out, to also make sure that what I explained works as intended.

Alternatively, you could also test kmar's solution and see if that solves it for you, or if you get the same behavior.

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 4:02 pm

ExpEM wrote:
Sat Nov 28, 2020 3:13 pm
I wrote this function: (...snip...)
I see, so I assume you are trying to do something like inverse kinematics for the tail (correct me if I'm wrong)
I believe you want both intersection points in this case as if the ray was infinite (you can easily change my analytic solution by removing FMin/FMax and the t2 < t1 and c < 0 conditions),
because you might actually end up casting the ray from inside the sphere...
Then you should pick either intersection1 or intersection2 based on which one is closer to the next segment? Or actually the one that's further along the nextseg-prevseg direction (just guessing here)

Other than that, I agree with Feralidragon that geometric solutions in general are more intuitive. The problem with analytic solutions is that as the problem gets more complicated,
they tend to skyrocket in complexity very quickly. But in this case, I believe the analytic solution is still very simple and easy to grasp.

EDIT: if you only want the points to be SDist units apart, then why not simply

Code: Select all

dir = current - previous;
dir *= SDist / VSize(dir)
current = previous+dir

ShaiHulud
Adept
Posts: 395
Joined: Sat Dec 22, 2012 6:37 am

Re: Point where a line segment intersects a sphere?

Post by ShaiHulud » Sun Nov 29, 2020 2:44 am

Apologies for derailing the discussion, but a summative version of this topic might be a worthwhile addition to this Wiki page for future reference:

https://wiki.beyondunreal.com/Legacy:Un ... ctor_Maths

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

Re: Point where a line segment intersects a sphere?

Post by ExpEM » Sun Nov 29, 2020 9:19 pm

Good news, I figured out why things broke when I fixed the function.
The problem was two fold:

Code: Select all

	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;
	}
Which wouldn't have been a bad thing except for the way I was using the function:

Code: Select all

	for (I=1; I<50; I++)
	{
Log("***********************************");
Log("Processing TestBody["$I$"].");
		SphereOrigin = TestBody[I-1].Location;

		While (FindSphereIntersection(UnCompassPoints[LastSegment+1], UnCompassPoints[LastSegment], SphereOrigin, SDist, Intersection1, Intersection2) < 1)
		{
			LastSegment++;
			Assert(LastSegment < 64); //Testing.
Log("While loop forced increment. LastSegment = "$LastSegment$".");
		}

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

		TestBody[I].SetLocation(Intersection1);
	}
What this dose is feed in line segments until >=1 is returned, a 1 is returned when one intersection point is valid, a two is returned when both points are valid. Then we place a body segment and move onto the next.
So what dose this mean?
Using the broken function always made Intersection2 be rejected, so a 1 was returned (when Intersection1 was valid) or a 0 was returned (when Intersection1 was invalid).
After fixing the function, with Intersection2 no longer being constantly rejected this happened:

Code: Select all

	else if (Reject1 && !Reject2)
	{						
		Log("Rejected #1");				
		Intersection1 = Intersection2;		
		Return 1;						
	}	
And everything broke.
Essentially, what happens in the code is if Intersection2 is positive it has hit the line in the wrong direction. I didn't take this into account (bad ExpEM) so the next body segment was placed the wrong way down the line on top of another segment, then the next one would be placed correctly from the wrong location, so also on top of another segment. And then we have a loop of "place backwards, place forwards, place backwards, place forwards".

And so the fix:

Code: Select all

	else if (Reject1 && !Reject2)
	{						
		Log("Rejected #1");					
		Return 0;						
	}	
Return 0 not 1.
This fix is specific to how I am using the function where I now know that Intersection2 should always be discarded.
For general purpose this would be more appropriate:

Code: Select all

	if (Reject1 && Reject2)
		Return 0; //No hit.
	else if (Reject1 && !Reject2)
		Return 1; //Intersection2 hit.
	else if (!Reject1 && Reject2)
		Return 2; //Intersection1 hit.
	else
		Return 3; //Both hit.

User avatar
Gustavo6046
Godlike
Posts: 1158
Joined: Mon Jun 01, 2015 7:08 pm
Personal rank: Zeta Group leader

Re: Point where a line segment intersects a sphere?

Post by Gustavo6046 » Sun Nov 29, 2020 11:41 pm

Feralidragon wrote:
Sat Nov 28, 2020 3:50 pm
I'm flattered, but I am not such a thing
Yes you are, hun! Yes, you are!

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

Re: Point where a line segment intersects a sphere?

Post by ExpEM » Mon Nov 30, 2020 3:12 am

Gustavo6046 wrote:
Sun Nov 29, 2020 11:41 pm
Feralidragon wrote:
Sat Nov 28, 2020 3:50 pm
I'm flattered, but I am not such a thing
Yes you are, hun! Yes, you are!
I knew I wasn't the only one who had a dedicated altar! Sacrifice the binary to the code god!

User avatar
Gustavo6046
Godlike
Posts: 1158
Joined: Mon Jun 01, 2015 7:08 pm
Personal rank: Zeta Group leader

Re: Point where a line segment intersects a sphere?

Post by Gustavo6046 » Mon Nov 30, 2020 7:37 pm

Yes, all the 128-bit floating points!