Repositorio Institucional de Documentos

2 Clustering Bidireccional en Iluminaci´on Global Basada en Puntos Resumen La s´ıntesis de im´agenes fotorrealistas por ordenador, requiere modelar y simular de forma precisa las interacciones entre luz y materia. Para conseguir este realismo, no s´olo se debe calcular la iluminaci´on que proviene de las distintas fuentes de luz que iluminan la escena, sino que tambi´en se debe tener en cuenta la energ´ıa reflejada entre las distintas superficies, denominada iluminaci´on global. A pesar de los grandes avances tecnol´ogicos, la generaci´on de este tipo de im´agenes requiere de una gran cantidad de tiempo y recursos. En producciones cinematogr´aficas este coste tiene un importante impacto debido a la complejidad de las escenas modeladas adem´as de la necesidad de generar miles de fotogramas. Por ello, las productoras invierten millones de d´olares en potentes clusters de c´alculo para la generaci´on de contenido digital de sus pel´ıculas, siendo la investigaci´on y desarrollo de nuevas t´ecnicas un tema de gran inter´es. En los ´ultimos a˜nos, han surgido t´ecnicas capaces de calcular la iluminaci´on global de forma aproximada. A pesar de ofrecer resultados aproximados, son lo suficientemente convincentes como para que sus errores pasen desapercibidos. Algunos de estos m´etodos simulan la luz reflejada por las superficies como un conjunto de luces virtuales (VPLs), calculando su contribuci´on mediante una evaluaci´on jer´arquica de las mismas, agrupando VPLs similares como una ´unica fuente de energ´ıa. Debido a su eficiencia, estas t´ecnicas han sido extensamente utilizadas en multitud de producciones cinematogr´aficas. A pesar de su eficiencia, estos m´etodos no escalan bien con el n´umero de p´ıxels a iluminar. Este hecho se agrava con las enormes resoluciones necesarias en la creaci´on de contenido digital. La alta definici´on se ha convertido en un est´andar y el contenido 3D se est´a implantando progresivamente, donde la generaci´on de im´agenes desde m´ultiples puntos de vista es necesaria. Sin embargo, las muestras generadas desde la c´amara presentan una coherencia que puede ser explotada para aproximar la luz que reciben. En este proyecto se aborda el desarrollo de una nueva t´ecnica para el c´alculo de la iluminaci´on global basada en VPLs, que explota las similitudes entre las muestras desde la c´amara y las VPLs para reducir de forma adaptativa la cantidad de computaci´on, mediante la evaluaci´on jer´arquica de las contribuciones de las luces sobre los puntos a iluminar. De esta manera, podemos desarrollar un algoritmo capaz de generar im´agenes o grupos de im´agenes de alta resoluci´on con gran cantidad de elementos de iluminaci´on con costes sublineales, tanto en el n´umero de luces virtuales como en el n´umero de p´ıxels. Para llevar a cabo esta tarea, implementamos el algoritmo escalable Point Based Color Bleeding, adapt´andolo a un framework basado en trazado de rayos, y planteando mejoras para evitar algunos de sus problemas m´as comunes. As´ı mismo, desarrollamos una nueva t´ecnica capaz de aproximar la iluminaci´on global jerarquizando el conjunto de muestras generadas desde la c´amara para finalmente combinar ambos algoritmos en una t´ecnica que minimiza el coste del renderizado, con ´ordenes de complejidad sublineales con respecto del n´umero de luces y muestras. 3 Agradecimientos Quiero dar gracias a Adri´an por su implicaci´on y ayuda a lo largo de la realizaci´on del proyecto. A ´el y a Diego por darme la oportunidad de trabajar en otros proyectos del grupo. Y por supuesto a todos los compa˜neros del Graphics and Imaging Lab. Tambi´en a mi familia y amigos por su apoyo a lo largo de estos a˜nos. 5 6 ´ Indice general 1. Introducci´on 1 2. Conocimiento previo 3 2.1. Iluminaci´on indirecta con luces virtuales . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2. Trabajoprevio ...................................... 5 3. Point-Based Global Illumination 7 3.1. Preproceso ........................................ 7 3.2. C´alculo de la iluminaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2.1. Condiciones de parada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2.2. Singularidades .................................. 10 3.2.3. Testdevisibilidad ................................ 11 4. Clustering de muestras de la c´amara 13 4.1. Preproceso ........................................ 13 4.2. C´alculo de la iluminaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.2.1. Condiciones de parada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 5. Clustering bidireccional 17 5.1. Preproceso ........................................ 17 5.2. C´alculo de la iluminaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 5.2.1. Visibilidad .................................... 18 5.2.2. Condiciones de parada y refinado de pares . . . . . . . . . . . . . . . . . . . 19 6. Resultados 21 6.1. An´alisisderendimiento ................................. 21 6.1.1. An´alisis de rendimiento de PBGI . . . . . . . . . . . . . . . . . . . . . . . . 21 6.1.2. An´alisis de rendimiento del m´etodo de clustering de muestras . . . . . . . . 22 6.1.3. An´alisis de rendimiento del m´etodo bidireccional . . . . . . . . . . . . . . . 23 6.2. An´alisis de calidad y par´ametros . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 6.2.1. Algoritmo de clustering deVPLs........................ 24 6.2.2. Algoritmo de clustering demuestras ...................... 24 6.2.3. Algoritmo de clustering de VPLs y muestras . . . . . . . . . . . . . . . . . 24 7 8´ INDICE GENERAL 6.2.4. An´alisisdeerror ................................. 24 6.3. Resultadosadicionales.................................. 27 7. Conclusiones 31 7.1. Discusi´on y trabajo futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 7.2. Conclusi´onpersonal ................................... 32 7.3. Diagrama temporal del proyecto . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 A. M´etodos auxiliares 39 A.1. Muestreo uniforme de superficies . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 B. Resultados adicionales 41 B.1.Tablasderendimiento .................................. 41 Cap´ıtulo 1 Introducci´on La s´ıntesis de im´agenes fotorrealistas por ordenador, requiere modelar y simular de forma precisa las interacciones entre luz y materia. Para conseguir este realismo, no s´olo se debe calcular la iluminaci´on que proviene de las distintas fuentes de luz que iluminan la escena, sino que se debe tener en cuenta la energ´ıa reflejada entre las distintas superficies, denominada iluminaci´on global. Sin embargo, su c´alculo requiere de una ingente cantidad de tiempo y recursos. En producciones cinematogr´aficas este coste tiene un especial impacto: debido a la complejidad de las escenas generadas, un ´unico fotograma requiere horas de c´alculo; por ejemplo, en Cars 2 cada fotograma necesit´o una media de 11.5 horas de render 1 2. Este coste por fotograma se multiplica por la cantidad de frames que son necesarios renderizar (129600 para 90 minutos a 24 fps). A pesar de su elevado coste, prescindir de la iluminaci´on global ofrece resultados poco realistas como se puede observar en la Figura 1.1, y por ello las productoras invierten millones de d´olares en grandes clusters de c´alculo para la generaci´on del contenido digital de sus pel´ıculas, siendo el estudio y desarrollo de nuevas t´ecnicas eficientes de renderizado un tema de gran inter´es. Figura 1.1: La iluminaci´on global es imprescindible para dotar realismo a una imagen. Como se puede observar, incluso con modelos geom´etricos detallados, la ausencia de la luz reflejada entre las superficies (derecha) oculta muchos de los detalles y da un resultado antinatural. Por el contrario, la iluminaci´on global permite generar im´agenes m´as cre´ıbles y fieles a la realidad (derecha). Fuente: [TL04]. c 2011 Dreamworks Animation LLC. Diversos trabajos resuelven la iluminaci´on global model´andola como un conjunto de luces virtuales (VPLs) que simulan la energ´ıa reflejada por las superficies. La contribuci´on de estas luces 1http://www.cnet.com/news/new-technology-revs-up-pixars-cars-2 2En Pixar, el coste est´andar es de alrededor de 10 horas por fotograma. Fuente: Henrik Wann Jensen. 1 8CAP´ ITULO 3. POINT-BASED GLOBAL ILLUMINATION de tener un ´area asociada, se puede realizar una analog´ıa con el concepto de VPL descrito en el Cap´ıtulo 2. El ´area Ase calcula como la superficie total que abarcan las primitivas de la escena dividida por el n´umero de muestras generadas, la normal del disco es la normal de la superficie en la posici´on de la VPL. Finalmente, asumiendo que las superficies tienen una reflectancia Lambertiana, la luz emitida depende ´unicamente de la energ´ıa recibida desde las fuentes de luz, siendo calculada como: Le(~ωo) = Aρ πLih~n, ~ωoi+.(3.1) siendo ρel albedo1de la superficie. Aunque este m´etodo permite generar millones de puntos de forma eficiente, se ignora si est´an ocluidos con respecto de las luces de la escena, por lo que se pueden generar muestras que no contribuir´an a la iluminaci´on global. N´otese que el resto del algoritmo es independiente de c´omo se generan las luces virtuales pudiendo utilizar otras alternativas (e.g. Transporte de part´ıculas [Kel97]). El ´arbol de luces Con el fin de evaluar de una forma eficiente la contribuci´on de las VPLs generadas, son introducidas en una jerarqu´ıa creando clusters de luces virtuales. Bas´andonos en [Chr08], utilizamos un ´arbol de tipo octree. Aunque se podr´ıa haber utilizado otro tipo de estructuras de particionamiento del espacio, un octree nos permite construir la jerarqu´ıa de forma r´apida. Durante la generaci´on del ´arbol, los nodos se subdividen hasta que las hojas contienen un n´umero m´aximo de VPLs. En la implementaci´on realizada, para una gesti´on ´optima de la memoria se utiliza un m´aximo de ocho VPLs por hoja. 3.2. C´alculo de la iluminaci´on Para calcular la iluminaci´on global de forma eficiente, para cada punto a iluminar xrecorremos el ´arbol desde su nodo ra´ız, refinando el corte del ´arbol hasta que se alcanza la condici´on de parada (ver Secci´on 3.2.1). La iluminaci´on en xse calcula como la suma de la contribuci´on de cada uno de los nodos del corte (Ecuaci´on 2.5). Esto significa que es necesario evaluar, adem´as de la BRDF y los t´erminos de atenuaci´on geom´etrica, la visibilidad de xdesde los nodos (ver Secci´on 3.2.3), y la radiancia emitida desde cada nodo. En el caso de que el nodo es una hoja (una VPL individual), calculamos su contribuci´on evaluando la Ecuaci´on 2.5. N´otese que el t´ermino geom´etrico puede producir singularidades en forma de puntos brillantes, en puntos cercanos a la VPL; en la Secci´on 3.2.2 describimos c´omo gestionarlas. En caso de que el nodo a evaluar sea un cluster de VPLs, se aproxima su contribuci´on como la suma de todas las VPLs que contiene. ´ Esta es dependiente de la direcci´on de emisi´on, pero de baja frecuencia, por lo que proyectamos la suma de las contribuciones de las luces virtuales en arm´onicos esf´ericos. M´as detalles sobre arm´onicos esf´ericos se pueden encontrar en [Gre03]. Para almacenar iluminaci´on difusa, se considera que 3 niveles de arm´onicos esf´ericos (9 coeficientes) ofrecen suficiente precisi´on [RH01, Chr08]. 3.2.1. Condiciones de parada Para determinar si un cluster es lo suficientemente preciso se utiliza el valor de su ´angulo s´olido ΩLcon respecto del punto a iluminar. El ´angulo s´olido, definido como la proyecci´on de un ´area sobre una esfera de radio unidad, mide el tama˜no aparente de una superficie Sdesde un punto x y es calculado como: 1El albedo es la cantidad de radiaci´on que cualquier superficie refleja respecto a la radiaci´on que incide sobre la misma. 3.2. C ´ ALCULO DE LA ILUMINACI ´ ON 9 ΩL=ZA h~ns, ~ωsi d(s, x)2ds ≈kAkh~nA, ~ωAi d(A, x)2.(3.2) con Ala superficie de Svisible desde xcon ´area kAk,~nsla normal en un punto diferencial s∈A, ~ωsyd(s, x) direcci´on y distancia desde sax, y ~nA,~ωAyd(A, x) la normal, direcci´on y distancia desde un punto representativo en Ahasta x. El ´area proyectada de un nodo, se puede aproximar como la suma de las ´areas proyectadas de las VPLs que contiene. Al igual que la energ´ıa emitida, el ´area proyectada de una VPL var´ıa en funci´on de su orientaci´on. Por ello, se procede de manera an´aloga almacenando su valor en una base de arm´onicos esf´ericos. De esta forma, es posible obtener el valor aproximado del ´area proyectada de un cluster y calcular su ´angulo s´olido. Sin embargo, en ocasiones cuando los clustes son muy grandes, el error introducido por esta aproximaci´on provoca artefactos en la imagen. Para evitarlos, calculamos un segundo valor del ´area proyectada ΩSa partir de la esfera de radio rque envuelve el volumen de un cluster como: ΩS=πr2 d2.(3.3) Para acelerar el proceso de renderizado, se impone una condici´on adicional. A menudo, los puntos a iluminar est´an orientados de tal forma que nunca recibir´an energ´ıa de muchas de las VPLs. Esta situaci´on puede ser detectada permitiendo evitar el recorrido de ramas completas que nunca contribuir´an a la iluminaci´on. Para calcular esta condici´on de corte, se calcula el producto escalar entre la normal del punto x,~nxy los vectores desde xhasta las ocho esquinas de la bounding box del cluster como se muestra en la Figura 3.3. Si alguno de los productos escalares es mayor que cero, indica que puede haber VPLs dentro del cluster que pueden irradiar el punto x; si todos los productos escalares son menores que cero, se finaliza el recorrido para ese nodo y sus hijos. Denominamos a esta condici´on de parada ’Test del horizonte’. Por tanto, las condiciones de parada del algoritmo de clustering de VPLs son: 1. ΩL´ Angulo s´olido de un nodo calculado de acuerdo a la Ecuaci´on 3.2. 2. ΩS´ Angulo s´olido de un nodo calculado de acuerdo a la Ecuaci´on 3.3. 3. Test del horizonte. Figura 3.2: El c´alculo del valor ΩSpermite evitar las imprecisiones introducidas por los arm´onicos esf´ericos para calcular el ´area proyectada. Izquierda: Resultado obtenido aplicando ΩS.Derecha: Resultado obtenido sin utilizar ΩS. 10 CAP´ ITULO 3. POINT-BASED GLOBAL ILLUMINATION nx x Figura 3.3: Muchos de los clusters del ´arbol no contribuyen a la iluminaci´on debido a la orientaci´on de los puntos a iluminar. Esta situaci´on se detecta calculando el producto escalar entre la normal las muestras, y los vectores que apuntan a las esquinas de la bounding box del cluster. Si todos los productos escalares son menores que cero, se descartar´an todas las ramas que dependen de ese nodo. 3.2.2. Singularidades Las singularidades consisten en picos de energ´ıa producidos por VPLs a distancias pr´oximas a cero provocando que el t´ermino geom´etrico (Ecuaci´on 2.4) tienda a infinito. Una forma de solventar este problema consiste en establecer un valor m´aximo para el t´ermino geom´etrico. Sin embargo, esta aproximaci´on produce una p´erdida en la iluminaci´on. En escenas difusas esta p´erdida de energ´ıa solo es visible en ciertas ´areas (esquinas o geometr´ıa compleja), pero es significativo en materiales brillantes donde estos picos de energ´ıa proceden de las propiedades de reflectancia de los objetos [KFB10]. La soluci´on adoptada para evitar estas singularidades consiste en modelar las VPLs como luces virtuales esf´ericas (Virtual Spherical Lights o VSLs) [HKWB09]. Conceptualmente, la VSL expande la luz puntual 0D en una esfera de radio finito 3D como muestra la Figura 3.4. De esta forma la energ´ıa recibida se calcula integrando la radiancia saliente sobre el ´angulo s´olido de la VSL, eliminando el t´ermino geom´etrico. Figura 3.4: Luz esf´erica virtual. Un punto de una superficie xcon normal ~nxy vista desde una direcci´on ~ωorecibe energ´ıa de una VSL desde todo el ´angulo s´olido Ωj, localizada en pj, con normal ~npj. Fuente: [HKWB09]. Calculamos la energ´ıa reflejada en un punto xdesde una VPL modelada como una VSL jde radio rj, integrando su radiancia en el ´angulo s´olido Ωjcomo: Lr(x, ~ωo) = LV P L πr2 jZΩi fr(x,~ l, ~ωo)h~nx,~ li+fr(y,~ ij,−~ l)h~npj,−~ li+V(x, y)dl. (3.4) siendo LV P L la radiancia recibida de todas las fuentes de luz por la VPL modelada como VSL. 3.2. C ´ ALCULO DE LA ILUMINACI ´ ON 11 Para simplificar el c´alculo de la Ecuaci´on 3.4 hacemos algunas aproximaciones: 1. Calculamos la visibilidad entre el punto xy el centro de la VSL, pj. Asumiendo un n´umero suficiente de luces virtuales, este test es preciso. 2. El vector normal y la BRDF de los puntos jen las superficies contenidas en la VSL son aproximados por la normal ~npjy la BRDF de la posici´on de la VSL pj. 3. Teniendo en cuenta que modelamos la iluminaci´on global difusa, la BRDF de la VSL es constante y puede ser extra´ıda de la integral. 4. Utilizamos un radio fijo para las VSLs calculado multiplicando el radio de la VPL, rV P L, por una constante k. 5. La radiancia recibida por la VSL de las fuentes de luz es igual a LV P L =Liπr2 V P L, siendo Lila radiancia recibida en la posici´on pjdesde las fuentes de luz. Con estas asunciones, simplificamos la Ecuaci´on 3.4 como: Lr(x, ~ωo) = Li k2 ρj πV(x, pj)ZΩi fr(x,~ l, ~ωo)h~nx,~ li+h~npj,−~ li+dl. (3.5) siendo ρjel albedo del punto pj. Utilizando este m´etodo, se elimina el t´ermino 1/d2de la ecuaci´on, evitando las singularidades cuando una VPL est´a muy cerca de una superficie. Para resolver la integral de la Ecuaci´on 3.5 utilizamos integraci´on por Monte Carlo aproximando su valor como: Lr(x, ~ωo)≈ Le k2 ρj πV(x, pj) N X i=1 fr(x,~ li, ~ωo)h~nx,~ lii+h~npj,−~ lii+1 p(~ li).(3.6) siendo Nel n´umero de muestras, y p(~ li) la probabilidad de generar la muestra ~ li, en nuestro caso uniforme en el ´angulo s´olido de la VSL en x. Los valores escogidos para el multiplicador del radio kvar´ıan entre escenas. En las pruebas realizadas se ha encontrado que valores entre tres y seis ofrecen buenos resultados. El n´umero de muestras es proporcional al ´angulo s´olido de la VSL [HKWB09], utilizando un m´aximo de 100 muestras para Ωi= 2π. Esta situaci´on se da sin embargo de una forma extraordinaria y en la mayor´ıa de las ocasiones se utilizar´a un n´umero mucho menor. En la Figura 3.5 se compara el resultado obtenido entre la utilizaci´on de VPLs y VSLs. 3.2.3. Test de visibilidad A la hora de calcular la energ´ıa recibida sobre un punto, se debe determinar el t´ermino de visibilidad V(Ecuaci´on 2.3). En la implementaci´on realizada del algoritmo, esta operaci´on se basa en trazado de rayos en direcci´on a la VPL o cluster. Consideramos que existe una oclusi´on si la intersecci´on m´as cercana se da a una distancia menor que la existente entre el punto a iluminar y la VPL o cluster. En el caso de las VPLs, se trazan rayos desde el punto xhasta su posici´on. Sin embargo, orientar los rayos al centro un cluster ofrece malos resultados, obteniendo artefactos en forma de ruido estructurado (banding). Esto es debido a la correlaci´on en las muestras entre p´ıxels. Para solucionar este problema, la estrategia empleada es similar a la aproximaci´on descrita en la Secci´on 3.2.2. En lugar de trazar el rayo al centro del cluster, se muestrea estoc´asticamente la direcci´on del rayo en el ´angulo s´olido del cluster, de forma similar a muestrear una VSL. De esta forma, pese a que aumenta la varianza, reducimos la correlaci´on entre muestras, lo que elimina el banding produciendo mejores resultados [RAMN12]. En nuestra implementaci´on, utilizamos una ´unica muestra por cluster, ofreciendo buenos resultados. En la Figura 3.6 se comparan los resultados obtenidos aplicando este m´etodo de c´alculo de la visibilidad con el trazado de rayos al centro del cluster. 12 CAP´ ITULO 3. POINT-BASED GLOBAL ILLUMINATION Figura 3.5: Comparaci´on de los resultados para diferentes valores de ken una Cornell-Box difusa (izquierda), para k= 0,1,2,3. N´otese c´omo al aumentar el valor de klas singularidades presentes como ruido de alta frecuencia son suavizadas, mientras que la cantidad global de energ´ıa en la escena es preservada. Figura 3.6: Comparaci´on entre el muestreo de la visibilidad de los clusters de forma determinista al centro del cluster (izquierda), o estoc´asticamente en el ´angulo s´olido comprendido por el cluster (derecha), para el mismo n´umero de muestras. N´otese c´omo usando muestreo estoc´astico el banding es significativamente reducido, ofreciendo mucho mejores resultados con el mismo coste. En ambos casos s´olo la iluminaci´on indirecta es calculada. Cap´ıtulo 4 Clustering de muestras de la c´amara A pesar de que las t´ecnicas que aproximan la iluminaci´on global jerarquizando las luces virtuales en clusters trabajan de forma eficiente, escalan linealmente con la cantidad de puntos que deben ser iluminados, lo cual afecta a su rendimiento al renderizar im´agenes de alta resoluci´on, o multivista (e.g. est´ereo o light fields). La coherencia que presentan estos puntos puede ser aprovechada para aproximar la energ´ıa que reciben con complejidades sublineales. Aunque existen m´etodos capaces de agrupar tanto las luces virtuales como los puntos a iluminar, no trabajan con todo el posible conjunto de muestras que pueden ser generadas, perdiendo generalidad y la posibilidad de aproximar un mayor n´umero de muestras. En el presente cap´ıtulo, presentamos nuestra t´ecnica para el c´alculo de la iluminaci´on global basada en puntos que permite agrupar las muestras de todos los posibles puntos de vista en el espacio de la escena trabajando con todo su conjunto. Este m´etodo servir´a como punto de partida para explorar nuevos algoritmos para el c´alculo de la iluminaci´on global de forma escalable respecto del n´umero luces y muestras, que presentamos en el Cap´ıtulo 5. De forma similar al algoritmo desarrollado en el Cap´ıtulo 3, este m´etodo trabaja en dos etapas. En la fase de preproceso, se generan tanto las VPLs como los puntos visibles desde la c´amara; estas ´ultimas son introducidas en una estructura jer´arquica que se utiliza despu´es para aproximar la iluminaci´on indirecta en grupos de p´ıxels. En la etapa de renderizado, la iluminaci´on indirecta se calcula recorriendo el ´arbol de muestras creando un corte que aproxima la visibilidad y la radiancia recibida por las muestras. La Figura 4.1 muestra un ejemplo del funcionamiento del algoritmo. 4.1. Preproceso Datos de entrada El algoritmo desarrollado, necesita del conjunto de muestras generadas desde la c´amara, que son creadas trazando rayos que intersectan con la geometr´ıa de la escena. Todos los puntos a iluminar deben ser almacenados para poder crear una jerarqu´ıa que permita aproximar la energ´ıa que reciben desde las VPLs. Para cada punto generado se almacena su posici´on, su normal, la direcci´on del rayo a partir del que ha sido generada, la BRDF de la superficie en la que residen, su peso, siendo este ´ultimo la probabilidad con que se genera la muestra y el p´ıxel desde el que se ha trazado el rayo. El ´arbol de muestras El conjunto de muestras generado es introducido en una jerarqu´ıa. De forma an´aloga al trabajo desarrollado en el Cap´ıtulo 3, utilizamos un ´arbol de tipo octree, permitiendo crear una jerarqu´ıa de forma eficiente. Sin embargo, esta estructura particiona el espacio sin tener en cuenta la orientaci´on de las muestras. Por ello, en un trabajo futuro se evaluar´a la utilizaci´on de otro tipo de estructuras que permitan agrupar puntos con normales similares. 13 14 CAP´ ITULO 4. CLUSTERING DE MUESTRAS DE LA C ´ AMARA Figura 4.1: Izquierda: Escena para la que se generan 4 muestras desde la c´amara e iluminada por una VPL. La energ´ıa reflejada desde la VPL puede ser aproximada para algunas de las muestras generadas. Derecha: Representaci´on simplificada del ´arbol de muestras. La l´ınea verde representa las hojas y nodos utilizados para aproximar la iluminaci´on, formando un corte en el ´arbol. En este ejemplo, la iluminaci´on en los nodos agrupados en el cluster naranja es calculada s´olo para el cluster, y propagada a sus hijos al final del proceso. 4.2. C´alculo de la iluminaci´on Para calcular la iluminaci´on global, este m´etodo recorre el ´arbol de muestras para cada VPL comenzando por el nodo ra´ız, creando un corte hasta alcanzar la precisi´on necesaria (ver Secci´on 4.2.1). Si un nodo es una hoja del ´arbol (una muestra) la energ´ıa reflejada se calcula de acuerdo a la Ecuaci´on 2.5. En caso contrario, el cluster aproximar´a la visibilidad y la energ´ıa recibida para todas las muestras que contiene. El test de visibilidad se calcula trazando un rayo desde la VPL al centro del cluster. Sin embargo, en superficies no alineadas con los ejes se obtienen malos resultados. Para solucionar este problema, durante la inicializaci´on del ´arbol de muestras se refina la posici´on del centro de cada nodo mediando las posiciones de las muestras que contienen, mejorando notablemente la calidad del test como muestra la Figura 4.2. Para aproximar la radiancia recibida mediante los clusters y evitar su c´alculo en las hojas del ´arbol, hay que tener en cuenta algunos aspectos. Los nodos deben de almacenar la energ´ıa recibida por todas las luces virtuales. A su vez, la atenuaci´on geom´etrica y la BRDF deben ser calculados para las hojas, siendo estos valores dependientes de la direcci´on de incidencia y de su orientaci´on. Para llevar a cabo esta tarea, se evaluaron distintas alternativas; en base al trabajo de Walter et al. [WABG06], es posible aproximar la radiancia reflejada a partir de una muestra elegida de forma aleatoria dentro del conjunto de puntos contenidos por cada cluster. Tambi´en se valor´o aproximar estad´ısticamente la contribuci´on en todo el cluster, mediante el modelado de forma probabil´ıstica del conjunto de puntos discretos que forman el cluster [JHY+14, BN12]. No obstante, es dif´ıcil valorar c´omo se ver´ıa afectada la precisi´on de la radiancia incidente utilizando este m´etodo. Finalmente, se opta por utilizar una aproximaci´on basada en los trabajos de Sloan et al. [SKS02], y Ramamoorthi y Hanrahan [RH01], almacenando la radiancia incidente sobre los clusters en arm´onicos esf´ericos. Este tipo de bases nos permiten almacenar de una forma eficiente la energ´ıa recibida manteniendo la componente direccional de la misma, de modo que permite su uso sobre BRDFs arbitrarias. Adem´as, el uso de arm´onicos esf´ericos nos permite calcular la integral de la radiancia reflejada como el producto escalar entre la proyecci´on en arm´onicos esf´ericos de la BRDF y de la radiancia incidente. Mediante esta propiedad, tras atravesar el ´arbol sumamos la energ´ıa almacenada en los nodos hasta las hojas, y calculamos la radiancia reflejada como la integral entre esta suma y la atenuaci´on geom´etrica de cada muestra proyectada en arm´onicos esf´ericos. Para m´as detalles de esta operaci´on consultar [Gre03]. La limitaci´on de esta aproximaci´on es que s´olo resulta ´util con materiales de baja frecuencia 4.2. C ´ ALCULO DE LA ILUMINACI ´ ON 15 Figura 4.2: Comparaci´on de los resultados obtenidos mediante el refinamiento de los centros de los clusters en una Cornell-Box difusa sin la componente directa. Izquierda: Resultado obtenido sin refinar el centro de los clusters. Las superficies no alineadas con los ejes y las zonas con oclusiones presentan artefactos que degradan la calidad de la imagen. Derecha: Resultado obtenido refinando el centro de los clusters como la media de las posiciones de las muestras que contienen. La precisi´on del test de visibilidad aumenta, eliminando la mayor´ıa de los artefactos. (en nuestro caso Lambertianos). Por ello, se implementa una versi´on alternativa que utiliza los clusters de muestras para aproximar ´unicamente la visibilidad, de forma que cuando un nodo es lo suficientemente preciso y es visible, la radiancia reflejada es calculada en las hojas. A pesar de ser menos eficiente, teniendo en cuenta que el c´alculo de la visibilidad es la operaci´on m´as costosa durante el c´alculo de la iluminaci´on, este m´etodo mantiene ´ordenes de complejidad sublineales con respecto del n´umero de muestras. 4.2.1. Condiciones de parada De forma similar al algoritmo presentado en el Cap´ıtulo 3, para determinar la precisi´on de un cluster se utiliza el valor de su ´angulo s´olido con respecto de las VPLs. Para calcular este valor, es necesario conocer el ´area que proyecta cada nodo hacia la VPL que se est´e tratando. Dado que las muestras son puntos 0D y no disponen de ´area, no es posible aproximar este valor de la forma en que trabaja el algoritmo del Cap´ıtulo 3 mediante arm´onicos esf´ericos. Por ello, este valor se calcula a partir el ´area proyectada de la esfera que envuelve a cada cluster de acuerdo a la Ecuaci´on 3.3. Con el prop´osito de obtener m´as precisi´on en los clusters cercanos al punto de vista, el ´angulo s´olido es calculado tambi´en desde la posici´on de la c´amara, de manera que se obtenga un nivel adicional de control en la calidad final de la soluci´on generada. Sin embargo, en general la utilizaci´on del ´angulo s´olido desde las VPLs ofrece la precisi´on suficiente, dejando este par´ametro como una condici´on de parada adicional, pero no indispensable. Teniendo en cuenta que la jerarquizaci´on en un octree crea clusters subdividiendo el espacio, se ignora la orientaci´on que pueden tener las muestras contenidas. En ciertas zonas de la escena como esquinas o superficies curvas, el test de visibilidad no es lo suficientemente preciso, obteniendo resultados con poca calidad sino se utilizan umbrales del ´angulo s´olido extremadamente peque˜nos. Para poder obtener un nivel de precisi´on extra en estas situaciones, se impone una condici´on adicional que permite refinar m´as los clusters con mucha variaci´on geom´etrica. Estos casos son detectados mediante la utilizaci´on de una estructura en forma de cono que acota las normales contenidas. Estableciendo un valor m´aximo para el ´angulo de apertura de dicho cono, se evita la utilizaci´on de clusters que contengan muestras que violen esta restricci´on como mostramos en la Figura 4.3. 16 CAP´ ITULO 4. CLUSTERING DE MUESTRAS DE LA C ´ AMARA Una t´ecnica utilizada habitualmente es la utilizaci´on de mapas de normales para simular geometr´ıas complejas en las superficies mediante la variaci´on del c´alculo de la iluminaci´on. La utilizaci´on del cono de normales con estos materiales puede tener un gran impacto en el rendimiento. Por ello, esta condici´on se aplica sobre las normales de la geometr´ıa, dado que el c´alculo de la visibilidad depende ´unicamente de la geometr´ıa. Este m´etodo escala bien con el n´umero de p´ıxels (ver Cap´ıtulo 6). Sin embargo, tiene un coste lineal respecto del n´umero de VPLs. En la siguiente secci´on presentamos un algoritmo escalable que combina el clustering jer´arquico de luces virtuales (Cap´ıtulo 3) y de muestras de la c´amara. Figura 4.3: Efecto del test del cono de normales en la escena Cornell-Box. En verde se muestran las muestras que satisfacen esta restricci´on, y en rojo las que la violan, para ´angulos m´aximos de 1.5 radianes (Izquierda) y 0.1 radianes (Centro). (Derecha) Ejemplo de cono de normales para tres puntos contenidos en un cluster. El cono queda definido por su direcci´on ~ dy su ´angulo de apertura α. Cap´ıtulo 5 Clustering bidireccional Las t´ecnicas descritas hasta ahora, se limitan a agrupar luces virtuales o muestras generadas desde la c´amara de forma independiente. Aunque se consigue calcular la iluminaci´on global de una escena de una forma m´as eficiente, si se combinan ambas estrategias es posible obtener costes sublineales con respecto de la cantidad de VPLs y muestras. En este cap´ıtulo, se propone un nuevo algoritmo que combina el clustering jer´arquico de luces virtuales aproximando la iluminaci´on indirecta [WFA+05, Chr08] (Cap´ıtulo 3), y el de muestras desde la c´amara descrito en el Cap´ıtulo 4, de modo que el coste del algoritmo sea de orden (O(log(M + N))). Partiendo de los ´arboles de VPLs y muestras, el algoritmo trabaja con una jerarqu´ıa impl´ıcita que representa todas las posibles relaciones entre nodos de luces y nodos de puntos a iluminar como muestra la Figura 5.1. Cada nodo de esta jerarqu´ıa empareja elementos del ´arbol de VPLs y del ´arbol de muestras formando pares de nodos. Para aproximar la iluminaci´on global, comenzando a partir del par formado por los nodos ra´ız de ambos ´arboles, ´estos son refinados creando nuevos pares, hasta cumplir las condiciones de parada. El resultado es un corte en la jerarqu´ıa formado por el conjunto de pares utilizados para calcular la iluminaci´on global, aproximando tanto la radiancia reflejada por las superficies como la recibida por las muestras. 5.1. Preproceso Los datos de entrada del algoritmo son el conjunto de VPLs que modelan la iluminaci´on indirecta y las muestras generadas desde la c´amara. Crear una ´arbol a partir de todos los posibles pares de VPLs y muestras es un proceso costoso tanto en tiempo como en memoria. Por ello, se utiliza una jerarqu´ıa impl´ıcita sobre el espacio de los posibles pares, formada por el producto cartesiano de los ´arboles independientes de luces y muestras. El nodo ra´ız representa el espacio de todos los posibles pares de nodos, mientras que las hojas representan pares individuales de VPLs y muestras. Mediante la relaci´on de los dos ´arboles, es posible disponer de una jerarqu´ıa, sin la necesidad de construirla expl´ıcitamente como muestra la Figura 5.1. 5.2. C´alculo de la iluminaci´on Para calcular la iluminaci´on global, el algoritmo selecciona de forma adaptativa un conjunto de pares de nodos que permiten aproximar la iluminaci´on global. Este conjunto forma un corte en la jerarqu´ıa donde, para cada nodo hoja, el conjunto de caminos desde la ra´ız hasta dicha hoja contiene un ´unico nodo del corte. Para crear el corte, el algoritmo parte del par formado por las ra´ıces de los ´arboles de luces y muestras, y crea nuevos pares hasta alcanzar las condiciones de parada (Secci´on 5.2.2). A la hora de calcular la iluminaci´on global, se procede de forma an´aloga a 17 24 CAP´ ITULO 6. RESULTADOS 6.2. An´alisis de calidad y par´ametros A continuaci´on, presentamos el an´alisis de la calidad de imagen obtenida con los tres algoritmos desarrollados con el objetivo de determinar los par´ametros ´optimos para sus condiciones de parada. Para la realizaci´on de las pruebas, se utiliza la escena Cornell-Box sin la componente de iluminaci´on directa, con 100000 VPLs y una resoluci´on de 1024x1024 y 2 muestras por p´ıxel. 6.2.1. Algoritmo de clustering de VPLs En la Figura 6.5 mostramos los resultados obtenidos para el m´etodo PBGI con ´angulos s´olidos m´aximos ΩL= 0,1 sr y ΩL= 0,01 sr fijando un valor ΩS= 0,1 sr. Un umbral de ΩL= 0,1 sr ofrece resultados con m´as ruido debido a las oclusiones, el cual se hace m´as notable conforme aumenta la complejidad de la escena. Por el contrario, un valor ΩL= 0,01 sr permiten minimizar este efecto, manteniendo buenos niveles de escalabilidad con el n´umero de VPLs. 6.2.2. Algoritmo de clustering de muestras Para el algoritmo de clustering de muestras, utilizamos valores ΩM= 0,01 sr, ΩM= 0,001 sr y ΩM= 0,0001 sr para el ´angulo s´olido y valores α= 1,5 rad y α= 0,1 rad. La Figura 6.6 muestra los resultados obtenidos. N´otese la necesidad de utilizar umbrales menores con respecto al m´etodo PBGI para obtener buenos resultados. Valores de ΩM= 0,01 sr y ΩM= 0,001 sr presentan ruido estructurado, especialmente en zonas con oclusiones, mientras que con un valor m´aximo ΩM= 0,0001 sr este efecto es pr´acticamente inapreciable. Adicionalmente, el par´ametro αtiene consecuencias m´as notables con valores altos ΩM, sin embargo en escenas con geometr´ıa detallada, resulta de utilidad con el fin de obtener un mayor grado de precisi´on incluso con ´angulos s´olidos peque˜nos. 6.2.3. Algoritmo de clustering de VPLs y muestras Para la t´ecnica bidireccional, analizamos la calidad de los resultados estableciendo valores ΩL= 0,1sryΩL= 0,01 sr para los clusters de VPLs y valores para los clusters de muestras ΩM= 0,001 sr y ΩM= 0,0001 sr, mostrando en qu´e medida afecta cada uno a la calidad de imagen. Los resultados obtenidos se muestran en la Figura 6.7. Minimizando el par´ametro ΩMobtenemos mejores resultados que minimizando el valor de ΩL. Sin embargo dada la poca precisi´on del test de visibilidad entre clusters, necesitaremos ser restrictivos y utilizar valores de ΩL= 0,01 sr y ΩM= 0,0001 sr. Cabe destacar como, al contrario que la t´ecnica de clustering de muestras, el efecto del ´angulo m´aximo entre las normales de las muestras es mayor, aunque las superficies con normales muy dispares en general siguen presentando artefactos. 6.2.4. An´alisis de error Para analizar el error introducido por cada t´ecnica, calculamos el MSE en base a un ground truth calculado evaluando todas las muestras y VPLs. En la Figura 6.8 mostramos los resultados obtenidos. Para PBGI y el m´etodo bidireccional obtenemos un mayor error. Este es introducido por la aproximaci´on de la energ´ıa mediante arm´onicos esf´ericos. Sin embargo, estos m´etodos generan im´agenes con menos artefactos. Por el contrario, los algoritmos de clustering de muestras presentan un valor menor para el error, debido a la utilizaci´on de las VPLs de forma individual y el hecho de necesitar ´angulos s´olidos m´aximos m´as bajos para obtener resultados aceptables. 6.2. AN ´ ALISIS DE CALIDAD Y PAR ´ AMETROS 25 Figura 6.5: Comparaci´on de la calidad de imagen para el algoritmo de clustering de VPLs con ΩL= 0,1 sr y ΩL= 0,01 sr. Figura 6.6: Comparaci´on de la calidad de imagen para el algoritmo de clustering de muestras con valores ΩM= 0,01 sr, ΩM= 0,001 sr, ΩM= 0,0001 sr, y ´angulos m´aximos para el cono de normales α= 1,5 rad y α= 0,1 rad. 26 CAP´ ITULO 6. RESULTADOS Figura 6.7: Comparaci´on de la calidad de imagen para el algoritmo de clustering de VPLs y muestras variando los par´ametros ΩL, ΩMyα. Figura 6.8: MSE para el algoritmo de clustering de VPLs (Izquierda), clustering de muestras (Centro) y clustering de VPLs y muestras (Derecha). 6.3. RESULTADOS ADICIONALES 27 6.3. Resultados adicionales A continuaci´on se presentan resultados adicionales en escenas con una complejidad superior. Teniendo en cuenta la escalabilidad lineal con respecto del n´umero de VPLs del m´etodo de clustering de muestras, se utilizar´a PBGI y el m´etodo bidireccional. En el Anexo B se recogen las estad´ısticas del rendimiento obtenido para las distintas escenas calculadas. En los resultados obtenidos, a la izquierda presentamos la imagen completa renderizada con el m´etodo bidireccional, a excepci´on de la escena Bunny. A le derecha comparamos la calidad entre los dos m´etodos en algunas zonas de las escenas, siendo la columna izquierda el m´etodo de clustering de VPLs, y la columna derecha el m´etodo de clustering de VPLs y muestras. Figura 6.9: Escena light field. Figura 6.10: Escena Sponza. 28 CAP´ ITULO 6. RESULTADOS Figura 6.11: Escena Sibenik. Figura 6.12: Escena Bunny. (Izquierda): Resultado obtenido con PBGI. (Derecha): N´otese como el algoritmo bidirecccional no es capaz de calcular la iluminaci´on global sobre materiales de alta frecuencia (Conejo central). 6.3. RESULTADOS ADICIONALES 29 Figura 6.13: Escena San Miguel. 30 CAP´ ITULO 6. RESULTADOS Cap´ıtulo 7 Conclusiones En este proyecto, hemos desarrollado un nuevo algoritmo que permite el c´alculo eficiente de la iluminaci´on global (difusa) utilizando t´ecnicas de clustering en espacio de luces y de muestras de c´amara. Como punto de partida, hemos implementado PBGI [Chr08], un algoritmo de iluminaci´on global basado en clustering de VPLs utilizado en producci´on cinematogr´afica (Cap´ıtulo 3). Para ello, lo hemos adaptado a un sistema basado en trazado de rayos [PH10] y hemos resuelto los problemas comunes a las t´ecnicas basadas en luces virtuales como las singularidades y la presencia de ruido estructurado, para lo cual hemos adaptado las VSLs [HKWB09] a PBGI, adem´as de otros problemas derivados de la aproximaci´on introducida por la utilizaci´on de clusters. Posteriormente, hemos dise˜nado una t´ecnica de renderizado capaz de agrupar las muestras generadas desde uno o m´ultiples de vista, obteniendo costes sublineales con respecto de su n´umero. A diferencia de trabajos previos [WABG06, WHB+13], nuestra t´ecnica trabaja con el conjunto total de muestras en la escena, lo que nos permite aprovechar mejor la coherencia presente en las muestras desde la c´amara. Finalmente, hemos propuesto un nuevo m´etodo capaz de combinar el algoritmo de clustering de luces virtuales implementado, y el nuevo m´etodo de clustering de muestras de la c´amara, permitiendo obtener ´ordenes de complejidad sublineales ((O(log(M + N)))). Sus resultados han sido estudiados en varios escenarios, observando que en la mayor´ıa de casos es posible obtener calidades similares a PBGI en un tiempo menor. 7.1. Discusi´on y trabajo futuro Pese a que la t´ecnica presentada es capaz de calcular la iluminaci´on global de una forma eficiente, con ´ordenes de complejidad sublineales con respecto del n´umero de luces virtuales y de muestras, presenta algunas limitaciones que deber´an ser tratadas en trabajos futuros. En la implementaci´on llevada a cabo, ´unicamente calculamos la iluminaci´on global proveniente del primer rebote de la luz en las superficies. Para extenderlo a m´ultiples rebotes ser´ıa necesario repetir el proceso de iluminaci´on iterativamente. N´otese que nuestro m´etodo, al ser sublineal tanto en las luces como en los puntos de sombreado, permite que este proceso sea muy eficiente. Otra alternativa ser´ıa la generaci´on de las luces virtuales mediante trazado estoc´astico de part´ıculas [Kel97]; en este caso, la extensi´on ser´ıa trivial. Asimismo, la utilizaci´on de arm´onicos esf´ericos funciona bien para aproximar la iluminaci´on de baja frecuencia, sin embargo necesitamos mayor precisi´on para poder tratar con materiales de mayor frecuencia. La soluci´on trivial para manejar estos materiales es resolver la integral estoc´asticamente, muestreando la BRDF e introduciendo las muestras generadas dentro de la jerarqu´ıa de muestras desde la c´amara. Otra opci´on ser´ıa aumentar el n´umero de bandas de arm´onicos esf´ericos a almacenar, basado 31 32 CAP´ ITULO 7. CONCLUSIONES en la frecuencia de la funci´on de reflectancia [DHS+05, LALD12]; sin embargo, para escenas con muchas superficies especulares esta aproximaci´on ser´ıa muy ineficiente en memoria, y adem´as podr´ıa dar problemas de ringing [SHHS03]. Adicionalmente, el uso de t´ecnicas basadas en VPLs es muy prometedor para renderizar jer´arquicamente materiales transl´ucidos [JMLH01]; explorar c´omo incorporar este tipo de materiales a nuestro algoritmo bidireccional es un interesante trabajo futuro a explorar [AWB08]. Atendiendo a los resultados, en la mayor´ıa de las im´agenes renderizadas, conseguimos reducir el tiempo de renderizado. Sin embargo, en algunas escenas (Bunny), el algoritmo de clustering de VPLs resulta m´as eficaz que el m´etodo bidireccional. Esto es debido a las diferencias de normales dentro de los clusters de muestras, que hacen que el algoritmo tenga que refinar significativamente el ´arbol, de modo que los costes fijos de la t´ecnica se vuelven dominantes. Por ello, evaluaremos el uso de otro tipo jerarqu´ıas que agrupen las muestras teniendo en cuenta su orientaci´on con el prop´osito de generar cluster de mayor calidad. La utilizaci´on t´ecnicas de prefiltrado que nos permitan aproximar el contenido de un cluster de muestras mediante una distribuci´on estad´ıstica, puede resultar interesante para calcular la iluminaci´on en un cluster con un menor grado de error [BN12]. Finalmente, el algoritmo est´a limitado por la memoria consumida, debido a que almacenamos los ´arboles de VPLs y muestras desde la c´amara. Para solucionar este problema en escenas de gran complejidad, limitadas por la memoria del sistema, se pueden adaptar t´ecnicas de compresi´on [BB12] y de almacenamiento out-of-core [KTO11] existentes para VPLs al ´arbol de muestras de c´amara. N´otese que los resultados mostrados en la Secci´on 6.3 han sido renderizados con versiones multihilo, donde el algoritmo de clustering de VPLs es capaz de repartir mejor la carga de trabajo entre los procesadores, por lo que la mejora en el scheduling del m´etodo bidireccional es un aspecto importante a mejorar. Las heur´ısticas de error de los algoritmos presentados est´an basadas en el ´angulo s´olido entre puntos y clusters. Aunque efectivas, est´as t´ecnicas son demasiado conservativas, y no son intuitivas a la hora de ser definidas por el usuario. El desarrollo de nuevas heur´ısticas que utilicen informaci´on basada en la frecuencia de las superficies a iluminar [FPG01, DBD+07], de las BRDFs en la escena [LALD12], o haciendo uso de las limitaciones del sistema visual humano [RFWB07, Hˇ CA+12], es una l´ınea de trabajo futuro muy interesante. 7.2. Conclusi´on personal A nivel personal, la realizaci´on de este proyecto ha supuesto un reto que me ha permitido iniciarme en el campo de los gr´aficos por ordenador, y profundizar en las bases f´ısicas en las que se fundamentan. Trabajar junto a la gente del Graphics and Imaging Lab me ha permitido conocer de primera mano la forma de trabajo en investigaci´on, d´andome la oportunidad de colaborar con el art´ıculo A Framework for Transient Rendering, aceptado en la conferencia internacional SIGGRAPH Asia 2014, desarrollado en colaboraci´on con Jaroz Wojciech investigador jefe del grupo de gr´aficos en Disney Research, Z¨urich. La relaci´on con Adri´an y Diego ha sido realmente buena adem´as de con el resto de compa˜neros del laboratorio, siendo grandes profesionales y mejores personas, dispuestas a ayudar en todo momento. 7.3. Diagrama temporal del proyecto A continuaci´on presentamos la evoluci´on temporal del proyecto, iniciado en octubre de 2013, hasta su finalizaci´on en septiembre de 2014. 7.3. DIAGRAMA TEMPORAL DEL PROYECTO 33 Definiciónédeléproyecto Documentaciónéeéinvestigación AprendizajeédeléframeworkéPBRT ImplementaciónédeéPBGI ImplementaciónédeéextensionesédeéPBGI Investigaciónédeétécnicasébidireccionales ImplemetaciónédelémétodoéCM1 Implementaciónédelémétodoébidireccional Redacciónédeélaémemoria Febrero Marzo Abril Mayo Junio Julio Agosto Septiembre 2 Octubre Noviembre Diciembre Enero 1Algoritmoédeéclusteringédeémuestras Figura 7.1: Distribuci´on temporal de las tareas realizadas en este proyecto. 40 AP ´ ENDICE A. M ´ ETODOS AUXILIARES Ap´endice B Resultados adicionales B.1. Tablas de rendimiento Algoritmo ΩL10k 100k 200k 300k 400k 500k PBGI 0.1 71 50 56 51 53 53 PBGI 0.01 225 134 155 119 122 127 PBGI 0.001 365 1407 1851 1079 1153 1308 Lineal 662 4986 9480 13841 18227 22468 Tabla B.1: Coste en segundos del algoritmo descrito en el Cap´ıtulo 3 en comparaci´on a calcular linealmente las luces virtuales. Para las pruebas realizadas se utiliza una resoluci´on de 256x256x1 y ΩS= 0,1. Algoritmo ΩMα256x256x1 256x256x2 512x512x1 512x512x2 1024x1024x1 1024x1024x2 CM SH 0.01 1.5 90 112 156 204 305 419 CM SH 0.01 0.1 106 141 198 268 389 524 CM SH 0.001 1.5 347 459 572 673 831 1007 CM SH 0.001 0.1 365 495 614 745 910 1095 CM SH 0.0001 1.5 437 829 1636 2508 3955 5086 CM SH 0.0001 0.1 451 852 1681 2565 4037 5140 CM V 0.01 1.5 139 207 382 603 1225 2030 CM V 0.01 0.1 154 232 415 662 1303 2175 CM V 0.001 1.5 453 617 854 1129 1979 2897 CM V 0.001 0.1 429 598 859 1162 1961 2910 CM V 0.0001 1.5 429 964 1828 2753 4749 6377 CM V 0.0001 0.1 498 905 1793 2732 4705 6336 Lineal 673 1133 2075 4634 7825 16184 Tabla B.2: Tabla de tiempos en segundos para el algoritmo de clustering de muestras. Las pruebas realizadas utilizan 10000 VPLs, ΩC= 0,1. CM atiende a Clustering de Muestras, SH a la implemtaci´on basada en arm´onicos esf´ericos y V a la versi´on que aproxima ´unicamente la visibilidad. 41 42 AP ´ ENDICE B. RESULTADOS ADICIONALES Algoritmo ΩLΩM256x256x1 512x512x1 1024x1024x1 PBGI 0.01 138 544 2189 BD 0.01 0.001 205 377 1154 BD 0.01 0.0001 235 460 1829 Tabla B.3: Tabla tiempos en segundos para m´etodo bidireccional con respecto de PBGI. En los test realizados se han utilizado 100 mil VPLs, α= 0,1 , ΩS= 0,1 y ΩC= 0,1 Algoritmo ΩLΩM50k 100k 150k CM 0.001 2745 5112 8086 BD 0.01 0.001 536 377 445 BD 0.01 0.0001 640 460 522 Tabla B.4: Tabla comparativa del rendimiento del m´etodo bidireccional con el algoritmo de clustering de muestras. En los test realizados se ha fijado una resoluci´on de 512x512x1, α= 0,1, ΩS= 0,1 y ΩC= 0,1. Escena Resoluci´on N VPLs PBGI Bidireccional light field 4096x4096x2 100000 12936 5056 Sponza 2048x2048x2 5000000 15134 7690 Sibenik 1024x1024x2 1000000 4905 3769 Bunny 2048x2048x2 5000000 3515 5858 San Miguel 1024x1024x2 8000000 10678 8299 Tabla B.5: Tabla de tiempos para las escenas adicionales presentadas en la Secci´on 6.3