En gráficos por computadora , el algoritmo de círculo de punto medio es un algoritmo que se utiliza para determinar los puntos necesarios para rasterizar un círculo . El algoritmo del círculo de Bresenham se deriva del algoritmo del círculo del punto medio. [ cita requerida ] El algoritmo se puede generalizar a secciones cónicas . [1]
El algoritmo está relacionado con el trabajo de Pitteway [2] y Van Aken. [3]
Resumen
Este algoritmo dibuja los ocho octantes simultáneamente, comenzando desde cada dirección cardinal (0 °, 90 °, 180 °, 270 °) y se extiende en ambos sentidos para alcanzar el múltiplo más cercano de 45 ° (45 °, 135 °, 225 °, 315 ° ). Puede determinar dónde detenerse porque cuando y = x, ha alcanzado los 45 °. La razón para usar estos ángulos se muestra en la imagen de arriba: A medida que aumenta y, no salta ni repite ningún valor de y hasta alcanzar los 45 °. Entonces, durante el ciclo while, y se incrementa en 1 en cada iteración, yx disminuye en 1 en ocasiones, sin exceder nunca 1 en una iteración. Esto cambia a 45 ° porque ese es el punto donde la tangente es subida = corrida. Mientras que subir> correr antes y subir
La segunda parte del problema, el determinante, es mucho más complicada. Esto determina cuándo disminuir x. Por lo general, viene después de dibujar los píxeles en cada iteración, porque nunca baja del radio del primer píxel. Debido a que en una función continua, la función para una esfera es la función para un círculo con el radio dependiente de z (o cualquiera que sea la tercera variable), es lógico que el algoritmo para una esfera discreta (vóxel) también dependa de este algoritmo de círculo de punto medio. Pero al mirar una esfera, el radio entero de algunos círculos adyacentes es el mismo, pero no se espera que tenga exactamente el mismo círculo adyacente a sí mismo en el mismo hemisferio. En cambio, un círculo del mismo radio necesita un determinante diferente, para permitir que la curva se acerque un poco más al centro o se extienda más.
Algoritmo
El objetivo del algoritmo es aproximar la curva usando píxeles; en términos sencillos, cada píxel debe estar aproximadamente a la misma distancia del centro. En cada paso, la ruta se amplía eligiendo el píxel adyacente que satisface pero maximiza . Dado que los píxeles candidatos son adyacentes, la aritmética para calcular la última expresión se simplifica y solo requiere cambios de bits y adiciones. Pero se puede hacer una simplificación para comprender el desplazamiento de bits. Tenga en cuenta que un desplazamiento de bits a la izquierda de un número binario es lo mismo que multiplicar por 2. Ergo, un desplazamiento de bits a la izquierda del radio solo produce el diámetro que se define como radio multiplicado por dos.
Este algoritmo comienza con la ecuación del círculo . Para simplificar, suponga que el centro del círculo está en. Considere primero el primer octante solamente y dibuje una curva que comience en el punto y avanza en sentido antihorario, alcanzando el ángulo de 45.
La dirección rápida aquí (el vector base con el mayor aumento de valor) es ladirección. El algoritmo siempre da un paso en positivodirección (hacia arriba), y ocasionalmente da un paso en la dirección lenta (el negativo dirección).
De la ecuación del círculo se obtiene la ecuación transformada , dónde se calcula solo una vez durante la inicialización.
Deje que los puntos en el círculo sean una secuencia de coordenadas del vector al punto (en la base habitual). Los puntos se numeran según el orden en el que se extraen, con asignado al primer punto .
Para cada punto, se cumple lo siguiente:
Esto se puede reorganizar así:
Y lo mismo para el siguiente punto:
Dado que para el primer octante el siguiente punto siempre será al menos 1 píxel más alto que el anterior (pero también como máximo 1 píxel más alto para mantener la continuidad), es cierto que:
Entonces, reelabora la ecuación del siguiente punto en una recursiva sustituyendo :
Debido a la continuidad de un círculo y a que el máximo a lo largo de ambos ejes es el mismo, claramente no saltará x puntos a medida que avanza en la secuencia. Por lo general, permanece en la misma coordenada x y, a veces, avanza uno.
Luego, la coordenada resultante se traduce agregando coordenadas de punto medio. Estas frecuentes adiciones de enteros no limitan mucho el rendimiento , ya que esos cálculos cuadrados (raíz) se pueden ahorrar en el ciclo interno a su vez. Nuevamente, el cero en la ecuación del círculo transformado se reemplaza por el término de error.
La inicialización del término de error se deriva de un desplazamiento de ½ píxel al inicio. Hasta la intersección con la línea perpendicular, esto conduce a un valor acumulado de en el término de error, de modo que este valor se utilice para la inicialización.
Los cálculos frecuentes de cuadrados en la ecuación circular, las expresiones trigonométricas y las raíces cuadradas se pueden evitar nuevamente disolviendo todo en pasos simples y usando el cálculo recursivo de los términos cuadráticos de las iteraciones anteriores.
Variante con aritmética basada en números enteros
Al igual que con el algoritmo de línea de Bresenham , este algoritmo se puede optimizar para matemáticas basadas en números enteros. Debido a la simetría, si se puede encontrar un algoritmo que solo calcule los píxeles de un octante, los píxeles se pueden reflejar para obtener el círculo completo.
Comenzamos definiendo el error de radio como la diferencia entre la representación exacta del círculo y el punto central de cada píxel (o cualquier otro punto matemático arbitrario en el píxel, siempre que sea consistente en todos los píxeles). Para cualquier píxel con un centro en, el error de radio se define como:
Para mayor claridad, esta fórmula para un círculo se deriva en el origen, pero el algoritmo se puede modificar para cualquier ubicación. Es útil comenzar con el puntoen el eje X positivo. Debido a que el radio será un número entero de píxeles, claramente el error de radio será cero:
Debido a que comienza en el primer octante positivo en sentido antihorario, avanzará en la dirección con el mayor recorrido , la dirección Y, por lo que está claro que. Además, debido a que se trata solo de este octante, los valores X tienen solo 2 opciones: permanecer igual que la iteración anterior o disminuir en 1. Se puede crear una variable de decisión que determine si lo siguiente es cierto:
Si esta desigualdad se mantiene, entonces grafique ; si no, entonces trama. Entonces, ¿cómo determinar si esta desigualdad se mantiene? Comience con una definición de error de radio:
La función de valor absoluto no ayuda, así que eleva ambos lados al cuadrado, ya que un cuadrado siempre es positivo:
Dado que x> 0, el término , entonces dividir obtiene:
Por lo tanto, el criterio de decisión cambia de usar operaciones de punto flotante a una simple suma, resta y desplazamiento de bits de enteros (para las operaciones de multiplicar por 2). Si, luego disminuya el valor de X. Si, luego mantenga el mismo valor de X. Nuevamente, al reflejar estos puntos en todos los octantes, resulta un círculo completo.
Dibujando octantes incompletos
Las implementaciones anteriores siempre dibujan solo octantes o círculos completos. Para dibujar solo un cierto arco desde un ángulo a un ángulo , el algoritmo necesita primero calcular el y coordenadas de estos puntos finales, donde es necesario recurrir a cálculos trigonométricos o de raíz cuadrada (ver Métodos de cálculo de raíces cuadradas ). Luego, el algoritmo de Bresenham se ejecuta sobre el octante o círculo completo y establece los píxeles solo si caen dentro del intervalo deseado. Después de terminar este arco, el algoritmo se puede finalizar prematuramente.
Si los ángulos se dan como pendientes , entonces no se necesitan trigonometría ni raíces cuadradas: simplemente verifique que se encuentra entre las pendientes deseadas.
Generalizaciones
También es posible utilizar el mismo concepto para rasterizar una parábola , elipse o cualquier otra curva bidimensional . [4]
Referencias
- ^ Donald Hearn; M. Pauline Baker (1994). Gráficos por computadora . Prentice Hall. ISBN 978-0-13-161530-4.
- ^ Pitteway, MLV, " Algoritmo para dibujar elipses o hipérbolas con un trazador digital ", Computer J., 10 (3) de noviembre de 1967, págs. 282-289
- ^ Van Aken, JR, " Un algoritmo de dibujo de elipse eficiente ", CG&A, 4 (9), septiembre de 1984, págs. 24-35
- ^ Zingl, Alois (diciembre de 2014). "La belleza del algoritmo de Bresenham: una implementación simple para trazar líneas, círculos, elipses y curvas de Bézier" . fácil.Filtrar . Alois Zingl . Consultado el 16 de febrero de 2017 .
enlaces externos
- Dibujar círculos : un artículo sobre cómo dibujar círculos, que se deriva de un esquema simple a uno eficiente.
- Algoritmo de círculo de punto medio en varios lenguajes de programación