SSBO哈希表，缺失值

Question

我正在试着做一个数据压缩实验。我试图压缩三维纹理为哈希表，以避免存储空卷信息。

为此，我编写了散列函数和恢复函数(它们在不同的着色器中)：

struct Voxel
{
    int filled;
    ivec4 position;
    vec4 normal;
    vec4 color;
};

layout(std430, binding = 0) buffer voxel_buffer
{
    uint index;
    Voxel voxels[];
};
// Data storing shader
int a_size = 10000000;
void insert(vec3 pos, Voxel value) {
    ivec3 discretized = ivec3(pos / v_size);
    int index = int(pow(7, discretized.x) * pow(2, discretized.y) * pow(3, discretized.z)) % a_size;

    for(int i=0; i<50; i++) {
        if(atomicCompSwap(voxels[index].filled, 0, 1) == 0) {
           Voxel c_voxel = voxels[index];
           value.position = ivec4(discretized, 1);
           voxels[index] = value;
           break;
         }

        index = (index * index) % a_size;
    }
}
//Data reading shader
int a_size = 10000000;
vec4 fetch(vec3 pos) {
    ivec3 discretized = ivec3(pos / v_size);
    int index = int(pow(7, discretized.x) * pow(2, discretized.y) * pow(3, discretized.z)) % a_size;

    for(int i=0; i<50; i++) {
        Voxel c_voxel = voxels[index];

        if(ivec4(discretized,1) == voxels[index].position)
            return voxels[index].color;

        index = (index * index) % a_size;
    }
}

然而，我目前的问题是，我遗漏了大约90%的体素值：

​

​

预期的结果是：

​

​

对于什么可能是错误，我有一些想法，但似乎没有一个是错的：

• 散列数大于数组大小。我分配了10万个字节，体素结构的总大小应该是4*4*3 = 48，给出了可能的元素总数2 083 333.33。我将数组大小限制在100万，这是其中的一半，所以我不应该访问未分配的内存。
• 哈希函数碰撞超过50次，导致大多数元素被丢弃。我可能是错的，但我使用二次更新来增加哈希指数，这应该比线性好。而且我也是依靠FTA保证独特的密钥生成，然后消化。所以我对这么多哈希碰撞超过50次表示怀疑。此外，保留的体素都在一个很好的区域(线性对角线切片)，这一事实似乎不符合这一假设。如果这是一个碰撞问题，我应该看到一个半均匀的整体分布，而不是一个定义得很好的区域。
• 驱动程序不能为ssbo分配那么多的vram。我使用的GTX 1070与最新的NVIDIA驱动程序，文档中说，规范保证最小大小为128 MB，但大多数实现允许您分配到总内存大小。我分配了10万字节，这在上限之内，即使驱动程序将我的内存对齐到128 MB，也不应该影响我的计算结果，因为我自己跟踪逻辑数组大小。

你知道为什么压缩时我会失去这么多信息吗？

编辑:根据注释添加原子操作

编辑2:在评论中找到了解决方案，结果：

​

一些记忆丧失仍然发生，但这是意料之中的。

Answer 1

您的散列函数

int(pow(7，discreed.x)* pow(2，discreed.y)* pow(3，discreed.z)% a_size；

很穷。因为discretized是一个ivec3，所以整个操作都在处理整数，而术语pow(2, discretized.y)将是0 (每当discretized.y是>= 31时)，从而得到要计算到0的完整哈希值。另外，对于discretized.y < 0，您应该得到0，因为生成的分数也不能由int类型表示。此外，您的二次探测对于index == 0也失败，因为您将探测相同索引的50倍。