Ray casting

El trazado de rayos es la base metodológica para el modelado sólido CAD/CAM 3D y la renderización de imágenes. Es esencialmente lo mismo que el trazado de rayos en gráficos por computadora, donde rayos de luz virtuales se "proyectan" o "trazan" a lo largo de su trayectoria desde el punto focal de una cámara a través de cada píxel del sensor de la cámara para determinar qué es visible a lo largo del rayo en la escena 3D.

El término "Ray Casting" fue introducido por Scott Roth mientras trabajaba en los Laboratorios de Investigación de General Motors entre 1978 y 1980. Su artículo, "Ray Casting for Modeling Solids" ^{[ 1 ]} , describe objetos sólidos modelados mediante la combinación de sólidos primitivos , como bloques y cilindros, utilizando los operadores de conjunto unión (+), intersección (&) y diferencia (−). La idea general de utilizar estos operadores binarios para el modelado de sólidos se debe en gran medida al grupo de modelado geométrico de Voelcker y Requicha en la Universidad de Rochester. ^{[ 2 ] [ 3 ]}

Antes del trazado de rayos (ray casting), los algoritmos de gráficos por computadora proyectaban superficies o aristas (por ejemplo, líneas) del mundo 3D al plano de la imagen, donde se debía aplicar la lógica de visibilidad. La proyección del mundo al plano de la imagen es una transformación de sistema de coordenadas homogéneas 3D, también conocida como proyección 3D , transformación afín o transformación proyectiva ( homografía ). Renderizar una imagen de esta manera es difícil de lograr con la eliminación de superficies/aristas ocultas. Además, las siluetas de superficies curvas deben resolverse explícitamente, mientras que son un subproducto implícito del trazado de rayos, por lo que no hay necesidad de resolverlas explícitamente cada vez que cambia la vista.

El trazado de rayos simplificó enormemente la representación de imágenes de objetos y escenas 3D, ya que una línea se transforma en otra. Así, en lugar de proyectar bordes y superficies curvas de la escena 3D al plano de la imagen 2D, las líneas transformadas (rayos) se intersecan con los objetos de la escena. Una transformación de coordenadas homogénea se representa mediante una matriz de 4×4. Esta técnica matemática es común en gráficos por computadora y modelado geométrico . ^{[ 4 ]} Una transformación incluye rotaciones alrededor de los tres ejes, escalado independiente a lo largo de los ejes, traslaciones en 3D e incluso sesgo. Las transformaciones se concatenan fácilmente mediante aritmética matricial. Para su uso con una matriz de 4×4, un punto se representa mediante _{[ X} , Y , Z , 1 ] y un vector de dirección mediante [ Dx , Dy _, Dz , 0] . (El cuarto término corresponde a la traslación, que no se aplica a los vectores de dirección) .

El trazado de rayos es el más básico de los numerosos algoritmos de renderizado de gráficos por computadora que utilizan el algoritmo geométrico de trazado de rayos . Los algoritmos de renderizado basados ​​en trazado de rayos operan en orden de imagen para renderizar escenas tridimensionales en imágenes bidimensionales. Los rayos geométricos se trazan desde el ojo del observador para muestrear la luz ( radiancia ) que viaja hacia el observador desde la dirección del rayo. La velocidad y simplicidad del trazado de rayos provienen del cálculo del color de la luz sin trazar recursivamente rayos adicionales que muestreen la radiancia incidente en el punto donde impactó el rayo. Esto elimina la posibilidad de renderizar con precisión reflejos , refracciones o la atenuación natural de las sombras ; sin embargo, todos estos elementos pueden simularse hasta cierto punto, mediante el uso creativo de mapas de textura u otros métodos. La alta velocidad de cálculo hizo del trazado de rayos un método de renderizado práctico en los primeros videojuegos 3D en tiempo real .

