Ray-box Intersection Theory

Question

Deseo determinar el punto de intersección entre un rayo y una caja. La caja se define por su coordenada 3D mínima y coordenada máxima 3D y el rayo se define por su origen y la dirección a la que apunta.

Actualmente, estoy formando un avión para cada cara de la caja y estoy cruzando el rayo con el avión. Si el rayo se cruza con el plano, entonces verifico si el punto de intersección está o no en la superficie de la caja. Si es así, verifico si es la intersección más cercana para este rayo y regreso la intersección más cercana.

La forma en que comprobar si el punto plano-intersección es en la propia superficie de la caja es a través de una función

bool PointOnBoxFace(R3Point point, R3Point corner1, R3Point corner2) 
{ 
    double min_x = min(corner1.X(), corner2.X()); 
    double max_x = max(corner1.X(), corner2.X()); 
    double min_y = min(corner1.Y(), corner2.Y()); 
    double max_y = max(corner1.Y(), corner2.Y()); 
    double min_z = min(corner1.Z(), corner2.Z()); 
    double max_z = max(corner1.Z(), corner2.Z()); 
    if(point.X() >= min_x && point.X() <= max_x && 
    point.Y() >= min_y && point.Y() <= max_y && 
    point.Z() >= min_z && point.Z() <= max_z) 
    return true; 

    return false; 
} 

donde corner1 es una esquina del rectángulo para que cara de la caja y corner2 es la esquina opuesta. Mi implementación funciona la mayor parte del tiempo, pero a veces me da una intersección incorrecta. Por favor, vea la imagen:

La imagen muestra rayos que vienen del ojo de la cámara y que golpean la superficie de la caja. Los otros rayos son las normales a la superficie de la caja. Se puede ver que el rayo en particular (en realidad se ve lo normal) sale de la "parte posterior" de la caja, mientras que lo normal debería aparecer desde la parte superior de la caja. Esto parece ser extraño, ya que hay muchos otros rayos que golpean la parte superior de la caja correctamente.

Me preguntaba si la forma en que estoy comprobando si el punto de intersección está en la caja es correcta o si debería usar algún otro algoritmo.

Gracias.

Answer 1

Aumentar las cosas por epsilon no es realmente una buena manera de hacerlo, ya que ahora tiene un borde de tamaño epsilon en el borde de su caja a través del cual pueden pasar los rayos. Así que te desharás de este conjunto de errores (relativamente común) y terminarás con otro conjunto (raro) de errores extraños.

Supongo que ya está imaginando que su rayo está viajando a cierta velocidad a lo largo de su vector y encuentra el momento de la intersección con cada plano. Entonces, por ejemplo, si está intersecando el plano en x=x0, y su rayo va en la dirección (rx,ry,rz) desde (0,0,0), entonces el tiempo de intersección es t = x0/rx. Si t es negativo, ignórelo - va por el otro camino. Si t es cero, debe decidir cómo manejar ese caso especial: si ya se encuentra en un avión, ¿lo rebotan o lo atraviesan? También es posible que desee manejar rx==0 como un caso especial (para que pueda golpear el borde de la caja).

De todos modos, ahora tiene exactamente las coordenadas donde golpeó ese avión: son (t*rx , t*ry , t*rz). Ahora puede leer si t*ry y t*rz están dentro del rectángulo en el que deben estar (es decir, entre el mínimo y el máximo para el cubo a lo largo de esos ejes). No prueba la coordenada x porque ya sabe que la golpea De nuevo, debe decidir si/cómo manejar las esquinas golpeadas como un caso especial. Además, ahora puede ordenar sus colisiones con las diversas superficies por tiempo y elegir la primera como punto de colisión.

Esto le permite calcular, sin recurrir a factores epsilon arbitrarios, si su rayo interseca su cubo y dónde se cruza, con la precisión posible con la aritmética de coma flotante.

lo que sólo tiene tres funciones como la que ya tienes: una para comprobar si se golpea dentro yz suponiendo que golpea x, y los correspondientes para xz y xy el supuesto de que se golpea y y z respectivamente.

---

Editar: Código añadió a (más detallados) muestran cómo hacer las pruebas de forma diferente para cada eje:

#define X_FACE 0 
#define Y_FACE 1 
#define Z_FACE 2 
#define MAX_FACE 4 

// true if we hit a box face, false otherwise 
bool hit_face(double uhit,double vhit, 
       double umin,double umax,double vmin,double vmax) 
{ 
    return (umin <= uhit && uhit <= umax && vmin <= vhit && vhit <= vmax); 
} 

