使用libigl的KNN代码运行极慢甚至停滞，如何优化及排查问题？

一、核心问题分析 #

1. 函数误用（可能的逻辑错误） #

你当前调用igl::knn是基于八叉树查找网格顶点的最近邻，但需求是找“网格上的最近邻点”——这里的“网格上”通常指网格表面（包含三角面内部的点），而非仅顶点。如果是这个需求，igl::knn完全不符合预期，不仅结果错误，还会因为方向错了导致后续性能问题。

2. 八叉树构建未优化 #

默认调用igl::octree(V, O_PI, O_CH, O_CN, O_W)时，没有指定八叉树的最大深度或最小单元格尺寸，对于5万顶点的网格，可能生成的八叉树划分过粗，导致KNN查询时需要遍历大量节点，性能急剧下降。

3. KNN查询的冗余操作 #

虽然每组仅25个查询点，但八叉树结构不合理的情况下，每个查询都要遍历大量分支，叠加后出现卡顿甚至停滞。

二、针对性优化方案 #

方案1：如果需求是找网格表面的最近点（推荐） #

替换igl::knn为igl::point_mesh_squared_distance，该函数专门计算点到三角网格的最近点，且支持八叉树加速：

#include <igl/point_mesh_squared_distance.h>

// ... 原有代码 ...

for (int i=0;i< vec_pts.size();i++)
{
  Eigen::MatrixXd query = vec_pts[i];
  Eigen::VectorXd sqr_dists;
  Eigen::VectorXi I; // 最近面的索引
  Eigen::MatrixXd closest_points; // 网格表面上的最近点坐标
  const double t_before = igl::get_seconds();
  // 使用八叉树加速点-网格最近点计算
  igl::point_mesh_squared_distance(query, V, F, sqr_dists, I, closest_points, O_PI, O_CH, O_CN, O_W);
  const double t_after = igl::get_seconds();
  std::cout << "time for surface nearest neighbor query in sec " << t_after - t_before << std::endl;
}

方案2：如果确实需要找顶点的KNN #

优化八叉树构建

调用igl::octree时指定最大深度参数（比如设置为10-12，根据网格尺寸调整），避免划分过粗：

// 增加最大深度参数，比如设置为10
const int max_depth = 10;
igl::octree(V, max_depth, O_PI, O_CH, O_CN, O_W);

改用FLANN加速KNN

IGL也支持FLANN库进行更高效的KNN查询，性能比默认八叉树KNN更优：

#include <igl/knn.h>
#include <flann/flann.hpp>

// ... 原有代码 ...

// 构建FLANN索引
flann::Index<flann::L2<double>> index(V.transpose(), flann::KDTreeIndexParams(10));
index.buildIndex();

for (int i=0;i< vec_pts.size();i++)
{
  Eigen::MatrixXd query = vec_pts[i];
  Eigen::MatrixXi I;
  Eigen::MatrixXd D;
  const double t_before = igl::get_seconds();
  // 查询1近邻
  igl::knn(query, V, 1, index, I, D);
  const double t_after = igl::get_seconds();
  std::cout << "time for vertex KNN query in sec " << t_after - t_before << std::endl;
}

注意：需要确保编译环境链接FLANN库。

三、额外性能建议 #

• 提前将所有查询点合并为一个大矩阵，一次性完成查询，避免多次调用的开销。
• 编译时开启O3优化（-O3编译参数），大幅提升数值计算性能。

内容的提问来源于stack exchange，提问作者user27665