云风的 BLOG

lua 从 5.2 开始，简化了 5.1 中的模块管理方式，然后一直保持到现在这个样子。

模块用 require 加载，同名模块在一个 vm 中只加载一次，第 2 次开始会返回上次加载的结果。加载模块时会利用 package.path 或 package.cpath 中定义的字符串模板，把模块名转换为文件名，依次尝试打开文件。

我在新项目中，由于整合了不少模块，感觉现有的这套机制有点点不够用。所以我做了一点点小改动，支持了类似 python 的模块管理那样的相对机制。当在一个模块中 require 另一个模块时，会先尝试加载相对路径上的模块，再尝试绝对路径。这样可以方便我们集成独立开始的模块，并放在独立的名字空间中。也方便给模块内置测试子模块。

例如，我独立开发了一个叫 foobar 的模块，它自己有一个子模块叫 foobar.baz ，在集成到系统中时，我希望把它们一起放在 common 名字空间下。使用的时候可以用 require "common.foobar" 来引用。

如果直接用 lua 原生的模块管理机制，我需要修改 foobar 主模块的代码，把里面的 require "foobar.baz" 改成 require "common.foobar.baz" 。同理，如果我不满意 foobar 这个名字，想换名也很麻烦。

所以我希望在新机制下，foobar 的主模块引用自己的子模块 baz，只需要 require "baz" 即可。如果同一目录下有 baz.lua 这个文件，就优先加载它。而外部模块也可以通过 require "foobar.baz" 直接引用这个子模块。

新机制最好可以兼容原生机制，所以不必另起一套模块管理代码。我们要做的只是获取当前模块的名字，在 foobar 主模块中调用 require 时，尝试给参数加上 foobar. 的前缀，引入失败再按原生路径尝试。

好在 lua 原生机制已经把当前模块名作为参数传递进来了。我们只需要实现这么一个函数：

local loaded = package.loaded
local searchpath = package.searchpath

function import(modname)
    if modname then
        local prefix = modname:match "(.*%.).*$" or (modname .. ".")
        return function(name)
            local fullname = prefix .. name
            local m = loaded[fullname] or loaded[name]
            if m then
                return m
            end
            if searchpath(fullname, package.path) then
                return require(fullname)
            else
                return require(name)
            end
        end
    else
        return require
    end
end

这个 import 会生成一个模块导入函数，完成以上逻辑。我把这个函数定义成了全局函数，在项目开头就引入。然后，在每个模块的最前面加入这样一行：

local require = import and import(...) or require

如果定义了 import 则用 import 生成一个 require 代替原生版本；否则直接使用原生版本。

另外，我更倾向于用目录来管理模块。即使一个模块只有一个文件，也放在一个单独的目录中。lua 原生模板的约定是 ?/init.lua 用目录中的 init.lua 作为主模块的入口，我更喜欢 ?/?.lua 直接用目录名同名文件做主入口。

Posted by 云风 at 10:23 AM | Permalink | Comments (2)

如果用纯 lua 来做向量/矩阵运算在性能要求很高的场合通常是不可接受的。但即使封装成 C 库，传统的方法也比较重。若把每个 vector 都封装为 userdata ，有效载荷很低。一个 float vector 4 ，本身只有 16 字节，而 userdata 本身需要额外 40 字节来维护；4 阶 float 矩阵也不过 64 字节。更不用说在向量运算过程中大量产生的临时对象所带来的 gc 负担了。

采用 lightuserdata 在内存额外开销方面会好一点点，但是生命期管理又会成为及其烦心的事。不像 C 中可以使用栈作临时储存，C++ 中有 RAII 。且使用 api 的时候也会变得比较繁琐。

我一度觉得在 lua 层面提供向量运算的基础模块是不是粒度太细了。曾经也想过许多方法来改善这方面。这两天实践了一下想了有一段时间的方案，感觉能初步满意。

