Die Tür zum Cyberspace: Der DSP als Grafikkoprozessor, Teil 2 - Farbe, Licht und Schatten

Nachdem in der ersten Folge die für die Darstellung einer 3D-Objektwelt als Drahtmodell notwendigen Transformationen besprochen wurden, kommt nun Farbe ins Spiel. Die hier vorgestellten Algorithmen zur Berechnung der vom Betrachter aus sichtbaren Flächen und deren Helligkeitsintensitäten bezüglich einer frei positionierbaren Lichtquelle ermöglichen bereits eine für Echtzeitanwendungen beachtliche realistische Darstellung.

Bis heute gibt es keinen Rechner, der auf dem Raytracing-Prinzip beruhende Berechnungen in Echtzeit durchführen kann - daher kommen auch für den DSP des Falcon nur auf Flächen anzuwendende Algorithmen in Frage. Bild 1 illustriert die Zwischenergebnisse der drei hier vorgestellten Berechnungen am Beispiel des beliebten ATARI Logos - dem Default-Objekt des Beispiel-Programms.

Der erste Schritt zur Erzeugung einer räumlich wirkenden Darstellung besteht in der Entfernung der Linien, die vom Betrachter aus nicht sichtbar sind (es sei denn, es handelt sich um einen Glaskörper).

Hidden Lines

Der hier verwendete Hidden-Line-Algorithmus arbeitet sehr schnell, liefert aber nur unter bestimmten Bedingungen korrekte Ergebnisse:

  1. Die Eckpunkte einer Fläche müssen, von außerhalb des Objekts betrachtet, diese im Uhrzeigersinn umschreiben.
  2. Die Flächen müssen konvex sein (Anm.: Die Form eines „C" ist konkav, die eines „O" konvex).

Diese Bedingungen sind bei der Konstruktion einer Objektwelt unbedingt zu erfüllen (konkave Flächen können immer aus zwei oder mehr konvexen Flächen zusammengesetzt werden). An dem im Bild 2 dargestellten Würfel läßt sich das Hidden-Line-Prinzip leicht verdeutlichen. Betrachten Sie Vorder- (A) und Rückfläche (B) des Objekts und vergleichen Sie deren Punktnummern mit den Reihenfolgen in der folgenden Flächenstruktur:

Fläche A: 1,2,3,4,1 
Fläche B: 5,6,7,8,5

Aus Ihrer Sicht wird Fläche A im Uhrzeigersinn, Fläche B aber gegen den Uhrzeigersinn umschrieben. Wenn Sie nun den Würfel in Gedanken drehen, ist es genau umgekehrt. Die Aufgabe besteht also darin, alle Flächen zu eliminieren, deren Punktindizes bezüglich des Betrachters gegen den Uhrzeigersinn verlaufen.

Mit etwas Vektor-Algebra lassen sich die Richtungen der Verbindungslinien einer Fläche eindeutig bestimmen. Vom ersten Punkt der Fläche bildet man einen Vektor P zum zweiten Punkt und einen Vektor Q zum dritten Punkt der Fläche. Das Vektorprodukt (oder Kreuzprodukt) dieser beiden Vektoren liefert den auf der Fläche senkrecht stehenden s.g. Normalvektor R. Diesen Vektor vergleichen wir mit einem weiteren Vektor S, der vom ersten Punkt der Fläche zum Projektionszentrum zeigt. Zeigen beide Vektoren in die gleiche Richtung (± 90°), ist die Fläche nicht sichtbar (siehe Bild 2 und 3). Für die Berechnungen werden die Koordinaten des Beobachtersystems benutzt - die Flächenalgorithmen werden also nach Translation und Rotation und vor der Zentralprojektion ausgeführt.

Ein Vektor ist nichts anderes als eine richtungsweisende Verbindung zwischen zwei Punkten im Raum oder in der Ebene. Die Komponenten ergeben sich aus der Subtraktion des Startpunkts vom Zielpunkt.

Bilden wir also die oben genannten Vektoren:

P(px,py,pz)     = (x2-x1,y2-y1,z2-z1) 
Q(qx,qy,qz)     = (x3-x1,y3-y1,z3-z1) 
S(sx,sy,sz)     = (projektx-x1,projekty-y1, projektz-z1)
                = (-x1,-y1, projektz-z1)

Zur Erinnerung: Das Projektionszentrum liegt auf der z-Achse, daraus folgt: projektx - projekty = 0.
Den auf P und Q senkrecht stehenden Vektor R erhalten wir über das Kreuzprodukt:

R(rx,ry,rz) = P x Q
            = (py*qz-pz*qy, pz*qx-
              px*qz,px*qy-py*qx)

Um die Richtungen von Rund S vergleichen zu können, bilden wir das Skalarprodukt der beiden Vektoren:

c = R * S = |R| * |S| * cos(α)
  = rx*sx + ry*sy + rz*sz

c ist eine reelle Zahl und a der von beiden Vektoren eingeschlossene Winkel. Wenn α zwischen 90° und 270° liegt, zeigen beide Vektoren in verschiedene Richtungen und das Sichtbarkeitskriterium ist erfüllt. Der Cosinus dieser Winkel ist kleiner Null, daher reicht es, das Vorzeichen des Skalarprodukts zu prüfen: Ist c < 0, ist die Fläche sichtbar.

Fehlerfrei können mit dieser Methode allein jedoch nur einzelne, konvexe Körper dargestellt werden, da Flächen, die zwar vom Beobachterstandpunkt aus sichtbar, jedoch von anderen Flächen verdeckt sind, nicht erkannt werden können (vgl. Bild 1). An dieser Stelle wird es notwendig, das Problem der verdeckten Linien bzw. Flächen von einer ganz anderen Seite anzugehen:

Bild 1: Vom Drahtmodell zur plastischen Darstellung
Bild 2: Die Vorderseiten eines Objekts lassen sich von den nicht sichtbaren Rückseiten durch Richtungsvergleich der Vektoren R und 5 unterscheiden.
Bild 4: Auf die senkrecht zu den Lichtstrahlen liegende Fläche fallen mehr Lichtstrahlen.
Bild 3: Richtungsvergleich zweier Vektoren über den Cosinus des eingeschlossenen Winkels

Der Painter-Algorithmus

Das Prinzip ist denkbar einfach: Analog zur Entstehung eines Ölgemäldes, bei dem zuerst der Hintergrund und danach die weiter vorn liegenden Objekte gemalt werden, muß dafür gesorgt werden, daß die Flächen in der Reihenfolge ihres Abstandes zum Projektionszentrum gezeichnet werden. Dadurch werden die von der Hidden-Line-Routine nicht eliminierten (Teil-) Flächen überdeckt.

Da die z-Achse des Beobachtersystems direkt auf den Betrachter zeigt, liegen die Flächen mit den kleinsten z-Koordinaten am weitesten hinten; müssen also zuerst gezeichnet werden. Wir bilden das arithmetische Mittel aus den z-Koordinaten der Eckpunkte und erhalten so die mittlere z-Koordinate jeder Fläche, die zusammen mit der Flächennummer in der Ausgabeliste gespeichert wird. Diese Liste wird dann entsprechend sortiert und der Zeichenroutine des Host-Programms übergeben.

Der Schwachpunkt des Painter-Prinzips liegt in der Berechnung des z-Mittelwerts, der ja genaugenommen nur für den Flächenmittelpunkt gültig ist. Je größer eine Fläche ist, desto größer ist die Gefahr, daß Darstellungsfehler auftreten. Aus diesem Grund bestehen Objekte, die nicht für Echtzeitanwendungen gedacht sind, meist aus sehr vielen kleinen Facetten (z.B. CAD-3D2-Objekte). Bei der Objektkonstruktion sollten darum sehr große Flächen - bspw. die Seitenwände eines langen Flures - in mehrere kleinere unterteilt werden.

Der Painter-Algorithmus allein könnte schon das gewünschte Ergebnis liefern; die Kombination mit dem zuvor beschriebenen Hidden-Line-Algorithmus erzeugt aber nicht zuletzt durch einen enormen Geschwindigkeitsvorteil bessere Resultate. Die Ausgabe auf dem Bildschirm ist in puncto Geschwindigkeit das schwächste Glied in der Kette, daher liegt das Bestreben darin, schon im Vorfeld möglichst viele Flächen zu eliminieren. Bei der Berechnung der mittleren z-Koordinaten werden daher auch gleich die hinter dem Beobachter liegenden Flächen (zmittel > 0) aussortiert.

