Manifold k-NN: Accelerated k-NN Queries for Manifold Point Clouds

一句话总结

把只能查最近邻（\(k=1\)）的动态规划最近邻搜索（DP-NNS）推广到任意 \(k\)，得到一套面向流形采样点云、比 \(kd\)-树在”体到面”查询中快 1~10 倍，并原生支持前缀子集查询与点删除的动态 \(k\)-NN 框架。

研究背景

• 领域现状：\(k\)-NN 搜索是几何处理与图形学的基础原语（法向估计、去噪、隐式重建、点云配准都要用）。主流做法是 \(kd\)-树、八叉树、\(R\)-树等空间划分结构。Wang 等人 2025 年提出的 DP-NNS 利用增量 Voronoi 图，为每个站点维护一个”后继列表”，在流形数据上比传统结构更快。
• 核心痛点：一是这些空间划分结构是”流形盲”的——它们按坐标轴或包围盒切分整个三维空间，不理会点其实只分布在二维流形（曲面）上。在”查询点散布于体积、目标点约束在曲面”的体到面场景（如 MLS 投影、SDF 求值）里，剪枝失效、遍历节点过多。二是 DP-NNS 虽然快，却只能查 \(k=1\)，无法直接给出局部邻域统计；朴素地在对偶 Delaunay 图上做广度优先扩展会带来大量冗余的几何谓词计算。
• 本文 idea：一个几何观察——若 \(p_i\) 是查询 \(q\) 在 \(P\) 中的最近邻，则第二近邻要么落在前缀集合 \(P_{1:i-1}\)，要么落在 \(p_i\) 的后继列表里。递归地套用这一原则，就能把 \(k\)-NN 拆成一串在动态划分的插入历史区间上协同进行的 1-NN 查询。

方法

整体框架：把点集按插入顺序（birth-time）编号，\(k\)-NN 搜索被表述为对”插入历史”区间的递归划分。先做一次标准 1-NN 查询确定最近邻并顺手缓存路径上的”过渡站点”，随后每确认一个近邻，就遍历它的后继列表把候选插入一个容量为 \(k\) 的有序候选表，超出前 \(k\) 名的自然被剪枝。

flowchart LR
  A["按插入序编号 + 增量 Delaunay 建后继表"] --> B["1-NN 查询并缓存过渡站点"]
  B --> C["确认第 i 近邻"]
  C --> D["遍历其后继列表插入候选表 N"]
  D --> E{"已得 k 个?"}
  E -- 否 --> C
  E -- 是 --> F["返回 k 近邻"]

关键设计：

• 状态转移与核心定理：给定按插入序排好的 \(k\) 个近邻，其下标把整个插入历史 \([1,n]\) 切成 \(k+1\) 个互不相交的区间。定理保证第 \((k+1)\) 近邻必然落在前缀区间 \(P_{1:i_1-1}\)，或落在这 \(k\) 个近邻之一的后继列表 \(L_{i_j}\) 中。证明分两种情况：落在最前缀区间时它就是该前缀的 1-NN；否则它插入时必然剪掉了某个已知近邻的 Voronoi 单元，因而按定义会进入后者的后继列表。这样就把昂贵的全局搜索限制到少数几个受控子集。
• 过渡站点（Transition Sites）缓存：定义为满足 \(p_j = \Phi_{1:j}(q)\) 的站点，即”在自己插入那一刻恰好是 \(q\) 的最近邻”。这些点必然出现在初始 1-NN 增量搜索路径上，因此一次 1-NN 查询顺带全部收集，避免了在前缀区间 \([1,i_1-1]\) 里再做穷举。
• 复杂度：预处理由增量 Delaunay 构建主导，三维平均 \(O(n\log n)\)（最坏 \(O(n^2)\) 罕见）。后继列表平均长度 \(O(\log n)\)，对 \(k\) 个近邻各遍历一次，\(k\)-NN 查询期望复杂度 \(O(k\log n)\)。
• 前缀子集与多分辨率查询：只要忽略下标超过阈值 \(m\) 的候选，搜索就严格限制在前缀 \(P_{1:m}\)，零额外开销。若 birth-time 按由粗到细的采样顺序组织，就能在任意几何分辨率上查询而不改数据结构，天然适配 LOD 与流式几何的时序查询。
• 点删除的局部更新：后继列表与构建历史深度耦合，删点很棘手。作者用两条引理把问题局部化——引理 4.2 说明不涉及被删点 \(p_i\) 的邻接关系在删除后不变；引理 4.3 说明新出现的邻接只可能发生在 \(p_i\) 的原邻居之间，且其新 Voronoi 边必落在原 \(\mathrm{Cell}(p_i)\) 内部。于是只需对”曾与 \(p_i\) 相邻的站点”（约 25~35 个）做一次局部增量 Delaunay 重建，并用共享 Voronoi 顶点是否落在原单元内来过滤伪邻接，即可保证删除后的后继表与”从未插入 \(p_i\)”的构建结果数学等价。

