Intersection between two rectangles in 3D

Question

To get the line of intersection between two rectangles in 3D, I converted them to planes, then get the line of intersection using cross product of their normals, then I try to get the line intersection with each line segment of the rectangle.

The problem is the line is parallel to three segments, and intersect with only one in NAN,NAN,NAN which is totally wrong. Can you advise me what's wrong in my code?

I use vector3 from this link http://www.koders.com/csharp/fidCA8558A72AF7D3E654FDAFA402A168B8BC23C22A.aspx

and created my plane class as following

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace referenceLineAlgorithm
{
struct Line
{

    public Vector3 direction;
    public Vector3 point;

}

struct lineSegment
{

    public Vector3 firstPoint;
    public Vector3 secondPoint;

}

class plane_test
{
    public enum Line3DResult
    {
        Line3DResult_Parallel = 0,
        Line3DResult_SkewNoCross = 1,
        Line3DResult_SkewCross = 2
    };

    #region Fields

    public Vector3 Normal;
    public float D;
    public Vector3[] cornersArray;
    public Vector3 FirstPoint;
    public Vector3 SecondPoint;
    public Vector3 temp;
    public Vector3 normalBeforeNormalization;


    #endregion

    #region constructors

    public plane_test(Vector3 point0, Vector3 point1, Vector3 point2, Vector3 point3)
    {
        Vector3 edge1 = point1 - point0;
        Vector3 edge2 = point2 - point0;
        Normal = edge1.Cross(edge2);
        normalBeforeNormalization = Normal;

        Normal.Normalize();
        D = -Normal.Dot(point0);

        ///// Set the Rectangle corners 
        cornersArray = new Vector3[] { point0, point1, point2, point3 };

    }

    #endregion

    #region Methods
    /// <summary>
    /// This is a pseudodistance. The sign of the return value is
    /// positive if the point is on the positive side of the plane,
    /// negative if the point is on the negative side, and zero if the
    ///  point is on the plane.
    /// The absolute value of the return value is the true distance only
    /// when the plane normal is a unit length vector.
    /// </summary>
    /// <param name="point"></param>
    /// <returns></returns>
    public float GetDistance(Vector3 point)
    {
        return Normal.Dot(point) + D;
    }

    public void Intersection(plane_test SecondOne)
    {
        ///////////////////////////// Get the parallel to the line of interrsection (Direction )
        Vector3 LineDirection = Normal.Cross(SecondOne.Normal);

        float d1 = this.GetDistance(LineDirection);
        float d2 = SecondOne.GetDistance(LineDirection);

        temp = (LineDirection - (this.Normal * d1) - (SecondOne.Normal * d2));

        temp.x = Math.Abs((float)Math.Round((decimal)FirstPoint.x, 2));
        temp.y = Math.Abs((float)Math.Round((decimal)FirstPoint.y, 2));

        Line line;
        line.direction = LineDirection;
        line.point = temp;

        ////////// Line segments 

        lineSegment AB, BC, CD, DA;

        AB.firstPoint = cornersArray[0]; AB.secondPoint = cornersArray[1];
        BC.firstPoint = cornersArray[1]; BC.secondPoint = cornersArray[2];
        CD.firstPoint = cornersArray[2]; CD.secondPoint = cornersArray[3];
        DA.firstPoint = cornersArray[3]; DA.secondPoint = cornersArray[0];

        Vector3 r1 = new Vector3(-1, -1, -1);
        Vector3 r2 = new Vector3(-1, -1, -1);
        Vector3 r3 = new Vector3(-1, -1, -1);
        Vector3 r4 = new Vector3(-1, -1, -1);

        /*
        0,0 |----------------| w,0
            |                |
            |                |
        0,h |________________|  w,h


         */

        IntersectionPointBetweenLines(AB, line, ref r1);
        IntersectionPointBetweenLines(BC, line, ref r2);
        IntersectionPointBetweenLines(CD, line, ref r3);
        IntersectionPointBetweenLines(DA, line, ref r4);

        List<Vector3> points = new List<Vector3>();
        points.Add(r1);
        points.Add(r2);
        points.Add(r3);
        points.Add(r4);
        points.RemoveAll(

           t => ((t.x == -1) && (t.y == -1) && (t.z == -1))


           );

        if (points.Count == 2)
        {
            FirstPoint = points[0];
            SecondPoint = points[1];


        }




    }

    public Line3DResult IntersectionPointBetweenLines(lineSegment first, Line aSecondLine, ref Vector3 result)
    {
        Vector3 p1 = first.firstPoint;
        Vector3 n1 = first.secondPoint - first.firstPoint;


        Vector3 p2 = aSecondLine.point;
        Vector3 n2 = aSecondLine.direction;

        bool parallel = AreLinesParallel(first, aSecondLine);
        if (parallel)
        {

            return Line3DResult.Line3DResult_Parallel;
        }
        else
        {
            float d = 0, dt = 0, dk = 0;
            float t = 0, k = 0;

            if (Math.Abs(n1.x * n2.y - n2.x * n1.y) > float.Epsilon)
            {
                d = n1.x * (-n2.y) - (-n2.x) * n1.y;
                dt = (p2.x - p1.x) * (-n2.y) - (p2.y - p1.y) * (-n2.x);
                dk = n1.x * (p2.x - p1.x) - n1.y * (p2.y - p1.y);
            }
            else if (Math.Abs(n1.z * n2.y - n2.z * n1.y) > float.Epsilon)
            {
                d = n1.z * (-n2.y) - (-n2.z) * n1.y;
                dt = (p2.z - p1.z) * (-n2.y) - (p2.y - p1.y) * (-n2.z);
                dk = n1.z * (p2.z - p1.z) - n1.y * (p2.y - p1.y);
            }
            else if (Math.Abs(n1.x * n2.z - n2.x * n1.z) > float.Epsilon)
            {
                d = n1.x * (-n2.z) - (-n2.x) * n1.z;
                dt = (p2.x - p1.x) * (-n2.z) - (p2.z - p1.z) * (-n2.x);
                dk = n1.x * (p2.x - p1.x) - n1.z * (p2.z - p1.z);
            }

            t = dt / d;
            k = dk / d;

            result = n1 * t + p1;

            // Check if the point on the segmaent or not 
           // if (! isPointOnSegment(first, result))
            //{
               // result = new Vector3(-1,-1,-1);


           // }

            return Line3DResult.Line3DResult_SkewCross;

        }



    }
    private bool AreLinesParallel(lineSegment first, Line aSecondLine)
    {
        Vector3 vector = (first.secondPoint - first.firstPoint);
        vector.Normalize();

        float kl = 0, km = 0, kn = 0;
        if (vector.x != aSecondLine.direction.x)
        {
            if (vector.x != 0 && aSecondLine.direction.x != 0)
            {
                kl = vector.x / aSecondLine.direction.x;
            }
        }
        if (vector.y != aSecondLine.direction.y)
        {
            if (vector.y != 0 && aSecondLine.direction.y != 0)
            {
                km = vector.y / aSecondLine.direction.y;
            }
        }
        if (vector.z != aSecondLine.direction.z)
        {
            if (vector.z != 0 && aSecondLine.direction.z != 0)
            {
                kn = vector.z / aSecondLine.direction.z;
            }
        }

        // both if all are null or all are equal, the lines are parallel
        return (kl == km && km == kn);




    }

    private bool isPointOnSegment(lineSegment segment, Vector3 point)
    {
        //(x - x1) / (x2 - x1) = (y - y1) / (y2 - y1) = (z - z1) / (z2 - z1)
        float component1 = (point.x - segment.firstPoint.x) / (segment.secondPoint.x  - segment.firstPoint.x);
        float component2 = (point.y - segment.firstPoint.y) / (segment.secondPoint.y - segment.firstPoint.y);
        float component3 = (point.z - segment.firstPoint.z) / (segment.secondPoint.z - segment.firstPoint.z); 

        if ((component1 == component2) && (component2 == component3))
        {
            return true;


        }
        else
        {
            return false;

        }

    }

    #endregion
}
}

