Algorytm diamentowo-kwadratowy
Algorytm diamentowo-kwadratowy to metoda generowania map wysokości dla grafiki komputerowej . Jest to nieco lepszy algorytm niż trójwymiarowa implementacja algorytmu przemieszczenia punktu środkowego, która tworzy dwuwymiarowe krajobrazy. Jest również znany jako losowy fraktal przemieszczenia punktu środkowego , fraktal chmury lub fraktal plazmy , ze względu na efekt plazmy wytwarzany po zastosowaniu.
Pomysł został po raz pierwszy przedstawiony przez Fourniera , Fussella i Carpentera w firmie SIGGRAPH w 1982 roku.
Algorytm diamentowo-kwadratowy zaczyna się od dwuwymiarowej siatki, a następnie losowo generuje wysokość terenu na podstawie czterech wartości początkowych ułożonych w siatkę punktów, tak że cała płaszczyzna jest pokryta kwadratami.
Opis
Algorytm diamentowo-kwadratowy zaczyna się od dwuwymiarowej kwadratowej tablicy o szerokości i wysokości 2 n + 1. Cztery punkty narożne tablicy muszą najpierw zostać ustawione na wartości początkowe. Kroki rombu i kwadratu są następnie wykonywane naprzemiennie, aż wszystkie wartości tablicy zostaną ustawione.
- Krok rombu: dla każdego kwadratu w tablicy ustaw środek tego kwadratu jako średnią z czterech punktów narożnych plus losową wartość.
- Krok kwadratu: dla każdego rombu w tablicy ustaw punkt środkowy tego rombu jako średnią czterech punktów narożnych plus losową wartość.
W każdej iteracji wielkość losowej wartości należy pomnożyć przez 2 −h , gdzie h jest wartością z przedziału od 0,0 do 0,1 (niższe wartości dają bardziej nierówny teren).
Podczas kroków kwadratowych punkty znajdujące się na krawędziach tablicy będą miały ustawione tylko trzy sąsiednie wartości zamiast czterech. Istnieje wiele sposobów radzenia sobie z tą komplikacją – najprostszym jest wzięcie średniej tylko z trzech sąsiednich wartości. Inną opcją jest „zawijanie”, biorąc czwartą wartość z drugiej strony tablicy. Ta metoda, używana ze spójnymi początkowymi wartościami narożników, umożliwia również łączenie wygenerowanych fraktali bez nieciągłości.
Wyobrażanie sobie
Poniższy obraz pokazuje kroki związane z uruchomieniem algorytmu diamentowo-kwadratowego na tablicy 5 × 5.
Aplikacje
Algorytm ten może być używany do generowania realistycznie wyglądających krajobrazów , a różne implementacje są używane w oprogramowaniu do grafiki komputerowej, takim jak Terragen . Można go również stosować jako wspólny składnik tekstur proceduralnych .
Artefakty i rozszerzenia
Algorytm diamentowo-kwadratowy został przeanalizowany przez Gavina SP Millera w SIGGRAPH 1986, który opisał go jako wadliwy, ponieważ algorytm wytwarza zauważalne pionowe i poziome „zagniecenia” z powodu najbardziej znaczących zakłóceń zachodzących w prostokątnej siatce. Artefakty siatki zostały rozwiązane w uogólnionym algorytmie wprowadzonym przez JP Lewisa. W tym wariancie wagi sąsiednich punktów uzyskuje się przez rozwiązanie małego układu liniowego motywowanego teorią estymacji, a nie ustalania. Algorytm Lewisa umożliwia również syntezę niefraktalnych map wysokości, takich jak wzgórza lub fale oceanu. Podobne wyniki można skutecznie uzyskać za pomocą syntezy Fouriera, chociaż traci się możliwość udokładnienia adaptacyjnego. Algorytm diamentowo-kwadratowy i jego udoskonalenia zostały omówione w książce.
- ^ Fournier, Alain; Fussell, Don; Stolarz, Loren (czerwiec 1982). „Komputerowe renderowanie modeli stochastycznych” . Komunikaty ACM . 25 (6): 371–384. doi : 10.1145/358523.358553 .
- ^ Fournier, Alain; Fussell, Don; Stolarz, Loren (czerwiec 1982). „Komputerowe renderowanie modeli stochastycznych” . Komunikaty ACM . 25 (6): 371–384. doi : 10.1145/358523.358553 . ISSN 0001-0782 .
- ^ „Generowanie losowego fraktalnego terenu” . web.archiwum.org . 2006-04-20 . Źródło 2022-12-13 .
- ^ Miller, Gavin SP (sierpień 1986). „Definicja i renderowanie map terenu”. ACM SIGGRAPH Grafika komputerowa . 20 (4): 39–48. doi : 10.1145/15886.15890 .
- ^ Lewis, JP (1 lipca 1987). „Uogólniony podział stochastyczny”. Transakcje ACM na grafice . 6 (3): 167–190. CiteSeerX 10.1.1.21.3719 . doi : 10.1145/35068.35069 .
- ^ ab Peitgen , Heinz-Otto, Dietmar Saupe (1988). Nauka obrazów fraktalnych . Nowy Jork: Springer-Verlag. ISBN 978-0-387-96608-3 .
Linki zewnętrzne
- Prosty moduł mapy wysokości typu open source dla Lua wykorzystujący algorytm diamentowo-kwadratowy
- Generowanie losowego terenu fraktalnego: algorytm kwadratu diamentu z GameProgrammer.com
- Plasma Fractal ze strony internetowej Justina Seystera
- Fraktale plazmowe ze strony domowej Patricka Hahna
- Samouczek dotyczący terenu z Lighthouse3d.com
- Losowe przemieszczenie punktu środkowego z płótnem
- Metoda losowego przemieszczenia punktu środkowego
- Algorytm diamentu i kwadratu na Github (PHP)
- Przykład jazdy próbnej implementacji algorytmu na blogu Clean Coder wuja Boba
- Implementacja X11 z klasycznym przewijaniem w bok Xmountains . Szczegóły algorytmu .
- Implementacja Pythona , krótka i prosta. Obsługuje zarówno stałe, jak i okresowe warunki brzegowe.