UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD Escuela de Ciencias Básicas, Tecnología e Ingeniería Ingeniería de Sistemas Módulo del curso Computación Gráfica

CAPÍTULO 5 Algoritmos básicos En este capítulo se revisan los fundamentos geométricos y matemáticos a partir de los cuales se generan los algoritmos que dibujan primitivas gráficas como líneas, circunferencias y arcos. Para su desarrollo se utilizó el capítulo correspondiente del texto de Claudio Delrieux y se complementa con la codificación en Java de los algoritmos. Es muy difícil escoger un conjunto de primitivas gráficas que sea adecuado para la representación de todo tipo de entidades gráficas. Sin embargo, el siguiente subconjunto resulta suficiente en la práctica: Puntos: Se especifican a partir de su localización y color. Su discretización es directa, como se mencionó con anterioridad. Segmentos de recta: Son esenciales para la mayor parte de las entidades. Se especifican a partir de un par de puntos que representan sus extremos. Circunferencias: En algunos casos representar entidades curvadas con segmentos poligonales puede ser inadecuado o costoso, por lo que en la prácticas las circunferencias o círculos se adoptan como primitivas. Se especifican con la posición de su centro y su radio. Polígonos: Son indispensables para representar entidades sólidas. Se representan a partir de la secuencia de puntos que determina la poligonal de su perímetro.

Lección 21 Especificación de una discretización En el momento de escoger un método de discretización para una primitiva gráfica, es indispensable contar con criterios que permitan evaluar y comparar las ventajas y desventajas de las distintas alternativas. Entre todas las especificaciones posibles, podemos mencionar las siguientes: Apariencia: Es la especificación más obvia, aunque no es fácil describirla en términos formales. Normalmente se espera que un segmento de recta tenga una “apariencia recta” más allá de que se hallan escogido los pixels matemáticamente más adecuados. Tampoco debe tener discontinuidades. Debe pasar por la discretización del primer y último punto del segmento. Debe ser uniforme, etc. Simetría e invariancia geométrica: Esta especificación se refiere a que un método de discretización debe producir resultados equivalentes si se modifican algunas propiedades geométricas de la primitiva que se está discretizando. Por

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD Escuela de Ciencias Básicas, Tecnología e Ingeniería Ingeniería de Sistemas Módulo del curso Computación Gráfica

ejemplo, la discretización de un segmento no debe variar si dicho segmento se traslada a otra localización en el espacio, o si es rotado, etc. Simplicidad y velocidad de cómputo: Como los métodos tradicionales de discretización de primitivas se desarrollaron hace tres décadas, en momentos en que las posibilidades del hardware y software eran muy limitadas, los resultados eran muy sensibles al uso de memoria u operaciones aritméticas complejas. Por lo tanto, los métodos tienden a no depender de estructuras complejas y a ser directamente implementables en hardware específico de baja complejidad.

21.1 Métodos de discretización Dada una primitiva gráfica a discretizar, debemos encontrar los pixeles que la representen de la manera más correcta posible. Para ello, lo más adecuado es caracterizar matemáticamente a dicha primitiva, de modo que su discretización pueda efectuarse en forma sencilla. Entre los diversos métodos que pueden plantearse destacamos los dos siguientes: Evaluar su ecuación diferencial a diferencias finitas: Este método, denominado DDA (discrete diference analyzer) consiste en plantear la ecuación diferencial de la primitiva a discretizar, y luego evaluar dicha expresión a intervalos adecuados. Análisis del error: Estos métodos fueron desarrollados por Bressenham y se basan en analizar, dado un pixel que pertenece a la discretización de la primitiva, cuál es el próximo pixel que minimiza una determinada expresión que evalúa el error que comete la discretización.

Lección 22 Segmentos de recta El análisis de los métodos de discretización de rectas parte de considerar el comportamiento esperado en determinados casos particulares. Dichos casos surgen de suposiciones específicas que simplifican el problema, pero que al mismo tiempo se pueden generalizar a todos los demás casos por medio de simetrías. Dado un segmento de recta que va de (x0; y0) a (x1; y1), se supone que:   

