Hemos visto que en los modelos locales de iluminación
(modelos de sombreado) solamente se considera la relación
entre el punto de vista (en el caso de la componente especular),
el punto de la superficie y la fuente de luz. En estos modelos
no interviene la interacción entre diferentes objetos que
pueden transmitirse luz entre sí, por lo que, en general,
no será posible considerar efectos como las sombras, la
reflexión de unos objetos en otros y la interdifusión
de la luz. Tampoco se suelen considerar en los modelos locales
los procesos de interacción de la luz con el medio de transmisión,
salvo simulaciones simples de la absorción y difusión
atmosférica constante.
En este tema vamos a analizar otros modelos más
generales de iluminación que consideran, en principio,
todos los fenómenos de interacción y permitirán
cubrir las limitaciones de los modelos locales a costa de incrementar
el coste de computación.
4.1. CARACTERIZACIÓN DE LA LUZ. ECUACIONES
INTEGRALES DE LA ILUMINACIÓN.
Se trata de analizar cómo evoluciona la intensidad
de luz que saliendo de un determinado punto r se transmite
en una dirección w.
Podemos dividir el comportamiento general de la luz
en dos procesos (esta distinción es clara mientras consideremos
que el índice de refracción del medio cambia bruscamente
y sólo en ciertas superficies) que se detallan a continuación.
4.1.1. TRANSMISIÓN A TRAVÉS DEL
MEDIO
La magnitud que describe la intensidad transmitida es:
ángulo sólido
La ecuación diferencial que describe el cambio
de esta intensidad en la dirección w es:
(
Ec.1)
gradiente, dirección
en la que aumenta la intensidad de la luz
coeficiente de extinción
(coeficientes
de absorción y dispersión)
luz emitida por el medio
luz proveniente de la difusión
de otras fuentes que puede calcularse como:
Por tanto la intensidad de la luz a lo largo
de una recta definida por 
podría
calcularse mediante la integración de la ecuación
1.
4.1.2. INTERACCIÓN CON UNA SUPERFICIE
Para calcular la intensidad que sale reflejada o transmitida en una dirección w tenemos que integrar para todas las direcciones del espacio de donde puede provenir radiación para ver qué porcentaje saldrá en la dirección w:
En estas dos ecuaciones, la de la transmisión
y la interacción con una superficie, se considera todo
el comportamiento de la luz desde el punto de vista de la energía
(la información de fase se pierde). De hecho ambas ecuaciones
podrían englobarse en una sola, puesto que la interacción
con una superficie puede considerarse un tipo particular de dispersión.
Debido a la complejidad de efectuar estos cálculos
integrales con funciones generales, normalmente recurriremos a
aproximaciones (ya descritas) para simplificar este comportamiento
general y obtener modelos más eficientes que puedan ser
utilizados para el cálculo de la iluminación.
El trazado de rayos clásico cumple dos funciones
diferentes. Por una parte incluye el cálculo geométrico
de la imagen, la proyección de la escena tridimensional
sobre la ventana de visualización, resolviendo el problema
que en el procesamiento de gráficos en tiempo real (ver
3.2) se abordaba mediante la proyección de los vértices
de los polígonos. En este sentido, el trazado de rayos
puede considerarse como un método de visualización
diferenciado. El fundamento de esta técnica de proyección
puede remontarse a la idea aristotélica de la visión
como emisión de influjos en línea recta desde el
ojo. Para efectuar la proyección se trazarán en
sentido inverso los rayos que llegarían al punto de observación
(cámara u ojo) desde la dirección correspondiente
a cada uno de los pixeles de la ventana de visualización.
El color de cada pixel estará, pues, asociado a este rayo.
La segunda función del trazado de rayos consiste
en efectuar la evaluación de la intensidad luminosa
(color) transportada por cada rayo en función de su recorrido
por la escena. En este sentido el trazado de rayos implica la
existencia de un modelo de iluminación global en el que,
como veremos, aparecen progresivamente otros rayos en un proceso
de evaluación recursiva.
En todo este proceso la naturaleza de la luz se aproxima
con el modelo de la óptica geométrica. La luz se
caracterizará por una cierta cantidad de energía
radiante que se transmite en una dirección bien definida
(normalmente en línea recta, considerando que el índice
de refracción no varía a lo largo del medio de transmisión),
tal y como definíamos en el apartado anterior.
Podemos dividir el proceso del trazado de rayos en
distintos pasos :
4.2.1. SELECCIÓN DE RAYOS DESDE EL PUNTO
DE VISTA.
Para comenzar el trazado de cada rayo debemos decidir
su dirección de salida y asociarlo con un determinado pixel
de la imagen. Suponiendo para este análisis preliminar
que asociamos un único rayo a cada pixel, ¿cuál
es la dirección en la que el rayo deja el punto de vista?
Como aproximación se puede emplear la perspectiva
plana o lineal, similar al modelo de cámara oscura con
una pupila de entrada puntual
Otra aproximación sería reproducir
el hecho de que la superficie del ojo no es plana sino curva.
De esta forma se reproduciría la distorsión curvada
de la imagen (que aparece en nuestra visión), pero se seguirá
obteniendo una imagen nítida de todos los objetos, independientemente
de su distancia, cosa que no sucede en la realidad.
Podemos solucionar este efecto haciendo que la pupila
de entrada de los rayos sea extensa. Para obtener el color de
un pixel deberíamos entonces lanzar varios rayos que pasen
por diferentes puntos de la pupila. De esta manera, según
la distancia y la posición de los objetos éstos
pueden aparecer enfocados o borrosos, reproduciendo el efecto
de profundidad de campo que aparece en la visión
o en las cámaras.
Otro efecto que podemos considerar es la existencia
de una lente en la pupila, extensa o puntual, que modifique las
trayectorias de los rayos. Las lentes, convergentes o divergentes,
desvían los rayos que no pasan exactamente por su centro.
El método de lanzar varios rayos para conseguir
desenfocar los objetos debido a la profundidad de campo constituye
un primer ejemplo de técnica de muestreo (sampling)
que consiste en dar color a cada pixel en función de varias
muestras de rayos en lugar de uno sólo. Esta técnica
de muestreo también puede ser utilizada para reducir los
defectos de dentado debidos al tamaño de los pixels (antidentado
o antialiasing).
En la parte izquierda de la figura se observa el
efecto de dentado producido cuando se lanza un solo rayo por pixel.
Aquellos rayos que intersectan con el objeto aparecen con color
oscuro, y los que no lo hacen toman el color del fondo. El efecto
es una transición brusca y quebrada en la frontera del
objeto. En la parte derecha se observa el efecto de suavizado
que se produce al muestrear cada pixel con cuatro rayos, puesto
que el color resultante para cada pixel se calcula como la media
entre las intensidades de sus rayos. De esta manera, la frontera
del objeto aparece representada con una transición suave.
4.2.2. EVALUACIÓN DE LA INTENSIDAD DE UN
RAYO
Como hemos indicado, para calcular la intensidad
que el rayo transportará cuando llegue al punto de observación
procedente de la escena se sigue un proceso recursivo, resultando
un algoritmo como el siguiente:
evaluar (rayo)
para cada hijo
evaluar (rayo.hijo)
En un modelo sencillo los rayos hijos creados a
partir de la intersección con una superficie serán
solamente un rayo reflejado y uno transmitido.
El resultado de este proceso recursivo es la creación de un árbol de rayos, en el que cada uno depende de las intensidades asignadas a sus hijos.
4.2.2.1. EVALUACIÓN DE LA TRANSMISIÓN
POR EL MEDIO
Se puede aplicar el método general que hemos
visto al tratar las ecuaciones integrales de la luz, pero usualmente
se aplican modelos más sencillos:
Si consideramos el comportamiento físico,
la intensidad decrece con el cuadrado de la distancia 
,
pero este modelo produce cambios demasiado bruscos en la iluminación
cuando no se considera conjuntamente con el efecto de difusión.
Por esta razón se suelen emplear modelos fenomenológicos
del tipo 
donde pueden ajustarse los paramétros
a,b,c según el medio.
Si consideramos que la constante de absorción
del medio es constante la intensidad decrece de forma exponencial
con la distancia: 
A la intensidad originalmente transmitida por el rayo se suma una componente añadida por la luz que, proveniente de otras direcciones, sale dispersada en la dirección de transmisión. Si la proporción de luz dispersada y su intensidad es constante con la distancia.
Entonces 
, siendo Is
la intensidad proveniente de la dispersión.
Normalmente este proceso y el de absorción
se dan a la vez y entonces tenemos:
Las dos situaciones extremas se producen cuando:
Es decir, a poca distancia la transmisión no produce ningún efecto sobre el color original del rayo.
Cuando la distancia aumenta mucho el color del rayo se confundirá totalmente con la intensidad que viene por dispersión. Esto sucede, por ejemplo, cuando observamos una escena a través de la niebla, donde los objetos adquieren progresivamente un color blanquecino con la distancia, debido a la luz que la niebla dispersa desde el Sol hacia el observador.
El proceso de dispersión y absorción
puede simularse también colocando muchas 'partículas'
en el medio y haciendo que los rayos interactuen con ellas como
si fueran superficies. Este sistema es muy flexible (permite,
por ejemplo, calcular la transmisión a través de
una nube de tamaño y densidad no constante, pero es demasiado
costoso en términos computacionales.
4.2.2.2. EVALUACIÓN DE LA INTERACCIÓN
CON LA SUPERFICIE
El modelo más elemental consistiría
en suponer que la interacción es perfectamente especular,
y crear para cada rayo que llega a una superficie un rayo hijo
que sale en la dirección reflejada y un segundo hijo (en
el caso de que el segundo medio sea transparente) en la dirección
de transmisión especular. Las relaciones de intensidad
entre el rayo padre y los hijos vendrían definidas por
los coeficientes de reflexión y transmisión especular.
Se formaría así un árbol de
rayos como el que podemos ver en la figura 2.2.2. Para poder efectuar
la evaluación de la intensidad según este modelo
habría que calcular el color de los rayos situados en las
'hojas' de este árbol y retroceder hacia los rayos padres,
llegando eventualmente al rayo inicial. La forma de asignar colores
a los rayos terminales sería:
Pero podemos fácilmente darnos cuenta de la
enorme cantidad de rayos que habría que considerar para
llegar a trazar los caminos que llevan, después de infinidad
de reflexiones y transmisiones, hasta las fuentes de luz. Esto
resulta virtualmente imposible cuando definimos (como se suele
hacer en trazado de rayos) fuentes de luz puntuales. Parece más
sensato y eficiente asignar un color al rayo dependiendo de su
'cercanía' a la fuente de luz, sin esperar a que efectivamente
la intersecte.
Otras opciones , más interesantes proponen añadir un termino de intensidad a los rayos intermedios que no dependan de sus rayos hijos. Un posibilidad para dotar de color a los rayos en los niveles intermedios del árbol de rayos es lanzar un tercer rayo desde cada punto de intersección hasta la fuente de luz (rayo de sombra). Si el rayo de sombra no intersecta a ningún otro objeto antes de llegar a la fuente de luz, entonces ésta es visible desde el punto de intersección, iluminándolo. En caso contrario ese punto estaría dentro de la 'sombra' producida por otro objeto que detiene la luz procedente de la fuente. Si la fuente es visible, entonces podemos aplicar un modelo de sombreado para calcular el color básico del rayo y añadirle luego la influencia de los rayos hijos.
De este modo tendríamos el algoritmo :
evaluar (rayo)
/* interacción superficie */
si no hemos alcanzado la profundidad máxima del árbol
crear rayos hijos Ir , It y evaluarlos
calcular intensidad propia superficie
lanzar rayo de sombra a cada fuente de luz
si (rayo sombra no intersecta objeto) aplicar modelo iluminación para calcular I propia
modelo sombreado: componente ambiente + componente difusa + componente especular
devolver la intensidad propia combinada
con Ir
, It
Los rayos Ir , It siguen siendo muy importantes para formar imágenes de objetos reflejados o reproducir la transparencia de los materiales.
Dependiendo de la precisión deseada y del tiempo de computación disponible pararemos este proceso recursivo en un nivel más o menos profundo del árbol.
De esta manera, combinando la evaluación de
un modelo de sombreado en los puntos de intersección con
el árbol de rayos reflejado y transmitido, obtenemos un
modelo local para los colores, con sombras e imágenes de
otros objetos moduladas por el color propio del objeto. Pero se
pierde mucha de la riqueza presente en el comportamiento real
de la luz en las superficies. Por ejemplo, al tener una reflexión
especular perfecta, no podemos reproducir superficies de brillo
difuso ('glossy'), ya que la imagen de un objeto aparecerá
reflejada en los otros con perfecta nitidez. Otro efecto que tampoco
es posible representar es la interacción difusa entre los
distintos objetos. Estas limitaciones son debidas a que hemos
reducido toda la distribución reflejada y transmitida a
un único rayo en cada dirección.
Para aproximar de forma más exacta las distribuciones
de luz reflejada y transmitida debemos descomponer cada rayo en
un número mayor de rayos hijos, cuyo peso relativo debe
calcularse de manera que se reproduzca la forma de la distribución.
En el caso de un comportamiento perfectamente difuso estaríamos
reproduciendo el mismo comportamiento que más adelante
estudiaremos en el método de radiosidad.
El problema ahora es que, sobre todo para el caso
de un comportamiento difuso, tenemos demasiados rayos y la cantidad
de rayos en el árbol se multiplica demasiado, volviéndose
computacionalmente intratable. Por esta razón se suele
limitar el número de rayos. Cuando los objetos son muy
difusos, para no tener que lanzar muchos rayos es preferible utilizar
el modelo de iluminación basado en radiosidad en lugar
del trazado de rayos.
Otro problema específico del método
de trazado de rayos es la imposibilidad de considerar directamente
fuentes extensas de luz. Esta limitación se debe
al hecho de que los rayos de sombra y el correspondiente modelo
de sombreado suponen que la fuente es un foco puntual. Normalmente
las fuentes extensas se simulan mediante conjuntos de fuentes
puntuales.
Otro problema del trazado de rayos relacionado con
las fuentes de luz es el hecho de que el método no permite
visualizar éstas directamente como un objeto más
de la escena, puesto que al ser puntuales es imposible que los
rayos lanzados lleguen nunca a intersectarlas. La manera de solventar
esta limitación es colocar alrededor de la fuente de luz
un objeto extenso cuyo material emite luz, y que aparecerá,
por tanto, coloreado al aplicarle el método de sombreado.
Sin embargo, veremos que el método de radiosidad ofrece
una mejor solución a los dos problemas que el trazado de
rayos plantea respecto a las fuentes de luz.
4.2.2.3. ORGANIZACIÓN Y OPTIMIZACIÓN
DEL CÁLCULO DE INTERSECCIONES
La parte más importante de coste temporal
en la ejecución de un trazado de rayos, alrededor del 90%,
es consumido por el cálculo de las intersecciones. Por
esta razón es importante disponer de mecanismos para organizar
y optimizar el cálculo de la siguiente intersección
para un rayo dado, y también para adaptar el número
de rayos involucrado.
Veamos primero dos métodos que pueden utilizarse
para reducir el número de objetos en la escena que son
candidatos a intersectar con un rayo. La idea básica consiste
en ir descartando objetos que sabemos que no se encuentran en
el espacio atravesado por el rayo, reduciendo el cálculo
geométrico de la intersección rayo-superficie a
un pequeño número de cuerpos.
Podemos usar cualquiera de las técnicas de
subdivisión espacial que hemos visto (octrees, BSP_trees,
…), en su utilización como representaciones de objetos,
para dividir la escena 3D en zonas y excluir aquellas que el rayo
no atraviesa, ahorrando el cálculo de intersecciones con
los objetos que contienen. Por tanto, en este caso no estamos
utilizando estas estructuras para describir los objetos, sino
su distribución espacial en la escena.
Un mismo objeto puede ocupar más de una celda de la partición, lo que habrá que tener en cuenta para no calcular varias veces la misma intersección.
Las estructuras jerárquicas orientadas (octrees) son ideales, ya que podemos ajustarlas para que los elementos mínimos contengan un cierto número de objetos y además permite hacer comprobaciones de manera sencilla. Veamos un ejemplo en dos dimensiones utilizando un quadtree:
En la parte izquierda puede verse la distribución de objetos (círculos) en la escena, y su división por medio del quadtree, que aparece en la parte derecha.
Una forma de realizar la comprobación de las
intersecciones para descartar objetos sería recorrer recursivamente
el quadtree y continuar comprobando solamente aquellos nodos que
atraviesa el rayo, descartando los otros. Finalmente, al llegar
a los nodos de las hojas tendríamos que comprobar la intersección
con los objetos.
Podemos observar que el cálculo inicial de
las intersecciones (que supondría comprobar siete objetos)
se reduce a calcular la interseccion con tres, más las
comprobaciones con los nodos del quadtree que son mucho más
eficientes.
El problema de este método de comprobación
recursiva es que tras computar todas las intersecciones (resultan
solamente dos en nuestro caso), éstas deben ordenarse por
distancia para saber cuál es la más cercana. Si
pudiéramos recorrer los nodos del árbol siguiendo
la misma dirección que el rayo (recorrido direccional),
bastaría con comprobar las intersecciones hasta que nos
encontráramos con la primera de ellas (a menos que se trate
de una primitiva CSG, como veremos). Existen algoritmos que permiten
recorrer de esta forma las particiones espaciales, jerárquicas
o no.
En el ejemplo del quadtree anterior un recorrido
direccional procedería en este orden:
Como vemos, es un proceso mucho más eficiente, y encontramos inmediatamente el punto adecuado de intersección comprobando un único objeto.
En el caso de realizar una partición homogénea
no jerárquica (voxels), se puede aplicar un algoritmo similar
al empleado para recorrer los pixeles de una recta (Bresenham)
o el D.D.A. (Digital Differential Analyzer). El problema
de las particiones homogéneas es su ineficiencia, ya que
podemos tener muchas celdas sin objetos y otras que contienen
muchos objetos cuyas intersecciones habrá que comprobar
con un mayor coste. Es decir, no tenemos la posibilidad de hacer
un división adaptativa, como en el caso de las estructuras
jerárquicas.
Veamos ahora una versión 3D del algoritmo
DDA (3DDDA).
Este recorrido con información direccional
también se puede realizar mediante una partición
espacial que tenga en cuenta el origen y la dirección de
los rayos (como podemos ver en la siguiente figura). Estos métodos
resultan especialmente útiles cuando el punto de vista
permanece fijo, ya que entonces no es necesario rehacer la partición.
Si el punto de vista se moviera habría que redistribuir
de nuevo los objetos en los elementos de la partición espacial,
lo que sería ineficiente. Otro inconveniente de este tipo
de partición es que si no se crea una estructura adaptativa
(jerárquica) habrá elementos que contendrán
muchos objetos y otros que no contendrán ninguno.
En este caso se trata también de sustituir
el cálculo de la intersección del rayo con un objeto
complejo por una comprobación más eficiente que
utiliza una primitiva geométrica más sencilla. La
forma de hacerlo es recubrir los objetos o grupos de objetos con
un volumen envolvente, que será una forma geométrica
muy sencilla (esfera, caja).
Comprobaremos primero la intersección del
rayo con el volumen envolvente. Si el rayo no lo intersecta, entonces
no existirá tampoco intersección con el objeto que
contiene, y nos podemos evitar ese cálculo.
Los tipos de volúmenes envolventes más
comunes son :
Este tipo de comprobación se puede hacer todavía
más eficiente empleando una estructura jerárquica
de volúmenes.
Cuando se comprueba la existencia de intersección
con el volumen asociado a un nodo se siguen comprobando sus nodos
hijos, hasta llegar a un nodo terminal. Si el rayo intersecta
al nodo terminal, entonces hay que calcular con detalle la intersección
con los objetos que éste envuelve. Este proceso recursivo
se resume en el siguiente algoritmo:
comprobar (nodo, rayo)
{
si ( existe intersección (nodo, rayo) )
{
si nodo es terminal comprobar_objetos(nodo, rayo)
sino para cada hijo[i] de nodo
comprobar (hijo[i], rayo)
}
}
4.2.3. CÁLCULO DE INTERSECCIONES RAYO-OBJETO
Vamos a hacer un repaso de los métodos de
cálculo de las intersecciones con ciertas formas geométricas
que pueden ser utilizadas para definir los objetos o sus volúmenes
envolventes.
El problema general es:
Donde supondremos que el vector director de la recta
que representa el rayo tiene un módulo unitario: 
de
manera que entonces 
distancia recorrida
por el rayo.
Así se puede parametrizar el rayo como: 
Calcular la intersección consistirá
en hallar las coordenadas de un punto 
,
tal que en él coinciden el rayo y la superficie del objeto.
Alternativamente, también podemos averiguar el valor del
en ese punto, lo que nos permitirá
saber directamente la distancia hasta la intersección y
el punto de intersección.
4.2.3.1. INTERSECCIÓN CON OBJETOS DEFINIDOS
POR ECUACIONES ELEMENTALES
El punto P debe satisfacer al mismo tiempo la ecuación
de la esfera de radio r y centro rc , y de la
recta.
Como vemos, la recta puede intersectar a la esfera
en dos puntos, uno de entrada y otro de salida. En este caso tomaremos
como solución válida la correspondiente al valor
más pequeño de s. Podemos observar que basta
con calcular el signo del discriminante para saber si existe o
no intersección. En el caso negativo, no tendremos que
hacer más cálculos.
Este método de cálculo puede aplicarse
de forma muy similar a otras cuádricas (paraboloides, elipsoides
e hiperboloides), que llevarán a un criterio similar con
discriminante, y también puede intentar aplicarse a otras
superficies de ecuaciones más complicadas, pero en muchos
casos no será posible llegar a una expresión analítica
(con una fórmula explícita) para las soluciones.
Más adelante veremos qué métodos aproximados
pueden utilizarse en esos casos.
Con esto determinaríamos 
sobre
el plano, y tendríamos que utilizar algún test de
pertenencia del punto al polígono para averiguar si el
punto de intersección cae fuera o dentro de éste.
Algunos algoritmos para comprobar la pertenencia de un punto a
un polígono son:
Regla de la paridad de intersecciones.
Si se traza una semirecta
desde el punto a comprobar y el número de intersecciones
con la frontera del objeto es par, el punto es exterior, mientras
que si es impar el punto es interior.
Regla del número de intersecciones orientadas.
Se suma o resta uno dependiendo
de la dirección de cada una de las aristas intersectadas.
Si la suma es cero el punto es exterior y si es distinto de cero
el punto es interior.
Regla del número de pertenencia a triángulos
orientados. Es equivalente al anterior.
Para polígonos convexos se puede utilizar
un test con la posición respecto a las aristas.
Comparando la posición
del punto respecto al vector normal a cada arista podemos decidir
si el punto es interior o exterior, de tal forma que si el punto
es interior a todas las aristas lo es al objeto, mientras que
el punto es exterior cuando al menos el punto es exterior a alguna
de las aristas. Este método sólo puede emplearse
si el objeto es un polígono convexo.
El método de trazado de rayos sirve también para representar directamente imágenes de objetos definidos por árboles CSG sin necesidad de calcular el objeto resultante de las operaciones booleanas (ver figura 2.3.3.2).
Se trata del único caso en el que para representar
un objeto deberemos calcular varias intersecciones, aunque al
trabajar con primitivas geométricas sencillas el cálculo
seguirá siendo poco costoso.
El proceso de cálculo puede resumirse en cuatro
pasos (ver figura 2.3.3.2):
1º. Calcular todas las intersecciones del rayo
con cada una de las primitivas del árbol CSG y ordenarlas
por distancia 
.
2º. Decidir el intervalo que cubre cada objeto sobre el rayo.
3º. Efectuar las operaciones CSG 
,
indicadas en el árbol, sobre los intervalos.
4º. Seleccionar el extremo del intervalo resultante
que esté más cercano al origen del rayo. Este será
el punto de intersección con el objeto CSG.
Problema: ¿qué
pasa en la intersección o unión de dos objetos transparentes
que tienen materiales?. Hay que definir cómo se comportan
las operaciones de unión e intersección respecto
a los materiales en el caso de objetos transparentes de diferentes
propiedades internas (índice de refracción, color
debido a la absorción selectiva).
Para resolver la intersección deberemos combinar
las ecuaciones paramétricas del plano y de la recta del
rayo:
Normalmente resulta más conveniente suponer
que el rayo está definido por las intersección de
dos planos 
. Para hallar el punto de intersección
se hace indirectamente, calculando primero dos curvas pertenecientes
a la superficie que se cortan en el punto de intersección:
Resolver estas intersecciones supone encontrar la
solución a ecuaciones implícitas complicadas. Para
hacerlo deben emplearse en la mayoría de ocasiones métodos
numéricos, ya que no existe una expresión exacta.
Vamos a dar una breve descripción de un par de estos métodos:
* Método 1 : aplicación
del método de Newton para calcular 
.
Se trata de hallar 
(los valores
de los parámetros en el punto de intersección).
Es un método iterativo:
Hacemos una hipótesis
sobre los valores de 
En cada iteración
hallamos un nuevo par de valores a partir de los anteriores:
donde 
Para poder calcular la inversa del determinante de
esta matriz y resolver el problema, el Jacobiano debe ser distinto
de cero, lo cual sucede siempre que el rayo no sea tangente a
la superficie.
* Método 2 : transformación
de la ecuación de la intersección en una ecuación
implícita vectorial.
Esta ya es una ecuación implícita,
puesto que tiene la forma:
Ecuación implícita
de 3 variables (en realidad 3 ecuaciones, una para cada coordenada
x,y,z)
Podríamos aplicar también el método de Newton para resolverla, pero el problema es que los métodos de Newton para tres variables no siempre convergen.
Hay otros métodos numéricos para resolver
este tipo de ecuaciones basados en la minimalización
de la distancia. En ellos se trata de hacer variar los
parámetros 
hasta acercarse más
de un cierto umbral (métodos de búsqueda de
mínimos)
El problema es que puede encontrarse un mínimo
local o existir varios mínimos.
Como hemos visto anteriormente toda superficie implícita
tiene la forma 
, una sola ecuación
de tipo potencial (una magnitud se llama potencial cuando es escalar
y existe su gradiente, el vector formado por las derivadas respecto
a cada una de las coordenadas espaciales). Veamos cómo
podemos transformar una ecuación para el punto de intersección
de esta superficie con el rayo en una ecuación implícita
de una única variable:
Para resolver una ecuación de este tipo podemos
aplicar un método numérico para hallar los ceros
de una función. Un ejemplo es el método del
Gradiente. Si utilizamos el módulo de la función
F (ver figura) hallar el punto en que vale cero es equivalente
a buscar el punto de altura mínima. La forma de hacerlo
es suponer inicialmente un valor de la solución y a partir
de él intentaremos acercarnos al mínimo siguiendo
la dirección dada por la pendiente o gradiente de la función.
Para evaluar cuánto vale la pendiente en un punto s
hallaremos los valores de la función en dos puntos cercanos
a derecha e izquierda; s+r y s-r. El valor del radio
de búsqueda r se reducirá cuando lleguemos
a un punto en el que las pendientes hacia ambos lados son crecientes.
El algoritmo a emplear podría ser como sigue:
Si trabajamos en 3D el espacio de búsqueda
será una esfera (para n dimensiones seria una hiperesfera)
El método del gradiente tiene un inconveniente:
al 'descender' por la función podemos llegar a un mínimo
local, que no es el mínimo absoluto buscado de valor cero.
Una forma de evitar este problema es volver a la gráfica
de la función original F y buscar puntos en que la función
cambia de signo, en lugar de valores mínimos de su módulo.
Además de los casos que hemos visto hasta
hora, también hay métodos especiales para hallar
la intersección con representaciones específicas
de objetos.
* Distribución de alturas
(Height Field)
Este tipo de objeto, que se puede definir explícitamente
como tal en algunos trazadores (p.ej. en POVRay) tiene una estructura
especial que facilita el cálculo de las intersecciones.
La especificación de este objeto supone dar
la altura para un conjunto de vértices, que pueden disponerse
sobre una rejilla regular o distribuidos irregularmente sobre
un plano.
z = f(x, y)
Para calcular la intersección en el caso de
una rejilla regular se puede aplicar el algoritmo de Bresenham
o cualquier otro algoritmo de recorrido de puntos barridos por
una línea, visitando uno a uno, de manera direccional,
los elementos de la rejilla sobre los que pasa el rayo hasta encontrar
la intersección.
Para la estructura de TIN (red irregular de triángulos) se aprovecha también la información direccional, comenzando por el el triángulo más cercano y pasando luego al triángulo vecino que sea adyacente a la arista sobre la que pasa el rayo (ver figura). De nuevo, nos detendremos cuando encontremos un triángulo que intersecta al rayo.
* Datos en volumen (voxels,
octrees, etc.)
Si tenemos un objeto cuyo material va variando en
diferentes regiones, y esta variación (en densidad, color,
etc.) viene definida por una partición espacial, habrá
que recorrer ésta de forma direccional siguiendo al rayo.
Tenemos diferentes posibilidades para visualizar el objeto, según
el aspecto que queramos darle y la zona que deseemos explorar.
Una opción es visualizar solamente aquellos puntos en que
la densidad o variable distribuida por el volumen tome un valor
dentro de cierto rango (por ejemplo, en los datos resultantes
de una simulación de fluidos queremos ver las zonas donde
la presión alcanza un valor entre 1 y 2 unidades). En ese
caso recorreremos el volumen hasta encontrar un punto donde se
cumpla la condición.
Por el contrario, si suponemos que todo el objeto
tiene un cierto grado de transparencia, para saber qué
intensidad o color tenemos que asignar al rayo ya no bastará
con encontrar la intersección más cercana, sino
que habrá que evaluar cómo afecta al rayo su paso
a través de todo el volumen del objeto. Para efectuar este
cálculo se usarán modelos más sencillos,
como el que se propone a continuación:
Donde Cf es el
color del fondo
Supongamos que se ha asignado a cada celda i
a lo largo del recorrido del rayo un cierto color propio Ci
y un grado de transparencia i .El algoritmo que calcularía
el color del rayo deberá tener en cuenta que el color de
las celdillas traseras se ve modificado por el color de las que
hay delante, que actúan como filtros.
Algoritmo
desde s = n hasta 0 con paso = -1 hacer
pintar rayo con color C
Esta técnica para calcular la iluminación
de una escena ya no considera la luz como un conjunto de rayos,
como una magnitud vectorial, sino que la caracteriza como una
magnitud escalar, como una cierta cantidad de energía presente
en cada punto del espacio, y en particular sobre la superficie
de los objetos que hay que iluminar. A diferencia del trazado
de rayos, no nos interesará saber en qué dirección
exacta viaja cada porción de intensidad luminosa, sino
cuánta energía sale de cada parte de una superficie
y va a parar a otras superficies para llegar finalmente al observador.
En lugar de basarnos en la aproximación que hace la óptica
geométrica nos basaremos en ciertas aproximaciones de la
Termodinámica que estudia la transmisión del calor
por radiación.
Las principales características de este método
son:
4.3.1. DEFINICIÓN DE RADIOSIDAD
La radiosidad se define como la cantidad de energía que se transmite por unidad de tiempo y de superficie.
Está relacionada con la luminancia (energía
que sale de un determinado punto y va en una cierta dirección
cubriendo un cierto ángulo sólido).
4.3.2. ECUACIÓN GLOBAL DE LA RADIOSIDAD
Supongamos una escena formada por objetos cuya superficie
ha sido descompuesta en trozos y queremos calcular la radiosidad
que emite cada uno de esos trozos como resultado del intercambio
de energía radiante que se ha dado entre ellos hasta llegar
a un estado de equilibrio final.
Como no tenemos en cuenta la naturaleza ondulatoria
de la luz, la energía que procedente de diferentes sitios
llega a un mismo punto se sumará sin más, es decir,
la radiosidad tiene la propiedad de linealidad.
La energía que emite un trozo i se
deberá por un lado a la que emita por sí mismo (Ei)
y por otra parte reenviará una cierta proporción
(dada por el coeficiente de reflectancia difusa) de la que le
llega de otros trozos de la escena:
La energía que proviene de otros trozos será
una suma, cada uno de cuyos términos será proporcional
a la radiosidad que emite otro trozoj
. Es decir, una fracción, que
llamaremos Fij, de la energía
emitida por un trozo j llegará al trozo y:
Juntando esta ecuación con la anterior resulta
la ecuación global de la radiosidad para un trozo i:
Donde para cada trozo i:
es
la energía debida a su propia emisión.
es el coeficiente de reflexión
difusa.
es el factor de forma
o proporción de la energía emitida por un elemento
j llega al elemento i.
Este factor de forma puede definirse también
como la proporción de ángulo sólido que el
trozo j cubre en la escena desde el punto de vista del trozo i.
Puede demostrarse que Fij = Fji, y puede calcularse como:
Donde :
es el ángulo entre
el vector normal del trozo i y el vector que une i
con j.
es el ángulo entre
el vector normal del trozo j y el vector que une i
con j.
es la distancia entre
ambos trozos.
El factor de forma no tiene dimensiones físicas,
ya que es un factor de proporcionalidad; sólo depende de
las propiedades geométricas de los dos trozos en cuestión
y de su posición relativa en la escena. Por tanto, su valor
no va a cambiar si los trozos no se mueven ni cambian de forma.
La ecuación que hemos obtenido para cada radiosidad
Bi es en realidad un sistema de n ecuaciones con n incógnitas
para una escena con n trozos. Las incógnitas son los valores
de radiosidad para cada trozo.
Para resolver el sistema de ecuaciones de la radiosidad
podemos emplear los métodos clásicos de resolución
de sistemas de ecuaciones lineales, para hallar directamente los
valores de las incógnitas Bi. Este sería el método
directo de resolución de la radiosidad. Este método
requiere una gran capacidad de almacenamiento para guardar todos
los valores de la matriz (una escena puede tener miles de trozos,
y por tanto se requeriría calcular y almacenar millones
de factores de forma), y los cálculos también resultarán
muy costosos.
Es por ello por lo que se han desarrollado otros
métodos de resolución conocidos como métodos
progresivos. Estos métodos no se basan en considerar
la ecuacion de radiosidad como la representación del estado
final de equilibrio energético para resolverla directamente,
sino que tratan de ver cómo se desarrolla la interacción
de energía entre los trozos a lo largo del tiempo, reproduciendo
de esta forma el fenómeno físico. En el método
progresivo supone que la energía se encuentra inicialmente
en los objetos emisivos (fuentes de luz) y se calcula cómo
se va repartiendo paso a paso por la escena.
De esta forma no se necesita obtener la solución
exacta sino sólo una aproximación suficientemente
buena al estado de equilibrio final. Además, podemos ir
calculando los factores de forma conforme los vayamos necesitando,
sin tener que calcularlos todos previamente. Así necesitaremos
mucho menos espacio de almacenamiento, aunque es probable que
debamos calcular repetidas veces los mismos factores de forma.
Algoritmo del método de radiosidad progresiva
Necesitamos definir las siguientes variables:
acumula la radiosidad total
de cada trozo.
representa la cantidad de
energía que queda por emitir desde cada trozo i
hacia los demás.
El algoritmo inicializa estas variables suponiendo
que la energía está inicialmente concentrada en
las fuentes de luz, y luego entra en un bucle, en el que se escoge
aquél trozo que tiene más energía por enviar,
y ésta se distribuye a los demás trozos. El proceso
termina cuando la cantidad de energía que se envía
es más pequeña que un cierto umbral, que será
el error máximo que estamos cometiendo en la radiosidad.
Inicio
la energía
que tiene cada uno es la que emite por sí mismo
y es la misma
que le queda por enviar
Repetir
elegir 
para
que converja más rápido
enviar la energía de este trozo a todos los demás trozos mediante :
hacer : error
poner a cero 
:
hasta
( error < umbral )
Ejemplo: Vamos a comparar
el funcionamiento de los dos métodos con un ejemplo muy
sencillo.
Tenemos tres trozos en la escena. Supongamos que
los factores de forma toman los valores: Fii=0, F12=0.4,
F13=0.6 y F23=0.2. Uno de los trozos está
emitiendo por sí mismo una radiosidad de 1 (es la fuente
emisora de luz) y todos los materiales tienen un coeficiente de
reflectancia =0.5.
La formulación de la matriz sería la
siguiente:
Que puede resolverse mediante el método directo,
dando B1 = 1.16745, B2 = 0.27123 y B3
= 0.37736.
Veamos ahora la versión progresiva. Seguimos
los pasos del algoritmo descrito. En la siguiente tabla se muestra
la evolución de la distribución de energía
en los tres trozos. Observamos que las cantidades de energía
que se van enviando se hacen cada vez más pequeñas
y los valores de la radiosidad convergen a la solución
exacta. En la tabla se han destacado en negrita los valores máximos
de la radiosidad que queda por enviar en cada iteración.
|
|
|
|
|
| |
 |
4.3.4. CÁLCULO DE LOS FACTORES DE FORMA
Como hemos visto, en cualquiera de los dos métodos es necesario
calcular los factores de forma para saber qué porcentaje
de energía hay que enviar desde un trozo a los demás.
La forma directa de efectuar este cálculo es utilizar la
integral espacial que define el factor de forma. Desafortunadamente,
esta integral solamente puede resolverse de forma analítica
para ciertos casos, en concreto cuando los dos trozos son circulares
o son polígonos, o cuando uno de ellos se considera infinitesimal
y el otro es un polígono.
Sin embargo, los factores de forma deben tener además en
cuenta la posibilidad de oclusión o sombra de producida
por otros objetos. Esta posibilidad resulta un grave inconveniente
para los métodos analíticos, porque habría
que introducir una nueva función Hij en la integral
que representara la función de visibilidad entre cada trozo
diferencial i y j, lo que produciría una
función total muy complicada y difícil de integrar
analíticamente.
La otra posibilidad es efectuar la integración de forma
numérica o aproximada. En algunos casos se aproxima uno
de los dos trozos como un punto infinitesimal, lo cual facilita
mucho el cálculo. Un método fácil de implementar
es el método del hemicubo, en que se proyecta la escena
tal como es vista desde el trozo que emite la energía,
sobre una ventana. Contando los pixels que cubre cada objeto,
y según la posición del pixel en la ventana, puede
averiguarse de forma aproximada el factor de forma de cada trozo
al que hay que enviar energía.
A continuación se comentan otros métodos numéricos.
Mediante el teorema de Stokes la integral de superficie que define
el factor de forma puede transformarse en una integral que recorre
la frontera de la superficie, y ésta puede resolverse mediante
métodos numéricos de integración en una dimensión,
pero sigue existiendo el problema de la visibilidad.
Los métodos de Montecarlo son un tipo especial de métodos
para el cálculo de integrales que se basan en calcular
valores para puntos escogidos al azar. Por ejemplo, si tuviéramos
que calcular el área de una superficie de forma extraña
podríamos escoger una serie de puntos xi , yi
al azar en una región del plano que contiene a nuestra
superficie. El porcentaje de puntos que caigan dentro del área
buscada respecto al total nos dará el tamaño relativo
de este área respecto a la región del plano donde
hemos situado los puntos si éstos han sido generados mediante
una distribución aleatoria uniforme.
Sean N y N' el número de puntos dentro de las superficies
S y S' respectivamente. Entonces podemos aproximar la relación
entre el valor de las dos áreas como : 
siendo N el número de puntos en S y N' el número
de puntos en S'-S . En la figura siguiente podemos ver un ejemplo
de cómo se realizaría:
Para calcular el factor de forma tenemos que estimar qué
porcentaje de área sobre el máximo posible ocupa
un trozo visto desde otro. Para ello podemos lanzar rayos desde
uno de ellos con una orientación al azar. Midiendo el porcentaje
de rayos que atraviesan el otro trozo respecto al número
total que hemos lanzado sabremos lo grande que resulta visto desde
el primero. Este sistema tiene la ventaja adicional de que incluye
la visibilidad, ya que si el rayo atraviesa un objeto intermedio,
entonces no debemos contarlo.
En los métodos anteriores la descomposición de los
objetos de la escena en trozos debía realizarse antes de
calcular la radiosidad , lo cual no resulta muy eficiente, ya
que la elección del tamaño de los trozos puede no
ser adecuada para todas las zonas. Otros métodos permiten
efectuar la descomposición en trozos al mismo tiempo que
van calculando los factores de forma. Si el factor de forma es
muy grande es que los dos trozos son demasiado grandes o están
demasiado próximos, y para obtener mayor exactitud conviene
subdividirlos. La división progresiva en trozos puede también
efectuarse según la distribución de energía
durante el método progresivo, refinando la descomposición
en trozos en aquellos lugares de la superficie donde hay mayor
variación de radiosidad (por ejemplo en los bordes de una
sombra).
Si estamos empleando la radiosidad dentro de un trazado de rayos el calculo del color no supone ningún problema, basta con calcular la aportación de cada rayo sobre el pixel correspondiente. Pero si estamos utilizando trozos poligonales para luego proyectarlos sobre la ventana, debemos buscar una forma adecuada de asignar colores a los vértices de los polígonos para que luego se interpole el color en los pixels internos.
La solución más trivial es asignar un mismo color
a todos los vértices de un trozo según la radiosidad
acumulada para ese trozo en cada una de las componentes RGB. Pero
entonces todo el trozo será rellenado con un color uniforme,
y se notará la discontinuidad de la iluminación
entre unos trozos y otros.
Otra solución mejor es asignar a cada vértice el
color en función de la intensidad de energía acumulada
en cada uno de los triángulos que se conectan a él.
La forma más exacta de determinar esta función f
sería utilizar una integral, para dar mayor importancia
a las zonas del trozo vecino que están más cercanas
al vértice, por ejemplo añadiendo un factor inverso
con el cuadrado de la distancia:
: intensidad
del polígono vecino, d: distancia de cada dS al vértice
Sin embargo, el cálculo de esta integral es costoso y se
puede utilizar simplemente la media entre las intensidades de
los triángulos vecinos, que funciona bien cuando las áreas
de los polígonos son similares y no tienen formas alargadas:
Sin embargo, existirán ciertos casos en los que no querremos
que la coloración sea continua, por ejemplo en las juntas
entre el suelo y la pared de una habitación, porque entonces
la esquina parecería redondeada en lugar de variar bruscamente
el color en el ángulo. Podemos utilizar las diferencias
entre los vectores normales de los trozos para determinar si debemos
producir una continuidad en la coloración o no.