从0构建 3D GIF动画，看清计算机运行机制

从0构建 3D GIF动画，看清计算机运行机制

在《从 0 构建 WAV 文件》中，我们通过了解wav文件的结构与格式，学会了如何用朴素的方式构建声音文件；在《从 2D 转 3D 的本质》中，我们领悟了游戏中所谓三维世界，不过是简单的投影。
今天我们将了解一个更加复杂但有趣的文件格式-GIF，在了解其本质的同时，我们将不依赖任何庞大的图形库（如 OpenGL、DirectX）或图像库（如 OpenCV、ImageMagick），仅凭 C++ 标准库，完成上一篇文章用python实现的旋转立方体并以GIF文件的方式呈现出来。
我们将进一步加深对计算机本质的理解：一切复杂的表象，归根结底都是“数学计算”与“数据存储”的结合。
1. GIF文件结构

相比于 WAV 文件的简单粗暴，GIF 的结构要精密得多，因为它天生是为了网络传输而设计的（包含了压缩机制）。
当我们用二进制视角观察 GIF 时，它是由一个个 数据块（Block） 组成的：

数据块 (Block Name)中文名称字节数 (Bytes)作用与核心逻辑Header头标识6一般为 GIF89a，当然也有GIF87a,用于声明这是一个GIF文件，采用xx标准。Logical Screen Descriptor逻辑屏幕描述符7画布设定：定义图像总宽高、背景色索引及是否使用全局调色板。Global Color Table全局颜色表3 × N颜料盘：存储 RGB 颜色（如 00 FF 00），N 为颜色数（最大256）。 默认使用RGB颜色时，每个颜色均采用3个字节存储Application Extension应用程序扩展19 (通常)最常用的是 Netscape 扩展，用于“循环播放次数”。Graphic Control Extension图形控制扩展8播放控制：定义每一帧的延迟时间（动画快慢）和透明色。Image Descriptor图像描述符10帧属性：定义当前这一帧在画布上的位置（x, y）和尺寸。Image Data图像数据可变用处如其名Trailer结束标识1终点：固定为 0x3B (分号)，标志文件彻底结束。其中，最重要的就是图像数据了，其他的块用于规定这些图像数据应当如何呈现到我们眼中或是告知文件的开始结束，因此对于我们来说，其他块基本上都有固定模板，只有图像数据需要我们自己定义。
2.LZW-GIF强制使用的图像压缩算法

搞定了GIF的文件结构，接下来就需要我们解决另一个拦路虎，LZW——一个经典的无损图像压缩算法，为了解决他，我们可以从他的原理入手。
LZW通过为复杂数据构建简单索引来减少存储的数据量，这一点是朴素的哈希算法，当然，这一算法的发明者通过一套特殊的规则使得其他人可以直接通过索引数据反推出复杂数据，而在GIF中，则是GIF发明公司将他所规定的规则写好，编写GIF的人根据这一套规则构建数据，然后其他人直接使用套用了这一套规则的解码器解码，便能将数据还原成原来的样子。
GIF的解码器又是如何读取数据的呢？解码器初始时一次性读取9位数据，然后从字典中添加这一对应关系，根据GIF规范，一旦字典里的条目达到 512 个，解码器就会自动将读取位宽从 9 位增加到 10 位。如果我们直接存放数据，那么结果就是数据读取错位，解码出来的内容就会与我们想象中的不一样，如果我们想要让他的数据读取正常，通常做法就是：我们构建一个同步状态机，即模拟GIF解码器读取数据的过程写入数据，构建一个字典，以相同的标准增加写入位宽，从而让解码器读取时能正确读取。但是这一过程看着就十分繁琐，能不能用一个简单的方法来让解码器正常读取数据呢？
3.解决方案

GIF 协议中有一个特殊的指令叫 Clear Code（清除代码，值为256）。它的作用是告诉解码器：“嘿，把之前的字典都忘了吧，我们重新开始。”
利用这一点，我们可以在代码中采用了一种偷鸡的策略：

• 我们不尝试去寻找复杂的重复模式。
  
• 我们每写入一小段像素（例如 125 个），就立刻发送一个 Clear Code。
  
• 这强制让 LZW 字典始终处于“初始状态”。在初始状态下，LZW 的编码就等同于直接输出像素的颜色索引值。
  

现在，让我们来实现他
4. 构建3d立方体

在上一篇关于 3D 本质的文章中，我们推导出了两个核心公式。在这个程序中，我们将直接把它们转化为 C++ 代码。
旋转公式

为了让立方体动起来，我们需要每一帧都改变顶点的 \((x, y, z)\) 坐标。这里使用旋转矩阵的简化版：

1. Point3D rotate(Point3D p, float angle) {
2.     // 绕 Y 轴旋转
3.     float nx = p.x * cos(angle) - p.z * sin(angle);
4.     float nz = p.x * sin(angle) + p.z * cos(angle);
5.     // 绕 X 轴微调旋转，让旋转看起来更立体
6.     float ny = p.y * cos(angle * 0.8f) - nz * sin(angle * 0.8f);
7.     nz = p.y * sin(angle * 0.8f) + nz * cos(angle * 0.8f);
8.     return {nx, ny, nz};
9. }

复制代码

