1.数据结构专题(三) | iVox (Faster-Lio): 智行者高博团队开源的增量式稀疏体素结构 & 源码解析

数据结构专题(三) | iVox (Faster-Lio): 智行者高博团队开源的增量式稀疏体素结构 & 源码解析

       在年初，智行者高博团队和清华大学联合发表了Faster-Lio的工作，该成果收录于IEEE RA-Letters，其开源代码展示了如何通过增量式稀疏体素结构iVox，提升Lidar-inertial Odometry（LIO）的算法效率。相较于MaRS-Lab的云手机系统源码是什么FastLio2，Faster-Lio在保持精度的同时，得益于iVox的设计，尤其是在增删操作上的高效性，显著减少了维护local map和查询近邻的时间。

       高博在知乎文章中详细解读了Faster-Lio，特别是iVox的创新设计。我们从数据结构的everyonepiano源码角度出发，通过简化的方式解释iVox：首先，利用哈希表（如C++的std::unordered_map）将体素空间坐标作为key，通过精心设计的空间哈希函数映射到有限的索引空间，实现快速的增删操作。哈希表的优化和抗冲突设计使得碰撞概率极低，即使有冲突，引人源码也能快速忽略。

       此外，iVox采用了伪希尔伯特曲线（PHC）来组织体素，这种曲线将高维空间划分为一系列单元，并通过分段曲线连接，便于一维空间索引。空调源码尽管希尔伯特曲线是理想化的，但在工程实践中，PHC在接近填充空间的同时，保持了可接受的实现复杂度。

       Faster-Lio的源码解析显示，核心在于IVox类，dbtuils源码其中grids_map_和grids_cache_是关键数据结构。AddPoints()负责增量点的添加，通过哈希查找确保高效，而GetClosestPoint()则通过kNN搜索找到最近邻。

       尽管论文与代码存在一些差异，如体素过时删除策略，但整体上，iVox的设计思路清晰，哈希表和空间组织策略的结合使得其在实际应用中表现出色。然而，对于体素内点的处理，实际工程中可能更倾向于简化，例如通过体素降采样和八叉树结构，这些方法在某些场景下可能会比PHC更易于实现。

       最后，作者WGH无疆强调，iVox是简单实用的解决方案，但希尔伯特曲线在工程实践中的优势可能有限，尤其是在点数不多的情况下。未来，他们将探讨其他类似的工作，如CMU的Super Odometry，其中可能结合了哈希表和八叉树。欢迎大家继续关注和交流。