Hispanopedia Wiki
Articulo de referencia

Algoritmo del círculo del punto medio

Rasterización de un círculo de radio 23 con el algoritmo de círculo de punto medio de Bresenham. Solo se calcula el octante verde; simplemente se refleja siete veces para formar...

Hispanopedia WikiContenido en espanolLectura gratuita
Rasterización de un círculo de radio 23 con el algoritmo de círculo de punto medio de Bresenham. Solo se calcula el octante verde; simplemente se refleja siete 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 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 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 ambas direcciones 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 omite ni repite ningún valor de x hasta alcanzar los 45°. Entonces, durante el bucle while , x se incrementa en 1 con cada iteración, e y se decrementa en 1 ocasionalmente, nunca excediendo 1 en una iteración. Esto cambia en 45° porque ese es el punto donde la tangente es elevación = recorrido . Mientras que elevación > recorrido antes y elevación < recorrido después.

La segunda parte del problema, el determinante, es mucho más compleja. Este determina cuándo decrementar y . Generalmente se aplica después de dibujar los píxeles en cada iteración, ya que nunca baja del radio del primer píxel. Dado que en una función continua , la función para una esfera es la misma que para un círculo cuyo radio depende de z (o de la tercera variable), es lógico pensar que el algoritmo para una esfera discreta ( de vóxeles ) también se basaría en el algoritmo del círculo del punto medio. Sin embargo, al observar 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 en el mismo hemisferio. En cambio, un círculo del mismo radio necesita un determinante diferente, para permitir que la curva se acerque ligeramente al centro o se extienda más.

Algoritmo

El objetivo del algoritmo es aproximar un círculo o, más formalmente, la curva.incógnita2+y2=r2{\displaystyle x^{2}+y^{2}=r^{2}}utilizando píxeles. Para simplificar, nuestro objetivo es aproximar un círculo de centro.(0,0){\displaystyle (0,0)}y radio enteror∈norte{\displaystyle r\in \mathbb {N} }. Además, solo dibujamos hasta el primer octante del plano, para lo cual dibujamos una curva desde el punto(r,0){\displaystyle (r,0)}y procede en sentido contrario a las agujas del reloj hasta un ángulo de 45°; los octantes restantes se pueden llenar fácilmente rotando y/o reflejando ese primer segmento de la curva alrededor del centro. En cada paso, la ruta se extiende eligiendo el píxel adyacente que mejor satisfaceincógnita2+y2=r2{\displaystyle x^{2}+y^{2}=r^{2}}.

La dirección "rápida" en el primer octante (el vector base con el mayor aumento de valor) es lay{\displaystyle y}-dirección (véase diferenciación de funciones trigonométricas ). En la práctica, esto significa que el algoritmo siempre da un paso en la dirección positiva.y{\displaystyle y}dirección (hacia arriba), y ocasionalmente da un paso en la dirección "lenta" (la negativa)incógnita{\displaystyle x}dirección, hacia la izquierda). Si el punto dibujado en el pasonorte{\displaystyle n}es(incógnitanorte,ynorte){\displaystyle (x_{n},y_{n})}, por lo tanto imponemosynorte+1=ynorte+1{\displaystyle y_{n+1}=y_{n}+1}y tienen que decidir si establecerincógnitanorte+1{\displaystyle x_{n+1}}aincógnitanorte{\displaystyle x_{n}}oincógnitanorte−1{\displaystyle x_{n}-1}.

La elección se realiza calculando la distancia entre el punto medio de decisión.(incógnitanorte−0,5,ynorte+1){\displaystyle (x_{n}-0.5,y_{n}+1)}al centro del círculo, de ahí el nombre del algoritmo. Con la suposición anterior de un círculo de centro(0,0){\displaystyle (0,0)}, esta distancia es igual ad=(incógnitanorte−0,5)2+(ynorte+1)2{\displaystyle d={\sqrt {(x_{n}-0.5)^{2}+(y_{n}+1)^{2}}}}. Sid>r{\displaystyle d>r}El punto medio matemáticamente se encuentra fuera del círculo, y el punto candidato más interno está en(incógnitanorte−1,ynorte+1){\displaystyle (x_{n}-1,y_{n}+1)}debe dibujarse. Inversamente sid<r{\displaystyle d<r}, el punto medio se encuentra dentro del círculo y el punto candidato(incógnitanorte,ynorte+1){\displaystyle (x_{n},y_{n}+1)}satisface mejor la ecuación del círculo. La iteración completa para el primer octante es la siguiente:

