algorithm graphics

algorithm - ¿Cómo creo una línea de grosor arbitrario usando Bresenham?



graphics (10)

Algunas rutas simples para usar:

  1. para cualquier ancho n donde n es impar. para cualquier punto p trazado también traza los puntos arriba / abajo para n / 2 (si la línea es> 45 grados, dibuje de lado a lado).
    • No es realmente una línea adecuada del grosor correcto, más como un lápiz en cursiva, pero muy rápido.
  2. para el punto de inicio p (x, y) elija los puntos t0 y b de modo que estén centrados en p pero n píxeles separados. para el punto final haga lo mismo resultando en t1 b1. Dibuja líneas desde t0 -> t1, t1-> b1, b1 -> t0, b0 -> t1. Rellena el rectángulo resultante.
    • El truco aquí es escoger los puntos para que aparezcan ortogonales a la dirección del camino.
  3. para cada punto p en la línea en lugar de dibujar un punto, dibuje un círculo.
    • Esto tiene la ventaja de hacer que los puntos finales estén "limpios" sin importar la orientación.
    • no debería haber necesidad de renderizar círculos en sólido, excepto el primero.
    • algo lento

Actualmente estoy usando el algoritmo de Bresenham para dibujar líneas, pero tienen (por supuesto) un píxel de grosor. Mi pregunta es ¿cuál es la forma más eficiente de dibujar líneas de grosor arbitrario?

El lenguaje que estoy usando es C.

Aquí hay una implementación en papel y Delphi de una versión modificada del algoritmo de Bresenham para dibujar líneas gruesas.

También puede querer echar un vistazo a Anti-Grain Geometry , una biblioteca para la renderización de software de gráficos 2D de alta calidad y alto rendimiento. Eche un vistazo a la página de demostración para tener una idea de lo que puede hacer.

Creo que la mejor manera es dibujar un rectángulo en lugar de una línea, ya que una línea con ancho es un objeto bidimensional. Tring para dibujar un conjunto de líneas paralelas para evitar sobregirar (para reducir el ancho de banda de escritura) y underdraw (píxeles que faltan) sería bastante complejo. No es demasiado difícil calcular los puntos de esquina del rectángulo desde el punto inicial y final y el ancho.

Hago esto con bastante frecuencia para generar imágenes de fibras y esferas para simulaciones de medios porosos. Tengo una buena forma simple de hacer esto utilizando una técnica de análisis de imagen muy estándar conocida como la "transformación de distancia". Esto requiere tener acceso a algún paquete de análisis de imagen. Yo uso Python con Scipy, así que esto no es un problema. Aquí hay una demostración para convertir puntos distribuidos aleatoriamente en esferas:

import scipy as sp import scipy.ndimage as spim im1 = sp.rand(100, 100) < 0.995 # Create random points in space dt = spim.distance_transform_edt(im1) im2 = dt < 5 # To create sphere with a radius of 5

¡Y eso es todo! La transformación de distancia puede ser lenta para imágenes muy grandes, pero hay una versión eficiente. Por ejemplo, ImageJ tiene una paralelizada. Obviamente, para crear fibras gruesas solo creas tu imagen de las delgadas, luego aplica los pasos 2 y 3 de arriba.

Para mi aplicación de impresora térmica integrada, utilizando el algoritmo de Bresenham, la línea era demasiado delgada. No tengo GL ni nada lujoso. Terminé simplemente disminuyendo el valor de Y y dibujando más líneas debajo de la primera. Cada número de grosor sumó otra línea. Muy rápido de implementar y realizado para los resultados deseados imprimiendo desde un mapa de bits monocromático hasta el térmico.

Para una mayor precisión, y también un buen rendimiento para líneas más gruesas, puede dibujar la línea como un polígono. Algún pseudo código:

draw_line(x1,y1,x2,y2,thickness) Point p[4]; angle = atan2(y2-y1,x2-x1); p[0].x = x1 + thickness*cos(angle+PI/2); p[0].y = y1 + thickness*sin(angle+PI/2); p[1].x = x1 + thickness*cos(angle-PI/2); p[1].y = y1 + thickness*sin(angle-PI/2); p[2].x = x2 + thickness*cos(angle-PI/2); p[2].y = y2 + thickness*sin(angle-PI/2); p[3].x = x2 + thickness*cos(angle+PI/2); p[3].y = y2 + thickness*sin(angle+PI/2); draw_polygon(p,4)

Y opcionalmente se podría dibujar un círculo en cada punto final.

Supongo que dibujarías tramos horizontales de una línea de límite a otra, y calcularás el valor de x de cada una de las líneas mediante el método de Bresenham a medida que avanzas (en un solo bucle).

No lo he intentado.

Los puntos finales pueden necesitar algo de atención, para que no se vean extrañamente aislados.

Tome otro bucle de Bresenham y utilícelo para modificar la posición inicial y final de la línea original en dirección rectangular. El problema es encontrar de manera eficiente el punto de inicio correcto y no dibujar ningún píxel dos veces (u omitir un píxel) al dibujar la siguiente línea.

El código C de trabajo y probado está disponible en el código C de Github.

Aquí una página de prueba que incluye algunas líneas de muestra creadas por este código. Los píxeles negros son los puntos de partida para el algoritmo.

Yo estaba enfrentando el mismo problema hace algún tiempo. Sobre la base de este paper , creé una implementación de referencia de Matlab, que me gustaría compartir en GitHub .