jueves, 23 de febrero de 2012

2. Transformaciones geométricas

Un paquete gráfico permite al usuario especificar que parte de una imagen definida se debe visualizar y dónde esta parte se debe colocar en el dispositivo de visualización. Cualquier sistema de coordenadas que sea conveniente, referido al sistema de referencia de coordenadas del mundo, se puede usar para definir la imagen.

2.1. Transformaciones bidimensionales Traslación
Se aplica una traslación en un objeto para cambiar su posición a lo largo de la trayectoria de una línea recta de una dirección de coordenadas a otra. Convertimos un punto bidimensional al agregar las distancias de traslación, tx y ty a la posición de coordenadas original (x ,y) para mover el punto a una nueva posición (x’, y’).
Los polígonos se trasladan al sumar el vector de traslación a la posición de coordenadas de cada vértice y se vuelve a generar el polígono utilizando un nuevo conjunto de coordenadas y vértices y las especificaciones actuales de los atributos.

Rotación
Se aplica una rotación bidimensional en un objeto al cambiar su posición a lo largo de la trayectoria de una circunferencia en el plano de xy  para generar una rotación, especificamos un ángulo de rotación θ y la posición (xr , yr) del punto de rotación (o punto pivote) en torno al cual se gira el objeto.

2.2. Coordenadas homogéneas y representación matricial
En las aplicaciones de diseño y de creación de imágenes, realizamos traslaciones, rotaciones y  escalaciones para ajustar los componentes de la imagen en sus posiciones apropiadas. En este tema consideramos cómo se pueden volver a formular las representaciones de la matriz de modo que se pueden procesar de manera eficiente esas secuencias de transformación.

2.3. Composición de transformaciones bidimensionales Traslaciones
Se se aplican dos vectores de traslación sucesivos (t x1, ty1) y (t x2 , t y2 ) en la posición de coordenadas P, la localización transformada final P, la localización transformada final P’se calcula como:
donde se representan P y P’ como vectores de columna de coordenadas homogéneas. Podemos verificar este resultado al calcular el producto de la matriz para las dos agrupaciones asociativas. Asimismo, la matriz de transformación compuesta para esta secuencia de transformaciones es:
que demuestra que dos transformaciones sucesivas son aditivas.

Rotaciones
Dos rotaciones sucesivas que se aplican en el punto P producen la posición transformada
Al multiplicar las dos matrices de rotación, podemos verificar que dos rotaciones sucesivas son aditivas:
de modo que es posible calcular las coordenadas giradas finales con la matriz de rotación compuesta como

Escalaciones
Concatenar matrices de transformación para dos operaciones de escalación sucesivas produce la siguiente matriz de escalación compuesta:

La matriz resultante en este caso indica que las operaciones de escalación sucesivas son multiplicativas. Es decir, si debiéramos triplicar el tamaño de un objeto dos veces en una sucesión, el tamaño final sería nueve veces el tamaño original.

Rotación del punto pivote general
Con un paquete gráfico que sólo ofrezca una función de rotación para girar objetos con respecto del origen de las coordenadas, podemos generar casi cualquier punto pivote seleccionado (x r , y r ) al realizar la siguiente secuencia de operaciones de traslación-rotación-traslación:
1. Traslade el objeto de modo que se mueva la posición del punto pivote al origen de  las coordenadas.
2. Gire el objeto con respecto del origen de las coordenadas.
3. Traslade el objeto de manera que se regrese el punto pivote a su posición original.


Escalación del punto fijo general
La siguiente figura ilustra una secuencia de transformación para producir escalación con respecto de una posición fija seleccionada (x f , y f ) al utilizar una función de escalación que sólo puede escalar en relación con el origen de las coordenadas.

1. Traslade el objeto de modo que el punto fijo coincida con el origen de las coordenadas.
2. Escale el objeto con respecto del origen de las coordenadas
3. Utilice la traslación inversa del paso 1 para regresar el objeto a su posición original.

