Drop your Files!
Drop or select Files here
0%
Dateien
Aktuelle Datei
Optionen
Diese Warteschlange
EXIF Daten löschen
Zufälliger Dateiname
Große Bilder auf 1080p verkleinern

Nutzer-Einstellungen (Anmeldung erforderlich)
Upload automatisch beginnen
Speichern
Abgeschlossene Uploads

Statistiken

stats
Hits: 1599303
Visits: 274313
Gesamte Querys: 18524976
Gesamte Renderzeit: 43890.2 sek
User: 23

Zufallsspruch

stats
Um die Bösen gewinnen zu lassen, reicht es schon aus, das die Guten nichts tun.
von Lukas
01.10.12
Immer wieder werden Videos oder Bilder veröffentlicht, die alle Leute ins Staunen versetzen. Mit Schlagworten wie "Revolution der der 3D-Grafik" oder "Spiele-Engine der Zukunft" werden die Beiträge noch aufgemotzt, um den gewünschten OHA Effekt zu bekommen.

Bekannt sind zwei Engines, die Unlimited Detail Software aus dem sonnigen Australien und die Atomontage Engine. Beide basieren auf der selben Technik, die Atomontage Engine ist mir aber wesentlich sympathischer, weil die in ihren Videos nicht so reden, wie auf Verkaufssendern, wenn sie Pfannen anpreisen, in denen nichts anbrennt. "But wait, there is more!"

Die grundlegende Technik erklärt
Was ist das Geheimnis der schönen Grafik, die sogar noch in Realtime laufen soll? Das ist nicht schwer. Beide Engines setzen auf eine große Ansammlung von Voxeln (quasi kleine Teilchen, in diesem Fall die kleinsten Teile in der Engine), die in einem Oct-Tree organisiert werden. Ein Oct-Tree ist kurz gesagt nur eine Methode, um 3D-Volumendaten (wie unsere Voxel) so zu speichern, dass sie für bestimmte Algorithmen sehr schnell zu durchsuchen sind. Weitere Infos sollte man Wikipedia entnehmen können.
Da man nun eine gut sortierte Ansammlung von Voxeln hat, kann man beginnend von der Kamerapositon Linien in den Raum aussenden, das sog. Raycasting. Für diese Linie wird nun berechnet, wann sie das erste mal auf Geometrie bzw. einen der Voxels trifft. Das wird für jeden Pixel auf dem Bildschirm ausgeführt (mit einer jeweils leicht veränderten Linie) und man hat ein fertiges Bild.
Damit das in Realtime funktioniert, haben beide Teams viel Arbeit in die Optimierung des Raycasting-Algorithmus und der effizienten Speicherung der Volumen-Daten gesteckt.

Im Vergleich dazu die bekannte Methode:
In fast jedem Spiel, was man heutzutage sieht, wird die 3D-Szene in Polygonen gespeichert. D.h. drei Punkte im Raum, die ein Dreieck bilden. Dieses Punkte werden mit der Projektionsmatrix (eine Matrix die aus der Position, Ausrichtung und FoV der Kamera berechnet wird) multipliziert, sodass man aus den 3D-Koordinaten Bildschirmkoordinaten bekommt. Zwischen diesen Bildschirmkoordinaten wird eine Textur entsprechend skaliert und angepasst. Alles andere wie Beleuchtung und ähnliches sind Tricks, deren Erklärungen hier definitiv nicht notwendig sind.

Der Vorteil in dem Verfahren der Oct-Tree Renderer liegt auf der Hand: Man kann eine riesige Anzahl an Volumendaten speichern (d.h. extrem viele Details) aber die Komplexität in der Berechnung pro Pixel steigt nur mit der Genauigkeit der Abtastung. Und man bekommt wirklich nur den für den Pixel notwendigen Voxel und braucht keine Sachen zu berechnen, die später nicht mal sichtbar sind. Im Polygon Verfahren hingegen steigt die Dauer des Rendervorgangs Linear mit der Anzahl der Polygonen, d.h. mit der Detailgenauigkeit, weil jedes Polygon berechnet wird.

