图形学实验框架 Dandelion 始末（五）：交互式几何编辑

原计划一口气写完《始末》这个系列，却在去年年初中断。写下这篇文章的时候已经是 2025 年，实在始料不及。这篇文章着重于 Dandelion “建模模式”背后的交互实现与数据同步机制，而不是几何算法，因为我认为前者是回忆录中更值得回顾的部分。

几何编辑的两个核心问题

到实现渲染模式和渲染器为止，Dandelion 已经是一个能够加载、管理和显示模型数据的小工具了。然而此前的所有功能（以及此后要实现的简单动画）基本上是重计算而轻交互、多流程而少状态的功能。用软光栅渲染器举个例子：它以几何数据 (Mesh)、变换信息、光源为输入，计算出每个像素的渲染结果。整个渲染过程按顶点处理、光栅化、片元处理、写入缓冲的流程执行，每一步读取上一步的输出，计算完成后写入自己的输出变量。虽然为了支持渲染，GUI 和物体数据中包含了一些状态，但这些状态在渲染过程中不会发生改变，整体的渲染流程全部是“前向”的，很容易被拆分成若干个互不影响的函数——也就是耦合度很低的函数。

就算法本身而言，几何处理算法与渲染流程也是类似的。但为了引入交互式的几何编辑功能，必须实现三维的交互操作和对应的可视化反馈，而 GUI 库对这些功能没有任何支持，这是第一个问题。对于渲染而言，“有状态”的变量最多只是变换、材质和光源，而对于几何编辑而言，“有状态”的变量是所有的几何数据，是图元级别而非物体级别的数据。图元数据不仅数量上非常庞大，还在内存和显存两个位置各有一份副本，所以任何修改首先需要从 UI/UX 层面同步到内存数据，再从内存同步到显存数据，这是第二个问题。

从功能角度，我们的参考对象 Scotty3D 把这两个问题都解决得不错：

• 允许操作者拾取（pick，三维交互方面常用这个词代替“选中”）物体、三角形、边、顶点等多种不同粒度的元素，选中后既有高亮的视觉反馈，也能对所选元素进行各种操作；
• 将几何编辑操作划分为“局部操作”与“全局操作”两类，分别对应只影响几个图元的操作与影响整个物体的操作，并分别实现了内存-显存同步机制，保证编辑后能正确重绘画面。

所以 Dandelion 继承了 Scotty3D 的许多交互设计，以及区分对待几何编辑操作的思想。

然而，Scotty3D 也有些不尽如人意的地方，其中最成问题的就是性能不佳。在我本科尚未毕业时，我用的还是一台装有 i5 8250U 和 GeForce 940MX 的轻薄本（2018 年产，实际 GPU 性能已经远逊于当代的集成显卡），加载一个几千面的模型并进入编辑模式后，帧数从 60 骤降到 35 左右；而如果加载著名的 Stanford Dragon 模型（约 30 万面），进入编辑模式后甚至达不到 3 帧！2022 年秋季学期上课的同学中，有不少人的笔记本性能甚至更差，以至于验收都无法正常进行。这使我决定从头重新实现所有的交互操作、视觉反馈和数据同步。

半边网格数据结构

在谈实现之前，还是要简单讲讲这个对几何编辑非常重要的数据结构。半边网格 (Halfedge Mesh)，是高效查改 Mesh 的一种辅助数据结构。这里我不多谈它的设计和实现，以免长篇大论。不过有个问题是避不开的：为什么几何编辑需要这种数据结构？

因为常规的 Mesh 存储不能满足几何操作的要求。最常用的 Mesh 数据结构大体上是顶点数组+顶点索引的模式，顶点数组维护属性、顶点索引维护图元。这种存储方式不直接反映任何拓扑上的邻接关系，而各种邻接关系正是几何操作频繁使用的。大多数几何操作的思想继承自微分几何学，遍历各种“邻域”——比如顶点邻域、边邻域——是在 Mesh 上近似微分操作的主要手段，而顶点索引不能为这种操作提供任何便利，所以我们还需要加速结构。

