Dibujo lineal rápido suavizado

11

El algoritmo de línea de Bresenham es una forma de dibujar líneas rectas usando solo operaciones enteras rápidas (suma, resta y multiplicación por 2). Sin embargo, genera líneas con alias. ¿Hay una forma rápida similar de dibujar líneas antialias?

antialiasing pixel-graphics line-drawing marca
fuente
1
Un par de preguntas ... ¿estás haciendo la lógica de dibujo en la CPU o GPU? Además, ¿está buscando algoritmos basados ​​en enteros o coma flotante?
Alan Wolfe
55
@AlanWolfe, algoritmos enteros en la CPU: el mismo entorno para el que fue diseñado el algoritmo de Bresenham.
Mark
3
en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm es el clásico, aunque la página de wikipedia está bastante a medias y no tengo acceso al documento. Sin embargo, esto se siente como una pregunta perezosa, ya que es bastante fácil encontrarlo haciendo un google básico.
yuriks
2
Solo pensando en voz alta, creo que debería ser fácil adaptar Bresenham para dibujar líneas de varios píxeles de grosor. Luego puede hacer antialiasing calculando la distancia de cada centro de píxeles desde la línea matemática ideal y aplicando alguna función de caída.
Nathan Reed
2
Sin embargo, no puedo marcar un comentario como correcto.
Mark

Respuestas:

9

¿Hay una forma rápida similar de dibujar líneas antialias?

No, porque, por definición, una línea suavizada toca más píxeles. Tales algoritmos serán más lentos.

En un rasterizador de software, la forma ubicua de dibujar líneas suavizadas es el algoritmo de línea de Xiaolin Wu . No es difícil de implementar, y de todos modos hay un pseudocódigo inusualmente de alta calidad en ese enlace.

En una tubería ráster de hardware, el primitivo de línea se expande a un cuadrante de espacio de pantalla mediante el sombreador de geometría predeterminado (o proporcionado por el usuario), y luego se dibuja como dos triángulos, que luego se pueden suavizar de la manera habitual.

En un rastreador de rayos, hay una variedad de opciones. Vale la pena pensar en cómo realmente quieres dibujar un objeto 1D. Tal vez como un cilindro (¡corteja las sombras!). Tenga en cuenta que esto introduce problemas de perspectiva / escorzo que pueden (o no) ser lo que desea. No hay una generalización clara. Entonces, obviamente, hagas lo que hagas, simplemente lo supermuestreas.

imallett
fuente
"y de todos modos hay un pseudocódigo inusualmente de alta calidad en ese enlace", no estoy de acuerdo. Ese pseudocódigo probablemente no sea una implementación adecuada del algoritmo de Wu a pesar de que parece ser lo que se usó en innumerables lugares en la web. El algoritmo original de Wu se dibujó desde ambos extremos hacia el centro y en realidad fue más rápido que el de Bresenham porque realiza aproximadamente la mitad de las operaciones a pesar de que escribe en más píxeles. Estoy hablando del algoritmo real de Wu, no el publicado en el artículo vinculado de Wikipedia.
Octopus
@Octopus [Expresa un vago escepticismo, especialmente en la parte más rápida, pero carece de contexto para refutar o confirmar; si es así, las fuentes, correcciones y ediciones son, por supuesto, bienvenidas.]
Imallett
Depende de lo que cuentes. Si dibuja desde ambos extremos hacia adentro, entonces el algoritmo de Wu realiza la mitad de los cálculos pero el doble de escrituras de píxeles. Consulte la Tabla 1 en el documento de Wu, vinculado en Wikipedia. Entonces, si las escrituras de píxeles son caras, como es el caso al escribir en un TFT en una conexión en serie, entonces el algoritmo de Wu es más caro que el de Bresenham. (Debo admitir que no veo por qué el algoritmo de Bresenham tampoco puede usar la simetría.)
Jan-Åke Larsson
1
Pero sí estoy de acuerdo con @Octopus, incluso aceptando "dibujar de un extremo al otro", el pseudocódigo es el algoritmo de Wu solo si se usa la aritmética de enteros en todo momento. El código que veo en línea usa aritmética de punto flotante, que es un cambio significativo. En el artículo de Wu, el algoritmo solo usa aritmética de enteros (o en realidad aritmética de punto fijo).
Jan-Åke Larsson