PDA

View Full Version : Cubic Interpolation In Fragment Shader



toneburst
06-05-2010, 02:25 AM
I guess this is more of a conceptual problem that anything else. I'm just struggling with some ideas about interpolation methods. What I'm attempting to do is make a fragment shader to create the transfer function mentioned in this post
http://graphicsrunner.blogspot.com/2009/01/volume-rendering-102-transfer-functions.html

It's basically a cubic interpolation curve between 7 values for alpha spaced across the x-axis of a small 1D texture.

Looking at this page on interpolation methods
http://local.wasp.uwa.edu.au/~pbourke/miscellaneous/interpolation/
my initial thought was that I needed a simple 1D version of the algorithm.


double CubicInterpolate(
double y0,double y1,
double y2,double y3,
double mu)
{
double a0,a1,a2,a3,mu2;

mu2 = mu*mu;
a0 = y3 - y2 - y0 + y1;
a1 = y0 - y1 - a0;
a2 = y2 - y0;
a3 = y1;

return(a0*mu*mu2+a1*mu2+a2*mu+a3);
}

This I can do fairly easily in a shader, with mu being the x value across the texture, scaled to the 0>1 range between each point.

However, it turns out that only works if the points are equally-spaced along the x, and I need to be able to slide them along the x-axis, so my next thought was that I could try a 2D version, which apparently can be done by simply applying the same algorithm to the two axes independently (in my case, x, and alpha value). I can work out how to apply the cubic interpolation method independently to the x and y values of a set of 2D points (where a point can be placed in an arbitrary position in 2D space, according to a given value of mu), but what I can't work out is how to apply the same thing in a fragment shader program. I'm guessing the equation has to be rearranged in some way, but I've no real idea where to start in doing this.

Any tips, anyone? I'm sure this is really simple stuff to someone with better maths skills than me...

Cheers,

a|x
http://www.machinesdontcare.wordpress.com

I hope I've explained this in a way that makes some sense.

sqrt[-1]
06-06-2010, 04:53 PM
This is not what you are looking for, I just thought I would point out that:
return(a0*mu*mu2+a1*mu2+a2*mu+a3);

Will probably be faster if written as:
return (((a0*mu)+a1)*mu+a2)*mu+a3);

Should generate to just 3 mad instructions.

toneburst
06-07-2010, 03:32 AM
Hey, thank you sqrt[-1], that's handy, cheers!

I'm thinking now that a strictly smooth curve probably isn't super-important for my particular application (making a transfer-function lookup-table for 3D direct volume rendering).

That said, I'd still really like to work out how to do it! The problem as I understand it, is, so get a truly smooth curve between unequally-spaced points, and avoid the issues seen in the screenshots below

http://mcserver.gold.ac.uk/temp/cubicspline-2-3.png

http://mcserver.gold.ac.uk/temp/cubicspline-2-4.png

you'd need to interpolate on both axes, but then the points across each segment would be unequally-spaced also. But, in a shader, the points are always equally-spaced because texel/pixels are always in a strict grid.

Could I somehow map the relationship between x and mu across each segment in a prepass, and then use that value as mu in the second pass to lookup the value on the other axis, maybe?

Does this make any sense at all?

a|x

sqrt[-1]
06-07-2010, 09:46 PM
I don't fully uderstand what you are trying to do, but to get smooth interpolation between a series of points it sounds like you want to use a spline.

Specifically you probably want second order continuity for real smooth blending - but you may have to pre-process the data? (as the weight values might to too complex for a shader? perhaps)

Look for Hermite spline, cardinal Spline, TCB spline etc as these are spline types which intersect the control points (as opposed to B-splines etc)

toneburst
06-09-2010, 02:50 AM
Hmm... I suspected I hadn't explained myself very well. I am actually using cubic spline interpolation. I'm calculating the coefficients externally to the shader itself, then passing them in as a series of vec2 and vec4 uniforms.

What I'm trying to do is create a smooth gradation of values across the width of a texture. The screenshots above show a graph of the curve, on top of the lookup-table texture itself, where the values of the curve are applied to the alpha channel of the texture.

With a 1D cubic spline interpolation, as outlined on Paul Bourke's site, this works fine if the points are spaced equally along the x-axis, but that's not the case if the points aren't equally-spaced. I'd like to be able to slide the points along the X (without actually sliding them past each other), and the curve to remain smooth, without the corners you can see in the screenshots above, but I'm not sure how to approach it in a shader.

I'm happy to render each segment separately, to cut down on the number of uniforms that need to be passed in to the shader, and remove the necessity to determine the current segment in the shader itself, incidentally, if that helps.

Cheers,

a|x

lobbel
06-16-2010, 05:52 AM
Hello,
you can use the catmull rom spline. The Spline goes through the basic points and you dont need to solve any equations. You can
also use it for 1D, 2D or 3D case. You only need to interpolate
the axis. But for interpolation you need 4 points and the interpolation happens on point 2 and 3. The first point and the last point control the shape of the spline.

Here you can download a catmull rom spline implementation.
http://rapidshare.com/files/399644361/CRSpline.rar.html

The link you posted is about transfer function design for volume rendering. These functions are created on CPU side and send as
1D texture to the shader. There the isovalue of the CT dataset is used as index/lookup for the transfer texture.
Actually it makes no sense to use a curved transfer function
for a 8bit 1D transfer texture.

For higher order texture filtering i recommend the chapter 9.2
at page 223 of the book "Real-Time Volume Graphics" by Engel, Hardwiger etc. You can read these pages on google books. There they introduce some convolution filters as well as the
catmull rom.

regards,
lobbel