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.^[1]

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

El problema general de determinar el primer objeto interceptado por un rayo,^[2]

Una técnica para determinación de las caras ocultas (HSR por sus siglas en inglés), también conocida como determinación de las superficies visibles (VSD), basada en buscar la primera intersección de un rayo lanzado desde el observador a través de cada pixel de una imagen,

Un algoritmo no recursivo de renderización ray-tracing que sólo lanza rayos primarios, o

Un método directo de renderización de volúmenes llamado también volume ray casting, en que el rayo es "empujado a través" del objeto y el campo escalar en 3D de interés es muestreado a lo largo del rayo dentro del objeto. En este método no son expandidos rayos secundarios.^[3]

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[editar]

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.^[4] 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.^[5]

Trazado hacia adelante y hacia atrás[editar]

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[editar]

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:

Suponiendo que llegasen fotones al punto de visión siguiendo la trayectoria de un rayo dado, es preciso saber de dónde viene dicha luz, es decir, cuál es su punto de partida o procedencia. Los puntos de procedencia pueden encontrarse en las superficies de los objetos, en las fuentes de luz o ser luz de fondo, es decir, carente de un punto concreto de procedencia.

Paso 2:

En la fase anterior hemos supuesto que llega luz al punto de visión, pero no sabemos si realmente llega. Entonces, para una trayectoria dada, una vez que se conoce el punto de procedencia, se ha de averiguar si existen fotones que recorran el camino del rayo. Si al punto de procedencia llega luz desde de cualquier lugar, cabe la posibilidad de que parte de esa luz alcance también el punto de visión, siguiendo la trayectoria del rayo. Por tanto, es necesario averiguar si llega luz al punto de procedencia y, en caso afirmativo, cuánta llega y de qué color.

Paso 3:

Una vez que se conoce la intensidad y color de la luz que llega al punto de procedencia, la última cuestión que ha de resolver el algoritmo es averiguar qué cantidad de esta luz llega al observador, y cuál es su color.

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[editar]

Wolfenstein 3-D[editar]

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.^[6]

Serie Comanche[editar]

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.^[7]

Relación con la geometría computacional[editar]

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.^[8] Una técnica es utilizar un sparse voxel octree.

Véase también[editar]

Volumetric Ray casting
2.5D
Modo 7
Adaptive tile refresh
Sprite (Gráfico de ordenador)

Referencias[editar]

↑ Roth, Scott D. (February 1982), «Ray Casting for Modeling Solids», Computer Graphics and Image Processing 18 (2): 109-144, doi:10.1016/0146-664X(82)90169-1 .
↑ Woop, Sven; Schmittler, Jörg; Slusallek, Philipp (2005), «RPU: A Programmable Ray Processing Unit for Realtime Ray Tracing», Siggraph 2005 24 (3): 434, doi:10.1145/1073204.1073211 .
↑ Daniel Weiskopf (2006). GPU-Based Interactive Visualization Techniques. Springer Science & Business Media. p. 21. ISBN 978-3-540-33263-3.
↑ "Ray-tracing and other Rendering Approaches" Archivado el 17 de noviembre de 2018 en Wayback Machine. (PDF), lecture notes, MSc Computer Animation and Visual Effects, Jon Macey, University of Bournemouth
↑ Goldstein, R. A., and R. Nagel. 3-D visual simulation.
↑ Wolfenstein-style ray casting tutorial by F. Permadi
↑ Andre LaMothe.
↑ "Ray shooting, depth orders and hidden surface removal", by Mark de Berg, Springer-Verlag, 1993, ISBN 3-540-57020-9, 201 pp.