Computergrafik – Teil 2

Kommentare (13)

1. #1 Engywuck

   Juli 19, 2012

   klitzekleiner Einwand: nicht jeder Schüler hatte im Mathematikunterricht Vektoren und Matrizen – es gibt außerhalb des Gymnasiums noch andere Schulformen 🙂

   Dennoch ein schöner Artikel. gehst Du zukünftig noch auf Raytracing ein?

   Zum Thema Grafik an sich: Ich hab mal irgendwo gelesen (finde den Link nicht mehr), dass es da bei den allerersten grafikfähigen Rechnern (so in den 1960ern) ein Problem gab: wenn eine Linie gezeichnet werden sollte musste der Hauptprozessor alle Punkte der Linie berechnen und in den Grafikspeicher schreiben. Was bei höheren Auflösungen einfach zu viel Zeit brauchte, die besser für “intelligente” Aufgaben verwendet würden. Also erschuf man einen “dummen” Coprozessor und ließ den hauptprozessor nur noch Start, Winkel und Läge in den Speicher schreiben, der Coprozessor wandelte das dann in die linie um. Aber warum nur Linien? Mit wenig Mehraufwand kann er auch Rechtecke und Kreise zeichnen- also einbauen, das spart zeit beim hauptprozessor. Hmm, aber wir wollen bei technischen Zeichnungen immer wiederkehrend dasselbe Objekt aus mehreren “Primitiven” zeichen, und soooviel mehraufwand ist ja nicht, dem Coprozessor beizubringen, Listen abzuarbeiten, wenn wir schon dabei sind auch mit Rekursion und Verzweigungen. Hoppla, so langsam kann der coprozessor ja fast soviel wie der hauptprozessor, wäre doch geschickt, wenn wir diese Rechenkraft für was sinnvolleres verwenden könnten. Geben wir ihm doch einfach einen “dummen” Prozessor bei, für den er die Linien-Eigenschaften (Start, Länge, Winkel) berechnet und in dessen Speicher schreibt, dann können wir den Grafikprozessor im Rest der Zeit zur Unterstützung bes Hauptprozessors bei wichtigen Berechnungen einsetzen….

2. #2 Sepp

   Juli 19, 2012

   @Engywuck: “gehst Du zukünftig noch auf Raytracing ein?”

   Raytracing ist, von der Mathematik aus gesehen, noch viel einfacher als der beschriebene Vorgang. Wie der Name schon sagt, wir für jeden Pixel einfach ein Strahl in die Welt geschossen. Dort wo der Strahl ein Objekt trifft, wird berechnet welche Lichtquellen den Punkt ausleuchten (und wie stark) und ggf. weitere Strahlen erzeugt, welche die Brechung oder Spiegelung beschreiben. Die Mathematik ist fast identisch mit der oben gezeigten, man kann allerdings noch ein paar Optimierungen vornehmen. Hinzu kommen dann noch einige Verfeinerungen um das Entstehende Bildrauschen zu entfernen. Genaues sollte aber bei Wikipedia stehen. Raytracer sind wirklich so einfach wie sie sich anhören.

   Noch zu deinem Gedanken mit der ständigen Wiederentwicklung der Grafikprozessoren: Das wird so nicht passieren, da CPU und GPU grundsätzlich verschiedene Konzepte haben. Eine CPU ist gut darin Aufgaben sequentiell zu erledigen und wild in Programmen hin und her zu springen. Also das, was man sich so unter Programmieren vorstellt. GPUs hingegen arbeiten massiv parallel. Und das können durchaus hunderte Aufgaben sein. Im Idealfall handelt es sich dabei um die selben Aufgaben nur mit verschiedenen Daten. Noch besser ist es, wenn diese einfach blind abgearbeitet werden können, ohne dass man auf den Speicher der Grafikkarte zugreifen müsste oder große Sprünge im Code durchführt.

   Natürlich gibt es für die Konzepte auch Namen. CPUs arbeiten nach dem SISD-Prinzip (Singe Instruction Single Data) und GPUs nach SIMD (Singe Instruction Multiple Data). Nur, falls du danach suchen möchtest.

   Sebastian

