Kreis in Assembler

[Dr. Irata]

Fujiama ist over, mein Programm abgegeben, Zeit mal wieder für ein "Problem", was ich hier schon längs bearbeiten wollte:

Einen Kreis mit Radius r und den Koordinaten x,y in Assembler berechnen und zeichnen lassen.
Sicherlich gibt es hier einige gute Ansätze, die ich gerne mit euch entwickeln bzw. besprechen würde. Es sollte am Ende ein schnelles, kurzes und elegantes Verfahren herauskommen.
Dabei würde ich gerne 2 verschiedene Ansätze mit euch entwickeln: Ein Ansatz darf Tabellen hinterlegen und ein anderer Ansatz muss es berechnen ohne Tabellen.
Das Ergebnis kommt dann gut aufgearbeitet mit entsprechendem Assembler Code (MADS) und Erklärung ins nächste Magazin...

[Irgendwer]

"ATMAS Toolbox" https://atariwiki.org/wiki/attach/Atmas ... mas2tb.atr
enthält eine sehr schnelle Kreisroutine in Assembler - die im Wesentlichen dem entspricht, was ich auch in "Disc'o Pop" umgesetzt habe.

[Dr. Irata]

gibt es da auch einen lesbaren Quellcode??

[Irgendwer]

...und noch ein kleiner Zusatzhinweis:
Die meisten Routinen können nur Kreise mit ungeradem Durchmesser. Für gerade Durchmesser braucht man extra Logik, wie z.B. hier diskutiert:
https://stackoverflow.com/questions/358 ... n-diameter

[Irgendwer]

gibt es da auch einen lesbaren Quellcode??

Ja, Quellen sind dabei.

[Irgendwer]

Als kleiner Service :

KREISE.DOC

Code: Alles auswählen

=====================================

         Dokumentation zu

            KREISE.SRC

=====================================

Haben Sie schon versucht, Kreise in
BASIC auf den Bildschirm zu zeichen?
Wenn ja, dann wissen Sie, dass man
dabei am besten den Kaffe holt,
Zigarette besorgen geht, oder den
fehlenden Schlaf der letzten am
Computer verbrachten Nacht nachholt.

In Maschinensprache geht natuerlich
alles schneller und besser, warum
soll's mit dem Kreisemalen nicht
genauso sein?

Bevor ein Kreis am Bildschirm er-
scheinen will, muss man gewoehnlich
schon etwas an Mathematik aufbieten.
Entweder strapaziert man die Kreis-
gleichung und kommt dem Kreis mit
Wurzeln auf die Spur, oder man
macht's mit Hilfe von trigono-
metrischen Funktionen, sprich Sinus
und Kosinus.

Jedem Assemblerprogrammierer wird
inzwischen der Mut vergangen sein,
denn mit Wurzeln oder gar einem
Sinus will man sich in Assembler
wirklich nicht herumschlagen.
Schliesslich hat man auch ohne Sinus
schon genug Probleme.


Es geht auch ohne
-----------------

Eine wirklich hochinteressante
Methode zum Zeichnen von Kreisen
habe ich im BASIC XL-TOOLKIT (von
OSS) entdeckt. Damit ist es moeglich,
einen Kreis nur mit Hilfe von
Additionen und Subtraktionen zu
berechnen. Das Pogramm arbeitet mit
einer Naeherungsformel fuer einen
Achtel-Kreisbogen, der ganze Kreis
wird dann durch Spiegelung dieses
Bogens erzeugt.

Am Ende dieses Files finden Sie
das BASIC-Programm als Anhang.

Da ich vor gar nicht zurueckschrecke,
habe ich dieses Programm sogleich
in Assembler umgesetzt, und, Sie
werden es sehen, was herausgekommen
ist tatsaechlich beeindruckend.


High-Speed PLOT
===============

Wuerde man jetzt mit diesem wirklich
schnellen Kreis-Algoritmus die PLOT
Routine des Betriebssystems ver-
wenden, so hiesse das einen Porsche
mit Goggomotor zu fahren.

Nein, hier musste schon eine super-
schnelle PLOT-Routine her. Die finden
Sie in dem UP PLOT, es arbeitet mit
allen Zwei-Farb Graphikmodi (GR.4,6,
8,14) und geht, da es mit Tabellen
arbeitet, recht flott.

