3D Grafik Basic's verstehen ("Programmieren" lernen advanced)

Fragt sich dann noch, welche Vektoren man damit so vergleichen mag ...

Eine schöne Variante sind die Flächennormalen von oben, d.h. die Normalenvektoren, d.h. die per Kreuzprodukt errechenbaren Ergebnisvektoren, die senkrecht auf der Fläche stehen, die man befragt hat. Diese Flächennormalen vergleicht man nun direkt mit der Z-Achse. Wenn die Fläche in Richtung der Z-Achse "schaut", dann zeigt sie quasi nach hinten. Wenn die Flächennormale aber entgegen der Z-Achse orientiert ist, dann zeigt die Oberfläche irgendwie in Richtung zum Betrachter.

Wenn man also einen Körper hat, der so aufgebaut ist, das man nur nach außen zeigende Flächen hat, der also die Innenflächen verbirgt, dann ist es eine gute Schätzung, wenn man davon ausgeht, daß alles was Fläche ist, wenn man das Skalarprodukt mit der Z-Achse bildet und dabei ein negativer Wert herauskommt, zum Betrachter zeigen muß. Ist das Skalarprodukt von Flächennormale und Z-Achse dagegen postiv und daher zumindest >0 , dann heißt das, das es mit hoher Trefferrate eine Fläche ist, die nach hinten zeigt.

Und: solche Flächen könnte man - man sieht sie ja sowieso nicht - auch einfach beim Zeichnen und Berechnen auslassen !

Das funktioniert bei "soliden" Würfeln auch ganz prima - denn da ist es immer so, daß, egal wie man diese dreht, drei Seiten von vorn zu sehen sind und die drei anderen eben nicht - sie sind Rückseiten bzw. vom Beobachter weg gerichtet.

Wenn man die nun einfach ausläßt, hat man eine schöne Anwendung für die ganze Vektorisiererei - nämlich "Auslassen unnötig zu berechnender Rückflächen" oder in TechSpeech:

Backface Culling

und hier sind noch zwei Bilder, einmal alle sechs Flächen mit ihren Flächennormalen und dazu das Gleiche aber mit Backface Culling auf ON

Es gibt natürlich Situationen, wo man das nicht gut benutzen kann - etwa, wenn die Flächen vorn in irgendeiner Form transparent sind. Oder auch, wenn man Dinge baut, die von beiden Seiten gesehen werden müssen, z.B. ein Segelschiff mit einem einfachen Dreieck als Großsegel, wobei das Segel von beiden Seiten zeichenbar sein muß.

Die beiden obigen Formen der Vektormultiplikation selbst laufen einem aber immer wieder über den Weg - insbesondere auch bei der Beleuchtungsberechnung (Shading) und etwa bei der Verformung von Texturen.

Dazu noch die beiden exe-Dateien als Anhang zum Selberansehen.

Topic: ScanlineConversion und Rasterizer - oder wie das Bild besser auf den Bildschirm kommt

Nachdem nun schon so Einiges geht, muß man sich dann auch mal irgendwie Gedanken machen, wie das Bild vernünftig(er) auf den Bildschirm kommt. Die Abbildungen bisher sind ja als Drahtgittermodelle schon schön, aber noch fehlt ein bißchen das, was die 3D Grafik überhaupt erst hat zu so einem Erfolg werden lassen.

Drahtgittermodell und Linien lassen sich ja mittlerweile zeichnen - und benutzt werden dafür einfach nur die normalen Linienroutinen, die der Rechner so anbietet. Im Normalfall gehen diese auf einen Algorithmus zurück, der einfach nur "Bresenhams Linienalgorithmus" oder "der olle Bresenham" heißt und der es erlaubt mit relativ kleinem Aufwand und schnell (!) eine gerade Linie zu zeichnen - und das in einem beliebigen Winkel vom Startpunkt. [WikiP] [PaperIBM]

Die so entstehenden umgrenzten Flächen könnte man jetzt mit einem PAINT Befehl füllen oder alternativ davon irgendwelche geometrischen Unterteilungen - etwa der Seitenflächen des Würfels - ausrechnen und dann diese möglichst "optimal" ausmalen. So ließe sich etwa eine Seitenfläche / Viereck eines Würfels, egal wie man es dreht, immer irgendwie in einen mittig liegenden rechteckigen Block mit horizontalen und vertikalen Seiten und 4 ihn umgebende Dreiecke zerlegen, wobei der zentrale Block ziemlich einfach und schnell gefüllt wäre und die 4 Dreiecke ließen sich weiter unterteilen bis man quasi auf Pixelebene angelangt ist.

Solche Sachen sind auch durchaus gemacht worden - in Software - bis mal ein paar Leute angefangen haben, die Sachen ein wenig per Hardware zu beschleunigen.

Dabei sind die, in umgesetzter bekannterer Hardware, wichtigeren Meilensteine wahrscheinlich diese hier

( teils zu finden z.B. bei [1 , (August 5)] )

James H. Clark, The Geometry Engine: A VLSI Geometry System for Graphics, ComputerGraphics Vol.16 No.3 (1982), p. 127-133

Akeley, K., and Jermoluk, T. High-performance polygon rendering, Proceedings of the 15th annual conference on Computer graphics and interactive techniques (1988), ACM Press, pp. 239-246.

Kurt Akeley, RealityEngine Graphics, 1993

Wie man schon an den Titeln sehen kann, ist das erste Augenmerk gewesen, die Geometrieberechnungen zu beschleunigen. Das sind also alle Sachen die man mit den Weltkoordinaten so macht. Wenn man damit fertig ist, erhält man Vektoren, die Polygone beschreiben (können), die im Raum angeordnet sind und auf den Ausgabebildschirm umgerechnet werden können, z.B. um Linien damit zu zeichnen.

Man kann diese Daten aber auch an eine weitere Hardware weiterreichen, die sie auf besondere Art aufbereitet und dann daraus ein Bild erzeugt. ( Der nächste Schritt ist dann das Einführen von hardwarebeschleunigten Texturen, 1993. )

Die Trennung hier erfolgt quasi direkt am Übergang vom mathematischen Modellraum zum 2D Abbild. Und erst die Hardwarebeschleunigung dieses zweiten Schrittes, hat die 3D Graphik dann letztlich populär auch auf dem PC werden lassen - und damit Lara Croft, Doom und Serious Sam "Wirklichkeit".

Die Geometrieeinheit übergibt dafür folgende Informationen an die nachfolgenden "Abteilungen", nämlich an die Scanline-Conversion und den nachfolgenden Rasterizer: Für jeden Punkt aus der Welt werden Werte für X,Y und Z sowie evtl. Farbwerte für R,G,B und möglicherweise zusätzlich alpha (d.h. Transparenz) durchgereicht.

Dabei wird die Geometrieeinheit die Sachen in irgendeiner Form als "geordnetes" Polygon übergeben - prinzipiell können das Vierecke, Trapeze, Fünfecke oder sonstwas sein, es muß nur irgendwie definiert sein, damit die Hardware das einfach abarbeiten kann - am Ende lief es dann letztlich auf Dreiecke als quasi einfachstes Polygon hinaus.

Dreiecke haben nämlich die gute Eigenschaft, daß sie, egal wie man sie verdreht, knickt, kantet immer eine definierte Fläche darstellen. Und außerdem kann man so ziemlich jedes andere Polygon vorher - oder auch bereits in der Hardware aber noch vor der ScanlineConversion - in Dreiecke zerlegen.

Die in der 3D Hardware beschleunigt durchgerechneten Vektoren der "Welt", kommen also als Eckpunkte (X,Y) von "flachen" Polygonen mit einer Information über ihre Tiefe (Z) in der Scanline-Conversion an und bringen i.a. noch Farbinformationen mit (jeder Punkt für sich).

Dabei stellen sie geometrisch Polygone dar, die je nach Aufbau der folgenden 2D Hardware direkt benutzt oder weiter zerlegt werden. Der heute übliche Wege ist Dreiecke zu benutzen - und das hat letztlich, weil es dann am einfachsten wird, rückwirkend dazu geführt, daß bereits die Modellkoordinaten ganz am Anfang und damit die Modelle i.a. komplett aus Dreiecken aufgebaut werden.

Die Scanline-Conversion selbst benutzt dann eine Eigenschaft der Art in der Fernseh- und Monitorbilder üblicherweise aufgebaut werden - sie sind nämlich i.a. aus Linien aufgebaut, die schön regelmäßig übereinander liegen.

Dabei kann man nun in jeder Einzelzeile nachschauen, an welcher Stelle ein Objekt beginnt und an welcher es endet. Man sucht also nach den Schnittpunkten der Polygone mit den Linien in denen das Bild aufgebaut werden wird.

Und dabei ergibt sich dann noch ein Pluspunkt für Dreiecke: Egal was man mit dem Dreick vorher angestellt hat, die planare 2D Abbildung wird immer so sein, daß, wenn man eine Bildschirmlinie entlangwandert, man maximal auf zwei Schittpunkte mit dem Dreieck trifft !

