Глубина узла из кода местоположения октодерева

В статье Расширенные октодеревья 2: представления узлов заявлено:

AABB узла может храниться явно, как и раньше, или его можно вычислить из глубины дерева узла, хранящейся неявно внутри кода местоположения. Чтобы получить глубину дерева в узле из его кода местоположения, требуется флаговый бит, указывающий на конец кода местоположения. Без такого флага было бы невозможно отличить, например, между 001 и 000 001. Используя бит 1 для обозначения конца последовательности, 1 001 можно легко отличить от 1 000 001. Использование такого флага эквивалентно установке кода местоположения корня октодерева в 1.

Код местоположения представляет собой 32-битное слово. То есть ... 001 и ... 000 001 могут быть равны, как говорит автор, если и только если все биты, следующие за первым примером, равны битам во втором примере.

Как маркировка конца последовательности помогает нам определить глубину узла в дереве?

Автор использует пример ... 1 001 и ... 1 000 001. Имеет ли первый узел глубину 1, а второй — 2? Если да, то откуда мне знать? Код местоположения представляет собой 32-битное слово, поэтому биты, следующие за «флагом конца», могут следовать как ... 001 001, что также является допустимым узлом.

Так что я действительно не понимаю, как сохранить в 32-битном слове как код местоположения, так и глубину узла в дереве.


octree
person gnzlbg    schedule 04.09.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Я только что прочитал эту статью и у меня возник тот же вопрос. Я думаю, что ответ заключается в том, что, определив корневой узел с индексом «001», вы можете гарантировать, что первый (самый значащий) 1 бит, который вы видите в коде местоположения, указывает на корень. Так:

... 000 001 000 001 can be read as <root> <0,0,0> <0,0,1>, level 2
... 000 000 001 001 can be read as <root> <0,0,1>, level 1
... 000 000 000 001 can be read as <root>, level 0
person karantza    schedule 27.12.2015
comment
в основном вы переключаетесь до тех пор, пока у вас не будет только 001 или меньше (например, 000), количество сдвигов до этого - это количество уровней, которые у вас есть. - person gnzlbg; 31.12.2015