Pixel manipulation performance

Question

I have created a function that adds "shadow" to the content of a canvas. The algorithm for adding shadow follows these rules:

1. If the either x or y is 0, ignore.
2. If the pixel on the current pixel's top left corner is not completely transparent, set current pixel's alpha value to 0.1.

This algorithm runs from top to bottom, left to right. Here's the relevant part, where rendered is a canvas that already contain rendered content.

    function getIndex(x, y){
        return (y * width + x) * 4;
    }

    function isClear(x, y){
        var index = getIndex(x, y);
        return data[index + 3] === 0;
    }

    function isInShadow(x, y){
        if(x < 1 || y < 1)                          return false;
        if(isClear(x, y) && !isClear(x - 1, y - 1)) return true;

        return false;
    }

    var width = rendered.width, height = rendered.height,
        imgData = renderedCtx.getImageData(0, 0, width, height),
        data = imgData.data;

    for(var x = 0; x < width; x++){
        for(var y = 0; y < height; y++){
            if(isInShadow(x, y)){
                data[getIndex(x, y) + 3] = 256 * 0.1;
            }
        }
    }

    renderedCtx.putImageData(imgData, 0, 0);

As you can see, this function performs per pixel manipulation and is quite slow in performance. What is a good way to improve performance, probably without checking each pixel independently?

Answer 1

Use diagonals. The idea is to have only one pixel check, compared to two you have now:

1. find the first occupied pixel on a diagonal
2. skip to an unoccupied one
3. fill with 0.1 while unoccupied
4. repeat 1-3 until out of bounds

Considering everything should be inlined, the code would be like this:

var x, y, index, index0,
    len = width * height * 4,
    stride = width * 4;
    strideDia = stride + 4; // distance to the sibling pixel towards bottom-right

// walk diagonals from the bottom-left corner to the top-left corner
for (x = 0, y = height, index0 = (y * width + x)*4 + 3; --y >= 0; ) {
    index = index0 -= stride;

    while (index < len && x < width) {
        // find an occupied pixel
        while (index < len && x < width && !data[index])
            index += strideDia, x++;
        // skip to an unoccupied
        while (index < len && x < width && data[index])
            index += strideDia, x++;
        // fill with 0.1 all unoccupied
        while (index < len && x < width && !data[index]) {
            data[index] = 25; // 0.1 * 256
            index += strideDia;
            x++;
        }
    }

    x = 0;
}

// walk diagonals from the top-left corner to the top-right corner
// (0,0) is skipped as it was processed in the previous walk block
for (x = 0, y = 0, index0 = (y * width + x)*4 + 3; ++x < width; ) {
    index = index0 += 4;
    var x0 = x;

    while (index < len && x < width) {
        // find an occupied pixel
        while (index < len && x < width && !data[index])
            index += strideDia, x++;
        // skip to an unoccupied
        while (index < len && x < width && data[index])
            index += strideDia, x++;
        // fill with 0.1 all unoccupied
        while (index < len && x < width && !data[index]) {
            data[index] = 25; // 0.1 * 256
            index += strideDia;
            x++;
        }
    }

    x = x0;
}

Another potentially promising idea would be to use asm.js.

Answer 2

This is my attempt of optimizing the performance of the loop:

var width = rendered.width, height = rendered.height,
    imgData = renderedCtx.getImageData(0, 0, width, height),
    data = new Uint8Array(imgData.data.buffer),
    arrayWidth = width * 4, arrayHeight = height * 4;

for(var y = 0; y < arrayHeight; y+=4){
    for(var x = 0; x < arrayWidth; x+=4){
        if(x > 0 && y > 0 && !data[y * width + x + 3] && data[(y - 4) * width + x - 1]){
            data[y * width + x + 3] = 25;
        }
    }
}

renderedCtx.putImageData(imgData, 0, 0);

I eliminated all function calls since calling a separate function requires more operations, and the loops are also flipped to avoid possible cache misses. The result is that the loop's running time is greatly decreased, making getImageData the most expensive operation in this function.

Answer 3

A simple optimization that most programmers fail to notice:

if (...)  return true  else  return false;

==>

return (...);

Instead of looking at every pixel, only look at each diagonal from upper left toward the south-east. (Assuming 0,0 is in the north-west.) It seems that once you hit a clear spot, the rest of the diagonal line gets an alpha of 256*0.1? Take advantage of that and plow down the diagonal.