Das ist zwar bei Vierecken im Normalfall auch so, aber z.B. nicht, wenn man sie über eine Diagonale gefaltet hat. Einsichtiger ist es möglicherweise bei anderen "...ecken" (unten rechts), da sieht man, daß im Linienverlauf einer Linie auch mal 4 oder mehr Schnittpunkte mit einem komplexeren Polygon auftreten können.

Die Gesamtidee ist nun, daß man für jede Linie einfach abfragt, an welcher Stelle das aktuell bearbeitete Polygon - und eben optimalerweise ein Dreieck - die angeschaute Bildschirmlinie "quert". Diese Schnittpunkte merkt man sich und wenn man alle Schnittpunkte "gesammelt" hat, erhält man somit eine 2D Abbildung der Figur, von der ja vorher nur die Eckpunkte aus der Geometrieeinheit übergeben worden sind !

Das ganze Verfahren vereinfacht sich auch noch dadurch, daß ja die Außenpunkte - nämlich die Eckpunkte - des Polygons bekannt sind. Man kann daher darauf verzichten die komplette Bildschirmlinie durchzumustern, sondern es reicht, sich auf den Bereich einzuschränken, in dem man das "Event", also den potentiellen Schnittpunkt, erwarten kann - nämlich zwischen xmin und xmax der übergebenen X-Werte und zwischen ymin und ymax der Y-Werte (Bild unten links).

Das Bild zeigt eine "zerlegte" Würfelfläche - ein Viereck, was zu 2 Dreiecken umdeklariert worden ist. Davon wird nun nur ein Dreieck betrachtet. Ziel ist es dabei aus drei bekannten Eckpunkten die schraffierte Fläche zu erhalten.

Damit das klappt läuft nun also die Scanline-Conversion jede in Frage kommende Linie zwischen xmin-xmax und ymin-ymax ab. Dabei versucht sie die Außenkanten des Dreiecks zu ermitteln. Und das geht, weil man ja aus den bekannten Eckpunkten mittels dreier einfacher Liniengleichungen die Verbindungen ausrechnen kann.

Nach y=mx+n (mit m als Anstieg und n als Startpunkt), lassen sich alle 3 Außenlinien des Dreiecks beschreiben - und daher auch bestimmen, an welcher Stelle die Schnittpunkte mit der Bildschirmlinie auftreten müssen.

Insbesondere aber: Man kann diese Berechnung nun hier komplett in 2D machen (X,Y). Prinzipiell ließe sich sowas auch in Vektoren und mit der 3D Geometrieeinheit mit (X,Y,Z) rechnen - aber die Variante, die nun kommt ist VIEL einfacher.

Da ja jede Außenkante selbst auch eine Linie ist, kommt hier wieder der "Bresenham" ins Spiel - allerdings in modifizierter Form. Die Herren Swanson und Thayer haben um 1986 eine Variante [1] des Bresenham (und auch anderes [2]) vorgestellt, die es erlaubt, für jedes Y - also für jede einzelne Bildschirmlinie - genau einen Punkt der beiden Außenlinien des Polygons zu finden, die die Linie schneiden - und das bei höherer Exaktheit und gleicher Geschwindigkeit.

Darüber werden zunächst in Y-Richtung für jede Bildschirmlinie die Schnittpunkte bestimmt. Die Abschnitte, die zwischen den beiden Außenpunkten auf jeder Linie liegen, sind also in ihrer Gesamtheit die Innenbereiche des Polygons/Dreiecks und haben als Linien eine besondere Bezeichung - das sind sogenannte Spans.

Die Spans sind also eine Reihe "guter Punkte" - Punkte die man zeichnen möchte, von denen man bisher aber nur die Außenbegrenzung kennt und idealerweise (Dreieck) weiß, daß es nur einen Span pro Bildschirmlinie geben kann.

Das Bild oben-rechts zeigt die drei Geradengleichungen, bzw. deren Anstiege, die sich jeweils aus delta-y durch delta-x ergeben; wobei man hier besser delta-x durch delta-y benutzt, weil man so einfacher von ymin bis ymax suchen kann (Algorithmus siehe Link [1]).

Das Bild unten-links zeigt in grün die gefundenen Schnittpunkte mit den Außenlinien.

Je einer pro Y-Wert.

Und man muß sich bewußt sein, daß bisher noch rein gar nichts gezeichnet wurde ! Das kommt aber im nächsten Schritt, und der ist theoretisch relativ einfach, denn:

Nun werden in genau der anderen Richtung - nämlich in X-Richtung - einfach entlang der Bildschirmlinien alle Punkte gezeichnet, die sich innerhalb der Spans befinden. Dadurch entsteht eine jeweils kurze Linie pro Bildschirmzeile - aber: alle zusammen ergeben dann exakt die flächig gefüllte Kontur des gewünschten Dreiecks.

Diese Sache wird nun für jedes darzustellende Dreieck durchexerziert - und da kann man sich vorstellen, daß da einiges an Rechnerei zusammenkommt. Und auch darum ist es bereits vorher so wichtig, möglichst alles, was man nicht berechnen will oder muß, auszusortieren - so früh wie irgend möglich. Die Scanline-Conversion und auch der Rasterizer - dieser nämlich ist für das letzte Linienzeichnen in X-Richtung zuständig - sind irgendwann ausgelastet, auch wenn sie evtl. in Hardware vorliegen.

Zudem hat wenigstens der Raterizer auch noch andere Aufgaben, und das hat dann schon was mit Farbe zu tun.

.

Nein, kein Buch ... aber wer weiß, was noch so draus wird ...