x = (x1 - x0 )  0, y = (y1 - y0 )  0, y x  y.

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD Escuela de Ciencias Básicas, Tecnología e Ingeniería Ingeniería de Sistemas Módulo del curso Computación Gráfica

Esto equivale a trabajar en el “octavo” del espacio de pantalla sombreado en la Figura 38, donde el origen es el pixel que corresponde a la discretización del punto (x0;y0) y la zona sombreada a los lugares donde puede ubicarse el punto (x1;y1 ).

Figura 38 Espacio designado para caracterizar la discretización de rectas

22.1 Segmentos de recta DDA Como ya se mencionó, los métodos DDA evalúan la ecuación diferencial de la primitiva a intervalos finitos. En el caso particular de los segmentos de recta, la ecuación diferencial es:

El método busca encontrar una secuencia de n + 1 puntos tales que (x0;y0) = (x0;y0); (x1;y1); … (xn;yn) = (x1;y1). La discretización de cada uno de ellos son los pixeles de la discretización del segmento. Esta propiedad, si bien es trivial, es de gran importancia porque determina que la discretización de un segmento de recta es invariante frente a transformaciones afines. Esto significa que es equivalente transformar los extremos del segmento y discretizar el segmento transformado, o discretizar primero y transformar cada punto obtenido. Sin embargo, la primera alternativa es mucho más eficiente.

Dada la ecuación diferencial y un incremento finito arbitrario , podemos pasar de un pixel dado de la secuencia al siguiente por medio de la expresión

 determina la “frecuencia” de muestreo del segmento. Un valor muy pequeño

determina que muchas muestras producirán puntos que serán discretizados al

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD Escuela de Ciencias Básicas, Tecnología e Ingeniería Ingeniería de Sistemas Módulo del curso Computación Gráfica

mismo pixel. Por el contrario, un valor muy grande determinaría que el segmento aparezca “punteado” en vez de ser continuo como corresponde. Un valor práctico es elegir x = 1 y por lo tanto n = x, es decir, la discretización tiene tantos pixeles como longitud tiene el segmento en la variable que más varía (más uno, dado que la secuencia tiene n + 1 puntos). Al mismo tiempo es fácil ver que

En la Figura 39 es posible ver el resultado de discretizar un segmento particular por el método DDA. Observese que los puntos extremos (x0; y0) a (x1;y1) son en efecto puntos y por lo tanto están ubicados en cualquier lugar dentro del pixel que corresponde a su discretización.

Figura 39 Discretización de un segmento de recta con DDA

Un algoritmo sencillo escrito en lenguaje Java que computa la discretización de un segmento de recta por el método DDA se muestra en la Figura 40. Obsérvese que se computan las variables en punto flotante, y que además se requiere una división en punto flotante que corresponde al cálculo de m. Un pequeño paréntesis para explicar algunas sentencias que pueden causar dudas: 1. Sobre el parámetro Graphics g (línea 26), corresponde al contexto gráfico de la ventana (algo así como un lienzo) sobre el cual se dibuja. 2. La llamada al método setColor (línea 34) permite modificar el color actual con el cual se está dibujando, se toma el color como un objeto de tipo Color que puede ser de los preterminados de Java o creado a partir de los parámetros r, g, b. Esta llamada al método setColor permite modificar el color del “lápiz” que dibuja sobre el contexto gráfico.

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD Escuela de Ciencias Básicas, Tecnología e Ingeniería Ingeniería de Sistemas Módulo del curso Computación Gráfica

Figura 40 Codificación en Java del algoritmo DDA de dibujo de líneas

3. Java no tiene una sentencia básica para dibujar puntos (pixeles), en este caso se utiliza la sentencia g.drawRect (línea 35) para dibujar un rectángulo con un ancho y alto de 0, que en su ejecución se traduce a pintar un único pixel ubicado en el punto enviado como parámetro. 4. En la misma sentencia g.drawRect (línea 35) se utiliza el “casting” a enteros para lograr la discretización de las coordenadas flotantes.

