1

我使用分析器查看了一些运行速度不够快的代码。发现下面这个函数占用了大部分时间，而这个函数中一半的时间都花在了floor. 现在，有两种可能性：优化这个函数或者上一层，减少对这个函数的调用。我想知道第一个是否可行。

int Sph::gridIndex (Vector3 position) const {
    int mx = ((int)floor(position.x / _gridIntervalSize) % _gridSize);
    int my = ((int)floor(position.y / _gridIntervalSize) % _gridSize);
    int mz = ((int)floor(position.z / _gridIntervalSize) % _gridSize);

    if (mx < 0) {
        mx += _gridSize;
    }
    if (my < 0) {
        my += _gridSize;
    }
    if (mz < 0) {
        mz += _gridSize;
    }

    int x = mx * _gridSize * _gridSize;
    int y = my * _gridSize;
    int z = mz * 1;
    return x + y + z;
}

Vector3只是一些简单的类，它存储三个浮点数并提供一些重载运算符。_gridSize是类型int并且_gridIntervalSize是float. 有 _gridSize ^ 3 个桶。

该函数的目的是提供哈希表支持。每个 3d 点都映射到一个索引，位于大小为 _gridIntervalSize ^ 3 的相同体素中的点应该落在同一个桶中。

4

3 回答 3

2

涉及数学时的第一条优化规则：消除除法、平方根和三角函数。

inverse_size = 1 / _gridIntervalSize; ....that should be done only once, not once per call.

int mx = ((int)floor(position.x * inverse_size) % _gridSize);
int my = ((int)floor(position.y * inverse_size) % _gridSize);
int mz = ((int)floor(position.z * inverse_size) % _gridSize);

我还建议删除 mod 操作，因为这是另一个除法 - 如果您的网格大小是 2 的幂，您可以使用 & (gridsize-1) 这也将允许您删除底部的条件代码，这是另一个很大的节省。

另一方面，使用重载运算符可能会伤害您。这是一个敏感的话题，所以我会让你尝试一下并自己决定。

于 2010-12-08T12:10:30.003 回答
1

我假设您使用floor因为负值是可能的，并且因为当您转换为时您不希望由于默认截断而出现异常int（值从两侧向零舍入，从而产生一些过大的体素）。

如果您可以为向量中的每个值指定一个安全的最负值，则可以在强制转换_gridIntervalSize之前减去该（负）值，或者更确切地说是最接近的负倍数，然后删除floor.

使用fmod可以确保你有一个安全的最负值，并替换 integer %，但这可能是一种反优化。尽管如此，作为一个快速变化，它可能值得检查。

此外，检查您的平台是否支持向量指令，以及是否可以轻松地鼓励您的编译器使用它们。x86 芯片当然具有整数向量指令以及浮点（旧的 Pentium 1 MMX 指令，首先），并且可能能够比“普通” CPU 指令集更有效地处理这一点。这甚至可能是为您的编译器挖掘向量指令内在函数列表并进行一些手动优化的情况。首先检查编译器可以为您做什么 - 我不确定这种优化编译器已经为您做了多少。

一个可能微不足道的微优化......

return (mx * _gridSize + my) * _gridSize + mz;

保存一个整数乘法。当然，微不足道，编译器无论如何都可能捕获它，但这是一个古老的习惯。

哦 - 注意前面的下划线。这些是保留的标识符。不太可能引起问题，但如果他们这样做了，你就不能抱怨。

编辑

避免这种情况的另一种方法floor是分别处理正面和负面。如果您愿意接受网格单元格边缘的项目可能位于错误的单元格中（无论如何都可能，因为浮动应该被认为是近似的）。只需-1在负数情况下应用偏移量，将其从零拉出几乎完全正确的量，以补偿截断。之后您可能会考虑进行一点点的增量尾数（以在您期望的单元格中获得整数值），但这可能是不必要的。

如果您可以对您的尺寸施加二次幂限制，则可能有一种巧妙的方法可以有效地从浮点数中提取网格位置，避免%x、y 和 z 中的每一个的部分或全部乘法、下限和，假设一个标准的浮点表示（即这是不可移植的）。再次，分别处理正面和负面。提取指数，相应地对尾数进行位移，然后屏蔽掉不需要的位。

于 2010-12-08T11:50:26.607 回答
0

我认为您需要查看更高的层次结构才能真正提高速度。也就是说，在哈希图中存储点真的是最有效的解决方案吗？我假设你有一个 Vector3 数组，即：

Vector3 *点[大小][大小][大小]

其中 3D 数组中的每个元素都是 Vector3 的数组。

您使用的算法不能保证每个 Vector3 数组中点的均匀分布，这可能是一个问题。其中的一组点将_gridIntervalSize映射到同一个数组。

另一种方法是使用八叉树，它类似于二叉树，但每个节点都有八个子节点。每个节点都需要最小/最大 x/y/z 值来定义节点覆盖的体积。向树中添加值：

递归搜索树找到可以包含点的最小节点

将点添加到节点

如果节点中的点数 > 节点中点数的上限

创建子节点并将点移动到子节点

如果沿特定轴的值变化很小，您可能希望使用四叉树。另一种方法是使用 BSP - 将世界分成两半并递归查找要添加您的点的容器。同样，这些可以是动态的。

将浮点数转换为整数并使除法平面位于整数值上也将加快该过程。

谷歌搜索上述术语将引导您对算法进行更深入的分析。

最后，在无限平面中使用浮点数（或双精度数）是一个坏主意 - 从 (0,0,0) 得到的距离越远，精度越低（浮点值之间的差距随着值的增加而增加）。您将需要“重置”浮点值以保持精度。一种方法是“平铺”空间并更改坐标以使用整数和浮点部分。整数部分定义了“瓦片”，浮点部分定义了瓦片中的位置。此方法为您提供了一种更简单的散列方法 - 只需使用整数部分，不需要调用floor，只需要整数计算。另一种方法是使用定点值而不是浮点值，但这会限制您的精度。

如果您可以扩展坐标系的顶级要求，那么您可能可以使用更好的算法。

于 2010-12-08T13:11:11.600 回答