Индексная упаковка на плоском массиве «3D» с использованием битовой маски

Question

Мой мир 3D-игр хранится в плоском массиве байтов. Мир имеет 1024 x 1024 в ширину/длину и 256 высот. Таким образом, массив имеет длину 268435456 байт. Для того, чтобы получить доступ к массиву я использую указатель индекса, рассчитанный таким образом:

WORLD_WIDTH_SHIFT = 10; 
WORLD_HEIGHT_SHIFT = 8; 

indexPointer = (((Px << WORLD_WIDTH_SHIFT) + Pz) << WORLD_HEIGHT_SHIFT) + Py; 

Я перемещаться вокруг массива во время обработки путем добавления предопределенных констант к значению индекса для повышения производительности. Движение на запад (положительная ось х) достигается следующим образом:

WEST = WORLD_WIDTH * WORLD_HEIGHT; 
NORTH = WORLD_HEIGHT; 
SOUTH = -WORLD_HEIGHT; 
WEST = WORLD_WIDTH * WORLD_HEIGHT; 
EAST = -WORLD_WIDTH * WORLD_HEIGHT; 
UP = 1; 
DOWN = -1; 

indexPointer += WEST; 

Чтобы предотвратить индекс выходящую за пределы диапазона, и к тому, что я тупо думал достичь обертку я добавил битовую маску на результат:

WORLD_ARRAY_SIZE = WORLD_WIDTH * WORLD_WIDTH * WORLD_HEIGHT; 
WORLD_ARRAY_SIZE_MASK = WORLD_ARRAY_SIZE - 1; 
WEST = WORLD_WIDTH * WORLD_HEIGHT; 

indexPointer = (indexPointer + WEST) & WORLD_ARRAY_SIZE_MASK; 

Это хорошо работает на оси X выше, но на оси z (с севера на юг) обертывание, как я обнаружил после того, как он дал некоторые мысли, очевидно, не сработает. Исправьте меня, если я ошибаюсь, но мне нужен способ выполнить битовую маску на битах, которые представляют координату z в indexPointer. Первые 8 бит - это высота, следующие 10 бит - координаты z, а окончательные 10 бит - координаты x. Есть ли способ выполнить это, не извлекая 10 бит в отдельное поле, а затем выполнить сложение и маску, а затем восстановить окончательный указатель?

Answer 1

Учитывая константы:

HIGH = 1; 
NORTH = WORLD_WIDTH; 
WEST = NORTH*WORLD_HEIGHT; 

вы можете изменить свой "приращение" функции:

public static void UpdatePointer (int indexPointer, int dir) { 
    int mask0 = 0xffc0000; 
    int mask1 = 0x003ff00; 
    int mask2 = 0x00000ff; 
    res = (indexPointer&mask0+dir)&mask0; 
    res |= (indexPointer&mask1+dir)&mask1; 
    res |= (indexPointer&mask2+dir)&mask2; 
    return res; 
} 

Это, таким образом, более или менее то, что вам нужно вместо indexPointer += update.

---

Объяснение:

Проблема заключается в том, что при добавлении константы, что добавление значения может привести к ручной клади. В основном вы хотите представить три «целых числа» в одно целое. Теперь даны целые числа имеют значения:

#bits 10 10 8 
value 12 1023 15 

и добавить ко второму числу, что один будет переливаться в результате:

#bits 10 10 8 
value 13 0 15 

хотя второе «целое» имеет правильное значение, то первое имеет увеличивается.

Вы можете решить эту проблему путем маскировки. Давайте посмотрим на вторую инструкцию маски:

(indexPointer&mask1+dir)&mask1; 

(остальные эквиваленты).

Здесь мы сначала применяем маску к indexPointer. Это гарантирует, что мы «извлечем» правильное целое число.Итак:

#bits 10 10 8 
value 12 1023 15 

теперь становится:

#bits 10 10 8 
value 0 1023 0 

Это может быть полезно, чтобы предотвратить переполнение dir третье целое число, и, таким образом, вызывая приращение второго.

Теперь мы «добавить» в dir к значению, в результате чего:

#bits 10 10 8 
value 1 0 0 

но теперь мы маска снова в результате:

#bits 10 10 8 
value 0 0 0 

Так вторая инструкция марка определяется значение второе «целое число» равно нулю и не оказывает никакого влияния на другие целые числа.

То же самое для первой маски, где перенос ПроВеншн более заметным:

#bits 10 10 8 //initial state 
value 12 1023 15 

#bits 10 10 8 //masking with mask0 
value 12 0 0 

#bits 10 10 8 //adding dir 
value 12 1 0 

#bits 10 10 8 //masking again 
value 12 0 0 

Если позже выполнить или операцию на трех операций, конечное состояние будет:

#bits 10 10 8 //final result 
value 12 0 15 

---

Альтернатива:

альтернативой является использование бит «переполнения». В этом случае indexPointer использует 8+1+10+1+10 = 30 бит, с одним бит между ними для переполнения. В этом случае обновление является:

indexPointer += dir; 
indexPointer &= 0x3ff7feff; 

где 0x3ff7feff маска, чтобы очистить переполнение биты снова:

0x3ff7feff = 11 1111 1111 0 11 1111 1111 0 1111 1111 

для того, чтобы «использовать» указатель, вы будете нуждаться в небольшой компактной операции:

int realPointer = ((indexPointer&0x3ff00000)>>0x02)|((indexPointer&0x7fe00)>>0x01)|(indexPointer&0xff); 

Или функция обновления гласит:

public static void UpdatePointer (int indexPointer, int dir) { 
    int temp = ((indexPointer&0xffc0000)<<0x02)|((indexPointer&0x3ff00)<<0x01)|(indexPointer&0xff); 
    temp += dir; 
    return ((temp&0x3ff00000)>>0x02)|((temp&0x7fe00)>>0x01)|(temp&0xff); 
} 

Очевидно, вам нужно где-то оплатить цену.