1

I have some code and i don't know what algorithm it is using to generate the curve using control points (similar to how Bezier works as an example).

float Blend(float a, float b, float c, float d, float percent)
{
    // this computes one component
    // for points p_0, p_1, p_2, p_3 then the variables a,b,c,d
    // correspond to the x/y/z components for those points

    const float kThird     = 1.0f / 3.0f;
    const float kTwoThirds = 2.0f / 3.0f;

    float dc = d - c;
    float cb = c - b;
    float ba = b - a;

    float e = dc - cb;
    float f = cb - ba;

    float g;

    // e - f
    // = ((d - c) - (c - b)) - ((c - b) - (b - a))
    // = -a + 3b - 3c + d

    g = e - f;
    g = g * (percent - kTwoThirds);

    g = g + f;
    g = g * (percent - kThird) / kTwoThirds;

    g = g + ba;
    g = g * percent / kThird;

    g = g + a;

    return g; // computes one component at a time

}

Code is in C++, should be easy enough to read, if not let me know.

That's the code, can't really figure out which algorithm it is.

https://i.stack.imgur.com/dcoKJ.png

The above picture is the curve generated using control points:

  • (0, 0)
  • (0, 1)
  • (1, 1)
  • (1, 0)

I would like to know the name of this curve algorithm if anyone can identify it.

Jyrki Lahtonen
  • 133,153
razr32
  • 113
  • Welcome to Math.SE! Since this is a mathematics forum, not everyone here can read code. It would greatly improve the readability if you would include a pseudo-code version of this C++ code. Moreover, you have not really asked a question: you don't know which algorithm this is, but what do you want to know from us? How it works, what the name is? – Hrodelbert Aug 25 '15 at 08:45
  • Yes, the name of the algorithm is what i want so that i can better understand how it works. – razr32 Aug 25 '15 at 08:46
  • it's the degree 3 polynomial interpolation sending (0,1/3,2/3,1) to (a,b,c,d) – mercio Aug 25 '15 at 09:45

1 Answers1

1

It looks like it's doing Newton interpolation over the points $(0, a)$, $(\frac{1}{3}, b)$, $(\frac{2}{3}, c)$ and $(1, d)$ and evaluating at $p$ if I'm not mistaken, where $p$ is percent.

wsc
  • 207
  • A quick look at Newton interpolation it looks something like this: b_0 + b_1(x_1 - x_0) + b_2(x_2 - x_1)(x_1 - x_0) but with my blend function they aren't added together they are multiplied except for the last point like so: a + (p / 3)(ba + ((p - kThird) / kTwoThirds) * (f + ( ... ) )) it's more nested in that everything is going to be multiplied by p / 3 so that when p = 0 the output will be a which is the start of the curve. – razr32 Aug 25 '15 at 10:37
  • If you expand out the expression (it's easier to read from bottom to top), you'l find that the forms match, just that the evaluation of divisions is deferred until later and the polynomial is evaluated akin to Horner's method where say a common factor of $x-x_1$ is brought to the front to reduce the number of multiplications required. – wsc Aug 25 '15 at 10:48