Kreisberechnung sinus/cosinus oder Quadratwurzelmethode



  • Ist es zB in C++ unerheblich, welche Methode man verwendet? Bzw wird dies ähnlich optimiert?



  • Das kommt darauf an.



  • Es geht nur um das Zeichnen eines einfachen Kreis. Nimmt man die Zeit für die Ausgabe weg, gibt es zwischen den Methoden verschiedene Leistung?

    edit: also nur die Berechnung selbst.


  • Mod

    lemon03 schrieb:

    Es geht nur um das Zeichnen eines einfachen Kreis. Nimmt man die Zeit für die Ausgabe weg, gibt es zwischen den Methoden verschiedene Leistung?

    Zeichnen von Kreisen macht man ganz anders, sofern du nicht einfach eine fertige Funktion benutzt. Schließlich möchtest du genau jeden nötigen Pixel möglichst nur einmal setzen. Und komplexe Fließkommaoperationen zum Berechnen ganzer Zahlen (Pixelkoordinaten) sind auch unnötig aufwendig. Mit einer winkelbasierten Schleife wird man entweder Lücken haben und/oder viel Zeit verschwenden.



  • Ok, ist wohl ein größeres Thema.

    Kam nur gerade in meinem Grafikbuch dran, und abgesehen von der Fingerübung wollte ich wissen, ob sich dies gegenüber der "klassischen" sinus/cosinus Methode überhaupt lohnt.


  • Mod

    lemon03 schrieb:

    Kam nur gerade in meinem Grafikbuch dran

    Du hast ein Buch über Computergrafik, in dem Kreise gezeichnet werden, indem man Sinus/Cosinus/Sqrt benutzt? 😮



  • frueher galt der bresenham kreisalgorithmus als der "tollste" den man unbedingt kennen musste:
    http://www.geeksforgeeks.org/bresenhams-circle-drawing-algorithm/



  • SeppJ schrieb:

    Du hast ein Buch über Computergrafik, in dem Kreise gezeichnet werden, indem man Sinus/Cosinus/Sqrt benutzt? 😮

    Ein alter Home-Computer Schinken aus den 80ern.



  • Was ist die Quadratwurzelmethode?
    Eine Koordinate vorgeben und die andere per Pythagoras berechnen?

    lemon03 schrieb:

    SeppJ schrieb:

    Du hast ein Buch über Computergrafik, in dem Kreise gezeichnet werden, indem man Sinus/Cosinus/Sqrt benutzt? 😮

    Ein alter Home-Computer Schinken aus den 80ern.

    Gerade da sollte (zumindest auch) der Bresenham drinnen stehen.



  • Genau. Mit

    y = sqrt( r^2 - x^2 )
    

    Viertelkreise erzeugen und spiegeln.


  • Mod

    lemon03 schrieb:

    SeppJ schrieb:

    Du hast ein Buch über Computergrafik, in dem Kreise gezeichnet werden, indem man Sinus/Cosinus/Sqrt benutzt? 😮

    Ein alter Home-Computer Schinken aus den 80ern.

    Bresenham ist aus den 60ern. Entwickelt für eines der ersten (das erste?) grafischen Ausgabegeräte überhaupt! Gerade zu der Zeit und auch noch über 30 Jahre später, war es extrem wichtig, Fließkommaoperationen zu vermeiden, was die genannten optimierten Algorithmen auch tun. Hätte man einen Kreis wirklich Pixel für Pixel mathematisch mit Sinus und Cosinus berechnet, hätte man zugucken können, wie das mehrere Sekunden zum Zeichnen braucht. Ich habe das auf dem Atari so gemacht, weil das der erste Ansatz ist, auf den ein 13jähriger kommt, wenn er eben kein Buch über fortgeschrittene Algorithmen vorliegen hat, daher weiß ich, dass das wirklich viel zu langsam ist.

    Wenn das jedoch in einem Fachbuch aus der Zeit nicht besser drinsteht, als das ein mäßig begabter Mittelstufenschüler sich an einem Nachmittag ausdenken kann, dann bezweifle ich mal schwer die Qualität (und somit auch den sonstigen Inhalt) des Buches. Ist leider oft so, dass jeder Stümper sich als Computerbuchautor betätigen kann, da die zuständigen Herausgeber nur die Form, nicht aber den Inhalt prüfen können (oder es ihnen schlicht egal ist, Hauptsache man hat etwas zu verkaufen). Da ist es dann oft besser, ein Buch überhaupt nicht weiter zu lesen, als irgendwelchen falschen Müll zu lernen.

    Jürgen Wolf: "Grafik auf dem C64 von A bis Z"?



  • Gegenüber diesem Buch ein echt beleidigender Ton.

    Grafik mit dem Home-Computer
    Rüdeger Baumann
    1984
    https://www.eurobuch.com/buch/isbn/3802307690.html

    Bereue es schwer, gefragt zu haben.



  • lemon03 schrieb:

    Genau. Mit

    y = sqrt( r^2 - x^2 )
    

    Viertelkreise erzeugen und spiegeln.

    Ich hoffe, dass da was von Achtelkreisen steht. Damit sollten sich auch die Lücken erledigt haben.

    Ich hoffe, dass Bresenham auch in dem Buch vorkommt, aber zur Vollständigkeit gehört meiner Meinung auch, die "einfache" Variante zu zeigen.

    @Lemon: Wenn es dir um Fingerübung geht, implementier die verschiedenen Varianten und Vergleiche sie.



  • Hatte jetzt nicht erwartet, das meine simple Anfrage, ob sinus- oder Wurzelberechnungen in aktuellen Sprachen gleich optimiert werden, man sich also kein Kopf machen muss, solch ein Drama auslöst.

    Wenn dem Bresenham, ich denke schon.

    void bufferDrawLine( const Draw& draw,
                         int X1, int Y1,
                         int X2, int Y2,
                         const std::string& ch_name,
                         std::size_t ch_idx,
                         const bool& show )
    {
        int n = abs( X2 - X1 );
    
        if ( n < abs( Y2 - Y1 ) ) n = abs( Y2 - Y1 );
        if ( n == 0 )
        {
            std::cout << "bufferDrawLine(): nicht moeglich\n";
            std::cout << "X1: " << X1 << "  X2: " << X2 << '\n';
            std::cout << "Y1: " << Y1 << "  Y2: " << Y2 << '\n';
            ready();
        }
    
        double x = static_cast<double> ( X1 );
        double y = static_cast<double> ( Y1 );
    
        double dx = ( X2 - X1 ) / static_cast<double> ( n );
        double dy = ( Y2 - Y1 ) / static_cast<double> ( n );
    
        for ( int i = 0; i < n; ++i )
        {
            bufferDrawDot( draw, toInt( x ), toInt( y ), ch_name, ch_idx, show );
            x += dx;
            y += dy;
        }
    }
    

    Zu den besagten Viertelkreisen steht: (Es gibt keine pdf von dem Buch)

    Beispiel 4 arbeitete Mit Sinus und Cosinus - doch die Berechnung dieser Funktion ist zeitaufwändig. Wir suchen schnellere Verfahren. Kommen wir noch mal auf die Gleichung

    x^2 + y^2 = r^2
    

    zurück! Sie führt uns zur Darstellung

    y = sqrt( r^2 - x^2 )
    

    mit

    -r <= x <= r
    

    Sie liefert uns aber nur den oberen Halbkreis; den unteren bekommen wir durch Spiegelung an der x-Achse.
    Dies bringt uns auf die Idee, die Vollkommenheit des Kreises, nämlich seine Symmetrie, noch mehr in Betracht zu ziehen. Es genügt ja, einen Viertelkreis zu berechnen, d.h. die Variable x zwischen 0 und dem Radius r wandern zu lassen, und die übrigen Kreisteile durch Spiegelung an x- und y- Achse zu gewinnen.
    Dies vollbringt das Programm auf der folgenden Seite.

    Dann gehts weiter mit

    Das vorherige Programm benötigte immerhin noch Quadratwurzelfunktion und Multiplikation. Nun wollen wir das Verfahren zur Kreiserzeugung weiter vereinfachen, indem wir nur noch Addition und Subtraktion zulassen...

    Weitere Fragen zu den Inhalten? Irgendwelche Wünsche? Stehe jederzeit Rede und Antwort zur Verfügung.

    Schlangenmensch schrieb:

    @Lemon: Wenn es dir um Fingerübung geht, implementier die verschiedenen Varianten und Vergleiche sie.

    Du meint, die Zeiten der Berechnungen messen?



  • lemon03 schrieb:

    Hatte jetzt nicht erwartet, das meine simple Anfrage, ob sinus- oder Wurzelberechnungen in aktuellen Sprachen gleich optimiert werden, man sich also kein Kopf machen muss, solch ein Drama auslöst.

    Drama?
    Wir sagen dir bloss was sache ist, Drama sehe ich hier keines.

    Egal.

    Aber zu deiner eigentlichen Frage:
    Was ziemlich klar ist, ist dass Winkelfunktionen nochmal ein Stück teurer sind als Wurzelziehen.
    Ich würde also davon ausgehen dass jede sin/cos Variante die ausreichend fein unterteilt dass man keine langen Liniensegmente mehr sieht deutlich langsamer ist als die sqrt Variante.

    Das hat aber mit "aktuellen Sprachen" genau nichts zu tun, sondern eher damit dass "sin" eben langsamer ist als "sqrt".
    Vermutlich.

    Aber ja, wenn du's genau wissen willst, dann bastel dir nen Benchmark.

    Weitere Fragen zu den Inhalten? Irgendwelche Wünsche? Stehe jederzeit Rede und Antwort zur Verfügung.

    Aaaah, du meinst das Drama das DU selbst veranstaltest. OK.



  • Bresenham hat sogar auf meinem 286er ganz gut funktioniert (8 Mhz, weil der "Turbomodus" mit 16 Mhz immer abstürzte - ist dem PC wohl immer von der atemberaubenden Geschwindigkeit schwindlig geworden). Lang, lang ist's her...



  • lemon03 schrieb:

    Gegenüber diesem Buch ein echt beleidigender Ton.

    Grafik mit dem Home-Computer
    Rüdeger Baumann
    1984
    https://www.eurobuch.com/buch/isbn/3802307690.html

    Bereue es schwer, gefragt zu haben.

    Dir ist schon klar welches Jahr wir haben?
    Trägst du auch noch dieselbe Frisur und die selben Klamotten wie 1984?
    George Orwell lässt grüssen.



  • Kannst Du Dir vorstellen, das man so etwas aus reinem Interesse macht? Einfach, um ein Gefühl zu bekommen, wie man das damals gemacht hat? Auch aus nostalgischen Gründen?

    Wenn Du Dich mit alten 8-Bittern beschäftigst, dann doch nicht deswegen, weil Du die letzten 30 Jahre im Koma gelegen hast.

    Das ist so dermaßen albern, wie man sich hier über ein Buch mokiert!


  • Mod

    lemon03 schrieb:

    Kannst Du Dir vorstellen, das man so etwas aus reinem Interesse macht? Einfach, um ein Gefühl zu bekommen, wie man das damals gemacht hat? Auch aus nostalgischen Gründen?

    Das ist so dermaßen albern, wie man sich hier über ein Buch mokiert!

    In dem Buch steht aber nicht drin, wie man es damals gemacht hat! Es mokiert sich auch niemand über das Buch, sondern wir weisen sachlich darauf hin, dass das Buch wohl offensichtlich nicht gut ist, wenn es Sachverhalte falsch darstellt. Wenn du sachliche Kritik an deinem Lehrmaterial nicht von persönlichen Angriffen auf dich unterscheiden kannst, ist das dein Problem.

    (Beziehungsweise steht es wohl doch drin. Aber wie sich herausstellt, hast du wohl einfach nicht weit und aufmerksam genug gelesen, um zu merken, dass das, wonach du hier fragst, die Schilderung des Autors ist, wie man es naiv machen würde und wieso das dumm ist, das so zu machen. Insofern liegt das Problem wohl eher beim Leser, nicht beim Autor)



  • lemon03 schrieb:

    Zu den besagten Viertelkreisen steht: (Es gibt keine pdf von dem Buch)

    Beispiel 4 arbeitete Mit Sinus und Cosinus - doch die Berechnung dieser Funktion ist zeitaufwändig. Wir suchen schnellere Verfahren. Kommen wir noch mal auf die Gleichung

    x^2 + y^2 = r^2
    

    zurück! Sie führt uns zur Darstellung

    y = sqrt( r^2 - x^2 )
    

    mit

    -r <= x <= r
    

    Sie liefert uns aber nur den oberen Halbkreis; den unteren bekommen wir durch Spiegelung an der x-Achse.
    Dies bringt uns auf die Idee, die Vollkommenheit des Kreises, nämlich seine Symmetrie, noch mehr in Betracht zu ziehen. Es genügt ja, einen Viertelkreis zu berechnen, d.h. die Variable x zwischen 0 und dem Radius r wandern zu lassen, und die übrigen Kreisteile durch Spiegelung an x- und y- Achse zu gewinnen.
    Dies vollbringt das Programm auf der folgenden Seite.

    Dann gehts weiter mit

    Das vorherige Programm benötigte immerhin noch Quadratwurzelfunktion und Multiplikation. Nun wollen wir das Verfahren zur Kreiserzeugung weiter vereinfachen, indem wir nur noch Addition und Subtraktion zulassen...

    Weitere Fragen zu den Inhalten? Irgendwelche Wünsche? Stehe jederzeit Rede und Antwort zur Verfügung.

    Hier ein kurzer Auszug aus Wikipedia:

    Tatsächlich besitzt jedes Pixel auf dem Kreis sieben weitere symmetrische Pixel, die sich trivial berechnen lassen. Es genügt demnach, nur einen Achtelkreis zu zeichnen und anstatt nur einem Pixel folgende acht Pixel einzufärben:
    (x, y) (y, x) (y, −x) (x, −y) (−x, −y) (−y, −x) (−y, x) (−x, y)

    lemon03 schrieb:

    Schlangenmensch schrieb:

    @Lemon: Wenn es dir um Fingerübung geht, implementier die verschiedenen Varianten und Vergleiche sie.

    Du meint, die Zeiten der Berechnungen messen?

    Genau. Und das Ergebnis betrachten. Dabei übst du ein bisschen programmieren und bekommst ein Gefühl für unterschiedliche Algorithmen.


Anmelden zum Antworten