There are many useful functions in FMath to determine intersections e.g. between a line and a box, a line and a plane … but not to calculate the intersection of two lines. Or is there one?
For all those who are interested I found a working solution here Find the point of intersection of two 3D line segments, works in 2D if z=0 · GitHub and implemented a simple function for UE (I only did 2 tests for the method):
bool PCGUtils::lineToLineIntersection(const FVector& fromA, const FVector& fromB, const FVector& toA, const FVector& toB, FVector& _outIntersection)
{
FVector da = fromB - fromA;
FVector db = toB - toA;
FVector dc = toA - fromA;
if (FVector::DotProduct(dc, FVector::CrossProduct(da, db)) != 0.0) {
return false;
}
FVector crossDaDb = FVector::CrossProduct(da, db);
float prod = crossDaDb.X * crossDaDb.X + crossDaDb.Y * crossDaDb.Y + crossDaDb.Z * crossDaDb.Z;
float res = FVector::DotProduct(FVector::CrossProduct(dc, db), FVector::CrossProduct(da, db) / prod);
if (res >= 0.0f && res <= 1.0f) {
_outIntersection = fromA + da * FVector(res, res, res);
return true;
}
return false;
}This method is right basically…But there are some point that may haven’t be considered…
if (res >= 0.0f && res <= 1.0f)
This condition can not include all the situation…
For example…
Line a and line b will not intersect…Just like the picture i give below…But it will return true.Because the cross point is on line a.
In order to make it right,it must consider if the intersect point is on line b too…
What’s more ,I found some different from your answer and the answer on github…
On github,the answer is
float res = FVector::DotProduct(FVector::CrossProduct(dc, db), FVector::CrossProduct(da, db)) / prod;
Your answer is
float res = FVector::DotProduct(FVector::CrossProduct(dc, db), FVector::CrossProduct(da, db) / prod);
There are some different about “)”…
I havn’t test which one is right .But I’m using the github answer and it looks right…
Thanks for the solution you provides. It helps me a lot.
1 Like
I make some change for this function.
Check if the intersect point is on line a and line b at the same time.
Here is the code
_outIntersection = fromA + da * FVector(res, res, res);
FVector fromAToIntersectPoint = _outIntersection - fromA;
FVector fromBToIntersectPoint = _outIntersection - fromB;
FVector toAToIntersectPoint = _outIntersection - toA;
FVector toBToIntersectPoint = _outIntersection - toB;
if (FVector::DotProduct(fromAToIntersectPoint, fromBToIntersectPoint) <= 0 && FVector::DotProduct(toAToIntersectPoint, toBToIntersectPoint) <= 0)
{
return true;
}
return false;
}
Well.Unfortunately,this is still not the correct answer…I forget the paralla situation…
if (FVector::DotProduct(dc, FVector::CrossProduct(da, db)) != 0.0) {
return false;
}
This function can not check the paralla situation…So I made some change…
Here is the final code…
FVector da = fromB - fromA;
FVector db = toB - toA;
FVector dc = toA - fromA;
FVector crossDaDb = FVector::CrossProduct(da, db);
float prod = crossDaDb.X * crossDaDb.X + crossDaDb.Y * crossDaDb.Y + crossDaDb.Z * crossDaDb.Z;
if(prod == 0 || FVector::DotProduct(dc,crossDaDb) != 0)
{
return false;
}
float res = FVector::DotProduct(FVector::CrossProduct(dc, db), FVector::CrossProduct(da, db)) / prod;
_outIntersection = fromA + da * FVector(res, res, res);
FVector fromAToIntersectPoint = _outIntersection - fromA;
FVector fromBToIntersectPoint = _outIntersection - fromB;
FVector toAToIntersectPoint = _outIntersection - toA;
FVector toBToIntersectPoint = _outIntersection - toB;
if (FVector::DotProduct(fromAToIntersectPoint, fromBToIntersectPoint) <= 0 && FVector::DotProduct(toAToIntersectPoint, toBToIntersectPoint) <= 0)
{
return true;
}
return false;
1 Like
If you want a really functional solution which takes into account all possible configurations (including segments being points) here it is.
If segments overlap it returns the first point of intersection from the first segment’s point of view.
bool FindPointSegmentIntersection(const FVector Point, const FVector SegmentStart,
const FVector SegmentEnd)
{
const FVector Da = Point - SegmentStart;
const FVector Db = SegmentEnd - SegmentStart;
if (FVector::CrossProduct(Da, Db).IsNearlyZero())
{
const float Res = Da.SizeSquared() / Db.SizeSquared();
const float DotProd = FVector::DotProduct(Da, Db);
if (DotProd >= 0 && 0 <= Res && Res <= 1)
{
return true;
}
}
return false;
}
bool FindSegmentSegmentIntersection(const FVector Segment1Start, const FVector Segment1End,
const FVector Segment2Start, const FVector Segment2End,
FVector& IntersectionPoint)
{
// both points
if (Segment1Start == Segment1End && Segment2Start == Segment2End)
{
if (Segment1Start == Segment2Start)
{
IntersectionPoint = Segment1Start;
return true;
}
return false;
}
//segment 1 is point
if (Segment1Start == Segment1End)
{
if (FindPointSegmentIntersection(Segment1Start, Segment2Start, Segment2End))
{
IntersectionPoint = Segment1Start;
return true;
}
return false;
}
//segment 2 is point
if (Segment2Start == Segment2End)
{
if (FindPointSegmentIntersection(Segment2Start, Segment1Start, Segment1End))
{
IntersectionPoint = Segment2Start;
return true;
}
return false;
}
//both segments
const FVector S1Delta = Segment1End - Segment1Start;
const FVector S2Delta = Segment2End - Segment2Start;
const FVector Delta = Segment2Start - Segment1Start;
const FVector Cross = FVector::CrossProduct(S1Delta, S2Delta);
if (Cross.IsNearlyZero())
{
if (!FVector::CrossProduct(Delta, S2Delta).IsNearlyZero())
{
//parallel
return false;
}
//overlap
const float T0 = FVector::DotProduct(Delta, S1Delta) / S1Delta.SizeSquared();
const float T1 = T0 + FVector::DotProduct(S2Delta, S1Delta) / S1Delta.SizeSquared();
if (T0 <= 0 && T0 <= 1)
{
IntersectionPoint = Segment1Start + (S1Delta * T0);
return true;
}
if (T0 <= 0 && 0 <= T1)
{
IntersectionPoint = Segment1Start;
return true;
}
if (0 <= T1 && T1 <= 1)
{
IntersectionPoint = Segment1Start + (S1Delta * T0);
return true;
}
if (T0 <= 1 && 1 <= T1)
{
IntersectionPoint = Segment1Start;
return true;
}
return false;
}
if (!FMath::IsNearlyZero(FVector::DotProduct(Delta, Cross)))
{
//skew
return false;
}
FVector Cross1 = FVector::CrossProduct(Delta, S1Delta);
const FVector Cross2 = FVector::CrossProduct(Delta, S2Delta);
FVector Start = Segment2Start;
FVector SDelta = S2Delta;
if (Cross1.IsNearlyZero())
{
Cross1 = Cross2;
Start = Segment1Start;
SDelta = S1Delta;
}
const float Dot1 = FVector::DotProduct(Cross1, Cross);
const float Dot2 = FVector::DotProduct(Cross2, Cross);
const float Denom = Cross.SizeSquared();
if (0 <= Dot1 && Dot1 <= Denom && 0 <= Dot2 && Dot2 <= Denom)
{
IntersectionPoint = Start + (SDelta * (Dot1 / Denom));
return true;
}
return false;
Thanks a lot for this!
Here is a version that works with FTransform directly. The process is splitted in two methods, to make it easier to retrieve the 2 coplanars vectors linking the intersection point to both origins. In my case, that’s the only info i need. I also changed to naming of the vectors to make it a bit easuier to decypher 
bool MyClass::coplanar_right(const FTransform& A, const FTransform& B, FVector& rightA, FVector& rightB)
{
if (FVector::Distance(A.GetTranslation(), B.GetTranslation()) < 1e-5)
{
// these transforms seems to be VERY close...
return false;
}
FVector normA = A.GetRotation().GetForwardVector();
FVector normB = B.GetRotation().GetForwardVector();
if (FMath::Abs(normA.Dot(normB)) > 1 - 1e-3)
{
// these transforms seems to be VERY parallel...
return false;
}
FVector posA = A.GetTranslation();
FVector posB = B.GetTranslation();
// computing perpendicular to the both normals
FVector normC = normA.Cross(normB);
float det = normC.SquaredLength();
if (det != 0)
{
rightA = normA.Cross(normC);
rightB = normB.Cross(normC);
return true;
}
return false;
}
bool MyClass::transform_intersection(const FTransform& A, const FTransform& B, FVector& pos)
{
FVector rightA, rightB;
if (!coplanar_right(A, B, rightA, rightB))
{
return false;
}
FVector diff = B.GetTranslation() - A.GetTranslation();
float res = FVector::DotProduct(
diff.Cross(rightB),
rightA.Cross(rightB) / rightA.Cross(rightB).SquaredLength()
);
pos = A.GetTranslation() + rightA * res;
// debug is a ULineBatchComponent making it easy to visualise your intersection point
// FVector posA = A.GetTranslation();
// FVector posB = B.GetTranslation();
// debug->DrawLine(
// posA,
// posB,
// FColor(255, 0, 0), 0, .5, -1);
// debug->DrawLine(
// posA - rightA * 2000,
// posA + rightA * 2000,
// FColor(255, 255, 0), 0, .2, -1);
// debug->DrawLine(
// posB - rightB * 2000,
// posB + rightB * 2000,
// FColor(255, 0, 255), 0, .2, -1);
// debug->DrawLine(
// posA + diff * .5,
// pos,
// FColor(0, 0, 0), 0, .2, -1);
return true;
}