云风的 BLOG

在 粒子系统的设计 中，提到我们的管理器按 ECS 结构设计，管理器管理的是属性间的关联而非数据，这给材质属性的容器实现提供了极大的弹性。

如果单个粒子管理器同时呈现的最多的材质数量非常少，比如 8 个，那么最直接简单的方法是给每种材质一个单独的属性，用 tag M0 排到 M7 即可。这样，我们只要用管理器的 api 直接筛选对应的 tag 就可以得到每种材质的对象集合。

但如果材质种类很多，我觉得独立 tag 的方式就不合适了。

我首先想到的是可不可以单独设计一个材质容器的数据结构。对管理器来说，容器只需要支持向里面添加新数据、重新排列数据两个接口，具体容器是什么无所谓。对渲染来说，最重要的是可以快速遍历出同一材质下的所有对象。

比较直接的方法是用 id 来表示材质，为每个材质 id 都建立一个数组。如果不考虑对象删除，又因为粒子的材质一旦创建也不会修改，所以向容器添加一个新对象，就是根据添加的对象的材质 id 分别添加到对应的数组中。这样，渲染的时候，就可以简单的遍历对应材质的数组了。

对象删除是一个难题。因为上面的数据结构中，没有建立对象和材质的反向映射关系。所以这是一个 O(n) 的操作：需要遍历所有的材质数组，找到要删除的对象在那个数组中，才可以删除。

但好在渲染本身就需要遍历所有材质的所有对象，我们可以把两件事情一起做。管理器在删除对象的时候是靠一个 remap 表来通知容器重组内部数据的，比如 remap （7 : 1) 表示把 7 号移到 1 号，并将 1 号删除。我们可以暂时把 remap 信息记录在一个映射表中，在渲染遍历的时候对每一项多做一个查表操作，判断是否已经被删除或移动了编号（从 7 号材质变成了 1 号材质）。

但我在实现的时候，发现代码写起来非常的麻烦。写了一个小时之后，我停下来思考是否有更简单的做法。

我重新考虑更直接的数据结构：让材质属性就是一个 id 。在渲染阶段，只需要对这个材质属性数组做一个排序就够了。排完序后的材质属性，相同的材质自然就连在一起。

一开始我没有优先考虑这个数据结构的原因是，排序是 O(N * log N) 的，最坏可能到 O(N*N) 。而按上面的方法，渲染则是 O(N) 的（遍历完所有材质属性就够了）。

那么有没有方法用 O(N) 的时间复杂度完成材质的分类呢？

我认为只要加上一点合理的限制就可以了。比如限制同时使用的材质不超过 255 个。那么我们就可以获得两点好处：1. 用一个字节就可以储存材质 id 。2. 可以用桶排序。

因为我们的管理器中管理的是材质属性在容器中的序号，而且管理器能保证序号是连续的（删除对象会重排序号）。所以，我们可以在渲染环节，在栈上建立一个临时的一个序号数组；而材质上限是 255 个的话，建立一个 [255] 的桶数组即可。

// particle_id  is uint16_t if MAX_PARTICLE less than 64K
struct material_context {
  particle_id index[MAX_PARTICLE];
  particle_id head[MAX_MATERIAL];
};

一开始，只需要把 head[] 初始化为空（此处为 INV , INVALID_PARICLE），而 index[] 不需要初始化。

如果有 10 个粒子对象，假设它们的材质 id 为 0 1 0 1 0 1 0 1 0 1 0 。也就是奇数项是 0 号材质，偶数项是 1 号材质。我们遍历这个数组一次，就可以完成分类。

head[] 保存的链表的头索引，此处，head[0] 为 9 head[1] 为 8 ，即最后添加进去的项；index 中每一项都是同材质链表上的 next 索引。此处为 { INV, INV, 0, 1, 2, 3, 4, 5, 6, 7 } 。

这个数据结构中保存了两条链表：9 - 7 - 5 - 3 - 1 - INV 和 8 - 6 - 4 - 2 - 0 - INV 。

遍历这个链表也很容易：

static inline particle_id
material_begin(struct material_context *ctx, material_id matid) {
   return ctx->head[matid];
}

static inline particle_id
material_next(struct material_context *ctx, particle_id prev) {
  return ctx->index[prev];
}

for (particle_id i = material_begin(ctx, matid); i != INVALID_PARICLE; i = material_next(ctx, i) {
   ...
}

进一步，我们可以在整理后，记录下每个材质的对象个数，如果为零，就可以重新调整一下，把材质属性数组中最大的材质 id 映射成已经没有人使用的 id 。把 id 空出来供新材质使用。

我们引擎外层是用 lua 封装的，所以，所有的材质可以放在 lua 表中，用更长的 key （例如材质名）索引，不向应用层暴露内部的材质 id 。在 C 层上，则 cache 住最多 255 个材质对象以供渲染 api 直接取用。

这里保留一个材质 id 作为空材质。万一同时存在的材质超过了 255 个，就设置为空材质，渲染阶段直接跳过。