%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Autor: Alexzander Arriaga Martinez
% Sitio web: http://fenix.cs.buap.mx
% Correo-e : alex.arriaga.m@gmail.com
% Facebook : /alex.arriaga.m
% Twitter  : @alex_arriaga_m
% Youtube  : /aarriagamx
% Blogspot : http://alexarriagam.blogspot.com/
% Wordpress: http://mrfenixito.wordpress.com/
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Documento: 
% 	Presentación de tesis para obtener el grado de Ingeniero en Ciencias de la Computación
% Título:
%	Artífice: Generador de ciudades virtuales mediante autómatas celulares.
%			  Un enfoque desde los sistemas complejos y auto-organizantes
% Institución: 
%	Facultad de Ciencias de la Computación (http://www.cs.buap.mx)
%	Benemérita Universidad Autónoma de Puebla (http://www.buap.mx)
% 
\documentclass[xcolor=dvipsnames]{beamer}
%\usetheme{Boadilla}
%\usetheme[height=7mm]{Rochester}
%\usetheme{Madrid}
%\usetheme{Pittsburgh}
%\usetheme{Copenhagen}
%\usetheme{Singapore}
%\usetheme{Malmoe}

% Estos son algunos de los temas con los que se puede probar
%AnnArbor     Ilmenau
%Antibes      JuanLesPins
%Bergen       Luebeck
%Berkeley     Madrid
%Berlin       Malmoe
%Boadilla     Marburg
%boxes        Montpellier
%CambridgeUS  PaloAlto
%Copenhagen   Pittsburgh
%Darmstadt    Rochester
%default      Singapore
%Dresden      Szeged
%Frankfurt    Warsaw
%Goettingen   
%Hannover

%GreenYellow Yellow
%Goldenrod Dandelion
%Apricot Peach Melon YellowOrange
%Orange BurntOrange Bittersweet RedOrange
%Mahogany Maroon BrickRed
%Red OrangeRed RubineRed

%WildStrawberry Salmon CarnationPink VioletRed Rhodamine
%Mulberry RedViolet Fuchsia Lavender Thistle 

%Orchid DarkOrchid Purple Plum Violet RoyalPurple BlueViolet
%Periwinkle CadetBlue
%CornflowerBlue MidnightBlue NavyBlue RoyalBlue Blue Cerulean Cyan ProcessBlue SkyBlue Turquoise
%TealBlue Aquamarine BlueGreen Emerald
%JungleGreen SeaGreen Green ForestGreen PineGreen LimeGreen YellowGreen SpringGreen
%OliveGreen RawSienna Sepia Brown Tan Gray Black

% Estos tres temas particularmente me gustaron
%\usetheme{Berkeley}
%\usetheme{Frankfurt}
%\usetheme{Marburg}


\usepackage{ragged2e}
\setbeamertemplate{navigation symbols}{} % Ocultar iconitos abajo
%\usecolortheme[named=BrickRed]{structure}
\useoutertheme{infolines}{\title{}}
\usetheme{Warsaw} % Recomendado
%\useoutertheme{shadow}
\useinnertheme{rounded}


%\expandafter\def\expandafter \insertshorttitle
%\expandafter{%
 % \insertshorttitle\hfill }%
%  \insertframenumber\,/\,\inserttotalframenumber}

% Opciones de configuración para modificar los colores por defecto que brinda el tema
%\usecolortheme{beetle} % 2
%\usecolortheme{beaver} % 4
%\usecolortheme{dolphin} % 2
%\usecolortheme{dove} % 6
%\usecolortheme{fly} % 6
%\usecolortheme{lily} % 2
%\usecolortheme{orchid} % 2
%\usecolortheme{rose} % 2
%\usecolortheme{seagull} %4
%\usecolortheme{seahorse} % 2
%\usecolortheme{sidebartab}%
%\usecolortheme{wolverine} %1


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% CÓDIGO PRESENTACIÓN %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage[spanish]{babel}
\usepackage[utf8]{inputenc}
%\usepackage{shadow}


\title{Artífice: Generador de ciudades virtuales mediante autómatas celulares. Un enfoque desde los sistemas complejos y auto-organizantes}
\author{
Alexzander Arriaga Martinez %\\ \vspace{2mm} \tiny \textbf{Asesores:} \\ Dr. Abraham Sánchez López \\ Dr. Carlos Gershenson \\ Dr. Isaac J. Rudomín Goldberg
}

\date{15 de julio de 2011}
\institute{\\ \vspace{2mm} \tiny \textbf{Asesores:} \\Dr. Abraham Sánchez López \\(FCC-BUAP) \\Dr. Carlos Gershenson \\(IIMAS-UNAM) 
	\\ Dr. Isaac J. Rudomín Goldberg \\(ITESM-CEM)
	}
\logo{ \includegraphics[width=2cm]{img/logo.png}}
% Si se desea incluir una imagen de fondo descomentar esta linea
%\usebackgroundtemplate{ \includegraphics[width=\paperwidth, height=\paperheight]{img/fondo.jpg} }

\begin{document}
%\beamerdefaultoverlayspecification{<+->}
\frame[plain] %Quita las barras de navegacion en el inicio de la presentacion
{\titlepage}

% Genera una diapositiva automatica al inicio de cada sección destacando ésta.
%\AtBeginSection[]
%{
% \frame
% {
% \frametitle{Agenda}
% \tableofcontents [allowframebreaks, currentsection]
% }
%}

\section[Agenda]{}
\frame%[allowframebreaks] % Divide el contenido en varios frames si éste es muy largo
{
\frametitle{Agenda}%{\centerline{Agenda}}
\setbeamercovered{dynamic}
\transblindshorizontal % Efecto de transición
%\scriptsize %Reduce el tamaño de fuente
%\tableofcontents %[pausesections]
\begin{enumerate}
	\item Presentación \pause
	\item Marco teórico \pause
	\item Planteamiento del problema \pause
	\item Estado del arte \pause
	\item Análisis del problema \pause
	\item Propuesta de solución \pause
	\item Implementacion \pause
	\item Resultados obtenidos \pause
	\item Conclusiones
\end{enumerate}
}
\section{Presentación}
\frame
{
	\begin{center}
		\huge Presentación
	\end{center}
}
\subsection{Objetivo general}
\frame
{
\transblindshorizontal % Efecto de transición
  %\frametitle{Objetivo general}
  \begin{block}{Objetivo general}\justifying
  Construir  un software, llamado \textit{Artífice} para simular el crecimiento de ciudades virtuales
  en términos de la ocupación de su terreno y con base en ello estudiar el crecimiento poblacional. 
  \end{block}
}
\subsection{Objetivos específicos}
\frame
{
\transblindshorizontal % Efecto de transición
  \frametitle{Objetivos específicos}
  \setbeamercovered{dynamic}
  \transboxin
  %Va mostrando un ítem por transparencia
  \begin{itemize}\justifying
    \item Utilizar un método sistémico para determinar los componentes, relaciones y estructura de una ciudad. \pause
    \item Construir un modelo que represente una ciudad, este modelo deberá ser capaz de evolucionar 
    (mediante el uso de Autómatas Celulares). \pause
    \item Simular el crecimiento de una ciudad en términos de la ocupación de su terreno. \pause
    \item Implementar un visor 3D de las ciudades generadas. \pause
  \end{itemize}
}

%%%%%%%%%%%%%%%%%%%%%%%%%% Sección 1: Sistemas complejos %%%%%%%%%%%%%%%%%%%%%%%%%% 
\section{Marco teórico}
\frame
{
	\frametitle{}
	\begin{center}
		\huge Marco teórico
	\end{center}
}
\subsection{Comprendiendo a la Complejidad}
\frame[allowframebreaks]
{
\justifying
\transblindshorizontal % Efecto de transición
	\frametitle{Definición: Complejidad}
%	\setbeamercovered{dynamic}
	Raíz latina \textit{plectere}  $\Longrightarrow$ ``entrelazado'' o ``entretejido'' (Cilliers; 2002).
	Cualidad de aquello que está formado por múltiples partes, el comportamiento del \textbf{todo} no puede determinarse
	estudiando las \textbf{partes} por separado.
%	\pause
	\begin{block}{Importante}\justifying
	``La complejidad de un sistema se incrementa con el número de componentes distintos, la cantidad de conexiones entre
	ellos, las complejidades de los elementos y las complejidades de las conexiones'' (Gershenson; 2004).
	\end{block}
%	\pause
}
\frame
{
	\justifying
	\frametitle{Sistemas complejos}
	\transboxout
	Sistemas con múltiples partes; interesa el estudio de las interacciones de éstas y no la particularidad de las mismas.
	\begin{figure}
	\begin{center}
		\includegraphics[width=5cm]{img/sistemas_dinamicos.jpg}
		\caption{Ejemplos de sistemas complejos}
	\end{center}
	\end{figure}
}
\subsection{Autómatas celulares}
\frame
{
	\transboxin
	\frametitle{Autómatas celulares como motores conceptuales}
	\begin{block}{Autómata celular}\justifying
	\textbf{Modelo} para un sistema dinámico no continuo. Evoluciona a pasos discretos en un \textit{espacio regular infinito}.
	\end{block}
}
\frame
{
	\justifying
	\transboxin
	\frametitle{Autómata celular: definición}
	\begin{block}{Definición}\justifying
	Un Autómata Celular es una 4-tupla:
	\begin{equation} 
		<\sum, \upsilon, \varphi, s_{0} >
	\end{equation}
	
	Evolucionando en $d \in \mathbb{Z}$ donde:
	\begin{itemize}
		\item $\sum $ es un conjunto finito de estados.
		\item $\upsilon $ una conexión local tal que $ \upsilon = \{ X_{i,j, \ldots , n: d} \}$. Llamada también vecindad. Donde $ \{ X_{i,j, \ldots , n: d} \}$ representa el espacio de evoluciones.
		\item $\varphi: \upsilon  \rightarrow \sum$ representa la función de transición.
		\item $s_{0} $ es la configuración inicial del Autómata Celular.
	\end{itemize}
	\end{block}
}

\frame
{
\justifying
\frametitle{Autómata celular: espacio de evoluciones}
	Un AC puede evolucionar en alguna dimensión, hasta el momento las más utilizadas han sido la 1D, 2D y 3D.
	Cada uno de estos espacios de evoluciones, se aplican a diferentes problemas.
	\begin{figure}
	\begin{center}
	    \includegraphics[height=1.1in]{img/espacios}
		\caption{Espacios de evoluciones más utilizados}
	\end{center}
	\end{figure}
}

\frame
{
	\justifying
	\frametitle{Autómata celular: estado}
	Un \textbf{estado} $s$ es formalmente un elemento $\sum, (s \in \sum)$ que puede ser asignado a una célula mediante la función de transición. El estado equivale a una configu\-ración única 
	y no ambigua del conjunto de estados de algún autómata celular n-dimensional.
}

\frame
{
\justifying
\frametitle{Autómata celular: vecindad}
	\transdissolve
	Vecindades más comunes para AC's bidimensionales: \textbf{vecindad de Moore} y \textbf{vecindad de Von-Neumann}; llamamos \textbf{células vecinas} a aquellas que son inmediatamente 
	adyacentes a una \textbf{célula central} (Ilachinski; 2001).
	
	%Las formas explícitas de estas vecindades se definen como sigue (Ilachinski; 2001):
	%\begin{equation*}
	%	\left\lbrace
	%	\begin{array}{l}
	%	a): \sigma^{(t+1)}_{i,j} = \phi( \sigma^{(t)}_{i-1,j-1}, \sigma^{(t)}_{i,j-1}, 	\sigma^{(t)}_{i+1,j-1}, \sigma^{(t)}_{i-1,j}, \sigma^{(t)}_{i,j}, \sigma^{(t)}_{i+1,j}, \sigma^{(t)}_{i-1,j+1}, \sigma^{(t)}_{i,j+1}, \sigma^{(t)}_{i+1,j+1} ) \\
	%	b): \sigma^{(t+1)}_{i,j} = \phi( \sigma^{(t)}_{i,j}, \sigma^{(t)}_{i-1,j}, 	\sigma^{(t)}_{i+1,j}, \sigma^{(t)}_{i,j-1}, \sigma^{(t)}_{i,j+1} )\\
	%	\end{array}
	%	\right.
	%\end{equation*}
	
	\begin{figure}
	\begin{center}
	    \includegraphics[height=1.0in]{img/vecindades_comunes.jpg}
		\caption{Vecindades de Moore y Von-Neumann}
	\end{center}
	\end{figure}
}

