« June 2020 | Main | August 2020 »

July 21, 2020

裁剪和空间管理

今天想谈谈游戏引擎中 Culling 模块。

当场景中的可渲染对象很多,而当前会被渲染的对象相较甚少的时候,我们通常会启用一个 culling 的过程。Culling 会想办法剔除一些当前不必渲染的对象,避免这些对象提交到 GPU ,让 GPU 承担剔除的过程。这样可以减少 CPU 到 GPU 的带宽。

最基本的 Culling 是用相机的视锥体和对象做一个相交测试,如果对象和视锥体不相交,则可判定它不必渲染;复杂的 Culling 还包括遮挡测试,如果一个对象完全被墙体挡住,那么也不必渲染。这篇只谈前者。

很容易得知,Culling 算法的复杂度上限为 O(n) 。即,我们把场景中的每个对象逐一和视锥体做一次相交判断即可。这里的 n 为场景中元素的个数。

当 n 特别大的时候,通过巧妙地设计数据结构,我们则有可能把复杂度降低。但如何做到呢?

因为视锥体参与算法的主要是它的空间属性,所以被测试对象可以用其空间信息做一些组织,减少相交测试的次数。这就是按空间位置对对象做管理的动机。

本质上来说,Culling 模块的数据结构,就是对场景上的对象按空间属性重新分组。每个组,组内元素有一些共性。视锥体可以和这些共性做一次判定,得到的结果可以分为三类:

  1. 该组对象全部包含在视锥体内。
  2. 该组对象全部不在视锥体内。
  3. 该组对象部分存在视锥体内。

对于第一、二类结果,我们可以一次性的得到一组对象和视锥体的相交测试结果。对于第三类情况,假设我们每个组内还继续分成若干子集,那么就可以递归这个过程。

无论以什么基准分组,最终都会组织为这样的树结构:先将全部对象粗分为若干组,每个组内再细分为子组,依次递归,直到最后不可分的组内有适当数量的元素。这样,Culling 算法的时间复杂度就降低为 O(log N) 。


综上所述,我们可以看到,以树结构对场景中所有对象分组是核心,怎样分组是次要的。不同的分组方式在不同的情况下可能有不同的效果。很难有普适最好的方法。

第二,Culling 是一个优化流程。有没有 Culling 过程,结果都是正确的。我们可以将 Culling 模块看作是一个加速查找的 Cache ,有了 Culling 模块,渲染层更容易挑选出需要渲染的对象。所以从设计上来说,我们应该把 Culling 定义成一个可选的加速 Cache 层,其数据结构不可喧宾夺主,变成引擎的核心容器。

强调第二点,是因为场景管理模块通常天然有一棵场景树,特别类似 Culling 的需求。很多人喜欢附带的把它附加上空间分割的内涵,供 Culling 模块使用。典型的实现就是在场景树的中间节点保持维护着子节点的包围盒的并集。我认为这种设计是不可取的。


下面我们来看空间管理的思路。为了方便解说,以 2D 空间为例,但所有算法都很容易推广到 3D 空间。

如果你的对象均匀的分布在场景中,那么最简单和自然的方法是用等距网格把空间切分为等大的正多边形。用正方形、三角形、六边形均可。从实现上看,正方形相对简单。

3D 空间往往也是用 2D 网格。这是因为大多数场景在纵向上的对象分布几乎都贴近地面,不太需要在高度轴上细分管理。如果有需要,我们也可以扩展成 3D 网格。

等距网格的好处是数据结构简单。如果对象数量不算太多,我们甚至不需要分层。从空间位置,可以 O(1) 的快速定位到子空间的位置。对象移动导致从一个子空间迁移到另一个子空间中,管理成本非常低。

但是,缺点也非常明显。如果空间很大,对象分布不均匀时,管理太多的格子的空耗成本非常大。解决方案就是将网格分级,先用粗狂的分割方案将空间粗略分开。如果子空间中对象总数不多时,就不再细分;否则,再将子空间分割成若干更小的空间。

在这个指导思想之下,权衡实现的复杂度成本,就得到了四叉树这种数据结构。

