Sign in to follow this  
smurfkiller

color gradient from beizer curve

Recommended Posts

I want to make a color gradient from a beizer curve. The problem is that a beizer curve is parametric where for example x = f(t), y = f(t). I need to compute a 'y' (clor value) based on 'x'. But because the curve is parametric do not have any other option than to compute the 'y' value by sampling the 'x' axis. Is there no other solution? This is verry similar to 3dsMax material editor where you can control color gradients and other functions by beizer curves.

Share this post


Link to post
Share on other sites
I'm not sure a bezier curve is precisely the type of curve you need. But perhaps something very similar. Consider a polynomial function f(x) = a·x3 + b·x2 + c·x + d. You can evaluate this function anywhere between 0 and 1, and get a single value back (y). Two problems that we must solve, though, are that we have four unknowns (a, b, c, and d), and depending on what those values are, the result could be just about anything. But if we choose the unknowns carefully, we can restrict the range of the function when x is between 0 and 1. How do we choose values for a, b, c and d? There are a variety of ways, but here are two very useful ones:

We need four knowns of some form in order to determine the four unknowns. First, let's assume that f(0) = g0 and f(1) = g1. Basically, we are saying that when x is 0, we know that we'll get g0, the value that we chose ahead of time that will be at the very beginning of the color gradient. And the same for g1, except that it is the value of the color gradient at the very end. So this gives us two knowns.

The easy way to calculate the second two knowns would be to do essentially the same thing as above, but for values when x is 1/3 and 2/3. We could say then that f(1/3) = g1/3 and f(2/3) = g2/3. So now that we have four knowns, how do we get the four unknowns a, b, c, and d?

First, using the g constants that we have chosen, rewrite the polynomial above, with the x value filled in:

f(0) = g0 = a·(0)3 + b·(0)2 + c·(0) + d
f(1/3) = g1/3 = a·(1/3)3 + b·(1/3)2 + c·(1/3) + d
f(2/3) = g2/3 = a·(2/3)3 + b·(2/3)2 + c·(2/3) + d
f(1) = g1 = a·(1)3 + b·(1)2 + c·(1) + d

These simplify into

g0 = d
g1/3 = a·(1/27) + b·(1/9) + c·(1/3) + d
g2/3 = a·(8/27) + b·(4/9) + c·(2/3) + d
g1 = a + b + c + d

When you solve that system of equations (you can do it the basic algebraic way, or use linear algebra, whichever you're more comfortable with), you get

a = 9/2·g1 - 27/2·g2/3 + 27/2·g1/3 - 9/2·g0
b = -9/2·g1 + 18·g2/3 - 45/2·g1/3 + 9·g0
c = g1 - 9/2·g2/3 + 0·g1/3 - 11/2·g0
d = g0

So whatever you choose for g0, g1/3, g2/3, and g1, you can use those four values to determine a, b, c, and d, plug all that into f(x) = a·x3 + b·x2 + c·x + d, and then figure out what f(x) equals. The resulting gradient will be a curve that starts at g0, goes through both g1/3 and g2/3 when x is 1/3 and 2/3 respectively, and ends at g1.

The other way to determine the other two knowns is a little more creative, and requires a bit of calculus knowledge. It is more similar to bezier curves, however. Instead of saying that the curve equals g1/3 and g2/3 when x is 1/3 and 2/3 respectively, let's say that the slope of the curves equals s0 and s1 when x is 0 and 1 respectively. This will mean that we know the value and slope of the curve only at x = 0 and 1, but we don't know anything about the curve in between. We still have the first and last equations from above, because they came from our first two knowns:

f(0) = g0 = a·(0)3 + b·(0)2 + c·(0) + d
f(1) = g1 = a·(1)3 + b·(1)2 + c·(1) + d

which as above simplify to:

g0 = d
g1 = a + b + c + d

Our second two equations will come from the derivative of the polynomial, however, because it is the derivative that specifies slope.

f'(0) = s0 = 3·a·(0)2 + 2·b·(0) + c
f'(1) = s1 = 3·a·(1)2 + 2·b·(1) + c

which simplify to:

s0 = c
s1 = 3·a + 2·b + c

Solving these four equations, this time we get:

a = 2·g0 - 2·g1 + s0 + s1
b = -3·g0 + 3·g1 - 2·s0 - s1
c = s0
d = g0

So again, once you have determined g0, g1, s0, and s1, you can figure out a, b, c and d, and thus the overall equation.

So depending on if you merely want to supply four values for the curve to equal when x is 1, 1/3, 2/3, and 1, then you can use the first system. Or if you'd rather supply the values and slopes when x is 0 and 1, then you can use the second system. In both cases, the resulting value will be the color gradient, and if you chose values that make sense for the values and slopes, then the color gradient will always be in a range that makes sense as well.

Share this post


Link to post
Share on other sites
Thanks alot for the reply, the first aproach is verry similar to solving the bezier functions:

x(t) = at3 + bt2 + ct + x0
x1 = x0 + c / 3
x2 = x1 + (c + b) / 3
x3 = x0 + c + b + a

where:

c = 3 (x1 - x0)
b = 3 (x2 - x1) - c
a = x3 - x0 - c - b

I will try the second aproach with the slopes.



Share this post


Link to post
Share on other sites
I found out that this aproach is not exactly what im after. The problem is that the bezier curve is given in parametric space if you look at the example below you see that the gradient for a bezier curve is given as y = f(x):
description of your image
This basicaly means that i need to express y = f(x), where y = f(t) and x = f(t). Maybe someone have an idea how they do that i 3dsmax. I think they are sampling the 'x axis' for some values of parameter 't' but that wont work for my purpose.

Share this post


Link to post
Share on other sites
Quote:
Original post by smurfkiller
Maybe someone have an idea how they do that i 3dsmax. I think they are sampling the 'x axis' for some values of parameter 't' but that wont work for my purpose.
I'm just jumping in here without having read the whole thread, but if you need y(x) I think you should be able to get it as follows.

1. Derive t(x) from x(t) by solving x(t) for t
2. Plug t(x) into y(t) to yield y(t(x)), which gives you the y(x) you're looking for

I think the degree of t(x) will be the same as that of the curve, so you'll need a cubic solver of some sort.

I didn't test this or work through it in detail, so it may or may not be correct.

Share this post


Link to post
Share on other sites
Quote:
Original post by smurfkiller
I think that is very complicated since the solution leads to three roots where two of them can be complex.
Well, yeah, but that's exactly what you get if you solve a 2D cubic curve for one coordinate in terms of another. Isn't that what you want to do? Or maybe I'm missing something...

Share this post


Link to post
Share on other sites
No its not posible, its like trying to express a parametric curve in none parametric form. Unless its something im missing?
For example circle: x = r*cos(t), y = r*sin(t) if you try to express y = f(x) you get a function where there are two values for a given x value, so you have to split it in y = ±f(x). The question is how do i plug in the solution of tree roots into one equation?

Share this post


Link to post
Share on other sites
Quote:
Original post by smurfkiller
No its not posible, its like trying to express a parametric curve in none parametric form. Unless its something im missing?
For example circle: x = r*cos(t), y = r*sin(t) if you try to express y = f(x) you get a function where there are two values for a given x value, so you have to split it in y = ±f(x). The question is how do i plug in the solution of tree roots into one equation?
Well, I'm not absolutely certain that my solution is correct, but I'm fairly certain. I'll try to clarify a bit.

In general, if you solve a cubic curve for y in terms of x or vice versa, you get a cubic equation, the solution of which has either zero, one (possibly tangent), two (one tangent), or three real roots. If you draw some different cubic curves it should become apparent why this is so. This is somewhat similar to your circle example where one x corresponds to (possibly) two values of y.

Your particular example has some constraints such that, theoretically, there should only ever be one real root. Nevertheless, to find the solution I think you'll still need to solve a cubic equation. Maybe there's a way around it, but if so it's not occurring to me.

Share this post


Link to post
Share on other sites
Actually, any cubic equation with real coefficients is guaranteed to have a real root. To visualise this (suppose y = y(x)), observe that as x tends to an infinity, so must y (though not necessarily with the same sign). Hence by the Intermidiate Value Theorem, every such cubic must cross the x-axis. The other roots may or may not be real.

Determining y(s) = y(x^(-1)(s)) seems like a good idea, and it works fine so long as x is invertible, but the Inverse Function Theorem (let's see if I can name any more theorems [rolleyes]) demands that x(s) be strictly increasing/decreasing, or equivalently, has two complex roots.
Since there are no constraints on Bezier splines (unlike B-Splines) restricting the nature of the roots (within the given interval), this method isn't guaranteed to succeed. So in general, it fails.

The reason we can't simply use the real root that we know exists is that we may end up with nasty discontinuities and bifurcations, which will be unstable depending on what method you use to extract the polynomial's roots. This will manifest itself as potential sudden colour changes as you cross a node.

This situation could be avoided if it were possible to determine the root that exists at all times and keep track of it in each section of the spline, but with floating-point error this is unreliable.

Certainly, better method exist to determine the colour of the spline than attempting to eliminate the Bezier parameter. If you tell us what the colour of the spline is supposed to represent, we may be able to suggest a better alternative.

Regards
Admiral

Share this post


Link to post
Share on other sites
The spline can represent any value that is supose to change smoothly over a time interval [0, 1]. Again take a look at this image:
description of your image
Here you see that the gradient below the bezier curve is just representing the value of 'y-axis' based on value of 'x-axis'. In my case i would like to make a function where:

float value = func(float a, float b, float c, float d, float time);

so by suplying the constant vector (a, b, c, d) and a time value (range from 0 to 1) i should get a result wich is based on a bezier or similar spline like in the picture above.

The (not so)simple question: how do they calculate values for that colorgradient at the bottom of the picture based on the bezier spline at the top of the picture?

The sad thing is that im not so god at math. If i could find the guy that programed that for 3dsMax im sure he would be more than glad to help me, the problem is that i don't know where to ask.

Share this post


Link to post
Share on other sites
I think you are overthinking the problem. They create the gradient from the curve by simply evaluating the curve. The gradient is not explicitly a function of x. It is explicitly a function of the parameter t, just like you want.

Share this post


Link to post
Share on other sites
No it's absolutely not. The bezier curve in the image above is evaluated for a parameter t, x = f(t) and y = f(t) but it is plotted for 'x' and 'y'. The gradient is then based on the 'x' and 'y' value. You can never get a curve like that by a cubic polynome. You are ofcaurse right that a bezier function 'can' be used in that way but that is not what im after and that is sertenly not how they use bezier curves in 3dsMax.

Share this post


Link to post
Share on other sites
What is this x and y you keep speaking of? That graph you show is a graph of f(t), where f is a cubic function, and t is the parameter. Are you talking about a bezier in 3D space?

Share this post


Link to post
Share on other sites
I think he's talking about a cubic Bezier curve in 2D. If you look at the example you can see the typical interface of movable control points and associated tangents. The example is in the Cartesian plane; neither axis represents t.

What I gather is that the OP wants to find, for a given x value, a corresponding y value. Presumably there are constraints on the interface such that there is a one-to-one correspondance between x and y within the range of interest.

TheAdmiral is correct that there were a couple of errors in my previous post, but it still seems to me that the solution I proposed initially should work. To reiterate, the idea is to find the value of t corresponding to the given x by solving a cubic (given the apparent constraints of the posted example there should be exactly one real root), and then plug this value into y = f(t) to find the y corresponding to the given x.

Share this post


Link to post
Share on other sites
In your case I'd just evaluate the curve at some points, and then simply construct an approximation of the curve by "drawing" straight lines between those points. Once you've got that, just order the segments by the value of x (or create them pre-ordered) and you've got what you were looking for. :)

If you're worried about the accuracy of this approach you can employ some kind of adaptive subdivision scheme. A shameless plug: Adaptive subdivision of Bezier curves. This might possibly be even more accurate than what you would get by solving the problem analytically (floating point errors near the edges probably wouldn't be very nice).

P.S.
The approach I describe on the link above could probably be further optimized to better suit your restrictions, though. For example, you don't have to continue subdivision if the endpoints are closer than 1 "pixel" along the x-axis, assuming the curve is generally well-behaved...

Share this post


Link to post
Share on other sites
I think I will have to face soon the problem you are presenting here, so I've been thinking about it. The problem in here is typical for parametric curves: the value 't' doesn't move constantly over the curve. Taking as example your image, in the begining of the curve 't' moves faster that at the end ('t' tends to move faster when the control points are more near). Because of that we can not, for example, evaluate the middle point of the curve as f(0.5).

What you want in here is to be able to evaluate the distance of the curve on the X axis, so let's say: what is the value of y for x=0.5?

I read about finding such a solution using iterative methods, so it involves to get and initial solution, and use the result to find a better solution. One of that methods is Newton's method (I think there was an article about it in some of the Game Gems books). But keep in mind that you will stop with some value approximated, and not exact.

Another way I am thinking in is to evaluate the curve at several points, for instance every 0.01 increments of 't'. Then you can use the resulting set of points as a poliline and resample it for getting values at even increments of X (you can get them by linear interpolation). At the end you will end with a table with the values you are trying to get (again, approximated ones, but you can increase accuracy by reducing the increment of 't' when evaluating the curve). I think I will use this way, so I hope it works fine.

Share this post


Link to post
Share on other sites
A numerical solution is not very intresting in my case cause i want to use the calculations in a shader. The main purpose is for a particle system where you should be able to control some particle properties by supluying ponly 4 constant values into the shader as properties.

Share this post


Link to post
Share on other sites
I still think you are overthinking the problem. X & Y space coordinates are not an issue here. The curve is a function of 4 user defined constants, and a single parameter t. If you define the parameterization of the curve so that points on the curve have coordinates (t, f(t)):0<=t<=1, the color value of the gradient (at least for one color channel) at t is simply max(0,min(1,f(t))), assuming you want the color values clipped to be between 0 and 1 inclusive. This is essentially what I used in a sound editor I wrote, whereby the function of the curve was used to scale the rate of playback.

[Edited by - Mastaba on September 9, 2006 4:05:57 PM]

Share this post


Link to post
Share on other sites
The first solution I'd propose (you probably won't like it) would be to to find a more suitable means of defining your curve. If you need explicit evaluation among your coordinates, don't use a parametric system. People use Bezier splines when they want to perform loop-the-loops and the likes. Any such shapes will confuse the hell out of the spectrum you are trying to draw.