\frame
{
	\justifying
	\frametitle{Autómata celular: función de transición}
	\transdissolve
	La función de transición $\varphi: \upsilon  \rightarrow \sum$ se aplica a todas las células del espacio de evoluciones. 
	
	La función $\varphi$ toma como argumentos los valores de la célula en cuestión y los valores de sus vecinos, 
	y regresa el nuevo valor que la célula tendrá en la siguiente generación.

	Esta función $\varphi$ se aplica de forma homogénea a todas las células, por cada paso discreto de tiempo.
}
\subsection{El juego de la vida}
\frame
{
	\justifying
	\frametitle{El juego de la vida}
	\transdissolve
	\textit{Life}, el mejor ejemplo de autómata celular bidimensional.
	Creado por John H. Conway, publicado en 1970 en la columna \textit{Mathematical Recreations} en \textit{Scientific American}. (McIntosh; 1988).
	\begin{figure}
	\begin{center}
		\includegraphics[width=6cm]{img/juego_vida_3d.jpg}
		\caption{Implementación propia del juego de la vida}
	\end{center}
	\end{figure}
}
\frame{
	\frametitle{Reglas del juego de la vida}
	\transsplitverticalin
	\begin{itemize}
		\item \textbf{Regla de supervivencia} \pause
		\item \textbf{Regla de nacimiento} \pause
		\item \textbf{Regla de muerte} \pause
	\end{itemize}
	\begin{center}
	Veamos un ejemplo...
	\end{center}
}