La idea detrás del trazado de rayos es trazar rayos desde el ojo, uno por píxel, y encontrar el objeto más cercano que bloquea la trayectoria de ese rayo; piense en una imagen como una mosquitera, donde cada cuadrado de la pantalla es un píxel. Este es entonces el objeto que el ojo ve a través de ese píxel. Utilizando las propiedades del material y el efecto de las luces en la escena, este algoritmo puede determinar el sombreado de este objeto. Se parte de la suposición simplificadora de que si una superficie está frente a una luz, la luz llegará a esa superficie y no será bloqueada ni quedará en sombra. El sombreado de la superficie se calcula utilizando modelos de sombreado tradicionales de gráficos por computadora 3D . Una ventaja importante que ofrecía el trazado de rayos sobre los algoritmos de escaneo de líneas más antiguos era su capacidad para manejar fácilmente superficies y sólidos no planos, como conos y esferas . Si una superficie matemática puede ser intersectada por un rayo, se puede renderizar utilizando el trazado de rayos. Se pueden crear objetos complejos utilizando técnicas de modelado sólido y renderizarlos fácilmente.

Del resumen del artículo "Ray Casting para modelado de sólidos": ^{[ 5 ]}

Para visualizar y analizar los sólidos compuestos modelados, se proyectan rayos de luz virtuales a modo de sondas. Gracias a su simplicidad, la proyección de rayos es fiable y extensible. El problema matemático más complejo reside en encontrar los puntos de intersección entre líneas y superficies. Así, superficies como planos, cuádricas, toros e incluso parches de superficie paramétricos pueden delimitar los sólidos primitivos. La idoneidad y la eficiencia de la proyección de rayos son cuestiones que se abordan aquí. El mayor reto consiste en lograr una rápida generación de imágenes para el modelado interactivo.

Los rayos de luz y la geometría de la cámara constituyen la base de todo el razonamiento geométrico aquí presentado. Esta figura muestra un modelo de cámara estenopeica para el efecto de perspectiva en el procesamiento de imágenes y un modelo de cámara paralela para el análisis de masas. El modelo simple de cámara estenopeica consta de un punto focal (o punto de visión) y una matriz de píxeles cuadrada (o pantalla). Los rayos de luz rectos atraviesan la matriz de píxeles para conectar el punto focal con la escena, un rayo por píxel. Para sombrear las imágenes, se miden las intensidades de los rayos y se almacenan como píxeles. La superficie reflectante responsable del valor de un píxel interseca el rayo de dicho píxel.

Cuando la distancia focal, es decir, la distancia entre el punto focal y la pantalla, es infinita, la vista se denomina "paralela" porque todos los rayos de luz son paralelos entre sí y perpendiculares a la pantalla. Si bien la perspectiva es la forma natural de tomar fotografías, algunas aplicaciones requieren rayos que puedan distribuirse uniformemente en el espacio.

Modelo conceptual

Para facilitar el modelado, un sistema de coordenadas estándar típico para la cámara tiene la pantalla en el plano X-Y, la escena en el semiplano +Z y el punto focal en el eje −Z.

Un rayo es simplemente una línea recta en el espacio 3D del modelo de _la cámara. Se define mejor en forma parametrizada como un vector de puntos (X₀, Y₀ , _Z₀ ) y un vector de dirección (Dx, Dy, Dz ) _. En _esta forma _, los puntos de la línea se ordenan y se acceden mediante un único parámetro t . Para cada valor de t _, se define un punto correspondiente ( X , Y , Z ) en la línea:

$${\displaystyle {\begin{aligned}X&=X_{0}+t\cdot D_{x}\\Y&=Y_{0}+t\cdot D_{y}\\Z&=Z_{0}+t\cdot D_{z}\end{aligned}}}$$

Si el vector está normalizado, entonces el parámetro t es la distancia a lo largo de la línea. El vector se puede normalizar fácilmente con el siguiente cálculo:

