graphics - 像素与多边形重叠 : efficient (scanline-type) algorithm

Question

问题说明:我有一个矩形且均匀间隔的像素图像，其顶点坐标为 (i,j)、(i+1,j)、(i, j+1)、(i+1, j+1) [i=0,。 ..,m-1; j=0,...,n-1] 和顶点坐标为 (x_1,y_1), ..., (x_n, y_n) 的多边形 P。现在我想有效地计算每个像素与 P 重叠的百分比。P 可以是非凸的，甚至是自交的。

本质上，这是扫描线光栅化算法的“软”概括，该算法可以有效地检查像素中心是否位于多边形内部/外部。

我可以想到以下方法:

(1) 对图像进行上采样(例如按 10*10 倍)，计算多边形内有多少个子像素中心，然后除以 100。问题:时间效率、内存效率、准确性。

(2) 在稍大且经过 (0.5,0.5) 平移的网格上使用扫描线算法来计算完全位于内部/外部的像素，创建“边界”像素列表，沿逆时针方向行走边缘并计算沿途所有像素的交叉区域。问题:需要微妙的编码，容易引入错误。

我的问题:有人已经遇到过这个问题吗？您知道第三种更好的方法吗？如果没有，您是否通过(1)或(2)获得了更好的体验？我认为这个问题可能会在抗锯齿的情况下出现？

Answer 1

进行精确的几何分析可能不会太困难。

首先处理那些被多边形部分覆盖的像素:您可以使用 technique from ray-tracing快速找到与多边形边缘相交的所有像素。然后您可以使用 Cohen-Sutherland算法有效地找到边缘和像素之间的交点，因此您可以计算该像素的覆盖面积。

请注意，您可以避免 Cohen-Sutherland 中涉及的两个裁剪操作之一，因为相邻像素将共享一个片段交点。例如 - 如果您有两个相邻像素 A 和 B 与线段 p->q 相交于点 a1、a2、b1 和 b2，然后 a2 和 b1 将是相同的。在针对 B 进行剪辑时，将段 a2->q 传递到例程中应该可以避免重复工作。

您必须专门处理包含多边形顶点的像素，但这也不应该太棘手:Cohen-Sutherland 也会在这里提供帮助。

自相交的多边形也会引发一些特殊情况来处理 - 与两个或多个边相交的像素。我很容易想象，在所有情况下精确处理这些可能会很棘手，因此我很想在这里采用上采样方法。

一旦识别出这些边缘像素，您就可以执行标准扫描线操作来填充多边形的内部像素。

编辑:实际上，现在我想得更多了，你完全可以跳过科恩-萨瑟兰步骤。链接论文中的算法可以轻松扩展以返回线段和像素网格之间的交点。该段将在 min( tMaxX, tMaxY ) 处留下给定像素。跟踪最后一个导出点以重新用作下一个像素的入口点。