我的应用场合是 3d game engine ，engine 计划用 ecs 框架搭建，这为向量运算模块的优化提供了不错的基础。至少在对象生命期管理方面有了 system/component 的约束，做起来会简单许多。

游戏引擎中用到向量运算的场合主要是两类，一类是处理某项事务时用到的大量临时对象，通常是 3x3 矩阵，vector3 和 vector4 ；另一类是引擎中的对象需要用矩阵记录下其空间状态。我认为，无论是 vector 还是 matrix ，虽然它们的数据尺寸比系统的字宽大，但它们依然应被视为值类型，而不是引用类型。但是由于 vector/matrix 的值长度大于语言支持的原生类型，无法直接在值类型的原生变量中放在，所以一般我们还是要借用某种引用语义。就好比 string 在 lua 中是值语义的，但使用引用类型的方式实现出来的。

也就是说，在设计库的时候，即使支持 A *= B 这样的运算，因为 A 和 B 都是按引用的方式实现的，但也并不是将 A * B 的结果直接覆盖到旧有的 A 引用的值空间上。这和 A = “hello" ; A = A .. " world" 一样，新的字符串 hello world 并没有覆盖已有的 hello 这个字符串。

lua 中的基础数据类型中，属于值类型可以用来做这个封装的有三种：number(id) ，lightuserdata 和 string 。我曾经想过直接用 string 将 vector/matrix 的值用 string.pack 打包，但细想一下并不比 userdata 好多少。lightuserdata 若是直接储存数据在内存中的地址的话，和 C 的裸指针没什么差别，用起来实在是不太放心。所以可选的就只有数字 id 了。

5.3 版以前的 lua 可以保存 52bit 有效精度的数字，5.3 版以后则在大多数平台上有 64bit 精度可用。用作索引 id 号的话绰绰有余。加上 id 这个间接层，我们可以很容易的识别出哪些无效 id ，比用指针安全很多。

因为游戏通常是按帧处理业务的，每帧之间没有特别的联系，如果在帧内没有特别的把某个值记下来，那么通常就不会再使用它了。我想，用帧号（版本号）+ 顺序数字 作为值对象的唯一 id ，即可以方便的索引到数据块（使用一大块连续内存数组即可），又能快速排除已经销毁的对象。构造新对象也是 O(1) 的操作，还可以用 O(1) 时间批量作废当前帧用到的所有临时对象。

即，任何向量运算操作，都产生新的值对象，一旦产生，就不再修改其值。每个对象用一个唯一数字 id 来表示。除非特别注明，一个值需要长期保留，这些对象的生存时间都不会长于一帧。每帧结束后，通过递增版本号的方式来让旧的临时 id 失效。

在运算操作方面，每个针对向量的一元或二元操作都增加一次 lua 到 C 的函数调用有时也显得重了。比如两个 vector4 相加，运算量不过是四次加法，而 lua 到 C 的函数调用则远大于此。我觉得借鉴 forth 的设计比较好。单独再设计一个数据栈，操作全部基于数据栈进行；如果设计复杂的操作流程，还可以增加指令栈（暂时还没用到，所以没有实现）。也就是把向量操作的相关操作都基于一个独立于 lua 语言本身的栈上去完成。比如两个矩阵相乘再去逆，可以写成 :

command ( mat1, mat2, "*~") 用来表示 ~ (mat1 * mat2)

也就是先把 mat1 和 mat2 两个 id 压栈， * 会弹出栈顶的两个对象做矩阵乘法，把结果压回。而随后的 ~ 取逆矩阵的操作则将栈顶的对象弹出，做逆矩阵运算，结果再放回去。

这样，一个 command 函数，通过若干参数，就可以完成一系列的运算操作。且连续的运算是通过一个字符串常量传递给 C 模块的，大大的减少了 lua 和 C 的交互次数。这些操作都是基于数据栈的，加上这个数据栈和 lua 本身的交互指令就完备了。

我暂时设计了一系列和数据栈操作有关的指令：

