Point where a line segment intersects a sphere?

[Feralidragon]

@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]

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]

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]

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.

[Gustavo6046]

I'm flattered, but I am not such a thing

Yes you are, hun! Yes, you are!

[ExpEM]

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!

[Gustavo6046]

Yes, all the 128-bit floating points!