Αλγόριθμος διαμαντιού τετραγώνου

Ο Αλγόριθμος διαμαντιού τετραγώνου^[1] είναι μια μέθοδος δημιουργίας χαρτών ύψους για γραφικά υπολογιστών. Πρόκειται για έναν ελαφρώς καλύτερο αλγόριθμο σε σχέση με την τρισδιάστατη εφαρμογή του αλγορίθμου μετατόπισης του μέσου σημείου, ο οποίος παράγει δισδιάστατα τοπία. Είναι επίσης γνωστός ως τυχαίο φράκταλ μετατόπισης μεσαίου σημείου, φράκταλ νέφους ή φράκταλ πλάσματος, λόγω του φαινομένου πλάσματος που παράγει κατά την εφαρμογή του.

Κινούμενο φράκταλ πλάσματος με ανακύκλωση χρώματος

Η ιδέα παρουσιάστηκε για πρώτη φορά από τους Φουρνιέ, Φούσσελ και Κάρπεντερ στο SIGGRAPH το 1982^[2] .

Ο αλγόριθμος διαμαντιού τετραγώνου ξεκινάει από ένα δισδιάστατο πλέγμα και στη συνέχεια δημιουργεί τυχαία το ύψος του εδάφους από τέσσερις αρχικές τιμές που είναι τοποθετημένες σε ένα πλέγμα σημείων, έτσι ώστε ολόκληρο το επίπεδο να καλύπτεται από τετράγωνα.

Περιγραφή

Ο αλγόριθμος του διαμαντιού τετραγώνου ξεκινά με έναν δισδιάστατο τετραγωνικό πίνακα πλάτους και ύψους 2ⁿ + 1. Τα τέσσερα γωνιακά σημεία του πίνακα πρέπει πρώτα να οριστούν σε αρχικές τιμές. Στη συνέχεια εκτελούνται εναλλάξ τα βήματα του διαμαντιού και του τετραγώνου μέχρι να οριστούν όλες οι τιμές του πίνακα.

Το βήμα διαμαντιού: Για κάθε τετράγωνο του πίνακα, ορίστε το μέσο σημείο του τετραγώνου αυτού να είναι ο μέσος όρος των τεσσάρων γωνιακών σημείων συν μια τυχαία τιμή.
Το βήμα του τετραγώνου: Για κάθε διαμάντι στον πίνακα, ορίστε το μέσο σημείο αυτού του διαμαντιού να είναι ο μέσος όρος των τεσσάρων γωνιακών σημείων συν μια τυχαία τιμή.

Σε κάθε επανάληψη, το μέγεθος της τυχαίας τιμής θα πρέπει να πολλαπλασιάζεται με 2^−h, όπου h είναι μια τιμή μεταξύ 0,0 και 1,0 (χαμηλότερες τιμές παράγουν πιο τραχύ έδαφος)^[3].

Κατά τη διάρκεια των τετραγωνικών βημάτων, στα σημεία που βρίσκονται στα άκρα του πίνακα θα οριστούν μόνο τρεις γειτονικές τιμές αντί για τέσσερις. Υπάρχουν διάφοροι τρόποι για να αντιμετωπιστεί αυτή η επιπλοκή - ο απλούστερος είναι να ληφθεί ο μέσος όρος μόνο των τριών γειτονικών τιμών. Μια άλλη επιλογή είναι η "περιτύλιξη", λαμβάνοντας την τέταρτη τιμή από την άλλη πλευρά του πίνακα. Όταν χρησιμοποιείται με συνεπείς αρχικές γωνιακές τιμές, η μέθοδος αυτή επιτρέπει επίσης τη συρραφή των παραγόμενων φράκταλ χωρίς ασυνέχειες.

Απεικόνιση

Η παρακάτω εικόνα δείχνει τα βήματα που απαιτούνται για την εκτέλεση του αλγορίθμου του διαμαντιού-τετραγώνου σε έναν πίνακα 5 × 5.

Εφαρμογές

Αυτός ο αλγόριθμος μπορεί να χρησιμοποιηθεί για τη δημιουργία ρεαλιστικών τοπίων και διάφορες υλοποιήσεις χρησιμοποιούνται σε λογισμικό γραφικών υπολογιστών όπως το πρόγραμμα Terragen. Εφαρμόζεται επίσης ως κοινό συστατικό σε διαδικαστικές υφές.

Τεχνουργήματα και επεκτάσεις

