Spatial Index 与 Working Setworking-set

空间索引回答“附近可能有谁”，Working Set 回答“Renderer 现在应该为谁付出成本”。它们不是同一个概念。

学习目标

  • 理解全量扫描为什么会进入 Camera 热路径；
  • 手算一次 AABB 相交和 RBush 分支剪枝；
  • 推导 Visible + Overscan + Pinned；
  • 计算前后两帧的 enter / stay / exit；
  • 用指标证明 Document 与 Renderer 容量已经解耦。

1. 为什么只做“视口裁剪”还不够

最直接的实现会在每次平移时遍历所有节点：

const visible = document.values().filter((node) => intersects(node.bounds, viewBounds))

这虽然只绘制 visible 节点，但查询仍然是 O(N)。当 pointermove 每秒触发几十次、Document 有几万节点时，主线程仍会反复扫描完整作品。

空间索引的作用不是让一次矩形比较更快，而是提前组织节点，让查询跳过整片不相交区域。

2. RBush 里保存什么

RBush 属于 R-tree：叶子保存节点的世界坐标 AABB，中间分支保存一组孩子的最小外包矩形。

interface SpatialEntry {
  nodeId: string
  minX: number
  minY: number
  maxX: number
  maxY: number
}

圆形、旋转矩形或路径也先计算 AABB 做粗筛；框选或命中需要精确时，再对少量候选执行真实几何判断。粗筛宁可多返回附近节点，不能漏掉真实可见节点。

3. 手算一次分支剪枝

四个节点：

节点 World AABB
A [0, 0, 80, 60]
B [120, 40, 180, 140]
C [40, 220, 140, 320]
D [220, 180, 280, 260]

教学分组：

Root [0,0,280,320]
├─ G1 [0,0,180,140]
│  ├─ A [0,0,80,60]
│  └─ B [120,40,180,140]
└─ G2 [40,180,280,320]
   ├─ C [40,220,140,320]
   └─ D [220,180,280,260]

Camera 查询 Q=[100,10,300,150]：Root 相交；G1 相交，继续检查 A/B；G2 的 minY=180 > Q.maxY=150，因此 C/D 整组跳过；最终只有 B 命中。

矩形相交：

function intersects(a: Bounds, b: Bounds): boolean {
  return !(
    a.maxX < b.minX || a.minX > b.maxX ||
    a.maxY < b.minY || a.minY > b.maxY
  )
}

4. Camera 移动和节点移动的区别

Camera 平移/缩放
  → 重新计算查询 Bounds
  → spatialIndex.search()
  → 不修改索引

节点移动/缩放/旋转
  → World AABB 改变
  → remove(oldEntry) + insert(newEntry)

新增节点 insert，删除节点 remove。不要在 Camera 每次变化时重建整棵树。

Core 只依赖 SpatialIndex 端口。LinearSpatialIndex 适合教学和小数据测试；生产大文档可替换为 RBushSpatialIndex。

5. Working Set 由三部分组成

Visible：屏幕当前能看到
Overscan：视口外即将进入的一圈
Pinned：正在拖动、编辑或播放，不能中断

集合公式：

VisibleSet = index.search(exactBounds)
NearbySet  = index.search(expandedBounds)
WorkingSet = NearbySet ∪ PinnedSet

Overscan 是 NearbySet - VisibleSet。如果配置使用屏幕像素，必须换成 World 单位：

overscanWorld = overscanPx / camera.zoom

否则 zoom 改变时预加载带在屏幕上会忽宽忽窄。

6. 用四个节点推导 Working Set

A：位于 Overscan
B：当前 Visible
C：远离 Camera
D：被拖出视口，但仍 Pinned

于是：

VisibleSet = { B }
NearbySet  = { A, B }
PinnedSet  = { D }
WorkingSet = { A, B, D }

C 仍然存在于 Document、SpatialIndex 和持久化存储，只是当前不创建 Renderer handle。

7. 前后帧为什么要做集合差分

previous = { B, C }
next     = { A, B, D }

enter = next - previous = { A, D }
stay  = next ∩ previous = { B }
exit  = previous - next = { C }
集合 动作 关键点
enter hydrate 创建 handle、获取资源租约
stay reuse/update 不重复创建对象
exit grace 后 dehydrate 释放运行时成本，不删 Document

如果每帧销毁并重建整个 Working Set，空间索引节省的查询成本又会被对象抖动抵消。

8. 完整算法

function calculateFrame(view: ViewState, pinned: Set<string>) {
  const exact = view.worldBounds
  const expanded = expand(exact, view.overscanPx / view.camera.zoom)
  const visible = ids(spatialIndex.search(exact))
  const nearby = ids(spatialIndex.search(expanded))
  const next = union(nearby, pinned)

  return {
    visible,
    workingSet: next,
    enter: difference(next, previous),
    stay: intersection(next, previous),
    exit: difference(previous, next),
  }
}

关系闭包也可能加入 Working Set，例如箭头进入时补充端点节点。但必须设置深度或数量上限，防止一条关系链把整幅 Document 拉进当前工作集。

9. 操作 Demo

Demo 固定保存 1,200 个节点：

  1. 记录初始 Document / candidates / Working Set / handles；
  2. 平移到远区，观察 Document 不变、enter/exit 变化；
  3. 把 overscan 从 180px 改成 0，快速平移并观察加载频率；
  4. 改成 600px，观察 Working Set 和内存代价；
  5. 拖动一个节点越过视口边界，确认 Pinned 让交互不中断；
  6. 等待稳定后检查 handle 数接近 Working Set。

10. 如何验收“真的有界”

Document：1,200 → 12,000
Working Set：仍主要由视口面积和节点密度决定
Renderer handles：稳定后接近 Working Set
Camera 移动：不重建完整 SpatialIndex

若 Document ≈ Working Set ≈ renderedObjectCount，画布只是坐标可以无限平移，并没有实现容量虚拟化。

常见错误

  • 用 Canvas Local Bounds 查询 World 索引；
  • Camera 移动时更新所有索引项；
  • 把 Visible 直接等同于 Working Set；
  • 忽略 Pinned，拖拽一出视口就丢失 handle；
  • overscan 不除 zoom；
  • 只隐藏离屏对象，不释放对象与资源；
  • 为了关系闭包把整张图无界拉入 Working Set。

课后实验

分别实现 Linear 与 RBush 两个 SpatialIndex，生成聚集分布和均匀分布节点。记录搜索候选数、查询耗时与 Working Set 大小；不要只比较一次查询，要模拟连续 Camera 平移。