我们从空间中心,沿着两个相互垂直的坐标轴,将空间切分成四份;然后根据需要,将对象数量很多的象限,递归的切割成四个子空间。如果将这个思路推广到 3D 空间,那就是八叉树。

可以看到,四叉树就是对等距网格的改良。降低对象稀疏之处子空间的管理成本。但是,这个方案也有缺点:

  1. 对于无限空间,不太容易选取切割点。
  2. 通过空间位置定位子空间的复杂度从 O(1) 上升到了 O(log N) 。
  3. 对象是有体积的,如果对象穿过了切割线,对象的归属问题比较麻烦。

那么,有没有改进方案呢?

让我们回头来看最初:我们要做的是按空间对对象递归分组,以达到用 O(log N) 裁剪对象的目的。无论我们是用四叉树还是八叉树,只不过是树的层次上子节点的数量不同而已。既然可以每级的分叉可以是 4 或 8 ,很自然的可以想到,最简洁的分割方式应该是二叉树。

也就是说,我们可以每次对空间一分为二,然后根据需要对左右两个子空间递归分割。最后的效果是一样的,但数据结构可以更紧凑、算法可以实现的更高效。这里、和坐标轴对齐的分割线,在子空间的原点开始分割,都不是必须的。

如果我们可以用任意角度的直线在任意位置对空间一分为二,至少可以解决上面的问题 3 。因为我们总能找到不把对象一分为二的切割线。如果游戏场景里有大量的墙壁就更好了,我们沿着墙切割就好了。那么每个子空间都能迅速判定出在每堵墙的左边还是右边。甚至我们能把这些对象相对一个子空间排出一个的前后次序来。

没错,这就是大名鼎鼎的 BSP 。


用任意斜度的直线(或 3D 空间中的平面)分割空间,算法上可能涉及更复杂的数据运算。我们还可以退回一步,如果我们保持切割线和坐标轴对齐,但是在切割点上则不从中心点,而是选择恰当的地方,效果可能更好。

比如,每次切割子空间的时候,我们都选一个坐标轴平行线,让分割后的左右子空间均衡的容纳相同数量的对象。这样的效率肯定是最高的。(对于 2D 平面)因为每次切割都可以选择 X 轴平行或和 Y 轴平行。为了让切割后的子空间更接近正方形(这样对和视锥体相交测试更友好),我们每次选较长的方向一分为二最好。

如果这样做,最终每个子空间容纳的对象数量都大致相当。不像四叉树,这次我们可以保持一个完整的二叉树。即每个叶子节点的深度都是一致的。

储存完全二叉树不管从空间管理还是算法处理上都有极大的优势。我们知道,储存一个 n 层完全二叉树,只需要一块 2^n - 1 个连续 slot 空间即可。甚至不需要额外保存子节点的引用,因为本节点的索引乘二后,就可以计算出左右子节点的位置。

这样我们可以回避上面的问题 2 :空间位置定位子空间的复杂度又退回了 O(1) 。

没错,这就是大名鼎鼎的 K-D Tree 。


一般,我们以对象的中心点做 K-D tree 的子空间切分线的标准。但对象是有体积的,有些对象可能压线。这样就会导致最视锥体判定的时候可能出错:有的子空间不在视锥体内,但是对象因为压线的缘故超出了子空间的范围,实际是在视锥体内的。

怎么解决呢?

方法是,我们只以对象中心点和分割线去判定对象的归属。但每个子空间都重新根据内部的对象的包围盒计算出一个整体的包围盒。也就是说,相邻一对子空间的包围盒很可能有重叠之处。通过包围盒的计算,也很好的解决了无线空间的分割问题。

没错,这就是大名鼎鼎的 BVH (bounding volume hierarchy) 。


最后,我们来谈谈 K-D Tree/ BVH 的实现细节。

在做空间二分的时候,一个最重要的需求就是怎样把 n 个对象依某个坐标轴上的位置分成两组。也就是,怎样把无序的 n 个数组分成大小两组,大组集合中的每个数字都大于小组集合中的数字。