La ejecución del algoritmo daría como resultado algo similar a lo mostrado en la Figura 41 para 3 líneas diferentes. Para poder discretizar un segmento de recta en cualquiera de las posibilidades es necesario considerar las simetrías que se aplican. Si por ejemplo no se cumple que y = (y1 - y0)  0, entonces hay que considerar pendientes negativas (simetría A), caso que el algoritmo de la Figura 40 realiza automáticamente. En cambio, si x = (x1 - x0 )  0, entonces es Figura 41 Ejecución del algoritmo DDA necesario decrementar a x en el ciclo e iterar en Java mientras no sea menor que x1 (simetría B).

Por último, si no se cumple que x  y, entonces es necesario intercambiar los roles de las variables x e y (simetría C). Cualquier combinación de situaciones se puede resolver con combinaciones de simetrías (ver Figura 42).

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD Escuela de Ciencias Básicas, Tecnología e Ingeniería Ingeniería de Sistemas Módulo del curso Computación Gráfica

Figura 42 Simetrías para discretizar segmentos de recta

22.2 Segmentos de rectas por Bressenham En el algoritmo DDA para segmentos de recta es necesario computar sumas entre las variables en punto flotante, y además se requiere una división en punto flotante para computar la pendiente. El mérito del algoritmo que vamos a presentar consiste en que todas las operaciones se realizan en aritmética entera por medio de operaciones sencillas, y por lo tanto, su ejecución es más rápida y económica, y es de fácil implementación con hardware específico. El punto de partida del análisis es el siguiente. Si la discretización de los puntos extremos del segmento debe pertenecer a la discretización del segmento, entonces es conveniente efectuar la llamada al algoritmo luego de discretizar los extremos. Esto significa que (x0; y0) y (x1; y1),y por lo tanto x y y son enteros.

Figura 43 Si p pertenece a la discretización el próximo punto será E o D

Luego, si p es un pixel que pertenece a la discretización del segmento, entonces en las condiciones particulares mencionadas, el próximo pixel solamente puede ser el ubicado a la derecha (E o “hacia el este”), o el ubicado en diagonal hacia la derecha y hacia abajo (D o “en diagonal”) como se muestra en la Figura 43.

La decisión de ir hacia el paso E o D se toma en función del error que se comete en cada caso. En este algoritmo se considera que el error es la distancia entre el

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD Escuela de Ciencias Básicas, Tecnología e Ingeniería Ingeniería de Sistemas Módulo del curso Computación Gráfica

centro del pixel elegido y el segmento de recta, medida en dirección del eje Y positivo del espacio de pantalla (es decir, hacia abajo). Si el error en p fuese cero, entonces al ir hacia E el error pasa a ser m (la pendiente del segmento), y en D el error pasa a ser m - 1 (ver Figura 44).

Figura 44 Error al desplazarse en E

Figura 45 Elección del próximo pixel

En general, si en p el error es e, la actualización del error es:  

Paso a E : e = e + m Paso a D : e = e + m –1

Por lo tanto, la elección del paso E o D depende de que el valor absoluto de e+m sea o no menor que el valor absoluto de e+m-1. Expresado de otra manera, sea e el error en un determinado pixel. Si e +m> 0.5 entonces el segmento de recta pasa más cerca del pixel D, y si no, pasa más cerca del pixel E (ver Figura 45). Una de las economías de cómputo del método proviene de poder evaluar el error preguntando por cero. Es fácil ver que si se inicializa el error en e = m – 0.5 entonces en cada paso hay que chequear e >0 para elegir D. La otra economía proviene de realizar manipulaciones algebraicas para efectuar un cómputo equivalente pero en aritmética entera. Como se evalúa el error por cero, multiplicar el error por una constante no afecta el resultado. Por lo tanto, multiplicamos el error por 2x. A partir de dicho cambio, se constatan las siguientes igualdades:

 y  e0  2x  0.5   2y  x  x   

Paso a E : e = e+2y Paso a D: e = e+2(y-x)

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD Escuela de Ciencias Básicas, Tecnología e Ingeniería Ingeniería de Sistemas Módulo del curso Computación Gráfica

De esta manera todas las operaciones se efectúan en aritmética entera, con su correspondiente agilización del tiempo de procesamiento.

Figura 46 Algoritmo de Bressenham para segmentos de recta

La implementación del algoritmo de Bressenham para segmentos de recta se muestra en la Figura 46. Teniendo en cuenta que los productos por 2 en aritmética entera se efectúan con un desplazamiento a izquierda, es posible observar que el mismo utiliza operaciones elementales e implementables con hardware específico muy sencillo.

Lección 23 Discretización de circunferencias Como en el caso de los segmentos de recta, en la discretización de circunferencias o círculos es posible trabajar un sólo segmento de la circunferencia y se obtienen las demás por simetría. Igualmente se dispone de algoritmos DDA y de Bressenham para el dibujo de circunferencias. En este aparte se mostrará una adaptación del algoritmo DDA a partir de la ecuación de la circunferencia, tomado de la página internet de Roberto Albornoz. Para poder realizar el dibujo de la circunferencia usaremos las ecuaciones de la circunferencia en coordenadas polares que son:

x  r * cos  y  r * sen 

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD Escuela de Ciencias Básicas, Tecnología e Ingeniería Ingeniería de Sistemas Módulo del curso Computación Gráfica

Estas ecuaciones serán las que ocuparemos para calcular cada punto (x,y) del círculo, donde el r será obviamente el radio de círculo y  será el ángulo que forma el radio con la parte positiva del eje x. En forma gráfica sería así:

Figura 47 Circunferencia con coordenadas polares

El ángulo deberá estar en radianes ya que las funciones de seno y coseno que incluye Java, trabajan con los ángulos en radianes. La fórmula para transformar grados a radianes es la siguiente: radianes 

gra dos *  180

Entonces para dibujar el círculo de un radio determinado, solamente tenemos que hacer un ciclo desde 0 hasta 360, pero con incrementos pequeños, calcular cada punto con las ecuaciones en coordenadas polares e ir dibujando cada punto. El ciclo en vez de ir de 0 a 360 (ángulos en grados) irá de 0 a 6.28 (360*3.14/180=6.28) ya que el ángulo debe estar en radianes. Como dijimos el ciclo de 0 a 6.28 debe hacerse con incrementos pequeños, no contando de uno en uno, ya que para un círculo de radio muy grande, podrían aparecer huecos entre un punto y el siguiente, por lo tanto tenemos que usar un incremento fraccionario. El valor 0.005 produce buenos resultados. Dibujar el círculo punto a punto es una tarea un poco lenta, debido a que se debe calcular en cada punto el seno y el coseno del ángulo, y estas funcionas son muy lentas. Para solucionar esto se pueden crear tablas predefinidas o pre-calculadas. En la siguiente figura se muestra el código en Java que permitiría dibujar el círculo en una ventana.

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD Escuela de Ciencias Básicas, Tecnología e Ingeniería Ingeniería de Sistemas Módulo del curso Computación Gráfica

Figura 48 Código en Java para el dibujo de circunferencias

Nótese que al calcular las coordenadas x e y, estamos sumándoles las coordenadas cx e cy. Esto se hace para trasladar el centro del círculo a cualquier punto que queramos. De esta forma, para dibujar un círculo solamente es necesario especificar las coordenadas del centro (cx, cy), el radio, el color del círculo y el contexto gráfico.

Figura 49 Resultado de la ejecución del algoritmo dibujo de circunferencias

Lección 24 Dibujo de polígonos Se considera un polígono una figura cerrada, formada a partir de varias líneas. Para la discretización de polígonos se considerarán 2 tipos de polígonos: los irregulares y los regulares, en concordancia con lo mostrado por Steven R Davidson en su curso de gráficos disponible en internet.

24.1 Polígonos irregulares La graficación de polígonos irregulares se realiza a partir de un conjunto de puntos que se unen secuencialmente, el polígono se cierra al unir el primer y último puntos. A continuación se muestra el código Java que dibujaría un polígono irregular a partir de un vector de elementos de tipo Punto y el correspondiente número de puntos.

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD Escuela de Ciencias Básicas, Tecnología e Ingeniería Ingeniería de Sistemas Módulo del curso Computación Gráfica

Figura 50 Código en java para el dibujo de polígonos

Figura 51 Resultado de la ejecución del algoritmo de dibujo de Polígonos

Cabe recordar que en Java, al igual que en C, el índice de los vectores inicia en 0. Por tanto, la primera línea se dibuja desde el primer punto (índice 0) hasta el segundo punto (índice 1), continúa del segundo al tercero (índice 2) y así sucesivamente, hasta dibujar la línea del penúltimo punto (índice N-2) hasta el último punto del vector (índice N-1). Al finalizar el ciclo, dibuja la línea de cierre del polígono entre el último punto (índice N-1) y el primero (índice 0).

Como se podrá deducir del código el objeto Punto incluye las coordenadas x e y de un punto en el plano cartesiano.

24.2 Polígonos regulares Un polígono regular se compone de aristas/lados de igual longitud. Esto implica que el ángulo entre cada arista contigua es el mismo. Si trazamos un segmento del centro a un vértice y otro segmento del centro a otro vértice contiguo, entonces el ángulo entre estos dos segmentos es un divisor de 2π = 360°. En otras palabras, cada ángulo mencionado es inversamente proporcional a la cantidad de lados del polígono regular. Podemos usar la siguiente fórmula: 

α = 2π / N, donde α es el ángulo, y N es la cantidad de lados

Crearemos polígonos regulares en base a una circunferencia que circunscribe nuestro polígono regular. Esto implica, que el centro de la circunferencia coincide con el centro geométrico de cualquier polígono regular. Para esto, necesitamos usar algunas funciones trigonométricas, junto con el ángulo ya calculado. El paso

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD Escuela de Ciencias Básicas, Tecnología e Ingeniería Ingeniería de Sistemas Módulo del curso Computación Gráfica

principal es averiguar la coordenada del siguiente vértice de nuestro polígono. Usaremos las siguientes fórmulas:  x i = cx + r * cos( i*α )  y i = cy + r * sen( i*α ) donde:  i = 0,1,2,...,N-1,  r es el radio de la circunferencia, y  c = (cx, cy) es la coordenada del centro geométrico de la circunferencia y del polígono. Al agregar el centro a nuestra fórmula, conseguimos mover el centro geométrico del origen (0,0) al que nosotros deseemos. En la Figura 52 se muestra el código que generaría los polígonos regulares.

Figura 52 Código en java para dibujar polígonos regulares

Los parámetros de entra para el método especifican el número de lados del polígono (N), el punto centro de la circunferencia (centro), el radio de la circunferencia (radio), el contexto gráfico (g) y el color.

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD Escuela de Ciencias Básicas, Tecnología e Ingeniería Ingeniería de Sistemas Módulo del curso Computación Gráfica

Observe que es necesario hacer un proceso de conversión a entero del dato resultante en la multiplicación del coseno del ángulo por el radio (líneas 46 y 47), ya que las coordenadas de los puntos se deben expresar como datos enteros. Los datos así calculados se utilizan en la conformación de cada vértice del polígono (línea 48). Finalmente, una vez obtenidas las coordenadas de todos los vértices del polígono se realiza la llamada al proceso de dibujarPolígonos explicado Figura 53 Resultado de la ejecución del en la sección anterior (línea 50). algoritmo para dibujar polígonos regulares

Lección 25 Llenado de áreas Si bien existen diversos métodos, aquí presentaremos el más económico y difundido, que se basa en encontrar la intersección de todos los lados del polígono con cada línea de barrido (a y constante), por lo que el método se denomina conversión scan del polígono. Este método es de gran importancia porque se generaliza a una clase de algoritmos denominados scan-line para resolver determinados problemas de iluminación y sombreado en tres dimensiones. Todo polígono plano puede descomponerse en triángulos. Por lo tanto el triángulo será la base del análisis de la conversión scan de polígonos en general. Para computarla es necesario dimensionar dos arreglos auxiliares de enteros minx, maxx que para cada línea de barrido almacenarán el menor y mayor x respectivamente.

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD Escuela de Ciencias Básicas, Tecnología e Ingeniería Ingeniería de Sistemas Módulo del curso Computación Gráfica

Figura 54 Dibujo scan de un polígono

1. Inicializar minx a infinito y maxx a menos infinito. 2. Discretizar cada arista del triángulo (con DDA o Bressenham) reemplazando la sentencia de dibujado por  if (x>maxx[y]) maxx[y]=x;  if (x