algorithm - flood - Dibujar líneas con alias de 1 píxel de espesor en tiempo real

bresenham line drawing algorithm

Question

Breve reseña: estoy trabajando en una aplicación de dibujo basada en la web y una de las herramientas que estoy implementando es un lápiz de 1 píxel de espesor. La herramienta permite al usuario dibujar líneas alias de 1px en el lienzo.

Para determinar dónde está dibujando el usuario en el lienzo, se controlan las coordenadas del mouse. Si mouse1 se mantiene presionado, el pixel que el cursor está sobre cambiará. Esencialmente funciona igual que la herramienta de lápiz en Photoshop.

NOTA: el algoritmo de Bresenham no funcionará para esta situación. Mi entrada se envía en tiempo real, por lo que no estoy dibujando una línea de P0 a P1, donde la distancia entre P0 y P1 es de muchos píxeles. En general, P1 es un vecino de P0.

El problema que estoy teniendo es que mis líneas resultantes no tienen un peso perfectamente limpio de 1px. Aquí hay un ejemplo:

Tenga en cuenta que ambas líneas se dibujan a mano, por lo que hay alguna variación. Lo que es interesante es que Photoshop es capaz de hacer una representación de 1px mucho más clara de la línea que dibujo. La razón por la cual mi línea se ve más sucia es debido a esto:

Al dibujar con la herramienta en mi aplicación, los píxeles rojos se rellenan. En Photoshop, los píxeles rojos no se completan. Esto tiene sentido porque para pasar de un píxel dado a, digamos, a su vecino del sudeste, ya sea el vecino del este o del sur probablemente pasará por alto. Existe una posibilidad extremadamente pequeña de que el cursor pase exactamente sobre la esquina en el vecino del sudeste, evitando el dibujo del píxel rojo, pero esto normalmente no sucede.

Entonces, la pregunta que me queda es cómo Photoshop puede omitir los píxeles rojos que se muestran en mis líneas. Lo único que podía pensar era esperar hasta que dos píxeles se pusieran en cola antes de dibujar alguno de ellos, así sabría si se pasó por alto a un "vecino de la esquina". En ese caso, simplemente no dibujaría el primero de los dos píxeles porque sería equivalente a un píxel rojo en mi diagrama. Esto corre el riesgo de no dibujar un píxel previsto si el usuario dibuja un píxel, mueve el cursor un píxel hacia el sur y luego un píxel hacia el este. Ambos píxeles deberían dibujarse, pero el algoritmo diría lo contrario.

¿Algunas ideas? ¿Cómo podría Photoshop manejar este problema?

Answer 1

La diferencia entre ambas líneas es básicamente que Photoshop está reconsiderando el n-1 píxel dibujado DESPUÉS de dibujar el píxel ny borrándolo si da positivo con una de las siguientes máscaras:

 x 1 x       x 1 x
 1 o x   or  x o 1
 x x x       x x x

o

 x x x       x x x
 1 o x   or  x o 1
 x 1 x       x 1 x

x = No me importa
o = El píxel n-1
1 = pixel marcado después de dibujar el pixel n

O escrito como lógica:

Supongamos que el píxel n-1 está en [i, j], entonces, después de marcar el píxel n, verifique:

If ( (a[i-1,j  ]==1 && a[i  ,j-1]==1) ||
     (a[i-1,j  ]==1 && a[i  ,j+1]==1) ||
     (a[i  ,j-1]==1 && a[i+1,j  ]==1) ||
     (a[i  ,j+1]==1 && a[i+1,j  ]==1))
Then
     Unmark a[i,j];

Puede que desee dibujar su línea con un píxel retrasado solo por no mostrar sus píxeles "desaparecidos" (aunque dudo que sea notable a esa escala).

.

Answer 2

Original : Eche un vistazo al algoritmo de línea de Bresenham. Se puede extender fácilmente con respecto al suavizado, etc.

Editar : Con respecto al desarrollo de la pregunta y las discusiones (especialmente los comentarios a continuación), me gustaría extraer algunos puntos interesantes: la herramienta de lápiz de Photoshop también dibuja líneas muy similares con píxeles "este" y "sureste" también , si el mouse se mueve con relativa lentitud, lo que proporciona muchas muestras para todos esos píxeles. Tan pronto como el mouse se mueve más rápido, la trayectoria no proporciona muestras para todos los píxeles directamente adyacentes. El resultado sería la línea deseada de 1 píxel de espesor. En conclusión, observamos: no hay "magia" detrás de la herramienta de lápiz de Photoshop; parece escanear menos muestras. Para más detalles ver discusiones / comentarios a continuación.

Answer 3

Supongo que finalmente resolvió su pregunta (han pasado 6 años ...), pero solo quería decir que su aplicación parece funcionar realmente mejor que Photoshop en este caso particular. Aunque creo que sé cuál era tu objetivo (evitar los agrupamientos de píxeles), el "grosor constante" se logra mejor con tu aplicación (a pesar de esas agrupaciones no deseadas), mientras que Photoshop crea un patrón de "cuerda de salchicha" que puede ser más inteligente, pero no tan ancho constante y, por lo tanto, no tan "real". Es probable que se deba a un manejo diferente de los valores decimales (redondeo) y a la selección de los píxeles para llenar u omitir. Pero, nuevamente, este es un viejo tema.