$${\displaystyle {\begin{aligned}{\text{dist}}&={\sqrt {D_{x}^{2}+D_{y}^{2}+D_{z}^{2}}}\\D_{x}^{'}&=D_{x}\ /{\text{ dist}}\\D_{y}^{'}&=D_{y}\ /{\text{ dist}}\\D_{z}^{'}&=D_{z}\ /{\text{ dist}}\end{aligned}}}$$

Dadas las definiciones geométricas de los objetos, cada uno delimitado por una o más superficies, el resultado de calcular la intersección de un rayo con todas las superficies delimitadas en la pantalla se define mediante dos matrices:

Parámetros del rayo: t [1], t [2], …, t [ n ]

Punteros de superficie: S [1], S [2], …, S [ n ]

Donde n es el número de intersecciones rayo-superficie. La lista ordenada de parámetros del rayo, t [ i ] , denota los puntos de entrada y salida. El rayo entra en un sólido en el punto t [1] , sale en t [2] , entra en un sólido en t [3] , etc. El punto t [1] es el más cercano a la cámara y t [ n ] es el más lejano.

En asociación con los parámetros del rayo, los punteros de superficie contienen una dirección única para la información de la superficie intersectada. La superficie puede tener diversas propiedades, como color, especularidad, transparencia con o sin refracción, translucidez, etc. El sólido asociado a la superficie puede tener sus propias propiedades físicas, como la densidad. Esto podría ser útil, por ejemplo, cuando un objeto está compuesto por un conjunto de diferentes materiales y interesa conocer su centro de masa y sus momentos de inercia.

Tres algoritmos que utilizan el trazado de rayos se emplean para crear dibujos lineales, generar imágenes sombreadas y calcular volúmenes y otras propiedades físicas. Cada algoritmo, a partir de un modelo de cámara, proyecta un rayo por píxel en la pantalla. Para calcular el volumen, la resolución de la pantalla depende de la precisión deseada. En el caso de los dibujos lineales y el sombreado de imágenes, la resolución determina la calidad de la imagen.

Dibujos lineales

Para dibujar los bordes visibles de un sólido, genere un rayo por píxel que se mueva de arriba abajo y de izquierda a derecha en la pantalla. Evalúe cada rayo para identificar la superficie visible S [1] , el primer puntero de superficie en la lista ordenada de intersecciones rayo-superficie. Si la superficie visible en la posición del píxel ( X , Y ) es diferente de la superficie visible en el píxel ( X − 1, Y ) , muestre una línea vertical de un píxel de longitud centrada en ( X − ½, Y ) . De manera similar, si la superficie visible en ( X , Y ) es diferente de la superficie visible en el píxel ( X , Y − 1) , muestre una línea horizontal de un píxel de longitud centrada en ( X , Y − ½) . El dibujo resultante consistirá únicamente en bordes horizontales y verticales, con apariencia dentada en resoluciones bajas.

El sistema de trazado de rayos de Roth generó las imágenes de los objetos sólidos de la derecha. Para la optimización se utilizaron delimitación de cajas, delimitación dinámica y coherencia. Para cada imagen, la pantalla se muestreó con una densidad de aproximadamente 100 × 100 (es decir, 10 000) rayos y se localizaron nuevos bordes mediante búsquedas binarias. A continuación, se trazaron rayos adicionales a intervalos de un píxel a ambos lados de los bordes, siguiendo todos los bordes. Cada imagen se dibujó en un tubo Tektronix con una resolución de 780 × 780.

Cálculo de volumen y momentos de inercia

El volumen (y propiedades similares) de un sólido delimitado por superficies curvas se calcula fácilmente mediante el método de integración de “sumas aproximadas”, aproximando el sólido con un conjunto de paralelepípedos rectangulares. Esto se logra tomando una imagen “en profundidad” del sólido en una vista paralela. Al proyectar rayos a través de la pantalla hacia el sólido, este se divide en elementos de volumen. Dos dimensiones de los paralelepípedos son constantes, definidas por el espaciado bidimensional de los rayos en la pantalla. La tercera dimensión es variable, definida por el punto de entrada y salida calculado. Específicamente, si las distancias horizontal y vertical entre los rayos en la pantalla son S , entonces el volumen “detectado” por cada rayo es:

$${\displaystyle S\times S\times {\frac {t[2]-t[1]+t[4]-t[3]+\ldots +t[n]-t[n-1]}{L}}}$$

donde L se define como la longitud del vector de dirección. (Si ya está normalizado, es igual a 1).

$${\displaystyle L={\sqrt {D_{x}^{2}+D_{y}^{2}+D_{z}^{2}}}}$$

Cada${\displaystyle {\tfrac {t[i]\ -\ t[i-1]}{L}}}$ es la longitud de un segmento de rayo que se encuentra dentro del sólido.

Esta figura muestra los paralelepípedos de un sólido modelado mediante trazado de rayos. Se trata de un modelo de cámara de proyección paralela.

Esta figura muestra un ejemplo de los operadores binarios en un árbol de composición usando “+” y “−”, donde se evalúa un solo rayo.

El procedimiento de trazado de rayos comienza en la parte superior del árbol de composición sólida, desciende recursivamente hasta la parte inferior, clasifica el rayo con respecto a los sólidos primitivos y luego regresa hacia arriba en el árbol combinando las clasificaciones de los subárboles izquierdo y derecho.

Esta figura ilustra la combinación de las clasificaciones izquierda y derecha para los tres operadores binarios.

El trazado de rayos es una herramienta de modelado natural para crear imágenes sombreadas. El sistema de trazado de rayos en escala de grises desarrollado por Scott Roth y Daniel Bass en los Laboratorios de Investigación de GM producía imágenes en una pantalla raster a color Ramtek alrededor de 1979. Para componer imágenes, el sistema proporcionaba al usuario los siguientes controles:

• Vista
  • Dirección y posición de visualización
  • Distancia focal: perspectiva de ángulo de anchura a paralela
  • factor de zoom
• Iluminación
  • Número de fuentes de luz
  • Ubicación e intensidad de las luces
  • Opcionalmente, sombrear
  • Intensidades de la luz ambiental y del fondo
• Reflectancia superficial
  • % reflejado difusamente
  • % reflejado especularmente
  • % transmitido

Esta figura muestra una escena de mesa con sombras proyectadas por dos fuentes de luz puntuales.

Los algoritmos de sombreado que implementan todos los efectos realistas son computacionalmente costosos, pero relativamente sencillos. Por ejemplo, la siguiente figura muestra los rayos adicionales que podrían proyectarse para una sola fuente de luz.

Para renderizar un solo píxel de la imagen, el algoritmo lanza un rayo desde el punto focal y determina que interseca un rectángulo semitransparente y un círculo brillante. A continuación, se lanza otro rayo desde ese punto en la dirección simétricamente opuesta a la normal de la superficie en el punto de intersección rayo-superficie para determinar qué es visible en el reflejo. Este rayo interseca el triángulo, que es opaco. Finalmente, se comprueba si cada punto de intersección rayo-superficie está en sombra. El rayo de detección de sombras se lanza desde el punto de intersección rayo-superficie hasta la fuente de luz para determinar si alguna otra superficie bloquea esa trayectoria.

Turner Whitted denomina a los rayos secundarios y adicionales «trazado de rayos recursivo». ^{[ 6 ]} [Renderizar una habitación llena de espejos sería costoso, por lo que limitar el número de recursiones es prudente.] Whitted modeló la refracción para transparencias generando un rayo secundario desde el punto de la superficie visible en un ángulo determinado por el índice de refracción del sólido. El rayo secundario se procesa luego como un rayo especular. Para la fórmula de refracción y ejemplos gráficos, véase el artículo de Whitted.

El trazado de rayos se considera un método de fuerza bruta para resolver problemas. El algoritmo mínimo es sencillo, sobre todo teniendo en cuenta sus múltiples aplicaciones y su facilidad de uso, pero estas suelen generar muchos rayos. Se pueden generar millones de rayos para renderizar un solo fotograma de una película de animación. El tiempo de procesamiento informático aumenta con la resolución de la pantalla y el número de sólidos/superficies primitivas en la composición.

Al utilizar cuadros delimitadores mínimos alrededor de los sólidos en el árbol de composición, la búsqueda exhaustiva de una intersección rayo-sólido se asemeja a una búsqueda binaria eficiente . El algoritmo de fuerza bruta realiza una búsqueda exhaustiva porque siempre visita todos los nodos del árbol, transformando el rayo en los sistemas de coordenadas locales de las primitivas, comprobando las intersecciones rayo-superficie y combinando las clasificaciones, incluso cuando el rayo claramente no alcanza el sólido. Para detectar un "fallo claro", un algoritmo más rápido utiliza el árbol de composición binario como una representación jerárquica del espacio que ocupa la composición sólida. Sin embargo, toda la información de posición, forma y tamaño se almacena en las hojas del árbol donde residen los sólidos primitivos. Los nodos superior e intermedio del árbol solo especifican operadores de combinación.

Al caracterizar el espacio que ocupan todos los sólidos mediante contornos, se obtiene un resumen abstracto de la posición y el tamaño de cada nodo del árbol. A continuación, las pruebas rápidas de "intersección del rayo con el contorno" guían la búsqueda en la jerarquía. Si la prueba falla en un nodo intermedio del árbol, se garantiza que el rayo se encuentra fuera del conjunto, por lo que no es necesario recorrer sus subárboles para una investigación más exhaustiva.

Evaluar con precisión el ahorro de costos que supone el uso de recintos es difícil porque depende de la distribución espacial de las primitivas (la distribución de complejidad) y de la organización del árbol de composición. Las condiciones óptimas son:

• No hay recintos primitivos que se superpongan en el espacio.
• El árbol de composición está equilibrado y organizado de manera que los subsólidos cercanos en el espacio también estén cerca en el árbol.

Por el contrario, la peor situación es:

• Todos los recintos primitivos se superponen mutuamente.

Las siguientes son algunas de las mejoras de rendimiento introducidas en el artículo de Roth sobre el trazado de rayos, pero posteriormente otros autores han realizado mejoras considerables.

Eliminaciones tempranas

Si el operador en un nodo compuesto del árbol es − o & y el rayo se clasifica como fuera del subsólido izquierdo del compuesto, entonces el rayo se clasificará como fuera del compuesto independientemente de su clasificación con respecto al subsólido derecho. Por lo tanto, clasificar el rayo con respecto al subsólido derecho es innecesario y debe evitarse para mayor eficiencia.

Transformaciones

Al combinar inicialmente la transformación de pantalla a escena con la transformación de escena a local de la primitiva y almacenar las transformaciones de pantalla a local resultantes en las estructuras de datos de la primitiva, se elimina una transformación de rayo por cada intersección rayo-superficie.

Recursión

Dado un árbol de composición profundo, la recursión puede resultar costosa al combinarse con la asignación y liberación de memoria. La recursión se puede simular utilizando arreglos estáticos como pilas.

Límites dinámicos

Si solo se muestran los bordes visibles del sólido, el algoritmo de trazado de rayos puede delimitar dinámicamente el rayo para truncar la búsqueda. Es decir, tras detectar que un rayo interseca un subsólido, el algoritmo puede usar el punto de intersección más cercano a la pantalla para ajustar el límite de profundidad de la prueba de la "caja de intersecciones de rayos". Esto solo funciona para la parte + del árbol, comenzando desde la parte superior. Con – y &, las partes cercanas "dentro" del rayo pueden convertirse posteriormente en "fuera".

Coherencia

El principio de coherencia establece que las superficies visibles en dos píxeles vecinos tienen más probabilidades de ser iguales que diferentes. Los desarrolladores de gráficos por computadora y sistemas de visión han aplicado esta verdad empírica para mejorar la eficiencia y el rendimiento. En el caso de los dibujos lineales, el área de la imagen que contiene bordes suele ser mucho menor que el área total de la imagen, por lo que el trazado de rayos debe concentrarse alrededor de los bordes y no en las regiones abiertas. Esto se puede implementar eficazmente muestreando la pantalla con rayos de forma dispersa y luego localizando, cuando los rayos vecinos identifican superficies visibles diferentes, los bordes mediante búsquedas binarias.

Los bordes dentados causados ​​por el aliasing son un efecto indeseable de las técnicas de muestreo de puntos y un problema clásico de los algoritmos de visualización rasterizada. Los bordes lineales o con curvas suaves aparecerán dentados, lo que resulta especialmente molesto en las animaciones, ya que el movimiento de la imagen hace que los bordes parezcan borrosos o como pequeñas escaleras mecánicas en movimiento. Además, se pueden perder detalles de la escena más pequeños que el espacio entre los rayos. Los bordes dentados de un dibujo lineal se pueden suavizar mediante el seguimiento de bordes. El objetivo de este algoritmo es minimizar el número de líneas necesarias para dibujar la imagen con una precisión de un píxel. El resultado son bordes suaves. Los dibujos lineales anteriores se realizaron de esta manera.

Para suavizar los bordes dentados en una imagen sombreada con precisión subpíxel, se deben proyectar rayos adicionales para obtener información sobre los bordes. (Véase Supermuestreo para un enfoque general). Los bordes se forman por la intersección de superficies o por el perfil de una superficie curva. Aplicando la "coherencia" como se describió anteriormente mediante búsqueda binaria, si la superficie visible en el píxel ( X , Y ) es diferente de la superficie visible en el píxel ( X + 1, Y ) , se puede generar un rayo a medio camino entre ellas en ( X + ½, Y ) e identificar la superficie visible allí. La distancia entre los puntos de muestreo se puede subdividir aún más, pero la búsqueda no necesita ser profunda. La profundidad de búsqueda principal para suavizar los bordes dentados es una función del gradiente de intensidad a través del borde. El costo de suavizar los bordes dentados es asequible, ya que:

• El área de la imagen que contiene bordes suele ser un pequeño porcentaje del área total; y
• Los rayos adicionales emitidos en las búsquedas binarias pueden tener una profundidad limitada (la de las primitivas visibles que forman los bordes).

Para conocer la historia del trazado de rayos, consulte el apartado de gráficos por rayos, ya que ambas técnicas son esencialmente la misma, aunque con nombres diferentes. Scott Roth acuñó el término «trazado de rayos» antes de haber oído hablar de «ray tracing». Además, el desarrollo del trazado de rayos por parte de Scott Roth en los Laboratorios de Investigación de GM se produjo simultáneamente con el trabajo de trazado de rayos de Turner Whitted en los Laboratorios Bell.

En los primeros juegos en primera persona, el raycasting se usaba para renderizar eficientemente un mundo 3D a partir de un campo de juego 2D usando un escaneo unidimensional simple sobre el ancho horizontal de la pantalla. ^{[ 7 ]} Los primeros juegos de disparos en primera persona usaban el raycasting 2D como una técnica para crear un efecto 3D a partir de un mundo 2D. Si bien el mundo aparece en 3D, el jugador no puede mirar hacia arriba o hacia abajo, o solo en ángulos limitados con distorsión de cizallamiento. ^{[ 7 ] [ 8 ]} Este estilo de renderizado elimina la necesidad de disparar un rayo para cada píxel en el fotograma como es el caso con los motores modernos; una vez que se encuentra el punto de impacto, la distorsión de proyección se aplica a la textura de la superficie y se copia una columna vertical completa del resultado en el fotograma. Este estilo de renderizado también impone limitaciones en el tipo de renderizado que se puede realizar, por ejemplo, ordenación de profundidad pero no almacenamiento en búfer de profundidad . Es decir, los polígonos deben estar completos delante o detrás de otros, no pueden superponerse o intersecarse parcialmente.

En geometría computacional , el problema de trazado de rayos también se conoce como problema de disparo de rayos y puede plantearse como el siguiente problema de consulta: dado un conjunto de objetos en un espacio d -dimensional, preprocesarlos en una estructura de datos de modo que para cada rayo de consulta, el objeto inicial alcanzado por el rayo pueda encontrarse rápidamente. El problema se ha investigado para diversas configuraciones: dimensión del espacio, tipos de objetos, restricciones en los rayos de consulta, etc. ^{[ 12 ]} Una técnica es utilizar un octree de vóxeles disperso .

• Trazado de rayos (gráficos) Un algoritmo de trazado de rayos más sofisticado que considera la iluminación global.
• Mapeo de fotones
• Radiosidad (gráficos por computadora)
• trazado de rutas
• Lanzamiento de rayos volumétricos
• 2.5D

• Raycasting de planos en WebGL con código fuente
• Raycaster interactivo para Commodore 64 en 254 bytes (con código fuente)
• Raycaster interactivo para MSDOS en 64 bytes (con código fuente)