Propiedades de concatenación
La multiplicación de matrices es asociativa. Para tres matrices cualesquiera A, B y C, el producto matricial A·B·C se puede llevar a cabo al multiplicar primero a por B o multiplicar primero B por C:
A·B·C =(A·B)·C =A·(B·C )

2.4.Transformación ventana-área de vista
Algunos paquetes gráficos permiten que el programador especifique coordenadas de primitivas de salida en un sistema de coordenadas de mundo de punto flotante, usando las unidades que sean relevantes para el programa de aplicación: angstroms, micras, metros, millas, años luz, etcétera. Se emplea el término de mundo porque el programa de aplicación representa un mundo que se crea o presenta interactivamente para el usuario:
Como las primitivas de salida se expresan en coordenadas de mundo, hay que indicar al paquete de subrutinas gráficas cómo establecer la correspondencia entre las coordenadas de mundo y las coordenadas de pantalla (usaremos el término específico coordenadas de pantalla para relacionar este análisis específicamente con SRGP, pero podrían usarse dispositivos de impresión, en cuyo caso sería más apropiado el término coordenadas de dispositivo).

2.5.Transformaciones de composición general y de eficiencia computacional
Una transformación bidimensional general, que representa una combinación de traslaciones, rotaciones y escalaciones. Solo necesitamos efectuar cuatro multiplicaciones y cuatro adiciones para transformar las posiciones de las coordenadas. Este es el número máximo de cálculos que se requieren para cualquier secuencia de transformación, una vez que se han concatenado las matrices individuales y evaluadas los elementos de la matriz compuesta. Sin concatenación, se aplicarían las transformaciones individuales una a la vez y se podría reducir en forma considerable el número de cálculos. De esta manera, una implementación eficiente de las operaciones de transformación consiste en formular matrices de transformación, concatenar cualquier secuencia de transformación y calcular las coordenadas transformadas

2.6.Representación matricial de transformaciones tridimensionales
Así como las transformaciones bidimensionales se pueden representar con matrices de3 X 3 usando coordenadas homogéneas, las transformaciones tridimensionales se pueden representar con matrices de 4 X 4, siempre y cuando usemos representaciones de coordenadas homogéneas de los puntos en el espacio tridimensional. Así, en lugar de representar un punto como (x, y, z ), lo hacemos como (x, y, z, W ), donde dos de estos cuádruplos representan el mismo punto si uno es un multiplicador distinto de cero del otro: no se permite el cuádruplo (0, 0, 0, 0). Como sucede en el espacio bidimensional, la representación estándar de un punto (x, y, z, W ) con W ≠ 0 se indica (x/W, y/W, z/W, 1).

2.7.Composición de transformaciones tridimensionales
El objetivo es transformar los segmentos de línea dirigida P1P2 y P1P3 en la figura 2.18 de su posición inicial en la parte (a) a su posición final en la parte (b). De esta manera, el punto P1 se trasladará al origen P 1P2 quedará en el eje positivo y P 1P3 quedará en la mitad del eje positivo del plano (x, y ). Las longitudes de las líneas no se verán afectadas por la transformación. Se presentan dos formas de lograr la transformación deseada. El primer método es componer las transformaciones primitivas T , R x , Ry y Rz . Este método, aunque es algo tedioso, es fácil de ilustrar y su comprensión nos ayudará en nuestro conocimiento de las transformaciones. El segundo método, que utiliza las propiedades de las matrices ortogonales especiales que se analiza en la sección anterior, se explica de manera mas breve pero es más abstracto.

Glosario Unidad 2: Transformaciones

Coordenadas Geométricas:  son un instrumento usado para describir un punto en el espacio proyectivo.  Pueden usarse como un sistema alternativo de coordenadas para trabajar en el espacio euclídeo, pues éste puede verse como un subconjunto del espacio proyectivo. De ese modo, las coordenadas homogéneas son ampliamente usadas en infografía para la representación de escenas en tres dimensiones.

Stack: Es una lista ordinal o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos. Esta estructura se aplica en multitud de ocasiones en el área de informática debido a su simplicidad y ordenación implícita de la propia estructura.

lunes, 20 de febrero de 2012

