« 游戏 UI 模块的选择 | 返回首页 | 裁剪和空间管理 »

动态字模的管理

在上一篇 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) 的时间复杂度。

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

Comments

@YuqiaoZhang

我正在用 imgui 做工具,计划用 RmlUI 作 runtime 。

但是针对中文的字体管理,现在并没有看到有做得过的去的开源库。这个首先就必须东亚开发人员做,西方主流开发人员根本不关心 glyph 数量太多的问题。甚至他们对 Unicode 就不太上心。我这几年已经给 3,4 个热门开源库修了 UTF-16 的处理 bug 了。imgui 在我提 pr 之前,连 Plane 0 之外都懒得支持。

嗯,我没理解对。之前看到你在把codepoint和fontid合并就想到应该用perfect hash,但是这个表不是固定大小的,所以也可能用不太上(可以自己搜一个好的hash function?)。不过这种一般类似cache的表好像也不大处理冲突,直接用个cuckoo hashing的做法把一个slot给直接evict掉好了,避免一些pathological cases。

云风不考虑使用第三方库吗?UI一般认为是引擎的边缘部分,即使国际上很有名的公司,也普遍使用第三方库?

毛遂自荐下,我觉得我搞的这个动态字体生成还是不错的。
https://github.com/matrix3d/spriteflexjs/blob/master/src/flash/__native/te/CharSet.as
支持htmltext
https://github.com/matrix3d/spriteflexjs/blob/master/src/flash/text/TextField.as#L221

大神啊

这个 hash map 是不断的动态构建的。prefect hash 有什么优势?冲突又有什么劣势?

为啥hash map会有冲突?可以直接用perfect hash吧,类似cmph这样的:http://cmph.sourceforge.net/

@mingchen 我觉得慢的话可以把 cache 的贴图持久化到文件系统中。

另外可以试试 https://github.com/memononen/SDF

之前用stb运行时生成sdf buffer挺慢的,手机平台几乎没法忍受,后来改为预渲染了

云风大哥厉害,请收下小弟的膝盖~

Post a comment

非这个主题相关的留言请到:留言本