lunes, 11 de marzo de 2013

Resumen del llibro


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. 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. Un usuario puede seleccionar una única zona para visualización, o varias zonas para visualización simultánea o para una secuencia animada panorámica a través de una escena. Las transformaciones de visualización bidimensional desde las coordenadas universales a las coordenadas del dispositivo implican operaciones de traslación, rotación y cambio de escala,así como procedimientos de borrado de aquellas partes de la imagen que se encuentran fuera de los límites de una zona seleccionada de la escena.
 
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.
Para aplicaciones bidimensionales, la trayectoria de rotación se encuentra en el plano xy sobre un eje que es paralelo al eje z. Las transformaciones de cambio de escala cambian las dimensiones de un objeto con respecto a una posición fija. Podemos expresar las transformaciones bidimensionales como operadores de matrices de 3 por 3 y las transformaciones tridimensionales como operadores de matrices de 4 por 4, de tal forma que esas secuencias de transformaciones pueden concatenarse dentro de una matriz compuesta.
En general, podemos representar tanto transformaciones bidimensionales como tridimensionales con matrices de 4 por 4. Representar operaciones de transformaciones geométricas con matrices de formulación eficiente, en tanto en cuanto nos permite reducir los cálculos aplicando una matriz compuesta a una descripción de un objeto para obtener su posición transformada.
Para encontrar la matriz de la posición transformada expresamos posiciones de coordenadas como matrices de columna. Elegimos la representación de matriz columna para puntos de coordenadas porque ese es el convenio matemático estándar y, muchos paquetes gráficos siguen dicha convención.
Nos referimos a una matriz de tres o cuatro elementos (vector) como una representación de coordenadas homogéneas. Para transformaciones geométricas, al coeficiente homogéneo se le asigna el valor 1. Las transformaciones compuestas se forman como multiplicación de matrices de raslación, rotación, cambio de escala y otras transformaciones. Podemos usar combinaciones de traslación y rotación para aplicaciones de animación y podemos usar combinaciones de rotación y escalación para cambiar el tamaño de los objetos en cualquier dirección especificada.

En general, la multiplicación de matrices no es conmutativa. Obtenemos diferentes resultados, por ejemplo, si cambiamos el orden de la secuenca traslación-rotación. Las transformaciones entre sistemas de coordenadas cartesianos se lleva a cabo con una secuencia de transformaciones traslación.rotación que hacen que los dos sistemas coincidan. Especificamos el origen de coordenadas y vectores de eje para un marco de referencia respecto al marco de referencia original.
En un sistema bidimensional, un vector define completamente las direcciones del eje de coordenadas; pero en un sistema tridimensional, hay que especificar dos de las tres direcciones de los ejes. Las transformaciones geométricas son transformaciones afines. Esto es, pueden expresarse como una función lineal de posiciones de coordenadas. Traslación, rotación y escalación son transformaciones afines. Transforman líneas paralelas en líneas paralelas y posiciones de coordenadas finitas en posiciones finitas.
 
 

 

 

Figura

martes, 5 de marzo de 2013

Algoritmo de Bresenham para trazar líneas y circunferencias


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 conversion 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.


x


k


y


k


y


i+1


x


k+1


y

d


1


d


2 }}


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


d



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


y


d



2 = (yk + 1) - y = yk + 1 - m (xk + 1) - b


Alfredo Weitzenfeld Gráfica: Línea


4


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


p

k

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


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


p

k

+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.


p



0 = 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).


Alfredo Weitzenfeld Gráfica: Línea


5


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.


Ejemplo

Para ilustrar el algoritmo, utilicemos la línea con extremos (20,10) y (30,18).

Esta línea tiene una pendiente de 0.8, con


D


x = 10, Dy = 8


El parámetro de decisión inicial tiene el valor


p



0 = 2 Dy - Dx = 6


y los incrementos para calcular parámetros de decisión sucesivos son

2


Dy = 16, 2Dy - 2Dx = -4


Trazamos el punto inicial (


x0,y0) = (20,10) y determinamos las posiciones de pixel sucesivos a lo largo de la


trayectoria de la línea a partir del parámetro de decisión como


k p

k

(xk+1,yk+1)


0 6 (21,11)

1 2 (22,12)

2 -2 (23,12)

3 14 (24,13)

4 10 (25,14)

5 6 (26,15)

6 2 (27,16)

7 -2 (28,16)

8 14 (29,17)

9 10 (30,18)

Un trazo de pixeles se genera a lo largo de la trayectoria de esta línea.

En la siguiente rutina, se presenta una implementación del trazo de líneas de Bresenham para pendiente en el

rango 0 < |


m | < 1, con trazo de izquierda a derecha en el caso de m positivo y de derecha a izquierda en el caso de


m



negativo.


void LineBres(Display* display, Window win, GC gc, int x0, int y0, int x1, int y1)

{

int x, y, dx, dy, xend, p, incE, incNE;

dx = abs(x1 - x0);

dy = abs(y1 - y0);

p = 2*dy - dx;

incE = 2*dy;

incNE = 2*(dy-dx);

/* determinar que punto usar para empezar, cual para terminar */

if (x0 > x1) {

x = x1;

y = y1;

xend = x0;

}

else {

x = x0;

y = y0;

xend = x1;


Alfredo Weitzenfeld Gráfica: Línea


6


}

/* se cicla hasta llegar al extremo de la línea */

while (x <= xend)

{

XDrawPoint(display,win,gc,x,y);

x = x + 1;

if (p < 0)

p = p + incE

else {

y = y + 1;

p = p + incNE;

}

}

}


El algoritmo de Bresenham se generaliza para líneas con una pendiente arbitraria al considerar la simetría entre

los diversos octantes y cuadrantes del plano de


xy.


Para una línea con una pendiente


m > 1, intercambiamos las funciones de las direcciones de x y y, o sea, pasamos a


lo largo de


y en pasos unitarios y calculamos los valores sucesivos de x que se aproximan mas a la trayectoria de la


línea.

Asimismo, podemos revisar el programa para trazar pixels iniciando desde cualquier extremo.

Si la posición inicial para una línea con una pendiente positiva es el extremo derecho, tanto


x como y disminuyen


conforme pasamos de derecha a izquierda.

Con el fin de asegurarnos de que los mismos pixeles se tracen sin que importe el extremo en que se comienza, se

seleccionara el pixel superior (o inferior) cuando se pase exactamente en el medio (


d1 = d2).


En el caso de pendientes negativas, los procedimientos son similares excepto que ahora, una coordenada decrece

conforme la otra aumenta.

Por ultimo, es posible manejar los casos especiales por separado.

Las líneas horizontales (


Dy = 0), las líneas verticales (Dx = 0) y las diagonales | Dy | = | Dx | se pueden cargar en

forma directa sin procesarlas mediante el algoritmo para el trazo de líneas.