投影公式（透视）

如何把 3D 坐标变成屏幕上的像素点？记得那个核心法则吗？“近大远小，本质就是除以 Z”。

1. pair<int, int> project(Point3D p, int W, int H) {
2.     float fov = 160.0f;        // 视野系数
3.     float viewer_dist = 4.0f;  // 眼睛离物体的距离
4.     // 核心逻辑：除以 (z + dist)
5.     float factor = fov / (viewer_dist + p.z);
6.     return { (int)(p.x * factor + W / 2), (int)(p.y * factor + H / 2) };
7. }

复制代码

有了这两个函数，我们就能在内存里的一个二维数组（vector pixels）上画线了。
手写 GIF 编码器

我们实现了一个极简的编码器（struct GifBitStream）。它的工作是把像素点的颜色索引（0或1）打包成变长的二进制码流。

1. // GIF 的数据存储不仅是字节，还需要处理“位操作”
2. // 比如写入一个 9-bit 的代码，可能跨越两个字节
3. struct GifBitStream {
4.     vector<u8> byteData;
5.     u32 bitBuffer = 0;
6.     int bitCount = 0;
8.     void writeCode(u32 code, int size) {
9.         // 将数据移位并存入缓冲区...
10.         // 凑够8位就写入 byteData
11.     }
12.     // ...
13. };

复制代码

特别说明：绕过LZW的问题

生成的GIF没有压缩，体积较为大
4. 完整代码

下面是完整的 C++ 代码：

• 计算：旋转 3D 点 -> 投影成 2D 点。
  
• 绘图：在内存的黑板上画线（Bresenham 直线算法）。
  
• 编码：将内存的黑板按照 GIF 协议压缩并写入文件。
  

(代码较长，建议直接复制编译运行，感受生成的快感)
[code]#include using namespace std;#define u8 uint8_t#define u16 uint16_t#define u32 uint32_tstruct Point3D {     float x, y, z; };struct Edge {     int u, v; }oint3D rotate(Point3D p, float angle) {    float nx = p.x * cos(angle) - p.z * sin(angle);    float nz = p.x * sin(angle) + p.z * cos(angle);    float ny = p.y * cos(angle * 0.8f) - nz * sin(angle * 0.8f);    nz = p.y * sin(angle * 0.8f) + nz * cos(angle * 0.8f);    return {nx, ny, nz};}pair project(Point3D p, int W, int H) {    float fov = 160.0f;     float viewer_dist = 4.0f;    float factor = fov / (viewer_dist + p.z);    return { (int)(p.x * factor + W / 2), (int)(p.y * factor + H / 2) };}inline void drawLine(vector& buffer, int W, int H, int x0, int y0, int x1, int y1) {    int dx = abs(x1 - x0), sx = x0 < x1 ? 1 : -1;    int dy = -abs(y1 - y0), sy = y0 < y1 ? 1 : -1;    int err = dx + dy;    while (true) {        if (x0 >= 0 && x0 < W && y0 >= 0 && y0 < H) buffer[y0 * W + x0] = 1;        if (x0 == x1 && y0 == y1) break;        int e2 = 2 * err;        if (e2 >= dy) { err += dy; x0 += sx; }        if (e2 >= 8;            bitCount -= 8;        }    }    inline void flush(ofstream& f) {        if (bitCount > 0) byteData.push_back(bitBuffer & 0xFF);        // GIF 规定：数据必须切成每块最大 255 字节的小块        for (size_t i = 0; i < byteData.size(); i += 255) {            u8 blockSize = (u8)min((size_t)255, byteData.size() - i);            f.put(blockSize);            f.write((char*)&byteData, blockSize);        }        f.put(0); // 块结束    }};inline void writeWord(ofstream& f, u16 v) {     f.put(v & 0xFF);     f.put((v >> 8) & 0xFF); }inline void writeGifFrame(ofstream& f, const vector& pixels, int W, int H) {    // 1. 图形控制扩展 (帧间隔)    f.put(0x21);     f.put(0xF9);     f.put(0x04);    f.put(0x09);       // 属性：还原背景，不使用透明    writeWord(f, 4);   // 延迟 40ms (1/25 FPS)    f.put(0);     f.put(0);    // 2. 图像描述符    f.put(0x2C);    // 偏移    writeWord(f, 0);     writeWord(f, 0);     // 宽高    writeWord(f, W);     writeWord(f, H);     f.put(0x00);    // 3. 数据    f.put(0x08); // 8位色    GifBitStream stream;    const int ClearCode = 256; //清空指令    const int EOICode = 257;    stream.writeCode(ClearCode, 9); // 清空解码器字典    int pixCount = 0;    for (u8 p : pixels) {        stream.writeCode(p, 9);        pixCount++;        //每 125 个像素重置一次字典，保证位宽不变，不会提前读取到下一个字节        if (pixCount == 125) {            stream.writeCode(ClearCode, 9);             pixCount = 0;        }    }    stream.writeCode(EOICode, 9); // 结束    stream.flush(f);}signed main(int argc,char* argv[]){    const int W = 200, H = 200;    ofstream f("cube_perfect.gif", ios::binary); //以二进制方式写入GIF文件    // [Header]     f

谢谢楼主提供！