Intersección entre dos rectángulos en 3D

Question

Para obtener la línea de intersección entre dos rectángulos en 3D, los convertí en planos, luego obtuve la línea de intersección utilizando el producto cruzado de sus normales, luego trato de obtener la intersección de líneas con cada uno segmento de línea del rectángulo.

El problema es la línea es paralela a tres segmentos, y se cruzan con sólo uno de cada NAN, NAN, NAN que es totalmente equivocado. ¿Me puede avisar qué hay de malo en mi código?

utilizo vector3 desde este enlace http://www.koders.com/csharp/fidCA8558A72AF7D3E654FDAFA402A168B8BC23C22A.aspx

y creó mi clase plano que tras

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); 



    } 

y esto es valores de prueba Saludos

Answer 1

Es necesario especificar una cosa primero:

• por el rectángulo 3D, que quiere decir pla ne rectángulo en un plano 3D. (no es un prisma rectangular ).

Digamos que sus rectángulos no son coplanares ni paralelos, y por lo tanto hay una única línea D1 que representa la intersección del plano descrito por cada rectángulo.

Dada esta suposición su son 4 situaciones posibles para la intersección de 2 rectángulos R1 y R2:

(nota: a veces D1 no corta ni R1 ni R2 y R1, R2 puede ser girado un poco para que D1 no siempre se intersecte en lados paralelos, sino en lados consecutivos)

Cuando hay una intersección entre los 2 rectángulos, D1 siempre interseca R1 y R2 en la misma intersección (cf 1ra y 2da imagen)

Su modelo no es buena debido a que su línea no puede ser parallele a 3 segmentos del mismo rectángulo ...

como lo pidió en esta pregunta: 3D lines intersection algorithm una vez que tenga D1 (Get endpoints of the line segment defined by the intersection of two rectangles) acaba de determinar la intersección con cada segmento de el rectángulo. (Se deben verificar los 4 segmentos de cada rectángulo)

Luego verifique la intersección común ... si encuentra una, sus rectángulos se cruzan.

sentimos que es muy difícil de comprobar directamente el código, pero supongo que con estas paces de información que debe ser capaz de detectar el error.

Espero que ayude.

---

EDIT:

definir un rectángulo por un punto y 2 vectores:

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

definir los planos descritos por R1 y R2: P1 y P2

Una ortogonal vector a P1 (resp. P2) es n1 (resp. n2). Deje n1 = u^v y n2 = u'^v 'con:

continuación

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

Entonces, si usted está buscando para D1 D1 de la ecuación es:

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 

(por lo que sólo con la expresión de sus rectángulos se puede obtener la ecuación de D1 con una fórmula cerrada.)

Ahora veamos las intersecciones:

los 4 puntos en R1 son:

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

como se describe en 3D lines intersection algorithm hacer:

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 puede ser nulo)

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

si Ij '= Ik'! = null entonces es un punto de intersección

si lo hizo correctamente paso a paso, debería llegar a la solución correcta; a menos que no haya entendido completamente la pregunta ...

Answer 2

El programa calcula la línea de intersección de los planos que pasan por dos rectángulos. El programa luego busca intersecciones entre esta línea y los bordes de uno de los rectángulos. Se devuelve dos puntos de intersección de esos dos puntos que se encuentran. No voy a debatir si esto es algo sensato porque no conozco el contexto del programa.

Repasemos el código y busquemos las cosas que podrían estar equivocadas.

El programa calcula la recta que pasa por los dos planos de esta manera:

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; 

El cálculo de la dirección de la línea está bien, pero el cálculo de point está mal, como usted probablemente sabe. Pero pretenderé tener un punto y una dirección válidos y continuar con el resto del programa.

El programa llama a AreLinesParallel() para deshacerse de los bordes que son paralelos a la línea a través de los planos.El código es el siguiente:

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)); 

El código más o menos cheques que los elementos de la dirección del borde dividida por los elementos de la dirección de la línea son todos iguales entre sí. Es un procedimiento peligroso en el que confiar. Debido a los errores de redondeo, los procedimientos posteriores aún pueden, por ejemplo, dividir por cero, incluso si AreLinesParallel() afirma que las líneas no son realmente paralelas. Es mejor no usar el procedimiento en absoluto.

Ahora viene la carne del código, una prueba de intersección entre el borde y la línea:

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; 

Un error de este código es la falta de un comentario que explica el origen del algoritmo. Si no hay un algoritmo documentado al que hacer referencia, el comentario puede contener la derivación que conduce a las fórmulas. La primera rama se ocupa de (x, y), la segunda con (y, z) y la tercera con (z, x), por lo que supongo que las ramas resuelven la intersección en 2D y elevan estos hallazgos a 3D. Calcula determinantes para verificar líneas paralelas para cada proyección 2D. No debería tener que hacer este tipo de ingeniería inversa.

De todos modos, este es el código que produce los valores NaN. Ninguna de las tres ramas se activa, por lo que d = 0 al final, lo que da una división por cero. En lugar de confiar en AreLinesParallel() para evitar la división por cero, es mejor verificar el valor que realmente importa, es decir, d.

Por supuesto, el código aún necesita más trabajo, porque aún no sabemos si las líneas se cruzan en 3D. Además, el punto está en el borde solo si 0 <= t && t <= 1. Y probablemente aparecerán más errores ya que los anteriores están siendo reparados.