lavfi: add Perlin noise generator

5 files changed, 496 insertions, 0 deletions

diff --git a/libavfilter/Makefile b/libavfilter/Makefile
index 5992fd161f..63088e9286 100644
--- a/libavfilter/Makefile
+++ b/libavfilter/Makefile
@@ -603,6 +603,7 @@ OBJS-$(CONFIG_NULLSRC_FILTER)                += vsrc_testsrc.o
 OBJS-$(CONFIG_OPENCLSRC_FILTER)              += vf_program_opencl.o opencl.o
 OBJS-$(CONFIG_PAL75BARS_FILTER)              += vsrc_testsrc.o
 OBJS-$(CONFIG_PAL100BARS_FILTER)             += vsrc_testsrc.o
+OBJS-$(CONFIG_PERLIN_FILTER)                 += vsrc_perlin.o perlin.o
 OBJS-$(CONFIG_QRENCODE_FILTER)               += qrencode.o textutils.o
 OBJS-$(CONFIG_QRENCODESRC_FILTER)            += qrencode.o textutils.o
 OBJS-$(CONFIG_RGBTESTSRC_FILTER)             += vsrc_testsrc.o
diff --git a/libavfilter/allfilters.c b/libavfilter/allfilters.c
index c532682fc2..63600e9b58 100644
--- a/libavfilter/allfilters.c
+++ b/libavfilter/allfilters.c
@@ -569,6 +569,7 @@ extern const AVFilter ff_vsrc_openclsrc;
 extern const AVFilter ff_vsrc_qrencodesrc;
 extern const AVFilter ff_vsrc_pal75bars;
 extern const AVFilter ff_vsrc_pal100bars;
+extern const AVFilter ff_vsrc_perlin;
 extern const AVFilter ff_vsrc_rgbtestsrc;
 extern const AVFilter ff_vsrc_sierpinski;
 extern const AVFilter ff_vsrc_smptebars;
