algorithm - Ray-box Intersection Theory

3d raytracing

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 compruebo si el punto de intersección del plano está en la 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 esa cara de 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, mira la imagen:

La imagen muestra los rayos que salen del ojo de la cámara y 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

¿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 2

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

Answer 3

PointOnBoxFace debe ser una verificación bidimensional en lugar de tridimensional. Por ejemplo, si está probando contra el plano z = z_min , entonces solo debería necesitar comparar 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 prueba contra ese plano. Encuentra un punto de intersección de ( x , y , 0.999999999). Ahora, aunque y están dentro de los límites, z no es del todo correcto.

Answer 4

Aumentar las cosas con epsilon no es realmente una excelente 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ás intersecando el plano en x=x0 , y tu rayo va en dirección (rx,ry,rz) desde (0,0,0) , entonces el tiempo de intersección es t = x0/rx . Si t es negativo, ignóralo - vas por el otro lado. Si t es cero, debes decidir cómo manejar ese caso especial: si ya estás en un avión, ¿lo rebotas o lo atraviesas? 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 tienes exactamente las coordenadas donde golpeaste ese plano: 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 épsilon arbitrarios, si su rayo interseca su cubo y dónde lo hace, con la precisión posible con la aritmética de coma flotante.

Entonces solo necesitas tres funciones como la que ya obtuviste: una para probar si yz dentro de yz suponiendo que presionas x , y las correspondientes para xz y xy suponiendo que pulses y y z respectivamente.

Editar: el código agregado (muy detallado) muestra 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....
}

(Acabo de tipear esto, no lo compilé, así que ten cuidado con los errores.) (Editar: acaba de corregir un i -> first .)

De todos modos, el punto es que tratas las tres direcciones por separado, y pruebas para ver si el impacto ha ocurrido dentro del cuadro de la derecha en las coordenadas (u, v), donde (u, v) son (x, y), (x , z) o (y, z) según el plano que golpee.

Answer 5

EDITAR: Ignore esta respuesta (vea los comentarios a continuación donde se muestra de manera convincente el error de mis formas).

Está probando si el punto está dentro del volumen, pero el punto está en la periferia de ese volumen, por lo que puede encontrar que es una distancia "infinitesimal" fuera del volumen. Intente hacer crecer la caja con un pequeño epsilon, 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 convertir sus representaciones de bit en ints y comparar los enteros para un pequeño desplazamiento, 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 insegura puede lograr el mismo efecto. (Gracias a @Novox por sus comentarios, que me llevaron a una buena página explicando esta técnica en detalle).