Hallo Besucher, der Thread wurde 1,2k mal aufgerufen und enthält 8 Antworten

letzter Beitrag von Mike am

Ein Highres-Kreis in BASIC, möglichst kurz und schnell, wer kanns?

    Anlass ist dieser Vergleich:



    Leute, das muss doch auch kürzer gehen, oder? Und vielleicht auch schneller als der Specci?


    Hier als Referenz die Doku des Circle-Befehls wie er in Spectrum-Basic implementiert ist:

    - https://zxbasic.readthedocs.io/en/docs/circle/


    Oben in CBM-BASIC das ist ja ein ziemlicher Spaghetti-Code, man beachte z.B. Zeile 15 und dann 90.


    Wer bekommt es kürzer und evtl. sogar schneller hin, als der Circle-Befehl des Spectrum-Basic. Und zwar nicht nur mit Hilfe von ExBasic-Level-II, Simon's-Basic oder einer anderen Erweiterung, sondern insbesondere mit dem originalen CBM BASIC V2.0 im ROM und in Assembler.


    4 Kategorien:


    1. In CBM BASIC 2.0

    2. Simon's BASIC - das dürfte einfach ein 1-2-Zeiler sein: https://www.c64-wiki.de/wiki/CIRCLE

    3. ExBasic Level II - das kennt scheinbar keine passenden Grafikbefehle, wird einem also wahrscheinlich keinen Vorteil verschaffen

    4. Assembler mit Aufruf per SYS aus BASIC


    Die eigentliche Routine, welche den Kreis zeichnet, soll die gleichen Parameter <x>, <y> und <radius> bekommen, welche auch der Circle-Befehl auf dem Specci hat. Die jeweilige Laufzeit des Programms wäre auch interessant. Wer einen Specci hat, kann hier mal die Referenzzeit für den Circle-Befehl vorgeben, die zumindestens für Variante 2, und 4 zu schlagen wäre, der Circle-Befehl läuft ja dort sicher auch in Z80-Assembler.


    Randbedingung: Die Zeitmessung muss auf Originalhardware ohne Hardware-Beschleunigung (Super-CPU, Turbo-Chameleon, c't 65sc816 Karte, etc.) oder Vice in Standardkonfig erfolgen, sonst wärs ja unfair.


    Ich bin gespannt!

    Wenn man die Parameterdarstellung des Kreises mit Sinus und Cosinus hernimmt, dann ist das ein Garant dafür, daß das in BASIC weder kurz noch schnell ist. Pures BASIC V2 auf dem C64 bringt darüber hinaus exakt 0 % Unterstützung für Grafik mit, mehr als 50 % von so einem Demonstrationsprogramm gehen dann erstmal dafür drauf, die Grafik einzuschalten, die Bitmap zu löschen und einzelne Pixel zu zeichnen. Vergleiche mit einem CIRCLE-Befehl, der in einem anderen BASIC fix als Maschinencode eingebaut ist, sind darum erstmal Äpfel und Birnen.


    Der Bresenham für Kreis oder Ellipse (abgeleitet aus der Kegelschnittgleichung) braucht ca. ein Dutzend Programmzeilen. Die innere Schleife benötigt dann ausschließlich Additionen, Subtraktionen, Absolutwertbildung und Vergleiche. Zur Berechnung einiger Hilfsvariablen werden vor der inneren Schleife noch Multiplikationen benötigt, "teure" Operationen wie Division, SIN(), COS() oder SQR() kommen gar nicht vor. Das sieht dann etwa so aus:

    Das ist ein Ausschnitt aus einem kompletten Programm für BASIC V3.5 oder V7.0 in dem Thread hier: "Wake Up Clock!!!!". Den DRAW-Befehl muß man in BASIC V2 als Unterprogramm abbilden, die Details dazu erspare ich mir hier.


    In BASIC ist das jetzt immer noch nicht besonders schnell (aber wenigstens mathematisch genau!), eine Implementierung in 65xx-Maschinencode habe ich aber zur Hand und die schafft ca. 4000 Punkte pro Sekunde. Dem Kreis oder der Ellipse kann man dann nicht mehr beim Malen zuschauen, die Figur steht dann praktisch instantan auf dem Bildschirm.

    Bei Input64 gab's dafür mal einen Wettbewerb. Ich meine, das praktikabelste ist DX/DY rechnen, und spiegeln. Eigentlich muss man nur einen Achtel-Kreis rechnen, die anderen Teile kann man durch spiegeln der X/Y-Position um die Achsen bzw. vertauschen von DeltaX/DeltaY errechnen.

    Zitat von Endurion

    Bei Input64 gab's dafür mal einen Wettbewerb. Ich meine, das praktikabelste ist DX/DY rechnen, und spiegeln. Eigentlich muss man nur einen Achtel-Kreis rechnen, die anderen Teile kann man durch spiegeln der X/Y-Position um die Achsen bzw. vertauschen von DeltaX/DeltaY errechnen.

    Eine derartige Optimierung (für die Ellipse ist allerdings nur die 4-fach-Symmetrie möglich) ist in meinem Beispiel unmittelbar vor deinem Beitrag schon eingepreist. ;)

    Ich finde es immer sehr spannend, wenn in solchen Artikeln in der Herleitung vorkommende Brüche durch Handwedelei wegdiskutiert werden.


    Meine Implementierung in Beitrag Nummer #4 ist, nochmals gesagt, mathematisch exakt und kommt ausschließlich mit ganzen Zahlen aus. Während der Kreis- bzw. Ellipsenbogen 'verfolgt' wird, wählt die Fallunterscheidung in den Zeilen 34 bis 37 aus drei möglichen Kandidaten den Punkt aus, der den geringsten Abstand vom Bogen hat. Während des 'oberen' Teils des Bogens kommen dabei (automatisch) nur die Fälle 0 (waagerecht) und 1 (diagonal) in Betracht, im 'rechten' Teil wechselt das dann zu 1 (diagonal) und 2 (senkrecht). Der Algorithmus vermeidet dabei eine komplizierte Fallunterscheidung wo der 45°-Winkel liegt, weil das erstens wiederum komplizierte Fließkomma-Rechnungen braucht und zweitens dies bei sehr dünnen Ellipsen auch fehlschlagen kann (die Ellipse wird dann nicht vollständig gezeichnet!).


    andi6510: Die "Methode von Jesko" kann aus der Differentialgleichung für den Kreis (y' = -x/y) abgeleitet werden, ist aber durch die endliche Schrittweite auf dem Bildschirm ebenfalls nicht 100%ig exakt.


    ...


    Und falls sich wer wundert, warum ich den einfacheren Kreis-Bresenham hier gar nicht erst anbringe: der Ellipsen-Bresenham ist erstens eine nützliche Verallgemeinerung mit wenig mehr Aufwand, und zweitens sind nicht auf jedem Rechner die Pixel quadratisch (so z.B. auf dem VC-20), so daß man von vornherein schon eine Ellipse zeichnen muß um das auszugleichen. :whistling: