从零开始手敲次世代游戏引擎(卌)

终于四十了。
前面两篇我们使用bullet库进行了一些简单的弹性碰撞的物理场景仿真演示。也很粗略的说了一下碰撞检测的一些相关概念。但是这显然是不够的。
为了真正理解计算机是怎么进行这些物理计算的,特别是在游戏这么一个软实时系统当中,是如何“又快又省”地做到这些的,我觉得非常有必要再造一下轮子。
在前面的文章当中,我们提到过,碰撞检测的基本数学原理就是高中所学的解析几何。简单复习一下:
3维空间的两个几何体(或者2维空间的几何形状)如果发生碰撞,则说明它们之间有了肢体接触。用数学的语言来说的话,就是至少存在一个点,满足这个点既在A上又在B上。或者,如果用集合的概念来说的话,就是
A\cap B\ne Ø\\
所谓解析几何,就是通过建立某种坐标系,将几何体转化为代数方程,然后用代数的方法去研究几何问题。在解析几何当中,A与B的交点就是代表A与B的方程所组成的方程组的所有解。(如果只考虑边界与边界的交点的话)
因此,很显然的,几何上A与B是否相交的问题,就可以转化为在某个坐标系下代表A的方程与代表B的方程是否有共通解,也就是方程组是否有解的问题。
然而,在游戏当中,仅仅依靠这种方法是不行的。因为:
  1. 游戏当中绝大多数的几何体都是无法解析表达的。就是说你写不出它的方程。比如我们一个足球游戏,要检测脚与球的碰撞。球还好说,脚就是一个很难用解析的方式(方程)去表示的几何体;
  2. 当代游戏当中往往有成百上千个几何体,各种形状。如果它们均可动,那么任何两个几何体之间都可能会发生碰撞。为了检测这样的碰撞,我们不得不检查所有可能的组合。这是一个很大的量;
  3. 方程组是否有解的问题本身就是一个复杂的问题。就算有判定公式的些特殊情况,判定公式的计算,对于游戏引擎那可怜的ms计算的周期来讲,也往往是十分昂贵的;
  4. 游戏当中往往需要知道的只是碰上了还是没碰上,并不需要知道到底是A的什么地方碰到了B的什么地方,也就是说不需要精确解(定量判断),只需要定性就好。
所以,一般来说游戏当中并不会直接对场景物体求交,而是通过给场景物体包裹一个基本几何体(被称为是碰撞盒,也叫包围盒,等等),将复杂的场景物体求交近似为简单几何体求交来进行的,也就是我们前一篇所提到过的那些基本形状。
这些基本形状十分有用。不仅仅在物理引擎当中会用到它们,它们对于场景的快速建模(关卡设计)、场景渲染的优化、调试等都非常有意义。所以我们有必要在引擎当中实现它们。
实现基本几何体
让我们在Framework目录下面新建一个子目录,取名为Geometries。然后在下面新建一个Geometry类,定义基本的几何体共通的属性:
我们首先定义了几何体形状类型,用于在运行时判断实例所代表的几何体形状。然后我们定义了我们希望所有几何体都支持的几个方法:
  1. 获取球形包围盒(GetBoundingSphere)
  2. 获取与坐标轴平行的长方体(立方体)包围盒(GetAabb)
  3. 获取物体在以当前线速度和角速度保持运动一小段时间(time Step)之后的AABB包围盒
球形包围盒
球形包围盒直接的碰撞检测比较单纯,如下图。当两球心距离 d>r_{1}+r_{2} 的时候,碰撞未发生。反之,碰撞发生。
但是,虽然公式很简单,计算量却不是最小的。这是因为空间任意两点之间的距离为原点到这两点的向量的差、所得到的向量的长度。向量的长度计算涉及到乘方与开方,是比较慢的计算。
图片来自网络:http://jccc-mpg.wikidot.com/intersections-and-collision-detection
AABB包围盒
AABB包围盒是长方体包围盒的一个特例,它的长宽高平行于坐标轴。也就是说,没有旋转。AABB包围盒不见得是(或者说很多时候不是)最小的长方体包围盒。但是因为它没有旋转,所以有以下这样非常好的性质:
  1. 当且仅当两个AABB包围盒在各个坐标轴上所对应的(投影的)区间都发生重叠的时候,两个AABB包围盒才相交。
这就是说,对于AABB包围盒的碰撞检测,我们可以检测其在每个坐标轴上的投影。只要有一个坐标轴上的投影不重叠,那么两个AABB包围盒就不发生碰撞。
虽然对于最坏的情况(发生了碰撞),我们需要在x,y,z三个轴上各自进行一次区间是否重合的检测,但是每次检测实际上只是分别比较两个投影区间的最小值/最大值,这对于CPU/GPU来说是非常简单的操作,计算量很低。
图片来自网络:http://myselph.de/gamePhysics/collisionDetection.html
好了。有了这个基本的几何体类,我们就可以从它派生生成各种具体的几何形状的类了。比如球体:
长方体:
等等。我们可以这样不断添加我们所需的几何体来丰富我们引擎的功能。
下一篇我们将尝试将这些几何体可视化,并且实现一个我们自己的碰撞检测模块。
关于Windows版的连续集成
之前我们使用Circle CI实现了Linux/MacOS/Android三种平台的连续集成。但是因为Circle CI不支持Windows的连续集成,所以这个问题一直放置到现在。
好在另外有一个名为AppVeyor的云服务商为所有GitHub上的开源项目提供了免费的Windows的连续集成环境,在本篇的代码当中我们利用了这个环境。
使用方法非常简单,在AppVeyor网站完成项目注册之后,同样是通过一个YAML文件来描述所需要做的工作。对于我们这个项目,这个文件如下:
只不过目前这个文件好像只能放在项目根目录下,与Circle CI的目录结构稍微有些不一样。
关于编辑器
如我在系列开篇所述,可能是由于历史原因,我更喜欢使用命令行。相应的,作为命令行当中的优秀文本编辑器-VIM,是我用来写本系列代码的主要工具。
但是这并不是说我推荐使用VIM,或者反对其它的编辑器。其实编辑器的选择只有一个标准,那就是自己用得舒服即可。
其实最近我也在用VS Code,很好用。强烈推荐。

从零开始手敲次世代游戏引擎(三十九)

从零开始手敲次世代游戏引擎(三十八)当中我们使用bullet实现了一个基本的场景物理仿真,但是没有对游戏当中所使用的物理仿真进行一些最基本的解说。本篇我们就来简要看一下是怎么做到的。
如前一篇所说,游戏当中用到的物理仿真,一般包括以下两个主要的环节:
  1. 碰撞检测:主要用来检测当前帧当中的几何体是否发生了碰撞;
  2. 运动学(力学):主要用来推算下一帧当中几何体的位置。