Da wir gerade beim Aussortieren sind: Für bestimmte Anwendungen, z.B. Fahr- oder Flugsimulatoren, die mit komplexen, aus vielen Objekten bestehenden Welten arbeiten, bietet es sich an, eine Objektliste zu verwalten. Dann kann eine allen Berechnungen vorgelagerte Routine schon ganze Objekte aussortieren, wenn diese nicht im Sichtfeld des Betrachters liegen.

Beleuchtung

Eine plastisch wirkende Darstellung braucht das Zusammenspiel zwischen Licht und Schatten. Da aus Geschwindigkeitsgründen auch hier keine Strahlverfolgung jedes Bildpunktes in Frage kommt, beschränken wir uns wieder auf einen Flächenalgorithmus. Eine weitere Vereinfachung besteht in der Definition nur einer Lichtquelle, obwohl das hiervorgestellte Prinzip leicht auf mehrere, auch farbige Lichtquellen erweitert werden kann. Auch könnte man jeder Fläche einen Reflektionskoeffizienten zuordnen, um verschiedene Materialeigenschaften zu simulieren.

Zur Verdeutlichung des Prinzips reicht aber die einfachste Variante - die Definition einer Punktlichtquelle im Raum, die in alle Richtungen ein weißes Licht mit konstanter Intensität verstrahlt. Die Position speichern wir im ersten Array-Element des Weltkoordinatensystems. Die Lichtkoordinaten werden also den gleichen Transformationen unterworfen wie alle anderen Objektpunkte und können mit jedem Zyklus geändert werden. In einem Action-Spiel könnte man z.B. leicht einen Sonnenumlauf programmieren. Der Spieler müßte dann seine Aufgabe bis „Sonnenuntergang“ erledigt haben ...

Um die Heliigkeitsintensität einer Fläche zu berechnen, prüfen wir ihre Orientierung zur Lichtquelle. Auf eine senkrecht zur Lichtquelle stehende Fläche fallen mehr Lichtstrahlen, als auf eine mehr oder weniger schräg stehende Fläche (siehe Bild 4).

Ein Maß für die Helligkeit erhalten wir also durch Bestimmung des genauen Winkels. Die notwendigen Rechenschritte gleichen den Vektoroperationen des Flidden-Line-Algorithmus: Bildung des auf der Fläche senkrecht stehenden Normalvektors R über das Kreuzprodukt aus P und Q. Anstelle des Vektors S zum Projektionszentrum bilden wir den Vektor L vom 1. Punkt der Fläche zur Lichtquelle (x0,y0,z0):

L(lx,ly,lz) = (x0-x1,y0-y1,z0-z1)

Den von beiden Vektoren eingeschlossenen Winkel α bzw. dessen Cosinus erhalten wir wieder über das Skalarprodukt c:

c = L * R = |L| * |R| * cos(α) 
  = lx*rx + ly*ry + lz*rz

Hier reicht es nicht, allein das Vorzeichen von c zu prüfen. Dieses gibt lediglich Aufschluß darüber, ob eine Fläche angestrahlt wird oder der Lichtquelle abgewandt ist. Ist c < 0, wird die Fläche angestrahlt, und wir müssen den Cosinus von α berechnen, um ein Maß für die Helligkeitsintensität Vzu erhalten (siehe Bild 5).

Wie aus dem mittleren Teil der letzten Gleichung zu ersehen ist, ist c gleich dem Cosinus, wenn die Beträge von L und R (|L|,|R|) gleich 1 sind. Der Betrag eines Vektors gibt die Länge des Vektors an - wir müssen also L und R auf die Länge 1 skalieren.

Den sogennanten Einheitsvektor erhalten wir, wenn wir die Komponenten eines Vektors durch dessen Betrag dividieren. Errechnen wir zunächst die Beträge von L und R:

|L| = SQR[lx2+ly2+lz2) und |R| = SQR(rx2+ry2+rz2)

Die Einheitsvektoren Le und Re bestimmen:

lex = lx/|L|; ley = ly/|L|; lez = lz/|L| und rex = rx/|R|; rey = ry/|R|; rez = rz/|R|

Bild 5: Der Cosinus von alpha liefert ein Maß für die Lichtintensität einer Fläche.