static void Main(string[] args)
    {

        //// create the first plane points 
        Vector3 point11 =new Vector3(-255.5f, -160.0f,-1.5f) ;    //0,0
        Vector3 point21 = new Vector3(256.5f, -160.0f, -1.5f);   //0,w
        Vector3 point31 = new Vector3(256.5f, -160.0f, -513.5f); //h,0
        Vector3 point41 = new Vector3(-255.5f, -160.0f, -513.5f); //w,h 

        plane_test plane1 = new plane_test(point11, point21, point41, point31);

        //// create the Second plane points 

        Vector3 point12 = new Vector3(-201.6289f, -349.6289f, -21.5f);
        Vector3 point22 =new Vector3(310.3711f,-349.6289f,-21.5f);
        Vector3 point32 = new Vector3(310.3711f, 162.3711f, -21.5f);
        Vector3 point42 =new Vector3(-201.6289f,162.3711f,-21.5f);
        plane_test plane2 = new plane_test(point12, point22, point42, point32);


        plane2.Intersection(plane1);



    }

and this is test values Best regards

Answer 1

You need to specify one thing first:

• by 3D rectangle, you mean plane rectangle on a 3D plane. (not a rectangular prism).

Let's say your rectangles are not coplanar nor parallele, and therefore there is one unique line D1 that represents the intersection of the plane described by each rectangle.

Given this assumption their are 4 possible situations for the intersection of 2 rectangles R1 and R2:

(note: sometimes D1 doesn't intersect neither R1 nor R2 and R1 , R2 can be rotated a little bit so D1 doesn't always intersect on parallele sides, but consecutive sides)

When there is an intersection between the 2 rectangles, D1 always intersect R1 and R2 on the same intersection (cf 1st and 2nd picture)

Your model is not good because your line cannot be parallele to 3 segments of the same rectangle...

As you asked in this question : 3D lines intersection algorithm once you have D1 ( Get endpoints of the line segment defined by the intersection of two rectangles ) just determinate the intersection with each segment of the rectangle.(The 4 segments of each rectangles need to be checked)

Then check for common intersection... if you find one then your rectangles intersect.

Sorry it's very hard to directly check the code, but I guess with these peaces of information you should be able to find the error.

Hope it helps.

---

EDIT:

define a rectangle by a point and 2 vectors :

R2 {A ,u ,v}
R1 {B, u',v'}

define the planes described by R1 and R2 : P1 and P2

One orthogonal vector to P1(resp. P2) is n1 (resp. n2).Let n1 = u ^ v and n2 = u' ^ v' with :

then

P1: n1.(x-xA,y-yA,z-zA)=0
P2: n2.(x-xB,y-yB,z-zB)=0

Then if you're just looking for D1 the equation of D1 is :

D1: P1^2 + P2 ^2 =0 (x,y,z verify P1 =0  an P2 =0 )

D1 : n1.(x-xA,y-yA,z-zA)^2 + n2.(x-xB,y-yB,z-zB)^2 =0

(so just with the expression of your rectangles you can get the equation of D1 with a closed formula.)

Now let's look at the intersections :

the 4 points in R1 are :

{ A , A+u , A+v, A+u+v }

as describe in 3D lines intersection algorithm do :

D1 inter [A,A+u] = I1
D1 inter [A,A+v] = I2
D1 inter [A+u,A+u+v] = I3
D1 inter [A+v,A+u+v] = I4

(I1,I2,I3,I4 can be null)

same for D2 you get I1' I2' I3' I4'

if Ij'=Ik' != null then it's an intersection point

if you did that correctly step by step you should get to the correct solution; unless I didn't fully understand the question...

Answer 2

The program computes the line of intersection of the planes passing through two rectangles. The program then looks for intersections between this line and the edges of one of the rectangles. It returns two points of intersection of such two points are found. I'm not going to debate whether this is a sensible thing to do since I don't know the context of the program.

Let's go through the code and look for things that could be wrong.

The program computes the line passing through the two planes like this:

Vector3 LineDirection = Normal.Cross(SecondOne.Normal);

