01.17.12

…functional Nonsense

Posted in Rants at 6:03 pm by Phil

In letzter Zeit höre ich ständig, dass Java Script eine funktionale Programmiersprache sei. Naja, wenn man das von irgenjemand unbedarftem hört ist das eine Sache, hört man das aber von einem hochbezahlten IT Consultant kommt einem schon ein bisschen die Galle hoch.

Liebe Leute: Nur weil eine Sprache higher-order Funktionen hat ist sie noch lange nicht funktional. Da gehört schon ein bisschen mehr zu. Wäre dem nicht so, dann wäre bspw. C# ebenfalls funktional.

Das schlimme an der Sache ist, dass man am Ende nicht mehr geneigt ist fachlichen Aussagen betreffender Personen unbedingt Glauben zu schenken.

10.10.11

RipOff Dungeons

Posted in Projekte at 10:10 pm by Phil

So, ich bin endlich mal wieder dazu gekommen ein bisschen Games zu programmieren. Das Resultat dieser Bemühungen nennt sich RipOff Dungeons und ist ein ziemlich schnell zusammengestrickter Clon von Desktop Dungeons. Der Spieler wählt aus einer von drei Klassen aus und versucht einen zufällig generierten Dungeon zu befreien, indem er den Boss ins Jenseits befördert. Aktuell bin ich gerade bei etwas, was man ungefähr Alpha Version nennen könnte: Die Klassen sind alle spielbar (allerdigns fehlen noch Spezialfähigkeiten), es gibt Dungeons und Monster und wenn man aufpasst kann man sogar gewinnen. Zu tun bleibt:

  • Spezialfähigkeiten für den Dieb und den Zauberer
  • Balancing

Optional könnte ich mir noch vorstellen:

  • Mehr Items
  • Mehr Monster
  • Mehr Tilesets
  • evtl. noch Händler und Geld

Zur Technik:

  • Entwickelt mit C#/.Net 4.0 und XNA
  • Alle Ressourcen, also Grafiken und Sounds hab ich mir aus freien Quellen im Netz zusammengeklaubt
  • Insgesamt sind zwischen 40 un 60 Stunden bislang reingeflossen

Ziel ist, irgendwann in den nächsten Monaten (hoffentlich noch vor Weihnachten) soweit zu kommen, dass es veröffentlichbar ist.

09.05.11

Simple Rasterization (2)

Posted in Artikel & Tutorials at 8:48 pm by Phil

Ich habe mit dem Code der letzten Episode einige Leistungsmessungen durchgeführt und komme mit meinem kleinen Laptop (1.3 Ghz C2D) auf 14000 Triangles/Sekunde. Das ganze ist mit etwas Vorsicht zu geniessen, da die Testsequenz folgendermaßen aussieht:

  • Es wird ein Triangle 300 x gezeichnet
  • Dieses Triangle wird in jedem Frame etwas kleiner
  • Die Startgröße ist der halbe Bildschirm
  • Die Endgröße ist 1 / 100 des Bildschirms

Der Test ist natürlich deutlich verzerrt – in Wirklichkeit dürften wir etwas mehr Triangles pro Sekunde erhalten, da in der Realität die Triangles allesamt relativ klein sind und maximal ein Triangle pro Frame riesig sein dürfte. Nichtsdestotrotz war der letzte Code nicht optimal. Neben einigen Problemstellen die mir heute aufgefallen sind und in vielen Situationen dazu führen dass überhaupt nicht gezeichnet wird hatten wir die Casts von Float nach Int, die uns Zeit gefressen haben. Ausserdem wurden die Triangles by Value übergeben, d.h. es wurden für die Übergabe Kopien angefertigt, die je 3 * Vertices * 3 Komponenten * 4 Byte also 9 x 4 = 36 Byte groß waren. Hier würde eine Referenz oder ein Zeiger dafür sorgen, weniger Speicherbandbreite zu verbrauchen und somit die Leistung zumindest etwas erhöhen.