Bilden wir jetzt wieder das Skalarprodukt, reduziert sich die Gleichung auf:

c = cos(α) = lexrex + leyrey + lez*rez

Nehmen wir c absolut, erhalten wir eine reelle Zahl im Bereich von 0 bis 1 als Maß für die Helligkeit Vder Fläche. Dieser Wert wird noch durch einen variablen Lichtfaktor zur Kontrastregelung modifiziert.

Das weitere Vorgehen hängt vom eingestellten Grafikmodus und dem verwendeten Farbmodell ab. Für monochrome Darstellung erhält man die ATARI-Grauwert-Füllmuster 0 (weiß) bis 8 (schwarz) durch die Formel fillstyle = (int)(8 - 8*V). Arbeitet man mit 256 Farben, könnte man eine eigene Farbpalette mit z.B. 16 Farbtönen in jeweils 16 Helligkeiten installieren und V auf 16 Abstufungen reduzieren. Für mich lag es nahe, den True-Color-Modus des Falcon zu nutzen, da es hier keine Einschränkung durch eine begrenzte Farbpalette und die damit verbundenen Farbreduktionen gibt.

HSV - Ein alternatives Farbmodell

Um völlig unabhängig von der Grafik-Hardware zu sein, kann man sich vom RGB-Farbmodell lösen und die Berechnungen (wie auch die Farbgebung bei der Objekterstellung) im sogenannten HSV-Farbmodell durchführen. Das HSV-Modell bietet zunächst den Vorteil, die Farbgebung intuitiv gestalten zu können. Wer kann sich schon die RGB-Komponenten eines „milchigen orange“ vorstellen?

So wie vielleicht ein Maler seine Farben mischt, wird im HSV-Modell aus einem Farbenkreis zuerst die reine Farbe gewählt, deren Helligkeit und Reinheit durch Hinzumischen von Schwarz- und Weißanteilen verändert werden kann. Für diese Art der Farbwahl gibt es drei Parameter: Hue (H) gibt die Farbe als Winkel auf dem Farbenkreis zwischen 0° und 360° an, die Sättigung (S) und die Helligkeit (V) liegen im Bereich von 0 bis 1, wobei S=1 die maximale Sättigung (Reinheit) und V=1 die maximale Helligkeit darstellt (siehe Bild 6). Der Parameter V ist also unabhängig vom Farbton und korrespondiert direkt mit dem Ergebnis unserer Lichtberechnung. Um die Farbe auf dem Monitor darstellen zu können, muß natürlich eine Konvertierung ins RGB-Modell erfolgen. Obwohl die Umrechnung einfach und mit dem DSP schnell zu realisieren ist, habe ich mich in letzter Minute dazu entschlossen, die Farben direkt im RGB-Modell zu berechnen, da der benötigte Quellcode für die Konvertierung unverhältnismäßig lang ausfiel. Eine Übersicht über die gängigen Farbmodelle und Routinen zur Konvertierung finden Sie in [3],

Zur Praxis

Das Format der Flächenstruktur wird für jede Fläche um einen Farbwert und 4 Codebits, mit denen man ohne Aufwand einfache Attribute (z.B. Eigenleuchten) realisieren kann, erweitert:

[Farbe],[Code|Eckenanz.], [Index 1], [Index 2], ....[Index n],[Index 1]

Um DSP-Speicher zu sparen, werden die ersten beiden Elemente bei der Dateninitialisierung in einem DSP-Word zusammengefaßt. Der Farbwert (Falcon-True-Color) befindet sich dann in den oberen 16 Bits, die Bits 4-7 können einen Code enthalten und die unteren vier Bits geben die Eckenanzahl an (max. 15).

Die drei Aufgaben - Ermitteln der sichtbaren Flächen, Berechnung der Lichtintensitäten und Sortieren der Flächen nach absteigender z-Koordinate - werden alle vom Unterprogramm hiddenline ausgeführt, das nach der Transformation der Weltkoordinaten ins Beobachtersystem aufgerufen wird. Neben den Zeigern auf die Koordinaten-Arrays wird ein Zeiger auf die Flächenstruktur wflach und ein Zeiger auf die Flächenausgabeliste fla_list gesetzt. Der erste Eintrag der Ausgabeliste bleibt zunächst frei, hier wird am Ende die Anzahl der zu zeichnenden Flächen eingetragen. Jede sichtbare Fläche belegt drei Einträge: z-Koordinate, errechneter Farbwert und Flächennummer.

