I am looking for a fast way to calculate the line segment of two given rectangles in 3D. For instance, each 3D rectangle is defined by its four vertices.
A solution in any reasonable programming language will do.
+1
A:
You'll need to combine three common 3D operations:
Turn the two rectangles into two planes (just take three of the four vertices and build the plane from that).
Intersect the two planes to get an infinite line (see here).
Intersect this line with the bounding lines of the first rectangle. You should get two intersections which are the end points of the line segment you seek.
Aaron Digulla
2009-11-09 10:34:08
I believe this computes intersection of the first rectangle with the plane that contains the second rectangle. And 2. might yield a plane instead of a line (the case when both rectangles are in the same plane).
Rafał Dowgird
2009-11-09 11:28:41
@Rafał Dowgird: You're right about 2. One should first check if the rectangles are parallel (through their normals) before trying to find an intersection.
Ivan
2009-11-09 11:41:50
The intersection algorithm will tell you when the planes are coplanar (see the link I posted for the test).
Aaron Digulla
2009-11-09 12:45:54
Perhaps I don't understand 3. What do "the lines" in "Intersect the lines" refer to?
Rafał Dowgird
2009-11-09 14:03:28
Oops ... fixed. It's the line which you get from step #2. Your 3D library should come with helper methods that implement all of these operations.
Aaron Digulla
2009-11-09 14:45:56
Ok, what happens in point 3. if the first rectangle does not intersect with the second one, but intersects with its plane? Won't you get a false intersection?
Rafał Dowgird
2009-11-09 14:55:59
@Rafał: No since either or both intersection points will lie outside of the line segments which bound the rectangle. If you write the code, the cross and vector products will tell you about these cases.
Aaron Digulla
2009-11-09 15:03:00
@Aaron: You are intersecting an infinite line with a rectangle, right? How can their intersection points lie outside the line segments that bound the rectangle?
Rafał Dowgird
2009-11-09 16:58:23
@Rafal: Take two rectangles which are away from the X axis by 2 units. One lies in the plane createy by the X and Y axis and the other in the plane XZ. They don't intersect but the planes from step #1 do: Their intersection is the X axis. So you get a line in step 2 but there are no intersection points with either of the original rectangles. I suggest to sit down and write the code. It will be pretty obvious how it works and why.
Aaron Digulla
2009-11-10 07:56:08
@Aaron: If neither of the rectangles intersects the line, then it is ok. If only rectangle 1 intersects the other plane, then you have a false intersection. Will try to explain in an own answer.
Rafał Dowgird
2009-11-10 08:32:41
+1
A:
Based on Aaron's answer, which I believe contains an error:
- Turn the two rectangles into two planes (just take three of the four vertices and build the plane from that).
- Intersect the two planes to get an infinite line (*).
- Intersect this line with the bounding lines of the first rectangle.
- Intersect result of 3 with the bounding lines of the second rectangle.
If you omit step 4, then you get a false intersection when first rectangle intersects the second rectangle's plane but not the rectangle itself. Example:
rectangle1=[(-1,-1,0),(-1,1,0),(1,1,0),(1,-1,0)]
rectangle2=[(0,50,50),(0,50,40),(0,40,40),(0,40,50)]
Plane1 is z=0, plane2 is x=0, their intersection is the y axis, which intersects rectangle1 at 1 and -1. The rectangles do not intersect, though.
(*) If the planes overlap, the rectangles' intersection can still be a line, but it's a rather nasty case.
Rafał Dowgird
2009-11-10 08:43:36