具有不同半径的圆覆盖算法

Question

为了制作一个游戏，我正在绘制几千个半径不同的密集圆形团簇，由一系列（x，y，r）三元组定义。以下是由14,000个圆形组成的示例图像：

我打算在游戏中增加一些动态效果，例如合并团簇，为此我需要在每一帧重新绘制所有圆形。

绘制时绘制的圆形中有许多（可能80-90％）被后续绘制覆盖。因此，我怀疑通过预处理可以显着提高绘制循环的速度，消除覆盖的圆形。是否有一种算法可以以合理的效率识别它们？

我可以容忍相当大数量的假阴性（即绘制了实际上被覆盖的某些圆形），只要它们不会太多以至于绘制效率受到影响即可。我也可以容忍假阳性，只要它们几乎是真阳性（例如删除仅被覆盖99％的某些圆形）。只要看起来还可以，我也可以接受圆形分布方式的更改。

- Cosmologicon

Answer 1

这种筛选本质上就是隐藏表面算法（HSAs）所做的事情，特别是“对象空间”这种类型。在您的情况下，圆的排序顺序为它们提供了一个有效的恒定深度坐标。事实上它是恒定的，简化了问题。

关于HSA的经典参考资料在这里。建议阅读以获取灵感。

受此思想启发的一个想法是考虑使用“扫描线”算法来处理每个圆，例如从上到下移动的水平线。扫描线包含它所接触的圆的集合。通过将输入圆列表按顶部坐标排序进行初始化。

扫描以“事件”为单位推进，即每个圆的顶部和底部坐标。当到达顶部时，将圆添加到扫描中。当其底部出现时，将其删除（除非已经像下面描述的那样消失）。当新的圆进入扫描时，将其与已经存在的圆进行比较。可以将事件保留在最大（y坐标）堆中，根据需要懒惰地添加它们：下一个输入圆的顶部坐标加上所有扫描线圆的底部坐标。

进入扫描的新圆可以执行以下3件事中的任何一件或多件。

1. 对于隐藏在扫描中的较深圆形（因为我们正在识别要绘制的圆形而不是，所以这种决策的保守方面是使用新圆形的最大包含轴对齐框（BIALB）记录每个现有更深圆形的遮挡区域。）
2. 被其他深度较小的圆形遮挡。（这里的保守方式是使用每个其他相关圆形的BIALB来记录新圆形的遮挡区域。）
3. 具有未被遮挡的区域。

每个圆的遮挡区域必须得到维护（随着处理更多圆，它通常会增长），直到扫描线到达其底部。如果遮挡区域在任何时候覆盖整个圆，则可以将其删除并永远不绘制。

记录遮挡区域的详细程度越高，算法的效果就越好。矩形区域的联合是一种可能性（例如，请参见Android的Region代码）。另一个选择是单个矩形，尽管这可能会导致许多错误结果。

同样，需要快速的数据结构来查找可能遮挡和被遮挡的圆形。包含BIALB的间隔树可能是一个好选择。

请注意，在实践中，像这样的算法只有在基元数量巨大时才能产生胜利，因为快速的图形硬件是如此之快。

- Gene

---

我认为维护每个圆的被遮挡面积的想法行不通，因为要准确地（甚至是保守地）做到这一点，就需要避免计算新圆已经遮挡过的区域，而这很棘手。更好的解决方案是，针对每个圆维护一组完全覆盖其尚未被遮挡部分的最小包含轴对齐框（SIAABs），并在出现覆盖圆的BIALBs时将其减去。如果一个圆的SIAAB集合变为空，则该圆是不可见的，并且可以删除。 - j_random_hacker

这听起来很有前途，但我不理解细节。据我所知，对于每一对连续事件（水平线），在那个时间内扫描中的每个圆圈，我需要找到完全被圆圈覆盖的最大框。如果没有其他问题，那似乎需要进行大量的sqrt操作，是吗？另外，什么是Android的Region？它在您链接的论文中吗？（抱歉，我刚开始阅读。） - Cosmologicon

Answer 2

这是我脑海中的一个简单算法：

1. 将 N 个圆插入四叉树中（从下面开始）
2. 对于每个像素，使用四叉树确定最上层的圆（如果存在）
3. 用圆的颜色填充像素

添加圆指的是将圆心加入四叉树。这会为叶子节点创建4个子节点。将圆存储在该叶子节点中（该节点现在不再是叶子）。因此，每个非叶节点对应一个圆。

要确定最上层的圆，请遍历四叉树，并沿途测试是否在该节点处与像素相交。最上层的圆是最深处与像素相交的圆。

这应该需要 O(M log N) 的时间（如果圆分布得很好），其中 M 是像素数量，N 是圆的数量。如果树退化，则最坏情况仍为 O(MN)。

伪代码：

quadtree T
for each circle c
    add(T,c)
for each pixel p
    draw color of top_circle(T,p)

def add(quadtree T, circle c)
    if leaf(T)
        append four children to T, split along center(c)
        T.circle = c
    else
        quadtree U = child of T containing center(c)
        add(U,c)

def top_circle(quadtree T, pixel p)
    if not leaf(T)
        if intersects(T.circle, p)
            c = T.circle
        quadtree U = child of T containing p
        c = top_circle(U,p) if not null
    return c

- tskuzzy

---