Ο αλγόριθμος του διαμαντιού-τετραγώνου αναλύθηκε από τον Γκέιβιν Σ. Π. Μίλερ στο SIGGRAPH 1986^[4], ο οποίος τον περιέγραψε ως ελαττωματικό επειδή ο αλγόριθμος παράγει αξιοσημείωτες κάθετες και οριζόντιες " ζάρες" λόγω της σημαντικότερης διαταραχής που λαμβάνει χώρα σε ένα ορθογώνιο πλέγμα. Τα τετελεσμένα του πλέγματος αντιμετωπίστηκαν σε έναν γενικευμένο αλγόριθμο που εισήγαγε ο J.P. Λιούις.^[5] Σε αυτή την παραλλαγή τα βάρη στα γειτονικά σημεία λαμβάνονται με την επίλυση ενός μικρού γραμμικού συστήματος με κίνητρο τη θεωρία της εκτίμησης, αντί να είναι σταθερά. Ο αλγόριθμος του Λιούις επιτρέπει επίσης τη σύνθεση μη κλασματικών χαρτών ύψους, όπως κυλιόμενων λόφων ή ωκεάνιων κυμάτων. Παρόμοια αποτελέσματα μπορούν να επιτευχθούν αποτελεσματικά με τη σύνθεση Fourier,^[6] αν και χάνεται η δυνατότητα προσαρμοστικής βελτίωσης. Ο αλγόριθμος διαμαντιού τετραγώνου και οι βελτιώσεις του εξετάζονται στο βιβλίο των των Πίτγκεν και Σάουπε "Η επιστήμη των μορφοκλασματικών εικόνων (The Science of Fractal Images)"^[6].

Δείτε επίσης

Παραπομπές

↑ «The Diamond Square Algorithm». learn.64bitdragon.com. Ανακτήθηκε στις 30 Αυγούστου 2023.
↑ Fournier, Alain; Fussell, Don; Carpenter, Loren (June 1982). «Computer rendering of stochastic models». Communications of the ACM 25 (6): 371–384. doi:10.1145/358523.358553. ISSN 0001-0782.
↑ «Generating Random Fractal Terrain». 20 Απριλίου 2006. Αρχειοθετήθηκε από το πρωτότυπο στις 20 Απριλίου 2006. Ανακτήθηκε στις 13 Δεκεμβρίου 2022.
↑ Miller, Gavin S. P. (August 1986). «The definition and rendering of terrain maps». ACM SIGGRAPH Computer Graphics 20 (4): 39–48. doi:10.1145/15886.15890.
↑ Lewis, J. P. (1 July 1987). «Generalized stochastic subdivision». ACM Transactions on Graphics 6 (3): 167–190. doi:10.1145/35068.35069. https://archive.org/details/sim_acm-transactions-on-graphics_1987-07_6_3/page/167.
↑ ^6,0 ^6,1 Peitgen, Heinz-Otto, Dietmar Saupe (1988). The Science of Fractal Images . New York: Springer-Verlag. ISBN 978-0-387-96608-3.

[1] «The Diamond Square Algorithm». learn.64bitdragon.com. Ανακτήθηκε στις 30 Αυγούστου 2023.

[fournier-2] Fournier, Alain; Fussell, Don; Carpenter, Loren (June 1982). «Computer rendering of stochastic models». Communications of the ACM 25 (6): 371–384. doi:10.1145/358523.358553. ISSN 0001-0782.

[3] «Generating Random Fractal Terrain». 20 Απριλίου 2006. Αρχειοθετήθηκε από το πρωτότυπο στις 20 Απριλίου 2006. Ανακτήθηκε στις 13 Δεκεμβρίου 2022.

[miller-4] Miller, Gavin S. P. (August 1986). «The definition and rendering of terrain maps». ACM SIGGRAPH Computer Graphics 20 (4): 39–48. doi:10.1145/15886.15890.

[5] Lewis, J. P. (1 July 1987). «Generalized stochastic subdivision». ACM Transactions on Graphics 6 (3): 167–190. doi:10.1145/35068.35069. https://archive.org/details/sim_acm-transactions-on-graphics_1987-07_6_3/page/167.

[PeitgenSaupe-6] 6,0 ^6,1 Peitgen, Heinz-Otto, Dietmar Saupe (1988). The Science of Fractal Images . New York: Springer-Verlag. ISBN 978-0-387-96608-3.

[1]

[2]

[3]

[4]

[5]

[6]