Θόρυβος Πέρλιν

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

Ιστορία[Επεξεργασία | επεξεργασία κώδικα]

Ο Κεν Πέρλιν ανέπτυξε τον θόρυβο Πέρλιν το 1983 ως αποτέλεσμα της απογοήτευσής του από την "μηχανική" εμφάνιση των εικόνων που δημιουργούνταν από υπολογιστή (CGI) εκείνη την εποχή^[2]. Περιέγραψε επίσημα τα ευρήματά του σε μια εργασία του στο SIGGRAPH το 1985 με τίτλο "An Image Synthesizer".^[3] Τον ανέπτυξε αφού εργάστηκε στην ταινία επιστημονικής φαντασίας Tron (1982) της Ντίσνεϊ για την εταιρεία κινουμένων σχεδίων Mathematical Applications Group (MAGI)^[4].Το 1997, ο Πέρλιν τιμήθηκε με το βραβείο Όσκαρ Τεχνικής Επίτευξης για τη δημιουργία του αλγορίθμου, η αιτιολογία του οποίου ήταν η εξής:^[5]^[6]^[7]^[8]

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

Ο Πέρλιν δεν υπέβαλε αίτηση για διπλώματα ευρεσιτεχνίας σχετικά με τον αλγόριθμο, αλλά το 2001 του χορηγήθηκε δίπλωμα ευρεσιτεχνίας για τη χρήση 3D+ υλοποιήσεων του θορύβου simplex για τη σύνθεση υφών. Ο θόρυβος Simplex έχει τον ίδιο σκοπό, αλλά χρησιμοποιεί ένα απλούστερο πλέγμα πλήρωσης χώρου. Ο θόρυβος Simplex ανακουφίζει ορισμένα από τα προβλήματα του "κλασικού θορύβου" του Πέρλιν, μεταξύ των οποίων η υπολογιστική πολυπλοκότητα και τα οπτικά σημαντικά κατευθυντικά τεχνουργήματα^[9].

Εφαρμογές[Επεξεργασία | επεξεργασία κώδικα]

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

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

Χρησιμοποιείται συχνά σε βιντεοπαιχνίδια για να δημιουργήσει διαδικαστικά παραγόμενο έδαφος που να μοιάζει φυσικό.

Λεπτομέρεια αλγορίθμου[Επεξεργασία | επεξεργασία κώδικα]

Ο θόρυβος Πέρλιν υλοποιείται συνήθως ως συνάρτηση δύο, τριών ή τεσσάρων διαστάσεων, αλλά μπορεί να οριστεί για οποιονδήποτε αριθμό διαστάσεων. Μια υλοποίηση περιλαμβάνει συνήθως τρία βήματα: τον ορισμό ενός πλέγματος τυχαίων διανυσμάτων κλίσης, τον υπολογισμό του γινομένου τελείας μεταξύ των διανυσμάτων κλίσης και των μετατοπίσεών τους και την παρεμβολή μεταξύ αυτών των τιμών.^[10]

Ορισμός πλέγματος[Επεξεργασία | επεξεργασία κώδικα]

Ένα δισδιάστατο πλέγμα διανυσμάτων κλίσεων.

Ορίστε ένα $n$ -διάστατο πλέγμα όπου κάθε διατομή του πλέγματος συνδέεται με ένα σταθερό τυχαίο n-διάστατο διάνυσμα κλίσης μοναδιαίου μήκους, εκτός από τη μονοδιάστατη περίπτωση όπου οι κλίσεις είναι τυχαία κλιμάκια μεταξύ -1 και 1.

Εσωτερικό γινόμενο[Επεξεργασία | επεξεργασία κώδικα]

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

Σφαίρα φωτιάς που παράγεται από το "(θόρυβο Πέρλιν)"

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

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

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