很酷，我喜欢这个。只是为了明确起见，第一个循环是O（Nd），其中d是四叉树的深度，并且您假设O（M log N）循环支配了这个循环，对吗？我只是想知道这是否可能更快：为每个像素初始化一个布尔数组并将其设置为false。对于每个圆，从顶部开始，设置它覆盖的每个像素的布尔值，并仅在它设置先前未设置的布尔值时保留该圆。 - Cosmologicon

这就是我所说的一个好算法。唯一的问题是，你需要让CPU完成所有工作，并且每个圆将具有恒定的颜色（除非CPU还进行了一些光照计算）。此外，树的实际效率将取决于圆的分布情况。根据给出的示例图像，我预计大约一半的圆代表背面表面，因此您可以期望类似于O（2M log N/2）的计算时间。 - kuroi neko

Answer 3

根据您提供的示例图像，似乎您的圆形具有几乎恒定的半径。如果它们的半径不能低于一定数量的像素，则可以利用圆的简单几何来尝试图像空间方法。

想象一下，您将渲染表面划分为一个网格，以便最小的渲染圆可以像这样适合网格：

圆的半径为sqrt(10)格，覆盖至少21个正方形，因此如果您将任何圆完全重叠的正方形标记为已绘制，则将消除大约21/10pi圆面积的部分，即约为2/3。

您可以通过这里了解最佳圆覆盖的一些想法。

剔除过程看起来有点像一个反向绘画算法：

For each circle from closest to farthest
   if all squares overlapped (even partially) by the circle are painted
       eliminate the circle
   else
       paint the squares totally overlapped by the circle

您还可以通过在给定圆形未完全覆盖的网格方块上涂色（或消除从已涂面积中略微溢出的圆形），以增加消除圆形的数量，以换取一些误报来“作弊”。

然后，您可以使用Z缓冲算法（即让GPU完成其余工作）来呈现剩余的圆形。

CPU方法

这假设您将网格实现为内存位图，没有GPU的帮助。

要确定要绘制的正方形，您可以使用基于圆心与网格距离（示例图像中的红色十字）和实际圆半径的预计算模式。

如果直径的相对变化足够小，则可以定义一个二维表，该表由圆半径和距离最近网格点的中心索引。

检索到正确的模式后，您可以使用简单的对称性将其应用于适当的位置。

相同的原理也可用于检查圆是否适合已涂面。

基于GPU方法

我很久以前就开始从事计算机图形学了，但是如果当前的技术允许，您可以让GPU为您绘制。

将网格绘制出来可以通过渲染每个圆并按比例缩放以适应网格来实现

检查消除需要读取包含圆的所有像素值（按网格尺寸缩放）。

效率

网格尺寸应该有一个最佳点。更密集的网格将覆盖更高比例的圆面积，从而消除更多圆（减少误判），但计算成本将以o(1/grid_step²)增长。

当然，如果渲染的圆可以缩小到大约1像素直径，那么你也可以放弃整个算法，让GPU来处理。但与基于GPU像素的方法相比，效率随着网格步长的平方增长。

在我的示例中使用网格，您可以预期对于完全随机的圆集合，大约有1/3的误判。

对于您的图片，似乎定义了体积，应该消除2/3的前景圆和（几乎）所有后向圆。消除超过80％的圆可能值得努力。

话虽如此，在暴力计算竞赛中很难击败GPU，因此我只有最模糊的想法关于实际性能收益。不过尝试一下可能很有趣。

- kuroi neko

Answer 4

如果一个圆完全在另一个圆内部，那么它们中心之间的距离加上较小圆的半径最多等于较大圆的半径（自己画图看一下！）。因此，您可以进行以下检查：

float distanceBetweenCentres = sqrt((topCircle.centre.x - bottomCircle.centre.x) * (topCircle.centre.x - bottomCircle.centre.x) + (topCircle.centre.y - bottomCircle.centre.y) * (topCircle.centre.y - bottomCircle.centre.y));

if((bottomCircle.radius + distanceBetweenCentres) <= topCircle.radius){
  // The bottom circle is covered by the top circle.
}

为了提高计算速度，您可以先检查顶部圆圈的半径是否大于底部圆圈，如果不是，则无法覆盖底部圆圈。希望这能帮到您！

- msgambel

---

在某种程度上是这样，但如果你有10,000个圆，那么必须检查大约1/2 * 10,000 * 10,000对。这就是使这成为一个有趣问题的原因。更不用说一个圆可能会被几个其他圆的并集遮挡，所以成对比较并没有那么有帮助。 - Gene

我在考虑每次添加新圆时检查它，以至少移除成对的圆。 - msgambel

我的第一反应是，虽然这是一个非常简单的测试，但它只能匹配一小部分圆形。然而，我在我的示例图像上进行了测试，惊讶地发现它可以消除51％的绿色圆圈和20％的紫色圆圈。因此，这可能仍然是值得的，至少作为第一步。 - Cosmologicon

太棒了！在添加新圆时，这绝对是一个快速检查。还有很多更强大的解决方案，从这个解决方案中受益，可以减少总数。 - msgambel

Answer 5

您没有提及Z分量，因此我假设它们按Z顺序列在列表中并从后向前绘制（即绘图算法）。

正如之前的张贴者所说，这是一种遮挡剔除练习。

除了所述的物体空间算法之外，我还建议研究屏幕空间算法，例如分层Z-缓冲。您甚至不需要z值，只需位标志指示是否存在某些内容。

请参见：http://www.gamasutra.com/view/feature/131801/occlusion_culling_algorithms.php?print=1

- Dithermaster