碰撞检测的理论基础是我们高中所学的解析几何。由于复杂几何体的解析表达十分复杂甚至不存在,对于游戏这种软实时系统,一般是采用基本几何体替代场景当中的复杂几何体来进行碰撞检测的。这些基本几何体被称为碰撞模型,也称为碰撞包围盒。
被作为碰撞模型使用的基本模型一般有如下几个:
  1. 平面。平面在其延展方向是无限大的。比如方程 z = 1z = 1 就描述了一个平行于x,y轴的面积为∞的平面;
  2. 球体。球体可以通过球心坐标和半径方便地描述;
  3. 长方体(立方体)。可以通过其中心坐标,以及长、宽、高进行描述;
  4. 圆柱体。圆柱体可以通过其中心坐标,底面半径及高描述;
  5. 圆锥体。与圆柱类似;
  6. 胶囊体。是一个圆柱和两个半球体的复合。一般用来作为游戏当中人形角色的包围盒,相对圆柱形的平底,半球形的底面对于地面的坡度或者较小的起伏有较好的适应性。
  7. 三角形。虽然是平面图形,但是我们在之前已经知道了,游戏当中的几何体一般都是用一连串的三角形描述的。所以对于不能使用上面这些基本形的情况,我们依然是使用一个三角形组成的网格模型,只不过一般顶点数远小于渲染用模型的低模,来进行碰撞检测。
这些基本形状的碰撞检测的原理就是解析几何当中的求交点计算。当然这是有相当计算量的,所以在游戏当中会采用很多手段来减少计算量,比如使用AABB算法来避免不必要的求交计算。
而运动学则主要是根据牛顿三定律计算物体的运动和位置的变化。
比如下面这么一个场景:
那么我们可以为每个台球绑定一个球形的碰撞模型,而为球台绑定一个长方形的碰撞模型。至于球杆,我们可以绑定一个圆柱体。当我们按下键盘上某个按键的时候,我们给白色的母球加一个100牛顿的力,那么就得到如下这么一个仿真的结果:
 
 
视频封面

上传视频封面

 
 
球之所以会从球台边界跑出去,是因为目前我们给球台绑定的还是一个非常基本的长方形形状,所以球台边界和球台里面是一样高的。就导致了这个现象。
我们可以通过绑定更为复杂的形状,或者在球台边界绑定额外的长方形,来解决这个问题。
关于游戏逻辑
我在前面的文章当中也提到了,游戏逻辑本身并不应该是游戏引擎的一部分。游戏引擎提供接口给游戏内容开发者编写游戏逻辑。
因此在本篇的例子当中,我对我们的项目代码结构进行了重组,新加了一个游戏逻辑基类:GameLogic,并且改变之前将引擎代码直接编译成为可执行文件的做法,取而代之的是将其编译成为库文件,最终与Game目录下的从GameLogic继承而来的具体游戏逻辑进行链接,得到最终的可执行文件。
当然,仅仅这样其实还是远远不够的。为了封装成为一个可以复用的游戏引擎,我们接下来至少还需要做如下的工作:
  1. 将头文件分离出Private和Public版本。Private是编译引擎的时候参照的,具备完整的信息,而Public版本只暴露二次开发时需要知道的接口。这样做可以进一步分离游戏引擎和游戏本身,方便游戏引擎的版本升级;
  2. 统一不同RHI的Shader编写方式,导入一个中间方式(如:Nvidia CG),并且编写相关的转换工具;
  3. 对Asset目录进行区分,将引擎所用资源和每个游戏所用资源分开;
另外一方面,我们的游戏引擎现在虽然有了基本的图形渲染、输入、物理仿真模块,但是从功能上还缺少诸如AI、动画、视频播放、音频音效等部分。
另外从开发调试以及优化的观点,我们还缺少驱动模块(用来调整不同模块的执行频率以及CPU多核心调度)、Profiling及调试模块等。
最后我们还需要有编辑器,方便对导入的资源进行简单的修改,以及场景结构的安排等。

从零开始手敲次世代游戏引擎(三十七)

从零开始手敲次世代游戏引擎(三十六)文末所预告的,我们暂且将图形渲染告一个段落,开始一些其他模块的基本编写工作。本篇将探讨用户输入模块的编写。
我们知道,电脑一般是以键盘和鼠标作为主要的输入设备;而手机则是主要依靠触摸屏以及内置的重力加速度传感器/陀螺仪;游戏主机设备则一般是游戏手柄输入。
虽然外形和使用方法差别明显,但是对于电脑系统来说,这些都是外设,而且是低速外设。这些设备多通过串行总线(比如USB)与计算机系统相连。
由于操作系统的一个重要职能就是管理硬件设备,而且设备可能会被多个程序所共享,因此在我们一般不需要直接与这些硬件设备的驱动直接打交道,而是通过操作系统所提供的接口进行访问。这也意味着,在不同的系统上我们会遇到不同的接口,即使是同一个类型/型号的硬件设备。
除了本世纪兴起的体感类游戏之外,传统的游戏一般以开关量输入和模拟量输入为主要控制输入信息。开关量就是指诸如键盘按键、鼠标按键、手柄按键那种,只有按下和非按下(弹起)这两种状态的控制量;而模拟量输入则是指诸如手柄摇杆或者近些年手柄两肩上的板机那样,在一个范围之内可以连续改变其角度从而产生一个连续变化的输入的控制量。
我们首先来使用键盘当中的光标方向键来模拟开关量,控制模型的转动,像下面这样:
视频封面

上传视频封面