Die Idee war nur, das ich mal versuche aufzuschreiben, was dafür an minimalem Basiszeugs zu wissen ist. Siehe [#13(!) und #14]. Ich kann Dich aber trösten, es kommt nicht mehr allzuviel, es ist also gleich vorbei ... es kommen nur noch 3 Sachen zu Beleuchtung (Shading allgemein und Flat, Phong, Gouraud) und zwei Worte zum Frustum Culling und was evtl. sonst noch paßt, und hoffe, daß alles zusammen doch ein paar Leuten gefällt ; und evtl. dann noch ein paar Buch- und Webempfehlungen.

Tja, was soll man dazu sagen ... China ist groß !

Wenn Du magst, such doch mal den Titel von dem Buch (bzw. der 82'er Software) raus, was Du angesprochen hast. Dann haben auch andere was davon.

Topic: Farbe für den Rasterizer

Oben haben wir gesehen, daß das Bild für den Bildschirm zeilenweise nochmal neu "gefunden" wird. Das ist im Übrigen genau so ein Punkt, den man als extrem kompliziert erleben kann, wenn man das erste Mal über soetwas liest. Es ist nämlich eigentlich absolut unlogisch, warum man die 3D-Linien, die man ja gerade so schön mit den Vektoren ausrechnen konnte, plötzlich überhaupt nicht mehr benutzt, sondern stattdessen nur die Eckpunkte in eine "Maschine" (Scanline-Conversion) wirft und die daraus quasi "magisch" das Bild nochmal auf eine völlig andere Art und Weise in 2D neu aufbaut.

Eines haben wir aber bisher unberücksichtigt gelassen - nämlich, welchen Farbwert der Rasterizer jedem einzelnen Punkt zuweisen soll, wenn er die Spans in Pixel umsetzt, die dann auch schon tatsächlich im Framebuffer bzw. Graphic-Speicher als Bildinformation vorliegen.

Im einfachsten Fall nimmt man dafür halt einfach eine Standardfarbe, z.B. weiß. Damit bekommt man dann ein Bild, was aber nur für wenige Objekte funktioniert, weil man schnell nichts mehr unterscheiden kann.

Prinzipiell kann man aber auch für jeden Eckpunkt einen Farbwert mitgeben. Oder, wenn man es ganz einfach mag, dann nur einen Farbwert für die gesamte Polygonfläche. Dem Rasterizer ist das letztlich völlig egal - der malt einfach jeden Pixel mit dem vorliegenden Wert aus.

Bei einer Farbe pro Fläche (pro Dreieck) kann man dann auch schon wieder solche Dinge wie mit den grauen Linien machen - einfach den Farbwert für weiter hinten liegende Objekt weniger hell gestalten. Das klappt durchaus auch mit Farben, nicht nur mit Graustufen, so daß man z.B. 64 (oder 256) Farbabstufungen nach hinten bekommt - für jede Grundfarbe (R,G,B).

Eine Variante, die Farbe zu bestimmen, wenn man für jeden Eckpunkt einen RGB Wert "mitbekommt", wäre auch, einfach einen Mittelwert der 3 Eckpunkte zu bilden, also sowas

Rotwert = INT ( ( Rotwert-Ecke1 + Rotwert-Ecke2 + Rotwert-Ecke3 ) / 3 )

Grünwert = INT ( ( Grünwert-Ecke1 + Grünwert-Ecke2 + Grünwert-Ecke3 ) / 3 )

Blauwert = INT ( ( Blauwert-Ecke1 + Blauwert-Ecke2 + Blauwert-Ecke3 ) / 3

und diesen Wert an den Rasterizer zum Malen zu übergeben.

Je nachdem, wie das ganze Graphicsystem aufgebaut ist, kann das massiv bremsend wirken, oder gar nicht bemerkt werden - ganz in Abhängigkeit davon, wo und wie diese Art Berechnungen gemacht werden (echte Graphic-Hardware, Software, Software auf einer Maschine mit FPA (numerischer CoProzessor), Software mit Tabellen für Farbwerte etc.)

Eine schöne Variante ist, wenn man die Eckfarbwerte schon bekommt, einen Übergang der Farbwerte von einer Ecke zur benachbarten auszurechnen - d.h. die Farbwerte zu interpolieren.

Dazu wird i.P. einfach der Abstand der Farbwerte für jede der drei Grundfarben einzeln durch den Abstand in Pixeln von Ecke 1 zu Ecke 2 geteilt und auf den niedrigeren Farbwert aufaddiert, also

Farbwert = kleinerer Wert von beiden + aktuelle Pixelnummer * ( ABS (Farbwert-Ecke1 - Farbwert-Ecke2) / Pixelzahl des Abstands)

Das kann man dann für jede der drei Seiten des Dreiecks machen und mit diesen Werten die Einzelpixel des Spans einfärben lassen. Dadurch ergeben sich weiche Farbverläufe innerhalb der Fläche. Die Farben selbst hängen aber in keiner Form von der Umgebung oder Position des Objekts ab, sie sind quasi statisch und immer gleich.

Interessanter wird das Ganze, wenn man eine künstliche Beleuchtung einführt und die Farben in Abhängigkeit der Objektposition zur "Sonne" errechnet.

Im Nachgang, und bevor es dezent vektorbasiert weitergeht, noch eine kleine Bastelei. Kann sein, daß das mehr Verwirrung stiftet, als wirklich hilfreich zu sein, aber es ist quasi ein kleiner "software-rasterizer" mit vorgeschalteter "scan-conversion" zum Basteln. Es wird ein Dreieck vorgegeben (DATA Zeilen) und das oben geschriebene Bildumsetzen in gaaanz langsam und nur für dieses eine Dreieck durchgerechnet - also erst in Y-Richtung die Spans finden (über Liniengleichung jeder Dreiecksseite) und dann in X-Richtung die Spans ausmalen.

Abbruch mit ESC Key - alternativ kommen immer neue Zufallsdreiecke.

DECLARE SUB spans (x1!, y1!, x2!, y2!)
DECLARE SUB warte (t!)

SCREEN 12

REM --- variablendef's und dreieck einlesen (deck) ---

DIM SHARED deck(2, 2)
FOR i = 0 TO 2: FOR j = 0 TO 2: READ deck(i, j): NEXT: NEXT
REM jeweils ein punkt mit (x,y,z) koordinaten
DATA 42,125,25,   228,245,56,   165,336,15

DIM SHARED span1(512), span2(512)

restart:
CLS

REM --- das dreieck zeichnen ---

LINE (deck(0, 0), deck(0, 1))-(deck(1, 0), deck(1, 1)), 14
LINE (deck(1, 0), deck(1, 1))-(deck(2, 0), deck(2, 1)), 14
LINE (deck(2, 0), deck(2, 1))-(deck(0, 0), deck(0, 1)), 14


REM --- die spans finden , scan-line conversion ---

PRINT " ... scan-conversion"

REM spans vorbelegen/löschen ; benutzt wird einfach der erste "freie"
FOR i = 0 TO 511: span1(i) = -1: span2(i) = -1: NEXT

REM jede dreieckseite in y-richtung ablaufen und die schnittpunkte finden
xa = deck(0, 0): ya = deck(0, 1): xe = deck(1, 0): ye = deck(1, 1)
CALL spans(xa, ya, xe, ye)
xa = deck(1, 0): ya = deck(1, 1): xe = deck(2, 0): ye = deck(2, 1)
CALL spans(xa, ya, xe, ye)
xa = deck(2, 0): ya = deck(2, 1): xe = deck(0, 0): ye = deck(0, 1)
CALL spans(xa, ya, xe, ye)


REM --- die spans auslesen und je eine horizontale linie zeichnen

PRINT " ... rasterizer"

FOR i = 0 TO 511
 s1 = span1(i): s2 = span2(i)
 IF (s1 >= 0) AND (s2 >= 0) THEN
   REM anzeigen und infos
   LINE (7, i)-(9, i), 14
   LINE (320, 20)-(639, 23), 0, BF
   LINE (s1 + 320, 20)-(s2 + 320, 23), 14, BF
   REM die eigentliche rasterlinie
   LINE (s1 + 320, i)-(s2 + 320, i), 14
   CALL warte(4)
 END IF
NEXT

IF INKEY$ <> CHR$(27) THEN
 REM neues zufälliges Dreieck
 RANDOMIZE TIMER
 deck(0, 0) = RND * 319: deck(0, 1) = RND * 400 + 40
 deck(1, 0) = RND * 319: deck(1, 1) = RND * 400 + 40
 deck(2, 0) = RND * 319: deck(2, 1) = RND * 400 + 40
 GOTO restart:
END IF

END


SUB spans (x1, y1, x2, y2)

REM (anfang,ende) vertauschen, so daß y1 immer das kleinere y bekommt
IF y1 > y2 THEN SWAP y1, y2: SWAP x1, x2

REM Anstieg der Linie berechnen - für laufrichtung y
dx = x2 - x1
dy = y2 - y1

m = dx / dy

REM bereich für anzeigebalken löschen
LINE (0, 0)-(4, 479), 0, BF

REM x auf ersten startwert setzen
x = x1

REM jeden y-wert genau einmal durchlaufen
FOR y = y1 TO y2

 REM zu jedem y das errechnete x der linie speichern
 x = x + m
 IF span1(y) = -1 THEN span1(y) = INT(x) ELSE span2(y) = INT(x)

 REM infobalken
 LINE (1, y)-(3, y), 14
 REM berechnete punkte der linie anzeigen
 LINE (x, y)-(x, y), 13
 LINE (x + 320, y)-(x + 320, y), 15

 CALL warte(1)

NEXT y

END SUB


SUB warte (t)

h1 = TIMER * 1000

DO
 h2 = TIMER * 1000 - h1
LOOP UNTIL h2 > t

END SUB

Man sieht, daß das meiste eher Zubehör ist - also Anzeigen etc. Beide Teile zusammen setzen aber die 3D Werte in 2D Bilder um. Bemerkenswert dabei ist: a.) das ist total simpel (eigentlich), b.) es ist sehr einfach in Hardware umsetzbar, v.a. auch weil es immer das gleiche macht, c.) es ist auch auf mehrere Rechen-Untereinheiten aufteilbar, die z.B. nur einen bestimmten Y-Bereich oder jede je ein einzelnes Dreieck auswerten.

Topic: Shading mit einfacher Beleuchtung

Wie kommt man nun zu Bildern, die nicht nur Farben haben, sondern evtl. auch ein bißchen "echtes Licht" ?

Die Idee dahinter war anfangs, daß man möglichst die (damals neuen) mittels Scanline gerenderten Flächen unterscheiden können wollte. Dafür gab es dann primär die Idee, daß man das in Abhängigkeit vom Blickpunkt macht und zur Vereinfachung annimmt, daß die Lichtquelle quasi auch beim Betrachter steht. Die Lichtstrahlen fallen daher quasi von vorn in das Bild hinein und beleuchten das Bild und kommen dann entweder zum Betrachter in abgeschwächter Form zurück - oder eben nicht (nämlich wenn die Fläche z.B. seitlich zeigt). Wie das so ausgesehen hat, kann man bei Gary Scott Watkins (Utah, 1970) auf den Seiten 42 - 51 und 61 - 63 anschauen. Die Kirche in Bild 35 ( Seite 61 ) hatte dabei auf einer PDP-10 eine Renderzeit von nur (!) 2,5 Minuten.

Allerdings ist das Lichtmodell eher die heutige Erkärung - damals haben die wohl einfach eine Funktion gesucht, die die Flächen hell macht, wenn man direkt draufschaut und sie entsprechend abdunkelt, wenn sie zur Seite wegkippt. Und da eignet sich dann der Cosinus (wieder mal) ganz gut.

Daher ist die heutige Erklärung wohl ein bißchen nachträglich aufgesetzt, aber trotzdem natürlich nicht völlig verkehrt. Diese beginnt nämlich mit dem Lambertschen Gesetz bzw., was das Gleiche ist, dem Lambertschen Cosinusgesetz.

Dies ist einfach eine Beobachtung, die man macht, wenn man Dinge beleuchtet, etwa auf einer optischen Bank oder einfach mit einer Taschenlampe. Sie besagt dabei sowas wie: Das Licht wird von einer beleuchteten Flächen aufgenommen und, zumindest in Teilen, wieder in den Raum abgegeben. Dabei hängt der wieder abgegebene Teil natürlich vom Material der Fläche ab (Holz, Papier, Stoff usf.). Darüberhinaus gilt aber ziemlich gut, daß das meiste Licht quasi senkrecht zur Oberfläche wieder "entweicht" und die nach den Seiten hin abgestrahlte "Lichtmenge" ganz gut beschreibbar ist mit dem Cosinus zwischen -90 Grad und 90 Grad. Und nach hinten kommt halt (Ausnahme Transparenzen) nichts durch.

Diese Art Lichtabgabe hat auch nichts mit Reflektion o.ä. zu tun - sie ist quasi eine Eigenschaft von Material, die generell besteht. Natürlich gilt die Beschreibung nur gut für ziemlich gleichartige, in sich ähnlich strukturierte, flächige Elemente einer Oberfläche. Außerdem funktioniert das Lambertsche Gesetz auch so "Pi-mal-Daumen" nur im Bereich des sichtbaren Lichts, außerhalb dessen gibt es Abweichungen. Trotzdem kann man sagen, daß gilt:

die (Ab)Strahlstärke I ist abhängig vom Winkel des abgestrahlten Lichtes und zudem proportional zum Produkt aus Fläche und dem Cosinus des Winkels

Sie ist also senkrecht maximal und nimmt ab je "schräger" man auf die Fläche schaut.

Und genau das macht man ja bei gekippten Flächen in Computergraphiken.

Es ist auch schon bekannt, wie man das benutzen kann - denn strenggenommen haben wir sowas ja schon gemacht, nämlich beim Backface Culling, dort allerdings mit einer Ja/Nein Entscheidung (überhaupt sichtbar/nicht sichtbar).

Hier macht man das ähnlich: Es wird ein Vektor bestimmt, der die Fläche und ihre Lage im Raum beschreibt - nämlich ein Normalenvektor, eine Flächennormale. Die kann man wieder über das Kreuzprodukt von zwei Vektoren berechnen, die die Fläche mit aufbauen. Im Optimalfall nimmt man einfach den Normalenvektor, den man vorher sowieso schonmal ausgerechnet hat.

Und dann - s.o. - ist die Lichtquelle ja in einer Achse mit dem Auge des Beobachters und da der im einfachsten Fall in Richtung Z-Achse schaut, kann man auch einfach den Winkel zwischen dem Normalenvektor und der Z-Achse bestimmen. Bestimmt man davon den Cosinus, bekommt man quasi direkt ein Maß für die Helligkeit, die die beleuchtete Fläche abstrahlt.

Diesen Wert muß man dann nur noch auf die Helligkeiten der Grafikkarte abbilden - also 1 = Maximum und 0 = dunkel; und alles dazwischen wird in soviele Helligkeitsstufen unterteilt, wie die Grafikkarte gerade darstellen kann.

Ob damit dann nur Graustufen angezeigt werden, oder eine vorhandene Farbe (R,G,B) aufgehellt wird, ist für den Ablauf eigentlich egal.

Man bekommt daher eine Helligkeit der Fläche und kann diesen einen Wert direkt benutzen, um die Scanline bzw. die Spans im Rasterizer zu zeichnen. Für diesen Fall, nämlich, daß man genau eine Farbe/Helligkeit für die gesamte Fläche verwendet, ergibt sich ein sogenanntes: Flat Shading.

Die Bilder sehen dann aus wie der Amiga Boing Ball, nur daß die Seitenflächen abgedunkelt erscheinen. Das große Problem dabei ist, daß es ja keine Übergänge zwischen den Helligkeiten/Farben gibt und deshalb die Kanten der Polygone optisch noch betont hervortreten. Fläche 1 stößt an Fläche 2 und an der Grenze zwischen beiden entsteht optisch eine Kante.

Das allermeiste, was als 3D Demo auf Amiga/Atari und Co zu sehen ist, benutzt - wenn es denn überhaupt geshadet wird - so ein Flat-Shading; was aber oft auch gar nicht nötig ist.

Etwa sind beim Spiel "Virus" [Atari YT, Amiga YT] bzw. dem Analogon "Zarch" [Archimedes YT] zwar jede Menge Polygone zu sehen, aber geshadet ist da eigentlich kaum was. Lediglich bei Zarch gibt es einen einfachen Tiefenalgorithmus, der die Flächen abdunkelt je weiter hinten sie im Bild liegen und das Raumschiff (der Lander) ist Flat-Shaded - d.h. beim Drehen und Kippen wechselt die Helligkeit der Flächen.

Und hier noch ein bekanntes Amiga Demo (Phenomena - Enigma) mit einem Teil [2:12], der völlig ohne Shading auskommt (man beachte z.B. den grauen Turm, mit trotz Drehung statisch grauen Farben) und einem Teil mit Flat-Shading [6:12], was ziemlich hübsch ist.

Topic: Shading mit einfacher Beleuchtung und weichen Übergängen (und evtl. auch vielen Farben)

Der nächste Schritt hin zu bunten Bildern - oder in dem Fall eher: zu Bildern mit stufenlosen Schattierungen, die an den Enden der Flächen nahtlos ineinander übergehen - kam 1971. Zu der Zeit wurde in Utah mit Flächen experimentiert, die möglichst auch Bögen und Beulen haben können sollten.

Dabei stört dann so ein optischer Bruch, der beim Flatshading entsteht, schon sehr das Erscheinungsbild.

Die Lösung wurde von Henri Gouraud vorgestellt - unter dem "Patronat" von Evans-and-Sutherland, v.a. dem letzteren - und heißt heute Gouraud Shading.

Dieses verwendet statt einem Vektor pro Fläche einen Normalenvektor an jedem Eckpunkt der Fläche.

Für diesen wird dann die gleiche Berechnung wie oben angestellt und in Abhängigkeit des Winkels bzw. des Cosinuswertes ein Shading-Wert (also eine Helligkeit) für diesen Eckpunkt berechnet.

Dabei sitzt die Lichtquelle wieder direkt am Betrachter und dieser schaut der Z-Achse folgend ins Bild hinein.

Anschließend - und das ist das Neue - werden die Shadingwerte der Eckpunkte linear interpoliert, d.h. es wird ein weicher Übergang von einer Ecke zur anderen errechnet, nach

S = (1-a) * S1 + a * S2

mit a zwischen 0...1 und S1,S2 als den beiden Eckpunkthelligkeiten. S ist dabei der errechnete Shadingwert für den Punkt zwischen S1 und S2 an der mittleren Position a.

Dieser Wert S wird an der passenden Scanline benutzt und an den Rasterizer gegeben. Und dieser wiederum kann innerhalb der Scanline eine gleiche Interpolations-Berechnung auch nochmal machen, und damit die Scanline selbst interpolieren - zwischen dem Wert S und einem weiteren S für die Strecke, die am anderen Ende des Spans, und damit der Scanline, sitzt.

Damit ergeben sich dann "fließende" Helligkeitsverteilungen innnerhalb des gesamten Polygons.

Für Farben macht man die Interpolation jeweils innerhalb einer Grundfarbe - R,G,B - und verdreifacht damit natürlich locker mal den Rechenaufwand.

An der Stelle sind dann auch Grafikkarten/VideoChips interessant, die nicht 32 Bit Farben benutzen, sondern einen gewissen Satz an Grundfarben in bestimmten Helligkeitsstufen darstellen können - dort reicht dann nämlich ebenfalls die eine Interpolation für die Helligkeit aus.

Lediglich wenn die Flächen nicht in ausreichend kleinen Winkeln ineinander übergehen, stößt das Gouraud Shading an echte Grenzen und muß man evtl. ein bißchen nachbessern. Dann kann man statt einer Normale an einer Ecke der Fläche zusätzlich die Normalen der an dieser Ecke angrenzenden Flächen berücksichtigen und z.B. daraus einen Mittelwert bilden und diesen dann "shaden". Den Wert kann man dann aber auch gleich für alle angrenzenden Flächen in diesem Eckpunkt benutzen, so daß nur die Mittelwertbildung selbst zusätzliche Berechnung erfordert.

Hier die Originalarbeit zum "mal Reinschauen" und dazu noch, ziemlich mittig, der entsprechende Artikel dazu als PDF (Gouraud H.: "Continuous Shading of Curved Surfaces", IEEE Transactions on Computers, C-20, pp. 623–629, 1971).

Und hier zum Effekt-Anschauen: Polygon Discount (by Lamers) Atari Falcon (YT) ; ach ja, natürlich nur der rechte Teil ...

Topic: Shading mit Reflexen und aufwendiger Berechnung - Phong-Shading

