3D der nächsten Generation: Fortgeschrittene Algorithmen der 3D-Grafik, Teil 1
Erinnern Sie sich? Vor über einem Jahr verhelfen wir Ihnen mit Grafikroutinen zum »Aufstieg in die dritte Dimension«. Jetzt liefern wir Ihnen neue Algorithmen, die Ihre Grafiken in neuem Glanz erstrahlen lassen.
In den TOS-Ausgaben 1/91-4/91 lernten wir die Grundlagen dreidimensionaler Grafik kennen. Dabei erweiterten wir Schritt für Schritt die »TOS-Animation-Language« (TAL), welche aus einfachen Befehlsdateien wunderschöne Grafiken zauberte. Doch bei komplexen oder sich durchdringenden Objekten traten Fehler des Hidden-Surface-Algorithmus zutage. Außerdem störten bei runden Objekten die groben Helligkeitsverläufe an der Oberfläche. Stürzen wir uns also gleich auf das erste Problem: Allgemein beschrieben besteht unsere Aufgabe darin, eine Reihe von Grundobjekten in korrekter Weise auf Bildpunkte zu projizieren. Für jeden Bildpunkt müssen wir nun das sichtbare Objekt auswählen. Als Entscheidungskriterium bietet sich hier die z-Koordinate an: Der Bildpunkt mit der niedrigsten z-Koordinate ist darzustellen, da er am nächsten zur Kamera liegt. Durch dieses Vorgehen treten auch keine Probleme mit sich durchstoßenden Objekten auf, da wir nicht mehr auf der Ebene von Objekten, sondern auf der Ebene von unteilbaren Bildpunkten operieren. Würden wir auf jeden Bildpunkt alle Flächen projizieren, so würde unser Atari so manche schlaflose Nacht verbringen, Raytracing wäre nicht langsamer. Deshalb gehen wir das Problem von der anderen Seite an: Für jeden Bildpunkt merken wir uns einfach die z-Koordinate des aktuellen Bildpunktes. Dazu richten wir uns das zweidimensionale Feld »d_z[MAXX][MAXY]« ein, welches für jeden Punkt der »MAXX« Spalten und »MAXY« Zeilen die z-Koordinate des Bildpunktes enthält. Nun stellen wir sämtliche Dreiecke unseres projizierten Bildes dar, wobei wir nur jeweils die Punkte mit minimaler z-Komponente zeichnen. Realisieren können wir dies nach folgendem Algorithmus, der nach seiner Wirkungsweise »depth-buffer«, Tiefenpuffer-Algorithmus genannt wird:
-
Setze alle d_z[x][y] = unendlich
-
Wiederhole für alle Dreiecke:
2.1 Bestimme alle Punkte (px,py,pz) des projizierten Dreiecks und die zugehörige Farbe f
2.2 Wenn pz < d_z[px][Py], dann setze d_z[px][py]=pz und stelle den Bildpunkt (px,py) in Farbe f dar.
Wir zeichnen jeden Bildpunkt, falls noch kein näher zur Kamera liegender Bildpunkt existiert. Nachteil des Verfahrens ist der enorme Speicherbedarf. Bei Integer-Elementen (2 Byte) würde der Tiefenpuffer bei bei einer Auflösung von 1280x960 Punkten ganze 2.34 MByte verschlingen.
Doch wenden wir unsere Aufmerksamkeit nun dem Zeichenvorgang zu. Bislang konnten wir munter mit den GEM-Funktionen zur Polygondarstellung hantieren. Jetzt müssen wir jeden Bildpunkt im Alleingang zeichnen, da wir stets die z-Koordinate beachten müssen. Zunächst benötigen wir die Funktion »d_setpixel(x,y,z,c)« zum Setzen des Grafikpunktes (x,y,z) der Farbe c. Dieser Vorgang ist unter Punkt 2.2 des Tiefenpuffer-Algorithmus beschrieben, ln der nächsten Kursfolge wollen wir bereits angedeutet ein Verfahren zur besseren Schattierung von Objekten kennenlernen. Aus diesem Grunde ist die neue »TAL«-Version speziell für die niedrige Auflösung ausgelegt. Das Programm arbeitet nach wie vor nur in Graustufen, von denen uns der Grafikchip aber gerade acht anbietet. Um eine größere Anzahl von Graustufen und zudem einen geringeren Speicherbedarf für den Depth-Buffer-Algorithmus zu erzielen, fassen wir vier Pixel zu einem Bildpunkt zusammen.
Wie in Bild 1 zu sehen, fassen wir zwei Zeilen aus jeweils zwei Pixel zusammen, so daß zwischen den zwei Helligkeitsstufen A (helle Kästchen) und B (dunkle Kästchen) drei zusätzliche Tönungen entstehen. Somit stehen uns 8 + 3 x 7 = 29 Helligkeitsstufen zur Verfügung. Die Bildpunkte stellen wir mit der »put_pixel«-Line-A-Funktion dar.
Liegt der darzustellende Bildpunkt in unserem nunmehr nur 160 x 100 Punkte großen Koordinatensystem und ist die z-Koordinate des Punktes geringer als die im z-Puffer, zeichnen wir diesen:
if ((z<d_z[x][y])&&(x>=0)&&(y>=0)&&
(x>MAXX) && (y<MAXY))
{ d_z[x][y]=z;-----}
Als »d_z[][]«-Datentyp verwenden wir übrigens Integerzahlen, die lediglich zwei Byte pro Pixel beanspruchen. Daraus ergibt sie eine Größe des Tiefenpuffers von 160 x 100 x 2 Byte = 32000 Byte.
Wie aber stellen wir ein komplettes Dreieck dar? Wir spicken bei den Kollegen vom Fernsehen und verfahren wie beim Aufbau eines Fernsehbildes: Vom obersten bis zum untersten Punkt des Dreiecks stellen wir die Zeilen einfach gesondert dar, die sogenannte »Scanline Conversion«. Dabei verwenden wir die Funktion »d_hline« zum Zeichnen einer horizontalen Linie, die wiederum die oben ersonnene »d_setpixel«-Funktion verwendet.
»Scanline Conversion« bei Dreiecken ist aufgrund des simplen Aufbaus recht einfach realisierbar. Zunächst unterteilen wir das darzustellende Dreieck in zwei Hälften: Von der Zeile des obersten bis zur Zeile des mittleren Eckpunktes und von der Zeile des mittleren bis zur Zeile des unteren Eckpunktes (siehe Bild 2). Innerhalb jeder Hälfte befinden sich nun zwei Begrenzungskanten mit konstanten Steigungen, zwischen denen wir in jeder Zeile eine horizontale Linie ausfüllen. Eine Kante (im Beispiel Ecke 1 -> Ecke 2) hat sogar eine über den gesamten Bereich konstante Steigung. Die Steigung »m« einer Geraden zwischen den Punkten A und B läßt sich bekanntlich nach der Formel m = deltaX/deltaY = (BX-AX)/(BY-AY) berechnen. Zunächst berechnen wir die Steigungen ml und m2 der zwei Kanten der oberen Dreieckshälfte. In der Variablen ty legen wir die aktuelle Zeile ab, t und tx2 enthalten die Endkoordinaten der beiden Endpunkte der aktuellen horizontalen Linie.
Zu Anfang setzen wir ty auf die y-Koordinate des obersten Punktes, t und tx2 enthalten beide die zugehörige x-Koordinate. Wir zeichnen die aktuelle Zeile von (t,ty) nach (tx2,ty) und erhöhen ty um eins. Durch Umstellen der Steigungsformel können wir nun bestimmen, um welchen dx-Wert sich die tx-Werte ändern: deltaX = m * deltaY. Da wir jeweils um eine Zeile nach unten wandern, nimmt deltaY den Wert 1 an, weshalb deltaX der Steigung m entspricht. Deshalb addieren wir zu t die Steigung m1 und zu tx2 die Steigung m2. Diesen Vorgang wiederholen wir solange, bis die Zeile des mittleren Punktes durchlaufen wurde. Analog zu diesem Verfahren füllen wir die zweite Hälfte des Dreiecks, nachdem wir die Steigung der zweiten Kante berechnet haben.
Eine Anforderung haben wir bislang jedoch noch nicht erfüllt: Die z-Koordinaten bleiben unberücksichtigt. Diese Unzulänglichkeit ist leicht beseitigt: Wir verfahren genau wie mit den x-Koordinaten, berechnen also zunächst die Steigungen mz1 und mz2 nach dem Muster: mz = deltaz/deltay = (z2-z1 )/(y2-y1). Nun führen wir die Variablen tz1 und tz2 ein, die wir anfangs auf den z-Wert der oberen Ecke setzen und nach dem Darstellen einer Zeile um mz1 bzw. mz2 erhöhen. Wir können somit die horizontale Linie unter Angabe der z-Koordinate von (t,ty,tz1) nach (tx2,ty,tz2) zeichnen.
Das Darstellen der horizontalen Linie mit der Funktion »d_hline« erfolgt nach einem ähnlichen, vereinfachten Muster. Die y-Koordinate bleibt konstant und somit unangetastet. Zunächst sorgen wir durch einen eventuellen Punkttausch dafür, daß Punkt 1 die geringere x-Koordinate besitzt und setzen die Variable tx auf die x-Koordinate von Punkt 1. Zum Schluß zeichnen wir den Bildpunkt und erhöhen tx um 1. Diesen Vorgang wiederholen wir solange, bis tx größer als x2 ist.
Aber auch hier bleibt die z-Komponente noch vernachlässigt, die sich von Pixel zu Pixel stetig in Abhängigkeit zur x-Koordinate ändert. Innerhalb der Scanline besitzt z die konstante Steigung mz = deltaZ/ deltaX = (Z2-Z1 )/(X2-X1). Da wir pixelweise Vorgehen, ist deltaX stet eins, weshalb deltaZ = mz. Vor dem Zeichnen des ersten Punktes setzen wir also tz=z1 und erhöhen tz nach jedem Pixel um die Steigung mz. Somit haben wir für jeden Punkt, den wir per »d_setpixel«-Aufruf setzen, eine korrekte z-Koordinate. Starten Sie nun bitte in der niedrigen ST-Auflösung »TAL.TOS«, damit wir den Lohn unserer Arbeit auf dem Bildschirm erblicken. Auf der TOS-Diskette finden Sie die Beispielskripte SCRIPT1.3D bis SCRIPT7.3D. Besonders interessant ist das letzte Skript, das sich durchstoßende Objekte enthält.
Während der Berechnungsphase erscheint für jedes bearbeitete Dreieck ein Dezimalpunkt auf dem Bildschirm, so daß Sie über den Fortgang der Berechnung stets im Bilde sind. Starten Sie das Programm als »UP«, übergeben Sie den Namen des gewünschten Scripts in der Dialogbox.
Zum Abschluß wollen wir es jedoch nicht versäumen, Ihnen den Befehlsschatz der neuen »TAL«-Version vorzustellen. Dieser ist größtenteils zu alten Versionen kompatibel. Unterschiede gibt es nur bei den Darstellungsmodi. Vektor-, Hidden-Line- und einfacher schattierter Modus sind nicht mehr vorhanden, sondern nur noch der Depth-Buffer-Modus, »SHADING« genannt.
Kommentare im Quelltext trennen Sie durch ein Sternchen (»*«) ab. Als Trennsymbole zwischen Zahlenwerten sind Leerzeichen oder beliebige Interpunktionszeichen erlaubt. Objekte definieren Sie innerhalb folgender Struktur:
OBJECT <nr> . . . ENDOBJECT
Innerhalb dieser Struktur definieren wir unsere 3D-Akteure aus den Grundelementen: Dreiecke, Rechtecke, Rotationskörper, Kugeln.
Ein Dreieck legen wir mit Hilfe der Eckpunkte fest:
TRIANGLE(,y1,z1,x2,y2,z2,x3,y3,z3)
Ein Rechteck erfordert ein weiteres Koordinatentripel:
RECTANGLE(,y1,z1,x2,y2,z2,x3,y3,z3,x4,y4,z4)
Zur Verwendung eines Rotationskörpers legen wir die Rotationsschrittzahl (maximal 20), die Zahl der Ecken der zu rotierende Facette (maximal 20) sowie die x-und y-Koordinaten der Facette fest:
ROTATE(rotzahl,ecken,y1,x2,y2,...)
Einen Kegel erhalten wir beispielsweise durch die Anweisung:
ROTATE(10,2,0,50,100,-50)
Zum Erzeugen einer Kugel geben wir die Rotationsschrittzahl und den gewünschten Radius an:
BALL(rotzahl,radius)
Die so definierten Objekte können wir nun (auch mehrmals) in unsere 3D-Welt setzen, wozu wir den PLACE-Befehl verwenden. Außer der Objektnummer übergeben wir die gewünschte Position, die Rotationswinkel um die x-, y- und z-Achse sowie Skalierungsfaktoren in x-, y- und z-Orientierung:
PLACE(obnr,x,y,z,rotx,roty,rotz,scalex,scaley, scalez)
Mit der folgenden Anweisung setzen wir das in x-Richtung auf zweifache und in y-Richtung auf halbe Größe gebrachte Objekt 1 an den Ort (10;-20;400):
PLACE(1,10,-20,400,-15,30,20,2,0.5,1)
Rotiert wurde hierbei um -15, 30 und 20 Grad. Alle PLACE-Aufrufe löschen Sie mit dem Befehl »CLEAR«. Mit der Anweisung »CAMERA« legen wir den Kamerastandort in der 3D-Welt, die Rotation um die drei Achsen sowie den Augenpunkt (normalerweise um -500) fest:
CAMERA(posx,posy,posz,rotx,roty,rotz,augpunkt)
Mit dem »SHADING«-Kommando geben wir die Richtung der parallel verlaufenden Lichtstrahlen an:
SHADING(lix,liy,liz)
Der Befehl DRAW zeichnet schließlich unsere 3D-Landschaft. »GETKEY« wartet auf einen Tastendruck und »SAVE« speichert ein fertiges Bild im Degas-Format.
Soviel als kurze Einweisung in die TOS-Animation-Language. Betrachten Sie doch einfach die Beispielskripte und ändern Sie diese nach Ihren Vorstellungen. Den Turbo-C-Quelltext können Sie nach Belieben an Ihre persönlichen Anforderungen anpassen. Besser aber Sie warten damit, es kommen ja noch zwei Updates. (ah)
Kursübersicht
Teil 1: Depth-Buffer-Algorithmus □ Scanline-Conversion
Teil 2: Gouraud-Shading für stufenlose Schattierung
Teil 3: Erweitertes Beleuchtungsmodell
Frank Mathy