2.1 Trazo de líneas rectas y 2.2 Representación y trazo de polígonos

DDA

El analizador diferenciador digital (DDA - Digital Differential Analyzer) es un algoritmo de conversión de rastreo que se basa en el calculo ya sea de Dy o Dx por medio de las ecuaciones:

(4) Dy = m Dx

(5) Dx = Dy / m

Se efectúa un muestreo de la línea en intervalos unitarios en una coordenada y se determina los valores enteros correspondientes mas próximos a la trayectoria de la línea para la otra coordenada.

Tomemos una línea con pendiente positiva, si la pendiente | m | £ 1, se hace el muestreo en x en intervalos unitarios (Dx = 1 y Dy = m dado que m = Dy / Dx) y se calcula cada valor sucesivo de y como:

(6) yk+1 = yk+ m

El subíndice toma valores enteros a partir de 1 y aumenta a razón de 1 hasta alcanzar el valor final.

Ya que m puede ser cualquier numero real entre 0 y 1, los valores calculados de y deben redondearse al entero mas cercano. Para líneas con una pendiente | m | > 1, se revierten las funciones de x y y, o sea, se realiza un muestreo de y en intervalos unitarios (Dy = 1 y Dx = 1/m dado que m = Dy / Dx) y se calcula cada valor sucesivo de x como:

(7) xk+1 = xk+ 1/m

Las ecuaciones (6) y (7) se basan en la suposición de que las líneas deben procesarse del extremo izquierdo al derecho.

Si este procesamiento se revierte, entonces Dx o Dy serian -1, y   yk+1 = yk - m o xk+1 = xk - 1/m



Algoritmo de Bresenham para trazar líneas

Un algoritmo preciso y efectivo para la generación de líneas de rastreo, desarrollado por Bresenham (1965), convierte mediante rastreo las líneas utilizando solo cálculos incrementales con enteros que se pueden adaptar para desplegar también curvas.

El algoritmo busca cual de dos pixeles es el que esta mas cerca según la trayectoria de la línea.

Consideremos el proceso de conversión para líneas con pendiente positiva 0 < m < 1.

Las posiciones de pixel a lo largo de la trayectoria de una línea se determinan al efectuar un muestreo de x en intervalos unitarios.

Si se inicia desde el extremo izquierdo (x0,y0) de una línea determinada, se pasa a cada columna sucesiva y se traza el pixel cuyo valor de y se aproxima mas a la trayectoria de la línea de rastreo.

Si suponemos que se debe desplegar el pixel en (xk,yk), a continuación se necesita decidir que pixel se debe desplegar en la columna xk+1.

Las alternativas son los pixeles (xk+1,yk), y (xk+1,yk+1).

Al realizar el muestreo en la posición xk+1 designamos la separación de pixeles verticales de la trayectoria de la línea matemática como d1 y d2.



La coordenada de y en la línea matemática en la posición de la columna de pixel xk+1 se calcula como:

(10) y = m (xk + 1) + b

Entonces

d1 = y - yk = m (xk + 1) + b yk                  y               d2 = (yk + 1) - y = yk + 1 - m (xk + 1) - b

La diferencia entre estas dos separaciones es

(11) d1 - d2 = 2 m (xk + 1) - 2 yk + 2 b - 1

Un parámetro de decisión pk para el paso k en el algoritmo de línea se puede obtener al reordenar la ecuación anterior, de modo que implique solo cálculos de enteros.

Esto se logra sustituyendo m = Dy / Dx donde Dx y Dy son las separaciones horizontal y vertical de las posiciones de los extremos de la línea y al definir:

(12) pk = Dx (d1 - d2) = Dx (2 Dy / Dx (xk + 1) - 2 yk + 2 b - 1)

= 2 Dy xk - 2 Dx yk + 2 Dy + 2 b Dx - Dx

= 2 Dy xk - 2 Dx yk + c

El signo de pk es el mismo que el de d1 - d2 puesto que Dx > 0 en el ejemplo.

El parámetro c es un constante, donde c = 2 Dy + 2 b Dx - Dx, que es independiente del pixel.