\section{Planteamiento del problema}
\frame
{
	\frametitle{}
	\begin{center}
		\huge Planteamiento del problema
	\end{center}
}
\subsection{Motivación}
\frame
{
  \frametitle{Motivación}
  \transdissolve
  \begin{enumerate}\justifying
	  \item El estudio de las ciudades en términos de crecimiento poblacional resulta un tema relevante en nuestros días. \pause
	  \item Los seres humanos hemos llegado casi ya a los 6900 millones de personas. \pause
	  \item Los simuladores para el crecimiento poblacional y generación de ciudades son privados y su código fuente no
	 está disponible para mejorarlos. \pause
     \item Existen trabajos realizados con autómatas celulares, sin embargo en México existe poco desarrollo en esta área. \pause
     \item Los proyectos que usan autómatas celulares no brindan herramientas de visualización 3D. \pause
	\end{enumerate}
}
\subsection{Caso de estudio: planeación en urbanismo}
\frame
{
	\justifying
	\frametitle{Ejemplo de la importancia de la planeación en urbanismo}
	\textbf{CASO:} Nuevo San Juan del Grijalva, Chiapas.
	
	En 2007 las lluvias destruyeron 11 comunidades indígenas el gobierno mexicano crea la \textbf{primera ciudad rural sustentable}
	
	\begin{figure}
	\begin{center}
		\includegraphics[width=9cm]{img/san_juan_del_grijalva}
		\caption{Nuevo San Juan del Grijalva}
	\end{center}
	\end{figure}
}

%%%%%%%%%%%%%%%%%%%%%%%%%% Sección 2: Estado del Arte %%%%%%%%%%%%%%%%%%%%%%%%%% 
\section{Estado del Arte}
\frame
{
	\frametitle{}
	\begin{center}
		\huge Estado del Arte
	\end{center}
}
\subsection{Técnicas procedurales para generación de ciudades}
\frame[allowframebreaks]
{
  \justifying
  \frametitle{\textit{Grid layout} y primitivas geométricas}
  \transwipe
  Genera una ciudad en tiempo real, p. ej. \textit{UndiscoveredCity} que crea una red de caminos basada en un \textit{grid}. 
  Los edificios se construyen con primitivas geométricas simples.

  \begin{figure}
  \begin{center}
  		\includegraphics[width=4cm]{img/undiscoveredcity_piso_fachada_gen.jpg}
  		\caption{Construcción de piso y caras de los edificos de \textit{UndiscoveredCity}}
  \end{center}
  \end{figure}  
  Las coordenadas de localización de los edificios en el \textit{grid} se usan como semilla para la generación. El texturizado se
  realiza con 10 imágenes dife\-rentes.
  
  \begin{figure}
  \begin{center}
  		\includegraphics[width=6cm]{img/undiscoveredcity_ejemplo.jpg}
  		\caption{Ciudad generada con tiempo real con \textit{UndiscoveredCity}}
  \end{center}
  \end{figure}
  
}
\subsection{Sistemas Lindenmayer (L-Systems)}
\frame[allowframebreaks]
{
  \justifying
  \frametitle{Sistemas Lindenmayer \textit{(L-Systems)}}
  	\transdissolve
  Gramáticas formales utilizadas originalmente por Biológos para modelar el proceso de crecimiento de plantas.
  Creadas por \textbf{Aristid Lindenmayer}.
  	\begin{figure}[htb]
	\begin{center}
		\includegraphics[width=1.5in]{img/sistema_lindenmayer.jpg}
		\caption{Un ejemplo de generación de plantas}
	\end{center}
	\end{figure}
	
	 Idea central $\Longrightarrow$ \textbf{sobreescritura}. Define objetos por reemplazo sucesivo de sus partes. Se comienza con un objeto simple
  	 y se modifica mediante producciones.
  	 Formalmente un \textit{L-System} se define como (Kelly \& McCabe; 2003): 
	\begin{figure}[htb]
	\begin{center}		
		\includegraphics[width=2.5in]{img/edificios_Lsystem.jpg}
		\caption{Edificios generados con \textit{L-Systems}}
	\end{center}
	\end{figure}
}
\subsection{Simulación basada agentes}
\frame
{
  \justifying
  \frametitle{Simulación basada agentes}
  \transdissolve

  Enfoque propuesto en 2004 (Lechner, Watson, et. al; 2004).
  \textit{CityBuilder} construido sobre $NetLogo^{TM}$.
  Esta simulación describe comportamientos y semántica (local) con agentes que interactúan con su entorno.
  \begin{figure}
  \begin{center}
 		\includegraphics[width=4cm]{img/ejemplos_citybuilder.jpg}
  		\caption{Simulación de crecimiento con \textit{CityBuilder}}
  \end{center}
  \end{figure}
}
\frame
{ 
  \justifying
  \transsplitverticalin
  Los agentes base son los \textbf{agentes desarrolladores} quienes buscan extensiones de tierra urbanizables, cuando la encuentran ``proponen'' a la 
  ciudad su construcción y si ésta la autoriza (con base en sus restricciones), se compra la tierra y se construye o mejora la estructura previa.
  
  \begin{figure}
  \begin{center}
  		\includegraphics[width=5.5cm]{img/citybuilder_fases.jpg}
  		{\tiny \caption{ Una secuencia de fases de desarrollo. Arriba: uso de la tierra. Abajo: densidad de población}}
  \end{center}
  \end{figure}
}