Ein paar Jahre nach Gouraud - nämlich 1975 - gab es eine wesentliche (!) Verbesserung in der Herangehensweise an das Problem mit dem Einfärben von Pixeln. Beschrieben hat die ein Herr Phong, dessen Arbeit man im Original bei [1] herunterladen kann: Phong B.T.: "Illumination for Computer Generated Pictures".

Wer vorhat nur einen einzigen derartigen Artikel überhaupt anzuschauen, sollte m.E. unbedingt diesen nehmen.

Eigentlich wird da nicht nur ein neues Shading vorgestellt, sondern gleich ein komplettes neues sogenanntes "Beleuchtungsmodell". Der Unterschied ?? Das eine, das Shading, ist eine Technik, wie man etwas berechnet, das Modell dazu ist quasi die theoretische Begründung dafür. Es macht in diesem Fall Sinn, das zu unterscheiden, weil man das Phong Beleuchtungsmodell auch mit anderen Arten des Shadings anwenden kann.

Der Ansatzpunkt ist v.a., daß vorher übliche Modelle eigentlich kaum etwas mit "echter Physik des Lichtes" zu tun haben - mal abgesehen von der zufälligen Übereinstimmung der Winkelfunktion beim Lambertschen Gesetz. Letztlich ist auch das Phong Beleuchtungsmodell keine echte "Naturbeschreibung" - aber es ist in seinem Effekt viel näher an den beobachtbaren natürlichen Bildern.

Insbesondere die völlig fehlende Benutzung des minmal vorhandenen Modells für die allermeisten dargestellten Punkte wird beim Phong-Shading aufgehoben - soll heißen: vorher wurde die Mehrheit der Punkte gar nicht gerechnet. Hier werden erstmals alle (!) Punkte, die angezeigt werden sollen, einer Lichtberechnung unterworfen. Diese geschieht genauso, wie das bei Flat-Shading für einen Vektor und bei Gouraud-Shading für die Eckvektoren gemacht wird - nur eben hier für alles.

Theoretisch könnte das nun bedeuten, daß man für jeden Punkt eine Normale mittels Kreuzprodukt berechnet - praktisch waren und sind Computer aber langsam !

Und daher ist der Weg, den das Phong-Shading benutzt, dieser:

Die Normalenvektoren werden, wie vorher auch, für die Eckpunkte direkt aus der 3D-Welt errechnet. Im Anschluß werden aber nicht direkt die Helligkeits-/Farbwerte der Eckpunkte berechnet und diese entlang einer Kante interpoliert - sondern es werden die Normalenvektoren interpoliert. Das Ergebnis ist dann eine Reihe von Normalenvektoren. Dies geschieht für jede Kante. Man umgibt also das Polygon rundherum mit Normalenvektoren - wie ein Gartenzaun aus Lanzen. Anschließend wird - wieder ähnlich dem Gouraud - für jede Scanline eine weitere Interpolation gemacht - zwischen den beiden Außenvektoren. Dadurch erhält man für jeden Span eine Reihe von Normalenvektoren, d.h. für jeden darzustellenden Punkt der Fläche genau einen Vektor.

Und erst dieser wird dann - so wie bei Gouraud ausschließlich die Ecken - zur Lichtberechnung benutzt.

Man hat also für jeden Bildpunkt einen Vektor der einzeln ausgewertet werden muß: ein immens höherer Rechenaufwand. Und dabei hat man sich ja schon das direkte Vektorberechnen gespart, sondern nur interpoliert.

Was dann mit dem Vektor des Einzelpunktes gemacht wird, ist dann wieder recht flexibel. Man könnte ihn z.B. einfach nur so "beleuchten" wie das oben geschehen ist - also Cosinus des Winkels zur Z-Achse bestimmen und dieses als Helligkeit benutzen.

Schon das würde einen Vorteil erbringen - die Gebilde würden abgerundeter erscheinen und an Kanten auftretende helle Streifen würden reduziert; der Effekt wäre sowas wie ein schöneres und runderes Gouraud ohne optische Störstellen.

Zum Phong-Shading nach dem Phong-Beleuchtungsmodell gehören aber noch zwei andere Sachen:

neben der sogenannten diffusen Beleuchtung - nämlich eben dem Licht, was man über die Cosinus-Auswertung ins Spiel bringt - kommen noch ambiente Beleuchtung und Reflexionshelligkeiten (specular lights).

Ambient bedeutet dabei einfach eine Grundhelligkeit, die im gesamten Bild auftritt. Es ist wie so eine Art Helligkeitsregler, der alle Objekte an allen Stellen heller werden läßt. Dabei wird für jede Fläche noch eine Materialkonstante mitmultipliziert, so daß bestimmte Flächen "schneller" hell werden als andere.

Und "specular lights" sind Helligkeiten, die durch Reflexionen entstehen. Dazu wird für jeden Vektor geschaut, ob und wie sich die Winkel zwischen Lichtquelle und insbesondere deren reflektiertem Strahl am Objekt und dem Beobachter sich verhalten. Maiximales Licht und damit addierte Heligkeit kommt an, wenn der reflektierte Strahl die gleiche Lage, wie die Sichtachse hat. Auch hier wird letztlich wieder einfach ein Cosinus des Winkels zwischen den beiden Vektoren (Sichtachse - reflektierter Strahl) gebildet (über Skalarprodukt) und dieser in Helligkeiten übersetzt.

Die Gesamtgleichung des Lichtmodells lautet dann

I _gesamt = I _ambient + I _diffus + I _specular

mit I (großes "i") für Lichtstrom/-stärke.

Interessant sind die entstehenden Kugelobjekte mit ihren runden Reflexionsflecken auch deshalb, weil man die nahezu ubiquitär in Amiga Demos wiederfindet - dort allerdings als gemalte Pixelkugeln bzw. Bälle mit einem weißen Fleck (meist links oben), die sich dann - völlig ohne eine Anpassung an eine ebenso nicht vorhandene Lichtquelle - in vielerlei Bahnen und Ellipsen bewegen und so tun als ob sie Phong geshadete Kugeln seien.

.

Eine Weiterentwicklung des Phong-Shadings ist das 1977 vorgestellte Blinn-Beleuchtungsmodell [WikiP]. Dieses vereinfacht die Art wie die Reflexionen berechnet werden und ist dadurch schneller, bei kaum unterscheidbaren Bildern. Die Kombination Blinn-Phong ist auch das, was SGI in seinem Iris GL bzw. Open GL [WikiP,e] [WikiP,d] fürs Shading benutzt(e).

Topic: Teekannen und Abziehbildchen, Bump-Maps als Beispiel für Texturen

Nun könnte man ja denken, daß damit alle Probleme geklärt und eine befriedigende Lösung gefunden war. Für reine CAD Modelle, Automobil- und Flugzeugbau und natürlich auch U-Boot, Flugzeugträger und sonstige Großschiffe, aber auch Häuser und Betonvisualisierungen reicht das völlig aus. Aber es gab da eben noch Sachen, die man damit abseits solcher Dinge anstellen kann.

Und wie die Leute so sind ... sie spielen gern. In Utah hatte man dafür, nach Kugeln, Zylindern und Donutringen (Tori), eine wundersame Teekanne entdeckt - den "teapot".

[WikiP,e][WikiP,d][Bild] und eine Version davon in [OpenGL]

Das Original steht heute im Museum in Mountain View.

[X398.84][Objektseite bei CHM][Bilder]

Und - das ist für ein deutsches Computerforum sicher ganz interessant - es handelt sich dabei um eine Melitta Teekanne aus, wahrscheinlich zu der Zeit noch, deutscher Produktion; benannt nach Melitta Bentz, die mit 73 Pfennigen (!) Eigenkapital 1908 in Dresden eine Firma zur Herstellung der von ihr erfundenen Papierfiltertüten für Kaffee hat eintragen lassen. Ihr Mann kam übrigens aus Clausthal-Zellerfeld - falls das hier doch irgendwie von Interesse sein sollte ... so schließt man Kreise ...

In Utah war das dann einfach ein schönes komplexes Testobjekt, dessen Formen von Martin Newell zum Datensatz "gemacht" worden waren und das sich als "Mem" unauslöschlich in die Computergeschichte eingeschrieben hat.

Insbesondere der Artikel

Blinn, J. F., and Newell, M. E. Texture and reflection in computer generated images. Communications of the ACM 19, 10 (1976), 542-547 [PDFlink]

lohnt sich diesbezüglich mal anzuschauen, schon rein wegen der Bilder.

Generell war so eine Teekanne nämlich prima geeignet, um darauf Dinge in verzerrter Form abzubilden. Also zum Beispiel Bilder.

Letztlich bedeutet das, daß man für jeden berechneten Pixel im Ergebnisbild einen Farbwert aus einer Vorlage ausliest und den zugehörigen Pixel dementsprechend umfärbt. Dabei kann man auch andere Werte außer Farben ändern, z.B. die Helligkeit über alle 3 Farben (Schatten) oder auch die Vektoren nachträglich nochmal beeinflussen, s.u.