Die geplotteten Punkte werden Ex-
klusiv-Oder verknuepft, d.h. wenn Sie
einen Punkt auf ein bereits gesetztes
Pixel plotten, so wird dieses ge-
loescht. Auf diese Art koennen Sie
einen Kreis einfach durch nochmaliges
Zeichnen wieder vom Bildschirm ent-
fernen.


DEMO
====

Im Demo-Programm werden Ihnen die
Faehigkeiten dieser Kreis-Routine
anschaulich gezeigt: Sie koennen
einen Kreis mit dem Joystick ueber
den Bildschirm bewegen. Die Groesse
des Kreises koennen Sie mit dem
Feuerknopf veraendern.

Benutzt wird die Graphikstufe 6,
die die gleiche Aufloesung wie GR.7
besitzt, nur eben mit zwei Farben
arbeitet. Sie koennen auch mal
GR. 14 versuchen, nur bekommen Sie
dann 'Eier' statt Kreise, da die
Pixels nicht mehr quadratisch sind.


Hier noch das Basic-Programm:
-----------------------------

 10 PHI=0:RADIUS=30
 20 MX=79:MY=47
 30 X=RADIUS:Y=0
100 GRAPHICS 6+16:COLOR 1

110 PLOT (MX+X,MY+Y)
130 PLOT (MX-X,MY+Y)

140 PLOT (MX-X,MY-Y)
120 PLOT (MX+X,MY-Y)

150 PLOT (MX+Y,MY+X)
170 PLOT (MX-Y,MY+X)

180 PLOT (MX-Y,MY-X)
160 PLOT (MX+Y,MY-X)

200 PHIY =PHI+Y+Y+1
210 PHIXY=PHIY-X-X+1
220 PHI  =PHIY
230 Y    =Y+1
240 IF ABS(PHIXY)>ABS(PHIY) THEN
    PHI=PHIXY:X=X-1
250 IF Y<=X THEN 110
290 GOTO 290



phi = 0;
y = 0;
x = radius;

mxpx = mx + x;
mxmx = mx - x;
mxpy = mx;
mxmy = mx;

mypy = my;
mymy = my;
mypx = my + x;
mymy = my - x;

do
{
plot (...)

phi = phi + y+y+1;
phixy = phi -x-x+1;

++y;
++mxpy;
--mxmy;
++mypy;
--mymy;


if abs(phixy) > abs(phi) then
   phi = phixy;
   --x;
   ++mxmx;
   --mxpx;
   ++mymx;
   --mypx;

}
while(y<=x)



Die einzelnen Befehle sind im
Assemblerprogramm als Kommentar
angegeben, so dass Sie sich leichter
zurechtfinden.

Noch ein Tip zum Schluss: Interessant
ist dieses Programm auch in GR. 8,
aber dazu reicht der reservierte
Speicherplatz ab $A800 nicht aus.
Waehlen Sie daher mit dem CUSTOMIZER
(Beschreibung siehe CUSTOM.DOC)
den EXTEND-Modus an, aendern Sie
ORG auf $9000 und ZLAENGE auf 40,
den GR.8 hat ja 40 BYTES pro Zeile.
Gestartet wird das PGM dann mit
G9000 im Monitor. Schliesslich koennen
Sie XMAX (achtung, nur bis 255!)und
YMAX noch vergroesern, um mehr
Bewegungsfreiheit zu bekommen.

Sie werden staunen, wie schnell
besonders die kleineren Kreise ueber
den Bildschirm flitzen.

[Irgendwer]

KREISE.SRC

Code: Alles auswählen

***********************************
*          High-Speed Kreise
*
*         in Maschinensprache
***********************************
*
* IOCB-Struktur, CIO-Befehle...
*
ICCOM	EQU $342
ICBAL	EQU $344
ICBAH	EQU $345
ICAX1	EQU $34A
ICAX2	EQU $34B
CIOV	EQU $E456   CIO-Vektor
COPEN	EQU   3
CCLSE	EQU  12
*
* Betriebssystem-Variable
*
SAVMSC	EQU  $58	   Bildschirm-Adresse
STICK0	EQU  $278   Joystick 0
STRIG0	EQU  $284   Trigger  0
*
* Konstante des Demo-Programmes
*
MX	EQU 79      Mittelpunkt X
MY	EQU 47      Mittelpunkt Y
RADMAX	EQU 79      max. Radius
YMAX	EQU 96      Aufloesung vert.
XMAX	EQU 160     Aufloesung hor.
ZLAENGE	EQU 20      Bytes pro Zeile
*
* Zeropage-Variable
*
ZEIGER	EQU $D4	   Zeropage fuer PLOT
XLAUF	EQU $D6     X-Laufvariable
YLAUF	EQU $D7     Y-Laufvariable
PHI	EQU $D8     Variable fuer
PHIY	EQU $DA     Naeherung
PHIXY	EQU $DC
APHIY	EQU $DE     Absolutwert PHIY
APHIXY	EQU $E0     Absolutwert PHIXY
MXLAUF	EQU $E2     Laufvariable MP
MYLAUF	EQU $E3
RADIUS	EQU $E4     Laufvariable Radius

	ORG $A800 im res. Bereich