%\subsection{Generación basada en plantillas}
%\frame
%{
%  \justifying
%  \transdissolve
%  \frametitle{Generación basada en plantillas}
%  Se basa en una plantilla con datos de población y plantillas simples para la red de caminos, estas plantillas se aplican a
%  un mapa geográfico y más tarde esta red se deforma atendiendo a restricciones locales (Sun, Yu, et. al.; 2002).
  
%  \begin{figure}
%  \begin{center}
%  		\includegraphics[width=3cm]{img/templates_caminos.jpg}
%  		\caption{Ejemplos de patrones para generación de caminos y los resultados obtenidos al aplicarlos}
%  \end{center}
%  \end{figure}
%}
%\subsection{Split grammars}
%\frame
%{
%  \justifying
%  \transboxin
%  \frametitle{\textit{Split grammars}}
%  Basadas en gramáticas de figuras (Stiny; 1980): gramática formal -no como un \textit{L-System} pues se encuentra 
%  basada en primitivas de figuras y no en símbolos. 
%  Los bloques básicos de construcción se basan en figuras parametri\-zadas y una etiqueta.
  
%  \begin{figure}
%  \begin{center}
%  		\includegraphics[width=2.8cm]{img/splitgrammars_pasos.jpg}
%  		\caption{Ejemplo de una \textit{split grammar} y su derivación completa}
%  \end{center}
%  \end{figure}
%}
%\frame
%{
%  \justifying
%  \transboxin
%  \frametitle{\textit{Split grammars}}
%  Se tiene una base de datos de entrada con aproximadamente 200 reglas y 40 atributos, toma alrededor de 2 semanas el ensamble para tener
%  gramáticas consistentes.
  
%  \begin{figure}
%  \begin{center}
%  		\includegraphics[width=4cm]{img/splitgrammars_ejemplos.jpg}
%  		\caption{Ciudad generada con \textit{split grammars}}
%  \end{center}
%  \end{figure}
%}

%\subsection{Otras tecnicas auxiliares}
%\frame
%{
%  \transdissolve
%  \frametitle{Otras tecnicas auxiliares}
%  \begin{itemize}\justifying
%  	\item \textbf{Fractales.} Objetos semigeométricos cuya estructura básica, fragmentada e irregular se repite a diferentes escalas;
%	usados en la generación de nubes, árboles, montañas.
	
%	 ``Las formas naturales tiende a ser irregulares y fragmentadas y exhiben una complejidad incomparable con la geometría
%	 regular'' (Mandelbrot; 1982).
%  \end{itemize}
%}

%\frame
%{
%  \transboxin
%  \frametitle{Otras tecnicas auxiliares}
%  \begin{itemize}\justifying
%  	\item \textbf{Funciones Perlin noise.} Ken Perlin (1982) para el filme Tron; suma de funciones \textit{noise} (funciones 
%	pseudo-aleatorias que generan una serie de valores que son interpolados en forma de ``ruido coherente''). A partir de ellas
%	se crean texturas de apariencia natural que tienen detalles fractales.
%  \end{itemize}
%}

