一、背景
现代引擎需要对海量的透明和不透明物体进行排序，目的是决定绘制顺序。
不同的引擎采用不同的排序方式，不同的方式的排序速度有着显著的差异。
unreal engine和cocos均采用比较器排序。
除此之外，两个引擎均没采用速度更快的基数排序，可能跟基数排序本身的局限性有关。
二、比较器排序 vs 基数排序
下面以简单的数组排序说明比较器排序和基数排序的区别。
2.1 比较器排序
下面以简单数组举例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 初始: [173] [045] [089] [012] [045] [250] [173] [001]
A B C D E F G H
比较 B(045) vs A(173) → 回调1次 → 045<173 → B 挪到最前
[045] [173] [089] [012] [045] [250] [173] [001]
B A C D E F G H
比较 C(089) vs A(173) → 回调2次 → 089<173
再比 C(089) vs B(045) → 回调3次 → 089>045 → C 插中间
[045] [089] [173] [012] [045] [250] [173] [001]
B C A D E F G H
比较 D(012) → 连比 A、C、B 三次 → D 到最前
[012] [045] [089] [173] [045] [250] [173] [001]
D B C A E F G H
…… 每个新元素都要来回比、来回挪
|
当然比较器排序的算法有很多，上面是比较简单的一种，帮助理解。
2.2 基数排序
两个数组：元素数组原地不动，另建一个整数键数组，整数在键数组里按「位」搬运。
初始状态
1
2
3
| 键数组: [173] [045] [089] [012] [045] [250] [173] [001]
元素: A B C D E F G H
桶: 桶0[] 桶1[] 桶2[] 桶3[] 桶4[] 桶5[] 桶6[] 桶7[] 桶8[] 桶9[]
|
第 1 轮：按「个位」散桶 → 收集
看每个数的个位（173 的个位是 3）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 散桶:
桶0 [250] ← F 个位=0
桶1 [001] ← H 个位=1
桶2 [012] ← D 个位=2
桶3 [173] [173] ← A、G 个位=3 (A 先进桶，保持在 G 前)
桶4 []
桶5 [045] [045] ← B、E 个位=5 (B 先进桶，保持在 E 前)
桶6 []
桶7 []
桶8 []
桶9 [089] ← C 个位=9
收集(桶0→桶9 依次倒出):
键数组: [250] [001] [012] [173] [173] [045] [045] [089]
F H D A G B E C
|
第 2 轮：按「十位」散桶 → 收集
在上一轮收集结果上，看十位（250 的十位是 5）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 散桶:
桶0 [001] ← H 十位=0
桶1 [012] ← D 十位=1
桶2 []
桶3 []
桶4 [045] [045] ← B、E 十位=4
桶5 [250] ← F 十位=5
桶6 []
桶7 [173] [173] ← A、G 十位=7
桶8 [089] ← C 十位=8
桶9 []
收集:
键数组: [001] [012] [045] [045] [250] [173] [173] [089]
H D B E F A G C
|
第 3 轮：按「百位」散桶 → 收集
1
2
3
4
5
6
7
8
9
| 散桶:
桶0 [001] [012] [045] [045] [089] ← H、D、B、E、C 百位=0
桶1 [173] [173] ← A、G 百位=1
桶2 [250] ← F 百位=2
桶3 ~ 桶9 []
收集:
键数组: [001] [012] [045] [045] [089] [173] [173] [250] ← 排好了
H D B E C A G F
|
2.3 对比
|
比较器排序 |
基数排序 |
| 比较/回调次数 |
O(n log n)（每次都是函数回调） |
0 |
| 搬运的是什么 |
元素对象在原数组来回交换 |
整数在键/桶数组按位搬 |
| 总代价 |
O(n log n) × 回调开销 |
O(d·n)，纯整数，常数小 |
| 额外内存 |
0（原地） |
键数组 + 计数桶 + 临时数组 |
且基数排序在近有序和完全有序的情况下，效率反而不如比较器排序，这也可能也是cocos和unreal engine不采纳这种方式的原因。
1
2
3
| 完全有序: [1, 2, 3, 4, 5, 6, 7, 8] ← 一个都不用动
近有序: [1, 2, 8, 4, 5, 6, 7, 3] ← 8 和 3 错位，其余都对了
乱序: [8, 3, 6, 1, 5, 7, 2, 4] ← 全乱
|
三、cocos vs unreal
cocos引擎不透明队列要依次对比hash（可以理解成材质数量）、depth、shaderId三项。透明队列要对比hash、priority、depth、shaderId四项。
1
2
3
4
5
6
7
| export function opaqueCompareFn (a: IRenderPass, b: IRenderPass): number {
return (a.hash - b.hash) || (a.depth - b.depth) || (a.shaderId - b.shaderId);
}
export function transparentCompareFn (a: IRenderPass, b: IRenderPass): number {
return (a.priority - b.priority) || (a.hash - b.hash) || (b.depth - a.depth) || (a.shaderId - b.shaderId);
}
|
unreal 把多个排序字段打包进一个 64 位整数，每次元素比较只需要比较这个整数；排序总比较次数仍是 O(n log n)，但单次比较成本很低，且 C++ 侧可内联。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class FMeshDrawCommandSortKey {
union {
uint64 PackedData;
struct {
uint64 VertexShaderHash : 16;
uint64 PixelShaderHash : 32;
uint64 Background : 1;
uint64 Masked : 15;
} BasePass;
struct {
uint64 MeshIdInPrimitive : 16;
uint64 Distance : 32;
uint64 Priority : 16;
} Translucent;
struct {
uint64 VertexShaderHash : 32;
uint64 PixelShaderHash : 32;
} Generic;
};
FORCEINLINE bool operator<(FMeshDrawCommandSortKey B) const { return PackedData < B.PackedData; }
FORCEINLINE bool operator!=(FMeshDrawCommandSortKey B) const { return PackedData != B.PackedData; }
};
|