• P 把栈顶元素弹出，并将 id 返回到 lua 中。
• V 把栈顶元素弹出，并将数据内存地址以 lightuserdata 的形式返回到 lua 中。 用来传递到其它（比如渲染）模块，指针保证在当前帧有效。
• T 把栈顶元素弹出，并将数据构造为一个 lua table ，方便调试、持久化等。
• R 把栈顶元素移除 (不返回到 lua )。
• D 复制栈顶元素。
• M 把栈顶元素弹出，用其值构造一份新的持久化的值，并把新的持久化对象的 id 返回到 lua 。

操作这个运算模块只有一个函数，通过一些列不同的输入来完成操作。如果参数为 table 则把 table 的内容作为 vector 或 matrix 的值来构造出新的对象压入堆栈。

如果参数为数字，则当作过去构造出来的对象 id 压栈。其中，一个特别的设计是，如果这个 id 对应的是一个持久值（即不会在当前帧结束后失效），在这个 id 重新压会数据栈后，又会变成一个临时对象。这样，你可以放心的写

local a = command (a,b,"*M") -- 即 a = a * b 这个语义。

旧有的 a 即使是一个 M 值，也会被标记为失效。如果这里的 b 是一个持久化的常量，不希望临时回收，则可以采用另一个设定 ：

local  a = command (a,-b,"*M") -- 当 id 为负的时候，可以返回压栈而不改变其持久化特性。

我昨天在实现的时候做了两个版本，前一个版本把持久化标记加在内部堆的 slot 上，但这样会导致堆空间不连续，每帧重利用的时候，要么加大了回收的负担，要么增加了新构造对象的负担。好处是做持久化标记代价很小。

后来我又实现了一版，把临时对象和持久化对象分开空间储存；临时对象用最简单的栈式连续内存分配，每帧结束复位一下栈顶指针即可。持久对象则用 freelist 管理。所有对象从外部入栈时都一定先放在临时区，用 M 指令转换到持久区，做一次值拷贝。而消除持久化，删除它只需要简单加到 wish freelist 里（按前文所述的规则），待帧结束后合并 freelist 和 wish freelist 两个链表即可，不必再做拷贝。

这块代码将来会随我们的游戏引擎开源并维护。暂时我把昨天一些初步的实现贴在了 gist 上，供参考 。注：gist 上这个版本不会维护。

后续改进见：https://blog.codingnow.com/2018/02/linalg_improvement.html

Posted by 云风 at 01:05 PM | Permalink | Comments (14)

现代 2d 游戏的图形地层绝大多数也是基于 3d api 实现的。为了提高性能，通常要把若干图元 (sprite) 装箱在整张贴图中。这个装箱过程可以是在线下完成，也可以是在运行期来做。

TexturePacker 就是做这件事的优秀商业工具。不过我认为把它放在开发工具链中还有一些不足。图元的装箱和根据装箱结果合成贴图是两件事情，如果我们是手工操作，合在一起完成当然方便；但如果是在自动化流程中，分开独立完成更好。因为迭代开发过程中，每次重新打包资源，都只会修改少部分图元，且图元的大小未必会改变。如果大小不变，就不必重新做装箱运算。

如果部分修改图元，则合成贴图的过程有可能能减少运算过程。通常我们需要对最终的贴图做一次压缩，生成类似 ETC 的压缩贴图类型，这是极消耗 cpu 的。而 ETC 压缩格式是基于 4x4 的区块独立压缩，只要保证图元尺寸是 4 的倍数、就可以先压缩，再合成。这样，没有修改过的图元就可以不必重新运算，直接从文件 cache 中读回。

有些时候不合成、仅保存装箱结果更适用。可以在运行时根据 altas 数据把分离的图元装载在贴图中。分开打包独立的图元资源更适合游戏更新。

第二，在提高装箱利用率上面 TexturePacker 做了很多的努力。很多 sprite 的边角会有大量的空白，仅仅按轴对齐的四边形包围盒裁剪还是浪费太大。它的最新版本支持了多边形装箱、即尽可能的把边角都裁剪下来。这种做法的代价是增加了运行时的多边形数量（对 2d 游戏来说，通常不太重要），但让装箱边角余料可能多填一些小 sprite 进去。

