Hello, Guest the thread was viewed1.1k times and contains 25 replies

last post from Krill at the

TSB: Kreise mit Bresenham und ohne

  • Ich hab mal eine Frage an Systemprogrammierer. Ich hab mal mit TSB (in Simons' Basic wäre das so ähnlich) einen Kreis mit Bresenham-Algorithmus (mit dem Befehl PLOT) und dann mit identischen Parametern mit dem eingebauten Befehl ARC malen lassen. Ergebnis: die PLOT-Version ist viereinhalb Mal schneller als der Maschinenalgorithmus von ARC. Das liegt nun daran, dass (T)SB Kreise mit SIN und COS berechnen und zwar Punkt für Punkt (keine Quadranten bzw. Oktanten wie Bresenham).


    Meine Frage nun: Wie kann ich bei Bresenham clippen, so dass ich einen Befehl wie ARC (wenn ich das umprogrammiere) auch für Kreisbögen - wofür er gedacht ist - verwenden kann? In BASIC65 (vom Mega65) scheint das zu gehen.


    Hier mein Listing (läuft unter TSB und zeichnet zwei Kreise mit Angabe der Abarbeitungsdauer):

    Mein (Fern-) Ziel ist es, die schnarchlangsamen Algorithmen von Simons' Basic in TSB zu ersetzen. Geht das überhaupt? (Die Sprite-Bewegungsbefehle nutzen ebenfalls die PLOT-Routinen.)


    Arndt

  • Mir geht‘s vor allem darum, nur Teile eines Bresenham-Kreises zeichnen zu können, mit Angabe von Startwinkel und Endwinkel. Der Algorithmus für Vollkreise ist in HSG ja schon ziemlich unübertrefflich (in obigem Demo würde ein HSG-Kreis 00.06s brauchen).


    Arndt

  • Einige Gedanken dazu:


    Mich wundert zunächst mal, daß der mit Plot "nachgebaute" Bresenham in den Zeilen 1000 bis 1080 jetzt schon schneller sein soll als der ARC Befehl. Dann kann der doch raus, sozusagen.


    Üblicherweise wird ein Kreis-Bresenham noch so verfeinert, daß die Multiplikationen komplett rausfliegen, damit entfallen dann auch 2*x und 2*y und werden durch "2x" und "2y" ersetzt, welche parallel um 2 erhöht bzw. erniedrigt werden.


    So wie ich das sehe, kann der ARC-Befehl keine Ellipsen zeichnen. Eine Möglichkeit der Nachimplementierung von V3.5/V7 CIRCLE, mit einer Sinus- und Cosinus-Tabelle, die das kann, hab' ich mal für MINIGRAFIK gemacht:

    Bedeutung der Variablen:

    Kreis(bögen) und Ellipsen(bögen) werden hier, wie beim CIRCLE-Befehl aus V3.5/V7 aus Linienstücken gezeichnet. Allerdings wird nicht gegen den Bildschirmrand beschnitten, das muß der Line-Befehl selbst machen.


    ...


    Ich hätte auch noch eine BASIC- und Maschinensprach-Implementierung einer puren Bresenham-Ellipse parat. Die braucht man beim VC ohnehin um überhaupt Kreise zeichnen zu können (die Pixel sind ja deutlich rechteckig, und mit einer Ellipse kann man das kompensieren), aber da hab ich's (noch) nicht geschafft, ihr Bögen beizubringen. Dazu müßte man meines Erachtens zwei Geradengleichungen zu den Winkeln hernehmen und mit den aktuellen x,y-Offsets vergleichen, und dabei eine Menge Fallunterscheidungen mit hineinnehmen ...

  • Ich mach mal einen Schuss ins Blaue: Anfangs- und Endpunkt des Bogens als x/y berechnen, ein Rechteck durchlegen und jeden gemalten Punkt gegen das Rechteck clippen. Man müsste zwischen <180 und >180 Grad-Bögen unterscheiden, im einen Fall nur innerhalb und im anderen nur außerhalb des Rechtecks malen.

  • Ich hatte für Kreise am CPC (als ich mir einen CIRCLE Befehl gebaut habe) eine Routine aus einer Zeitschrift genommen, die nur mit Integer-Werten auskommt. Die hatte ich modifiziert, so daß nur 1/4 Kreis berechnet wird und der Rest gespiegelt. War sau schnell.


    Sowas in der Art konnte ich jetzt beim Googlen finden https://mark-ogden.uk/mirrors/…lle/SchnelleTabellen.html

  • Ich mach mal einen Schuss ins Blaue: Anfangs- und Endpunkt des Bogens als x/y berechnen, ein Rechteck durchlegen und jeden gemalten Punkt gegen das Rechteck clippen. Man müsste zwischen <180 und >180 Grad-Bögen unterscheiden, im einen Fall nur innerhalb und im anderen nur außerhalb des Rechtecks malen.

    Für Winkel zwischen 90° und 180° lassen sich für diese Methode recht schnell Gegenbeispiele finden, wo Teile des Kreisbogens nicht richtig berücksichtigt werden:



    So einfach geht's also leider nicht. :(

  • jetzt schon schneller sein soll als der ARC Befehl. Dann kann der doch raus, sozusagen.

    Nein, die Grafikbefehle sind alle miteinander verbandelt.

    So wie ich das sehe, kann der ARC-Befehl keine Ellipsen zeichnen.

    Doch, Ellipsen kann er, deswegen rx und ry im Bresenham-Beispiel.

    Üblicherweise wird ein Kreis-Bresenham noch so verfeinert, daß die Multiplikationen komplett rausfliegen, damit entfallen dann auch 2*x und 2*y und werden durch "2x" und "2y" ersetzt, welche parallel um 2 erhöht bzw. erniedrigt werden.

    Ah ja! Stimmt. :zustimm:

    Anfangs- und Endpunkt des Bogens als x/y berechnen, ein Rechteck durchlegen und jeden gemalten Punkt gegen das Rechteck clippen.

    Genau das war's, worauf ich hinaus wollte! Das muss doch irgendwie möglich sein?

    Für Winkel zwischen 90° und 180° lassen sich für diese Methode recht schnell Gegenbeispiele finden,

    Oder doch nicht?


    Arndt

    ( Mike : Ich bau mal dein Beispiel für TSB um.)

  • Bezug auf Post #4: War das so gedacht? Das Programm zeichnet zuerst einen Kreis, darüber dann immer mehr eine senkrechte Ellipse, dreht weiter über noch mal eine senkrechte Ellipse und endet wieder im Kreis:


    Listing:

    Arndt

  • Ich hatte für Kreise am CPC (als ich mir einen CIRCLE Befehl gebaut habe) eine Routine aus einer Zeitschrift genommen, die nur mit Integer-Werten auskommt. Die hatte ich modifiziert, so daß nur 1/4 Kreis berechnet wird und der Rest gespiegelt. War sau schnell.

    Man kann auch X/Y tauschen, dann genügt das Berechnen von 1/8 des Kreises. Behebt aber immer noch nicht das Clipping :)

  • Man kann auch X/Y tauschen, dann genügt das Berechnen von 1/8 des Kreises. Behebt aber immer noch nicht das Clipping :)

    So funktionierte mein Beispiel. Es zeichnet einen Kreis mit PLOT in rund 6 Sekunden an acht Stellen gleichzeitig. Darum ja meine Frage nach dem Einschränken.


    Arndt

  • So in etwa?

    Quote

    To draw only a certain arc from an angle \alpha to an angle \beta, the algorithm needs first to calculate the x and y coordinates of these end points, where it is necessary to resort to trigonometric or square root computations (see Methods of computing square roots). Then the Bresenham algorithm is run over the complete octant or circle and sets the pixels only if they fall into the wanted interval. After finishing this arc, the algorithm can be ended prematurely.


    If the angles are given as slopes, then no trigonometry or square roots are necessary: simply check that y/x is between the desired slopes.

  • Bezug auf Post #4: War das so gedacht? Das Programm zeichnet zuerst einen Kreis, darüber dann immer mehr eine senkrechte Ellipse, dreht weiter über noch mal eine senkrechte Ellipse und endet wieder im Kreis:

    Grundsätzlich ja, aber das Ergebnis "landet" jetzt im wesentlichen im Koordinatenbereich von MINIGRAFIK auf dem VC-20, also 160x192. Auch das Pixel-Aspekt-Verhältnis in W hattest Du nicht angepaßt, dadurch "verziehen" sich jetzt die gedrehten Ellipsen obwohl sie eigentlich ihre Form beibehalten sollten.


    Damit das alles paßt, solltest Du Initialisierung und Aufruf der Routine in den Zeilen 100 bis 180 wie folgt ändern:

    Code
    1. 100 [...]:W=1
    2. [...]
    3. 140 [...]:N=80:A=60:[...]
    4. [...]
    5. 170 M=70+X*.5
    6. 180 B=33:[...]

    Dann kommt das wieder so raus, wie das im Original mit dem CIRCLE-Befehl gedacht war - ich hatte die Parametrierung genau andersherum in Richtung VC-20 angepaßt, damit das Ergebnis visuell gleich bleibt.


    Ein Pixel-Aspekt-Verhältnis von W=1 stimmt zwar nicht ganz für den C64, ist hier aber genau genug. :)

  • Typo in der Korrektor? X -> P, oder?

    Code
    1. 170 M=70+P*.5

    Ja. Mist. Da sollte ein P stehen.:schande: GoDot - Arndt, die Figur sollte dann genau zentriert auf dem Bildschirm erscheinen, ohne die Öffnung in der Mitte. Mit P=0 ist M=70, mit P=180 (eine halbe Umdrehung) ist M=160, also genau in der Mitte, und mit P=360 ist dann M=250, bis 320 sind es dann wieder 70 Pixel.

  • die Figur sollte dann genau zentriert auf dem Bildschirm erscheinen

    Tut sie leider nicht, denn

    mit P=180 (eine halbe Umdrehung) ist M=160

    m=70+p/4 -> m=70+180/4= 115 (x-Mittelpunkt der ganz linken waagerechten Ellipse) und

    mit P=360 ist dann M=250

    m=70+360/4= 160 (x-Mittelpunkt der ganz rechten waagerechten Ellipse).


    Oder hab ich irgendwo was übersehen?


    Arndt


    Edit: Aber wir entfernen uns vom Thema!