摘要

本文先介绍了路径与贝塞尔曲线相关概念，阐述了传统路径的局限，引出 Figma 的矢量网络概念及其优势，接着详细讲解矢量网络背后的图结构、填充相关算法，如最小循环基算法，还探讨了图中的交点、曲线边等多种特殊情况的处理，最后提及部分省略话题和未来研究方向。

一、传统路径相关概念

• 路径（Paths）是由一系列线条和曲线组成，可由节点（nodes，也称为顶点 vertices）和边（edges）构成。节点和边可以描述一个路径，如一个路径可以表示为一系列节点(0, 1, 2, 3, 4)，也可以是组成它的边的序列(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)。
• 边分为直线和曲线两种类型，曲线边是贝塞尔曲线（Bezier curves）。贝塞尔曲线由四个点定义，两个节点的位置构成曲线的起点和终点，每个节点还有一个控制点。通过控制点可以控制曲线的形状，在大多数应用中，这些控制点显示为从各自节点延伸出来的手柄。
• 计算机绘制曲线是通过将曲线分割成直线并绘制这些直线来实现的，分割的直线越多，曲线就越平滑。计算曲线上的点可以使用德卡斯特里奥算法（De Casteljau's algorithm），该算法还可用于细分贝塞尔曲线。

二、传统路径的局限性

• 路径是单一连续链，这意味着每个节点只能连接到一到两个其他节点，三路交叉无法使用单个路径创建，要创建三路交叉，必须使用两个或更多路径。这就涉及到处理不同路径的定位和分组问题，并且对单个路径的更改可能导致对多个其他路径的更改。虽然经验丰富的设计师可以提前规划来解决这些问题，但在某些情况下，这种限制会带来很多麻烦。

三、Figma 的矢量网络（Vector Networks）