Der große Brocken ist allerdings die Gleitkommamathe loszuwerden. Gleitkomma ist zwar auf modernen Rechnern vergleichbar schnell wie Integer, aber eben nur vergleichbar. In unserem letzten Ansatz haben wir einen recht guten Job gemacht zumindest keine teuren Rechenoperationen während der Rasterisierung zu durchzuführen, sondern alles was teuer ist aus den Loops rauszhalten und nur einmal zu berechnen. Allerdings haben wir nach wie vor ein bisschen Vektoraddition und Umwandlung von Gleitkomma nach Integer. Letzteres wollen wir nun loswerden. Dazu werden wir sog. “Fixed Point Arithmetik” benutzen. Die Idee dahinter ist es, alle Gleitkommawerte als Integer darzustellen indem der Gleitkommawert bspw. mit 1000 multipliziert wird. So wird aus 1.14 der Integer 1140, ohne das wir Präzision velieren. Das funktioniert dann zumindest für Additionen und Subtraktionen sehr schnell. Wenn wir den “echten” Wert haben wollen teilen wir einfach wieder durch den zuvor verwendeten Multiplikator. Wenn wir uns nocheinmal den entsprechenden Codeteil vom letzten mal anschauen fällt uns etwas praktisches auf:

LineNo = static_cast<int>(left.y);
Pixels = buffer->moveTo (left.x, LineNo);
int lx = static_cast<int> (left.x);
int rx = static_cast<int> (right.x);

Wir haben hier zwar die beiden Positionen left und right, deren Komponenten als Gleitkommawerte vorliegen, allerdings wollen wir hier ja eigentlich immer eine ganze Pixelposition, d.h. wir können jeweils den Nachkommaanteil wegwerfen. Wenn wir nun hergehen und vorher den Multiplikator geschickt wählen, so können wir uns die Division sparen und stattdessen einfach einen Bitshift machen. Das könnte dann folgendermaßen aussehen:

int dir_Lx = static_cast<int> (left.x * 1024.0f);
int dir_Ly = static_cast<int> (left.y * 1024.0f);
int dir_Rx = static_cast<int> (right.x * 1024.0f);
int dir_Ry = static_cast<int> (right.y * 1024.0f);

Diese Zeilen überführen unsere Laufrichtung nach Fixed-Point. Ich habe hier 1024 als Multiplikator gewählt, weil 1024 = 2^10 ist, d.h. auf der Integerseite können wir durch 1024 teilen, indem wir die Zahl um 10 Bits nach rechts shiften. Moment mal: Vorher hatten wir drei Conversions, jetzt sinds aber vier. Ist das nicht langsamer? Nein, ist es nicht. Denn diese vier Conversions können ausserhalb des Rasterungsloops stattfinden. Der Teil, den wir uns vorher betrachtet haben sieht hinterher dann so aus:

LineNo = lefty >> 10;
int lx = leftx >> 10;
int rx = rightx >> 10;
Pixels = buffer->moveTo (leftx, LineNo);

Ich gehe hier davon aus, dass leftx, lefty,rightx jeweils Integervariablen sind, die ebenfalls im Fixed-Point Format vorliegen. Eine entsprechende Anpassung des Renderingcodes läuft ca. 20-25 % schneller als die Gleitkommavariante.

Dieser ganze Artikel liest sich leider etwas abstrakt, allerdings fehlen mir sowohl Zeit als auch Lust ein paar erläuternde Zeichnungen zu schreiben. Ich hoffe irgendwann, wenn alles soweit ist, einfach mal den ganzen funktionierenden und kommentierten Quelltext zu veröffentlichen.

Im nächsten Teil werden wir uns mit dem Thema Texturierung beschäftigen.

08.30.11

Simple Rasterization

Posted in Artikel & Tutorials at 2:03 pm by Phil

Ich habe mich in den letzten Wochen etwas mit dem Thema “Software Rendering” beschäftigt. Ist ja aktuell mit APIs wie DirectX und OpenGL nicht mehr wirklich gefragt, allerdings verspricht die Thematik einiges an neuem Wissen, insbesondere was das Thema Codeoptimierung angeht. Abgesehen davon kommen noch interessante Themen wie “Screen-Space-Transformation” und “Texturing” hinzu. Interessanterweise gibt es gerade was das Thema Rasterisierung angeht verflucht wenig Hilfestellung im Netz.

Das ganze hier soll eine kleine Artikelserie zum Thema Softwarerendering werden – die Zeitabstände sind dabei komplett willkürlich, kommt drauf an, wann ich wie Zeit habe etwas zu schreiben. Nun aber zur Sache Schätzchen :)

