« October 2020 | Main

November 27, 2020

粒子管理器的 C++ 封装

这篇接着上一篇 粒子系统的设计

TL;DR 在花了一整个晚上用 C++ 完成了这一块的功能后,我陷入了自我怀疑中。到底花这么多精力做这么一小块功能有意义么?强调类型安全无非是为了减少与之关联的代码的缺陷,提高质量;但代码不那么浅显易懂却降低了质量。

我们用 C 实现了一个基于 ECS 结构的粒子系统的管理器,代码 psystem_manager.h 在这里

先来回顾一下设计:在这个粒子系统中,我期望把粒子对象的不同属性分开管理。

即:传统的面向对象的数据结构中,一个对象 particle 可以有很多属性 a,b,c 。通常是用一个结构体(或类)静态定义出来的,这些属性也可以看作是 a b c 组件,它们构成了粒子对象。而在 ECS 结构中,我们在每个时间点,并非去处理一个对象的多个属性,而是处理同一个属性的多个对象。所以,我们最好按属性分类将多个对象的同一属性聚合起来,而不是按对象,把同一对象的不同属性聚合在一起。

这是因为,在处理单个属性时,往往并不关心别的属性。比如,我们在递减生命期,处理生命期结束的对象时,关心的仅仅是生命期这个属性;在处理粒子受到的重力或其它力的影响时,我们只关心当前的加速度和速度;在计算粒子的空间位置时,只关心上一次的位置和瞬间速度;而在渲染时候,无论是生命期、加速度、速度,这些均不关心。

当数据按属性聚合,代码在批量处理数据时,连续内存对 cache 友好,即使属性只有一个字节,也不会因为对齐问题浪费内存。同一属性的数据尺寸完全相同,处理起来更简单。而且粒子对象相互不受影响,我们只是把同一个操作作用在很多组数据上,次序不敏感。非常适合并行处理。

更重要的是,不同类型的粒子需要自由的根据需要组合属性和行为。有的粒子有物理信息参与刚体碰撞运算,有的则只需要显示不需要这个信息;有的粒子有颜色信息,有的不需要有;有的粒子是一个面片,有的却是一个模型,拥有不同的材质。这导致粒子对象包含的信息量是不同的。及时拥有同一属性,作用在上面的行为也可能不同:例如同样是物理形状信息,可能用于刚体碰撞,改变运动轨迹,也可能只是为了触发一下碰撞事件。

在传统的面向对象的方式中,常用多态(C++ 的虚函数)来实现,或者有大量的 if else switch case 。

如果能按组件和行为聚合,那么就能减少大量的分支。每个粒子的功能组合(打开某个特性关闭某个特性)也方便在运行时决定,而不用生成大量的静态类。

但换种方式组织数据也有难点:原本用偏移量和直接的指针聚合在一起的单一对象,被打破分散在了多个数据块中。同一个对象的不同部分建立联系会比较麻烦。这种需求会出现在两个场合:

  1. 对象删除时,需要找到所有的组件删除。
  2. 多个组件有关联处理时,需要从一个组件 A 找到同一个粒子上的组件 B 。

最简单粗暴的方法是还是建一个空的根对象,让它对所有的组件都保留一个指针;然后没有组件都保留一个对这个空对象的指针。在组件比较零碎时,这些相互引用的指针会造成大量的内存占用,甚至超过组件本身的数据尺寸。

我之前写的管理器模块就是实现这样的数据结构,并尽可能的减少额外内存的使用,同时、同一粒子间的的组件相互引用能保持 O(1) 的访问时间。为了让这个管理器的功能内聚,在设计的时候,我考虑了几点:

  1. 管理器只管理关系,不管理数据内存,内存在外部由别的模块负责。
  2. 外部数据被视为可用连续内存块管理,不需要外部记录任何形式的引用值(指针或 id 的形式都不需要)。
  3. 不强制要求外部数据在连续内存块上,由外部自己决定如何储存。
  4. 外部数据推荐用 POD 结构,但不强制。
  5. 可以在迭代的过程中删除对象,不破坏迭代过程。让删除仅仅是做标记,基于粒子系统的特点,即使是刚被删除的对象中的组件,在其上做处理也是无害的。
  6. 整理被删除对象放在统一的地方一次处理,在保持外部内存块连续的基础上,做最少的数据移动。外部数据移动的过程不用 callback 的形式驱动。

