Klötzchengrafik

In der vergangenen Woche, eigentlich überwiegend nur Freitag Abend, habe ich mich ein wenig mit Isosurfaces beschäftigt und ein erstes, sichtbares Ergebnis vorliegen. Dabei handelt es sich um die sogenannte Cuberille-Darstellung eines Iso-Modells, welches ich euch natürlich nicht vorenthalten möchte.

Aber zunächst ein wenig mehr darüber, was dies überhaupt ist. Dabei möchte ich auch ein paar Zahlen nennen, um das Ganze näher einzuschätzen.

Als Datenbasis habe ich die Dichtewerte eines Objektes in einem Raster vorliegen, daß 256 * 256 * 256 Zellen enthält. Mit Dichtewerten ist damit ungefähr das gemeint, was ein Computertomograph z.B. bei einer Magnetresonanztomografie (MRT) erzeugt. Mir liegt in jeder dieser fast 16,8 Millionen Zellen also ein Wert vor, der 8 Bit Größe hat und dabei angibt, ob dieser Würfel leer (=0) ist, oder welche Dichte vorhanden ist (>0). Je höher der Wert, desto mehr Material befindet sich in diesem Würfel.

Die einfachste Möglichkeit dies zu visualisieren ist schlicht und einfach für jeden Würfel, der Material enthält, auch einen Würfel zu rendern. Und exakt dies ist auch das, was ich hier gemacht habe. Dies ist nicht schwer. Eine einfache Schleife, die über alle Würfel läuft und den Vertex- und Index-Buffer entsprechend mit Würfeln befüllt. Dabei entsteht aber sofort das erste Problem: ungefähr 4 Millionen Würfel müssten dargestellt werden, allerdings sind davon nur ein Bruchteil sichtbar. Alle innenliegenden Würfel müssen nicht dargestellt werden, da diese durch die äußeren verdeckt werden.

Die Lösung dafür ist der sogenannte „Asymptotic Decider“ von Nielson und Hamann. Dieser Algorithmus, eigentlich für den Marching Cubes Algorithmus entwickelt, filtert etwas vereinfacht ausgederückt alle Würfel aus, die nicht von der Iso-Fläche geschnitten werden die aus den Dichtewerten generiert werden kann. Durch diese wichtige Optimierung konnte ich die Anzahl der notwendigen Würfel zur Darstellung bereits auf knapp 450.000 senken. Die Generierung dauert dadurch nur unwesentlich länger, also eine sehr gute und günstige Optimierung.

Wer jetzt nachrechnet, der merkt schnell, daß bei 24 Dreiecken schnell die maximale Größe des Draw-Aufrufs von knapp über 1.000.000 Primitive gesprengt würde. Eine mögliche Lösung dafür wäre, daß einfach mehrere Draw-Aufrufe generiert werden. Nicht schwer, aber nicht notwendig. Ich habe einfach alle innenliegenden Flächen wegoptimiert. Wenn also zwei Würfel nebeneinander liegen, dann kann man natürlich die Flächen nicht sehen, die zwischen den beiden Würfeln liegen. Auch diese Optimierung ist sehr einfach und schnell und senkt die Anzahl der Flächen um fast 30%.

Übrigens habe ich für die folgende Darstellung, die sich daraus ergibt, noch die Dichtewerte als Graustufen kodiert. Je heller der Grauwert, desto mehr Material befindet sich im Würfel. Dies führt zur etwas seltsamen Darstellung wird im weiteren Verlauf aber noch sehr wichtig werden.

Der ein oder andere wird jetzt sicherlich sofort an Minecraft denken. Ja, das liegt sicherlich nahe, aber das ist nicht das, was ich erreichen möchte. Ich habe schlicht und einfach die Basis für weitere Experimente gelegt. Ich kann den „Cuberille-Algorithmus“ ganz einfach durch andere Algorithmen austauschen. Wo dies hinführen wird? Das werde ich euch in unregelmäßigen Abständen berichten 😉 Das Laden der ca. 16MB an Dichtewerten von Festplatte und das erzeugen des Vertex- und Index-Buffers daraus dauert übrigens ca. 743 Millisekunden. Dabei habe ich weniger auf Geschwindigkeit geachtet, als an Lesbarkeit des Codes. Vermutlich könnte dieser nochmal um ca. 30% beschleunigt werden.

Advertisements

