优化轴对齐边界框检查

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-tree而不是八叉树)或一种全新的算法来利用数据中的某些模式。

• 您可以将循环从"for each point check otrees“转换为"for each otree check points"，这允许您一遍又一遍地重用边界数据。

• 您可以确保您正在访问数据(points，可能)以最有效的方式(即按顺序而不是随机跳来跳去)。

• 通过重构的循环，您可以使用SSE在一条指令中执行多个边界测试(没有分支！)。

Answer 2

我觉得挺不错的。我能想到的唯一微优化就是将*_p声明为静态