我在用 C 语言实现完管理器后,写了一个简单的使用案例 (见 test.c )。同事理解了思路后,接手来做其它部分。他倾向于用 C++ 来完成后面的编写,理由是需要类型安全。

我个人虽然不太喜欢用 C++ 做设计,不过我的工作原则是,在保证模块划分清晰,接口明确的前提下,具体实现尊重实现者的意愿。爱用什么写就用什么写。

做后续的工作的起点,是需要做一个外部的数据容器集,可以存放不同的组件(属性)数据。也就是说,有若干的组件数组,每个放一个特定类型的组件,单个数组里有整个系统内拥有这个属性的所有粒子对象的该组件。

看起来会是这样的:

struct particle_manager *manager;
arrayType1 t1;
arrayType2 t1;
arrayType3 t3;
arrayType4 t4;
...

这就保存了整个粒子系统中的所有数据,而关联关系的数据在之前实现的 particle_manager 结构中。加起来就是全部。

显然,把 Type1 到 TypeN 的 array (实际用 std::vector 实现) 这么平坦的放在这里,会造成大量的重复代码。因为外部要处理 manager 模块的 arrange remap 信息(在删除对象后数据重排列)时,处理代码并不关心具体类型。所以很自然的,数据结构就演变为:

attribute * attribs[MAXCOMPONENTS];
struct particle_manager *manager;

给这些不同类型的数据容器加上一个基类 attribute ,保存一个基类指针的数据就够了。这样方便处理。

我们在实现这个系统(给关联关系的管理器增加实际数据的管理)时,需求有三:

  1. 添加一个由若干组件构成的粒子:需要分别给不同的属性容器追加数据,然后告诉管理器增加一个粒子。
  2. 删除任何一个组件时,同时删除和这个组件关联的组件(同一粒子对象)。管理器会报告数据块如何重新排列,接下来需要按这个信息重组数据块。
  3. 迭代特定的组件数组。依次取出数组中的每个组件数据。

对于需求 3 ,由于实际上我们就是用平坦内存(std::vector)储存的,迭代本身是非常廉价的。但是以上结构直接使用是类型不安全的。C++ 通过模板技术可以实现类型安全并不增加额外的成本。这是实现者选用 C++ 封装的动机。

我们可以提供这样一个 api :

vector<类型>& particle_system::attrib<类型>();

使用者正确的填写了组件的类型,就能返回对应的容器引用。它干的事情其实只是通过类型 ID 找到 attribs[] 中对应的那个 attrib * ,取出里面的引用。这个功能非常简单,C++ 带来的好处就是强类型避免犯错。如果类型没有写对,不能通过编译,而不是发生运行时错误(如果是 C 接口,恐怕就是使用类型 ID 而不是类型本身,也只能报告运行时错误)。

另外,还有一些衍生的需求。属性数据类型可以被分为三类:

  1. POD 的数据结构。
  2. 原生数据类型(例如 float int 这些)或其它库提供的基础数据结构(例如 float3 matrix 等)。
  3. 复杂的接口(带虚表的对象)。

对于 3 ,希望用 raw 指针而不是智能指针(智能指针其实就是 2 )。这是因为依然希望最终在处理整块数据的数据,面对的是连续内存块上的有明确数据布局的数据。raw 指针会比智能指针对象更清晰。

但这给 C++ 封装带来了一点挑战。因为容器可以是 container<类型> 也可以是 container<类型*> 。再重排列的算法上也有一点差别:raw 指针需要更小心的处理。这会用到模板的偏特化来解决。

另外,还需要从一个组件找到关联的组件数据。我希望无论是容器里是值对象还是 raw 指针,接口全部返回组件的指针,并用 nullptr 表示没有关联的组件。不同的数据储存形式也加大了封装层的复杂度。

同事在实现的时候遇到了一些语言技术细节上的困难(毕竟我们并不常用 C++ 开发),我们一起讨论,这激起了我的一点兴趣。我这些年都没有实际用 C++ 创作过新代码(但一直有阅读和维护第三方 C++ 项目,并不算陌生),虽然我对 C++ 新标准不算熟悉,但还是勉强能写写。这次的需求本质上并不复杂,只是用 C++ 模板封装一个比较简单的功能(给粒子管理器在关系管理的基础上增加数据管理),并提供类型安全。我决定自己也试着实现一个版本。