• 概念：2016 年，Figma 引入了矢量网络，它解除了“单一连续”的限制，允许任意两个节点无限制地连接在一起。例如对于一个立方体形状，使用传统路径至少需要 3 个不同路径来描述，而使用矢量网络，只需要简单地抓住一条边并移动它，形状就会如预期那样变化，并且可以更轻松地进行一些操作，如给立方体添加一个洞。矢量网络虽然不能创建其他工具无法创建的东西，但它确实减少了创建过程中的很多阻碍，并且实现了以前不可能的工作流程。
• 实现：

  （一）图（Graph）结构

    - **节点（Nodes）**：图中的节点有两个属性，一个唯一的 id 和一个位置。
    - **边（Edges）**：边是两个节点之间的连接，每条边由两个边部分组成，一个边部分包含一个节点的 id 和一个可选的控制点。如果边的控制点被省略，该边就变成一条直线。
  

  （二）填充（Filling）相关

    - **循环（Cycles）**：在矢量网络中，填充工具允许对图的不同“区域”进行填充切换，这些区域可以定义为一个节点 id 的循环序列。但是在一个循环中，可能存在多个视觉上不同的“区域”，需要找到其中的“小循环”，这就涉及到最小循环基（Minimal Cycle Basis）的概念。
    - **最小循环基算法**：通过确定基于左右方向选择哪条边来找到最小循环基。在图中选择最左边的节点开始，按照顺时针（CW）或逆时针（CCW）的规则选择边，当形成一个循环后，移除循环的第一条边和相关的“细丝”（Filaments，只有一个相邻边的节点），然后重复这个过程，直到没有细丝为止，这样就得到了图的最小循环基。
    - **数学原理**：在这个过程中，需要用到向量的行列式（determinant）来确定一条边相对于另一条边的顺时针或逆时针方向。通过计算两个向量形成的平行四边形的行列式，可以判断一个向量是在另一个向量的左边还是右边，从而确定选择哪条边更合适。
  

  （三）图中的交点（Intersections in the graph）

    - **交点处理**：图中的边可能会相交，这给定义“填充区域”带来了困难。Figma 解决这个问题的方法是“扩展图”（Expanding the graph），即对于每个交点，在交点处创建一个节点，然后将相交的边在该点分割成新的边。对于有多个交点的边，将交点的数据结构进行组织，创建交点映射（Intersection map），在遇到交点时创建节点并添加到交点映射中，按照一定规则创建新的边。
    - **特殊情况**：
        - **自相交（Self - intersection）**：三次贝塞尔曲线可能会自相交，需要检查每个三次贝塞尔边是否自相交，并在自相交处进行扩展处理。
        - **曲线边（Curvy edges）**：在处理由三次贝塞尔曲线定义的边时，原用于处理直线边的最小循环基算法会变得复杂。例如在选择哪条边更合适（如更逆时针的边）时，不能简单地将贝塞尔曲线转换为由起点和终点定义的直线来处理。针对这个问题，有一些解决方案，如将贝塞尔曲线的起始切线转换为由起始节点和控制点构成的直线来获取初始角度，还有取曲线上特定 t 值的点或者按照曲线长度取点等方法，但都存在一些局限性。作者提出了一种“激光”（Lasers）方法，通过将贝塞尔曲线分割并离散化为多个点，检查从起始节点到这些点的直线是否与其他边相交来确定合适的边，但这种方法在某些特殊情况下也会失败，进而提出改进方案，如在遇到特殊情况时创建一条从当前点到前一个点的直线用于相交测试。
        - **平行边（Parallel edges）**：当两条边平行时，确定哪条边更好是比较困难的，作者提出了几种可能的解决方案，如取曲线上特定 t 值的点、按照曲线长度取点、“激光”方法等，并针对平行边与前一条边的不同关系（如一条或两条边平行于前一条边）进行了讨论。
        - **循环嵌套（Cycles inside of cycles）**：在处理有循环嵌套的图的填充时，需要考虑如何定义内部和外部边界。一种方法是使用奇偶规则（Even - odd rule），即从一个点向任意方向发射一条无限长的“激光”，如果与奇数个“墙”（边）相交，则该点在形状内部，否则在外部。在处理嵌套循环时，还引入了直接子循环（Direct subcycles）的概念，父循环可以有多个直接子循环，但由于非相交规则，一个子循环只能有一个父循环。根据这个概念，在绘制循环时，从最外层的“填充”循环开始，然后查看其子循环，如果子循环与其父循环有相同的填充设置，则不需要绘制该子循环。
        - **连续循环（Contiguous cycles）**：图可能有多个“循环簇”，可以使用深度优先遍历（depth - first traversal）来找到这些连续循环，但要注意不能通过标记为交叉（crossings）的边爬到相邻节点。
        - **部分扩展（Partial expansion）**：当鼠标悬停在由交点定义的区域时，显示的是扩展图的一个循环。如果直接扩展图来定义这个区域，可能会不必要地扩展一些交点。所以可以采用部分扩展图的方法，只扩展定义所选循环的交点，基本实现方法是在创建扩展图时为每个扩展节点添加元数据，记录是由原始图的哪两条边以及在什么 t 值下产生的交点，当点击循环时，遍历每个节点，如果节点存在于扩展图但不存在于原始图，则将其添加到新的部分扩展图中。
  

四、省略话题和未来研究方向

• 省略话题：
  • 连接（Joins）：Figma 提供了三种类型的连接（圆形、尖形和方形），但本文未讨论如何实现这些不同类型的连接。
  • 笔画对齐（Stroke align）：Figma 还提供了三种图形笔画对齐方式（中心、内部和外部），本文未涉及如何确定内部或外部性以及在图没有循环时会发生什么情况。
  • 布尔运算（Boolean operations）：像大多数矢量图形工具一样，Figma 也提供布尔运算，但本文未讨论如何实现这些运算。
• 未来研究方向：
  • 填充的不同处理方式：作者对探索不同的填充处理方式感兴趣，如使用多个不同的“填充层”并以一个矢量对象作为参考，这样可以解决“一个图，多种颜色”的问题，而无需复制图层并在后续修改时保持多个矢量对象同步。
  • 图形动画（Animating the graph）：作者希望探索在给定类似 After Effects 的表达式和基于参考的系统下，结合矢量网络可以实现什么效果，或者利用类似 Blender 的着色器编辑器或 Fusion 的基于节点的工作流程的节点编辑器来实现动画效果。