Dandelion 的半边网格 HalfedgeMesh 大量参考了 Scotty3D 的代码，这里再次感谢 CMU 老师和助教们无私的开源贡献。但为了让编写和使用更简洁，我还是在底层更换了不少东西。半边网格是包含大量指针的数据结构，首先要用链表组织半边、顶点、边、面片四种基本图元，然后再用指针维护四种图元之间的邻接关系。Scotty3D 直接使用 std::list 实现双链表，省去了自己实现的麻烦。但 std::list 是非侵入式链表，数据类型不是节点类型，且并没有对外暴露节点类型。偏偏半边网格需要在数据类型内增加节点类型的指针（比如顶点 Vertex 类型内要有指向某个半边的指针），以此提供遍历邻域的能力。最终 Scotty3D 选择全部用迭代器实现指针，并大量定义了 Ref 和 CRef 为后缀的类型别名（比如 using VertexRef = list<Vertex>::iterator）。诚然，迭代器的性能开销不算大，但到处都是的 Ref 类型还是容易让初学者感到迷惑。所以最终我选择全部改用指针实现，包括自己实现侵入式链表（utils/linked_list.hpp 中的 LinkedListNode<T> 和 LinkedList<T>）、所有图元类型的引用关系全部表示为裸指针。在与指针战斗了不知道多少天之后，这一修改还给 Dandelion 带来了一个副产品：指针类型与引用类型的项目内规范。

简单来说包括这么几条：

• 裸指针 T* 表示引用关系，但不表示所有权。换言之，指针 T* x 的持有者不考虑 x 的分配和释放问题。
• 引用类型 T& 用于传递参数和返回结果。换言之，引用类型是临时的，表示可以临时访问或者修改某个对象。
• 智能指针 unique_ptr 和 shared_ptr 管理所有权，unique_ptr<T> x 的持有者负责分配和释放 x。如果需要传参，先转成引用；如果新构造的对象需要保存 x 的引用关系，先转成裸指针。

引入半边网格有些类似向数据库中加入索引（通常是 B+ 树），能让很多操作执行加快，但也在输入（操作）和底层数据之间增加了一层，需要时时小心确保加速结构和底层数据之间是一致的，增加了很多同步问题。除了接下来要聊的同步方案，Dandelion 还采用一条很激进的策略，那就是只允许编辑单个物体、只保留一个半边网格，一旦退出建模模式，附属于 Scene 对象的 HalfedgeMesh 马上销毁。

交互：多粒度拾取与内存-显存同步

任何编辑操作的过程都可以简单概括为选中、修改、同步、重绘这几步，而在三维空间中，第一个问题就是如何“选中”。通过光标在屏幕上选择三维实体的操作通称“拾取” (picking)，负责把二维的屏幕坐标（点击或者拖动的位置）转换到三维空间，并判断这个坐标在哪个可选中的对象上。形式化一下，拾取操作代表一个将 $\mathbb{R}^2$ 映射到某个有限集合的函数

$$p:\mathbb{R}^2\rightarrow\text{set of selectable units}$$

对渲染稍有印象的朋友很容易联想到光线追踪：如果把观察相机的位置 $\mathbf{e}$ 作为原点，窗口视作三维空间中的一个矩形，那么点击的位置可以在矩形上确定一点 $\mathbf{c}$，这两个点就能确定一条射线。而这条射线类似我们的视线，它打到哪里，就代表我们看到（点击）了哪里，也就代表了我们的选择操作。相应的代码实现和光线追踪完全一样，可以直接用之前写好的射线求交功能。

不过对于光线追踪而言，射线求交要获取的是坐标、法线和材质；对编辑操作而言，求交要获取的则是图元和物体。如果要拖曳一个顶点，那就要选中顶点；如果要拉伸一条边，那就要选中边，等等。

然而在三维场景中，真实存在的几何数据只有面片，射线也只能和面片求交。连求交都无法实现，如何才能选中其他类型的图元呢？Scotty3D 的做法是进入建模模式后临时增加大量的 Mesh：

• 每个顶点处增加一个小球
• 每条边上增加一个圆柱
• 每条半边上增加一个箭头（也就是一个圆柱+一个圆锥）

有了 Mesh，这些图元也就都可以用求交选中了。这个思路说起来很简洁，但制造了巨大的性能问题，堪称是一个力大砖飞的解决方案。例如一个立方体有 24 条半边、8 个顶点、18 条边和 12 个三角形面，假如每个小球、圆柱和箭头各有 20 个面，

• 在布局模式下，只需要渲染 12 个三角形面；
• 在建模模式下，需要渲染足足 1012 个三角形面。

