Reprezentacja mapy sferycznej


19

Moja najnowsza gra odbędzie się na małej planetoidie. Szukam dobrej struktury danych do reprezentowania komórek na powierzchni kuli. Trójkąty, kwadraty, pięciokąty, sześciokąty? Który z nich najbardziej ogranicza rozciąganie i tworzy najlepsze kafelki?

Mapowanie sferyczne jest najłatwiejsze, ale rozciąganie na biegunach jest niedopuszczalne. Tworzenie kostek jest również dość łatwe, ale w pobliżu rogów sześcianu nadal byłby znaczny rozciągnięcie. Podział dwudziestościanu wydaje się najlepszy pod względem rozciągania, ale istnieje problem z indeksowaniem wielu trójkątnych układów i znalezienie sąsiadujących komórek na granicach byłoby trudne.

Wydaje mi się, że przydałby mi się pojedynczy liniowy układ punktów reprezentujących N-gony, każdy z tablicą wskaźników N sąsiadów, ale to wydaje się ogromną stratą miejsca.

Gra ma elementy RTS, więc będę przechowywać takie rzeczy, jak mapy wpływów oraz przeprowadzanie wyszukiwania i konwertowania ścieżki A *, więc reprezentacja musi być wydajna.


Jak ważna jest dokładna topologia mapy, a nie tylko pozwalanie aktorom pójść w jednym kierunku i ostatecznie skończyć w miejscu, w którym zaczęli? Najprostszym i najbardziej wydajnym przedstawieniem byłby torus / pączek.
congusbongus

1
Tak, wspomniałem o mapowaniu sferycznym i problemach z biegunami. Chcę przechowywać wartości wokół powierzchni, więc potrzebuję mapowania od punktu powierzchni 3D do indeksu tablicy z możliwie najmniejszym rozciąganiem.
DaleyPaley

Możesz spróbować podzielić czworościan, aby utworzyć kulę. Składa się z trójkątów o równej wielkości i rozmieszczeniu.
thalador

1
@thalador Dzięki za sugestię. Nie jestem pewien, ale myślę, że dwudziestościany są lepsze niż czworościany, jeśli pójdę drogą trójkątną. Ale zresztą teselacja nie stanowi problemu. Niepokoi mnie efektywne indeksowanie macierzy.
DaleyPaley

Odpowiedzi:


12

Okej, dla każdego zainteresowanego tym tematem opiszę teraz wybrane rozwiązanie. Dziękujemy wszystkim, którzy odpowiedzieli i dali mi pomysły.

Po pierwsze, dla „najlepszego” teselacji jako punkt wyjścia wybiorę ścięty dwudziestościan . Podzielenie go prowadzi do bardzo ładnego mozaikowania sześciokątów z 12 pięciokątami zapewniającymi krzywiznę. Ponadto kontynuacja podziału na podwójny da mi bardzo dobrą trójkątną siatkę do renderowania z ładnymi właściwościami. Odnośnie 12 pięciokątnych komórek: mogę je zignorować, uczynić je wyjątkowymi (tak jak jedyne miejsca, w których można zbudować bazy) lub ukryć je pod scenerią.

Sześciokątne i pięciokątne komórki będą przechowywane w strukturze danych o połowie krawędzi dla łatwego dostępu do sąsiadów i szybkiego przejścia. Jedyną trudną częścią jest ustalenie, w której komórce znajduje się dany punkt świata, ale można tego dokonać, zaczynając od losowej komórki i idąc w kierunku punktu przez sąsiadów.

Mam nadzieję, że ktoś uzna te informacje za przydatne. Wiele się nauczyłem i nie mogę się doczekać, aby uzyskać pewne wyniki.

Edytować:

Oto obraz pokazujący wynik mojego podziału dwudziestościanu i podwójnego przełączania siatki przy użyciu struktury danych o połowie krawędzi.

Mogę zrobić kilka iteracji relaksacyjnych, aby obszary komórek były jeszcze bardziej jednolite.

dwudziestościan


7

Istnieje sposób, aby to zrobić raczej elegancko, opierając się na dzieleniu dwudziestościanu, jak sugerowałeś w swoim pytaniu. Dwudziestościan składa się z 20 równobocznych trójkątów, które można pogrupować w 5 zestawów, przy czym 4 trójkąty w zestawie tworzą kształt równoległoboku:

wprowadź opis zdjęcia tutaj

(Grupy czterech trójkątów z przeciągniętym przez nie zawijakiem to równoległoboki, o których mówię. Strzałki mówią, które krawędzie byłyby sklejone ze sobą, aby złożyć to w dwudziestościan).