*************************************
* Demo-Programm: Ein beliebig grosser
* Kreis kann mit dem Jostick am
* Schirm bewegt werden.
*************************************
*
* GRAPHICS 6+16
*
START	LDA #6+16	GRAPHICS 7,
	JSR GRAPHICS	ganzen Screen
	JSR PLOTAB	Tabellen...
	LDA #MX
	STA MXLAUF
	LDA #MY
	STA MYLAUF
	LDA #45		Vorgabe f.
	STA RADIUS

DEMO	JSR KREIS	Kreis zeichen
*
* Joystick oder Knopf aktiv
*
WARTEN	LDA STICK0	Stick 0
	CMP #15		bewegt?
	BNE KRSNEU	ja -->
	LDA STRIG0	Knopf gedr.
	BNE WARTEN	nein--
*
* wenn Joystick bewegt wurde, dann
* zuerst den alten Kreis loeschen
*
KRSNEU	JSR KREIS	Kreis loeschen

	LDA STICK0
	AND #8
	BNE LINKS
	INC MXLAUF
	JMP UNTEN
LINKS	LDA STICK0
	AND #4
	BNE UNTEN
	DEC MXLAUF
UNTEN	LDA STICK0
	AND #2
	BNE OBEN
	INC MYLAUF
	JMP TRIGGER
OBEN	LDA STICK0
	AND #1
	BNE TRIGGER
	DEC MYLAUF
*
* mit dem Feuerknopf kann der Radius
* veraendert werden.
*
TRIGGER	LDA STRIG0
	AND #1
	BNE SCHLUSS
	INC RADIUS
	LDA RADIUS
	CMP #RADMAX	zu gross?
	BCC SCHLUSS	nein-->
	LDA #3		min. Radius
	STA RADIUS
SCHLUSS	JMP DEMO

*************************************
* Dieses Unterprogramm zeichnet einen
* Kreis mit:
*
* RADIUS: Radius des Kreises
* MXLAUF: Mittelpunkt X-Koord.
* MYLAUF: Mittelpunkt Y-Koord.
*************************************

KREIS	LDA RADIUS
	STA XLAUF
	LDA #0
	STA YLAUF
	STA PHI
	STA PHI+1
*
PIXEL	JSR SPIEGEL
	JSR APPROX
*
* Until YLAUF>XLAUF
*
	LDA XLAUF
	CMP YLAUF
	BCS PIXEL
	RTS

*************************************
* Naeherung fuer 1/8-Kreissektor
*************************************
*
* PHIY=PHI+YLAUF+YLAUF+1
*
APPROX	LDA PHI+1
	STA PHIY+1
	CLC
	LDA PHI
	ADC YLAUF
	BCC APRX1
	INC PHIY+1
APRX1	CLC
	ADC YLAUF
	BCC APRX2
	INC PHIY+1
APRX2	STA PHIY
	INC PHIY
	BNE APRX3
	INC PHIY+1
*
* PHIXY=PHIY-XLAUF-XLAUF+1
*
APRX3	LDA PHIY+1
	STA PHIXY+1
	SEC
	LDA PHIY
	SBC XLAUF
	BCS APRX4
	DEC PHIXY+1
APRX4	SEC
	SBC XLAUF
	BCS APRX5
	DEC PHIXY+1
APRX5	STA PHIXY
	INC PHIXY
	BNE APRX6
	INC PHIXY+1
*
* PHI=PHIY
*
APRX6	LDA PHIY
	LDX PHIY+1
	STA PHI
	STX PHI+1
*
* YLAUF=YLAUF+1
*
	INC YLAUF
