Ray casting
# Ray casting

Ray casting hace referencia al uso de la intersección rayo-superficie para solucionar una variedad de problemas en gráficos por ordenador y geometría computacional. El término fue introducido en gráficos por computadora en un artículo publicado por Scott Roth en 1982 para describir un método de renderización de modelos de geometría constructiva de sólidos.

Ray casting puede referirse a una variedad de problemas y técnicas:

A pesar de que "ray tracing" y "ray casting" fueron a menudo utilizados indistintamente en literatura temprana de gráficos por computadora, el empleo más reciente de dichos términos intenta diferenciarlos. La distinción radica en que ray casting es un algoritmo de renderizado que nunca traza recursivamente rayos secundarios, mientras que otros métodos de renderizado basados en ray tracing tienden a hacerlo.

## Concepto

El Ray casting es el más básico de muchos algoritmos de renderización de gráficos por computadora que usan el algoritmo geométrico de ray tracing. Los algoritmos basados en ray tracing operan en orden de imagen para renderizar escenas tridimensionales a imágenes bidimensionales. Los rayos geométricos son trazados desde el ojo del observador (trazado hacia atrás) para calcular la radiancia que viaja hacia el observador en la dirección del rayo. La rapidez y simplicidad del trazado de los rayos provienen de computar el color de la luz sin trazar recursivamente rayos adicionales para obtener la radiancia incidente en el punto donde el rayo intercepta. Esto elimina la posibilidad de renderizar con exactitud las reflexiones, refracciones, y las sombras. Aun así todos estos elementos pueden ser simulados en un cierto grado, con el uso ingenioso de mapas de textura u otros métodos. La velocidad de cómputo del ray casting lo convirtió en un método práctico de renderizado para los primeros videojuegos de 3D con renderización de escenas en tiempo real.

En la naturaleza, una fuente de luz emite un rayo de luz que viaja eventualmente hacia una superficie que interrumpe su trayectoria. Uno puede figurarse dicho "rayo" como un flujo de fotones que viajan a lo largo del mismo camino. Al llegar a este punto, cualquier combinación de tres cosas podría pasar con la luz del rayo: absorción, reflexión, y refracción. La superficie puede reflejar toda o parte del rayo de luz, en una o varias direcciones; pudiendo incluso absorber parte del mismo, resultando esto en una pérdida de intensidad de la luz reflejada y/o refractada. Si la superficie posee propiedades de transparencia o es traslúcida, ella refracta una porción de la luz que viaja dentro de la misma en una dirección, absorbiendo a su vez parte del espectro (y posiblemente alterando el color). Para el cómputo de la luz absorbida, reflejada y refractada no debe considerarse más de la propia luz que llega a la superfiacie. Una superficie no puede, por ejemplo, reflejar el 66% de un rayo de luz y refractar el 50% del mismo, ya que entre los dos sumarían 116%. En este punto los rayos reflejados y/o refractados pueden golpear otras superficies, momento en donde sus propiedades de absorción, refracción, y reflectantes son recalculadas basándose en los rayos incidentes. Algunos de estos rayos viajan de tal manera que interceptan nuestros ojos, haciendo posible que veamos la escena, así que contribuyen con la renderización final de la imagen. Entonces para aminorar el cómputo, tan sólo una fracción de los rayos son considerados, en este caso, los que llegan al observador.

El primer algoritmo ray casting usado para renderizar fue presentado por Arthur Appel en 1968. La idea detrás de ray casting es trazar rayos desde el observador, uno por pixel, y encontrar el objeto más cercano que interrumpe la trayectoria del mismo. Usando las propiedades de los materiales y el efecto de las luces en la escena, este algoritmo puede determinar el sombreado de este objeto. Por la hipótesis de simplificación podemos decir que si una superficie está orientada hacia una fuente de luz y no hay ningún objeto en su trayectoria, la luz alcanzará esa superficie y no será bloqueada o sombreada. El sombreado de la superficie es calculado usando los modelos tradicionales de sombreado de gráficos por computadora en 3D. Una importante ventaja del ray casting que resalta por encima de los scanline-rendering fue su habilidad de lidiar fácilmente con superficies no planas y sólidos, como conos y esferas. Si una superficie matemática puede ser interceptada por un rayo, esta puede ser renderizada por ray casting. Modelos más complejos pueden ser creados usando técnicas de modelización de sólidos y ser fácilmente renderizados.