首先我们需要在Framework/Common当中新建一个Runtime Module: InputManager,其中包含平台无关的四个方向键的按下和恢复(弹起)响应函数:
然后我们需要将各个平台的按键消息与其挂钩:
Mac OS
我们需要将Cocoa当中的按键消息(NSEventTypeKeyDown, NSEventTypeKeyUp)与InputManager进行挂钩,大致是下面这么一个样子:
Windows平台
我们需要将Windows消息当中的(WM_KEYDOWN, WM_KEYUP)消息与InputManager的方法进行挂钩,大约是下面这个样子:
Linux
我们需要将XCB Event当中的(XCB_KEY_PRESS, XCB_KEY_RELEASE)与InputManager的方法进行挂钩,大致是下面这个样子:
这里需要注意的是XCB返回的是键盘的扫描码。这个扫描码实际上是指的按键的物理位置(电气位置),在不同类型的键盘上是不一样的。我这里简便起见直接使用了扫描码,但是这其实是不对的(没有通用性)。实际上还应该需要根据系统提供的键盘配置文件将扫描码转换成为按键名称之后才对。
映射完成之后,我们需要在InputManager.cpp当中添加这几个按键响应对于场景的操作逻辑。这部分其实才是日常的游戏开发当中所说的游戏程序(逻辑)的重要一部分。也就是说,我们目前到此为止所写的代码多属于游戏引擎的开发,而游戏内容的开发(使用游戏引擎开发游戏)的编程工作则主要是编写用户输入是如何影响游戏场景(当然也包括AI输入等)。
因此,这部分应该是可以由引擎使用者改写的。在软件行业这叫“支持二次开发”。这又是一个很深的坑,因为我们需要封装我们的引擎接口,选择需要支持的二次开发语言(比如Lua、JavaScript、Python、C#或者是C++),并提供一整套相关的工具。这些我们在后面会通过许多篇文章来进行。这里我们首先采用Hard Coding的方法来快速测试。
首先我们在Framework/Common/GraphicsManager.hpp当中删除按照时间自动旋转模型的代码,并暴露两个新的方法:
第一个方法表示将模型按照X轴进行旋转,第二个方法表示将模型按照Y轴进行旋转。参数radians表示旋转的弧度。我们的引擎采用右手坐标系,所以radians为正表示逆时针旋转(当👀朝着坐标轴-方向看的时候),而为负表示顺时针旋转。
然后我们在InputManager.cpp当中,根据不同的按键调用这两个方法就可以轻松实现如上面视频所示的用按键对模型旋转的控制了。比如下面这样:
关于演示用模型
演示用模型来自参考引用*1,许可证类型为个人使用(非商业用途)。一些贴图为TGA格式,所以我根据参考引用*2在Framework/Parser之下新增了TGA文件格式的解析器。TGA格式很简单,所以就不另外写单独的特别篇来阐述解析器的编写了,有兴趣的请直接看本篇对应的代码。
 
参考引用:
图标

从零开始手敲次世代游戏引擎(Android特别篇)-3

在文章从零开始手敲次世代游戏引擎(Android特别篇)-2当中我们完成了执行环境的部署,并打通了开发环境和执行环境。但是到目前为止我们只是完成了C/C++部分的交叉编译,并没有实现Android应用程序的开发。
事实上,Android是一套基于Linux上Java虚拟机的Java程序集团。也就是说,与之前我们开发macOS版类似,我们无法在C/C++当中完成与系统各项服务:如窗体管理/输入输出管理等的交互。在macOS当中,我们写了Object C++代码来桥接Cocoa和我们的引擎;在Android当中,我们需要通过JNI glue来桥接Java和C/C++代码。(JNI = Java Native Interface,Java本地代码接口)
参考引用*1为我们展示了在Java Code当中调用C/C++代码的方法。然而,采用这种方式的程序其主循环(Main Loop)仍然是在Java代码当中。这样的做法对于一般大多数应用程序来说是可以接受的,但是对于诸如游戏引擎这类对于性能要求比较高的场合,是不太合适的。
如果做过一些Android Java开发的人应该知道,Android的应用开发其实某种程度挺类似于网页开发,GUI开发的基本单位是Activity,每个Activity包括一个界面(可以通过基于XML的resource文件定义)和一组控制这个界面的程序(Java),Activity之间的迁移通过暴露Intent接口来实现。这与Web开发的网页(通过HTML编写)+脚本(JavaScript)+ URL参数的方式是十分类似的。
所以,为了实现高效的本地代码,最好是能够用C/C++直接写Activity,而不是在Java编写的Activity当中通过JNI去调用C/C++写的功能Function。
当然我们并不是第一个吃鸡的人。这类问题在早期的Android版本当中是不好解决的,但是在今天,由于商业引擎的推动,较新的Android版本当中已经有了比较好的解决方式:Native Activity。参考引用*2为我们展示了这个Native Activity的使用方法。
让我们将参考引用*2的代码下载下来,放到我们的代码树的Platform/Android目录(新建)下。然后我们启动我们的docker容器(切换到Android开发环境),在Platform/Android目录下执行:
就可以编译生成这个Sample的APK文件了。这证明了我们的docker环境是正常的。
(这里面有个小细节。Google Samples当中的代码似乎已经有一段时间没更新了。对于Native Activity这个Sample,其依赖的“com.android.support.constraint:constraint-layout:1.0.1”这个组件已经过期。如果编译的时候提示找不到这个包,请将其改为“com.android.support.constraint:constraint-layout:1.0.2”。具体位置是在app/build.gradle当中)
(可以从这里下载编译生成的APK安装包。注意是开发包,没有进行签名,系统会提示安装风险,请自行判断)
执行的效果如下:
 
 

视频封面

上传视频封面

 
 
有了Google官方的Sample,接下来我们需要解决的问题主要就是如何将Android标准的基于Gradle的项目与我们的基于CMake的项目统合起来。
一种首先可能会想到的方法是,我们采用从零开始手敲次世代游戏引擎(Android特别篇)-1当中介绍的方法,先将我们的引擎代码编译称为动态库(libMyGameEngine.so),然后在Android应用当中引用这个库。也就是说,我们需要分开的两个步骤,第一次编译引擎,第二次编译应用。
其实在参考引用*2当中,已经为我们展示了直接在Gradle当中进行CMake的调用,于应用构建的过程当中自动构建本地代码模块的方法。如果我们打开参考引用*2的app/build.gradle文件,可以看到如下的内容:
红框所示部分,就是通过Gradle调用CMake的关键。
不仅如此,Gradle还会自动将CMake生成的生成物保存到Gradle的编译目录,所以我们只需要在我们的AndroidManifest.xml当中直接引用我们的引擎动态库就可以,而不必关心它会被放在什么地方。
上图最后一行的MyGameEngine,就是我们动态库的名字。注意在Linux环境当中,编译出来的实际文件名是libMyGameEngine.so。但是这个前缀“lib”和扩展名“.so”是不需要指定的。
为了生成这个动态库,我们需要在Platform目录下面新建Android目录,并且参照参考引用*2当中的写法,如下书写CMakeLists.txt
其中,AndroidApplication.*,OpenGLESApplication.*是将参考引用*2当中的代码,按照我们的架构和继承关系进行分解之后的产物。而AndroidAssetLoader.*,是从AssetLoader派生出的子类,原因是当我们最终在打包APK(APK是Android上面的安装包)的时候,如果将Asset目录下的资源打包进去,那么这些资源其实并不会在安装之后展开到安装对象的文件系统当中,而是继续以压缩文件的方式存在(APK文件其实就是一个ZIP压缩包。Java编译之后的jar文件也是一个ZIP压缩包)
这就是说,在这种情况下,通过通常的fopen/fclose/fread系列的API我们是无法读取到资源文件到,而是需要通过Android NDK提供的特殊接口,AAssetManager去读写这些文件。所以我们这里单独派生出了一个类来对应这个特别的需求。
将资源文件打包进APK的方法是,在app/build.gradle当中添加sourceSets,然后指定从哪里拷贝资源文件:
好了,在进行完这些改造和代码的重组之后,我们可以通过在Platform/Android目录下执行./gradlew assembleDebug来完成整个项目的编译构建工作。(需要在安装了Android SDK/NDK的环境当中进行)
代码在下面这个链接当中。目前在模拟器上运行是OK的,在我的Huawei P9上面仍然有问题,尚在Debug当中。
图标
本地代码(C/C++)调试方法:
与PC本地开发不同,嵌入式开发由于代码执行环境与开发环境是分离的两个环境,无法直接使用调试器(gdb / lldb)启动并调试可执行文件。这里需要用到的就是调试服务(如gdbserver)
方法是,首先将预先交叉编译后的调试服务程序推送到目标机器。对于Android,在NDK的prebuild目录当中提供了预先编译好的gdbserver。使用adb push命令推送过去就可以了。注意需要根据目标机器的CPU选择正确的版本:
(注意推送之后需要添加“x”属性)
然后,通过adb shell命令启动gdbserver,并指定需要调试的程序,以及gdbserver侦听的TCP端口号(用于接收来自开发环境的调试命令)。因为这个命令不会自动退出,需要在最后指定“&”参数将其置于后台,以便我们继续输入命令:
然后,通过adb forward命令,将运行环境当中gdbserver侦听的端口映射到开发环境当中:(实质上是ssh port forwarding)
然后在开发环境当中启动gdb。NDK当中有提供这个客户端,在下面这个目录当中
$ANDROID_NDK_HOME/prebuilt/linux-x86_64/bin/
启动之后,输入下面这个命令,连接运行环境当中的gdbserver:
之后就如同在本地使用GDB一样,通过b命令设置断点,s命令单步等。不再赘述。
对于被打包在APK当中的C/C++代码,因为该代码由Java启动(即使使用Native Activity,其实程序仍然是从Java层启动的)。也就是说,在运行环境里面并没有可以启动这个应用的可执行文件。对于这种情况,首先需要通过手点击主菜单应用程序的图标,将程序启动起来,或者(对于我们这种使用docker没有window的情况)使用如下命令启动应用:
然后使用
列出执行当中的应用进程,查找我们的应用程序的进程号码(下图星号所示):
然后执行:
来启动gdbserver。其它的相同。
如果程序一启动就崩溃,那么这种方式显然赶不及,那么还需要在“设置 > 开发者选项”当中打开“等待调试器”。不过这一项通常是无效状态,需要在“选择调试应用”当中首先指定被调试应用,这一项就可以选择了。打开之后,应用程序启动会立即中断,等待我们将gdb连通之后,输入“c”命令,就可以继续执行了。
 
Circle CI的自动化测试
采用Docker环境的好处是我们可以直接在Circle CI当中完成大多数不需要人工参与的自动化测试。我们可以将到此为止所写的整个编译以及构建执行环境、打通与开发环境的连接的操作全部写到Circle CI的YAML脚本当中,从而完成程序的自动测试。相关脚本请直接参考GitHub上的源代码当中的.circleci/config.yml文件。
并且,Circle CI支持将编译结果保存提供下载。上文当中提供的APK下载就是采用的这种方式。具体做法同样参考上述配置文件。
 
关于Android环境下的调试输出
我们的引擎目前是直接将调试信息输出到stdout / stderr,但是在以APK形式安装的程序当中,stdout / stderr是被重定向到/dev/null,也就是被丢弃的。因此,为了能够看到我们的Log,我们需要将Log重新定向到NDK所提供的机制当中。具体的做法有三种:
  1. 修改我们的代码,将相关代码替换成Android NDK的接口。但是这显然对于跨平台的代码来说不可接受;
  2. 编写专门的调试模块,并且对于不同的平台采用不同的输出方法。这个在我们后续的文章当中会有介绍;
  3. 利用Unix/Linux的管道和重定向机制,在应用程序里面另外启动一个线程,从我们的主线程接收Log并且将Log输出到NDK的接口当中。这个是本篇采用的方法。具体实现在Platform/Android/AndroidApplication.cpp当中。
另外,查看这个Log输出的方法是使用下面的命令:
但是这个命令会输出所有的log,包括我们的,包括系统和其它应用的。NDK提供的Log接口当中可以指定一个Tag,在我们的例子当中,我们指定了“MyGameEngine”作为我们的Tag,所以我们可以通过下面使用这个命令这样来过滤:
这样我们就可以看到大量我们的程序输出的关于重力加速度传感器的读数:(下面的数据因为是在模拟器当中采集的,所以不变)
参考引用
图标
图标
图标
图标
图标
图标
图标
图标
图标

从零开始手敲次世代游戏引擎(Android特别篇)-1

本篇开始我们将我们开发的引擎移植到Android上面去。
首先我们需要构建Android的开发环境。无论是基于Windows的Visual Studio,还是基于mac OS的XCode,亦或是基于java的Eclipse,以及google的Android Studio,都能够支持Android的开发。
不过一如既往的,我讨厌在项目代码树当中混进某种IDE的杂七杂八的文件,所以我选择使用命令行环境。当然,IDE环境在调试的时候很方便,我们可以用cmake随时生成IDE的项目配置文件,在IDE当中进行编辑调试。
由于我们的代码支持多平台,我时常需要在不同的操作系统之间切换编写确认代码。在每一个系统上安装一套android SDK/NDK环境会变得费时费力,且不容易保持环境的一致性。况且我们需要使用Circle CI进行连续集成,这个环境最好是能够很容易在不同的物理机/操作系统间迁移的。docker能很好的解决这个问题,参考引用*2展示了一个基于Ubuntu的安装了android SDK/NDK的典型docker环境的构筑方法。
为了能够在Mac上面使用Docker,我们首先需要安装Docker服务。安装的方法请参考参考引用*1。如果是Windows或者Linux环境,其安装方法也可以在该页面的左侧导航栏当中找到。
安装完成之后,在命令行通过下面的命令,就可以启动并进入这个环境:
参数选项“-it”表示我们需要以交互的方式进入这个docker,“-v $(pwd):/project”表示把当前的目录映射到docker当中的/project目录,也就是将我们的代码树挂载到docker当中的/project目录。这也隐含着执行这个命令的时候需要在我们的项目代码根目录下。“tim03/android-sdk-ndk”是使用参考引用*2构建的docker容器名称,也就是包含了android SDK NDK的开发环境。“bash”是指docker启动之后进入Linux的BASH命令行。
进入之后,缺省是在根目录下,执行“cd”命令切换当前目录到项目根目录:
执行ls命令查看当前目录下是否包括了我们的源代码文件:
在之前我们虽然做了Windows / Linux / Mac OS三种平台的开发,但是这三种平台都是基于PC的平台,我们都是在其自身进行开发并编译的。(虽然其实我们在从零开始手敲次世代游戏引擎(七)当中简要介绍了一点儿在Linux平台编译测试Windows平台程序的一种方法)
而对于诸如Android平台(或者IOS平台,以及无法在这里公开介绍细节的PS4/PSV平台)的开发,是通过在PC平台编译程序,然后再推送到目标平台进行执行的。这种方式被称为交叉编译,是嵌入式开发的一种比较基本的流程。
对于用惯IDE或者商用游戏引擎的人来说,可能不太会注意到这里面的区别(因为在IDE或者商用游戏引擎当中,基本上只要在平台选项当中切换一下就好了,整个流程与PC开发基本相同)。但是如果深入到细节,那么会发现两者有着很多不同。总的来说,嵌入式开发要麻烦一些。
坚持使用命令行的一个好处就是,我们可以精确知道实际的步骤,了解当中的细节。在这个基础之上,选用IDE/商用引擎进行开发,提高工作效率;而当我们遇到一些难解的问题的时候,又有能力将IDE/商用引擎打包好的一系列自动化步骤进行手动拆解,查找问题,从而获得超越“泛泛之辈”的能力。
因为我们的项目是基于CMake的。CMake下进行交叉编译的方法是通过建立TOOLCHAIN File来实现的。
基于参考引用*3所提供的CMake文法规格,我们项目根目录下建立cmake/android.cmake文件如下:
  1. 第一行是告诉CMake我们要交叉编译的目标平台是Android。因为Android是CMake已经知道的平台,写入这一条能够让CMake找到正确的交叉编译工具;
  2. 第二行是指定我们程序对应的Android的API Level。因为我们的程序其实并没有什么很特别依赖Android功能的地方,这个版本其实不是非常的重要;
  3. 第三行是指定目标CPU的ABI(Application Binary Interface,应用二进制接口)。Android其实是支持诸如x86, x86-64, arm, arm64, mips, mips64等多个架构的。这里为了简便起见,我们只指定了armeabi-v7a接口。这个接口是32bit的接口,相对较老,但是支持浮点的硬件加速,在当今大多数基于arm的手机上都支持;
  4. 第四行是告诉CMake在编译的时候生成NEON代码。NEON是arm CPU上的SIMD代码集,相当于Intel CPU的SSE系列;
  5. 第五行其实在armeabi-v7a的时候没有啥用。如果我们在第三行指定的是armeabi,那么这行是告诉CMake生成32位代码,而不是16位代码;(嗯,在arm64满天飞的今天,16位代码的确已经很老了)
  6. 第六行是告诉CMake关于Android NDK的安装位置。这个“ANDROID_NDK_HOME”环境变量是我们在创建编译环境的时候导出的。具体可以参看参考引用*2的Dockerfile;
  7. 第七行是告诉CMake在编译的时候链接GNU c++库。Android NDK提供了好几套c++库,缺省是一套被称为“c++_static”的经过大量裁剪的c++库。因为我们的代码基于C++ 11,当中使用了一些c++_static当中不支持的功能,因此需要在这里指定gnustl_static。
好了。有了这个TOOLCHAIN文件之后,我们只需要在使用CMake进行编译的命令行当中,加入如下的参数选项,告诉CMake使用这个TOOLCHAIN文件,就可以实现PC->Android的交叉编译了:
完整的命令行可以参考本篇文章对应的代码当中的build_crossguid_android.sh
通过同样的方式修改项目根目录下的build_opengex.sh / build.sh,我们就能实现整个引擎到Android的交叉编译。当然,因为Android并不支持OpenGL(Android支持的是OpenGL ES,是OpenGL的一个子集)和DirectX,其实我们还需要修改RHI下面的CMake文件,以及Platform下面的CMake文件,去除这些库的编译。

从零开始手敲次世代游戏引擎(三十六)

从零开始手敲次世代游戏引擎(三十五),首先导入合并从零开始手敲次世代游戏引擎(PNG特别篇)当中所写的PNG文件解析器,然后手工编辑aili.ogex,向👀材质添加eye.png贴图。执行程序,可以看到👀已经有了。(不过我们可以发现眼睛其实只是浮在脸前方的一个片面。。。这个是建模的锅,不怪我。。。)

另外仔细观察可以发现右侧的头发(side hair)没有正确的着色。这是因为右边的头发是通过对左侧的头发进行镜像得到的。虽然在Blender里面看起来没有什么问题,但是这种镜像会导致两个问题:

  1. 导出的三角形顶点的旋转方向从逆时针变为顺时针,从而导致被GPU裁剪(Culling)掉;
  2. 导出的模型变换矩阵是下面这个样子:(以X轴镜像为例)

可以看到包括一个对X坐标去反的计算。而我们的shder里面有对于法线的这么一个计算:

其中的modelMatrix就是上面这个矩阵。这就导致法向量也被镜像,也就是出现反转。所以我们看到的就是上面屏幕录制里面那样黑漆漆的。

这个问题我们可以通过修改OGEX导出脚本来修正,或者在今后我们编写了我们的游戏引擎的Editor之后,在Editor里面修正。所以我们这里就暂时不作进一步的展开了。

好了,到这里我们对于图形渲染基本管线的搭建就暂时告一个段落。当然图形渲染是一个很深的坑,我们还有很多很多没有实现的东西,比如随便列举一些:

  1. 点光源之外的光源类型
  2. 多光源
  3. 阴影生成
  4. diffuse贴图之外的贴图,如法线贴图,位移贴图,等等
  5. VS和PS之外的Shader,如Geometry Shader, Compute Shader等等
  6. 图像后处理

在场景组织和管理方面,我们也有很多可以进一步完善的东西,如:

  1. 场景物体的层次结构,分组和定义在组级别的坐标变换
  2. 场景的异步加载

等等。但是在继续深入介绍这些东西之前,作为一个游戏引擎的运行时,我决定先进行其它几个重要模块的基本构建,比如输入模块,驱动模块,策略模块,调试辅助模块等等。


接下来说一下工程方面的进展。感谢CircleCI,在之前免费的Linux环境的基础上,为我免费提供了基于macOS的连续集成环境。现在每一个push到github上的commit,都会自动进行Linux和macOS两个版本的编译和测试用例的执行确认,如下图:

实现起来也很简单,如下面这样修改我们的circleCI的脚本即可:

确实非常方便,欢迎大家在自己的项目当中也多多尝试。再次感谢CircleCI对于OpenSource项目的大力支持!

(最近一直在生病😷,文章更新的比较慢了,请多多包涵)

最后顺便说一句,第一届中国大学生AR/VR竞赛昨天拉下帷幕。虽然大赛自身的组织有很多的仓促,但是同学们的作品真的都很棒。期待大家加入游戏开发的大家庭。

从零开始手敲次世代游戏引擎(PNG特别篇)

从零开始手敲次世代游戏引擎(三十五)当中我们完成了衣裙贴图的加载和绘制。但是所谓画龙点睛,我们的模型目前仍然是没有?的。之所以这样,因为眼睛的贴图是PNG格式的,而目前我们只写了BMP和JPEG格式的解析器。
那么让我们立即开始PNG格式解析器的编写。
经过BMP和JPEG格式的锤炼,我们对此应该已经是比较驾轻就熟的了。首先依然是从FrameWork/Parser当中现有的代码拷贝生成PNG.hpp,然后根据参考引用当中的PNG格式的规格说明,修改这个代码。
与JPEG格式类似,PNG格式也是将数据组织为Chunk单位进行存储的。其Chunk的头部通过4个ASCII字母(8bit)类型进行标识。比较有意思的是,在这个4字母的标识符当中,PNG格式使用了字母的大小写来表示Chunk的一些属性。比如:
  1. 第一个字母大写表示该Chunk是一个基本Chunk,也就是PNG标准规定的必须有的Chunk。相对的,如果小写则表示该Chunk是一个扩展Chunk,也就是说是可有可无的;
  2. 第二个字母大写表示该Chunk表示符是经过国际标准化组织标准化过的,而小写则表示是未经标准化由应用私自扩展的(也就是说如果小写,表示这部分是没有互换性的);
  3. 第三个字母目前必须大写。小写保留给今后,目前还没想好有什么用;
  4. 第四个字母表示这个Chunk能否原样复制到经过处理之后的图片当中,即使我们并不知道这个Chunk是用来干啥的。如果小写,那么我们可以无脑地将其复制到处理之后另存的图片当中,即使我们不知道这个Chunk的含义;如果大写,那么如果我们对第一个字母为大写的Chunk进行了任何修改,就不能原样复制第四个字母为大写的Chunk。换句话说,第四个字母表示该Chunk当中的数据是否对第一个字母为大写的Chunk有依赖性。
图片的数据是存储在IDAT这个chunk里面。将数据提取出来之后,首先要将其解压缩。与JPEG不同,PNG文件格式是无损压缩格式,它采用得数据压缩就是LZ77,也就是我们熟知的zip压缩包采用的压缩方式。(严格来说,zip当中可以有多种压缩算法,一些是被申请了专利的。而LZ77是public的)
LZ77压缩也可以理解为一种动态的霍夫曼编码,细节上与JPEG采用的霍夫曼有一点不同。我们可以基于之前在JPEG解析器当中编写的霍夫曼树的代码编写LZ77的解压缩代码。也可以导入成熟的库-zlib。我这里采用的是后者。
zlib的使用方法可以参考参考引用*5。
在完成解压之后,需要对数据进行反过滤(defiltering)。为了提高压缩率,我们需要减少数据的带宽,也就是减少数据的统计方差。更为通俗一点来讲的话,我们需要让数据尽可能地集中在0的两边,而不是分布在取值范围所容许的所有值上(0-255)。
在前面介绍的JPEG当中,我们是通过一个被称为quantization的过程实现这个目的的。而在PNG当中,使用一种称为prediction(预测)的算法实现这个目的。这个算法其实是利用图像的连续性,使用当前像素周边已知的像素值来预测当前像素的值。(在数学意义上,就是相当用偏导数替代值)。对于大多数图像来说,导数的变化幅度要远低于值的变化幅度,从而能够起到减少带宽的目的。
对于这个偏导数的选择(也就是用周边的哪个或者哪几个像素预测当前像素的值),PNG规范规定了几种方式,并且以行(Scan Line)为单位,对方式进行了选择。也就是说,在解压出来的数据当中,每行数据的第一个字节,并不是图像数据的一部分,而是对于这个预测公式的一个选择参数。
最后完成的代码在这里:
运行测试的结果如题图所示。
注意目前的代码只考虑了color type为6,也就是rgba类型的非索引png图片格式。其它的类型稍加修改就可以对应,但是目前还未编写。
参考引用
  1. https://en.m.wikipedia.org/wiki/LZ77_and_LZ78

从零开始手敲次世代游戏引擎(三十五)

从零开始手敲次世代游戏引擎(三十四)。我们开始导入材质。最终效果如下:
(本文所使用3D模型及贴图来自于ermmus制作的小萝莉(AILI)。许可证类型:CC-BY。感谢无私的分享精神)
 
 
视频封面

上传视频封面

 
 
首先作为第一步,我们导入材质的基本参数。我们需要进一步完善我们在从零开始手敲次世代游戏引擎(二十九)所写的SceneNode,SceneObject的结构,导入包括材质的基本颜色(diffuseColor),高光颜色(SpecularColor)和高光系数(SpecularPower)等颜色/参数。然后我们需要修改我们的GraphicsManager(在这里我们暂时只实现了OpenGLGraphicsManager),让它能够将这些材质参数传递给我们的Fragment Shader。最后是修改我们的Shader,将我们之前写死在Shader里面的材质参数,替换成uniform类型的变量。
下面是所有这些变更的代码:
变更之后的效果如下:
 
视频封面

上传视频封面

 
 
可以看到一部分材质已经应用上去了。最为明显的就是面部、手、脚这些裸露的部分。
至于衣裙以及?,这些是使用的基于贴图的材质。主要是这两种:
AILI: Textured by ermmus Creative Commons Attribution 3.0 CC-B
AILI: Textured by ermmus Creative Commons Attribution 3.0 CC-B
可能是因为我所使用的OGEX导出脚本与Blender的版本不匹配的问题,导出的aili.ogex文件当中并没有到贴图的链接。不过OGEX文件是文本文件,很容易编辑。我们可以手动加上去:
 
 
同时检查模型的UV坐标(也就是贴图坐标)已经正确的导出了:
然后我们结合我们在从零开始手敲次世代游戏引擎(JPEG特别篇)-3开发的成果,将贴图也加载进来。相关的代码在
接下来我们需要将贴图通过图形API接口从CPU传递到GPU,并且修改我们的Shader以及初始化Shader的代码,将UV坐标正确地传递给GPU。相关的代码在:
这样我们就完成了一个基本的贴图导出和加载的过程。最后的效果在本文开篇已经展示了。

接下来讲一些工程方面的事情。
我们现在代码已经有了一定的规模,而且支持多个平台,不同的RHI(图形渲染API)。在这样的情况下,每次对代码进行了变更,是应该在各个平台进行测试的。
这个过程十分重要,但是如果手动操作会十分的耗费时间,并且单调乏味。
事实上,行业当中一般采用“连续集成”(CI = Continues Integration)来对应这个需求。大一点的软件公司都会有专门的人/部门负责这部分工作。
所谓CI,就是指使用一套自动化流水线工具,当代码发生更新的时候,自动的按照既定的步骤对代码进行编译、测试、分发的过程。
我们的代码托管在GitHub上面,GitHub提供了CircleCI的集成,并为开源项目提供了免费的配额。开通了CircleCI的集成之后,通过十分简单的配置,CircleCI就会对我们每一个提交进行自动化编译与测试,并将结果显示在GitHub当中,如下图这样:
画面当中绿色的勾就是CircleCI添加上去的测试结果。上面是按照branch进行显示的,我们还可以按照commit进行显示:
CircleCI不仅支持Linux版本的CI,也支持macOS版本的CI。不过macOS版本的服务缺省是不免费提供的。目前我正在和CircleCI协商是否可以获得相关免费资源。
设置CircleCI的方法很简单。点击下面这个链接,然后按照页面提示进行就可以了。
对于诸如Android/iPhone等标准开发流程(就是使用IDE进行开发的项目),CircleCI可以自动检测出项目编译和测试的方法。对于像我们这样的深度自定义产品,需要在项目文件夹里面新建一个目录和文件,描述我们项目的编译和测试方法:
.circleci/config.yml
 
参考引用

从零开始手敲次世代游戏引擎(JPEG特别篇)-3

从零开始手敲次世代游戏引擎(JPEG特别篇)-2我们写了一个最基本的JPEG文件解码器。当中采用的例子是一个只有白黑两种颜色的16×8像素的图片。
如果我们采用更为复杂的图片,会不会有什么问题呢?
接下来我们可以来进行这方面的确认。
首先我们使用GIMP这个开源的图像编辑软件创建一幅稍微复杂的,带有红黄蓝绿4个颜色的16×16的JPEG文件,如下:
在保存(Export)的时候,GIMP 会提示如下一些选项:(需要展开Advanced Options)
首先让我们尝试去掉所有的复选框的勾选。然后点击Export。这时候执行我们所写的解码器,最后输出的结果如下:
可以看到基本上没有什么问题,但是红色色块的部分R的值不是FF,而是FE;绿色色块的部分G的值虽然是FF但是B通道出现了个1;而蓝色色块的部分与红色色块的部分类似FF编变成了FE;至于黄色的色块,我们设定的颜色是FF E3 08但是还原出来的是FF E2 08。
由于这个误差出现的情况在蓝色和红色色块类似,而在绿色和黄色色块出现的情况不同,我们可以推测它是与颜色相关的阶段发生的误差,而不是诸如DCT等各个通道均等处理阶段发生的误差,更不应该是在Quantization阶段因为舍弃了部分绝对值较小的高频信号导致的。我们可以立即验证这一点:
我们当前的Quantization矩阵是
重新回到GIMP,将Quality从原来的90调节到100,其它保持不变:
我们会发现Quantization矩阵变成了下面这个样子:
也就是不对DCT矩阵进行任何缩放。这就会导致所有绝对值大于(0.5)的AC分量都被按原样保留,但是最终还原的RGB数据仍然是一样的。
所以,到这里我们至少有两个收获:
  1. 在导出JPEG时设置的品质参数Q,实际上是控制着Qunatization矩阵的内容。Q设置得越高,Quantization矩阵当中的值就越大,DCT矩阵按元素与Quantization矩阵相除并取整之后得到的0⃣️就越多,压缩率就越大,但是也意味的越多的高频信号被丢弃,图像的锐度(细节)丢失得越多;
  2. 在色空间变换的时候,会产生颜色的轻微改变。
这些知识对于游戏开发的时候的(特别是美术同学)的提示至少是,
  1. 首先,对于需要严格指定颜色的情况,不要使用JPEG格式导出贴图;
  2. JPEG格式更加适合实拍的贴图,而不适合手绘的贴图;
  3. 设置比较高的Q参数可以得到比较好的细节,但是这对于矫正和原图的色差没有什么帮助。
然后我们来看导出选项当中的Optimization选项。在☑️这个选项之前,我们得到的密码本是和上一篇差不多的那一长串。在☑️之后,密码本如下:
是的,你没看错,这就是全部4个密码本。是不是比上一篇单个密码本还小?
所以☑️这个选项的用途就是,缩小密码本的大小。在密码本当中只包括实际用到的值,而去掉那些没有用到的值。而且,索引也是经过优化的,变得更短了。(因为值少了,我们可以用更短的学号(索引))
所以这里学到的是:
  1. ☑️Optimization选项可以减小导出的JPEG文件的大小,并且不会对还原出来的图片质量造成任何损失。
好了。关于JPEG的导入这里就暂告一个段落了。

从零开始手敲次世代游戏引擎(JPEG特别篇)-2

(首先说一下,这篇会非常难看。但是如果动手去做了,会对各项能力有极大的提高)
我们现在有了核心的算法库,接下来就是实际读取JPEG文件并进行解码了。
首先,JPEG标准(参考引用*2)定义了JPEG交换文件的大的框架结构。
其次,JPEG文件有JFIF和Exif这两种主要的具体实现格式。我们先来看JFIF。JFIF的格式可以参考(参考引用*1)
总的来说,JPEG文件是一个二进制文件,当中包括了一系列以0x FF xx作为开始标记的数据段(Segement)
每个数据段的格式基本如下:
  1. 首先是2个字节的标识符,以FF开头。如 FF C0;
  2. 然后是2个字节的长度,表示该段的长度(有例外,比如包含实际图像数据的SOS段);
  3. (这里需要注意的是,首先,JPEG当中所有的二进制存储都是Big Endian的,或者说是按照网络字节顺序存储的。对于两个字节以上的数据类型,是按照从高位字节(MSB)到低位字节(LSB)的顺序进行存储的,这与X86架构的存储方式是反的;)
  4. (其次,这个长度不包括标识符的2个字节,但是包括其自身的2个字节;)
  5. 接下来的内容则根据段的类型决定。
所以,我们首先需要定义这些段(头)的结构。我们从Framework/Parser/BMP.hpp拷贝新建Framework/Parser/JFIF.hpp,然后根据(参考引用*1)(参考引用*2)当中的(segment header)定义,编写对应的结构体(代码有删节):
然后,我们循环检测段的开头标志,用上面定义的这些结构体将存储在段头结构当中的数据提取出来,大致是如同下面这么一个感觉(有大量删节):
其中,0x FF DA(SOS, Start Of Scan)是实际图像数据存储块开始的标志。当我们检测到这个标志的时候,我们就可以开始Dump图像的数据,直到遇到0x FF D9(EOI, End Of Image)为止。
不过这里面需要注意的问题是,实际上图像数据里面,也会出现0x FF这样的值。为了不让其打乱我们的定位标志,JPEG标准规定,对于图像数据当中出现0x FF这样的情况,在其后立即插入0x 00,也就是以0x FF 00来代表0x FF。(同时,JPEG标准规定,不存在0x FF 00这样的段标志)
上一篇文章当中我们也提到了,JPEG是将图像分割成为8×8的图像块进行编码的。(参考引用*3)当中比较详细地介绍了手工解码一个十分简单的JPEG图像文件的过程。
在我们编程的时候,测试用例的选择同样是十分重要的。一个好的测试用例,可以大大加快我们开发的速度和质量。由于JPEG解码过程涉及到非常多的运算和类型转换,使用一个简单明确的数据样本可以帮助我们快速地找到问题。这里我选用了与参考引用*3相同的图片。这样我们可以将程序解码的每一步结果与文章当中提供的结果进行对比,快速找到问题。这个图片是这样的:
图片来自参考引用*3
太小?放大的话,如下(外框和虚线表示像素边界,不是原图片的一部分):
图片来自参考引用*3
是一个16像素宽,8像素高的图片。左边8×8是全黑,右边8×8是全白。
这么一个图片,在压缩之前是 16(像素(宽)) * 8(像素(高)) * 3 (字节/像素)= 384个字节。经过JPEG压缩之后,是304个字节到653个字节之间。
什么?653个字节?那不是更大了?是的,这是因为JPEG文件的构造当中,除了图像数据之外,还有很多记录图像属性以及压缩算法参数的元数据。因为我们的图片太小了,所以这些开销反而成为了大头。事实上,如果抛去这部分开销,压缩后的图像数据只有7到9个字节。
一般来说,JPEG的压缩率大约在1/5左右。当然这和很多因素有关。
我们接下来就来看这区区9个字节是怎么一步一步展开成为384个字节的。
经过上面的程序的处理,我们可以从文件当中的SOS和EOS这两个标志之间,提取出下面这9个字节的图像数据:
首先,如上面所说的,0x FF 00实际上是代表着FF。所以其实有效的数据一共有8个:
然后,这8个数据其实是一种变种的霍夫曼(Huffman)编码(参考引用*5)。霍夫曼是上个世纪50年代MIT的高材生。这种编码的核心思想就是,用尽量短的2进制bit代表最多出现的数据。
比如说我们有100个人,每个人有一个学号。如果其中有些人经常来上课,我们就给他一个短一点儿的号码。不太来上课的,我们就给他一个长一点的学号。这样的话,每次点名的时候,我们就可以少写一点儿字。
在计算机当中,所有数都是用二进制表示的。比如十进制8,用二进制表示是1000,这个长度就是4个bit;而十进制1,用二进制表示还是1, 这个长度就只有1个bit。如果在一个序列当中,8经常出现,而1出现的比较少,那么我们通过(强行)定义二进制1代表8,而二进制1000代表1,那么就可以缩短整个编码的长度,而不会丢失任何数据。
因此很容易可以想到,如果想要对一个序列进行霍夫曼编码,首先需要统计在这个序列当中基本符号的种类和出现频率。然后将基本符号按照出现频率从高到低进行排序,对于高的给予尽可能短的编码,对于低的给予稍长一些的编码,目的是使最终的整体码长最短。
这是一个算法问题。有兴趣的可以参考(参考引用*5)。我这里就不作更多的展开了。
我们这里需要实现的是霍夫曼编码的解码。绝大部分的解码,最终都是类似一个查字典的过程。首要的是构建这个字典(如果放在安全领域就叫密码本),然后根据索引一个个查出来就好了。
JPEG文件的目的并不是加密,所以这个密码本是放在文件当中的。这也是为什么在我们这个例子当中,压缩之后的文件反而变大的原因。
JPEG的密码本的起始标志是0x FF C4。我们在文件当中定位到它,然后将其提取出来。提取出来的结果大致如下(出于篇幅考虑只列出了部分):
竖线左侧的是编码(索引,密文),右侧的是值(词条,符号,明文)
这里需要注意的有以下几点:
  1. 虽然JPEG当中保存了这个字典(密码本),但是为了缩小文件尺寸(毕竟JPEG的目的是压缩),没有直接保存编码(索引,密文),而只是保存了值(词条,符号,明文)以及其在Huffman Tree当中的层级。我们需要自己根据这些信息重建Huffman Tree来生成索引;
  2. JPEG当中这样的字典(密码本)有4个。其内容是根据被保存的图片内容以及压缩品质设置变化的。在解码的过程当中会根据当前提取的数据状态使用不同的字典(密码本)(后面详述)
好了。接下来我们需要了解JPEG文件当中图像数据的组织形式。上一篇文章当中我们所提到的8×8分块,这个其实是最底层的组织形式。事实上,彩色图像会包括R/G/B这3个通道(注意普通的JPEG不支持Alpha通道,也就是透明度)。上一篇文章当中也提到,在JPEG压缩的过程当中,首先会将像素的色彩空间从RGB转成YCbCr。这样做的原因(或者说目的)是为了进一步减少文件尺寸。
不过单纯的RGB转YCbCr,这个是一个3个分量到3个分量的坐标轴转换,并不会直接带来数据的减少。秘密在于YCbCr的DownSampling。RGB三个通道都是彩色通道,其对于人眼的重要度其实是基本均等的(如果硬要说的话,G相对来说更重要一些)。但是到了YCbCr领域,Y(辉度)是最重要的(人眼的辨识度/敏感度最高),而两个色差信号就比较不重要一些。
所以,在变换到YCbCr之后,我们就可以将CbCr这两个通道的图缩小。意思是,比如8×8的图像块,Y通道仍然维持8×8的分辨率,但是CbCr这两个通道可以只保留4×4的分辨率,甚至只保留2×2的分辨率,就可以了。事实上,大部分的彩色电视信号,都是采用了这种方式来减少信号的码率。需要进一步了解的,可以参考(参考引用*6)
图片来源:Wikipedia
说了这么多,好像和前面的霍夫曼编码没有什么关系呢?
如果是原版的霍夫曼编码,那么只需要按照字典将“密文”一一翻译成为明文就可以了。然而JPEG当中的复杂性在于,它有4个密码本。什么时候使用哪个密码本,是和上面所说的YUV格式息息相关的。这是因为各个信号的统计分布很可能是非常不一样的。结合其特点使用不一样的密码本可以进一步减少压缩后的文件大小。
常规的做法是,对于Y信号(通道)使用一套密码本,而对于CbCr信号(通道)使用另外一套密码本。注意我这里使用的是“一套”,而不是“一个”。为什么呢?
因为单单是这样解释不了JPEG使用4个密码本的原因(看起来似乎2个就够了?)。这时候请回想起(或者如果还没有看过,请看)上一篇文章当中关于DCT/IDCT的介绍。经过DCT变换之后,矩阵的左上角(0,0)位置的值绝对值一般远大于矩阵当中的其他值。这个左上角的值被称为直流分量(DC。沿用电学称呼,在这里其实与电流没有任何关系)代表的是8×8像素块的平均值,它的统计特性与其他值(交流分量,AC。)也是非常不同的。
可能聪明的你已经猜到,其实JPEG不仅为不同的信道指定了(可能)不同的密码本,也为DCT当中的直流分量和交流分量指定了不同的密码本。所以实际上是这么一个分配情况:
  1. 用于Y通道DC分量的密码本
  2. 用于Y通道AC分量的密码本
  3. 用于CbCr通道DC分量的密码本
  4. 用于CbCr通道AC分量的密码本
下面是我们这个例子当中用到的Y通道的AC分量密码本,对比上面DC分量的密码本,我们可以看到它们是非常不同的(符号的数量远多于DC分量):
好了,有了这些知识储备之后,我们就可以解码那神秘的8个字节了:
在JPEG当中,是按照下面这么一个顺序存储数据的(这里以YUV444为例):
我们根据这个顺序反复替换对应的密码本,就可以得到Y,Cb,Cr三个分量的DCT矩阵。不过这里实际上还有一个秘密,就是被霍夫曼编码的其实并不是矩阵的值,而是关于矩阵的值的一个描述。具体来说:
将FC展开成二进制:
查阅Y(DC)密码本,可以得到前7位(1111 110)= 0x 0a。(为什么我们知道是前7位?仔细看看上面霍夫曼的编码(索引),你会发现在同一个密码本里面没有任何一个短的码会成为长的码的开头一部分。所以我们只需要一位一位的去匹配,直到找到对应的值为止。这就是霍夫曼编码的NB之处)
这个0x 0a其实并不代表Y(DC)的值是10。它的意思其实是说,接下来的10个bit是DC的值。所以我们从第8位开始往后取出10个bit,这才是DC的值。
这就是JPEG当中的霍夫曼编码与常规的霍夫曼编码不同的地方,被称为huffman / entropy coding。其目的当然是:为了进一步毫无人性地减少文件的尺寸。(提供以bit为单位,而不是byte为单位的存储方式)
这就是全部的秘密了吗?
并不是。JPEG是一个相当复杂的编码体系。接下来的AC部分,规则又有些不一样了。
原因其实也并不复杂。每个8×8矩阵里面,DC只有一个,位于(0,0)位置,但是AC有63个,并且大多数为0⃣️。学过算法的应该知道,这是一种典型的稀疏矩阵。下面是我们这个例子的左边8×8的Y分量DCT矩阵:
所以,如果按照DC的存储方式,即使是0,我们也需要为每个0分配存储空间(哪怕是1bit)。这个显然还不够省。
所以AC分量采用的编码方式是,在用于说明数据格式的那个字节(也就是被霍夫曼编码的那个字节当中)除了说明后面有几个bit用来表示AC分量之外,还说明有几个连续的零。但是因为其实这个说明符只有一个字节,所以其中的高4位用于表示连续的0⃣️的个数,低4位用于表示AC分量的bit数。这样的话,最多能够表示的连续的0⃣️的个数是15个。
这对于上面这种情况,还是不够省。所以JPEG又规定,如果数据说明字节的值为0,则表示从该位置开始之后到第64个矩阵元素的值都是0。
这就是全部的秘密了吗?
很可惜,虽然已经很复杂了,还有。
因为DCT矩阵的特点就是左上角有值,右下角基本都是0⃣️,所以传统的按行列进行存储的话,会把0⃣️分散在非零的值之间,不能达到最大的压缩率。所以,JPEG当中对于矩阵的存储采用的是ZigZag方式,如下:
图片来源:ISO/IEC 10918-1 : 1993(E)(参考引用*2)
这样可以将矩阵当中的0⃣️串一长串,然后用一个0x 00早早的将这个矩阵结束掉。
也就是说:
如果矩阵全为零,那么一个0x 00就可以代表它。(压缩率1/64)
如果矩阵里面只有稀稀拉拉几个值,那么几个字节就可以代表它。

好了,经过这样眼花缭乱的技巧之后,我们上面的8个字节,就可以展开成为下面这6个矩阵:
这里最后的一个步骤:Y分量的DC部分在块间是存储的差值。也就是说,第二个8×8块的Y(DC)其实应该是第一个8×8块的Y(DC)+第二个8×8块的Y(DC)。也就是说上面第二个块的Y分量矩阵需要修正为 -512 + 1020 = 508
然后将这些8×8矩阵分别用上一篇我们所写的IDCT变换变换回来,得到:(CbCr为全零矩阵,IDCT之后仍然是全零矩阵)
然后将其上浮128(使得值域从[-128 ,127]变为[0, 255]),然后使用我们上一篇所写的YCbCr –> RGB色彩空间变换,得到最终结果如下:
每组数据分别包括R、G、B三个分量
这正是我们用于测试的图片的样子(左边8×8黑色,右边8×8白色)
最后附上完整的程序执行输出,供有兴趣的读者参考:(代码在jpeg分支当中)
*上面的说明当中还省略了被称为Quantization的过程。这个过程是将DCT矩阵的不同元素进行缩放,使得AC的部分尽可能变成绝对值小于1的小数,然后在取整的时候变成0。JPEG之所以是有损压缩,除了色空间变换之后的YUV chrome sub sampling,数据的丢失主要就是发生在这一步。而上面介绍的其他步骤,在不考虑计算误差的情况下,都是可逆的)
 
参考引用