PDF de programación - YAReW: Sistema Asistente al Proceso de Render basado en Tecnicas de Data Mining

UNIVERSIDAD DE CASTILLA-LA MANCHA
ESCUELA SUPERIOR DE INFORM ÁTICA

INGENIERÍA

EN INFORM ÁTICA

PROYECTO FIN DE CARRERA

YAReW: Sistema Asistente al Proceso de
Render basado en Técnicas de Data Mining

Lorenzo Manuel López López

Diciembre, 2007

UNIVERSIDAD DE CASTILLA-LA MANCHA
ESCUELA SUPERIOR DE INFORM ÁTICA

Departamento de Informática

PROYECTO FIN DE CARRERA

Autor:
Director: Carlos González Morcillo

Lorenzo Manuel López López

Diciembre, 2007.

c Lorenzo Manuel López López. Se permite la copia, distribución y/o modificación de este docu-
mento bajo los términos de la licencia de documentación libre GNU, versión 1.1 o cualquier versión
posterior publicada por la Free Software Foundation, sin secciones invariantes. Puede consultar esta
licencia en http://www.gnu.org.
Este documento fue compuesto con LATEX. Imágenes generadas con OpenOffice y GIMP.

TRIBUNAL:

Presidente:
Vocal:
Secretario:

FECHA DE DEFENSA:

CALIFICACI ÓN:

PRESIDENTE

VOCAL

SECRETARIO

Fdo.:

Fdo.:

Fdo.:

Resumen

Elegir una buena configuración de los parámetros de entrada de cualquier motor de render
basado en iluminación global no es una tarea fácil. La calidad de los resultados producidos
y el tiempo de cómputo requerido por el proceso son dos medidas que dependen fuertemen-
te de la configuración de valores escogida. Además, cada implementación define sus propios
parámetros con unos valores de entrada y un significado concreto. Esto supone que la búsque-
da de una buena configuración de render se lleva a cabo normalmente a través de un proceso
de prueba y error muy costoso en tiempo para el usuario.

El sistema propuesto con este proyecto es un asistente orientado a proporcionar soporte a
la decisión al usuario en términos de configuraciones de render que maximizan la calidad de
los resultados producidos tratando de minimizar el tiempo de cómputo requerido.

Abstract

Choosing a good configuration of the input parameters for a any global illumination based
render engine is not an easy task. The quality of the synthesised image, as well as the CPU
time spent in the process, depends to a great extent on the values of the input variables of the
render engine which is to be used. Besides, those variables and their values are completely
dependent on each implementation, which means that usually a trial-error process is the only
way to learn how to find the best configuration of input parameters for each situation.

The system which has been developed along with this project is a data mining based
rendering wizard which aims to give to the user decision support consisting on rendering
settings which try to maximise the quality of the synthesised image and minimise the CPU
time required by the process.

A papá y a mamá.
Por vuestro amor, entrega e ilusión.

Agradecimientos

Muchas han sido las personas que han contribuido a lo largo de toda mi vida a alcanzar
tan importante hito, sin embargo el espacio disponible aquí es limitado, por lo que espero que
las no incluidas sepan entenderlo.

A Carlos González, por la inspiración, los ánimos, las ideas, por su gran ayuda en el desa-
rrollo de este proyecto, por la confianza que ha depositado en mi desde el primer momento
y sobre todo, por ser un gran amigo a la vez que un gran director. Al grupo de investigación
Oreto, por permitirme utilizar sus instalaciones durante la parte más intensiva del desarro-
llo de este proyecto y rodearme de tan genial ambiente de trabajo. A Javier Albusac, por su
ayuda en la revisión de este documento. A José Ángel (Blankito) Mateos, por haber sido mi
gran compañero y hermano desde el principio hasta el final de esta aventura. ¡Qué bien nos
lo hemos pasado!. A Maribel, por todo el apoyo y el amor. Te has convertido en un pilar
muy importante en mi vida. A Papá, porque con tu esfuerzo esto se ha hecho posible. A mis
hermanos, por todo lo que nos queremos. Y a Maribelita, por la comprensión y todo el amor
que me das, a pesar de todo el tiempo que esto te ha robado.

A Mamá, por todas las fuerzas que me das cada día. Siempre estarás conmigo.

Índice general

Índice de figuras
Índice de cuadros
Índice de algoritmos

1. Introducción

1.1. Motivación .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
1.2. Terminología .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3. Estructura del documento . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.
.

.
.

.
.

.
.

2. Objetivos e Hipótesis de Trabajo

3. Antecedentes, Estado de la Cuestión

.

Introducción .

