Mapeado de fotones
El concepto de Mapeado de fotones (en inglés Photon mapping), fue introducido por en junio de 1996. Él, al igual que los que se dedican a la informática gráfica, tuvo la necesidad de un algoritmo que fuera capaz de renderizar imágenes de geometría compleja con iluminación global; un algoritmo que fuera capaz de manejar cualquier tipo de geometría y de BRDF (Bidirectional reflectance distribution function).
Mapeado de Fotones (Photon Mapping)
En aquella época, estaba de moda el cálculo de radiosidad basado en elementos finitos (irradiance maps).
Los métodos de radiosidad tienen problemas con los BRDF especulares y son demasiado costosos cuando la geometría se complica demasiado.
Aparecieron alternativas a los elementos finitos en forma de técnicas multipaso, illumination maps y las técnicas de ray tracing basadas enteramente en Monte Carlo.
La mejor alternativa sin duda fue la última de ellas, pero provocaba cierto ruido en la imagen debido a la varianza de los resultados. Eliminar este ruido presenta un sobrecoste demasiado grande.
El mapeado de fotones fue desarrollado por Jensen como una alternativa a las técnicas de trazado de rayos basadas enteramente en Monte Carlo. El fin era obtener las mismas ventajas pero con un método más eficiente que no sufriera complicaciones por el ruido.
Para ello parece correcto pensar que hay que usar el mismo algoritmo basado en el trazado de rayos y además hay que procurar un algoritmo eficiente de transporte de la luz en la escena ya que tanto las luces como el observador son parte primordial de la síntesis de imágenes. También queremos utilizar técnicas de Monte Carlo vistas anteriormente pero con la certidumbre de que la componente de radiación se mantiene suave a lo largo de grandes regiones para la mayoría de los modelos. Para estas regiones parece razonable pues, almacenar y reutilizar la información extraída sobre su iluminación. Y todo ello sin dividir las superficies en trozos finitos, queremos que nuestro modelo maneje cualquier tipo de objeto.
La primera idea para solucionar el problema es pues, la de desacoplar la representación de la iluminación de la geometría. Esto nos permite tanto manejar geometría arbitraria como modelos complejos.
La segunda idea es que la iluminación en la escena puede ser almacenada como puntos en una estructura de datos global, el mapa de fotones, en inglés photon map. Muchas alternativas a los puntos fueron consideradas pero todas fallaban en una de las tres condiciones: capacidad de representar cualquier tipo de iluminación, estar desacoplado frente a la geometría y ser compacto. Por eso los puntos son la manera más flexible posible de manejar superficies de cualquier tipo de BRDF. Estos puntos además de su posición almacenarán también información sobre la dirección de incidencia de la luz y otros factores que nos facilitarán los cálculos.
El mapa de fotones puede entenderse como una caché de caminos de luces en un trazado de caminos (path tracing) direccional y podría ser utilizado ciertamente para tal método. Pero también puede usarse en un método diferente de estimación de la iluminación basada en la estimación de densidad. Esta estimación de densidad tiene la ventaja que su error es de una frecuencia mucho más baja que el que se da en los tradicionales métodos de Monte Carlo.
El método de estimación de densidad es mucho más rápido que un trazador puro basado en Monte Carlo. Sin embargo pagamos el precio de utilizar una estimación de densidad y por tanto un método que no nos dará siempre un rendimiento correcto, y que siempre dependerá de que para que converja más a la solución correcta se deberán almacenar y utilizar cuantos más fotones mejor.
Usaremos el nombre 'Mapeado de fotones' para designar el algoritmo que genera, almacena y usa la iluminación como puntos, y el 'Mapa de fotones' como la estructura usada para procesar estos puntos. Así mismo,, el 'Trazado de fotones' será la técnica usada para generar los puntos que representan la iluminación en el modelo.
El método del mapeado de fotones es un método de dos pasos donde los pasos son:
- Trazado Fotónico (Photon Tracing), construir el mapa de fotones trazando fotones desde las luces y a través de la escena.
- Radiación estimada (Radiance Estimate), estimar la radiación producida en un punto de la escena mediante estimación de densidad.
Así el mapa de fotones será construido usando 'Trazado fotónico' donde los fotones son emitidos desde las luces y almacenados al interactuar con las superficies del modelo. Una vez construido el mapa de fotones lo utilizaremos para calcular la luz radiada.
Trazado Fotónico (Photon Tracing)
El trazado fotónico es el proceso de emitir fotones desde las fuentes de luz y trazarlos a través de la escena. Esta será la técnica usada para construir el mapa fotónico. Vamos a ver cómo los fotones son generados en las fuentes de luz y cómo podemos seguir su recorrido en la escena de forma eficiente. Siendo esto la base para construir un buen mapa de fotones.
Emisión Fotónica (Photon Emission)
Las luces pueden ser de muchos tipos y en este apartado veremos como emitir fotones de forma eficiente desde cada una de ellas ya que el mapeado fotónico admite cualquier tipo de luz.
Así como pasa en la realidad, un enorme número de fotones son emitidos desde cada fuente de luz. La potencia de la luz será dividida entre todos los fotones emitidos por igual, y por eso cada fotón transportará una fracción de la potencia de la fuente de luz inicial. Es importante remarcar aquí que la potencia de los fotones será proporcional al número de fotones emitidos y no al número de fotones almacenados en el mapa de fotones.
La emisión desde una luz puntual será aleatoria en todas las direcciones esféricas alrededor del punto de luz. La emisión en una luz direccional será aleatoria en posición pero con la dirección de la luz. Y la emisión desde luces con formas, por ejemplo esféricas y planares, aleatoria sobre su superficie.
Dispersión y Reflexión de Fotones (Photon Reflection and Scattering)
Cuando un fotón colisiona con un objeto, este puede ser con las mismas probabilidades reflejado, transmitido por refracción o absorbido. Que pase una cosa u otra se decide probabilísticamente basándonos en los parámetros del material de la superficie en colisión. La técnica para decidir el tipo de interacción se conoce como ruleta rusa.
El método de la ruleta rusa es una técnica estadística que nos servirá para desestimar fotones que no sean importantes a fin de concentrarnos sólo en los que si lo sean. También se usa para asegurarse de que los fotones almacenados en el mapa fotónico tengan aproximadamente la misma potencia de luz. Esto será necesario para una buena estimación de radiación.
La idea básica de la ruleta rusa es que podemos tomar muestras aleatorias para eliminar trabajo y aun así obtener un resultado correcto. Es por ello una de las técnicas estándar Monte Carlo. Con la ruleta rusa decidiremos si un fotón en colisión es reflejado o absorbido. Dado un material con reflectividad d, y un fotón que colisiona con él con potencia sigma:
if (random()<d) reflejar el fotón con potencia sigma else el fotón es absorbido
La idea intuitiva que hay debajo de esto es que si lanzamos 1000 fotones contra una superficie con reflectividad 0.5, podemos bien reflejar los 1000 fotones con la mitad de potencia que tenían antes o reflejar solo 500 con la potencia intacta. La ruleta rusa nos seleccionará esos 500 fotones, reduciéndonos el cómputo requerido por el trazado fotónico.
Por tanto a partir de la colisión de un fotón y gracias a la probabilidad lanzaremos otros que le siguen en direcciones de reflexión, refracción o simplemente desecharemos el fotón porque es absorbido por el material. Sin embargo cada colisión de un fotón provoca que lo almacenemos en el mapa fotónico como veremos a continuación.
Almacenamiento Fotónico (Photon Storing)
Como hemos mencionado ya, los fotones son almacenados a medida que colisionan contra superficies difusas o más bien no especulares. La razón de esto es que almacenar fotones que colisionan contra superficies especulares o reflectantes, no nos aportan información pues la probabilidad de que un fotón incida por la dirección especular es muy pequeña o cero. Por tanto si queremos simular reflexiones lo mejor será simularlas mediante el rayotrazado, en inglés raytracing. Para todas las otras interacciones fotón-superficie, el mapa fotónico deberá tener información sobre ellas.
Es importante observar que los fotones representan la iluminación (flujo) que llega a las superficies. Esto es una optimización notable que nos da la llave para aproximar la iluminación reflectada en muchos puntos de la superficie.
Para cada interacción fotón-superficie, serán almacenados la posición del fotón, la potencia del mismo y la dirección incidente.
Dese el momento que queremos que nuestra estructura de mapa fotónico sea útil para el algoritmo del mapeado fotónico, esta deberá ser muy rápida en encontrar los fotones vecinos más cercanos en 3 dimensiones a una posición dada. Para ello Jensen se basó en la estructura que vamos a utiliza nosotros también, los Kd-Tree balanceados.
Kd-Tree balanceados
La complejidad por encontrar un fotón en un Kd-Tree balanceado es de O(log N), donde N es el número de fotones en el mapa de fotones.
La eficiencia para encontrar los fotones más cercanos a una posición dada es un punto crítico dentro del mapeado fotónico. Afortunadamente, la simplicidad de los Kd-Trees permite implementar un algoritmo sencillo y eficiente de búsqueda para tal fin. Este algoritmo será una extensión directa de los algoritmos de búsqueda binaria estándar.
Para encontrar los vecinos más cercanos en un Kd-Tree balanceado, empezaremos por la raíz y añadiremos fotones a la lista de resultados si estos están dentro de una cierta distancia. Para encontrar los n fotones más cercanos, la lista de resultados será ordenada como si el que está más lejos pudiera ser eliminado si otro fotón más cercano fuera encontrado. Y así sucederá iterativamente sobre el Kd-Tree hasta que encontremos los fotones más cercanos.
Para el algoritmo de búsqueda será necesario que un radio máximo inicial le sea definido con tal de limitar la búsqueda. Un buen radio de búsqueda permitirá al algoritmo realizar una búsqueda óptima reduciendo el número de fotones testeados.
Con el Kd-Tree y un algoritmo de búsqueda eficaz y rápido sobre él, obtendremos la lista de los n fotones más cercanos a una posición en 3d dada. Ello nos permitirá pasar a calcular la estimación de radiación sobre ese mismo punto de la forma que veremos a continuación.
Radiación Estimada (Radiance Estimate)
La información en el mapa fotónico puede ser usada para calcular la radiación que sale desde una superficie en una dirección dada. Desde el momento que la dirección de llegada es almacenada con cada fotón, podremos integrar la información con cualquier BRDF.
Para calcular la radiación , que sale de un punto de intersección en una superficie con BRDF , buscaremos primero los fotones con menor distancia a . Basándonos en la suposición de que cada fotón representa el flujo , que llega a desde la dirección , podremos integrar toda esta información dentro de la ecuación del rendering como sigue:
Aquí se usa una aproximación a donde una esfera centrada en es expandida hasta que contenga a fotones y tenga radio . Luego será aproximada como . El resultado es una ecuación que nos permite computar una estimación sobre la radiación reflejada en cualquier posición de cualquier superficie usando el mapa de fotones.
Esta será la base de la técnica del mapeado fotónico y aunque tanto Jensen como otros han hecho pequeñas aportaciones para mejorar el resultado en ciertos casos especiales, la base del método sigue intacta. Por tanto, el mapeado fotónico es una forma sencilla, rápida y ajustable de calcular cual es la parte de iluminación global que recae sobre una situación dada en 3 dimensiones.
Y aunque esto también nos lo podía solucionar la técnica de la radiosidad, el mapeado fotónico funcionará con cualquier tipo de material y de fuente de luz, y en un tiempo mucho mejor que en la anterior técnica.