Για ένα σημείο σε ένα δισδιάστατο πλέγμα, αυτό θα απαιτήσει τον υπολογισμό τεσσάρων διανυσμάτων μετατόπισης και γινομένων τελείας, ενώ σε τρεις διαστάσεις θα απαιτήσει οκτώ διανύσματα μετατόπισης και οκτώ σωτερικά γινόμενα. Γενικά, ο αλγόριθμος έχει Συμβολισμός Big $O (2 n)$ ^[11] σε $n$ διαστάσεις.

Παρεμβολή[Επεξεργασία | επεξεργασία κώδικα]

Το τελικό βήμα είναι η παρεμβολή μεταξύ των $2 n$ παραγώγων σημείων. Η παρεμβολή πραγματοποιείται με τη χρήση μιας συνάρτησης που έχει μηδενική πρώτη παράγωγο (και ενδεχομένως και δεύτερη παράγωγο) στους $2 n$ κόμβους του πλέγματος. Επομένως, σε σημεία κοντά στους κόμβους πλέγματος, η έξοδος θα προσεγγίζει το Εσωτερικό γινόμενο του διανύσματος κλίσης του κόμβου και του διανύσματος μετατόπισης προς τον κόμβο. Αυτό σημαίνει ότι η συνάρτηση θορύβου θα διέρχεται από το 0 σε κάθε κόμβο, δίνοντας στον θόρυβο Πέρλιν τη χαρακτηριστική του εμφάνιση.

Εάν $n = 1$ , ένα παράδειγμα συνάρτησης που παρεμβάλλει μεταξύ της τιμής $a 0$ στον κόμβο πλέγματος 0 και της τιμής $a 1$ στον κόμβο πλέγματος 1 είναι το εξής

f(x)=a_{0}+\operatorname {smoothstep} (x)\cdot (a_{1}-a_{0})\quad {\text{for }}0\leq x\leq 1

Οι συναρτήσεις θορύβου για χρήση σε γραφικά υπολογιστών παράγουν συνήθως τιμές στο εύρος [–1.0, 1.0] και μπορούν να κλιμακωθούν ανάλογα.

Ψευδοκώδικας[Επεξεργασία | επεξεργασία κώδικα]

Ακολουθεί ο ψευδοκώδικας για την εφαρμογή του θορύβου του Πέρλιν σε δισδιάστατο χώρο.

 // Function to transition smoothly from 0.0 to 1.0 in the range [0.0, 1.0]
 function smoothstep(float w) {
     if (w <= 0.0) return 0.0;
     if (w >= 1.0) return 1.0;
     return w * w * (3.0 - 2.0 * w);
 }
 
 // Function to interpolate smoothly between a0 and a1
 // Weight w should be in the range [0.0, 1.0]
 function interpolate(float a0, float a1, float w) {
     return a0 + (a1 - a0) * smoothstep(w);
 }
 
 // Computes the dot product of the distance and gradient vectors.
 function dotGridGradient(int ix, int iy, float x, float y) {
 
     // Precomputed (or otherwise) gradient vectors at each grid node
     extern float Gradient[IYMAX][IXMAX][2];
 
     // Compute the distance vector
     float dx = x - (float)ix;
     float dy = y - (float)iy;
 
     // Compute the dot-product
     return (dx*Gradient[iy][ix][0] + dy*Gradient[iy][ix][1]);
 }
 
 // Compute Perlin noise at coordinates x, y
 function perlin(float x, float y) {
 
     // Determine grid cell coordinates
     int x0 = floor(x);
     int x1 = x0 + 1;
     int y0 = floor(y);
     int y1 = y0 + 1;
 
     // Determine interpolation weights
     // Could also use higher order polynomial/s-curve here
     float sx = x - (float)x0;
     float sy = y - (float)y0;
 
     // Interpolate between grid point gradients
     float n0, n1, ix0, ix1, value;
     n0 = dotGridGradient(x0, y0, x, y);
     n1 = dotGridGradient(x1, y0, x, y);
     ix0 = interpolate(n0, n1, sx);
     n0 = dotGridGradient(x0, y1, x, y);
     n1 = dotGridGradient(x1, y1, x, y);
     ix1 = interpolate(n0, n1, sx);
     value = interpolate(ix0, ix1, sy);
 
     return value;
 }

