Intersección Rayo

De Codepixel

Enlaces genéricos de intersección

Sobre la robustez de la intersección rayo/triángulo

[editar] Intersección Rayo Box

  • siggraph : breve explicación en la web de siggraph.
  • flicode : mejorando el código anterior, para algunos casos de NaN.
  • gamedev : y un código de ejemplo.

[editar] Interseccion rayo / triángulo

En campos como el ray tracing o la simulación física, la intersección de rayo/triángulo es una rutina clave, donde se invierte mucha parte del tiempo de cálculo.

El primer método propuesto se basa en mirar las coordenadas baricéntricas de la intersección del rayo con el plano del triángulo, para comprobar posteriormente si están dentro del triángulo. Este método se describe en raytracing news de noviembre del 88, o en el libro Graphics Gems de Andrew Glassner, de 1990. Es fácil de entender y de derivar en papel con conocimientos básicos de matemáticas. Hay que tener cuidado con temas como puntos en el origen, triángulos de área 0, etc, ya que el código requiere de divisiones. Por ejemplo, recordad que los números en coma flotante en un ordenador incluyen el -0.0, comprobaciónes del tipo x > 0 se evalúan incorrectamente con el 0 negativo.

El segundo método, y el más usado en muchos campos, es el que denomina MT97, por los autores del paper Fast Minimum Storage Ray Triangle Intersection, publicado en 1997. Se basa en desplazar y rotar el rayo a un espacio de coordenadas donde u,v son las coordenadas baricéntricas. Lo más importante de este algoritmo es que no requiere de precálculos, ahorrando así mucha memoria y el proceso de previo de generar datos por cara. La función sólo necesita los 3 vértices del triángulo para devolver un resultado correcto. Es la opción más adecuada para soluciones "on the fly" de generación de triángulos.

El tercer método, es el propuesto en Interactive Rendering with Coherent Ray Tracing, por Ingo Ward en sus trabajos de ray tracing en tiempo real. El método se basa en que la baricéntricas de la intersección son las mismas aunque veamos el triángulo proyectado en un plano. El cálculo es un poco mayor que el MT97 si lo hacemos por fuerza bruta. Pero lo interesante es que podemos precalcular muchos datos necesarios en una tabla antes de realizar las intersecciones. Usando este tabla, se logra un aumento considerable de velocidad, a costa de más accesos a memoria. La estructura de aceleración ocupa unos 48 bytes por cara, que son unos aceptables 48Mb en una malla típica de 1M de triángulos. Pero lo que hace realmente potente este método es la facilidad con la que se adapta a SSE. Permitiendo así testear 4 rayos contra 1 mismo triángulo en pocos ciclos.

El cuarto método, propuesto en Ray-Triangle Intersection Algorithm for Modern CPU Architectures, usa coordenadas plücker, que es un sistema de coordenadas muy apropiado para resolver problemas de intersecciones. El problema es que, a parte de ser 6D, son costosas de calcular. Pero permiten elimitar divisiones costosas. Y funciona muy bien cuando comprobamos 4 rayos, o incluso paquetes de 4x4 rayos contra un triángulo. Ademas, si los triángulos comparten bordes, se pueden aprovechar cálculos entre cada testeo de intersección.

Otro método que es muy eficiente en tarjetas (porque ahorra tamaño en la estructura de aceleración) es el propuesto por Sven Woop, en A Ray Tracing Hardware Architecture for Dynamic Scenes

[editar] Ejemplo de Intersección MT97

código de ejemplo, basado en Fast Minimum Storage Ray Triangle Intersection


template <typename Real>
bool IntersectionTemplate<Real>::intersect_triangle(const RayTemplate<Real> & ray,
                   const PointTemplate<Real> & vert0,
				   const DirectionTemplate<Real> & edge1, const DirectionTemplate<Real> & edge2,
                   Real *t, Real *u, Real *v)
{
   DirectionTemplate<Real> tvec, pvec, qvec;
   Real det,inv_det;

   /* begin calculating determinant - also used to calculate U parameter */
   pvec = ray.GetDirection().Cross(edge2);

   /* if determinant is near zero, ray lies in plane of triangle */
   det = edge1.Dot(pvec);

#ifdef TEST_CULL           /* define TEST_CULL if culling is desired */
   if (det < Math::EPSILON())
   {
      return (false);
   }

   /* calculate distance from vert0 to ray origin */
   tvec = Direction ( vert0 , ray.GetOrigin() );

   /* calculate U parameter and test bounds */
   *u = tvec.Dot(pvec);
   if (*u < Real(0.0) || *u > det)
   {
      return (false);
   }

   /* prepare to test V parameter */
   qvec = tvec.Cross(edge1);

    /* calculate V parameter and test bounds */
   *v = ray.GetDirection().Dot(qvec);
   if (*v < Real(0.0) || *u + *v > det)
   {
      return (false);
   }

   /* calculate t, scale parameters, ray intersects triangle */
   *t = edge2.Dot(qvec);
   inv_det = Real(1.0) / det;
   *t *= inv_det;
   *u *= inv_det;
   *v *= inv_det;
#else                    /* the non-culling branch */
   if (det > -Math::NEARZERO() && det < Math::NEARZERO())
   {
     return (false);
   }
   inv_det = Real(1.0) / det;

   /* calculate distance from vert0 to ray origin */
   tvec = Direction ( vert0 , ray.GetOrigin() );

   /* calculate U parameter and test bounds */
   *u = tvec.Dot(pvec) * inv_det;
   if (*u < Real(0.0) || *u > Real(1.0) )
   {
     return (false);
   }

   /* prepare to test V parameter */
   qvec = tvec.Cross(edge1);

   /* calculate V parameter and test bounds */
   *v = ray.GetDirection().Dot(qvec) * inv_det;
   if (*v < Real(0.0) || ( (*u + *v) > Real(1.0)) )
   {
     return (false);
   }

   /* calculate t, ray intersects triangle */
   *t = edge2.Dot(qvec) * inv_det;
#endif
   return (true);
}
Herramientas personales