动态字体的贴图管理
汉字的显示，是基于 3d api 的图形引擎必须处理的问题。和西方文字不同，汉字的字形很难全部放在一张贴图上，尤其是游戏中有大小不同的字体的需求更是如此。即使放下，也很浪费内存或显存。如果不想申请很大的贴图来存放汉字字形，图形引擎往往需要做动态字形贴图的处理。
即，动态生成一张贴图，把最近常用的汉字画在上面。几乎所有成熟的基于 3d api 的图形引擎都需要有相关的模块才可以对汉字更好的支持。但我到目前为止，还没有看到有把这个模块独立出来的。大多数开源引擎都是在自己的框架内来实现差不多的功能。我觉得，这部分管理功能和如何管理贴图其实没有关系、和取得字形的方法也没有关系、不必和 3d api 打交道，也不用涉及到底用 freetype 还是 os 自带的 api 取得汉字字形，所以值得独立实现。
我们的需求本质上是对一张贴图的区块进行管理。每个汉字都占据其中的一小块。当贴图填满时，最久没有用过的汉字块可以被淘汰掉，让新的汉字覆盖上去。同样的字体的最大高度是相同的，可以排列在一行，但宽度可以不同。横向排列时，少许的空洞的允许的。
我设计了如下接口：
struct dfont_rect {
int x;
int y;
int w;
int h;
};
struct dfont * dfont_create(int width, int height);
void dfont_release(struct dfont *);
const struct dfont_rect * dfont_lookup(struct dfont *, int c, int height);
const struct dfont_rect * dfont_insert(struct dfont *, int c, int width, int height);
void dfont_flush(struct dfont *);
用 create/release 创建/删除一个管理对象，管理一张指定大小的贴图。贴图本身并不在这个管理对象内，它只负责管理贴图的空间划分。
可以用 insert 来创建一个指定宽高的矩形空间，并为这个空间指定一个 id 。这个 id 一般用汉字的 unicode 即可。insert 会返回一个矩形区域，如果贴图满了，且无法腾出空间，则返回空。禁止创建高度相同的相同 id 。
lookup 可以用于查询一个指定高度的 id ，如果贴图上不存在，则返回空。lookup 会记录这个字最近被使用过，不会被立刻淘汰。
贴图上创建的字型块，在调用 dfont_flush 之前都一定保留。调用 dfont_flush 后，如果贴图满，会淘汰最久没有使用的等高的字形空间。
我把一个开源实现放在 github 上了。不过暂时还没有放在任何项目中用，程序结构略微复杂，所以很可能有 bug 。
具体使用时，每次渲染一个汉字，可以先 lookup 查询过去是否创建过，如果没有，则算出这个字的尺寸，调用 insert 得到一个新的矩形空间，然后取得汉字的位图，上传到贴图的指定区域。每帧渲染完毕，调用一次 dfont_flush 即可。
一般情况下，创建一张 2048 宽的 dfont 对象大约就够用了。但是在字形的淘汰过程中，可能会导致贴图内有空洞（如果能保证尺寸相同，则不会产生这个结果），所以可能会比预想的少排一些字在贴图上。所以实际用的时候，可以考虑创建多创建一个 dfont 对象，交替使用，定期切换。
Comments
这个很好,这个思想很多游戏里应该在用的,也有每个字一个图片,但明显有问题的, 还有比较常用的就是一个字体一个图片,这就需要较大的显存了.
Posted by: zhupf | (20) August 4, 2013 12:34 AM
好吧，证明是我没看明白。。。
Posted by: 林翌蕁 | (19) May 15, 2013 11:50 PM
博主，你好，最近也在研究字体缓存这个东西。看了你的代码，有几个不明白的东西，list_for_each_entry(hr, &line->head, next_char),这一句出现在find_space这个函数里面，我不明白next_char这个哪里来的，没有看到相关定义.还有一个问题是，不知道您这部分代码能不能支持不同宽度和高度的字体呢？希望得到您的解答，谢谢！
Posted by: 林翌蕁 | (18) May 15, 2013 11:17 PM
@牛顿顿
我重新考虑了一下, 对于中文字, offx 和 offy 都是没有那么必要的. 也不需要 1.5 倍的储存容量.
实际上, 严格来说, 保存 offx offy 依然不够. 还需要保存字间宽和行间距才够.
而汉字偏向于方块的这个特性, 按留出间距后的字形来保存, 实际浪费未必很大.
Posted by: Cloud | (17) April 8, 2013 03:00 PM
不建议使用typedef的原因是因为一旦一个这样的名字出现在某个头文件，则使用这个头文件的人必须去找出申明这个typedef的源头，必须去把那个文件也include进来，否则编译通不过，从而给头文件的include关系增加难度。
Posted by: davidxu | (16) April 7, 2013 03:11 PM
@牛顿顿
是我疏忽了，过两天加上。不过纵向偏移是不用的。贴图上的排布不适合高度不一致。
Posted by: Cloud | (15) April 4, 2013 10:36 AM
最近在看风魂++源码，很好。。公司主要是java,不过要维护一个C++项目，才没办法将C++重新捡起。。云风的小数据内存管理这个类写的很好，看了两天才彻底看明白。。膜拜楼主。。
Posted by: tom | (14) April 4, 2013 10:18 AM
以前的项目中我也是做回收的，再后来就不做了，常用的字和符号也就那点
Posted by: 秒大刀 | (13) April 3, 2013 04:23 PM
我认可这样简洁的接口设计。
但我认为dfont_rect的定义能够适用于矩形贴图块，但不能很好的表达字体。
比如使用freetype,我们不能简单的忽略掉 face->glyph->bitmap_left及face->glyph->bitmap_top. 这两个数值。
也不能基于这两个数值简单的把位图进行偏移并且放入到我们的字体方块的左上角。如果单纯的对齐渲染，会发现整行的文字存在某种不和谐。
这是由于字体base-line之类的存在，一个16x16ps的字体的渲染范围是可能大于这个范围的。
当然可以用更大的空间（我试验的结果，1.5倍基本就行了,取决于字体）来容纳这个字体位图，以正确包含偏移。
我采用的方案是为每个字符额外存储了两个偏移数值：
offsetX=face->glyph->bitmap_left;
offsetY=face->size->metrics.y_ppem-face->glyph->bitmap_top;
这是我实际应用字体时遇到的问题。也不知道是不是有其他更好的解决方法。
Posted by: 牛顿顿 | (12) April 3, 2013 02:56 PM
以前做的项目都是动态字体，现在其实也不太需要了。用一张1024的RGBA8贴图每个通道都可以独立出来存储字体，然后用shader取出来，差不多小字体可以放一个完整的字库。现在中文字体也就2w多个字而已。这样也不影响效率。
Posted by: yuanlin2008 | (11) April 3, 2013 11:03 AM
你怎么区分、管理代码的开源实现和非开源版本？
Posted by: 韦恩 | (10) April 3, 2013 10:37 AM
两处错别字：
可以用 insert 来创建一个制定宽高的矩形空间 ->
可以用 insert 来创建一个“指定”宽高的矩形空间
得到一个新的矩形空间，然后取得汉字的位图，上传到贴图的制定区域 ->
得到一个新的矩形空间，然后取得汉字的位图，上传到贴图的“指定”区域
Posted by: i4oolish | (9) April 2, 2013 10:12 PM
云风大哥，你在SD2大会的演讲《高性能健壮系统中的内存管理》都几年了网上也没找到视频，CSDN怎么这么吝啬，不懂得造福一下后辈程序员。
Posted by: wei | (8) April 2, 2013 08:48 PM
C++当C用，比纯C好用啊，主要是结构体继承太有用了
Posted by: readdir_r | (7) April 2, 2013 08:38 PM
一般不用typedef,但是有时候像那种特别长的,如unsigned char可能会用下,特别函数参数有四个或更多的时候,会显得特别长,就觉得看着不太爽
一般用u1,u2,u4啥的
Posted by: fish | (6) April 2, 2013 07:25 PM
最近真的被typedef搞得一堆无名火起了，很不理解为什么有那么多人喜欢用这玩意，而且各有各的命名方式，最后的结果可能就是用了几个库，每个都对一个类型定义了一个名字，同一个类型有n个名字，直接能把人看傻
Posted by: et | (5) April 2, 2013 06:40 PM
一般大家认为，使用typedef会使数据类型不那么清楚明显，而且还会带来一些陷进问题。特别是当代码量变大之后，使用typedef给结构体定义一个乱七八糟的名字往往还不如直接使用strut来得清晰。可以去看一下linux kernel的代码风格，他们也是建议尽量不要使用typedef
Posted by: Anonymous | (4) April 2, 2013 06:22 PM
https://www.kernel.org/doc/Documentation/CodingStyle :
Chapter 5: Typedefs
Posted by: marmot | (3) April 2, 2013 06:15 PM
为什么要用 typedef ? 因为打字速度不够?
Posted by: Cloud | (2) April 2, 2013 05:14 PM
是否可以分享不使用 typedef 来声明 struct 的原因。
Posted by: 匿名 | (1) April 2, 2013 05:03 PM