Algorithm - Given a set of pixels with coordinates, how to find all the contiguous lines in an efficient way?

Question

I am working on an extrusion function to create a mesh given a 2D texture and the thickness of it.

Example:

I have achieved finding the outline of the texture by simply looking for the pixels either near the edge or near transparent ones. It works great even for concave (donut-shaped) shapes but now I am left with an array of outline pixels.

Here is the result:

The problem is that the values, by being ordered from top-left to bottom-right, they are not suitable for building an actual 3D outline.

My current idea is the following:

Step 1.

From index [0], look at the right-hand side for the nearest contiguous point different from the starting point.

• If found, move it into another array.

• If nothing, look at the bottom. Continue until the starting point has been reached.

Step2.

Pick another pixel, if any, from the pixels remained in the array.

Repeat from Step1.

This, in my head, would work but it seems quite inefficient. Researching, I found about the Moore-Neighbor tracing algorithm but I couldn't find anywhere an example where it worked with convex shapes.

Any thoughts?

Answer 1

At the end, I managed to find my own answer, so here I want to share it:

After finding the outline of a given image (using the alpha value of each pixel), the pixels will be ordered in rows, good for drawing them but bad for constructing a mesh.

So, the next step is to find contiguous lines. This is done by checking first if there are any neighbors to the found pixel giving priority to the ones top/left/right/bottom (otherwise it will skip the corners).

Keep going until no pixels are left in the original array.

Here is the actual implementation (for Babylon.js but the idea works with any other engine):

Playground: https://www.babylonjs-playground.com/#9GPMUY#11

var GetTextureOutline = function (data, keepOutline, keepOtherPixels) {
    var not_outline = [];
    var pixels_list = [];
    for (var j = 0; j < data.length; j = j + 4) {
        var alpha = data[j + 3];
        var current_alpha_index = j + 3;
        // Not Invisible
        if (alpha != 0) {
            var top_alpha = data[current_alpha_index - (canvasWidth * 4)];
            var bottom_alpha = data[current_alpha_index + (canvasWidth * 4)];
            var left_alpha = data[current_alpha_index - 4];
            var right_alpha = data[current_alpha_index + 4];

            if ((top_alpha === undefined || top_alpha == 0) ||
                (bottom_alpha === undefined || bottom_alpha == 0) ||
                (left_alpha === undefined || left_alpha == 0) ||
                (right_alpha === undefined || right_alpha == 0)) {
                pixels_list.push({
                    x: (j / 4) % canvasWidth,
                    y: parseInt((j / 4) / canvasWidth),
                    color: new BABYLON.Color3(data[j] / 255, data[j + 1] / 255, data[j + 2] / 255),
                    alpha: data[j + 3] / 255
                });

                if (!keepOutline) {
                    data[j] = 255;
                    data[j + 1] = 0;
                    data[j + 2] = 255;
                }
            } else if (!keepOtherPixels) {
                not_outline.push(j);
            }
        }

    }

    // Remove not-outline pixels
    for (var i = 0; i < not_outline.length; i++) {
        if (!keepOtherPixels) {
            data[not_outline[i]] = 0;
            data[not_outline[i] + 1] = 0;
            data[not_outline[i] + 2] = 0;
            data[not_outline[i] + 3] = 0;
        }
    }


    return pixels_list;
}

var ExtractLinesFromPixelsList = function (pixelsList, sortPixels) {
    if (sortPixels) {
        // Sort pixelsList
        function sortY(a, b) {
            if (a.y == b.y) return a.x - b.x;
            return a.y - b.y;
        }
        pixelsList.sort(sortY);
    }

    var lines = [];
    var line = [];
    var pixelAdded = true;
    var skipDiagonals = true;
    line.push(pixelsList[0]);
    pixelsList.splice(0, 1);

    var countPixels = 0;
    while (pixelsList.length != 0) {
        if (!pixelAdded && !skipDiagonals) {
            lines.push(line);
            line = [];
            line.push(pixelsList[0]);
            pixelsList.splice(0, 1);
        } else if (!pixelAdded) {
            skipDiagonals = false;
        }

        pixelAdded = false;
        for (var i = 0; i < pixelsList.length; i++) {
            if ((skipDiagonals && (
                line[line.length - 1].x + 1 == pixelsList[i].x && line[line.length - 1].y == pixelsList[i].y ||
                line[line.length - 1].x - 1 == pixelsList[i].x && line[line.length - 1].y == pixelsList[i].y ||
                line[line.length - 1].x == pixelsList[i].x && line[line.length - 1].y + 1 == pixelsList[i].y ||
                line[line.length - 1].x == pixelsList[i].x && line[line.length - 1].y - 1 == pixelsList[i].y)) || (!skipDiagonals && (
                    line[line.length - 1].x + 1 == pixelsList[i].x && line[line.length - 1].y + 1 == pixelsList[i].y ||
                    line[line.length - 1].x + 1 == pixelsList[i].x && line[line.length - 1].y - 1 == pixelsList[i].y ||
                    line[line.length - 1].x - 1 == pixelsList[i].x && line[line.length - 1].y + 1 == pixelsList[i].y ||
                    line[line.length - 1].x - 1 == pixelsList[i].x && line[line.length - 1].y - 1 == pixelsList[i].y
                ))) {
                line.push(pixelsList[i]);
                pixelsList.splice(i, 1);
                i--;
                pixelAdded = true;
                skipDiagonals = true;
            }
        }


    }
    lines.push(line);
    return lines;
}