Jeśli te trójkąty są podzielone na mniejsze trójkąty, cały równoległobok może być indeksowany jak tablica prostokątna n przez 4n (n = 4 w przykładzie):

wprowadź opis zdjęcia tutaj

Liczby w każdej komórce są numerami kolumn prostokątnego układu. Zasady znajdowania sąsiadów w tablicy są dość proste: poziomymi sąsiadami są tylko plus lub minus 1 kolumna, podczas gdy pionowy sąsiad jest albo minus jeden rząd i plus jedna kolumna, albo plus jeden rząd i minus jedna kolumna, w zależności od tego, czy numer kolumny jest odpowiednio parzysty lub nieparzysty.

Jednak nadal musisz napisać kod specjalnego przypadku, aby znaleźć sąsiadów, którzy przekraczają granicę od jednego równoległoboku do drugiego. Jest to nieco skomplikowane, ponieważ w niektórych miejscach góra lub dół jednego równoległoboku będzie połączony z bokiem drugiego, lub góra i dół zostaną połączone z poziomym przesunięciem między nimi itp. Prawdopodobnie struktura pół krawędzi lub podobne przydatne byłyby tu równoległoboki. Jednak przynajmniej relacje są symetryczne między wszystkimi 5 równoległobokami: wszystkie mają ten sam wzór, w którym strona jest połączona z którą drugą stroną swoich sąsiadów.


To naprawdę bardzo ładna reprezentacja. Moje główne obawy dotyczące metod trójkątnych polegały na utrzymaniu trójkątnych tablic i wszystkich szwów. Jest tu jeszcze trochę szwów, ale tablice są prostokątne. Dzięki, bardzo dobrze wiedzieć
DaleyPaley

3

Hmmm - komentarze na temat rozciągania wskazują, że poruszasz się między mapowaniem sferycznym i planarnym, co prowadzi do zniekształceń na biegunach

Jeśli chcesz, aby płytki były płaskie i jednolite, masz rację, że dwudziestościan, a konkretnie dwudziestościan ścięty, jest dość powszechny

Możesz znaleźć wszystkie różne mapowania tutaj - Kuliste Wielościany na wikipedii

Jeśli chodzi o utrzymywanie relacji między twarzami, jest to problem topologiczny - może być pomocna albo skrzydlata krawędź, albo czworokątna krawędź (i masz wspaniałą okazję poznać zupełnie nową formę algebry) Winged Edge


Ach, ścięty dwudziestościan. Tak, właśnie tego potrzebuję. Dzięki. Ponadto, chociaż nigdy nie korzystałem ze skrzydlatej krawędzi, często używałem pół krawędzi do manipulacji siatką, więc jestem dobrze zorientowany w tym obszarze. Pozdrawiam, jestem blisko rozwiązania.
DaleyPaley

2

Chyba spóźniam się trochę na przyjęcie, ale oto możliwe rozwiązanie, które można wykorzystać do utrzymania kulistego świata o dowolnym rozmiarze i jednolitym wyglądzie.

Kluczową rzeczą do zrozumienia tutaj jest to, że świat nie jest płaski, a zatem 100% jednolite kafelkowanie byłoby niemożliwe (wynika to z tak zwanego twierdzenia Hairy Ball ). Należy dopuścić pewne nieprawidłowości, a najlepsze, na co możemy liczyć, to równomierne rozłożenie tych nierówności na powierzchni, tak aby każda była jak najmniejsza.

W rzeczywistości jest to dość łatwe w sposób niedeterministyczny. Najpierw wybierz równomiernie N losowych punktów wokół powierzchni. Upewnij się, że te punkty są w rzeczywistości jednakowe (patrz Zbieranie punktów kuli , wzory 9-11). W drugim etapie sprawiamy, że punkty te są mniej losowe i bardziej jednolite: zakładamy, że wszystkie te punkty mają ujemny ładunek elektryczny, aby się wzajemnie odpychały. Symuluj ruch punktów przez kilka kroków, aż zbiegną się one w stan równowagi. Ta końcowa konfiguracja punktów da ci siatkę, która jest prawie równomiernie rozmieszczona na powierzchni kuli.


1
Nigdy nie słyszałem o teorii owłosionej piłki, jest to dość interesujące. Muszę powstrzymać się od żartów. Wcześniej tak dzieliłem punkty na sfery, ale problem polega na tym, że poligonizacja jest znacznie wolniejsza niż podział polytopa. Również kształty i wartościowość komórek będą zbyt niejednolite dla moich upodobań. Mimo wszystko dziękuję.
DaleyPaley
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.