// 0.0 if we missed, the time of impact otherwise 
double hit_box(double rx,double ry, double rz, 
       double min_x,double min_y,double min_z, 
       double max_x,double max_y,double max_z) 
{ 
    double times[6]; 
    bool hits[6]; 
    int faces[6]; 
    double t; 
    if (rx==0) { times[0] = times[1] = 0.0; } 
    else { 
    t = min_x/rx; 
    times[0] = t; faces[0] = X_FACE; 
    hits[0] = hit_box(t*ry , t*rz , min_y , max_y , min_z , max_z); 
    t = max_x/rx; 
    times[1] = t; faces[1] = X_FACE + MAX_FACE; 
    hits[1] = hit_box(t*ry , t*rz , min_y , max_y , min_z , max_z); 
    } 
    if (ry==0) { times[2] = times[3] = 0.0; } 
    else { 
    t = min_y/ry; 
    times[2] = t; faces[2] = Y_FACE; 
    hits[2] = hit_box(t*rx , t*rz , min_x , max_x , min_z , max_z); 
    t = max_y/ry; 
    times[3] = t; faces[3] = Y_FACE + MAX_FACE; 
    hits[3] = hit_box(t*rx , t*rz , min_x , max_x , min_z , max_z); 
    } 
    if (rz==0) { times[4] = times[5] = 0.0; } 
    else { 
    t = min_z/rz; 
    times[4] = t; faces[4] = Z_FACE; 
    hits[4] = hit_box(t*rx , t*ry , min_x , max_x , min_y , max_y); 
    t = max_z/rz; 
    times[5] = t; faces[5] = Z_FACE + MAX_FACE; 
    hits[5] = hit_box(t*rx , t*ry , min_x , max_x , min_y , max_y); 
    } 
    int first = 6; 
    t = 0.0; 
    for (int i=0 ; i<6 ; i++) { 
    if (times[i] > 0.0 && (times[i]<t || t==0.0)) { 
     first = i; 
     t = times[i]; 
    } 
    } 
    if (first>5) return 0.0; // Found nothing 
    else return times[first]; // Probably want hits[first] and faces[first] also.... 
} 

(me acaba de escribir esto, no compilarlo, así que ten cuidado de los bichos.) (Edit: simplemente ha corregido un i ->first)

de todos modos, el punto es que el tratamiento de las tres direcciones por separado, y la prueba para ver si se ha producido el impacto en el cuadro de la derecha de (u, v). coordenadas, donde (u, v) son cualquiera (x , y), (x, z), o (y, z) dependiendo del avión que golpee.

Answer 2

El código se ve bien. Intenta encontrar este rayo en particular y depurarlo.

Answer 3

EDITAR: Ignorar esta respuesta (ver comentarios a continuación, donde estoy bastante convincentemente demostrado el error de mis formas).

Está comprobando si el punto está dentro del volumen, pero el punto está en la periferia de ese volumen, por lo que puede encontrar que se trata de una distancia "infinitesimal" fuera del volumen. Intentar cultivar la caja por una pequeña épsilon, por ejemplo:

double epsilon = 1e-10; // Depends the scale of things in your code. 
double min_x = min(corner1.X(), corner2.X()) - epsilon; 
double max_x = max(corner1.X(), corner2.X()) + epsilon; 
double min_y = min(corner1.Y(), corner2.Y()) - epsilon; 
... 

Técnicamente, la forma correcta de comparar números casi iguales es para emitir sus representaciones de bits a enteros y comparar los números enteros por alguna pequeña compensación, por ejemplo, en C :

#define EPSILON 10 /* some small int; tune to suit */ 
int almostequal(double a, double b) { 
    return llabs(*(long long*)&a - *(long long*)&b) < EPSILON; 
} 

por supuesto, esto no es tan fácil en C#, pero tal vez la semántica inseguras puede lograr el mismo efecto. (Gracias a @Novox por sus comentarios, que me llevaron a un agradable page explicando esta técnica en detalle.)

Answer 4

¿Podría ser que ese rayo termine pasando exactamente por el borde de la caja? Los errores de redondeo de punto flotante pueden hacer que no se vean tanto en la cara derecha como en la cara posterior.

Answer 5

PointOnBoxFace debe ser una verificación bidimensional en lugar de tridimensional. Por ejemplo, si está probando en el plano z = z_min, solo debe comparar x y y con sus respectivos límites. Ya has descubierto que la coordenada z es correcta. La precisión del punto flotante es probable que lo haga tropezar mientras "vuelve a verificar" la tercera coordenada.

Por ejemplo, si z_min es 1.0, primero pruebe en ese plano. Encuentra un punto de intersección de (x, y, 0.999999999). Ahora, aunque x y y están dentro de los límites, z no es del todo correcto.