一、Scatter 在 GTSAM 中到底干什么？
概述
gtsam::Scatter负责把 GaussianFactorGraph 中“局部因子块”散射（scatter）到“全局线性系统结构”中。
它是“因子图 → 线性代数” 的桥梁。
稍微严谨一点
在 GTSAM 的线性化阶段，我们面对的是：
min δ x ∣ A δ x − b ∣ 2 \min_{\delta x} | A \delta x - b |^2δxmin∣Aδx−b∣2
其中：
每个 GaussianFactor 只涉及部分变量
每个变量在全局向量中有一个slot（位置）
Scatter 的任务就是：
把 factor 的局部 Jacobian block，复制到全局系统的正确 block 位置
二、Scatter 的输入和输出
2.1 输入
| 输入 | 含义 |
|---|---|
GaussianFactorGraph | 线性化后的因子集合 |
Ordering | Key → 全局变量顺序 |
VariableIndex | Key → 出现在哪些 factor 中 |
2.2 输出（逻辑意义）
Scatter 本身不直接生成矩阵，而是：
构造Block Index / Slot 信息
为后续构建：
HessianFactorBayesTreeEliminationTree
提供快速访问结构
三、Scatter 的核心数据结构
3.1 Slot（槽位）
在 GTSAM 中，每个变量被映射到一个slot：
Key → Slot Index → (起始列, 维度)例如：
| Key | Slot | Dim |
|---|---|---|
| x1 | 0 | 6 |
| x0 | 1 | 6 |
| x2 | 2 | 3 |
3.2 Scatter 的原子单位
structGTSAM_EXPORTSlotEntry{Key key;size_t dimension;SlotEntry(Key _key,size_t _dimension):key(_key),dimension(_dimension){}std::stringtoString()const;friendbooloperator<(constSlotEntry&p,constSlotEntry&q){returnp.key<q.key;}staticboolZero(constSlotEntry&p){returnp.dimension==0;}};重点：
Scatter 解决的不是“数值问题”，而是“索引 + 布局问题”
3.2.1、SlotEntry 是什么？
SlotEntry= 一个变量在 Scatter 中的“占位符”
它回答三个问题：
- 是谁？→
Key key - 占多大？→
size_t dimension - 怎么排序？→
operator<
Scatter 本质上就是：
FastVector<SlotEntry>3.2.2、结构定义逐行拆解
structGTSAM_EXPORTSlotEntry{struct：纯数据结构GTSAM_EXPORT：- DLL 导出宏（Windows）
- 允许跨库使用
说明 SlotEntry 是公共 ABI 的一部分
1 Key：变量的“符号 ID”
Key key;Key是gtsam::Key本质上是
uint64_t通常由：
- 字符 + index 组合（如
X(5)）
- 字符 + index 组合（如
SlotEntry 不关心变量的类型（Pose / Point / etc）
- 只认
Key
2 dimension：这个变量占几列？
size_t dimension;表示：
- 该变量在线性系统中占用的自由度
例如：
Pose3→ 6Point3→ 3Vector2→ 2
Scatter 后续会计算：
key → dimension → offset → [offset, offset+dim)3 构造函数
SlotEntry(Key _key,size_t _dimension):key(_key),dimension(_dimension){}不做任何检查
不关心：
- dimension 是否为 0
- 是否重复 key
SlotEntry 是“哑结构”，逻辑在 Scatter 里保证
四、Scatter 的核心算法流程
4.1 构造阶段
Scatter(constGaussianFactorGraph&gfg,constOrdering&ordering)这一步做了什么？
- 遍历
ordering - 为每个 key 分配一个 slot
- 查询该变量的维度
- 计算 prefix sum（列偏移）
数学/内存视角
| x1 (6) | x0 (6) | x2 (3) | ^ ^ ^ 0 6 124.2 Scatter 行为（逻辑）
当一个 GaussianFactor 要被处理时：
foreach variable in factor:col=colOffsets_[slot(key)]copy(local_block → global_block)Scatter不关心数值计算是否正确
只关心“放哪”
五、Scatter 在 GTSAM 流水线中的位置
NonlinearFactorGraph ↓ linearize GaussianFactorGraph ↓ Scatter BlockIndex / Slot layout ↓ Eliminate BayesTree / HessianScatter 是Elimination 的前置基础设施
六、FastScatter 扩展应用
FastScatter 代码如下：
classFastScatter:publicgtsam::Scatter{public:FastScatter(constgtsam::GaussianFactorGraph&gfg,constgtsam::Ordering&ordering);};6.1 FastScatter 的设计动机
原版 Scatter 的问题
构造过程涉及：
- Key 查找
- 多次 map / vector 操作
在大规模问题中：
- Scatter 构造本身成为瓶颈
6.2 FastScatter 的核心优化思路
一次性预计算 + 最小化间接访问
典型优化点：
| 优化点 | 原 Scatter | FastScatter |
|---|---|---|
| Key 查找 | map | array / contiguous |
| slot 映射 | 动态 | 预展开 |
| offsets | 即算 | 缓存 |
6.3 FastScatter 的典型内部策略
classFastScatter:publicScatter{std::vector<Key>ordered_keys_;// slot → keystd::vector<size_t>slot_of_key_;// key → slot（压缩）};FastScatter 仍然是 Scatter
它只改变“怎么更快地算 slot”
七、FastScatter 在工程中的实际意义
什么时候需要？
- 大规模 SLAM / STEAM
- Batch 优化
- 高频线性化 + 消元
不需要的时候？
- 小图
- 教学代码
- 非性能关键路径
八、Scatter vs HessianFactor vs Elimination（区分清楚）
| 模块 | 职责 |
|---|---|
| Scatter | 索引 & block 放置 |
| HessianFactor | 数值累加 |
| Elimination | 消元 & 条件化 |
Scatter 不做数值累加
Scatter 不做高斯消元
九、手写极简 Scatter示例
目标：我们这个 Scatter 要干什么？
把一组变量 Key → 映射成线性系统里的列区间
也就是：
Key → dimension → offset → [offset, offset + dim)一、极简 Scatter 的职责（只保留 4 件事）
我们删掉 GTSAM 的一切复杂性，只保留：
- 变量 Key
- 变量维度 dim
- 排序
- offset 计算
不做的事情：
- 不支持动态 factor
- 不支持多种 elimination
- 不支持 BayesTree
- 不做错误检查
二、极简 SlotEntry
usingKey=uint64_t;structSlotEntry{Key key;size_t dim;size_t offset;// 线性系统中的起始列SlotEntry(Key k,size_t d):key(k),dim(d),offset(0){}booloperator<(constSlotEntry&other)const{returnkey<other.key;}};对比 GTSAM：
- GTSAM 的
SlotEntry不存 offset - 我们为了展示显式存出来
三、极简 Scatter 类
classMiniScatter{public:// 添加变量voidadd(Key key,size_t dim){slots_.emplace_back(key,dim);}// 排序 + 计算 offsetvoidfinalize(){std::sort(slots_.begin(),slots_.end());size_t cur=0;for(auto&s:slots_){s.offset=cur;cur+=s.dim;}total_dim_=cur;}// 查询size_toffset(Key key)const{for(constauto&s:slots_){if(s.key==key)returns.offset;}throwstd::runtime_error("Key not found");}size_tdim(Key key)const{for(constauto&s:slots_){if(s.key==key)returns.dim;}throwstd::runtime_error("Key not found");}size_ttotalDim()const{returntotal_dim_;}voidprint()const{for(constauto&s:slots_){std::cout<<"Key "<<s.key<<" dim="<<s.dim<<" offset="<<s.offset<<std::endl;}}private:std::vector<SlotEntry>slots_;size_t total_dim_{0};};四、如何使用这个 Scatter
intmain(){MiniScatter scatter;// 假设这是 ordering + factor 推出来的scatter.add(1,6);// Pose3scatter.add(3,3);// Point3scatter.add(2,6);// Pose3scatter.finalize();scatter.print();std::cout<<"Total dim = "<<scatter.totalDim()<<std::endl;}输出示例：
Key 1 dim=6 offset=0 Key 2 dim=6 offset=6 Key 3 dim=3 offset=12 Total dim = 15五、这一刻，已经“本质等价于 Scatter”
现在已经理解了：
| GTSAM Scatter | 手写的 |
|---|---|
| SlotEntry | SlotEntry |
| Ordering | sort by key |
| Column index | offset |
| Linear system layout | totalDim |
六、Scatter 在矩阵构建中的真实用途
当构建线性系统：
A.block(row,scatter.offset(key),rdim,scatter.dim(key))+=J;这句代码所有 magic 都来自 Scatter。
七、为什么 GTSAM 的 Scatter 比这个复杂？
GTSAM 版本额外支持：
| 能力 | 原因 |
|---|---|
| Ordering 优先 | 消除顺序 |
| Zero-dim slot | ordering-only 变量 |
| 动态 factor | graph-driven |
| 无 offset 成员 | 避免冗余 |
| FastVector | cache-friendly |
十、总结
gtsam::Scatter是一个“结构构建器”，不是一个“数值求解器”。
它的存在是为了：
- 把“因子图世界”
- 映射到
- “稀疏线性代数世界”
