sábado, 9 de mayo de 2015

Ray-tracing algorithm

CC BY-SA 3.0 Hochgeladen von Withego
El algoritmo Trazador de rayos, más conocido en el argot técnico como "Ray-tracing", es un método de generación de imágenes tridimensionales con gran realismo, cuyo principio de  funcionamiento es el mismo que el producido por la luz natural. Mediante la ecuación de la línea recta que describe un rayo de luz que incide sobre una superficie es posible determinar las características físicas del objeto como el color, rugosidad, brillo y efectos como reflexión, refracción, absorción o fluorescencia. Así mismo, mediante ecuaciones similares a las  anteriores es posible definir la proyección de las sombras de cada objeto sobre una determinada superficie. Dicho algoritmo fue propuesto inicialmente por Turner Whitted en 1979, pero ya estaba basado en la técnica gráfica de determinación de superficies visibles de Arthur Appel denominado Ray Casting (1968).

Figura 1. Esquema básico del Ray-tracing. Henrik GFDL.






Como se muestra en la figura 1, la clave consiste en generar un rayo por cada elemento discreto del plano perpendicular al vector director existente entre la cámara y la esfera. Dicho de otro modo, es necesario determinar la intersección de cada rayo que parte del píxel del plano orientado por la cámara con la esfera. De esta forma podríamos definir la siguiente ecuación de la línea recta en paramétricas:

\[ r \equiv \begin{cases}x = x_0 + v_x t \\ y = y_0 + v_y t \\ z = z_0 + v_z t\end{cases} \]
 y la ecuación de la esfera en forma implícita:
 \[ (x - x_cx)^2 + (y-c_y)^2 + (z - c_z)^2 - R^2 = 0 \]

debemos sustituir la ecuación de la línea recta en la ecuación anterior, pero para ello es necesario utilizar la ecuación vectorial de la recta en la forma:

\[ p(t) = o + td \]

donde o equivaldría a un punto de la recta, por ejemplo (2,1,3), y d a su vector director, por ejemplo (7,2,-5).

Una vez obtenida la ecuación en forma vectorial procedemos a la sustitución en la ecuación de la esfera:

\[ (p - c) \cdot (p - c) - R^2 = 0 \]
Por lo tanto, cualquier punto p que satisfaga esta ecuación se encuentra en la esfera:
\[ (o  + td - c) \cdot ( o + td -c ) - R^2 = 0 \]
Simplificando tenemos que:
\[ ( d \cdot d) t^2 + 2d\cdot(o -c)t + (o-c)\cdot(o-c)-R^2=0 \]
De esta ecuación todo es conocido excepto el parámetro t, por lo que despejaremos la ecuación cuadrática del tipo:
\[ At^2 + Bt + C = 0\]
Cuya solución es:
\[ t = \frac{-B \pm \sqrt{B^2 - 4AC}}{2A}  \]
Donde obtenemos el discriminante: \[\Delta = B^2 - 4AC \] que nos indicará el número de soluciones de la ecuación. Si el discriminante es negativo, la raíz cuadrada es imaginaria y no existe intersección entre la esfera y la línea. Si el discriminante es positivo, existen dos soluciones: una donde el rayo entra en la esfera y otra donde el rayo abandona la esfera. Si el discriminante es 0, indica que el rayo impacta únicamente en un punto.

A partir del valor de t podemos determinar el lugar de colisión del rayo con la esfera mediante su sustitución en la ecuación de la recta.
 \[ t = \frac{-d \cdot (o-c)\pm\sqrt{(d \cdot (o-c))^2 - (d \cdot d)((o-c) \cdot (o-c)-R^2)}}{(d \cdot d)} \]

El algoritmo de "renderizado" tendría por tanto la siguiente forma:
Vector3 dir(0, 0, -1); // Vector director del rayo
Image im(500, 500); // Imagen de destino
// Itera sobre los píxeles de la superficie discreta
for (int i = 0; i < 500; i++)
   for (int j = 0; j < 500; j++)
   {
      tmax = 100000.Of;
      is_a_hit = false;
      Ray r(Vector3(i, j, 0), dir); // Rayo
      // itera sobre la lista de objetos
      for(int k = 0; k < objetos.size(); k++)
         if (objetos[k].hit(r, .00001f, tmax, rec)) 
         {
           tmax = rec.t;
           is_a_hit = true;
         }
         if (is_a_hit)
             im.set(i, j, rec.color); // Color del objeto
          else
             im.set(i, j, rgb(.2, .2, .2)); // Color de fondo
    }

im.writeImage();

donde rec es una estructura de datos que almacena información sobre la colisión: parámetro t, color, etc. Para la información del color se utilizan valores normalizados, es decir, comprendidos entre [0,1].

Finalmente, cabe decir que las desventajas de la técnica de Trazado de rayos es la dificultad para generar los fotogramas o frames por segundo en tiempo real eficiente en el contexto de la aplicación; aunque gracias a las nuevas tarjetas y GPU multinúcleo y los pipelines gráficos programables mediante shaders es posible alcanzar un nivel óptimo de frames (FPS). 

Según Wikipedia (1) «El algoritmo básico de trazado de rayos fue mejorado por Robert Cook (1985) para simular otros efectos en las imágenes mediante el muestreo estocástico usando un método de Montecarlo; entre estos efectos podemos citar el desenfoque por movimiento (blur motion), la profundidad de campo o el submuestreo para eliminar efectos de aliasing en la imagen resultante.
En la actualidad, el algoritmo de trazado de rayos es la base de otros algoritmos más complejos para síntesis de imágenes (mapeado de fotones, Metropolis, entre otros) que son capaces de simular efectos de iluminación global complejos como la mezcla de colores (color blending) o las cáusticas»

Fuentes bibliográficas:
  • Matemáticas I - Ed. Edelvives.
  • Whitted T. (1979) An improved illumination model for shaded display. Proceedings of the 6th annual conference on Computer Graphics and Interactive Techniques.
  • Realistic Ray-tracing. Pete Shirley y R. Keith Morley. Ed. A K Peters.
  • http://es.wikipedia.org/wiki/Trazado_de_rayos (1).