incógnita0=ry0=0dnorte=(incógnitanorte−12)2+(ynorte+1)2incógnitanorte+1={incógnitanortesi dnorte<rincógnitanorte−1si dnorte>rynorte+1=ynorte+1{\displaystyle {\begin{aligned}x_{0}&=r\\y_{0}&=0\\d_{n}&={\sqrt {\left(x_{n}-{\frac {1}{2}}\right)^{2}+(y_{n}+1)^{2}}}\\x_{n+1}&={\begin{cases}x_{n}&{\text{si }}d_{n}<r\\x_{n}-1&{\text{si }}d_{n}>r\end{cases}}\\y_{n+1}&=y_{n}+1\end{aligned}}}

La iteración termina una vez que la línea de pendiente de 45°y=incógnita{\displaystyle y=x}se cruza, por lo tanto, tan pronto como se cumple la condicióny>incógnita{\displaystyle y>x}se cumple.

Variante con aritmética basada en números enteros.

Al igual que con el algoritmo de la línea de Bresenham original , este algoritmo se puede optimizar para usar solo matemáticas basadas en números enteros. Comenzamos definiendo el error de radio.PAGnorte{\displaystyle P_{n}}como la diferencia entrednorte2{\displaystyle d_{n}^{2}}y el radio al cuadrador2{\displaystyle r^{2}}para evitar tener que calcular una raíz cuadrada costosa y no entera. Esto también cambia ligeramente la condición para determinarincógnitanorte+1{\displaystyle x_{n+1}}:

PAGnorte=dnorte2−r2=(incógnitanorte−12)2+(ynorte+1)2−r2incógnitanorte+1={incógnitanortesi PAGnorte<0incógnitanorte−1si PAGnorte>0{\displaystyle {\begin{aligned}P_{n}&=d_{n}^{2}-r^{2}=\left(x_{n}-{\frac {1}{2}}\right)^{2}+(y_{n}+1)^{2}-r^{2}\\x_{n+1}&={\begin{cases}x_{n}&{\text{si }}P_{n}<0\\x_{n}-1&{\text{si }}P_{n}>0\end{cases}}\end{aligned}}}

Para eliminar el1/2{\displaystyle 1/2}En este caso, el error de radio se puede calcular recursivamente:

PAGnorte+1=(incógnitanorte+1−12)2+(ynorte+1+1)2−r2=(incógnitanorte+1−12)2+(ynorte+1)2+2(ynorte+1)+1−r2=(incógnitanorte+1−12)2+PAGnorte−(incógnitanorte−12)2+2(ynorte+1)+1=PAGnorte+(incógnitanorte+12−incógnitanorte2)−(incógnitanorte+1−incógnitanorte)+2(ynorte+1)+1{\displaystyle {\begin{aligned}P_{n+1}&=\left(x_{n+1}-{\frac {1}{2}}\right)^{2}+(y_{n+1}+1)^{2}-r^{2}\\&=\left(x_{n+1}-{\frac {1}{2}}\right)^{2}+(y_{n}+1)^{2}+2(y_{n}+1)+1-r^{2}\\&=\left(x_{n+1}-{\frac {1}{2}}\right)^{2}+P_{n}-\left(x_{n}-{\frac {1}{2}}\right)^{2}+2(y_{n}+1)+1\\&=P_{n}+\left(x_{n+1}^{2}-x_{n}^{2}\right)-(x_{n+1}-x_{n})+2(y_{n}+1)+1\end{aligned}}}

Junto con la condición enincógnitanorte+1{\displaystyle x_{n+1}}computaciónPAGnorte+1{\displaystyle P_{n+1}}se convierte

PAGnorte+1=PAGnorte+{2(ynorte+1)+1=2ynorte+1+1si PAGnorte<02(ynorte+1)−2(incógnitanorte−1)+1=2ynorte+1−2incógnitanorte+1+1si PAGnorte>0{\displaystyle P_{n+1}=P_{n}+{\begin{cases}2(y_{n}+1)+1&=2y_{n+1}+1&{\text{si }}P_{n}<0\\2(y_{n}+1)-2(x_{n}-1)+1&=2y_{n+1}-2x_{n+1}+1&{\text{si }}P_{n}>0\end{cases}}}

Un valor inicialPAG0{\displaystyle P_{0}}para(incógnita0,y0)=(r,0){\displaystyle (x_{0},y_{0})=(r,0)}se obtiene mediante aproximación:

PAG0=(r−12)2+(0+1)2−r2=r2−r+14+1−r2=1,25−r≈1−r{\displaystyle {\begin{aligned}P_{0}&=\left(r-{\frac {1}{2}}\right)^{2}+(0+1)^{2}-r^{2}\\&=r^{2}-r+{\frac {1}{4}}+1-r^{2}\\&=1.25-r\\&\approx 1-r\end{aligned}}}

Este algoritmo optimizado se puede implementar en Python de la siguiente manera:

import numpy as np # solo para el array de imágenesr = 67 # radio del círculoimg = np . zeros ([ 2 * r + 1 ] * 2 , dtype = int ) # imagen de tamaño (2r + 1) x (2r + 1) para ajustarse al círculo x , y , p = r , 0 , 1 - r # valores iniciales x0 = r, y0 = 0, p0 = 1 - r while x >= y : # mientras el punto (x, y) esté en el primer octante for j , k in [( 1 , 1 ), ( 1 , - 1 ), ( - 1 , 1 ), ( - 1 , - 1 )]: # dibujar en todos los cuadrantes img [ j * x + r , k * y + r ] = 1 img [ k * y + r , j * x + r ] = 1 x , y = x - ( 1 if p > 0 else 0 ), y + 1 # actualizar x e y según el error de radio p p += 1 - 2 * x + 2 * y si p > 0 sino 1 + 2 * y # actualiza el error de radio p con x e y actualizados

El método de Jesko

Un algoritmo de círculo de punto medio mejorado [ 4 ] solo requiere 5 operaciones aritméticas por paso (para 8 píxeles) y, por lo tanto, es más adecuado para sistemas de bajo rendimiento. Las operaciones contadas en el bucle principal son:

  1. La comparación x >= y (se considera 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, ya que no se realiza ninguna operación aritmética real. En la representación en complemento a dos de las variables, solo es necesario comparar el bit de signo .
  5. x=x-1 [x--]

Operaciones: 5

t1 = r / 16 x = r y = 0 Repetir hasta que x < y El píxel (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

Dibujando octantes incompletos

Las implementaciones anteriores siempre dibujan solo octantes o círculos completos. Para dibujar solo un arco determinado desde un ánguloα{\displaystyle \alpha }en ánguloβ{\displaystyle \beta }, el algoritmo necesita primero calcular elincógnita{\displaystyle x}yy{\displaystyle y}coordenadas de estos puntos finales, donde es necesario recurrir a cálculos trigonométricos o de raíz cuadrada (ver 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 dentro del intervalo deseado. Después de completar este arco, el algoritmo puede finalizarse prematuramente.

Si los ángulos se dan como pendientes , entonces no es necesario usar trigonometría ni raíces cuadradas: simplemente compruebe quey/incógnita{\displaystyle y/x}está entre las pendientes deseadas.

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 computadora . 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 para dibujar elipses ", CG&A, 4(9), septiembre de 1984, págs. 24-35
  4. ↑ Para conocer el historial de 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 .
  • Dibujar círculos : un artículo sobre cómo dibujar círculos, que pasa de un esquema simple a uno eficiente.
  • Algoritmo del círculo del punto medio en varios lenguajes de programación
Lecturas relacionadas
6 articulos
Gráficos de computadoraGráficos de computadoraLos gráficos por computadora se ocupan de generar imágenes y arte con la ayuda de computadoras . Los gráficos por computadora son una tecnología fu...RasterizaciónRasterizaciónEn gráficos de computadora , la rasterización ( inglés británico ) o rasterización ( inglés americano ) es la tarea de tomar una imagen descrita en...CírculoCírculoUn círculo es una figura que consta de todos los puntos de un plano que se encuentran a una distancia dada de un punto dado, el centro . La distanc...Algoritmo de línea de BresenhamAlgoritmo de línea de BresenhamEl algoritmo de línea de Bresenham es un algoritmo de dibujo de líneas que determina los puntos de una imagen rasterizada n -dimensional que deben ...Sección cónicaSección cónicaUna sección cónica , cónica o curva cuadrática es una curva obtenida a partir de la superficie de un cono que interseca un plano . Los tres tipos d...Dirección cardinalDirección cardinalLos cuatro puntos cardinales son las cuatro direcciones principales de la brújula : norte , sur , este y oeste , comúnmente denotados por sus inici...