Schneller Line-Algorithmus

Software-Entwicklung, Compiler, Interpreter, ...
Antworten
Benutzeravatar
bbock
Beiträge: 242
Registriert: 08.02.2015, 15:31

Schneller Line-Algorithmus

Beitrag von bbock »

Die in diesem Forum bereits vorgestellten Grafikroutinen für die Joyce bestehen aus einem Maschinencode-Kern (KERNEL.INC) und darauf aufbauenden Pascal-Prozeduren und -Funktionen. Der Maschinencode-Kern stellt nur eine Prozedur zum Zeichnen eines einzelnen Bildpunkts zur Verfügung (und darüber hinaus Prozeduren zum Auslesen und Schreiben des Bildschirmspeichers).

Insbesondere das Zeichnen von Linien wird häufig in Grafikprogrammen verwendet. Möchte man die Performance von Grafikprogrammen erhöhen, dann liegt es nahe, einen schnelleren Line-Algorithmus zu entwerfen. Mein erster Ansatz war, die Pascal-Routine Line aus GRAPHLIB.INC in Assembler neu zu schreiben. Beim letzten Klubtreffen habe ich einen Bresenham Line Algorithmus in Z80 Assembler bekommen, so dass ich ihn nicht komplett selbst implementieren musste. Allerdings waren noch einige Anpassungen nötig, um den Code auf der Joyce zum Laufen zu bringen.

Die ganze Angelegenheit stellte sich als deutlich schwieriger heraus, als ich ursprünglich angenommen hatte. Das liegt an der besonderen Art der Grafikspeicher-Verwaltung (Stichwort: Roller RAM) und am für den Zugriff auf den Grafikspeicher erforderlichen Bank Switching.

Meine erste funktionierende Lösung eines Line-Algorithmus in Maschinencode war zunächst eine Enttäuschung: gegenüber der Pascal-Prozedur war die Maschinencode-Variante nur ca. 10% schneller. Das kam mir viel zu langsam vor! Also untersuchte ich den Algorithmus näher (hier war der Debugger des Emulators CP/M Box wirklich hilfreich) und hatte sogleich einen Verdacht: Der Line-Algorithmus ruft für jedes zu setzende Pixel die Einzelpunkt-Plot-Routine (PltPix bzw. GX_Dot) auf, und diese beginnt mit einem XBIOS-Call für's Screen Bank Switching. D.h. ein XBIOS-Call für jedes Pixel! Ich dachte mir, es müsste doch reichen, das Bank Switching nur einmalig zu Beginn des Line-Algorithmus auszuführen und dann die Plot-Routine so aufzurufen, dass der vorangestellte XBIOS-Call umgangen wird. Dann hätten wir ein Bank Switching pro Line, nicht eins pro Pixel. Das sollte einen deutlichen Speedup bringen, vor allem bei längeren Linien.

Als kleiner Vorgeschmack folgen zwei Testprogramme: eines mit der alten Pascal-Line-Variante (TESTLIN2.PAS) und dann dasselbe nochmal mit der neuen Maschinencode-Variante (TESTLINE.PAS). Soviel sei verraten: Die MC-Variante ist mehr als 3,5 mal so schnell.
testline.zip
TESTLINE und TESTLIN2
(17.14 KiB) 583-mal heruntergeladen
Benutzeravatar
bbock
Beiträge: 242
Registriert: 08.02.2015, 15:31

Schneller Line-Algorithmus

Beitrag von bbock »

Für die Entwicklung verwendete ich folgende Tools:
  • CP/M Box: Joyce-Emulator mit Debugger
  • ZX-IDE: ein Cross Assembler auf Basis von Flat Assembler, eigentlich für den Sinclair ZX81 gedacht: https://forum.tlienhard.com/phpBB3/view ... ?f=2&t=632
  • listz80: gehört zum ZX-IDE-Paket; erzeugt Listings mit Adressen, Hex-Codes und Assembler Source
  • dZ80: Disassembler
  • ein selbst entwickeltes Java-Programm zum Umwandeln der von der ZX-IDE erzeugten BIN-Dateien in Hex Codes für Pascal
Benutzeravatar
bbock
Beiträge: 242
Registriert: 08.02.2015, 15:31

Schneller Line-Algorithmus

Beitrag von bbock »

Hier sind schon mal die Dateien für alle, die selbst mit Joyce-Grafik unter Turbo Pascal experimentieren möchten. Das erste Paket enthält den Line- und den Dot-Algorithmus, aber keine Routinen für den Bildschirmzugriff (MC-Startadresse $F400):
Line_Only.zip
Nur der schnelle Line- und der Dot-Algorithmus
(3.88 KiB) 564-mal heruntergeladen
Das zweite Paket dient dem Ersatz von KERNEL.INC durch KERNEL2.INC. Der Maschinencode-Teil ist durch die zusätzliche Line-Routine zu lang um es ab $F400 unterbringen zu können, daher beginnt der MC ab $F200:
Full_Kernel.zip
Vollständiger Ersatz für KERNEL.INC mit dem schnellen Line-Algorithmus
(4.75 KiB) 556-mal heruntergeladen
Fortsetzung folgt...
Antworten