Un uso temprano del algoritmo de renderización ray casting de Appel fue hecho por El Grupo de Aplicaciones Matemáticas, Inc., (MAGI) de Elmsford, Nueva York.

## Trazado hacia adelante y hacia atrás

Cuando el trazado de los rayos se implanta de forma que emule el viaje natural de los fotones, se trata del trazado hacia adelante. El trazado de rayos hacia adelante es teóricamente un método válido. Ocurre, sin embargo, que muchos fotones que salen de la lámpara nunca llegan al observador, es decir, que no juegan papel alguno en la construcción de la imagen. Dado que computacionalmente es muy caro trazar rayos que no sirven de nada, es necesario encontrar una solución a este problema. La clave para evitar el coste que representa el cálculo inútil está en invertir el recorrido de los fotones.

Si un fotón llega al ojo del observador, necesariamente ha tenido que cruzar la pantalla siguiendo la dirección del rayo. Entonces, si se trazan exclusivamente los rayos de luz que parten del punto de visión, a través de los píxeles de la pantalla hacia el espacio vectorial (conocidos como rayos primarios), nos aseguramos de que el sistema gráfico trabaje únicamente con los rayos útiles. Cuando el trazado de rayos se realiza de esta forma, se trata del trazado hacia atrás. Dado el ahorro de cálculos que implica el invertir el recorrido de los fotones, el trazado de rayos hacia atrás es el procedimiento utilizado.

## Fases en el algoritmo de ray casting

Siguiendo la pista de los fotones partiendo del punto de visión hacia los objetos y fuentes de luz, los pasos que ha de dar el algoritmo de ray casting son los siguientes:

Paso 1:

Paso 2:

Paso 3:

El trazado de un rayo cualquiera finaliza pintando el píxel cruzado por el rayo con el color e intensidad de la luz que llega al observador. Si por cada píxel de la pantalla se efectúan los pasos anteriores, al finalizar tendremos en la pantalla la imagen que ve el observador.

## Ray casting en videojuegos

### Wolfenstein 3-D

El mundo en Wolfenstein 3-D está construido de una cuadrícula de paredes con altura uniforme encontradas en pisos unicolor y techos. Para dibujar el mundo, un solo rayo es trazado por cada columna de píxeles de pantalla y un trozo vertical de textura de pared es seleccionado y escalado según donde en el mundo el rayo intercepta una pared y qué tan lejos viaja antes de hacerlo.

### Serie Comanche

El motor de Voxel Space desarrollado por NovaLogic para los Comanche games traza un rayo a través de cada columna de píxeles de la pantalla y prueba cada rayo contra los puntos en un mapa de alturas. Entonces transforma cada elemento del mapa a una columna de píxeles, determina cuáles son visibles y los dibuja con el color correspondiente del mapa de textura.

## Relación con la geometría computacional

En geometría computacional, el problema de ray casting es también conocido como el problema de lanzamiento del rayo y puede ser presentado como el siguiente problema de consulta: Dado un conjunto de objetos en d-espacio dimensional, preprocesarlos en una estructura de datos de modo que para cada rayo de consulta, el primer objeto interceptado por el rayo pueda ser encontrado rápidamente. El problema ha sido investigado para varias configuraciones: dimensión espacial, tipos de objetos, restricciones sobre los rayos de consulta, etc. Una técnica es utilizar un sparse voxel octree.