Μεταβολή[Επεξεργασία | επεξεργασία κώδικα]

Πολλές εφαρμογές του θορύβου Πέρλιν χρησιμοποιούν το ίδιο σύνολο μεταθέσεων που χρησιμοποίησε ο Κεν Πέρλιν στην αρχική του εφαρμογή^[12]. Η εφαρμογή αυτή έχει ως εξής:

int permutation[] = { 151, 160, 137,  91,  90,  15, 131,  13, 201,  95,  96,  53, 194, 233,   7, 225,
                      140,  36, 103,  30,  69, 142,   8,  99,  37, 240,  21,  10,  23, 190,   6, 148,
                      247, 120, 234,  75,   0,  26, 197,  62,  94, 252, 219, 203, 117,  35,  11,  32,
                       57, 177,  33,  88, 237, 149,  56,  87, 174,  20, 125, 136, 171, 168,  68, 175,
                       74, 165,  71, 134, 139,  48,  27, 166,  77, 146, 158, 231,  83, 111, 229, 122,
                       60, 211, 133, 230, 220, 105,  92,  41,  55,  46, 245,  40, 244, 102, 143,  54,
                       65,  25,  63, 161,   1, 216,  80,  73, 209,  76, 132, 187, 208,  89,  18, 169,
                      200, 196, 135, 130, 116, 188, 159,  86, 164, 100, 109, 198, 173, 186,   3,  64,
                       52, 217, 226, 250, 124, 123,   5, 202,  38, 147, 118, 126, 255,  82,  85, 212,
                      207, 206,  59, 227,  47,  16,  58,  17, 182, 189,  28,  42, 223, 183, 170, 213,
                      119, 248, 152,   2,  44, 154, 163,  70, 221, 153, 101, 155, 167,  43, 172,   9,
                      129,  22,  39, 253,  19,  98, 108, 110,  79, 113, 224, 232, 178, 185, 112, 104,
                      218, 246,  97, 228, 251,  34, 242, 193, 238, 210, 144,  12, 191, 179, 162, 241,
                       81,  51, 145, 235, 249,  14, 239, 107,  49, 192, 214,  31, 181, 199, 106, 157,
                      184,  84, 204, 176, 115, 121,  50,  45, 127,   4, 150, 254, 138, 236, 205,  93,
                      222, 114,  67,  29,  24,  72, 243, 141, 128, 195,  78,  66, 215,  61, 156, 180 };

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

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

