2D-Grafik Bresenham's line algorithm

[Meeresgott]

Hallo,

ich habe einen Bug in meiner PlotLine Funktion, die ich mir nicht erklären kann. Ich benutze den hier verlinkten Algorithmus.
Allerdings werden alle 250 Pixel die Linie mal mit zwei Pixel mal mit einem gezeichnet.

Hier ist meine Implementierung:

    public void plotLine(int x0, int y0, int x1, int y1, Color color) {

        int dx = Math.abs(x1 - x0);
        int sx = x0 < x1 ? 1 : -1;
        int dy = -Math.abs(y1 - y0);
        int sy = y0 < y1 ? 1 : -1;
        int err = dx + dy;

        while (true) {
            setPixel(x0, y0, color);
            if (x0 == x1 && y0 == y1) break;

            int e2 = 2*err;
            if (e2 >= dy) {
                err += dy;
                x0 += sx;
            }
            if (e2 <= dx) {
                err += dx;
                y0 += sy;
            }
        }

Die Pixels werden in einem 1D-Array gespeichert.
Die Methode setPixel ist hier:

    public void setPixel(int x, int y, Color color) {

        if (x < 0 || x >= getpW() || y < 0 || y >= getpH()) {
            return;
        }

        p[y * getpW() + x] = color.getRGB();
    }

Die Methode getpW() gibt die Breite des Bildes zurück.
Die Methode getpH() gibt die Höhe des Bildes zurück.

Bei dem Objekt Color handelt es sich um java.awt.Color.

Hier ist ein Bild wie ich mit dieser Methode alle 10 Pixel eine vertikalen und eine horizontale Linie einzeichne.


Ich denke man sieht hier gut, was das Problem ist, allerdings fällt mir kein Fehler in der Implementierung auf ? Habt ihr eine Idee ?

Viele Grüße,
Meeresgott

 

[mrBrown]

Ich würde darauf tippen, dass das nur an der Darstellung, und nicht an deinem Algorithmus liegt, HiDPI kann solche Fehler uU verursachen.

Kannst du ein minimales ausführbares Beispiel hochladen?

EDIT: Speicher das Bild mal als png, anstatt das ganze in nem Fenster anzuzeigen, dann sollte man sehen, wie es wirklich aussieht.

 

[Meeresgott]

Du hast recht ! Ich habe eine Screenshot Funktion geschrieben und wenn ich direkt das Bild Speichere habe ich diesen Fehler nicht mehr


Musst du leider in Vollbild anzeigen lassen, da das Vorschaubild etwas verzerrt ist.

Der Einfachste Fall ist einfach nur ein Strich, brauchst du diesen noch ? Es scheint offensichtlich an der Darstellung zu liegen. Hast du eine Idee wie ich meine Darstellung verbessern kann ?

 

[mrBrown]

Hast du eine Idee wie ich meine Darstellung verbessern kann ?

Puh...welches JDK nutzt du? Afair gabs da mal Änderungen bei Swing bzgl HiDPI, die helfen könnten.

Vielleicht kann irgendwer mit Ahnung von Swing da mehr zu sagen, möglicherweise @mihe7?

 

[Meeresgott]

Ich benutze die JDK Version 11.03+12 allerdings ist meine Maven Target Version 1.6 ( falls das relevant sein sollte )

Hier ist ein Teil meiner Klasse, in der ich das JFrame erstelle:

private Window(int height, int width, String name) {
        this.height = height;
        this.width = width;
        this.name = name;

        bufferedImage = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB);

        canvas = new Canvas();
        Dimension dimension = new Dimension(width, height);
        canvas.setPreferredSize(dimension);
        canvas.setMaximumSize(dimension);
        canvas.setMinimumSize(dimension);

        frame = new JFrame();
        frame.setTitle(name);
        frame.setLayout(new BorderLayout());
        frame.add(canvas, BorderLayout.CENTER);
        frame.pack();

        frame.setLocationRelativeTo(null);
        frame.setResizable(false);

        canvas.createBufferStrategy(2);
        bufferStrategy = canvas.getBufferStrategy();
        graphics = bufferStrategy.getDrawGraphics();


        this.renderer = new Renderer(bufferedImage);
    }

