Вопросы Теги

Как вычислить 3D число Morton (чередуйте биты 3 ints),

Здесь есть множество вариантов, но я не удивился, когда не было быстрых однострочников, это то, что я использовал в начале своих сценариев: [[ "$(command -v mvn)" ]] || { echo "mvn is not installed" 1>&2 ; exit 1; } [[ "$(command -v java)" ]] || { echo "java is not installed" 1>&2 ; exit 1; }

это основано на выбранном здесь ответе, а другой источник (а я немного поиграюсь).

надеюсь, что это будет полезно для других.

35
задан Taylor 23 October 2018 в 17:57
поделиться

4 ответа

Вы можете использовать ту же технику. Я предполагаю, что переменные содержат 32-битные целые числа с высшими 22 битами, установленными на 0 (что немного более ограничительно, чем необходимо). Для каждой переменной x , содержащей одно из трех 10-битных целых чисел, мы делаем следующее: 

x = (x | (x << 16)) & 0x030000FF;
x = (x | (x <<  8)) & 0x0300F00F;
x = (x | (x <<  4)) & 0x030C30C3;
x = (x | (x <<  2)) & 0x09249249;

Затем с x , y и z три обработанных 10-битных целых числа мы получаем результат, взяв: 

x | (y << 1) | (z << 2)

Этот метод работает следующим образом. Каждый из x = ... строки выше «разбивают» группы битов пополам, чтобы между битами других целых чисел оставалось достаточно места. Например, если мы рассмотрим три 4-битных целых числа, мы разделим одно с битами 1234 на 000012000034, где нули зарезервированы для других целых чисел. На следующем шаге мы разделим 12 и 34 таким же образом, чтобы получить 001002003004. Несмотря на то, что 10 бит не подходят для хорошего повторного деления на две группы, вы можете просто считать это 16 бит, когда вы теряете самые высокие в конце .

Как видно из первой строки, на самом деле вам нужно только, чтобы для каждого входного целого числа x было установлено, что x & 0x03000000 == 0 .

строки выше «разбивают» группы битов пополам, чтобы между ними оставалось достаточно места для битов других целых чисел. Например, если мы рассмотрим три 4-битных целых числа, мы разделим одно с битами 1234 на 000012000034, где нули зарезервированы для других целых чисел. На следующем шаге мы разделим 12 и 34 таким же образом, чтобы получить 001002003004. Несмотря на то, что 10 бит не подходят для хорошего повторного деления на две группы, вы можете просто считать это 16 бит, когда вы теряете самые высокие в конце .

Как видно из первой строки, на самом деле вам нужно только, чтобы для каждого входного целого числа x было установлено, что x & 0x03000000 == 0 .

строки выше «разбивают» группы битов пополам, чтобы между ними оставалось достаточно места для битов других целых чисел. Например, если мы рассмотрим три 4-битных целых числа, мы разделим одно с битами 1234 на 000012000034, где нули зарезервированы для других целых чисел. На следующем шаге мы разделим 12 и 34 таким же образом, чтобы получить 001002003004. Несмотря на то, что 10 бит не подходят для хорошего повторного деления на две группы, вы можете просто считать это 16 бит, когда вы теряете самые высокие в конце .

Как видно из первой строки, на самом деле вам нужно только, чтобы для каждого входного целого числа x было установлено, что x & 0x03000000 == 0 .

если мы рассмотрим три 4-битных целых числа, мы разделим одно с битами 1234 на 000012000034, где нули зарезервированы для других целых чисел. На следующем шаге мы разделим 12 и 34 таким же образом, чтобы получить 001002003004. Несмотря на то, что 10 бит не подходят для хорошего повторного деления на две группы, вы можете просто считать это 16 бит, когда вы теряете самые высокие в конце .

Как видно из первой строки, на самом деле вам нужно только, чтобы для каждого входного целого числа x было установлено, что x & 0x03000000 == 0 .

если мы рассмотрим три 4-битных целых числа, мы разделим одно с битами 1234 на 000012000034, где нули зарезервированы для других целых чисел. На следующем шаге мы разделим 12 и 34 таким же образом, чтобы получить 001002003004. Несмотря на то, что 10 бит не подходят для хорошего повторного деления на две группы, вы можете просто считать это 16 бит, когда вы теряете самые высокие в конце .

Как видно из первой строки, на самом деле вам нужно только, чтобы для каждого входного целого числа x было установлено, что x & 0x03000000 == 0 .

30
ответ дан 27 November 2019 в 06:56
поделиться

Следующий код находит число Мортона из трех 10-битных входных чисел. Он использует идею из вашей ссылки и выполняет распределение битов на этапах 5-5, 3-2-3-2, 2-1-1-1-2-1-1-1 и 1-1-1- 1-1-1-1-1-1-1, потому что 10 не является степенью двойки. 

