lunes, 27 de febrero de 2012

Transformaciones geométricas




Objetivo. El estudiante conocerá y aplicará las principales transformaciones geométricas sobre objetos en 2D y 3D.

Las transformaciones geométricas básicas son la traslación, la rotación y la escalación. La traslación mueve un objeto con una trayectoria en línea recta de una posición a otra. La rotación mueve un objeto de una posición a otra a lo largo de una trayectoria circular sobre un eje de rotación específico.

Cualquier sistema de coordenadas que sea conveniente, referido al sistema de referencia de coordenadas del mundo, se puede usar para definir la imagen. En el caso de las imágenes bidimensionales, una vista se selecciona especificando una región del plano xy que contiene la imagen total o cualquier parte de ella.

Las partes dentro de las zonas seleccionadas se mapean entonces sobre zonas especificadas de las coordenadas del dispositivo. Cuando se seleccionan múltiples zonas de vista, estas zonas se pueden colocar en ubicaciones de visualización independientes, o algunas zonas se podrían insertar en zonas de visualización más grandes.

2.1. Transformaciones bidimensionales Traslación

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’).

2.1.                                      x’ = x + tx’                                          y’ = y + ty

El par de distancia de traslación (tx’, ty) se llama vector de traslación o vector de cambio.

Se pueden expresar las ecuaciones anteriores en una sola ecuación matricial al utilizar vectores de columna para representar las posiciones de coordenadas y el vector de traslación:

2.2.                     P =[X1/X2],                 P' =[X '1/X '2]                      T =[Tx/Ty]

Esto nos permite expresar las dos ecuaciones de traslación bidimensional en la forma de matriz:

2.3.                                                P' = P + T

en ocasiones, las ecuaciones de transformación matricial se expresan en términos de vectores de renglón de coordenadas en vez de vectores de columna. En este caso, expresaríamos las representaciones matriciales como P[x y] y T[tx ty].

La traslación es una transformación de cuerpo rígido que mueve objetos sin deformarlos, es decir, se traslada cada punto del objeto la misma distancia. Se traslada un segmento de línea recta al aplicar la ecuación de transformación 2.3 en cada uno de los extremos de la línea y se vuelve a trazar la línea entre las nuevas posiciones de los extremos.

Rotación

Los valores positivos para el ángulo de rotación definen rotaciones en sentido opuesto a las manecillas del reloj alrededor del punto pivote y los valores negativos giran los objetos en la dirección del reloj . También es posible describir esta transformación como una rotación sobre el eje de rotación que es perpendicular al plano de xy y pasa a través del punto pivote.

En la figura 2.3, r es la distancia entre constante del punto desde el origen, el ángulo ϕ es la posición angular original del punto desde el plano horizontal y θ es el ángulo de rotación. Utilizando identidades trigonométricas podemos expresar las coordenadas transformadas en término de los ángulos θ y ϕ como:

2.4.                            x ' = r cos(f+0 ) = r cosf cos0- r sinf sin0
                               y' = r sin(f+0 ) = r cosf sin0- r sinf cos0

Las coordenadas originales del punto en las coordenadas polares son

2.5.                           x = r cosf, y = r sin0

Al sustituir las expresiones 2.5 en 2.6, obtenemos las ecuaciones de transformación para girar un punto en la posición (x, y) s través de un ángulo θ al rededor de un origen:

2.6.                     x ' = x cos0 - ysin0
                         y = x sin0 + y cos0

Con las representaciones del vector de columna 2.2 para las posiciones de coordenadas podemos expresar las ecuaciones de rotación en la forma de matriz:

2.7.          P' = R·P

donde la matriz de rotación es:

2.8.       R =  cos0 -sin0
                    Sin0 cos0

Cuando las posiciones de coordenadas se representan como vectores de renglón en vez de vectores de columna, el producto de la matriz en la ecuación de rotación 2.7 se transpone, de modo que el vector de coordenadas de renglón transformado [x’ y’] se calcula como

            P'T = (R·P)T = PT ·RT

donde PT = [x y] y se obtiene la transposición RT de la matriz R con sólo cambiar el signo de los términos del seno.

Escalación

Una transformación de escalación altera el tamaño de un objeto. Se puede realizar esta operación para polígonos al multiplicar los valores de coordenadas (x, y) de cada vértice por los factores de escalación sx y sy para producir las coordenadas transformadas (x’, y’):

              2.10.                         x ' = x·sx , y' = y·sy

El factor de escalación sx escala objetos en la dirección de x mientras que el factor de escalación sy lo hace en dirección de y. También se pueden expresar las ecuaciones de transformación 2.10 en forma matricial:

2.11.      x '    sx        0      .x
             y´      0     sy      y 

2.12.          P' = S·P

donde S es la matriz de escalación 2 por 2 en la ecuación 2.11.

2.2. Coordenadas homogéneas y representación matricial

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. Es posible expresar cada una de las transformaciones básicas en la forma de matriz general con las posiciones de coordenadas P y P’ representadas como columnas de vector.

2.15.                     P' = MP + M2

La matriz M1 es una matriz de 2 por 2 que contiene factores de multiplicación y M2 es una matriz de columnas de dos elementos que contiene términos de traslación. Para la traslación, M1 es la matriz de identidad. Para la rotación o la escalación M2 contiene los términos de traslación asociados con el punto pivote o el punto fijo de escalación.

Un planteamiento más eficiente combinaría las transformaciones de manera que se obtengan las coordenadas finales directamente a partir de las coordenadas iniciales para eliminar el cálculo de coordenadas intermedias. De esta manera, se debe de formular nuevamente la ecuación 2.15 para eliminar la adición de la matriz asociada con los términos de la traslación M2.

Para expresar cualquier transformación bidimensional como una multiplicación de matriz, representamos cada posición de coordenadas cartesianas (x, y) con las tres coordenadas homogéneas (xh, yh, h), donde

2.16.          x = xh / h,           y = yh / h

Por tanto, una representación general de coordenadas homogéneas se puede expresar también como (h·x, h·y, h). Para transformaciones geométricas bidimensionales, seleccionamos el parámetro homogéneo h como cualquier valor no cero. Así, existe un número finito de representaciones homogéneas equivalentes para cada punto de coordenadas (x, y).

Una opción conveniente consiste en sólo establecer h = 1. Entonces, se representa cada posición bidimensional con las coordenadas homogéneas (x, y, 1). Se requieren otros valores para el parámetro h, por ejemplo, en las formulaciones de matriz de transformaciones de vista tridimensionales.

2.3. Composición de transformaciones bidimensionales

Con las representaciones de matriz del tema anterior, podemos establecer una matriz para cualquier secuencia de transformaciones como una matriz de transformación compuesta al calcular el producto de la matriz de las transformaciones individuales. La creación de productos de matrices de transformación a menudo se conoce como concatenación o composición de matrices.

Traslaciones, rotaciones y escalaciones

Traslaciones

Se se aplican dos vectores de traslación sucesivos (tx1, ty1) y (tx2, ty2) en la posición de coordenadas P, la localización transformada final P, la localización transformada final P’ se calcula como:

2.23.       P' = T (tx2, ty2 {T (tx1, ty1P} = T (tx2 , ty2 T (tx1, ty1{ )}·P

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