Bild 6: RGB-Einheitswürfel und HSV-Farbmodell

Nach der Zeiger- und Variableninitialisierung wird für jede Fläche die Arbeitsschleife hideloop einmal durchlaufen. Zunächst werden die Vektoren P und Q gebildet. Der Zugriff auf die Koordinaten erfolgt über die Punktindizes aus der Flächenstruktur. Die Indizes der ersten drei Punkte werden in den Offset-Registern N1, N2 und N3 gespeichert und für den Zugriff in das dem jeweiligen Adreßregister (R5, R6, R7) zugehörige Offset-Register (N5, N6,N7) übertragen („move Y:(R5+N1)...“ geht nicht!). Da nicht alle Ergebnisse in Registern gehalten werden können, dienen die Variablen X:var_1 bis X:var_6 als Zwischenspeicher. Als nächstes wird das Kreuzprodukt aus P und Q berechnet, um den Normalvektor Rzu erhalten. Das geht besonders komfortabel durch den „mac"-Befehl, der das Multiplikationsergebnis direkt zum/vom Inhalt des Akkus addiert/subtrahiert. Wichtig zu wissen ist, daß der DSP grundsätzlich im fraktionalen Zahlenformat (-1...0.999999) rechnet, $400000 also nicht 4194304, sondern 0.5 bedeutet. Trotzdem kann man ein Multiplikationsergebnis als Integerwert interpretieren, wenn man auch die Bits des unteren Akku-Halbregisters (A0 bzw. B0) betrachtet und den Wert halbiert. Das funktioniert natürlich nur, wenn man nicht die Multiplikationsbefehle mit automatischer Rundung (mpyr und macr) benutzt (siehe Tabelle „DSP-Integer-Arithmetik“)! Da uns nur die Richtung von R interessiert und das Ergebnis nicht mehr als 24 Bit beansprucht, speichern wir einfach A0 bzw. B0 als Richtungskomponenten ab. Jetzt wird der Vektor S zum Projektionszentrum gebildet. Der folgende bedingte Sprung wertet ein Codebit aus, das eine Fläche an der Sichtbarkeitsberechnung vorbeischleust. Solch eine Fläche wird auch dann gezeichnet, wenn die Punktindizes nicht im Uhrzeigersinn stehen. Sie ist also von beiden Seiten sichtbar. Sinnvoll ist das z.B. bei freistehenden, nicht an die Hülle eines Körpers gebundenen Flächen.

Für den Richtungsvergleich wird nun das Skalarprodukt S * R errechnet. Nur wenn das Ergebnis negativ ist, ist die Fläche sichtbar, und es wird mit der Lichtberechnung fortgefahren.

Hier wird zunächst ein weiteres Codebit geprüft. Ist es gesetzt, behält die Fläche ihren ursprünglichen Farbwert. Auf diese Art können, je nach Farbgebung, lichtabsorbierende oder leuchtende Flächen dargestellt werden.

Da wir den Normalvektor R bereits berechnet haben, wird direkt der Vektor L zur Lichtquelle und das Skalarprodukt L * R gebildet. Ist es positiv, liegt die Fläche im Dunkeln, ansonsten muß der genaue Helligkeitsfaktor berechnet werden.

Die Routine vector_1 berechnet auf die oben beschriebene Art aus den in den Registern X1, Y0 und Y1 übergebenen Vektorkomponenten den Einheitsvektor. Um die auf 24-Bit-Werte begrenzte Wurzelfunktion „sqrt“ des ATARI-Falcon-Toolkits benutzen zu können, muß der Vektor verkürzt werden, da die Summe der Quadrate der Komponenten leicht 24 Bit übersteigen kann. In einer Schleife werden Betrag und Vektorkomponenten solange halbiert, bis der obere Teil des Akkus = 0 ist, der Wert sich also nur noch in A0 befindet. Um das testen zu können, wird A1 in den zuvor gelöschten B-Akkumulator übertragen, da der „tst“-Befehl immer alle 56 Bits berücksichtigt.