\subsection{Autómatas celulares en modelado urbano}
\frame
{
  \transboxout
  \justifying
  \frametitle{AC's en urbanismo}
  ``La estructura espacial (que además es discreta) de ciudades reales hace que su representación como autómata celular
  sea natural'' (Mavroudi; 2007).
  
  Las propiedades de una unidad espacial (lote de terreno) se pueden determinar mediante el análisis de sus vecindades.
}
\frame
{
  \transdissolve
  \frametitle{Sistemas basados en reglas de urbanismo puro}
  \setbeamercovered{dynamic}
  \begin{itemize}\justifying
	\item Simuladores que generan ciudades hipotéticas. \pause
	\item Los resultados que generan pueden explicarse mediante reglas de urbanimo. \pause
	\item Usados para probar nuevas ideas sobre urbanismo. \pause
	\item Destacan los trabajos de Webster \& Wu, 1998 y 2002. \pause
  \end{itemize}
}

\frame
{
	\begin{figure}
	\begin{center}
		\includegraphics[width=4cm]{img/wu.jpg}
		\caption{Ejemplo de generación con el método de Webter \& Wu}
	\end{center}
	\end{figure}
}
\frame
{
  \transboxin
  \frametitle{Modelos de ciudades reales}
  \begin{itemize}\justifying
	\item Destacan los trabajos de Clarke \& Gaydos 1997 y 1998. Modelos para la Bahía de San Francisco y el corredor
	de Washington/Baltimore (E.U.A).	
  \end{itemize}
  
  \begin{figure}
	\begin{center}
		\includegraphics[width=3cm]{img/clarke_gaydos.jpg}
		\caption{Ejemplo de generación con el método de Clarke \& Gaydos}
	\end{center}
	\end{figure}
}

\frame
{
  \transboxout
  \frametitle{Modelos altamente restringidos}
  \setbeamercovered{dynamic}
  \begin{itemize}\justifying
	\item Modelos de planeación normativa. \pause
	\item Simulan patrones basados en objetivos. \pause
	\item Pueden ser evaluados para reunir ciertos criterios para desarrollo sustentable (Mavroudi; 2007). \pause
	\item Yeh \& Li 2002 y 2002, usan este tipo de modelos para generar formas urbanas monocéntricas y policéntricas. \pause
  \end{itemize}
}

\frame
{
	\begin{figure}
	\begin{center}
		\includegraphics[width=8cm]{img/yeh_li.jpg}
		\caption{Ejemplo de generación con el método de Yeh \& Li}
	\end{center}
	\end{figure}
}

%%%%%%%%%%%%%%%%%%%%%%%%%% Sección 3: Análisis del problema y propuesta de solución %%%%%%%%%%%%%%%%%%%%%%%%%% 
\section{Análisis del problema}
\frame
{
	\begin{center}
		\huge Análisis del problema
	\end{center}
}
\subsection{Modelo sistémico}
\frame
{
  \transdissolve
  \frametitle{Modelo sistémico}
  \begin{block}{Idea general}\justifying
  Modelar al objeto mediante la determinación de sus \textbf{componentes}, así como las \textbf{relaciones} entre ellos.
  Esas relaciones determinan la \textbf{estructura del objeto}.
  \end{block}
}
\subsection{La ciudad y sus componentes}
\frame
{
  \transboxin
  \frametitle{La ciudad y sus componentes}
  \begin{figure}
  \begin{center}
	\includegraphics[width=10cm]{img/modelo_sistemico.jpg}
  \end{center}
  \end{figure}
}

\section{Propuesta de solución}
\frame
{
	\begin{center}
		\huge Propuesta de solución
	\end{center}
}
\subsection{Modelo basado en autómata celular}
\frame
{
  \transboxout
  \frametitle{Modelo basado en autómata celular}
  \setbeamercovered{dynamic}
  \begin{itemize}\justifying
  \item \textbf{Espacio de evoluciones.} 2D por similitud con las extensiones de tierra. \pause
  \item \textbf{Conjunto de estados.} Cada lote del terreno -célula- puede tener 1 de 7 estados 
  que corresponden con el tipo de construcción. \pause
  	\begin{enumerate}
  		\item No urbanizado
  		\item Residencial
  		\item Empresarial
  		\item Comercial
  		\item Zona verde
  		\item Camino
  		\item Vacío
  	\end{enumerate}
  \end{itemize}
}

\frame
{
  \frametitle{Modelo basado en autómata celular}
  \setbeamercovered{dynamic}
  \begin{itemize}\justifying
	\item \textbf{Vecindad.} De Moore. \pause
	\item \textbf{Configuración inicial.} Imagen, texto plano o entrada directa. \pause
	\item \textbf{Función de transición.} Toma la vecindad de Moore y se aplica ite\-rativamente para 
  que la ciudad \textbf{evolucione} por $n$ \textbf{generaciones}. El estado de una célula se determina mediante 
  un \textbf{proceso de umbra\-lización} tomando las restricciones dadas por el usuario (restricciones de población).
  \pause
  \end{itemize}
}

\subsection{Representación de la ciudad como sistema complejo}
\frame
{
  \justifying
  \frametitle{Representación de la ciudad como sistema complejo}
  Artífice ve a la ciudad como un conjunto de células porciones de tierra.
  Como en todo sistema complejo \textbf{no interesa} estudiar cada lote por separado sino más bien \textbf{qué hacen en conjunto} (vecindades).
}
\subsection{Evolución y emergencia en el modelo}
\frame
{
  \justifying
  \transglitter
  \frametitle{Evolución y emergencia en el modelo}
  \setbeamercovered{dynamic}

  Artífice provee \textbf{evolución} dado que una ciudad \textbf{evoluciona} desde una configuración inicial $(t=0)$ hasta una configuración de \textbf{no evolución} $(t=n)$ con $n$ el número de generaciones.
  La evolución puede detenerse por dos factores:
  \begin{enumerate}\justifying
  \item Las restricciones impuestas ya no lo permiten (al evaluar la función de transición). \pause
  \item Se termina el terreno disponible. \pause
  \end{enumerate}
}

\frame
{
	\frametitle{Evolución y emergencia en el modelo}
  	\transglitter
  	\begin{figure}
  	\begin{center}
  		\includegraphics[width=9cm]{img/paro_por_no_terreno.jpg}
  		\caption{Ejemplos de no evolución}
  	\end{center}
  	\end{figure}

}

%%%%%%%%%%%%%%%%%%%%%%%%%% Sección 4: Implementación %%%%%%%%%%%%%%%%%%%%%%%%%% 
\section{Implementación}
\frame
{
	\begin{center}
		\huge Implementación
	\end{center}
}
\subsection{Metodología de desarrollo}
\subsection{Análisis Orientado a Objetos}
\frame
{
  \transboxin
  \frametitle{Análisis Orientado a Objetos}
  \setbeamercovered{dynamic}
  \begin{enumerate}
  \item Objetos \pause
  \item Relaciones \pause
  \item Comportamiento \pause
  \end{enumerate}
}

%\frame
%{
%  \transboxout
%  \frametitle{Ejemplos de casos de uso}
%  \begin{figure}
%  \begin{center}
%	\includegraphics[width=5cm]{img/casos_uso_aplicacion.jpg}
%	\caption{Casos de uso módulo principal}
%  \end{center}
%  \end{figure}
%}

\subsection{Diseño Orientado a Objetos}
\frame
{
  \transdissolve
  \frametitle{Diseño Orientado a Objetos}
  \begin{figure}
  \begin{center}
	\includegraphics[width=5cm]{img/flujo_doo.jpg}
	\caption{Flujo del proceso de diseño \textit{Orientado a Objetos}}
  \end{center}
  \end{figure}
}

\frame
{
  \transboxin
  \frametitle{Diseño Orientado a Objetos}
  \begin{figure}
  \begin{center}
	\includegraphics[width=5cm]{img/clases_model.jpg}
	\caption{Diagrama de clases del paquete \textit{ArtModel}}
  \end{center}
  \end{figure}
}

\frame
{
  \transboxout
  \frametitle{Diseño Orientado a Objetos}
  \begin{figure}
  \begin{center}
	\includegraphics[width=5cm]{img/clases_graphics.jpg}
	\caption{Diagrama de clases del paquete \textit{ArtGraphics}}
  \end{center}
  \end{figure}
}

\frame
{
  \transboxin
  \frametitle{Diseño Orientado a Objetos}
  \begin{figure}
  \begin{center}
	\includegraphics[width=5cm]{img/clases_view.jpg}
	\caption{Diagrama de clases del paquete \textit{ArtView}}
  \end{center}
  \end{figure}
}
\subsection{Visor 3D}
\frame
{
  \frametitle{Visor 3D}
  \transdissolve
  \begin{figure}
  \begin{center}
	\includegraphics[width=6cm]{img/prueba_ciudades.png}
	\caption{Ejemplo de ciudades en el visor 3D}
  \end{center}
  \end{figure}
}
\subsection{MEF para renderizado de ciudades}
\frame
{
  \frametitle{MEF para renderizado de ciudades}
  \transboxout
  \begin{figure}
  \begin{center}
	\includegraphics[width=5.5cm]{img/maquina_estados_dibujado_ciudad.jpg}
	\caption{Máquina de estados finitos para renderizado}
  \end{center}
  \end{figure}
}

\subsection{Renderizado por estado}
\frame
{
  \justifying
  \frametitle{Renderizado por estado}
  \transwipe
  Se tiene un edificio para cada estado (a excepción del estado residencial con cinco posibles edificios).
  \begin{figure}
  \begin{center}
	\includegraphics[width=12cm]{img/residencial_1_renderizado.jpg}
	\caption{Primer modelo de edificio para estado residencial}
  \end{center}
  \end{figure}
}

\frame
{
  \frametitle{Renderizado para estado residencial}
  \transboxout
  \begin{figure}
  \begin{center}
	\includegraphics[width=10cm]{img/residencial_2_renderizado.jpg}
	\caption{Segundo modelo de edificio para estado residencial}
  \end{center}
  \end{figure}
}

\frame
{
  \frametitle{Renderizado para estado residencial}
  \transwipe
  \begin{figure}
  \begin{center}
	\includegraphics[width=8cm]{img/residencial_3_renderizado.jpg}
	\caption{Tercer modelo de edificio para estado residencial}
  \end{center}
  \end{figure}
}

\frame
{
  \frametitle{Renderizado para estado residencial}
  \transboxin
  \begin{figure}
  \begin{center}
	\includegraphics[width=10cm]{img/residencial_4_renderizado.jpg}
	\caption{Cuarto modelo de edificio para estado residencial}
  \end{center}
  \end{figure}
}

\frame
{
  \frametitle{Renderizado para estado residencial}
  \transwipe
  \begin{figure}
  \begin{center}
	\includegraphics[width=8cm]{img/residencial_5_renderizado.jpg}
	\caption{Quinto modelo de edificio para estado residencial}
  \end{center}
  \end{figure}
}
\frame
{
  \frametitle{Renderizado para estado empresarial}
  \transboxout
  \begin{figure}
  \begin{center}
	\includegraphics[width=7cm]{img/empresarial_renderizado.jpg}
	\caption{Modelo de edificio para estado empresarial}
  \end{center}
  \end{figure}
}

\frame
{
  \frametitle{Renderizado para estado comercial}
  \transboxin
  \begin{figure}
  \begin{center}
	\includegraphics[width=8cm]{img/comercial_renderizado.jpg}
	\caption{Modelo de edificio para estado comercial}
  \end{center}
  \end{figure}
}

\frame
{
  \frametitle{Renderizado para estado zona verde}
  \transboxin
  \transwipe
  \begin{figure}
  \begin{center}
	\includegraphics[width=6cm]{img/zverde_renderizado.jpg}
	\caption{Modelo para estado zona verde}
  \end{center}
  \end{figure}
}

\frame
{
  \frametitle{¿Por qué OpenGL?}
  \transsplithorizontalin
  \setbeamercovered{dynamic}
  
  \begin{enumerate}\justifying
	\item Interfaz directa con el hardware. \pause
	\item Programación ``desde cero'' implementación tan eficiente como se requiera. \pause
	\item Estándar a nivel mundial para generación de aplicaciones 3D. \pause
	\item Estándar abierto (se puede contribuir a su desarrollo). \pause
	\item Independiente del hardware. \pause
	\item Multiplataforma (Shreiner; 2010). \pause
  \end{enumerate}
}

\subsection{Técnicas avanzadas de graficado por computadora}
\frame
{
  \frametitle{Técnicas avanzadas de graficado por computadora}
  \transdissolve
  \setbeamercovered{dynamic}
  \begin{itemize}
  \item Manejo de nivel de detalle. \pause
  \item Uso de \textit{display lists}. \pause
  \end{itemize}
  \begin{figure}
	\begin{center}
	\includegraphics[width=6cm]{img/lod_conejo.jpg}
	\caption{Ejemplo de manejo de nivel de detalle}
	\end{center}
  \end{figure}
}
\subsection{Artífice como un rompecabezas}
\frame
{
	\frametitle{Habitantes}
	\transdissolve

	Dos clases de población:
	\begin{enumerate}
	\item Pob. productora
	\item Pob. consumidora
	\end{enumerate}
}
\frame
{
   \justifying
	\frametitle{Construcciones}
	\transboxin
	Diversos tipos dependiendo del estado de la célula actual. En visor 2D se representan con colores.
	\begin{figure}
	\begin{center}
		\includegraphics[width=3.8cm]{img/codigo_colores_por_estado.jpg}
		\caption{Colores propuestos para la versión 2D de \textit{Artífice}}
	\end{center}
	\end{figure}
}
\frame
{
   \justifying
	\frametitle{Vialidades}
	\transboxout
	La red de caminos se toma como una cuadrícula estática (puede darse con una imagen).
}

\frame
{
   \justifying
	\frametitle{Terreno}
	\transsplithorizontalout

	La versión inicial es de 100 lotes por lado en un \textit{grid}. Cada lote tiene una extensión de $100 m$ por lado.
	Cuando se carga una imagen el terreno se toma del tamaño de ésta (w,h).
	
	\begin{figure}
	\begin{center}
		\includegraphics[width=5cm]{img/terreno_artifice.jpg}
		\caption{Terreno de \textit{Artífice}}
	\end{center}
	\end{figure}	
}
\frame[allowframebreaks]
{
	\frametitle{Entrada}
	\transboxout
	\begin{itemize}
	 \item Archivos de texto.
	 \item Imagenes (PNG, JPEG, BMP,...).
	\end{itemize}
	\begin{figure}
	\begin{center}
		\includegraphics[width=4cm]{img/ejemplo_arch_entrada_y_mapa.jpg}
		\caption{Ejemplo de archivo de texto de entrada}
	\end{center}
	\end{figure}

	\begin{figure}
	\begin{center}
		\includegraphics[width=10cm]{img/ejemplo_mapa_entrada_evolucion.jpg}
		\caption{Ejemplo de mapa de entrada y su evolución}
	\end{center}
	\end{figure}
}
%%%%%%%%%%%%%%%%%%%%%%%%%% Sección 4: Resultados obtenidos %%%%%%%%%%%%%%%%%%%%%%%%%% 
\section{Resultados obtenidos}
\frame
{
	\begin{center}
		\huge Resultados obtenidos
	\end{center}
}
%\subsection{Pruebas Orientadas a Objetos}
%\frame
%{
%  \justifying
%  \frametitle{Pruebas Orientadas a Objetos}
%  \transboxin

%  ``Cada reutilización es un nuevo contexto de uso y es prudente repetir las pruebas. Parece probable que se necesitarán
%  menos pruebas para obtener una alta fiabilidad en sistemas orientados a objetos'' (Binder; 1994).
  
%  Para \textit{Artífice} se han realizado pruebas para las todas las clases, un ejemplo de ejecución se muestra enseguida:
%  \begin{figure}
%	\begin{center}
%		\includegraphics[width=6cm]{img/diagrama_prueba_ac.jpg}
%		\caption{Diagrama de ejecución de pruebas para la clase \textit{CAutomataCelular}}
%	\end{center}
%	\end{figure}
%}
\subsection{Ejemplos de ejecución}
\frame[allowframebreaks]
{
  \frametitle{Ejemplos de ejecución}
  \begin{table}[!hbt]
	\begin{center}
		\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}
			\hline
			RC   & RE & RZV & No. Gen. \\   %& NU   & Res.  & Empres. 	 & Comer & Z. Verde & Pob.  \\
			\hline
			100  & 18 & 10  & 57 		\\  %& 9630 & 292	 &    40	 &   6	 &  32      & 1476  \\
			330  & 20 & 15  & 296 		\\  %& 8173 & 1481	 &    156	 &   11	 &  179     & 7304  \\
			495  & 20 & 20  & 298 		\\  %& 4705 & 4342	 &    468	 &   20	 &  465     & 21176 \\
			625  & 16 & 16  & 656 		\\  %& 6654 & 2703	 &    376	 &   10	 &  257     & 13380 \\
			692  & 18 & 20  & 210 		\\  %& 8811 & 969	 &    117	 &   3	 &  100     & 4752  \\
			725  & 25 & 25  & 301 		\\  %& 3557 & 5422	 &    456	 &   14	 &  551     & 25768 \\
			825  & 20 & 16  & 151 		\\  %& 9199 & 652	 &    77	 &   1 	 &  71      & 3200  \\
			856  & 20 & 25  & 397 		\\  %& 4369 & 4657	 &    526	 &   11	 &  437     & 22520 \\
			1054 & 22 & 35  & 273 		\\  %& 463  & 8007	 &    803	 &   17	 &  710     & 38144 \\
			1054 & 30 & 40  & 221 		\\  %& 88   & 8553	 &    612	 &   17	 &  730     & 39644 \\
			\hline
		\end{tabular}
		\caption{Estadísticas de diez ciudades con restricciones variables}
		\label{tabla-ejecuciones}
	\end{center}
	\end{table}
		
	\textbf{Acotaciones:}
	\begin{itemize}\justifying
		\item \textbf{RC.} Restricción en zonas comerciales.
		\item \textbf{RE.} Restricción en zonas empresariales.
		\item \textbf{RZV.} Restricción en zonas verdes.
		\item \textbf{No. Gen.} Número de generaciones hasta el estado de no evolución.
		%\item \textbf{NU.} Número de zonas no urbanizadas.
		%\item \textbf{Res.} Número de edificios de tipo residencial.
		%\item \textbf{Empres.} Número de edificios de tipo empresarial.
		%\item \textbf{Comer.} Número de edificios de tipo comercial.
		%\item \textbf{Z. Verde.} Número de zonas verdes.
		%\item \textbf{Pob.} Población total.
	\end{itemize}
}