3. #3 Marcus Frenkel

   Juli 19, 2012

   @Engywuck

   klitzekleiner Einwand: nicht jeder Schüler hatte im Mathematikunterricht Vektoren und Matrizen – es gibt außerhalb des Gymnasiums noch andere Schulformen 🙂

   Deswegen ja nochmal die Erklärung. 😉 Aber ok, ich dachte, dass das in allen Schulformen wenigstens einmal kurz angerissen wird.

   Dennoch ein schöner Artikel. gehst Du zukünftig noch auf Raytracing ein?

   Das war eigentlich der Plan gewesen; ob ich es allerdings wirklich mache, muss ich noch sehen, da es, wie Sepp schon beschrieben hat, wirklich ziemlich einfach ist, zumindest, was die Grundlagen angeht (optimiertes Raytracing ist dann wieder eine ganz andere Sache).

   @Sepp

   Natürlich gibt es für die Konzepte auch Namen. CPUs arbeiten nach dem SISD-Prinzip (Singe Instruction Single Data) und GPUs nach SIMD (Singe Instruction Multiple Data).

   Fast; zumindest moderne x86-Prozessoren haben auch SIMD-Befehlssätze (Stichwort: SSE).

4. #4 Engywuck

   Juli 20, 2012

   wenn Raytracing in der realen Umsetzung so einfach wäre würde es heute eingesetzt werden in Grafikkarten. Meines Wissens ist die Etablierung von Raytracing derzeit aber eher ein Fernziel von intel, weil sie das heute übliche Verfahren mit ihrer Methode, Prozessoren (und Grafikeinheiten) zu bauen nicht wirklich hinbekommen.

   zum Thema Grafikeinheiten und CPU: derzeit sind wir anscheinend wieder im Zyklus der Vereinheitlichung: Stichwort APU (also Grafikkarte auf demselben die wie CPU), und immer stärkere Nutzung der SIMD-Fähigkeit der Grafikkarten (plus deren Spezialbauteile wie Grafikformatdecoder), auch durch zunehmendes Ersetzen der klassischen Algorithmen durch welche, die Mehrfachkerne auszunutzen verstehen (es hat seinen Grund, warum im Consumer-Bereich immer noch weitgehend bei Quadcore Schluss ist) – moderne Grafikkarten sind heute ja auch nur begrenzt SIMD, teilweise haben sie Ansätze zu MIMD, da die vorhandenen (beispielsweise) 640 “Shader” gleichzeitig mehrere Programme “fahren” können (z.B. 2 oder 16 verschiedene).

   Das besprochene war aber ürsprünglich “nur” bei den Großrechnern aufgetreten, mit langen Wegen zwischen CPU und Grafikeinheit und CPUs, die so langsam waren, dass *sehr* große Teile der Rechenzeit für die Grafikdarstellung draufgingen. Bei den ersten Spielekonsolen war das aber auch nicht grausig anders: die “KI” und sonstige “Physik”-berechnungen fanden während des Zeilenrücklaufs statt, da die CPU selber das Farbsignal für den Fernseher modulierte(!). Die allererste Fassung, aus der später der RaspberryPi hervorging (ich warte auf meinen immer noch 🙁 ) hat das ähnlich umgesetzt: https://www.raspberrypi.org/archives/264 Mich juckt’s ja immer noch in den Fingern, das Ding nachzubauen. Wenn ich nur wüsste, wozu 😉

5. #5 Marcus Frenkel

   Juli 20, 2012

   @Engywuck
   Das Problem beim Raytracing ist nicht die Umsetzung, sondern die benötigte Rechenkapazität – die ist bedeutend höher als bei der Rasterisation, weswegen es in aktuellen Produktionen nicht eingesetzt wird.

   Mich juckt’s ja immer noch in den Fingern, das Ding nachzubauen. Wenn ich nur wüsste, wozu 😉

   Darum. Reicht das nicht? 😉

