1 /*
2 * This file is part of FFmpeg.
3 *
4 * FFmpeg is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * FFmpeg is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License along
15 * with FFmpeg; if not, write to the Free Software Foundation, Inc.,
16 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
17 */
18
19 /**
20 * @file
21 * Perlin Noise generator, based on code from:
22 * https://adrianb.io/2014/08/09/perlinnoise.html
23 *
24 * Original article from Ken Perlin:
25 * http://mrl.nyu.edu/~perlin/paper445.pdf
26 */
27
28 #include <math.h>
29
33
35 {
36 num++;
39 return num;
40 }
41
42 static inline double grad(
int hash,
double x,
double y,
double z)
43 {
44 // Take the hashed value and take the first 4 bits of it (15 == 0b1111)
46 // If the most significant bit (MSB) of the hash is 0 then set u = x. Otherwise y.
47 double u =
h < 8
/* 0b1000 */ ? x : y;
48 double v;
49
50 // In Ken Perlin's original implementation this was another
51 // conditional operator (?:), then expanded for readability.
52 if (
h < 4
/* 0b0100 */)
53 // If the first and second significant bits are 0 set v = y
54 v = y;
55 // If the first and second significant bits are 1 set v = x
56 else if (
h == 12
/* 0b1100 */ ||
h == 14
/* 0b1110 */)
57 v = x;
58 else
59 // If the first and second significant bits are not equal (0/1, 1/0) set v = z
60 v = z;
61
62 // Use the last 2 bits to decide if u and v are positive or negative. Then return their addition.
63 return ((
h&1) == 0 ?
u : -
u)+((
h&2) == 0 ? v : -v);
64 }
65
66 static inline double fade(
double t)
67 {
68 // Fade function as defined by Ken Perlin. This eases coordinate values
69 // so that they will "ease" towards integral values. This ends up smoothing
70 // the final output.
71 // use Horner method to compute: 6t^5 - 15t^4 + 10t^3
72 return t * t * t * (t * (t * 6 - 15) + 10);
73 }
74
75 static double lerp(
double a,
double b,
double x)
76 {
77 return a + x * (
b -
a);
78 }
79
80 // Hash lookup table as defined by Ken Perlin. This is a randomly
81 // arranged array of all numbers from 0-255 inclusive.
83 151, 160, 137, 91, 90, 15, 131, 13, 201, 95, 96, 53, 194, 233, 7, 225,
84 140, 36, 103, 30, 69, 142, 8, 99, 37, 240, 21, 10, 23, 190, 6, 148,
85 247, 120, 234, 75, 0, 26, 197, 62, 94, 252, 219, 203, 117, 35, 11, 32,
86 57, 177, 33, 88, 237, 149, 56, 87, 174, 20, 125, 136, 171, 168, 68, 175,
87 74, 165, 71, 134, 139, 48, 27, 166, 77, 146, 158, 231, 83, 111, 229, 122,
88 60, 211, 133, 230, 220, 105, 92, 41, 55, 46, 245, 40, 244, 102, 143, 54,
89 65, 25, 63, 161, 1, 216, 80, 73, 209, 76, 132, 187, 208, 89, 18, 169,
90 200, 196, 135, 130, 116, 188, 159, 86, 164, 100, 109, 198, 173, 186, 3, 64,
91 52, 217, 226, 250, 124, 123, 5, 202, 38, 147, 118, 126, 255, 82, 85, 212,
92 207, 206, 59, 227, 47, 16, 58, 17, 182, 189, 28, 42, 223, 183, 170, 213,
93 119, 248, 152, 2, 44, 154, 163, 70, 221, 153, 101, 155, 167, 43, 172, 9,
94 129, 22, 39, 253, 19, 98, 108, 110, 79, 113, 224, 232, 178, 185, 112, 104,
95 218, 246, 97, 228, 251, 34, 242, 193, 238, 210, 144, 12, 191, 179, 162, 241,
96 81, 51, 145, 235, 249, 14, 239, 107, 49, 192, 214, 31, 181, 199, 106, 157,
97 184, 84, 204, 176, 115, 121, 50, 45, 127, 4, 150, 254, 138, 236, 205, 93,
98 222, 114, 67, 29, 24, 72, 243, 141, 128, 195, 78, 66, 215, 61, 156, 180
99 };
100
103 {
105
111
113 for (
i = 0;
i < 512;
i++) {
115 }
116 } else {
118 uint8_t random_permutations[256];
119
122
124
125 for (
i = 0;
i < 256;
i++) {
126 random_permutations[
i] =
i;
127 }
128
129 for (
i = 0;
i < 256;
i++) {
130 unsigned int random_idx =
av_lfg_get(&lfg) % (256-
i);
131 uint8_t random_val = random_permutations[random_idx];
132 random_permutations[random_idx] = random_permutations[255-
i];
133
135 }
136 }
137
138 return 0;
139 }
140
142 {
148 int aaa, aba, aab, abb, baa, bba, bab, bbb;
149 double x1, x2, y1, y2;
150
152 // If we have any period on, change the coordinates to their "local" repetitions
153 x = fmod(x, perlin->
period);
154 y = fmod(y, perlin->
period);
155 z = fmod(z, perlin->
period);
156 }
157
158 // Calculate the "unit cube" that the point asked will be located in
159 // The left bound is ( |_x_|,|_y_|,|_z_| ) and the right bound is that
160 // plus 1. Next we calculate the location (from 0.0 to 1.0) in that cube.
162 yi = (int)y & 255;
163 zi = (int)z & 255;
164
166 yf = y - (int)y;
167 zf = z - (int)z;
168
169 // We also fade the location to smooth the result.
173
174 aaa =
p[
p[
p[
xi ] + yi ] + zi ];
182
183 // The gradient function calculates the dot product between a pseudorandom
184 // gradient vector and the vector from the input coordinate to the 8
185 // surrounding points in its unit cube.
186 // This is all then lerped together as a sort of weighted average based on the faded (u,v,w)
187 // values we made earlier.
192 grad(bba,
xf-1, yf-1, zf),
194 y1 =
lerp(x1, x2, v);
195
197 grad(bab,
xf-1, yf , zf-1),
200 grad(bbb,
xf-1, yf-1, zf-1),
202 y2 =
lerp(x1, x2, v);
203
204 // For convenience we bound it to 0 - 1 (theoretical min/max before is -1 - 1)
205 return (
lerp(y1, y2,
w) + 1) / 2;
206 }
207
209 {
210 double total = 0;
211 double frequency = 1;
212 double amplitude = 1;
213 double max_value = 0; // Used for normalizing result to 0.0 - 1.0
214
216 total +=
perlin_get(perlin, x * frequency, y * frequency, z * frequency) * amplitude;
217 max_value += amplitude;
219 frequency *= 2;
220 }
221
222 return total / max_value;
223 }