Im Kernproblem geht es beim Zeichnen bzw. Rendern von 3d Grafik darum, aus räumlichen Koordinaten (also solchen mit X,Y und Z Komponenten) eine zweidimensionale Abbildung zu erzeugen, die sich nach Möglichkeit auch noch so verhalten soll, wie die “reale Welt”, d.h. wie haben eine projektive Abbildung, bei der Objekte, die weiter entfernt zur Kamera sind optisch kleiner wirken. Mit den mathematischen Hintergründen der 3d Geometrie werden wir uns zu einem anderen Zeitpunkt befassen – stattdessen rollen wir alles von hinten auf und beginnen mit der Frage, wie wir überhaupt etwas zeichnen, d.h. wir gehen davon aus, dass wir ein Objekt bereits in Bildkoordinaten haben und es einfach nur noch auf den Schirm bringen wollen. Okay, welches Setup haben wir?

  • Es gibt irgendwo ein Fenster in dem wir unsere Grafik anzeigen wollen
  • Es gibt irgendwo einen Array, der uns als Backbuffer dient. Konkret wollen wir RGBA in je 8 Bit darstellen können. Daraus ergeben sich 32 Bit pro Pixel. Wir verwenden einen Integer Array, also ein int pro Pixel, bei dem die oberen 8 Bit den Rotkanal darstellen und die unteren 8 Bit den Alphakanal. Wir verwenden ints weil wir so auf einfache Weise komplette Pixel bearbeiten können.

Grundlegendes: Für meinen Code habe ich der Einfachheit halber SDL zum schnellen Öffnen eines Fensters und zur Verwaltung von Buffern verwendet. Der Vorteil dabei ist, dass der Code damit relativ unabhängig vom Betriebssystem wird und wir uns auf den eigentlich interessanten Teil konzentrieren können. Um die einzelnen SDL Surfaces habe ich noch eine kleine Klasse herumgestrickt, die mir ein paar Vereinfachungen beim Zugriff auf die Pixelebene erlaubt. Die Klasse nennt sich Buffer und hat folgendes Interface:

class Buffer
{
    public:
        Buffer(int x, int y);      // erzeugt einen leeren Buffer mit den gegebenen Abmessungen
        Buffer(const char* file);  // erzeugt einen Buffer aus einer Bilddatei
        virtual ~Buffer();
        void lock ();              // Lockt die zugrundeligende Surface um auf die Pixelebene zugreifen zu können
        void unlock ();            // entfernt das Lock.
        int* getPixels ();         // Liefert einen Zeiger auf den Anfang der Pixel, d.h. auf 0/0
        int* moveTo (int x, int y);  // Liefert einen Zeiger auf ein beliebiges Pixel
        SDL_Surface* getSurface () {return Data;}  // liefert die Zugrundeliegende SDL Surface
    protected:
    private:
        SDL_Surface* Data;
        int sizeX;
        int sizeY;
};
für jedes Pixel im Buffer:
  wenn (Pixel im Dreieck):
   Pixel einfärben
  sonst:
   tu nix

In C++/C sähe das dann so aus:

  int sx = buffer-&gt;sx;
  int sy = buffer-&gt;sy;
  buffer-&gt;lock();
  for (int i = 0; i &lt; sy; i++)
  {
    for (int i2 = 0; i2 &lt; sx; i2++)     {     if (Triangle.containsPixel (i2, i))     {         int* pixel = buffer-&gt;moveTo (i2, i);
        *pixel = 0xff0000ff;
      }
    }
  }
  buffer-&gt;unlock();

