Tips und Tricks für Programmierer

Ich programmiere derzeit ein 3D-Weltraumspiel und benötige dazu eine Linienroutine, die ohne Rücksicht auf AES und VDI in den Bildschirm schreibt. Nur - schnell muß sie sein.

Für Probleme dieser Art haben wir unsere Experten aus der Demo-Programmierer-Ecke befragt: Hier der Vorschlag von Felix Brandt alias »Flix« der »Delta Force«:

Eine Assembler-Routine zu schreiben, die eine Linie von einem Punkt zu einem anderen zeichnet, scheint denkbar einfach zu sein. Tatsächlich kann man so eine Routine schnell entwickeln, jedoch wird die Geschwindigkeit der Routine sehr zu wünschen übrig lassen. In den meisten Fällen spielt aber gerade die Geschwindigkeit die größte Rolle (etwa Vektorgrafiken). Daher lohnt es sich, ein paar Taktzyklen durch Optimierung einzusparen. Die folgenden Beispiele dienen gleichzeitig als Anleitung optimierter Assemblerprogrammierung im allgemeinen.

Unsere Routine soll - nachdem man ihr in D0 und D1 die Koordinaten des ersten Punktes, in D2 und D3 die Koordinaten des zweiten Punktes und in A0 die Adresse des Bildschirmspeichers übergibt - eine Linie in einer Plane zwischen den beiden Punkten zeichnen. Die Routine auf der TOS-Disk läuft in allen drei ST-Auflösungen. Im Artikel besprechen wir aber nur die niedrige ST-Auflösung.

Eine Linie besteht bekanntlich aus Punkten. Daher liegt es nahe, eine Routine zu schreiben, die Koordinaten für eine Punktunterroutine liefert. Dabei ist es günstig, die Koordinaten der Anfangs- und Endpunkte der Linie gegebenenfalls so zu vertauschen, daß die Linien immer von links nach rechts gerichtet sind. Nun muß man zwischen zwei verschiedenen Arten von Linien unterscheiden: sogenannte »H-Linien«, bei denen die Differenz der X-Koordinaten größer ist als die der Y-Koordinaten (anschaulich formuliert sind das Linien, die eher einer Waagerechten als einer Senkrechten gleichen) und »V-Linien« (alle restlichen Linien). Alle weiteren Verfahren beziehen sich zunächst auf die H-Linien.

Man kann nun die X-Koordinate des zu zeichnenden Punktes von links nach rechts durchlaufen lassen und an den entsprechenden Stellen die Y-Koordinate um eins erhöhen oder erniedrigen. Die schnellste Methode, diese Stellen zu finden, besteht darin, einen Wert, der nach folgender Formel errechnet wird, solange zu einem Datenregister wortbreit zu addieren, bis ein Übertrag entsteht (Carry-Flag gesetzt):

x=(Differenzd. Y-Koordinaten/Differenz d. X-Koordinaten) x 65536

Bei jedem Übertrag erhöhen oder erniedrigen wir die Y-Koordinate. Diese Methode ist sehr schnell, da sie auf Festkommazahlen verzichtet. Beispiel einer Linie von (0, 0) nach (50,15). Nach obiger Formel beträgt x gerundet 19661. Das Zählerdatenregister muß zu Beginn 32768 enthalten. Nun wird der erste Punkt bei 0,0 gesetzt und 19661 zum Datenregister addiert; Ergebnis 52429. Nachdem der zweite Punkt gesetzt wurde, enthält das Daten register wegen des Übertrags 6554. Folglich erhöhen wir die Y-Koordinate des zu setzenden Punktes um eins. Dieses Verfahren gilt, solange die X-Zielkoordinate nicht erreicht ist.

Der größte Schwachpunkt der bisherigen Linienroutine ist, daß sie eine komplette Punktunterroutine enthält, obwohl die Punkte, die gesetzt werden, alle nebeneinander liegen. Bei der Optimierung von Assemblerroutinen kann man sich oft mit Tabellen weiterhelfen, die Programm-Code enthalten. Bei einer Linienroutine wäre etwa der Code für alle möglichen Linien angebracht, der nur aus OR- und RTS-Befehlen besteht und im besten Fall einen Punkt pro Taktzyklus setzt. Leider ist die Zahl aller möglichen Linien sehr groß und eine solche Code-Tabelle würde etliche Gigabyte Speicher schlucken.