But supposing that you're not at liberty to replace the Bezier splines, here's a recursive method that should give you reliable results without that much of a headache:

Create a function to find the y value corresponding to an x that is strictly between the bounds provided. By recursively calling this function, terminating when the bounds are adjacent, you can reasonably quickly evaluate y for every x without too much redundancy:

void FillBetweenBounds(tMin, tMax) {
float xMin = X(tMin);
float xMax = X(tMax);
// Terminate if bounds are adjacent
if (fabsf(xMax - xMin) <= 1.0f) return;

// Calculate and plot the "midpoint"
float tMid = (tMin + tMax) * 0.5f;
float xMid = X(tMid);
float yMid = Y(tMid);
Plot(xMid, yMid, GetColour(yMid));

// Recurse
FillBetweenBounds(tMin, tMid);
FillBetweenBounds(tMid, tMax);
}

void FillEntireGradient() {
FillBetweenBounds(0.0f, 1.0f);

// FillBetweenBounds doesn't plot the extremes
// so we need to do them manually

// Some or all of this block may want to go inside FillBetweenBounds
float xMin = X(0.0f);
float xMax = X(1.0f);
float yMin = Y(0.0f);
float yMax = Y(1.0f);
Plot(xMin, yMin, GetColour(yMin));
Plot(xMax, yMax, GetColour(yMax));
}





