Algoritmo del círculo de punto medio

Determina los puntos necesarios para rasterizar un círculo.

Rasterización de un círculo de radio 23 con el algoritmo de círculo de punto medio de Bresenham. Solo el verde En realidad, el octante se calcula simplemente se refleja ocho veces para formar los otros siete octantes.

Un círculo de radio 23 dibujado mediante el algoritmo de Bresenham

En gráficos por computadora , el algoritmo del círculo de punto medio es un algoritmo que se utiliza para determinar los puntos necesarios para rasterizar un círculo . Es una generalización del algoritmo de línea de Bresenham . El algoritmo se puede generalizar aún más a las secciones cónicas . ^{[1] [2] [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 anterior: a medida que x aumenta, no se salta ni repite ningún valor de x hasta llegar a 45°. Entonces, durante el bucle while , x aumenta en 1 con cada iteración, e y disminuye en 1 en ocasiones, nunca excediendo 1 en una iteración. Esto cambia en 45° porque ese es el punto donde la tangente es rise = run . Mientras que rise>run antes y rise<run después.

La segunda parte del problema, el determinante, es mucho más complicado. Esto determina cuándo decrementar y . Por lo general, viene después de dibujar los píxeles en cada iteración, porque nunca va por debajo 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 del algoritmo del círculo de punto medio. Pero cuando se mira una esfera, el radio entero de algunos círculos adyacentes es el mismo, pero no se espera que tenga el mismo círculo exacto 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.

• Ciento cincuenta círculos concéntricos dibujados con el algoritmo del círculo de punto medio.
• 
  A la izquierda, todos los círculos están dibujados en negro.
• 
  A la derecha, se utilizan juntos el rojo, el negro y el azul para demostrar la concentricidad de los círculos.

Algoritmo

El objetivo del algoritmo es aproximar un círculo , más formalmente, aproximar la curva usando píxeles; en términos sencillos, cada píxel debe estar aproximadamente a la misma distancia del centro, como es la definición de un círculo. En cada paso, la ruta se extiende al elegir 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, requiriendo solo desplazamientos 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 multiplicarlo por 2. Por lo tanto, un desplazamiento de bits a la izquierda del radio solo produce el diámetro que se define como el radio por dos. ${\displaystyle x^{2}+y^{2}=r^{2}}$ ${\displaystyle x^{2}+y^{2}\leq r^{2}}$ ${\displaystyle x^{2}+y^{2}}$

Este algoritmo comienza con la ecuación del círculo . Para simplificar, supongamos que el centro del círculo está en . Para comenzar, considere solo el primer octante y dibuje una curva que comience en el punto y avance en sentido contrario a las agujas del reloj hasta alcanzar un ángulo de 45°. ${\displaystyle (0,0)}$ ${\displaystyle (r,0)}$

La dirección rápida aquí (el vector base con el mayor aumento de valor) es la dirección (ver Diferenciación de funciones trigonométricas ). El algoritmo siempre da un paso en la dirección positiva (hacia arriba) y, ocasionalmente, da un paso en la dirección lenta (la dirección negativa ). ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle x}$

De la ecuación del círculo se obtiene la ecuación transformada , donde se calcula solo una vez durante la inicialización. ${\displaystyle x^{2}+y^{2}-r^{2}=0}$ ${\displaystyle r^{2}}$

Sean los puntos del círculo una secuencia de coordenadas del vector hasta el punto (en la base habitual). Los puntos se numeran según el orden en que se dibujan, y se asigna al primer punto . ${\displaystyle n=1}$ ${\displaystyle (r,0)}$

Para cada punto se cumple lo siguiente:

${\displaystyle {\begin{aligned}x_{n}^{2}+y_{n}^{2}=r^{2}\end{aligned}}}$

Esto se puede reorganizar de esta manera:

${\displaystyle {\begin{aligned}x_{n}^{2}=r^{2}-y_{n}^{2}\end{aligned}}}$

Y lo mismo para el siguiente punto:

${\displaystyle {\begin{aligned}x_{n+1}^{2}=r^{2}-y_{n+1}^{2}\end{aligned}}}$

Dado que para el primer octante el siguiente punto siempre será al menos 1 píxel más alto que el último (pero también como máximo 1 píxel más alto para mantener la continuidad), es cierto que:

${\displaystyle {\begin{aligned}y_{n+1}^{2}&=(y_{n}+1)^{2}\\&=y_{n}^{2}+2y_{n}+1\end{aligned}}}$

${\displaystyle {\begin{aligned}x_{n+1}^{2}=r^{2}-y_{n}^{2}-2y_{n}-1\end{aligned}}}$

Entonces, reelabore la ecuación del siguiente punto en una recursiva sustituyendo : ${\displaystyle x_{n}^{2}=r^{2}-y_{n}^{2}}$

${\displaystyle {\begin{aligned}x_{n+1}^{2}=x_{n}^{2}-2y_{n}-1\end{aligned}}}$

Debido a la continuidad de un círculo y a que los máximos a lo largo de ambos ejes son los mismos, claramente no se saltará x puntos a medida que avance en la secuencia. Por lo general, se mantiene en la misma coordenada x y, a veces, avanza un punto hacia la izquierda.

La coordenada resultante se traduce luego mediante la adición de coordenadas de punto medio. Estas frecuentes adiciones de números enteros no limitan mucho el rendimiento , ya que esos cálculos de raíz cuadrada se pueden ahorrar en el bucle interno. 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 obtiene a partir de un desplazamiento de ½ píxel al inicio. Hasta la intersección con la línea perpendicular, esto genera un valor acumulado de en el término de error, de modo que este valor se utiliza para la inicialización. ${\displaystyle r}$

Los cálculos frecuentes de cuadrados en la ecuación del círculo, expresiones trigonométricas y raíces cuadradas se pueden evitar nuevamente disolviendo todo en pasos individuales y utilizando 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 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: ${\displaystyle (x_{i},y_{i})}$

${\displaystyle RE(x_{i},y_{i})=\left\vert x_{i}^{2}+y_{i}^{2}-r^{2}\right\vert }$

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 punto en el eje X positivo. Debido a que el radio será un número entero de píxeles, claramente el error de radio será cero: ${\displaystyle (r,0)}$

${\displaystyle RE(x_{i},y_{i})=\left\vert x_{i}^{2}+0^{2}-r^{2}\right\vert =0}$

Como 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, como solo afecta a este octante, los valores de X solo tienen 2 opciones: permanecer iguales a la iteración anterior o disminuir en 1. Se puede crear una variable de decisión que determine si lo siguiente es verdadero: ${\displaystyle y_{i+1}=y_{i}+1}$

${\displaystyle RE(x_{i}-1,y_{i}+1)<RE(x_{i},y_{i}+1)}$

Si se cumple esta desigualdad, entonces se traza ; si no, entonces se traza . Entonces, ¿cómo determinar si se cumple esta desigualdad? Comencemos con una definición de error de radio: ${\displaystyle (x_{i}-1,y_{i}+1)}$ ${\displaystyle (x_{i},y_{i}+1)}$

${\displaystyle {\begin{aligned}RE(x_{i}-1,y_{i}+1)&<RE(x_{i},y_{i}+1)\\\left\vert (x_{i}-1)^{2}+(y_{i}+1)^{2}-r^{2}\right\vert &<\left\vert x_{i}^{2}+(y_{i}+1)^{2}-r^{2}\right\vert \\\left\vert (x_{i}^{2}-2x_{i}+1)+(y_{i}^{2}+2y_{i}+1)-r^{2}\right\vert &<\left\vert x_{i}^{2}+(y_{i}^{2}+2y_{i}+1)-r^{2}\right\vert \\\end{aligned}}}$

La función de valor absoluto no ayuda, por lo que elevamos al cuadrado ambos lados, ya que el cuadrado siempre es positivo:

${\displaystyle {\begin{aligned}\left[(x_{i}^{2}-2x_{i}+1)+(y_{i}^{2}+2y_{i}+1)-r^{2}\right]^{2}&<\left[x_{i}^{2}+(y_{i}^{2}+2y_{i}+1)-r^{2}\right]^{2}\\\left[(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1)+(1-2x_{i})\right]^{2}&<\left[x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1\right]^{2}\\\left(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1\right)^{2}+2(1-2x_{i})(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1)+(1-2x_{i})^{2}&<\left[x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1\right]^{2}\\2(1-2x_{i})(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1)+(1-2x_{i})^{2}&<0\\\end{aligned}}}$

Como x > 0, el término , por lo que dividiendo queda: ${\displaystyle (1-2x_{i})<0}$

${\displaystyle {\begin{aligned}2\left[(x_{i}^{2}+y_{i}^{2}-r^{2})+(2y_{i}+1)\right]+(1-2x_{i})&>0\\2\left[RE(x_{i},y_{i})+Y_{\text{Change}}\right]+X_{\text{Change}}&>0\\\end{aligned}}}$

Por lo tanto, el criterio de decisión cambia de usar operaciones de punto flotante a simples sumas, restas y desplazamientos de bits de números enteros (para las operaciones de multiplicación por 2). Si ⁠ ⁠ ${\displaystyle 2(RE+Y_{\text{Change}})+X_{\text{Change}}>0}$ , entonces decrementamos el valor de x . Si ⁠ ⁠ ${\displaystyle 2(RE+Y_{\text{Change}})+X_{\text{Change}}\leq 0}$ , entonces mantenemos el mismo valor de x . Nuevamente, al reflejar estos puntos en todos los octantes, resulta un círculo completo.

Podemos reducir el cálculo calculando únicamente el delta entre los valores de esta fórmula de decisión a partir de su valor en el paso anterior. Comenzamos asignando ⁠ ⁠ ${\displaystyle E}$ como ⁠ ⁠ ${\displaystyle 3-2r}$ que es el valor inicial de la fórmula en ⁠ ⁠ ${\displaystyle (x_{0},y_{0})=(r,0)}$ , luego como arriba en cada paso si ⁠ ⁠ ${\displaystyle E>0}$ lo actualizamos como ⁠ ⁠ ${\displaystyle E=E+2(5-2x+2y)}$ (y decrementamos X ), de lo contrario ⁠ ⁠ ${\displaystyle E=E+2(3+2y)}$ a partir de ahí incrementamos Y como de costumbre.

El método de Jesko

El algoritmo ya ha sido explicado en gran medida, pero hay más optimizaciones.

El nuevo método presentado ^[4] funciona con sólo 5 operaciones aritméticas por paso (para 8 píxeles) y, por lo tanto, es más adecuado para sistemas de bajo rendimiento. En la operación "si", sólo se comprueba el signo (¿positivo? Sí o No) y hay una asignación de variable, que tampoco se considera una operación aritmética. La inicialización en la primera línea (desplazamiento de 4 bits a la derecha) se debe únicamente a la belleza y no es realmente necesaria.

De esta forma obtenemos operaciones contables dentro del bucle principal:

1. La comparación x >= y (se cuenta como una resta: x - y >= 0)
2. y=y+1 [y++]
3. t1 + y
4. t1-x

   La comparación t2 >= 0 no se tiene en cuenta porque no se realiza ninguna operación aritmética real. En la representación de complemento a dos de las variables, solo se debe comprobar el bit de signo.

5. x=x-1 [x--]

Operaciones: 5

t1 = r / 16 x = r y = 0 Repetir hasta que  x < y Los píxeles (x, y) y todos los píxeles simétricos están coloreados (8 veces) y = y + 1 t1 = t1 + y  t2 = t1 - x  Si  t2 >= 0 t1 = t2  x = x - 1

Dibujar octantes incompletos

Las implementaciones anteriores siempre dibujan solo octantes o círculos completos. Para dibujar solo un cierto arco desde un ángulo hasta un ángulo , el algoritmo primero debe calcular las coordenadas y de estos puntos finales, donde es necesario recurrir a cálculos trigonométricos o de raíz cuadrada (consulte Métodos para calcular 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 en el intervalo deseado. Después de terminar este arco, el algoritmo puede finalizar prematuramente. ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle x}$ ${\displaystyle y}$

Si los ángulos se dan como pendientes , entonces no es necesaria trigonometría ni raíces cuadradas: simplemente verifique que esté entre las pendientes deseadas. ${\displaystyle y/x}$

Generalizaciones

También es posible utilizar el mismo concepto para rasterizar una parábola , una elipse o cualquier otra curva bidimensional . ^[5]

Referencias

1. Donald Hearn; M. Pauline Baker (1994). Gráficos por ordenador . Prentice-Hall. ISBN 978-0-13-161530-4.
2. Pitteway, MLV, "Algoritmo para dibujar elipses o hipérbolas con un trazador digital", Computer J., 10(3) noviembre de 1967, pp 282-289
3. Van Aken, JR, "Un algoritmo eficiente de dibujo de elipse", CG&A, 4(9), septiembre de 1984, págs. 24-35
4. Para conocer el historial de la publicación de este algoritmo, consulte https://schwarzers.com/algorithms
5. Zingl, Alois (diciembre de 2014). "La belleza del algoritmo de Bresenham: una implementación sencilla para trazar líneas, círculos, elipses y curvas de Bézier". easy.Filter . Alois Zingl . Consultado el 16 de febrero de 2017 .

Enlaces externos

• Dibujar círculos - Un artículo sobre cómo dibujar círculos, que deriva de un esquema simple a uno eficiente
• Algoritmo del círculo de punto medio en varios lenguajes de programación