43

我有大量矩形，有些与其他矩形重叠；每个矩形都有一个绝对的 z 顺序和一个颜色。（每个“矩形”实际上是粒子效果、网格或纹理的轴对齐边界框，并且可能是半透明的。但只要您不尝试在其他矩形后面剔除矩形，就更容易抽象地思考彩色矩形，所以我将在问题描述中使用它:)

改变“颜色”的成本相当高；连续绘制两个蓝色矩形比绘制两个不同颜色的矩形要快得多。

绘制甚至不在屏幕上的矩形的成本也很高，应该避免。

如果两个矩形不重叠，则它们相对于彼此的绘制顺序并不重要。只有当它们重叠时，z 顺序才重要。

例如：

重叠的矩形

1（红色）和4（红色）可以画在一起。2（蓝色）和 5（蓝色）也可以一起绘制，3（绿色）和 7（绿色）也可以。但必须在 6（蓝色）之后绘制 8（红色）。所以要么我们将所有三个红色画在一起，然后将蓝色画成两组，或者我们将所有蓝色画在一起，然后将红色画成两组。

一些矩形可能会偶尔移动。（不是全部；已知一些矩形是静态的；其他已知是移动的。）

我将在 JavaScript/webGL 中绘制这个场景。

如何以合理的顺序绘制矩形以最小化颜色变化，并在 JavaScript 剔除代码与让 GPU 剔除之间取得良好的折衷？

（仅仅计算出哪些矩形重叠，哪些是可见的很昂贵。我有一个基本的四叉树，这极大地加快了我的场景绘制速度（与仅发出整个场景的绘制操作相比）；现在的问题是如何最小化 OpenGL状态变化并尽可能连接属性数组）

更新我创建了一个非常简单的测试应用程序来说明问题并作为解决方案演示的基础： http ://williame.github.com/opt_rects/

源代码在 github 上，可以很容易地被分叉：https ://github.com/williame/opt_rects

事实证明，很难制作一个具有足够状态更改的小测试应用程序来实际重现我在完整游戏中看到的问题。在某些时候，您将不得不认为状态更改可能足够昂贵。同样重要的是如何加快空间索引（演示中的四叉树）和整体方法。

4

4 回答 4

16

您做出了非常错误的假设，即您在桌面浏览器上获得的性能将以某种方式决定您 iPhone 上的性能。您需要了解 iPhone 硬件实现了基于 tile 的延迟渲染，这意味着无论如何，片段着色器在流水线中使用得非常晚。正如 Apple 自己所说（“<em>不要浪费 CPU 时间从前到后对对象进行排序”），对您的图元进行 Z 排序只会给您带来一点性能提升。

但这是我的建议：如果更改颜色很昂贵，请不要更改颜色：将其作为顶点属性传递，并将行为合并到一个超级着色器中，这样您就可以在一个或几批中绘制所有内容，甚至无需排序。然后对您的平台进行基准测试并确定最佳批量大小。

于 2013-01-17T08:21:47.733 回答
12

选择颜色，而不是盒子！

在任何时间点，一个或多个盒子都是可涂漆的，即它们可以在下一次涂漆而不会产生问题（尽管可能会因为与最近涂漆的盒子颜色不同而产生成本）。

每一点的问题都是：接下来我们应该选择什么颜色来绘制？没有必要考虑选择单独的可绘制框来绘制，因为一旦你选择了一个特定的框来绘制下一个，你还不如绘制当时可以绘制的所有可用的相同颜色的框。那是因为画一个盒子永远不会增加对问题的约束，它只会删除它们；如果您可以在不更改当前颜色的情况下选择不绘制可绘制的盒子，则不能使解决方案的成本低于其他方式，因为您稍后必须绘制此盒子并且可能需要更改颜色。这也意味着我们绘制相同颜色的可绘制盒子的顺序并不重要，因为我们将在一个盒子绘制操作“块”中一次绘制所有这些盒子。

依赖图

首先构建一个“位于下方”的依赖图，其中每个彩色矩形由一个顶点表示，如果矩形 v 与矩形 u 重叠并位于其下方，则从 v 到 u 有一条弧（箭头）。我的第一个想法是通过找到传递闭包来使用它来构建“必须在之前绘制”依赖图，但实际上我们不需要这样做，因为下面的所有算法都关心顶点是否可绘制. 可绘制顶点是没有前驱（弧内）的顶点，采用传递闭包不会改变顶点是否有 0 个弧内。