Si el pixel yk esta mas cerca de la trayectoria de la línea que el pixel yk + 1 (es decir d1 < d2), entonces el parámetro de decisión pk es negativo.

En ese caso, trazamos el pixel inferior; de otro mode, trazamos el pixel superior.

Los cambios de coordenadas a lo largo de la línea ocurren en pasos unitarios ya sea en la dirección de x o en la de y.

Por tanto, es posible obtener los valores de parámetros de decisión sucesivos al utilizar cálculos incrementales en enteros. En el paso k + 1, el parámetro de decisión se evalúa con base en la ecuación anterior como:

pk+1 = 2 Dy xk+1 - 2 Dx yk+1 + c

Al sustraer la ecuación (12) de la anterior obtenemos

pk+1 - pk = 2 Dy (xk+1 - xk) - 2 Dx( yk+1 - yk)

Pero xk+1 = xk + 1, de manera que

(13) pk+1 = pk + 2 Dy - 2 Dx( yk+1 - yk)

donde el termino yk+1 - yk es 0 o 1, dependiendo del signo del parámetro p. Este calculo recurso de los parámetros de decisión se realiza en cada posición entera de x, empezando en el extremo izquierdo de las coordenadas de la línea. El primer parámetro p0 se evalúa a partir de la ecuación (12) en la posición del pixel inicial (x0,y0), sustituyendo

con b = y0 - m x0 y m = Dy / Dx.

p0 = Dx (2 Dy / Dx(x0 + 1) - 2 y0 + 2 (y0 - (Dy / Dx) x0) - 1)

= 2 Dy x0 + 2 Dy - 2 Dx y0 + 2 Dx y0 - 2 Dy x0 - Dx

donde se obtiene la siguiente ecuación:

(14) p0 = 2 Dy - Dx

En resumen, los pasos son:

1. Se capturan los dos extremos de la línea y se almacena el extremo izquierdo en (x0,y0).

2. Se carga (x0,y0) en el bufer de estructura, o sea, se traza el primer punto.

3. Se calculan las constantes Dy, Dx, 2Dy, 2Dy-2Dx, y se obtiene el valor inicial para el parámetro de decisión como p0 = 2 Dy - Dx.

4. En cada xk a lo largo de la línea, que inicia en k = 0, se efectúa la prueba siguiente: si pk < 0, el siguiente punto que se debe trazar es (xk+1,yk) y pk +1 = pk + 2 Dy. De otro modo, el siguiente punto en trazarse es (xk+1,yk+1)

y pk +1 = pk + 2 Dy - 2Dx.

5. Se repite el paso 4 otras Dx veces.






















Referencias
http://cannes.itam.mx/Alfredo/Espaniol/Cursos/Grafica/Linea.pdf
http://arantxa.ii.uam.es/~pedro/graficos/teoria/Primitivas/Primitivas.htm

jueves, 16 de febrero de 2012

Cubo en 2 dimensiones con OpenGL

Código del programa
#include <GL/glut.h>

void myinit(void)
{
      glClearColor(0.0, 1.0, 5.0, 1.0);
      glColor3f(1.0, 0.0, 3.0); 
      glMatrixMode(GL_PROJECTION);
      glLoadIdentity();
      gluOrtho2D(0.0, 500.0, 0.0, 500.0);
      glMatrixMode(GL_MODELVIEW);
}


