Sphärische Kartendarstellung

Mein letztes Spiel wird auf einem kleinen Planeten stattfinden. Ich suche eine gute Datenstruktur für die Darstellung von Zellen auf der Oberfläche einer Kugel. Dreiecke, Quadrate, Fünfecke, Sechsecke? Welches minimiert die Dehnung am meisten und schafft die besten Fliesen?

Die sphärische Abbildung ist am einfachsten, aber die Dehnung an den Polen ist nicht akzeptabel. Cubemapping ist auch ziemlich einfach, aber in der Nähe der Würfelecken wäre immer noch eine beträchtliche Strecke vorhanden. Die Unterteilung eines Ikosaeders scheint in Bezug auf die Dehnung am besten zu sein, es besteht jedoch das Problem, dass viele dreieckige Arrays indiziert werden und benachbarte Zellen an den Grenzen nur schwer zu finden sind.

Ich denke, ich könnte eine einzige lineare Anordnung von Punkten verwenden, die N-Gons darstellen, jede mit einer Anordnung von N Nachbarindizes, aber das scheint eine enorme Verschwendung von Platz zu sein.

Das Spiel hat RTS-Elemente, also werde ich Dinge wie Einflusskarten speichern und A * -Pfadfindung und -Faltung durchführen, daher muss die Darstellung effizient sein.

Okay, für alle, die sich für dieses Thema interessieren, werde ich nun die von mir gewählte Lösung detailliert beschreiben. Vielen Dank an alle, die geantwortet und mir Ideen gegeben haben.

Als erstes wähle ich für die 'beste' Tesselation das abgeschnittene Ikosaeder als Ausgangspunkt. Eine Unterteilung führt zu einer sehr schönen Tesselation von Sechsecken mit 12 Pentagonen, die für die Krümmung sorgen. Wenn ich die Unterteilung auf Dual fortsetze, erhalte ich ein sehr gutes Dreiecksnetz für das Rendern mit schönen Eigenschaften. Zu den 12 fünfeckigen Zellen: Ich kann sie ignorieren, sie zu etwas Besonderem machen (so wie die einzigen Stellen, an denen Basen gebaut werden können) oder ich kann sie unter der Kulisse verstecken.

Die hexagonalen und fünfeckigen Zellen werden in einer Datenstruktur mit halber Kante gespeichert, um den Zugriff auf die Nachbarn zu vereinfachen und eine schnelle Überquerung zu ermöglichen. Der einzige schwierige Teil besteht darin, herauszufinden, in welcher Zelle sich ein bestimmter Weltpunkt befindet. Sie können jedoch auch von einer zufälligen Zelle aus auf den Punkt durch die Nachbarn zugehen.

Ich hoffe, dass jemand diese Informationen nützlich findet. Ich habe viel gelernt und freue mich auf einige Ergebnisse.

Bearbeiten:

Hier ist ein Bild, das das Ergebnis meiner Ikosaeder-Unterteilung und des Umschaltens zwischen zwei Maschen unter Verwendung einer Datenstruktur mit halber Kante zeigt.

Möglicherweise mache ich einige Wiederholungen der Entspannung, um die Zellbereiche noch gleichmäßiger zu machen.

Es gibt eine Möglichkeit, dies auf elegante Weise zu tun, indem Sie ein Ikosaeder unterteilen, wie Sie in Ihrer Frage vorgeschlagen haben. Ein Ikosaeder besteht aus 20 gleichseitigen Dreiecken, und diese Dreiecke können in 5 Sätze gruppiert werden, wobei die 4 Dreiecke in einem Satz eine Parallelogrammform bilden:

(Die Gruppen von vier Dreiecken mit einem durchgezogenen Kringel sind die Parallelogramme, von denen ich spreche. Die Pfeile geben an, welche Kanten zusammengeklebt würden, um diese zu einem Ikosaeder zusammenzufalten.)

Wenn diese Dreiecke in kleinere Dreiecke unterteilt sind, kann das gesamte Parallelogramm wie ein n × 4n-Rechteck-Array indiziert werden (im Beispiel n = 4):

Die Zahlen in jeder Zelle sind die Spaltennummern des rechteckigen Arrays. Die Regeln für das Auffinden von Nachbarn innerhalb des Arrays sind recht einfach: Die horizontalen Nachbarn sind nur plus oder minus 1 Spalte, während der vertikale Nachbar entweder minus eine Zeile und plus eine Spalte oder plus eine Zeile und minus eine Spalte ist, je nachdem, ob der Die Spaltennummer ist gerade oder ungerade.

Sie müssen jedoch noch einen Sonderfallcode schreiben, um Nachbarn zu finden, die die Grenze von einem Parallelogramm zum nächsten überschreiten. Es ist etwas knifflig, da an einigen Stellen die Ober- oder Unterseite eines Parallelogramms mit der Seite eines anderen verbunden wird oder Ober- und Unterseite mit einem horizontalen Versatz dazwischen verbunden werden. Möglicherweise eine Struktur mit halber Kante oder ähnliches für die Parallelogramme wäre hier hilfreich. Mindestens jedoch sind die Beziehungen zwischen allen 5 Parallelogrammen symmetrisch: Sie folgen alle demselben Muster, in dem die Seite mit der anderen Seite ihrer Nachbarn verbunden ist.

Hmmm - die Kommentare zu Stretch deuten darauf hin, dass Sie sich zwischen sphärischer und planarer Abbildung bewegen. Dies führt zu Verzerrungen an den Polen

Wenn Sie möchten, dass die Kacheln flach und gleichmäßig sind, haben Sie Recht, dass ein Ikosaeder, insbesondere ein abgeschnittenes Ikosaeder, ziemlich häufig ist

Sie können all die verschiedenen Zuordnungen hier finden - Sphärische Polyeder auf Wikipedia

Was die Aufrechterhaltung der Beziehungen zwischen den Flächen angeht, ist dies ein Topologieproblem. Möglicherweise finden Sie Winged Edge oder Quad Edge hilfreich (und Sie haben die wunderbare Gelegenheit, eine ganz neue Form der Algebra kennenzulernen). Winged Edge

Ich schätze, ich komme ein bisschen spät zur Party, aber hier ist eine mögliche Lösung, die verwendet werden kann, um eine kugelförmige Welt von beliebiger Größe und einheitlichem Erscheinungsbild aufrechtzuerhalten.

Der Schlüssel zum Verständnis ist hier, dass die Welt nicht flach ist und daher eine 100% gleichmäßige Kachelung unmöglich wäre (dies folgt aus dem sogenannten Hairy Ball Theorem ). Einige Unregelmäßigkeiten müssen zugelassen werden, und das Beste, auf das wir hoffen können, ist, diese Unregelmäßigkeiten gleichmäßig auf der Oberfläche zu verteilen und sie so klein wie möglich zu machen.

Es ist eigentlich ziemlich einfach, es nicht deterministisch zu machen. Wählen Sie zunächst N zufällige Punkte gleichmäßig um die Oberfläche. Stellen Sie sicher, dass diese Punkte tatsächlich gleichmäßig sind (siehe Auswahl von Kugelpunkten , Formeln 9-11). Im zweiten Schritt machen wir diese Punkte weniger zufällig und einheitlicher: Nehmen wir an, dass alle diese Punkte eine negative elektrische Ladung haben, so dass sie sich gegenseitig abstoßen. Simulieren Sie die Bewegung der Punkte in mehreren Schritten, bis sie sich in einem Gleichgewichtszustand befinden. Durch diese endgültige Konfiguration der Punkte erhalten Sie ein Netz, das nahezu gleichmäßig über die Oberfläche der Kugel verteilt ist.