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

Question

对于一个游戏,我绘制了几千个随机分布的圆形的密集簇,这些圆圈具有不同的半径,由一系列(x,y,r)三元组定义.这是一个包含14,000个圆圈的示例图像:

我有一些动态效果,比如合并群集,但为了实现这一点,我需要每帧重绘所有的圆圈.

绘制的圆圈中的许多(可能是80-90%)被后续绘制覆盖.因此我怀疑通过预处理,我可以通过消除覆盖的圆圈来显着加快我的绘制循环.是否有一种能够以合理的效率识别它们的算法？

我可以忍受相当多的假阴性(即绘制一些实际被覆盖的圆圈),只要它不是那么多,绘制效率会受到影响.我也可以容忍误报,只要它们几乎是正面的(例如删除一些仅覆盖99%的圆圈).我也可以改变圈子的分布方式,只要它看起来还不错.

Answer 1

这种剔除本质上是隐藏的表面算法所做的 - 特别是称为"对象空间"的变种.在您的情况下,圆的排序顺序为它们提供了有效的恒定深度坐标.它不变的事实简化了问题.

关于HSA的经典参考就在这里.我会给它读一些想法.

受这种想法启发的一个想法是用"扫描线"算法考虑每个圆圈,比如从上到下移动的水平线.扫描线包含它正在触摸的一组圆圈.通过按顶部坐标对圆的输入列表进行排序来初始化.

扫描在"事件"中前进,"事件"是每个圆的顶部和底部坐标.到达顶部时,将圆圈添加到扫描中.当它的底部出现时,将其移除(除非它已经如下所述消失).当一个新的圆圈进入扫描时,请考虑它已经存在的圆圈.您可以将事件保存在最大(y坐标)堆中,根据需要随意添加它们:下一个输入圆的顶部坐标加上所有扫描线圆的底部坐标.

进入扫描的新圆圈可以完成3件事中的任何一件或全部.

1. 扫描中的模糊圆圈具有更大的深度.(由于我们确定了不绘制的圆圈,因此该决定的保守方面是使用新圆圈中最大的包含轴对齐框(BIALB)来记录每个现有更深圆圈的模糊区域.)

2. 被其他深度较小的圆圈遮挡.(这里保守的方法是使用彼此相关圆的BIALB来记录新圆的模糊区域.)

3. 有没有遮挡的区域.

必须保持每个圆圈的模糊区域(通常会在处理更多圆圈时增长),直到扫描线到达其底部.如果遮挡区域在任何时候覆盖整个圆圈,则可以删除它并且从不绘制.

隐藏区域的记录越详细,算法就越好.矩形区域的联合是一种可能性(例如,参见Android的区域代码).单个矩形是另一个,但这可能会导致许多误报.

类似地,还需要用于在扫描线中找到可能模糊和模糊的圆的快速数据结构.包含BIALB的区间树可能很好.

请注意,在实践中,像这样的算法只能产生原始数量的巨大成功,因为快速的图形硬件是如此......快.

Answer 2

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

\n

想象一下，您将渲染表面划分为正方形网格，以便最小的渲染圆可以适合网格，如下所示：

\n

\n

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

\n

您可以在这里获得一些关于正方形最佳圆形覆盖的想法

\n

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

\n

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

\n

您还可以通过绘制未完全被给定圆覆盖的网格方块（或消除从已绘制的表面稍微溢出的圆）来“作弊”，以一些误报为代价增加消除的圆的数量。

\n

然后，您可以使用 Z 缓冲区算法渲染剩余的圆圈（即让 GPU 完成其余工作）。

\n

基于CPU的方法

\n

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

\n

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

\n

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

\n

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

\n

可以使用相同的原理来检查圆是否适合已涂漆的表面。

\n

基于 GPU 的方法

\n

我已经很长时间没有使用计算机图形学了，但如果当前技术水平允许，您可以让 GPU 为您绘图。

\n

绘制网格可以通过渲染每个圆圈以适应网格来实现

\n

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

\n

效率

\n

网格尺寸应该有一些最佳点。更密集的网格将覆盖更大比例的圆表面，从而消除更多圆（更少的假阴性），但计算成本将以 o(1/grid_step\xc2\xb2) 增长。

\n

当然，如果渲染的圆圈可以缩小到大约 1 像素直径，您也可以转储整个算法并让 GPU 来完成工作。但与基于 GPU 像素的方法相比，效率随着网格步长的平方而增长。

\n

在我的示例中使用网格，对于完全随机的一组圆圈，您可能会出现大约 1/3 的漏报。

\n

对于你的图片，它似乎定义了体积，2/3 的前景圆圈和（几乎）所有的后向圆圈都应该被消除。剔除超过 80% 的圆圈可能值得付出努力。

\n

话虽如此，在强力计算竞赛中击败 GPU 并不容易，因此我对您可以期望的实际性能增益只有最模糊的了解。不过，尝试一下可能会很有趣。

\n