Ich zeichne das BufferedImage hier mit mit Graphics#drawImage()

public void update(){
        graphics.drawImage(bufferedImage,0,0, canvas.getWidth(), canvas.getHeight(), null);
        bufferStrategy.show();
}

Und hier "extrahiere" ich das Pixel Array aus dem BufferedImage:

RenderTarget(BufferedImage bufferedImage) {
        pW = bufferedImage.getWidth();
        pH = bufferedImage.getHeight();

        p = ((DataBufferInt) bufferedImage.getRaster().getDataBuffer()).getData();
}

ich hoffe, ihr habt alles, zur not kann ich auch die komplette Window Klasse zur Verfügung stellen.

 

[Thallius]

Du wirst kein vernünftiges Ergebnis bekommen solange du nicht mit Subpixeln arbeitest. Du must die Position des Pixels auf dem Screen in 1/10 rechnen und dann das Ergebnis entsprechend auf die umliegenden 4 Pixel aufteilen.

 

[Meeresgott]

Also verstehe ich das richtig, dass ich intern mit einem Areal von 10 * 10 Pixeln rechne und dann zum anzeigen dieses Areal in 4 Teile also in (NW, NO, SW und SO) von dem jeweiligen Subareal den Mittelwert nehme und dieser Mittelwert ist dann die Farbe eines Pixels ?

 

[Thallius]

Oder die Transparenz. Je nachdem mit was du arbeitest.

 

[mrBrown]

Das Problem, dass ein Pixel nicht einem echten Pixel entspricht, bleibt allerdings bestehen.

 

[Thallius]

Das Problem, dass ein Pixel nicht einem echten Pixel entspricht, bleibt allerdings bestehen.

Durch das Antialiasing wirkt es aber wie eines. Besser kann es ein Computer halt nicht darstellen

 

[Meeresgott]

Ich habe jetzt ein wenig rum probiert allerdings scheinen alle meine Ansätze zu Imperforation zu sein.

Einer der relativ gut aussah war das BufferedImage, dass ich verwende um einen Faktor "scale" zu vergrößern und die setPixel methode so umzuschrieben:

public void setPixel(int x, int y, Color color) {

        if (x < 0 || x >= getpW() || y < 0 || y >= getpH()) {
            return;
        }
        for (int xx = 0; xx < x + scale; xx++){
            for (int yy = 0; yy < y + scale; yy++){
                p[yy * getpW() + xx] = color.getRGB();
            }
        }

    }

nach dem ein dann alles gezeichnet wurde wollte ich mit diesem Ansatz das Bild wieder um den Faktor scale verringern:

public void update(){
    graphics.drawImage(bufferedImage.getScaledInstance(bufferedImage.getWidth()/scale,bufferedImage.getHeight()/scale,0),0,0, canvas.getWidth(), canvas.getHeight(), null);
    bufferStrategy.show();
}
    }

Allerdings komme ich dann auf ungefähr 0.01 FPS ... Hat jemand eine andere Idee deinen Vorschlag effizienter zu implementieren ?

 

[Meeresgott]

Habe auch versucht, das hier umzusetzen: https://www.java-forum.org/thema/bufferedimage-und-antialias.70643/ allerdings macht es keinen Unterschied..

 

[Thallius]

Ich habe dir mal einen wirklich alten C-Code von mir angehängt. Aber der sollte es entsprechend übersetzt tun.

 

[Meeresgott]

Habe jetzt was gefunden was funktioniert allerdings immer noch nicht so der Knüller ist was die Performance angeht.

graphics2D.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
        graphics2D.setRenderingHint(RenderingHints.KEY_INTERPOLATION, RenderingHints.VALUE_INTERPOLATION_BILINEAR);