此外，每当一个给定颜色的盒子只有与其祖先颜色相同的盒子时，它将被绘制在同一个“块”中——因为所有这些祖先都可以在它之前绘制而不改变颜色。

加速

为了减少计算量，请注意，当某个特定颜色的所有可绘制框都没有不同颜色的后代时，绘制该颜色不会为其他框打开任何可绘制的新机会，因此我们不需要考虑这一点在考虑下一步要画哪种颜色时，我们总是可以把它留到以后，而不会有增加成本的风险。事实上，最好把这种颜色留到以后再画，因为到那时其他这种颜色的盒子可能已经可以上漆了。调用颜色有帮助如果至少有一个该颜色的可绘制盒子具有不同颜色的后代。当我们到达没有剩余有用颜色的地步（即当所有剩余的盒子只重叠相同颜色的盒子，或者根本没有盒子）时，我们就完成了：只需绘制每种剩余颜色的盒子，在任何订单。

算法

这些观察结果提出了两种可能的算法：

  1. 一种快速但可能不是最优的贪心算法：选择下一个产生最新可绘制顶点的颜色绘制。（这将自动只考虑有用的颜色。）

  2. 一种较慢、精确的 DP 或递归算法：对于每种可能的有用颜色 c，请考虑通过绘制所有可绘制的 c 色框生成的依赖图：

    令 f(g) 为在依赖图 g 中绘制所有框所需的最小颜色变化次数。然后

    f(g) = 1 + min(f(p(c, g)))

    对于所有有用的颜色 c，其中 p(c, g) 是通过绘制颜色 c 的所有可绘制框产生的依赖图。如果 G 是原始问题的依赖图，则 f(G) 将是最小更改数。颜色选择本身可以通过向后追溯 DP 成本矩阵来重建。

    f(g) 可以被记忆来创建一个动态编程算法，当两种不同的颜色选择排列产生相同的图形时，该算法可以节省时间，这种情况经常发生。但可能即使在 DP 之后，该算法也可能需要一定数量的时间（以及空间），这与盒子的数量呈指数关系......我会考虑是否可以找到更好的界限。

于 2013-01-16T16:28:21.717 回答
2

这是一种可能性。你必须对它进行基准测试，看看它是否真的是一种改进。

For all rectangles, back to front:
  If this rectangle has been marked as drawn, skip to the next one
  Set a screen-sized unseen surface to all black
  Call this rectangle's color "the color"
  For rectangles starting with this one and proceeding toward the front
    If (this rectangle's color is the color and
        all the pixels of this rectangle on the unseen are black) then
      Add this rectangle to the to-draw list
    Draw a white rectangle with this rectangle's shape on the unseen surface
    If the unseen surface is more than half white, break
  For all rectangles on the to-draw list:
    Draw the rectangle
    Mark it as drawn

不能保证在排序方面是最佳的，但我认为它会非常接近，并且在预绘图步骤中它是最坏情况的二次方。它确实取决于图形缓冲区的回读速度是否很快。一个可能有帮助的技巧是创建一个新的像素表面，它是感兴趣区域的缩小版本。它的颜色将是原始白色的一部分。

于 2013-01-17T18:11:08.847 回答
2

首先以随机（但正确）的顺序绘制，例如严格的 z 顺序。绘制每一帧时，要么计算颜色变化的次数，要么计算一个完整帧所花费的实际时间。每一帧，尝试交换两个矩形的顺序。被交换的矩形不能重叠，因此可以按任意顺序绘制而不违反正确性；除此之外，它们可以随机选择，或者对列表进行线性传递，或者...下一帧。如果进行交换既不会减少也不会增加颜色变化的次数，保持 50% 的几率。对于在前一帧中没有重叠但由于移动而开始重叠的任何矩形，只需交换它们，使它们按 z 顺序排列。

这与交换项目对的排序算法有一些关系，除了我们无法比较项目外，我们需要遍历整个列表并计算颜色变化。这在开始时会表现得很糟糕，但会相对较快地收敛到一个好的顺序，并且会适应场景的变化。我认为每帧都计算一个最佳顺序可能不值得；这将获得并维持一个接近最佳的订单，只需很少的额外工作。

参考您拥有的图纸： 随机选择的初始抽奖顺序：1、6、2、4、5、8、3、7（5 种颜色变化）。交换 5,8。新订单：1,6,2,4,8,5,3,7（4 种颜色变化）=> 保持新订单。

于 2013-01-20T11:33:07.750 回答