大致估算 $F$ 个三角形面的 Mesh 有多少图元时，一般按顶点数 $V=\frac{1}{2}F$、边数 $E=\frac{3}{2}F$ 计算，那么半边有 $H=2E=3F$ 条，那么建模模式下就需要额外渲染 $20(V+E+H)=100F$ 的面片😱无怪乎加载了五千面的模型后，Scotty3D 帧数会大幅下降——毕竟此时场景中已经有大约五十万面片（两万五千个辅助图元）了，对 940MX 这样的低端显卡来说负担绝对不轻。更加可怕的是，求交操作必须有真实的几何数据才能完成，也就是场景中真的存在两万多个小球、圆柱或箭头的副本，而不是利用 实例化绘制 (Instantiated Draw) 技术渲染出来的“假象”。如此巨大的 Draw Call 和光栅化开销，我是绝对无法接受的。

上面的估算是基于一个理想均匀 Mesh 假设：所有顶点的度（相邻的面片数）都是 6，因此每个顶点被 6 个面共享、每条边被 2 个面共享。折算一下，每个面占有 $3\times\frac{1}{6}=\frac{1}{2}$ 个顶点、$3\times\frac{1}{2}=\frac{3}{2}$ 条边。

于是我放弃了给每个图元增加 Mesh 的做法，转向另一种比较取巧的思路：能否只和面片求交就判断出使用者想选中的是什么图元呢？顶点和边都是没有体积的，但从使用者的意图角度看，点击面片的边缘可以代表拾取边、点击角可以代表拾取顶点。由于射线求交的返回结果中包含重心坐标，判断相交的位置在不在边缘或顶角上相当容易。获取到重心坐标后，Dandelion 会按如下顺序判断被拾取的是哪种图元：

1. 射线打中靠近顶角的位置（蓝色区域）时代表顶点；
2. 打中比较靠近边界的位置（深绿色区域）时代表半边；
3. 打中靠近边界的位置（浅绿色区域）时代表边；
4. 打中中间位置（白色区域）时代表面片。

借助这种间接选择的方法，无论要拾取的是哪种图元，射线都只需要与面片求交一次，其他图元则不必增加实际存在的 Mesh，也就不必面对 Scotty3D 那样巨大的开销了。

现在我有了拾取操作的实现方案，不过距离真正实现还差一些技术细节。这些细节包括 UI 层面的拾取状态管理，以及 UI→Halfedge Mesh→Mesh→VRAM Buffer 的整个同步过程。

在不同的模式下，可以被拾取的对象包括物体和各种图元，而可以被选中的对象还包括光源。再加上“什么都没有选中”的情况，选择/拾取操作可能的状态会有很多种。加上建模模式下的拾取操作与其他模式不一样，完整的选择/拾取操作逻辑是比较复杂的。整理过后，我给出的实现方案是：

• 用 Controller::on_picking 作为统一入口，响应鼠标点击、生成拾取射线，并根据当前的模式决定转到 pick_object 还是 pick_element
• Controller::pick_object 与 Controller::pick_element 的逻辑很相似，都是先求交然后根据交点判断是否执行拾取，再调用 select
• Controller::select 将直观的“拾取”转换为实际的“选择”，会根据要选择的对象类型调用 select_object/select_halfedge/select_vertex 等不同的函数，最终修改 Controller::selected_element

如果只考虑之前的求交、拾取逻辑，select 与那一大堆 select_ 前缀的函数似乎都有些多余，让这个实现显得很复杂。它们的实际作用也的确不是处理空间上的拾取逻辑，而是更新拾取后的渲染数据，让被选的对象高亮显示。由于实时渲染要先设置数据和状态才能更新画面，我甚至还要再增加一个 unselect 函数，专门负责清理与之前被选对象关联的状态，以免多出一些不该有的高亮来。

完成这些部分之后，选择状态就保存在了 Controller::selected_element 这个属性中。它是一个 SelectableType 类型的变量，而 SelectableType 则是所有可选中类型的联合：

using SelectableType =
    std::variant<std::monostate, Object*, const Halfedge*, Vertex*, Edge*, Face*, Light*>;

当使用者拾取了一个顶点后，select 方法就会更新 selected_element 属性，并附带更新 HalfedgeMesh::inconsistent_element——这代表半边网格上此顶点的信息需要逐帧同步到 GL::Mesh::vertices 中对应的顶点。当使用者通过 toolbar 上的滑动条改变顶点坐标时，Scene::render 方法就会调用 HalfedgeMesh::sync 方法，在渲染画面前完成 HalfedgeMesh→GL::Mesh 的同步（包括内存和显存）。