但我认为其实还可以找到更多方法。

这篇 blog 就想谈谈最近我在为公司新的 2d 项目完善 ejoy2d 的工具链，编写装箱工具时，做的一些工作。

我发现，有很多 sprite 会在边角留下很多空白，虽然打包压缩后并不多占安装包空间，但是减少了贴图利用率（进而增加了运行时的显存/内存负担）。如果我们能稍做变形，就可以在不损失信息量的前提下，用更小的矩形包容下。比如我们上个项目中有下面这么一张（左）图，这把武器是按透视角度斜着创作的，在左下和右上都留下了空白。如果我们做一个斜切变换，就能变为右图，图元面积从 358x305 变为了 149x284 ，面积减少到 38.8% 。

由于线性过滤的关系，图在处理后有点糊，可以做一次锐化：

这个方法很容易想到，我们在之前的项目中却是人工制作的：美术先在图形处理软件中对图形做变形，然后再通过编辑器变回来组装成游戏里用的状态。明显这个过程是可以由程序自动化完成的，难点在于找到算法。我在这几天实现的图元打包工具时采用了一个时间复杂度为 O(n^2) 的算法来求最优解。但实际上算法优化空间很大，我认为理论上是能做到 O(log N) 的。好在通常 n 不大，整体运行时间不长。而且单个图元做完一次就可以 cache 结果，不修改图元就不必重新运算，所以这个优化可以留到后面慢慢做。

算法是这样的：

我们先尝试对图在水平方向做斜切，也就是按比例把每条水平扫描线做平移，即把矩形拉扯为一个平行四边形。在这个过程中，每个像素都是保留的，有效像素数量没有改变，所以信息量是一致的。同时，每移动一个像素，就尝试在垂直方向做同类处理，当我们尝试完所有的 x,y 方向的变幻组合，每种情况下都计算一下 AABB ，就能找到最佳参数。ps. 由于这个过程是线性变化的，所以未必要逐一尝试。

我试了另一张我们游戏中的图片，处理结果和美术手工处理的几乎一致（程序计算出来的甚至比美术凭经验做出来的略好一点）。

但不是所有的图片都适合做这样的处理，比如常见的菱形手绘地块，由于变形太多，虽然像素都保留了，但运行时绘制的时候因采样算法的影响，图像糊得比较厉害。

这和图片旋转会糊掉的道理是一样的。这种可以在打包工具中标记出不做处理（美术给图片加个指定的后缀供打包程序识别）。另外，如果运行期不需要缩放的话，用 GL_NEAREST 采样比用 GL_LINEAR 更好。

ejoy2d 在设计贴图数据格式的时候就考虑了这种需求。sprite 在 altas 数据中描述的是贴图上的四个顶点坐标映射到屏幕上的四个顶点位置，而没有像其它 2d 引擎那样只描述了一个偏移量。所以我们只需要做逆运算计算出变换过的图元的四个顶点对应在屏幕上实际的四个角即可。

算法的实现在我正在开发的贴图打包工具里单列为一个 lua 的 C 模块，可以方便的由工具链调用。实现并没有优化，主要是希望简单明了。 注：这个工具尚在开发中。

另外，我们还可以结合通过适当的切割来进一步提高利用率。比如一张 100x100 的图元，很可能切割成左右 50 像素的两半后，每一部分都小于 100 像素。（单个 sprite 由多个区块构成，在 ejoy2d 的底层也有天然支持）不过要注意：当把 100 像素宽的图元切割为两部分时，需要两侧都留边。即每边都是 51 像素，多保留对面的一个像素宽，这样运行时拼接起来才不会有缝。至于切割线的最优位置（未必在正中间），也可以通过穷举来计算。

Posted by 云风 at 02:52 PM | Permalink | Comments (25)