Dado un cuadro delimitador y una línea (dos puntos), determine si la línea se cruza con el cuadro

Question

Dado un cuadro delimitador, con definiciones como bounds.min.(x/y/z), bounds.max.(x/y/z), y dos puntos en el espacio 3D (expresados ​​como objetos Vector3), ¿cómo puedo determinar si la línea hecha por los dos puntos se cruza con el cuadro delimitador?

Answer 1

Déjeme Google que para usted: Line Box Intersection (http://www.3dkingdoms.com/weekly/weekly.php?a=3)

Otro enlace, con referencias (y de código) para una gran cantidad de pruebas de intersección: http://www.realtimerendering.com/intersections.html

Si desea obtener más información sobre las pruebas de intersección, ésta es la biblia: Real-Time Collision Detection (Amazon)

EDIT: el algoritmo en este paper ("un eficiente y robusto Ray-Caja de empalme algoritmo", Amy Williams y Steve Barrus y R. Keith Morley y Peter Shirley; Diario de gráficos, GPU , un nd herramientas de juego, vol. 10 (1), 49-54, 2005) parece especialmente conciso y viene con el código fuente (C++) también.

Answer 2

Puede representar su cuadro delimitador como 12 triángulos (2 para cada una de las 6 caras). Luego puede verificar la intersección de su línea con cada uno de ellos. Tengo una función de intersección línea-triángulo, pero fue escrita para mi propio motor de renderizado de software, no para D3D. Puedo intentar convertirlo, si necesitas el código.

Answer 3

Aquí hay una manera de hacerlo si quiere hacer los cálculos usted mismo: Interseque la línea con cada uno de los 6 planos creados por el cuadro delimitador.

La representación vectorial de la línea es X = B + t * D, donde B es una Tupla (x, y, z) del punto base (por ejemplo, su primer punto) y D es la dirección de la línea , nuevamente expresado como Tuple (dx, dy, dz). Obtienes la dirección restando uno de los puntos del otro, así que si tienes puntos P1 (x1, y1, z1) y P2 (x2, y2, z2), entonces D = P2 - P1 y B = P1, lo que significa D = (x2 - x1, y2-y1, z2-z1). Llamaremos a los elementos de este vector dx, dy y dz.

La representación paramétrica del plano es x + y + z = c. Por lo tanto, convierta su cuadro delimitador a esta representación y luego use la representación paramétrica de su línea, p. las tres ecuaciones x = x1 + t dx, y = y1 + t dy, z = y1 + t * dz, para sustituir x, y y z en la ecuación de su plano. Resuelve para t. Como cada uno de sus 6 planos va a ser paralelo al plano creado por 2 del eje, su problema se vuelve más fácil; por ejemplo, para el plano que es paralelo al plano creado por los ejes xey, la ecuación de su plano simplemente se convierte en z = c, mientras que c es la coordenada z de uno de los puntos del cuadro delimitador, y así sucesivamente.

Ahora use t para calcular el punto de intersección de la línea con su plano. (Si t es < 0 o> 1, entonces la línea se cruza EXTERIOR de P1-P2, si t> = 0 y t < = 1, entonces la línea se cruza con el avión en algún lugar entre P1 y P2)

Ahora' no he terminado todavía La ecuación del plano te da un plano, no un rectángulo, por lo que el punto de intersección con el plano podría estar FUERA de tu rectángulo, pero como ahora tienes las coordenadas de tu intersección (x = x1 + t * dx, etc.), puede ver fácilmente si ese punto está dentro del rectángulo de su cuadro delimitador. Su problema ahora se reduce para verificar si un punto en el espacio 2D está dentro de un rectángulo de cuadro delimitador, lo cual es trivial de verificar.

Por supuesto, lo primero que debe hacer si realmente utiliza esta solución es verificar si la línea también está alineada a lo largo de un eje porque en ese caso, su código de intersección se vuelve trivial y también soluciona el problema de la línea no se cruza con algunos planos, por ejemplonúmeros enormes o pequeños de t, tal vez incluso sobre o bajo flujo.

Apuesto a que hay formas más rápidas de hacerlo, pero funcionará.

Answer 4

Este es el código que parece estar funcionando, convertida de la respuesta de Greg S en C#:

bool CheckLineBox(Vector3 B1, Vector3 B2, Vector3 L1, Vector3 L2, ref Vector3 Hit) 
{ 
    if (L2.x < B1.x && L1.x < B1.x) return false; 
    if (L2.x > B2.x && L1.x > B2.x) return false; 
    if (L2.y < B1.y && L1.y < B1.y) return false; 
    if (L2.y > B2.y && L1.y > B2.y) return false; 
    if (L2.z < B1.z && L1.z < B1.z) return false; 
    if (L2.z > B2.z && L1.z > B2.z) return false; 
    if (L1.x > B1.x && L1.x < B2.x && 
     L1.y > B1.y && L1.y < B2.y && 
     L1.z > B1.z && L1.z < B2.z) 
    { 
     Hit = L1; 
     return true; 
    } 
    if ((GetIntersection(L1.x - B1.x, L2.x - B1.x, L1, L2, ref Hit) && InBox(Hit, B1, B2, 1)) 
     || (GetIntersection(L1.y - B1.y, L2.y - B1.y, L1, L2, ref Hit) && InBox(Hit, B1, B2, 2)) 
     || (GetIntersection(L1.z - B1.z, L2.z - B1.z, L1, L2, ref Hit) && InBox(Hit, B1, B2, 3)) 
     || (GetIntersection(L1.x - B2.x, L2.x - B2.x, L1, L2, ref Hit) && InBox(Hit, B1, B2, 1)) 
     || (GetIntersection(L1.y - B2.y, L2.y - B2.y, L1, L2, ref Hit) && InBox(Hit, B1, B2, 2)) 
     || (GetIntersection(L1.z - B2.z, L2.z - B2.z, L1, L2, ref Hit) && InBox(Hit, B1, B2, 3))) 
     return true; 

    return false; 
} 

bool GetIntersection(float fDst1, float fDst2, Vector3 P1, Vector3 P2, ref Vector3 Hit) 
{ 
    if ((fDst1 * fDst2) >= 0.0f) return false; 
    if (fDst1 == fDst2) return false; 
    Hit = P1 + (P2 - P1) * (-fDst1/(fDst2 - fDst1)); 
    return true; 
} 

bool InBox(Vector3 Hit, Vector3 B1, Vector3 B2, int Axis) 
{ 
    if (Axis == 1 && Hit.z > B1.z && Hit.z < B2.z && Hit.y > B1.y && Hit.y < B2.y) return true; 
    if (Axis == 2 && Hit.z > B1.z && Hit.z < B2.z && Hit.x > B1.x && Hit.x < B2.x) return true; 
    if (Axis == 3 && Hit.x > B1.x && Hit.x < B2.x && Hit.y > B1.y && Hit.y < B2.y) return true; 
    return false; 
} 

Answer 5

versión de JavaScript, basado en la respuesta SpikeX y glMatrix:

// all args are Vec3, Hit will be filled by this algo 
function checkLineBox(B1, B2, L1, L2, Hit) 
{ 
    if (L2[0] < B1[0] && L1[0] < B1[0]) return false; 
    if (L2[0] > B2[0] && L1[0] > B2[0]) return false; 
    if (L2[1] < B1[1] && L1[1] < B1[1]) return false; 
    if (L2[1] > B2[1] && L1[1] > B2[1]) return false; 
    if (L2[2] < B1[2] && L1[2] < B1[2]) return false; 
    if (L2[2] > B2[2] && L1[2] > B2[2]) return false; 
    if (L1[0] > B1[0] && L1[0] < B2[0] && 
     L1[1] > B1[1] && L1[1] < B2[1] && 
     L1[2] > B1[2] && L1[2] < B2[2]) 
    { 
     vec3.set(L1, Hit); 
     return true; 
    } 

    if ((getIntersection(L1[0] - B1[0], L2[0] - B1[0], L1, L2, Hit) && inBox(Hit, B1, B2, 1)) 
     || (getIntersection(L1[1] - B1[1], L2[1] - B1[1], L1, L2, Hit) && inBox(Hit, B1, B2, 2)) 
     || (getIntersection(L1[2] - B1[2], L2[2] - B1[2], L1, L2, Hit) && inBox(Hit, B1, B2, 3)) 
     || (getIntersection(L1[0] - B2[0], L2[0] - B2[0], L1, L2, Hit) && inBox(Hit, B1, B2, 1)) 
     || (getIntersection(L1[1] - B2[1], L2[1] - B2[1], L1, L2, Hit) && inBox(Hit, B1, B2, 2)) 
     || (getIntersection(L1[2] - B2[2], L2[2] - B2[2], L1, L2, Hit) && inBox(Hit, B1, B2, 3))) 
     return true; 

    return false; 
} 

var temp = vec3.create(); 
function getIntersection(fDst1, fDst2, P1, P2, Hit) 
{ 
    if ((fDst1 * fDst2) >= 0) return false; 
    if (fDst1 == fDst2) return false; 

    vec3.subtract(P2, P1, temp); 
    vec3.scale(temp, (-fDst1/(fDst2 - fDst1))); 
    vec3.add(temp, P1, Hit); 

    return true; 
} 

function inBox(Hit, B1, B2, Axis) 
{ 
    if (Axis == 1 && Hit[2] > B1[2] && Hit[2] < B2[2] && Hit[1] > B1[1] && Hit[1] < B2[1]) return true; 
    if (Axis == 2 && Hit[2] > B1[2] && Hit[2] < B2[2] && Hit[0] > B1[0] && Hit[0] < B2[0]) return true; 
    if (Axis == 3 && Hit[0] > B1[0] && Hit[0] < B2[0] && Hit[1] > B1[1] && Hit[1] < B2[1]) return true; 
    return false; 
}