↑ «Ken Perlin». physbam.stanford.edu. Ανακτήθηκε στις 25 Οκτωβρίου 2023.
↑ Perlin, Ken. «Making Noise». noisemachine.com. Ken Perlin. Αρχειοθετήθηκε από το πρωτότυπο στις 8 Οκτωβρίου 2007.
↑ Perlin, Ken (July 1985). «An image synthesizer». ACM SIGGRAPH Computer Graphics 19 (97–8930): 287–296. doi:10.1145/325165.325247.
↑ Perlin, Ken. «In the beginning: The Pixel Stream Editor» (PDF). Ανακτήθηκε στις 31 Μαΐου 2022.
↑ Tanner, Mike. «Oscar is FX Wizard's Reward» (στα αγγλικά). Wired. ISSN 1059-1028. https://www.wired.com/1997/01/oscar-is-fx-wizards-reward/. Ανακτήθηκε στις 2022-05-31.
↑ Original source code
↑ «Archived copy». Αρχειοθετήθηκε από το πρωτότυπο στις 1 Μαΐου 2018. Ανακτήθηκε στις 29 Μαΐου 2011. CS1 maint: BOT: original-url status unknown (link) of Ken Perlin's 'coherent noise function'
↑ Gustavson, Stefan. «Simplex noise demystified» (PDF). Αρχειοθετήθηκε από το πρωτότυπο (PDF) στις 21 Μαρτίου 2023. Ανακτήθηκε στις 24 Απριλίου 2019.
↑ US patent 6867776, Kenneth Perlin, "Standard for perlin noise", issued 2005-03-15, assigned to Kenneth Perlin and Wsou Investments LLC
↑ Gustavson, Stefan. «Simplex noise demystified» (PDF). Αρχειοθετήθηκε από το πρωτότυπο (PDF) στις 10 Μαρτίου 2023. Ανακτήθηκε στις 24 Απριλίου 2019.
↑ «Wayback Machine» (PDF). web.archive.org. Αρχειοθετήθηκε από το πρωτότυπο στις 8 Μαρτίου 2014. Ανακτήθηκε στις 23 Οκτωβρίου 2023. CS1 maint: Unfit url (link)
↑ Perlin, Ken. «Perlin noise». Ανακτήθηκε στις 26 Αυγούστου 2020.
↑ «Perlin Noise: Part 2». Αρχειοθετήθηκε από το πρωτότυπο στις 17 Φεβρουαρίου 2023. Ανακτήθηκε στις 26 Αυγούστου 2020.

[1] «Ken Perlin». physbam.stanford.edu. Ανακτήθηκε στις 25 Οκτωβρίου 2023.

[ken_powerpoint-2] Perlin, Ken. «Making Noise». noisemachine.com. Ken Perlin. Αρχειοθετήθηκε από το πρωτότυπο στις 8 Οκτωβρίου 2007.

[Perlin:1985:IS:325165.325247-3] Perlin, Ken (July 1985). «An image synthesizer». ACM SIGGRAPH Computer Graphics 19 (97–8930): 287–296. doi:10.1145/325165.325247.

[4] Perlin, Ken. «In the beginning: The Pixel Stream Editor» (PDF). Ανακτήθηκε στις 31 Μαΐου 2022.

[5] Tanner, Mike. «Oscar is FX Wizard's Reward» (στα αγγλικά). Wired. ISSN 1059-1028. https://www.wired.com/1997/01/oscar-is-fx-wizards-reward/. Ανακτήθηκε στις 2022-05-31.

[kens_aa-6] Original source code

[7] «Archived copy». Αρχειοθετήθηκε από το πρωτότυπο στις 1 Μαΐου 2018. Ανακτήθηκε στις 29 Μαΐου 2011. CS1 maint: BOT: original-url status unknown (link) of Ken Perlin's 'coherent noise function'

[8] Gustavson, Stefan. «Simplex noise demystified» (PDF). Αρχειοθετήθηκε από το πρωτότυπο (PDF) στις 21 Μαρτίου 2023. Ανακτήθηκε στις 24 Απριλίου 2019.

[9] US patent 6867776, Kenneth Perlin, "Standard for perlin noise", issued 2005-03-15, assigned to Kenneth Perlin and Wsou Investments LLC

[10] Gustavson, Stefan. «Simplex noise demystified» (PDF). Αρχειοθετήθηκε από το πρωτότυπο (PDF) στις 10 Μαρτίου 2023. Ανακτήθηκε στις 24 Απριλίου 2019.

[11] «Wayback Machine» (PDF). web.archive.org. Αρχειοθετήθηκε από το πρωτότυπο στις 8 Μαρτίου 2014. Ανακτήθηκε στις 23 Οκτωβρίου 2023. CS1 maint: Unfit url (link)

[12] Perlin, Ken. «Perlin noise». Ανακτήθηκε στις 26 Αυγούστου 2020.

[13] «Perlin Noise: Part 2». Αρχειοθετήθηκε από το πρωτότυπο στις 17 Φεβρουαρίου 2023. Ανακτήθηκε στις 26 Αυγούστου 2020.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]