1. INTRODUCCIÓNDiseño asistido por computadora, entornos de realidad vir-

tual y visualización de datos son algunas de las herramientasdiseñadas a partir de los gráficos obtenidos mediante unacomputadora (Hearn y Baker, 2003). Existen muchas clasesdistintas de conjuntos de datos, por lo que los esquemas devisualización dependen de las características de los datos.La visualización con colores es una técnica para represen-tar los datos. Educación y formación, Arte por computadora,entretenimiento, procesamiento de imágenes.

Paquetes gráficos.GL, OpenGL, VRML (lenguaje para el modelado de reali-

dad virtual),

2. PRIMITIVAS DE GRAFICACIÓNLas funciones de un paquete gráfico que se utilizan para

describir los distintos componentes de una imagen se de-nominan primitivas. Las primitivas gráficas que describen lageometría de los objetos se les conoce como primitivas geo-métricas. Entre las primitivas geométricas están los círculos,las cuádricas, las cónicas, las superficies y curvas de tipospline. Las primitivas gráficas se proyectan sobre un planobidimensional.

Los componentes de las imágenes se describen en unmarco de referencia universal que al final se hace correspon-der con el sistema de coordenadas del dispositivo de salida.

2.1 Algoritmos de trazado de líneas.Un segmento de línea recta dentro de una escena está

definido por las coordenadas de los dos extremos del seg-mento. La ecuación de una línea recta está dada por:

y = mx+ b (1)

Para determinar las posiciones de los píxeles a lo largo deun trayecto de línea recta se utilizan las propiedades geomé-tricas de la línea.

El algoritmo de análisis diferencial digital (DDA). La ma-nera en que trata el problema de la línea recta es sim-ple, utiliza una variable de rastreo (la variable que seincrementa de pixel en pixel), como aquella que tienemayor variación. Es decir, si ∆x

∆y> 1 se elige x de lo

contrario y. Esto es independientemente del cuadranteque se quiera graficar.

Algoritmo 1 DDA Digital Diferential AnalyzerEntrada: xini, yini, xfin, yfinSalida: Una línea recta.

1: si |∆x||∆y| ≥ 1 entonces2: longitud = |∆x|3: si no4: longitud = |∆y|5: fin si6: A = ∆x

longitud

7: B = ∆ylongitud

8: x = xini + 0.5 ∗ Signo(A)9: y = yini + 0.5 ∗ Signo(B)

10: k = 111: mientras k ≤ longitud hacer12: graficar (x, y)13: x = x+A14: y = y +B15: k = k + 116: fin mientras

Algoritmo de Bresenham. Utiliza sólo cálculos enteros pa-ra calcular los incrementos. El algoritmo asume que los

puntos finales de la línea recta son enteros. Peque-ñas variaciones en el algoritmo son necesarias paralos cuatro casos (Rogers, 1998):

Pendiente positiva < 1

Pendiente negativa > −1Pendiente positiva ≥ 1

Pendiente negativa ≤ −1

Presentaremos el algoritmo para el primer caso; lasmodificaciones para los demás casos deberán ser ob-vias. Dado que la pendiente de la línea es menor que1, la cordenada en y varía más lentamente que la coor-denada en x. Podemos modificar la ecuación 1 para sudigitalización agregando un subíndice a x indicando elnúmero del píxel.

y = mxk + b

El algoritmo asume que se nos da el primer píxel dela línea que será graficada, supóngase que es (x0, y0).Ahora deseamos descubir que píxel se tiene que im-primir en la posición x1. Dado que la pendiente es po-sitiva y menor que 1, sabemos que será cualquiera y0o y0 + 1. La pregunta, ¿Cuál elegir y al mismo tiempoutilizar operaciones con enteros?Generalizando el problema decimos: que tenemos quedeterminar el píxel en la posición (xk, yk) y deseamosencontrar el valor de y correspondiendo a la posiciónxk + 1. Sabemos que este valor puede ser cualquierayk o yk + 1. Utilizando la ecuación 2.1, tenemos:

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

Eligiendo el valor más pequeño de y, yk calcularemosla distancia entre el valor exacto y y este valor comod1.

d1 = y − yk = m(xk + 1) + b− yk (3)

de igual manera calculamos la distancia d2 del valorexacto y y el valor más grande yk + 1

d2 = yk + 1− y = yk + 1−m(xk + 1)− b (4)

Obviamente deseamos escoger la diferencia más pe-queña. Si encontramos la diferencia entre d1 y d2 obte-nemos:

d1 − d2 = 2m(xk + 1) + 2b− 2yk − 1 (5)

El signo de esta diferencia nos dirá que píxel elegir. Sila diferencia es negativa entonces yk es el más cercanoal valor y de lo contrario si es positivo, yk + 1 es elmás cercano. Si la diferencia es 0 entonces cualquierapuede ser escogido.Hasta ahora, no hemos considerado el cálculo sin nú-meros no-enteros. Recordemos que los puntos finalesson enteros y son conocidos. Así que podemos calcu-lar la pendiente como:

m =∆y

∆x(6)

Haciendo una sustitución en la ecuación 5, y multipli-cando por ∆x tenemos:

∆x(d1 − d2) = 2∆yxk − 2∆xyk + [2∆y +∆x(2b− 1)](7)

La cantidad en los paréntesis cuadrados no dependede los píxeles con subíndice k. Cada factor de lado de-recho de la ecuación es entero, con excepción de b.Para simplificar la ecuación definimos C como la canti-dad constante que se encuentra en los paréntesis cua-drados.

C = 2∆y +∆x(2b− 1) (8)

Además tenemos al valor para elegir como:

pk = ∆x(d1 − d2) = 2∆yxk − 2∆xyk + C (9)

Si pk es positiva elegimos yk+1 de lo contrario yk. Pa-ra deshacernos de C utilizamos un método recursivo,para calcular las series de los valores pk. El pixel en lasiguiente posición a elegir dependiendo el valor pk+1

es:

pk+1 = 2∆yxk+1 − 2∆xyk+1 + C (10)

Ahora podemos eliminar C restando la ecuación 9 deesta ecuación, obteniendo:

pk+1 − pk = 2∆y(xk+1 − xk)− 2∆x(yk+1 − yk) (11)

Pero como xk+1 − xk = 1 dado que los pasos entrex es de un píxel a la vez. De tal manera que tenemosnuestra ecuación para elegir los píxeles como:

pk+1 = pk + 2∆y − 2∆x(yk+1 − yk) (12)

Todos los valores en esta ecuación son enteros, lo úni-co que resta es calcular p0. Sustituimos en la ecuación7 el valor de b.

b = y0 −mx0 = y0 −(∆y

∆x

)x0 (13)

Multiplicando y cancelando los términos obtenemos:

p0 = 2∆y −∆x (14)

Resumiendo el algoritmo de Bresenham, para el casoen que la pendiente m está dada como 0 < m < 1.

1. Obtener los dos puntos extremos de la línea encoordenadas de píxel.

2. Calcular las constantes ∆x y ∆y.3. Graficar (x0, y0) como el primer punto.4. Calcular el parámetro pk (en k = 0 utilizando la

ecuación 14) y utilizarla para encontrar el siguien-te valor de y. Si pk < 0 el siguiente punto a grafi-car es (xk + 1, yk). Es decir:

pk+1 = pk + 2∆y (15)

Sino, el siguiente punto a graficar es (xk +1, yk +1).

pk+1 = pk + 2∆y − 2∆x (16)

5. repetir el paso 4 hasta el píxel xn

2.2 Algoritmo de Bresenham y del punto me-dio para trazado de circunferencias

Algoritmo de Bresenham para trazado de circunferencias.La ecuación de una circunferencia centrada en el punto(x, y) es:

(x− xc)2 + (y − yc)2 = R2 (17)

El método más simple para trazar una circunferenciaconsiste en asignar a x todos los valores enteros quese encuentran entre xc − R y xc + R. Para calcular ydespejamos de la ecuación 17 y, y obtenemos:

y =√R2 − (x− xc)2 + yc (18)

Este método requiere un considerable número de cálcu-los para cada paso. Además el espaciado entre los pí-xeles no es uniforme. Otra forma de calcular los puntos

es utilizando las coordenadas polares de la circunfe-rencia. Es decir:

x = xc + rcosθ (19)y = yc + rsenθ (20)

Lo anterior, aunque presenta un espaciado homóge-neo aun tiene el problema de los cálculos laboriosos.Considerando que el monitor representa las coordena-das gráficas en la parte superior izquierda y y se incre-menta hacia abajo, entonces tenemos los octantes dela figura 1.

Fig. 1: División en octantes en un círculo.

Octante coordenada x coordenada y1 y x2 x y3 −x y4 −y x5 −y −x6 −x −y7 x −y8 y −x

De la ecuación 17 con xc = 0 y yc = 0, podemos en-contrar el valor correspondiente a xk + 1.

y2 = r2 − x2k+1

= r2 − (xk + 1)2

