I have a point in 3d space and I have a Vector3 that is closeby. I need to find the point (drawn in blue) along that Vector3 which is exactly 60 meters from the point I already have (labeled “my point” below).
I realize that there will actually be two points along the Vector3 that are exactly 60 meters from the point I have. I’d be thrilled if I could figure out how to get either or both.
That is a circle - line intersection basically and a quick google search brought up this answers on Stackoverflow.
I did a quick C# Unity implementation of the code because this was an interesting question and I also wanted the implementation myself:
public Vector3[] LineCircleIntersection(Vector3 center, float radius, Vector3 rayStart, Vector3 rayEnd)
{
Vector3 directionRay = rayEnd - rayStart;
Vector3 centerToRayStart = rayStart - center;
float a = Vector3.Dot(directionRay, directionRay);
float b = 2 * Vector3.Dot(centerToRayStart, directionRay);
float c = Vector3.Dot(centerToRayStart, centerToRayStart) - (radius * radius);
float discriminant = (b * b) - (4 * a * c);
if (discriminant >= 0)
{
//Ray did not miss
discriminant = Mathf.Sqrt(discriminant);
//How far on ray the intersections happen
float t1 = (-b - discriminant) / (2 * a);
float t2 = (-b + discriminant) / (2 * a);
Vector3[] hitPoints;
if (t1 >= 0 && t2 >= 0)
{
//total intersection, return both points
hitPoints = new Vector3[2];
hitPoints[0] = rayStart + (directionRay * t1);
hitPoints[1] = rayStart + (directionRay * t2);
}
else
{
//Only one intersected, return one point
hitPoints = new Vector3[1];
if (t1 >= 0)
{
hitPoints[0] = rayStart + (directionRay * t1);
}
else if (t2 >= 0)
{
hitPoints[0] = rayStart + (directionRay * t2);
}
}
return hitPoints;
}
//No hits
return null;
}
Most of this code is explained on the stackoverflow question, but if there is anything else you want to know specifically about it let me know.
This problem is well explained at A Minimal Ray-Tracer: Rendering Simple Shapes (Sphere, Cube, Disk, Plane, etc.) The first method is using projection. The second method is using an algebraic method.
var firstSphereIntersection = raySphereIntersection(SphereCenter, SphereRadius, lineOrigin, unitVectorOfForwardFromLineOrigin);
Above is how you can call into the function below. It’s yet another way, that you probably shouldn’t do. It’s moving a point along a ray in a loop until it is radius away from the center of the sphere. The performance is surly poor compared to single iteration methods.
private Vector3 raySphereIntersection(Vector3 sphereCenter, float sphereRadius, Vector3 rayStart, Vector3 rayUnitForward)
{
Ray ray = new Ray(rayStart, rayUnitForward);
float rayDistance;
if (raySphereIntersection(sphereCenter, sphereRadius, ray, out rayDistance))
{
return ray.GetPoint(rayDistance);
}
return Vector3.zero;
}
private bool raySphereIntersection(Vector3 sphereCenter, float sphereRadius, Ray ray, out float rayDistance)
{
float distanceOnRay = 0;
float distanceToSphereCenter = Vector3.Distance(sphereCenter, ray.origin);
float distanceToEdge = sphereRadius - distanceToSphereCenter;
while (distanceToEdge > 0.01)
{
float lastDistance = distanceToSphereCenter;
if (distanceToSphereCenter < sphereRadius)
{
// add distance if ray was going directly towards sphere edge
distanceOnRay += (sphereRadius - distanceToSphereCenter);
distanceToSphereCenter = Vector3.Distance(sphereCenter, ray.GetPoint(distanceOnRay));
}
else // distanceToSphereCenter must be > sphereRadius
{
// subtract distance if ray was going directly towards sphere center
distanceOnRay -= (distanceToSphereCenter - sphereRadius);
distanceToSphereCenter = Vector3.Distance(sphereCenter, ray.GetPoint(distanceOnRay));
// if ray is not going towards the sphere, it'll never hit it
if (distanceToSphereCenter > lastDistance)
{
rayDistance = 0;
return false;
}
}
distanceToEdge = sphereRadius - distanceToSphereCenter;
}
rayDistance = distanceOnRay;
return true;
}
Thanks @GameVortex. This was SUPER helpful for my little project, but I am getting a strange result that I was hoping someone could explain… I have concentric circles in which I have stored into a list of Radius’s (or is it Radii?). Anyway, I run through each one and work out my discriminant and all that… and I get my little test to print our the Vectors of each point that my line crosses, in order of collision (outermost, into the smallest radii, then back out again to the outermost).
It works for the most part… except that If my point StartPoint is inside the largest circle then my first result is always at the opposite side of that circle… then it goes back to printing the correct order.
Also, for some reason, unless my path either points at the middle radius or cuts through it, my Discriminant comes back with a negative result…
public Vector3[] CircleLineCollision(Vector3 sunPos, float sunRadius, Vector3 shipStart, Vector3 DestinationPlanet)
{
// This is the function that takes a position and radius of a circle and the start and end of a line and tells you any points where they intersect.
Vector3 directionOfShip = DestinationPlanet - shipStart;
Vector3 centerToShipStart = shipStart - sunPos;
Vector3[] IntersectingPoints;
float a = Vector3.Dot(directionOfShip, directionOfShip);
float b = 2 * Vector3.Dot(centerToShipStart, directionOfShip);
float c = Vector3.Dot(centerToShipStart, centerToShipStart) - (sunRadius * sunRadius);
float discriminant = (b * b) - (4 * a * c);
Debug.Log("discriminant : " + discriminant.ToString());
if (discriminant >= 0)
{
//Ship Hits The Sun
discriminant = Mathf.Sqrt(discriminant);
//Where do the journey path intersections happen
float t1 = (-b - discriminant) / (2 * a);
float t2 = (-b + discriminant) / (2 * a);
if (t1 >= 0 && t2 >= 0)
{
// Debug.Log("You will intersect the Sun's orbit twice");
//total intersection, return both points
IntersectingPoints = new Vector3[2];
IntersectingPoints[0] = shipStart + (directionOfShip * t1);
IntersectingPoints[1] = shipStart + (directionOfShip * t2);
}
else
{
// Debug.Log("You will only intersect the Sun's Orbit once");
//Only one intersected, return one point
IntersectingPoints = new Vector3[1];
if (t1 >= 0)
{
IntersectingPoints[0] = shipStart + (directionOfShip * t1);
}
else if (t2 >= 0)
{
IntersectingPoints[0] = shipStart + (directionOfShip * t2);
}
}
return IntersectingPoints;
}
//No hits
return null;
}