Voxel-Datenstrukturen und -Algorithmen



  • Hallo da,
    ich bin in der Planung eines Freizeit-Projekts, bei dem ich mir vorstelle, dass die Verarbeitung der Geometrie in Voxeln sehr vieles stark vereinfachen und unter einen Hut bringen würde.
    Ich muss die Teile eigentlich nicht rendern, schon gar nicht schnell, aber wende mich dennoch hierher, weil das ja in der Grafik gerade ein aktuelles Thema ist.
    Meine Frage: Gibt's da schon Standardlektüre, die mögliche Datenstrukturen, Updates, Algorithmen usw. zusammenfasst? Ich habe bislang nur zuhauf Papers aufgetrieben, aber da geht ja jeder anders heran und mir wäre eine aufbereitete Zusammenfassung natürlich lieber.

    Viele Grüße


  • Mod

    genau wie bei standardlektruere ueber dreiecke, wird standardlektruere ueber voxel davon abhaengen was du damit machen willst. z.b. wird minecraft sicherlich nichts von der standardlektruere nutzen die medizinisches rendern und scannen von voxeln im detail eroertert.



  • Okay, ich brauch dynamische Voxeldaten, also wenn ich irgendwo was entferne, müssen zum Beispiel in einer Baumrepräsentation Knoten umgebaut werden, und das am besten so, dass nicht über die Zeit alles woanders landet im Speicher. Es sollte irgendwie sparse sein, sodass 10k³ Elemente im Speicher nicht ausufern. Die Inhalte werden "niedrigfrequent" (Kein Schachbrettmuster auf feinster Ebene) sein, sodass hier eine Sparse-Darstellung wohl sehr erfolgversprechend ist.
    Wenn das technisch nicht realisierbar ist, so käme ich wohl auch 1k³ hin, aber die bekommt man ja auch schon unge"sparse"t im Speicher unter.
    Auf jeden Fall, brauche ich Datenstrukturen und Algorithmen für diese Repräsentation.
    Im Prinzip ist es wohl auch das, was Minecraft so kann, denke ich, um Dein Beispeil aufzugreifen. Also ich brauche es nicht animiert, nur "shape"-bar.

    Und dann das übliche, schnelle Kollisionsabfrage zwischen Octree und einfachen geometrischen Körpern usw...

    Ich finde die Standardlektüre für Dreiecke schlägt aber schon ziemlich viel auf einen Streich, für die 3D-Grafik schneidet man dann ja nur alles weg, was nicht unbedingt benötigt wird. Also generell -> speziell.



  • Also wenn das Ding ein "sparse" Octree ist, dann ist mir natürlich schon klar, dass man das Teil eben als hierarchische BBox-Sache betrachten kann und damit schnell Kollisionen ausschließt usw, oder dass man dann zuerst mit Kugeln weitermachen könnte. Oder dass man irgendwie Freispeicher im der Struktur unterbringen kann, um Umbauten möglichst lokal zu halten. Aber der Teufel liegt ja immer im Detail und ich denke dass es viele Menschen auf der Erde gibt, die das alles schon genauer untersucht haben und das dann in Buchform gegossen haben oder so.



  • 10k³ Elemente ... 1k³

    😕 10 bzw. 1 Gigaelement(e)? Vielleicht solltest du mal deine Randbedingungen nennen, also auch deine eingesetzte Hardware, insbesondere die obere Grenze deines dir zur Verfuegung stehenden Speichers.



  • Ich meinte Zehntausend hoch 3. Oder anders: bei nem Byte pro Element wäre das also insgesamt knapp ein Terabyte. Das meiste davon ist aber entweder zum großen Teil leer oder voll. Plus die Oberfläche zwischen beidem 😉



  • Ich würde für eine solche Volumendarstellung gerne nicht mehr als 1GB verwenden. Dass das also einen handelsüblichen Rechner nicht über die Maßen belastet. (250 ... 125) : 1 sparse klingt natürlich trotz Anbetracht der Umstände nach viel, aber ich stelle mir das ohne Probleme machbar vor, in Abhängigkeit davon wie das Volumen hinterher wirklich aussieht. Wenn es dennoch im Laufe der Zeit zu groß wird, könnte ich auch damit leben, die letzte Stufe wegzuschneiden.


Log in to reply