Drehroutine: Trigonometrie in Assembler

Trigonometrische Funktionen in einer höheren Programmiersprache, wiez.B. BASIC oder PASCAL, einzusetzen, ist relativ einfach. Schwierigerwird es, wenn man sich auf der untersten Ebene der Programmierkunst bewegt, da, wo man wirklich alles selber machen muß, in Assembler. Aber ist es wirklich so schwierig?

Dr. Michael Schütz

Nein, sonst gäbe es vermutlich diesen Artikel nicht. Die Programmierung in Assembler unterscheidet sich deutlich von höheren Sprachen. Hierbei überlegt man sich mindestens zweimal, ob für eine Rechnung wirklich Realzahlen erforderlich sind, oder ob vielleicht ein quadratisches Ergebnis nicht ebensogut für die Länge eines Vektors zu gebrauchen sei wie (mathematisch korrekt) die Wurzel daraus.

Wozu Trigonometrie in Assembler?

Wer selber programmiert, weiß, wie langsam Interpreter, aber auch Compiler, mit dem „Sinus“ und „Cosinus“ fertigwerden. Sicherlich, die Werte mit acht bis zehn Stellen hinter dem Komma auszurechnen, braucht eine gewisse Zeit (immerhin muß eine Potenzreihe mit fünf bis zehn Gliedern ausgerechnet werden), aber für die meisten Anwendungen, wie z.B. für eine Drehroutine, reicht ein gerundeter Wert im Integerformat auch. Daß dabei faszinierende Geschwindigkeiten erreicht werden können, zeigen Grafikprogramme wie STAD oder SHORTY. Aber nicht nur die Geschwindigkeit, die Funktionen wie das Drehen eines Ausschnittes um beliebige Winkel erst erträglich macht, nein auch die Programmlänge sollte im Zeitalter der 4-MB-Rechner nicht außer acht gelassen werden. Das im folgenden beschriebene und abgedruckte Programm ist 760 Byte lang und vermag einen Ausschnitt um beliebige ganzzahlige Winkel zu drehen.

Von der Theorie ...

Die Theorie der Drehung eines Vektors um einen Winkel Alpha beschränkt sich auf zwei Gleichungen:

py = xcos(a) + ysin(a)
px = ycos(a) - xsin(a)

Bild 1: Sin/Cos-Verlauf im Bereich von 0-360°

Und schon hat der Vektor mit den Koordinaten x, y die neue Position px, py. Die einzige Schwierigkeit dabei: Wie komme ich an die SIN- und COS-Werte? Da wir einen Vektor oder einen Ausschnitt nur um ganzzahlige Winkel drehen wollen, brauchen wir maximal 360 Sinus- und ebensoviel Cosinus-Werte. Das hört sich doch recht wenig an .... 720 Werte, da könnte man doch eine Tabelle.... richtig, nichts geht schneller, als die gewünschten Werte einfach aus einer im Programm befindlichen Tabelle zu holen. Bei 720 Daten im 2-Byte-Integerformat ergibt sich eine Tabellenlänge von 1440 Byte. Unter der Berücksichtigung, daß gilt:

cos(a) = sin(a+90)

kann die Hälfte der Tabelle eingespart werden, indem für den Cosinus- der Sinus-Wert des Winkels+90° berechnet wird. Es gibt noch eine weitere Vereinfachung. Es reicht nämlich aus, die Sinus-Funktion im Bereich von 0 bis 90° zu tabellieren, da der Bereich von 90 bis 180° einfach an der 90°-Senkrechten gespiegelt ist (vgl. Bild 1). Beispiel:

sin(110°) = sin(180-110°) = sin(70°)
cos(110°) = sin(110+90°) = -sin(20°)

... zur Praxis

Mit dieser Theorie bewaffnet, schreiten wir zur Tat. Das Programm ist in mehrere Teile gegliedert:

drehen: Start der Routine
mitte: Mittelpunkt berechnen
block: dreht einen Ausschnitt
npos: berechnet neue Koordinaten
up-dreh: die eigentliche Drehroutine
cosi: berechnet sin/cos

Als erstes stellt die cos/-Routine sicher, daß der Drehwinkel 360° nicht überschreitet, bevor die sin/cos-Werte ermittelt werden. In den Zeilen 25-47 folgen dann die Berechnung des Mittelpunktes, um den gedreht wird, und eine kurze Löschrou-tine, da die Ausschnittroutine {block) nur gesetzte Punkte dreht (der Zielbildschirm muß deshalb weiß sein). Ab Zeile 49 kann man sagen: es geht rund. Die Hauptschleifen (rd0-rd2) werden mit Parametern gefüttert {dx, dy, Quelle, Ziel) und jedes „gedrehte“ Bit wird ab Zeile 69 (plot) wieder gesetzt.

Beendet wird die Rotation durch die Berechnung der neuen Ausschnittgrenzen (px1, py1, px2, py2) ab Zeile 105.

GEM und die Auflösung