Sowas nennt sich dann eine Textur.

Und da es nicht mehr auf den Vektoren beruht, sondern die bereits gerenderten Pixel verändert werden, nennt man sowas auch ein "per-pixel-shading".

Eine besonders schöne einfache Form, wo man den Übergang zwischen beiden - Vektoren vs. Pixel - auch gut sieht ist das in

Blinn J.F., Simulation of Wrinkled Surfaces, Proc. 5th Conference on Computer Graphics and Interactive Techniques, 1978 [PDFlink (ganz unten)]

vorgestellte Umrechnen der Vektoren namens Bump-Mapping.

Es handelt sich dabei i.P. um eine per-pixel-geshadete Textur - mit der besonderen Note, daß die Vektoren nochmal "angefaßt" werden. Dabei wird die normale Berechnung in Weltkoordinaten etc. gemacht, bis zu dem Punkt, wo das Shading einsetzt. Aber bevor die letztendliche Beleuchtungsberechnung erfolgt, kommt noch ein zusätzlicher Schritt: nach dem Phong/Blinn Shading, erhält man ja, für jeden Pixel des Bildes einen Vektor. Dieser wird nun nach einem bestimmten Modus verkürzt. Dazu verwendet man eine "Map", d.h. eine Art Bild bzw. Tabelle in die Werte zwischen 0 und 1 eingetragen sind.

Nach Umrechnen der Positionen auf das Modellobjekt, kann man diese Werte mit den interpolierten Vektoren multiplizieren und so nachträglich (!) die Länge der Vektoren und damit die Helligkeiten noch beeinflussen. Es ergibt sich dabei ein Effekt, der optisch eine Rauhigkeit der Oberfläche erscheinen läßt, die aber natürlich im Modell selbst gar nicht vorhanden ist.

Vorteil der Sache ist, daß man Oberflächen plötzlich mit zusätzlichen Eigenschaften versehen kann und trotzdem ein Objektmodell mit sehr wenigen Eckpunkten (Polygonen) verwenden kann - wobei das aufwendige Berechnen zusätzlicher Geometriedaten den Aufwand beim BumpMapping deutlich übersteigen würde, weshalb dieses Vorgehen einen Geschwindigkeitsgewinn bedeutet.

Die Dungeonwände aus Ziegel etc. bei Doom und Co sind i.a. BumpMapped. Ebenso Einschußlöcher oder Planetenoberflächen.

Noch wichtiger ist die Benutzung im Rahmen des sogenannten Normal-Mapping [WikiP,d], womit man die Komplexität einer Spielfigur oder eines anderen Modellobjektes drastisch reduzieren kann. Es ist sowas wie ein vorweggenommenes Bump-Mapping. Dabei berechnet man die Unterschiede zwischen einem hochauflösenden Modell und einem Modell vom gleichen Objekt mit definierter geringerer Polygonzahl, die man als "Höheninformation" in einer Bump-Map ablegt. Beim Darstellen verwendet man dann immer das Modell mit den wenigen Polygonen, d.h. schnell berechenbar, und modifiziert es immer(!) mit der vorberechneten Map. Man bekommt ein Endergebnis, was optisch so aussieht, wie das hochauflösende Modell - nur VIEL schneller im Raum zu berechnen ist.

.

Topic: Werbung

https://friesland-porzellan.de/utah-teekanne

Topic: Frustum und Frustum-Culling und so ...

Eine Sache, die ganz gut wichtig ist, ist noch offengeblieben. Nämlich, wie das Festlegen des "Sehfensters" üblicherweise funktioniert und damit einhergehend der Begriff des Frustum-Cullings.

Wir sind damit also wieder eine Ecke weiter vorn in der Grafikbearbeitung gelandet - und zwar an der Schnittstelle zwischen Weltkoordinaten bzw. Kamerakoordinaten und deren Abbildung auf die Bildschirmkoordinaten. Das ist also vor der Scan-Conversion, vor dem Rasterizer, vor dem Shading und Lighting und vor dem Texturieren.

Ganz oben ist das was nun kommt schonmal angedeutet worden - als ein Bild, bei dem eine vordere und eine hintere Ebene festgelegt haben, welche Objekte überhaupt gezeichnet werden sollen.

Diese Ebenen bezeichnet man als front und back oder als near und far oder als nah und fern.

Die Idee dabei ist, daß man alles, was zwischen den beiden Ebenen liegt, zeichnet und alles andere - davor und dahinter - wegläßt.

Was dort aber noch fehlt sind die seitlichen Begrenzungen. Die könnte man nun auch einfach per Abfrage von maximalen und minimalen zulässigen X bzw. Y Werten festlegen (was auf kleinen Rechnern sehr sinnvoll sein kann).

Die elegantere Variante ist, eine Art Sehfenster einzurichten und für dieses weitere Grenzen festzulegen. Dabei stellt man sich vor, daß man von vorn auf die vordere Ebene schaut - die near Ebene. Dabei wird für diese eine X-Ausdehnung mit einem xmin (links) und einem xmax (rechter Rand) festgelegt, ebenso ein ymin (unten) und ymax (oben); oder auch left, right, top, bottom. Da der Abstand zum Betrachter durch die Ebene selbst festliegt (quasi der Z-Wert der near Ebene), ergibt sich dadurch ein Strahlenverlauf über die äußeren Ecken wie im Bild.

Da die hintere Ebene auch bereits durch die Tiefe festgelegt wird, ergeben sich ihre äußeren Eckpunkte automatisch aus dem Strahlenverlauf. Würde man jetzt die near Ebene weiter zum Betrachter hin setzen, würde automatisch die hintere Ebene größer werden und andersherum.

Die sich so ergebende geometrische Figur zwischen den beiden Ebenen und ihren Verbindungen an den äußeren Ecken sieht aus wie eine gekappte Pyramide - nämlich ein Pyramidenstumpf, auf englisch: Frustum.

Man hat auf die Art ein Sichtfenster in die Welt definiert, was relativ flexibel ist (Verschieben der Ebenen) und klar definierte Grenzen aufweist, Vorder- und Rückseite + 4 gleichartige Seitenflächen.

Nun kann man damit zwei Sachen machen:

• entweder man testet alle Objekte seiner Welt gegen diesen Pyramidenstumpf - und alles was außerhalb liegt wird überhaupt nicht weiter betrachtet; nur die Objekte, die im Frustum liegen, werden an die Zeichenroutine geschickt und vorher noch mit einer Projektionsmatrix umgerechnet
• oder man rechnet alle (!) Objekte mittels einer sogenannten Projektionsmatrix um, die das Frustum beschreibt, und während der Umrechnung werden die Vektoren der Objekte so "verzerrt", daß man hinterher ganz einfach feststellen kann, ob sie innerhalb des Frustum liegen, oder ob doch außerhalb

Variante 1 hat den Vorteil, daß nicht alle 3D-Daten durch die Stufe mit der Matrix müssen und insbesondere, wenn dieser Teil in einer Hardware ausgeführt wird, die aber mit einem langsamen Bus angebunden ist, wird es sinnvoll sein, vorher solche Tests zu machen.

Diese können dabei auch durchaus sehr grob ausfallen. Etwa indem man Objekte aus der Welt mit einer zusätzlichen Kugel "umhüllt", die zwar zum Modellobjekt gehört und dieses vollständig einschließt, aber nie gezeichnet werden soll, sondern nur für diesen Test benutzt wird. Dadurch kann man einfach die Kugel gegen die Frustum-Grenzen testen und wenn sie komplett außerhalb liegt, muß von dem Objekt gar nichts zur Grafikkarte geschickt werden.

Wie das "in echt" aussieht, kann man sich hier ansehen (gut lesbares Pascal):

https://wiki.delphigl.com/index.php/Tutorial_Frustum_Culling

Man sieht also hier schon, daß das Frustum irgendwie zwei Funktionen hat - zum einen ist es Auswahlkriterium für dargestellte Objekte, zum zweiten wird es diese aber auch umrechnen, mittels Matrix, entweder alle oder nur einen Teil.

Das Umrechnen ist dabei eigentlich ein zweistufiger Vorgang. Zunächst wird das Frustum auf ein standardisiertes Format gebracht - einen regelmäßigen Pyramidenstumpf mit einem Quadrat als Grundfläche. In einem zweiten Schritt wird dieser dann noch so umgerechnet, daß der gesamte Raum innerhalb der gekappten Pyramide so verändert wird, daß sich am Ende ein Würfelvolumen ergibt. Die vordere (near) Ebene wird also "aufgezogen" und zwar bis sie gleiche Größe wie die "far" Ebene hat. Ebenso alle Punktebenen zwischen near und far. Am Ende wird der Raum auf einen Koordinatenraum zwischen -1 und +1 für alle drei Achsen umgerechnet sein. Man erhält so einen Bildraum, dessen Vordergrund vergrößert wird und der nun nicht mehr schräge Seitenflächen hat, sondern schöne "gerade" Ebenen. Und die kann man prima abtesten.

