Is there a way to interpolate color across the line with only integer calculation ?`

Question

Here is my function that does interpolation

static public PixelData InterpolateColour(Point start, Point end ,float curLength, float totalLength){

    float endPercent = curLength / totalLength;             // Calculates the percent of colour at the ending point of the line to be used in current pixel 
    float startPercent = 1 - (curLength / totalLength);     // Calculates the percent of colour at the starting point of the line to be used in current pixel 

    float startHueInRadians[] = PixelData.PixelDataToHsbInRadians(start.getColour());   // Converting the ending point colour into a hsb colour model 
    float endHueInRadians[] = PixelData.PixelDataToHsbInRadians(end.getColour());       // Converting the starting point colour into a hsb colour model


    startHueInRadians[0] = (startHueInRadians[0] == 0) ?                                            // if the start colour is red then then choosing the value to be zero or 2*pi
                           ((endHueInRadians[0] >= (Math.PI * 4)/3) ?  (float)(Math.PI * 2) : 0)    // if the end colour is red then then choosing the value to be zero or 2*pi
                           : startHueInRadians[0];

    endHueInRadians[0] = (endHueInRadians[0] == 0) ? 
                         ((startHueInRadians[0] >= (Math.PI * 4)/3) ?  (float)(Math.PI * 2) : 0)
                         : endHueInRadians[0];



    float a = start.getColour().getAInInt() * endPercent + end.getColour().getAInInt() * startPercent;  //Interpolating alpha, which is not working :(                   
    float h = endHueInRadians[0] * endPercent + startHueInRadians[0] * startPercent;                    //Interpolating hue.
    float s = endHueInRadians[1] * endPercent + startHueInRadians[1] * startPercent;                    //Interpolating staturation, which is useless currently. :(
    float b = endHueInRadians[2] * endPercent + startHueInRadians[2] * startPercent;                    //Interpolating value, which is useless currently. :(

    float f[] = {h,s,b};

    PixelData p = PixelData.HsbinRadiansToPixelData(f);     // Converting interpolated hsb back to rgb

    p.setAInInt((int)a);    //setting the alpha value 

    return p;               // returing the intepolated value 
}

It is working properly but it is giant bulky code that runs very slowly because it has all kind of Ternary operator, floating point arithmetic and also it runs once per pixel.

I am currently refactoring my code to be small and less hacky.

What are some interpolation algorithm that are used in computer graphics ? because i came up with this code and it is just bad.

Answer 1

Yes, it is possible to use only integer calculations. I will describe how, but bear in mind that the difference in speed between integer arithmetic and floating point arithmetic is not as great as it was historically. If you want your code to run faster, it is best to profile and identify which parts of the code are taking up most time, before considering whether to convert a particular aspect to use integers.

---

A straight line through colour space

Looking at the code, it appears you first convert from RGB to HSB then create a linear gradient, and convert it back to RGB.

A linear gradient is a straight line through the colour space, so you can use an integer based straight line algorithm to generate it without the need for floating point arithmetic. For example, the integer based version of Bresenham's algorithm.

H, S, and B are being treated independently, so you can calculate each one separately. For example, the H component can be calculated by treating the line as a straight line from (x0, H0) to (x1, H1), instead of the usual (x0, y0) to (x1, y1).

If the range of y values along the line is greater than the range of x values along the line then Bresenham's algorithm will step along integer y values instead of x values. The algorithm can still be applied in exactly the same way, just using (y0, H0) to (y1, H1).

You can also combine all 4 calculations into a single loop, keeping track of a parameter each for determining y value, H value, S value and B value.

The only difference from plotting a line on the screen (using x and y) is that not every value of H, S, and B needs to be taken. If the x range is greater than the y range, the algorithm steps through each of the x values checking whether to increment y. If the y range is greater then it instead steps through the values of y checking whether to increment x. However, if the range of H is greater than the range of x, it makes no sense to step through H values, as many of them will correspond to the same x value, wasting calculations. If the range of H is smaller than the range of x then the algorithm can proceed as usual. If the range of H is often going to be larger than the range of x then it is worth considering a different approach. Similarly for S and B.

Fitting the colour space to your line

One way to eliminate this problem is to tailor your colour space to the x (or y if greater) range required for this specific line. Since your input colours and final output colours are in RGB, you are not constrained to a particular range for the HSB colours. You are free to convert from 256 levels of R, G, and B to 1000 levels of H, S, and B (or 1000000, or whatever you choose). If you choose to use a colour space where the range of H values used is the same integer as the range of x values used, then you won't even need to use a line drawing algorithm for the colours. Simply store the required values for converting back to RGB, and each of the H, S, and B values will be x plus a constant.

This will require modifying your conversion function, but this will probably be necessary anyway, as it currently uses radians, which are not going to help with keeping things integer.

More accurate colour spaces

Note that using a colour space like HSB will not give gradients which look as even as if using a more perceptually uniform color space such as Lab. However, since such spaces require calculating roots and you are looking to keep to integer arithmetic as much as possible, I'm assuming you are happy with HSB. If you did want to use something like Lab, you could still potentially keep to integers by using look up tables.

What inputs does this need to work for?

You also mention having to make decisions in the code which also takes up time. I would question how much difference this makes since the decisions are outside the loops and therefore only performed once. If you really want to eliminate them, ask yourself which inputs the code needs to work for.

Currently the code checks the start and end values of the hue and decides whether to change the hue clockwise or anticlockwise. If you eliminate this check the code will still work, but it may not always give the colour direction the user intended. Deciding this automatically also may not give the direction the user intended (since different users have different expectations, and the requirement may change from one use to the next). You could simply take the direction as an additional parameter, which would avoid having to make the decision.

Code review

Meaningful variable names

The use of "hue" in the naming of variables that store all three of hue, saturation and brightness makes the code less intuitive to read, potentially causing the reader to wonder whether saturation and brightness have been overlooked. It also makes the code difficult to reason about, since startHueInRadians[0] is a hue, while startHueInRadians[1] is a saturation, which is not only not a hue, but also presumably not in radians.

In addition to making the code more accessible to others, you may also find it easier to work with it yourself if the naming is consistent, especially if you look back at the code after a few months.

A potential bug

If one end of the colour gradient is at hue zero (red), the code checks whether the other end is greater than or equal to two thirds of the way around the hue circle. This corresponds to blue. If it is less than blue, then the gradient proceeds from zero upwards (anticlockwise), otherwise it proceeds from 2 pi downwards (clockwise). This means that a gradient from red to a colour with hue just above blue will go from red to magenta to blue. A gradient from red to a colour with hue just below blue will go from red to yellow to green to cyan to blue, which may not be what is expected. Intuitively, I would expect the cut off to be half way around the circle rather than two thirds, so that the gradient always includes the fewest colours (taking the shorter, more direct route).

If you did intend to have this asymmetry, note that choosing a similar red with hue just above or just below zero will override this behaviour, forcing the long route or the short route respectively.

If you want the gradient to consistently take the shorter route, then the code will need to check which route to take for all values, not just zero. For example, currently choosing the start hue just above zero and the finish hue just below zero will give start and finish colours that both look red, but the gradient will pass through red, yellow, green, cyan, blue, magenta and back to red, rather than just fading subtly from one hue of red to another.