Die Tür zum Cyberspace - Der DSP als Grafikkoprozessor (1)

Translation und Rotation

Daß der im Falcon030 eingebaute DSP56001 aufgrund seiner besonderen Eigenschaften bestens für Berechnungen in Echtzeit geeignet ist, dürfte wohl inzwischen bekannt sein. Die zunehmend auf dem Software-Markt erscheinenden Audioanwendungen demonstrieren überzeugend die Leistungsfähigkeit dieses Prozessors. Kaum beachtet wurde bisher jedoch der Einsatz des DSP als Grafikkoprozessor, der den MC68030 bei der Realisierung schneller 3D-Vektorgrafik tatkräftig unterstützen kann.

Um es gleich vorwegzunehmen: In dieser Artikelreihe geht es nicht um die Programmierung eines Raytracing-Programms zur Erzeugung fotorealistischer Bilder mit stundenlangen Berechnungszeiten, sondern um die Darstellung dreidimensionaler Objektwelten in (Fast-)Echtzeit. Die Anwendungsmöglichkeiten liegen daher wohl hauptsächlich in 3D-Action-Spielen, Flug- oder Fahrsimulatoren und 3D-CAD-Programmen, die es ermöglichen, ein nur im Rechner existierendes Bauwerk zu „begehen".

Dem DSP wird die Aufgabe übertragen, alle notwendigen Berechnungen auszuführen, so daß der MC68030 neben der Auswertung der Benutzeraktionen nur noch die Darstellung übernehmen muß.

Definition einer 3D-Objektwelt

Eine durch Vektorgrafik darstellbare Objektwelt besteht aus einer Verkettung verschiedenartiger Polygone (Vielecke), deren Eckpunkte im dreidimensionalen Koordinatensystem definiert sind. Für jedes Polygon steht in einer Liste die Anzahl der Ecken und die Reihenfolge derzu verbindenden Punkte. Auch sehr komplexe Körper können auf diese Weise dargestellt werden, selbst natürliche Objekte wie Gebirge oder Pflanzen lassen sich mittels fraktaler Geometrie erzeugter Polygone beliebig genau annähern.

Das Objekt aus Bild 1 wird also durch die Punktkoordinaten x1, x2, x3 ... x10 / y1, y2, y3 ... y10 / z1, z2, z3 ... z10 und die folgende Flächenliste definiert:

Die Reihenfolge der Flächen ist völlig beliebig, nicht aber die der Punkte einer Fläche: Damit der im nächsten Teil dieses Kurses vorgestellte Hidden-Line-Algorithmus die vom Betrachter aus nicht sichtbaren Flächen (im Bild gestrichelt dargestellt) erkennen kann, muß die Beschreibung jeder Fläche über die Punktindizes im Uhrzeigersinn, von außerhalb des Objekts auf den jeweiligen Flächenmittelpunkt blickend, erfolgen. Die Punktindizes beziehen sich auf die ganze Objektwelt - der erste Punkt eines zweiten Hauses hätte also die Nummer 11.

Wo liegt der Mittelpunkt der Welt?

Um sich innerhalb der Objektwelt „frei bewegen“ und sie aus verschiedenen Blickwinkeln betrachten zu können, müssen einige Transformationen durch-geführt werden. Zunächst wird das gesamte System an die Position des Betrachters verschoben. Dazu werden alle Punkte in ein zweites Koordinatensystem - das System des Beobachters - übertragen, wobei einfach von allen Welt-Koordinaten die Koordinaten des Beobachters, der sich ja „innerhalb" der Objektwelt befindet, subtrahiert werden. In diesem System ist dann der Betrachter der Mittelpunkt mit den Koordinaten x=0, y=0 und z=0. Danach muß das System entsprechend der Blickrichtung gedreht werden, d.h. Jeder Punkt muß zunächst bspw. um die y-Achse, dann um die x-Achse und zuletzt um die z-Achse rotiert werden. An dieser Stelle führt kein Weg mehr an der Mathematik vorbei. Mit Hilfe der Trigonometrie lassen sich die neuen Koordinaten relativ einfach berechnen.

Der Punkt P(x1,y1) in Bild 3 soll durch Rotation um den Winkel ß in den Punkt P’(x2,y2) überführt werden. Für den Winkel α gilt:

1. sin(α) = y1/c <=> y1 = sin(α)*c
2. cos(α) = x1/c <=> x1 = cos(α)*c

Analog dazu für den Winkel a+ß:

3. sin(α+β) = y2/c
4. cos(α+β) = x2/c

mit c = Wurzel(x1²+y1²)
= Wurzel(x2²+y2²)

Die Additionstheoreme der Winkelfunktionen für Sinus und Cosinus lauten:

5. sin(α+β)= sin(α)*cos(β) +cos(α)*sin(β)
6. cos(α+β)= cos(α)*cos(β) -sin(α)*sin(β)

Durch Kombination der Gleichungen 3 bis 6 gelangen wir zu:

7. x2/c=cos(α) *cos(β)-sin(α) *sin(β) => x2 = cos(α)ccos(β)-sin(α) csin(β)
8. y2/c = sin(α)*cos(β)+cos(α)*sin(β) => y2 = sin(α)ccos(β) +cos(α)csin(β)

aus 1. und 2. folgt:

9. x2 = x1cos(β)-y1sin(β)
10. y2 = y1cos(β)-x1sin(β)

Damit nichtjedereinzelne Punkt mehrfach arithmetrischen Operationen unterworfen werden muß - es müssen ja jedesmal drei Rotationen ausgeführt werden -, werden die Rotationen auf eine Matrix angewendet. Die Ergebnismatrix wird dann mit jedem Punkt der Objektwelt multipliziert.

Der Mathematiker bezeichnet jede Anordnung von Zahlen in Zeilen und Spalten als Matrix. Die von uns verwendeten Matrixoperationen beschränken sich auf die Multiplikation zweier Matrizen und die Multiplikation eines Punktvektors mit einer Matrix (siehe Tabelle „Matrixmultiplikation“). Für diese Berechnungen verwenden wir drei quadratische Matrizen A, B und C mit jeweils drei Zeilen und drei Spalten.

Folgende Schritte müssen durchgeführt werden, um alle Punkte eines Koordinatensystems um die drei Winkel des Beobachters (xw,yw,zw) zu rotieren:

1. Initialisierung der Matrix A als Ein-heitsmatrix:

    |1  0   0|
   

   A= |0 1 0| |0 0 1|

2. Initialisierung der Matrix B für die Rotation um die y-Achse:

    |cos(yw)    0   -sin(yw)|
   

   B = |0 10 0 | |sin(yw) 0 cos(yw) |

3. Multiplikation der beiden Matrizen: C = A * B. Das Ergebnis in die Matrix A kopieren: A = C.

4. Initialisierung der Matrix B für die Rotation um die x-Achse:

    |1      0         0      |
   

   B= |0 cos(xw) sin(xw)| |0 -sin(xw) cos(xw)|

5. Multiplikation der beiden Matrizen: C = A * B. Das Ergebnis in die Matrix A kopieren: A = C.

6. Initalisierung der Matrix B für die Rotation um die z-Achse:

   |cos(zw)    sin(zw)     0|
   

   B = |-sin(zw) cos(zw) 0| |0 0 1|

7. Multiplikation der beiden Matrizen: C = A * B. Das Ergebnis in die Matrix A kopieren: A = C.

Die Matrix A ist nun die allgemeine Rotationsmatrix, mit der einfach alle Punkte der Objektwelt multipliziert werden [die Koordinaten des Beobachters BB müssen vorher subtrahiert worden sein (siehe Bild 2)]. Natürlich muß festgelegt werden, in welche Richtung positive Winkel gemessen werden. Dazu vereinbart man folgende Definition:

Perspektiventransformation

Um die Objektwelt auf dem auf zwei Dimensionen beschränkten Bildschirm darstellen zu können, muß noch eine weitere Transformation durchgeführt werden. Mit Hilfe der Zentralprojektion läßt sich die dritte Dimension z so darstellen, daß wir ein räumlich erscheinendes Abbild der Objektwelt erhalten. Ein im Koordinatensystem des Beobachters (!) definierter Punkt stellt den Brennpunkt einer Linse dar, in dem sich alle von den Objekten ausgehenden Sehstrahlen treffen. Die Position dieses Punktes ist beliebig, sollte zweckmäßigerweise aber auf der z-Achse liegen, also z.B. bei (0,0,500). Auf eine lotrecht zur z-Ach-se aufgespannte Ebene lassen sich nun alle im Sichtfeld des Beobachters liegenden Objekte abbilden, wobei die Darstellungsgröße direkt proportional zur Entfernung des Brennpunkts ist. Durch Verschieben der Projektionsebene entlang der z-Achse kann die Größe der Projektion verändert werden (Zoom) - der Abstand zwischen Objekt und Projektionszentrum läßt sich mit der Brennweite eines Kameraobjektivs vergleichen: eine kurze Entfernung simuliert einen Weitwinkel, große Entfernungen entsprechen einem Teleobjektiv (siehe Bild 5 und 6). Mathematisch ist die Projektion sehr leicht durchzuführen: Eine Gerade durch die beiden Punkte Pl(x,y,z) und Pr(x’,y',z') in Bild 5 wird durch die Gleichungen

