Tiny Rubik’s Cube

1. 问题描述

本次大作业的目标是开发一个带有图形用户界面的普通三阶魔方模拟程序. 具体要求如下:

• 魔方展示: 实现魔方的平移、放大、缩小功能, 并能自适应窗口大小进行展示.
• 操作编码: 自定义一套编码系统, 用于表示魔方的各种基本操作 (例如, 前面顺时针旋转 90 度、顶面逆时针旋转 90 度等).
• 文件交互:
  • 实现打开文本文件的功能, 该文件包含一系列预定义的魔方操作编码.
  • 程序能够读取这些编码并执行相应的魔方操作.
• 魔方操作:
  • 支持用户通过交互界面执行单个魔方操作.
  • 支持通过动画形式自动播放文件中的一系列操作.
• 动画效果: 在进行任何操作或转动魔方时, 必须以平滑的动画形式展示过程, 方便用户观察和理解.
• 保存功能: 用户可以将当前的操作序列保存为文本文件, 文件内容为自定义的操作编码.
• 文档编写: 详细介绍模拟算法、图形界面设计等内容.

参考资料:《清华教授的小课堂魔方真好玩》 (雍俊海著, 清华大学出版社).

2. 使用指南

2.1. 环境配置

1. 安装 xmake
2. 安装 VS Code 并添加 C++ 扩展
3. 克隆项目仓库: git clone https://github.com/liblaf/tiny-rubiks-cube.git
4. 安装依赖: xmake require

2.2. 构建与运行

# 配置项目
xmake config --mode=debug

# 构建项目
xmake

# 运行程序
xmake run

2.3. 基本操作

1. 手动操作:
   • F/B/U/D/L/R: 旋转前面/后面/上面/下面/左面/右面
   • Shift + 按键: 逆时针旋转
   • F2: 重复上一次操作
2. 记录与回放:
   • 点击 “Record” 开始记录操作
   • 执行一系列旋转操作
   • 点击 “Stop Recording” 结束记录
   • 点击 “Replay” 回放操作序列
3. 文件操作:
   • 操作序列保存在 demo/actions.txt
   • 格式示例: F B U D L R R' L' D' U' B' F'

2.4. 3D 视图控制

• 旋转视图: 鼠标左键拖动
• 平移视图: 鼠标右键拖动
• 缩放视图: 鼠标滚轮
• 重置视图: 按 R 键

3. 开发环境与工具

为了完成这个项目, 我选择并配置了以下开发环境和工具:

• 操作系统: Linux
• 集成开发环境 (IDE): Visual Studio Code (VS Code). VS Code 轻量且强大, 拥有丰富的插件生态, 非常适合 C++ 开发.
• 构建系统: Xmake. Xmake 是一个基于 Lua 的现代化构建工具, 跨平台且易于使用, 能够简化项目的编译和依赖管理. 项目中的 xmake.lua 文件定义了项目的构建规则.
• 语言服务器: Clangd. Clangd 为 VS Code 提供了强大的 C++ 语言支持, 如代码补全、语法检查、跳转定义等, 极大地提高了编码效率. 配置文件为 .clangd.
• 代码格式化工具: Clang-Format. 为了保持代码风格的一致性, 我使用了 Clang-Format, 并根据 Google C++ Style Guide 进行了配置 (配置文件为 .clang-format).
• 编程语言: C++20. 利用了 C++20 的一些现代特性.
• 核心依赖库:
  • Polyscope (v2.3): 这是一个用于 3D 数据可视化的 C++ 库, 支持快速构建交互式用户界面. 我主要用它来显示魔方模型和集成 ImGui 图形界面.
  • ImGui: 一个轻量级的图形用户界面库, 我用它在 Polyscope 窗口中创建按钮、文本等交互元素.
  • GLM (OpenGL Mathematics): 一个用于图形编程的数学库, 提供了向量、矩阵等数据结构和运算, 用于处理魔方块的变换 (旋转、位置).
  • Eigen (v3.4.0): 另一个强大的 C++ 模板库, 用于线性代数运算, 主要在加载和处理模型顶点数据时使用.
  • TinyObjLoader (v2.0.0rc13): 一个简单易用的 .obj 文件加载库, 我用它来加载魔方的 3D 模型.
  • spdlog: 一个快速、头文件式的 C++ 日志库, 用于输出调试信息和程序运行状态.
  • dbg-macro: 一个方便的 C++ 调试宏, 用于打印变量值等.

