Repeating alpha over/under operation multiple times

Question

I have two RGBA colors in linear [0..1] space, src and dst and I want to alpha blender src over/under dst n times. Of course, I could call the respective operation n times using the result from the previous one (which is what I am currently doing), but I want to optimize it into a single operation. I think just calculating the correct alpha on src should be sufficient, but I may be wrong. Here's what I currently use:

public static final Color alphaOver(Color dst, Color src) {
    float src1A = 1 - src.a;
    float outA = src.a + dst.a * src1A;

    if (outA == 0)
        return Color.TRANSPARENT;
    return new Color(
            outA,
            (src.r * src.a + dst.r * dst.a * src1A) / outA,
            (src.g * src.a + dst.g * dst.a * src1A) / outA,
            (src.b * src.a + dst.b * dst.a * src1A) / outA);
}

public static final Color alphaUnder(Color dst, Color src) {
    return alphaOver(src, dst);
}

public static final Color alphaOver(Color dst, Color src, int times) {
    Color ret = dst;
    for (int i = 0; i < times; i++)
        ret = alphaOver(ret, src);
    return ret;
}

public static final Color alphaUnder(Color dst, Color src, int times) {
    Color ret = dst;
    for (int i = 0; i < times; i++)
        ret = alphaUnder(ret, src);
    return ret;
}

How can I optimize the last two functions?

user1118321 · Accepted Answer · 2018-09-08T05:28:58.053

1

So taking source over as an example, the math works out to:

dst = a * src + (1 - a) * dst

Taking Nathan Reed's suggestion of replacing (1 - a) with b, that gives us:

dst = a * src + b * dst

If we perform the next iteration, it becomes:

dst = a * src + ab * src + b^2 * dst

Doing it again, we get:

dst = a * src + ab * src + ab^2 * src + b^3 * dst

And then:

dst = a * src + ab * src + ab^2 * src + ab^3 * src + b^4 * dst

The pattern appears to be:

int exponent;
for (exponent = 0; exponent < numIterations; exponent++)
{
    newDst += a * pow(b, exponent) * src;
}
newDst += pow(b, exponent) * dst;

edited Sep 08 '18 at 05:28

answered Sep 07 '18 at 20:28

user1118321

3,361
9
14

Are you sure to plug the result of the first alpha over into `src` of the next one? As I understand it, I would put it into `dst` instead. This lines up with some quick tests of the final equation with black `src`, white `dst` and an a>0. Overlaying black over white should darken the color but ` + dst` prevents this. – piegames Sep 07 '18 at 20:43
I agree that substituting into `dst` is the correct thing to do here. If you imagine doing `n` separate blends on top of each other, the `src` would be the same for all, and result of each blend would be the following blend's `dst`. I think you should be able to simplify the result to a single blend using alpha of `1 - (1 - a)^n` though. (Try defining a new variable `b = 1 - a`, and repeating the derivation you used for the first part of the answer.) – Nathan Reed Sep 08 '18 at 02:37
Great idea! I've updated it with your suggestion. Let me know how it works. – user1118321 Sep 08 '18 at 05:30
How about `dst := (1 - b)*src + b*dst`, and then rewrite that as `src + b*(dst - src)`. Then it works out similarly to your original derivation. :) – Nathan Reed Sep 08 '18 at 05:48
Ah, I see what you mean. I'll give that a try in the morning. I'm getting sleepy now and would probably screw it up. – user1118321 Sep 08 '18 at 06:18
Whoa, that looks really good. Am I allowed to bracket out `src` in that sum, to avoid multiplicating with `src` n times and reduce it to once at the end? Because if so, this becomes a geometric series which can be optimized even further. – piegames Sep 08 '18 at 08:09
Absolutely! If it works, go for it! – user1118321 Sep 08 '18 at 14:48

Repeating alpha over/under operation multiple times

1 Answers1