如果偷懒的话,我们可以对这组数组做一次 qsort ,然后从中间分开。时间复杂度为 O(N log N) ,空间复杂度为 O( log N ) (递归深度)。但其实更好的针对性算法可以把空间复杂度降低到 O(1) ,速度也能更快。

因为我们要的是分组而不是有序。所以我们可以像 qsort 的 inplace 算法那样,先找一个标点。因为迟早要计算整体包围盒,所以我倾向于选取包围盒长轴的中点,而不是 qsort 那样选取其中一个元素。以这个标点对所有元素二分。

如果刚好得到要求,就结束。否则对超出数量的一侧继续这个过程。

例如,如果需要对 8 个元素对分为 4:4 ,如果第一趟分为了 3:5 ,则只需要继续对 5 的一侧分为 1:4 , 而不必再处理 3 的一侧。这个过程就不再需要递归,而作简单循环即可。


另一个问题是,我们到底需不需要对 K-D Tree 做动态调整。

我的想法是,不是那么必要,仅在需要的时候做即可。一个静态的 K-D Tree 更好实现、更好维护。因为大多数场景中,大比例的可渲染物件都是位置不变的。我们可以用大量的静止物体构建一个 K-D Tree 作为空间的大致划分方案。每个节点其实只需要保存切割方向和切割线的位置。(btw ,如果想要紧凑的数据结构,可以把切割方向 2bit 编码到切割线这个 float 的内部。这样,保存一颗完整的 K-D tree 只需要 2^n 个 float )

我在设计时,倾向于不在 BVH 数据结构中保存对象引用列表,而仅维护一个包围盒。无论是静态物体还是动态物体,都参与子空间的包围盒的计算。从简化角度看,包围盒可以只扩大而不减少。如果演变得非常畸形的话,可以考虑重建整个空间结构。

记住:空间划分仅仅是 Cache ,而 Cache 可以根据实际需求去设计失效和重建的规则。

其实,我们并不需要太深的树层次。或许 10 层就足够了(可以划分出 512 个子空间)。如果场景特别的大,我认为应该按区域分成多颗树。而大型物件(如山体,巨型建筑)和小型物件也应该分属不同的容器。这样,方便用和摄像机的距离做初筛。

那么,每个空间树,就可以用一块固定的内存承载,实现起来非常简单,重建也很容易。甚至还能直接对这个 Cache 做持久化。


struct kdtree {
    float split[KDTREE_NODES];
    struct boundingbox box[KDTREE_NODES];
};

void kdtree_build(struct kdtree *space, int n, struct boundingbox *aabbs);
int kdtree_insert(struct kdtree *space, const struct boundingbox *aabb);
const struct boundingbox * kdtree_box(struct kdtree *space, int index);

这是我设计的核心 api 。build 方法可以通过 n 个包围盒构建一个 kdtree 结构来。然后我们可以不断地 insert 包围盒对象,可以获得这个对象所在的 slot 编号。至于这个 slot 最终保存了哪些对象,是用户额外储存的,这里的数据结构仅维护包围盒。


因为 culling 只是一个优化过程,使用完全独立的数据结构。我认为甚至它可以放在额外线程中处理。因为我们可以每次把视锥体扩大,交给 culling 线程做判定。而不必急于拿回 culling 结果。

虽然我们每次得到的 culling 结果都是过去提交的请求,但是,如果当前的视锥体在请求时提供的范围内(请求时扩大了),那么就可以直接用结果。否则,可以跳过 culling 直接渲染(或在本地做一次 O(n) 的 culling )

July 16, 2020

动态字模的管理

在上一篇 blog 中,我谈到了 UI 模块。而 UI 模块中绕不开的一个问题就是怎么实现文字渲染。

和西方文字不同,汉字的数量多达数万。想把所有文字的字模一次性烘培到贴图上未尝不可,但略显浪费。如果游戏只是用有限几种字体倒也不失一种简单明了的方法。但如果使用字体丰富,而多数字体只使用几个汉字,那么就不太妥当了。

我在设计 ejoy2d 的时候实现过一版动态字模的管理。但我觉得略显简陋。最近重新做了一版。

