优化重叠矩形的绘制
我有大量的矩形，有些与其他的重叠; 每个矩形都有一个绝对的z次序和一个颜色 。 （每个“矩形”实际上是粒子效果，网格或纹理的轴alignment的边界框，并且可能是半透明的，但只要不尝试挑选其他矩形，就更容易抽象地思考彩色矩形，所以我会用在问题描述:)
改变“颜色”的成本相当高; 其绘制两个蓝色矩形比绘制两个不同颜色的矩形要快得多。
甚至不在屏幕上绘制矩形的成本也相当高，应该避免。
如果两个矩形不重叠，它们相对于彼此的顺序并不重要。 只有它们重叠时，z顺序才是重要的。
例如：
1（红色）和4（红色）可以一起绘制。 2（蓝色）和5（蓝色）也可以绘制在一起，如3（绿色）和7（绿色）。 但是8（红色）必须在6（蓝色）之后绘制。 所以要么我们把所有的三个红色画在一起，画两个蓝色，要么把所有的蓝色画在一起，画两个红色。
而且有些矩形可能会偶尔移动。 （不是所有的人都知道，有些矩形是静止的，有些则是已知的。）
我将在JavaScript / webGL中绘制这个场景。
我怎样才能以合理的顺序绘制矩形， 以最大限度地减less颜色变化 ，与JavaScript剔除代码的良好折衷与让GPU剔除？
（只是算出哪些矩形重叠，哪些是可见的，是昂贵的，我有一个基本的四叉树 ，这很快就绘制了我的场景（相比之下，只是发射整个场景的绘制操作）;现在的问题是如何最小化OpenGL状态更改并尽可能地连接属性数组）
更新我创build了一个非常简单的testing应用程序来说明问题，并作为解决scheme演示的基础： http : //williame.github.com/opt_rects/
源代码在github上，很容易分叉： https ： //github.com/williame/opt_rects
事实certificate，很难做出一个足够的状态变化的小testing应用程序来真正重现我在整场游戏中看到的问题。 在某些时候，你必须把它看作是一种状态变化足够昂贵的情况。 同样重要的是如何加快空间索引（演示中的四叉树）和整体方法。
你在做一个错误的假设，你在桌面浏览器上获得的性能会以某种方式决定你iPhone上的性能。 您需要了解iPhone硬件实现基于磁贴的延迟渲染 ，这意味着片段着色器在stream水线中使用得非常晚。 正如苹果自己所说的那样（“ 不要浪费CPU时间从前到后sorting对象 ”），Zsorting你的原语将使你的性能得到一点提升。
但是我的build议是：如果改变颜色是昂贵的， 只是不要改变颜色 ：把它作为一个顶点属性，并把行为合并成一个超级着色器，这样你就可以在一个或几个批次中绘制所有东西，而不需要sorting。 然后基准和确定您的平台的最佳批量大小。
select颜色，而不是盒子！
在任何时候，一个或多个盒子都是可涂漆的 ，也就是说，他们可以在接下来不会出现问题的情况下进行涂漆（尽pipe可能由于与最近涂漆的盒子具有不同的颜色而引入成本）。
每一个问题的问题是：我们应该select什么颜色来绘制下一个？ 没有必要考虑挑选单独的可绘制的盒子，因为只要你select一个特定的盒子来绘制下一个盒子，就可以绘制当时可以绘制的相同颜色的所有盒子。 这是因为画一个盒子从来不会增加对问题的限制，而只是去除它们。 如果不改变当前的颜色，select不涂色可上漆的盒子不能使解决scheme的成本降低，因为之后你必须画上这个盒子，而这可能需要换色。 这也意味着我们以同样的颜色绘制可绘制的盒子的顺序并不重要，因为我们将在盒子绘画操作的一个“块”中一次绘制所有这些。
依赖关系图
首先build立一个“谎言之下”的依赖关系图，其中每个彩色矩形由一个顶点表示，如果矩形v与矩形u重叠并且位于其下面，则从v到u有一个弧（箭头）。 我的第一个想法是通过查找传递闭包来构build“必须在之前绘制”依赖关系图，但实际上我们不需要这样做，因为下面所有的algorithm都关心的是顶点是否可绘制。 可绘制顶点是没有前置（顶点）的顶点，并且传递闭包不会改变顶点是否有0个入弧。
另外，每当一个给定颜色的盒子只有与其祖先相同颜色的盒子时，它将被绘制在相同的“块”中 – 因为所有这些祖先都可以在不改变颜色的情况下在其之前被绘制。
加速
为了减less计算量，请注意，每当某些特定颜色的所有可绘制的盒子都没有不同颜色的后代时，绘制这种颜色不会为其他盒子创造任何新的机会，因此我们不需要考虑这个考虑下一种颜色的颜色 – 我们可以随时留下，不用担心增加成本。 事实上， 最好留下这种颜色，直到后来，因为那个时候这种颜色的其他盒子可能已经变成可涂漆了。 如果至less有一个具有不同颜色后裔的颜色的可绘制框，请调用一种颜色。 当我们到达没有有用的颜色剩余的时候（即，当所有剩余的盒子只重叠相同颜色的盒子，或者根本没有盒子时），那么我们完成了：只绘制每个剩余颜色的盒子，挑选颜色任何订单。
algorithm
这些观察提示了两种可能的algorithm
- 一个快速但可能不是最佳的贪婪algorithm：select绘制产生最新的可绘制顶点的颜色。 （这将自动考虑只有有用的颜色。）
-
一个更慢，更准确的DP或recursionalgorithm：对于每个可能有用的颜色c，考虑通过绘制所有可绘制的c颜色框产生的依赖关系图：
设f（g）是绘制依赖图g中所有框所需的颜色变化的最小数量。 然后
f（g）= 1 + min（f（p（c，g）））
对于所有有用的颜色c，其中p（c，g）是通过绘制颜色c的所有可绘制框产生的依赖关系图。 如果G是原始问题的依赖关系图，那么f（G）将是最小变化次数。 颜色select本身可以通过向后追溯DP成本matrix来重build。
可以记忆 f（g）以创builddynamic编程algorithm，该algorithm在任何颜色select的两个不同排列产生相同的graphics时将节省时间，这将经常发生。 但可能是，即使在DP之后，这个algorithm也会花费一定的时间（因此空间），这个时间在盒子的数量上是指数级的。我会考虑是否可以find一个更好的边界。
这是一个可能性。 你必须对它进行基准testing，看看它是否有改进。
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
不能保证在sorting上是最优的，但是我认为它会非常接近，在预绘步骤中是最差的二次方。 它取决于graphics缓冲区的回读速度。 一个可能会有所帮助的技巧是创build一个新的像素表面，这个表面是感兴趣区域的缩小版本。 它的颜色将是原来的白色部分。
以随机（但是正确）的顺序开始，例如按严格的顺序。 在绘制每一帧时，要么计算颜色变化的次数，要么计算完整帧的实际时间。 每一帧，尝试交换两个矩形的顺序。 要交换的矩形不得重叠，因此可以按任意顺序绘制而不违反正确性。 除此之外，可以随机select，或者通过列表进行线性传递，或者…如果进行交换减less了颜色变化的次数，则保持新的顺序，如果没有恢复它，并尝试在下一帧。 如果交换既不减less也不增加颜色变化的数量，保持50％的几率。 对于在前一帧中没有重叠但由于移动而开始重叠的任何矩形，只需交换它们，以便它们按z顺序排列。
这与交换对项目的sortingalgorithm有一些关系，除了我们不能比较项目，我们需要通过整个列表并计算颜色变化。 起初performance非常糟糕，但相对较快地衔接到一个良好的秩序，并将适应现场的变化。 我觉得这可能是不值得的，每一帧都要计算一个最佳的顺序。 这将得到并保持一个几乎没有额外工作的接近最优的订单。
参照您的图纸：初始绘制顺序随机挑选：1,6,2,4,5,8,3,7（5种颜色变化）。 交换5,8。 新订单：1,6,2,4,8,5,3,7（4种颜色变化）=>保持新订单。
