Schnelles Antialiasing-Strichzeichnen

11

Der Linienalgorithmus von Bresenham ist eine Möglichkeit, gerade Linien nur mit schnellen ganzzahligen Operationen (Addition, Subtraktion und Multiplikation mit 2) zu zeichnen. Es werden jedoch Alias-Zeilen generiert. Gibt es eine ähnlich schnelle Möglichkeit, Antialias-Linien zu zeichnen?

Kennzeichen
quelle
1
Ein paar Fragen ... machst du die Zeichenlogik auf der CPU oder GPU? Suchen Sie auch nach ganzzahligen Algorithmen oder Gleitkommazahlen?
Alan Wolfe
5
@AlanWolfe, ganzzahlige Algorithmen auf der CPU - dieselbe Umgebung, für die der Bresenham-Algorithmus entwickelt wurde.
Mark
3
en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm ist der Klassiker, obwohl die Wikipedia-Seite ziemlich halbherzig ist und ich keinen Zugriff auf das Papier habe. Dies fühlt sich jedoch wie eine faule Frage an, da es ziemlich einfach ist, dies durch einfaches Googeln zu finden.
Yuriks
2
Wenn ich nur laut nachdenke, sollte es einfach sein, Bresenham für das Zeichnen von mehr Pixel dicken Linien anzupassen. Anschließend können Sie Antialiasing durchführen, indem Sie den Abstand jedes Pixelzentrums von der mathematischen Ideallinie berechnen und eine Falloff-Funktion anwenden.
Nathan Reed
2
Ich kann einen Kommentar jedoch nicht als richtig markieren.
Mark

Antworten:

9

Gibt es eine ähnlich schnelle Möglichkeit, Antialias-Linien zu zeichnen?

Nein, da per Definition eine Anti-Alias-Linie mehr Pixel berührt. Solche Algorithmen sind langsamer.


In einem Software-Rasterizer ist der Linienalgorithmus von Xiaolin Wu die allgegenwärtige Methode zum Zeichnen von Anti-Alias-Linien . Es ist nicht schwer zu implementieren, und an diesem Link befindet sich ohnehin ein Pseudocode von ungewöhnlich hoher Qualität.

In einer Hardware-Raster-Pipe wird das Linienprimitiv durch den Standard-Geometrie-Shader (oder den vom Benutzer bereitgestellten Geometrie-Shader) zu einem Bildschirmraum-Quad erweitert und dann als zwei Dreiecke gezeichnet, die dann auf die übliche Weise gegen Aliasing geschützt werden können.

In einem Raytracer gibt es eine Vielzahl von Optionen. Es lohnt sich darüber nachzudenken, wie Sie tatsächlich ein 1D-Objekt zeichnen möchten. Vielleicht als Zylinder (woo Schatten!). Beachten Sie, dass dies zu Problemen mit der Perspektive / Verkürzung führt, die möglicherweise Ihren Wünschen entsprechen (oder auch nicht). Es gibt keine klare Verallgemeinerung. Was auch immer Sie tun, Sie probieren es einfach aus.

imallett
quelle
"Und trotzdem gibt es unter diesem Link einen ungewöhnlich hochwertigen Pseudocode", stimme ich nicht zu. Dieser Pseudocode ist wahrscheinlich keine ordnungsgemäße Implementierung des Wu-Algorithmus, obwohl er anscheinend an unzähligen Stellen im Internet verwendet wurde. Wus ursprünglicher Algorithmus zog von beiden Enden nach innen in Richtung Zentrum und war tatsächlich schneller als der von Bresenham, da er ungefähr halb so viele Operationen ausführt, obwohl er in mehr Pixel schreibt. Ich spreche von Wus tatsächlichem Algorithmus, nicht dem, der im verlinkten Wikipedia-Artikel veröffentlicht wurde.
Octopus
@Octopus [drückt vage Skepsis aus, insbesondere in Bezug auf das schnellere Bit, aber es fehlt der Kontext, um dies zu widerlegen oder zu bestätigen - wenn dies der
Fall
Kommt darauf an, was du zählst. Wenn Sie von beiden Enden nach innen zeichnen, führt der Wu-Algorithmus die Hälfte der Berechnungen durch, jedoch doppelt so viele Pixelschreibvorgänge. Siehe Tabelle 1 in Wus Artikel, der auf Wikipedia verlinkt ist. Wenn also Pixelschreibvorgänge teuer sind, wie dies beim Schreiben in eine TFT über eine serielle Verbindung der Fall ist, ist der Wu-Algorithmus teurer als der von Bresenham. (Ich muss zugeben, ich verstehe nicht, warum Bresenhams Algorithmus auch keine Symmetrie verwenden kann.)
Jan-Åke Larsson
1
Aber ich stimme @Octopus zu und akzeptiere sogar "Zeichnen von einem Ende zum anderen". Der Pseudocode ist Wus Algorithmus nur, wenn durchgehend ganzzahlige Arithmetik verwendet wird. Code, den ich online sehe, verwendet Gleitkomma-Arithmetik, was eine bedeutende Änderung darstellt. In Wus Arbeit verwendet der Algorithmus nur Ganzzahlarithmetik (oder tatsächlich Festkomma-Arithmetik).
Jan-Åke Larsson