Äußerst schnell und platzsparend hingegen ist folgende Code-Tabelle, auf die ich nach zahlreichen Optimierungen gestoßen bin.

; D7=128, DG„64, D5„32, D4„16, D3„8, D2„4, D1„1 
; D0=32768
; A0=Screenadresse, A1=Summand
; A2=160 oder -160
REPT 20	;	20	Mal	das	Ganze
OR.B D7, (A0) ; 16. Bit setzen / 8 Bytes pro Pixel
ADD.W A1,D0
BCC.S *+2
ADDA.W A2,A0
OR.B D6,(A0)	;	15. Bit setzen
ADD.W A1,D0 
BMI.S *+2 
ADDA.W A2,A0
OR.B D5,(A0)	;	14.	Bit	setzen
(...)
OR.B D4,(A0) ; 13. Bit setzen
(...)
OR.B D3,(A0) ; 12. Bit setzen
(...)
OR.B D2,(A0) ; 11. Bit setzen
(...)
BSET D1, (A0) ; 10. Bit setzen
(...)
OR.B D1,(A0)+ ; 9. Bit setzen
(...)
OR.B D7, (A0) ; 8. Bit setzen
(...)
OR.B D6,(A0) ; 7. Bit setzen
(...)
OR.B D5, (A0) ; 6. Bit setzen
(...)
OR.B D4,(A0) ; 5. Bit setzen
(...)
OR.B D3, (A0) ; 4. Bit setzen
(...)
OR.B D2,(A0) ; 3. Bit setzen
(...)
BSET D1, (A0) ; 2. Bit setzen
(...)
OR.B	D1, (A0) ; 1. Bit setzen
(...)
ADDQ.W A0 ; Nächstes Wort
ENDR
RTS

Wenn man diese Routine von Anfang an startet, zeichnet sie eine 320 Punkte lange H-Linie. Wenn man sie 8 Bytes später anspringt, ist die Linie 319 Punkte lang und so weiter.

Das einzige Problem ist jetzt, daß die Linien immer an einer Wortgrenze (durch 16 teilbare X-Koordinate)

aufhören müssen. Also benötigen wir 16 Versionen der obigen Routine im Speicher, wobei jede einen Pixel vorher aufhört als die vorige. Die Code-Tabelle für V-Linien ist glücklicherweise nicht so umfangreich:

; D0=32768, D1=Zweierpotenz des ersten zu setzenden Bits, D2=1
; A0=Screenadresse, A1=Summand, A2=160 oder -160 
REPT 200	; 200 Mal
OR.W D1,(A0) ; Bit setzen / 14 Bytes pro Pixel 
ADD.W A1,D0 
BCC.S *+6
ROR.W D2,D1	; Nächstes X
BCC.S *+2 
ADDQ.W A0
ADDA.W A2,A0	; Nächstes Y
ENDR
RTS

Diese Routine zeichnet eine 200 Pixel lange V-Linie. Je nach gewünschter Länge erfolgt der Einsprung früher oder später. Um die Linienroutine sinnvoll einzusetzen, reicht es nicht, nur Linien zeichnen zu können. Ebenso schnell müssen wir sie auch löschen. Hier gibt es verschiedene Möglichkeiten: In seltenen Fällen ist es erforderlich, daß nur die Punkte der Linie dem Reißwolf zum Opfer fallen, was auch sehr lange dauert. Schneller geht es, alle von der Linie betroffenen Wörter zu löschen. Bei sehr vielen Linien ist es sogar am besten, den ganzen Bildschirm zu löschen. Da das Zeichnen von Linien auch mit dem neuen Atari Falcon nicht hardwaremäßig vonstatten geht, muß man dort ebenfalls auf Optimierungstricks zurückgreifen. Der Linienalgorithmus, der in diesem Artikel vorgestellt wurde, müßte grundsätzlich auch auf dem Falcon laufen, da er auf selbstmodifizierenden Code verzichtet. Interessant dürfte es auch sein, eine Linienroutine für die True-Colour-Auflösungen des Falcon zu schreiben, da dort ein Pixel genau einem Speicherwort entspricht. (Felix Brandt - Delta Force/ah)