Problem with Scan-Line Polygon Filling algorithm in java

Question

(please don't mark this question as not clear, I spent a lot of time posting it ;) )

Okay, I am trying to make a simple 2d java game engine as a learning project, and part of it is rendering a filled polygon as a feature. I am creating this algorithm my self, and I really can't figure out what I am doing wrong. My though process is something like so: Loop through every line, get the number of points in that line, then get the X location of every point in that line, Then loop through the line again this time checking if the x in the loop is inside one of the lines in the points array, if so, draw it.

Disclaimer: the Polygon class is another type of mesh, and its draw method returns an int array with lines drawn through each vertex. Disclaimer 2: I've tried other people's solutions but none really helped me and none really explained it properly (which is not the point in a learning project).

The draw methods are called one per frame.
FilledPolygon:

@Override
    public int[] draw() {
        int[] pixels = new Polygon(verts).draw();
        int[] filled = new int[width * height];

        for (int y = 0; y < height; y++) {
            int count = 0;
            for (int x = 0; x < width; x++) {
                if (pixels[x + y * width] == 0xffffffff) {
                    count++;
                }
            }

            int[] points = new int[count];
            int current = 0;
            for (int x = 0; x < width; x++) {
                if (pixels[x + y * width] == 0xffffffff) {
                    points[current] = x;
                    current++;
                }
            }

            if (count >= 2) {
                int num = count;
                if (count % 2 != 0)
                    num--;

                for (int i = 0; i < num; i += 2) {
                    for (int x = points[i]; x < points[i+1]; x++) {
                        filled[x + y * width] = 0xffffffff;
                    }
                }
            }
        }

        return filled;
    }

The Polygon class simply uses Bresenham's line algorithm and has nothing to do with the problem.
The game class:

@Override
    public void load() {
        obj = new EngineObject();
        obj.addComponent(new MeshRenderer(new FilledPolygon(new int[][] {
                {0,0},
                {60, 0},
                {0, 60},
                {80, 50}
        })));
        ((MeshRenderer)(obj.getComponent(MeshRenderer.class))).color = CYAN;
        obj.transform.position.Y = 100;
    }

The expected result is to get this shape filled up.(it was created using the polygon mesh):

The actual result of using the FilledPolygon mesh:

Did not go through your code but see [how to rasterize rotated rectangle (in 2d by setpixel)](https://stackoverflow.com/a/19078088/2521214) Your main problem is that this algo works only for convex polygons !!! which clearly your wanted output is not ... so you should divide your polygon into set of convex polygons first (by ear-clipping or whatever else algo). Also your description of the algo sounds susspicious ... compare with mine for errors in logic (or its a different algo than I am thinking of?) — Spektre, Sep 26 '19 at 10:37

score 0 · Answer 1 · answered Sep 26 '19 at 09:30

You code seems to have several problems and I will not focus on that.

Your approach based on drawing the outline then filling the "inside" runs cannot work in the general case because the outlines join at the vertices and intersections, and the alternation outside-edge-inside-edge-outside is broken, in an unrecoverable way (you can't know which segment to fill by just looking at a row).

You'd better use a standard polygon filling algorithm. You will find many descriptions on the Web.

For a simple but somewhat inefficient solution, work as follows:

process all lines between the minimum and maximum ordinates; let Y be the current ordinate;
- loop on the edges;
- assign every vertex a positive or negative sign if y ≥ Y or y < Y (mind the asymmetry !);
- whenever the endpoints of an edge have a different sign, compute the intersection between the edge and the line;
- you will get an even number of intersections; sort them horizontally;
- draw between every other point.

You can get a more efficient solution by keeping a trace of which edges cross the current line, in a so-called "active list". Check the algorithms known as "scanline fill".

score 0 · Answer 2 · answered Sep 26 '19 at 13:29

Note that you imply that pixels[] has the same width*height size as filled[]. Based on the mangled output, I would say that they are just not the same.

Otherwise if you just want to fill a scanline (assuming everything is convex), that code is overcomplicated, simply look for the endpoints and loop between them:

public int[] draw() {
    int[] pixels = new Polygon(verts).draw();
    int[] filled = new int[width * height];

    for (int y = 0; y < height; y++) {
        int left = -1;
        for (int x = 0; x < width; x++) {
            if (pixels[x + y * width] == 0xffffffff) {
                left = x;
                break;
            }
        }
        if (left >= 0) {
            int right = left;
            for (int x = width - 1; x > left; x--) {
                if (pixels[x + y * width] == 0xffffffff) {
                    right = x;
                    break;
                }
            }
            for (int x = left; x <= right; x++) {
                filled[x + y * width] = 0xffffffff;
            }
        }
    }

    return filled;
}

However this kind of approach relies on having the entire polygon in the view, which may not always be the case in real life.

As for your statement, even if the object is half off-screen, the mesh (draw() method) returns a calculation of the vertices, and they can't be a minus, granting you (hopefully) always a closed shape. — Coder's Crux, Sep 26 '19 at 17:14

Problem with Scan-Line Polygon Filling algorithm in java

2 Answers2