Der perfekte Software-Renderer, Teil 1
eine Tutorial-Serie von t.c.p. / Eichel
Anmerkung des Autors: Teile dieses Textes sind schon etwas älter, also lasst euch nicht von den Sprüchen zu aktueller 3D-Entwicklung stören.
1. Einführung
In den letzten Monaten ging der Trend bei 3D-Grafik immer mehr Richtung Hardware-Rendering, und er fängt jetzt erst richtig an. Fast jeder hat inzwischen eine 3dfx-, nVidia- oder Ati-3D-Karte und kann durch die "Unterstützung" von Direct3D schnellere und bessere 3D-Grafik erleben, als sie jemals mit Software-Rendering möglich wäre. Warum also ein Artikel über Software-Rendering? Dafür gab es mehrere Gründe:
a.) Demo-Coder sind keine API-Weicheier. 3D-Karten können nur durch API-Funktionen (SDK's) angesteuert werden. Kein Hersteller ist bis jetzt auf die Idee gekommen, Hardware-Infos über seine Karte zu veröffentlichen (naja, bis auf Matrox, aber auch nur für die Millenium, und die ist ja, wie jeder weiß, in Sachen 3D nicht mal die Zeit wert, den Namen auszusprechen). Durch die APIs wird man als Coder gezwungen, sich auf den Mist zu verlassen, den andere verbockt haben. Das Credo des Demo-Coders lautet immer noch: Selbst ist der Coder. Oder: Wenn man nicht alles selber codet...
b.) Die Hardware ist und bleibt eingeschränkt.
Manche Sachen wie Refraction-Mapping (heißt das so?), Phong-Shading oder
Curved-Surfaces werden von der Hardware nicht unterstützt.
Ebenso kann eine S-Buffer-Engine mit den 3D-Karten von heute nichts
anfangen, da die ihr eigenes Triangle-Setup machen (natürlich würde
sowieso jeder den Hardware-Z-Buffer verwenden, ich brauchte nur ein Beispiel).
Außerdem können sie nur Dreiecke zeichnen, was allerdings kein so
großes Problem ist, wie wir noch sehen werden. Aber immerhin ein
Problem. ;)
c.) Nicht jeder hat's so dick. Es gibt immer noch Leute ohne 3D-Karte. Und wer will denen schon die lausigen Direct3D Software-Renderer antun? Bestimmt keiner. Hehe.
d.) Demo-Compos. Auf vielen Demo-Parties sind immer noch keine hardware-beschleunigten Demos zugelassen, oder es gibt getrennte Compos. Wer dann lieber in der 'richtigen' Competition mitmachen will, braucht natürlich Hardware... ähm, Software-Rendering. ;)
e.) FatMap2 ... ist echt klasse, aber es bleiben trotzdem noch Probleme, z.b. Lücken zwischen benachbarten Faces und diese 'Polygone vs. Dreiecke' Geschichte. Ich bin halt eher für Dreiecke. Tja, und außerdem heißt's "Fast Affine Texture Mapping", und die meisten hätten doch wohl auch gerne einen schicken perspektiv-korrekten Mapper...
Genug Gründe? OK, dann noch ein kurzer Absatz über meine Vorstellungen, wie diese Tutorial-Serie aussehen soll, dann kann's auch schon los gehen.
2. Wie ich's mir vorstelle
Also, ich hab mir das so gedacht. Da ich gerade an einer 3D-Engine schreibe und einige kleine Probleme mit dem Software-Rendering habe, bin ich auf die Idee gekommen, eine Artikel-Reihe wie diese zu schreiben, die das Ziel hat, den möglichst perfektesten Software-Renderer zu designen. Das heißt natürlich, dass ich alleine nicht zu Rande kommen werde, und dazu die die Hilfe des geneigten Lesers benötige. :)
Ich werde in jeder Ausgabe einen kommentierten, möglichst gut lesbaren Source eines Triangle-Renderers vorstellen. Dabei kommen nacheinander Flat-, Z-Buffer-, Texture- und Perspektiv-Texture-Renderer an die Reihe, zusammen mit ausführlichen Kommentaren zu den verwendeten Techniken, aber auch den Problemen, die mir bei der Implementierung aufgefallen sind, und die die Renderer vom Status des Perfekten trennen. Sobald ich mit dem Renderer zufrieden bin, gibt's den nächsten. Ich hoffe jetzt, dass ich ein bisschen Feedback aus euch rausleiern kann, so dass ich vielleicht ein paar Tips kriege, wie ich die Renderer verbessern kann. Im Gegenzug werde ich mir ebenfalls Gedanken machen und alle Verbesserungen in jeder neuen Ausgabe veröffentlichen, damit alle davon profitieren können.
Zum Thema Anspruch: Diese Tutorials sind für fortgeschrittene Coder gedacht, die zumindest schon einmal einen Software-Renderer geschrieben haben und wissen, was es mit den ganzen Steigungen, Prestepping und Offsets auf sich hat. Der Zweck ist, wie schon gesagt, vorhandene Renderer zu verbessern und Optimierungstricks zu lernen, wobei ich nicht unbedingt behaupte, alles zu wissen (ich hab eigentlich null Ahnung, wie sich später herausstellen wird), sondern genauso wie manch anderer noch jede Menge offene Fragen und implementierungsspezifische Probleme habe, die ich gerne mit eurer Hilfe klären würde...
3. Schon geht's los: Allgemeines zu den Renderern
Mir ist schon klar, dass es den universellen Software-Renderer nicht geben kann. Das Adjektiv 'perfekt' bezieht sich nur auf die Bild-Qualität. Ich habe daher folgende Einschränkungen gemacht:
a.) Der hier vorgestellte Code ist bis aufs Äußerste unoptimiert. Die Optimierungsphase ist das Zeitaufwendigste am Coden von Renderern, und soll dem Leser als Zeitverschwendung überlassen werden. :)
b.) C++ is the buzz. Der Compiler muss 32-bittig sein, und sollte x86-Code erzeugen. Mit kleinen Abänderungen müsste diese Einschränkung aber zunichte zu machen sein.
c.) Beim Rendern beschränken wir uns, wie die 3D-Karten auch, auf Dreiecke. Das hat den Grund, dass Dreiecke einfacher und schneller zu rendern und außerdem Polygone mit mehr als 3 Vertices für keine 3D-Engine unbedingt von Nöten sind.
Tipp: Geclippte Polygone einfach triangulieren:
Vertex * v1 = clippedVertices[0];
for (i = 0; i < clippedVertexCount-2; i++) {
Vertex * v2 = clippedVertices[i+1];
Vertex * v3 = clippedVertices[i+2];
Face f = Face(v1, v2, v3);
renderTriangle(f);
}
d.) Es wird nicht im Screen-Space geclippt. Wir wollen sauberen Code, und keinen mit If's vollgemüllten. Clipping gehört in den Object-Space!
e.) Die Span-Renderer (Span = horizontaler Abschnitt des Dreiecks) sind auf 32 Bit Farbtiefe beschränkt, im sogenannten ARGB8888-Modus. Außerdem gehe ich von einem linearen Framebuffer (LFB) ähnlich dem Mode 13h aus, bei dem der Pitch (also die Anzahl Bytes, die man auf ein Offset aufaddieren muss, um in die nächste Zeile zu gelangen) exakt gleich der Bild-Breite mal der Bytes pro Pixel ist. Ein Pixel sieht im Detail so aus:
31 23 15 7 0 aaaaaaaarrrrrrrrggggggggbbbbbbbb alpha rot grün blau
Andere Farbtiefen sind einfach zu implementieren. Echt.
f.) Es wird von folgender Struktur für ein Dreieck (Face) ausgegangen:
struct (oder class) Face {
Vertex * v[3]; // Pointer zu den drei Vertices
long color; // Farbe (ARGB8888)
long * Texture; // Pointer zur Textur
float area; // Flaeche des Dreiecks
};
Und so soll ein Eckpunkt (Vertex) aussehen:
struct (oder halt class) Vertex {
float x, y, z; // World-Space Koordinaten
float sx, sy, sz; // Screen-Space Koord. (sz = 1 / z)
float u, v; // Texture-Space Koord. (0.0...1.0)
long color;
}
Als Parameter wird dem Renderer eine Face-Struktur übergeben. So können Renderer für Texture-Mapping, Gouraud-Shading, etc. allgemein gehalten werden.
g.) Die Texturgröße wird auf 256*256 begrenzt.
h.) Es wird durchgängig mit Floats gearbeitet. Fixpunkt Arithmetik kommt später, hat er gesagt.
4. Der Flat-Renderer
Nichts besonders Aufregendes. Vertices sortieren, Steigungen und Prestepping berechnen, obere Hälfte zeichnen, untere Hälfte zeichnen. Die Methode, durch die Berechnung des längsten Spans
float longest = (y2 - y1) / height * (x3 - x1) + (x1 - x2);
herauszufinden, auf welcher Seite des Dreiecks sich der zweite Vertex befindet, hab ich aus FatMap geklaut.
// Globale Variablen, die vor der Benutzung des Renderers
// gesetzt werden muessen
// Breite des Screens in Pixeln
long g_screenWidth;
// In den Framebuffer werden die Dreiecke gerendert, bevor
// dieser in den Bildschirmspeicher kopiert/geflippt wird
long * g_Framebuffer;
// Globale Variablen, auf die die Span-Renderer zugreifen
// und die von den Renderern gesetzt werden
// Farbe
long g_color;
// Framebuffer-Offset
long g_offset;
// Laenge des Spans
int g_length;
// Haeufig verwendete Inline-Funktionen
inline bool aBiggerB(float a, float b) {
// Vergleicht zwei Floats mit gleichem Vorzeichen, ohne
// die FPU zu nutzen
return (*(long *)&a) > (*(long *)&b);
}
inline void swapVertices(Vertex ** a, Vertex ** b) {
// Vertauscht zwei Vertices (verwendet beim Sortieren)
Vertex * vertex = *a;
*a = *b;
*b = vertex;
}
// Der Renderer
void renderFlatTriangle(Face & face) {
// Zeichnet ein einfarbiges (Flat) Dreieck in den
// Framebuffer
// Pointer auf die Vertices
Vertex * v1 = face.v[0],
* v2 = face.v[1],
* v3 = face.v[2];
// Vertices nach Ordinate aufsteigend sortieren (also
// so, dass v1 der oberste und v3 der unterste Vertex
// ist)
if (aBiggerB(v1->sy, v2->sy)) swapVertices(&v1, &v2);
if (aBiggerB(v1->sy, v3->sy)) swapVertices(&v1, &v3);
if (aBiggerB(v2->sy, v3->sy)) swapVertices(&v2, &v3);
// Screen-Space Koordinaten
float x1 = v1->sx,
y1 = v1->sy,
x2 = v2->sx,
y2 = v2->sy,
x3 = v3->sx,
y3 = v3->sy;
// Integer-Varianten der Screen-Space Ordinaten,
// aufgerundet
int y1i = int(ceil(y1)),
y2i = int(ceil(y2)),
y3i = int(ceil(y3));
// Hoehe des Dreiecks in Pixeln
int height = y3i - y1i;
if (!height) return;
// Farbe des Dreiecks
g_color = face.color;
// Start Offset
g_offset = y1i * g_screenWidth;
// Steigung der linken und rechten Seite
float ldxdy, rdxdy;
// Laenge des laengsten Spans
float longest = (y2-y1) / height * (x3-x1) + (x1-x2);
if (longest < 0) {
// Wenn longest < 0, dann befindet sich v2 auf der
// rechten Seite des Dreiecks
rdxdy = (x2 - x1) / (y2 - y1);
ldxdy = (x3 - x1) / (y3 - y1);
}
else {
rdxdy = (x3 - x1) / (y3 - y1);
ldxdy = (x2 - x1) / (y2 - y1);
}
// Prestep-Faktor fuer subpixel-korrektes Rendering
float prestep = y1i - y1;
// Interpolations-Variablen fuer die linke und die
// rechte X-Koordinate
float rx = x1 + prestep * rdxdy,
lx = x1 + prestep * ldxdy;
// Laufvariable fuer den aktuellen Span
int span;
// Obere Haelfte des Dreiecks zeichnen
if (y1i != y2i) {
// Outer Loop: Alle Spans der oberen Dreieck-Haelfte
// durchlaufen
for (span = y1i; span < y2i; span++) {
int lxi = int(ceil(lx));
int rxi = int(ceil(rx));
g_length = rxi - lxi;
if (g_length > 0) {
g_offset += lxi;
renderFlatSpan();
g_offset += g_screenWidth - lxi;
}
else g_offset += g_screenWidth;
lx += ldxdy;
rx += rdxdy;
}
}
else span = y2i;
// Untere Haelfte des Dreiecks zeichnen
if (y2i != y3i) {
// Neuer Prestep
prestep = y2i - y2;
// Neue Steigung
if (longest < 0) {
rdxdy = (x3 - x2) / (y3 - y2);
rx = x2 + prestep * rdxdy;
}
else {
ldxdy = (x3 - x2) / (y3 - y2);
lx = x2 + prestep * ldxdy;
}
for (; span < y3i; span++) {
int lxi = int(ceil(lx));
int rxi = int(ceil(rx));
g_length = rxi - lxi;
if (g_length > 0) {
g_offset += lxi;
renderFlatSpan();
g_offset += g_screenWidth - lxi;
}
else g_offset += g_screenWidth;
lx += ldxdy;
rx += rdxdy;
}
}
}
// Der Span-Renderer
void renderFlatSpan() {
long * dest = g_Framebuffer + g_offset;
int length = g_length;
while (length) {
*(dest++) = g_color;
length--;
}
}
5. Anmerkungen
Einiges zu den speziellen Merkmalen des Renderers: Da sind zum einen die globalen Variablen, die nicht sehr elegant erscheinen. Hier ist die Frage, ob es effizienter und sauberer ist, diese als Parameter an die Span-Renderer zu übergeben. Ich würde behaupten: Nein. Außerdem ist es so einfacher, die Span-Renderer in externem Assembler-Code zu schreiben.
Weiterhin haben wir ein sehr umfangreiches Triangle-Setup (der Code, der vor dem Zeichnen der ersten Dreiecks-Hälfte ausgeführt wird), und das, obwohl wir bis jetzt bloß Flat-Rendering implementiert haben. Hier wäre es sinnvoll (für dieses Tutorial allerdings zu speziell), einen Renderer zu schreiben, der nicht bloß ein einziges, sondern gleich eine ganze Liste von Dreiecken mit denselben Eigenschaften zeichnet. Da sich diese meist auch Vertices teilen, könnte man den Setup-Code stark optimieren.
Ansonsten bin ich mit diesem (zugegebenermaßen sehr einfachen) Renderer recht zufrieden. Er arbeitet sehr genau, trotz Subpixel-Korrektur ohne Lücken zwischen benachbarten Dreiecken (wie das bei den FatMap-Routinen leider der Fall ist) und ist auch gemessen an dem Aufkommen an Fließkommaberechnungen einigermaßen effizient.
6. Abschied
Dies war der erste Einblick in die zauberhafte Welt des perfekten Software-Renderings, sagte der weiße Hase und: Folge mir, Alice. Beiliegend solltet ihr ein kleines Beispiel-Programm finden, das zum Testen, Rumprobieren und Optimieren verwendet werden darf. Wie schon (oft) gesagt: Wer Anmerkungen zum Code hat, ein besseres Beispiel-Programm weiß oder 300 Gramm Milchschokolade in weniger als 20 Sekunden essen kann, der mailt!
In der nächsten Ausgabe gibt es dann eine geschwindigkeitsoptimierte Version des Flat-Renderers mit Fixpunkt Berechnung und schnellerem Span-Renderer. Außerdem winkt Monsieur Gouraud mit dem Interpolations-Zaunpfahl.
Macht's gut und codet nur, was euch Spaß macht...
t.c.p.
Eichel Demo Delivery Service