Das hört sich schön und toll an, wenn man nur diesen Teil der 3D-Grafik betrachtet (und Unlimited Detail bemüht sich unglaublich auch genau diesen Teil hervorzuheben). Aber:

5 Gründe, warum Oct-Tree-Renderer keinen Einzug in die Spiele Industrie haben werden:

1. Speicherplatz: Sie preisen ihre Detailgenauigkeit an und konzentrieren sich bei ihren Präsentationen auf die Tatsache, dass der Rendervorgang sehr schnell geht. Dabei vergessen aber die meisten, dass ein hoher Detailgrad auch eine entsprechende Menge an Details/Voxels/"Atomen" benötigt. Um diese Datenmenge zu bewältigen gibt es unterschiedliche Ideen: Entweder man streamt von der Festplatte (d.h. wenn man einer Region mit der Kamera näher kommt, werden mehr Details aus der Region geladen) oder entsprechend komprimiert (was allerdings zu entsprechender Zeit wieder dekomprimiert werden muss, was Leistung kostet). Bei Unlimited Detail sieht man z.B. prima, dass sie ihre Daten stumpf wiederholen. Die Island-Demo besteht aus kleinen wiederholenden Elementen, die so angeordnet sind, dass es halbwegs schön aussieht. Um Spielewelten mit großer Abwechslung zu gestalten, reichen heutzutage die Speicher nicht aus (die schnellen Speicher wie RAM und VRAM sowieso nicht).

2. Animation/Dynamik: Wie anfangs erwähnt, braucht man für das Oct-Tree Verfahren einen gut organisierten Datenhaufen. Die gute Organisation oder Sortierung muss immer beibehalten werden. D.h. falls ein Objekt (aus vielen vielen Voxeln) verschoben werden soll, müssen die Voxels aus der Ursprungsposition entfernt werden und die Ursprungsposition neu organisiert werden und danach die Voxels an der Ziel-Position eingefügt werden und dort ebenfalls alles neu organisiert werden. Das ist eine Menge Daten-Herumschieberei mit zusätzlichem Organisationsaufwand. Falls dann noch komplette Animationen für z.B. Menschen nach dem Skelett-System dazukommen, müssen Datenhaufen gedreht, skaliert und verschoben werden und das viele Male. Das ist ein riesiger Aufwand, diese Animation zu berechnen und somit auch zu realisieren. Bei Polygonen ist es für den PC dank beschränkter Polygonen-Anzahl wesentlich einfacher. Zudem man noch eine Menge Tricks abwenden kann, um Details hinzuzufügen, die mit animiert werden, aber ohne zusätzlichen Rechenaufwand zu verursachen.

3. Dynamische Beleuchtung: Falls sich jemand mit 3D-Grafik ein wenig auskennt oder zumindest physikalisch Bescheid weiß, dem ist bekannt, dass man zur Beleuchtung vor allem eins braucht: Normalen. Das sind normalisierte Vektoren, die senkrecht auf einer Oberfläche stehen. Um die Helligkeit einer Stelle der Geometrie zu errechnen, berechnet man den Winkel zwischen dem Lichtvektor und der Normale. Die Normalen sind bei Polygon-Renderern einfach zu bekommen. Bei Oct-Trees sieht das schon wieder ganz anders aus. Eine Möglichkeit wäre die Normalen direkt in der der Datenmenge des Oct-Trees zu speichern, womit die Datenmenge aber extrem ansteigen würde. Zusätzlich müsste man die Normale dann bei Drehung oder Transformierung eines Objektes immer mit Anpassen, was die Animation wieder rechenaufwendiger machen würde. Die bekannten Demos der beiden Engines haben zwar auch Beleuchtungseffekte, aber die sind alle statisch. D.h. Vorher wurde die Farbe der Voxels schon angepasst, je nachdem wie gut beleuchtet ein Voxel ist. Es gibt zwar Ansätze, das Problem zu umgehen, aber noch nichts Vergleichbares mit dem Polygon-Renderer.

