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:
- Die Eckpunkte einer FlĂ€che mĂŒssen, von auĂerhalb des Objekts betrachtet, diese im Uhrzeigersinn umschreiben.
- 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.
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)