Kamera und Pixel

Die Welt besteht aus Dreiecken im Raum, der Bildschirm aus einem Raster von Pixeln. Der Weg dazwischen hat vier Schritte.

1. Alle Punkte aus Sicht der Kamera angeben
2. Punkte auf die Bildebene projizieren
3. Für jedes Dreieck die Pixel bestimmen und einfärben (Rasterisierung)
4. Pro Pixel entscheiden, was vorn liegt (Tiefenpuffer)

Schritt 1: Die Sicht der Kamera

Die Kamera steht irgendwo in der Welt und blickt in eine Richtung. Damit sich leichter rechnen lässt, verschiebt und dreht man die ganze Welt so, dass die Kamera im Ursprung steht und entlang der z-Achse blickt. Das sind die Operationen aus Kapitel 1: erst die Kameraposition abziehen, dann um den Blickwinkel zurückdrehen. Danach ist z einfach die Entfernung in Blickrichtung.

Schritt 2: Projektion

Vor der Kamera steht im Abstand f die Bildebene. Der Bildpunkt eines Punktes P liegt dort, wo die Gerade von der Kamera zu P die Bildebene schneidet. In der Seitenansicht entstehen zwei ähnliche Dreiecke, und der Strahlensatz liefert:

y′ ÷ f = y ÷ z   ⟹   y′ = y · f ÷ z

Für x gilt dasselbe. Durch die Division durch z erscheint Entferntes kleiner: Das ist die ganze Perspektive.

def projiziere(p, f):
    x, y, z = p
    return [x * f / z, y * f / z]

Schritt 3: Rasterisierung

Nach der Projektion kennt der Computer von jedem Dreieck drei Punkte auf dem Bildschirm. Der Bildschirm ist aber ein Raster aus Pixeln, wie du es von der Pixelgrafik kennst. Die Rasterisierung beantwortet zwei Fragen: Welche Pixel gehören zum Dreieck? Und: Welche Farbe bekommt jedes davon?

Frage 1: Welche Pixel gehören zum Dreieck?

Das Verfahren ist schlicht: Der Computer geht alle Pixel in der Nähe des Dreiecks der Reihe nach durch. Bei jedem prüft er, ob die Pixelmitte im Dreieck liegt. Wenn ja, wird das Pixel gefärbt. „In der Nähe“ heißt: im kleinsten Rechteck, das das Dreieck umschließt.

Gestrichelt ist das umschließende Rechteck. Ein kleiner Punkt bedeutet: geprüft, liegt außerhalb. Ein gefülltes Kästchen bedeutet: gehört zum Dreieck.

Wie prüft man „liegt im Dreieck“?

Die Prüfung wird auf eine einfachere Frage zurückgeführt: Auf welcher Seite einer Geraden liegt ein Punkt? Die Gerade von a nach b teilt die Ebene in zwei Hälften. Die Funktion kante liefert für die eine Hälfte positive Zahlen, für die andere negative und genau auf der Geraden null.

def kante(a, b, p):
    return (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0])

Schalte auf „Drei Kanten“: Ein Dreieck hat drei Kanten, a nach b, b nach c und c nach a. Liegt p bei allen dreien auf der Innenseite, ist p im Dreieck. Ist auch nur ein Wert negativ, liegt p außerhalb. Mehr als diese drei kleinen Rechnungen braucht der Test nicht.

Zusammen mit der Schleife über das Rechteck ist das der ganze Algorithmus:

for py in range(y_min, y_max + 1):               # Zeile für Zeile
    for px in range(x_min, x_max + 1):           # Pixel für Pixel
        p = [px + 0.5, py + 0.5]                 # Pixelmitte
        if kante(a, b, p) >= 0 and kante(b, c, p) >= 0 and kante(c, a, p) >= 0:
            setze_pixel(px, py, farbe)

Frage 2: Welche Farbe? Die Textur

Im einfachsten Fall hat das ganze Dreieck eine Farbe. So sieht der Würfel links aus. Eine Kiste aus Holz bräuchte so aber Tausende winziger Dreiecke, nur um die Bretter darzustellen.

Deshalb verwendet man eine Textur. Das ist ein ganz gewöhnliches Bild, das wie ein Aufkleber auf die Dreiecke gelegt wird. Der Würfel bleibt bei 12 Dreiecken, die Einzelheiten stecken im Bild.

Welche Stelle der Textur gehört zu welchem Pixel?

Für die drei Ecken eines Dreiecks ist das festgelegt: Jede Ecke ist an einer Stelle der Textur „festgesteckt“. Diese Stelle wird mit zwei Zahlen (u | v) zwischen 0 und 1 angegeben und zusammen mit der Ecke gespeichert (Kapitel 2).