\frame
{
  \transdissolve
  \frametitle{Ejemplos de ejecución}
  \begin{figure}
	\begin{center}
		\includegraphics[width=6cm]{img/prueba_ciudad_1.jpg}
		\caption{Primera ciudad arbitraria en \textit{Artífice}}
	\end{center}
	\end{figure}
}
\frame
{
  \transboxin
  \frametitle{Ejemplos de ejecución}

  \begin{figure}
	\begin{center}
		\includegraphics[width=6cm]{img/prueba_ciudad_2.jpg}
		\caption{Segunda ciudad arbitraria en \textit{Artífice}}
	\end{center}
	\end{figure}
}

\frame
{
  \transdissolve
  \frametitle{Ejemplos de ejecución}
  \begin{figure}
	\begin{center}
		\includegraphics[width=12cm]{img/prueba_ciudad_2b.jpg}
		\caption{Tercera ciudad arbitraria en \textit{Artífice}}
	\end{center}
	\end{figure}
}

\subsection{Alcances y limitaciones}
\frame
{
  \transdissolve
  \frametitle{Alcances}
  \setbeamercovered{dynamic}
  \begin{enumerate}\justifying
	\item<1-> Modelo de autómata celular para generación de ciudades hipotéticas
	\item<2-> Implementación sistémica
	\item<3-> Simulación de ocupación del terreno
	\item<4-> Incluye un visor 3D
	\item<5-> Posibilidad de imágenes y archivos de texto plano como entrada
	\item<6-> Siete posibles estados por célula (lote)
	\item<7-> Control paramétrico de reglas de transición
	\item<8-> Manejo de 2 niveles de detalle para estado residencial
	\item<9-> Permite analizar crecimiento poblacional por generación
	\item<10-> Implementación \textit{Orientada a Objetos}
  \end{enumerate}
}
\subsection{Limitaciones del software}
\frame
{
  \transdissolve
  \frametitle{Limitaciones del sofware}
  \setbeamercovered{dynamic}
  \begin{enumerate}\justifying
	\item<1-> Particionado del terreno
	\item<2-> Número de estados
	\item<3-> Modificación de estados ya establecidos
	\item<4-> No se utilizan agentes que interactúen con su entorno
	\item<5-> Plataforma de desarrollo
  	\item<6-> Sólo se toman siete estados
  \end{enumerate}
}

