lunserv Sep 30 2013 at 23:20

Линейное представление октодерева с использованием кода Мортона

3 min

14K

Game development*Algorithms*

From sandbox

+28

Comments 28

Mrrl Oct 1 2013 at 08:38

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

unsigned long decodeIndex( const unsigned long index ) {
  unsigned long ind = index & 0x0249249249249249;
  ind=((ind*0x10000100001)>>40);
  return DecodeTable[(int)ind&0xFFFFF];  
}

Должно получиться не хуже, чем 5 сдвигов и 10 логических операций. Правда, теряется 4 мегабайта памяти :(

DrSmile Oct 1 2013 at 12:31

Операции с некешированной памятью — самые дорогие в современных процессорах. Умножения/сложения/разные битовые операции — наоборот, самые дешевые.

Mrrl Oct 1 2013 at 14:35

Действительно. Пришлось разбить табличку на две — отдельно для старших 10 бит, отдельно для младших. В итоге вычисления по табличкам получились в 2.3 раза быстрее, чем сдвигами (на 64-битной сборке): распаковка 10^9 точек по табличкам — 3.3 сек, сдвигами — 7.7 сек.

aleks_raiden Oct 1 2013 at 12:13

А где здесь геймдев-то?

-1

Lertmind Oct 1 2013 at 12:23

Октодеревья чаще используют в геймдеве.

aleks_raiden Oct 1 2013 at 12:26

Где, как, для чего, по каким соображениям — этого в статье ничего нет, потому и спрашиваю

Mrrl Oct 1 2013 at 14:47

Я тоже не очень понимаю, как можно использовать код Мортона для хранения. Как, например, хранить облако точек в виде octree — понятно: разбиваем область на 8 кубиков, в 8 бит записываем маску непустых кубиков, дальше для каждого непустого кубика пишем его представление в том же виде (рекурсивно). Если в кубике осталась только одна точка — записываем младшие биты её координат и прочую информацию (цвет, нормаль...). Код Мортона в этой ситуации полезен только для подготовки дерева — точки в такой структуре идут в порядке возрастания их кодов, так что можно их отсортировать, и дальше всё просто. Но как использовать коды именно для хранения информации?

lunserv Oct 2 2013 at 00:53

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

                      000000
                         | 
   ================================================
   000000 001000 010000 011000 100000 101000 111000
                   |
      =======================================================
      010000 010001 010010 010011 010100 010101 010110 010111

то есть для листьев сохраняется весь путь по дереву. Чем глубже дерево, тем больше будет этот путь — по 3 бита на уровень (2^3 = 8 частей). Тогда для дерева глубиной 16 необходимо 45 бит на лист + глубина. И код Мортона здесь не нужен.
В описываемом в статье способе листья дерева располагаются вдоль кривой(Лебега, Гильберта и тд) и храниться только их глубина, то есть все дерево из примера будет храниться как
[1|2 2|2 2|2 2|2 2|1 1|1 1|1 1|1] (здесь запись x|y означает десятичную запись числа, где каждый элемент представляет байт — 0000|0000) — используется 4 бита на лист. Далее только по этому значению глубины можно вычислить вещественные координаты каждого листа.

lunserv Oct 2 2013 at 01:08

в записи дерева ошибка, правильно так:

                       000000
                         | 
   =======================================================
   000000 001000 010000 011000 100000 101000 110000 111000
                   |
      =======================================================
      010000 010001 010010 010011 010100 010101 010110 010111

[2|2 3|3 3|3 3|3 3|3 2|2 2|2 2|0] (считаем что 0 — отсутствие элемента, нумерация уровней с 1).

Mrrl Oct 2 2013 at 08:29

В моём примере это дерево (15 точек) будет храниться так:

1; 0xff; 0; i0; 0; i1; 1; 0xff; 0; i20; 0; i21; 0; i22; 0; i23; 0; i24; 0; i25; 0; i26; 0; i27; 0; i3; 0; i4; 0; i5; 0; i6; 0; i7
Здесь 0 и 1 — биты, указывающие, идёт дальше разбиение на кубик или точка, 0xff — маска, означающая, что все подкубики непустые, i0,i1,i3..i7 — координаты точек, локализованных на верхнем уровне (при глубине дерева 15 это 42 бита), i20,i21..i27 — координаты точек, локализованных на втором уровне (по 39 бит — старшие 2 бита каждой координаты уже известны). Итого на структуру дерева — 39 бит (против 60 в вашем примере) плюс 606 бит на уточнение координат.
Если какой-то элемент (подкубик) пропущен (не содержит точек), то в маске в соответствующем месте будет стоять 0, и в последующем списке информации про этот подкубик не будет.

lunserv Oct 2 2013 at 14:59

Итого на структуру дерева — 39 бит (против 60 в вашем примере) плюс 606 бит на уточнение координат.

хорошо, в предложенном в статье способе 60 бит не хранятся, а вычисляются. Храниться только 4 бита на лист — все больше ни чего — ни предыдущие уровни, ни каких масок и тд.
Возможно тогда напишу статью с более подробным описанием самого представления.

Mrrl Oct 2 2013 at 15:00

15 чисел (по одному на лист), по 4 бита каждое — итого 60. Разве нет?

lunserv Oct 2 2013 at 18:37

да, думал речь идет про 60 бит (3 по 20) для кода.
я не понял как у вас получилось 39 бит и что значит 606 бит на уточнение координат. то есть по вашему для хранения приведенного выше дерева нужно 39 + 606 = 645 бит против 60 предложенных в статье?
что будет происходить при более глубоком дереве — нужно сохранять весь путь?

Mrrl Oct 2 2013 at 18:53

У меня задача — есть множество точек, заданных координатами (в данном примере 15 точек, координаты 15-битные), и надо их упаковать. Когда в octree я дохожу до области, в которой находится одна точка, то для определения её положения пройденного пути недостаточно — надо указать положение точки в области. И это занимает 3*(15-d) бит на точку (d — глубина области в дереве).
Сохранять путь должна программа обхода — а как же иначе? В самом дереве путь не хранится, он деревом определяется.

lunserv Oct 2 2013 at 19:12

в приведенном способе обход осуществляется сразу по листьям.

Mrrl Oct 2 2013 at 19:25

Но путь всё равно накапливается (пусть суммированием, а не наращиванием), и сохраняется в программе обхода? То, что в вашем подходе нет рекурсии, и за счёт этого время перехода к следующему листу O(1) — согласен.

Mrrl Oct 2 2013 at 15:11

Кстати, допускает ли эта структура пропущенные листья? Или её назначение — задать разбиение всего пространства (большого куба)?

lunserv Oct 2 2013 at 18:38

да, это полное разбиение пространства, на этом и основан алгоритм.

Mrrl Oct 2 2013 at 18:59

А, ну, тогда есть решение за 8/7 бита на лист дерева, вне зависимости от глубины. Если у нас есть область, не являющаяся листом, то разобьём её на 8 подобластей, и составим 8-битную маску, в которой 0 соответствует подобласти-листу, а 1 — подобласти, которая ещё подлежит разбиению. Код области = [маска | коды подобластей]. В вашем примере дерево кодируется 2 байтами — [0x04, 0x00]

lunserv Oct 2 2013 at 19:14

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

Mrrl Oct 2 2013 at 19:28

Если будет «разбиение листа», то это уже не лист. Если все узлы 2-го уровня разбиты на 9 листьев, то в дереве будет 64 листа, а в коде — 9 байт: [0xFF,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00]. 72/64 = 9/8 бита на лист.

lunserv Oct 2 2013 at 19:44

хорошо, а если разбить 3-тий уровень? в данном подходе затраты на хранение будут расти с каждым уровнем.

Mrrl Oct 2 2013 at 19:57

Будут. Но никогда не превысят 8/7. Если у нас 512 листьев, то код составляет 1+8+64=73 байта, т.е. 73/64 бита на лист.

lunserv Oct 2 2013 at 20:14

получается у вас для каждой последовательности должна храниться маска всех предыдущих уровней?
можете привести пример, как в вашем способе будет выглядеть запись дерева, где корень разбит на 8, затем самый левый потомок на восемь и у него самый левый на восемь?
и как вычислять координаты листьев при таком представлении?

Mrrl Oct 2 2013 at 20:44

Если я не перепутал число уровней, то код будет таким: [0x01,0x01,0x00]

Перебор всех листьев выглядит примерно так:

typedef unsigned int uint;
typedef unsigned char byte;
void Process(byte *T,int depth){
   Process(T,0,0,0,1u<<depth);
}
byte *Process(byte *T,uint x,uint y,uint z,uint level){
  byte mask=*T++;
  level>>=1;
  for(int k=0;k<8;k++){
    uint x1=x+level*(k&1),y1=y+level*((k>>1)&1),z1=z+level*((k>>2)&1);
    if(mask&1) T=Process(T,x1,y1,z1,level);
    else ProcessList(x1,y1,z1,level);
    mask>>=1;
  }
  return T;
}

Но я его не проверял, написал первое, что пришло в голову.

lunserv Oct 2 2013 at 20:56

хорошо, у вашего представления свои достоинства, для каких то задач оно подойдет лучше.
в статье про id Tech 6 говорится что

является возможным сжатие SVO до уровня 1,15 битов на один воксел

возможно использовалось похожее представление на предложенное вами.

vladimirovich Oct 3 2013 at 21:39

разые есть способы, кстати.

Вот способ через умножение, правда, 64 битное. 8 битный вход и 16 битный выход

unsigned char x; // Interleave bits of (8-bit) x and y, so that all of the
unsigned char y; // bits of x are in the even positions and y in the odd;
unsigned short z; // z gets the resulting 16-bit Morton Number.

z = ((x * 0x0101010101010101ULL & 0x8040201008040201ULL) *
0x0102040810204081ULL >> 49) & 0x5555 |
((y * 0x0101010101010101ULL & 0x8040201008040201ULL) *
0x0102040810204081ULL >> 48) & 0xAAAA;

lunserv Oct 3 2013 at 23:51

в статье приведена эта ссылка

Show the best of all time