FFmpeg
perlin.c
Go to the documentation of this file.
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 
30 #include "libavutil/lfg.h"
31 #include "libavutil/random_seed.h"
32 #include "perlin.h"
33 
34 static inline int inc(int num, int period)
35 {
36  num++;
37  if (period > 0)
38  num %= period;
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)
45  int h = hash & 15;
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.
82 static uint8_t ken_permutations[] = {
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 
101 int ff_perlin_init(FFPerlin *perlin, double period, int octaves, double persistence,
102  enum FFPerlinRandomMode random_mode, unsigned int random_seed)
103 {
104  int i;
105 
106  perlin->period = period;
107  perlin->octaves = octaves;
108  perlin->persistence = persistence;
109  perlin->random_mode = random_mode;
110  perlin->random_seed = random_seed;
111 
112  if (perlin->random_mode == FF_PERLIN_RANDOM_MODE_KEN) {
113  for (i = 0; i < 512; i++) {
114  perlin->permutations[i] = ken_permutations[i % 256];
115  }
116  } else {
117  AVLFG lfg;
118  uint8_t random_permutations[256];
119 
121  perlin->random_seed = av_get_random_seed();
122 
123  av_lfg_init(&lfg, perlin->random_seed);
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 
134  perlin->permutations[i] = perlin->permutations[i+256] = random_val;
135  }
136  }
137 
138  return 0;
139 }
140 
141 static double perlin_get(FFPerlin *perlin, double x, double y, double z)
142 {
143  int xi, yi, zi;
144  double xf, yf, zf;
145  double u, v, w;
146  const uint8_t *p = perlin->permutations;
147  double period = perlin->period;
148  int aaa, aba, aab, abb, baa, bba, bab, bbb;
149  double x1, x2, y1, y2;
150 
151  if (perlin->period > 0) {
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.
161  xi = (int)x & 255;
162  yi = (int)y & 255;
163  zi = (int)z & 255;
164 
165  xf = x - (int)x;
166  yf = y - (int)y;
167  zf = z - (int)z;
168 
169  // We also fade the location to smooth the result.
170  u = fade(xf);
171  v = fade(yf);
172  w = fade(zf);
173 
174  aaa = p[p[p[ xi ] + yi ] + zi ];
175  aba = p[p[p[ xi ] + inc(yi, period)] + zi ];
176  aab = p[p[p[ xi ] + yi ] + inc(zi, period)];
177  abb = p[p[p[ xi ] + inc(yi, period)] + inc(zi, period)];
178  baa = p[p[p[inc(xi, period)] + yi ] + zi ];
179  bba = p[p[p[inc(xi, period)] + inc(yi, period)] + zi ];
180  bab = p[p[p[inc(xi, period)] + yi ] + inc(zi, period)];
181  bbb = p[p[p[inc(xi, period)] + inc(yi, period)] + inc(zi, period)];
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.
188  x1 = lerp(grad(aaa, xf , yf , zf),
189  grad(baa, xf-1, yf , zf),
190  u);
191  x2 = lerp(grad(aba, xf , yf-1, zf),
192  grad(bba, xf-1, yf-1, zf),
193  u);
194  y1 = lerp(x1, x2, v);
195 
196  x1 = lerp(grad(aab, xf , yf , zf-1),
197  grad(bab, xf-1, yf , zf-1),
198  u);
199  x2 = lerp(grad(abb, xf , yf-1, zf-1),
200  grad(bbb, xf-1, yf-1, zf-1),
201  u);
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 
208 double ff_perlin_get(FFPerlin *perlin, double x, double y, double z)
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 
215  for (int i = 0; i < perlin->octaves; i++) {
216  total += perlin_get(perlin, x * frequency, y * frequency, z * frequency) * amplitude;
217  max_value += amplitude;
218  amplitude *= perlin->persistence;
219  frequency *= 2;
220  }
221 
222  return total / max_value;
223 }
224 
FFPerlin::random_mode
enum FFPerlinRandomMode random_mode
define how to compute the permutations array
Definition: perlin.h:68
av_lfg_init
av_cold void av_lfg_init(AVLFG *c, unsigned int seed)
Definition: lfg.c:32
u
#define u(width, name, range_min, range_max)
Definition: cbs_h2645.c:251
FFPerlin::period
double period
spatial repeat period, if negative it is ignored
Definition: perlin.h:46
perlin.h
w
uint8_t w
Definition: llviddspenc.c:38
b
#define b
Definition: input.c:41
fade
static double fade(double t)
Definition: perlin.c:66
hash
uint8_t hash[HASH_SIZE]
Definition: movenc.c:58
av_get_random_seed
uint32_t av_get_random_seed(void)
Get a seed to use in conjunction with random functions.
Definition: random_seed.c:167
FFPerlin
Perlin generator context.
Definition: perlin.h:42
av_lfg_get
static unsigned int av_lfg_get(AVLFG *c)
Get the next random unsigned 32-bit number using an ALFG.
Definition: lfg.h:53
lfg.h
xi
#define xi(width, name, var, range_min, range_max, subs,...)
Definition: cbs_h2645.c:418
ff_perlin_get
double ff_perlin_get(FFPerlin *perlin, double x, double y, double z)
Compute Perlin noise given the x, y, z coordinates.
Definition: perlin.c:208
grad
static double grad(int hash, double x, double y, double z)
Definition: perlin.c:42
period
it s the only field you need to keep assuming you have a context There is some magic you don t need to care about around this just let it vf default minimum maximum flags name is the option keep it simple and lowercase description are in without period
Definition: writing_filters.txt:89
ff_perlin_init
int ff_perlin_init(FFPerlin *perlin, double period, int octaves, double persistence, enum FFPerlinRandomMode random_mode, unsigned int random_seed)
Initialize the Perlin noise generator with parameters.
Definition: perlin.c:101
inc
static int inc(int num, int period)
Definition: perlin.c:34
AVLFG
Context structure for the Lagged Fibonacci PRNG.
Definition: lfg.h:33
FFPerlinRandomMode
FFPerlinRandomMode
Definition: perlin.h:31
FFPerlin::random_seed
unsigned int random_seed
when random_mode is set FF_PERLIN_RANDOM_MODE_RANDOM, set random seed used to compute the permutation...
Definition: perlin.h:74
a
The reader does not expect b to be semantically here and if the code is changed by maybe adding a a division or other the signedness will almost certainly be mistaken To avoid this confusion a new type was SUINT is the C unsigned type but it holds a signed int to use the same example SUINT a
Definition: undefined.txt:41
lerp
static double lerp(double a, double b, double x)
Definition: perlin.c:75
ken_permutations
static uint8_t ken_permutations[]
Definition: perlin.c:82
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:256
FFPerlin::octaves
int octaves
total number of components making up the noise, each one with doubled frequency
Definition: perlin.h:52
xf
#define xf(width, name, var, range_min, range_max, subs,...)
Definition: cbs_av1.c:598
FFPerlin::persistence
double persistence
ratio used to compute the amplitude of the next octave component with respect to the previous compone...
Definition: perlin.h:58
random_seed.h
FF_PERLIN_RANDOM_MODE_KEN
@ FF_PERLIN_RANDOM_MODE_KEN
Definition: perlin.h:33
FF_PERLIN_RANDOM_MODE_RANDOM
@ FF_PERLIN_RANDOM_MODE_RANDOM
Definition: perlin.h:32
h
h
Definition: vp9dsp_template.c:2070
FFPerlin::permutations
uint8_t permutations[512]
permutations array used to compute the Perlin noise hash
Definition: perlin.h:63
perlin_get
static double perlin_get(FFPerlin *perlin, double x, double y, double z)
Definition: perlin.c:141