EDIT: Super danke!! Ich werde deinen Code implementieren, in der Hoffnung, dass die Performance besser ist als das was bei meinem Ansatz heraus kommt ^^

Könntest du mir verraten welche Paramter diese Funktion erwartet ?

void line(struct OperatorImage *Dest,double x_1,double y_1,double x_2,double y_2, double thickness)

Das erste ist das Bild soweit bin ich ^^

 

[Thallius]

Das erste ist halt der Bildspeicher, dann die start und end Koordinaten und du kannst noch eine Pixelstärke angeben. Also wie breit die Linie sein soll.

Da das ganz noch auf Pentium 1 Rechnern gelaufen ist sollte die Performance mehr als ausreichend sein.

 

[mrBrown]

Ich habe dir mal einen wirklich alten C-Code von mir angehängt. Aber der sollte es entsprechend übersetzt tun.

Einfach das Bild in gewünschter Größe reinwerfen oder muss man selber noch irgendwas skalieren?

 

[Thallius]

Einfach das Bild in gewünschter Größe reinwerfen oder muss man selber noch irgendwas skalieren?

Eigentlich sollte das so funktionieren. Aber das ist echt lange her das ich das geschriben habe. Das Datum oben ist das letze mal als ich es in einem Projekt eingesetzt habe. Geschrieben habe ich das vor ca. 30 Jahren....

 

[Xyz1]

if (x < 0 || x >= getpW() || y < 0 || y >= getpH()) { return; }

Daran erkennt man Anfänger...

public static BufferedImage bresenham(int x0, int y0, int x1, int y1, BufferedImage i, Color c) {
    int dx = Math.abs(x1 - x0), sx = x0 < x1 ? 1 : -1;
    int dy = -Math.abs(y1 - y0), sy = y0 < y1 ? 1 : -1;
    int err = dx + dy, e2; /* error value e_xy */

    while (true) {
        i.setRGB(x0, y0, c.getRGB());
        if (x0 == x1 && y0 == y1)
            break;
        e2 = 2 * err;
        if (e2 > dy) {
            err += dy;
            x0 += sx;
        } /* e_xy+e_x > 0 */
        if (e2 < dx) {
            err += dx;
            y0 += sy;
        } /* e_xy+e_y < 0 */
    }

    int w = i.getWidth();
    int h = i.getHeight();
    BufferedImage b = new BufferedImage(w * 4, h * 4, BufferedImage.TYPE_INT_ARGB);
    AffineTransform at = new AffineTransform();
    at.scale(4.0, 4.0);
    AffineTransformOp scaleOp = new AffineTransformOp(at, AffineTransformOp.TYPE_NEAREST_NEIGHBOR);
    b = scaleOp.filter(i, b);
    return b;
}

public static void main(String[] args) throws IOException {
    JFrame f = new JFrame();
    f.add(new JLabel(new ImageIcon(bresenham(10, 10, 90, 90, new BufferedImage(100, 100, BufferedImage.TYPE_INT_ARGB), Color.RED))));
    f.pack();
    f.setVisible(true);
}

hth

 

[mrBrown]

Daran erkennt man Anfänger...

Ne, daran erkennt man jemanden, der schon mal was von defensiver Programmierung gehört hat
Anfänger erkennt man eher an am weglassen solcher Checks...


Deine Lösung ist btw der Grund für dieses Problem, und nicht die Lösung dafür

 

[mrBrown]

@Meeresgott

Welches OS und welche DPI-Einstellung nutzt du? Das Muster dort sieht recht interessant aus, das hab ich in der Form noch nirgends gesehen.


Bist du ansonsten mit den Ansätzen hier schon weiter gekommen? Falls ja, wie siehts aus und mit welcher Variante?
(Ich hab ja schon oben gesagt, dass ich nicht allzu viel davon erwarte, bei so schmalen Strichen fällt sowas immer auf oder geht stark zur Lasten der Qualität...)


