Figuren aus Dreiecken

Eine 3D-Figur ist eine Hülle aus Dreiecken. Gespeichert wird sie in zwei Listen.

Die Datenstruktur

Die erste Liste enthält die Eckpunkte. Die zweite enthält für jedes Dreieck drei Nummern, die auf Eckpunkte verweisen. Für einen Würfel:

ecken = [[-1,-1,-1], [ 1,-1,-1], [ 1, 1,-1], [-1, 1,-1],     # Nummer 0 bis 3
         [-1,-1, 1], [ 1,-1, 1], [ 1, 1, 1], [-1, 1, 1]]     # Nummer 4 bis 7

dreiecke = [[0, 2, 1], [0, 3, 2],      # Vorderseite: zwei Dreiecke
            [5, 7, 4], [5, 6, 7],      # Rückseite
            ...]                       # insgesamt 12 Dreiecke

Warum zwei Listen?

Benachbarte Dreiecke teilen sich Eckpunkte. Würde man für jedes Dreieck drei eigene Punkte speichern, bräuchte der Würfel 12 · 3 = 36 Punkte. Mit der Indexliste sind es 8. Wichtiger noch: Bewegt sich die Figur, wird jeder Eckpunkt nur einmal umgerechnet. In großen Netzen gehört ein Eckpunkt im Mittel zu etwa sechs Dreiecken.

Warum Dreiecke?

Drei Punkte liegen immer in einer Ebene. Vier Punkte tun das nicht zwingend, ein Viereck kann geknickt sein, und dann ist unklar, welche Fläche gemeint ist. Vierecke werden deshalb in zwei Dreiecke zerlegt.

Vorder- und Rückseite

Die Reihenfolge der drei Nummern legt fest, welche Seite außen ist: Hier gilt: Von außen betrachtet laufen die Ecken im Uhrzeigersinn. Dreiecke, die der Kamera ihre Rückseite zeigen, liegen bei einem geschlossenen Körper immer hinten und werden gar nicht erst gezeichnet. Das spart etwa die Hälfte der Arbeit.

Wie viele Dreiecke braucht eine Figur?

Runde Formen lassen sich mit Dreiecken nur annähern. Die Kugel unten besteht aus S Segmenten rundum und S ÷ 2 Ringen, das ergibt 2 · S · (S ÷ 2 − 1) Dreiecke.

Verdoppelt man die Feinheit, vervierfacht sich die Zahl der Dreiecke: Sie wächst quadratisch, also O(S²). Der sichtbare Gewinn wird dabei immer kleiner. Schalte die Kanten aus und suche den Wert, ab dem du keinen Unterschied mehr siehst.

Wie viele Dreiecke sinnvoll sind, hängt davon ab, wie groß die Figur auf dem Bildschirm erscheint. Ein Dreieck, das kleiner ist als ein Pixel, ist verschwendete Rechenzeit. Hauptfiguren heutiger Spiele haben Zehntausende bis über hunderttausend Dreiecke, eine ganze Szene mehrere Millionen. Kapitel 7 zeigt, wie Spiele für entfernte Objekte gröbere Fassungen verwenden.

Haare und Aussehen

Einzelne Haare zu modellieren wäre zu teuer. Haare bestehen deshalb aus schmalen Bändern, die jeweils eine ganze Strähne zeigen. Auch die Zöpfe der Ritterin bestehen aus solchen Bändern.

Ein Dreieck ist zunächst nur eine Fläche. Damit es nach Metall oder Stoff aussieht, wird ein Bild darauf abgebildet, die Textur. Dafür speichert jeder Eckpunkt zusätzlich zwei Zahlen (u | v), die sagen, welche Stelle des Bildes zu ihm gehört. Wie daraus die Farbe jedes Pixels wird, erklärt Kapitel 4.