Ein Pixel irgendwo im Dreieck liegt zwischen den Ecken. Seine Stelle in der Textur ist eine Mischung der drei Eckstellen. Wie stark jede Ecke zählt, hängt davon ab, wie nah das Pixel an ihr liegt. Diese drei Anteile ergeben zusammen immer 100 %.

Probiere drei Stellen aus: genau auf einer Ecke (100 % für diese Ecke), in der Mitte einer Kante (je 50 % für die beiden Ecken dieser Kante) und in der Mitte des Dreiecks (je ein Drittel).

Mit den Anteilen wird gemischt. Sind die Ecken an den Texturstellen u_a, u_b und u_c festgesteckt, dann gilt für das Pixel:

u = Anteil_a · u_a + Anteil_b · u_b + Anteil_c · u_c

Für v gilt dasselbe. An der Stelle (u | v) wird die Farbe aus dem Texturbild gelesen. Das ist die Farbe des Pixels.

flaeche   = kante(a, b, c)
anteil_a  = kante(b, c, p) / flaeche
anteil_b  = kante(c, a, p) / flaeche
anteil_c  = kante(a, b, p) / flaeche

Schritt 4: Der Tiefenpuffer

Bisher wurde jedes Dreieck für sich gezeichnet. In einer Szene liegen aber viele Dreiecke hintereinander, und mehrere können dasselbe Pixel bedecken. Sichtbar sein darf nur das vorderste.

Das fertige Bild ist eine Tabelle: Für jedes Pixel ist eine Farbe gespeichert. Der Tiefenpuffer ist eine zweite Tabelle mit genauso vielen Zeilen und Spalten. In ihr steht für jedes Pixel keine Farbe, sondern eine Zahl: wie weit das entfernt ist, was an diesem Pixel gerade zu sehen ist. Am Anfang steht überall „unendlich weit“.

Die Regel beim Zeichnen lautet: Ein Pixel wird nur dann neu gefärbt, wenn das neue Dreieck dort näher ist als der Wert im Tiefenpuffer. Dann wird auch die neue Entfernung eingetragen.

Die ferne Fläche C wird zuletzt gezeichnet und landet trotzdem hinten. Die Reihenfolge, in der die Dreiecke gezeichnet werden, ist also gleichgültig. Niemand muss sie vorher sortieren.

UNENDLICH = float("inf")
bild  = [[HINTERGRUND for x in range(breite)] for y in range(hoehe)]   # Tabelle der Farben
tiefe = [[UNENDLICH   for x in range(breite)] for y in range(hoehe)]   # Tabelle der Entfernungen

def setze_pixel(px, py, z, farbe):
    if z < tiefe[py][px]:           # näher als alles, was hier bisher gezeichnet wurde?
        tiefe[py][px] = z
        bild[py][px] = farbe

In der Demo hat jede Fläche überall dieselbe Entfernung. Ein schräg stehendes Dreieck hat an jeder Ecke eine andere Entfernung z. Für die Pixel dazwischen wird z genauso gemischt wie die Texturstelle: mit den Anteilen.

Alles zusammen und der Aufwand

Die folgende Szene wird in deinem Browser mit genau diesen vier Schritten berechnet, ohne Grafikkarte. Die Würfel durchdringen sich teilweise. Der Tiefenpuffer löst das Pixel für Pixel richtig auf. Verändere die Zahl der Würfel und beobachte die Zähler.

Was du ablesen kannst:

• Eckpunkte und Dreiecke wachsen genau im Gleichschritt mit der Zahl der Würfel. Doppelt so viele Würfel bedeuten doppelt so viel Arbeit: linearer Aufwand, O(n).
• Geprüfte Pixel hängen davon ab, wie groß die Dreiecke auf dem Bildschirm sind. Viele kleine Dreiecke kosten wenig, wenige bildschirmfüllende kosten viel.
• Verworfene Pixel sind vergebliche Arbeit: Sie wurden berechnet, lagen aber hinter etwas anderem. Je mehr sich überdeckt, desto größer wird dieser Anteil. Kapitel 7 zeigt, wie man Verdecktes gar nicht erst zeichnet.
• Kein Schritt braucht das Ergebnis eines anderen Dreiecks oder Pixels, außer dem einen Vergleich im Tiefenpuffer. Deshalb lässt sich die Arbeit auf sehr viele Recheneinheiten verteilen. Das ist die Aufgabe der Grafikkarte (Kapitel 6).