Gleichzeitig erhält man so eine Projektion, die dem menschlichen Sehmodus nahekommt.

Die vordere linke Würfelecke ist dann die (-1,-1,-1) die hintere obere eine (1,1,1).

Wenn man den Test auf "im Raum enthalten" erst jetzt macht, fragt man einfach nur alle Vektoren ab, ob sie in irgendeiner Koordinate kleiner als ABS(1) sind, wenn ja, hat er zumindest Anteil am Raum des (vorherigen) Frustums und muß daher komplett oder teilweise gezeichnet werden.

Einziger Nachteil ist, daß die Matrix zum Umrechnen relativ komplex ist - was aber nichts macht, da man diese ja nur einmal ausrechnen muß (wie bei den Rotationsmatrizen) und dann mit fixen Werten für sämtliche Vektoren benutzen kann.

Neu errechnen muß man sie natürlich bei Kamerafahrten oder bei Änderungen des Sehfeldes.

Und so sieht das aus:

Dabei stehen n für "near" und f für "far" - also die beiden Ebenen bzw. deren Z-Werte. Das andere sind die Begrenzungen des Sichtfensters in der near Ebene.

Und wieso ... - nun das ist relativ unanschaulich, aber wird

hier https://www.ece.ubc.ca/~saifz/eece478/course/viewingin3d.pdf

oder hier http://www-lehre.inf.uos.de/~cg/2006/skript/node115.html

oder hier https://www.songho.ca/opengl/gl_projectionmatrix.html

relativ ordentlich erklärt. Dabei muß man beachten, daß bei der zweiten (deutschen) Erklärung, der Würfel nicht auf -1 bis +1 normiert wird, sondern auf 0 bis 1, weshalb manches anderes aussieht. Dafür sind die Skizzen ganz brauchbar. Ich finde Version 1 am verständlichsten, leider nur in Englisch (Seite 7-10).

Am Ende läuft es auf verkappte Strahlensätze hinaus ... also so Sachen wie: das Verhältnis zweier bekannter Strecken ist auf zwei weitere direkt übertragbar, wenn sie im gleichen rechtwinkligen Dreieck liegen - und bedeutet, daß man X und Y Werte von Ebenen, die zwischen near und far liegen im gleichen Verhältnis verändern kann und so ihre neue Position im Würfel findet, und damit solch eine Ebene also "aufzieht".

Die Multiplikation mit einem einzelnen Vektor geschieht wieder ganz genau wie oben schon beschrieben.

Eine Sache ist dabei wichtig - der Z-Wert wird nicht nach diesen Strahlensatz-Verhältnissen geändert, weshalb sich die Z-Werte nicht gleichmäßig verteilt verhalten. Immerhin liegen sie aber ebenfalls in einem Bereich zwischen -1 und +1. Und das wiederum erlaubt eine ganz besondere Art zu entscheiden, wie und ob die Pixel letztlich gesetzt werden.

Dies ist die Voraussetzung für die Benutzbarkeit eines Z-Buffers.

Eine Sache ist evtl. aber jetzt schon klar: Z-Werte größer 1 oder kleiner -1 wird man wohl gar nicht zeichnen müssen - sie liegen ja hinter der hinteren bzw. vor der vorderen Ebene des Frustums, welches jetzt zum Würfel geworden ist.

Topic: Z-Buffer

Eine echte Problematik der 3D Geschichten ist die Sache mit der Frage:

Wie kommt die Tiefe ins Bild ?

Ein paar Lösungen sind oben schon immer mal erwähnt worden. So ist es zum Beispiel kein ganz schlechter Gedanke, einfach alle Objekte von hinten nach vorn durchzusortieren und dann entsprechend, d.h. hinten beginnend, übereinander zu zeichnen. Sowas nennt sich "Painters Algorithm". Das erfordert, könnte man denken, einen zusätzlichen Sortierschritt - und das ist meist auch so. Letzteres muß aber evtl. gar nicht sein, es kommt nämlich auch ein bißchen darauf an, wie man seine Objekte im Raum "verteilt" hat. Das ist insbesondere auf Rechnern ohne FPU und ohne viele Megahertze so ein Modus, der ganz sinnvoll sein kann - indem man einfach für jedes Objekt einen eigenen Korridor in der Tiefe vorsieht, in dem sich kein anderes Objekt bewegen darf; in dem Fall fällt der Sortierschritt dann auch weg, weil die Tiefe der Objekte immer erhalten bleibt (nur ums Bild Herumdrehen darf man sich selbst dann nicht).

Aufwendiger ist, wenn man alle Überlappungnen tatsächlich berechnet und die überlappten Dinge einfach ausläßt. Dabei ist das Problem gar nicht so sehr, daß das rechenaufwendig ist, vielmehr ist der Rechenaufwand selbst überhaupt nicht vorhersagbar - es kommt halt darauf an, wieviele Überlappungen auftreten - mit wenigen ist das sehr schnell, bei einem Blickwinkel mit vielen ist das sehr langsam. Und das heißt, daß man immer "Reserverechenleistung" haben muß, um das abzufangen. Für "Real-Time-Graphics" - z.B. Games - eigentlich völlig ungeeignet.

Eine Idee, die quasi beides ermöglicht - schnelles Zeichnen ohne aufwendiges Vorsortieren und relativ definierte benötigte Rechenzeiten - ist der Z-Buffer.

Offiziell wurde dieser "erfunden" von Edwin Catmull (WikiP), Mitgründer von Pixar und sicher einer der wenigen Leute, die per se Mathematik mach(t)en und trotzdem einen Oscar bekommen haben, oder in diesem speziellen Fall sogar drei. Aufgeschrieben in Edwin Catmull: A Subdivision Algorithm for Computer Display of Curved Surfaces. Dissertation, Report UTEC-CSc-74-133, Computer Science Department, University of Utah, Salt Lake City 1974, was man sich hier (Volltextlink) anschauen kann, ab Seite 32 (nicht die vom PDF Seitencounter). Dabei hat der Text selbst ein ganz anderes Thema, das ist da nur Zusatz - wird aber schon für alle Bilder, ab Seite 70 (und ganz am Ende nochmal in schöner), benutzt.

Ein gewaltiger Vorteil ist, daß man damit ein ordentlich nach Tiefe aufgemaltes Bild bekommt, ohne sich darum kümmern zu müssen, irgendeine Form von Reihenfolge der Daten zu berücksichtigen, die man zeichnen möchte. Das macht der Z-Buffer automatisch richtig - er ist also SEHR bequem.

(Vorsortieren schadet aber natürlich trotzdem nicht.)

Der große Nachteil: das Teil braucht Speicherplatz - und nicht zu knapp.

Die Idee dahinter ist nämlich, daß man einfach einen kompletten zweiten Framebuffer einführt, in den man aber nicht Farbwerte hineinschreibt, sondern für jede (X,Y) Koordinate einen Z-Wert.

Wer sich an RAM Preise aus der Zeit der ersten wirklich benutzbaren PC-Grafikkarten erinnern kann, hat evtl. eine Vorstellung, wie ambitioniert das Mitte der Siebziger Jahre gewesen sein muß.

Es wird also in einem Stück Speicher für jede Koordinate ein Z-Wert "mitgeführt". Bei 1024x1024 Pixeln (das ist die "3mal Mega Workstation" Auflösung) benötigt man daher zusätzlich zum normalen Framebuffer (Grafikspeicher) noch 1024 mal 1024 mal benutzte Bitzahl pro Z-Wert an Sonderspeicher. Bei einer 16 Bit Zahl pro Z-Wert sind das also 2 Byte (16 Bit) mal 1Mega = 2 Megabyte, nur für die Zusatzgeschichte mit den Z-Werten.

Als die Rechner im privaten Alltag ankamen, hatte ein Atari MegaST ziemlich genau 1 Megabyte Arbeitsspeicher - für alles. Der normale 500er Amiga 512kB. Und ein Highend-PC sowas um 4MByte. Man sieht also - ausgesprochen ungünstige Ausgangslage für derartige Sachen.

Und so sieht es dann aus

Links ist das Bild selbst zu sehen, mit ein paar Dreiecken.

Rechts ist ein in X und Y-Richtung gleich großer Speicher, in den aber nur die "Z-Werte" geschrieben, werden.

Dabei sind hier unterschiedliche Graustufen unterschiedliche Werte. Hinten im Bild liegen die großen Werte (hier heller), im Bildvordergrund werden die Objekt mit den niedrigen Z-Werten stehen (hier dunkel).

Das Bild zeigt auch nur den Endzustand - wenn das Bild fertig aufgebaut ist. Nur wie kommt man nun dahin ?

Einen Anhaltspunkt bieten die beiden Zahlen -1 und 1. Das sind nämlich die beiden äußeren Grenzen, die aus der Berechnung mit dem Frustum und der Umrechnerei auf einen Einheitswürfel sich ergeben. -1 ist ganz vorn, 1 ist ganz hinten. Sie entsprechen daher gewissermaßen den Ebenen, die wir oben mit near und far bezeichnet haben. Alle zu zeichnenden Z-Werte liegen dazwischen. Die anderen sind ja schließlich dem Frustum-Culling zum Opfer gefallen.

Man könnte die natürlich auch gleich so, wie sie sind benutzen. Allerdings sind Operationen auf ganzen Zahlen i.a. viel schneller und u.a. darum werden diese Werte auf Integer (natürliche) Zahlen abgebildet. Man rechnet sie also um auf z.B. 0 bis 65535, wenn man einen 16 Bit tiefen Z-Buffer verwendet, oder auf Werte von 0 bis 16777215, wenn man 24 Bit Z-Buffer Tiefe benutzt.

Während dieser Umrechnerei werden sie auch noch auf eine Art verzerrt, die dazu führt, daß Werte, die weiter vorn im Raum liegen, viel mehr Zahlen zur Verfügung haben, als solche die weiter hinten im Raum sind.

Wichtig ist aber v.a., daß man so für jeden Eckpunkt eines Dreiecks - und nur die werden ja aus dem Weltmodell geliefert - neben X und Y Wert einen Z-Wert mit in die Umsetzung ins 2D Bild mitnimmt.

Die Scan-Conversion wird genauso wie bisher schon gemacht, dabei evtl. ein Shading für die Farbwerte mitberechnet - zunächst für alle Y-Werte und anschließend noch für die X-Werte im Rasterizer. Dabei werden die Farbwerte zwischen den Eckpunkten linear interpoliert - sei es nun einfach nach Gouraud als direkte Farbwerte oder nach Phong als Normalenvektoren.

Und nun kommt der ganze Trick : Mit den Z-Werten macht man es einfach genauso !

Es kommen also für ein einzelnes Dreieck - nun ja, genau: 3 Ecken in der 2D-Verarbeitung an. Also Werte für X und Y wie bisher und nun auch noch Z. Dabei ist das Neue, daß wir uns jetzt erstmals an dieser Stelle überhaupt für den Z-Wert interessieren, ja er wird letztlich sogar aufgehoben, wenn nötig.

Ganz zu Beginn wird dazu der komplette Z-Buffer auf einen Wert gesetzt, der für "ganz hinten" steht. Der Z-Buffer wird initialisiert mit dem Maximum.

Bei 16 Bit ist das also z.B. eine 65535.

Nun kommt ein neues Dreieck in die "Verarbeitung". Dabei werden die Farbwerte wie gehabt berechnet. Und zusätzlich wird für jede Scanline des Dreiecks entlang der Seitenlinien auch noch ein Z-Wert berechnet - ebenfalls durch Interpolation der Z-Werte an den zugehörigen Ecken.

So erhält man für jede Scanline, d.h. also für jeden Span, zwei Z-Werte - einen links und einen rechts an den äußeren Grenzen des Spans.

Und mit diesen geht man dann in den Rasterizer. Der interpoliert ja schon die Farbwerte (bzw. Normalenvektoren (bei Phong)) und nun auch noch für den aktuellen Span in X-Richtung zwischen den beiden äußeren Z-Werten. So wird für jeden X-Wert des Spans ein definitiver Z-Wert ermittelt - abgeleitet letztlich aus den 3 Z-Werten an den Eckpunkten.

Der entscheidende Unterschied zum Zeichnen ohne Z-Buffer ist nun der:

Es wird hier - und zwar ganz kurz bevor der Pixel gesetzt wird - noch nachgeschaut, welcher Wert an dieser aktuellen Stelle (X,Y) schon im Z-Buffer drinsteht.

Wenn da ein Wert vorhanden ist, der größer als der vom aktuellen (noch nicht gezeichneten) Punkt ist, dann bedeutet das ja, daß der aktuelle Punkt weiter vorne im Bild liegen muß - denn hinten im Bild sind ja die großen Z-Werte. Dieser Punkt würde also auf jeden Fall das überdecken, was im Bild evtl. schon vorhanden ist, und auch wenn die Stelle noch leer ist und noch nichts dort gezeichnet ist, wäre er "weiter vorne". In dem Fall würde der Punkt, d.h. das Pixel, also gesetzt. Und das bedeutet, daß man den Farbwert des Punktes in den normalen Framebuffer schreiben darf. Und weil man ja nun an dieser Stelle und an "dieser Tiefe" was geschrieben hat, wird auch noch der Wert im Z-Buffer aktualisiert - der bekommt einfach den Z-Wert vom eben gesetzten Pixel.

Wenn dagegen der Z-Wert des aktuellen Punktes im Rasterizer größer als der an der passenden Stelle (X,Y) im Z-Buffer ist, dann liegt der Punkt natürlich hinter dem was da als letztes in "dieser Tiefe" hineingeschrieben worden ist. Konsequenterweise passiert dann einfach gar nichts - der Punkt wird verworfen und erscheint nicht im Bild - denn da war ja schon was da, was anscheinend weiter vorne im Bild liegt, weshalb man den Punkt im 2D Bild so sowieso nicht sehen könnte.

Wenn man so will, ist das einfach die Anwendung der seltsamen Umsetzung des Bildes von 3D auf 2D mittels Scanline und Rasterizer - nur eben jetzt noch, neben X und Y und Farben und Licht, auch für Z.

Das Sortieren der Tiefenlage entsteht dadurch gewissermaßen "automatisch".

Wer das jetzt zu komplex findet, der versuche mal das folgende Bild zu durchdenken.

Dort soll das hellblaue Dreieck gezeichnet werden. Dieses wird mittig von dem orange-gelben leicht überdeckt.

Dabei ist die Ausgangslage natürlich so, daß das hellblaue Dreieck noch NICHT im Bild ist und auch der Umriß von ihm im Z-Buffer ist natürlich noch NICHT vorhanden. Die obere Bildreihe ist das Ergebnisbild, wenn alles geklappt hat und zeigt im roten Kreis den anzuschauenden Bereich an.

Herausgegriffen ist eine einzelne Scanline, nämlich die, wo die Spitze von dem orange-gelben Dreieck sich befindet. Dabei wird davon ausgegangen, daß das orange-gelbe Dreieck bereits gezeichnet ist. Es sind also die Farbwerte dafür bereits im Framebuffer eingetragen und alle dafür berechneten Z-Werte stehen im Z-Buffer (die kleine graue Ecke),

Aus den Eckpunkten des blauen Dreiecks, was noch nicht zu sehen ist, hat die Scanconversion die Z-Werte genommen und interpoliert, weshalb für die Außenwerte der einzelnen Scanlinie links und rechts je ein Z-Wert bekannt ist. Und die werden nun innerhalb der Linie nochmal interpoliert, so daß für jeden Einzelpunkt ein Z-Wert berechnet ist.

Diese vergleicht der Rasterizer punktweise mit dem Z-Buffer und stellt fest, ob der Z-Wert des Punktes größer (>) oder kleiner (<) als der im Z-Buffer an der Stelle, an die eben dieser Punkt gehören würde, ist. Dort wo das orange-gelbe Dreieck schon gezeichnet ist, liegt der hellblaue Punkt im Z-Wert an einer größeren Position (>) als das orange-gelbe Dreieck, dessen Z-Werte bereits im Z-Buffer stehen. Dort wird darum auch gar nichts gemacht - hellblau liegt hinten.

An den Stellen, wo kein orange-gelbes Dreieck mehr ist, ist dagegen nur noch der Hintergrund. Und der hat ja einen maximal hohen Z-Wert, der seit der Initialisierung im Z-Buffer steht. Dort wird beim Vergleich der potentielle(!) neue hellblaue Punkt einen kleineren Wert haben, und darum wird dann dort ein hellblauer Punkt im Raster und somit in den Bildschirmspeicher gesetzt. Zusätzlich wird der Z-Wert des Hintergrundes im Z-Buffer überschrieben mit dem Z-Wert vom eben gesetzten Punkt und so Z-Buffer und Framebuffer wieder in Einklang gebracht.

Das Schöne dabei ist, daß das für alle Tiefen und alle Überlappungen gleichartig so funktioniert. Es kostet zwar eine zusätzliche Interpolationsreihe parallel zu der von den Farben/Normalenvektoren und man benötigt den großen Extra-Speicher.

Dafür muß man sich aber nicht mehr um Tiefen-Sortiererei und Überlappungs-Sonderfälle kümmern, etwa solche Sachen wie z.B. offene Ringe, in deren Mitte man wieder das Dahinterliegende durchsehen kann. Mit einem Wort, der Z-Buffer hat immer Recht.

Nach langem Z-Buffer Text noch was Versöhnliches (oder Gruseliges?) von Ed Catmull, zumindest aber passend zum generellen Thema

A computer animated hand - Ed Catmull - 1972

.