c++ - Blit 队列优化算法

Question

我正在寻求实现一个管理 blit 队列的模块。有一个表面，该表面的部分(由矩形包围)被复制到表面内的其他地方:

add_blt(rect src, point dst);

可以有任意数量的操作按顺序发布到队列中。最终，队列的用户将停止发送 blits，并要求一组最佳操作以在表面上实际执行。该模块的任务是确保没有像素被不必要地复制。

当然，由于重叠，这变得棘手。 blit 可以重新 blit 先前复制的像素。理想情况下，blit 操作将在优化阶段进行 segmentation ，这样每个 block 都可以通过单个操作到达其最终位置。

把它们放在一起很棘手，但并非不可能。我只是不想重新发明轮子。

我在网上四处查看，唯一找到的是 SDL_BlitPool Library它假设源表面与目的地不同。它还会做很多看似不必要的繁重工作:区域和类似的构建 block 是给定的。我正在寻找更高层次的东西。当然，我不会在嘴里看礼物马，我也不介意做实际工作......如果有人能提出一个基本的想法，让这个问题看起来不像实际那么复杂现在，那也很棒。

编辑:

考虑 aaronasterling 的回答……这行得通吗？

• 实现自定义区域处理程序代码，可以维护它包含的每个矩形的元数据。当区域处理程序拆分一个矩形时，它会自动将此矩形的元数据与生成的子矩形相关联。

• 优化运行开始时，创建一个由上述自定义代码处理的空区域，将其称为主区域

• 遍历 blt 队列，对于每个条目:

  • 让 srcrect 成为被检查的 blt 的源矩形

  • 获取srcrect和master region的交集到temp region

  • 从master region中移除temp region，因此master region不再覆盖temp region

  • 将 srcrect 提升到一个区域 (srcrgn) 并从中减去 temp region

  • 用当前blt的 vector 偏移temp region和srcrgn:它们的并集将覆盖当前的目标区域blt

  • 添加到 master region temp region 中的所有 rect，保留原始源元数据(第一步添加当前 blt到 master 区域)

  • Add to master region all rects in srcrgn，添加当前blt的源信息(第二步添加当前 blt 到 master 区域)

• 通过检查作为合并候选的相邻子矩形是否具有相同的元数据来优化 master region。如果 (r1.x1 == r2.x1 && r1.x2 == r2.x2) | 两个子矩形是合并候选者(r1.y1 == r2.y1 && r1.y2 == r2.y2)。如果是，将它们合并。

• 枚举主区域的子矩形。返回的每个矩形都是优化的 blt 操作目标。关联的元数据是 blt 操作的来源。

Answer 1

我想到的一个想法是将要添加的矩形的定义点存储在四叉树中(或其他一些能够实现高效碰撞检测的结构)。所以现在当你添加一个新的矩形时，你可以测试它是否有碰撞。这个想法是，当一个新矩形与一个旧矩形发生碰撞时，您可以通过将旧矩形分成 4、3 或 2 个新矩形来解决冲突，这些新矩形不包括与新添加的矩形相交的部分。我们知道旧矩形不与任何其他旧矩形相交，因此，因为新创建的矩形包含在其中，我们知道它们也不相交，因此您不必对它们执行碰撞检测。

例如，开始于:

并添加一个矩形:

将解决:

在这里，一个旧矩形被分成两个新矩形，另一个被分成三个。

这保证了在添加一个新的矩形后，队列始终处于没有交集的状态，这意味着复制这些矩形不会复制一个像素两次。