不得不说，我在写这部分代码之前，从来没有如此频繁地使用过 std::variant、std::visit 和各种各样的 lambda 表达式。甚至还因为与静态变量、静态 lambda 表达式相关的一些生命周期问题，度过了若干苦苦调试的白天——因为那段时间持续无休工作，夜晚早就完全没精神了。

上面谈到的只是局部形变的同步方式，仅适用于单个顶点/边/面片的修改。对于各种改变拓扑的局部操作，以及 Mesh 细分、简化之类的全局操作，Dandelion 会执行全局同步。全局同步由 HalfedgeMesh::global_inconsistent 标记触发，会彻底重写 GL::Mesh 的所有数据。这种同步方式比较常规，这里就简单带过。

渲染：辅助图元与视觉反馈

刚才说图元拾取的时候，我提到

无论要拾取的是哪种图元，射线都只需要与面片求交一次，其他图元则不必增加实际存在的 Mesh

然而尽管无需使用大量的 Mesh，半边、顶点这些图元还是要渲染出来的。而且，如果某个图元被选中了，那么还有必要用另一种颜色高亮显示，提供最基本的视觉反馈。

既然不必用实际存在的 Mesh 来表示图元，那为了降低渲染开销，我就要搬出实时渲染第一要诀了：近似一下，能看就行。所以在 Dandelion 中，

• 顶点是用 GL_POINT 渲染的，通过增大 point size 来避免太小看不见的问题；
• 同理，边是用 GL_LINES 渲染的，调大了 line width；
• 半边的箭头呢？其实它不是真的箭头，而是五条线段伪装出来的。用重心坐标控制作为轴的线段保持在离边很近但又不重叠的位置，再用相对于轴的坐标来添上四条短线段。所有的坐标（长度和位置）都是相对的，无论面片大小都不会出错。

这样一来，绘制辅助图元所需的数据量比 Scotty3D 少了一个量级；而无需几何求交意味着同类的辅助图元可以被并入一个 Draw Call，每帧也只需要增加三个而不是成千上万个 Draw Call。从算法的角度去评估，这大概算不上什么优化，称为取舍——效果和性能之间的取舍——也许更合适。不过这个取舍带来了极明显的性能提升：在两年的教学中，实时渲染性能不再是完成实验的瓶颈，我们再也没有遇到过同学的电脑跑不动实验的事情，这足以让我满意了。

为了尽可能加快渲染，除了面片以外的所有图元都是没有着色计算的，直接使用全局统一的颜色，不存在顶点色和存储顶点颜色的 Buffer。如果我要让选中的图元渲染为蓝色🔵，而其他图元都维持黄色🟡，那么我就不得不在选中时从 Buffer 中删去这个图元，然后在取消选择时把它加回去。对一个很长很长（可能有几万、几十万）图元的 Buffer（相当于数组）做随机删除的代价太大了，这不好。不过我们需要的是高亮效果，只要能看到就可以。那么只要先渲染所有图元，再把被选中的图元复制出来单独渲染盖上去就好了。Controller 类有一个 GL::Mesh 成员 highlighted_element 专门用来存放复制出来的图元，每一帧绘制完其他所有图元之后，会关闭深度测试再把它叠加绘制上去。

如果这种做法继续推广，就得到了分层 (layer) 的渲染策略。比如场景内的物体属于视图层，这种特殊的高亮属于 UI 层，通过 Draw Call 排序实现不同层按顺序叠加。现在 Dandelion 还没有那么多样的渲染需求，所以也没有作正式的分层和 Draw Call 重排处理。不过这是 2.0 版本重要的优化特性之一，期待能早日实现。

下回分解

讲到这里，Dandelion 的搭建工作已经进行了 80%。最后的一部分工作是添加物理动画，但我对此的了解实在少得可怜，虽然在 SiyuanLuo 学弟的帮助下完成了一些简单的模拟，但也还是没有多少值得一提的东西。有的朋友可能还是对这篇文章没有提及几何处理算法感到奇怪，那是因为相比于在框架上实现算法，我更想回忆的是尝试实现交互式编辑的经历。毕竟我所实现的算法都十分经典，又有 Scotty3D 的文档（虽然这部分没有源码）可供参考，一写不好就显得寡淡。

下一篇文章我会简单聊聊 Dandelion 现有的物理动画，之后就是这个系列的尾声——也是我四年助教生涯的尾声了，我想谈谈自己为什么选择做助教、为什么选择做课改，以及四年间对交大计算机本科教学的一些思考。