Ускоренный способ преобразования 1D -> 3D с использованием мощностей 2 измерения

Question

Я пытаюсь оптимизировать доступ и изменение данных 3D-среды, потому что некоторые операции нужно делать миллионы раз. В настоящее время я следующие оптимизации на месте:

• с помощью плоского массива (1D)
• Размеры по степеням 2
• Bit-сдвига, где это возможно, вместо умножения/деления

индексирование 3D-векторов выглядит следующим образом:

• изменение вектора X будет увеличивать/уменьшать индекс Ь у 1
• Изменение вектора Y будет увеличение/уменьшение индекса по 3DEnvironmentSize.X
• Изменение Z вектора будет увеличивать/уменьшать индекс на 3DEnvironmentSize.X * 3DEnvironmentSize.Y

Учитывая следующий псевдокод:

mapSize.X = 4 
mapSize.Y = 4 
mapSize.Z = 2 

Xdif = 1 
Ydif = mapSize.X = 4 
Zdif = mapSize.X * mapSize.Y = 16 

Xexponent = log2(Xdif) = log2(1) = 0 (2^0 = 1 = Xdif) 
Yexponent = log2(Ydif) = log2(4) = 2 (2^2 = 4 = Ydif) 
Zexponent = log2(Zdif) = log2(16) = 4 (2^4 = 16 = Zdif) 

Можно было бы перейти от 3D -> 1D данного вектора (1,2,1), используя следующий:

location.X = 1 
location.Y = 2 
location.Z = 1 

shiftIndex.X = location.X << Xexponent = 1 << 0 = 1 
shiftIndex.Y = location.Y << YExponent = 2 << 2 = 8 
shiftIndex.Z = location.Z << Zexponent = 1 << 4 = 16 

index = shiftIndex.X + shiftIndex.Y + shiftIndex.Z = 1 + 8 + 16 = 25 

Как вы можете видеть, я использую бит-сдвиг для увеличения скорости обработки. Теперь я знаю, как конвертировать 3D -> 1D с использованием devisions и делением остатков с данным индексом 30, как так:

index = 30 

location.X = index % mapSize.X 
location.Y = (index/mapSize.X) % mapSize.Y 
location.Z = ((index/mapSize.X)/mapSize.Y) % mapSize.Z 

Есть ли способ использовать битый сдвиг (или что-нибудь еще в этом отношении) вот как-то что сделает это быстрее? Я пытаюсь это сделать в течение некоторого времени, но я не могу взломать его, если это возможно даже в первую очередь.

Answer 1

Мне дали ответ в другом месте.

Когда вы делите на число, имеющее мощность 2, вы можете заменить это деление на операцию сдвига вправо, которая является показателем мощности 2. Операция модуля может быть заменена (опять же, если она мощность 2) побитно и оператором и n - 1. Где n - это номер, на котором вы ныряли. Так заключить код:

mapSize.X = 4 
mapSize.Y = 4 
mapSize.Z = 2 

Xdif = 1 
Ydif = mapSize.X = 4 
Zdif = mapSize.X * mapSize.Y = 16 

XDifExponent = log2(Xdif) = log2(1) = 0 (2^0 = 1 = Xdif) 
YDifExponent = log2(Ydif) = log2(4) = 2 (2^2 = 4 = Ydif) 
ZDifExponent = log2(Zdif) = log2(16) = 4 (2^4 = 16 = Zdif) 

XSizeExponent = log2(mapSize.X) = log2(4) = 2 (2^2 = 4 = mapSize.X) 
YSizeExponent = log2(mapSize.Y) = log2(4) = 2 (2^2 = 4 = mapSize.Y) 
ZSizeExponent = log2(mapSize.Z) = log2(2) = 1 (2^1 = 2 = mapSize.Z) 

Vector3D -> Index example: 
location.X = 1 
location.Y = 2 
location.Z = 1 

shiftIndex.X = location.X << XDifExponent = 1 << 0 = 1 
shiftIndex.Y = location.Y << YDifExponent = 2 << 2 = 8 
shiftIndex.Z = location.Z << ZDifExponent = 1 << 4 = 16 

index = shiftIndex.X + shiftIndex.Y + shiftIndex.Z = 1 + 8 + 16 = 25 

Index -> Vector3D example: 
index = 30 

location.X = index & (mapSize.X - 1) = 2 
location.Y = (index >> XSizeExponent) & (mapSize.Y - 1) = 3 
location.Z = ((index >> XSizeExponent) >> YSizeExponent) & (mapSize.Z - 1) = 1 

Answer 2

Вы просто пытаетесь упаковать 3 номера в большую?

Если да, то почему вы просто не смещаете и не маскируете?

ThreeToOne(v3) -> v3.x | (v3.y << 8) | (v3.z << 16) 

OneToThree(v) -> v3(v & 0xFF, v >> 8 & 0xFF, v >> 16 & 0xFF)