EDIT: du kannst auch mal mit sun.java2d.uiScale rumspielen, möglicherweise reicht das, muss die Anwendung natürlich zu lassen.

 

[Xyz1]

Anfänger erkennt man eher an am weglassen solcher Checks

Total unnötig, der Code schmeißt eh eine Exception, so man diesen falsch aufruft.

 

[Xyz1]

Deine Lösung ist btw der Grund für dieses Problem, und nicht die Lösung dafür

Aha, man kann die (einzige) richtige Lösung natürlich in Abrede stellen... die schönste Art ist das allerdings nicht.

 

[kneitzel]

Wenn die Informationen in einem eindimensionalen Array liegen, dann ist die Prüfung der Werte durchaus wichtig. Denn bei einem gedachten Bild von 10x10 Pixeln (Eindimensionales Array der Länger 100) würde sonst ein Aufruf von 12, 2 eben kein Fehler auslösen sondern das Pixel im Index 2*10 + 12 = 32 setzen.
==> Der Check ist somit sehr wohl gut und notwendig und Deine Bewertung, dass der Code bei falschem Aufruf eh eine Exception wirft, offensichtlich falsch,

 

[mrBrown]

Total unnötig, der Code schmeißt eh eine Exception, so man diesen falsch aufruft.

Sehr gut, du hast das Problem also erkannt - das ist der erste Schritt zur Besserung

Aha, man kann die (einzige) richtige Lösung natürlich in Abrede stellen... die schönste Art ist das allerdings nicht.

Deine Lösung hat genau das gleiche Problem (was du einfach uU aufgrund deines Monitors nicht siehst).

Der Grund ist die Art des Hochskalierens, das Muster sieht mit Nearest-Neighbor anders aus als bei @Meeresgott, Artefakte durchs Skalieren sieht man trotzdem.
Zeichne einfach mal ein Linienmuster und wähle einen entsprechenden Faktor, das ist 10px Abstand und Factor 1,23:




Die Skalierung mir 4 produziert keine Artefakte (weil N*4 immer eine grade Zahl bleibt), aber wenn danach noch mal skaliert wird (zB zur Darstellung auf dem Bildschirm), hat man wieder Artefakte. Weniger auffällig (1px ist im Verhältnis zu 4px einfach weniger als zu 1px), aber da ist es trotzdem.



Den Effekt kann man oftmals sogar bei einfacher Schrift sehen: IIIIIIIII (<- alles "große i's")
Auf vielen Bildschirmen mit "logischer" != nativer Auflösung sehen die nicht alle genau gleich groß aus, hier als Bildschirmfoto:

 

[Xyz1]

dass der Code bei falschem Aufruf eh eine Exception wirft, offensichtlich falsch

Bitte erst denken, dann posten...

Deine Lösung hat genau das gleiche Problem (was du einfach uU aufgrund deines Monitors nicht siehst)

Was entspricht hier nicht Bresenham? (Bis auf, dass das Fenster nicht schließt ).

public static BufferedImage bresenham(int x0, int y0, int x1, int y1, BufferedImage i, Color c, int f) {
    int dx = Math.abs(x1 - x0), sx = x0 < x1 ? 1 : -1;
    int dy = -Math.abs(y1 - y0), sy = y0 < y1 ? 1 : -1;
    int err = dx + dy, e2; /* error value e_xy */

    while (true) {
        i.setRGB(x0, y0, c.getRGB());
        if (x0 == x1 && y0 == y1)
            break;
        e2 = 2 * err;
        if (e2 > dy) {
            err += dy;
            x0 += sx;
        } /* e_xy+e_x > 0 */
        if (e2 < dx) {
            err += dx;
            y0 += sy;
        } /* e_xy+e_y < 0 */
    }

    BufferedImage b = new BufferedImage(i.getWidth() * f, i.getHeight() * f, BufferedImage.TYPE_INT_ARGB);
    AffineTransform at = new AffineTransform();
    at.scale(f, f);
    AffineTransformOp scaleOp = new AffineTransformOp(at, AffineTransformOp.TYPE_NEAREST_NEIGHBOR);
    b = scaleOp.filter(i, b);
    return b;
}

