优化重叠矩形的绘制
Wil*_*ill 43 javascript algorithm math webgl spatial-index
我有大量的矩形,有些与其他矩形重叠; 每个矩形具有绝对的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
事实证明很难做出一个具有足够状态变化的小测试应用程序来实际重现我在完整游戏中看到的问题.在某些时候,你必须把它当作一个给定的状态变化可能足够昂贵.同样重要的是如何加速空间索引(演示中的四叉树)和整体方法.
sam*_*var 16
您正在做出错误的假设,即您将在桌面浏览器上获得的性能将以某种方式决定iPhone的性能.您需要了解iPhone硬件实现基于图块的延迟渲染,这意味着片段着色器无论如何都会在管道中使用很晚.正如Apple自己所说的那样(" 不要浪费CPU时间从前到后排序对象 "),对原语进行Z排序将使您获得很少的性能提升.
但这是我的建议:如果改变颜色很昂贵,就不要改变颜色:将它作为顶点属性传递,并将行为合并到一个超级着色器中,这样你就可以在一个或几个批次中绘制所有内容而不进行排序.然后基准测试并确定适合您平台的最佳批量大小.
- @Will你需要提供更多关于你想做什么的信息,因为使用一个大的`if()`来合并几个着色器肯定是微不足道的.如果"颜色"的概念延伸到渲染状态,则它根本不是同一个问题,特别是如果涉及alpha混合. (2认同)
- @Will是的,这是需要解决的全部新问题和妥协:-)但是根据您提供的信息,您只能获得改进的一般策略,而不是全功能的解决方案. (2认同)
j_r*_*ker 12
选择颜色,而不是盒子!
在任何时间点,一个或多个盒子都是可涂漆的,即它们能够在不引入问题的情况下进行涂漆(尽管由于与最近涂漆的盒子具有不同的颜色而可能引入成本).
每个方面的问题是:我们接下来要选择什么颜色？没有必要考虑选择绘制单个可绘制的盒子,因为只要你选择一个特定的盒子来绘制下一个,你也可以绘制当时可以绘制的相同颜色的所有可用盒子.那是因为画一个盒子永远不会增加问题的约束,它只会删除它们; 并且如果不改变当前的颜色而选择不绘制可涂漆的盒子,则无法使解决方案比原本更便宜,因为您以后必须对此盒子进行涂漆,这可能需要更换颜色.这也意味着我们绘制相同颜色的可涂漆盒子的顺序并不重要,因为我们将在一个"块"的盒子涂装操作中一次性地绘制所有这些盒子.
依赖图
首先构建一个"位于下面"的依赖图,其中每个彩色矩形由顶点表示,如果矩形v与矩形u重叠并位于其下方,则从v到u有一个弧(箭头).我的第一个想法是通过查找传递闭包来使用它来构建"必须绘制之前"依赖图,但实际上我们不需要这样做,因为下面关注的所有算法都是顶点是否可绘制.可绘制顶点是没有前驱(弧内)的顶点,并且采用传递闭包不会改变顶点是否具有0个圆弧.
此外,每当给定颜色的盒子只有与其祖先颜色相同的盒子时,它将被涂在同一个"块"中 - 因为所有这些祖先都可以在它之前被涂上而不改变颜色.
加速
要减少计算量,请注意,每当所有特定颜色的可涂漆盒子都没有不同颜色的后代时,涂上这种颜色不会为其他盒子开辟任何新的机会变得可以涂抹,所以我们不需要考虑这个在考虑接下来要涂漆的颜色时的颜色 - 我们总是可以将它留到以后,没有增加成本的风险.事实上,最好将这种颜色留下来,直到后来,因为到那时,这种颜色的其他盒子可能已经变得可以涂漆了.呼叫色有帮助,如果有这种颜色具有不同颜色的后裔中的至少一个上漆框.当我们到达没有有用颜色的时候(即当所有剩余的盒子只重叠相同颜色的盒子,或根本没有盒子)时,我们就完成了:只需绘制每个剩余颜色的盒子,选择颜色任何订单.
算法
这些观察提出了两种可能的算法
- 快速但可能不是最理想的贪婪算法:选择接下来绘制产生最新可绘制顶点的颜色.(这将自动考虑仅有用的颜色.)
一个较慢,精确的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)可以被记忆以创建动态编程算法,每当2种颜色选择的不同排列产生相同的图形时,这将节省时间,这将经常发生.但也许甚至在DP之后,这个算法可能需要花费一定时间(因此空间)在盒子数量上呈指数...我将考虑是否可以找到更好的界限.
- 似乎我的评论因冒犯而被删除.让我再试一次:"@Will:我的华夫饼干？回答你的问题,不,我不会为你提供演示代码.看看你能不能找出原因." (4认同)
- @ilmiacs:在我看来,几乎任何提供一些算法优化的方法都需要构建该图.但是无论你是否将它存储在特定的数据结构中,你都需要在任何情况下完成这项工作,因此创建图形不应该为任何必须理解哪些框彼此重叠的方法增加很多开销.但我同意这里的递归算法对于合理大小的数据集来说几乎肯定太贵了. (2认同)