4
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ Also, the shadow is infinite, right? So you can simply continue it diagonally to the bottom-right until an occupied pixel is encountered. Start in the bottom left corner and work the diagonals until the top right corner is reached. And again, inline everything, increment the index directly without multiplication. \$\endgroup\$ – wOxxOm Aug 4 '16 at 23:43
  • \$\begingroup\$ I'm confused on what you mean by "Start in the bottom left corner and work the diagonals until the top right corner is reached". Are you suggesting to treat each diagonal as one line? How does that enable it to skip checking for certain pixels? \$\endgroup\$ – Derek 朕會功夫 Aug 4 '16 at 23:46
  • \$\begingroup\$ Ah, I see what you mean. Going to test that out. \$\endgroup\$ – Derek 朕會功夫 Aug 5 '16 at 0:05
  • \$\begingroup\$ @wOxxOm Is there an easy and fast way to iterate through the 2D array diagonally? It sounds good in theory but it seems difficult to implement. \$\endgroup\$ – Derek 朕會功夫 Aug 5 '16 at 1:36
  • \$\begingroup\$ Do you have a jsFiddle or something to test? Am curious to try a web worker mini-library to see if it helps cases like this. \$\endgroup\$ – Sergio Aug 5 '16 at 11:54
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ So I tested the code in your answer but it probably went into an infinite loop since it froze my page... \$\endgroup\$ – Derek 朕會功夫 Aug 6 '16 at 5:06
  • \$\begingroup\$ I've tested it again and indeed it's a little bit faster :) \$\endgroup\$ – Derek 朕會功夫 Aug 6 '16 at 6:16
  • \$\begingroup\$ I've inlined everything in my original code (and reordered the loops, not sure if cache misses is a thing in JS) and amazingly it reduced the running time quite significantly. \$\endgroup\$ – Derek 朕會功夫 Aug 7 '16 at 1:08
  • \$\begingroup\$ It'd be reasonable if you post your code and accept it as a solution. \$\endgroup\$ – wOxxOm Aug 7 '16 at 5:04
  • \$\begingroup\$ I have posted my code however your answer will stay as marked as solution. \$\endgroup\$ – Derek 朕會功夫 Aug 8 '16 at 17:16
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.