Alle Vektorkomponenten werden durch den von „sqrt" gelieferten Betrag dividiert. Der Routine divide muß in R0 ein Flag übergeben werden (Bit 1), falls eine Integer-Division mit ganzzahligem Ergebnis durchgeführt werden soll. Wie aus der Tabelle „DSP-Arithmetik“ zu ersehen ist, müssen in einem solchen Fall der Dividend nach A0 übertragen und das Ergebnis verdoppelt werden. Da die einzelnen Vektorkomponenten - absolut betrachtet - immer kleiner oder gleich dem Vektorbetrag sind, erwarten wir in diesem Fall ein fraktionales Ergebnis; R0 wird also auf Null gesetzt. Die Divisionsroutine benutzt R0 auch als „Negations-Flag“ (Bit 0), da bei negativem Dividend das Ergebnis negiert werden muß (der Divisor ist bei allen vorkommenden Divisionen positiv).

Das absolut genommene Skalarprodukt der Einheitsvektoren Le und Re liefert endlich die Lichtintensität Vim Bereich von 0 bis 1. „+1" ($800000) wird beim Transfer des Akkus in das 24-Bit-Register X1 automatisch nach 0.999999 ($7FFFFF) gewandelt. Mit dem vom Benutzer regelbaren Parameter litefak wird das Spektrum von V eingegrenzt. Auf diese Weise wird der Kontrast zwischen direkt beleuchteten und im Schatten liegenden Flächen geregelt, liteoffs beträgt immer (1 - litefak) und dient zur Anhebung des Spektrums in den hellen Bereich; bei einer Verringerung des Kontrasts werden also die dunklen Flächen aufgehellt.

Mit V werden nun die RGB-Komponenten der ursprünglichen Farbe multipliziert. Dazu müssen die im True-Color-Modus des Falcon 5 Bit breiten Komponenten auf das Formatdes RGB-Einheitswürfels gebracht werden: Ist der entsprechende Anteil ausmaskiert, braucht dieser nur um eine bestimmte Anzahl von Bits geshiftet zu werden, um die richtige fraktionale Zahl darzustellen.

Beispiel: Der Blauanteil wäre = 16 ($000010). Shiftet man den Wert um 18 Bits nach links, erhält man $400000 = 0.5 (fraktional), was genau dem Anteil im RGB-Einheitswürfel entspricht.

Die RGB-Einheitswerte werden also mit V multipliziert und durch Maskieren, Shiften und ODERn wieder zu einem 16-Bit-Falcon-TC-Wert zusammengesetzt. Der Farbwert wird in N6 zwischengespeichert, und es wird mit der Berechnung der mittleren z-Koordinate der Fläche fortgefahren.

Das arithmetische Mittel wird berechnet und mit zmax verglichen. Den Parameter zmax könnte man als Clipping in der 3. Dimension bezeichnen. Mit ihm können die Flächen aussortiert werden, die hinter dem Betrachter liegen und somit unsichtbar sind. Normalerweise hat zmax den Wert Null, so daß ein einfacher Test auf zmittel > 0 genügen würde. Bei bestimmten Einstellungen der Parameter für die Zentralprojektion kann es aber Vorkommen, daß Projektionsfehler auftauchen, wenn die Fläche zu nahe am Brennpunkt liegt. Setzt man zmax auf einen negativen Wert (z.B. -200), werden diese Flächen aussortiert.

Die Flächen, die alle Ausscheidungen überstanden haben, werden in die Ausgabeliste eingetragen. Dann wird die Adresse auf die nächste Fläche gesetzt und die Schleife erneut durchlaufen, bis alle Flächen bearbeitet sind. Im Anschluß daran wird die Ausgabeliste in sortznach absteigenden z-Koordinaten sortiert.

Extras

Um das DSP-Programm mit dieser Folge komplett zu haben, enthält das Listing noch zwei weitere kleine Unterprogramme: litemove bewegt die Lichtquelle ganz ohne Zutun des Host-Programms mit jedem Zyklus um 1° weiter auf einer Kreisbahn um die x- und y-Achse. Start und Stop der Lichtrotation geschehen durch Setzen bzw. Löschen eines Bits in der Variablen doflag, die Teil der variablen Parameterliste ist.