*
* Absolutwerte von PHIXY und PHIY
*
	LDX #PHIXY
	LDY #APHIXY
	JSR ABSOLUT
	LDX #PHIY
	LDY #APHIY
	JSR ABSOLUT
*
* IF ABS(PHIXY)<ABS(PHIY) THEN
*
	LDA APHIXY+1
	CMP APHIY+1
	BNE APRX7
	LDA APHIXY
	CMP APHIY
APRX7	BCS GRGLCH	ist '>='
*
* PHI=PHIXY:XLAUF=XLAUF-1
*
	LDA PHIXY
	LDX PHIXY+1
	STA PHI
	STX PHI+1
	DEC XLAUF
*
GRGLCH	RTS

************************************
* Acht Spiegelungen des Kreisbogens
* plotten
************************************
*
* PLOT MX+XLAUF, MY+YLAUF
*
SPIEGEL	LDA MXLAUF
	CLC
	ADC XLAUF
	TAX
	LDA MYLAUF
	CLC
	ADC YLAUF
	TAY
	JSR PLOT
*
* PLOT MX-XLAUF, MY+YLAUF
*
	LDA MXLAUF
	SEC
	SBC XLAUF
	TAX
	LDA MYLAUF
	CLC
	ADC YLAUF
	TAY
	JSR PLOT
*
* PLOT MX+XLAUF, MY-YLAUF
*
	LDA MXLAUF
	CLC
	ADC XLAUF
	TAX
	LDA MYLAUF
	SEC
	SBC YLAUF
	TAY
	JSR PLOT
*
* PLOT MX-XLAUF, MY-YLAUF
*
	LDA MXLAUF
	SEC
	SBC XLAUF
	TAX
	LDA MYLAUF
	SEC
	SBC YLAUF
	TAY
	JSR PLOT
*
* PLOT MX+YLAUF, MY+XLAUF
*
	LDA MXLAUF
	CLC
	ADC YLAUF
	TAX
	LDA MYLAUF
	CLC
	ADC XLAUF
	TAY
	JSR PLOT
*
* PLOT MX-YLAUF, MY+XLAUF
*
	LDA MXLAUF
	SEC
	SBC YLAUF
	TAX
	LDA MYLAUF
	CLC
	ADC XLAUF
	TAY
	JSR PLOT
*
* PLOT MX+YLAUF, MY-YLAUF
*
	LDA MXLAUF
	CLC
	ADC YLAUF
	TAX
	LDA MYLAUF
	SEC
	SBC XLAUF
	TAY
	JSR PLOT
*
* PLOT MX-YLAUF, MY-YLAUF
*
	LDA MXLAUF
	SEC
	SBC YLAUF
	TAX
	LDA MYLAUF
	SEC
	SBC XLAUF
	TAY
	JSR PLOT
	RTS

*************************************
* Berechnung des Absolutwertes
*                (Betrages)
*
* <X>:Zeiger auf 16-Bit Integer des
*     der umzuwandelnden Zahl
* <Y>:Zeiger auf Ergebnis (ebenfalls
*     16-Bit Int.), beides sind
*     Zeiger in die Zerpage!
*
*************************************

ABSOLUT	LDA 1,X		Vorzeichen des MSB		negativ?
	BMI ANEG		negativ->
	STA 1,Y		positive Zahl
	LDA 0,X		Absolutwert ist
	STA 0,Y		die Zahl selbst
	RTS
*
* bei neg. Zahlen: Zahl=0-Zahl
*
ANEG	SEC	
	LDA #0	zuerst das LSB
	SBC 0,X
	STA 0,Y
	LDA #0	und jetzt das MSB
	SBC 1,X
	STA 1,Y
	RTS

*************************************
* GRAPHICS-Unterprogramm
*
* Aufruf: JSR GRAPHICS
*
* PARAMETER:
* <A> 0 bis 15 (XL/XE)
*     0 bis 11 (400/800)
*************************************

GRAPHICS PHA		Graphik-Stufe merken
	LDX #$60		IOCB Nr. 6
	LDA #CCLSE	Screen-IOCB zuerst
	STA ICCOM,X	schliessen
	JSR CIOV
	PLA		Graphik-Stufe
	STA ICAX2,X	zurueckholen
	AND #$F0		und passende
	EOR #$10		Bit-Kombination
	ORA #$0C		fuer Handler
	STA ICAX1,X	herstellen
	LDA #COPEN	jetzt den Befehl
	STA ICCOM,X	zum Oeffen des Screens
	LDA #SDEVICE	Zeiger auf Device-
	STA ICBAL,X	bezeichnung
	LDA #SDEVICE/256
	STA ICBAH,X
	JMP CIOV
	RTS	

SDEVICE	ASC "S:"		Display-Handler

*************************************
* HI-SPEED PLOT fuer Einfarb-Modi
*
* Aufruf: JSR PLOT
*
* PARAMETER:
* <X>,<Y> je nach Graphikstufe
*************************************

PLOT	CPY #YMAX	Grenzen
	BCS PLOTEND	pruefen
	CPX #XMAX
	BCS PLOTEND
	LDA ADRLO,Y	Bildschirm-
	STA ZEIGER	adresse
	LDA ADRHI,Y	in Zeropage
	STA ZEIGER+1
	TXA
	LSR		;geteilt
	LSR		;durch 8
	LSR
	TAY		;Index f. X-Pos
	TXA		X-Position
	AND #7
	TAX
	LDA PIXTAB,X	Welches Pixel
	EOR (ZEIGER),Y	und Pixel manipulieren	
	STA (ZEIGER),Y	zurueck in Graphik
PLOTEND	RTS

**************************************
* Erzeugt Adresstabellen fuer Plot
*
* muss vor der ersten Verwendung von
* Plot und nach dem GRAPHICS-Befehl
* stehen!
***************************************

PLOTAB	LDA SAVMSC	Anfangsadresse
	STA ZEIGER	des Video-Rams
	LDA SAVMSC+1
	STA ZEIGER+1
	LDY #0		Index auf 0

NXTADR	LDA ZEIGER	Adresstabellen
	STA ADRLO,Y	aufbauen
	LDA ZEIGER+1	MSB-Tabelle
	STA ADRHI,Y
	CLC
	LDA ZEIGER	Adresse des
	ADC #ZLAENGE	naechsten Zeilen
	STA ZEIGER	anfangs berechnen
	LDA ZEIGER+1
	ADC #0
	STA ZEIGER+1
	INY
	CPY #YMAX	schon f. alle Zeilen?
	BNE NXTADR	nein -->
	RTS
*
* ab hier stehen die Tabellen
*
PIXTAB	DFB 128,64,32,16,8,4,2,1
ADRLO	ORG *+YMAX	Platz fuer
ADRHI	ORG *+YMAX	Tabellen

[Dr. Irata]

lieben Dank schon mal.... du bist schnell!!

Den einen Link von dir - vielen Dank - habe ich mir schon mal angeschaut und fand die Basic Version von Slatko Bleha von 1989 echt interessant:

1 REM *******************************
2 REM PROGRAM : FAST CIRCLE DRAWING
3 REM AUTHOR : ZLATKO BLEHA
4 REM PUBLISHER: MOJ MIKRO MAGAZINE
5 REM ISSUE NO.: 1989, NO.3, PAGE 29
6 REM *******************************
7 REM
10 GRAPHICS 8:SETCOLOR 2,0,0:COLOR 3
20 ? "ENTER X, Y AND R"
30 INPUT X,Y,R
40 IF R=0 THEN PLOT X,Y:END
50 B=R:C=0:A=R-1
60 PLOT X+C,Y+B
70 PLOT X+C,Y-B
80 PLOT X-C,Y-B
90 PLOT X-C,Y+B
100 PLOT X+B,Y+C
110 PLOT X+B,Y-C
120 PLOT X-B,Y-C
130 PLOT X-B,Y+C
140 C=C+1
150 A=A+1-C-C
160 IF A>=0 THEN 190
170 B=B-1
180 A=A+B+B
190 IF B>=C THEN 60

Mit diesen sehr einfachen Befehlen zeichnet man einen Kreis. Keine aufwendigen Berechnungen....
Echt cool!! Ist dein Assembler-Code die Umsetzung dieses Basic Codes??

LG
Peter

[LarsImNetz]

https://de.wikipedia.org/wiki/Bresenham-Algorithmus

Fand ich bisher immer recht hilfreich.
Da nur ein Quadrant berechnet wird, müssen die 8 Quadranten durch entsprechende Spiegelung der Position gesetzt werden.
Gegenüber DiscOPop nicht so schnell, dafür ist ein großer Kreis aber noch rund.