Autor Wątek: Algorytm tworzenia terenu na podstawie punktów  (Przeczytany 1029 razy)

Offline Pasio

  • Użytkownik

# Marzec 09, 2011, 20:49:54
Witam,

mam zbiór punktów odczytanych z mapy w postaci współrzędnych geograficznych, w każdym z tych punktów mam jego wysokość. Dokonałem odpowiednich konwersji i całość zapisałem do "pseudo" mapy wysokości. "Pseudo" oznacza, że nie mam wysokości we wszystkich punktach tekstury i w tym momencie wygląda to tak:


Punkty mają dodatkowo taką własność, że układają się w poziomice. Może ma ktoś jakiś pomysł lub może istnieje jakiś algorytm jak uzyskać z tego pełną mapę wysokości ?

Biorę pod uwagę zastosowanie algorytmu triangulacji Delaunaya bądź szerzej wykorzystania diagramów Voronoi'a ale niewiem czy przy takim ustawieniu punktów nie wyjdzie coś dziwnego, bo zależy mi na dobrym odwzorowaniu terenu.

Bedę wdzięczny za wszelkie wskazówki :)

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline FoToN

  • Użytkownik

# Marzec 09, 2011, 21:54:53
Mógłbyś spróbować przelecieć pętlą wszystkie piksele i jeżeli przetwarzany piksel jest koloru czarnego to dajesz mu kolor najbliższego nie-czarnego piksela (bądź jeśli chcesz by była wyższa jakość, możesz pobrać kilka(naście) najbliższych pikseli nie-czarnych i odpowiednio interpolować kolor).

Offline Reg

  • Administrator
    • Adam Sawicki - Home Page

# Marzec 09, 2011, 22:38:41
Pierwsze, co mi przychodzi do głowy, to taki algorytm:

W każdej komórce jest jakaś wysokość lub specjalna wartość oznaczająca komórkę pustą.

Dopóki są jakieś komórki puste:
- Dla każdej komórki pustej:
- - Jeśli sąsiaduje z jakąś niepustą:
- - - Nadaj tej pustej wartość z tej sąsiedniej.

Ten algorytm ładnie załata widoczne na obrazku, który dołączyłeś, przerwy w isoliniach. Niestety nie zinterpoluje płynnie wartości między isoliniami. Trzebaby potem zapuścić na tej tablicy jakieś wygładzanie.

Offline _OskaR

  • Użytkownik

# Marzec 09, 2011, 23:38:16
Można poszukać np. czterech punktów - najbliższy w pionie (góra/dół) i w poziomie (lewo/prawo) i zsumować wszystko z odpowiednimi wagami (zależnie od odległości).

W sumie co ja tam kombinuję - poszukaj metody najbliższego sąsiada i podobnych - tu wymieniono parę metod - http://docs4.chomikuj.pl/197487,0,0,wyklady-sip-ii.doc
« Ostatnia zmiana: Marzec 09, 2011, 23:41:50 wysłana przez _OskaR »

Offline Liosan

  • Redaktor

# Marzec 10, 2011, 09:09:38
Ja bym spróbował w dwóch krokach:
1. wyznaczyć obszary, które leżą pomiędzy poziomicami; w zależności od tego, czy pracujesz na "pixelach" czy kształtach geometrycznych, możesz to zrobić jakimś floodfillem albo aproksymując dane poziomic krzywymi i brać obszar między nimi.

Jeśli masz sensowne dane, to dostaniesz 3 rodzaje obszarów - najprostsze leżące między 2 poziomicami (z ewentualnymi fragmentami "brzegu mapy", który przecież też je ogranicza), trochę trudniejsze mające tylko 1 poziomicę oraz "brzeg mapy" oraz też nieproste "wysepki" - szczyty gór itp.

2. Interpolować wielkość każdego punktu w obszarze jako średnią wysokości dwóch poziomic, które ten obszar otaczają, ważoną odległością wybranego punktu od tych poziomic. Jako odległość przyjąłbym odległość Hausdorffa - czyli odległość do najbliższego punktu na krzywej. Jeśli to ma być realtime, to pewnie chciałbyś nie sprawdzać całej krzywej tylko jakieś otoczenie wybranego punktu, czyli mógłbyś sample'e wrzucić w jakieś proste quadtree albo siatkę. Powinieneś dostać w miarę gładkie zbocza między poziomicami.

Jedyny problem to te obszary, które mają tylko jedną poziomicę (albo dwie poziomice o tej samej wartości). Tutaj przychodzą mi głowy dwa pomysły - pierwszy to taki, że strzelasz że najniższy/najwyższy punkt obszaru to ten najdalszy od poziomic, i że on jest o połowę różnicy między poziomicami wyższy albo niższy. Żeby się zastanowić czy wyższy czy niższy, trzeba spojrzeć na przyległe obszary - czy nasz obszar jest od nich wyżej (to ciągniemy dalej w górę - pewnie to Rysy) czy niżej (to ciągniemy dalej w dół - pewnie jakaś dolina), czy nie wiadomo (dwóch sąsiadów, i od obu sprzeczne info; albo nasz jedyny sąsiad ma tylko jedną poziomicę) - to trzeba losować ;). Drugi pomysł jest prostszy - olać sprawę, zobaczyć jak wygląda po interpolacji (czyli tam, gdzie faktycznie są jakieś dane z którymi można pracować), a potem pomyśleć :)

Jak pisałem na początku, pomysł mocno się opiera na własnościach poziomic. Jeśli dane będą od czapy, wyniki również :)

Liosan