Wie kann man Bresenhams Linienzeichnungsalgorithmus mit Sub-Pixel-Bias verwenden?

Question

Bresenham's line drawing algorithm ist bekannt und recht einfach zu implementieren.

Während es fortgeschrittenere Möglichkeiten gibt, Anti-Ail-Linien zu zeichnen, möchte ich eine Funktion schreiben, die eine Linie ohne Anti-Alias-Linie mit einer Pixelbreite auf Basis von Fließkomma-Koordinaten zeichnet.

Dies bedeutet, dass, während das erste und das letzte Pixel gleich bleiben, die Pixel, die zwischen ihnen gezeichnet werden, eine Verzerrung aufweisen, die auf der Subpixelposition beider Endpunkte basiert.

Im Prinzip sollte das nicht so kompliziert sein, da ich annahm, dass es möglich ist, die Subpixel-Offsets zu verwenden, um einen ursprünglichen error-Wert zu berechnen, und alle anderen Teile des Algorithmus bleiben gleich .

Kein Subpixel-Offset:

X### 
    ###X 

die rechte Hand Punkt hat eine Subpixel-Position in der Nähe der oberen Unter der Annahme, könnte die Zeile wie folgt aussehen:

Mit Sub-Pixel-Offset zum Beispiel:

X###### 
     X 

Gibt es eine versuchte & wahre Methode zum Zeichnen einer Linie, die Sub-Pixel-Koordinaten berücksichtigt?

---

Hinweis:

• Das ist wie eine gemeinsame Operation scheint, habe ich OpenGL-Treiber nehmen dies zum Beispiel in Betracht gesehen - GL_LINE verwenden, obwohl von einer schnellen Suche ich keine Antworten gefunden haben online - vielleicht falsche Suchbegriffe verwendet?
• Auf einen Blick diese Frage sieht aus wie es könnte ein Duplikat sein von:
  Precise subpixel line drawing algorithm (rasterization algorithm)
  Aber das fragt nach dem Zeichnen einer breiten Linie, das ist über die Verrechnung einer einzelnen Pixelzeile.
• Wenn es keine Standardmethode gibt, werde ich versuchen, dies zu schreiben, um als Antwort zu posten.

Answer 1

Nehmen wir an, Sie eine Linie P1 = (x1, y1)-P2 = (x2, y2) ziehen wollen, wo alle Zahlen sind Punkt Floating Pixelkoordinaten.

1. Berechnen Sie die wahren Pixelkoordinaten von P1 und P2 und malen sie: P* = (round(x), round(y)).

2. Wenn abs(x1* - x2*) <= 1 && abs(y1* - y2*) <= 1 dann sind Sie fertig.

3. Entscheiden Sie, ob es sich um eine horizontale (wahre) oder eine vertikale Linie (falsch) handelt: abs(x1 - x2) >= abs(y1 - y2).

4. Wenn es eine horizontal Linie ist und x1 > x2 oder wenn es sich um eine vertikale Linie und y1 > y2: swap P1 mit P2 (und auch mit P1*P2*).

5. Wenn es ein horizontal Linie ist, dass Sie die y-Koordinaten für alle x-Koordinaten zwischen x1* und x2* mit der folgenden Formel erhalten können:

   y(x) = round(y1 + (x - x1)/(x2 - x1) * (y2 - y1)) 
   

   Wenn Sie eine vertikale Linie Sie können die x-Koordinaten für alle y-Koordinaten zwischen y1* und y2* mit dieser Formel erhalten:

   x(y) = round(x1 + (y - y1)/(y2 - y1) * (x2 - x1)) 
   

Here is a demo Sie spielen, um, können Sie verschiedene Punkte auf der Linie versuchen 12.

Answer 2

die gleiche Herausforderung nur begegnet, kann ich bestätigen, dass dies möglich ist, als Sie erwartet haben.

Zuerst Rückkehren der einfachsten Form des Algorithmus: (die Fraktionen ignorieren, sie werden später verschwinden)

x = x0 
y = y0 
dx = x1 - x0 
dy = y1 - y0 
error = -0.5 
while x < x1: 
    if error > 0: 
     y += 1 
     error -= 1 
    paint(x, y) 
    x += 1 
    error += dy/dx 