Vamos a buscar las diferencias entre el punto yk o yk−1 y el punto del círculo. Tenemos entonces la d1

d1 = y2k − y2

= y2k − r2 + (xk + 1)2

De igual manera para el otro píxel.

d2 = y2 − (yk − 1)2

= r2 − (xk + 1)2 − (yk − 1)2

= r2 − (xk + 1)2 − y2k + 2yk − 1

Definimos el parámetro de decisión como

pk = d1 − d2= 2y2k + 2(xk + 1)2 − 2yk − 2r2 + 1 (21)

Podemos utilizar una relación recursiva como en el ca-so de la línea recta. Para hacer esto reescribimos laecuación 21 pero para pk+1

pk+1 = 2y2k+1 + 2(xk+1 + 1)2 − 2yk+1 − 2r2 + 1

Ahora restamos a la ecuación 21 esta ecuación.

pk+1 = 2y2k+1+2(xk+1+1)2−2yk+1−2y2k−2(xk+1)2+2yk

Tenemos dos casos si pk es negativa entonces yk +1 = yk. Sustituyendo esto junto con xk+1 = xk + 1,obtenemos:

pk+1 − pk = 4xk + 6 (22)

Si pk ≥ 0 entonces yk + 1 = yk − 1 y obtenemos

pk+1 − pk = 4(xk − yk) + 10 (23)

Lo que resta es calcular el valor inicial p0, el cual sepuede obtener directamente de la ecuación 21.

p0 = 3− 2r (24)

Entonces tenemos el algoritmo para dibujar los píxelesde un círculo en el segundo octante.

1. Especificar (un entero en píxeles) el radio r y elcentro (xc, yc) del círculo.

2. Inicializar x0 = 0 y y0 = r y graficar el primerpunto en la posición x0 + xc, y0 + yc

3. Calcular p0 con la ecuación 24

4. Mientras xk < yk hacer xk+1 = xk + 1

Si pk < 0 hacer yk+1 = yk graficar el siguientepíxel en la posición (xk+1+xc, yk+yc) y calcularpk+1 de la ecuación 22. Sino, hacer yk+1 = yk−1,graficar el siguiente píxel en la posición (xk + 1 +xc, yk − 1 + yc) y calcular pk+1 de la ecuación 23.

Algoritmo del punto medio utiliza la función fcirc(x, y) =x2+y2−R2, es 0 en el círculo, positiva fuera del círculoy negativa dentro del círculo. Puede demostrarse quesi el punto medio entre los píxeles A y B está dentrodel círculo entonces A es el punto más cercano, de locontrario B es el más cercano.

De igual manera que con el algoritmo de Bresenham,se plantea un método recursivo. Se calcula un p0 inicial.

Al inicio x0 = 0 y y0 = R, evaluando la función fcirc =(xk + 1, yk − 1/2), es decir su punto medio.

p0 = (xk + 1)2 + (yk − 1/2)2 −R2

Sustituyendo xk = 0 y yk = R

p0 = 1 + (R− 1/2)2 −R2

p0 = 1 +R2 −R+ 1/4−R2

p0 = 1 + 1/4−Rp0 = 5/4−R

2.3 Algoritmo del punto medio para genera-ción de elipses

Una elipse se define como el conjunto de puntos en que lasuma de las distancias desde dos posiciones fijas (focos) seala misma para todos los puntos (ver figura 2). Si etiquetamoscomo d1 y d2 las distancias de los dos focos desde cualquierpunto P = (x, y) de la elipse, la ecuación general de la elipsepuede escribirse Rowe (2001):

Algoritmo 2 Algoritmo del punto medioEntrada: xc, yc, y radio.Salida: Un círculo.

1: x = 0, y =radio.2: double d = 5.0/4.0− radio3: dibuja píxeles en el octante 1, 2, 4 y 74: mientras y > x hacer5: si p < 0 entonces6: p+ = 2x+ 17: si no8: p+ = 2(x− y) + 19: y −−

10: fin si11: x++12: dibuja píxeles en los 8 octantes13: fin mientras

Fig. 2: Una elipse definida por sus focos

d1 + d2 = constante

Expresando las distancias d1 y d2 en términos de las coorde-nadas de los focos F1 = (x1, y1) y F2 = (x2, y2), tendremos:

√(x− x1)2 + (y − y1)2+

√(x− x2)2 + (y − y2)2 = constante

(25)Para curvas más complejas, podemos determinar la pen-

diente de la línea tangente a la curva, calculando la derivadady/dx. Por ejemplo para determinar la pendiente de la líneatangente a la elipse. Empezamos con la ecuación de la elip-se centrada en el origen.

x2

a2+y2

b2= 1 (26)

donde a y b son constantes, llamadas ejes semi-mayor ysemi-menor. Utilizando derivación implicita encontramos laderivada dy/dx de la ecuación 26.

2x

a2+

2y

b2dy

dx= 0 (27)

Dado que la elipse contiene 4 cuadrantes que son simétri-cos, determinamos el algoritmo para graficar la elipse en elprimer cuadrante, luego entonces, utilizamos su simetría pa-ra obtener los restantes 3 cuadrantes. En el primer cuadrantela elipse tendrá un punto donde la pendiente de la tangentees −1. Para encontrar este punto sustituimos dy/dx por −1y obtenemos la relación.

a2y = b2x (28)

Podemos diseñar el algoritmo de tal manera que empece-mos con x = 0 y avancemos de uno en uno hasta alcanzarel punto especificado en la ecuación 28. Y como un segundopaso podemos iniciar en y = 0 y avanzando de uno en uno

Fig. 3: Una elipse

hasta que alcancemos el mismo punto. Ahora lo que resta essaber cuál píxel vamos a dibujar una vez que dibujamos elprimer píxel. Veamos como calcular el parámetro de decisiónpk para la elipse. Empecemos por considerar la parte dondela pendiente es menor que 1. En esta parte incrementamos xde uno en uno y calculamos la correspondiente coordenadaen y. Podemos acomodar la ecuación 26 para poder obtenery.

a2y2 = b2(a2 − x2) (29)

Primero, se asume que el píxel en la posición (xk, yk) hasido graficado. Intentamos saber, cuál píxel deberá ser gra-ficado después. Dado que la pendiente en esta región esnegativa, sabemos que yk+1 puede ser yk o yk − 1. Por con-siguiente, necesitamos saber las distancias de cada píxel ala curva. Y elegir áquel píxel que minimice la distancia. Pa-ra simplificar los cálculos considerese la distancia a2y2 paracalcular la diferencia. Es decir, vamos a obtener las diferen-cias entre la y y la posible yk+1, primero para yk+1 = yk,tenemos:

d1 = a2(y2k − y2)= a2y2k − b2(a2 − x2k+1)

Para yk+1 = yk − 1

d2 = a2(y2 − (yk − 1)2)

= b2(a2 − x2k+1)− a2(yk − 1)2

Ahora definimos el parámetro de decisión como la diferen-cia de estas dos cantidades.

pk = d1 − d2= 2a2(y2k − yk)− 2b2(a2 − x2k+1) + a2

Si pk < 0, elegimos yk+1 = yk, de lo contrario yk+1 =yk − 1. Podemos derivar una fórmula recursiva para calcularpk para mejorar la eficiencia. Utilizamos la ecuación ante-rior para obtener pk+1 y obtenemos la fórmula pk+1 − pk.Después de un poco de algebra y sustituyendo xk = xk+1,obtenemos.

Si pk < 0 obtenemos:

pk+1 = pk + 2b2(2xk + 3) (30)

en otro caso:

pk+1 = pk + 4a2(1− yk) + 2b2(2xk + 3) (31)

La condición inicial puede ser obtenida con la ecuación 30,con x0 = 0 y y0 = b.

p0 = a2(1− 2b) + 2b2 (32)

Fig. 4: Una curva de tipo spline formada mediante sec-ciones polinómicas cúbicas individuales definidas entreuna serie de puntos especificados.

Ahora completamos el algoritmo para el primer cuadrantedonde la magnitud de la pendiente es menor que 1. Iniciamoscon x = a y y = 0. Entonces para pk < 0 obtenemos:

pk+1 = pk + 2a2(yk + 3) (33)

en otro caso obtenemos:

pk+1 = pk + 4b2(1− xk) + 2a2(yk + 3) (34)

y la condición inicial es:

p0 = b2(1− 2a) + 2a2 (35)

2.4 PolilíneasUna polilínea es una figura que como su nombre lo indica

consta de varias líneas rectas, estas líneas están conecta-das y ordenadas de manera que el final coincide con el iniciode la segunda, el final de la segunda coincide con el iniciode la tercera y así sucesivamente. Existen dos tipos de poli-líıneas, en las cerradas el final de la ultima línea coincide conel inicio de la primera formando así una figura cerrada quepuede por ejemplo rellenarse. Las polilíneas abiertas no for-man polígonos sino que forman simplemente líneas quebra-das que pueden usarse para definición de extremos u otrasaplicaciones.

2.5 Curvas: Splines cúbicas naturales, Splinesde Hermite, Curvas de Bezier.

2.5.1 Polinomios y curvas de tipo splineUn función polinómica de grado n en x se define como:

y =

n∑k=0

akxk

= a0 + a1x+ . . .+ an−1xn−1 + anx

n

donde n es un entero no negativo y los valores ak sonconstantes, con an 6= 0. Una forma de realizar el ajuste de lacurva consiste en construir una sección curva de polinomiocúbico entre cada par de puntos especificados. Cada sec-ción curva se describe entonces en forma paramétrica de lamanera siguiente:

x = ax0 + ax1u+ ax2u2 + ax3u

3

y = ay0 + ay1u+ ay2u2 + ay3u

3

donde el parámetro u varía a lo largo del intervalo que vade 0 a 1.0. Una condición de contorno es que dos seccionescurvas adyacentes tengan las mismas coordenadas de po-sición en la frontera, con el fin de obtener una única curvasuave continua (Figura 4).

Podemos clasificar a las splines como:

Splines de interpolación: aquellas que pasan justo por lospuntos de control.

Splines de Aproximación: aquellas que pasan cerca de lospuntos de control.

En cualquier paso los puntos de control definen un polí-gono donde el spline queda confinado. Las condiciones decontinuidad pueden ser:

1. Continuidad paramétrica: si las derivadas paramétricasal final de cada segmento coinciden exactamente conlas derivadas paramétricas al inicio del siguiente seg-mento.

2. Continuidad geométrica: si las derivadas de cada parde segmentos son proporcionales (no necesariamenteiguales) en su frontera comun.

El problema con las splines cúbicas naturales es que si cual-quiera de los puntos de control es modificado, la curva com-pleta (todos los segmentos) deben e ser recalculados, es de-cir, los splines naturales no permiten control local.

2.5.2 Splines de HermitePermiten control local por que cada segmento de la curva

solo depende de las restricciones de sus puntos externos.Si P (u) representa la curva paramétrica que inicia en el

punto de control pk y termina en pk+1, entonces las restric-ciones que definen esa curva en ese segmento son:

P (0) = pk

P (1) = pk+1

P ′(0) = DPk

P ′(1) = DPk+1

El polinomio paramétrico P (U) es:

P (u) = au3 + bu2 + cu+ d (36)

O bien de manera matricial:

P (U) =[u3 u2 u 1

] abcd

(37)

P ′(u) es

P ′(u) = 3au2 + 2bu+ c (38)

O bien:

P ′(U) =[3u2 2u 1 0

] abcd

Es claro P (0) = d y que P (1) = a + b + c + d, además

P ′(0) = c y P ′(1) = 3a+ 2b+ c por lo tanto las restriccionespara la curva en el segmento que va de pk a pk+1 se puedenexpresar como:

pkpk+1

DPkDPk+1

=

0 0 0 11 1 1 10 0 1 03 2 1 0

abcd

Resolviendo este sistema de ecuaciones obtenemos:

abcd

=

2 −2 1 1−3 3 −2 −10 0 1 01 0 0 0

pkpk+1

DPkDPk+1

abcd

=MH

pkpk+1

DPkDPk+1

MH es la matriz de Hermite.Sustituyendo en 37 obtenemos:

P (u) =[u3 u2 u 1

] 2 −2 1 1−3 3 −2 −10 0 1 01 0 0 0

pkpk+1

DPkDPk+1

Realizando operaciones obtenemos:

P (u) = pk(2u3 − 3u2 + 1) + pk+1(−2u3 + 3u2) +

DPk(u3 − 2u2 + u) +DPk+1(u

3 − u2)

El problema con la utilización de las splines de Hermite esque estas requieren de la especificación de las derivadas encada punto de control, para remediar este problema, las spli-nes cardinales realizan una estimación de dichas derivadasmediante:

P ′(0) =1

2(1− t)(pk+1 − pk−1)

P ′(1) =1

2(1− t)(pk+2 − pk)

donde t es un parámetro que define la tensión de los seg-mentos de cada spline cardinal.

En el algoritmo 3 se observa el algoritmo para construiruna curva, utilizando dos puntos con sus correspondientesvectores tangentes a la curva.

Algoritmo 3 Curvas de HermiteEntrada: xini, yini, xfin, yfin, No_Pts,

DPxini, DPyini, DPxfin, DPyfinSalida: Curva.

1: para i← 0, No_Pts hacer2: t = i

No_Pts−1

3: b0 = 2t3 − 3t2 + 14: b1 = −2t3 + 3t2

5: b2 = t3 − 2t2 + t6: b3 = t3 − t27: x = b0 ∗ xini + b1 ∗ xfin + b2 ∗DPxini + b3 ∗DPxfin8: y = b0 ∗ yini + b1 ∗ yfin + b2 ∗DPyini + b3 ∗DPyfin9: grafica(x, y)

10: fin para

2.6 Estructura de un Programa OpenGLEn OpenGL se proporciona una biblioteca básica de fun-

ciones para especificar primitivas gráficas, atributos, trans-formaciones geométricas, transformaciones de visualización.La biblioteca está diseñada para ser independiente del hard-ware. Sin embargo, existen bibliotecas auxiliares para usarcon programas openGL.

2.6.1 Sintaxis básica de OpenGLLos nombres de las funciones de la biblioteca de OpenGL

utilizan como sintaxis el prefijo gl, y cada palabra que for-ma parte del nombre de la función empieza con mayúscula.Ejemplo:

glBegin glEnd glCopyPixelsglPolygonMode

Algunas funciones requieren que a sus argumentos se lesasigne una o más constantes simbólicas. Por ejemplo, unnombre de un parámetro, un valor para un parámetro o un

modo particular. Estás constantes empiezan con GL. Ade-más las palabras que conforman el nombre se escriben conmayúsculas. Ejemplos:

GL_2D GL_RGB GL_POINTS GL_POLYGON

Para la definición de los tipos de datos OpenGL utiliza es-pecífica sus propios tipos de datos. Ejemplos:

GLbyte GLshort GLint GLfloat

2.6.2 Bibliotecas relacionadasExisten bibliotecas relacionadas para operaciones espe-

ciales. La biblioteca GLU (Utilidad OpenGL) proporciona su-brutinas para la configuración de matrices de visualizacióny proyección, descripción de objetos complejos mediante lí-neas y aproximaciones poligonales, visualización de cuádri-cas y splines mediante aproximaciones lineales. Y el kit deherramientas de OpenGL. (GLUT), proporciona una bibliote-ca de funciones para interactuar con un sistema de ventanas.

Para compilar un programa en Ubuntu se utiliza la libreríalibGL.so, es decir:

g++ cubo.cc -lglut -lGL -lGLU -o cubo

2.7 Despliegue de lineas, triángulos, cuadra-dos, circunferencias, etc. mediante OpenGL

3. ALGORITMOS DE RELLENO DE ÁREAS

3.1 Relleno mediante ordenamiento de aris-tas.

El relleno de una región se realiza primero determinandola intersección de las posiciones de contorno con las líneasde rastreo de la pantalla. Entonces los colores de relleno sonaplicados a cada sección de la línea de rastreo.

3.2 Relleno mediante complementación.Este algoritmo hace uso del hecho de que al realizar la

operación XOR entre un valor y el valor actual de un píxel,se obtienen los efectos descritos en la siguiente tabla:

valor píxel resultado0 0 00 1 11 0 11 1 0

observe en esta tabla que encender un píxel que ya estáencendido es equivalente a apagarlo. Este hecho es clarocuando trabajamos con dibujos en blanco y negro, es decir,sabemos que dibujar una línea encima de otra idéntica a laque se esta trazando utilizando la operación XOR es equiva-lente a borrarla. Un comportamiento similar ocurre cuandose trabaja con líneas de cualquier color y el color del fon-do, es decir, si se dibuja una línea azul sobre un fondo rojoutilizando la operación XOR la línea que se obtiene es ver-de, pero al volver a dibujar la línea azul sobre dicha líneaverde recién trazada (de nuevo con la operación xor) se ob-tiene una línea roja igual que el fondo, por lo tanto la línea seborra. Entonces, el efecto de dibujar dos veces una mismalínea con la operación xor es equivalente a no dibujar nada.Es decir, lo anterior es válido para dibujos a color y no soloen blanco y negro.

3.3 Modificación mediante el uso de una cercaEl algoritmo de relleno mediante complementación no re-

quiere dedicar tiempo para ordenar o mantener ordenadaninguna lista de píxeles que conforman las líneas, pero encambio dedica demasiado tiempo a cambiar el color de de-masiados píxeles, algunos de ellos varias veces, este tiempo

Algoritmo 4 Algoritmo de relleno por complementaciónEntrada: Líneas del polígono ordenadas.

Color de rellenoSalida: Una figura con un nuevo color de relleno

