1

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

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

我已经通过 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 魔法以某种方式进行比较？

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

谢谢，安迪。

4

2 回答 2

2

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

你的函数看起来很好写。我怀疑您是否可以比您进一步优化这样的单个测试（或者如果可以，它不会是戏剧性的）。如果要优化整个操作，则需要在更高级别上进行：

  • 您可以尝试另一种结构（例如，kd-tree 而不是八叉树）或利用数据中某些模式的全新算法。
  • 您可以将循环从“for each point check otrees”反转为“for each otree check points”，这样您就可以一遍又一遍地重用边界数据。
  • 您可以确保以最有效的方式访问数据（可能是点）（即顺序而不是随机跳转）。
  • 通过重组循环，您可以使用 SSE 在一条指令中执行多个边界测试（没有分支！）。
于 2013-02-04T07:34:01.087 回答
-1

对我来说看起来不错。我能想到的唯一微优化是将 *_p 声明为静态

于 2013-01-29T09:26:29.933 回答