首先,我决定使用 SDF 来渲染字体,所以不必在贴图中管理不同大小的字模了。其次,我觉得汉字的宽度其实一致是一致的,我们不必再用复杂的装箱算法去节省贴图空间,改用等宽登高的固定大小矩形区域切分贴图,更容易做到灵活管理。

最终设计的管理器的 C API 大致是这样的:

void font_manager_init(struct font_manager *);
int font_manager_addfont(struct font_manager *, const void *ttfbuffer);
int font_manager_rebindfont(struct font_manager *, int fontid, const void *ttfbuffer);
void font_manager_fontheight(struct font_manager *F, int fontid, int size, int *ascent, int *descent, int *lineGap);
int font_manager_touch(struct font_manager *, int font, int codepoint, struct font_glyph *glyph);
const char * font_manager_update(struct font_manager *, int font, int codepoint, struct font_glyph *glyph, unsigned char *buffer);
void font_manager_flush(struct font_manager *);
void font_manager_scale(struct font_manager *F, struct font_glyph *glyph, int size);

管理器还是不管理具体贴图和像素,只管理区域。我们可以把多个 ttf 数据加载进去(得到一个 font id),也允许卸载掉,之后再使用的使用 rebind 。

核心的管理 api 是 touch 和 update 。touch 指用户计划使用一个字模了,这里可以获取到相关的 glyph 结构。但这个字模可能在 cache 中,也可能不在(根据返回值判断)。如果在 cache 中,就可以直接利用 glyph 结构中的 uv 渲染,否则,还需要调用 update 。

而 update 则真正将字模的像素从 ttf 回填到用户给出的 buffer 中。继而用户有责任上传到贴图中。

之所以将这两个 api 分开,是因为字体管理器不负责贴图管理,也不涉及更新贴图的 api 。

另外,因为我们用 SDF 渲染字体,所以提供一个 scale 函数计算对应的缩放信息。


值得一谈的这次这个字体管理模块的实现。

我在实现的时候,设计内部数据结构的指导原则是,采用固定大小的数据结构,并在使用过程中做到零内存分配。且不依赖任何渲染层的 API 。这并不太容易做到。

来看看需求:

不同的 font 不同的 codepoint 被放进这个数据结构中,这些数据可能动态增删,但希望可以 O(1) 检索。符合这个需求的似乎只能是 hash 表。而固定内存的 hash 表,通常被实现成开散列的。

我希望 cache 中保存的数据以 LRU 形式进出,即太久不太使用的字模会被淘汰掉。当我们 touch 一个字的时候,需要放在这个 LRU 队列的最前面;队列满的时候,需要从最后删掉一个。看起来,比较朴素的思想是用一个双向链表来实现这个数据结构。

另外,我们可能不希望一个 drawcall 只画一个字,所以提供了 flush 这个 api 告诉库发生了一次 draw 。在 两次 flush 之间,需要一个自增的版本号来区分。

所以最终,font_manager 这个数据结构是这样的:

struct font_slot {
    int codepoint_ttf;  // high 8 bits (ttf index)
    short offset_x;
    short offset_y;
    short advance_x;
    short advance_y;
    unsigned short w;
    unsigned short h;
};

struct priority_list {
    int version;
    short prev;
    short next;
};

struct font_manager {
    int version;
    int count;
    short list_head;
    short font_number;
    struct stbtt_fontinfo ttf[FONT_MANAGER_MAXFONT];
    struct font_slot slots[FONT_MANAGER_SLOTS];
    struct priority_list priority[FONT_MANAGER_SLOTS];
    short hash[FONT_MANAGER_HASHSLOTS];
};

struct font_glyph {
    short offset_x;
    short offset_y;
    short advance_x;
    short advance_y;
    unsigned short w;
    unsigned short h;
    unsigned short u;
    unsigned short v;
};

其中 codepoint 和 fontid 合并到一个 32bit 整数中。hash 函数采用:

static inline int
hash(int value) {
    return (value * 0xdeece66d + 0xb) % FONT_MANAGER_HASHSLOTS;
}

开散列 hash 结构,在发生冲突的时候采用固定步长 7 来选取下一个 slot 。