6. #6 Sepp

   Juli 21, 2012

   Meiner Meinung nach sind die SIMD-Fähigkeiten von CPUs aber schon sehr stark beschränkt sind. Eigentlich sind sie auch nur zu gebrauchen, wenn man so wenige Operationen durchführen muss, dass sich das Verschieben auf die GPU nicht mehr lohnt. Der Uhrsprung liegt bei SSE ja durchaus im Bereich der Spieleentwicklung und optimierung von Operationen auf Matrizen.

   @Engywuck: Marcus hatte es ja schon geschrieben, warum auf normalen Grafikkarten noch nicht auf GPUs gesetzt wird. Es gibt aber bereits einige Projekte, in denen Spiel zum Testen auf Raytracer umgestellt werden. Und auch die siggraph hat jedes Jahr etwas Neues.

   Das großartige an Spielen mittels Raytracern ist übrigens nicht nur die gute Grafik (wenn man es richtig macht), sondern auch die enorme Menge an zeichenbaren Daten. Der momentane Ansatz, Rasterisierung über Polygone bzw. Dreiecke, hängt stark von der Anzahl der zu Zeichnenden Elemente ab. Wenn du n Dreiecke im Sichtfeld hast, dann müssen diese alle gezeichnet werden, damit Verdeckung und Transparenz korrekt dargestellt werden.

   Verwendet man hingegen einen Raytracer, dann verringert sich die Komplexität sprughaft. Statt n Objekte müssen jetzt nur noch für jeden Pixel k*log(n) Objekte betrachtet werden, wenn man die Daten geschickt strukturiert. k kann dabei beliebig groß (aber üblicherweise konstant) werden, um so Reflektionen, Brechungen und das Einfallende Licht zu berechnen. Und hinzu kommt, dass man dies für jedes Pixel im Bild parallel machen kann. Transparenz und Verdeckung ergeben sich zusätzlich von ganz alleine.

   Wenn also irgendwann ein Prozessor mit einigen Tausend/Zehntausend spezialisierten Kernen bereit steht, dann kann man Spiele mit nahezu beliebiger Detailtreue erstellen. Und das ganze noch mit allen möglichen visuellen Effekten, welche einem fast geschenkt werden. Wenn die Entwicklung der Grafikkarten so weiter geht, wird dies in den nächsten Jahren sicher auf uns zukommen.

7. #7 haarigertroll

   Juli 21, 2012

   Sagt Euch die “Unlimited Detail”-Engine was? Die versprechen ja fast beliebige Detailauflösung auch auf mäßig leistungsfähiger Hardware mit einer Art Voxeldarstellung und intelligenten Suchalgorithmen.
   Mich würde nur mal interessieren, ob das wirklich so funktionieren kann, oder ob das nur Trickserei ist um Investoren anzulocken.
   Mir ist jedenfalls aufgefallen, dass in den Demos immer nur statische Objekte und Szenen dargestellt werden, angeblich weil es an Animationsdesignern fehlt…

   Was meint Ihr? Ist das wirklich so vielversprechend wie es angepriesen wird oder sollte man da eher skeptisch sein?

8. #8 Sepp

   Juli 21, 2012

   @haarigertroll: die versprechen viel haben aber noch gar nichts geliefert. Ich bin mir aber nicht sicher, ob die Entwickler nicht wissen was sie tun und mit irgendwelchen Buzzwords um sich schmeißen oder ob das ganze einfach nur Wichtigtuerei ohne Inhalt ist. in diesem Beitrag wird es eigentlich ganz gut erläutert: https://notch.tumblr.com/post/8386977075/its-a-scam

9. #9 haarigertroll

   Juli 21, 2012

   @Sepp: Danke für den Artikel! Das mit den sich wiederholenden Strukturen ist mir auch aufgefallen, aber es ist schön, das ein bisschen ausführlicher zu lesen.
   Außerdem hätte es mich ja schon sehr gewundert, wenn so eine kleine Klitsche einfach mal die gesamte Computergrafik-Entwicklung der letzten 20 Jahre über den Haufen geworfen hätte!