1: mientras existan líneas en el polígono hacer2: Calcular los puntos por los que pasa la línea (x, y)3: Sea A el conjunto de todas las coordenadas en x de

la línea.Sea B el conjunto de las coordenadas en y; desde elpunto que pertenece a la línea hasta el tamaño máxi-mo de columnas de la imagen.

4: para i ∈ A hacer5: para j ∈ B hacer6: Imagen original[i,j] = color de relleno XOR color

existente[i,j]7: fin para8: fin para9: fin mientras

se puede reducir si se emplea una cerca, la cerca es una lí-nea vertical infinita e imaginaria que pasa por cualquier vérti-ce del polígono, entonces, en lugar de modificar los píxeles ala derecha de cada línea se modifican los píxeles que estánentre la línea y la cerca solamente.

3.4 Algoritmo simple de siembra de semilla.Este algoritmo recibe un píxel inicial interior al área que se

quiere rellenar, llamamos a este píxel semilla, el algoritmopone este píxel en el color del relleno y enseguida verificalos píxeles que están alrededor de este, para cada píxel cir-cundante aquellos que no están en el color del relleno o en elcolor del borde los convierte en semillas nuevas. Para cadasemilla nueva se repite el proceso. Este algoritmo se puedeimplementar en forma iterativa haciendo uso de una pila obien en forma recursiva.

Algoritmo 5 Algoritmo de relleno por siembra de semillaEntrada: Coordenadas (x, y) de la semilla. Color de relleno.Salida: Una figura con un nuevo color de relleno

1: PUSH(x, y)2: mientras pila no esté vacía hacer3: POP(x, y)4: pintar en las coordenadas (x, y) el color de relleno5: si color(x− 1, y) /∈ {Relleno,Borde} entonces6: PUSH(x− 1, y)7: fin si8: si color(x+ 1, y) /∈ {Relleno,Borde} entonces9: PUSH(x+ 1, y)

10: fin si11: si color(x, y − 1) /∈ {Relleno,Borde} entonces12: PUSH(x, y − 1)13: fin si14: si color(x, y + 1) /∈ {Relleno,Borde} entonces15: PUSH(x, y + 1)16: fin si17: fin mientras

3.5 Siembra de semilla por línea de rastreo.Al aplicar el algoritmo de semilla tal y como se explicó en

la sección anterior para rellenar un área grande, muy proba-blemente se tendrán problemas de memoria, esto es debidoa que al sacar un elemento de la pila, se pueden introdu-cir cuatro. El algoritmo de siembra de semilla por línea derastreo soluciona este problema, al insertar un máximo de 2elementos a la pila por cada línea de píxeles que pone enel color de relleno, el algoritmo saca la semilla de la pila yrellena la línea de rastreo a la que corresponde la semillahacia la derecha y hacia la izquierda y al hacerlo checa los

píxeles que están en la línea de rastreo inmediata superior einmediata inferior, si encuentra al menos un píxel de la líneainmediata superior que no está en el color del relleno meteese píxel a la pila pero solo uno de toda la línea, hace lomismo con la línea inmediata inferior.

3.6 Funciones de OpenGL para manejo delcolor de las figuras y del fondo

void glColor3f(rojo, verde, azul)void glColor4f(rojo, verde, azul, alfa)void glClearColor3f(rojo, verde, azul)

4. ALGORITMOS DE RECORTEEn muchas aplicaciones se debe seleccionar una área de

recorte que define lo que sería visible por ejemplo para hacerun acercamiento a una sección de interés.

Los algoritmos de recorte son aplicados en vistas bidimen-sionales, para identificar aquellas partes de la imagen queestán dentro de una ventana de recorte.

4.1 Códigos de región para determinar la vi-sibilidad de líneas.

Una manera rápida para decidir cuales líneas son total-mente visibles, parcialmente visibles o trivialmente invisibleses utilizar los códigos de Cohen, este método funciona paraáreas de recorte rectangulares. La Figura 5 de los códigosde Cohen, el primer bit (el menos significativo) indica que elvértice está a la izquierda del área de recorte, el segundo bitindica que el punto se encuentra a la derecha, el tercero ycuarto bit indican que el punto está por arriba y por debajodel área de recorte respectivamente.

Fig. 5: Códigos de Cohen para determinar visibilidad.

Una línea es totalmente visible si los códigos de Cohenen ambos extremos son 0000. Si al hacer la operación ANDentre los códigos de Cohen de los extremos de una línea seobtiene un resultado distinto de 0000, entonces la línea estrivialmente invisible puesto que ambos extremos se encuen-tran a la izquierda o ambos están arriba, etc. Ahora bien, si laoperación AND entre los dos extremos de una línea resultaen 0000, esto no significa que la línea sea totalmente visiblesino que puede ser parcialmente visible o incluso totalmen-te invisible. Por supuesto, si uno de los extremos tiene unCódigo de Cohen de 0000 y el otro extremo tiene un códigodiferente, entonces la línea es parcialmente visible.

4.2 Algoritmo de recorte explícito en 2DPara las líneas que no pueden ser identificadas como den-

tro o fuera de la ventana completamente. Son identificadaspor la intersección con las líneas bordes de la ventana derecorte.

Las líneas que forman el área rectangular son:

y = ysup extremo superior

Fig. 6: Recorte de segmentos utilizando una ventana derecorte.

y = yinf extremo inferior

x = xder extremo derecho

x = xizq extremo izquierdo

La ecuación de la línea recta que pasa por los puntos(x1, y1) y (x2, y2) es:

y = mx+ b (39)

donde m = y2−y1x2−x1

Como la línea pasa por (x1, y1), entonces

y1 = mx1 + b

Por lo que:

b = y1 −mx1 (40)

Por lo tanto:

y = mx+ y1 −mx1Agrupando:

y = m(x− x1) + y1 (41)

De manera similar, despejando x de 39.

x =y

m− b

m

Sustituyendo 40 en la ecuación anterior obtenemos:

x =y

m− y1 −mx1

m

de donde:

x =y − y1m

+ x1 (42)

Por lo tanto, utilizando 41 obtenemos la intersección de larecta con el extremo derecho, mismo que ocurre en:

(xder,

y2 − y1x2 − x1

(xder − x1) + y1

)(43)

La intersección con el extremo izquierdo ocurre en:(xizq,

y2 − y1x2 − x1

(xizq − x1) + y1

)(44)

Utilizando 42 obtenemos la intersección de la recta con elextremo superior, el cual ocurre en:

((ysup − y1)

x2 − x1y2 − y1

+ x1, ysup

)(45)

La intersección con el extremo inferior ocurre en:

((yinf − y1)

x2 − x1y2 − y1

+ x1, yinf

)(46)

Fig. 7: Líneas que intersectan uno o más bordes de re-corte. Una forma parte de la ventana de recorte y la otrase encuentra fuera.

4.3 Algoritmo de Sutherland-Cohen.Es uno de los primeros algoritmos para recorte de líneas,

este método y sus variaciones, son ampliamente utilizados.Inicialmente, cada punto final de las líneas, se le asigna unvalor binario de 4 digitos, llamado código de región, cada bitrepresenta si el punto está dentro o fuera de la ventana derecorte. En la figura 5 se muestra un ejemplo. Un valor de1 indica que el punto final se encuentra fuera del borde dela ventana. De la misma manera un valor de 0 indica que elpunto final no está fuera (está dentro o sobre el borde) delcorrespondiente borde de la ventana.

Los valores de los bits en cada código son determinadoscomparando los valores de las coordenadas de los puntosfinales con el borde de la ventana de recorte. Un bit se po-ne en 1 si x < xvmin. En lugar de utilizar pruebas de de-sigualdades, podemos determinar los valores para cada có-digo más eficientemente utilizando operaciones de bits:

1. Calcular las diferencias entre las coordenadas de lospuntos finales y los bordes de la ventana.

2. Utilizar el bit de signo resultante de cada cálculo paraestablecer el valor correspondiente del código.

Algoritmo 6 Algoritmo de Sutherland-CohenEntrada: Puntos (p1, p2), extremos del segmento. Ventana

de recorteSalida: Recorte de la figura dado una ventana de recorte

1: para cada extremo de la ventana de recorte hacer2: Para la línea P1P2, determine si la línea es totalmen-

te visible o si puede ser descartada como trivialmentevisible.

3: Si P1 está fuera de la ventana de recorte continúa, delo contrario intercambia P1 y P2.

4: Reemplaza P1 por la intersección de P1P2 con el ex-tremo en turno.

5: fin para

4.4 Algoritmo de subdivisión del punto me-dio.

Encontrar la intersección de una línea con un área de re-corte rectangular puede hacerse por bisecciones, es decir,dividiendo la línea a la mitad y analizando ambas partes, unade ellas se descarta ya sea por ser trivialmente invisible opor ser completamente visible. La búsqueda de la intersec-ción continua en la otra mitad de la línea. Este método tienela enorme ventaja de poderse implementar muy fácilmente