Die Routine movecalc nimmt dem Host-Programm die Arbeit ab, aus den Blickwinkeln des Beobachters die genaue Bewegungsrichtung zu berechnen. Da die Beobachterposition in Welt-Koordinaten definiert ist, die Orientierung aber im Beobachtersystem erfolgt, wird schnell klar, daß wieder eine Transformation durchgeführt werden muß.

Ein Beispiel: Der virtuelle Weltenbummler befindet sich auf dem positiven Teil der x-Achse und blickt auf den Koordinatenursprung. Jetzt möchte er sich 100 Einheiten nach vorn bewegen. In diesem Fall müssen ja von der x-Koordinate des Beobachters 100 Einheiten subtrahiert werden. Richtet er nun den Blick entlang der z-Achse, müssen für eine Vorwärtsbewegung die 100 Einheiten von der z-Koordinate subtrahiert werden. Aus der Sicht des Betrachters wurde aber in beiden Fällen die z-Koordinate verändert, da das System ja immer entsprechend der Blickrichtung rotiert wird.

Die Lösung ist simpel: Man definiert drei Vektoren für die drei Basisbewegungen „seitwärts", „auf-/abwärts“ und „vor-/rückwärts“ im Beobachtersystem. Diese Vektoren fallen praktisch mit den Koordinatenachsen zusammen, daher ist auch jeweils nur eine Komponente ungleich Null. Diese Komponente ist gleichzeitig die Vektorlänge N und korrespondiert direkt mit der Bewegungsgeschwindigkeit. Die Vektoren werden als Punktkoordinaten in einem kleinen Array gespeichert. Wir haben also die drei Punkte (N,0,0), (0,N,0) und (0,0,N), die mit den schon bekannten Routinen rotiert werden. Rotationswinkel sind die Gegenwinkel des Betrachters (360° - Winkel), da es sich ja gewissermaßen um eine Rücktransformation handelt. Die neuen Koordinaten werden zusammen mit den anderen Ausgabedaten zum Host-Programm geschickt, das dann, je nach ausgewählter Bewegungsrichtung, die entsprechenden Komponenten zu den Beobachterkoordinaten addiert.

Demnächst...

... kommen wir dann endlich zur Darstellung auf dem Monitor. Das in Pure C geschriebene Host-Programm ist auf den True-Color-Modus abgestimmt und kann die Grafik wahlweise über VDI oder eine sehr schnelle Assembler-Routine ausgeben. Besprochen werden außerdem Möglichkeiten zur Erzeugung dreidimensionaler Objekte und Ideen zur Weiterentwicklung.

Literatur:

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

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

[3] ST-Computer 7-8/92: „Farbwahrnehmung und Farbmodelle“, Jörg Zettel, S. 99

# DSP-Arithmetik

Alle arithmetischen Operationen beziehen sich auf einen der beiden Akkumulatoren A oder B. Bei der Multiplikation und der Division muß man sich über die Wertebereiche der Operanden im Klaren sein und wie das Ergebnis zu interpretieren ist.

ADDITION/SUBTRAKTION

Das Ergebnis stimmt sowohl für Integerwerte als auch für fraktionale Zahlen.

  | X0 | A1 | A0 | add X0,A | A1 | A0 |   ------ | -- | -- | -- | -------- -- | -- | hex | $200000 | $400000 | - | | $600000 | - | - dez | 2097152 | 4194304 | - | —> | 6291456 | - | (w) frac | 0.25 | 0.5 | - | | 0.75 | - | (w)

MULTIPLIKATION

  | X0 | X1 | mpy X0,X1,A | A1 | A0 |   ------ | ------ | ------ | ------ | ------ | ------ | hex | $200000 | $400000 | --> | $100000 | 000000 | - dez | 2097152 | 4194304 | 20971524194304 | 1.759210^13 | 17592 * 10 * 13 | (f) frac | 0.25 | 0.5 | 0.25*0.5 | 0.125 | * | (w)

Das Ergebnis stimmt nur für fraktionale Zahlen. Das korrekte Integerergebnis (8.79609...10^12) erhält man, wenn man alle Bits von A1 und A0 betrachtet und den Wert halbiert! Für Integermultiplikationen sollte man daher nicht die Befehle mit automatischer Rundung (mpyr, macr) benutzen.

  | X0 | X1 | mpy X0,X1,A | A1 | A0 |   ------ | -- | -- | ----------- | -- | -- | hex | $200 | $4 | --> | $000000 | 000100 | - dez | 512 | 4 | 512*4 | - | 4096 | (f)

