Blit队列优化算法

Question

我希望实现一个管理blit队列的模块。只有一个曲面，并且这个曲面的一部分(以矩形为界)被复制到曲面的其他地方：

add_blt(rect src, point dst);

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

当然，这会因为重叠而变得棘手。一个blit可以重新创建以前复制的像素.理想情况下，blit操作将在优化阶段被细分，这样每个块都会通过一个操作到达其最后位置。

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

我在网上环顾了一下，唯一发现的是BlitPool库，它假设源表面与目的地不同。它也做了大量繁重的工作，似乎是不必要的:区域和类似的积木是给定的。我正在寻找更高层次的东西。当然，我不会在嘴里找一匹礼物马，我也不介意做实际的工作……如果有人能拿出一个基本想法，让这个问题看起来不像现在那么复杂，那就太棒了。

编辑：

想想aaronasterling的答案..。这个能行吗？

• 实现自定义区域处理程序代码，该代码可以维护其包含的每个矩形的元数据。当区域处理程序分割矩形时，它将自动将该矩形的元数据与生成的子矩形关联起来。
• 当优化运行开始时，创建一个由上述自定义代码处理的空区域，将其称为master region
• 遍历blt队列，并对每个条目进行迭代：

- Let `srcrect` be the source rectangle for the `blt` beng examined
- Get the intersection of `srcrect` and `master region` into `temp region`
- Remove `temp region` from `master region`, so `master region` no longer covers `temp region`
- Promote `srcrect` to a region (`srcrgn`) and subtract `temp region` from it
- Offset `temp region` and `srcrgn` with the vector of the current `blt`: their union will cover the destination area of the current `blt`
- Add to `master region` all rects in `temp region`, retaining the original source metadata (step one of adding the current `blt` to the `master region`)
- Add to `master region` all rects in `srcrgn`, adding the source information for the current `blt` (step two of adding the current `blt` to the `master region`)

​

• 通过检查合并候选的相邻子矩形是否具有相同的元数据来优化master region。如果是(r1.x1 == r2.x1 && r1.x2 == r2.x2) | (r1.y1 == r2.y1 && r1.y2 == r2.y2)，两个子矩形是合并候选。如果是的话，把它们结合起来。
• 枚举master region的子矩形。返回的每个矩形都是优化的blt操作目标。相关元数据是blt操作的源。

Answer 1

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

例如，首先：

​

​

并添加一个矩形：

​

​

将决心：

​

​

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

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

Answer 2

SDL_BlitPool..啊，那是我早期的作品。

闪电战的方式是

for_each(down to up) {
 if (overlapped) {
  1 split back-surface
   1-1 calculate overlap code
   1-2 add sub-rectangle (use overlap code)
   1-3 delete divided-surface
 }
}

简单地说就是这样。

“重叠代码”为0-15整数。

你知道，重叠模式只是16个模式。

02.png

重叠码为4位(0-15)值。

前2位是Y轴，尾2位是X轴(在SDL_BlitPool中).

每个1位值只是MSB值。

就像..。

01.png

在这个图像中: MSB ==箭头方向。

我以为还有更好的图书馆可以再买一间。嗯我想重写它。

对不起我的英语水平。