Ray casting es la base metodológica para el modelado de sólidos y la representación de imágenes 3D CAD/CAM. Es esencialmente lo mismo que el trazado de rayos para gráficos por computadora, donde se "proyectan" o "rastrean" rayos de luz virtuales 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 lo que es visible a lo largo del rayo en la imagen. 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 combinando 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 tenía que aplicar la lógica de visibilidad. La proyección del plano del mundo a imagen es una transformación del 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 esa manera es difícil de lograr con la eliminación de superficies o bordes ocultos. 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 es necesario resolverlo explícitamente cada vez que cambia la vista.
Ray Casting simplificó enormemente la representación de imágenes de objetos y escenas 3D porque una línea se transforma en una línea. Entonces, en lugar de proyectar bordes y superficies curvas en la escena 3D al plano de la imagen 2D, las líneas transformadas (rayos) se cruzan con los objetos de la escena. Una transformación de coordenadas homogénea está representada por una matriz de 4x4. La técnica matemática es común a los gráficos por computadora y al 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 usar con una matriz de 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 traducción y no se aplica a los vectores de dirección).
Ray casting es el más básico de muchos algoritmos de representación de gráficos por computadora que utilizan el algoritmo geométrico de trazado de rayos . Los algoritmos de renderizado basados en trazado de rayos funcionan en orden de imagen para renderizar escenas tridimensionales en imágenes bidimensionales. Los rayos geométricos se trazan desde el ojo del observador para tomar muestras de la luz ( radiancia ) que viaja hacia el observador desde la dirección del rayo. La velocidad y simplicidad de la proyección de rayos proviene de calcular el color de la luz sin rastrear recursivamente rayos adicionales que muestreen la radiancia incidente en el punto donde incide el rayo. Esto elimina la posibilidad de reproducir con precisión reflejos , 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 texturas u otros métodos. La alta velocidad de cálculo hizo que la proyección de rayos fuera un método de renderizado útil en los primeros videojuegos 3D en tiempo real.
La idea detrás de la proyección de rayos es rastrear los rayos del ojo, uno por píxel, y encontrar el objeto más cercano que bloquee el camino de ese rayo; piense en una imagen como una puerta mosquitera, en la que 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 hace la suposición simplificadora de que si una superficie se enfrenta a una luz, la luz llegará a esa superficie y no quedará bloqueada ni en sombra. El sombreado de la superficie se calcula utilizando modelos de sombreado de gráficos por computadora en 3D tradicionales. Una ventaja importante que ofrecía la fundición de rayos sobre los algoritmos de líneas de exploración más antiguos era su capacidad para tratar 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 representar mediante fundición de rayos. Se pueden crear objetos elaborados utilizando técnicas de modelado sólido y renderizarlos fácilmente.
Del resumen del artículo "Ray Casting for Modelling Solids": Para visualizar y analizar los sólidos compuestos modelados, se proyectan rayos de luz virtuales como sondas. Gracias a su simplicidad, la proyección de rayos es fiable y extensible. El problema matemático más difícil es encontrar puntos de intersección entre línea y superficie. Así, 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 de la proyección de rayos 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 aquí la base de todo razonamiento geométrico. Esta figura muestra un modelo de cámara estenopeica para efectos de perspectiva en el procesamiento de imágenes y un modelo de cámara paralela para análisis de masas. El modelo de cámara estenopeica simple 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 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, distancia entre el punto focal y la pantalla, es infinita, entonces la vista se llama "paralela" porque todos los rayos de luz son paralelos entre sí, perpendiculares a la pantalla. Aunque la vista en perspectiva es natural para tomar 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 medio espacio +Z y el punto focal en el eje -Z.
Un rayo es simplemente una línea recta en el espacio 3D del modelo de 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 ). De 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 recta:
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 + D y 2 + D z 2 )D x = D x / Dist.D y = D y / DistD z = D z / 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 del rayo-superficie. La lista ordenada de parámetros de rayos 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 de los rayos, los punteros de superficie contienen una dirección única para la información de la superficie intersectada. La superficie puede tener varias propiedades como color, especularidad, transparencia con/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 resultar útil, por ejemplo, cuando un objeto consta de un conjunto de diferentes materiales y el centro de masa general y los momentos de inercia son de interés.
Tres algoritmos que utilizan la proyección de rayos son hacer dibujos lineales, hacer 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 el volumen de cálculo, la resolución de la pantalla de píxeles a utilizar depende de la precisión deseada de la solución. Para dibujos lineales y 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 moviéndose 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 rayo-superficie. 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 de 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á únicamente de bordes horizontales y verticales, y se verá irregular en las resoluciones del 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 recintos de cajas, límites dinámicos y coherencia. Para cada imagen, se muestreó la pantalla con una densidad de aproximadamente 100x100 (por ejemplo, 10.000) rayos y se localizaron nuevos bordes mediante búsquedas binarias. Luego, se siguieron todos los bordes emitiendo 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 780x780.
IMÁGENES SOMBREADAS . Para hacer una imagen sombreada, vuelva a emitir un rayo por píxel en la pantalla. Esta vez, sin embargo, utilice el puntero de superficie visible S[1] en cada píxel para acceder a la descripción de la superficie. A partir de esto, calcule la normal a la superficie en el punto visible t [1]. El valor del píxel, la intensidad de la luz visualizable, es proporcional al coseno del ángulo formado por la normal a la superficie y el vector fuente de luz-superficie. Al procesar todos los píxeles de esta manera se produce una imagen de tipo rasterizado de la escena.
CÁLCULO DEL 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 fotografía "en profundidad" del sólido en una vista paralela. Proyectar rayos a través de la pantalla hacia el sólido divide el sólido 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-salida calculado. Específicamente, si las distancias horizontal y vertical entre los rayos en la pantalla es 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 dirección. (Si ya está normalizado, esto es igual a 1).
L = √(D x 2 + D y 2 + D z 2 )
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 fundición de rayos. Este es un uso del modelo de cámara de proyección paralela.
Esta figura muestra un ejemplo de operadores binarios en un árbol de composición usando + y – donde se evalúa un solo rayo.
El procedimiento de proyecció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 al á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.
Ray casting es una herramienta de modelado natural para hacer 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 rasterizada en color Ramtek alrededor de 1979. Para componer imágenes, el sistema proporcionó al usuario los siguientes controles:
Esta figura muestra una escena de mesa con sombras provenientes de dos fuentes de luz puntuales.
Los algoritmos de sombreado que implementan todos los efectos realistas son costosos desde el punto de vista computacional, pero relativamente simples. Por ejemplo, la siguiente figura muestra los rayos adicionales que podrían emitirse para una sola fuente de luz.
Para representar un solo píxel de la imagen, el algoritmo proyecta un rayo que comienza en el punto focal y determina que cruza un rectángulo semitransparente y un círculo brillante. Luego se debe proyectar un rayo adicional comenzando en ese punto en la dirección simétricamente opuesta a la normal de la superficie en el punto de intersección del rayo-superficie para determinar lo que es visible en la reflexión reflejada. Ese rayo corta el triángulo que es opaco. Finalmente, se prueba cada punto de intersección del rayo-superficie para determinar si está en sombra. El rayo "sensor de sombra" se proyecta desde el punto de intersección del rayo-superficie hasta la fuente de luz para determinar si alguna otra superficie bloquea ese camino.
Turner Whitted llama a los rayos secundarios y adicionales “Trazado de rayos recursivo”. [5] [Sería costoso renderizar una sala de espejos, 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 conocer la fórmula de refracción y ejemplos pictóricos, consulte el artículo de Whitted.
El lanzamiento de rayos se considera un método de fuerza bruta para resolver problemas. El algoritmo mínimo es simple, particularmente teniendo en cuenta sus numerosas aplicaciones y su facilidad de uso, pero las aplicaciones normalmente arrojan muchos rayos. Se pueden emitir millones de rayos para representar un solo fotograma de una película animada. El tiempo de procesamiento por computadora 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 (transforma el rayo en sistemas de coordenadas locales primitivos, prueba las intersecciones del rayo y la superficie y combina las clasificaciones), incluso cuando el rayo claramente no alcanza el sólido. Para detectar un "error claro", un algoritmo más rápido utiliza el árbol de composición binaria como una representación jerárquica del espacio que ocupa la composición sólida. Pero toda la información sobre 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 combinados.
Caracterizar con recintos el espacio que llenan todos los sólidos proporciona a todos los nodos del árbol un resumen abstracto de la información de posición y tamaño. Luego, las pruebas rápidas de “el rayo se cruza con el 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 recurrir a sus subárboles para investigar más a fondo.
Es difícil evaluar con precisión el ahorro de costos por el uso de recintos 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:
Por el contrario, la peor condición es:
Las siguientes son diversas mejoras de rendimiento realizadas en el artículo de Roth sobre la fundició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 son un problema clásico con los algoritmos de visualización de ráster. 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, es posible que se pierdan detalles de la escena que sean más pequeños que el espacio entre los rayos. Los bordes irregulares en un dibujo lineal se pueden suavizar siguiendo los bordes. El propósito de dicho algoritmo es minimizar el número de líneas necesarias para dibujar la imagen con una precisión de un píxel. Resultan bordes lisos. Los dibujos lineales de arriba se dibujaron de esta manera.
Para suavizar los bordes irregulares en una imagen sombreada con precisión de subpíxeles, se deben emitir 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 en (X+ ½,Y) y la superficie visible allí identificada. La distancia entre los puntos de muestra podría subdividirse aún más, pero la búsqueda no tiene por qué ser profunda. La profundidad de búsqueda principal 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 emitidos en búsquedas binarias pueden limitarse en profundidad (la de las primitivas visibles que forman los bordes), el costo de suavizar los bordes irregulares es asequible.
Para conocer la historia de la proyección de rayos, consulte trazado de rayos (gráficos) , ya que ambas 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 de la fundición de rayos por parte de Scott Roth en los laboratorios de investigación de GM se produjo al mismo tiempo que el trabajo de trazado de rayos de Turner Whitted en los laboratorios Bell.
En los primeros juegos en primera persona, se utilizaba raycasting para renderizar eficientemente un mundo 3D desde un campo de juego 2D mediante un simple escaneo unidimensional sobre el ancho horizontal de la pantalla. [6] Los primeros shooters en primera persona utilizaban la proyección de rayos 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 una gran distorsión. [6] [7] Este estilo de renderizado elimina la necesidad de disparar un rayo por cada píxel del 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 marco. Este estilo de renderizado también impone limitaciones sobre el tipo de renderizado que se puede realizar, por ejemplo, clasificación en profundidad , pero es posible que no el almacenamiento en búfer en profundidad . Es decir, los polígonos deben estar completamente uno delante o detrás del otro, no pueden superponerse ni intersectarse parcialmente.
El videojuego Wolfenstein 3D se construyó a partir de una cuadrícula cuadrada de paredes de altura uniforme que se unen 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ó y amplió una porción vertical de la textura de la pared según en qué parte del mundo el rayo golpea una pared y qué tan lejos viaja antes de hacerlo. [8]
El propósito de los niveles basados en cuadrículas era doble: las colisiones entre rayos y paredes se pueden encontrar más rápidamente ya que los posibles impactos se vuelven más predecibles y se reduce la sobrecarga de memoria. Sin embargo, codificar áreas abiertas requiere espacio adicional.
El juego ShadowCaster de Raven Software utiliza un motor mejorado basado en Wolfenstein con texturas adicionales para pisos y techos y alturas de paredes 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 altura . Luego transformó cada elemento del mapa de altura en una columna de píxeles, determinó cuáles son visibles (es decir, no han sido ocluidos por los píxeles que se dibujaron al frente) y los dibujó con el color correspondiente del mapa de textura. [9]
Los juegos posteriores de DOS, como DOOM de id Software, mantuvieron muchas de las restricciones de velocidad de raycasting 2.5D, pero cambiaron a técnicas de renderizado alternativas (como BSP ), lo que los hizo dejar de ser motores de raycasting. [10]
En geometría computacional , el problema de proyección de rayos también se conoce como problema de proyección 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 se puede encontrar rápidamente. El problema se ha investigado para varias configuraciones: dimensión del espacio, tipos de objetos, restricciones en los rayos de consulta, etc. [11] Una técnica es utilizar un octree de vóxel disperso .