diff --git a/libavfilter/perlin.c b/libavfilter/perlin.c
new file mode 100644
index 0000000000..09bae7ad33
--- /dev/null
+++ b/libavfilter/perlin.c
@@ -0,0 +1,224 @@
+/*
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with FFmpeg; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+/**
+ * @file
+ * Perlin Noise generator, based on code from:
+ * https://adrianb.io/2014/08/09/perlinnoise.html
+ *
+ * Original article from Ken Perlin:
+ * http://mrl.nyu.edu/~perlin/paper445.pdf
+ */
+
+#include <math.h>
+
+#include "libavutil/lfg.h"
+#include "libavutil/random_seed.h"
+#include "perlin.h"
+
+static inline int inc(int num, int period)
+{
+    num++;
+    if (period > 0)
+        num %= period;
+    return num;
+}
+
+static inline double grad(int hash, double x, double y, double z)
+{
+    // Take the hashed value and take the first 4 bits of it (15 == 0b1111)
+    int h = hash & 15;
+    // If the most significant bit (MSB) of the hash is 0 then set u = x.  Otherwise y.
+    double u = h < 8 /* 0b1000 */ ? x : y;
+    double v;
+
+    // In Ken Perlin's original implementation this was another
+    // conditional operator (?:), then expanded for readability.
+    if (h < 4 /* 0b0100 */)
+        // If the first and second significant bits are 0 set v = y
+        v = y;
+    // If the first and second significant bits are 1 set v = x
+    else if (h == 12 /* 0b1100 */ || h == 14 /* 0b1110 */)
+        v = x;
+    else
+        // If the first and second significant bits are not equal (0/1, 1/0) set v = z
+        v = z;
+
+    // Use the last 2 bits to decide if u and v are positive or negative.  Then return their addition.
+    return ((h&1) == 0 ? u : -u)+((h&2) == 0 ? v : -v);
+}
+
+static inline double fade(double t)
+{
+    // Fade function as defined by Ken Perlin. This eases coordinate values
+    // so that they will "ease" towards integral values. This ends up smoothing
+    // the final output.
+    // use Horner method to compute: 6t^5 - 15t^4 + 10t^3
+    return t * t * t * (t * (t * 6 - 15) + 10);
+}
+
+static double lerp(double a, double b, double x)
+{
+    return a + x * (b - a);
+}
+
+// Hash lookup table as defined by Ken Perlin.  This is a randomly
+// arranged array of all numbers from 0-255 inclusive.
+static uint8_t ken_permutations[] = {
+    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
+};
+
+int ff_perlin_init(FFPerlin *perlin, double period, int octaves, double persistence,
+                   enum FFPerlinRandomMode random_mode, unsigned int random_seed)
+{
+    int i;
+
+    perlin->period = period;
+    perlin->octaves = octaves;
+    perlin->persistence = persistence;
+    perlin->random_mode = random_mode;
+    perlin->random_seed = random_seed;
+
+    if (perlin->random_mode == FF_PERLIN_RANDOM_MODE_KEN) {
+        for (i = 0; i < 512; i++) {
+            perlin->permutations[i] = ken_permutations[i % 256];
+        }
+    } else {
+        AVLFG lfg;
+        uint8_t random_permutations[256];
+
+        if (perlin->random_mode == FF_PERLIN_RANDOM_MODE_RANDOM)
+            perlin->random_seed = av_get_random_seed();
+
+        av_lfg_init(&lfg, perlin->random_seed);
+
+        for (i = 0; i < 256; i++) {
+            random_permutations[i] = i;
+        }
+
+        for (i = 0; i < 256; i++) {
+            unsigned int random_idx = av_lfg_get(&lfg) % (256-i);
+            uint8_t random_val = random_permutations[random_idx];
+            random_permutations[random_idx] = random_permutations[256-i];
+
+            perlin->permutations[i] = perlin->permutations[i+256] = random_val;
+        }
+    }
+
+    return 0;
+}
+
+static double perlin_get(FFPerlin *perlin, double x, double y, double z)
+{
+    int xi, yi, zi;
+    double xf, yf, zf;
+    double u, v, w;
+    const uint8_t *p = perlin->permutations;
+    double period = perlin->period;
+    int aaa, aba, aab, abb, baa, bba, bab, bbb;
+    double x1, x2, y1, y2;
+
+    if (perlin->period > 0) {
+        // If we have any period on, change the coordinates to their "local" repetitions
+        x = fmod(x, perlin->period);
+        y = fmod(y, perlin->period);
+        z = fmod(z, perlin->period);
+    }
+
+    // Calculate the "unit cube" that the point asked will be located in
+    // The left bound is ( |_x_|,|_y_|,|_z_| ) and the right bound is that
+    // plus 1.  Next we calculate the location (from 0.0 to 1.0) in that cube.
+    xi = (int)x & 255;
+    yi = (int)y & 255;
+    zi = (int)z & 255;
+
+    xf = x - (int)x;
+    yf = y - (int)y;
+    zf = z - (int)z;
+
+    // We also fade the location to smooth the result.
+    u = fade(xf);
+    v = fade(yf);
+    w = fade(zf);
+
+    aaa = p[p[p[    xi         ] +     yi         ] +     zi         ];
+    aba = p[p[p[    xi         ] + inc(yi, period)] +     zi         ];
+    aab = p[p[p[    xi         ] +     yi         ] + inc(zi, period)];
+    abb = p[p[p[    xi         ] + inc(yi, period)] + inc(zi, period)];
+    baa = p[p[p[inc(xi, period)] +     yi         ] +     zi         ];
+    bba = p[p[p[inc(xi, period)] + inc(yi, period)] +     zi         ];
+    bab = p[p[p[inc(xi, period)] +     yi         ] + inc(zi, period)];
+    bbb = p[p[p[inc(xi, period)] + inc(yi, period)] + inc(zi, period)];
+
+    // The gradient function calculates the dot product between a pseudorandom
+    // gradient vector and the vector from the input coordinate to the 8
+    // surrounding points in its unit cube.
+    // This is all then lerped together as a sort of weighted average based on the faded (u,v,w)
+    // values we made earlier.
+    x1 = lerp(grad(aaa, xf  , yf  , zf),
+              grad(baa, xf-1, yf  , zf),
+              u);
+    x2 = lerp(grad(aba, xf  , yf-1, zf),
+              grad(bba, xf-1, yf-1, zf),
+              u);
+    y1 = lerp(x1, x2, v);
+
+    x1 = lerp(grad(aab, xf  , yf  , zf-1),
+              grad(bab, xf-1, yf  , zf-1),
+              u);
+    x2 = lerp(grad(abb, xf  , yf-1, zf-1),
+              grad(bbb, xf-1, yf-1, zf-1),
+                    u);
+    y2 = lerp(x1, x2, v);
+
+    // For convenience we bound it to 0 - 1 (theoretical min/max before is -1 - 1)
+    return (lerp(y1, y2, w) + 1) / 2;
+}
+
+double ff_perlin_get(FFPerlin *perlin, double x, double y, double z)
+{
+    double total = 0;
+    double frequency = 1;
+    double amplitude = 1;
+    double max_value = 0;                   // Used for normalizing result to 0.0 - 1.0
+
+    for (int i = 0; i < perlin->octaves; i++) {
+        total += perlin_get(perlin, x * frequency, y * frequency, z * frequency) * amplitude;
+        max_value += amplitude;
+        amplitude *= perlin->persistence;
+        frequency *= 2;
+    }
+
+    return total / max_value;
+}
+
diff --git a/libavfilter/perlin.h b/libavfilter/perlin.h
new file mode 100644
index 0000000000..200c494be5
--- /dev/null
+++ b/libavfilter/perlin.h
@@ -0,0 +1,101 @@
+/*
+ * Perlin noise generator
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+/**
+ * @file
+ * Perlin Noise generator
+ */
+
+#ifndef AVFILTER_PERLIN_H
+#define AVFILTER_PERLIN_H
+
+#include <stdint.h>
+
+enum FFPerlinRandomMode {
+    FF_PERLIN_RANDOM_MODE_RANDOM,
+    FF_PERLIN_RANDOM_MODE_KEN,
+    FF_PERLIN_RANDOM_MODE_SEED,
+    FF_PERLIN_RANDOM_MODE_NB
+};
+
+/**
+ * Perlin generator context. This needs to be initialized with the
+ * parameters used to generate the Perlin noise.
+ */
+typedef struct FFPerlin {
+    /**
+     * spatial repeat period, if negative it is ignored
+     */
+    double period;
+
+    /**
+     * total number of components making up the noise, each one with
+     * doubled frequency
+     */
+    int octaves;
+
+    /**
+     * ratio used to compute the amplitude of the next octave
+     * component with respect to the previous component
+     */
+    double persistence;
+
+    /**
+     * permutations array used to compute the Perlin noise hash
+     */
+    uint8_t permutations[512];
+
+    /**
+     * define how to compute the permutations array
+     */
+    enum FFPerlinRandomMode random_mode;
+
+    /**
+     * when random_mode is set FF_PERLIN_RANDOM_MODE_RANDOM, set random
+     * seed used to compute the permutations array
+     */
+    unsigned int random_seed;
+} FFPerlin;
+
+/**
+ * Initialize the Perlin noise generator with parameters.
+ *
+ * @param perlin Perlin noise generator context
+ * @param period spatial repeat period, if negative it is ignored
+ * @param octaves total number of components making up the noise, each one with doubled frequency
+ * @param persistence define ratio used to compute the amplitude of the next octave
+ *                    component with respect to the previous component
+ * @param random_mode define how to compute the permutations array
+ * @param random_seed when random_mode is set to FF_PERLIN_RANDOM_MODE_RANDOM, set random
+ *                    seed used to compute the permutations array
+ * @return a negative AVERROR code in case of error, a non negative value otherwise
+ */
+int ff_perlin_init(FFPerlin *perlin, double period, int octaves, double persistence,
+                   enum FFPerlinRandomMode random_mode, unsigned int random_seed);
+
+/**
+ * Compute Perlin noise given the x, y, z coordinates.
+ *
+ * @param perlin Perlin noise generator context
+ * @return normalized value for the perlin noise, in the range [0, 1]
+ */
+double ff_perlin_get(FFPerlin *perlin, double x, double y, double z);
+
+#endif  /* AVFILTER_PERLIN_H */
diff --git a/libavfilter/vsrc_perlin.c b/libavfilter/vsrc_perlin.c
new file mode 100644
index 0000000000..fb2eb4c9bb
--- /dev/null
+++ b/libavfilter/vsrc_perlin.c
@@ -0,0 +1,169 @@
+/*
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+/**
+ * @file
+ * Perlin noise generator
+ */
+
+#include <float.h>
+
+#include "perlin.h"
+#include "libavutil/lfg.h"
+#include "libavutil/opt.h"
+#include "avfilter.h"
+#include "internal.h"
+#include "formats.h"
+#include "video.h"
+
+typedef struct PerlinContext {
+    const AVClass *class;
+
+    int w, h;
+    AVRational frame_rate;
+
+    FFPerlin perlin;
+    int octaves;
+    double persistence;
+    unsigned int random_seed;
+    enum FFPerlinRandomMode random_mode;
+
+    double xscale, yscale, tscale;
+    uint64_t pts;
+} PerlinContext;
+
+#define OFFSET(x) offsetof(PerlinContext, x)
+#define FLAGS AV_OPT_FLAG_VIDEO_PARAM|AV_OPT_FLAG_FILTERING_PARAM
+
+static const AVOption perlin_options[] = {
+    { "size",     "set video size", OFFSET(w),          AV_OPT_TYPE_IMAGE_SIZE, {.str="320x240"}, 0, 0, FLAGS },
+    { "s",        "set video size", OFFSET(w),          AV_OPT_TYPE_IMAGE_SIZE, {.str="320x240"}, 0, 0, FLAGS },
+    { "rate",     "set video rate", OFFSET(frame_rate), AV_OPT_TYPE_VIDEO_RATE, {.str="25"}, 0, INT_MAX, FLAGS },
+    { "r",        "set video rate", OFFSET(frame_rate), AV_OPT_TYPE_VIDEO_RATE, {.str="25"}, 0, INT_MAX, FLAGS },
+    { "octaves", "set the number of components to use to generate the noise", OFFSET(octaves), AV_OPT_TYPE_INT, {.i64=1}, 1, INT_MAX, FLAGS },
+    { "persistence", "set the octaves persistence", OFFSET(persistence), AV_OPT_TYPE_DOUBLE, {.dbl=1}, 0.0, DBL_MAX, FLAGS },
+
+    { "xscale", "set x-scale factor", OFFSET(xscale), AV_OPT_TYPE_DOUBLE, {.dbl=1}, 0.0, DBL_MAX, FLAGS },
+    { "yscale", "set y-scale factor", OFFSET(yscale), AV_OPT_TYPE_DOUBLE, {.dbl=1}, 0.0, DBL_MAX, FLAGS },
+    { "tscale", "set t-scale factor", OFFSET(tscale), AV_OPT_TYPE_DOUBLE, {.dbl=1}, 0.0, DBL_MAX, FLAGS },
+
+    { "random_mode", "set random mode used to compute initial pattern", OFFSET(random_mode), AV_OPT_TYPE_INT, {.i64=FF_PERLIN_RANDOM_MODE_RANDOM}, 0, FF_PERLIN_RANDOM_MODE_NB-1, FLAGS, .unit = "random_mode" },
+    { "random", "compute and use random seed", 0, AV_OPT_TYPE_CONST, {.i64=FF_PERLIN_RANDOM_MODE_RANDOM},   0, 0, FLAGS, .unit = "random_mode" },
+    { "ken", "use the predefined initial pattern defined by Ken Perlin in the original article", 0, AV_OPT_TYPE_CONST, {.i64=FF_PERLIN_RANDOM_MODE_KEN}, 0, 0, FLAGS, .unit = "random_mode" },
+    { "seed", "use the value specified by random_seed", 0, AV_OPT_TYPE_CONST, {.i64=FF_PERLIN_RANDOM_MODE_SEED}, 0, 0, FLAGS, .unit="random_mode" },
+
+    { "random_seed", "set the seed for filling the initial pattern", OFFSET(random_seed), AV_OPT_TYPE_UINT, {.i64=0}, 0, UINT_MAX, FLAGS },
+    { "seed",        "set the seed for filling the initial pattern", OFFSET(random_seed), AV_OPT_TYPE_UINT, {.i64=0}, 0, UINT_MAX, FLAGS },
+    { NULL }
+};
+
+AVFILTER_DEFINE_CLASS(perlin);
+
+static av_cold int init(AVFilterContext *ctx)
+{
+    PerlinContext *perlin = ctx->priv;
+    int ret;
+
+    if (ret = ff_perlin_init(&perlin->perlin, -1, perlin->octaves, perlin->persistence,
+                             perlin->random_mode, perlin->random_seed)) {
+        return ret;
+    }
+
+    av_log(ctx, AV_LOG_VERBOSE,
+           "s:%dx%d r:%d/%d octaves:%d persistence:%f xscale:%f yscale:%f tscale:%f\n",
+           perlin->w, perlin->h, perlin->frame_rate.num, perlin->frame_rate.den,
+           perlin->octaves, perlin->persistence,
+           perlin->xscale, perlin->yscale, perlin->tscale);
+    return 0;
+}
+
+static int config_props(AVFilterLink *outlink)
+{
+    PerlinContext *perlin = outlink->src->priv;
+
+    outlink->w = perlin->w;
+    outlink->h = perlin->h;
+    outlink->time_base = av_inv_q(perlin->frame_rate);
+    outlink->frame_rate = perlin->frame_rate;
+
+    return 0;
+}
+
+static int request_frame(AVFilterLink *outlink)
+{
+    AVFilterContext *ctx = outlink->src;
+    PerlinContext *perlin = ctx->priv;
+    AVFrame *picref = ff_get_video_buffer(outlink, perlin->w, perlin->h);
+    int i, j;
+    uint8_t *data0, *data;
+    double x, y, t;
+
+    if (!picref)
+        return AVERROR(ENOMEM);
+
+    picref->sample_aspect_ratio = (AVRational) {1, 1};
+    picref->pts = perlin->pts++;
+    picref->duration = 1;
+
+    t = perlin->tscale * (perlin->pts * av_q2d(outlink->time_base));
+    data0 = picref->data[0];
+
+    for (i = 0; i < perlin->h; i++) {
+        y = perlin->yscale * (double)i / perlin->h;
+
+        data = data0;
+
+        for (j = 0; j < perlin->w; j++) {
+            double res;
+            x = perlin->xscale * (double)j / perlin->w;
+            res = ff_perlin_get(&perlin->perlin, x, y, t);
+            av_log(ctx, AV_LOG_DEBUG, "x:%f y:%f t:%f => %f\n", x, y, t, res);
+            *data++ = res * 255;
+        }
+        data0 += picref->linesize[0];
+    }
+
+    return ff_filter_frame(outlink, picref);
+}
+
+static int query_formats(AVFilterContext *ctx)
+{
+    enum AVPixelFormat pix_fmts[] = { AV_PIX_FMT_GRAY8, AV_PIX_FMT_NONE };
+
+    return ff_set_common_formats_from_list(ctx, pix_fmts);
+}
+
+static const AVFilterPad perlin_outputs[] = {
+    {
+        .name          = "default",
+        .type          = AVMEDIA_TYPE_VIDEO,
+        .request_frame = request_frame,
+        .config_props  = config_props,
+    },
+};
+
+const AVFilter ff_vsrc_perlin = {
+    .name          = "perlin",
+    .description   = NULL_IF_CONFIG_SMALL("Generate Perlin noise"),
+    .priv_size     = sizeof(PerlinContext),
+    .priv_class    = &perlin_class,
+    .init          = init,
+    .inputs        = NULL,
+    FILTER_OUTPUTS(perlin_outputs),
+    FILTER_QUERY_FUNC(query_formats),
+};