我个人的预期是这样的:

  1. 少用不必要的复杂模式,能解决问题就够了。目的就是达到类型安全,在使用的时候不再写显式的类型转换。写错类型时,在编译器就能检查出来。
  2. 头文件只暴露最少的信息,不在头文件中暴露模板方法的实现,尽量不在头文件中引用标准库或及其库,避免编译时间的膨胀。
  3. 使用模板的目的是用模板去约束类型,并减少重复的信息,易于维护。不追求语法上的技巧。不强求用最好(最新)的方法。

最终我花了一整个晚上才实现出来。代码不算太多,功能代码 100 来行,再加上 100 来行的简单使用案例(和之前的 C 版本基本功能一致)。我编写 C++ 模板代码不太熟练,中间编译错误的反复修正耽误了不少时间。但是,还是有大比例的时间在思考怎么用模板工具去绕出我想要的功能:类型约束检查。

这里是我最终的版本

最后,我们可以用一个简单的 for 语言迭代特定的组件数组。

void
particle_system::update_life(float dt) {
    int index = 0;
    for (auto &life : attrib()) {
        printf("lifetime: %f\n", life);
        life -= dt;
        if (life <= 0) {
            printf("REMOVE %d\n", index);
            remove(index);
        }
        ++index;
    }
}

这段代码是迭代一个 float 的 life 数组,把其中每个 float 递减 deltaT 。如果 life 小于等于 0 ,就标记对象为删除。

其中迭代支持标准的 C++ 形式 for (auto &life : attrib<lifetime>()) ,除去类型转换处理,它本质上就是在遍历一个 float [] 。

标记对象为删除也只需要 remove<lifetime>(index) 此处的 index 为 life 组件在 lifetime 属性数组中的当前序号。


另一个使用案例见 particle_system::update_print 的实现。

void
particle_system::update_print() {
    int n = size(TAG_PRINT);
    for (int i = 0;i<n;i++) {
        const value *v = sibling<value>(TAG_PRINT, i);
        if (v) {
            printf("Value = %d ", v->value);
        }
        const object *obj = sibling<object *>(TAG_PRINT, i);
        if (obj) {
            printf("Object = %d ", obj->value());
        }
        printf("\tParticle %d\n", i);
    }
}

它用 TAG_PRINT 遍历所有的有这个 tag 的对象。因为这是个虚拟 tag 并没有对应的组件,所以在这里并没有对应的数组容器。我们用 size(TAG_PRINT) 取出个数,然后 for i = 0 .. n 即可。在迭代中,可用 sibling<类型> 取到关联的组件。


最后是添加粒子的 api :

add({
    push_back(lifetime(20)),
    push_back(value { 0, 1 }),
    push_back(new object(42)),
    TAG_PRINT,
});

这些 push_back 会根据类型把组件添加到正确的容器中。同时, add 会将信息组织起来向管理器注册新的粒子。此处还可以打上虚拟 tag ,比如 TAG_PRINT

但实际上,这种用法的实际用途有限。因为我们最终并不会使用 C++ 代码静态的创建固定的粒子。而是发射器根据预定义的数据结构去分步创建。


在我花了一晚上时间(前后改了三版)最终完成了现在的版本后,我陷入了深深的怀疑中。仅仅是为了增加更严格的类型约束而消耗很多的精力到底有什么意义。其实我并没有完成太多实际的功能。当然代码量不大,算不上臃肿,但精力的开销却是能直接感受到的。大比例的代码和时间都是在想办法(通过不那么直观的形式)告诉编译器,这里应该增加怎样的约束,而不是完成运行时的某个特性。

另外,还不断的需要和内聚度做斗争(为此我调整了几次代码)。我期望不要把过多实现细节暴露在外面(尽量少在头文件中暴露出内部细节)。而 C++ 在这方面提供的语言层面的帮助却比较少:如果想定义方法针对类中的数据做操作,就需要把方法定义在类声明中暴露在头文件里。模板的前置声明写起来也很繁琐。