public static void main(String[] args) throws IOException {
    JFrame f = new JFrame();
    f.add(new JLabel(new ImageIcon(bresenham(1, 1, 34, 20, new BufferedImage(36, 22, BufferedImage.TYPE_INT_ARGB), Color.RED, 20))));
    f.pack();
    f.setVisible(true);
}

Habe eine native Auflösung.

Das erkennt doch sogar ein Blinder oder?

 

[Xyz1]

Die Skalierung mir 4 produziert keine Artefakte

Das ist richtig... Ich kann doch aber nichts dafür, wenn er so eine komische Bildschirmauflösung wählt, bei der man nichts mehr erkennen kann. Oder wenn sein Monitor zu klein ist oder what ever.

Jedenfalls sollte die Skalierung immer so gewählt werden daß bei der Skalierung keine Artefakte entstehen imo.

 

[mrBrown]

Was entspricht hier nicht Bresenham? (Bis auf, dass das Fenster nicht schließt ).

Der Code ist schon richtig, "schräge" Linien sehen damit genau so aus.

Das Problem von @Meeresgott ist allerdings ein anderes und tritt auch bei senkrechten Linien auf.

Habe eine native Auflösung.

Das erkennt doch sogar ein Blinder oder?

Gehören die Aussagen irgendwie zusammen? Oder beziehen die sich auf irgendwas anderes?

Das ist richtig... Ich kann doch aber nichts dafür, wenn er so eine komische Bildschirmauflösung wählt, bei der man nichts mehr erkennen kann. Oder wenn sein Monitor zu klein ist oder what ever.

Jedenfalls sollte die Skalierung immer so gewählt werden daß bei der Skalierung keine Artefakte entstehen imo.

Die meisten aktuellen Monitore dürften mit irgendeinem Skaling genutzt werden, da ist nichts dran "komisch"...

Skalierung *sollte* im Idealfall natürlich so gewählt werden, ist aber leider in den wenigsten Fällen passend.

 

[kneitzel]

Bitte erst denken, dann posten...

Wie wäre es, wenn Du Deinen Ratschlag selbst beherzigst? Und dann bitte einmal versuchen, Argumente zu bringen statt solcher pers. Angriffe.

Ansonsten finde ich es schon recht mies: immer wieder lieferst Du so schöne Steilvorlagen und da muss ich mich manchmal richtig zwingen, nicht drauf ein zu gehen und sachlich zu bleiben...

 

[Xyz1]

Also, das war doch kein persönlicher Angriff. Nur ich wundere mich warum das so bei mir funktioniert bei ihm aber nicht.

 

[mrBrown]

Nur ich wundere mich warum das so bei mir funktioniert bei ihm aber nicht.

Hab ich doch schon gesagt.

Nimm erstmal ein Linienmuster zum testen, da sieht man den Effekt deutlich besser als bei so einem Treppenmuster, am besten 1px Breite Linien mit einem "krummen" Abstand wie zB 7.
Dann skalier das ganze nicht mit 20, Fehler im Bereich von 1px sieht man logischerweise schlechter, wenn die Linie 20px breit ist.
Anstatt das direkt anzuzeigen, speicher das Bild einfach (die Anzeige bringt uU andere Fehler rein).

Den Effekt siehst du dann, wenn das ganze mit 1,5 skaliert wird (was ein durchaus üblicher Faktor ist).


Wenn dir das zu klein ist, kannst du *nachträglich* noch hochskalieren mit einer *ganzen Zahl* als Faktor.

Original (1px Breite Linien alle 7px):


Skaliert mit 1,5:

 

[Meeresgott]

Guten Morgen,

@mrBrown Ich verwende Windows 10 und für die Skalierung benutze ich den Faktor 1,5.

Ja bin ich! Also mit dem Ansatz auf den ich selber gekommen bin nach dem klar war, dass es am Alignement lag funktioniert alles sehr gut ist aber doch merklich langsamer.