LRU 队列使用 short index 的双向循环链表,保证调整优先级的时候是 O(1) 的时间复杂度。

其它具体代码就不列出了。

July 09, 2020

游戏 UI 模块的选择

在游戏(包括引擎)开发的过程中,谈及 UI 模块,通常所指有二:

  1. 开发工具所用到的 UI 。
  2. 游戏本身所用到的 UI 。

这两者很多时候都是共用的一个模块,比如之前的 Unity 就直接把引擎开发用的 UI 模块扔给开发者开发游戏使用。但很快,开发者就发现,适合工具开发的 UI 模块,在做游戏时就不那么顺手了。所以就有了第三方 UI 插件的流行,以至于最后又倒逼 Unity 官方重新制作游戏 UI 模块。

开发工具面临的需求和游戏场景面临的需求很不一样:

开发工具需要的时候更好的将内部数据以可视化方式呈现出来,供用户浏览和修改,以适应数据驱动的开发。UI 的呈现需要的一致性,风格统一有利于减少学习成本,同时需要清晰的表达复杂的数据结构。有时还需要将内部数据的变化过程同步的动态呈现,给开发者更直观的感受。

游戏 UI 是游戏过程的情感体验的一部分,外观和交互需要根据游戏设计专门化。它往往并不需要表达游戏内部复杂的数据结构,而是将那些数据以额外面对玩家的形式展现出来。玩家通过界面下达的指令也并非直接对数据的修改,而是以指令流的形式传递过去。另外,HUD 也是很大的一个部分,和 UI 对话框在设计上也有很大的不同。

他们两者之间在技术上的共性其实很小,针对这些共性的技术实现可能也只有几百到上千行代码的规模,远少于差异部分需要的代码量。我比较倾向于把这两个东西分开实现。

关于工具所用的 UI 模块的选择,我的开发生涯中早期使用过 MFC ,.net ,wxwidgets,Qt 。近两年做引擎开发时先选择的 iup ,后来转向 dear imgui 。这里面的选择无非是 Retained mode 和 Immediate mode 之争。在这个问题上,我目前比较赞成 im mode ,认同这篇 blog 的观点 。另外加一句,我觉得 stateless 模式可以减少 bug 。

在这个问题上,今天不想展开谈,这次主要说说游戏 ui 。

为游戏写 UI 模块,我自己动手干过两次,都是十多年前的事情。最早是为大话西游写的,后来因为学习 C++ 的新语法又重写过一版,但没有用在自己开发的游戏中(送给朋友,他倒是用在游戏产品里了)。在此之后,我的开发思路改变,不再追求自己实现,而是考察成熟方案。所以如非必要,就不再新起山头了。

最近做游戏引擎开发,又重新考虑该选择一个怎样的游戏 UI 模块。

首先考虑的是对已经在用的 imgui 做一番改造。试过 Nuklear 和 Dear imgui ,改造过程都不太满意。Dear imgui 在做工具开发上已经非常成熟,但项目已经明确了,聚焦于工具开发而不会考虑游戏 UI ,我稍微动了下手,觉得不应该背道而驰。

在做手机游戏开发的初期(陌陌争霸),我也尝试过自己实现一个简单的 IM mode 的 UI 模块,勉强够用,但似乎也不太好用。对游戏开发不太友好。后来就转向 Retained mode 的库。

前些年 CEGUI 非常流行,这两年似乎不那么活跃了。最近两年也涌现过几个类似的项目,看了一下感觉还是太复杂。这些复杂的项目似乎都奔着工具开发的领域去做,其实我是用不着的,犯不着为了不需要的需求增加项目的复杂度。

UI 模块本质上,实现需要解决的仅仅是一组矩形如何布局的问题。这个问题并不复杂,而且布局问题也有非常简洁的开源实现,不需要从头动手。实现了布局后,把控件顺次绘制出来即可。至于优化,可以探讨的方面很多,但可以列为单独任务。

而从设计角度,就是如何去描述这些控件,可以方便的翻译成布局信息。