3.1. Minería de Datos y Aprendizaje Máquina . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.2. Definiciones
Árboles de decisión . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.3.
3.1.4. Aprendizaje basado en instancias
. . . . . . . . . . . . . . . . . . .
3.1.5. Aprendizaje bayesiano . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.6. Algoritmos Genéticos
. . . . . . . . . . . . . . . . . . . . . . . . .
3.1.7. Otros métodos
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.8. Evaluación de algoritmos de aprendizaje . . . . . . . . . . . . . . . .
3.2. Síntesis de Imagen Realista . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1.
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.2. La Ecuación de Render . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.3. Métodos de Render . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.4. Consideraciones Finales . . . . . . . . . . . . . . . . . . . . . . . .

Introducción .

.

4. Metodología de Trabajo
.

Introducción .

.

.

.

4.1.
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2. Generación de la base de conocimiento . . . . . . . . . . . . . . . . . . . . .
4.2.1. Definición de atributos . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.2. Bootstrapping .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.3. Render de instancias . . . . . . . . . . . . . . . . . . . . . . . . . .

.

.

IX

XI

XII

1
1
7
8

9

13
13
13
15
17
24
27
29
31
34
38
38
42
42
61

64
64
68
71
75
76

VII

ÍNDICE GENERAL

VIII

4.2.4. Evaluación de la calidad de los resultados . . . . . . . . . . . . . . .
77
4.2.5. Extracción y codificación de información . . . . . . . . . . . . . . .
85
4.2.6. Evaluación del modelo . . . . . . . . . . . . . . . . . . . . . . . . .
88
89
4.3. Desarrollo de YAReW . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
89
4.3.1. Arquitectura del sistema . . . . . . . . . . . . . . . . . . . . . . . .
4.3.2. Etapa de análisis y preproceso de la escena de usuario . . . . . . . .
90
4.3.3. Etapa de estimación y optimización . . . . . . . . . . . . . . . . . . 103
4.3.4. Etapa de Presentación de Resultados . . . . . . . . . . . . . . . . . . 110

5. Resultados

Introducción .

113
5.1.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.2. Sugerencia de configuraciones de render . . . . . . . . . . . . . . . . . . . . 115
5.3. Estimación de tiempo de render y calidad de resultados . . . . . . . . . . . . 118

.

.

.

.

.

.

6. Conclusiones y Propuestas
.

6.1. Conclusiones
6.2. Líneas de investigación abiertas

121
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
. . . . . . . . . . . . . . . . . . . . . . . . 124
6.2.1. Propuestas para optimizar la generación de conocimiento . . . . . . . 124
6.2.2. Propuestas de optimización del sistema asistente . . . . . . . . . . . 126

. .

.

.

.

Apéndices

132

A. Código Fuente

.

.

132
A.1. Bootstrapping .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
A.2. Proyección de histograma . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
A.3. Trazador de rayos de iluminación directa . . . . . . . . . . . . . . . . . . . . 138
A.4. Importador de impactos de iluminación directa
. . . . . . . . . . . . . . . . 142
A.5. Optimizador genético de configuraciones render . . . . . . . . . . . . . . . . 146

.

.

B. Escenas Incluidas en la Base de Conocimiento

C. Imágenes a Color

Bibliografía

151

155

161

Índice de figuras

1.1. Algunos resultados del experimento de configuración de render realizado . .
1.2. Resultados del experimento realizado en Magarro . . . . . . . . . . . . . . .
Árbol para el problema de clasificación de iris . . . . . . . . . . . . . . . . .
3.1.
3.2. Entropía en el caso de una clasificación binaria
. . . . . . . . . . . . . . . .
3.3. Proceso de cruce y mutación en algoritmos genéticos . . . . . . . . . . . . .
Iluminación local e iluminación global . . . . . . . . . . . . . . . . . . . . .
3.4.
3.5. Método de RayCasting .
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6. Tipos de rayos que intervienen en RayTracing . . . . . . . . . . . . . . . . .
3.7. Técnicas de aceleración de cálculos en RayTracing . . . . . . . . . . . . . .
3.8. Algunas estructuras de división espacial
. . . . . . . . . . . . . . . . . . . .
3.9. RayTracing y Ambient Occlusion . . . . . . . . . . . . . . . . . . . . . . .
3.10. Ejemplo de radiosidad .
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.11. Esquema de la matriz de radiosidad . . . . . . . . . . . . . . . . . . . . . .
3.12. Esquema de PathTracing Bidireccional . . . . . . . . . . . . . . . . . . . . .
3.13. Comparación entre PathTracing Bidireccional y MLT . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
3.14. Algoritmo de mapeado de fotones
3.15. Utilización del mapa de fotones
. . . . . . . . . . . . . . . . . . . . . . . .
3.16. Comparativa de resultados con diferentes métodos de render
. . . . . . . . .

4.1. Efecto en los resultados de diferentes configuraciones de escena . . . . . . .
4.2. Estructura de la base de conocimiento manejada por YAReW . . . . . . . . .
4.3. Escena de interior generada automáticamente . . . . . . .