3

简洁版本：

尽管值略有变化，但我正在寻找一种技术，以随着时间的推移将几乎排序的数据保持在几乎排序的顺序中。

这是场景：

在 3D 图形的世界中，在绘制之前从前到后对对象进行排序通常是有益的。随着您的场景发生变化或您对场景的看法发生变化，这些数据可能需要重新排序，但是它通常会非常接近排序顺序（即，它不会在帧之间发生太大变化）。数据是否完全按排序顺序也不重要。将发生的最糟糕的事情是多边形将被渲染然后完全隐藏。这是一个小的性能打击，但不是世界末日。

考虑到这一点，是否可以提前对数据进行一次排序，然后每帧对数据应用一次最小补丁以确保数据大部分保持排序？在这种情况下，如果大多数对象按升序排列，则认为数据大部分已排序。也就是说，距离正确位置 10 步的1 个对象比距离正确位置 1 步的 10 个对象要好得多（好 10 倍）。

还值得注意的是，数据可以继续半定期修补，因为数据通常每秒渲染 30 次（左右）。只要计算是有效的，它就可以随着时间的推移继续进行，直到更改停止并且列表完全排序。

现有理念：

我对这个问题的下意识反应是：

  1. n log n在加载数据时对数据进行排序，并对大的更改（我可以很容易地跟踪）进行排序。

  2. 当数据开始缓慢变化时（例如，当场景旋转时），对数据应用某种类型的单个（线性）传递以向后交换邻居并尝试保持排序顺序（我认为这基本上是 shell 排序 - 也许有用于单次通过的更好算法）。

  3. 继续对每一帧进行一次部分排序，直到更改停止并且数据完全排序

  4. 返回第 2 步并等待更多更改。

4

5 回答 5

5

如果输入大部分已排序，则有多种排序在 O(n) 时间内运行，如果数据未排序，则在 O(n log n) 时间内运行。听起来你可以很容易地使用它。Timsort 就是这样一种排序，我相信它现在是 python 和 java 中的默认排序。Smoothsort 是另一种很容易自己实现的方法。

于 2012-06-26T19:39:03.710 回答
3

根据您的描述，听起来排序顺序会发生变化，而无需您更改数据本身。例如，您更改了相机，因此排序顺序应该更改，即使您没有修改任何多边形。

如果是这样，您无法在发生排序顺序更改时直接检测到它们。如果可以的话，我会为多边形列表创建存储桶，并在该存储桶中的“足够”多边形被触及时使用存储桶。

但我敢打赌你的系统不会那样工作。排序由视口确定。在这种情况下，排序前面的多边形比最后的多边形重要得多。

所以我会将多边形列表分成五分之一或类似的东西。从前到后，所以前五分之一是最靠近相机的部分。我会对每一帧的第一段进行完全排序。我将第二段划分为子段 - 再次说 5 - 并在每一帧对每个子段进行排序，这样每 5 帧第二个第五个被完全排序。将第三到第五段分割成 15 个子段，每 5 帧执行一次，这样其余的每 75 帧就完全排序。在 60 fps 时，您将每秒完全使用一次以上的显示列表。

优先考虑列表前面的好处是 1. 前面的多边形在屏幕上往往会更大，并且会更频繁地通过深度测试。列表末尾的错误订单通常并不重要。2. 列表的前面更容易因相机变化而发生排序变化。

还选择了那些有一点重叠的段范围，以便多边形可以以两种方式迁移到正确的段。

@OP：再想一想。您可能更关心排序成本保持有限 - 而不是场景复杂性爆炸。特别是因为一个非常复杂的场景应该 - 令人惊讶的是 - 不太容易受到不良排序的影响（因为通常多边形会变小）。

您可以定义您愿意每帧执行的固定数量的排序。将预算的 50% 用于尽可能多的列表前面的区域，将预算的 25% 用于对下一个区域进行排序，将 25% 的预算用于其余区域。