Erst A0/2 = $800 = 2048 liefert das korrekte Ergebnis.

DIVISION

Mit der Division verhält es sich etwas komplizierter. Hier muß man sich eine kleine Routine schreiben, die die Vorzeichen der Operanden auswertet (siehe DSP-Listing), da die „div"-lnstruktion nur für positive, fraktionale Zahlen gilt. Das Ergebnis (24 Bit) ist immer in A0 zu finden. Eine allgemeingültige Divisionsroutine muß zusätzlich noch zwei Fälle unterscheiden:

1. Dividend < Divisor (absolut)

Interessant ist hier das letzte Beispiel: Obwohl der Dividend durch die unterschiedliche Interpretation größer als der Divisor ist, wird das korrekte Integerergebnis in A0 geliefert, da $400000 eben doch größer als $10 ist!

  | X0 | A1 | rep #24
div X0,A | A1 | A0 |   ------ | -- | -- | ------------------- | -- | -- | hex | $400000 | $200000 | ---> | - | $400000 | frac | 0.5 | 0.25 | 0.25/0.5 | | 0.5 | (w) hex | $000010 | $000008 | | - | $400000 | dez | 16 | 16 | 8/16 | | frac 0.5 | (w) hex | $400000 | $000010 | | - | $000020 | frac | 0.5 | dez 16 | 16/0.5 | | dez 32 | (w)

2. Dividend > Divisor (absolut)

  | X0 | A0 | rep #24 div X0,A | A1 | A0 |   ------ | -- | -- | ------------------- | -- | -- | hex | $200000 | $400000 | ---> | - | $000001 | frac | 0.25 | 0.5 | 0.5/0.25 | | dez —> 1 | (f) hex | $000008 | $000010 | | - | $000001 | dez | 8 | 16 | 16/8 | | dez —> 1 | (f) hex | $000010 | $400000 | | - | $020000 | dez | 16 | frac 0.5 | 0.5/16 | | frac 0.0156 | (f)

Zu beachten ist zunächst, daß der Dividend in A0 (bzw. B0) übergeben werder muß (A1=0!), da es sonst zu einem Überlauf kommen kann. Das in A0 zurückgegebene Ergebnis muß unabhängig vom Zahlenformat in jedem Fall verdoppelt werden!

VEKTORBETRAG

Der Betrag eines Vektors |V| gibt dessen Länge an und errechnet sich aus der Wurzel der Summe der Quadrate der einzelnen Komponenten.

|V| = SQR(vx2+vy2+vz2)

SKALIERUNG

Die Länge eines Vektors kann durch Multiplikation mit einer Zahl (Skalar) verändert werden. Dabei ändert sich nicht die Richtung des Vektors.

V * c = (vxc,vyc,vz*c)

EINHEITSVEKTOR

Durch Skalierung, d.h. durch Division jeder Vektorkomponente durch den Vektorbetrag, erhält man einen Vektor der Länge 1, mit unveränderter Richtung.

Ve = (vx/|V|,vy/|V|,vz/|V|)

Zwei Vektoren können auf unterschiedliche Weise miteinander multipliziert werden:

SKALARPRODUKT

Das Skalarprodukt ist die Summe der Produkte der einzelnen Vektorkomponenten. Das Ergebnis ist, wie der Name schon sagt, kein Vektor, sondern eine reelle Zahl.

c = V * W = vxwx + vywy + vzwz= |V| * |W| * cos(α) <=> c = V((vx2+vy2+vz2)(wx2+wy2+wz2)) * cos(α)

α ist der von beiden Vektoren eingeschlossene Winkel.

Liegen V und W als Einheitsvektoren vor, erhält man in c direkt den Cosinus von α.

KREUZPRODUKT

Das Kreuzprodukt zweier Vektoren V und W liefert wiederum einen Vektor N. Dieser Ergebnisvektor steht senkrecht zu der von V und W aufgespannten Ebene (N = Normalvektor).

N = V x W = (vywz-vzwy,vzwx-vxwz,vxwy-vywx)


Klaus Heyne
Aus: ST-Computer 09 / 1995, Seite 90

Links

Copyright-Bestimmungen: siehe Über diese Seite