float d1 = this.GetDistance(LineDirection);
float d2 = SecondOne.GetDistance(LineDirection);

temp = (LineDirection - (this.Normal * d1) - (SecondOne.Normal * d2));

temp.x = Math.Abs((float)Math.Round((decimal)FirstPoint.x, 2));
temp.y = Math.Abs((float)Math.Round((decimal)FirstPoint.y, 2));

Line line;
line.direction = LineDirection;
line.point = temp;

The computation of the line direction is OK, but the computation of point is wrong, as you probably know. But I'll pretend we have a valid point and direction and carry on with the rest of the program.

The program calls AreLinesParallel() to get rid of edges that a parallel to the line through the planes. The code looks like this:

Vector3 vector = (first.secondPoint - first.firstPoint);
vector.Normalize();

float kl = 0, km = 0, kn = 0;
if (vector.x != aSecondLine.direction.x)
{
    if (vector.x != 0 && aSecondLine.direction.x != 0)
    {
        kl = vector.x / aSecondLine.direction.x;
    }
}
if (vector.y != aSecondLine.direction.y)
{
    if (vector.y != 0 && aSecondLine.direction.y != 0)
    {
        km = vector.y / aSecondLine.direction.y;
    }
}
if (vector.z != aSecondLine.direction.z)
{
    if (vector.z != 0 && aSecondLine.direction.z != 0)
    {
        kn = vector.z / aSecondLine.direction.z;
    }
}

// both if all are null or all are equal, the lines are parallel
return ((kl == km && km == kn));

The code more or less checks that the elements of the direction of the edge divided by the elements of the direction of the line are all equal to each other. It's a dangerous procedure to rely on. Because of round-off errors, later procedures may still, say, divide by zero, even if AreLinesParallel() claims that the lines aren't really parallel. It is better not to use the procedure at all.

Now comes the meat of the code, a test for intersection between the edge and the line:

float d = 0, dt = 0, dk = 0;
float t = 0, k = 0;

if (Math.Abs(n1.x * n2.y - n2.x * n1.y) > float.Epsilon)
{
    d = n1.x * (-n2.y) - (-n2.x) * n1.y;
    dt = (p2.x - p1.x) * (-n2.y) - (p2.y - p1.y) * (-n2.x);
    dk = n1.x * (p2.x - p1.x) - n1.y * (p2.y - p1.y);
}
else if (Math.Abs(n1.z * n2.y - n2.z * n1.y) > float.Epsilon)
{
    d = n1.z * (-n2.y) - (-n2.z) * n1.y;
    dt = (p2.z - p1.z) * (-n2.y) - (p2.y - p1.y) * (-n2.z);
    dk = n1.z * (p2.z - p1.z) - n1.y * (p2.y - p1.y);
}
else if (Math.Abs(n1.x * n2.z - n2.x * n1.z) > float.Epsilon)
{
    d = n1.x * (-n2.z) - (-n2.x) * n1.z;
    dt = (p2.x - p1.x) * (-n2.z) - (p2.z - p1.z) * (-n2.x);
    dk = n1.x * (p2.x - p1.x) - n1.z * (p2.z - p1.z);
}

t = dt / d;
k = dk / d;

result = n1 * t + p1;

A mistake of this code is the lack of a comment that explains the origin of the algorithm. If there is no documented algorithm to refer to, the comment can contain the derivation leading to the formulas. The first branch deals with (x, y), the second with (y, z) and the third with (z, x), so I assume that the branches solve for intersection in 2D and lift these findings to 3D. It computes determinants to check for parallel lines for each 2D projection. I shouldn't have to do this kind of reverse engineering.

Anyway, this is the code that produces the NaN values. None of the three branches are triggered, so d = 0 in the end, which gives a division by zero. Instead of relying on AreLinesParallel() to avoid division by zero, it's is better to check the value that actually matters, namely d.

Of course, the code still needs more work, because we don't know yet if the lines are crossing in 3D too. Also the point is on the edge only if 0 <= t && t <= 1. And probably more bugs will show up as the earlier ones are being fixed.