Wie an vielen Stellen zu sehen ist, unterstützt das Programm die Auflösung 640*400. Wird eine variable Auflösung gewünscht, müssen entsprechend die Grenzen (640,400 bzw. 639, 399) und die Zeilenbreite (80) angepaßt werden. Aus Geschwindigkeitsgründen empfehle ich den Bereich zu pat-chen (direktes Ändern der Zahlen im laufenden Programm, durch das Programm).


; Variabel Drehen ; von Dr. Michael Schütz ; ; (c) 1992 MAXON Computer ; ; ; INPUT: d0 Drehwinkel ; dx Breite des Ausschnittes ; dy Höhe des Ausschnittes ; px1 Position zum drehen ; py1 Position zum drehen ; ; OUTPUT: Koordinaten des gedrehten ; Ausschnittes ; px1 Ecke oben links x ; py1 Ecke oben links y ; px2 Ecke unten rechts x ; py2 Ecke unten rechts y ; ;-------------------------------------------- drehen: bsr cosi ; Winkel berechnen lea mx,a1 ; Mittelpunkt x lea my,a5 ; Mittelpunkt y move.w dx,d7 ; breite x move.w dy,d6 ; Breite y ext.l d7 ; als .l ext.l d6 ; als .l asr.w #1,d6 ; /2 asr.w #1,d7 ; /2 move.w d7,(a1) ; Mittelpunkt x move.w d6,(a5) ; Mittelpunkt y bsr up_dreh ; um Winkel drehen sub.w d6,(a1) ; sub.w d7,(a5) ; move.w px1,d0 ; Plus Start x add.w d0,(a1) ; move.w py1,d0 ; Plus Start y add.w d0,(a5) ; block: movea.l ziel,a0 ; Zielbildschirm movea.l a0,a4 ; auch nach a4 move.l #7999,d0 ; 32000 Byte .0: clr.l (a0)+ ; löschen dbra d0,.0 ; loop move.w dx,d5 ; breite x addi.w #1,d5 ; +1 movea.l #guelle,a0 ; Quelle start clr.w d3 ; y Zähler movea.l a0,a2 ; Quelle suba.w #80,a2 ; -80 (eine Zeile) .rd0: clr.w d1 ; x Zähler adda.w #80,a2 ; +80 (eine Zeile) movea.l a2,a0 ; Pointer sichern .rd1: move.b (a0)+,d4 ; Byte holen beq .re ; =0 ? ==> .re move.w #7,d2 ; 7 Bits .rd2: btst d2,d4 ; Bit gesetzt ? beq .bit ; nein --> .bit move.w d1,d7 ; ja X move.w d3,d6 ; Y bsr up_dreh ; errechnen add.w (a1),d6 ; Plus Mitte x add.w (a5),d7 ; Plus Mitte y .plot: addq.w #1,d6 ; x+1 cmpi.w #399,d7 ; max. y=399 bgt .bit ; zu groß tst.w d7 ; <0? blt .bit ; zu klein cmpi.w #639,d6 ; max. x=639 bgt .bit ; zu groß tst.w d6 ; <0? blt .bit ; zu klein addi.w #1,d7 ; y+1 mulu.w #80,d7 ; *80 Zeilen subi.w #640,d6 ; x=640-x neg.w d6 ; ext.l d6 ; und als .l divu.w #8,d6 ; d6=d6/8 sub.w d6,d7 ; Spalte subq.l #1,d7 ; -1 swap.w d6 ; das Bit bset d6,0(a4,d7.w) ; und setzen .bit: addq.w #1;dl ; Zähler erhöhen dbra d2,.rd2 ; weiter --> .rd2 .ree: cmp.w d5,d1 ; Breite x ? blt .rd1 ; nein --> .rd1 cmp.w dy,d3 ; Höhe y ? bgt .npos ; ja --> .npos addq.w #1,d3 ; sonst Y+1 bra .rd0 ; und --> .rd0 .re: addq.w #8,d1 ; + 8 Bit bra .ree ; und weiter ; ------------------------------------------- ; Neue Position berechnen ; ------------------------------------------- .npos: move.w #639,d0 ; max. x move.w #399,d1 ; max. y clr.w d2 ; min. x clr.w d3 ; min. y clr.w d7 ; Pos 0,0 clr.w d6 ; bsr dreh ; errechnen move.w dx,d7 ; Pos dx, 0 clr.w d6 ; bsr dreh ; errechnen move.w dx,d7 ; Pos dx,dy move.w dy,d6 ; bsr dreh ; errechnen clr.w d7 ; Pos 0,dy move.w dy,d6 ; bsr dreh ; errechnen tst.w d0 ; Test x1 bgt .n1 ; >0 --> .n1 clr.w d0 ; sonst =0 .n1: tst.w d2 ; Test x2 bgt .n2 ; >0 --> .n2 clr.w d2 ; sonst =0 .n2: tst.w d1 ; Test y1 bgt .n3 ; >0 .n3 clr.w d1 ; sonst =0 .n3: tst.w d3 ; Test y2 bgt .n4 ; >0 --> .n4 clr.w d3 ; sonst =0 .n4: move.w d0,px1 ; neue Position move.w d1,py1 ; des gedrehten move.w d2,px2 ; Ausschnittes auf move.w d3,py2 ; Bildschirm ziel rts ; ende dreh: bsr up_dreh ; drehen add.w (a1),d6 ; Mittelpunkt x add.w (a5),d7 ; Mittelpunkt y cmp.w d6,d0 ; Der größte blt .lo1 ; und der move.w d6,d0 ; kleinste Wert .lo1: cmp.w d7,d1 ; der neuen blt .lo2 ; Koordinaten move.w d7,d1 ; steht in : .lo2: cmp.w d6,d2 ; d0=x1 klein bgt .lo3 ; d1=y1 klein move.w d6,d2 ; d2=x2 groß .lo3: cmp.w d7,d3 ; d3=y2 groß bgt .lo4 ; move.w d7,d3 ; .lo4: rts ; ;------------------------------------ ; Daten ;------------------------------------ quelle: .DC.l 0 ; Adresse des Quellbildes ziel: .DC.l 0 ; Adresse der Zielbildes mx: .DC.w 0 ; Mittelpunkt x my: .DC.w 0 ; Mittelpunkt y dx: .DC.w 0 ; Breite x dy: .DC.w 0 ; Breite y px1: .DC.w 0 ; Position x1 py1: .DC.w 0 ; Position y1 px2: .DC.w 0 ; Position x2 py2: .DC.w 0 ; Position y2 ;------------------------------------ ; Die eigentliche Drehroutine ;------------------------------------ up_dreh: movem.l d0-d4,-(sp) ; Reg. retten move.w #10000,d2 ; Multiplikator move.w sinx,d3 ; d3=sin(w) move.w cosx,d4 ; d4=cos(w) move.w d3,d0 ; d0=sin(w) move.w d4,d1 ; d1=cos(w) muls.w d6,d4 ; d4=x*cos(wj muls.w d7,d3 ; d3=y*sin(w) add.l d4,d3 ; d3=d3+d4 divs.w d2,d3 ; d3=d3/10000 muls.w d7,d1 ; d1=y*cos(w) muls.w d6,d0 ; d0=x*sin(w) sub.l d0,d1 ; d1=d1-d0 divs.w d2,d1 ; d1=d1/10000 ext.l d1 ; neuer x-Wert move.l d1,d6 ; nach d6 ext.l d3 ; neuer y-Wert move.l d1,d7 ; nach d7 movem.l (sp)+,d0-d4 ; Reg. zurück rts ; und ende ;------------------------------------ ; Sinus und Cosinuswerte berechnen ;------------------------------------ cosi: cmpi.w #360,d0 ; Winkel Test ble .0 ; <=360 Grad subi.w #360,d0 ; sonst -360 bra cosi ; und loop .0: add.w d0,d0 ; 2 Byte Integer move.w d0,winkel ; als Winkel cmpi.w #181,d0 ; <90 Grad blt .3 ; ja --> .0 cmpi.w #361,d0 ; <180 Grad blt .1 ; ja -->.1 cmpi.w #540,d0 ; >270 Grad bgt .2 ; ja —> .2 subi.w #360,d0 ; -360 bsr .3 ; .r: neg.w sinx ; sinx=-sinx neg.w cosx ; cosx=-cosx rts ; und ende .1: subi.w #180,d0 ; -180 (90) lea sin,a0 ; für <=180 Grad move.w 0(a0,d0.w),cosx ; cosx=sin(x-90) neg.w cosx ; cosx=-cosx lea cos,a0 ; neg.w d0 ; move.w 0(a0,d0.w),sinx ; sinx=cos(x-90) rts ; .2: subi.w #360,d0 ; -360 (180) bsr .1 ; <360 bra .r ; .3: lea sin,a0 ; für <= 90 Grad move.w 0(a0,d0.w),sinx ; sinx=sin(d0) lea cos,a0 ; neg.w d0 ; move.w 0(a0,d0.w),cosx ; cosx=cos(d0) rts ; sinx: .DC.w 0 ; Sinuswert sin(winkel) cosx: .DC.w 0 ; Cosinuswert ccs(winkel) winkel: .DC.w 0 ; Winkel zum Drehen ;------------------------------------ ; Sinuswerte / sin(x)*1000 ;------------------------------------ sin: .DC.w 0000,0174,0348,0523,0697,0871,1045 .DC.w 1218,1391,1564,1736,1908,2079,2249 .DC.w 2419,2588,2756,2923,3090,3255,3420 .DC.w 3583,3746,3907,4067,4226,4383,4539 .DC.w 4694,4848,5000,5150,5299,5446,5591 .DC.w 5735,5877,6018,6156,6293,6427,6560 .DC.w 6691,6819,6946,7071,7193,7313,7431 .DC.w 7547,7660,7771,7880,7986,8090,8191 .DC.w 8290,8386,8480,8571,8660,8746,8829 .DC.w 8910,8987,9063,9135,9205,9271,9335 .DC.w 9396,9455,9510,9563,9612,9659,9702 .DC.w 9743,9781,9816,9848,9876,9902,9925 .DC.w 9945,9961,3975,9986,9993,9998 cos: .DC.w 10000


Links

Copyright-Bestimmungen: siehe Über diese Seite