2.25. T (tx2 , ty2 T (tx1, ty1) = T (tx1 + tx2 , ty1 + ty2 )

que demuestra que dos transformaciones sucesivas son aditivas.

Rotaciones

Dos rotaciones sucesivas que se aplican en el punto P producen la posición transformada

2.26.         P' = R(θ2 R(θ1{ P} = R(θ2 { R(θ1)}·P

Al multiplicar las dos matrices de rotación, podemos verificar que dos rotaciones sucesivas son aditivas:

2.27. R(02 )·R(01) = R(01 +02 )

de modo que es posible calcular las coordenadas giradas finales con la matriz de rotación compuesta como

2.28. P' = R(01 +02 )·P

Escalaciones

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

2.30. S(sx2 , sy2 )·S(sx1, sy1) = S(sxsx2 , sysy2 )

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 (xr, yr) al realizar la siguiente secuencia de operaciones de traslación-rotacióntraslació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 (xf, yf) 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.

La concatenación de las matrices para estas res operaciones produce la matriz de escalación requerida

2.34. T (xf , yf S(sx , sy T (−xf ,−yf ) = S(xf , yf , sx , sy )

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 lelvar a cabo al multiplicar primero a por B o multiplicar primero B por C:

2.35. A·B·C = (A·BC = A·(B·C)

En general el producto matricial A·B no es igual que B·A. Esto significa queremos trasladar y girar un objeto, debemos tener cuidado sobre el sentido en que se evalúa la matriz compuesta.

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.

Otra forma es que el programador de la aplicación especifique una región rectangular en coordenadas de mundo, llamada ventana de coordenadas mundiales y una región rectangular correspondiente en coordenadas de pantalla, llamada área de vista, con la cual se establece la correspondencia de la ventana de coordenadas mundiales.

La modificadora coordenada de mundo se emplea con ventana para subrayar que no se trata de una ventana de administrador de ventanas, un concepto distinto y más reciente que por desgracia tiene el mismo nombre. Este modificador se omitirá cuando no exista ninguna ambigüedad con respecto al tipo de ventana que se trate.

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.

Los elementos trsx y trsy son los términos de traslación que contienen combinaciones de distancias de traslación, coordenadas de punto pivote y de punto fijo, así como de ángulos de rotación y parámetros de escalación.

Por ejemplo, si debe escalar, girar un objeto con respecto de las coordenadas de su centroide (xc, yc) y después trasladarlo, los valores para los elementos de la matriz de transformación compuesta son

T (tx , ty R(xc , yc ,è S(xc , yc, sx , sy ) =

sx cos0      -sx sin0         xc (1- sx cos0 ) + ycsy sin0 ) + tx
sx sin0      -sy cos0          yc (1- sy cos0 ) + xcsx sin0 ) + ty
     0               0                                  1

Aunque la ecuación de matriz 2.35 requiere nueve multiplicaciones y seis adiciones, los cálculos explícitos para las coordenadas transformadas son 2.40.

                                                  x ' = x·rsxx + y·rsxy + trsx ,
                                                  y' = x·rsyx + y·rsyy + trsy

Así, en realidad 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.
.
2.6. Representación matricial de transformaciones tridimensionales

Así como las transformaciones bidimensionales se pueden representar con matrices de 3 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).

El sistema de coordenadas tridimensionales que se usará en los siguientes ejemplos es de mano derecha como se ilustra en la figura 2.16- Por convención las rotaciones positivas en el sistema de mano derecha son tales que, al ver hacia un eje positivo desde el origen, una rotación de 90° en sentido contrario al giro de las manecillas del reloj transformará un eje positivo en otro.

Se usa el sistema de mano derecha porque se trata de una convención matemática estándar, aunque en la graficación tridimensional es conveniente pensar en un sistema de mano izquierda sobrepuesto en la pantalla (fig. 2.17), ya que un sistema de mano izquierda da la interpretación natural de que los valores mayores de z se encuentran más lejos del observador.

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 P1P2 quedará en el eje positivo y P1P3 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.

El primer método es componer las transformaciones primitivas T, Rx, 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 más breve pero es más abstracto.

Para trabajar con las transformaciones primitivas, de nuevo dividimos un problema difícil en varios más sencillos. En este caso, la transformación deseada se puede llevar a cabo en cuatro pasos:

1. Traslación de P1 al origen.
2. Rotación sobre el eje y para que P1P2 esté en el plano (y, z).
3. Rotación sobre el eje x para que P1P2 esté en el eje z.
4. Rotación sobre el eje z para que P1P3 esté en el plano (y, z).

Paso 1: Traslación P1 al origen. La traslación es

2.59.    T (-x1,-y1,-z1) =
                               1 0 0 -x1
                               0 1 0 -y1
                               0 0 1 -z1
                               0 0 0   1

Al aplicar T a P1, P2 y P3 se obtiene

2.60.   P'1 = T (-x1,-y1,-z1).P1 =
                                                   0
                                                   0
                                                   0
                                                   1





Conceptos para  glosario de términos de la unidad

Coordenadas Homogéneas

En matemáticas, y más concretamente en geometría proyectiva, las coordenadas homogéneas son un instrumento usado para describir un punto en el espacio proyectivo. Fueron introducidas por el matemático alemán August Ferdinand Möbius en el año 1837.

También 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. Su notación en forma matricial se emplea en bibliotecas de programación gráfica en 3D como OpenGL y Direct3D.

En coordenadas homogéneas, todo punto bidimensional está definido por tres coordenadas. De tal modo que un punto de dimensiones x, y, se lo representa por la terna: x / w, y / w, w.

Matemáticamente, las coordenadas x y y se hallan dividiendo los dos primeros números entre el tercero, respectivamente.

En dos dimensiones, su valor se puede encontrar más fácilmente si w = 1, por simplificación. En tres dimensiones, suele ocurrir lo mismo w = 1.

Básicamente, se trata de ampliar el plano euclídeo (en el caso bidimensional) al plano proyectivo, es decir, incluirle los puntos impropios o del infinito.
Así, un punto impropio es aquel donde w = 0.

Una consecuencia de esta escritura es que un punto propio tiene infinitas formas de escribirlo, todo dependerá de los cocientes x / w y y / w (con w distinto de 0).


pila o stack( en programación)

Una pila (stack en inglés) 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.

Para el manejo de los datos se cuenta con dos operaciones básicas: apilar (push), que coloca un objeto en la pila, y su operación inversa, retirar (o desapilar, pop), que retira el último elemento apilado.

En cada momento sólo se tiene acceso a la parte superior de la pila, es decir, al último objeto apilado (denominado TOS, Top of Stacken inglés). La operación retirar permite la obtención de este elemento, que es retirado de la pila permitiendo el acceso al siguiente (apilado con anterioridad), que pasa a ser el nuevo TOS.

Por analogía con objetos cotidianos, una operación apilar equivaldría a colocar un plato sobre una pila de platos, y una operación retirara retirarlo.

Las pilas suelen emplearse en los siguientes contextos:
         Evaluación de expresiones en notación postfija (notación polaca inversa).
         Reconocedores sintácticos de lenguajes independientes del contexto
         Implementación de recursividad.


 Fuentes de información




No hay comentarios:

Publicar un comentario