点到体素映射的优化

Question

我使用探查器来查看一些运行速度不够快的代码。发现下面这个函数占用了大部分时间，而这个函数有一半的时间都花在了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 的同一体素中的点应该落在同一个桶中。

Answer 1

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

<代码>
inverse_size = 1 / _gridIntervalSize;
....应该只执行一次，而不是每次调用一次。

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) 这还允许您删除底部的条件代码，这是另一个很大的节省。

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

Answer 2

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

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

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

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

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

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

节省了一个整数乘法。当然，这是微不足道的，编译器可能会捕获它，但这是一个老习惯。

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

编辑

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

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

Answer 3

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

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

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

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

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

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

向节点添加点

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

<块引用>

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

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

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

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

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

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