en hardware e incluso en caso de implementarse en softwa-re tiene la ventaja de usar solo aritmética entera dado que laoperación de dividir entre dos es en realidad un corrimientohacia la derecha. El Algoritmo 7 es una versión recursiva deeste método.

Algoritmo 7 Algoritmo de subdivisión del punto medioEntrada: Puntos (p1, p2), extremos del segmento. Ventana

de recorteSalida: Recorte de la figura dado una venta de recorte

1: si (p1, p2) es una línea trivialmente invisible entonces2: Descarta el segmento de línea (p1, p2).3: fin si4: si (p1, p2) es una línea totalmente visible entonces5: Incluye como visible el segmento de línea (p1, p2).6: fin si7: pm = (p1 + P2)/28: Recorta(p1, pm)9: Recorta(pm, p2)

4.5 Algoritmo de Cyrus-Beck para recorte deregiones convexas.

El algoritmo de Cyrus-Beck hace uso del hecho de que unpunto a está dentro de un área de recorte convexa respecto acierta línea que define un borde si se cumple la desigualdad(Camarena, 2010):

n · (b− a) > 0 (47)

donde n es un vector normal a la línea que define el borde yb es cualquier punto en ese borde.

Por supuesto, a y b son a la vez puntos y vectores quevan del origen a la ubicación de los mismos. En realidad laecuación 43 nos dice que si a está dentro del área de recorte,entonces el vector que va de b hacia a (es decir, el vectorb − a) tiene un ángulo interno menor de 90 grados respectoal vector normal n. Por otro lado, el punto a se encuentrafuera del área de recorte si se cumple:

n · (b− a) < 0

Por otro lado el punto a se encuentra justo en el borde si

n · (b− a) = 0 (48)

El Algoritmo de Cyrus-Beck hace uso de la ecuación para-métrica de una línea recta que va de p1 a p2 que es:

p(t) = p1 + (p2 − p1)t (49)

donde t es el parámetro que vale 0 al principio de la línea (enp1) y 1 al final de la misma (en p2).

Aplicando 44 podemos obtener el valor de t para el cual lalínea coincide con la frontera del área de recorte despeján-dolo de:

n · (P (t)− f) = 0 (50)

donde f es cualquier punto en la frontera en cuestión.Lo que la ecuación anterior nos dice es que un vector que

corre a lo largo de la frontera (P (t) − f) tiene exactamente90 grados respecto a la normal que define dicha frontera (n).Despejando t de la ecuación anterior y luego sustituyéndolaen P (t) obtenemos las coordenadas donde la línea es cor-tada por la frontera en cuestión, el proceso se debe repetirpara cada una de las fronteras (líneas borde) que definen elárea de recorte convexa.

Sustituyendo la ecuación 45 en 46 obtenemos:

n · (p1 + (p2 − p1)t− f) = 0

n · (p1 − f) + n · (p2 − p1)t = 0

O bien:

n · w + (n ·D)t = 0

donde D = p2 − p1 es la directriz, ya que define la direcciónde la línea P (t), y w = p1 − f . Despejando t de la ecuaciónanterior:

t = − n · wn ·D

Si n ·D > 0, entonces el valor de t corresponde a un lugarcercano al inicio de la línea, si por el contrario n · D < 0, elvalor de t corresponde a un lugar cercano al final de la línea.

Fig. 8: Recorte en un área convexa.

Ejemplo: Recortar la línea que va del punto (−1, 1) al pun-to (3, 4) de acuerdo al área de recorte mostrada en la Figura8.

La directriz D es: [34

]−[−11

]=

[43

]Para la arista v5 − v6, la normal que apunta hacia adentro

del área de recorte es:

n =

[−1−1

]Entonces

n ·D =

[−1−1

] [43

]= −7 < 0

Lo cual significa que la intersección de la línea con la aristav5 − v6 está cerca del final de la línea.

tomando f =

[24

]como un punto que forma parte de la arista

v5 − v6 determinamos w:

w = p1 − f =

[−11

]−[24

]=

[−3−3

]De ahí que:

n · w =

[−1−1

] [−3−3

]= 6

Finalmente:

t = − n · wn ·D = − 6

−7 =6

7

Lo cual significa que esta arista intersecta a la línea en:

p

(6

7

)= p1 + (p2 − p1)

6

7

=

[−11

]+

([34

]−[−11

])6

7=

[17/725/7

]

Tabla 1: Cálculo de las aristas en la figura 8Arista n f w n · w n ·D ti tf

v1 − v2[11

] [11

] [−20

]−2 1 2

7

v2 − v3[10

] [02

] [−1−1

]−1 4 1

4

v3 − v4[1−1

] [03

] [−1−2

]1 1 −1

v4 − v5[0−1

] [14

] [−2−3

]3 −3 1

v5 − v6[−1−1

] [24

] [−3−3

]6 −7 6

7

v6 − v7[−10

] [33

] [−4−2

]4 −4 1

v7 − v8[−11

] [32

] [−4−1

]3 −1 3

v8 − v1[01

] [21

] [−30

]0 3 0

El proceso se repite para cada una de las aristas, el resul-tado se resume en la Tabla 1. En la columnas etiquetadas tiy tf se encuentran los valores de t correspondientes a lasintersecciones de la línea p1 − p2 con cada arista, cuando elvalor n · D es negativo el valor t se ubica en la columna tfpara recordar que es una intersección cercana al final de lalínea, si en cambio n ·D es una cantidad positiva entonces elvalor t se ubica en la columna ti dado que se trata de una in-tersección cercana al inicio de la línea. Se elige un solo valorde la columna ti, aquel que es el mayor de todos, en nuestroejemplo t = 2/7. De la misma manera, solo elegimos a unsolo valor de la columna tf , es decir al menor de todos, ennuestro ejemplo t = 6/7. Así mismo, aquellas líneas en lasque se cumple la condición ti < tf son las líneas que seencuentran dentro de la ventana. En caso contrario, no seguardan.

Para terminar el ejemplo solo resta decir que la línea re-cortada comienza en t = 2/7 y termina en t = 6/7, locual corresponde a una nueva línea que va de (1/7, 13/7)a (17/7, 25/7).

5. PIPELINE DE VISUALIZACIÓN BIDIMEN-SIONAL

Un paquete gráfico debe permitir a un usuario especificarcual parte de la escena se requiere desplegar y en que lugaren el dispositivo de salida, esto implica aplicar transformacio-nes de coordenadas globales a coordenadas de dispositivoque pueden incluir rotaciones, escalamientos y recortes delas partes de la escena que hayan quedado fuera del áreaseleccionada para ser desplegada.

5.1 Coordenadas locales, coordenadas globa-les, puerto de visión.

Las figuras aisladas están normalmente definidas en coor-denadas de modelado (MC) las cuales son relativas a algunaparte de la misma figura, por ejemplo el centro de la misma,así los vértices de un cuadrado pudieran ser:{(1, 1), (1,−1), (−1, 1), (−1,−1)}. Al establecer una escena,las diferentes figuras que la componen son convertidas acoordenadas globales (WC), entonces los vértices o puntosde control tiene valores relativos a un lugar específico de laescena misma.

Un área de la escena seleccionada para ser desplega-da se denomina “ventana”. Un área del dispositivo de salidadonde la ventana será mapeada se denomina “puerto de vi-sión”. La ventana especifica lo que será desplegado mientrasque el puerto de visión especifica donde será desplegado. Elmapeo de una parte de la escena en coordenadas globa-les a coordenadas de dispositivo implica normalmente mas

Fig. 9: Pipeline de visualización tridimensional.

de una transformación. Opcionalmente podemos convertir acoordenadas de vista (VC) como un método para establecerorientaciones arbitrarias de la ventana, enseguida se puedendefinir coordenadas normalizadas del puerto de visión (en elrango de cero a uno) y mapear las coordenadas de vista acoordenadas de vista normalizadas (NVC). En el paso final,todas las coordenadas contenidas en el puerto de visión sontraducidas a coordenadas de dispositivo (DC). La Figura 9resume este proceso.

Cambiando la posición del puerto de visión podemos verobjetos en diferentes lugares del dispositivo de salida, al cam-biar el tamaño del puerto de visión podemos lograr efectosde magnificación como viendo algo a traves de una lupa.En cambio, si hacemos la ventana mas pequeña tendremosefectos de acercamiento (zoom in) a alguna parte específicade la escena, por supuesto, al hacer la ventana mas grandeharíamos un alejamiento (zoom out). Se pueden lograr efec-tos de “paneo” moviendo la ventana por diferentes lugaresde la escena y manteniendo su tamaño fijo.

Manejar coordenadas de vista normalizadas de cero a unoes de utilidad para separar las transformaciones de vista yotras de las que son específicas del dispositivo, de esta ma-nera el paquete de graficación es independiente del dispo-sitivo de salida, el resultado queda en un cuadrado unitarioque será fácilmente mapeado a las coordenadas de cual-quier dispositivo de salida.

Normalmente todas las transformaciones son preparadaspara aplicarse via una sola matriz de transformación paraahorrar cálculos, el recorte de las líneas que quedan fue-ra del puerto de visión se hace entonces como ultimo paso,esta es una de las más importantes aplicaciones de los al-goritmos de recorte.

5.1.1 Funciones de OpenGL para visualización bi-dimensional.

El método reshape de la interfaz GLEventListener se ac-tiva ante cualquier cambio del tamaño de la ventana de des-pliegue (no confundir con la ventana que toma una parte dela escena), tambien se activa la primera vez que se lanza laaplicación. El método reshape recibe el tamaño de la venta-na de despliegue en los parámetros width y height, estosparámetros son justamente los que necesitamos para esta-blecer el tamaño del puerto de visión que es exactamente loque hace la línea:

gl.glViewport( 0, 0, width, height );

Cuando se pretende graficar solo en dos dimensiones sepuede hacer uso de una función de GLU (Graphics LibraryUtilities) denominada gluOrtho2D donde se define el rangode valores de coordenadas horizontales y verticales que sepretende manejar, así por ejemplo para indicar que en el ejehorizontal los valores posibles para dibujar irán desde 0 has-ta 450 mientras que en el eje vertical estos podrán variardesde 0 hasta 375 usaríamos la línea:

glu.gluOrtho2D( 0.0, 450.0, 0.0, 375.0);

Como en este caso no deseamos hacer ninguna opera-ción de proyección (proyectar figuras 3D en algún plano) seincluyen las líneas:

gl.glMatrixMode( GL.GL_PROJECTION );gl.glLoadIdentity();

La función completa reshape de este ejemplo queda:

public void reshape (GLDrawable drawable,int x,int y,int width,int height) {

GL gl = drawable.getGL();GLU glu = drawable.getGLU();gl.glViewport( 0, 0, width, height );gl.glMatrixMode( GL.GL_PROJECTION );gl.glLoadIdentity();glu.gluOrtho2D(0.0, 450.0, 0.0, 375.0);

}

6. TRANSFORMACIONES GEOMÉTRICASHasta ahora hemos visto como describir una escena en

términos de primitivas gráficas, tales como segmentos de lí-nea, áreas de relleno y atributos asociados con estas primiti-vas. Ahora, veremos las operaciones de transformación quepodemos aplicar a los objetos para moverlos o redimensio-narlos. Estas operaciones son utilizadas en las rutinas queconvierten escenas de descripción del mundo a la salida enun dispositivo. Las operaciones que son aplicadas a las des-cripciones geométricas de un objeto para que este cambiede posición, orientación o tamaño son llamados transforma-ciones geométricas.

6.1 Transformaciones afinesUna transformación afín es aquella que se puede escribir

de la forma:

x′ = axxx+ axyy + bxy′ = ayxx+ ayyy + by (51)

donde axx, axy, bx, ayx, ayy y by son constantes.Una transformación afín es una operación lineal, esto im-

plica que si se aplica la transformación a todos los puntosque forman una línea se obtiene otra línea que también sepuede obtener aplicando la transformación solo a los extre-mos de la línea y se generan los puntos intermedios median-te algún algoritmo de trazado de líneas como el de Bresen-ham, como corolario podríamos decir que si se transformaun punto que está a la mitad de la línea, este punto se ubi-cará justamente a la mitad de la línea transformada.

Ejemplos de transformaciones afines son la traslación, larotación, el escalamiento, la reflexión y la inclinación, cual-quier composición de estas operaciones también será unatransformación afín. Si la transformación afín solo hace usode rotaciones, traslaciones y reflexiones entonces las líneasparalelas al transformarlas continúan siendo paralelas, seconservan los ángulos entre cualquier pareja de líneas.

6.2 Transformaciones geométricas bidimensio-nales básicas. Traslación, Escalamiento yRotación

6.3 Coordenadas Homogéneas.

6.4 Transformaciones compuestas.

6.5 Escalamiento respecto a un punto fijo, Ro-tación respecto a un punto arbitrario.

Podemos controlar la posición de un objeto escalado,eligiendo su posición. Para esto elegimos un punto fijoel cual permanecerá sin cambio después de la trans-formación de escalamiento. Los objetos son redimen-sionados escalando las distancias entre los puntos delobjeto y el punto fijo. Para un punto con coordenadas(x, y) las coordenadas (x′, y′) son calculadas de lassiguientes relaciones:

x′ − xf = (x− xf )sxy′ − yf = (y − yf )sy

Podemos reescribir las ecuaciones para separar lostérminos que se suman.

x′ = x · sx + xf (1− sx)y′ = y · sy + yf (1− sy)

donde los términos xf (1 − sx) y yf (1 − sy) son cons-tantes para todos los puntos del objeto.

Escalamiento general

Para escalar con respecto a un origen dado tenemos:

1. Trasladar el objeto de tal manera que el punto fijocoincida con las coordenadas origen.

2. Escalar el objeto con respecto a la coordenadaorigen

3. Utilizar la traslación inversa del paso 1 para regre-sar el objeto a su posición original.

1 0 xf0 1 yf0 0 1

·sx 0 00 sy 00 0 1

·1 0 −xf0 1 −yf0 0 1

=

sx 0 xf (1− sx)0 sy yf (1− sy)0 0 1

Para obtener las ecuaciones de transformación para larotación de un punto respecto a cierto punto (xr, yr):

x′ = xr + (x− xr)cosθ − (y − yr)senθy′ = yr + (x− xr)senθ − (y − yr)cosθ

Rotación general

Podemos generar una rotación bidimensional tomandoen cuenta cualquier punto pivote (xr, yr) ejecutando lasiguiente secuencia de operaciones.

1. Trasladar el objeto de tal manera que el punto fijosea movido a la coordenada origen.

2. Rotar el objeto con respecto al origen.

3. Trasladar el objeto de tal manera que el punto pi-vote se regre a su posición original.

La matrix compuesta para esta secuencia se obtienecon la siguiente multiplicación de matrices.

1 0 xr0 1 yr0 0 1

·cosθ −senθ 0senθ cosθ 00 0 1

·1 0 −xr0 1 −yr0 0 1

=

cosθ −senθ xr(1− cosθ) + yrsenθsenθ cosθ yr(1− cosθ)− xrsenθ0 0 1

6.6 Reflexiones

6.7 Transformaciones Geométricas en 3D Sim-ples. Escalamiento, Traslación, Rotaciónrespecto al eje X, Rotación respecto al ejeY . Rotación respecto al eje Z.

6.8 Rotación respecto a un eje arbitrario. De-terminación de la Matriz de transforma-ción mediante:

No siempre queremos rotar alrededor de uno de los tresejes, necesitamos una matriz de transformación que nos per-mita realizar una rotación con un cierto ángulo θ alrededor deun eje arbitrario, para determinar dicha matriz existen tresmétodos populares, a continuación describiremos cada unode ellos.

6.8.1 Composición de matricesCuando un objeto es rotado con referencia a un eje que

no es paralelo a uno de los ejes del sistema de coordena-das, debemos llevar a cabo alguna transformación adicional.En este caso requerimos rotaciones para alinear el eje derotación con un eje seleccionado y entonces traer el eje a suorientación original. Dadas las especificaciones para el ejede rotación y el ángulo de rotación, podemos implementar larotación en 5 pasos.

1. Trasladar el objeto de tal manera que el eje de rotaciónpase por el origen.

2. Rotar el objeto de tal manera que el eje de rotacióncoincida con uno de los ejes.

3. Realizar la rotación especificada alrededor del eje se-leccionado.

4. Aplicar las rotaciones inversas para regresar el eje derotación a su orientación original.

5. Aplica la traslación inversa para regresar el eje de ro-tación en su posición espacial original.

El primer paso en la secuencia de rotación es calcular lamatriz de traslación que situará el eje de rotación de tal ma-nera que pase por el origen. Por que queremos una rotaciónen sentido contrario de las manecillas de reloj movemos elpunto p1 al origen. (Si la rotación hubiera sido especificadaen la dirección opuesta, moveriamos p2 al origen). Esta es lamatriz de traslación.

1 0 0 −x10 1 0 −y10 0 1 −z10 0 0 1

A continuación formulamos las transformaciones para po-

ner el eje de rotación en el eje z.

6.8.2 búsqueda de un conjunto de vectores ortogo-nales

6.8.3 uso de Cuaterniones

6.9 Transformaciones geométricas con OpenGL

6.10 Manejo de pilas de matrices con OpenGL

7. VISUALIZACIÓN 3DYa hemos hablado de transformaciones tridimensionales

de objetos en 3D pero la pantalla de la computadora (o elpapel de la impresora) son superficies, es decir son de solodos dimensiones, por lo tanto necesitamos de una forma pa-ra proyectar nuestros objetos tridimensionales en la pantalla.

7.1 Proyección en paraleloEn una proyección en paralelo, las posiciones de las coor-

denadas son transferidas a el plano de visión por medio delíneas paralelas.

Fig. 10: Proyección paralela de un segmento de línea enun plano de visión

7.2 Proyección en perspectivaPara la proyección en perspectiva, las posiciones de los

objetos son transformadas a coordenadas de proyección alo largo de líneas que convergen a un punto detrás del planode visión. A diferencia de las proyecciones en paralelo, unaproyección en perspectiva no preserva las proporciones re-lativas de los objetos. Sin embargo, las vistas en perspectivason más reales, porque los objetos distantes en la pantallade visualización son de tamaño menor.

En la ingeniería y en dibujos arquitectónicos, se utilizaneste tipo de proyecciones, porque las longitudes y ángulosson dibujados exactamente y pueden ser medidos a partirde los dibujos.

7.3 Pipeline de visualizacion tridimensional

7.4 Volumen de visión

7.5 Funciones de visualización tridimensionalde OpenGL

8. SUPRESIÓN DE LÍNEAS Y SUPERFICIESOCULTAS

Un problema importante en el proceso de desplegar imá-genes que luzcan reales es el de diferenciar las partes visi-bles de aquellas que no se podrían ver desde la posición dealgún observador. Existen varios métodos para lograr esto,expondremos aquí algunos de los mas importantes.

8.1 Supresión de segmentos de líneas ocultas.No solamente para mejorar el aspecto de una gráfica o de

un objeto sino para eliminar la ambigüedad de una figura ypor ende poderla entender, es necesario eliminar las líneaso los segmentos de línea que no deberían verse.

Para ilustrar esto, veamos como al eliminar ciertas líneasde un ambiguo cubo de alambre mostrado en la Figura 11(a), obtenemos el cubo no ambiguo que se muestra en laFigura 11 (b) y al eliminar otras líneas obtenemos el cubo noambiguo mostrado en la Figura 11 (c).

8.1.1 Algoritmo del horizonte flotanteEste algoritmo se utiliza para desplegar funciones de dos

variables y = f(x, z). La función se discretiza, para cadavalor discreto de z se traza la gráfica y = f(x, z = cte),cada valor de z corresponde con un plano, comenzamos porvalores de z que están mas cercanos al observador y convalores de z que se van alejando de este.

Si para cada valor dado de x, el valor y de la curva en elplano actual es mayor que el valor y para todas las curvasanteriores, entonces la curva es visible para ese valor espe-cífico de x, en caso contrario será invisible.

Para implementar este algoritmo simplemente hay que man-tener un arreglo del mismo tamaño que la resolución de la

Fig. 11: Al ocultar líneas de un cubo de alambre se elimi-na la ambigüedad implicita

imagen en el eje x. Los valores de este arreglo representanel horizonte y este horizonte “flota” a medida que cada curvaes dibujada.

Si para algún valor dado de x, el valor y correspondientede la curva en el plano actual es superior al máximo valoro inferior al mínimo valor entre todas las curvas anteriores,entonces la curva actual en dicho valor x es visible, si no secumple ninguna de las dos cosas, entonces es invisible. Paraimplementar el algoritmo del horizonte flotante se requierenentonces dos arreglos uno para almacenar los valores máxi-mos y el otro para almacenar a los mínimos, a estos arreglosse les denominan horizontes flotantes superior e inferior res-pectivamente.

8.2 Determinación de la ecuación de un planoPodemos determinar la ecuación del plano en el que re-

side cualquier cara o de un cuerpo rígido modelado por unnúmero finito de ellas. Cualquier punto (x, y, z) que perte-nezca al plano cumple con su ecuación que es:

ax+ by + cz + d = 0 (52)

o su forma normalizada (para la cual d = 1) que es:

ax+ by + cz = −1

Como tenemos tres incógnitas (a, b, c), entonces necesita-mos tres ecuaciones, es decir tres puntos que pertenezcanal plano (siempre y cuando no sean co-lineales), utilizamospor facilidad vértices que definen la cara cuyo plano quere-mos determinar, entonces si tenemos 3 vértices (x1, y1, z1),(x2, y2, z2) y (x3, y3, z3) entonces tenemos que resolver elsistema de ecuaciones:

ax1 + by1 + cz1 = −1ax2 + by2 + cz2 = −1ax3 + by3 + cz3 = −1

en forma matricial tenemos:x1 y1 z1x2 y2 z2x3 y3 z3

abc

=

−1−1−1

8.3 Determinación del vector Normal a un Plano

Una vez que tenemos la ecuación de un plano ax + by +cz + d = 0 entonces el vector que es normal a ese plano es:

N = (a, b, c)

También podemos determinar el vector normal al plano ha-ciendo el producto cruz o producto vectorial de dos vectoresque residan en ese plano, así es que si tenemos los vérti-ces (x1, y1, z1), (x2, y2, z2) y (x3, y3, z3), entonces podemos

hacer el producto cruz del vector (x1 − x2, y1 − y2, z1 − z2)y (x1 − x3, y1 − y3, z1 − z3). El vector que resulte será unvector normal al plano al que pertenecen esos tres puntosno colineales.

8.4 Detección de caras posteriores. Algoritmode Roberts

La detección de caras posteriores es un proceso cono-cido como “Culling” consiste en eliminar aquellas caras delos objetos de una escena que no pueden ser vistas desdela perspectiva de cierto observador, este proceso no resuel-ve el problema mas general en el que unos objetos tapana otros o ciertas partes de estos, simplemente se encargade averiguar cuales caras están ocultas por el mismo obje-to al que pertenecen. El algoritmo de Robert resuelve esteproblema de forma muy simple, solo funciona para objetosconvexos pero si el objeto es cóncavo siempre se puede di-vidir en varios objetos convexos.

Este método simplemente dice que una cara es posteriory por ende invisible a un observador si se cumple que:

Np ·N < 0

donde Np es el vector normal al plano al que pertenece lacara en cuestión y N es el vector que describe la direcciónde la vista del observador, es decir, si el ángulo entre Np yN es un ángulo obtuso (> 90 y < 180) entonces la cara esposterior, si el ángulo entre esos dos vectores es agudo (> 0y < 90), entonces es una cara visible,

8.5 Algoritmo del Buffer Z o Buffer de pro-fundidad.

Las partes visibles de una escena se pueden descubrir ha-ciendo algo similar al algoritmo del horizonte flotante, es de-cir, podemos mantener un arreglo con las distancias desdeel observador hasta la superficie mas cercana en cada direc-ción que quede dentro del volumen de visión, a diferencia delalgoritmo del horizonte flotante, el arreglo que necesitamosaquí es un arreglo bidimensional del tamaño de la resolu-ción de la imagen deseada. La distancia del observador a lasuperficie mas cercana es la profundidad (en lugar del ho-rizonte) y esta se mide normalmente por la coordenada z,por esta razón al buffer de profundidad también le llamamosbuffer Z. El algoritmo del buffer Z o buffer de profundidad pa-ra efectos de detección de superficies visibles o lo que es lomismo la eliminación de superficies ocultas (HSR por HiddenSurface Removal) consiste en lo siguiente:

Supongamos que todos los objetos que forman la escenatienen caras, no solo se debe pensar en objetos regularescomo los cubos que tienen 6 caras o pirámides (con 4 ca-ras) sino cualquier tipo de objeto, por ejemplo, una tetera sepuede modelar con alrededor de 500 caras triangulares.

Por cada objeto que forma parte de una escena y por ca-da cara que forma parte del objeto, determinar los puntosque la forman, por cada punto (x, y, z) de estos, compararsu profundidad z con la profundidad almacenada en el bufferZ para el correspondiente (x, y), si la profundidad del puntoes menor, reemplaza a la del buffer Z. Los valores de profun-didad de una cara se pueden obtener a partir de la ecuacióndel plano correspondiente a esa cara mediante:

z =−ax− by − d

c(53)

Una vez que se hayan procesado todos los puntos de to-das las caras de todos los objetos de la escena obtendremosen el buffer Z las profundidades mas cercanas y podremossaber de que color debe ser cada pixel (x, y) si además demantener el buffer Z mantenemos un buffer paralelo denomi-nado “buffer del color”. Cada vez que un valor de profundidadsustituye un valor en el buffer Z se sabe a que cara pertene-ce el nuevo valor de profundidad y el color de dicha cara sepuede almacenar en el buffer del color. En resumen:

IF zs < zbuffer[x,y] THENwrite intensity to colorbuffer[x,y];write zs to zbuffer[x,y];

END;

La principal ventaja de este método es su simplicidad, lasdesventajas son:

Demasiados cálculos innecesarios puesto que en de-masiadas ocasiones los pixeles sobreescriben pixelesanteriores.

Posibles errores de cuantización.

No soporta objetos transparentes.

8.6 Algoritmo del Buffer A para superficies trans-parentes.

Como se comentó en la sección anterior, el algoritmo delbuffer Z no puede manejar objetos transparentes o con cier-to grado de transparencia (translucidez). El algoritmo del buf-fer A es en realidad una modificación del algoritmo del bufferZ para soportar objetos translúcidos, la unica razón por laque recibe ese nombre es por que la A está en el extremoopuesto a la Z en el alfabeto. En el buffer A, en lugar dealmacenar simplemente un valor de profundidad se almace-na un apuntador a una lista ligada. Si el primer elemento dela lista es un objeto opaco, entonces la lista termina ahí, sien cambio se trata de un objeto translúcido, entonces la listacontinúa con el siguiente objeto mas cercano en la mismadirección, el cual también pudiera ser otro objeto translúcido,la lista continúa de manera que el último objeto es opaco.Para saber el color final de un píxel se debe recorrer la listaasociada a ese píxel, el color de los objetos translúcidos y elobjeto opaco de la lista correspondiente al píxel se combinanpara obtener el color final.

8.7 Algoritmo del Buffer Z por línea de ras-treo

Para acelerar el método del buffer Z, se puede procederpor línea de rastreo, por cada línea de rastreo, las posicioneshorizontales adyacentes a lo largo de la línea difieren solouna unidad, si se ha determinado que la profundidad en laposición (x, y) es z, entonces la profundidad de la siguienteposición (x+ 1, y) será

z′ =−a(x+ 1)− by − d

c= z − a

c

El valor a/c permanece constante mientras no nos cam-biemos de superficie de manera que al proceder por líneade rastreo, las profundidades se van determinando median-te una simple suma.

8.8 Método de proyección de rayosEn lugar de procesar cada punto de cada polígono de cada

objeto de una escena para determinar cual es la profundidadde la superficie mas cercana al observador en cada píxel delplano de visión. El método de proyección de rayos consisteen trazar una línea perpendicular al plano de visión, deter-minar a cuales polígonos intersecta esta línea y elegir la in-tersección mas cercana al plano de visión, esto se hace porcada pixel del plano de visión. En la Figura 12 se ha trazadoun rayo para cierto píxel y este intersecta 4 polígonos (doscaras de la pirámide y dos caras del cubo), pero la intersec-ción mas cercana al plano de visión es la cara que resultaríavisible al menos en lo que concierne al píxel de donde surgióel rayo. En el método del buffer de profundidad se procesancada uno de los polígonos de la escena en orden para deter-minar el mas cercano para cada pixel mientras que en estemétodo se toman los pixeles en orden y se sigue un rayo porcada píxel, este método ahorra cálculos.

Fig. 12: Detección de superficies visibles mediante elmétodo de trazado de rayos

8.9 Método del árbol BSPEl algoritmo del pintor es probablemente la más simple de

las técnicas para resolver el problema de remover las su-perficies ocultas, se trata de ordenar los polígonos en ordenascendente de profundidad (z) y simplemente desplegarloscompletos comenzando por los de mayor profundidad, los demenor profundidad cubrirán a los de mayor profundidad dela misma manera que en un lienzo al pintar un árbol, este cu-bre la parte del paisaje que queda detrás de él. El algoritmodel pintor falla cuando los polígonos se traslapan como en laFigura 13.

Fig. 13: El algoritmo del pintor no funciona con polígo-nos traslapados

Para solucionar el problema de los polígonos traslapados,se puede dividir el espacio sucesivamente hasta que las dife-rentes regiones en las que el espacio se haya dividido seanlo suficientemente pequeñas para que en su interior ningúnpolígono se traslape en profundidad con ningún otro polí-gono. Un árbol BSP (por Binary Space Partitioning) sirvepara representar la manera en que el espacio ha sido divi-dido. El espacio es particionado estableciendo planos quedividen a los polígonos en aquellos que quedan de un lado yaquellos que quedan del otro lado. Un árbol BSP tiene tantosniveles como planos divisorios, cada plano divisorio divide elespacio en dos (de ahí lo de binario). En la Figura 14, el pri-mer nivel del árbol corresponde con el plano y = 512 y elsegundo nivel corresponde con el plano x = 512, dividiendode esta manera el espacio en 4 regiones.

8.10 Funciones de OpenGL para suprimir su-perficies ocultas

OpenGL implementa tanto la eliminación de caras poste-riores (Algoritmo de Robert) como la eliminación de superfi-cies ocultas mediante el método del buffer Z de profundidad.

Fig. 14: El árbol BSP

La eliminación de caras posteriores se lleva a efecto median-te las funciones:

glEnable(GL_CULL_FACE);glCullFace(modo);

donde modo puede tomar el valor deGL_FRONT ,GL_BACKo GL_FRONT_AND_BACK. Utilizamos GL_BACK (Elmodo predeterminado) para eliminar caras posteriores, si usa-mos GL_FRONT se eliminan las caras frontales, esto tie-ne aplicación por ejemplo para ver el interior de edificios dedepartamentos. Si utilizamos GL_FRONT_AND_BACKse eliminan tanto las caras frontales como las posteriores,quedando solamente los puntos y líneas que no forman po-lígonos. La eliminación de caras se desactiva mediante lafunción:

glDisable(GL_CULL_FACE);

Para usar las rutinas de detección de visibilidad median-te buffer de profundidad debemos solicitar que configure unbuffer de profundidad y un buffer de refresco (el buffer delcolor), esto lo hacemos de la siguiente manera:

glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB|GLUT_DEPTH);

Para inicializar el buffer de profundidad y el buffer del colorhacemos:

glClear(GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT);

Como los valores de profundidad en el sistema de coor-denadas de pantalla 3D están normalizados y quedan en elrango de cero a uno, esta instrucción asigna puros valoresde 1.0 al buffer de profundidad. Finalmente, la detección dela visibilidad se activa mediante:

glEnable(GL_DEPTH_TEST);

y se desactiva mediante:

glDisable(GL_DEPTH_TEST);

9. ILUMINACIÓNLas partes reales de una escena son obtenidas mediante

la generación de proyecciones en perspectiva de los objetosy aplicando efectos de luz natural a las superficies. Un mode-lo de iluminación, también llamado modelo de iluminación,se utiliza para calcular el color de ua posición en la super-ficie del objeto. Los métodos de renderizado de superficieutiliza calculos de colores de modelos de iluminación paradeterminar los colores del píxel para todas las posicionesproyectadas de la escena. Las líneas de rastreo de algorit-mos imagen-espacio utilizan esquemas de interpolación. Elmodelo de iluminación se refiere al cálculo de intensidad deluz en un punto de la superficie.

9.1 Reflexión DifusaCuando la luz es incidente en una superficie opaca, parte

de esta es reflejada y parte es absorbida. La cantidad de luzincidente reflejada por lasuperficie depende del tipo de ma-terial. Los materiales brillosos reflejan más la luz incidente.Para las superficies transparentes, parte de la luz incidentepasa a través del material.

Las superficies que son ásperas tienden a esparcer la luzreflejada en todasla direcciones. La luz esparcida se llamareflexión difusa. El color de un objeto está dado por la refle-xión difusa, cuando el objeto es iluminado con una luz blan-ca, la cual está compuesta de la combinación de todos loscolores. Por ejemplo, un objeto azul, refleja la parte azul dela luz blanca y absorbe todos los demás colores. Si el objetoazul es visto bajo la luz roja, el objeto aparece negro porquela luz incidente es absorbida.

9.2 Ecuación de LambertEn la reflexión difusa la intensidad de luz parece ser la

misma cuando la superficie se observa desde cualquier di-rección. La intensidad no depende pues de la ubicación delobservador pero si depende de la orientación que la superfi-cie tiene respecto a la fuente de luz. La ecuación de Lambertnos dice que la intensidad de luz en una superficie debida ala reflexión difusa se calcula como:

Il,incidente = Ilcosθ

La cantidad de la luz incidente en una superfice desde unorigen con intensidad Il.

9.3 Reflexión Especular

Fig. 15: Objeto reflejado por una luz especular

9.4 Modelado de la Iluminación

9.5 Determinación del vector Normal a un vér-tice.

Fig. 16: Cada normal es perperdicular

9.6 Sombreado de Gourad

9.7 Sombreado de Phong

9.8 Funciones de OpenGL para manejo de Ilu-minación

9.9 Iluminación por proyección de Rayos

9.10 Radiosidad

9.11 Funciones de OpenGL para iluminación

Fig. 17: Imagen sin color

Fig. 18: Imagen utilizando únicamente reflexión difusa.

Fig. 19: Imagen con luz ambiental y reflexión difusa

ReferenciasCamarena, A. (2010). Notas de graficación.

Fig. 20: Imagen con reflexión especular y difusa.

Hearn, D.~D., y Baker, M.~P. (2003). Computer Graphics withOpenGL. Prentice Hall Professional Technical Reference,3 ed.

Rogers, D.~F. (1998). Procedural elements for computergraphics (2nd ed.). New York, NY, USA: McGraw-Hill, Inc.

Rowe, G. (2001). Computer Graphics With Java GrassrootsSeries. Palgrave Macmillan (UK).