\subsection{Limitaciones del visor 2D y 3D}
\frame
{
  \transdissolve
  \frametitle{Limitaciones del visor 2D y 3D}
  \setbeamercovered{dynamic}
  \begin{enumerate}
	\item<1-> Colores
	\item<2-> Número de estados
	\item<3-> Agregar soporte para \textit{CUDA}
	\item<4-> Uso de \textit{shaders GLSL ó HLSL}
	\item<5-> Generación de multivariedad de construcciones por estado
  	\item<6-> Texturizado de vialidades
  	\item<7-> Objetos móviles: autos, camiones, aviones, etc.
	\item<8-> Renderizado de los habitantes
  \end{enumerate}
}
\section{Conclusiones}
\frame
{
	\begin{center}
		\huge Conclusiones
	\end{center}
}
\subsection{Conclusiones y perspectivas}
\frame
{
  \transboxin
  \frametitle{Conclusiones y perspectivas}
  \setbeamercovered{dynamic}
	\begin{itemize}\justifying
	  \item<1-> \textit{Artífice} proporciona una forma alternativa de estudiar el crecimiento de ciudades.
	  \item<2-> La generación se encuentra basada en autómatas celulares bidimensionales cuya implementación no es muy compleja.
	  \item<3-> La función de transición aplica reglas simples que producen patrones complejos.
	  \item<4-> \textit{Artífice} brinda la posibilidad de ver la evolución de una ciudad en términos de la ocupación de su terreno y
	  su número de habitantes.
	\end{itemize}
}