即使抛开不太熟悉语言工具这个因素,我认为经验丰富其实也并不会减少太多精力去完成它。而代码质量却变得不那么显而易见。我只能说,现在的代码中冗余的信息并不算多,绝大对数代码行都在履行预设的任务。没有太多的信息重复。但是,到底够不够简单易维护却是很难判断的。至少一眼看上去这百来行代码并不是特别容易理解。这是违背我的美学的。可能应归结到我的能力和经验欠缺上,C++ 代码暂时写不出更好。

但更好(简单易理解)的门槛是不是有点高?

November 19, 2020

粒子系统的设计

这几天在重构引擎中的粒子系统。之前用 lua 做了个原型,这次用 C/C++ 重新实现一次。目前还是基于 CPU 的粒子系统,今后有必要再实现基于 GPU 的版本。

去年写过一篇 blog 也是谈粒子系统的 。 思路大致类似,但这次在数据结构的细节上做了一些专门的设计,有觉得还有点意思,值得写写。

首先,粒子对象本身就是一个集合了多种数据的数据块。我限制了同时最多 64K 个粒子片,这些粒子对象可以放在一块连续内存中,并且可以用 16bit 的 id 进行索引。

当粒子系统的效果比较复杂时,会有很多的属性可以自动变化。包括且不限于位置、颜色、方向、大小、速度、加速度等等。其中,加速度本质上是受力,而粒子可以受多个力的作用,重力,风,向心力(用于旋转)。

一种方案是把每个发射器以及它发射出来的粒子看成一个对象,另一种方案是把所有发射器发射出来的粒子统一看成一个整体。我倾向于后者。因为当发射器可以发射发射器时(烟花或闪电都有这方面的需求),管理起来要简单一些。在这个方案下,发射器只是粒子的一个特性(可以发射新的粒子)。

那么,每个粒子其实是若干特性的组合。使用类似 ECS 的视角去看待粒子会方便的多。

  1. 每个粒子对象的数据是由若干 Component 组合而成的。
  2. 粒子系统由若干变换构成,借用 ECS 的术语,就是由若干 System 组成;每个 System 针对一类 Component ,它对有这个 Component 的粒子做某个统一的变换。
  3. Component 可以仅仅是一个 tag 不对应真实的数据。比如 Component 有 A B C 三种实际可以对应到三个数据结构上的类型。但我们还可以拥有一个叫 AB 的 tag 表示同时拥有 A 和 B 的粒子;或是 Ac ,表示拥有 A 但没有 C 的粒子,等等。

粒子对象可以对应到 ECS 中的 Entity ,但和 ECS 框架不同,我们并不需要对外暴露 Entity ID 。这是由粒子系统的特性决定的:

每颗粒子都是自生自灭的,在出生那一刻就决定了生命过程中的所有状态变换。多个粒子间没有相互影响,更新粒子 A 的时候,不需要取出特定 B 粒子的状态,所以不需要用一个 EntityID 去固定索引特定粒子。在应用特定的计算规则时,每颗粒子都可以单独计算,不关心粒子间的计算先后次序。

针对这些特点,我们就可以设计特定的数据结构,在内存使用和计算方面获得优势。


首先,我们不应把组成粒子的多个组件在内存布局上聚合在一起(C++ 对象的传统方案);而应该按组件类型聚合多个例子。

比如,大部分粒子都有一个 float lifetime 属性,我们在内存布局上就可以把所有存活的粒子的 lifetime 平坦的聚合在一个 float 数组里。这可以获得两个好处:

  1. 如果某个粒子不需要 lifetime ,就可以不占内存。
  2. 对于一些特例(只有一个 system 操作这个属性时),方便日后做 SIMD 优化。

另外,我们需要一个每帧递减 lifetime 的 system ,这个系统遍历 lifetime 这个 Component 集合,递减每个变量。

该数据结构的设计难点在于:每个 Component 是分离的,但是在处理某个业务时,需要联合使用多个 Component 。比如,我们需要把 “速度” 叠加到 "位置" 上。我们在遍历 "速度" 时找到同一个粒子对应的 "位置",就是很麻烦的事情。

