x

Search in
Sort by:

Question Status:

Search help

  • Simple searches use one or more words. Separate the words with spaces (cat dog) to search cat,dog or both. Separate the words with plus signs (cat +dog) to search for items that may contain cat but must contain dog.
  • You can further refine your search on the search results page, where you can search by keywords, author, topic. These can be combined with each other. Examples
    • cat dog --matches anything with cat,dog or both
    • cat +dog --searches for cat +dog where dog is a mandatory term
    • cat -dog -- searches for cat excluding any result containing dog
    • [cats] —will restrict your search to results with topic named "cats"
    • [cats] [dogs] —will restrict your search to results with both topics, "cats", and "dogs"

Intersection between two lines

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?

Product Version: UE 4.10
Tags:
more ▼

asked Jan 20 '16 at 09:20 PM in C++ Programming

avatar image

padmalcom
142 11 13 18

(comments are locked)
10|2000 characters needed characters left

2 answers: sort voted first

For all those who are interested I found a working solution here https://gist.github.com/hanigamal/6556506 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;
 }
more ▼

answered Jan 20 '16 at 10:09 PM

avatar image

padmalcom
142 11 13 18

(comments are locked)
10|2000 characters needed characters left

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.

alt text

1.png (8.7 kB)
more ▼

answered Aug 26 '16 at 06:55 AM

avatar image

DennisDing
45 3 7 11

avatar image DennisDing Aug 26 '16 at 07:17 AM

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;

}

avatar image DennisDing Aug 26 '16 at 08:01 AM

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;
(comments are locked)
10|2000 characters needed characters left
Your answer
toggle preview:

Up to 5 attachments (including images) can be used with a maximum of 5.2 MB each and 5.2 MB total.

Follow this question

Once you sign in you will be able to subscribe for any updates here

Answers to this question