El Ray Casting es la base metodológica para el modelado de sólidos y la representación de imágenes mediante CAD/CAM en 3D. Es esencialmente lo mismo que el trazado de rayos para gráficos de computadora, donde los rayos de luz virtuales se "lanzan" o "trazan" en su trayectoria desde el punto focal de una cámara a través de cada píxel en el 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] Consulte modelado de sólidos para obtener una descripción general amplia de los métodos de modelado de sólidos. Esta figura de la derecha muestra una junta universal modelada a partir de cilindros y bloques en un árbol binario utilizando el sistema de fundición de rayos de Roth en 1979.
Antes de la proyección de rayos (y el trazado de rayos), los algoritmos de gráficos por computadora proyectaban superficies o bordes (por ejemplo, líneas) desde el 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 del sistema de coordenadas homogéneo 3D (también conocida como proyección 3D , transformación afín o transformación proyectiva ( homografía )). Representar una imagen de esa manera es difícil de lograr con la eliminación oculta de superficies/bordes. Además, las siluetas de superficies curvas deben resolverse explícitamente, mientras que es un subproducto implícito de la proyección de rayos, por lo que no hay necesidad de resolverlo explícitamente cada vez que cambia la vista.
La proyección de rayos simplificó enormemente la representación de imágenes de objetos y escenas 3D porque una línea se transforma en una línea. Por lo tanto, en lugar de proyectar bordes y superficies curvas en la escena 3D al plano de la imagen 2D, las líneas transformadas (rayos) se intersecan con los objetos en la escena. Una transformación de coordenadas homogéneas se representa mediante una matriz 4x4. La técnica matemática es común en gráficos de 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 4x4, un punto se representa mediante [X, Y, Z, 1] y un vector de dirección se representa mediante [D x , D y , D z , 0]. (El cuarto término es para la traslación y no se aplica a los vectores de dirección).
El ray casting es el más básico de muchos algoritmos de renderizado de gráficos por computadora que utilizan el algoritmo geométrico de trazado de rayos . Los algoritmos de renderizado basados en el 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 ray casting proviene de calcular el color de la luz sin trazar recursivamente rayos adicionales que muestrean la radiancia incidente en el punto en el que incide el rayo. Esto elimina la posibilidad de representar con precisión los reflejos , las refracciones o la caída natural de las sombras ; sin embargo, todos estos elementos se pueden falsificar hasta cierto punto, mediante el uso creativo de mapas de textura u otros métodos. La alta velocidad de cálculo hizo que el ray casting fuera un método de renderizado útil en los primeros videojuegos 3D en tiempo real.
La idea detrás del ray casting es rastrear rayos desde el ojo, uno por píxel, y encontrar el objeto más cercano que bloquea el camino de ese rayo; piense en una imagen como una puerta 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. Usando las propiedades del material y el efecto de las luces en la escena, este algoritmo puede determinar el sombreado de este objeto. Se hace la suposición simplificadora de que si una superficie se enfrenta a una luz, la luz llegará a esa superficie y no será bloqueada ni en sombra. El sombreado de la superficie se calcula utilizando modelos de sombreado de gráficos de computadora 3D tradicionales. Una ventaja importante que ofrecía el ray casting sobre los algoritmos de línea de exploración más antiguos era su capacidad para tratar fácilmente con superficies y sólidos no planos, como conos y esferas . Si una superficie matemática puede ser intersecada por un rayo, se puede renderizar utilizando ray casting. Se pueden crear objetos elaborados utilizando técnicas de modelado de sólidos y renderizarlos fácilmente.
Del resumen del artículo "Ray Casting for Modeling Solids": Para visualizar y analizar los sólidos compuestos modelados, se proyectan rayos de luz virtuales como sondas. En virtud de su simplicidad, el ray casting es confiable y extensible. El problema matemático más difícil es encontrar puntos de intersección de líneas y superficies. Por lo tanto, superficies como planos, cuádricos, toros y probablemente incluso parches de superficie paramétricos pueden limitar los sólidos primitivos. La adecuación y eficiencia del ray casting son cuestiones que se abordan aquí. Una capacidad de generación rápida de imágenes para el modelado interactivo es el mayor desafío.
Los rayos de luz y la geometría de la cámara forman la base de todo el razonamiento geométrico. 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 ocular) y una matriz de píxeles cuadrados (o pantalla). Los rayos de luz rectos pasan a través de 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 intersecta el rayo del 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í, perpendiculares a la pantalla. Aunque la vista en perspectiva es natural para hacer fotografías, algunas aplicaciones necesitan rayos que puedan distribuirse uniformemente en el espacio.
Para facilitar el modelado, un sistema de coordenadas estándar típico para la cámara tiene la pantalla en el plano XY, la escena en el semiespacio +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 como un vector de dirección en forma parametrizada como un punto (X 0 , Y 0 , Z 0 ) y un vector de dirección (D x , D y , D z ). En esta forma, los puntos de la línea se ordenan y se accede a ellos mediante un único parámetro t. Para cada valor de t, se define un punto correspondiente (X, Y, Z) en la línea:
X = X 0 + t · D x Y = Y 0 + t · D y Z = Z 0 + t · D z
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:
Dist = √(D x 2 + Dy 2 + D z 2 )Dx = Dx / Dist .Dy = Dy / Dist .Dz = Dz / Dist .
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 entre el rayo y la 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 alejado. 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 intersecada. La superficie puede tener varias propiedades, como color, especularidad, transparencia con o sin refracción, translucidez, etc. El sólido asociado con la superficie puede tener sus propias propiedades físicas, como la densidad. Esto podría ser útil, por ejemplo, cuando un objeto consiste en un conjunto de diferentes materiales y el centro de masa general y los momentos de inercia son de interés.
Existen tres algoritmos que utilizan la proyección de rayos para realizar dibujos lineales, crear imágenes sombreadas y calcular volúmenes y otras propiedades físicas. Cada algoritmo, dado un modelo de cámara, proyecta un rayo por píxel en la pantalla. Para calcular el volumen, la resolución de la pantalla de píxeles que se debe utilizar depende de la precisión deseada de la solución. Para los dibujos lineales y el sombreado de imágenes, la resolución determina la calidad de la imagen.
DIBUJOS DE LÍNEAS . Para dibujar los bordes visibles de un sólido, genere un rayo por píxel que se mueva de arriba hacia abajo, 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 de superficie de rayo. Si la superficie visible en la ubicación del píxel (X, Y) es diferente a la superficie visible en el píxel (X-1, Y), muestre una línea vertical de un píxel de largo centrada en (X-½, Y). De manera similar, si la superficie visible en (X, Y) es diferente a la superficie visible en el píxel (X, Y-1), muestre una línea horizontal de un píxel de largo centrada en (X, Y-½). El dibujo resultante constará solo de bordes horizontales y verticales, luciendo irregular en resoluciones de curso.
El sistema de proyección de rayos de Roth generó las imágenes de los objetos sólidos de la derecha. Para la optimización se utilizaron cajas, límites dinámicos y coherencia. Para cada imagen, se tomó una muestra de la pantalla con una densidad de unos 100 x 100 rayos (es decir, 10 000) y se localizaron nuevos bordes mediante búsquedas binarias. Luego, se siguió el recorrido de todos los bordes proyectando rayos adicionales en incrementos de un píxel en los dos lados de los bordes. Cada imagen se dibujó en un tubo Tektronix con una resolución de 780 x 780.
IMÁGENES SOMBREADAS . Para crear una imagen sombreada, nuevamente se proyecta un rayo por píxel en la pantalla. Esta vez, sin embargo, se utiliza el puntero de superficie visible S[1] en cada píxel para acceder a la descripción de la superficie. A partir de esto, se calcula la normal de la superficie en el punto visible t [1]. El valor del píxel, la intensidad de luz que se puede visualizar, es proporcional al coseno del ángulo formado por la normal de la superficie y el vector de la fuente de luz a la superficie. Al procesar todos los píxeles de esta manera se produce una imagen de tipo raster de la escena.
CÁLCULO DEL VOLUMEN Y LOS 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”, al aproximar 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, éste se divide en elementos de volumen. Dos dimensiones de los paralelepípedos son constantes, definidas por el espaciado 2D 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 horizontales y verticales entre los rayos en la pantalla son S, entonces el volumen “detectado” por cada rayo es
S × S × ( t [2] - t [1] + t [4] - t [3] + ∙∙∙ + 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.)
L = √ ( Dx2 + Dy2 + Dz2 )
Cada ( t [ i ]- t [ i -1])/L es una longitud de un segmento de rayo que está dentro del sólido.
Esta figura muestra los paralelepípedos de un sólido modelado mediante proyección de rayos. Se trata de un modelo de cámara con proyección paralela.
Esta figura muestra un ejemplo de los operadores binarios en un árbol de composición utilizando + y – donde se evalúa un solo rayo.
El procedimiento de creación de rayos comienza en la parte superior del árbol de composición de sólidos, desciende recursivamente hasta la parte inferior, clasifica el rayo con respecto a los sólidos primitivos y luego regresa hacia arriba del á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.
La proyección de rayos es una herramienta de modelado natural para crear imágenes sombreadas. El sistema de proyección de rayos en escala de grises desarrollado por Scott Roth y Daniel Bass en GM Research Labs produjo imágenes en una pantalla de trama de color Ramtek alrededor de 1979. Para componer imágenes, el sistema proporcionaba al usuario los siguientes controles:
Esta figura muestra una escena de mesa con sombras de dos fuentes de luz puntuales.
Los algoritmos de sombreado que implementan todos los efectos realistas son costosos en términos computacionales, pero relativamente simples. Por ejemplo, la siguiente figura muestra los rayos adicionales que se podrían proyectar para una sola fuente de luz.
Para que se represente un solo píxel de la imagen, el algoritmo proyecta un rayo que comienza en el punto focal y determina que intersecta un rectángulo semitransparente y un círculo brillante. Luego, se debe proyectar un rayo adicional que comience en ese punto en la dirección simétricamente opuesta a la normal de la superficie en el punto de intersección del rayo con la superficie para determinar qué es visible en el reflejo reflejado. Ese rayo intersecta el triángulo que es opaco. Finalmente, se prueba cada punto de intersección del rayo con la superficie para determinar si está en sombra. El rayo "detector de sombras" se proyecta desde el punto de intersección del rayo con la superficie hasta la fuente de luz para determinar si alguna otra superficie bloquea ese camino.
Turner Whitted denomina a los rayos secundarios y adicionales “trazado de rayos recursivo” [5] . [Representar una sala de espejos sería costoso, por lo que es prudente limitar el número de recursiones]. 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. Luego, el rayo secundario se procesa como un rayo especular. Para obtener la fórmula de refracción y ejemplos gráficos, consulte el artículo de Whitted.
El lanzamiento de rayos se puede considerar un método de fuerza bruta para resolver problemas. El algoritmo mínimo es simple, en particular si se tienen en cuenta sus múltiples aplicaciones y su facilidad de uso, pero las aplicaciones suelen lanzar muchos rayos. Se pueden lanzar millones de rayos para reproducir un solo fotograma de una película animada. El tiempo de procesamiento de la computadora aumenta con la resolución de la pantalla y la cantidad de superficies/sólidos primitivos 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 de rayo y 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 los primitivos, probando las intersecciones de rayo y superficie y combinando las clasificaciones) incluso cuando el rayo claramente no alcanza al sólido. Para detectar un “error 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 del sólido. Pero 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 superiores e intermedios del árbol solo especifican operadores de combinación.
Al caracterizar con recintos el espacio que ocupan todos los sólidos, se obtiene un resumen abstracto de la información de posición y tamaño para todos los nodos del árbol. Luego, las pruebas rápidas de “rayo que interseca recinto” guían la búsqueda en la jerarquía. Cuando la prueba falla en un nodo intermedio del árbol, se garantiza que el rayo se clasificará como fuera del compuesto, por lo que no es necesario recorrer sus subárboles para investigar más.
La evaluación precisa del ahorro de costes que supone el uso de recintos es difícil porque depende de la distribución espacial de las primitivas (la distribución de la complejidad) y de la organización del árbol de composición. Las condiciones óptimas son:
Por el contrario, la peor condición es:
Las siguientes son diversas mejoras de rendimiento realizadas en el artículo de Roth sobre la proyección de rayos, pero otros han realizado mejoras considerables posteriormente.
Los bordes irregulares causados por el aliasing son un efecto indeseable de las técnicas de muestreo de puntos y es un problema clásico con los algoritmos de visualización de trama. Los bordes lineales o suavemente curvados aparecerán irregulares y son particularmente objetables en las animaciones porque el movimiento de la imagen hace que los bordes parezcan borrosos o parezcan pequeñas escaleras mecánicas en movimiento. Además, se pueden perder detalles de la escena más pequeños que el espaciado entre los rayos. Los bordes irregulares en un dibujo lineal se pueden suavizar mediante el seguimiento de bordes. El propósito de un algoritmo de este tipo es minimizar la cantidad 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 dibujaron de esta manera.
Para suavizar los bordes irregulares de una imagen sombreada con una precisión de subpíxeles, se deben proyectar rayos adicionales para obtener información sobre los bordes. (Consulte Supermuestreo para obtener un enfoque general). Los bordes se forman por la intersección de superficies o por el perfil de una superficie curva. Aplicando "Coherencia" como se describió anteriormente mediante búsqueda binaria, si la superficie visible en el píxel (X, Y) es diferente a la superficie visible en el píxel (X+1, Y), entonces se podría generar un rayo a mitad de camino entre ellos en (X+½, Y) y la superficie visible allí identificada. La distancia entre los puntos de muestra se podría subdividir aún más, pero la búsqueda no necesita ser profunda. La profundidad de búsqueda primaria para suavizar los bordes irregulares es una función del gradiente de intensidad a lo largo del borde. Dado que (1) el área de la imagen que contiene bordes suele ser un pequeño porcentaje del área total y (2) los rayos adicionales proyectados en las búsquedas binarias pueden estar limitados en profundidad (la de los primitivos visibles que forman los bordes), el costo de suavizar los bordes irregulares es asequible.
Para conocer la historia del ray casting, consulte el término trazado de rayos (gráficos) , ya que ambos son esencialmente la misma técnica con nombres diferentes. Scott Roth había inventado el término "ray casting" antes de haber oído hablar del "ray tracing". Además, el desarrollo del ray casting por parte de Scott Roth en GM Research Labs se produjo simultáneamente con el trabajo de trazado de rayos de Turner Whitted en Bell Labs.
En los primeros juegos en primera persona, se utilizaba el raycasting para renderizar de forma eficiente un mundo 3D a partir de un campo de juego 2D mediante un simple escaneo unidimensional sobre el ancho horizontal de la pantalla. [6] Los primeros juegos de disparos en primera persona utilizaban el raycasting 2D como técnica para crear un efecto 3D a partir de un mundo 2D. Si bien el mundo parece 3D, el jugador no puede mirar hacia arriba o hacia abajo o solo en ángulos limitados con distorsión de corte. [6] [7] Este estilo de renderizado elimina la necesidad de disparar un rayo por cada píxel en el cuadro como es el caso de 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 cuadro. Este estilo de renderizado también impone limitaciones en el tipo de renderizado que se puede realizar, por ejemplo, la clasificación de profundidad , pero el almacenamiento en búfer de profundidad no. Es decir, los polígonos deben estar completos uno delante o detrás del otro, no pueden superponerse parcialmente ni intersecarse.
El videojuego Wolfenstein 3D se construyó a partir de una cuadrícula de paredes de altura uniforme que se unían a pisos y techos de colores sólidos. Para dibujar el mundo, se trazó un solo rayo para cada columna de píxeles de la pantalla y se seleccionó una porción vertical de la textura de la pared y se escaló según el lugar del mundo en el que el rayo impacta en una pared y la distancia que recorre antes de hacerlo. [8]
El objetivo de los niveles basados en cuadrículas era doble: las colisiones entre rayos y paredes se pueden detectar más rápidamente, ya que los impactos potenciales se vuelven más predecibles y se reduce la sobrecarga de memoria. Sin embargo, la codificación de áreas muy abiertas requiere espacio adicional.
El juego ShadowCaster de Raven Software utiliza un motor mejorado basado en Wolfenstein con texturas de pisos y techos adicionales y alturas de pared variables.
El motor Voxel Space desarrollado por NovaLogic para los juegos Comanche trazó un rayo a través de cada columna de píxeles de la pantalla y probó cada rayo contra puntos en un mapa de alturas . Luego transformó cada elemento del mapa de alturas en una columna de píxeles, determinó cuáles son visibles (es decir, no han sido ocluidos por píxeles que se han dibujado al frente) y los dibujó con el color correspondiente del mapa de texturas. [9]
Juegos DOS posteriores como DOOM de id Software mantuvieron muchas de las restricciones de raycasting 2.5D para la velocidad, pero luego cambiaron a técnicas de renderizado alternativas (como BSP ), lo que hizo que ya no fueran motores de raycasting. [10]
En geometría computacional , el problema de proyección de rayos también se conoce como el problema de disparo de rayos y puede enunciarse 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 varias configuraciones: dimensión espacial, tipos de objetos, restricciones en los rayos de consulta, etc. [11] Una técnica es utilizar un octree de vóxeles dispersos .