Is there a (family of) monotonically non-decreasing noise function(s)?

Question

I'd like a function to animate an object moving from point A to point B over time, such that it reaches B at some fixed time, but its position at any time is randomly perturbed in a continuous fashion, but never goes backwards. The objects move along straight lines, so I only need one dimension.

Mathematically, that means I'm looking for some continuous f(x), x ∈ [0,1], such that:

• f(0) = 0
• f(1) = 1
• x < y → f(x) ≤ f(y)
• At "most" points f(x + d) - f(x) bears no obvious relation to d. (The function is not uniformly increasing or otherwise predictable; I think that's also equivalent to saying no degree of derivative is a constant.)

Ideally, I would actually like some way to have a family of these functions, providing some seed state. I'd need at least 4 bits of seed (16 possible functions), for my current use, but since that's not much feel free to provide even more.

To avoid various issues with accumulation errors, I'd prefer the function not require any kind of internal state. That is, I want it to be a real function, not a programming "function".

Answer 1

For this post, y = f(t) where t is the parameter you vary (time/progress) and y is distance to target. So I will speak in terms of points on 2D plots where the horizontal axis is time/progress and the vertical is distance.

I think you can make a cubic Bezier curve with first point at (0, 1) and fourth (last) point at (1, 0). The two middle points can be randomly placed (x = rand, y = rand) within this 1-by-1 rectangle. I am unable to verify this analytically, but just from playing around with an applet (yeah, go ahead and laugh) it seems that the Bezier curve will never decrease with such a constraint.

This will be your elementary function b(p1, p2) which provides a non-decreasing path from point p1 to point p2.

Now you can generate a b(p(1) = (0, 1), p(n) = (1, 0)) and pick a number of p(i)'s along this curve such that 1

Essentially, you are generating one "general" path, and then breaking it up into segments and regenerating each segment.

Since you want a mathematical function: Suppose the above procedure is packaged into one function y = f(t, s) which gives you the distance at t for the function of seed s. You will need:

• 4 random numbers for placing the 2 middle points of the main Bezier spline (from (0, 1) to (1, 0))
• n-1 numbers for the bounds of each segment if you have n segments (the first segment always starts at (0, 1) ie t=0 and the last ends at (1,0) ie t=1)
• 1 number if you want to randomize the number of segments
• 4 more numbers for placing the middle points of the spline of the segment your t lands at

So each seed must supply one of the following:

• 7+n real numbers between 0 and 1 (if you want to control the number of segments)
• 7 real numbers and one integer greater than 1 (for a random number of segments)

I imagine you can accomplish either of these by simply supplying an array of numbers as the seed s. Alternatively, you could do something like supply one number s as seed, and then call the built-in random number generator with rand(s), rand(s+1), rand(s+2) and so on (or initialize with s and then keep calling rand.NextNumber).

Note that even though the whole function f(t, s) is made up of many segments, you are only evaluating one segment for each t. You will need to repeatedly calculate the boundaries of segments with this method, because you will have to sort them to make sure no two segments overlap. You can probably optimize and get rid of this extra work and only find the endpoints of one segment for each call, but it is not obvious to me right now.

Also, Bezier curves are not necessary, any suitably behaving spline will do.

I created a sample Matlab implementation.

The Bezier function (vectorized):

function p = bezier(t, points)
% p = bezier(t, points) takes 4 2-dimensional points defined by 2-by-4 matrix
% points and gives the value of the Bezier curve between these points at t.
% 
% t can be a number or 1-by-n vector. p will be an n-by-2 matrix.
    coeffs = [
        (1-t').^3, ...
        3*(1-t').^2.*t', ...
        3*(1-t').*t'.^2, ...
        t'.^3
    ];

    p = coeffs * points;
end

The compound Bezier function described above (deliberately left unvectorized to make it clear how much evaluation is needed for each call):

function p = bezier_compound(t, ends, s)
% p = bezier(t, points) takes 2 2-dimensional endpoints defined by a 2-by-2
% matrix ends and gives the value of a "compound" Bezier curve between
% these points at t.
% 
% t can be a number or 1-by-n vector. s must be a 1-by-7+m vector of random
% numbers from 0 to 1. p will be an n-by-2 matrix. 
    %% Generate a list of segment boundaries
    seg_bounds = [0, sort(s(9:end)), 1];

    %% Find which segment t falls on
    seg = find(seg_bounds(1:end-1)<=t, 1, 'last');

    %% Find the points that segment boundaries evaluate to
    points(1, :) = ends(1, :);
    points(2, :) = [s(1), s(2)];
    points(3, :) = [s(3), s(4)];
    points(4, :) = ends(2, :);

    p1 = bezier(seg_bounds(seg), points);
    p4 = bezier(seg_bounds(seg+1), points);

    %% Random middle points
    p2 = [s(5), s(6)] .* (p4-p1) + p1;
    p3 = [s(7), s(8)] .* (p4-p1) + p1;

    %% Gather together these points
    p_seg = [p1; p2; p3; p4];

    %% Find what part of this segment t falls on
    t_seg = (t-seg_bounds(seg))/(seg_bounds(seg+1)-seg_bounds(seg));

    %% Evaluate
    p = bezier(t_seg, p_seg);    
end

The script which plots the function for a random seed (note that this is the only place where a random function is called, the random variables to all other code are propagated from this one random array):

clear
clc

% How many samples of the function to plot (higher = higher resolution)
points = 1000;

ends = [
    0, 0;
    1, 1;
    ];

% a row vector of 12 random points
r = rand(1, 12);

p = zeros(points, 2);

for i=0:points-1
    t = i/points;
    p(i+1, :) = bezier_compound(t, ends, r);
end

% We take a 1-p to invert along y-axis here because it was easier to
% implement a function for slowly moving away from a point towards another.
scatter(p(:, 1), 1-p(:, 2), '.');
xlabel('Time');
ylabel('Distance to target');

Here's a sample output:

It seems to meet most of your criteria. However:

• There are "corners". This may be amenable by using Bezier curves more appropriately.
• It "obviously" looks like splines, although you can't really guess what it will do after a non-trivial period of time unless you know the seed.
• It very rarely deviates too much towards the corner (can be fixed by playing with the distribution of the seed generator).
• The cubic Bezier function cannot reach an area near the corner given these constraints.

Answer 2

I guess that instead of blending a bunch of transformed cosines (like the dot products in perlin noise give you), you could blend several monotonic functions that start at f(0)=0, like f(x) = x, or 2x, or x^2, etc. In fact since your domain is limited to 0=>1 you could also blend in trig functions that fit the bill within that domain like cos(90*x+270). To normalize your methods to end at 1, you can simply divide the weighted sum of these monotonic methods starting at f(0)=0 by f(1). Something like this should be fairly easy to invert as well (which I gather you want from the bit about stateless real functions versus programming functions).

Hope this helps.

Answer 3

One can analyze this crude picture You can end up with a function that performs your animation on the fly, by making use of an uniform rand function. I know this isn't the exact mathematical formula, but there's actually no mathematical formula for a random function, and even if there were one, you'd be coding a lot to achieve this. Considering you didn't specify any smoothness conditions, the speed profile is $C^0$ continuous (but since you're not dealing with robots, no need to worry about discontinuous acceleration profiles).

Answer 4

The usual way of generating an increasing sequence of N random numbers from [0,1] is to generate N random numbers in any range, then divide them all by their total sum, then sum them one-at-a-time to get the sequence.

Generate the sequence 2, 2, 5, 8, 6.
Their sum is 23, so our numbers to sum are 2/23, 2/23, 5/23, 8/23, and 6/23.
Our final sequence is 2/23, 4/23, 9/23, 17/23, 23/23

This can be extended to 2D by generating these values for both X and Y. You can increase N to get any granularity you want.

---

In @teodron's similar answer, you cited efficiency concerns with large time-scales. Without knowing the actual problem you're facing, I can't tell if that concern is valid; but another option would be to generate for small N, and simply smooth the result. Depending on the application, this may actually give better results.

N=100, no smoothing

N=15, with smoothing

Answer 5

I suggest this implementation inspired by the summation of octaves found in fractal noise, with a bit of cheap ass shuffling here and there. I believe it is reasonably fast and can be tuned by asking for fewer octaves than stored in the parameters with a loss of precision of about 1/2^octave.

You could see it as a piecewise implementation that only requires O(log(pieces)) time. The parameter array is used both for the divide-and-conquer pivot position, and for the distance traveled when reaching the pivot.

template<int N> struct Trajectory
{
    Trajectory(int seed = 0)
    {
        /* The behaviour can be tuned by changing 0.2 and 0.6 below. */
        if (seed)
            srand(seed);
        for (int i = 0; i < N; i++)
            m_params[i] = 0.2 + 0.6 * (double)(rand() % 4096) / 4096;
    }

    double Get(double t, int depth = N)
    {
        double min = 0.0, max = 1.0;
        for (int i = 0, dir = 0; i < N && i < depth; i++)
        {
            int j = (dir + 1 + i) % N;
            double mid = min + (max - min) * m_params[j];
            if (t < m_params[i])
            {
                dir += 1;
                t = t / m_params[i];
                max = mid;
            }
            else
            {
                dir ^= i;
                t = (t - m_params[i]) / (1.0 - m_params[i]);
                min = mid;
            }
        }
        t = (3.0 - 2.0 * t) * t * t; // Optional smoothing
        return min + (max - min) * t;
    }

    double m_params[N];
};

It could be made faster by pre-computing the floating point divisions, at the cost of storing three times as much information.

This is a quick example:

The example was obtained with the following code:

for (int run = 0; run < 5; run++)
{
    /* Create a new shuffled trajectory */
    Trajectory<12> traj;

    /* Print dots */
    for (double t = 0; t <= 1.0; t += 0.0001)
        printf("%g %g\n", t, traj.Get(t));
}

Answer 6

Thinking out loud, and admitting calculus is not my strong point... is this perhaps not possible? To avoid any obvious pattern, the average of the noise function over any change in x must be close to zero, and to guarantee monotonicity the amplitude of noise over that change in x must be smaller than the change in x, as any larger amplitude could result in a lower value at x' relative to x. But that would mean that as you reduce dx towards 0, such a function must also reduce dA (where A is amplitude) towards zero, meaning you get no contribution from any compliant noise function.

I can imagine it being possible to formulate a function that gradually decreases the noise contribution as x approaches 1, but that will give you a curved function that decelerates as x approaches 1, which is not what I think you want.