我的做法是用一个 16bit id 把它们关联起来。但和传统 ECS 的设计不同,这个 id 仅用于内部工作,不暴露给使用者。所有的 Component 都在一个线性数组中,我们的 API 可以通过 Component 的类型和在这个数组中的索引号,找到同个粒子的另一个 Component 在所属数组中的索引。

我为这个数据结构实现了一个管理器 ,它管理了之间的关系,但不管理实际的数据储存。

其核心 API 是这样的:

bool particlesystem_add(manager, n, components[])

向粒子系统添加一个粒子,这个例子由 n 个 component 构成。注意:这里并不涉及 Component 的具体数据(它不由 manager 管理),仅仅是描述 component 的类型。

如果添加成功,那么用户需要自己把对应的数据追加到自己维护的数组最后。

index particlesystem_component(manager, component, index, sibling_component)

找到 component 的索引 index 处对应的粒子的 sibling_component 在它这个类别数组中的索引。这个 API 用于找一个 component 的兄弟。

particlesystem_remove(manager, component , index)

将 component 的索引 index 处对应的粒子所有关联的组件全部删除。删除本身只做一个记号,需要等 arrange 的阶段才真正抹去。

particlesystem_arrange(manager, n, remap[], state)

整理所有粒子,将当前帧删除的粒子抹去。如果关联的数组中出现空洞,则重新排列数据,最终保证数据连续。这个 API 把重新映射关系填入用户传进去的 remap 映射表中。这个映射表会告诉用户,什么 component 的哪个索引槽位中的数据被调整到哪个新的槽位。

由于管理器不管理真正的 component 数据,所以用户需要根据 remap 自己重新调整存放 component 数据的容器内容。


具体的使用见上面代码中的 test.c ,它演示了一个极简的粒子系统,只有 lifetime 和 value 两个属性。 update 函数会递减 lifetime 属性;并将 delta 不为 0 的 value 属性减去 delta 值。

November 08, 2020

Lua binding 的一些方法

这几天在给 RmlUi 这个库写 Lua binding 。

这个库原本有一个官方的 lua binding ,但是新特性 Data Model 却没有实现。作者坦承自己对 Lua 不是特别熟悉,这个新特性也在开发中,暂时没想好该怎么做,所以只完成了 C++ 接口,Lua 接口留待这方面跟懂的人来做。

我觉得这个新特性有点意思,打算帮助这个项目实现 Lua 接口。在实现的过程中,发现原版的 Lua binding 做的过于复杂,且那些复杂度完全没有必要。所以打算自己全部重新实现一套。

原版的 binding 存在的问题非常有代表性,在很多提供了 Lua binding 的 C++ 项目中都出现过。那就是实现了一套非常复杂的对象生命期管理。这是因为,作者试图可以从 C++ 方面和 Lua 方面同时全面控制同一个对象,包括对象的构造和销毁。每个对象都有一个 C++ 版本和一个 Lua 版本,它们相互关联在一起,一边销毁后,都需要妥善通知另一方可以正确处理。

整套机制使用了 lua object 的 gc 方法以及 C++ 对象的引用计数,且整个业务逻辑都在 C++ 里实现,变得异常繁杂。

我的建议是:像这种本来就是 script 驱动的东西(Lua 在 RmlUi 中的地位类似于 javascript 于 web 页面),只应该由 Lua 管理对象的生命,C++ 的对象引用只是它的附属品。也就是说,即使你想在 C++ 里创建会销毁一个对象,也必须通过 Lua 接口的间接调用,而不应该提供任何 C++ API 直接控制。

第二,所有 C++ 对象都被映射为 Lua 中的 Userdata ,并为其提供 metamethod ,让这些 userdata 尽可能地表现和 C++ 对象一致。这用了大量的 C++ 代码去实现这些机制。本质上,这些都是胶水代码,没有实现任何新的特性,只是用来给转译 C++ 功能到 Lua 搭桥而已。这其中还包括了将 C++ 里的多种数据类型以及函数类型用模板映射到 Lua 中,以及反向映射。每个在 Lua 中的操作,都不断地通过 metamethod 映射到 C++ 中做对应操作。这些不仅臃肿而且低效。