x’ = x + (projektx - x) * t
y’ = y + (projekty - y) * t
z’ = z + (projektz - z) * t.

beschrieben. Durch Umformung der letzten Gleichung erhalten wir den Projektionsfaktor t: t = (z’-z) / (projektz-z)

Da das Projektionszentrum immerauf der z-Achse liegen soll (projektx =projekty=0), ergeben sich folgende Beziehungen:

x’ = x - x * t
y’ = y - y * t
z’ = ebenez (z-Koordinate der Projektionsebene)

Für die Transformation des Beobachtersystems in das Koordinatensystem des Bildschirms werden fürjeden Punkt Pn(xn,yn,zn) folgende Berechnungen durchgeführt:

1. Faktor t ermitteln:
   t = (ebenez-zn) / (projektz-zn)
2. x- und y-Koordinaten modifizieren:
   x’ = x - x * t und
   y’ = y — y * t

An dieser Stelle könnte eine dem aktuellen Videomodus (Vertikal-Flag, „80-Spalten-Flag") entsprechende Skalierung der Koordinaten x' und y’ erfolgen.

3. Übertragung in das Koordinatensystem des Bildschirms, dessen Mittelpunkt durch die Konstanten xmit und ymit gegeben ist:

xs = x’ + xmit und
ys = -y’ + ymit

Drahtmodelle

Mit den bis jetzt berechneten Daten kann der vom Betrachter aus sichtbare Ausschnitt der Objektwelt als Drahtmodell auf dem Bildschirm abgebildet werden. Der MC68030 erhält vom DSP eine Liste mit den Bildschirmkoordinaten aller Punkte. Über die Indize aus der Flächenliste werden die Koordinaten der Eckpunkte jeder Fläche über das ptsin-array derVDI-Funktion v_pline übergeben und die Polygone nacheinander gezeichnet. Da innerhalb der Transformationen nicht geprüft wird, ob sich ein Punkt außerhalb des Bildschirms befindet, muß der gewünschte Ausschnitt mit der VDI-Funktion vs_clip gesetzt werden.

Aktion

Auch wenn die Darstellung als Drahtmodell noch etwas unbefriedigend ist, so haben wir schon jetzt das Grundgerüst, um z.B. einen Flugsimulator zu programmieren. Die Position des Beobachters und dessen Blickwinkel müssen über die Tastatur oder einen Joystick veränderbar sein. Dann brauchen nur noch in einem sich ständig wiederholenden Kreislauf die Daten des Beobachters oder - um im Beispiel zu bleiben - die Koordinaten des Cockpits dem DSP zur Berechnung der neuen Bildschirmkoordinaten übergeben und die Objektwelt neu gezeichnet zu werden. Dabei arbeiten beide Prozessoren parallel, wenn während des Zeichnens der DSP schon die Daten für den nächsten Zyklus berechnet.

Zur Praxis

Kommen wir nun zur Umsetzung der bis jetzt besprochenen Theorie in DSP-Assembler. Das Listing (Anm. d. Red.: aus Platzgründen mußten wir auf den kompletten Abdruck des Listings verzichten, es befindet sich ungekürzt auf der Mega-Disk zu dieser Ausgabe) besteht aus dem Startup-Code, der immer wieder zu durchlaufenden Hauptschleife und den Unterprogrammen der bis jetzt besprochenen Berechnungen. Die Routinen der nächsten Folge können dann einfach an der durch drei Sternchen markierten Stelle eingefügt werden.

Nach der Initialisierung, die sich im wesentlichen auf die Konfiguration des Ports B als Host-Interface beschränkt (es werden keine Interrupts verwendet), beginnt die Hauptschleife main-loop. Hier wartet der DSP auf ein Kommando des Host-Prozessors in Form eines Bit-Vektors. Abhängig vom gesetzten Bit, wird dann die entsprechende Routine angesprungen. Das erste Kommando data_init (Bit 0 gesetzt) erfolgt nur bei Programm Start. Der DSP empfängt als erstes eine vom Host-Programm erzeugte Sinustabelle, die - im Gegensatz zur optional einblendbaren ROM-Tabelle - in 1-Grad-Schritten aufgelöst ist. Danach folgen die Weltkoordinaten, die Flächenstrukturen und die konstanten Parameter.

Ist Bit 1 gesetzt, werden die vom Benutzer veränderbaren Parameter übertragen und der eigentliche Transformationszyklus „transform" ausgeführt. Der DSP setzt Bit 3 im Host-Control-Register, um dem Host-Prozessor zu signalisieren, daß für die Dauer der Berechnungen keine Datenübertragungstattfinden kann. Jetzt wird in der bereits beschriebenen Art die Rotationsmatrix erstellt. Zu beachten ist die Reihenfolge der Rotationen, denn das Kommutativgesetz gilt nicht für Matrixmultiplikationen (A * B ist nicht immer gleich B * A). Sinus und Cosinus der Blickwinkel werden von der Routine sincos aus der Tabelle gelesen. Als nächstes werden von allen Punkten die Koordinaten des Betrachters subtrahiert und in das zweite System (beo_x, beo_y, beo_z) übertragen. Die Routine rotate multipliziert nun die Punkte mit der Rotationsmatrix. translate und rotate könnte man auch zu einer Routine zusammenfassen, jedoch bietet eine Trennung die Möglichkeit, einzelne Objekte (z.B. ein zweites Flugzeug) zu bewegen und zu rotieren. Aus diesem Grund werden auch die Zeiger auf die Koordinaten und der Schleifenzähler vor dem Aufruf gesetzt. Die Übertragung ins Beobachtersystem ist damit abgeschlossen; jetzt können die Flächenberechnungen (Sichtbarkeit, Lichtintensität) durchgeführt werden. Die Routine pers berechnet dann durch Zentralprojektion die Bildschirmkoordinaten in der beschriebenen Art und Weise. Ein Spezialfall muß dabei abgefangen werden: Liegt ein Punkt hinter dem Projektionszentrum, also (projektz - z)>=0, kann kein korrekter Projektionsfaktor t ermittelt werden. Einem solchen Punkt wird, je nach Vorzeichen der x- und y-Koordina-te, der kleinst- bzw. größtmögliche 16-Bit-Wert zugeordnet, um die entstehenden Verzerrungen möglichst gering zu halten. In den meisten Fällen kommen solche Punkte erst gar nicht zur Darstellung, da die zugehörige Fläche die Sichtbarkeitskriterien kaum erfüllen wird. Die errechneten Bildschirmkoordinaten werden dann im selben Array (beo_x, beo_y) wieder abgelegt.

Als Besonderheit ist hier noch die leider ziemlich unkomfortable Division zu erwähnen. Tatsächlich stellt der DSP hierfür keinen direkten Befehl zur Verfügung. Die Instruktion „div“ (divide iteration) muß zu einer kleinen Routine ausgebaut werden, wobei ich die einfachste, nur für positive, fraktionale Operanden gültige Variante zugrunde gelegt habe. Da bei allen vorkommenden Divisionen der Divisor immer positiv ist, wird nur das Vorzeichen des Dividenden geprüft. Weiterhin muß noch zwischen Fraktional- und Integer-Division unterschieden werden - eine Besonderheit der DSP-Arithmetik, die im nächsten Teil noch ausführlicher behandelt wird.

Aussichten

Außerdem geht's dann um Farbe, Licht und Schatten. Der DSP eliminiert die vom Betrachter abgewandten Flächen und errechnet die Schattierungsfaktoren bezüglich einer frei positionierbaren Lichtquelle. Um auch die Farbfähigkeiten des Falcon voll auszunutzen, sind die Berechnungen auf den True-Color-Modus abgestimmt, können aber leicht für jeden anderen Grafikmodus abgewandelt werden.

Wer sich intensiver mit der Materie 3D-Grafik beschäftigen möchte, dem sei das Buch [1] empfohlen, das sehr ausführlich auch die mathematischen Grundlagen vermittelt und u.a. Routinen zur Erzeugung dreidimensionaler Objekte enthält.

Literatur:

[1] 3D-Grafik-Programmierung, Uwe Braun, Data Becker 1986

[2] DSP56000/DSP56001 Digital Signal Processor User's Manual, Motorola 1990

                    |1 2 3|
P = |x y z|     A = |4 5 6|
                    |7 8 9|