java中的扫描线多边形填充算法问题

Question

（（请不要将此问题标记为不清楚，我花了很多时间发布它；））

[好，我正在尝试制作一个简单的2d Java游戏引擎作为学习项目，其中一部分是将填充的多边形渲染为特征。我自己创建了这个算法，但我真的不知道自己在做什么错。我的流程虽然是这样的：遍历每条线，获取该行中的点数，然后获取该行中每个点的X位置，然后这次再次遍历该行，检查循环中的x是否在points数组中的一条线内，如果是，请绘制它。

免责声明：Polygon类是网格的另一种类型，其draw方法返回一个int数组，该数组具有通过每个顶点绘制的线。免责声明2：我已经尝试过其他人的解决方案，但是没有一个人真正地帮助过我，也没有一个人正确地解释它（这不是学习项目的重点）。

draw方法称为每帧一个。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类仅使用Bresenham的line算法，与该问题无关。游戏类：

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

预期的结果是使该形状填充满。（它是使用多边形网格创建的：]

<< img src =“ https://image.soinside.com/eyJ1cmwiOiAiaHR0cHM6Ly9pLmltZ3VyLmNvbS80b2dYSnZtLnBuZyJ9” alt =“ img1”>

使用FilledPolygon网格的实际结果：

Answer 1

您的代码似乎有几个问题，我将不再关注。

您基于绘制轮廓然后填充“内部”行程的方法在一般情况下不起作用，因为轮廓在顶点和相交处连接，并且交替的外部边缘-内部-边缘-外部-交替出现，无法恢复方式（仅查看一行就无法知道要填充哪个段）。

您最好使用标准的多边形填充算法。您会在网上找到许多说明。

对于一个简单但效率不高的解决方案，请按以下步骤工作：

• 处理最小和最大坐标之间的所有线；令Y为当前纵坐标；

  • 边缘上的环；

  • 如果y≥Y或y

  • 每条边的端点具有不同的符号，请计算边与线之间的交点；

  • 您将得到一个偶数个交叉点；水平排序；

  • 在其他点之间绘制。

通过在所谓的“活动列表”中跟踪哪些边与当前线交叉，可以获得更有效的解决方案。检查称为“扫描线填充”的算法。

Answer 2

注意，您暗示pixels[]的大小与width*height相同。基于错误的输出，我想说它们是不一样的。

否则，如果您只想填充扫描线（假设所有内容都是凸面的，则说明该代码过于复杂，只需查找端点并在它们之间循环：

filled[]

但是这种方法依赖于在视图中具有整个多边形，在现实生活中可能并非总是如此。