使用alpha混合和z缓冲区来处理二维四边形的列表

我使用深度缓冲区作为我的二维渲染分层系统,我必须从后到前绘制他们,使半透明四边形工作。 问题是我必须根据他们的深度来分类我的四边形vector,每当我添加或删除一个,这是非常耗时的。 我之前做过这个,但是我不确定是什么原因,因为在我看来,如果我按照5000个四元组的顺序排列一个向量,那么如果删除其中的一个,其他4999个项目在一个框架。

我需要知道是否有替代方法,或者这只是它。

当数组已经大部分sorting(在下一帧重用)时,智能泡泡/插入sorting比快速sorting要快。

为了加速数据的复制而不是复制整个顶点值,可以使用索引缓冲区对顶点进行sorting。

当你删除四边形,你可以快速退化它们(设置所有的顶点为相同的值),而不是删除它们,并复制下面的四边形。

然后,您可以逐渐将其压缩到多个框架上,或者仅在需要时将其压缩。 插入带有这种孔的“瑞士奶酪”顶点arrays,可以将数据只移动到第一个孔,然后停止,而不是移动整个arrays。

克罗姆·斯特恩(Krom Stern)使用链接向量(一个较短的数组列表)的答案是非常好的,因为你可以将这个技巧调整到[绘制调用次数]和[单个缓冲区的sorting时间]之间的一个最佳位置,总是把额外的一点空闲每个缓冲区中的空间。

而为了更冒险:

如果插入速度非常重要,可以将正浮点数的前1 N位作为整数使用,将符号位跳转到链表中。

相同符号的IEEE浮点可以作为整数进行比较和sorting,这是其标准devise的一部分。 它们是一种补充而不是二者的补充,但是如果我们只使用正z,这并不重要。 如果我们既需要正负z,那么负z也需要一组反向分类函数。

 #define NBITS 10 // 1024 entries SortList *lists[1 << NBITS] = {0}; ... float z = object->z; if(z <= 0){ // IMPORTANT this includes negative zero which is distinct from positive zero z = 0; // negative float number are in reverse when interpreted as integers, this would need a set of reverse functions } uint32_t raw_z_bits = ((uint32_t &)z); uint32_t list_number = (raw_z_bits >> (31 - NBITS)); // 31 because we skip the sign bit uint32_t index_within_list = raw_z_bits & ((1 << (31 - NBITS))-1); AddToList(lists[list_number], index_within_list, object ); 

当您不知道需要sorting和/或已经使用浮点深度值的范围时,这非常有用。

如果使用整数深度值,则浮点黑客将限制深度值(0到+ 8M)的23位,因为32位浮点数只有23位(+ 1位符号)的精度(8位用于指数)。

所有这些变得很复杂,所以debugging的一个好主意是使用每帧sorting全部活动对象和validationfunction来进行独立的完整性检查,这将确认所有的事情都被正确地sorting,并且没有错误更快,逐步分拣系统。

你可以使用不同的方法来清单。

链接列表。 每个项目都有一个指向列表中下一个项目的指针。 插入和移除成本是O(1)。 这不是caching友好,但你可以尝试。

更好的sorting方法,例如,如果你使用泡沫sorting,你可以select一个更好的algorithm,更适合你的情况(单插入/删除不需要整个列表)。

你可以结合和存储你的对象链接向量,其中每个向量是例如32项,并链接到一个列表。 当vector变得太大时 – 将其分开。 当太小 – 合并到邻居。

您还可以查看空间分区(四叉树)。