Java:
graphics2D.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
graphics2D.setRenderingHint(RenderingHints.KEY_INTERPOLATION, RenderingHints.VALUE_INTERPOLATION_BILINEAR);

Wohingegen der Ansatz von @Thallius auch funktioniert und das Problem komplett beseitigt und trotz der größeren Datenmenge im Schnitt ca. 1.2ms raus holt im Gegensatz zu der bilinearen Interpolation.

Hier ist nochmal ein Screenshot von meiner Applikation aber diesmal mit der implementierten Lösung von Thallius:


Glaubt ihr, dass das Problem nur ensteht, weil ich meine Skalierung von Apps auf 150% gestellt habe ?

Edit: Auch hier das Bild bitte wieder in Vollbild betrachten die Komprimierung der Vorschau scheint Artefakte zu erzeugen

 

[Thallius]

Ich denke das ist auch das optimum was man rausholen kann und es sieht eben auch noch gut aus wenn du diagonale Linien machst.

 

[Meeresgott]

Ich denke das ist auch das optimum was man rausholen kann und es sieht eben auch noch gut aus wenn du diagonale Linien machst.

Ja, ich danke dir vielmals für den Tipp mit den Subpixeln der war Gold wert! Auch einfach zu implementieren für z.B. den Midpoint cirlce algorithm.
Es scheint so als hätte ich eine Baustelle weniger

 

[mrBrown]

Glaubt ihr, dass das Problem nur ensteht, weil ich meine Skalierung von Apps auf 150% gestellt habe ?

Ja, hängt ziemlich sicher damit zusammen, mit dem direkt gespeicherten Bild (wo keinerlei Skalierung greift) hast du ja den Vergleich.
Keine Ahnung, was genau das zum Skalieren genutzt wird, das genau dieses Muster auftritt, und ob das auf Swing oder auf Java-Seite liegt, aber das dürfte der Grund sein.



Du kannst einmal testen, die Skalierung explizit auf 1 festzusetzen (mit sun.java2d.uiScale), dann sollten die Linien wirklich 1px breit sein

 

[Meeresgott]

Ja, hängt ziemlich sicher damit zusammen, mit dem direkt gespeicherten Bild (wo keinerlei Skalierung greift) hast du ja den Vergleich.
Keine Ahnung, was genau das zum Skalieren genutzt wird, das genau dieses Muster auftritt, und ob das auf Swing oder auf Java-Seite liegt, aber das dürfte der Grund sein.

Ja ist richtig, stelle ich es auf 100% oder setzte die Skalierung fest tritt das Problem nicht mehr auf. Wirklich komisch..

Vielen Dank für eure Hilfe !

 

[mrBrown]

Ja ist richtig, stelle ich es auf 100% oder setzte die Skalierung fest tritt das Problem nicht mehr auf. Wirklich komisch..

Ne, komisch nicht

Mit 150% muss er aus zwei Pixeln die du gezeichnet hast drei zum Darstellen machen - ein Pixel muss also irgendwie aus den zweien hergeleitet werden, das verursacht den Fehler.

Bei 100% werden deine zwei gezeichneten Pixel auch als zwei dargestellt, sieht also genauso aus wie es sollte

 

[Xyz1]

Wie kann man denn bei einer Skalierung um 1.5 noch eine genau gezeichnete Linie erwarten? Das ist logisch unmöglich. Aber gut... Man kann die anderen ja mal zum Narren halten.

 

[mrBrown]

Wie kann man denn bei einer Skalierung um 1.5 noch eine genau gezeichnete Linie erwarten? Das ist logisch unmöglich.

Na endlich hast auch du das Problem erkannt

Das Problem ist aber nur wirklich sichtbar, wenn man wirklich 1px Genauigkeit braucht und abhängig vom verwendeten Algorithmus/Grafikframework/Whatever. In den meisten Fällen ist das nicht auffällig.