Проблема с алгоритмом заполнения полигонов Scan-Line в Java

Question

(пожалуйста, не помечайте этот вопрос как неясный, я потратил много времени на его публикацию;))

Хорошо, я пытаюсь сделать простой движок 2d-игры на Java в качестве учебного проекта,и частично это рендеринг заполненного многоугольника как объекта.Я сам создаю этот алгоритм, и я действительно не могу понять, что я делаю неправильно.Мой хотя процесс выглядит примерно так: перебрать каждую строку, получить количество точек в этой строке, затем получить X-положение каждой точки в этой строке, а затем повторить цикл по этой линии снова, проверяя, является ли х в циклевнутри одной из линий в массиве точек, если это так, нарисуйте ее.

Отказ от ответственности: класс Polygon - это другой тип сетки, а его метод draw возвращает массив int, в котором линии проходят через каждую вершину.Отказ от ответственности 2: Я пробовал решения других людей, но никто не помог мне, и никто не объяснил это должным образом (это не главное в учебном проекте).

Методы рисования называются по одному на кадр.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;
    }

Класс Polygon просто использует линейный алгоритм Брезенхэма и не имеет ничего общего с проблемой.Класс игры:

@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;
    }

Ожидаемый результат - заполнить эту фигуру (она была создана с использованием многоугольной сетки):

фактический результат использования сетки FilledPolygon:

Answer 1

Обратите внимание, что вы подразумеваете, что pixels[] имеет тот же размер width*height, что и filled[].Основываясь на искаженном выводе, я бы сказал, что они просто не совпадают.

В противном случае, если вы просто хотите заполнить строку сканирования (при условии, что все выпукло), этот код слишком сложен, просто ищите конечные точки иЦикл между ними:

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;
}

Однако такой подход основан на наличии всего многоугольника в представлении, что не всегда может иметь место в реальной жизни.

Answer 2

У вашего кода, кажется, есть несколько проблем, и я не буду на этом останавливаться.

Ваш подход, основанный на рисовании контура и заполнении "внутренних" прогонов, не может работать в общем случае, потому что контуры объединяются ввершины и пересечения, и чередование outside-edge-inside-edge-outside нарушено невосстановимым способом (вы не можете знать, какой сегмент заполнить, просто взглянув на строку).

Вы былучше использовать стандартный алгоритм заполнения полигонов.В Интернете вы найдете множество описаний.

Для простого, но несколько неэффективного решения выполните следующие действия:

• обработайте все строки между минимальной и максимальной ординатами;пусть Y будет текущей ординатой;

  • петля по краям;

  • присваивает каждой вершине положительный или отрицательный знак, если y ≥ Yили y

  • всякий раз, когда конечные точки ребра имеют другой знак, вычисляют пересечение между ребром и линией;

  • вы получите четное число пересечений;сортируйте их по горизонтали;

  • рисуйте между каждой другой точкой.

Вы можете получить более эффективное решение, сохранивпроследить, какие ребра пересекают текущую строку, в так называемом «активном списке».Проверьте алгоритмы, известные как «scanline fill».