我的建议是:只映射必要的 C style API 到 Lua 。例如 Object::Method 如果是必要的,那么只需要提供一个对应的 Lua API ObjectMethod 转发这个操作。所有 C++ 中的 API 都平坦的导入 Lua ,Object(this) 以 lightuserdata 传入,不做任何特殊处理。Object 的构造和销毁,也用 ObjectCreate 和 ObjectRlease 两个 API 的形式提供。

对于数据(参数和返回值)传递,做有限的转换支持即可。

最后,我们在 Lua 中将这些 raw api 组合起来,模拟出对象系统,让 Lua API 看起来和 C++ API 类似,对用户更加友好。即,胶水层放在 Lua 中,而不是在 C++ 里用 lua api 硬写(binding 代码生成的意义也不大)。动态语言天生适合做这个。


有一个常见的难题:如果一块数据同时需要从 Lua 和 C++ 直接访问,该如何实现。这通常出现在 binding 中存在回调代码时。如果数据在 Lua 中,而 C++ 侧开始做回调绑定时,只有一个指针或 handle 来代替对象做绑定,那么在 C++ 侧如何取到 Lua 中对应的对象去通知它处理回调?

比如,RmlUi 的 DataModel 对象,其 C++ Api 是这样的:

你可以将一个内存地址 bind 到一个 DataModel 中的变量上。具体可以看官方的例子:https://github.com/mikke89/RmlUi/blob/master/Samples/basic/databinding/src/main.cpp

例中,将 my_data.title 的内存地址绑定到了 basics 这个 DataModel 的 title 这个变量上。在 C++ 中改变这块内存, rml 中对应引用的地方就会随之改变。

显然,Lua 中的变量并不能直接为内存地址,所以要在 Lua 中实现这个特性就要绕一下。好在,RmlUi 的 Api 要求的是提供一个 DataVariable 对象,这个对象由 VariableDefinition 和一个 void * 构成。我们可以自定义 VariableDefinition 的 Get 和 Set 方法去执行解释这个 void * 。

大概有两种方法:

  1. 为 DataModel 生成一个自定义的内存结构,以 userdata 的形式放在 Lua 中。变量还是映射到内存地址上,使用标准的 VariableDefinition 。如果 Lua 中需要读写这个数据结构,再用自定义的 metamethod 去解析它。

  2. 为 DataModel 生成一个 lua table ,直接用 Lua 的原生形式保存数据。但在自定义的 VariableDefinition 去访问这个 lua table 。

我选择第二个方法,因为这样生命期管理要简单的多。也更方便在 Lua 侧调试。如果选用第一种方法,不仅生命管理更复杂,还需要对自定义内存结构编写动态解析的过程。这是因为,数据结构是动态的,无法在编译时写成 C struct 。

第二个方案的复杂处在于,如何实现自定义的 VariableDefinition 。它从 C++ 侧调用,却需要访问指定的 Lua 虚拟机中的数据。Lua 不像 Python ,可以用一个 pyobject 指针直接映射 python 虚拟机中的对象,我们需要找到一个合适的方法。

这是个经典问题。经典方法是使用 LuaL_ref , 在 C++ 中保存一个 handle 做引用,每次想从 C++ 中访问 Lua 对应数据时,都用 handle 查一次表,找到对象的 Lua 对象。

今天,我想介绍另一种方法。它更简单高效,代价是多一点点内存开销。

我们可以用一个 lua thread 而不是 lua table 来保存 C++ 中的数据。因为,thread 即 lua_State ,是唯一种可以从指针访问的 Lua 对象。

我为 DataModel 创建一个 Lua 的 userdata ,这个 userdata 里不直接保存数据(userdata 用来触发 metamethods),而用 lua_newthread 创建一个独立的 thread 来保存用户数据。然后,将这个 thread 放在 userdata 的 uservalue 中,保护其生命期;同时将 thread 的指针保存在 userdata 中供 C++ 侧直接读写。

也就是说,当你在 C++ 侧想访问这块数据,那么用一开始绑定的指针(这里保存在 VariableDefinition 对象中)就可以找到对应的 lua_State * ,直接可以读写里面的数据;而在 Lua 侧,metatable 中的 __index__newindex 可以简单使用标准 lua api 读写数据。

具体代码可以参考 我为 RmlUi 提交的 PR