4. Problem, vor denen die Polygon-Technik vor 20 Jahren auch stand: Es gibt in der 3D-Technik eine Menge Probleme. Viele beschäftigen sich mit Beleuchtung (Schatten, Ambient Occlusion, Global Illumination, SubSurfaceScattering und viele mehr) oder anderen Verfahren um ein realistisches Bild zu erzeugen, die nicht alle aufgezählt werden können. Ich bin mir sicher, dass es für alle dieser Probleme auch für den Oct-Tree Renderer eine Lösung gibt. Nur ich möchte zu bedenken geben, dass die 3D-Grafiker der Menschheit auch für den Polygonen-Renderer lange gebraucht haben, um die Lösungen auszutüfteln. Manche Verfahren wird man leicht wiederverwenden können (z.B. SSAO wenn ich mich nicht vertue), andere hingegen werden komplett neue Ansätze benötigen.

5. Hardware: In den letzten Jahren hat sich die Polygonen-Grafik etabliert. Das haben auch die Grafikkarten-Hersteller gemerkt und ihre Grafikkarten perfekt daran angepasst. Grafikkarten haben optimierte Hardware zum Rechnen mit Matrizen und Vektoren und sind auch sonst perfekt auch die Ansprüche der Polygonen-Grafik angepasst. Die Oct-Tree Grafik stellt ganz andere Anforderungen an die Hardware. Dieses Verfahren muss erst beweisen, dass es genug Potenzial hat für die Zukunft, dann werden auch die Grafikkarten- (vllt. sogar CPU-) Hersteller ihre Hardware dafür optimieren.


Ich tue das Oct-Tree Verfahren nicht als Teufelszeug ab. Es ist ein intelligentes neues Verfahren, in das die Teams viel Arbeit gesteckt haben. Es hat für bestimmte Bereiche auch ein enormes Potenzial. Aber aufgrund einiger großer Nachteile, wird dieses Verfahren für die Spieleindustrie nicht nutzbar sein. Und wenn es irgendwann sich so weit entwickelt hat, dass es gut funktioniert, bis dahin ist so viel Zeit vergangen, dass mit Polygonen-Renderern die gleiche Detailgenauigkeit erreicht ist.
Wie anfangs erwähnt, finde ich die Atomontage Engine wesentlich besser als den Versuch Unlimited Detail, weil letztere in ihren Videos stumpf behaupten, das wäre das beste und tollste und alles andere bräuchte man nicht mehr, und dabei die schlechtesten Resultate abliefern. Videos der Atomontage Engine sind zurückhaltend und versuchen schon Probleme dieser Technik zu lösen (wie z.B. das Auto Video, in dem gezeigt wird, dass „simple“ Animationen zu realisieren sind).


Kommentar Kommentare
04.12.12 um 15:41
Lukas sagt:

Hallo Marcel,

erstmal Danke für den Lob und eine dicke Entschuldigung, dass ich erst jetzt antworte und du wohl nie wieder diesen Blog lesen wirst...

Dein Einwand ist leider komplett richtig: Ich schmeiße die beiden Begriffe total durcheinander und als Leser hat man sicherlich den Anschein, als wäre es das selbe.

Zu den einzelnen Punkten werd ich nicht so viel sagen, weil ich vorhabe in naher Zukunft (falls ich Zeit finde) einen 2. Artikel zu veröffentlichen, in dem ich Lösungen für meine 5 genannten Probleme erläutere. Vorallem habe ich einen Interview-Partner gehabt, der total in der Materie steckt (den Programmierer von Atomontage). Daher nur kurz:
1. Mir wurde erklärt, dass durch sehr effiziente Kompressions Algorithmen dieses Problem mit Leichtigkeit zu umgehen ist (wie du schon gesagt hast)
2. Ja, es gibt viele gute Ansätze, ich habe aber von einem sehr interessanten gehört, den du jetzt nicht erwähnt hast. Verschieben durch Offset ist natürlich gut machbar. Ich möchte zu deinen "statischen" Objekten noch anmerken: Ja es gibt viel statisches, aber das ändert sich in modernen Spielen immer mehr. Es geht immer weiter in die Richtung, dass alles Zerstörbar ist. Vegetation jeder weht im Wind usw.. Also viel statisches wird es wohl nicht geben.
3.+4. Jein. Es erfolgt vieles auf der Bildebene, ja. Auch Verdeckungstechniken wie SSAO sind tatsächlich auf Bildebene zu machen, wie du schon gesagt hast. Allerdings gibt es auch immer noch mehrere Techniken die nicht auf Bildebene arbeiten (siehe zb. die Realtime Global Illumination aus Crysis 2).

Ich bedanke mich sehr für die Kritik, du hast in deinen Punkten absolut recht. Geplant war allerdings auch, dass ich wenige Tage nach diesem Artikel einen weiteren Artikel schreibe, der exakt die Vorteile bzw. Problemlösungen aufzählt. Daraus ist dank fehlender Zeit/Motivation nichts geworden.

LG
Lukas

10.10.12 um 16:01
Marcel sagt:

Hallo,

ich bin per Zufall auf deine Seite gestoßen und möchte ein paar Worte zu deinem Artikel/Blog-Eintrag verlieren. Zunächst einmal ist es eine schöne Zusammenfassung für den Laien, die das recht komplexe Thema verständlich darstellt. Allerdings wirfst du durch die Abstraktion für den Laien auch ein paar Begriffe etwas durcheinander, wodurch womöglich Missverständnisse auftreten können. Auch muss ich dir bei ein paar Punkten widersprechen.

Zunächst einmal ist ein Oct-Tree nur eine Baum-Datenstruktur, welche sich zum Speichern räumlicher Daten eignet und ein schnelles Auffinden dieser an einer bestimmten Position im Raum ermöglicht. Außerdem ist es möglich verschieden Detailstufen in dieser Datenstruktur abzulegen, so dass z.B. bei weiter Entfernung von einem 3D-Modell nur eine vereinfachte Version geladen und dargestellt werden muss. Am Anfang des Artikels hört sich die Beschreibung noch korrekt an, aber am Ende könnte der Laie vermuten Voxel und Oct-Tree sind Synonyme, was natürlich falsch ist. Der Vergleich ist also nicht zwischen Modellen aus Oct-Trees und Modellen aus Polygonen sondern zwischen Modellen aus Voxeln/Punktwolken und Modellen aus Polygonen. In vielen Engines werden Oct-Trees nämlich auch dazu verwendet um effizient nur die Teile eines Levels zu laden, die auch auf dem Bildschirm sichtbar sind bzw. in nächster Zeit sichtbar werden können(da in den meisten Fällen nicht der gesamte Level in den Arbeitsspeicher bzw. Videospeicher passt). Zusätzlich kann auch verhindert werden, dass Polygone zum rendern an die Grafikkarte geschickt werden, die nicht auf dem Bildschirm sichtbar sind und ohnehin durch die Rendering-Pipeline verworfen werden.

Zu deinen 5 Punkten die gegen eine Voxel-Engine sprechen:

1. Das Modelle auf Voxelbasis extrem viel Speicher benötigen ist vollkommen richtig. Auch mit immer größer werdenden Festplatten und Arbeitsspeicher wird das weiterhin ein Problem bleiben. John Carmack hat zwar für eine kommende id-Tech-Engine einen sehr effizienten Kompressions-Algorithmus in Aussicht gestellt(durchschnittlich 1,5 Bit pro Voxel), am Ende muss aber trotzdem immer der gerade für das Rendering benötigte Teil der Voxel als Oct-Tree vorliegen. Und eine Dekompression bedeutet immer zusätzlichen Rechenaufwand.

