Algoritmo de dibujo lineal

Dos líneas rasterizadas. Los píxeles de colores se muestran como círculos. Arriba: selección monocroma; abajo: Gupta-Sproull anti-aliasing; la línea ideal se considera aquí como una superficie.

En gráficos por computadora, un algoritmo de dibujo lineal es un algoritmo para aproximar un segmento de línea en medios gráficos discretos, como pantallas e impresoras basadas en píxeles. En tales medios, el dibujo lineal requiere una aproximación (en casos no triviales). Los algoritmos básicos rasterizan líneas en un color. Una mejor representación con múltiples gradaciones de color requiere un proceso avanzado, suavizado espacial.

En medios continuos, por el contrario, no se necesita ningún algoritmo para dibujar una línea. Por ejemplo, los osciloscopios de rayos catódicos utilizan fenómenos analógicos para dibujar líneas y curvas.

Lista de algoritmos de dibujo lineal

Líneas usando Xiaolin El algoritmo de Wu, mostrando "ropey" apariencia.

La siguiente es una lista parcial de algoritmos de dibujo lineal:

• algoritmo inactivo
• Analizador diferencial digital (algoritmo gráfico) — Similar al algoritmo de tracción de líneas ingenuas, con variaciones menores.
• El algoritmo de línea de Bresenham — optimizado para usar solamente adiciones (es decir, ninguna división Multiplicaciones); también evita computaciones de puntos flotantes.
• Xiaolin El algoritmo de línea de Wu — puede realizar anti-aliasing espacial, aparece "ropey" desde el brillo que varía a lo largo de la línea, aunque este efecto puede ser muy reducido pre-compensando los valores de píxel para la curva de gamma de la pantalla objetivo, por ejemplo out = en ^ (1/2.4).
• algoritmo de Gupta-Sproull

Un algoritmo de dibujo lineal ingenuo

El método más simple de apantallamiento es el dibujo directo de la ecuación que define la línea.

dx = x2 – x1
dy = y2 - y1
para x desde x1 a x2 doy = y1 + dy × (x − x1) / dx
plot(x, y)

Es aquí que los puntos ya han sido ordenados para que x_{1}}" xmlns="http://www.w3.org/1998/Math/MathML">x2■x1{displaystyle x_{2}x_{1}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/88ad1ff5ed10c069b85f1de99b085401a4ae5c72" style="vertical-align: -0.671ex; width:7.866ex; height:2.176ex;"/>. Este algoritmo funciona bien cuando dx≥ ≥ dSí.{displaystyle dxgeq dy} (es decir, la pendiente es menor o igual a 1), pero si <math alttext="{displaystyle dxdx.dSí.{displaystyle dx wondy}<img alt="dx (es decir, la pendiente superior a 1), la línea se vuelve bastante escasa con muchas lagunas, y en el caso limitado de dx=0{displaystyle dx=0}, una división por cero excepción ocurrirá.

El algoritmo de dibujo lineal ingenuo es ineficiente y, por lo tanto, lento en una computadora digital. Su ineficiencia se debe a la cantidad de operaciones y al uso de cálculos de punto flotante. En su lugar, se prefieren algoritmos como el algoritmo de línea de Bresenham o el algoritmo de línea de Xiaolin Wu.

Algoritmo Gupta y Sproll

El algoritmo Gupta-Sproll se basa en el algoritmo de línea de Bresenham, pero agrega suavizado.

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

DrawLine(x1, x2, y1, y2) {
x = x1;
y = y1;
dx = x2 - x1;
dy = y2 - y1;
d = 2 * dy − dx; // discriminador

// Distancia euroclidiana del punto (x, y) de la línea (firmado)
D = 0;

// Distancia euroclidiana entre puntos (x1, y1) y (x2, y2)
longitud = sqrt(dx * dx + dy * dy);

pecado = dx / longitud;
porque = dy / longitud;
 mientras (x.
IntensificarPixels(x, y − 1, D + cos);
IntensificarPixels(x, y, D);
IntensificarPixels(x, y + 1, D - cos);
x = x + 1
 si (d י= 0) {
D = D + pecado;
d = d + 2 * dis;
} más {}
D = D + pecado - porque;
d = d + 2 * (dy − dx);
y = y + 1;
}
}
}

La función IntensifyPixel(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 desde el línea.