实验结果

在体到面场景（\(10^6\) 个查询点分布于 \(2\times\) 包围盒，\(k=20\)）下与四类主流结构对比，本文在各标准模型上均取得最低平均查询时间，相对 \(kd\)-树等达到 1~10 倍加速；对 1000 万点的超大规模数据，相对专为大规模优化的 ArborX 也有 1~3 倍加速。

方法	Bunny	Kitten	Armadillo	Lucy
KD-tree	5.026	9.562	11.56	10.13
R*-tree	3.589	6.013	6.193	4.867
Octree	13.38	23.57	29.37	25.28
BD-tree	7.631	18.55	118.7	38.83
ArborX	3.744	6.608	7.675	5.772
DT-BFS	2.681	3.337	3.577	4.024
Ours	1.718	1.789	1.972	2.264

（平均查询时间，单位 \(\mu s\)，\(k=20\)，越小越好；节选自不同模型对比。）

其余实验用文字补充：在 Lucy 模型上随 \(k\) 变化（\(k=5\sim50\)），本文查询时间也全面领先，\(k=5\) 时仅 0.929 \(\mu s\)。前缀查询方面，扫描收敛分析（100 帧渐进扫描的二分搜索）比 \(kd\)-树 / \(R\)-树快数倍；时序缺陷定位中随机切换前缀 \(m\) 时本文维持每秒 5000~10000 次查询，而传统结构因每次都要重建仅 10~20 次，约 250~500 倍加速。代价是预处理约比 \(kd\)-树慢 20 倍，但在”构建一次、查询数百万次”的场景下这一开销被摊薄。动态基准（插入 / 查询 / 删除混合）中，尽管单次删除较慢，本文凭借查询优势取得更优的端到端吞吐。

亮点与局限

• 亮点：
  • 把成熟的 DP-NNS 从 \(k=1\) 干净地推广到任意 \(k\)，理论清晰（定理 + 两条删除引理），期望复杂度 \(O(k\log n)\)。
  • 前缀子集查询”零开销”是很实用的副产品，直接支持 LOD、流式扫描、时序回放等非顺序访问场景，相对重建式基线优势巨大。
  • 补齐了点删除算子，且局部重建规模与总点数无关（恒约 33 点），形成完整的动态邻域维护套件。
• 局限：
  • 预处理（增量 Delaunay + 后继表）约比 \(kd\)-树慢 20 倍，只有在查询密集场景才划算；一次性或删除密集的工作负载并不占优。
  • 方法本质面向 2-流形采样点云，对均匀体分布数据只是”有竞争力”而非领先；对高维或非流形数据的适用性未展开。
  • 单次删除操作比传统结构慢，需要靠查询收益来补偿，端到端优势依赖工作负载中查询占比足够高。

延伸思考

• 该框架把”最近邻查询”与”Voronoi/Delaunay 的增量构建历史”绑定，很自然地衔接 POCO、Point-NeRF 这类以海量 \(k\)-NN 为核心瓶颈的神经隐式重建 / 点云渲染管线——预处理成本一次摊销、查询极快，恰好契合它们在 marching-cubes 网格或相机光线上发起数百万次查询的模式。
• “零开销前缀查询”提示了一个更广的方向：把时间 / 分辨率维度编码进插入顺序，让同一结构服务多分辨率与时序回溯，值得思考能否推广到 kd-树之外的其它增量结构。
• 预处理偏慢与删除偏慢是主要短板，若能把增量 Delaunay 构建 GPU 化，或与 ArborX 式 BVH 遍历融合，可能在保持查询优势的同时压低建表成本。