c - 优化轴对齐边界框检查

Question

我目前正在大量使用点云，并且我已经实现了一种分割算法，该算法将具有特定最大距离的点聚类成多个段。

为了优化它，我给每个线段一个轴对齐的边界框，以检查给定点是否可能与线段匹配，然后再仔细观察并迭代这些点并计算距离(我实际上使用一个八叉树，修剪掉大部分点。)

我已经通过 gnuprof 运行了我的程序，这就是结果:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 52.42      5.14     5.14 208995661     0.00     0.00  otree_node_out_of_bounds
 19.60      7.06     1.92 189594292     0.00     0.00  otree_has_point_in_range
 11.33      8.17     1.11   405834     0.00     0.00  otree_node_has_point_in_range
  9.29      9.08     0.91   352273     0.00     0.00  find_matching_segments
 [...]

如您所见，大部分计算时间都花在了 otree_node_out_of_bounds 中，其实现如下:

int otree_node_out_of_bounds(struct otree_node *t, void *p)
{
    vec3 *_p = p;
    return (_p->x < t->_llf[0] - SEGMENTATION_DIST 
        || _p->x > t->_urb[0] + SEGMENTATION_DIST
        || _p->y < t->_llf[1] - SEGMENTATION_DIST 
        || _p->y > t->_urb[1] + SEGMENTATION_DIST
        || _p->z < t->_llf[2] - SEGMENTATION_DIST 
        || _p->z > t->_urb[2] + SEGMENTATION_DIST);
}

其中 SEGMENTATION DIST 是一个编译时常量，以允许 gcc 进行一些常量折叠。 _llf 和 _urb 是 float[3] 类型，表示八叉树的边界框。

所以，我的问题基本上是，是否可以对这个函数做一些偷偷摸摸的优化，或者更一般地说，是否有更有效的方法来对 AABB 进行边界检查，或者用更不同的方式来表达，可以我通过使用一些 C/gcc 魔法以某种方式加快了比较速度？

如果您需要更多信息来回答这个问题，请告诉我:)

谢谢，安迪。

Answer 1

这是一个被调用了很多次的小叶函数。分析结果总是高估了这些函数的成本，因为测量调用的开销相对于函数本身的成本来说很大。通过正常优化，整个操作的成本(在最终调用此测试的外部循环级别)将占整个运行时间的百分比较低。您可以通过使该函数在启用分析的情况下内联(例如使用 __attribute__((__always_inline__)))来观察这一点。

你的函数看起来没问题。我怀疑您是否可以比您更进一步地优化单个测试(或者如果可以，它不会是戏剧性的)。如果你想优化整个操作，你需要在更高的层次上进行:

• 您可以尝试另一种结构(例如，kd 树而不是八叉树)或一种利用数据中某些模式的全新算法。
• 您可以将循环从“针对每个点检查 otrees”反转为“针对每个 otree 检查点”，这样您就可以反复使用边界数据。
• 您可以确保以最有效的方式(即按顺序而不是随机跳跃)访问数据(可能是点)。
• 通过重组循环，您可以使用 SSE 在一条指令中执行多个边界测试(没有分支!)。