Я пытаюсь провести небольшой эксперимент по сжатию данных. Я пытаюсь сжать трехмерные текстуры в хеш-таблицы, чтобы избежать хранения информации о пустом томе.
Для этого я написал функцию хеширования и функцию получения (они находятся в разных шейдерах):
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% значений вокселей:
Ожидаемый результат:
У меня были некоторые идеи относительно того, что может быть не так, но, похоже, ни одна из них не была:
Количество хэшей больше размера массива. Я выделил 100 000 000 байт, общий размер структуры вокселей должен быть 4 * 4 * 3 = 48, что дает мне общее возможное число элементов 2 083 333,33. Я ограничил размер массива миллионом, что составляет половину от этого, поэтому я не должен обращаться к нераспределенной памяти.
Функция хеширования сталкивается более 50 раз, в результате чего большинство элементов отбрасывается. Я могу ошибаться, но я использую квадратичное обновление для увеличения хешированного индекса, это должно быть лучше, чем линейное. И я также полагаюсь на FTA, чтобы гарантировать генерацию уникального ключа перед перевариванием. Поэтому я скептически отношусь к тому, что так много хэшей сталкиваются более 50 раз. Более того, тот факт, что все вокселы были сохранены, находится в такой хорошей области (диагональный срез лайнера)
похоже, не соответствует этой гипотезе. Если бы это была проблема со столкновением, я бы увидел полуравномерное распределение целых, а не такую хорошо определенную область.
Драйвер не может выделить столько vram для ssbo. Я использую GTX 1070 с последними драйверами NVIDIA, в документации говорится, что спецификация гарантирует минимальный размер 128 МБ, но большинство реализаций позволяют вам выделить до общего объема памяти. Я выделил 100 000 000 байт, что ниже верхнего предела, и даже если драйвер выравнивает мою память по 128 МБ, это не должно влиять на результат моих вычислений, так как я сам отслеживаю размер логического массива.
Есть идеи, почему я теряю так много информации при сжатии?
EDIT:
Добавлены атомарные операции на основе комментария
РЕДАКТИРОВАТЬ 2:
Решение было найдено в комментарии, результат:
Некоторая потеря памяти все еще происходит, но это ожидалось.