void display( void )
{

    typedef GLfloat point2[2];     

point2 verticesc[8]={{50.0,50.0},{250.0,50.0},{250.0,250.0},{50.0,250.0},
{150.0,150.0},{350.0,150.0},{350.0,350.0},{150.0,350.0}}; /* Cuadrado aristas */


    glClear(GL_COLOR_BUFFER_BIT);

glBegin(GL_LINES);


    glVertex2fv(verticesc[0]);
glVertex2fv(verticesc[1]);
glVertex2fv(verticesc[1]);
glVertex2fv(verticesc[2]);
glVertex2fv(verticesc[2]);
glVertex2fv(verticesc[3]);
glVertex2fv(verticesc[3]);
glVertex2fv(verticesc[0]);
glVertex2fv(verticesc[0]);
glVertex2fv(verticesc[4]);
glVertex2fv(verticesc[4]);
glVertex2fv(verticesc[5]);
glVertex2fv(verticesc[5]);
glVertex2fv(verticesc[6]);
glVertex2fv(verticesc[6]);
glVertex2fv(verticesc[7]);
glVertex2fv(verticesc[7]);
glVertex2fv(verticesc[3]);
glVertex2fv(verticesc[7]);
glVertex2fv(verticesc[4]);
glVertex2fv(verticesc[6]);
glVertex2fv(verticesc[2]);
glVertex2fv(verticesc[5]);
glVertex2fv(verticesc[1]);
   
glEnd();

     glFlush(); 
 }


void main(int argc, char** argv)
{
    glutInit(&amp;argc,argv);
    glutInitDisplayMode (GLUT_SINGLE | GLUT_RGB); 
    glutInitWindowSize(500,500); 
    glutInitWindowPosition(0,0); 
    glutCreateWindow("Cubo 2D");
    glutDisplayFunc(display); 


    myinit();


    glutMainLoop();
}


Corrida del programa






martes, 14 de febrero de 2012

Dimensión Fractal

El concepto de dimensión en los fractales como consecuencia de la recursividad o autosimilitud a cualquier escala que poseen es algo muy complejo. Los fractales están compuestos por elementos cada vez más pequeños de sí mismos que se replican indefinidamente a menor escala, generándose una figura que tiene una superficie finita con un perímetro de longitud infinita y con un número infinito de vértices. En el lenguaje matemático del cálculo, diríamos que esta curva no se puede diferenciar.



Dimensión Minkowski-Bouligand

En la geometría fractal , la dimensión de Minkowski-Bouligand , también conocida como la dimensión de Minkowski o la dimensión de conteo de recuadros , es una manera de determinar la dimensión fractal de un conjunto S en un espacio euclidiano R n , o, más generalmente en un espacio métrico ( X ,  d ).



Dimensión de Hausdorff-Besicovitch

La dimensión de Hausdorff o dimensión de Hausdorff-Besicovitch es una generalización métrica del concepto de dimensión de un espacio topológico, que permite definir una dimensión fraccionaria (no-entera) para un objeto fractal.

 
Dimensión topológica

Normalmente consideramos que los puntos tienen dimensión 0, las líneas 1, las superficies 2 y los volúmenes 3. A esta idea de dimensión se le llama dimensión topológica.


Ejemplos de fractales
  Conjunto de Mandelbrot


Conjunto de julia



Conjunto de koch


Técnicas para generar fractales
Sistema iterativo de funciones.
Un sistema iterativo de funciones (SIF o IFS acrónimo del inglés Iterated function system) es una construcción matemática usada para representar de manera simple ciertos conjuntos fractales que presenten autosimilaridad. Muchos fractales clásicos autosimilares, autoafines y autoconformes pueden representarse como el único conjunto compacto invariante por un sistema iterativo de funciones contractivas.
Alfombra de Sierpinski

Conjunto de cantor




 Triangulo de Siernpinski


Curva de Peano




Curva del dragon



Copo de koch


Esponja de Menger

Fractales de algoritmo de escape
El algoritmo de tiempo de escape es uno de los más antiguos y para muchos programas fractales la única opción disponible. Este algoritmo está basado en el número de iteraciones necesario para determinar si la secuencia iterada por el sistema dinámico tiende a infinito o no.
Fractal de Lyapunov

Fractales aleatorios
Son generados por procesos estocásticos. Por ejemplo: Paisajes de fractal.
Paisajes fractales

Sistema estocástico
Un sistema estocástico es aquel que funciona mayormente por azar. Se trata pues de un algoritmo matemático que trata los procesos cuya evolución es aleatoria y que basa su resultado en probabilidades que cambian con el tiempo. El hecho de que los cálculos de probabilidades varíen con el tiempo es la diferencia con un modelo probabilístico no estocástico.


Referencias: