|
Trazado de rayos Autor: Ramix (Ramiro A. Gómez) Fecha: 25 de octubre, 2007
Web: www.peiper.com.ar
arte
1
Hola amigos de la información. Esta vez vamos a hablar de un algoritmo que
se las trae. Y es nada menos que "trazado de rayos"? Bien, pasemos a
describirlo.
El trazado de rayos es una técnica muy poderosa que nos permite visualizar
mundos en 3D con una calidad sin precedentes, algo así como lo mejor de lo
mejor. La calidad de las imágenes generadas con esta técnica son
fotorrealistas y es muy dificil diferenciarlas de la realidad.
La podemos encontrar en muchos paquetes gráficos tanto comerciales como gratuitos, entre ellos el excelente modelador 3D Blender. Entre otros, la usan los creadores de películas. Un ejemplo es la película "El señor de los anillos", en la que se uso esta técnica distribuida en un granja de PCs comunes y corrientes. Una solución económica y poderosa (que marca una tendencia actual).
Ahora bien, ganamos una calidad impresionante dificilmente superable. Pero... qué perdemos? Nos faltaba este detalle. Si bien esta técnica es lo mejor de lo mejor, el costo computacional que tiene es prohibitivo, sobre todo si queremos un tiempo real. Para procesar un cuadro puede tardar desde algunos minutos hasta horas! Todo depende de la complejidad de nuestra escena y de la velocidad de nuestra compu (y del tipo de optimizaciones que tenga el software trazador).
El algoritmo
El algoritmo de trazado de rayos es un algoritmo recursivo que consiste en
"tirar" un rayo por cada pixel de la pantalla y hacerlo rebotar por toda la
escena una cantidad determinada de veces. Este rayo en realidad es un
vector (matemático) que se intersecta con los objetos de la escena.
Para hacer esta intersección, el algoritmo básico de TR tiene que
comprobarla con todos los objetos de la escena. Hay muchos que no va a
intersectar, y de los objetos que intersecta elige el que esté más cerca del
punto de visión o de la cámara.
Se lo considera un algoritmo muy elegante dada su relativa simplicidad,
poco código necesario, y potencia para producir resultados asombrosos. Comparativamente es MUCHO MENOS ARTESANAL que openGL y DirectX, y con unas pocas reglas logra mejores imágenes que estos 2. Aunque es mucho más lento!
Ahora calculemos algo: por cada pixel tengo que tirar un rayo, y por cada rayo tengo que intersectarlo con todos lo objetos de la escena. La fórmula de cantidad de intersecciones totales sería:
I = pixAncho*pixAlto*cant_de_objetos Si tenemos un pantalla de 1024 x 768 y 100 objetos sería 1024*768*100 = 78643200.
Si amigos, 78 millones de intersecciones.
Y tenemos que tener en cuenta que si tenemos tiempo real necesitamos 24 cuadros o más por segundo.
Volvamos al algoritmo. Cuando un rayo intersecta a un objeto, desde ese punto en el espacio el rayo rebota en varios más. Y esos a su vez van a seguir rebotando en otros objetos, hasta una profundidad que nosotros especifiquemos. El color que devuelva el rayo va a ser la mayor parte el color del objeto que intersectó primero y de la luz, después va a ser el promedio de los colores de los objetos que intersectó en segundo lugar. Cuanto más profundo vayamos menos influye el color de los rayos más profundos. De esta forma obtenemos matices para los objetos que dependen del entorno en el que están. Y si lo pensamos bien, esto ocurre también en la vida real.
Efectos
Los efectos que produce el trazado de rayos son, en cierto sentido, "excitantes". Es muy común ver en internet una imágen con una copa de vino y las sombras de la copa de cristal y del vino reflejada sobre una linda superficie. Las sombras son el punto fuerte del trazado de rayos, además de que se producen por interacción (y no están predefinidas), lo que nos asegura que son muy reales.
Otro efecto interesante es el antialiasing. El antialiasing es un suavizado que evita los serruchos en las imágenes. Estos ocurren cuando hay cambios demasiado bruscos en la intensidad de los pixeles, y se nota aún más cuando no tenemos la suerte de tener un monitor de alta resolución. El efecto serrucho se produce cuando el color de los pixeles cambia repentinamente de blanco a negro, por ejemplo.
Cuando tenemos antialiasing, el cambio no es tan brusco, y entre los dos colores se "ponen" colores intermedios que hacen que nos parezca más suave la imágen. Si tenemos unos pixeles blancos y sus contiguos son negros, los pixeles del medio van a tomar escalas de grises, y así, con mayor resolución la vista tiende a promediar los colores muy pequeños.
El antialiasing se produce tirando más rayos por pixel, por ejemplo 4 (2x2),
9 (3x3), 16, 25, etc. (recordemos que el pixel es cuadrado). Pero la
performance va a caer aún más, desde 4 veces en adelante...(a menos que
hagamos algunos truquitos).
El desenfoque es otro efecto muy interesante. Podemos simular profundidad
de campo en nuestras escenas. ¿Qué es esto? La cámara ve nítido a cierta
distancia, y los objetos que no estén a esa distancia se vuelven borrosos, al
igual que pasa con las cámaras fotográficas reales.
Para los amantes del desenfoque en movimiento (más conocido como
motion blur, y que se puede apreciar en algunos juegos como los de autos
cuando vamos a mucha velocidad), el trazado de rayos también nos permite
hacer desenfoque
en movimiento.
Esto ya forma parte
de la sección
trazado de rayos
avanzado, pero en
la parte 2 de este
white paper vamos a
comentar cómo se
implementa este
efecto y la
profundidad de
campo.
Optimizaciones
El algorimtmo de TR básico es un tanto ineficiente, y tiene una eficiencia
O(n^2). Es decir que con n objetos va a hacer aproximademante n*n
operaciones. Si tenemos 10 objetos haría 100 op., y si tenemos 100 haría
10000 op. Es decir que cada vez crece más, lo que nos dice que no es
precisamente de los algoritmos ligeros tan deseados en el ambiente
informático.
Se han presentado muchas optimizaciones que se pueden hacer para
aumentar la performance, muchas de ellas llegan a hacer la eficiencia cuasi
lineal, a costa de usar más memoria.
Sin embargo, como es un tema relativamente nuevo, es probable que
muchas de las optimizaciones aún no se hayan descubierto (o inventado).
Seguramente existe un algoritmo similar con eficiencia O(2), O(3), etc. en el
que no importa la cantidad de objetos que tengamos, siempre el tiempo de
procesamiento va a ser casi el mismo. Imaginen que una solución así sería
bien pagada por los chicos del software propietario.
Entre las optimizaciones que son más comunes encontramos la subdivisión
espacial y la agrupación.
Paquetes de trazado de rayos
Los paquetes más conocidos hoy en día son Yafray (Yet another ray tracer) y
POVray. Yafray viene embebido en algunos programas de diseño 3D, como
por ejemplo Blender.
POVray es un lenguaje para producir gráficos con trazado de rayos y es
posible también encontrar algunos programas de diseño que lo usan. Uno de
los usos que se le dá es el benchmarking de procesadores (o sea, el testeo
de la performance). Intel y AMD publican en sus sitios web los benchmarks
de sus nuevas CPUs usando, entre otros, a POVray.
Bueno amigos. Es todo por hoy, no se pierdan la parte 2 de este white paper,
lleno de conceptos jugosos sobre esta técnica que realmente será el futuro
del 3D en muchas aplicaciones de informática.
Autor: Ramix (Ramiro Andrés Gómez)
Sitio web del que se obtuvo este white paper: www.peiper.com.ar
Referencias:
• Gráficos por computadora con OpenGL (Donald Hearn & Pauline Baker). PEARSON - Prentice Hall. ISBN-10: 84-205-3980-5. ISBN-13: 978- 84-205-3980-5
• Wikipedia (www.wikipedia.com)
• Diversos tutoriales de la web
Recursos gráficos
Los esquemas son diseños propios.
Las imágenes fueron tomadas de www.blender.org. Se presentan sólo para fines
demostrativos y pertenecen a sus respectivos autores. Prohibida su copia y/o utilización
comercial sin autorización del autor.
Trazado de rayos (parte 2) Autor: Ramix (Ramiro A. Gómez) Fecha: 4 de noviembre, 2007 Sitio web:
Esta es la segunda parte de trazado de rayos. Asumimos que si vas a leer este white paper ya leíste la primera parte, en la que te damos una pequeña pero concentrada introducción a este fascinante mundo del 3D. En este white paper vamos a ver como es el algoritmo en pseudo código, y vamos a explicar como se logran las técnicas más interesantes y que nos otorgan la mejor calidad a nuestras imágenes: el antialiasing, el desenfoque en movimiento y la profundidad de campo. Como ya mencionamos en la parte 1, el algoritmo de trazado de rayos propiamente dicho es costoso en su ejecución, y tiene una eficiencia O(n2). En este punto podemos notar un gran problema: si queremos implementar videojuegos o realidades virtuales con este técnica vamos a necesitar una capacidad de procesamiento que pocas computadoras personales tienen hoy en día (fines del 2007). Ya calculamos que para una escena simple con un resolución nativa tenemos alrededor de 78 millones de rayos por cuadro (frame), y no consideramos rayos recursivos. Para lograr los tan preciados 24 cuadros por segundo nos van a hacer falta varias cosas, que las |
un algoritmo optimizado (parte lógica) hardware potente |
segundo nos van a hacer falta varias cosas, que enumero en: • •
• implementación nativa en placas de video Quizás el recurso que más nos beneficie es el de un algoritmo optimizado. Optimizar un algoritmo puede requerir varios pasos y un toque fundamental en nuestra manga, que es la creatividad. Las optimizaciones enunciadas en general para el trazado de rayos son de tipo espacial. El algoritmo de trazado de rayos es muy elegante, dada su simpleza y recusividad.
¿Por qué es un algoritmo recursivo? Porque en su definición se autoinvoca una cantidad determinada de veces, lo que nos abstrae de la enorme complejidad de armar un árbol manualmente.
Supongamos que "tiramos" un rayo por pixel. Cuando ese rayo choque contra el objeto más cercano a la cámara, desde ese punto de choque "rebotarán" muchos más rayos, y cada uno de estos también rebotará. Si lo pensamos detenidamente, se forma una estructura de árbol, donde cada nodo es un rayo, y el nodo raíz es el primer rayo que tiramos por el pixel. Los hijos de cada nodo van a ser los rayos que se forman a partir del choque de este con un objeto. Ahora pasemos al pseudo código: trazarImagen () {
si p > limite de profundidad { retornar; }
para todos los pixeles {
rayo = rayo por los puntos (Ox,Oy) y (pixX,pixY) prof = 0
trazarRayo(rayo, prof) } } trazarRayo (Rayo r, profundidad p): Color {
obj = objeto más cercano que intersecta el rayo
rayos[] = rayos reflejados en obj
c = (color(obj) + suma(colores_luces, intensidad_luces)) * peso(p)
para todos los rayos[i] {
c = c + trazarImagen(rayo[i], p+1)*peso(p+1) } }
La función peso calcula un factor de peso para el color con respecto a la profundidad del rayo. Cuanto más profundo sea el rayo, más pequeño va a
ser este factor. Es decir que peso(p) nos devuelve un valor numérico flotante entre 0.0 y 1.0, que constituye una ponderación para el color adquirido. Como ven, el algoritmo es muy simpático y cuesta creer que un código tan escueto tenga la potencia que tiene. Obviamente que nos estamos olvidando de las funciones para describir los objetos, las texturas, las luces, etc. Pero la idea está en el algoritmo. |
Objetos tridimensionales
Un detalle que no podemos olvidar mencionar en este artículo es el aspecto
formal matemático que hay detrás de esto. Para representar los rayos, los
objetos, los colores, los efectos, etc. necesitamos una herramienta que nos
permita hacerlo usando números. Así, un rayo va a ser un conjunto de
números, los objetos también van a ser un conjunto de números, y así
podemos seguir. Lo importante del uso de las matemáticas en este sentido
es que hay una rama de ellas que se ocupa de describir objetos
geométricos: la GEOMETRIA ANALITICA.
Aunque el nombre nos asuste un poco, con su aplicación vamos a poder
hacer todo lo que comentamos antes, hacer intersecciones, representar
objetos tridimensionales, luces, humo, niebla, fuego, partículas,
resplandores, etc.
Los objetos más comunes que se pueden encontrar en un paquete de
raytracing son:
• las esferas
• los planos infinitos
• los triángulos
• los conos
• los cilindros
• las elipsoides
Cada una de estas figuras tiene una función que la representa. Por ejemplo, la ecuación de una esfera es:
También parece complicada, pero créanme que en un tiempito se nos hace familiar y hasta le empezamos a poner nombres(¡¡??). Bueno, no e tanto. Nadie quedó internado por programar un trazador de rayos en meses. Pero si lo hacemos en unos pocos días la historia ya es distin |
familiar y hasta le empezamos a poner nombres(¡¡??). Bueno, no es para programar un trazador de rayos en varios Pero si lo hacemos en unos pocos días la historia ya es distinta. No se aceptan quejas de ningún tipo, nada de reclamos si tía elipsoide los persigue, eh!! OK, volvamos a Tierra. X, Y, Z son variables, mientras que xc,yc, zc son el centro de nuestra esfera. radio lo dejo para que lo adivinen. La ecuación de un plano es X: Z = a*Y + b*X + c minúsculas a, b, c, etc. son los números que nos van a determinar la inclinación y posición del plano. No vamos a enunciar todas las ecuaciones, estas son algunas para dar una idea de la forma que tiene la descripción de cada figura 3D. Pasemos al rayo. El rayo es un caso especial de geometría, ya que no presenta superficie ni volúmen, es unidimensional. Pero sin embargo, sí atraviesa un espacio tridimensional. |
Las letras en mayúscula son las variables, mientras que las c, etc. son los números que nos van a determinar la inclina |
(X-xc)2+(Y-yc)2+(Z-zc)2=radio2
Podemos considerar que un rayo es un vector (matemático), con un punto de origen y otro punto de fin. La salvedad que tenemos que hacer es que el punto de fin en un rayo no determina realmente su fin, sino que nos determina el sentido y dirección del rayo. El sentido se refiere a si está dirigido hacia atrás o hacia adelante, la dirección especifica la pendiente de la recta que lo describe.
Para definir un rayo nos tenemos que valer de dos funciones de recta, una para el plano XY y otra para el plano YZ. Los dos juntas nos determinan un rayo que atraviesa un espacio 3D. El rayo sería:
Y = m1*X + b1
Z = m2*Y + b2 Las letras m1 y m2 son las pendientes que tiene la recta. Por ejemplo, si m1 es 1, la recta en el plano XY va a estar inclinada 45°. Estas variables pueden ser positivas y negativas. En el caso de que m sea positiva, cuanto más grande es más rápido crece. En el hipotético caso de que m=infinito, la recta va a tener 90°, va a ser vertical. Este es un punto a destacar, porque si implementamos un trazador de rayos vamos a tener que considerar el caso especial de que la recta sea vertical.
Las letras b1 y b2 son el punto que va a tener cada recta cuando su variable vale 0. Dicho en un amistoso lenguaje criollo, el desplazamiento hacia arriba o hacia abajo que va a tener la recta (manteniendo la pendiente igual).
Las intersecciones
que |
encontrar |
Para intersectar dos figuras geométricas vamos a tener
puntos X, Y, Z que satisfagan al mismo tiempo las ecuaciones de cada
figura. ¿Cómo hacemos esto? Con un sistema de ecuaciones.
Resolver un sistema de ecuaciones consta de reemplazar en alguna de
estas las variables por su definición. Para que quede más claro, podemos tomar la fórmula de la esfera y reemplazar Y por la definición de Y (la segunda ecuación), y Z por la definición de Z. Como Z está en función de Y, la reemplazamos nuevamente. Con esto, la ecuación de la esfera nos va a quedar representada sólo en función de X. Despejamos esta variable y obtenemos 2 soluciones X, que son las coordenadas en el eje x de las 2 intersecciones que tiene el rayo con la esfera.
Además nos tenemos que asegurar que xc, yc, zc, radio, m1, m2, b1, b2 sean valores numéricos, no variables.
Aplicando esta solución y el algoritmo presentado arriba en pseudo código, ya tenemos bastante desarrollado nuestro trazador de rayos. Sobre los triángulos
Como habrán notado en la mayoría de los juegos actuales, los objetos tridimensionales vienen poligonizados. ¿Qué quiere decir esto? Que se representan utilizando un montón de triángulos uno al lado del otro. Esto tiene sus ventajas, en particular si consideramos que la ecuación de un triángulo es la del plano con algunas restricciones, y resolver un sistema rayo-plano es más rápido que resolverlo con otra figura geométrica (con cuádricas, por ej.). Esta es una de las posibles razones por las que las placas de video vienen especialmente optimizadas para el procesamiento de triángulos, a tal punto que muchas veces escuchamos hablar de su potencia en base a la cantidad de millones de triángulos por segundo que procesa.
Efectos gráficos para trazado de rayos
Ya nombramos algunos de los más comúnes, el antialising, la profundidad de campo y el desenfoque en movimiento (motion blur). Hablemos primero del antialising.
Antialiasing La idea es la misma |
en los paquetes gráficos actuales más usados, |
que como OpenGL y DirectX.
Cuando tenemos variaciones de intesidad de color muy bruscas entre pixeles adyacentes, se puede apreciar un efecto de "serrucho" cuando vemos la imágen. Esta característica no es para nada deseable, en especial si lo que deseamos es realismo gráfico.
Por eso, aplicando algunas técnicas conseguimos suavizar la imágen, de manera que entre los pixeles haya una especie de transición en degradado que mejore la calidad gráfica.
Una de las técnicas más usuales es el supermuestreo. Consiste en tomar un pixel como si fuera un área, y por cada subárea de éste calculamos su color. Como la mínima unidad que pueden representar los monitores y pantallas es un pixel, tenemos que promediar los colores de cada subárea del pixel. O sea, por cada color (rojo, verde y azul) los sumamos y luego dividimos la suma por la cantidad de subáreas del pixel. En el trazado de rayos podemos implementar esta técnica de una manera harto sencilla: tirando más rayos por cada pixel. La calidad que obtengamos va a ser mejor, pero la performance va a caer estrepitosamente, 4 veces o más. Esto es porque al ser el pixel cuadrado, si ponemos 2 rayos por pixel, el total va a ser 2*2, con 3 rayos por lado sería 3*3, etc.
|
|
|
|
|
=¡a-n ■ |
|
|
|
|
• * |
|
* . |
|
H |
distintas distril nara lograr ant |
3UCíO ¡alia |
nes de rayos sing |
|
|
|
Aún no hay comentarios para este recurso.
Monografias, Exámenes, Universidades, Terciarios, Carreras, Cursos, Donde Estudiar, Que Estudiar y más: Desde 1999 brindamos a los estudiantes y docentes un lugar para publicar contenido educativo y nutrirse del conocimiento.
Contacto »