Algoritmo de dibujo de líneas

El método más sencillo para dibujar una línea consiste en calcular directamente las posiciones de los píxeles a partir de una ecuación de línea. Dado un punto de partida${\displaystyle (x_{1},y_{1})}$y un punto final${\displaystyle (x_{2},y_{2})}$Los puntos en la línea cumplen la ecuación.${\displaystyle y=m(x-x_{1})+y_{1}}$, con${\displaystyle \textstyle m={\frac {\Delta y}{\Delta x}}={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}}$siendo la pendiente de la recta. La recta se puede dibujar evaluando esta ecuación mediante un bucle simple, como se muestra en el siguiente pseudocódigo :

dx = x2 − x1 dy = y2 − y1 m = dy/dx para x desde x1 hasta x2 hacer y = m × (x − x1) + y1 trazar(x, y)

Aquí, los puntos ya han sido ordenados de manera que${\displaystyle x_{2}>x_{1}}$.

Este algoritmo es innecesariamente lento porque el bucle implica una multiplicación, que es significativamente más lenta que la suma o la resta en la mayoría de los dispositivos. Se puede lograr un método más rápido observando la diferencia entre dos pasos consecutivos:

Por lo tanto, basta con empezar simplemente en el punto${\displaystyle (x_{1},y_{1})}$y luego aumentar${\displaystyle y}$por${\displaystyle m}$una vez en cada iteración del bucle. Este algoritmo se conoce como analizador diferencial digital .

Porque redondeo${\displaystyle y}$redondear al número entero más cercano es equivalente a redondear${\displaystyle y+0.5}$Para evitar el redondeo, se puede utilizar una variable de control adicional que se inicializa con el valor 0,5.${\displaystyle m}$se agrega a esta variable en cada iteración. Luego, si esta variable supera 1.0,${\displaystyle y}$se incrementa en 1 y la variable de control se decrementa en 1. Esto permite que el algoritmo evite el redondeo y solo utilice operaciones con enteros. Sin embargo, para líneas cortas, este bucle más rápido no compensa la costosa división.${\displaystyle \textstyle m={\frac {\Delta y}{\Delta x}}={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}}$, lo cual sigue siendo necesario al principio.

Este algoritmo funciona perfectamente cuando${\displaystyle dx\geq dy}$(es decir, la pendiente es menor o igual a 1), pero si${\displaystyle dx<dy}$(es decir, pendiente mayor que 1), la línea se vuelve bastante dispersa con muchos huecos, y en el caso límite de${\displaystyle dx=0}$Se producirá una excepción de división por cero .

En determinadas situaciones, los algoritmos de dibujo de líneas de un solo color presentan problemas:

El algoritmo Gupta-Sproull se basa en el algoritmo de líneas de Bresenham , pero añade suavizado de bordes (antialiasing) .

Una variante optimizada del algoritmo de Gupta-Sproull se puede escribir en pseudocódigo de la siguiente manera:

DibujarLínea(x1, x2, y1, y2) { x = x1; y = y1; dx = x2 − x1; dy = y2 − y1; d = 2 * dy − dx; // discriminador // Distancia euclidiana del punto (x,y) a la línea (con signo) D = 0; // Distancia euclidiana entre los puntos (x1, y1) y (x2, y2) longitud = sqrt(dx * dx + dy * dy); seno = dy / longitud; cos = dx / longitud; mientras (x <= x2) { IntensificarPíxeles(x, y − 1, D + cos); IntensificarPíxeles(x, y, D); IntensificarPíxeles(x, y + 1, D − cos); x = x + 1 si (d <= 0) { D = D + sen; d = d + 2 * dy; } demás { D = D + sen − cos; d = d + 2 * (dy − dx); y = y + 1; } } }

La función IntensifyPixels(x,y,r) toma una transformación de línea radial y establece la intensidad del píxel (x,y) con el valor de un polinomio cúbico que depende de la distancia r del píxel a la línea.

Boyer y Bourdin introdujeron un algoritmo de aproximación que colorea los píxeles situados directamente debajo de la línea ideal. ^{[ 1 ]} Una línea renderizada de esta manera presenta algunas propiedades especiales que pueden aprovecharse. Por ejemplo, en casos como este, ciertas secciones de la línea son periódicas. Esto da como resultado un algoritmo significativamente más rápido que las variantes precisas, especialmente para líneas largas. El deterioro de la calidad solo es visible en líneas con una pendiente muy baja.

Una forma sencilla de paralelizar la rasterización de líneas monocromáticas consiste en permitir que varios algoritmos de dibujo de líneas dibujen píxeles desplazados a cierta distancia entre sí. ^{[ 2 ]} Otro método consiste en dividir la línea en varias secciones de longitud aproximadamente igual, que luego se asignan a diferentes procesadores para su rasterización. El principal problema reside en encontrar los puntos de inicio y fin correctos de estas secciones.

También existen algoritmos para arquitecturas de procesadores masivamente paralelos con miles de procesadores. En estos, cada píxel de una cuadrícula de píxeles se asigna a un único procesador, que luego decide si el píxel dado debe colorearse o no. ^{[ 3 ]}

Se han desarrollado jerarquías de memoria especiales para acelerar el acceso a la memoria durante la rasterización. Estas pueden, por ejemplo, dividir la memoria en múltiples celdas, cada una de las cuales renderiza una sección de la línea de forma independiente. ^{[ 4 ]} La rasterización con suavizado de bordes también puede ser compatible con hardware dedicado. ^{[ 5 ]}