假设您预算每帧排序 1000 个多边形，并且场景中有 10000 个多边形。每帧对前 500 个多边形进行排序。为下一个区域每十帧排序 250 个多边形。因此，第 1 帧为 501-750，第 2 帧为 751-1000，等等。然后将列表的其余部分划分为 250 个帧段，并根据您需要的帧数对它们进行循环排序。

这使排序成本保持不变，场景变得越来越复杂，并且很容易调整，您只需将排序预算调整到您能承受的范围内。

于 2012-06-26T18:43:58.730 回答
1

我将在这里提出一个借鉴其他许多人的解决方案。当然，我们从初始化时的完整对象开始。

我会做的是总是对每一帧的对象执行 10 次线性时间运行（如果你发现你的对象已经完全排序，则提前终止）。例如，每次运行都可以是一次冒泡排序，在整个数组上具有shell 排序式间隙：对于从 0 到 n-gap-1 的所有 i，比较 A[i] 和 A[i+gap]，并且如果它们没有排序，请交换它们。您可以使用固定的间隙序列，或者更好的是，让它在帧之间变化；无论哪种方式，如果您在对象不变的情况下制作了足够多的帧，那么您将拥有一个完全排序的序列。您甚至可以混合不同类型的子算法来运行，只要每次迭代都能提高“排序性”。

您可以添加 Rafael Baptista 的想法，即通过在前段多跑一次，或者选择将前半部分的间隙除以 2，或类似的方式，轻松地优先考虑场景的前部。

于 2012-06-26T23:08:54.563 回答
0

它并没有像您想象的那样巧妙地解决问题，因为您所要做的就是将相机旋转 90 度，并且排序的基础完全在不同的轴上。（X和Y轴是独立的，例如——向下看X轴会导致排序顺序不依赖X轴，向下看Y轴会导致排序顺序不依赖Y轴。）即使是 5 度的转弯也可能导致远处的“关闭”（就 Z 顺序而言）事物突然“远离”。

老实说 - 为对象生成绘制调用通常比对它们进行排序要花费更多的时间，特别是如果您有针对您的场景优化的排序算法并且您的游戏具有现代视觉复杂性。

排序实际上可以是 O(n)，尤其是对于基于直方图的算法或基数风格的算法。（是的，基数排序适用于整数，所以你必须将你的世界坐标缩放为整数，但通常这已经足够了，除非你有一个巨大的世界。）

话虽这么说，由于您已经对绘制的所有内容进行了 O(n) 操作，因此每帧都不会成为一个大问题，尤其是在高级和低级优化的情况下。

解决此问题的另一种常见方法是使用场景图，但出于您的目的，它最终基本上是每帧重新排序。但是，您可以将平截头体剔除、阴影剔除和细节级别计算构建到场景图遍历中。

如果您正在寻找近似值，而不是进行 z 距离排序，请执行真正的距离排序并更频繁地更新排序顺序以用于靠近的对象，而不是更频繁地用于更远的对象（取决于相机行进的距离）。这可以起作用，因为如果您离对象较远，移动不会导致观察者的角度经常改变，这反过来意味着旧的排序数据更有可能是有效的。我不喜欢这个，因为我喜欢允许我的游戏在地图上传送而没有任何问题的算法。（请注意，从磁盘流式传输资产成为传送的真正问题。）

于 2012-06-26T19:28:56.417 回答
0

Shell 排序适用于唯一值很少的列表和一些“需要短代码且不使用调用堆栈”的场景。

在您的情况下，您需要一种称为Adaptive sort的东西，这意味着算法“利用其输入中的现有顺序”。

如果你的空间很紧，你可以只使用直插排序，它是自适应的和就地的。

否则，您可以按照@RunningWild 的建议尝试 Timsort 和 Smoothsort，它们都是自适应排序算法。

于 2012-06-26T20:12:28.850 回答