Płynąca GPU oblicza wodę

Mam doświadczenie w inżynierii lądowej i regularnie wykonuję analizy hydrauliczne i hydrologiczne. Sprzedają stopnie za takie rzeczy, ale tak naprawdę to nie jest nauka o rakietach. Niedawno przyszło mi do głowy, aby zaimplementować cały proces hydrologiczny i hydrauliczny dla terenu na GPU. Nauczyłem się shaderów obliczeniowych dopiero niedawno, więc obecnie jestem lepszy w inżynierii niż w projektowaniu równoległych przepływów pracy GPU.

Możesz obliczyć ilość wody wytworzonej podczas opadów deszczu, korzystając ze wzoru:
Q (CF/S) = c * I (in/hr) * A (acres)

Mam trudności z wyjściem poza obliczanie „areału” nawet pierwszego obszaru.

Przegląd bieżącego wdrożenia:

1. Teren jest regularną siatką wierzchołków w odstępach 1-jednostkowych
2. Mapa wysokości zawiera jedną wartość wysokości R32 dla każdego wierzchołka
3. Obecnie zezwalam na przepływ tylko w 4 głównych kierunkach (bez przekątnych)
4. Używam Texture2D [int] jako szablonu dla wierzchołków, które już przeanalizowałem

Aktualny algorytm:

1. Gdy narzędzie terenu jest aktywne i teraz nie jest ....
2. Wyczyść „szablon”.
3. Skanuj cały teren w poszukiwaniu najniższej wysokości.
4. Ten pojedynczy punkt jest początkowym wejściem do CS_Flood.
5. CS_Flood wykonuje przejście osi X.
6. Każdy wierzchołek wejściowy jest rzutowany w obu kierunkach X- i X + do 2048 razy.
7. Znalezienie sąsiedniego wierzchołka o współrzędnej OOB wskazuje krawędź terenu w tym kierunku. CurrentPoint jest dołączany do bufora BoundaryPoints, a pętla projekcji dla tego kierunku zostaje zakończona. To było łatwe i działa świetnie za każdym razem.
8. Sąsiadujące wierzchołki o wysokości> = aktualna wysokość wierzchołka są zaznaczone na szablonie i dodane do bufora NextPass.
9. Sąsiadujące wierzchołki o wysokościach <aktualna wysokość wierzchołka wskazuje szczyt grzbietu i kończy pętlę projekcji. Przyszła iteracja zalewu może przepłynąć wokół podstawy grzbietu, w górę jego „tylnej” strony i po raz drugi wykryć ten sam grzbiet.
10. W tym celu wszelkie punkty szczytowe / graniczne, które zostaną wykryte więcej niż raz, nie będą BoundaryPoint.
11. Wszystkie punkty szczytowe / kalenicowe wykryte dokładnie raz są dołączane do punktów granicznych, a pętla projekcyjna w tym kierunku zostaje zakończona.
12. CS_Flood wykonuje przejście osi Z z tym samym kodem, używając punktów wygenerowanych przez przejście osi X jako dane wejściowe.
13. W tej chwili CS_Flood trwa naprzemiennie między dwoma kierunkami w nieskończoność. W końcu zakończę ogólną pętlę, gdy CS_Flood zakończy się, a bufor NextPass będzie pusty.

Idealnie w tym momencie punkty graniczne zawierałyby każdy wierzchołek występujący na naturalnym podziale drenażu. Krople wody lądujące w granicach ostatecznie spływają do tego samego niskiego punktu. Krople wody lądujące na granicy idą „gdzie indziej”.

Następnie:

1. Nie usuwając szablonu, ponownie zeskanuj teren w celu znalezienia najniższego, pozbawionego szablonów wierzchołka.
2. Iteruj CS_Flood.
3. Powtarzaj, aż szablon będzie pełny (lub coś podobnego).

3D jest trudny do zauważenia dzięki tym kolorom; pokazuje to linie konturu na integralnych elewacjach:
(otwór otoczony nasypem w pobliżu krawędzi)

Istnieje około 10 unikalnych sposobów drenażu przez wierzchołek; nadając każdemu unikalny kolor:
(widoczne okrągłe ślady narzędzia, ładnie pokazują „grzbiety”)

Pokazuje każdy punkt wygenerowany przez CS_Flood, granica lub w inny sposób, jako POINTLIST:

Algorytm zawsze prawie działa . Czasami działa nawet poprawnie. Innym razem algorytm jest wyraźnie zawarty we właściwym kształcie, ale będzie nadal generował punkty w nieskończoność. Jak widać na trzecim zrzucie ekranu, czasami się myli. Musi istnieć inna sytuacja / czynnik, który przeoczyłem. Byłbym wdzięczny za pomoc w znalezieniu mojego przeoczenia lub sugestie dotyczące prostszych i / lub bardziej eleganckich sposobów ataku na problem.

MissingPoint! może zostać uwzględniony poprzez wspomaganie algorytmu dodawania każdego nowego wykrytego BoundaryPoint do bufora NextPass. Podczas następnego przejścia 99% punktów wygenerowanych przez to wspomaganie pasma marnuje niewielką ilość czasu na GPU, stwierdzając, że nigdzie nie mogą iść i nic nie robiąc. Podczas pierwszego przejścia wysyłanie LowestPoint wraz z innymi punktami NextPass poradziłoby sobie również z tym konkretnym scenariuszem.

Wiem, że to prawdopodobne, i mając wystarczająco dużo czasu, będę w stanie pomóc zespołowi na tyle, by zrobić to, co chcę. Chciałbym to zrobić w lepszy, mądrzejszy, szybszy sposób, jeśli to możliwe, i nie mam jeszcze wystarczającego doświadczenia, aby wiedzieć lepiej.

Gdy kropla „próbowała” odwiedzić wierzchołek, szablon oznaczono za InterlockedExchangepomocą „oryginalnej wartości”, aby ustalić, czy już wzorowany (mimo że właśnie go nadpisałem).

Najlepszy algorytm, jaki wymyśliłem, nadał potopowi „podstawkę” i jedną zasadę: „nie spływaj ze wzgórza” (wysokości równe lub większe). To wyeliminowało prawie wszystkie skomplikowane testy. Chociaż ogólnie dobrze jest nie przepływać przez szczyty / grzbiety, płynie wzdłuż nich, ponieważ sąsiednie wierzchołki są „płaskie”. Czasami pozwala to kroplom przemknąć obok linii grzbietu.

Każdy punkt „za daleko” jest wtedy „przepływał” i wpłynie „do” obszaru drenażu (zatrzymuje się na 1) lub nie (zatrzymuje się na 0). „Notki” są odrzucane, a poprawiony notatnik jest kopiowany do „ostatecznego”. Jeśli finał jest już wytyczony, podkładkę na zarysowania odrzuca się. (Przyszłość: zderzenia te powinny łącznie reprezentować zewnętrzną granicę bieżącego obszaru zlewni).

Przy 10 FPS:

„Nots” są pokazane na czerwono, gdy duży obszar zostanie skopiowany do ostatecznego i zmieni kolor na zielony, wówczas algorytm powtarza się dla pozostałych nieoznaczonych obszarów.