2. Voxel lassen sich nicht so leicht animieren wie Modelle auf Polygon-Basis. Auch dieser Punkt ist richtig. Die von dir genannte Translation(also eine einfacher Verschiebung im Raum) stellt aber kein großes Problem dar. Sie lässt sich durch einfache Offsets beim Suchen in der Datenstruktur verwirklichen, vorausgesetzt das verschiedene Modelle in unabhängigen Quad-Trees abgelegt sind. Eine Rotation hingegen ist weitaus komplexer und nicht so einfach zu realisieren wie bei polygon-basierten Modellen. Aber auch hier gibt es schon effiziente Ansätze mit gewissen Einschränkungen z.B. http://www.youtube.com/watch?v=Tl6PE_n6zTk.
In einem Spiel gibt es allerdings auch viel Geometrie die gar nicht animiert werden muss. Terrain, Häuser, Bäume und andere statische Objekte mit Voxeln darzustellen ist also durchaus ein handhabbares Problem.

3. und 4. Bei den vielen modernen Rendering-Engines erfolgt Beleuchtung, Shadow-Mapping und andere Effekte erst in einem Post-Processing-Schritt, also auf Bildebene. Für diese Techniken ist es absolut irrelevant aus welchen 3D-Modell die benötigten Eingabe-Informationen erstellt wurden. Sie können somit mit minimalen Anpassungen genauso auf Voxel-Modelle angewendet werden wie auf Polygon-Modelle. Ein Voxel-Renderer könnte z.B. ein Farbbild(oft als Albedo bezeichnet) und ein Tiefenbild aus einem Voxel-Model erzeugen. Aus dem Tiefenbild kann anschließend ein Normalen-Bild abgeleitet werden, indem man die Nachbarpixel um einen Pixel berücksichtigt und mit Hilfe der Bildschirmposition und Tiefe der Pixel eine Ebene im Raum errechnet. Zu dieser Ebene kann dann ziemlich leicht die entsprechende Normale ermittelt werden. Mit Hilfe der Informationen Farbe, Tiefe und Normale für jeden Pixel können ohne Probleme die bekannten Effekte wie Beleuchtung, Shadow Mapping, Screen Space Ambient Occlusion, Depth of Field usw. auf die Ausgangsbilder angewendet werden. Auch die Aufwand für die Berrechnung wäre gleich, da diese nur von der Auflösung des zu rendernden Bildes abhängig ist und nicht von der Komplexität der Eingabe-Geometrie.

5. Schon heute können komplexe Voxel-Modelle mit gewissen Einschränkungen in Echtzeit dargestellt werden, wenn GPGPU-Feature(Cuda, OpenCL oder DirectCompute) der Grafikkarte genutzt werden. Von einem vollständig voxel-basierten Spiel(mit ansprechender Grafik) ist das natürlich noch weit entfernt, aber eine Mischung aus Voxel- und Polygon-Modellen ist vorstellbar bzw. in einigen Spielen schon umgesetzt. Falls die Hardware-Hersteller in Zukunft Hardware auf die Darstellung von Voxel-Modellen optimieren(nativer Hardware-Support für effiziente Zugriffe in Oct-Tree-Datenstrukturen, entsprechendes Streaming usw.), könnte das die Verbreitung von Voxel-Rendering deutlich beschleunigen.
Um mal ein bekanntes Beispiel zu nennen: die Cry-Engine 3 verwendet für bestimmte Teile des Terrains Voxel anstatt von Polygonen. Dadurch lassen sich viel besser Höhlen und andere feingliedrige Strukturen darstellen als es mit Polygonen möglich wäre.

Ich hoffe du verstehst die konstruktive Kritik nicht falsch. Wollte dich auf keinen Fall angreifen. Wie gesagt eine sehr schöne Zusammenfassung, die aber leider auch ein paar fachliche Fehler enthält.

Grüße

Marcel

06.10.12 um 09:53
Gast sagt:

Vielen Dank für den verständlich geschriebenen Überblick!


Kommentar schreiben:
Sie haben keine Berechtigung um Kommentare zu schreiben.