Marching Cubes mit LOD / Transvoxel

    • German

    We've posted a status update with some first screenshots of the new terrain generation. There is also a new update available for the Java version!

    • Marching Cubes mit LOD / Transvoxel

      Vorweg die Frage stellt sich eher direkt an red51, da ich denke mir wird kein anderer helfen können. ^^

      Ich versuche gerade in Unity Transvoxel zu implementieren. Ich habe mir auch das originale Papier von Eric Lengyel durchgelesen, aber irgendwie reicht mir das nicht um es auch implementieren zu können.
      In der PluginAPI von Rising World sehe ich, dass es auch LOD Chunks gibt, also müsste das Spiel ja auch irgendeinen LOD Algorhithmus haben für Marching Cubes.
      Da die Unity Version ja mittlerweile auch schon ein Terrain hat müsste das ja auch schon komplett implementiert sein mitterweile in Unity und C#.
      Hättest du vielleicht irgendwelche Hinweise wie ich es schaffe es wirklich auch umzusetzen? Irgendwie fühle ich mich einfach nur ratlos, suche echt schon seit Monaten auf Google (eigtl. sogar schon seit über einem Jahr) und ich bekomme es einfach nicht hin und fühle mich nur frustriert. Irgendwie stößt man nur auf zusammengeschusterte Source Codes die nicht funktionieren (die Source Codes kann man aber auch an einer Hand abzählen) oder man trifft auch Tutorials/Artikel die im Grunde die Implementierung komplett auslassen. Also im Grunde muss man es irgendwie einfach selbst wissen wie es geht. Aber ich befürchte wenn ich es selbst rausfinden will sitze ich noch 2 Jahre daran.
      Ich frag mich einfach nur wie du es damals schon so schnell geschafft hast das umzusetzen? Hattest du da irgendwelche Resourcen oder hast du dir es einfach selber ausgedacht oder bist du einfach intelligent genug dafür und ich verstehe es einfach nur nicht? ^^

      Würde mich total über Hilfe freuen, ich könnte jeden Tag meinen Kopf gegen die Wand hauen bei jedem erneuten Versuch.

      Mein letzter Versuch war das hier zu Unity zu konvertieren: github.com/BinaryConstruct/Tra…NA/tree/master/Transvoxel
      Die Tabellen lassen sich natürlich leicht übertragen. Aber der SurfaceExtractor ist schonwieder grausam zu entschlüsseln. Vor allem wenn es losgeht mit irgendwelchen Byte-Operationen für Variablen die keine ordentlichen Namen haben, nur einzelne Buchstaben. Ich könnte echt nur heulen.

      Hier was ich schon habe als Code (wenigstens etwas davon hinbekommen ^^): pastebin.com/BHuryGF1

      The post was edited 1 time, last by Kassa ().

    • Naja, unser Marching Cubes Algorithmus ist wirklich sehr einfach gehalten. Er basiert auf der Arbeit von Paul Bourke (den Artikel kennst du möglicherweise schon, das ist quasi der "Klassiker" wenn es um Marching Cubes geht): paulbourke.net/geometry/polygonise/
      Darauf basiert unsere Implementation, und dort stammen auch die Lookup-Tables her (die im Prinzip für die eigentliche "Magie" zuständig sind). Es gibt da draußen sicherlich bessere Algorithmen, allerdings ist der von Paul Bourke wirklich sehr schnell, und das spielte für uns eine wichtige Rolle.

      Etwas spezieller geht RW bei der Berechnung der Density-Map vor, aber unsere Lösung ist schon sehr RW spezifisch gehalten.

      LOD Chunks sind bei uns quasi nochmal ein eigenes Konstrukt. Hier berechnen wir anhand der Voxel Daten eine Höhenmap, anhand derer wir dann einen ganz simplen Mesh erzeugen können (daher sind im LOD-Terrain zB keine Überhänge oder Höhlen sichtbar). Hier wäre es viel zu aufwändig, die LOD-Berechnung im Marching Cubes Algorithmus zu berücksichtigen (zumal dann auch wesentlich mehr Daten zwischen Client und Server übertragen werden müssten), und das Ergebnis wäre es nicht wert. Ob und inwieweit wir das so bei der Unity-Version nochmal umsetzen werden, weiß ich allerdings noch nicht...

      Zur Transvoxel-Implementation kann ich dir leider nicht viel sagen :( Ich lese mich nur sehr ungerne in fremde Implementationen ein, lieber versuche ich, die zugrundeliegende Idee bzw. den Algorithmus dahinter zu verstehen und eine eigene Lösung zu entwickeln (auch wenn damit manchmal das Rad neu erfunden wird) :D
    • Cool, danke für die Antwort. Ich finde das originale Marching Cubes geht noch recht einfach zu implementieren. Was ich aber komisch finde ist das meine Terrains immer blockig werden. Also so Stufen-artig.
      Also selbst wenn ich zum Beispiel als Density-Funktion habe:

      height = x * 0.01f + 15.0f;

      Und dann als density Funktion:

      if (height < 15.0f) density = 1.0f
      else if (Mathf.Floor(height) == 15.0f) density = height % 1.0f;

      Dann müsste er mir ja immer wenn die Höhe über 15.0f ist den density Wert geben, der sich jedes mal um 0.01f erhöht. Also praktisch müsste jeder Punkt x dann bis zu 15.0f aufgefüllt werden und darüber hinaus dann nur mit 0.01f Schritten langsam höher werden. Was er dann aber bei mir macht ist dass er praktisch alles rundet auf 0 und 1. Also praktisch bleibt das Terrain dann immer bei mir gleich hoch und macht dann nur einen Schritt wenn es einen gewissen Density Wert überschreitet. Das sieht man ja auch oben im Bild, das ist Perlin Noise und da macht er dann auch einfach einen Schritt.

      Ich habe da auch mehrere Interpolation Funktionen probiert, eigtl. die üblichen die auch überall so benutzt um empfohlen werden, aber irgendwie will es einfach nicht. Weisst du eventuell womit das zu tuen hat? Hattest du das Problem auch am Anfang?

      Und benutzt du irgendwie kleinere Werte für die Zellgröße als 1? Also ist bei dir eine Zelle 1.0fx1.0fx1.0f groß oder muss man das vielleicht halbieren damit das "glatter" wird? Aber dann müsste man ja auch die doppelte Anzahl an Voxels laden. Und irgendwie wäre es ja dann trotzdem auch Stufen-artig, nur halt kleinere Stufen.

      Bei Transvoxel habe ich dieses Stufen-Problem komischerweise genauso wie bei der Lösung von Paul Bourke (hatte ich auch schonmal ausprobiert).
    • Ich weiss woran es lag.

      Ich habe immer nur positive density Variablen ausgerechnet mit der density Funktion. Hier ein Beispiel:

      Muss ich wohl rausfinden wie ich eine ordentliche glatte Density-Funktion erstelle für die Voxel-Map.

      Edit: Hat geklappt hiermit ^^:

      if (y < Mathf.Floor(height))
      {
      value = 1.0f;
      }
      else if (y == Mathf.Floor(height))
      {
      value = (height % 1.0f);
      }
      else if (y == Mathf.Ceil(height))
      {
      value = -(1.0f - (height % 1.0f));
      }



      The post was edited 1 time, last by Kassa ().

    • Freut mich, dass du das Problem lösen konntest :) Wir verwenden übrigens eine Blockgröße von 1, allerdings experimentieren wir ein wenig mit halber Blockgröße fürs Terrain, damit das Abbauen etwas präziser wird. Bin mir aber nicht sicher, ob wir diesen Weg wirklich gehen werden (da wir bei halber Blockgröße gleich 8x soviele Daten haben, und auch das Generieren der Chunks entsprechend länger dauert)