Schneller Line-Algorithmus
Verfasst: 27.12.2020, 23:05
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.
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.