spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Huh, witzig

Das ist tatsächlich auf eine minimalistische Art ziemlich stylish. Gute Arbeit! Ob Absicht oder nicht, ich finde es gut, dass Du für die Bewegung der Fische das LowRes-Raster verlassen hast. Und wie die kurz 1px breit werden, wenn sie wenden... herrlich :-)

Zitat von »Schrompf«

Das ist tatsächlich auf eine minimalistische Art ziemlich stylish. Gute Arbeit! Ob Absicht oder nicht, ich finde es gut, dass Du für die Bewegung der Fische das LowRes-Raster verlassen hast. Und wie die kurz 1px breit werden, wenn sie wenden... herrlich :-)

Danke. Ja die Fishbewegung war ursprünglich pixelweise, aber das war nicht so entspannend. Die Fische heben sich dadurch auch ein wenig ab, was gut ist, da sie im Mittelpunkt stehen sollen.

Ich hatte anfangs höhere Auflösungen ausprobiert, aber bin wieder zurück zu 64x36px weil es mir so am besten gefällt.
Irgendwann mache ich eine Version für pico8 da werden es dann 128x128px, aber leider wahrscheinlich pixelweise Bewegung der Fische.

Sonnenstrahlen sind hinzugekommen!

Ich arbeite seit ner Weile hin und wieder am ConeTracing. Die Idee ist wie beim RayTracing, wo man Strahlen durch die Szene verfolgt und guckt, was sie treffen. Nur dass hier kein Strahl (eine unendlich dünne Linie) getraced wird, sondern ein Strahl mit Ausdehnung, ein Kegel, Englisch "Cone".

Beim RayTracing unterscheidet man Primary Rays, also die Strahlen von der Kamera in die Szene, um zu schauen, welche Szenenteile auf welchen Pixeln landen, und Secondary Rays, also Strahlen von Oberflächen der Szene in die Szene hinein. Letztere sind meist viel wüster gestreut als die wohlgeordneten Primary Rays, die halt wie die Pixel aufm Monitor artig nebeneinander im gleichen Abstand liegen.

Primary Rays macht niemand, Rasterizing wird prinzipiell immer schneller sein. In den Secondary Rays liegt die eigentliche Magie - man kann damit ganz plump Reflektionen einsammeln, globale Beleuchtungseinflüsse aus der Umgebung sammeln oder Schatten von Lichtquellen holen. Das Problem beim RayTracing ist, dass der Ray unendlich dünn ist. Alle genannten Techniken brauchen aber Licht aus großen Bereichen, also muss man beim RayTracing sehr viele Strahlen losschicken und deren Einflüsse gewichtet aufsummieren. Und selbst ne NVidia RTX 2080 schafft bei FullHD und 60fps mit Mühe und Not einen Ray pro Pixel. NVidia fängt da an, diesen einen Ray clever zu streuen, über mehrere Frames hinweg die Ergebnisse wiederzuverwenden und mit GANs das heftige Rauschen, dass man dabei bekommt, rauszurechnen. Ich dagegen will Strahlen mit Volumen (== Kegel) verschicken und will das Aufsummieren der Einflüsse im Kegel analytisch lösen.

Wir nehmen als Beispiel mal den Schatten der Sonne. Die Sonne ist am Himmel eine Scheibe, also eine Fläche. Ein Punkt auf dem Boden bekommt also Licht von der Sonne aus verschiedenen Richtungen: die Strahlen links auf der Sonnenscheibe und die vom oberen Teil der Sonnenscheibe und so weiter addieren sich und ergeben einen hellen Punkt auf dem Boden. Wenn der Weg zur Sonne frei ist, ist das alles kein Problem. Das Problem fängt an, wenn irgendwas Kleines einen Schatten wirft. Das kleine Hindernis verdeckt nur einen Teil der Sonnenscheibe, wir kriegen also auf diesem Bodenpunkt anteilig weniger Licht von der Sonne.

Mit RayTracing müsste man nun von Bodenpunkt aus viele Strahlen in Richtung Sonnenscheibe abfeuern und jeden Strahl ein bisschen streuen, so dass die ganze Sonnenscheibe gleichmäßig abgetastet wird. Wenn wir genügend Strahlen nehmen, kriegen wir anteilig raus, wieviel von der Sonnenscheibe durch das kleine Hindernis verdeckt wird, und wieviel dunkler es auf diesem Bodenpunkt dadurch wird.