10. #10 7tupel

    August 3, 2012

    @Sepp

    Meiner Meinung nach sind die SIMD-Fähigkeiten von CPUs aber schon sehr stark beschränkt

    Das würde ich so nicht unterschreiben. Natürlich stimmt es, dass der Grad der Parallelisierung in einem Vektorrechner wie man ihn auf der GPU hat deutlich größer ausfällt (aktuelle Konsumer Grafikkarten im vertretbaren Preissegment kommen da schnell auf 1300 Kerne und mehr). Trotzdem ist der Performanceboost den man mit SSE erreichen kann enorm:
    Als Beispiel musste ich anfang des Jahres für die Uni einen Sobelfilter implementieren. In reinem C ist das schon recht fix. Meine Implementierung in Assembler mit SSE war trotzdem noch 28mal schneller als die (optimierte!) C Variante. Mit Hilfe von SSE kann man einerseits vier Pixel gleichzeitig berechnen und man kann den Speicherzugriff deutlich optimieren, indem man unter Berücksichtigung der Cachebreiten der CPU gleich mehrere Bildzeilen “vorladen” kann. Hierdurch fallen Speicherzugriffe weg, die hier wie so oft das Bottleneck sind.

    Das Grundprinzip von Raytracing ist wie schon gesagt wurde tatsächlich sehr einfach. Trotzdem kann man hier beliebig komplexe Algorithmen verwenden die alles andere als trivial sind. Beispielsweise sind quasi alle Computergenerierten 3D Effekte die man heute im Kino sieht mittels Raytracing gerendert, da die Bildqualität um ein vielfaches besser ist als bei klassischer Rasterisierung. Und diese Effekte machen heute oft einen Großteil des Budgets bei Filmproduktionen aus, alleine schon weil es oft Tage dauert eine Sequenz zu rendern die nur ein paar Sekunden dauert und nur im seltensten Fall ist nach dem ersten Rendern alles so wie es sein soll.
    Das Problem dabei ist die schon angesprochene Komplexität: In einem dummen Raytracer müsste man für jedes Pixel jedes Objekt der Szene prüfen, ob dieses auf dem Pixel abgebildet wird. Das kann man durch geschickte Datenstrukturen (z.B. Octree, BSP/k-d-Tree) deutlich beschleunigen (Größenordnung 1 Million zu nur 30 Berechnungen).
    Aber um ein Photorealistisches Bild zu erhalten muss man auf sehr komplexe Beleuchtungs und Schattierungsmodelle zurückgreifen, die wiederum einen hohen Berechnungsaufwand mit sich bringen(und andere Sachen wie Oversampling etc.).
    Nehmen wir als Beispiel eine Szene mit genau 1 Mio Objekten und einer Bildauflösung von 1920×1080 Pixeln. Wenn wir annehmen das für jedes Pixel genau 30 Schnittests durchgeführt werden müssen, dann kommen wir auf 1920*1080*30 = 62.208.000 Berechnungen. Wenn wir den super optimalen und völlig realistätsfremden Fall annehmen, das jede Berechnung genau 1 Mikrosekunde dauert (dauert in der Praxis deutlich länger wenn man wirklich gute Bilder haben möchte), dann kommen wir darauf das es 62,2 Sekunden dauert um unser Bild zu berechnen. Von Echtzeit ist das ganz schön weit weg.
    Ich entwickel aktuell an einen simplen Raytracer der mittels CUDA auf der GPU rechnet und im Idealfall Bilderzeugung in Echtzeit ermöglicht. Trivial ist das leider nicht.
    Die Projekte Echtzeit Raytracing für Computerspiele zu ermöglichen die es an verschiedenen Universitäten (und mit Sicherheit auch bei den GPU Herstellern) gibt sind meines Wissens nach leider alle noch nicht Praxistauglich, da wohl die wenigsten Leute zu Hause Massiv Parallele Systeme mit mehreren tausend Cores haben 😉 Aber da wird sich in den nächsten Jahren einiges tun.

11. #11 ahmkay

    August 9, 2012

    Sehr schöner Artikel! Jetzt versteh ich endlich was die ganze Matrix-Rechnerei in der Schule sollte 😉
    Freue mich schon auf Teil 3!

12. #12 Compuholic

    August 15, 2012

    Trägt zwar nicht unbedingt zum Verständnis der Sache bei aber für alle, die es interessiert können das ja mal genauer z.B. bei Wikipedia nachlesen.

    In der Praxis werden normalerweise nicht direkt kartesische 3D-Koordinaten verwendet sondern homogene Koordinaten. Das sind 4D-Koordinaten und natürlich verwendet man dann auch 4×4 Matrizen für die Transformationen. Der Vorteil ist, dass man mit 4×4 Matrizen ein paar Dinge machen kann, die mit 3×3 Matrizen nicht so einfach sind wie z.B. Translationen. Mit 3×3 Matrizen kann ich keine Translation im dreidimensionalen darstellen. Mit einer 4×4 Matrix schon.

    Der Vorteil ist, dass man in homogenen Koordinaten alle Transformationen durch Matrixmultiplikationen darstellen kann.

13. #13 Marcus Frenkel

    August 16, 2012

    @Compuholic
    Das ist natürlich richtig (führt nur für einen allgemeinen Überblicksartikel zu weit). Quaternionen wäre in dem Bereich ja auch noch so ein Thema…