项目文件结构如下:

demo/
  actions.txt       # 示例操作序列文件
src/
  action.cc         # 魔方操作逻辑实现
  action.h          # 魔方操作定义
  assets.cc         # 3D模型资源加载实现
  assets.h          # 3D模型资源加载定义
  cube.cc           # 整个魔方对象的实现
  cube.h            # 整个魔方对象的定义
  cubie.cc          # 单个魔方块 (“小方块”) 的实现
  cubie.h           # 单个魔方块的定义
  main.cc           # 程序主入口, GUI回调
  setup.cc          # Polyscope环境和魔方模型的初始化实现
  setup.h           # 初始化定义
  utils.cc          # 工具函数实现
  utils.h           # 工具函数定义
.clang-format       # 代码格式化配置
.clangd             # Clangd配置
.gitignore          # Git忽略文件配置
.repomixignore      # Repomix忽略文件配置 (项目提供的)
Justfile            # 简化xmake命令的脚本
xmake.lua           # Xmake构建配置文件

4. 设计思路

我的设计思路遵循模块化和事件驱动的原则, 力求代码结构清晰、易于扩展.

4.1 核心对象设计

程序的核心由以下几个类构成:

• Cubie (小方块):
  • 代表组成魔方的 26 个可见小方块之一 (不包括中心轴).
  • 每个 Cubie 存储其在魔方中的逻辑位置 (一个三维整数向量, 如 (-1, -1, -1) 表示一个角块) 和初始位置.
  • 它还负责管理自身在 3D 空间中的变换矩阵 (glm::mat4x4) , 并与 Polyscope 中的对应 SurfaceMesh (表面网格, 即模型的一个小片) 关联.
  • Cubie 知道如何根据给定的 Action 更新自己的变换 (用于动画) 和逻辑位置 (动画结束后).
