Trazado de rayos
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.
Este apunte fue enviado por su autor en formato ZIP (WinZip).
Para poder visualizarlo correctamente (con imágenes, tablas, etc) haga click aquí o aquí si desea abrirla en ventana nueva.
Trazado de rayos
Autor:
Ramix (Ramiro A. Gómez) Fecha: 25 de octubre, 2007
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
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
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
Este apunte fue enviado por su autor en formato ZIP (WinZip).
Para poder visualizarlo correctamente (con imágenes, tablas, etc) haga click aquí o aquí si desea abrirla en ventana nueva.
Monografías
Este apunte fue enviado por su autor en formato ZIP (WinZip).
Para poder visualizarlo correctamente (con imágenes, tablas, etc) 