Sehr straightforward, is aber offensichtlich etwas naiv. Konkret fassen wir hier jedes Pixel im Buffer an. Besser wäre, wenn wir uns nur das Bounding Rectangle des Dreiecks hernehmen und die Pixel dafür prüfen. Das ist insbesondere bei kleinen Dreickecken schneller, bei großen oder langgezogenen haben wir immernoch das Problem, denn im Zweifelsfall müssen wir hier immernoch den ganzen Buffer betrachten. Konkret ist die zu betrachtende Fläche immer *mindestens* doppelt so groß, wie das Dreieck, das wir eigentlich zeichnen wollen. Zu illustrieren ist das relativ einfach, wenn man ein Dreieck auf ein Blatt Papier malt und sich das umschliessende Rechteck dazuzeichnet. Achtung: Wir reden hier immer von Boundingrectangles, die axis-aligned, deren Seiten also parallel zu den Bildachsen sind. Bei passend hingedrehten Rechtecken ist die zu betrachtende Fläche stets doppelt so groß, wie das zugrundeliegende Dreieck. Da aber hingedrehte Rechtecke alles extrem viel komplizierter mache arbeiten wir mit unverdehten Rechtecken, die eben den Nachteil haben, im ungünstigesten Fall ein mehrfaches der eigentlichen Dreiecksfläche zu haben (als Gedankenexperiment: Ein flaches Dreick zwischen links unten auf dem Bildschirm und rechts oben. Das Ganze ist also etwas unpraktisch. Besser wäre, das Dreieck zeilenweise zu zeichnen und in jeder Zeile nur die Pixel anzufassen, die auch wirklich zum Dreieck gehören. Neben der Tatsache, dass wir weniger Pixel anfassen müssen kommt diese Technik auch dem Cachingverhalten der meissten Prozessoren entgegen, die oft versuchen sequenziell Daten in den Cache zu laden, d.h. wenn wir Pixel sequentiell in x-Reihenfolge einfärben sind wir sehr schnell unterwegs. Für diesen Ansatz benötigen wir jeweils den Anfangs- und den Endpixel des Dreiecks in jeder Zeile und können dann zwischen diesen Pixeln ohne weitere Spezialchecks füllen. Die spannende Frage ist nun, wie wir möglichst billig an diese Pixel kommen. Eine Möglichkeit wäre jeweils von der linken und rechten Seite auf höhe der gerade zu rasternden Zeile einen Strahl durch das Bild zu schiessen und zu prüfen mit welchen beiden Seiten des Dreiecks er sich schneidet. Dazu nehmen wir uns die Geradengleichung der Seiten her und lösen nach x auf:

y= mx + c  // – c // : m

(y – c) / m = x

Die Geradengleichungen können wir uns ganz einfach herleiten, gegeben seien 3 Punkte A, B, C, daraus ergeben sich folgende 3 Gleichungen:

f1 (x) = (A.y – B.y) / (A.x – B.x) * x + c

f2 (x) = (A.y – C.y) / (A.x – C.x) * x + c

f3(x) = (C.y – B.y) / (C.x – B.x) * x + c

Die c’s müssen wir uns auch noch irgendwie besorgen und bekommen sie, indem wir nach c auflösen und einen der beiden Punkte einsetzen:

c1 = - ( (A.y – B.y) / (A.x – B.x) * A.x – A.y)

c2 = - ( (A.y – C.y) / (A.x – C.x) * A.x – A.y)

c3 = - ( (C.y – B.y) / (C.x – B.x) * C. x – C.y)

Das ganze hört sich nun zwar nach relativ viel Mathe an, allerdings muss die Bestimmung der C’s nur einmal pro Dreieck vorgenommen werden. Dieser Ansatz ist mathematisch zwar nett aber codemäßig etwas blöde, da wir uns hier ein paar Sonderfälle einhandeln. Erstmal ist die Division durch m in der Formel für den Strahl ungut, da sie immer explodiert, wenn das Dreieck eine Kante hat, die parallel zu einer der Bildachsen ist, denn dann haben wir entweder eine Division durch null (im Falle von Paralleliltät zur X-Achse), oder m = unendlich im anderen Fall. Hinzu kommt, dass wir ja eigentlich keine Geraden, sondern Strecken betrachten, also müssen wir stets beachten, ob sich der Schnittpunkt innerhalb der durch die Dreieckseiten definierten Intervalle befindet und dann relativ umständlich auswählen von wo bis wor wir rastern wollen. Insbesondere der letzte Teil hier ist kritisch, weil er für jede Zeile passieren muss und uns stark ausbremsen wird.

Der meiner Ansicht nach beste Ansatz ist es, direkt an den Kanten des Dreiecks entlang zu laufen. D.h. wir nehmen einen Punkt als Start und laufen an den Seiten die den Punkt einschliessen zu den anderen Punkten. Unsere Schrittweite ist so gewählt, dass wir immer genau eine Zeile weit kommen.Pseudocode dafür wäre:

  Links = A
  Rechts = A
  RichtungLinks = YNorm (B - A)
  RichtungRechts = YNorm (C - A)
  while (Links != B):
    Zeile = Links.Y
    FülleZeile (Zeile, Links.X, Rechts.X)
    Links = Links + RichtungLinks
    Rechts = Rechts + RichtungRechts

Dabei ist “FülleZeile” im Wesentlichen ein For-Loop der unseren Buffer in der Zeile Links.Y von Links.X bis Rechts.X befüllt.
Was passiert da konkret? Wir starten bei Punkt A im Dreieck und wollen den beiden Seiten, die diesen Punkt einschliessen zu den jeweils anderen Punkten dieser Seiten laufen. Wir haben zwei aktuelle Positionen, links und rechts. Für beide Positionen gibt es eine Laufrichtung, nämlich zu jeweils anderen Punkt (d.h. von A nach C und von A nach B). Um sicherzustellen, dass wir immer genau eine Zeile weit laufen wird auf Y=1 normiert, d.h. die Vektoren werden durch Y geteilt. Der Loop läuft nun solange, bis der Linke Referenzpunkt an seinem Ziel, nämlich B, angekommen ist und füllt alle Zeilen dazwischen auf. Der Algorithmus wie oben beschrieben ist noch nicht ganz korrekt, denn irgendwann muss ja auch noch die Seite BC des Dreiecks in Betracht gezogen werden. Hinzu kommt, dass wir auch hier durch Y teilen, was explodieren wird, sobald wir eine Seite haben, die x-parallel ist. Was also tun?

Die Betrachtung der BC Seite ist relativ simpel. Dazu muss lediglich einer der beiden Läufer sein Ziel ändern, sobald er sein erstes Ziel erreicht,d.h. sobald links von A nach B gelaufen ist ändert er sein Ziel auf C, wahlweise auch andersherum, jenachdem, welche Form das Dreieck nun hat. Um das ganze möglichst einfach hinzubekommen müssen wir zunächst sicherstellen, dass immer der gleiche Läufer das Ziel ändern muss, z.B. der rechte. Dies stellen wir sicher, indem wir prüfen welcher Abstand kleiner ist AB oder AC. Der rechte Läufer bekommt den Punkt als Ziel zugewiesen, der näher an A ist. Dann müssen wir im while-Loop nur noch prüfen, ob er sein Ziel erreicht hat, und wenn ja das Ziel ändern. Das sähe dann in C++ ungefähr so aus:

while (left.x != dst1.x && left.y != dst1.y)
    {
        LineNo = static_cast<int> (left.y);
        int lx = static_cast<int> (left.x);
        int rx = static_cast<int> (right.x);
        rasterizeLine (LineNo, lx, rx)
        left  = left  + dir_L;
        right = right + dir_R;
        // Pruefen, ob der rechte Läufer angekommen ist, in diesem Fall
        // neues Ziel setzen
        if (right.x == dst2.x && right.y == dst2.y)
        {
            // Richtung zwischen dem aktuellen Punkt und dem naechsten Zielpunkt
            dir_R = dst1 - dst2;
        }
    }

Nun das einfachere Problem: Sollte eine Zeile x-parallel sein, so lassen wir die Normierung einfach weg. Dieser Speziallfall bedeutet nämlich, dass nur eine Zeile zu rastern ist. Beim weglassen der Normierung passiert folgendes:

  • Beim ersten Schleifendurchlauf wird noch nichts gerastert. Allerdings wird bei der Addierung der Richtungen der entweder links oder rechts sofort der Zielpunkt erreicht.
  • Im Zweitenschritt wird zwischen dem Zielpunkt und dem Punkt auf der anderen Seite gerastert.
  • Da wir beim Zielpunkt angekommen sind wird sofort der nächste Punkt ausgewählt (s.o.) und normal weiter gerastert.

Dieser Ansatz ist insgesamt schon recht flott und hat wenige Sonderfälle. Die vorhandenen Sonderfälle können alle ausserhalb der kritischen Zone abgehandelt werden, sodass der innerste Loop (das, was oben rasterizeLine heisst) erstaunlich simpel ist:

int* Pixels = buffer->moveTo (left.x, LineNo);
int lx = static_cast<int> (left.x);
int rx = static_cast<int> (right.x);
for (i = lx; i < rx; ++i)
{
*Pixels = 0xff0000ff;
++Pixels;
}

Die Einfachheit ist natürlich erstmal auch darauf zurückzuführen, dass wir hier die Pixel einfach in einer konstanten Farbe einfärben. Sobald Shading oder Texturen ins Spiel kommen wird das alles deutlich komplexer.
Was nun natürlich noch etwas hässlich ist, ist die Tatsache, dass wir hier Gleitkommamathe haben und pro Zeile drei Konvertierungen von Gleitkomma nach Integer, die langsam sind. Allerdings sei gesagt, dass ein C-Style Cast wie (int) x nocheinmal deutlich langsamer ist.

Das war der erste Teil dieses Tutorials. Im nächsten Teil werden wir uns mit weiteren Optimierungen und dem Thema Projektion befassen.