Dies bedeutet, dass für den ganzzahligen Koordinaten, wir ein halbes Pixel über dem Pixelgrenze beginnen (error = -0.5), und für jedes Pixel, das wir in x voranbringen, erhöhen wir die ideale y-Koordinate (und daher die aktuelle error) von dy/dx.

Zuerst wollen wir mal sehen, was passiert, wenn wir gezwungen zu stoppen x0, y0, x1 und y1 ganze Zahlen zu sein: (dies wird auch davon ausgehen, dass anstelle Pixelzentren zu verwenden, die Koordinaten auf die relative sind oben links jedes Pixels, da sobald Sie Subpixel-Positionen unterstützen, können Sie einfach die halbe Pixelbreite auf die x- und y in der Pixel-zentrierte Logik zurückzukehren)

x = x0 
y = y0 
dx = x1 - x0 
dy = y1 - y0 
error = (0.5 - (x0 % 1)) * dy/dx + (y0 % 1) - 1 
while x < x1: 
    if error > 0: 
     y += 1 
     error -= 1 
    paint(x, y) 
    x += 1 
    error += dy/dx 

die einzige Änderung, die anfängliche Fehlerberechnung war. Der neue Wert kommt von einer einfachen Triggerung, um die y-Koordinate zu berechnen, wenn x im Pixelzentrum ist. Es ist erwähnenswert, dass Sie die gleiche Idee verwenden können, um die Startposition der Linie innerhalb einer bestimmten Grenze zu begrenzen. Dies ist eine weitere Herausforderung, der Sie wahrscheinlich begegnen werden, wenn Sie mit der Optimierung beginnen möchten.

Nun müssen wir dies nur in Nur-Arithmetik umwandeln. Wir benötigen einen festen Multiplikator für die Teileingaben (scale), und die Divisionen können durch Multiplizieren behandelt werden, genau wie der Standardalgorithmus.

# assumes x0, y0, x1 and y1 are pre-multiplied by scale 
x = x0 
y = y0 
dx = x1 - x0 
dy = y1 - y0 
error = (scale - 2 * (x0 % scale)) * dy + 2 * (y0 % scale) * dx - 2 * dx * scale 
while x < x1: 
    if error > 0: 
     y += scale 
     error -= 2 * dx * scale 
    paint(x/scale, y/scale) 
    x += scale 
    error += 2 * dy * scale 

anzumerken, dass x, y, dx und dy denselben Skalierungsfaktor als Eingangsgrößen halten (scale), während error eine komplexere Skalierfaktor: 2 * dx * scale. Dies ermöglicht es, die Teilung und den Bruchteil in seiner ursprünglichen Formulierung zu absorbieren, bedeutet aber, dass wir die gleiche Skala überall dort anwenden müssen, wo wir sie verwenden.

Offensichtlich gibt es hier viel Platz zur Optimierung, aber das ist der grundlegende Algorithmus. Wenn wir Skala übernehmen ist eine Potenz von zwei (2^n), können wir die Dinge zu machen, ein wenig effizienter starten:

dx = x1 - x0 
dy = y1 - y0 
mask = (1 << n) - 1 
error = (2 * (y0 & mask) - (2 << n)) * dx - (2 * (x0 & mask) - (1 << n)) * dy 
x = x0 >> n 
y = y0 >> n 
while x < (x1 >> n): 
    if error > 0: 
     y += 1 
     error -= 2 * dx << n 
    paint(x, y) 
    x += 1 
    error += 2 * dy << n 

Wie bei dem Original, das funktioniert nur in dem (x> = y, x > 0, y> = 0) Oktant. Die üblichen Regeln gelten für die Erweiterung auf alle Fälle, aber beachten Sie, dass es einige zusätzliche Fehler gibt, da die Koordinaten nicht mehr in dem Pixel zentriert sind (d. H. Reflexionen werden komplexer).

Sie müssen auch auf ganzzahlige Überläufe achten: error hat die doppelte Genauigkeit der Eingabevariablen und einen Bereich von bis zur doppelten Länge der Zeile. Planen Sie Ihre Eingabe-, Genauigkeits- und Variablentypen entsprechend!