Embed Size (px)
Citation preview
INSTITUTO TECNOLÓGICO Y DE ESTUDIOS SUPERIORES DE MONTERREY CAMPUS ESTADO DE MÉXICO
DIVISIÓN DE GRADUADOS E INVESTIGACIÓN DIRECCIÓN DE MAESTRÍAS EN INGENIERÍA
ALGORITMOS GENÉTICOS EN EL DISEÑO DE ILUMINACIÓN
TESIS QUE PARA OPTAR EL GRADO DE MAESTRO EN CIENCIAS COMPUTACIONALES
PRESENTA
JOAQUÍN ELORZA TENA
Asesor: Dr. ISAAC J. RUDOMÍN GOLDBERG
Comité de tesis: Dr. JESÚS A. SÁNCHEZ VELÁZQUEZ Dr. CARLOS RODRÍGUEZ LUCA TERO
Jurado: Dr. JESÚS A. SÁNCHEZ VELÁZQUEZ Dr. CARLOS RODRÍGUEZ LUCA TERO Dr. ISAAC J. RUDOMÍN GOLDBERG
Presidente Secretario Vocal
Atizapán de Zaragoza, México, Noviembre de 1996
2
PREFACIO.
En la actualidad, la producción de imágenes realistas, a través de gráficas computacionales,
conlleva un gran esfuerzo humano para crear escenas y ambientes que representen de manera
fiel la realidad. Estas imágenes suelen tener una variedad de aplicaciones, desde la creación
de un juego para el simple entretenimiento hasta la creación de ambientes virtuales que
incluso permitan la creación física del ambiente.
El uso de gráficas computacionales ha permitido crear edificios desde antes de que sean
construidos, así como simular ambientes dentro de ellos para lograr efectos deseados de
acuerdo al uso que se les vaya a dar.
El esfuerzo de esta tesis es la búsqueda de métodos de graficación que de una manera sencilla
permitan diseñar la iluminación en edificios, definiendo el resultado deseado pintando una
escena, más que buscarlo a prueba y error. Este esfuerzo intenta sumarse al que otras personas
han emprendido para ofrecer soluciones gráficas, útiles para el diseño de la iluminación en
ambientes cerrados. Además, ofrece el uso de un enfoque de estrategias evolutivas, como lo
son los algoritmos genéticos, para la búsqueda de efectos deseados por los diseñadores de
iluminación.
CONTENIDO.
PREFACIO.
1 INTRODUCCIÓN.
1.1 PROBLEMA DE ILUMINACIÓN.
1.1.1 Ray Tracing.
1.1.2 Radiosidad. .
1.2 PROBLEMA INVERSO ..
1.2.1 Soluciones Pintando con Luz y Radioptimización.
1.2.2 Propuesta de esta tesis ..
1.2.3 Trabajo desarrollado. . .
1.3 ESTRUCTURA DE ESTA TESIS.
2 RADIOSIDAD Y SÍNTESIS DE IMÁGENES.
2.1 SÍNTESIS DE IMÁGENES.
2.2 ILUMINACIÓN GLOBAL.
2.2.1 Ray Tracing.
3
2
9
9
10
10
10
11
11
11
12
13
13
14
15
2.2.2 Radiosidad. . . . . . . . . 16
2.3 ECUACION DE RENDERING. . 16
2.4 SOLUCIONES MEDIANTE ELEMENTOS FINITOS Y MONTE CARLO. . 18
2.4.1 Factor de Forma. . . . . . . . . . . . .
2.4.2 Solución a la ecuación de Radiosidad ..
2.4.3 Algoritmo de Refinamiento Progresivo.
2.4.4 Algoritmo de Jerarquía Multinivel.
3 MÉTODOS DE OPTIMIZACIÓN.
3.1 MÉTODO DEL GRADIENTE DESCENDENTE.
3.2 RECOCIDO SIMULADO ....
3.3 ALGORITMOS GENÉTICOS.
3.3.1 ¿ Qué son ? ....... .
21
23
24
25
29
29
31
33
33
3.3.2 Elementos en un Algoritmo Genético ..
3.3.3 Esquemas. . . . . . . . . . . . . . . . .
4 SOLUCIÓN AL PROBLEMA INVERSO DE ILUMINACIÓN.
4.1 PROBLEMA INVERSO ..
4.2 PINTANDO CON LUZ.
4.3 RADIOPTIMIZACIÓN: OBJETIVO BASADO EN SÍNTESIS
IMÁGENES ...... .
DE
4
33
37
39
39
40
40
4.4 ALGORITMOS GENÉTICOS EN EL DISEÑO DE ILUMINACIÓN. 42
4.4.1 Radiosidad Jerárquica. . . . .
4.4.2 Representación del Problema.
4.4.3 Operadores Genéticos.
4.4.4 Función Objetivo. . . .
5 IMPLANTACIÓN DE LA SOLUCIÓN.
5.1 SISTEMA DE VISUALIZACIÓN EN 3D.
5.1.1 Pintando una escena ....... .
5.1.2 Visualización sólida o alambrada.
5.1.3 Suavización de la escena ...
5.1.4 Cálculo de aproximaciones ..
5.2 SOLUCIÓN AL PROBLEMA INVERSO DE ILUMINACIÓN ..
5.2.1 Alcances de la solución.
5.2.2 Radiosidad Jerárquica.
5.2.3 Algoritmo Genético.
5.2.4 Gradiente Descendente ..
5.3 GRAFICACIÓN DEL ERROR Y SNR DE APROXIMACIONES.
6 RESULTADOS EXPERIMENTALES.
6.1 ESCENAS PROPUESTAS. . .....
6.2 EXPERIMENTOS CON LOS MÉTODOS DE OPTIMIZACIÓN.
6.2.1 Gradiente Descendente .................... .
42
43
44
45
47
48
49
50
50
51
51
52
52
55
58
59
61
61
63
63
6.2.2 Algoritmo Genético.
6.2.3 Comparación de Métodos.
6.3 ANÁLISIS POR PRUEBA.
6.3.1 Escena "Cuarto" ..
6.3.2 Escena "armario".
6.3.3 Minimizando costos no uniformes: "Cuarto" ..
6.3.4 Pintando Escenas: "Mesa". . . . . . . .
7 CONCLUSIONES Y TRABAJO FUTURO.
7.1 CONCLUSIONES. . .
7.2 TRABAJO FUTURO.
ANEXOS
A DOCUMENTACIÓN DE ARCHIVOS DE ENTRADA.
5
64
69
70
71
71
75
77
80
80
81
83
83
B DOCUMENTACIÓN DE ARCHIVOS DE SALIDA DE LA SOLUCIÓN. 93
C DOCUMENTACIÓN DE SISTEMA DE VISUALIZACIÓN. 95
BIBLIOGRAFÍA 98
6
LISTA DE TABLAS.
1 Tabla de aptitudes porcentualizada. 34
2 Tiempo de evaluación de escenas. 62
3 Tiempo y error de AG con diferentes poblaciones. 69
4 Tiempo y error de gradiente y algoritmo genético. 70
5 Nivel de luz y costo no uniforme asociado. 75
7
LISTA DE FIGURAS.
1 Componentes de la reflexión. . 14
2 Ray Tracing. . . . . . . . . . . 15
3 Geometría del Factor de Forma. 22
4 Hemicubo. . . . . . . . . . . . . 23
5 Contribución de energía a cada parche. 26
6 Quadtrees jerárquicos e interacciones. 27
7 Mínimo local y global. 31
8 Aptitud proporcional. . 35
9 Cruzamiento de individuos. 36
10 Genotipo. 44
11 Cruzamiento de individuos con diferente longitud 45
12 Estructura del programa. . . . 56
13 Archivos de entrada y salida. . 57
14 Mejores individuos y Promedio para población de 150 y 60 generaciones. 59
15 Error obtenido por Gradiente Descendente en 20 pruebas. . 64
16 Evaluación de SNR en Gradiente Descendente. . . . . . . . 65
17 Error obtenido para un AG en 60 evaluaciones con una población = 10. 66
18 Error obtenido para un AG en 60 evaluaciones con una población = 30. 67
19 Error obtenido para un AG en 60 evaluaciones con una población = 60. 67
20 Evaluación de SNR para el AG en 60 evaluaciones con población = 30. 68
21 Evaluación de SNR para el AG en 20 evaluaciones con población = 60. 68
22
23
Evaluación del Error para gradiente.
Evaluación del Error para AG. . . . .
24 Evaluación del Error para gradiente.
25 Evaluación del Error para AG .....
26 Factores de costos no uniformes para niveles de luz discretos.
27
28
Evaluación del Error para gradiente en costos no uniformes.
Evaluación del Error para AG con costos no uniformes. . . .
72
72
74
74
76
76
77
29
30
Evaluación del Error para gradiente en Mesa.
Evaluación del Error para AG en Mesa .....
8
78
79
9
1 INTRODUCCIÓN.
Se presenta una nueva aproximación para el diseño de iluminación por síntesis de imagen
en ambientes cerrados, basándose en la solución de un problema inverso de iluminación que
a continuación explicaremos, así como las soluciones propuestas por algunos autores y la
propuesta por esta tesis.
1.1 PROBLEMA DE ILUMINACIÓN.
La meta de la investigación en síntesis de imágenes en las gráficas computacionales es el
desarrollo de métodos que permitan modelar y generar vistas de escenas tridimensionales.
Una de las tareas más difíciles en este campo es la simulación físicamente correcta y eficiente
de los efectos de iluminación global, es decir, de la iluminación de los objetos de una escena
por otros objetos.
10
1.1.1 Ray Tracing.
Uno de los primeros métodos para la evaluación de la iluminación fue desarrollado por
primera vez hace poco más de 15 años, aplicando una técnica recursiva conocida como "Ray
Tracing" [6, 27].
El método de ray tracing evalúa un modelo de iluminación global en el que se definen
características tales como reflexión, refracción y sombreado de los objetos en la escena. Ray
tracing define un punto fijo, normalmente la posición del observador, del cual parten rayos
hacia las superficies de los objetos; estos rayos a su vez pueden alcanzar de manera indirecta
a otros objetos debido a las propiedades de reflexión de las superficies.
1.1.2 Radiosidad.
Un método más reciente fue desarrollado basado en los principios físicos de la transferencia de
energía radiante entre superficies, por lo que se les conoce como métodos de "Radiosidad" [4,
24].
Radiosidad es un método que se basa en el principio de la conservación de la energía y, a
diferencia de ray tracing, se caracteriza por ser independiente de la posición del observador.
1.2 PROBLEMA INVERSO.
Para un diseñador de iluminación de edificios, no es suficiente la simulación físicamente
correcta del proceso de iluminación si no tiene una forma práctica de especificar los resultados
que desea obtener. El proceso que normalmente sigue es el de prueba y error, es decir, el
diseñador especifica la posición e intensidad de las fuentes de iluminación en una escena, y
observa si cumple con sus expectativas; si no, cambia la posición de las fuentes luminosas,
modifica las intensidades e incluso el tipo de luz para ver nuevamente el resultado; el proceso
se repite así hasta que se logra el efecto deseado por el diseñador.
11
1.2.1 Soluciones Pintando con Luz y Radioptimización.
El problema inverso de iluminación ha sido resuelto por Schoeneman et al [23] proponiendo
una solución más natural, en la que se le permite al diseñador especificar en una escena,
usando un pincel de luz, las áreas que desee ver iluminadas y con qué intensidad. Una
vez definido lo anterior, es labor del sistema encontrar la mejor configuración de fuentes
luminosas que logren ese efecto.
Otra propuesta es la que hace Kawai et al [12] usando técnicas de optimización aplicadas
a síntesis de imagen basados en radiosidad. Kawai define para una escena un modelo de
percepción basado en impresiones subjetivas, tales como agradable, privado, espacioso y
claridad visual. Estas percepciones son incluídas en el problema a manera de restricciones
para una función objetivo, la cual se minimiza para encontrar los valores que logren el efecto
especificado.
1.2.2 Propuesta de esta tesis.
En esta tesis se propone el uso de algoritmos genéticos [8], con una evaluación de funciones
de iluminación a través de radiosidad jerárquica [10] para resolver el problema inverso de
iluminación.
Se usan algoritmos genéticos dado que resultan ser excelentes métodos de búsqueda, pues
exploran en varias áreas a la vez, minimizando la posibilidad de "caer" en un mínimo local.
En la solución del problema inverso de iluminación se citarán algunos casos en los que un
algoritmo genético encuentra soluciones en mínimos globales, a diferencia de otros métodos
como el caso de gradiente descendente.
1.2.3 Trabajo desarrollado.
Aquí se ofrece una interfaz gráfica en la que el usuario puede visualizar una escena es
pecificada en un archivo. La interfaz gráfica permite "pintar" las áreas que desee ver ilumi
nadas. Esta escena puede ser guardada posteriormente en un archivo para buscar la mejor
12
configuración de niveles de luz en luces fijas, luces en posiciones variables, tipos de luces y
su costo asociado.
El trabajo se desarrolló en equipos IBM RS6000 modelo 41 Ta 66 MHz PowerPC, 32 MBytes
en RAM y con sistema operativo AIX 3.2.5. El software utilizado fue C como lenguaje de
programación y librerías gráficas de OpenGL1 [17] y GLUT2 [13].
1.3 ESTRUCTURA DE ESTA TESIS.
Esta tesis contiene siete capítulos. En el primero de ellos se presenta la introducción. En el
segundo se definen los hechos más relevantes al tema de Radiosidad y Síntesis de Imágenes.
El tercer capítulo describe un panorama general de Métodos de Optimización, incluyendo
Algoritmos Genéticos. En el cuarto se menciona el problema inverso de iluminación, las
soluciones que han sido propuestas y la solución que presenta este trabajo. A través del quinto
capítulo se describe el desarrollo del trabajo de esta investigación. En el sexto, se ofrecen los
resultados obtenidos en varios casos para escenas propuestas. Y el séptimo capítulo contiene
las conclusiones obtenidas en este trabajo de investigación, así como el trabajo futuro.
Finalmente, existe un área de anexos, en la que se describen los archivos de entrada y salida
para las escenas; y también se ofrece un texto que explica las opciones principales del sistema
de visualización en 3D.
1 OpenGL es un conjunto de utilerias gráficas que auxilian en el desarrollo de aplicaciones gráficas.
2 GLUT es un conjunto de herramientas que permiten generar ventanas, menus de cascada y operar dispositivos como el ratón en base a eventos.
13
2 RADIOSIDAD Y SÍNTESIS DE IMÁGENES.
En este capítulo se introducen los conceptos básicos de radiosidad y síntesis de imágenes:
qué es y cómo se define físicamente para quedar formulado matemáticamente en una
ecuación, así como algunos de los métodos que su solución conlleva.
2.1 SÍNTESIS DE IMÁGENES.
En la actualidad, los diseñadores de iluminación requieren simular correctamente la ilumi
nación y la percepción visual de la imagen, así como considerar las propiedades físicas de
los objetos y el medio ambiente asociado. Esta simulación de imágenes realistas es mejor
conocida como "Síntesis de Imágenes" [4].
La creación de imágenes a través de paquetes basados en síntesis de imágenes es un trabajo
arduo que no se sabe con exactitud cuánto tiempo tome, dado que normalmente siguen un
proceso de prueba y error. En este proceso el diseñador debe probar diferentes configuraciones
de luces, intensidades, posiciones y tipos de luz para obtener una escena que refleje una
imagen lo más parecida a la realidad.
14
~
+ \ + BRDF Difusa Espejo Especular
Fig. 1: Componentes de la reflexión.
2.2 ILUMINACIÓN GLOBAL.
Cuando se crean imágenes realistas en el campo de las Gráficas Computacionales es nece
sario definir un adecuado modelo de iluminación en el que los objetos de una escena sean
iluminados de manera directa por las fuentes luminosas y de manera indirecta por otros
objetos. Así, la iluminación global es la consideración del efecto completo de la iluminación
en una escena.
La iluminación indirecta en una escena, es decir, la iluminación por otros objetos, es el
resultado de la reflexión de la luz por otros objetos. La cantidad de luz reflejada depende de
las propiedades físicas del material, pues puede ser opaco, en cuyo caso no permite fácilmente
la transmisión de la luz; o muy reflectivo, facilitando la reflexión de la luz y la iluminación
al resto de la escena.
En la práctica, el fenómeno de la reflexión se define a través de una función de distribución
bidireccional (BRDF) la que se compone de tres tipos de reflexiones como se muestra en la
figura l. La reflexión difusa es la luz que se refleja de manera ideal en todas direcciones, así
como de manera direccional dependiendo de la aspereza de la superficie, y otras propiedades
físicas como la conductividad. Por otro lado, la reflexión especular, es la luz que refleja una
superficie de manera que se concentra en una porción angular, así, una reflexión especular
ideal puede verse en superficies con características de espejos ideales.
El tratamiento de la iluminación global ha requerido el diseño de métodos que simulan el
comportamiento de la luz en una escena; estos métodos son "Ray Tracing" y "Radiosidad",
punto de referencia
de proyección
posiciones de pixel en el plano de proyección
Fig. 2: Ray Tracing.
los cuales serán descritos brevemente a continuación.
2.2.1 Ray Tracing.
15
Una de las pnmeras evaluaciones del modelo de iluminación global fue hecha hace poco
más de 15 años, a través de la aplicación de un algoritmo recursivo con un concepto de
trazado de rayos ( Ray Tracing ). Este algoritmo considera la luz proveniente de las fuentes
de iluminación, así como las aportaciones de luz que provienen de la reflexión y refracción
de otros objetos.
El funcionamiento de este algoritmo es el siguiente: se define un punto fijo, normalmente
determinado por la posición del observador, del cual parten rayos hacia los objetos en la
escena. Los objetos pueden ser alcanzados directamente por estos rayos e indirectamente
como consecuencia de las reflexiones presentadas en otros objetos o superficies. De esta forma
se modela la iluminación en una escena; se puede observar que el resultado es dependiente
de la posición que tenga el observador. Otra característica básica del método de ray tracing
es que debe determinar las superficies visibles desde el punto fijo.
16
Una de las principales deficiencias del algoritmo de ray tracing es su dificultad para consi
derar en la reflexión el cálculo de la interreflección difusa. Ray tracing resulta un método
adecuado para modelar y calcular tanto reflexiones especulares exactas como transparencia
( ver figura 2 ) .
2.2.2 Radiosidad.
Otro método más reciente para evaluar el problema de la iluminación global toma en cuenta
las propiedades físicas y principios termodinámicos que poseen los objetos. El método se
basa en uno que se aplicó al problema del intercambio de calor entre superficies, por lo que
es mejor conocido como "Radiosidad".
Los métodos de radiosidad son aplicables a la solución de interreflección de la luz entre
superficies difusas ideales. El fundamento teórico del método de radiosidad es el principio
de conservación de la energía. Además, a diferencia de otras técnicas, radiosidad comienza
con una ecuación de balance de energía, la cual es aproximada por métodos numéricos.
A diferencia de ray tracing, radiosidad es independiente de la posición del observador, puesto
que soluciona la ecuación de iluminación en posiciones distribuídas sobre las superficies del
medio ambiente.
El método de radiosidad considera reflexiones difusas, pero no reflexiones especulares m
transparentes. Una solución por radiosidad resulta adecuada cuando se están modelando
medios ambientes cerrados tales como cuartos y oficinas.
2.3 ECUACION DE RENDERING.
El Rendering es un término para describir el proceso de iluminación y sombreado sobre
objetos en 30; también se asocia con el proceso de "síntesis de imágenes. La dificultad
para modelar la iluminación global, radica en gran medida en los cálculos de la iluminación
indirecta que recibe una superficie. Las superficies que participan en una escena pueden
recibir iluminación indirecta de cualquier otra superficie en la escena, así como también
17
pueden recibir la sombra de alguna otra superficie.
Los efectos de iluminación y sombreado entre superficies, también es descrito como "Ren
dering", y su modelo matemático fue definido por primera vez por Kajiya en una ecuación
que la llamó "Ecuación de Rendering". La solución que propuso se basa en la aplicación de
métodos de integración de Monte Cario y se expresa, para una superficie S, como:
L(x, w') j fr(x) L(x, w) G(x, x') V(x, x') dA (1) s
donde:
x y x' son elementos de diferentes superficies.
fr ( x) es la función de reflexión en el punto x.
L(x, w) es la radiación en x a lo largo del vector w.
G(x, x') es la orientación entre x y x' y está dada por:
G( ') _ G( , ) _ coso~ cos ºº X, X - X, X -1
,12 x-x
V(x, x') es la función de visibilidad, es 1 si x y x' son mutuamente visibles
y O de otra forma.
La ecuación anterior ha sufrido algunas adiciones para considerar intensidades entre dos
puntos, así como los modos de transporte de la luz en una superficie. Otra consideración
resulta al tener un medio ambiente consistente únicamente de superficies opacas, así, la
única fuente de luz adicional es debido a la emisión desde la superficie misma:
L(x', w') Le(x', w') + j fr(x) L(x, w) G(x, x') V(x, x') dA (2) s
donde:
Le(x', w') es la intensidad de la luz emitida entre dos puntos.
Haciendo algunas otras simplificaciones, la ecuación anterior puede expresar la conservación
de la energía luminosa, suponiendo que todas las superficies en el medio ambiente son
reflectores difusos Lambertianos3 . La ecuación queda ahora definida en términos de ra-
3 Reflejan la misma intensidad de luz en todas direcciones, independientemente de la dirección de llegada de la energía y su distribución.
diosidad como:
donde:
E(x)
p(x)
B(x')
B(x) E(x) + p(x) j B(x') G(x, x')1rV(x, x') dA'
s
es la emisión del elemento x.
es la reflectividad del elemento x.
es la radiosidad del elemento x.
18
(3)
La función de radiosidad describe un valor para cada posición sobre la superficie. También
podemos observar que el término de radiosidad aparece a ambos lados de la ecuación inte
gral, lo que representa una dificultad por no haber una solución analítica, es por esto que
normalmente se eligen métodos numéricos para su solución.
De la ecuación de radiosidad podemos decir que se trata del total de energía saliendo de un
punto en la superficie por unidad de área por unidad de tiempo y resulta de la suma de la
energía emitida directamente y la energía reflejada.
2.4 SOLUCIONES MEDIANTE ELEMENTOS FINITOS Y MONTE CARLO.
La ecuación de radiosidad es una ecuación integral difícil de solucionar analíticamente pues
la dimensión del espacio de la función de radiosidad B(x) es oo. Una primera forma de
solucionarla es reformular la ecuación discretizándola, de tal manera que se subdivide la
superficie en un número finito de parches y se soluciona la versión discreta para cada uno
de ellos. Esta aproximación se le conoce también como el método de elementos finitos pues
en lugar de emplear funciones globales básicas, se parte su dominio en un número finito de
piezas llamadas elementos, y usa funciones básicas que son locales a cada elemento.
La solución numérica a la ecuación de radiosidad se aproxima a través de una constante por
la combinación lineal de funciones base:
19
n
B(x) ~ B ¿ Bi Ni(x) (4) i=l
donde:
Bi es el conjunto de coeficientes desconocidos.
Ni = { o1
si x está fuera del elemento;
si x está dentro del elemento
La solución que se desea encontrar es aquélla que minimice el error entre las soluciones exacta
y aproximada, es decir:
B(x) - ÍJ(x) (5)
sin embargo, dado que la solución exacta es desconocida, el cálculo resulta imposible. En
lugar de esto, ÍJ(x) se caracteriza como:
ÍJ(x) E(x) + p(x) j ÍJ(x') G(x, x') dA' (6) s
así pues, la mejor solución a esta función es aquella que minimice el residuo:
r(x) ÍJ(x) - E(x) - p(x) j ÍJ(x') G(x, x') dA' (7) s
Existen dos métodos para minimizar el residuo: el método de colocación de puntos y el
método de Galerkin.
El método de colocación de puntos forza a aproximar la solución del residuo en cero, para un
conjunto de n puntos x1 , x2 , ... Xn donde n es el número de parámetros desconocidos [16].
La minimización del residuo a través del método de Galerkin [16] está asociado con los
métodos de elementos finitos; este método calcula n parámetros desconocidos seleccionando
n funciones de peso w1 ( x), w2 ( x), ... Wn ( x) de tal manera que la evaluación de cada una de
sus integrales sean cero, es decir,
20
b
j c(x)wi(x) dx 1, 1, 2, ... n (8) a
donde:
a, b es el rango de valores límite para x.
c(x) es el residuo evaluado en x.
Otra alternativa para la solución de la ecuación de radiosidad son los métodos que usan
números aleatorios para obtener una respuesta aproximada a un problema, este tipo de
métodos son mejor conocidos como métodos de Monte Carlo [21]. La integral es evaluada
en los puntos muestra, de tal suerte que los valores pueden variar dependiendo de como se
elijan los puntos muestra.
La rapidez para encontrar la respuesta depende de la elección de los puntos que minimicen
el residuo, aunque también se puede acelerar este proceso si se conoce alguna restricción
o rangos de valores en los que la función integrada genere mejores resultados. Este último
tipo de elección de puntos muestra es denominado muestreado por importancia, dado que
los valores se eligen en donde es más importante la función.
Para medios ambientes discretos, la ecuación de radiosidad se expresa en forma discreta a
través de una suma, suponiendo una radiosidad constante sobre los pequeños segmentos de
superficie, es decir,
donde:
n
Ei + Pi L Bj Fij j=l
es el factor de forma de j a i ( fracción de la energía que sale del
(9)
.IIBLIOTE
\ \\,-ul,1. 1}\~
~ l-..$":•:,¡;oy.., ~ ( /,
segmento j y llega al segmento i ) . Y está dado por: --... ·
Fij = 1 J J G(x, x') dAí dA '·¡, ., '.·· ~ A A \···,r _
- . ; ' . {1:. \;.:;· Una forma física más intuitiva para expresar la ecuación de radiosidad resulta de agre~-~
términos de las áreas A, como se observa en la siguiente ecuación:
fY'J93
21
n
EiAi + Pi L Bj ~j Ai (10) j=l
además, suponiendo que se cumple la relación de reciprocidad entre los factores de forma en:
F-·A· JZ J P·A-i1 i (11)
se obtiene:
n
Ei Ai + Pi L Bj Fji Aj (12) j=l
La interpretación física de la ecuación anterior es que la energía total, Bi Ai que sale de
un elemento, depende de la luz que emite directamente más la luz que es reflejada. La luz
reflejada depende de la luz que sale de cualquier elemento en el medio ambiente y llega a
este elemento.
La ecuación de radiosidad puede ser expresada en forma matricial como:
1 - P1F1,1 -p1F1,n B1 E1
-p2F2,1 -p2F2,n B2 E2
(13)
Pn-IFn-1,1 Bn-1 En-1
-pnFn,I 1- PnFn,n En En
2.4.1 Factor de Forma.
Una vez que se ha discretizado la escena, el cálculo de los factores de forma para la ecuación 12
resulta un proceso que consume mucho tiempo, pues se hace para cada parche en la escena.
A medida que se incrementa el número de elementos producto de la discretización, crecerá la
22
dA'
A'
V(x,x?
A
Fig. 3: Geometría del Factor de Forma.
complejidad temporal. Por ello, se han diseñado algoritmos que buscan minimizar el tiempo
asociado con estos valores.
El factor de forma, como vemos en la ecuación 9, es estrictamente una interpretación
geométrica ( ver figura 3 ), su valor depende exclusivamente de la forma y la posición
relativa de las superfices en la escena, y las propiedades de emisión y reflexión no alteran su
valor.
Los algoritmos que han sido diseñados para el cálculo de los factores de forma pueden
clasificarse en analíticos y numéricos. Los primeros pueden utilizarse de ser completamente
visibles las superfices. El segundo grupo hace sus cálculos basándose en muestreos de hemis
ferios o de áreas.
Algunos ejemplos de algoritmos analíticos utilizan el diferencial del área a un polígono con
vexo, así como de polígono a polígono.
Las soluciones numéricas para el factor de forma, aproximan su integral, como la suma de
las evaluaciones hechas para la superficie en varios puntos. Como ejemplo de este tipo de
métodos podemos mencionar los métodos de Monte Carlo antes descritos, el "método del
Hemicubo" y los "métodos jerárquicos".
23
Fig. 4: Hemicubo.
El método del Hemicubo empleado por Cohen et al [4] para el cálculo de los factores de forma,
define un hemicubo sobre la superficie de análisis. El hemicubo se subdivide en celdas de tal
manera que cada una de ellas define una posible dirección y un ángulo ( ver figura 4 ) . El
factor de forma se aproxima por la proyección de cada elemento sobre las caras del hemicubo
y sus factores de forma asociados a cada elemento.
Los métodos jerárquicos para la minimización de la complejidad buscan disminuir el número
de elementos en la escena con una mínima repercusión en la exactitud de la solución.
2.4.2 Solución a la ecuación de Radiosidad.
La solución de la ecuación de radiosidad conlleva a la solución de un sistema den ecuaciones
lineales con n incógnitas, las cuales resultan de la aproximación discreta de la función de
iluminación. Para resolver la ecuación de radiosidad, es decir, su sistema de ecuaciones,
podemos aplicar los siguientes pasos:
1. Entrada del modelo geométrico.
2. Definir el problema en espacios finitos.
(a) Subdivisión de superficies.
(b) Selección de funciones básicas.
( c) Selección de la métrica del error.
3. Cálculo de los factores de forma.
4. Solución del sistema de ecuaciones lineales.
5. Reconstrucción de la solución.
6. Despliegue de resultados a partir de un punto de observación.
24
Una de las primeras evaluaciones para la solución del sistema de ecuaciones fue el uso de la
eliminación Gaussiana [19, 20], sin embargo, se han generado algunas otras propuestas para
acelerar la solución.
Una solución interesante que podemos mencionar es el trabajo de Cohen et al [4], en el
cual proponen el uso de un hemicubo para el cálculo de los factores de forma, así como la
introducción de un algoritmo de refinamiento progresivo, que explicaré más adelante, como
un medio para la solución del sistema lineal de ecuaciones. Este método tiene la ventaja de
que converge rápidamente hacia una imagen exacta a la vez que despliega la imagen que se
está aproximando, a medida que el algoritmo procede.
Otra solución interesante es la propuesta por Hanrahan et al [10] quienes proponen una
solución a la radiosidad a través de un refinamiento jerárquico, buscando minimizar la com
plejidad temporal asociado al cálculo de los factores de forma.
2.4.3 Algoritmo de Refinamiento Progresivo.
El algoritmo de refinamiento progresivo de Cohen et al [4] es diferente del método tradicional
en que después de que han sido discretizadas las superficies para su análisis, se calcula un
renglón de la matriz de factores de forma, más que la matriz completa ( ver ecuación 13 ),
efectuando así un paso de la solución cada vez y desplegando el resultado intermedio. Este
algoritmo en pseudocódigo podría verse como:
Para ( todo i ) {
Bi = Ei
LiBi = Ei
} Mientras ( no converge ) {
}
Tomar i, tal que LiBi * Ai sea el mayor; Para ( cada elemento j ) {
Lirad = LiBi * p1 F1i
LiB1 = !iB1 + Lirad
B1 = B1 + !irad
} LiBi = O Desplegar la imagen usando Bi como la intensidad del elemento i
25
Este algoritmo puede interpretarse físicamente de la siguiente manera: todos los elementos i
en la escena tienen una radiosidad Bi, así como una proporción de radiosidad que no ha
"disparado" al medio ambiente. En cada iteración, el algoritmo elige el elemento con la mayor
radiosidad sin disparar, y la dispara a través del medio ambiente. Al hacerse este disparo,
los elementos restantes reciben una contribución de LiBi a su radiosidad, así como a su
porción de radiosidad no disparada. Finalmente, después del disparo, el elemento i no tiene
más radiosidad por disparar ( ver figura 5 ) .
El algoritmo hace a cada paso el disparo de la radiosidad del elemento con la mayor energía
LiBi A, actualizando a los elementos restantes. Cada paso toma O(n) operaciones, pues se
efectúa el cálculo de un renglón de la matriz de factores de forma ( ver ecuación 13 ). Cohen
et al [4] mostraron además, que se requieren menos de n pasos para obtener una buena
solución.
2.4.4 Algoritmo de Jerarquía Multinivel.
Este algoritmo diseñado por Hanrahan et al [10] construye una representación jerárquica de
la matriz de factores, de forma por medio de una subdivisión jerárquica de los parches de
acuerdo con un límite definido por el usuario.
26
Fig. 5: Contribución de energía a cada parche.
Este algoritmo está inspirado en el problema de N-Cuerpos, en el que se definen interacciones
gravitacionales entre una colección de partículas. Cada una de las partículas ejerce una
fuerza sobre las restantes n - 1 partículas, generando O(n2) interacciones. Sin embargo, se
ha encontrado que la fuerza ejercida por un grupo de partículas a cierta distancia de una
partícula, puede aproximarse a través de una sola interacción. De esta forma se reduce el
número de interacciones y como consecuencia el número de factores de forma necesarios para
la solución del problema.
A medida que avanza el algoritmo subdivide de manera adaptativa y en forma jerárquica las
superficies de los parches4 ( ver figura 6 ).
A la par de la subdivisión se generan ligas entre los nodos, lo cual representa una relación
física entre uno y otro conjunto de elementos definiendo el intercambio de energía entre ellos.
Cada liga representa un conjunto de factores de forma para todos los pares de elementos en
los subárboles ligados. En la matriz de factores de forma, la liga entre dos hojas de subárboles
representa una sola entrada, mientras que una liga a un nivel mayor representará un grupo
de factores de forma.
El refinamiento recursivo en este caso, define la subdivisión de superficies en quadtrees y
4 Resulta un quadtree de nodos.
27
Fig. 6: Quadtrees jerárquicos e interacciones.
crea ligas entre nodos de quadtrees. El pseudocódigo de este procedimiento se describe a
continuación:
Refina (Patch *p, Patch *q, f loat Ff ) {
Patch cual, r ;
}
Si ( Oraclel (p, q, Ff ) )
Ligar (p,q); si no {
}
cual= Subdividir (p, q); Si ( cual == q )
Para (cada nodo hijo r de q) Refina (p, r, Ff );
si no Si ( cual == p ) para ( cada nodo hijo r de p ) Refina ( r, q, Ff ) ;
s1 no Ligar (p, q);
float Oraclel( Patch *p, Patch *q, f loat Ff ) { Si ( p->area < Af y q->area < Af )
regresar( FALSO);
}
Si ( EstimarFactorForma ( p, q) < Ff ) regresar( FALSO);
sino
regresar( VERDADERO);
La descripción de los procedimientos antes mencionados es como sigue:
Oraclel, estima el error que podría generarse de ligarse los dos nodos,
más que ligarse un conjunto de nodos a niveles más bajos de p
y/o q.
Subdividir, es llamado cuando es necesaria la subdivisión de los parches a
niveles más bajos, permitiendo una reducción del error.
Ligar, construye la liga entre dos parches, calculando el factor de
forma entre las áreas representadas en los nodos p y q del
quadtree.
28
Para efectos de acelerar el cálculo de los factores de forma, Hanrahan et al [10] emplean
un estimado del factor de forma utilizando una solución analítica, empleando un disco que
rodee el área del elemento analizado. Así el cálculo se aproxima por:
cose ~ --w
7f q (14)
Hanrahan et al [10] citan que su algoritmo de refinamiento jerárquico reduce el número de
interacciones necesarias en la escena a la vez que mantiene la exactitud de los factores de
forma que son calculados. Así mismo indica que el algoritmo resulta adecuado en ambi
entes con relativamente pocos polígonos grandes, cuyo alto grado de brillantez requiere una
subdivisión en más elementos.
Este trabajo de investigación usó el algoritmo de refinamiento jerárquico como evaluación
para las funciones de iluminación.
29
3 MÉTODOS DE OPTIMIZACIÓN.
La necesidad de minimizar una solución al problema mverso de iluminación lleva a la
búsqueda de métodos que permitan mejorar la solución.
La Optimización es una de las tareas encaminadas a encontrar el mejor conjunto de condi
ciones que permitan lograr cierto objetivo formulado en términos matemáticos. Existen
métodos de optimización local y global basados en procesos naturales para encontrar un
óptimo local o global respectivamente. Estos métodos de optimización incluyen, entre otros:
"Gradiente Descendente", "Recocido Simulado" y "Algoritmos Genéticos". Se usan algorit
mos genéticos pues se buscan soluciones que minimicen la posibilidad de "caer" en mínimos
locales. Estos algoritmos han probado ser excelentes métodos de búsqueda, y han sido usados
en un trabajo propuesto por B. Lange para aplicarlos en iluminación [14].
3.1 MÉTODO DEL GRADIENTE DESCENDENTE.
Los métodos para minimizar una función objetivo f (x) con n variables independientes y
sin restricciones comienzan en una iteración i con un valor estimado para xi que supone un
mínimo. En iteraciones subsecuentes, es decir, en la iteración i + 1 se busca y se utiliza un
vector que permite orientar la dirección de la búsqueda de un nuevo valor para Xi+l menor
al anterior, de tal manera que,
(15)
30
La minimización de funciones puede hacerse usando métodos descendentes, que evaluen las
derivadas de la función objetivo. Este tipo de métodos también son conocidos como "Métodos
de Gradientes" [18, 20, 22].
El gradiente de una función f, denotado como Vf, es el conjunto de derivadas parciales de
f, respecto a cada una de las variables.
vf (16)
Físicamente el gradiente es un vector con n componentes, el cual se caracteriza por dar la
dirección en el cual f (x) crece. Una variante es emplear el valor negativo del gradiente, es
decir, la dirección descendente para calcular el mínimo.
El método del gradiente descendente inicia en un punto x 0 e iterativamente se mueve hacia
el óptimo usando,
(17)
donde:
fi es la longitud del peso óptimo.
Si = -vf vector gradiente descendente.
Finalmente, el método converge cuando alguna de las siguientes condiciones se satisface:
1 ... n (18)
(19)
Este método se considera como de optimización local pues puede caer en mínimos locales
como el punto B en la figura 7.
31
A
D
Fig. 7: Mínimo local y global.
3.2 RECOCIDO SIMULADO.
El Recocido Simulado [7, 11, 26] es un método usado para reducir la posibilidad de caer en
mínimos locales. El método es conocido así por la analogía del proceso físico para el templado
de metales.
Una sustancia o un metal al cual se le eleva su temperatura sufre alteraciones en su confi
guración atómica, de tal manera que posee un estado de energía mayor. Si por el contrario,
quisiéramos reducir la energía al mínimo posible, una disminución inmediata de la tempera
tura no lograría el efecto deseado, pues la configuración atómica no tendría una estructura
cristalina regular, y por ende no sería la energía mínima.
Para alcanzar la energía mínima global se emplea el proceso de recocido, en el cual se lleva
el material a una alta temperatura para después disminuirla gradualmente, con lo que los
átomos alcanzan su estado de equilibrio.
En este estado de equilibrio, el material sigue una distribución de probabilidad dada por la
relación:
P (!:le) a exp( -!:le/ kT)
donde:
!:le representa la diferencia de energía entre la actual y la previa.
P(l:le) es la probabilidad de que el sistema esté en un estado de energía !:le.
k Constante de Boltzmann que relaciona la temperatura y la energía.
T Programación de los cambios de temperatura en cada paso i, es decir,
las fluctuaciones entre las dos probabilidades previas.
32
(20)
El valor del cambio de la energía está dado por !:le = Ei+1 - Ei, la incorporación de los
comportamientos termodinámicos para su aplicación en la minimización de funciones se
hizo por primera vez en 1953 [19]. Para aplicar dicho comportamiento se simula un sistema
termodinámico suponiendo que su cambio de energía de E 1 a E2 tiene una probabilidad dada
por la ecuación 20. En esta ecuación cuando la energía Ei+l es menor que la energía Ei la
probabilidad es mayor a 1, por lo que arbitrariamente se define en l.
La simulación de un problema como un sistema termodinámico fue hecho por Metrópolis [19],
quien en su propuesta fijó algunas consideraciones:
l. La función objetivo f(x) debe definirse en términos de una energía E.
2. Un control del parámetro similar a la temperatura T, así como una programación de los cambios en el parámetro. Estos cambios indican la manera de ir bajando la temperatura, algunos experimentos citados por Ingber [11] muestran que este valor puede definirse a lo más de,
T(k) = ~ lnk
(21)
3. Una descripción de posibles configuraciones del sistema, es decir, los valores de las variables.
4. Un generador de cambios aleatorios en la configuración, es decir, opciones que se le dan al sistema para explorar. Dicho de otra forma, un l:lx que permite llevar al sistema de una configuración x a otra ubicada en x + l:lx. Este paso resulta problemático debido a la ineficiencia de los generadores propuestos en la actualidad.
La elección de un adecuado valor de T determina el éxito o fracaso para alcanzar el mínimo
global, por esto es necesario experimentar sobre cada problema en particular [19].
33
3.3 ALGORITMOS GENÉTICOS.
Durante los últimos años ha habido un mayor interés por aplicar las teorías de evolución
para la resolución de problemas de búsqueda de óptimos globales. Esta sección presenta los
conceptos básicos necesarios para la comprensión del tema.
3.3.1 ¿ Qué son ?.
"Los Algoritmos Genéticos (AGs), son modelos de máquinas de aprendizaje que basan su
comportamiento en los principios de la Genética Natural y la Selección Natural" [8]. Los AGs
se han probado como eficientes mecanismos de búsqueda cuando se aproxima a un óptimo
global, dentro de espacios grandes y complejos, además de haber sido probados en diversas
áreas [1, 2]. La manera en que operan los AGs, respecto a los mecanismos tradicionales de 1
optimización, hacen sus características propias:
l. Operan sobre un conjunto de parámetros codificados más que sobre los parámetros mismos.
2. Buscan en un conjunto de puntos más que sobre uno solo.
3. Usan una función objetivo.
4. Operan de manera probabilística más que determinística [5].
Las características anteriores determinan las posibilidades de uso de un AG para la solución
de algún problema particular pues puede resultar impráctico su uso. Se puede decir que el
uso de un AG es recomendable cuando se tengan problemas cuyo espacio de búsqueda sea
discreto, o bien, con espacio de búsqueda continuos, pero que posean un rango de soluciones
relativamente pequeño [3].
3.3.2 Elementos en un Algoritmo Genético.
Los componentes básicos que podemos encontrar en un AG son:
34
Tabla 1: Tabla de aptitudes porcentualizada.
No. Cadena Aptitud Porcentaje
A 1111 225 65.2
B 0100 16 4.6
e 0010 4 1.2
D 1010 100 29.0
Totales 345 100.0
• Representación apropiada del problema ( individuos en términos de cromosomas ) .
• Operadores genéticos ( reproducción, cruzamiento y mutación ) .
• Función Objetivo o de Aptitud.
La información contenida en un algoritmo genético se representa en su forma más sencilla
como secuencias de unos y ceros, suponiendo un alfabeto binario= {O, 1}. Así, el valor 01001
representa un valor para la(s) variable(s) asociada(s) al problema. Normalmente se le conoce
como "individuo" y se define en términos de cromosomas ( secuencias de unos y ceros ),
como aparece en el ADN humano.
El AG crea una población de individuos, los cuales se someten a procesos evolutivos en los
que actúan los operadores genéticos para generar nuevos y mejores individuos, sobreviviendo
los más aptos de acuerdo con una función de aptitud definida para el problema.
La primera generación se obtiene aleatoriamente. A partir de aquí, el algoritmo opera de
acuerdo a una función de aptitud para valorizar las soluciones codificadas ( ver tabla 1 ).
La siguiente generación resulta de un proceso de reproducción en el que se seleccionan pares
de individuos, quienes actuarán como padres de los nuevos individuos a generar. Un meca
nismo sencillo para seleccionar los individuos se basa en la analogía con una "ruleta". A cada
cromosoma se le asocia una fracción proporcional a la aptitud, así, al elegir un individuo, se
espera elegir los más aptos ( ver figura 8 ) .
35
A-ffi;l. --~
C-1,2--~
Fig. 8: Aptitud proporcional.
Una vez elegidos los individuos de una población, se aplica un operador de cruzamiento, el
cual combina el material genético de los padres. Normalmente este proceso opera en base a
un porcentaje de tal suerte que no todas las parejas elegidas se cruzan, y además varía el
punto de cruzamiento ( ver figura 9 ) .
Al ir generando nuevos individuos como resultado del cruzamiento entre ellos se utiliza un
operador de mutación, el cual permite que exista variedad en las generaciones subsecuentes.
El operador de mutación hace un cambio de alguna de las posiciones del cromosoma.
Los valores que pueden tener los operadores de mutación y cruzamiento son determinantes
para una apropiada convergencia. Un estudio de DeJong en 1975 [5] mostró que resulta
adecuado usar valores pequeños ( menos del 5% ) para el operador de mutación respecto al
valor que se asocia con el operador de cruzamiento ( mayor del 60% ) .
Los individuos en la población cuya medida de aptitud sea la más baja, son reemplazados
por nuevos individuos en generaciones subsecuentes. La determinación de cuándo terminar
un algoritmo genético puede resultar de decidir correr el algoritmo un número máximo de
36
Punto de Cruce Descendientes
¡ Padre 1 1 O O 1 O 1 1 O Hijo 1 [2_001 001
º' .. 1 1 O 1 Hijo2 11 101011
º' Padre 2
0010
Fig. 9: Cruzamiento de individuos.
generac10nes, o bien, detenerlo cuando la población se haya estabilizado y sus individuos
posean una aptitud similar.
El AG en pseudocódigo puede ser visto como sigue:
t = o Inicializa_Foblacion P(t) Evalua P(t); Mientras ( no converge )
t = t + 1
}
P' = SeleccionarPadres P(t) Cruzamiento P' ( t) Mutar P'(t) Evalua P'(t) P = P'(t)
Fin del AG
En estudios de Ingber [11] en los que compara AGs y Recocido Simulado, muestra una
versión modificada de Recocido Simulado para mejorar su rendimiento, aunque indica que
esto no resulta fácil de codificar. En sus pruebas ambos métodos encuentran la solución de
funciones propuestas ( hasta de 4 dimensiones ) en tiempos razonables. Los resultados a
detalle pueden consultarse en Ingber [11].
37
Recocido Simulado y AG requieren un tiempo de experimentación para encontrar aquellos
valores que lleven a una solución con las menores varianzas [8, 11, 19].
3.3.3 Esquemas.
Los algoritmos genéticos guían su búsqueda hacia una solución óptima, aprovechando la
información que está contenida en la población. En una población, los individuos con mejor
aptitud poseen características similares ( ver tabla 1 ) .
La tabla 1 muestra algunos individuos de cierta población, en ella podemos observar que los
individuos con una mayor aptitud tienen un 1 al principio de la cadena. De esta forma, las
similitudes entre los individuos más aptos pueden ser aprovechados para guiar la búsqueda.
Las similitudes en AG están expresadas en un concepto conocido como "esquemas". Un
esquema es una plantilla que describe a un conjunto de cadenas con similitudes en ciertas
posiciones.
Para ejemplificar este concepto, consideremos una codificación simple usando un alfabeto
binario { O, 1} al cual le agregamos un símbolo comodín, digamos *, con lo que nuestro
alfabeto queda en forma completa como {O, 1, * }. De esta forma, una cadenas puede quedar
representada a través del esquema H, si en cada posición del esquema existe un 1 para el
1 que exista en la cadena, un O para cada O que aparezca en la cadena y no importa cual
valor haya en la cadena si en el esquema aparece un símbolo de *· Por ejemplo, el esquema
H = *11*1, representa al subconjunto de 4 cadenas C = {01101,01111, 11101, 11111}; así
como el esquema H = *1111 representa al subconjunto de 2 cadenas C = {01111, 11111 }.
Existen algunas propiedades asociadas con los esquemas, por ejemplo, la longitud de la
cadena nos permite estimar el total de esquemas que podemos obtener, una cadena binaria
de longitud5 l posee un total de 31.
Otras dos propiedades de los esquemas son el orden y la longitud de definición. El orden
de un esquema H, denotado como o(H) es el número de de posiciones fijas en el esquema.
Por ejemplo, el esquema H = 101 * ** su orden es 3 , dicho de otra forma o(lül * **) = 3,
5 También conocida corno cardinalidad.
38
mientras que el orden del esquema O****** es 1.
La longitud de definición de un esquema H, expresado por <5(H), es la distancia entre la
primera y la última posición especificada en el esquema. Por ejemplo, la longitud del esquema
011*0** es <5 = 4 dado que <5(H) = 5 - 1, mientras que para el esquemaº****** es <5 = O.
Las propiedades anteriores proveen características que permiten un análisis mayor acerca de
las implicaciones que tiene la aplicación de los operadores genéticos de selección, cruzamiento
y mutación sobre una población de individuos. Los efectos de cada uno de estos operadores
sobre los esquemas pueden ocasionar que algunos se destruyan y otros persistan en subse
cuentes generaciones, tal es el caso de los esquemasº*** 1 y ***11* respectivamente. Puede
observarse en los esquemas anteriores que para el operador de cruzamiento es más difícil
destruir el esquema con longitud de definición menor.
El detalle del efecto que cada uno de los operadores genéticos puede ocasionar sobre un
esquema H puede verse en las referencias [8, 9].
39
4 SOLUCIÓN AL PROBLEMA INVERSO DE ILUMINACIÓN.
En la actualidad, los mecanismos para simular correctamente el proceso de iluminación no
han sido suficientes pues no tienen una forma práctica de definir los efectos que se desean
obtener. Se han propuesto alternativas diferentes que permiten simular los efectos de una
manera más natural y práctica para los diseñadores, solucionando de manera inversa el
problema. Este capítulo menciona las técnicas que han sido propuestas así como la propuesta
en este trabajo de investigación.
4.1 PROBLEMA INVERSO.
Las herramientas que emplean los diseñadores de iluminación normalmente siguen un proceso
de prueba y error, es decir, el diseñador especifica la cantidad de luces así como su posición
e intensidad en una escena; hecho esto, ve si el resultado cumple con sus expectativas; de no
ser así, cambia la posición de las luces, modifica sus intensidades e incluso el tipo de luz para
ver nuevamente el resultado; el proceso se repite así a prueba y error hasta que se logra el
efecto deseado. Este proceso resulta poco práctico y requiere de mucha intuición por parte
del diseñador, pues no es fácil simular correctamente el proceso de la iluminación si no se
pueden definir los resultados que se desean obtener.
40
4.2 PINTANDO CON LUZ.
Shoeneman et al [23] proponen como solución al problema inverso de iluminación un me
canismo más natural en el que el usuario crea una imagen objetivo o deseada, pintando
las áreas que desee con la ayuda de un pincel de luz y fijando fuentes de luz en posiciones
predeterminadas. El método de aproximación se encargará de determinar la configuración
de las fuentes de iluminación ( color e intensidad ) [23] que más se acerque al efecto deseado
por el usuario.
El problema es representado mediante una función objetivo '11 compuesta por n funciones
resultantes asociadas con cada fuente de luz, cada una de las cuales pueden ser calculadas
a través de Radiosidad. El problema de aproximación de esta función objetivo, consiste en
encontrar una combinación de pesos, wi, no negativos, tales que la función,
n
'11 = L Wicl>i
i=l
minimice la función objetivo 11'11-'1111· Así el problema se define en uno de "mínimos cuadra
dos" [15]. Para encontrar los pesos que minimicen la función objetivo, Schoeneman et al [23]
usan el método iterativo modificado de Gauss-Seidel. Al emplear Radiosidad esta solución
se caracteriza por ser independiente de la posición del usuario pero se limita a calcular la
iluminación directa.
4.3 RADIOPTIMIZACIÓN: OBJETIVO BASADO EN , ,
SINTESIS DE IMAGENES.
Kawai et al [12] proponen un método para el diseño de la iluminación en un medio ambiente
usando técnicas de optimización aplicadas a sistemas de síntesis de imágenes basados en
Radiosidad. Esta solución, determina la configuración óptima de la emisión de fuentes de
iluminación, reflexión de elementos y parámetros para el direccionamiento de fuentes de
iluminación, de tal manera que se minimice la energía o bien que la iluminación ofrezca
41
cierta ambientación en un cuarto cerrado.
La solución utiliza modelos de percepción psicológicos como criterio de optimización pues
está basado en impresiones subjetivas de la solución, tal como, que tan agradable y privado
resulta el efecto logrado. Algunas de las percepciones que son consideradas son el brillo,
espacio, así como claridad visual y agradable.
El problema es formulado en base a variables, restricciones y una función objetivo; para su
solución usaron un método de optimización basado en técnicas de optimización sin restric
ciones, de tal manera que el problema es convertido en un problema sin restricción a través
del método de penalización en el que se incluye un término en la función objetivo cada vez
que se excluye una restricción.
Kawai et al [12], categorizan las restricciones que sujetan a la función objetivo como físicas6,
orientadas al diseño7 y de barrera8. Cada una de las restricciones implicadas en el problema
se convierten en un término de la función objetivo empleando el método de penalización.
El método de penalización agrega un nuevo término a la función objetivo igual al cuadrado
de la restricción violada. Por ejemplo, si la restricción Cj, es una restricción de igualdad, tal
como Bij = Kj, el término de penalización correspondiente, f Cj en la función objetivo es
fcí = Aií(Kí - Bií) 2
Algo similar se aplica para las desigualdades, sólo que en este caso el término de penalización
se aplica cuando la restricción no se satisface y en otro caso es cero. Para minimizar esta
nueva función objetivo ya sin restricciones se aplica el método de Broyden-Fletcher-Goldfarb
Shanno ( BFGS ) [18].
6 Expresadas en la ecuación de Rendering.
7 Provistas por el usuario, a través de desigualdades o igualdades relacionadas con la Radiosidad.
8 Son los límites permisibles para generar un resultado físicamente correcto.
42
4.4 ALGORITMOS GENÉTICOS EN EL DISEÑO DE ILUMI
NACIÓN.
Este trabajo de investigación propone para resolver el problema inverso de iluminación, el
uso de algoritmos genéticos [8], con una evaluación de funciones de iluminación a través de
radiosidad jerárquica [10].
El problema de iluminación a través de AG ha sido tratado por Lange et al [14] para la deter
minación de la iluminación global empleando ray tracing como evaluación de las funciones
de iluminación. El estudio de Lange et al [14] resuelve de manera directa la iluminación
global. El algoritmo genético es usado para el cálculo de iluminación determinando la mejor
configuración de la dirección de los rayos incidentes que maximicen su función objetivo. Los
operadores genéticos empleados son selección, a través del método de la ruleta, el operador
de cruzamiento y el de mutación. El estudio indica un buen desempeño de los AGs como
mecanismo para la simulación de la iluminación.
El problema inverso de iluminación en su forma más general implica la búsqueda de la mejor
combinación de número de luces, intensidades, posiciones y tipos de luces que logren un
efecto deseado. Las características de robustez en la búsqueda de valores óptimos hace que
los AG constituyan un método adecuado para esta solución.
A continuación se describen los métodos empleados, es decir, Radiosidad Jerárquica y un
Algoritmo Genético usados para la solución del problema inverso de iluminación, así como
los componentes del algoritmo aplicados a este problema particular.
4.4.1 Radiosidad Jerárquica.
La evaluación de las funciones de iluminación del problema inverso se hace en este trabajo
usando el algoritmo de Radiosidad Jerárquica [10]. En principio se utilizó Radiosidad Pro
gresiva [4], sin embargo, el cálculo de los factores de forma mediante hemicubo resultaba de
un considerable tiempo de cálculo. Debido a lo anterior, se decidió emplear otro algoritmo
43
que, con una mínima repercusión en la exactitud de la solución, disminuyera el tiempo de
cálculo asociado a los factores de forma, tal es el caso de Radiosidad Jerárquica.
La solución codificada a través de Radiosidad Jerárquica [10] es facilmente configurable para
dar un mayor o menor nivel de jerarquías y por ende definición. El uso de este algoritmo en
conjunto con un algoritmo genético se definió para que pueda ser configurable el nivel de
subdivisión. En las pruebas que hice encontré que se obtienen buenos resultados al emplear
un menor grado de subdivisión cuando se busca la solución al problema inverso y un mayor
grado de subdivisión una vez que se encuentra la solución que se presenta al usuario.
4.4.2 Representación del Problema.
Como se menciona anteriormente, la solución del problema inverso en su forma más general
es necesario determinar el número de luces, sus intensidades, posiciones y tipos de luz; la
codificación de estas variables en el genotipo de un AG se hizo de manera sencilla usando
un alfabeto binario {0,1 }.
La representación propuesta para cada individuo está asociada con el número de luces
codificadas; en general, cada luz está representada por el valor de su radiosidad ( r, g, b ), su
posición en el espacio ( x, y, z ) así como el tipo de luz ( spot o área ) ( ver figura 10 ). El
número de luces en el genotipo es variable en la generación inicial cuando se busca el número
que mejor aproxime una escena.
Cada uno de los genes del cromosoma representan valores enteros, especificados a través de
secuencias de 1 's y O's. El rango de valores para radiosidad es de O a 255 por lo que se usan
8 posiciones para cada una de las variables; de manera similar se hace para las coordenadas,
mientras que para el tipo de luz basta con una posición para quedar especificada.
El algoritmo permite definir rangos y precisiones válidos para cada una de las variables
fijando intervalos específicos [Lmin, Lmax], de esta manera las posiciones de las luces pueden
limitarse a sólo ciertas zonas de la escena.
44
j=# de luces
J x i Y i z i r i g i b i Tipo de luz I
~I 1 ~I 11111 I~
I l
1 0
1 0
1
l / 0
/ l / 0
/ l
I
Color Spot ó Area
Posición
Fig. 10: Genotipo.
4.4.3 Operadores Genéticos.
El AG propuesto usa los tres operadores genéticos: selección, cruzamiento y mutación. El o
perador de selección que se implantó usa la técnica de la ruleta descrita en la sección 3.3.2. El
uso de este operador generaba discontinudades en la obtención del mejor individuo ( menor
error ) , por lo que se decidió modificar el operador tomando el mejor individuo de la ge
neración y pasarlo intacto a la siguiente. Esta modificación disminuyó las discontinuidades
generadas por la obtención del mejor individuo y contribuyendo a una mejor convergencia así
como un disminución en las discontinuidades del valor promedio de la población. El capítulo
6 muestra estos efectos.
El operador de cruzamiento usado es estándar, pues toma un par de individuos seleccionados
en la generación actual para producir los nuevos individuos. Se utiliza un solo punto de cruce
entre los individuos que se combinan, el cual puede estar a lo largo de la longitud del gen
cuando son de igual longitud ( mismo número de luces), o bien, a lo largo de la longitud del
cromosoma con la menor longitud, como se puede observar en la figura 11.
Finalmente, se ocupa el operador de mutación para modificar cualquier parámetro del gen a
la vez que se está creando el individuo en la nueva población, cabe mencionar aquí que este
operador no incrementa el tamaño del genotipo durante los cálculos, unicamente cambia el
45
Punto de Cruce Descendientes
! Padre 1 O 1 O O Hijo 1 11 O O O I
... Padre2 1 0 0 0 1 O O 1 Hijo2 B 11 oo 11
Fig. 11: Cruzamiento de individuos con diferente longitud.
valor del gen en una posición a lo largo del genotipo.
4.4.4 Función Objetivo.
La medida de la aptitud de cada individuo en la población busca minimizar la diferencia entre
la escena deseada y la aproximada. La aptitud se mide por la distancia entre las radiosidades
de cada parche de las dos escenas. Una distancia pequeña genera una mayor aptitud.
Para medir la distancia entre las dos escenas se calculó la magnitud del error a través de
RMS [4], el cual está dado por
donde:
Wi es el peso asignado a cada punto muestra, y en este caso, asociado
con el área del parche.
(22)
Otra manera de medir el error es el uso de la función de señal-ruido ( SNR ) en la cual el
46
objetivo es maximizar la señal, lo cual es más significativo como medida pues se considera la
distancia entre el mayor y menor valor. La función se calcula mediante la siguiente ecuación,
donde:
( dr(S)
2 )
SNR = 10 lag d(S, S')/n
representa el rango dinámico de la señal, es decir, la diferencia
entre el mayor y menor valor de radiosidad en este caso.
d(S, S') es la distancia entre las escenas.
(23)
Ambas funciones se codificaron para efectos de comparación experimental, sin embargo, la
métrica base fue RMS. Los resultados de ambas métricas se muestran en secciones posteriores.
47
5 IMPLANTACIÓN DE LA SOLUCIÓN.
Este capítulo explica la implantación de la solución al problema inverso de iluminación me
diante algoritmos genéticos [8] y gradiente descendente, evaluando funciones de iluminación
a través de radiosidad jerárquica [10]. Así mismo, se explica la manera en que se pueden
utilizar los programas para probar otros problemas, experimentar con diversos parámetros
y visualizar las aproximaciones así como las distancias a la solución real.
La implantación contiene tres módulos principales:
1. El visor de escenas.
2. La aproximación empleando algoritmos genéticos.
3. La aproximación con gradiente descendente.
La descripción y uso de cada módulo se encuentra en las siguientes secciones. La descripción
de archivos empleados, así como ejemplos de ellos, están contenidos en los anexos. Esta
implantación posee un módulo adicional que permite ver gráficamente el comportamiento
del error promedio, error mínimo y señal/ruido que el sistema genera a medida que avanza
hacia la solución.
Los programas fueron codificados en lenguaje C de UNIX para equipos RS6000 modelo
41 T a 66 MHz PowerPC, con 32 MBytes en RAM, y sistema operativo AIX 3.2.5. En su
parte gráfica se emplearon interfaces gráficas con Xll, OpenGL 9 [17] y GLUT 10 [13]. Por lo
anterior, para ejecutar adecuadamente estos programas, se recomienda el uso de un equipo
RS6000 con los paquetes y sistemas operativos mencionados.
9 OpenGL es un conjunto de utilerias gráficas que auxilian en el desarrollo de aplicaciones gráficas.
10 GLUT es un conjunto de herramientas que permiten generar ventanas, menus de cascada y operar dispositivos como el ratón en base a eventos.
48
5.1 SISTEMA DE VISUALIZACIÓN EN 30.
La solución integrada que se ofrece en esta tesis lleva al diseño de un sistema de visualización
en tres dimensiones, el cual permite ver una escena además de contar con algunas otras
características, entre las que podemos citar:
• Permite pintar las superficies de los objetos en una escena definiendo un efecto de iluminación deseado, utilizando un "pincel de luz".
• Cálculo de las aproximaciones mediante algoritmo genético y gradiente descendente.
• Cambio de color del "pincel de luz".
• Guarda escenas pintadas en archivo.
• Tiene movimientos de Rotación respecto a los ejes cartesianos.
• Tiene movimientos de traslación respecto a X, Y y Z.
• Guarda la posición inicial de la escena original ( esto resulta útil cuando se hacen muchos movimientos en el espacio de 3D ) .
• Dibujo de los ejes coordenados para facilitar la orientación.
• Visualización de la escena en forma sólida o alambrada.
• Opción de aplicar u omitir "Sombreado de Gouraud".
Para operar correctamente, el visor requiere que los archivos necesarios ( descritos en el Anexo
A ) estén en el lugar donde se ejecuta el sistema, así como los programas de aproximación
por algoritmo genético y gradiente descendente.
El uso de este sistema de visualización resulta muy sencillo una vez que se tiene una escena
lista para efectuar movimientos sobre ella. Al ejecutarse el visor aparece una ventana como
la mostrada en la lámina 1.
Las escenas que lee el visor están formadas por polígonos de cuatro vértices. Cada polígono
definido para la escena principal se considera como un "parche". Los parches pueden ser sub
divididos en más piezas a las que se les denomina "elementos". La escena original se guarda
en archivos con terminación "polígonos" y "vértices", mientras que la escena formada por
49
elementos y usada para definir un resultado deseado se almacena en los archivos "elementos"
y "vertelem" .
Cada vez que se elige una escena para leerse con el visor, este la mostrará con o sin algunas
características adicionales según se haya especificado mediante el menú de opciones. El uso y
efectos producidos al emplear las opciones principales del menú se describen en las secciones
siguientes. Para consultar la descripción completa de las opciones refierase al anexo C de
este documento.
5.1.1 Pintando una escena.
El sistema de visualización en 30 permite pintar una escena descrita primero encendiendo
el pincel de luz ( usando el ratón ) al eligir la quinta opción del menú principal. Hecho lo
anterior, se puede modificar el color del pincel de luz usando la 3ra opción del menú, al
elegirla aparecerá un submenú en el que se sugieren algunos colores por omisión: blanco,
gris y gris claro; sin embargo, existe la posibilidad de especificar un color determinado con la
última opción del submenú. Para especificar un color determinado es necesario proporcionar
el color en términos de sus valores RGB, cada uno de los cuales es un número entero en el
rango entre O y 255.
U na vez que se ha elegido el color con el que se desea pintar la escena y se ha encendido el
pincel de luz, ya se puede pintar sobre ella. Para pintar en algún lugar, es necesario mover
el ratón hacia el área en cuestión y presionar el botón derecho siempre que se desee pintar
un elemento de la escena. De esta manera, se pueden ir pintando los elementos de la escena
con los colores que mejor agraden o logren el efecto que desee el usuario.
La escena puede tener superficies no visibles en una posición por lo que podría pensarse
que no se pueden pintar. El procedimiento que se puede seguir para pintar en este tipo de
superficies es utilizar el concepto de "3D Painting", mediante las funciones de movimiento
( rotación y traslación ) que el sistema de visualización ofrece.
Al terminar de pintar una escena, ésta puede quedar como la mostrada en la lámina 2. La
50
escena pintada puede guardarse en archivos para que se considere como el resultado deseado
al buscar la configuración de luces que mejor la aproximen.
5.1.2 Visualización sólida o alambrada.
Una característica útil de este sistema es su capacidad para intercambiar de manera inmedia
ta algunas formas de visualizar la escena, tal es el caso de la visualización en forma sólida,
en el cual se considera a todos los objetos como sólidos. El caso contrario que se puede
emplear es la forma alambrada por lo que al elegirla se muestra en la escena la totalidad de
los parches formados simplemente por líneas que unen a sus vértices como se puede apreciar
en la lámina 3.
5.1.3 Suavización de la escena.
Los parches que forman una escena tienen un color en términos de RGB; de dibujar cada
parche con su color, la escena puede verse como formada por diversos cuadros, cada uno con
un color propio ( ver lámina 4 ). Para que lo anterior no suceda y se aprecie mejor, se usó
el método de sombreado de Gouraud [6] en el que en lugar de dibujar el color del parche se
dibuja el color de cada vértice. El cálculo del color de cada vértice se obtiene de la siguiente
manera:
l. Cada vértice se analiza para ver en qué elementos de un mismo parche participa.
2. Se promedia el color del vértice con el color de los elementos en los que es utilizado.
3. Se asigna al color del vértice el promedio calculado.
4. Se dibuja cada vértice con el color promediado, causando que OpenGL genere el "sombreado de Gouraud".
51
Por omisión el sistema muestra las escenas aplicando "sombreado de Gouraud" pero puede
intercambiarse con la opción ocho para ver la escena dibujada con el color de cada elemento.
5.1.4 Cálculo de aproximaciones.
Al pensar en un sistema integrado, el visor ofrece como alternativa la llamada a los sistemas
de aproximación empleando gradiente descendente y algoritmo genético sin salir del mismo.
Una vez que se ha definido una escena deseada, la iluminación requerida puede ser aproxi
mada usando la opción "Aproximar via" con la que aparece un submenú que permite elegir
el método por el cual se desee hacer la aproximación.
Al elegir un método de aproximación se pide el nombre de la escena donde se encuentran los
elementos y vértices que la forman. El archivo de elementos cuenta con la información del
parche y objeto al cual pertenece, su área, vector normal, radiosidad, así como su propiedad
de reflectancia.
Una vez que se llama al método de aproximación, éste trabaja hasta encontrar la aproximada
más cercana. Cuando se encuentra la solución es necesario emplear la opción "Cargar" y
visualizar la aproximación calculada al igual que su distancia de la escena deseada.
5.2 SOLUCIÓN AL PROBLEMA INVERSO DE ILUMINACIÓN.
La solución propuesta en esta tesis involucra, como ya se ha mencionado, el método de
radiosidad jerárquica para solución de funciones de iluminación, así como mecanismos de
optimización local y global como lo son gradiente descendente y algoritmos genéticos respec
tivamente. En esta sección se presentan las características de implantación de cada uno de
los métodos y referencias para su uso.
52
5.2.1 Alcances de la solución.
La solución propuesta para el problema inverso de iluminación consideró algunos casos
específicos, los cuales son resueltos por los métodos implantados. Los casos que se pueden
solucionar son los siguientes:
l. Nivel de luz para un número fijo de luces en posiciones fijas.
2. Nivel de luz y posición para un número fijo de luces.
3. Nivel de luz para un número variable de luces en posiciones fijas.
4. Nivel de luz, posición y cantidad de luces.
5. Costo asociado.
En el último caso, se trata de la minimización de un costo, el cual puede representar dinero,
watts o calor asociados a la configuración de iluminación que se obtenga.
Cada uno de los casos anteriores se especifican en el archivo "genetica" ( su descripción
completa puede consultarse en el anexo A ) por lo que es necesario editar este archivo para
especificar el caso y características del problema que se desee solucionar para la escena
propuesta.
Esta solución utiliza tipos de luces puntuales y de área. El nivel de luz se discretizó a ocho
posibles fijados internamente, para el rango de O a 255, con lo que no se pueden generar
luces con niveles fraccionarios, es decir, no se permiten luces de 75.5878 watts, por ejemplo.
No existe límite en el número de luces, sin embargo, es bueno no excederse de siete luces por
ejemplo, debido a que el nivel de subdivisión del método en escenas complejas puede crecer
mucho y acabarse la memoria.
5.2.2 Radiosidad Jerárquica.
El algoritmo de radiosidad jerárquica recibe la configuración propuesta y evalúa la función
de iluminación. La escena deseada se lee de los archivos que anteriormente se citaron; de
53
ellos se toma la información para generar el árbol jerárquico que se desea aproximar. El
árbol jerárquico se compone en sus niveles superiores por los parches de la escena original.
Conforme se hacen subdivisiones sobre los parches, de acuerdo con un límite de área, cada
parche se subdivide en cuatro elementos obteniendo nodos de un "quadtree". La subdivisión
se hace tantas veces como lo permita el límite de área definido por el usuario.
El método de radiosidad emplea el árbol original para iniciar los cálculos, con esto, comienza
a definir los pares de elementos que se podrán ligar o bien que no lo podran hacer de acuerdo
a una medida de la visibilidad entre ambos.
La visibilidad entre un par de elementos se calculó disparando cinco rayos entre los dos
elementos en análisis. Los rayos se definen por la unión de combinaciones de los cuatro
vértices y el centro de cada elemento con los correspondientes del otro. Así, el cálculo de
la visibilidad se determina por el porcentaje de rayos que fueron ocultados por algún otro
elemento en la escena. Este proceso se hace de la siguiente manera:
l. Dos elementos son completamente ocultos si el ángulo entre sus vectores normales es mayor a 90 grados, en cuyo caso no se analizan más.
2. En caso de no cumplir el punto anterior, tenemos que los elementos puede ser:
(a) Totalmente visibles si no existe un elemento en la escena que los tape.
(b) Parcialmente visibles si existe uno o más elementos que oculten a un porcentaje del total de los rayos disparados entre los elementos.
(c) Completamente visibles si uno o más elementos de la escena ocultan la totalidad de los rayos que se disparan entre los elementos analizados.
El resultado de la fase de visibilidad es un valor Ve que determina el porcentaje de visibilidad
entre los dos elementos. Así, dos elementos totalmente visibles tienen un valor de visibilidad
Ve = 1, mientras que de ser completamente invisibles tienen un valor de Ve = O y en otro
caso cualquier valor entre O y 1 indicará su visibilidad parcial.
El cálculo de visibilidad se hizo entre cada par de elementos, lo que conlleva un mayor tiempo.
Para minimizar este tiempo se puede usar un árbol BSP ( Binary Space Partition ) en el
que se crea un árbol binario para ordenar los elementos y disminuir las comparaciones entre
elementos. Esta implantación no la llevé a cabo por falta de tiempo.
54
A la par del cálculo de visibilidad entre los elementos, se hace una liga entre ellos siempre y
cuando cumplan las restricciones del método descritas en la sección 2.4.4. El factor de forma
entre los dos parches se calcula por un estimado analítico y un factor de visibilidad, es decir,
(24)
siendo Fe el estimado del factor de forma calculado como la suma alrededor del perímetro
de un polígono. Este factor de forma analítico es usado por Tampieri [25] para calcular
la contribución de radiosidad de un parche S "fuente" a un punto Pr sobre la superficie
"receptora". El estimado se calcula como:
donde:
1 n = - L f3i cos ªi
21r i=l
f3i es el ángulo entre el vector normal en Pr y el vector entre un par
de vertices
ai es el ángulo entre un par de vectores a los vertices i e i + 1.
(25)
La subdivisión de los parches se hace empleando un área límite. Hay dos opciones: una al
buscar una solución aproximada y otra más detallada que se utilizará para la presentación
final al usuario. De esta forma al operar el método no se invierte tanto tiempo en la etapa
de aproximación. Después de que se calculan las interacciones entre los elementos, estas son
utilizadas por el método para el intercambio de energía entre los elementos. La energia es
disparada de los elementos que forman una luz o bien de algún otro que previamente recibió
una contribución de parte de otro. El proceso de intercambio continua hasta que se alcanza
un nivel en el que los parches llevan una energía que no cambia de manera significativa con
un paso anterior.
Una vez que converge el método debido a que no existe más intercambio de energía, se calcula
el error entre la escena deseada y la aproximada empleando RMS. Para esto, se accesa el
árbol y se calcula la diferencia entre la radiosidad de los elementos de escena deseada y la
radiosidad calculada para los elementos de la aproximación. Los parches con un área mayor
55
tienen una mayor contribución sobre la diferencia de energía que los elementos de menor
área. RMS se calcula como:
(26)
De igual forma, se calcula el valor de señal/ruido siendo otra alternativa de medición. En
este caso, se determina el elemento con la radiosidadd mayor y menor con lo que se calcula
el rango dinámico, mientras que la distancia es el error que se calcula mediante RMS. Estos
datos permiten calcular el valor de SNR como se indica en la ecuación:
( dr(S) 2
)
SN R = 10 lag d(S, S')/n (27)
El error calculado representa la aptitud del individuo para el caso del algoritmo genético y
la evaluación para el caso de gradiente descendente.
5.2.3 Algoritmo Genético.
El módulo que se encarga de buscar una solución al problema inverso de iluminación, usando
un algoritmo genético y evaluando la iluminación a través de radiosidad jerárquica se pone
en funcionamiento de dos maneras: usando la opción que tiene el menú del sistema de
visualización, o bién, desde el shell de UNIX tecleando "garad" y presionando la tecla Enter.
Al llamarse al programa "garad" pide el nombre de la escena, una vez proporcionado es usado
para abrir cada uno de los archivos asociados con la escena y la evaluación del algoritmo
genético. Con este nombre se generan las salidas de soluciones aproximadas y "mundos
distantes" 11 , así como los archivos de mejores individuos, el promedio de la población y los
valores de señal/ruido que el AG encuentra en cada generación.
11 La diferencia entre la escena deseada y la aproximada. Un error máximo se ve blanco o iluminado, mientras que un error cero se ve negro.
Escenas Algoribno Genético
Configuración Genética
Configuración V"ISUalización
Fig. 12: Estructura del programa.
56
De manera muy general la forma en que opera el módulo garad se muestra en la figura 12,
como se puede observar, este módulo llama al algoritmo genético el cual va generando los
individuos para cada generación. Cada individuo representa la configuración propuesta de
pendiendo del caso que se desee solucionar.
Los operadores utilizados para el algoritmo son los estandar como se describieron en el
capítulo anterior. La población inicial es generada aleatoriamente dentro de los rangos válidos
que fije el usuario. Debido a que el cruzamiento de dos padres puede generar un hijo no apto
para las áreas determinadas como válidas, se optó por descartar a los hijos que presentaran
esta característica castigando el valor de su aptitud con un valor de una unidad y así en
evaluaciones posteriores no son seleccionados como padres.
El valor de la aptitud de cada individuo es el valor de RMS que regresa radiosidad jerárquica.
El método busca el individuo que genere el menor error. Este proceso termina después de un
número de generaciones propuesto por el usuario o bien cuando el error del mejor individuo
sea menor a un epsilon, normalmente igual a 0.0010 aunque puede configurarse.
Una vez encontrado el mejor individuo se vuelve a emplear radiosidad jerárquica para obtener
la solución que se presentará al usuario y la distancia entre los elementos de la escena deseada
Solución
GARAD
Algoritmo Genético
t Radiosidad Jerárquica
Error y Señal/Ruido
Fig. 13: Archivos de entrada y salida.
57
y la aproximada. Estas soluciones se almacenan en los archivos de polígonos y vértices con
terminación ".apxga".
Finalmente el algoritmo genético escribe en archivos los valores de cada generación que re
sultaron mejores, el promedio de cada población y el valor de señal/ruido. Estos archivos
son nombrados "Mejores.apxga", "Promedios.apxga" y "SNR.apxga", pueden ser accesados
a través de otro módulo adicional que los grafica. Las entradas y salidas del proceso pueden
verse en la figura 13.
El pseudocódigo del módulo se muestra a continuación:
1. Leer la escena deseada.
2. Leer parámetros de visualización.
3. Leer parámetros del algoritmo genético.
4. Generar Población P(O) en forma aleatoria
5. Para todo individuo Pi E P evaluar usando radiosidad jerárquica y generar la métrica de error a través de RMS y SNR.
6. Mientras ( no converge ) hacer
58
(a) Seleccionar el mejor individuo Pk E P y pasarlo intacto a la siguiente generación P(i + 1).
(b) Combinar los individuos Pi, p1 E P seleccionados vía ruleta aplicando los operadores de cruzamiento y mutación para generar la nueva población P'.
(c) Evaluar los nuevos individuos Pi E P' como antes
(d) Hacer P = P'
7. Generar la solución que se presentará al usuario.
5.2.4 Gradiente Descendente.
El método de gradiente descendente se implantó de la siguiente manera,
1. Se define un punto inicial aleatoriamente en un área determinada.
2. Al punto se asocian 26 vecinos a su alrededor tomando en cuenta movimientos unitarios en el espacio de 3D, niveles de luz y tipos de luces.
3. Para cada vecino se hace lo siguiente:
(a) Se checa que sea válido en las áreas definidas. en el archivo nombre_escena.genetica
(b) Se evalúa como solución para radiosidad jerárquica.
4. Después de explorar los vecinos, se determina el menor de ellos, el cual define la dirección de descenso.
5. De existir un vecino menor se usa como punto actual y se repite el proceso desde el paso 2.
6. En caso de que no exista un vecino menor al actual el algoritmo termina.
Como se puede ver, gradiente es un método muy sencillo de implantar. Los resultados
obtenidos en las pruebas diseñadas para evaluación se muestran en el siguiente capítulo.
0.6 ¡ /
0.5
'/ x/ 0.4 t-----~-------------------
0.3 /v 'x
/
O 2 +--------/-/ __ _
. )(,
0.1 /x,
+-----------+-' /7'~' / .. /X X x· x,/xX///,''-'YxX./
º L-~...-~ ........ ~~ ........ """' __ ._.. __ _ o 4 8 12 16 20 24 28 32 36 40 44 48 52 56 50
Promedio
• Mejores
Fig. 14: Mejores indiviuos y Promedio para población de 150 y 60 generaciones.
59
5.3 GRAFICACIÓN DEL ERROR Y SNR DE APROXIMA-
CIONES.
Una vez que se ha encontrado una solución a través del módulo anterior, se generan los
archivos con los valores que describen el comportamiento del algoritmo genético.
Los archivos genenerados pueden graficarse utilizando este pequeño módulo llamado
"gráficas". Para ejecutarlo es necesario llamarlo desde el shell de unix por su nombre junto
con la terminación de los archivos como parámetro; por esto se requiere tener los tres archivos
anteriormente descritos, es decir, "Mejores.apx**" 12 , "Promedios.apx**" y "SNR.apx**".
Tales archivos pueden ser renombrados del punto en adelante pero los tres deberán poseer
la misma terminación, de esta manera es posible mantener registros de pruebas en forma
histórica.
Al ejecutar "gráficas" seguido de la terminación de los archivos el programa lee los datos
contenidos en los archivos y procede a graficar el error asociado a cada generación. La línea
roja corresponde al menor error ( mejores individuos ), la línea blanca representa el error
12 ** puede ser ga ( algoritmo genético ), gd ( gradiente descendente ) o rs ( recocido simulado ).
60
promedio y la línea verde el valor de señal/ruido para cada generación. Para terminar el
programa simplemente se cierra la ventana. En la figura 14 podemos ver un ejemplo de
como se vería una gráfica.
Para la generación de las gráficas del capítulo de resultados se utilizaron los mismos archivos
que emplea este módulo, sin embargo, estos fueron modificados para usarse en el paquete
estadístico SAS versión 6.11 para la toma de decisiones.
61
6 RESULTADOS EXPERIMENTALES.
Este capítulo presenta los resultados experimentales obtenidos al aplicar los métodos de
gradiente descendente y algoritmo genético a una evaluación de funciones de iluminación,
a través de radiosidad jerárquica para escenas propuestas. Las pruebas realizadas con estos
métodos se ejecutaron en equipos IBM RS6000 41 T con las siguientes características:
• Procesador PowerPC 601 a 66MHz.
• 32 MBytes en RAM.
• Rendimiento en MFiops de
Linpack DP 20.1
Linpack SP 24.9
- Linpack TPP 41.9
• Dos usuarios conectados.
6.1 ESCENAS PROPUESTAS.
En esta tesis, se definieron tres escenas que fueran representativas para usarlas en el problema
inverso de iluminación. La primer escena propuesta se trata de un cuarto como el conocido
"room" del Cornell Box, por lo que llamaremos a esta escena "cuarto" para referencias
posteriores. La escena "cuarto" se puede apreciar en la lámina 5 en la cual existen dos cubos
en su parte central y dos paredes de color, la izquierda roja y la derecha azul.
Lámina 5
Tabla 2: Tiempo de evaluación de escenas.
Escena Tiempo
cuarto 24 seg.
armario 6 seg.
mesa 12 seg.
Area Límite
10,000 mm
10,000 mm
10,000 mm
62
Otra escena denominada "armario" es un caso extremo en el que un cuarto posee una pared
a la mitad, como si se tratara de un armario dentro del cuarto ( ver lámina 6 ). Finalmente,
tenemos una escena que representa un cuarto cuya iluminación ha sido "pintada" por el
usuario. Esta última es denominada "mesa" y tiene una pequeña mesa en el fondo del cuarto
( ver lámina 2 ) .
Una variante de las escenas anteriores fue el uso de costos no uniformes asociados a la
configuración de iluminación, esto puede representar watts, por ejemplo. Se fijaron ocho
niveles de luz a manera de discretizar la luz. En niveles de luz medio se asoció un costo
mayor, mientras que los niveles bajos tenian un costo menor pero no tanto como el que se
le dió a los niveles superiores.
Para cada una de las escenas anteriores se fijó una luz en una posición determinada, se
evaluaron las funciones de iluminación a través de radiosidad jerárquica [10] y se obtuvo
una escena deseada ya sin la luz. Las escenas pueden poseer áreas válidas por lo que la luz
sólo puede localizarse en ellas, esto permite definir los límites válidos en los que se pueden
acomodar las luces para que los métodos no las coloquen demasiado abajo o incluso dentro de
muros. El detalle de las estructuras para los archivos que forma la escena puede consultarse
en los Anexos A y B.
Las escenas están formadas por entre 16 y 25 parches considerando un nivel de subdivisión
dado por un área límite de 10,000 mm y 5,000 mm. Este nivel se seleccionó de tal manera que
no incrementara el tiempo de ejecución para la evaluación de radiosidad, aunque se puede
emplear un nivel menor para obtener la solución que se presenta al usuario con una mayor
calidad. El número de elementos después de subdividir con los límites de área citados fue de
63
106. El tiempo aproximado de ejecución de radiosidad jerárquica en cada una de las escenas
anteriores se muestra en la tabla 2.
La métrica de error que se usó como base fue RMS , sin embargo también se evaluó SNR;
ambas métricas se describen en el capítulo 4 para calcular la distancia a la solución deseada.
6.2 EXPERIMENTOS CON LOS MÉTODOS DE OPTI
MIZACIÓN.
El comportamiento de los métodos gradiente descendente y algoritmo genético se analizó
poniéndolos a prueba 20 veces. Los datos derivados de estas pruebas se integraron en diagra
mas que muestran el comportamiento del error ( calculado por RMS ) a medida que avanza
el método en un número de evaluaciones. Por evaluación, se entiende como un paso que hace
el método de optimización en su operación, es decir, gradiente descendente efectua un paso
cada vez que analiza 26 vecinos del punto actual, mientras que el algoritmo genético hace
un paso por cada cálculo de una generación.
Los diagramas fueron obtenidos con el paquete SAS versión 6.11 y muestran en una cajita,
por su alto la desviación estándar del promedio del error en cada evaluación, mientras que
por su ancho el número de pruebas que efecturaron esta evaluación. La cruz indica la media
del error en la evaluación actual. Una raya vertical muestra los valores extremo, es decir, el
mayor y menor error que se obtuvo en esa evaluación con 20 veces que se probó el método.
A continuación se muestran y analizan los diagramas para cada método.
6.2.1 Gradiente Descendente.
Como se mencionó en capítulos anteriores, la implantación de gradiente descendente calcula
26 vecinos cada vez que se fija un punto. La gráfica del error obtenido al aplicar este método
E r
0.4
0.3
r 0.2 o r
0.1
o
64
+ +
B 8
o 1 2 3 4 5 6
Evaluaciones
Fig. 15: Error obtenido por Gradiente Descendente en 20 pruebas.
20 veces se muestra en la figura 15. En esta figura se observa el comportamiento de gradiente
al aplicarse en una escena. Dependiendo del punto inicial, en relativamente pocas evalua
ciones se encuentra una solución adecuada. El tiempo que le tomó encontrar una solución
cercana a la deseada por el usuario fue aproximadamente 52 minutos, considerando que se
hacen las seis evaluaciones. En la gráfica podemos ver que no todas las pruebas tuvieron que
hacer las seis evaluaciones.
En la figura 16 se observa los resultados al usar SNR como métrica. El objetivo en este caso
es maximizar el valor de SNR.
6.2.2 Algoritmo Genético.
Las pruebas hechas con el algoritmo genético consideraron poblaciones de 10, 30 y 60 in
dividuos. En los tres casos, el número de evaluaciones se fijó hasta un máximo de 60, así
mismo, para las tres poblaciones la probabilidad de mutación fue de 0.01 mientras que la
65
15
10
+ 5
s N o R
-5
-10
-15
o 1 2 3 4 5 6
Evaluaciones
Fig. 16: Evaluación de SNR en Gradiente Descendente.
probabilidad de cruzamiento se fijó en un valor de 0.60.
En cada escena el algoritmo genético inició con una población de soluciones válidas generada
aleatoriamente. Conforme el algoritmo avanza se pueden generar nuevos individuos quienes
pueden ser aptos o no. Los individuos no aptos como ya se mencionó son castigados en su
aptitud para ser rechazados en evaluaciones posteriores.
La figura 17 muestra las pruebas efectuadas con una población de 10 individuos. El resultado
muestra que se acerca hacia una solución, sin embargo, en promedio la población no presenta
un comportamiento similar después de 60 evaluaciones, lo que hace que este muy disperso el
error y puedan obtenerse soluciones que en promedio no resulten visualmente correctas. En
promedio podemos ver que entre la evaluación 20 y 25 ya podemos tener una solución que
puede considerarse aceptable.
En la gráfica de la figura 18 puede observarse un cambio más constante en el comportamiento
del error promedio conforme se hacen más evaluaciones. Podemos ver que aproximadamente
a partir de la evaluación número 15, la población en 20 pruebas ya adquiere un compor
tamiento más uniforme y se puede terminar la ejecución del AG con un error aceptable
66
Poblacion 10 Evaluaciones 60
O. 4 -
~ 0.3-®~ r 0.2 - ~
~ 0.1 - r~8~~~~~~i~~e~~~~$~~~é~~~~~~~~~~~~~~e~ee~89fl~~ o -~.---,~-.---,~--r--,~---.-,~~~.~~~.~~~,~~~,~~-r--~-----r,~~~.~~~.~~~,,....,
o 5 1 O 15 2 O 2 5 30 35 40 45 50 55 60
Evaluaciones
Fig. 17: Error obtenido para un AG en 60 evaluaciones con una población = 10.
( aproximadamente de 0.09 ).
El comportamiento usando una población de 60 individuos se muestra en la figura 19. En este
caso, resulta evidente la manera en que opera el algoritmo genético desechando individuos que
llevan a soluciones alejadas de la deseada y mejorando la aptitud promedio de la población.
Se puede observar en la gráfica que aproximadamente entre la evaluación 15 y 20 ya se
obtiene una solución cercana con un error de alrededor de 0.10.
Otras figuras como 20 y 21 muestran el comportamiento que tiene la métrica SNR al usarse
en el algoritmo genético y seleccionar el individuo con el mayor valor de SNR. Los valores
obtenidos son el resultado de 20 pruebas. La figura 20 está asociada con una población de
30 individuos mientras que la figura 21 para una población de 60 individuos.
Otras figuras obtenidas, muestran el comportamiento al evaluar SNR buscando maximizar
su valor ( ver figuras 20 , 21 y 16 ). El comportamiento de esta métrica muestra un
crecimiento a medida que el algoritmo avanza pero también se observa una gran dispersión
de los valores a través de las evaluaciones en las 20 pruebas que se hicieron.
Debido al análisis de los datos anteriores decidí usar un algoritmo genético con una población
67
Poblacion = 30 Evaluaciones= 60
O. 30 -
1 1 1 1 o - ' , ' , ' ,5 4'0 45 50 55 60 1 1 1 o 15 2 o 2 5 30 3
O 5 .
Evaluaciones
Fig. 18: Error obtem o para u ·¿ n AG en 60 evaluaciones con una población = 30.
Poblacion = 60 Evaluaciones= 60
5
50 55 60 o.o 30 35 40 45 o 5 10 15 20 25
Evaluaciones
. AG en 60 evaluaciones con una población = 60. F. 19· Error obtemdo para un 1g. .
68
o 2 4 6 B 10 12 14 Evaluaciones 16 18 20
Fig. 20: Evaluación de SNR para el AG en 20 ac10n = 30. evaluacioness con pobl . ,
so,---~ Pobla · Evalu .cien= 60 aciones = 60
40
10
O 2 ----:--::-4 ~~-----.--------. 6 8 10 12 14 16 18 20 Evaluaciones 22 24 26 2 8 30
Fig. 21: Evaluación de SNR para el AG en 20 eval . uac10nes con pobl . , ac10n = 60.
69
Tabla 3: Tiempo y error de AG con diferentes poblaciones.
Tiempo (min.) Pob. = 10 Pob. = 30 Pob. = 60
8 0.21 0.27
17 0.13 0.22 0.27
26 0.09 0.14
35 0.09 0.13 0.23
44 0.08 0.12
52 0.08 0.10 0.18
70 0.08 0.10 0.14
87 0.08 0.09 0.11
173 0.07 0.09 0.09
media, es decir, una población de 30 individuos analizando hasta 20 evaluaciones de tal
manera que se asegurara una convergencia en casos normales así como en casos donde se
requiere más exploración. Respecto a las probabilidades se usó una probabilidad de mutación
P m = 0.01 y una probabilidad de cruzamiento Pe = 0.60. La tabla 3 muestra una comparación
del error que se obtiene en promedio, con poblaciones de 10, 30 y 60 individuos.
6.2.3 Comparación de Métodos.
Los tiempos de ejecución para gradiente descendente y algoritmo genético aplicado con los
tamaños de población descritos se muestran en la tabla 4. Estos tiempos fueron obtenidos
en promedio al ejecturase los algoritmos en los equipos indicados. Para efectos de hacer
comparables los métodos se puede considerar lo siguiente, gradiente en cada evaluación que
efectua, considera 26 cálculos de radiosidad, mientras que un algoritmo genético con una
población de 10 individuos, hace 10 cálculos de radiosidad, es decir aproximadamente dos
por cada una de gradiente. Para una población de 30 se hace 30 veces radiosidad, es decir,
70
Tabla 4: Tiempo y error de gradiente y algoritmo genético.
Tiempo (min.) Gradiente A.G. (pob=lü) A.G. (pob=30) A.G. (pob=60) 8 0.22 0.21 0.27
17 0.18 0.13 0.22 0.27 26 0.16 0.09 0.16 35 0.14 0.09 0.14 0.23 44 0.12 0.09 0.13 52 0.11 0.08 0.12 0.18 70 0.08 0.10 0.14 87 0.08 0.10 0.11
173 0.07 0.09 0.09
una correspondencia de casi uno a uno con gradiente. Ahora, si consideramos una población
de 60 individuos podemos decir por cada evaluación de algoritmo genético, gradiente efectua
dos. Comparando gradiente y un algoritmo genético con población de 10 individuos, aun
podemos ver que converge más rápido el algorimo genético, sin embargo para nuestras prue
bas experimentales con casos normales y casos con mínimos locales tomamos una población
de 30 individuos. Una población de 30 individuos hace aproximadamente una evaluación por
cada una que hace gradiente.
6.3 ANÁLISIS POR PRUEBA.
Las escenas descritas se utilizaron para efectuar las pruebas con los métodos de optimización.
Los resultados obtenidos para cada prueba se describen a continuación, además se muestran
ejemplos de las soluciones obtenidas para mostrar al usuario.
71
6.3.1 Escena "Cuarto".
La escena "cuarto" representa un caso normal en el que se tiene una área de un cuarto con
dos cubos en su interior. La escena original tenía la luz ubicada en la parte media de la pared
superior.
El tipo de problema que se definió para esta prueba fue el caso 2, es decir, los métodos
deben encontrar el nivel de luz y posición para un número determinado de luces.
Gradiente descendente al probarse en esta escena pudo encontrar una solución cercana dado
que no le resultó dificil avanzar en incrementos unitarios hacia una solución cercana. Una
solución encontrada por el método puede verse en la lámina 7 así como su escena "mundos
distantes" 13 en la lámina 8. El número de evaluaciones que en promedio le tomó al gradiente
encontrar una solución fue de 4, siendo una escena sencilla en la que no había demasiados
movimientos hacia la escena deseada. Este método localizó una luz por debajo de la posición
original. El tiempo empleado por gradiente descendente para esta solución fue de 42 minutos.
El comportamiento del algoritmo se puede ver en la figura 22.
Las pruebas usando el algoritmo genético obtuvieron escenas cercanas a la deseada como se
puede ver en la lámina 9, mientras que en la lámina 10, la diferencia entre los valores de
radiosidad de los elementos de la escena deseada y la aproximada. AG encontró la solución
en la evaluación 16 tomando un tiempo de 192 minutos. La gráfica 23 muestra el compor
tamiento del error en este método. AG invierte más tiempo para encontrar una solución sin
embargo obtiene una mejor solución a la obtenida por gradiente.
6.3.2 Escena "armario".
Esta escena representa un caso del tipo barrera pues se trata de un cuarto en el que existe
una pared que lo divide en dos secciones. El muro que divide es de color café como si se
13 La diferencia entre la escena deseada y la aproximada. Un error máximo se ve blanco o iluminado, mientras que un error cero se ve negro.
72
0.35
0.15
0.10 L---------------2~3 ~4 -5~6
O. OS 1 luaciones o Eva
radien te . . , del Error para g Fig. 22: Evaluac10n
- 30 Poblacion:; 60 luaciones Eva
~~ 55 60 50 40 45 25 30 35
O
O 5 1 5 2 O · nes · 1 O Evaluacio
o 5
. , del Error para AG. Fig. 23: Evaluac1on
73
tratara de un muro de madera. La sección izquierda tiene una pared azul y nada en su
interior. La sección derecha tiene en su interior un pequeño cubo color amarillo y una de las
paredes de esta sección es color rojo. La escena se puede apreciar en las láminas del Anexo D.
Esta prueba se diseño considerando que el método debía encontrar el nivel de luz, posición
y tipo de la fuente luminosa.
Al probar gradiente descendente en esta escena se colocó un punto de inicio dentro del
área obscura del cuarto, es decir, en el área izquierda no iluminada y tapada por la pared.
Gradiente buscó la mejor configuración de nivel de luz y posición de luces que lograran el
efecto deseado, sin embargo, por su naturaleza de ser un método local, no pudo avanzar más
allá de la primera evaluación de vecinos dado que cada uno de ellos no otorgaba un valor
del error menor al del punto actual. De esta manera, el método se quedó en un punto en el
cual no pudo seguir explorando más posibilidades. La solución que encontró gradiente puede
verse en la lámina 11, así como la diferencia respecto a la original en la lámina 12. Se puede
observar en la lámina 12 lo alejado que resultó esta solución al aplicar gradiente; hay que
recordar que una buena aproximación genera una escena de "mundos distantes" obscura, y
en este caso, la sección derecha del cuarto aparece iluminada. Sólo se hizo una evaluación lo
que tomó aproximadamente 3 minutos. La figura 24 muestra el comportamiento del error
en esta escena.
El algoritmo genético usado en la escena "armario" buscó en todas las áreas fijadas por el
usuario encontrando un resultado cercano como puede verse en la lámina 13, así como su
distancia de la deseada en la lámina 14. Esta solución se hizo efectuando 60 evaluaciones,
aunque en la evaluación 18 la población ya tenía un comportamiento aceptable con un error
de 0.09. El tiempo invertido en total fue de 210 minutos y si consideramos hasta la evaluación
18 el tiempo sería de 63 minutos. El comportamiento se puede observar en la figura 25.
E r r 0.426 o r
0.30
0.25
O. 20 E r r O .15 o r
0.10
o.os
o
el~
o
<>
1
o Evaluaciones
Fig. 24: Evaluac10n gradiente . . , del Error para
Ji[!]
2 4 6 B 10 12 14
Evaluaciones
. , d 1 Error para AG. Fig. 25: Evaluac10n e
Poblacion Evaluaciones
16 18 20
74
30 20
Lámina 13
75
Tabla 5: Nivel de luz y costo no uniforme asociado.
Nivel de Luz Factor de Costo 32 0.88 64 0.90 96 0.95
128 0.98 160 1.00 191 0.95 223 0.90 255 0.80
6.3.3 Minimizando costos no uniformes: "Cuarto".
Una variante a la prueba "cuarto" se hizo fijando costos no uniformes para los niveles de
luz de tal manera que las luces con niveles medios se consideran "más caros". Considerando
8 niveles de luz, el costo se fijó en factores fraccionarios, así en un nivel medio ( 4) se puso
un valor unitario para que el valor del error no cambiara, mientras que en un nivel menor
(1) de luz se puso una fracción menor a la unidad, sin embargo, se fijo una fracción un poco
menor en el nivel superior (8) de la luz. Ver la tabla 5 y la gráfica 26
Al probar el método de gradiente con la escena incluyendo costos no uniformes, se encontró
que al iniciar con valores menores al nivel medio, tendió a niveles menores cercanos al 1, sin
explorar en niveles superiores. Un resultado obtenido con este método se puede observar en la
lámina 15, así como su escena "mundos distantes" en la lámina 16. El tiempo que se invirtió
en encontrar la solución fue de 1 hora y media. La figura 27 muestra el comportamiento de
gradiente en las evaluaciones al minimizar el costo de la configuración de iluminación.
El algoritmo genético al probarse en esta escena exploró en todos los niveles de luz por lo
que pudo encontrar una solución con nivel de luz mayor al nivel medio. El tiempo que le
tomó al algoritmo encontrar esta solución fue de 3 horas. El tiempo que invertió AG para
encontrar la solución es el doble que el que inviertió GD, sin embargo, AG obtiene un mejor
resultado con el menor costo. El resultado puede verse en la lámina 17 y su distancia de la
deseada en la lámina 18. La figura 28 muestra el avance del algoritmo en la prueba de costos
76
l. 00 0.99 0.98 0.97
F 0.96 a 0.95 e 0.94 t 0.93 o 0.92 r
0.91 d 0.90 e 0.89
e O. 88
o 0.87 s 0.86 t o.as o 0.84
0.83 O. 82 O. 81 0.80
0.00 100.00 200.00 300.00
Nivel de luz
Fig. 26: Factores de costos no uniformes para niveles de luz discretos.
0.35
O.JO
+ E r r O. 25 + o r
O. 20 --+--
--+--
O .15
o 1 2 3
Evaluaciones
Fig. 27: Evaluación del Error para gradiente en costos no uniformes.
Lámina 15
o 2 4 6 8 10 12
Evaluaciones
14
77
Poblacion 30 Evaluaciones 20
16 1 8 20
Fig. 28: Evaluación del Error para AG con costos no uniformes.
no uniformes, en ella se ve que el algoritmo avanza al ir buscando la minimización del error
y el costo asociado con la configuración en 20 evaluaciones como máximo.
6.3.4 Pintando Escenas: "Mesa".
El objetivo principal de esta tesis es el de permitir a un usuario diseñar la iluminación sobre
una escena. El uso del sistema de visualización en 3D facilita el proceso de "pintado" como
se explica en el capítulo anterior. Un caso de este tipo es la escena "mesa" que se muestra
en la lámina 2. La escena original poseía una luz en la esquina derecha del fondo del cuarto.
A esta escena se le pintó la esquina izquierda mas cercana al observador. Para esta escena
se fijo el problema inverso como del tipo 4, es decir, encontrar la mejor configuración de
número de luces, con posición, nivel y tipo de luz.
Al aplicar gradiente a esta escena se obtuvo una solución aceptable después de hacer 8
evaluaciones, tomando como base que por cada evaluación se efectuó 26 veces el cálculo
78
0.25
O. 20 D E r r 0.15 o + r
+
C:J O .10
E:J [:] 8=I
EJ 0.05
o 1 2 3 4 5 ó 7 8
Evaluaciones
Fig. 29: Evaluación del Error para gradiente en Mesa.
de radiosidad jerárquica. El tiempo que le tomó a gradiente encontrar esta solución fue
de 52 minutos. La lámina 19 muestra la solución que se presenta al usuario al usar este
método y en la lámina 20 puede verse la escena de "mundos distantes". La figura 29 se
observa el comportamiento de gradiente con un cambio en la evaluación número 5 debido a
la exploración del algoritmo con más luces.
Usando algoritmo genético con un límite de 30 evaluaciones se obtuvo una solución como se
muestra en la lámina 21. La solución que encontró el algoritmo resulta aceptable y con un
error mejor que el obtenido por gradiente como puede verse en la lámina 22. El tiempo que
invirtió el algoritmo genético fue de 120 minutos. La figura 30 muestra el comportamiento
del algoritmo al hacer 20 evaluaciones para minimizar el error.
o .14
0.12
E O .10 r r
o o. 08 r
0.06
0.04
o 2 4 6 8 10 12
luaciones Eva
14
AG en Mesa . . , del Error para . 30· Evaluac1on F1g. ·
79
= 30 Poblacion = 20 l uaciones Eva
16 18 20
80
7 CONCLUSIONES Y TRABAJO FUTURO.
Este capítulo presenta las conclusiones derivadas de esta tesis así como el trabajo que se
puede desarrollar a futuro.
7.1 CONCLUSIONES.
Las pruebas experimentales hechas con un algoritmo genético cuyos operadores son estándar,
en pruebas diseñadas para el problema inverso de iluminación, usando radiosidad jerárquica
como evaluación de las funciones de iluminación, permiten concluir lo siguiente:
l. Un algoritmo genético como método de optimización en el problema inverso de ilumi
nación, constituye una buena alternativa cuando se tienen cuartos u oficinas que se
caracterizan por tener una distribución separada por áreas de trabajo.
2. El uso de algoritmo genético cuando se tienen áreas abiertas, es decir, sin separaciones
y sin cubículos, resulta adecuado pero no recomendado aplicarlo pues es posible utilizar
métodos de optimización locales que posiblemente con un menor esfuerzo, encuentren
una solución aceptable.
3. En pruebas efectuadas para la minimización de costos no uniformes, el algoritmo
genético mostró sus características de ser un método global al explorar en una
población de puntos más que en un solo punto. El algoritmo genético logró explo
rar en niveles donde el costo era el menor para niveles de luz discretos.
81
4. Las soluciones con una población de 30 individuos y hasta 30 generaciones resultan
subjetivamente razonables ( errores de 0.08 ) con un tiempo de proceso de alrededor
de 1 hora.
5. Utilizar poblaciones mayores a 30 individuos permiten encontrar soluciones con una
mejoría no significativa visualmente. De manera que no vale la pena esperar el tiempo
que se invierte, aproximadamente 7 veces el caso anterior, para una población de 60 in
dividuos y hasta 60 evaluaciones. Con estas características es posible obtener soluciones
con errores de alrededor de 0.045.
6. En escenas con áreas restrictivas para el posicionamiento de las luces, el algoritmo
genético mostró ser un método más adecuado para encontrar soluciones más cercanas
que emplear un método local como lo es gradiente descendente.
7. Los algoritmos genéticos en escenas que usan "pincel de luz" para el problema inverso de
iluminación son métodos adecuados pues pueden explorar de manera global el problema
con o sin mínimos locales, encontrando soluciones aceptables.
7.2 TRABAJO FUTURO.
El resultado de esta tesis puede verse mejorado al considerar los siguientes puntos como
trabajo futuro:
1. El uso de SNR como métrica debe ser explorado un poco más para poderlo elegir como
métrica base pues tal vez sea una mejor medida de lo que el ojo percibe como error.
2. No tuve tiempo de hacer suficientes pruebas con el método de Recocido Simulado para
comparar su comportamiento respecto a algoritmo genético. Es necesario explorar con
este método para analizar su comportamiento en el problema inverso de iluminación.
82
3. El "pincel de luz" puede mejorarse para el sistema de visualización en 30 modificándolo
para pintar como si se tratara de una brocha que "pinta" sobre la superficies, más que
como una pluma que al presionar sobre un elemento le cambia su color.
4. El uso del "sombreado de Gouraud" tiene un problema al suavizar superfices que no
tienen una subdivisión suficiente y los oculta algún parche. En este caso, se pueden
generar fugas de luz por lo que es necesario hacer modificaciones al método de subdi
visión, que eviten este problema.
5. El sistema de visualización puede ser mejorado y extendido en su parte gráfica ofre
ciendo otro tipo de objetos que se puedan dibujar, así como una mejor interfaz para
la creación de escenas. De igual manera, la solución en sí puede ampliarse definiendo
más tipos de luces.
6. El empleo de radiosidad jerárquica mostró un buen desempeño, sin embargo, todavía
puede mejorarse más en la fase de visibilidad dado que es posible emplear árboles BSP
que generen un menor número de comparaciones y redunden en una minimización del
tiempo de proceso para la evaluación de radiosidad.
7. La implantación de radiosidad sólo consideró superfices lambertianas por lo que se
puede ampliar el método agregando superfices traslúcidas y brillosas, entre otras.
8. El algoritmo genético puede considerar el uso de un operador de mutación que permita
cambiar el número de luces en el genotipo a medida que evoluciona el método y observar
si esta diversidad mejora el rendimiento del algoritmo genético.
9. Un cambio importante que puede hacerse en el algoritmo genético es su implantación
paralela y ver como mejoran los tiempos y aproximación obtenidos en la solución al
problema inverso de iluminación.
ANEXO A
DOCUMENTACIÓN ENTRADA.
DE
83
ARCHIVOS DE
La información que utiliza este sistema para la solución del problema inverso de iluminación
en una escena, ha sido separada para su mejor comprensión en siete archivos. Estos archivos
definen los polígonos, vértices, luces, parámetros de visualización y parámetros de ejecución
de un Algoritmo Genético. A continuación se lista cada uno de ellos así como la descripción
de su forma de uso:
nombre_escena.poligonos: En este archivo se describen los polígonos en la escena.
nombre_escena.vertices: Este archivo contiene los vértices que forman los polígonos.
nombre_escena.luces: Aquí se establecen las luces en la escena en las que para el caso libre
marcan su límite y guía.
nombre_escena.elementos: Es el archivo donde se guardan los elementos que componen a
cada parche de la escena y que son utilizados para definir la escena deseada a través
del pincel de luz.
nombre_escena.vertelem: Este archivo contiene los vértices de los elementos que conforman
a cada parche.
nombre_escena. parametros: Este es el archivo donde se especifican los parámetros de visua
lización de la escena descrita en 3D.
nombre_escena.genetica: Define los límites y parámetros para realizar los cálculos en un
algoritmo genético.
El resultado de la ejecución es almacenado en dos pares de archivos, similares a los dos
primeros arriba descritos:
84
nombre_escena.poligonos.apx** 14 y nombre_escena.vertices.apx**: Describen los polígonos
y vértices que resultan de la aproximación del problema inverso de iluminación usando
garad.c.
nombre_escena.poligonos.err** y nombre_escena.vertices.err**: En estos archivos quedan re
gistrados los polígonos así como los vértices de la escena "mundos distantes" entre la
escena original y la aproximada.
A continuación se describen a detalle cada uno de los archivos anteriores.
85
• Archivo de polígonos y archivo de elementos.
Estos archivos, así como el resto, poseen cada uno de los valores separados por un
espacio en blanco. El tipo de polígonos y elementos empleados son rectángulos para
cada uno de los cuales se definen sus características asociadas. Sus componentes, para
cada uno de los archivos, son los siguientes:
Numero_Foligonos o Total de Polígonos en la escena o
Numero_Elementos Total de Elementos en la escena
Vertice_l
Vertice_2
Vertice_3
Vertice-4
N umero_Farche
N umeroJ3olido
Nivel_Farche
Nivel...Elementos
Are a
vec_normal..x
vec_normaLy
vec_normal..z
reflectancia...r
reflectancia_g
reflectancia_b
emision...r
emision_g
emision_b
Vértices siguiendo regla de mano derecha
Número de Parche ( Polígono )
Número de Sólido al que pertenece el parche
Fuera de uso
Fuera de uso
Vector Normal de la superficie
Valor de Reflectancia de la superficie
en rangos de [0 .. 1]
Valor de Emisión de la superficie en
rangos de [ü .. l]
86
• Archivo de Vértices y Vertelem.
Estos archivos se asocian con el de polígonos, su primer campo es el total de vértices,
después de esto, existe una repetición de valores (x , y, z) para cada vértice.
Numero_Vertices
coordenada_x
coordenada_y
coordenada_z
• Archivo de Luces
Número total de vértices
Localización en 3D
El archivo de luces permite especificar las luces que habrá en la escena, sus posiciones y
características. Para el caso libre del problema inverso, es decir, para la determinación
del número de luces ideal , este archivo marca el límite de luces para la solución.
Numero_Luces
Posicion_x
Posicion_y
Posicion_z
Esquina_l_x
Esquina_Ly
Esquina_l_z
Esquina_2_x
Esquina_2_y
Esquina_2_z
NiveLParche
NiveLElemento
Cantidad total de luces
Localización en el espacio
Ubicación de una esquina del polígono
Ubicación de la segunda esquina
Fuera de uso
Fuera de uso
Are a
vec_normaLx
vec_normaLy
vec_normaLz
reflectanciaJ
reflectancia_g
reflectancia_b
em1s1onJ
emision..g
emision_b
tipoJuz
consumo
costo
vidautil
• Archivo de Parámetros.
Vector Normal
Propiedades de Reflectancia
Propiedades de Emisión
Tipo de luz, O-cuadrada 1-rectangular
consumo en watt's
costo asociado por el consumo
Vida Útil de la luz
87
El archivo de parámetros describe los valores ocupados para la visualización de la
escena.
UmbraLconvergencia Límite de Convergencia
Subdivision_Area Límite para subdivisión de Jerarquía
Subdivision_Area_Solucion Límite para subdivisión de solución.
Numero_Farches Inicialmente O
Parches Inicialmente O
N umero.Blementos Fuera de uso
Elementos Fuera de uso
N umero_Funtos Fuera de uso
Puntos Fuera de uso
Camara....x
Camara_y Ubicación de la cámara en 3D
Camara....z
Observador....x
Observador_y
Observador_z
Vec_Arriba....x
Vec_Arriba_y
Vec_Arriba....z
Vision_Campo....x
Vision_Campo_y
Plano_cercano
PlanoJejano
Localización del Observador
Vector de orientación.
Parámetros de la visión de campo
Planos para recorte
88
Resolucion-1Iemicubo....x
Resolucion-1Iemicubo_y
A puntador _buffer
Apuntador _ventana
Tamanio...M undo
Escala-1ntensidad
Fuera de uso
Fuera de uso
Fuera de uso
Fuera de uso
Area del mundo real
Escalamiento para dibujo progresivo.
Agregar_Termino..Ambiente O - No 1 - Si
89
90
• Archivo de parámetros del Algoritmo Genético.
Este archivo describe los límites y tipo de caso a resolver mediante un algoritmo
genético.
Limite.Luces
Dimension_por ...Luz
Tipo_problema
Tamaño_poblacion
Maxima_Generacion
Probabilidad...M utacion
Pro babilidad_Cruzamiento
Aplicar _Escalamiento
Areas_Limite
Tamaño_Caracteristica
Limite-1nferior
Limite--8uperior
Número máximo de luces en la escena
Cantidad de variables por cada luz ( posicion,
nivel de luz )
Caso del problema inverso
1-Nivel de Luz en posición fija
2-Nivel de Luz y posición variable
3-Nivel de luz para un número variable pero
limitado
4-Caso Libre
5-Costo
Tamaño de la población en el AG
Máximo número de generaciones
Probabilidad de Mutación
Probabilidad de Cruzamiento
O - No aplicar, 1 - Aplicar
Establecer el número de zonas delimitadas
para cada valor. Esto permite fijar más de
un par de límites para cada valor.
Tamaño de la característica
Cota inferior de la característica
Cota superior de la característica
La forma en la que se pueden cambiar los parámetros de los archivos anteriores para solu
cionar el problema inverso es sencilla, pero requiere cuidado al hacerlo. A continuación se
presentan algunos ejemplos de cómo y dónde hacer los cambios adecuados, estos ejemplos
91
están organizados de acuerdo con los casos que la solución propone:
• Caso 1: Nivel de Luz para un número fijo de luces en posiciones fijas.
Archivo Genetica: Este archivo debe configurarse para fijar el número de luces, la
dimensión debe fijarse en 3, es decir, (R, G, B). Para cada una de las variables su
rango válido se debe establecer desde O hasta 255. El valor de Tipo de Problema
se debe fijar en l.
Archivo de Luces: El archivo de luces deberá contener un número de instancias
igual al número especificado en el archivo genetica, además de establecer los
parámetros para cada una de las luces como se indica en la descripción del archivo.
• Caso 2: Nivel de luz y posición para un número fijo de luces.
Archivo Genetica: El número de luces debe fijarse en un valor límite, el valor de la
dimensión se debe fijar en 6 (R, G, B) y (x, y, z). Finalmente el tipo de problema
debe ser 2.
Archivo Luces: El número de luces debe ser igual al valor establecido en el archivo
genetica así como sus correspondientes instancias para describir cada luz.
• Caso 3: Nivel de luz para un número variable de luces en posiciones fijas.
Archivo Genetica: Se debe fijar el número límite de luces; el valor de la dimensión
debe ponerse en 3 (R, G, B) y el tipo de problema es 3.
Archivo Luces: Fijar el número de luces en un valor igual al que especificado en el
archivo genetica.
• Caso 4: Nivel de luz y posición para un número variable pero limitado de
luces.
Archivo Genetica: Este archivo debe tener capturado el número límite de luces que
el algoritmo podrá emplear para la solución, la dimensión de cada luz debe es
tablecerse en 7 ( (R, G, B), (x, y, z) y Tipo de Luz). El tipo de problema a resolver
es 4.
92
Archivo de luces: El archivo de luces debe contener un valor igual al especificado
en el archivo genetica.
• Caso 5: Costo Asociado.
Archivo Genetica: El número de luces se debe fijar y para cada luz la dimensión
deberá ser de 7, mientras que el tipo de problema debe ser 5.
Archivo Luces: El número de luces se fija igual que en el archivo anterior y para
cada luz se asocia los parámetros que la describen.
Cabe mencionar que el archivo "genetica" además se le puede configurar los parámetros del
tamaño de población ( popsize ), el cual debe ser un valor entero par; el número máximo de
generaciones, la probabilidad de mutación y la probabilidad de cruzamiento y finalmente , si
se desea aplicar, el escalamiento de la función objetivo.
El archivo de visualización tiene dos parámetros para realizar la subdivisión de los parches.
El primero es usado por el algoritmo genético y radiosidad jerárquica para calcular la con
vergencia hacia la escena deseada. Se sugiere que este valor sea igual al área más grande de
los parches de la escena deseada, para así no realizar demasiadas subdivisiones y provocar
una mayor extensión de tiempo en la evaluación de radiosidad. El segundo permite definir
un nivel de subdivisión para la solución final , por lo que este puede ser un valor igual o
menor al anterior para generar un mayor nivel de detalle.
93
ANEXO B
DOCUMENTACIÓN DE ARCHIVOS DE SALIDA ~
DE LA SOLUCION.
Los archivos de salida de esta solución contienen la solución aproximada y la distancia entre
la escena deseada y la aproximación, referida esta última como mundos distantes.
• Escena Aproximada: La escena aproximada guardada en archivo posee una estructura
muy similar a la que tiene la escena original, salvo porque los campos de emisión ahora
tienen el valor de la radiosidad del parche. Los datos están contenidos en un par de
archivos llamados " .. poligonos.apx??" 15 y " .. vertices.apx??".
• Escena "Mundos Distantes" 16 : Esta escena se genera para la solución final como la
diferencia de las radiosidades entre la escena original o deseada y la escena aproximada.
La estructura de los archivos es similar a la indicada para la escena original, solo que a
diferencia de la emisión en este caso cada polígono tiene la diferencia entre la radiosidad
deseada y la radiosidad aproximada. La terminación de los archivos es ".err??".
A continuación se muestra un ejemplo de los archivos para la aproximación de una escena.
La escena fue obtenida considerando el caso 1 indicado en el anexo A.
15 ?? puede ser ga ( algoritmo genético ), gd ( gradiente descendente ) o rs ( recocido simulado ).
16 La diferencia entre la escena deseada y la aproximada. Un error máximo se ve blanco o iluminado, mientras que un error cero se ve negro.
18
O 1 2 3 O O O O 46440.0 o.o -1.0 o.o 0.9 0.9 0.9 0.6423 0.3592 0.2687 4 5 6 7 1 1 O O 46440.0 o.o 1.0 o.o 0.9 0.9 0.9 1.0 0.6794 0.4014 8 9 10 11 2 2 O O 47515.0 1.0 o.o o.o 0.8 0.1 0.075 0.6099 0.05009 0.0276 12 13 14 15 3 3 O O 47736.0 o.o o.o 1.0 0.9 0.9 0.9 0.6723 0.3964 0.2927
94
16 17 18 19 4 4 O O 47515.0 -1.0 o.o o.o 0.075 0.1 0.35 0.06732 0.0568 0.1527 20 21 22 23 5 5 O O 4225.0 o.o 1.0 o.o 0.9 0.8 0.1 0.8111 0.3859 0.04202 24 25 26 27 6 5 O O 4225.0 o.o -1.0 o.o 0.9 0.8 0.1 0.3369 0.1968 0.01635 28 29 30 31 7 5 O O 4225.0 -0.866 o.o -0.5 0.9 0.8 0.1 0.4374 0.26397 0.0247 32 33 34 35 8 5 O O 4225.0 0.5 o.o -0.866 0.9 0.8 0.1 0.5732 0.2614 0.0228 36 37 38 39 9 5 O O 4225.0 0.866 o.o 0.5 0.9 0.8 0.1 0.9606 0.4904 0.04545 40 41 42 43 10 5 O O 4225.0 -0.5 o.o 0.866 0.9 0.8 0.1 0.7318 0.4320 0.0420
44 45 46 47 11 6 O O 4225.0 o.o 1.0 o.o 0.9 0.9 0.9 0.5913 0.3567 0.3493 48 49 50 51 12 6 O O 4225.0 o.o -1.0 o.o 0.9 0.9 0.9 0.3219 0.2116 0.1406
52 53 54 55 13 6 O O 8450.0 -0.866 o.o -0.5 0.9 0.9 0.9 0.5140 0.3305 0.2272 56 57 58 59 14 6 O O 8450.0 0.5 o.o -0.866 0.9 0.9 0.9 0.4818 0.2585 0.1706 60 61 62 63 15 6 O O 8450.0 0.866 o.o 0.5 0.9 0.9 0.9 0.6391 0.3619 0.2320 64 65 66 67 16 6 O O 8450.0 -0.5 o.o 0.866 0.9 0.9 0.9 0.8843 0.5732 0.3647 68 69 70 71 17 7 O O 1800.0 o.o -1.0 o.o o.o o.o o.o 1.0 1.0 1.0
95
ANEXO C
DOCUMENTACIÓN DE SISTEMA DE VISUALIZACIÓN.
El sistema de visualización integral en 3D permite cargar y generar una vista de una escena
original, la aproximación mediante la solución propuesta y la escena "mundos distantes" 17 .
De igual forma permite pintar áreas de la escena original para usarse como escena deseada.
El visor realiza una suavización del color calculando una interpolación del color por vértices
en lugar de usar únicamente el color de la superficie.
Para ejecutar este visor es necesario teclear "visor" en el shell y oprimir la tecla ENTER. Al
ejecutarse el visor aparece en el monitor una ventana identificada como "Visor de escenas
en 3D" y asociada a ella un menú de opciones. Este menú de opciones se activa al presionar
el botón derecho del ratón una vez que se está posicionando en cualquier parte del área de
la ventana. Las opciones del menú permiten realizar lo siguiente:
Cargar una Escena: Esta opción permite cargar una de tres escenas: la original o deseada,
la aproximada ( resultado del GA y Radiosidad) y la distancia entre las dos anteriores,
es decir, "mundos distantes". Una vez que se elige alguna de estas opciones el programa
pide el nombre de la escena por lo que es necesario cambiarse al shell de Unix y teclearlo.
Guardar una Escena: Para la escena original es posible "pintarle" áreas con un pincel de
luz ( a través del ratón ) y guardar los cambios en el archivo para que esta escena tenga
el efecto deseado.
Cambio de Color: Una vez que está activo el ratón como "pincel de luz" es posible cam
biarle el color a uno predefinido ( gris, gris claro, gris obscuro o blanco ) o bien a uno
que defina el usuario. Para este último caso es necesario cambiarse al shell de unix
y teclear donde se indica los valores para las variables R,G,B para obtener el color
deseado. Cada valor se establece como un entero en el rango de [0 .. 255].
17 La diferencia entre la escena deseada y la aproximada; una buena aproximación genera una escena de "mundos distantes" obscura.
96
Posición Inicial: El uso de est a opción permite regresar la escena a su posición inicial.
Esto resulta út il cuando se han efectuado una serie de movimientos de t raslación y
rotación que pueden "perder" al usuario en su orientación en el espacio en 3D.
Encender/ Apagar pincel de Luz: Esta opción ofrece la característica de activar el ratón
como un "pincel de luz", al encenderlo, cada vez que se presione el botón izquierdo del
ratón sobre un parche de la escena, el parche cambiará al color especificado ( el color
por omisión es blanco ). La opción de apagado desactiva esta propiedad del ratón y ya
no sigue pintando.
Dibujar /Borrar Ejes: Para orientar al usuario en el espacio de 3D es posible activar o
desactivar los ejes cartesianos XYZ que ubican el origen en 3D empleando esta opción.
Ver Alambrado/Sólidos: Activa y desactiva la visión de la escena como formada por
alambres o bien en forma sólida.
(No) Aplicar Gouraud: Activa o desactiva la aplicación del método de Gouraud para
suavizar la escena. Se dibuja el parche interpolando el valor del color para cada vért ice,
o bien simplemente se dibuj a el parche con su color.
Aproximar vía: Esta opción permite ejecutar cualquiera de los tres métodos de aproxi
mación para buscar la solución a la escena deseada. Los métodos que se pueden emplear
son: Algoritmo Genético, Gradiente Descendente y Recocido Simulado.
Acerca de Este Programa: Al seleccionar esta opción muestra como salida un texto que
indica el título de la tesis y los autores.
Salir: Esta opción permite terminar el programa "visor" .
Otra característica del visor es su capacidad para realizar movimientos de t raslación, rotación
y escalamiento sobre la escena. Las teclas definidas para realizar estos movimientos se des
criben a cont inuación:
...
97
• Movimientos de traslación y escalamiento
- Flecha Izquierda, Flecha Derecha: permite la traslación a lo largo del eje X, en
sentido negativo ( flecha izquierda) o en sentido positivo ( flecha derecha ).
Flecha Arriba, Flecha Abajo: ofrecen el movimiento de traslación en el eje Y,
con la flecha hacia arriba la escena se trasladará en el sentido positivo del eje Y,
mientras que al usar la flecha abajo la escena se moverá en el sentido negativo.
Z, z: Al presionar esta tecla el efecto producido es el acercamiento ( Z ) o el
alejamiento ( z ) de la escena.
• Movimientos de Rotación.
F5, F6: El uso de estas teclas está asociado con la rotación respecto al eje X. F5
hace una rotación positiva mientras que F6 la hace en forma negativa.
F7, F8: Estas teclas de función permiten la rotación de la escena respecto al eje
Y; así, presionando la tecla F7 la escena rotará en el sentido positivo respecto al
eje Y, mientras que al elegir F8 se realizará una rotación negativa respecto a Y .
F9, FlO: Para estas teclas se define la rotación respecto al eje Z de manera positiva
usando F9 y negativa a través de FlO.
Los movimientos antes descritos se realizan de manera uniforme a través de incrementos
y/ o decrementos de 2 unidades para el caso de la traslación. La rotación se realiza por
incrementos y decrementos de 2 grados y finalmente el acercamiento y alejamiento usa un
valor de 2 unidades para efectuar esta operación.
'
f
98
BIBLIOGRAFÍA.
[1 J D. Beasley. F AQ: comp.ai.genetic ( A guide to frequently asked questions ) Department of Computing Mathematics, University of Walles College of Cardiff, 1974. Disponible vía ftp anónimo ftp desde ftp://rtfm.mit.edu/pub/usenet/ news.answers/ aifaq/ genetic/ partl .. part6.
[2] C. Cantú. Solución a sistemas de ecuaciones no lineales aplicando Algoritmos Genéticos.
Master's thesis, Instituto Tecnológico y de Estudios Superiores de Monterrey, Campus Monterrey, México, 1992.
[3] C. A. Coello Coello. Introducción a los Algoritmos Genéticos. Revista Soluciones Avan
zadas, 17, Enero 1995.
[4] M. F. Cohen and J. R. Wallace. Radiosity and Realistic Image Syntesis. Academic Press Professional, 1993.
\ [5] K. A. DeJong. An analisys of the behavior of a class of genetic adaptive systems.
Dissertation abstracts international 36(10), 5140b, Doctoral dissertation, University of Michigan, 1975.
[6] J. D. Foley, A. van Dam, S. K. Feiner, and J. F. Hughes. Computer Graphics: Principies
and Practice. Addison-Wesley, New York, second edition, 1990.
[7] J. A. Freeman and D. M. Skapura. Neural Networks: Algorithms, Applications, and
Programming Techniques. Addison-Wesley, New York, 1991.
[8] D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning.
Addison-Wesley, New York, first edition, 1989.
[9] J. J. Grefenstette and J. E. Baker. How Genetic Algorithms work: a critical look at
implicit parallelism. In Morgan Kauffman, editor, Third International Conference on
Genetic Algorithms, pages 12-19. San Mateo California, 1989.
[10] D. Hanrahan, P. Salzman, and L. Aupperle. A rapid hierarchical radiosity algorithm. In (SIGGRAPH '91) Computer Graphics Proceedings, pages 197- 207, 1991.
[11 J L. lngber. Simulated Annealing: Practice versus theory , 1993. Disponible vía ftp anónimo en ftp://ftp.alumni.caltech.edu/pub/ingber/asa93sapvt.ps.Z.
[12] J. K. Kawai, J. S. Painter, and M. F. Cohen. Radioptimization - Goal Based Rendering.
In Computer Graphics Proceedings, Anual Conference Series, pages 147- 154, 1993.
[13] M. Kilgard. Silicon graphics, 1994. Disponible vía ftp anónimo en
ftp://sgigate.sgi.com/ opengl/xjournal/ G L UT.
99
[14] B. Lange and Ch. Hornung. A solution to Global Illumination br, Genetic Algorithms.
In R. F. Albrecht, C. R. Reeves, and N. C. Steels, editors, Artificial Neurnl Nets and
Genetic Algorithms, pages 595-601, lnnsbruck, Austria, April 1993. Springer-Verlag, Wien.
[15] Ch. L. Lawson and R. J. Hanson. Solving Least Squares Problems. Prentice Hall, Englewood Cliffs, 1974.
[16] P. E. Lewis and J. P. Ward. The Finite Element Method, Principies and applications.
Addison-Wesley, 1991.
[17] J. Neider, T. Davis, and M. Woo. OpenGL Progrnmming Cuide: The official guide to
learning OpenGL, Helease 1. Addison-Wesley, Massachusetts, 1993.
[18] R. W. Pike. Optimization far Engineering Systems. Van Nostrand Reihold Company,
New York, 1986.
[19] W. H. Press, Vetterling W. T., S. A. Teukolsky, and B. P. Flannery. Numerical Recipies
in C, the art of science computing. Cambridge University Press, second edition, 1995.
[20] S.S. Rao. Optimization: theory and applications. John Wiley and Sons, 1979.
[21] R. Y. Rubisntein. Simulation and the Monte Garlo Method. John Wiley and Sons, 1981.
[22] L.E. Sales. Introduction to Non-Linear Optimization. MacMillan, 1985.
[23] C. Schoeneman, J. Dorsey, B. Smits, J. Arvo, and D. Greenberg. Painting with Light. In Computer Grnphics Proceedings, Anual Conference Series, pages 143-146, 1993.
[24] F. X. Sillion and C. Puech. Radiosity and Global Illumination. Morgan Kaufmann
Publishers, Inc., 1994.
[25] F. Tampieri. Accurnte Form-Factor Computation. In David Kirk, editor, Grnphics
GEMS JI!, pages 557-580 (Code), 329-333 (Text). Academic Press., 1992.
[26] P. D. Wasserman. Neurnl Computing: Theory and Prnctice. Van Nostrand Reinhold,
New York, 1989.
[27] A. Watt. 3D Computer Grnphics. Addison-Wesley, New York, second edition, 1993.
![1415 algoritmos Geneticos.ppt [Modo de compatibilidad]webdiis.unizar.es/asignaturas/APD/wp/wp-content/... · L. Recalde, J. Campos. EINA. Algoritmos Genéticos 2 Algoritmos genéticos](https://img.pdfslide.es/doc/110x75/601984468bf28b1b295e732e/1415-algoritmos-modo-de-compatibilidadwebdiisunizaresasignaturasapdwpwp-content.jpg)