最近一段时间最打动我的是 Paradox 的游戏引擎。虽然是闭源的,但因为给群星做汉化 Mod 的缘故,我仔细研究了它。它的 UI 系统是完全可以 Mod 的,全部是文本呈现。给了我许多启发。

首先是 UI 的结构和呈现分离。在这个引擎中,区分了 .gui 和 .gfx 两类文件(其实文件格式是统一的,仅仅是后缀不同)。.gui 描述的是 UI 的结构,可以看成是把 UI 看作是树状层级的一个个矩形区域,描述出每个区域的功能。而这些矩形区域到底如何呈现,是用静态图片,还是有动画效果,又或者直接用线条绘制。以及一些和逻辑无关的表现行为,例如鼠标悬浮时需要有一些特别效果,等等。都单另放在一个 .gfx 文件中描述。这就有点像 html 和 css 的分离,但更简洁一些。

我想找找有没有类似设计的开源 UI 库,没有找到。其实自己实现也不算复杂,核心仅在于如何设计这个数据表达的形式,而这个从 Paradox 的游戏文件中已经可以找到完整的参考了。我前段时间自己设计了一版。但在设计的同时,也在继续寻找潜在可用的开源方案。

除了这些从头设计的开源 UI 库以外,这些年还流行另一种解决方案。那就是借用成熟的 UI 表达形式,为游戏环境重新实现。这些成熟的 UI 方案无非两种:flash 或 HTML/CSS 。这类方案的最大优势就是,开发 UI 的工具成熟,开发者不需要学习新概念。而对于 UI 怎样描述这方面,成熟的文件格式可以少踩很多坑。而另起山头自己设计的格式,虽然更简洁,或许能贴近需求,但难免在需求迭代之后,发现之前的失误。

这其中最为有名的是 Scaleform ,是对 Flash 的重新实现。星际 2 就用了它。不过这是个商业中间件,且已经停止开发。开源的类似品也有一些,不太成熟。考虑到 Flash 本身已经日薄西山,我也不想考虑这个系列。

HTML/CSS 方案最近几年非常流行。最有名的是基于开源 webkit 的各种改造。例如吃鸡就是用的这样的方案。但 webkit 还是过于复杂了,这种复杂性最终的反应就是用于游戏后,性能有问题,且不太好优化。吃鸡的团队就做了大量的改造,可以在某些特定场景下,提升一两个数量级的性能。可见 webkit 直接用于游戏引擎复杂度造成的潜在问题。

另外,Valve2 的 Source 2 引擎中提供的 UI 模块 Panorama UI 也是基于 HTML/CSS 的。这是一个商业闭源产品,但可以找到开源的类似品。很多年前,我关注过一个叫 LibRocket 的库,那个时候还不太完善,后来就停止维护了。最近我发现有人在它的基础上 fork 出来一个叫 RmlUI 的项目,我十分喜欢。裁剪掉了许多不必要的功能,代码做了整理以及一定的优化。明显其设计目的就是嵌入到其它游戏引擎中使用。

昨天我阅读了文档,玩了一下。发现一些 mingw 编译的小问题,顺手提了 PR 。这个项目非常活跃,直到昨天还有新的提交。我选择开源项目的首要考察因素就是维护者的活跃程度。所以暂时会把这个作为重点备选项目,尝试往我们正在开发的引擎中集成。


关于集成,一般的 UI 库都会提供一个抽象层让你对接渲染和系统输入消息。而渲染部分最难的是两个问题,一是如何保证性能,二是字体的管理。

由于大多数成熟的开源项目都是西方人领头的,对汉字这种字符量巨大的字符集没有过多的考虑。把动态烘培字模,限制使用贴图数量的方案优先级都排的比较低。如果不下一番功夫,一般就用巨大的贴图,烘培上所有的汉字了事。例如 imgui 就是这么干的,动态的字体贴图管理这个特性已经在 todo list 里停留了很久了,好像也看不到时间表。

如果游戏只使用一两种字体倒无所谓,想让字体丰富一些,这不是个办法。所以我前段时间静下心好好设计并实现了字体渲染中贴图管理的模块。改天我再写一篇 blog 记录一下。