Undocumented functions should be obvious, but just for clarity:
X(float t), Y(float t) evaluate x and y from the parameter, t.
GetColour(float y) determines the colour that y evaluates to.
Plot(float x, float y, DWORD colour) plots the point/vertical line in the spectrum accordingly.

There are a couple of things to look out for. First, I haven't tested this code at all. Second, you'll want to make sure that your t-scale isn't too homogeneous (and that the spline isn't too long) or floating point error will pull chunks out of your spectrum. Third, I didn't think too hard about which points get plotted and when, so you may need to tell FillBetweenBounds to plot its min/max/both as well as the midpoint to prevent missing bands under certain circumstances.

Although it looks like a sledgehammer cracking a nut, the running time of this algorithm isn't so big at all. Provided you have a little stack space to play with and you don't have a strict CPU quota to stick to, I can't imagine you'll have any problems.

Regards
Admiral

Share this post


Link to post
Share on other sites
I have actually seen runtime evaluation of Bezier curves to control particle properties in other engines I've worked with, and it's extremely slow, especially if you have more than one property being controlled that way and thousands of particles. I didn't actually look to see how they did the evaluation, but the problem boils down to inverting x(t) to get t(x) and plugging that into y(t) to get y(x), as jyk has said.

This isn't to say that Bezier curves are a bad approach, just that you probably shouldn't be evaluating them at runtime if you have your heart set on them. We were able to achieve massive speed increases by pre-sampling the curves at a configurable granularity, and at runtime performing a simple array lookup to get the value. You could also modify the lookup behavior to linearly interpolate between surrounding values, but that's still pretty fast compared to an iterative numeric method at runtime.

Share this post


Link to post
Share on other sites
Yes i start to relize now that aproach with splines is to complicated for fast evaluation. I think the best way of doing this is to paint gradient textures for each parameter and read that texturedata in the shader. Unfortunately you cannot do that unless you have latest hardware with texturefetch or similar. Im going for my original aproach with lineary interpolated points like mentioned above. I want to thank everyone for the help to clearify the problem for me.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this