• Action (操作):
  • 定义了魔方的一次基本操作. 例如, "F"表示正面顺时针旋转 90 度.
  • 包含操作的面 (Side 枚举: FRONT, BACK, UP, DOWN, LEFT, RIGHT) 和方向 (clockwise 布尔值, true 为顺时针).
  • 提供了从字符 (如 ‘F’, ‘'’) 解析操作的方法, 以及将操作转换为字符串的方法.
  • 能够计算执行此操作所需的旋转轴和旋转角度.
  • 可以从文本文件 (demo/actions.txt) 加载一系列操作, 也可以将一系列操作保存到文件.
• Cube (魔方整体):
  • 这是魔方的中心控制器, 包含一个由 27 个 Cubie 组成的集合 (尽管中心块 (0,0,0) 可能不直接参与旋转, 但为了结构完整性会创建).
  • 管理魔方的当前状态:
    • IDLE (空闲): 等待用户操作或指令.
    • ANIMATING (动画中): 正在执行一个操作的动画.
    • RECORDING (录制中): 用户进行的操作会被记录下来.
    • REPLAYING (回放中): 正在自动播放一系列操作.
  • 存储当前正在执行的 Action, 以及录制的操作序列 (std::deque<Action>).
  • 负责启动和更新动画. 当一个操作被触发时, 它会识别哪些 Cubie 需要参与这次旋转, 并通知它们开始动画.
  • 动画是基于时间的, Cube 会计算动画进度, 并传递给相关的 Cubie 进行更新.
• assets (资源管理模块):
  • 负责加载魔方的 3D 模型. 目前, 模型是从一个 .obj 文件 (assets/cube.obj) 加载的, 该文件由 tinyobjloader 库解析.
• setup (初始化模块):
  • 负责初始化 Polyscope 环境, 例如设置背景、光照等.
  • 将加载的 .obj 模型注册到 Polyscope 中, 并根据模型中各个小块的几何中心, 将它们组织成逻辑上的 Cubie. 每个 Cubie 在 Polyscope 中表现为一个 “group”, 包含构成该小块的若干个 “SurfaceMesh”.
  • 设置地面平面, 使魔方看起来更自然.
• utils (工具模块):
  • 包含一些辅助函数, 例如根据 Cubie 的逻辑位置生成其在 Polyscope 中的唯一名称.

4.2 用户界面 (UI) 与交互

• 图形界面使用 Polyscope 内建支持的 ImGui 库.
• 在 main.cc 中定义了一个回调函数 callback(), Polyscope 会在每一帧调用它.
• 显示信息: 在界面上显示魔方的当前状态 (如当前动作、是否在动画/录制/回放、已录制的动作序列).
• 用户输入:
  • 键盘操作: 通过键盘按键 (F, B, U, D, L, R, 配合 Shift 键改变方向) 直接触发魔方转动.
  • 按钮操作:
    • “Replay” (回放): 允许用户选择一个包含操作序列的文本文件进行播放.
    • “Record” (录制): 开始记录用户的键盘操作.
    • “Save to File” (保存到文件): 将录制的操作序列保存到文本文件.
    • “Stop Recording” (停止录制): 结束录制状态.
• Polyscope 自身提供了平移、缩放、旋转视角等基本的 3D 场景交互功能.

4.3 动画实现

动画是逐帧更新的:

1. 当一个 Action 被触发时, Cube 对象标记自己进入 ANIMATING 状态, 并记录动画开始时间.
2. 在每一帧的 Cube::update() 调用中, 计算从动画开始到现在所经过的时间, 并将其转换为一个进度值 progress (0.0 到 1.0).
3. Cube 识别出需要参与当前 Action 的所有 Cubie (例如, 如果是 “F” 操作, 就是所有 Z 轴坐标为 1 的 Cubie).
4. 对于每个参与动画的 Cubie, 调用其 update(action, progress) 方法.
5. Cubie::update() 方法根据 action 和 progress 计算出一个临时的旋转变换矩阵, 并应用到其管理的 Polyscope SurfaceMesh 上, 从而在屏幕上看到小方块的转动. 这个旋转是基于该 Cubie 在本次操作开始前的原始姿态进行的插值旋转.
6. 当 progress 达到 1.0 时, 动画结束. Cube 通知相关的 Cubie 调用 end(action) 方法, 该方法会更新 Cubie 的逻辑位置 (例如, 原本在 (1,1,1) 的角块, 经过 “F” 操作后, 其逻辑位置会变为 (1,-1,1)).
7. Cube 清除 ANIMATING 状态. 如果正在 REPLAYING 状态且还有未执行的操作, 则自动开始下一个操作的动画.

4.4 操作的编码与文件处理

• 编码:
  • 基本面旋转: ‘F’ (Front), ‘B’ (Back), ‘U’ (Up), ‘D’ (Down), ‘L’ (Left), ‘R’ (Right).
  • 方向: 默认顺时针. 字符后跟一个 ' (单引号) 表示逆时针 (例如 “F’”).
  • 双次旋转: 字符后跟一个 ‘2’ 表示顺时针旋转 180 度 (在实现中, 这等同于执行两次相同的顺时针 90 度操作).
  • 示例序列: F B U D L R R' L' D' U' B' F' (来自 demo/actions.txt)
• 文件读取: Action::from_file(filepath) 方法逐字符读取文件, 将编码转换为 Action 对象队列.
• 文件保存: Action::to_file(filepath, actions) 方法将 Action 对象队列转换为上述编码字符串并写入文件.

5. 实现细节

5.1 魔方模型的加载与设置 (setup.cc, assets.cc)

1. 加载 OBJ 模型:
   • assets::load_cube() 使用 tinyobjloader::ObjReader 解析 “assets/cube.obj” 文件. 这个 OBJ 文件应该包含了构成魔方的所有小面片 (比如每个小方块的 6 个面上的贴图部分).
2. 注册到 Polyscope:
   • setup::register_cube() 遍历 OBJ 文件中的所有形状 (shapes). 每个 shape 对应魔方上的一个小贴纸 (一个有颜色的面).
   • 顶点数据 (Eigen::MatrixX3f vertices) 和面索引 (std::vector<std::vector<int>> indices) 被提取出来.
   • 使用 polyscope::registerSurfaceMesh() 将每个 shape 注册为一个独立的表面网格.
   • 从 OBJ 关联的 .mtl 文件中加载每个面的漫反射颜色, 并设置为 Polyscope 网格的面颜色 (addFaceColorQuantity("diffuse", colors)).
3. 创建 Cubie 逻辑组 (setup::create_groups()):
   • 三阶魔方可以看作是 3x3x3 的结构. 我们定义一个局部坐标系, 中心为 (0,0,0), 每个小方块的中心可以在 {-1, 0, 1} 的 x, y, z 坐标上.
   • 该函数计算整个魔方模型的包围盒, 从而确定其中心和尺寸.
   • 然后, 它遍历 Polyscope 中已注册的每个表面网格 (shape), 计算该网格的几何中心.
   • 根据该几何中心相对于整个魔方中心的位置, 以及魔方单个小方块的理论尺寸, 推断出这个表面网格属于哪个逻辑 Cubie (其坐标如 (1, -1, 0)).
   • 具有相同逻辑位置 (x,y,z) 的所有表面网格会被添加到一个以该位置命名的 Polyscope Group 中 (例如, 组名为 " 1-1 0"). 这个 Group 就代表一个 Cubie.
4. 设置地面:
   • setup::setup_ground() 计算魔方模型的最低点, 并在其下方设置一个虚拟地面, 使视觉效果更佳.

5.2 Cubie 类 (cubie.h, cubie.cc)

• 构造函数 Cubie(glm::ivec3 location): 初始化 Cubie 的当前逻辑位置 _location 和初始逻辑位置 _location_initial. 初始位置用于生成其在 Polyscope 中的唯一名称.
• name(): 返回基于 _location_initial 生成的字符串名称, 用于获取其在 Polyscope 中的 Group.
• group(): 获取与此 Cubie 关联的 Polyscope Group.
• meshes(): 获取此 Cubie Group 下的所有 Polyscope SurfaceMesh 指针.
• transform(): 获取该 Cubie (具体来说是其 Group 下的第一个 mesh) 当前的变换矩阵.
• start(): 在动画开始前调用, 保存当前 Cubie 的变换矩阵 _start. 动画将基于这个初始状态进行.
• update(Action action, float progress):
  • 获取 _start 变换.
  • 调用 action.rotate(_start, progress) 来计算当前进度下的插值变换. Action::rotate(transform, progress) 的实现是 glm::rotate(progress * total_angle, axis) * initial_transform.
  • 将计算出的新变换应用到该 Cubie 的所有 meshes 上 (mesh->setTransform(transform)).
• end(Action action): 动画结束时调用. 使用 action.rotate(this->_location) 来更新 Cubie 的逻辑位置 _location. 注意这里的 action.rotate 是重载版本, 用于旋转一个 glm::ivec3 类型的逻辑位置向量.

5.3 Action 类 (action.h, action.cc)

• Side enum 和 clockwise bool: 定义了操作类型.
• axis_index(): 根据 Side (如 FRONT 是 Z 轴) 返回对应的轴索引 (0 for X, 1 for Y, 2 for Z).
• direction(): 根据 Side (如 FRONT 是 +1, BACK 是 -1) 返回在对应轴上的方向.
• rotate_angle(): 根据 clockwise 返回旋转角度 (-90 或 +90 度, 转换为弧度).
• rotate_axis(): 根据 axis_index() 和 direction() 构建一个标准化的旋转轴向量 (如 (0,0,1)).
• rotate(glm::ivec3 location) const: 输入一个逻辑位置, 将其绕原点根据当前 Action 的定义旋转 90 度, 返回新的逻辑位置. 用于动画结束后更新 Cubie 的逻辑坐标.
• rotate(glm::mat4x4 transform, float progress) const: 输入一个变换矩阵和动画进度, 返回基于进度插值旋转后的新变换矩阵. 用于实时更新 Cubie 的视觉表现.
• from_file(filepath) 和 to_file(filepath, actions): 实现操作序列的读写. from_file 会处理 ‘F’, ‘B’, ‘'’, ‘2’ 等字符.

5.4 Cube 类 (cube.h, cube.cc)

• 构造函数: 创建所有 27 个 Cubie 对象 (包括中心块 (0,0,0), 尽管它不旋转, 但它的存在可能简化了某些逻辑或索引).
• _cubies: 一个 std::vector<std::shared_ptr<Cubie>> 存储所有小方块.
• _state: IDLE, RECORDING, REPLAYING.
• _animating: 布尔值, 标记是否正在动画中.
• _action: 当前正在执行或刚被设置的 Action.
• _animation_start, _duration: 用于控制动画时间和进度.
• action(Action action) (setter):
  • 如果不在动画中, 则设置 this->_action.
  • 如果当前是 RECORDING 状态, 将此 action 加入 _actions 队列.
  • 设置 _animating = true, 记录 _animation_start.
  • 调用 animating_cubies() 找到所有受此 action 影响的 Cubie.
  • 对这些 Cubie 调用 start(), 让它们保存自己当前的变换状态.
• animating_cubies():
  • 根据当前 _action 的轴 (axis_index()) 和方向 (direction()), 遍历所有 _cubies.
  • 如果一个 Cubie 的逻辑位置在对应轴上的分量等于 action 的方向值 (例如, F 面旋转, 轴是 Z, 方向是 +1, 则所有 cubie->location().z == 1 的小方块参与旋转) , 则将其加入返回列表.
• update():
  • 如果不在动画中 (!this->animating()), 直接返回.
  • 计算动画进度 progress.
  • 如果 progress >= 1.0 (动画完成):
    • 设置 progress = 1.0.
    • 调用 animate_end().
    • 如果正在 REPLAYING 模式:
      • 如果 _actions 队列不为空, 取出下一个 action 并调用 this->action(next_action) 开始新的动画.
      • 如果队列为空, 则回放结束, 设置状态为 IDLE.
  • 对于 animating_cubies() 中的每个 Cubie, 调用 cubie->update(this->action(), progress).
• animate_end():
  • 对于 animating_cubies() 中的每个 Cubie, 调用 cubie->end(this->action()) 来更新其逻辑位置.
  • 设置 _animating = false.
• record_start(), record_end(), replay(actions): 管理录制和回放状态及操作队列.

5.5 主程序与界面 (main.cc)

• main() 函数:
  • 初始化 Polyscope (polyscope::init()).
  • 加载魔方模型 (cube::load_cube()).
  • 设置 Polyscope 环境和魔方模型 (cube::setup(*obj)).
  • 创建一个 std::shared_ptr<cube::Cube> 实例.
  • 将 callback 函数 (绑定了 cube 实例) 设置为 Polyscope 的用户回调 (polyscope::state::userCallback = std::bind(callback, cube)).
  • 显示 Polyscope 窗口 (polyscope::show()).
• callback(std::weak_ptr<cube::Cube> cube_wp) 函数:
  • 每帧调用 cube->update() 来驱动动画和逻辑更新.
  • 使用 ImGui::Text() 显示魔方状态信息.
  • 根据 cube->state() (IDLE, RECORDING, REPLAYING) 显示不同的 ImGui 按钮:
    • IDLE 状态: “Replay” 按钮 (使用 polyscope::promptForFilename() 获取文件路径, 然后 Action::from_file() 和 cube->replay()) 和 “Record” 按钮 (cube->record_start()).
    • RECORDING 状态: “Save to File” 按钮 (使用 polyscope::promptForFilename() 获取文件路径, 然后 Action::to_file()) 和 “Stop Recording” 按钮 (cube->record_end()).
    • 处理键盘输入:
    • 检测 F, B, U, D, L, R 键是否按下 (ImGui::IsKeyPressed()).
    • 检测 Shift 键是否按下 (ImGui::IsKeyDown()) 来确定旋转方向 (clockwise).
    • 调用 cube->action(cube::Action(...)) 来触发相应的魔方操作.