\frame
{
  \transboxout
  \frametitle{Conclusiones y perspectivas}
  \setbeamercovered{dynamic}
	\begin{itemize}\justifying
	  \item<1-> Se ha implementado un visor 3D sobre C++, utilizando OpenGL. El visor ha sido optimizado con manejo de nivel de detalle
	  y uso de \textit{display lists}.
	  \item<2-> La metodología de desarrollo se basa en Ingeniería \textit{Orientada a Objetos} lo que asegura la reutilización de
	  componentes.
	  \item<3-> Faltan aspectos por mejorar, pero con tiempo y esfuerzo \textit{Artífice} será una buena herramienta para los propósitos 
	  que fue construido.
	\end{itemize}
}
\subsection{Referencias}
\frame[allowframebreaks]
{
  \frametitle{Referencias}
  \begin{enumerate}
  \item \textbf{Peter M. Allen}, \textit{Cities and Regions as Self-Organizing Systems Models of Complexity}. Taylor \& Francis e-Library. 1997.
  \item \textbf{Michael Batty}, \textit{Fractal Cities. A Geometry of Form and Function}. Academic Press. Harcourt Brace \& Company, Publishers. 1994.
  \item \textbf{Andrew Ilachinski}, \textit{Cellular Automata, A Discrete Universe}. World Scientific Publishing. 2001.
  \item \textbf{Luke Benstead, Dave Astle And Kevin Hawkins}, \textit{Beginning OpenGL. Game Programming-Second Edition}. 
  Course Technology. CENGAGE Learning. 2009.
  \item \textbf{Roger S. Pressman}, \textit{Ingeniería del Software. Un enfoque práctico}. Mc Graw Hill. 2001.
  \item \textbf{Carlos Gershenson}, \textit{Enfrentando a la Complejidad: Predecir vs. Adaptar}. Cornell University Library. 1991.
  \item \textbf{P. V. Coveney}, \textit{Self-Organization and Complexity: A New Age for Theory, Computation and Experiment}.
  Proceedings of the Nobel Symposium on Self-Organization. 2003.
  \item \textbf{George Kelly \& Hugh McCabe}, \textit{A survey of Procedural Techniques for City Generation}. ITB Journal. 2003.
  \item \textbf{Yoav Parish \& Pascal M\"{u}ller}, \textit{Procedural Modeling of Cities}. ACM SIGGRAPH, Los Angeles, CA, USA. 2001.
  \item \textbf{Michael Batty \& Paul A. Longley}, \textit{Urban shapes as fractals}. Area, volumen 19.3, 1987.
  \item \textbf{Stefan Greuter, Jeremy Parker, Nigel Stewart \& Geoff Leach}, \textit{Real-time Procedural Generation of 'Pseudo Infinite' Cities}.
  RMIT University, Melbourne, Victoria, Australia.
  \item \textbf{Carlos Gershenson and Francis Heylighen}, \textit{How can we think the complex?}.
  Richardson, Kurt (ed.) Managing the Complex: Philosophy, Theory and Application. 2004.
  \item \textbf{Paul Cilliers}, \textit{Complexity \& Postmodernism Understanding Complex Systems}. Taylor \& Francis e-Library. 2002.
  \item \textbf{Kate Ascher}, \textit{Anatomy of a City}. The Penguin Press. 2005.
  \end{enumerate}
}

\frame
{
   \transboxin
	\frametitle{¿Mejor ya el \textit{Age} no?}
	\begin{center}
		\Huge{¡Gracias!}
	\end{center}
}

\end{document}