......................9876543210
............98765..........43210
........987....56......432....10
......98..7..5..6....43..2..1..0
....9..8..7..5..6..4..3..2..1..0

Выше вы можете увидеть расположение каждого бита перед первым и после каждого из четырех шагов. 

public static Int32 GetMortonNumber(Int32 x, Int32 y, Int32 z)
{
    return SpreadBits(x, 0) | SpreadBits(y, 1) | SpreadBits(z, 2);
}

public static Int32 SpreadBits(Int32 x, Int32 offset)
{
    if ((x < 0) || (x > 1023))
    {
        throw new ArgumentOutOfRangeException();
    }

    if ((offset < 0) || (offset > 2))
    {
        throw new ArgumentOutOfRangeException();
    }

    x = (x | (x << 10)) & 0x000F801F;
    x = (x | (x <<  4)) & 0x00E181C3;
    x = (x | (x <<  2)) & 0x03248649;
    x = (x | (x <<  2)) & 0x09249249;

    return x << offset;
}
4
ответ дан 27 November 2019 в 06:56
поделиться

Самым простым, вероятно, является таблица поиска, если у вас есть свободное пространство 4K: 

static uint32_t t [ 1024 ] = { 0, 0x1, 0x8, ... };

uint32_t m ( int a, int b, int c )
{
    return t[a] | ( t[b] << 1 ) | ( t[c] << 2 );
}

Битовый хак использует сдвиги и маски для распределения битов, поэтому каждый раз он сдвигает значение и или это, копируя некоторые биты в пустые места, затем маскируя комбинации, чтобы оставались только исходные биты.

например: 

x = 0xabcd;
  = 0000_0000_0000_0000_1010_1011_1100_1101    

x = (x | (x << S[3])) & B[3]; 

  = ( 0x00abcd00 | 0x0000abcd ) & 0xff00ff 
  = 0x00ab__cd & 0xff00ff 
  = 0x00ab00cd
  = 0000_0000_1010_1011_0000_0000_1100_1101
x = (x | (x << S[2])) & B[2]; 
  = ( 0x0ab00cd0 | 0x00ab00cd) & 0x0f0f0f0f 
  =   0x0a_b_c_d & 0x0f0f0f0f 
  = 0x0a0b0c0d 
  = 0000_1010_0000_1011_0000_1100_0000_1101
x = (x | (x << S[1])) & B[1]; 
  = ( 0000_1010_0000_1011_0000_1100_0000_1101 | 
      0010_1000_0010_1100_0011_0000_0011_0100 ) &
      0011_0011_0011_0011_0011_0011_0011_0011
  =   0010_0010_0010_0011_0011_0000_0011_0001
x = (x | (x << S[0])) & B[0]; 
  = ( 0010_0010_0010_0011_0011_0000_0011_0001 | 
      0100_0100_0100_0110_0110_0000_0110_0010 ) &
      0101_0101_0101_0101_0101_0101_0101_0101
  =   0100_0010_0100_0101_0101_0000_0101_0001

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

После того, как вы разложили входы, сдвинуть их так, чтобы значения одного попадали в нули другого.

] Чтобы расширить эту технику для более чем двух битов между значениями в конечном результате, вы должны увеличить сдвиги между тем, где заканчиваются биты. Это становится немного сложнее, поскольку размер начального блока не равен

8
ответ дан 27 November 2019 в 06:56
поделиться

Хорошее время, я сделал это только в прошлом месяце!

Ключевым моментом было выполнение двух функций. Один разносит биты до каждого третьего бита. Затем мы можем объединить три из них вместе (со сдвигом для последних двух), чтобы получить окончательное перемеженное значение Morton.

Этот код перемежается, начиная с HIGH битов (что более логично для значений с фиксированной запятой). Если ваше приложение составляет всего 10 бит на компонент, просто сдвиньте каждое значение влево на 22, чтобы оно начиналось со старших битов. 

/* Takes a value and "spreads" the HIGH bits to lower slots to seperate them.
   ie, bit 31 stays at bit 31, bit 30 goes to bit 28, bit 29 goes to bit 25, etc.
   Anything below bit 21 just disappears. Useful for interleaving values
   for Morton codes. */
inline unsigned long spread3(unsigned long x)
{
  x=(0xF0000000&x) | ((0x0F000000&x)>>8) | (x>>16); // spread top 3 nibbles
  x=(0xC00C00C0&x) | ((0x30030030&x)>>4);
  x=(0x82082082&x) | ((0x41041041&x)>>2);
  return x;
}

inline unsigned long morton(unsigned long x, unsigned long y, unsigned long z)
{
  return spread3(x) | (spread3(y)>>1) | (spread3(z)>>2);
}
5
ответ дан 27 November 2019 в 06:56
поделиться
Другие вопросы по тегам:

Похожие вопросы: