Un algoritmo de línea más efectivo para determinar las posiciones del pixel, creado por Bresenham, halla las coordenadas enteras más próximas a la trayectoria real de la recta utilizando solamente aritmética entera. Las posiciones de los pixeles en la pantalla se representan por las áreas rectangulares situadas entre líneas de una retícula. En cada uno de estos ejemplos, se necesita escoger entre dos alternativas de pixel en cada posición x. Comenzando desde el punto extremo izquierdo de la recta de la figura 3, se necesita determinar si el siguiente punto en la recta se trazará en la posición (11, 10) o bien en (11, 11). En forma análoga, la figura 4 muestra una trayectoria en línea con pendiente negativa. Aquí, se necesita escoger entre los puntos (51, 50) y (51, 49) como la siguiente posición de pixel que se encenderá. El siguiente pixel que se grafique en cada uno de estos ejemplos será aquel cuyo valor de y está más próximo a la posición real de y sobre la recta.

FIGURA 3	FIGURA 4

Una vez más, empezamos con una recta cuya pendiente es positiva y menor que 1. Las posiciones de los pixeles a lo largo de la trayectoria de la línea pueden trazarse después tomando etapas unitarias en la dirección x y determinando el valor de la coordenada y del pixel más cercano a la recta en cada etapa. Para establecer los cálculos que se necesitan en el algoritmo, se considera la situación que se muestra en la figura 5. Esta figura se supone que la posición del pixel (x_i, y_i) se ha trazado y ahora se necesita decidir cuál es el siguiente pixel que se graficará. Las dos alternativas de la siguiente posición del pixel están en las coordenadas (x_i + 1 , y_i) y (x_i + 1 , y_i + l).

FIGURA 5	FIGURA 6

En la figura 6, las diferencias de coordenadas entre el centro de los dos pixeles y la coordenada y de la recta se rotulan d₁, y d₂. La posición y puede calcularse como

 y = m(x_i + l) + b

Por lo tanto,

d₁ = y - y_i

  = m(x_i + 1) + b - y_i

y 

d₂ = (y_i + 1) - y

  = y_i + 1 - m(x_i + 1) - b

La diferencia entre estas dos distancias es

Ahora definiremos un parámetro que ofrece una medida de las distancias relativas de dos pixeles de la posición actual sobre una recta dada. De la sustitución de m = dy/dx se puede reescribir la ecuación 9 de manera que comprenda solamente aritmética entera:

p_i = dx(d₁ - d₂) (10)

= 2dy . x_i - 2dx . y_i + c

La constante c tiene el valor 2dy + dx(2b - l) y se podría calcular una sola vez para todos los puntos, pero se observará que la ecuación 10 puede ser revisada a fin de eliminar esta constante. El parámetro p_i tiene un valor negativo, si el pixel en la posición y_i está más próximo a la recta que el pixel superior. En este caso, se selecciona el pixel inferior; de lo contrario, se elige el píxel superior.

La ecuación 10 se simplifica relacionando parámetros de intervalos sucesivos de x. Por lo tanto, el valor de cada parámetro sucesivo se obtiene a partir del parámetro calculado con anterioridad. Podemos reescribir la ecuación 10 en la forma

Pero x_i+1 = x_i + 1, de modo que

p_i+1 = p_i + 2dy - 2dx . (y_i+1 - y_i) (11)

Esta ecuación nos da una manera de calcular el valor de cada parámetro sucesivo a partir del anterior. El primer parámetro, p₁, se obtiene de la evaluación de la ecuación 10 con (x₁, y₁) como punto extremo inicial y m = dy/dx:

Las etapas del algoritmo de Bresenham se resumen en el siguiente algoritmo, para una recta con pendiente positiva menor que 1. Como las constantes 2dy, dx y 2(dy-dx) necesitan ser evaluadas y almacenadas sólo una vez, la aritmética comprende únicamente la adición y la sustracción de enteros.

p_i+1 = p_i + 2dy

Pero si p_i >= 0, el siguiente parámetro es

p_i+1 = p_i + 2(dy-dx)

Un procedimiento para implantar el algoritmo se da en el programa que sigue. Las coordenadas de los puntos extremos de la recta sirven de entrada para este procedimiento a través de los parámetros x1, yl, x2 y y2. La llamada de set_pixel fija la posición en el buffer de estructura para el punto seleccionado.

procedure bres_line (xl, yl, x2, y2 : Integer);

Hasta ahora nos hemos limitado al estudio de rectas con pendiente positiva entre 0 y 1.

Cuando van a aplicarse modelos de sombreado a color a áreas de una escena o gráfica, conviene al usuario poder especificar el área que se llenará. Aunque los modelos de llenado podrían aplicarse a los interiores de los límites de un polígono definido con un comando de líneas, el procesamiento se simplifica si se utiliza un procedimiento aparte para definir el llenado de un área. Este punto de vista permite que un área designada se señale de inmediato como aquella que se desplegará con un interior especificado.

Se preenta el comando siguiente para definir el llenado del área de un polígono (el comando dependerá del lenguaje de programación utilizado):

 fill_area (n, x, y)

El área que se llenará está dentro del límite o frontera definido por la serie de n segmentos de línea conectados de (x[1], y[1]) a (x[n], y[n]) y de regreso a (x[1], y[1]

La implantación del comando fill_area de un paquete de gráficas depende del tipo de llenado que se use para desplegar el área. Un usuario podría desear que el área quedara en blanco o bien se llenara con un color sólido o algún patrón. Cuando el interior del área se deja en blanco, fill_area simplemente produce el perfil de la frontera o límite.

Como la circunferencia es una componente común de muchos tipos de imágenes y gráficas, los procedimientos para generar circunferencias (y elipses) se incluyen a menudo en paquetes de gráficas. Los parámetros básicos que definen una circunferencia son las coordenadas del centro (xc, yc) y el radio r (fig. 12). Podemos expresar la ecuación de una circunferencia en varias formas, mediante parámetros de coordenadas Cartesianas o polares. La figura 13 muestra la relación existente entre los parámetros Cartesianos y los polares.

FIGURA 12	FIGURA 13

 Una forma estándar de la ecuación de la circunferencia es el teorema de Pitágoras:

(x - xc)² + (y - yc)² = r² (16)

Esta ecuación podría usarse para trazar una circunferencia recorriendo el eje x enJ

pasos unitarios de xc - r a xc + r y calculando los valores de y correspondientes en cada posición como

y = yc +- (r² - (x - xc)²)^1/2 (17)

 Obviamente, este punto de vista implica una tarea de cálculo considerable en cada etapa y el espaciamiento entre las posiciones de los pixeles trazados no es uniforme, como se muestra en la figura 14. Podríamos ajustar el espaciamiento intercambiando x y y (probando valores de y y calculando valores de x) siempre que el valor absoluto de la pendiente de la circunferencia se hiciera mayor que 1. Pero esto agrega cálculos y la verificación del algoritmo.

Una manera de eliminar el espaciamiento desigual asociado con la ecuación 17 consiste en calcular puntos situados en la frontera circular mediante el uso de coordenadas polares. Si se expresa la ecuación de la circunferencia en forma polar paramétrica se obtiene el par de ecuaciones

x = xc + r . cos teta

y = yc + r . sen teta (18)

Cuando un despliegue se genera con estas ecuaciones mediante el uso de un valor angular fijo de teta, se traza una circunferencia con puntos igualmente espaciados a lo largo de la circunferencia. El tamaño de la etapa seleccionado de teta depende de la aplicación. Para generar circunferencias con un sistema de rastreo con rastreador, se puede fijar el tamaño de la etapa en 1/r y calcular posiciones de pixeles con muy poco espacio entre ellas. Este tamaño de etapa nos da pixeles que están separados aproximadamente una unidad.

Pueden mejorarse estos métodos aprovechando la simetría de las circunferencias. Un punto dado de la circunferencia puede trazarse en otros puntos de la circunferencia intercambiando coordenadas y alterando el signo de los valores coordenados. Como se ilustra en la figura 15, un punto en la posición (x, y) en un sector octavo de una circunferencia puede utilizarse para graficar los otros siete puntos que se muestran. Mediante el uso de este enfoque, podrían generarse todas las posiciones de pixeles alrededor de una circunferencia de un despliegue con rastreador calculando solamente los puntos dentro del sector de x = 0 a x = y.

La determinación de las posiciones de pixeles a lo largo de una circunferencia mediante el uso de la ecuación 17 o 18 requiere una cantidad considerable de tiempo de cómputo. El enfoque del teorema de Pitágoras implica multiplicaciones y extracción de raíces cuadradas, mientras que las ecuaciones paramétricas contienen cálculos trigonométricos y multiplicaciones. Podemos depurar la eficiencia de la generación de circunferencias aplicando un método que reduce los cálculos lo más posible a aritmética entera.

FIGURA 14	FIGURA 15

Como sucede en el algoritmo de generación de líneas, las posiciones enteras a lo largo de una trayectoria circular pueden obtenerse determinando cuál de los dos pixeles está más próximo a la circunferencia en cada etapa. Para simplificar los enunciados del algoritmo, primero se considera una circunferencia con centro en el origen coordenada (xc = 0 y yc = 0). También se calculan los puntos de un octavo de segmento de una circunferencia suponiendo que se obtendrán los puntos restantes por simetría para almacenarse en un rastreador. (Un sistema de rastreo al azar con un generador de vectores podría ampliar los cálculos a través de un cielo completo.) Se toman etapas unitarias en el sentido x, comenzando desde x = 0 y terminando cuando x = y. La coordenada inicial de nuestro algoritmo es por tanto (0, r).

En la figura 16 se muestra la situación en alguna etapa arbitraria del algoritmo. Se supone que la posición(x_i, y_i) se ha determinado como más próxima a la trayectoria de la circunferencia. La siguiente posición es por tanto (X_i + 1, y_i) o bien (x_i + 1, y_i - l).

Según la ecuación 16, el valor real de y en la trayectoria de la circunferencia se determina como

y² = r² - (x_i + 1)²

 La figura 17 ilustra la relación entre y y los valores coordenadas enteros, y_i y y_i - 1. Una medida de la diferencia en las posiciones coordenadas puede definirse en términos del cuadrado de los valores de y como

d₁ = y_i² - y²

    = y_i² - r² + (x_i + 1)² (19)

  y

d₂ = y² - (y_i - 1)²

    = r² - (x_i + 1)² - (y_i - 1)² (20)

FIGURA 16	FIGURA 17

 Ahora se crea un parámetro para determinar la siguiente posición coordenada como la diferencia entre d₁ y d₂:

p_i = d₁ - d₂

Si p_i es negativa, se selecciona el pixel en la posición y_i. De lo contrario, se selecciona el pixel situado en la localidad y_i - 1.

FIGURA 18	FIGURA 20

La prueba de la selección del siguiente pixel se cumple si la trayectoria real pasa sobre y_i o bien debajo de y_i - 1, como se muestra en la figura 18. En el primer caso, la figura 18(a), se tiene d₁ < 0, d₂ > 0 y p_i < 0, de manera que el punto en y_i sería el seleccionado. En el segundo caso, la figura 18 (b), d₁ > 0 y d₂ < 0. Ahora p_i > 0 y el punto en y_i - l es el que se selecciona.

Una forma recursiva del parámetro p se obtiene evaluando p_{i + 1}, en términos de p_i:

Esta expresión puede escribirse en términos de la ecuación 21 como

La posición y, y_i+1 es la misma que y_i o bien la misma que y_i - 1, según el valor de p_i. Comenzando desde p₁, el algoritmo determina cada parámetro p sucesivo desde o a partir del anterior. Se obtiene p₁ haciendo (x₁ y₁) = (0, r) en la ecuación 21:

El siguiente algoritmo resume las etapas que se llevan para calcular coordenadas enteras lo más próximas a la circunferencia definida. Para generalizar el algoritmo de manera que pueda trazarse una circunferencia con posición central arbitraria, simplemente se agrega xc a cada valor sucesivo de x y se agrega yc a cada valor calculado de y.

Aunque se requiere una multiplicación en el cálculo de cada parámetro, el multiplicador es una potencia de 2, de modo que la multiplicación puede implantarse como una operación de cambio lógica. Todas las otras operaciones son simplemente adiciones o sustracciones enteras. El procedimiento que sigue es un código de este algoritmo de circunferencia. La entrada para el procedimiento son las coordenadas del centro y del radio de la circunferencia. El procedimiento carga el arreglo del buffer de estructura con puntos situados en la circunferencia por medio de llamadas de la operación set_pixel.

p₁ = 3 - 2r

procedure bres_circle (x_center, y_center, radius : :Integer);

procedure plot_circle_points;