Algoritmo preciso de dibujo de líneas subpixel (algoritmo de rasterización)

Necesito un algoritmo que puede ser (un poco) más lento que el algoritmo de dibujo de líneas de Bresenham, pero tiene que ser mucho más exacto. Con “exacto” quiero decir: cada píxel tocado debe ser impreso. ¡No más, pero tampoco menos! Lo que significa que usar una línea más gruesa o similar no es una opción, ya que se involucrarán demasiados píxeles. Además, no necesito un marco gráfico o similar como se preguntó antes , ¡necesito el algoritmo! La aplicación no está realmente en ‘gráficos‘, es en el área de geografía donde los píxeles son ‘mosaicos’.

El principal problema para mí es que necesito una precisión subpíxel, lo que significa que una línea podría comenzar en 0.75 / 0.33 y no solo en 0/0 como en el caso de los valores enteros. Traté de crear una solución funcional para las últimas horas pero no puedo hacerlo funcionar; hay demasiados casos extremos.

Primero pensé que una versión anti-aliased como el algoritmo de Wu debería hacerlo pero imprime demasiados píxeles (especialmente para los puntos de inicio y final) y en ciertos casos todavía pierde algunos píxeles, por ejemplo, para líneas muy cortas.

Luego traté de hacer funcionar a Bresenham donde reemplacé el segundo ‘si’ con ‘else if’ como se señala aquí , y está más cerca, pero todavía no está allí. Luego traté de mover el Bresenham de entero a flotante, precisión que resultó en un ciclo sin fin (a medida que los valores x, y saltaban sobre la condición final if (y1 == y2 && x1 == x2) ).

Podría usar la solución ingenua de dibujo de líneas , pero ¿qué delta debería usar? Por ejemplo, si uso 0.1, aún perderé algunos píxeles y usar valores más pequeños probablemente demorará demasiado (y aún faltarán píxeles).

Una solución de trabajo en C / Java / … sería apreciada. Al menos debería funcionar para octante 1 pero una solución completa sería incluso mejor.

Actualización : se me ocurrió la siguiente idea: usar la rasterización de líneas ingenua y puede calcular 4 candidatos de píxeles para cada punto. Luego verifique esos 4 píxeles si la línea realmente los cruza. Pero no estoy seguro si la intersección de línea / caja puede ser lo suficientemente rápida.

Si necesita solo un color constante (no interpolado por el área de píxel utilizada), utilice DDA :

 void line_DDA_subpixel(int x0,int y0,int x1,int y1,int col) // DDA subpixel -> thick { int kx,ky,c,i,xx,yy,dx,dy; x1-=x0; kx=0; if (x1>0) kx=+1; if (x1<0) { kx=-1; x1=-x1; } x1++; y1-=y0; ky=0; if (y1>0) ky=+1; if (y1<0) { ky=-1; y1=-y1; } y1++; if (x1>=y1) for (c=x1,i=0;i 

dónde:

 void pnt(int x,int y,int col); 

es una rutina que rasteriza el píxel (x,y) con color col La fuente está en C ++

Creo que es estrecho pero de todos modos

DDA usa ecuación de línea paramétrica y=k*x+q o x=ky+q depende de la diferencia (si es mayor la diferencia de y por lo que no hay agujeros). La k es dy/dx o dx/dy la división completa se reduce a la resta + sum dentro del ciclo (última línea de cada ciclo). Esto se puede modificar fácilmente en cualquier cantidad de dimensiones (generalmente uso 7D o más con esto). En las máquinas modernas es la velocidad a veces mejor que Bresenham (depende de la plataforma y el uso).

Así es como se ve comparado con el simple DDA

Líneas DDA y DDA_subpixel

[edit2] coordenadas dobles // originalmente [edit1]

OK aquí está el nuevo código:

 void line_DDA_subpixel1(double x0,double y0,double x1,double y1,int col) // DDA subpixel -> thick { int i,n,x,y,xx,yy; // prepare data n-pixels,x1,y1 is line dx,dy step per pixel x1-=x0; i=ceil(fabs(x1)); y1-=y0; n=ceil(fabs(y1)); if (n 

Y así es como se ve:

Las coordenadas DDA y DDA_subpixel dobles

El ángulo debería ser de double precisión ahora, pero pnt (x, y, col) todavía está en números enteros.

[edit3] cruce de cuadrícula de píxeles

 void DDAf_line_subpixel(float x0,float y0,float x1,float y1,int col) // DDA subpixel -> thick { int i,n; float a,a0,a1,aa,b,d; // end-points pnt(x0,y0,col); pnt(x1,y1,col); // x-axis pixel cross a0=1; a1=0; n=0; if (x0x1) { a0=ceil(x1); a1=floor(x0); d=(y1-y0)/(x1-x0); a=a0; b=y1+(a0-x1)*d; n=fabs(a1-a0); } if (a0<=a1) for (aa=a,i=0;i<=n;i++,aa=a,a++,b+=d) { pnt(aa,b,col); pnt( a,b,col); } // y-axis pixel cross a0=1; a1=0; n=0; if (y0y1) { a0=ceil(y1); a1=floor(y0); d=(x1-x0)/(y1-y0); a=a0; b=x1+(a0-y1)*d; n=fabs(a1-a0); } if (a0<=a1) for (aa=a,i=0;i<=n;i++,aa=a,a++,b+=d) { pnt(b,aa,col); pnt(b, a,col); } } 

Finalmente tuve algo de tiempo para esto, así que pellizqué un poco al DDA, pero el id condujo a muchos if así que cambio bastante la rasterización. Ahora todos los cruces de cuadrícula de píxeles (intersecciones) se calculan y luego para cada uno se agrega el subpíxel correcto. Así es como se ve (sin subpíxeles incorrectos):

línea pixel crossing subpixel

Para cada línea de cuadrícula xoy es el primer punto de cruce calculado (a,b) y el step está en un eje 1 píxel y en el segundo el rest de acuerdo con dy/dx o dx/dy . Después de esto, el bucle for llena los subpíxeles ...

Si su línea es delgada y los píxeles son rectangulares (cuadrados):

enter image description here

a continuación, considere el uso de algoritmos de cruce de cuadrícula de voxel, por ejemplo, ver el artículo ” Fast Voxel Traversal Algorithm … ” por Woo y Amanatides.

Implementación práctica (en la sección transversal de la cuadrícula)

Respuesta para comentar:
Inicialización adecuada para las variables de coordenadas X (lo mismo para Y)

  DX = X2 - X1 tDeltaX = GridCellWidth / DX tMaxX = tDeltaX * (1.0 - Frac(X1 / GridCellWidth)) //Frac if fractional part of float, for example, Frac(1.3) = 0.3 

ejemplo en mi respuesta aquí