Viele Strahlen? Kacke, nich. Wär doch viel cooler, wenn wir statt dem unendlich dünnen Strahl, der ja nur trifft oder nicht trifft, einen Kegel abschicken könnten, der anteilig auf das kleine Hindernis trifft. Und das habe ich versucht. Ich kann jetzt analytisch ausrechnen, wieviel von einem kreisrunden|rechteckigen Kegel durch ein Rechteck|Voxelblob|Dreieck verdeckt wird. Und das habe ich eingesetzt, um einen Haufen Cones durch meine alte Voxelwelt zu tracen. Sind erstmal nur die Primary Rays, weil die am einfachsten zu coden sind, aber theoretisch sollte es ja nicht dabei bleiben. Und das sieht so aus:



Komplett ohne Licht sieht alles reichlich gleichförmig aus, es sind halt nur die Primary Rays. Bei Primary Rays hat man auch nicht wirklich was davon, dass das jetzt Cones anstatt Rays sind. Der einzige Vorteil ist, dass es in Bewegung komplett frickelfrei ist, weil halt für jeden Pixel anteilig die Farbwirkung jedes Voxels einberechnet wird.

Und es ist aktuell komplett in Software, weil ich die leichter debuggen kann. Irgendwann soll das schon noch auf die Grafikkarte wandern, da wär's dann auch drastisch schneller. Hier auf der CPU könnte ich noch ein bissl was optimieren und vektorisieren, aber viel besser wird's im Groben und Ganzen nicht mehr.

Interessant. Ich hatte schonmal davon gehört, aber eines habe ich nicht verstanden: Was ist mit Verdeckungen? In dem Moment, wo der Kegel ein Objekt trifft, muss ich für die dahinter liegenden Objekte die Verdeckung durch dieses getroffene Objekt berücksichtigen. Ich habe es dann nicht mehr mit einem Kegel zu tun, sondern mit einem "maskierten" Kegel, wobei die Maske mit einem Polygon beschrieben werden könnte. Ich hoffe, ich habe mich verständlich ausgedrückt. Also wie löst du Verdeckungen?

Und was genau zeigt dein Screenshot eigentlich? Ich hätte da eine gewisse Unschärfe erwartet dadurch, dass pro Pixel viele Objekte getroffen werden ... Oder sind deine Kegel einfach extrem dünn, ohne "Streuung"?

Man würde also z.B. Richtung Sonne einen Kegel schießen, der genau so breit ist, dass er die Sonne abdeckt? Und ich vermute mal, man speichert dann unterwegs eine prozentuale Verdeckung, so dass man an einer Objektkante z.B. nur noch 50% der Sonne sieht und dann entsprechend dunkler wird? Die Frage, die denke ich auch David gestellt hat, ist dann, die man diese Verdeckung entlang des Strahl repräsentiert. Als Prozentangabe scheint man das naheliegend und performant zu sein, aber wenn man zwei Objekte zwischen Oberfläche und Sonne hat, die sie jeweils um 50% verdecken, kann man damit dann nicht entscheiden, ob die Verdeckung weiterhin 50% ist, oder 100% oder irgendwo dazwischen. Und eine komplexere Darstellung, sich also zu merken welcher Teil des Kegels verdeckt ist, dürfte so aufwändig sein, dass man dann direkt mehrere Strahlen schießen könnte.

Allerdings kann man ja auch einfach immer das Maximum nehmen. In den allermeisten Fällen dürften Objekte ja größer sein, als die Lichtquellen, d.h. der Effekt tritt vor allen Dingen an Objektkanten auf. Vielleicht hat man dann in der Praxis gar nicht so viele Artefakte.

@David: meine Kegel im Screenshot sind sehr sehr dünn. Sie sind in der Vorauswahl runde Kegel und in der Endstufe viereckige Pyramiden exakt durch die Ränder eines einzelnen Pixels. Damit ist das Bild so scharf, wie man es von einem Rasterizer erwarten würde, aber man kriegt halt gleichzeitig perfekte[*] Subpixel-Genauigkeit.

Das [*] enthält eure Frage zur Verdeckung. Wir haben einen Kegel, und ein Primitive ragt da so von links rein und verdeckt zum Beispiel 43%. Wie genau kriege ich jetzt raus, was das nächste Primitive dahinter von den restlichen 57% weg nimmt? Wenn's von rechts reinragt, könnte es quasi unverdeckt vom Ersten am Prozentwert knuspern. Wenn es auch von links reinragt, gehen die ersten 43% ins Leere. Wie löse ich das?

Hier im Proof Of Concept löse ich das gar nicht. Ich rechne also jeden Primitive anteilig auf den Rest. Der Erste nimmt 43%, der zweite errechnet auch 43%, nimmt also 43% von den bislang übrigen 57% weg. In der Praxis sind meine Voxel aktuell deutlich größer als ein Pixel, ich habe also gute Chancen, dass nach ein paar wenigen Voxeln einer dabei ist, der 100% nimmt. Das liegt aber daran, dass mein Experiment aktuell rein implementationsbedingt zu früh die nächste LOD-Stufe rausholt. Eigentlich soll die SVT-Traversierung so weit gehen, bis sie bei ner Detailstufe rauskommt, deren Voxel in etwa so groß wie der Kegel sind. Mit so kleinen Primitives müsste das Einsammeln der Coverage wahrscheinlich deutlich weiter gehen, ehe ich für jeden Pixel >99% erreicht habe. Ding für später.

Nun hat Jonathan aber leider genau den Finger drauf. Im "Rundkegel Richtung Sonne"-Szenario bekäme ich durch diese Ignoranz eine Überdunkelung der Schatten. Eine Wand zum Beispiel besteht aus ner Reihe Voxel. Die Chance steht also ziemlich gut, dass mehrere Primitives immer die selbe Ecke der Kegelgrundfläche verdecken und meine primitive Methode deutlich zu hohe Werte ergibt. Das Ergebnis wäre wohl eine Penumbra Region, die deutlich schmaler als physikalisch korrekt aussieht und deutlich schneller zu Vollschatten übergeht.

Ich habe daran ein paar Gedanken verwendet, aber noch nichts implementiert. Tim Sweeny, der sich all meine Gedanken bereits vor 10 Jahren öffentlich auf Twitter gemacht hat, wollte das mit Dreiecken machen und pro Pixel einen kleinen BSP-Tree aufbauen, damit die Coverage absolut korrekt rauskommt. Das ist aber ein bissl sehr hardcore, denke ich. Wär natürlich cool, weil Du mit einer perfekten Coverage-Berechnung komplett auf Licht- und Schattenberechnungen verzichten könntest. Du könntest halt einfach pro Oberflächenstück dicke Cones in alle Richtungen schicken und all Dein Licht durch Emissive Primitives modellieren, und die räumlich korrekte Coverage würde vollautomatisch scharfe oder weiche Schatten ergeben. Sehr cool, aber nicht praktikabel, glaube ich.

Aber vielleicht reicht es schon, ne simple Bounding Area mitzurechnen. Also wenn ein Primitive von links an Deiner Kegelfläche knuspert, schiebst Du einfach die linke Kante so weit nach rechts. Damit verengt sich Deine Grundfläche für die nachfolgenden Primitives, weitere Primitives von links bewirken dann weniger oder gar nix, weitere Primitives von rechts dagegen umso mehr, weil die Gesamtfläche kleiner geworden ist. Für meine Voxel, die ja wegen ihrer schlichten rechteckigen Form entweder komplett covern (dann hast Du das Problem nicht) oder von einer Seite/Ecke aus in die Kegelfläche reinragen, müsste so ein simpler Ansatz aber schon passable Ergebnisse liefern.

Alternativ könnte man nen Mini-ZBuffer pro Kegel mitführen. Also z.B. ein AVX256-Register, in dem die Bits ein 16x16-Besetzt-Raster ergeben. Dann könnte man die komplette Coverage-Berechnung mit ein paar Logik-Ops abhandeln und nachher einfach Bits zählen, wieviele neue Rasterfelder das Primitive belegt hat.

Anekdote: ich nehme aktuell quadratische Voxel, die Schnittfläche mit nem Quadratischen Pixel zu berechnen ist trivial. Aber eigentlich ist das ja ein Flächenintegral "Schnittfläche Primitive mit Kegelgrundfläche", und ich habe in diversen ShaderToy-Experimenten auch andere Kombinationen ausgeformelt. Für beliebige Formen brauchst Du die Invertierte der Hüllenfunktion und das Integral. Ich habe auch mal für "Kreis vs. Rechteck" ausgerechnet, das Integral davon enthält einen ArcSin, glaube ich, das erschien mir nicht echtzeitfähig. In meinem VoxelSurvival-Spiel sind die Voxel sqrt³(1 - x³), das Integral davon enthält laut Wolfram Alpha eine unendliche Summe... sowas hab ich noch nie gesehen. Approximieren geht aber leider nicht, weil es Grenzfälle gibt, in denen man negative Werte oder NAN bekommt, wenn die Invertierte nicht perfekt zum Integral passt. Also habe ich eine Grundform gesucht, die halbwegs kreisig aussieht, und bin bei 1 - x^4 rausgekommen. Im ShaderToy fluppt das prächtig. Im Code hab ich diese Variante aber auskommentiert, weil allein die pow() darin laut Profiler 40% der gesamten Framezeit fressen. Und ich dachte immer, exp() und ln() wären mit float32 ein gelöstes Problem und quasi kostenlos. Da passt wahrscheinlich auch ein ArcSin wieder rein. Also hole ich evtl. irgendwann doch wieder die Kreisform raus.

x^4 kannst du auch ohne pow machen: x *= x; x *= x;

Ja, die Verdeckung korrekt zu lösen dürfte extrem schwierig sein. Darum war ich auch neugierig.

Wann hörst du auf einen Kegel zu verfolgen? Wenn die 100% erreicht sind? Dann würde es eine Rolle spielen, in welcher Reihenfolge die getroffenen Primitive abgearbeitet werden.

Mich würde mal ein Screenshot interessieren, wo die Kegel weiter geöffnet sind. Sieht das dann aus wie ein Blur-Filter, der über das Bild gelegt wurde?

Das Integral ist dann ja 1/4 * x⁵, aber das kriegt man trotzdem ersetzt. Unersetzbar war dagegen die Invertierte, nämlich (1 - y)^(1/4). Und ich habe festgestellt, dass zumindest aktuell ohne jede Beleuchtung die Voxel eh einfarbig ineinander übergehen, also ist es herzlich wurscht, welche Form sie haben. Daher sind's jetzt Rechtecke.

Beim Kegel-Tracen muss ich auf jeden Fall die Reihenfolge einhalten - von vorne nach hinten. Das habe ich am Anfang über ne schlichte SignBit-Invertierung gemacht. Ich traversiere ja einen Sparse Voxel Tree, in dem jeder Node einen großen Voxel mit der Durchschnittsfarbe darstellt und dann in 2x2x2 halb so große Voxel aufgeteilt wird. Mein Gedanke war, dass ich ja einfach die Subnodes in der Reihenfolge durchgehen kann, in der der Strahl zeigt, so dass automatisch die vorderen zuerst dran kommen. Die nötige Invertierung "1 - Index" ist für 2x2x2 einfach nur ein XOr mit den SignBits der Strahlrichtung, das ist superschnell. Leider ist es prinzipiell untauglich, weil damit immer nur die Subnodes eines Nodes untereinander sortiert sind. Der Nachbar-Subnode kommt dagegen im Ganzen davor oder danach, obwohl dessen Voxel eigentlich so ein bissl interleaved sein müssten. Das ist kaum zu merken bei 2³-Subnodes, aber bei mir geht's ja bis 2048³, und da sind die Kanten heftig. Also gibt's jetzt obendrauf noch nen plumpen std::sort nach Integer-Punktprodukt Strahlrichtung <-> Punktposition. "Obendrauf", weil sich herausgestellt hat, dass std::sort() drastisch schneller ist, wenn der Datensatz vorsortiert ist.

Und dann klappere ich die Voxel in Reihenfolge ab, bis ich ne Coverage von 99% habe. Weil die Voxel zumeist mehrere Pixel groß sind, geht das recht fix.

Und zum Schluss die Kegelöffnung bzw. bei rechteckiger Grundfläche wär's ja ein Pyramidenstumpf - Screenshot kann ich Dir leider nicht liefern, weil ich da aktuell noch ziemlich viel hardcoded habe, um's erstmal zum Laufen zu kriegen. Aber theoretisch hast Du Recht, ein Pyramidenstumpf, der sich schneller öffnet, als die Pixelgrundfläche sich in die Tiefe öffnet, müsste wie ein Weichzeichner wirken. Und dabei automatisch zu detailreduzierten Voxelstufen wechseln und damit deutlich schneller als ein Blur arbeiten :-) Allgemein hat das Prinzip echt viele geile Nebeneffekte. Wenn man den Kegel anfangs dicker macht, dann über einen Tiefenbereich auf Zielgröße hält und danach wieder aufweitet, kriegt man ne perfekte Tiefenunschärfe geschenkt UND spart noch Rechenzeit, weil die SVT-Traversierung früher aufhören kann.

Ich werde schon wieder ganz kribbelig, wenn ich dran denke, was man damit alles machen kann.

Zitat von »Schrompf«

Und selbst ne NVidia RTX 2080 schafft bei FullHD und 60fps mit Mühe und Not einen Ray pro Pixel.

Naja die 2000er Serie ist aber auch nicht für Raytracing gemacht. Die Leistung liegt nicht weit von der 1000er Serie entfernt. Meine 1080Ti dürfte sogar mehr Leistung haben als deine 2080. Mit den RTX ist zwar Raytracing möglich, aber benötigt von der ohnehin schon zu knappen Leistung (meine 1080Ti ist auch oft am Anschlag) halt auch noch etwas fürs Tracing. Daher sind deine auf Anschlag erreichten 60FpS kein Wunder (zumal die Karten auf HD nicht alles rausholen können - in 4k sind sie leistungseffizienter).

Aber davon mal abgesehen, finde ich dein Projekt spannend. Bin gespannt, was am Ende dabei rumkommt.