Veröffentlicht am 29.08.2011 in Algorithmen, Random Noise und mit , , , , getaggt. Setze ein Lesezeichen auf den Permalink. 12 Kommentare.

  1. Hi,

    netter Artikel, bin schon gespannt was da noch kommen wird.
    Im 6. Absatz hast du, glaube ich, 12 Dreiecke >pro Würfel< vergessen.

    • Danke, bin auch schon gespannt 🙂

      Dieser Artikel ist aus einem meiner mittlerweile endlosen Versuche entstanden, eine „extrem gute Spielidee“ ™ zu entwickeln 🙂

      Der Hinweis mit den 12 Dreiecken ist sehr gut und ich habe die Stelle sofort korrigiert. Danke sehr. Ich hatte an 12 Flächen á zwei Dreiecke gedacht 🙂

    • So, der nächste Artikel ist auch schon fertig: Marschierende Würfel

  2. Kannst du noch etwas dazu schreiben, wie du die innenliegenden Flächen wegoptimiert hast? Bei mir hat das mit 4 Millionen Würfeln ein paar Minuten gedauert. Ich implementiere zwar jetzt noch ein Octree-Struktur, die den Großteil der Abfragen abfangen sollte, würde mich aber sehr für dein Vorgehen interessieren. Du machst das immer besser 🙂

    • Selbstverständlich kann ich dazu etwas sagen 🙂 Ein Octree ist jedenfalls deutlich zu kompliziert, zumindest für meinen Fall.

      Ich habe ein Array mit 256*256*256 Dichte-Werten (Byte-Datentyp) in einem fortlaufenden Array vorliegen. Das ist deutlich schneller als ein Jagged- oder Multi-Dimension-Array, auch wenn man dann die Position mit 3 Multiplikationen und 3 Additionen anhand der dreidimensionalen Koordinaten errechnen muss. Beim eigentlichen Erzeugen der Würfel gehe ich nun wie folgt vor:

      – dreifach geschachtelte Schleife auf X-, Y- und Z-Achse
      – Prüfung ob Dichtewert > 0
      – Prüfung ob Anzahl der Nachbarn < 6 (bei exakt 6 Nachbarn ist es ein innenliegender Würfel)
      – Loop über alle Seiten des Würfels
      – Prüfung ob ein Seitennachbar vorhanden ist
      – die zwei Dreiecke in das Ziel-Array schreiben

      Sowohl die Indices, als auch die Vertices liegen in kleinen Arrays, über die ich immer wieder loope. Diese dürften komplett im Prozessorcache liegen, also extrem schnell sein. Ich addiere dann nur die entsprechenden Koordinaten bzw. Positionen auf. Das ist eigentlich der Schlüssel zur Geschwindigkeit. Je Würfel erfolgen 12 zusätzliche Lookups in das Daten-Array. Dies führt zu 36 Multiplikationen und 36 Additionen, was eigentlich der Hauptgeschwindigkeitsverlust ist. Evtl. kann man hier noch etwas mit einem kleinen LRU-Cache für die Nachbarn machen. Ich denke mal, daß man diesen Algorithmus noch auf ca. 400 Millisekunden beschleunigen könnte. Dies sollte dazu führen, daß man 96*96*96 Chunks vermutlich innerhalb der Update-Methode ohne Multithreading generieren könnte.

      Aber wie schon im Artikel geschrieben (hab ich doch, oder?): Ich habe nicht auf Optimierung geachtet. Durch Inlining etc. kann man sicherlich noch etwas mehr herausholen. Für mich ist es momentan schnell genug…

  3. Sieht sehr gut aus!

    Weißt du zufällig, wie viel Ram das ganze verbraucht?

    • Natürlich weiß ich das 🙂

      Die Dichtewerte, die von Festplatte geladen werden benötigen exakt 256*256*256 Byte, also ca. 16.8 Megabyte. Daraus wird ein Vertex-Buffer und ein Index-Buffer generiert. Dafür muss kurzzeitig ein entsprechendes Array im RAM aufgebaut werden, daß dann in den Grafikspeicher geladen wird. Der Index-Buffer hat dabei in diesem Beispiel eine Größe von ca. 5.2 Megabyte. Der Vertex-Buffer hat eine Größe von 15.06 Megabyte. Der Peak-Wert liegt also bei ca. 37 Megabyte, die dann geculled werden, sobald die gut 20 Megabyte Vertex- und Index-Daten auf die Grafikkarte geladen wurden.

  4. Wo hast du die Dichtewerte her? Wenn man so was mal nachmachen will wären Beispieldaten interessant.

  1. Pingback: Klötzchenwelt « "Mit ohne Haare"

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: