Октодерево, содержащее четыре цвета

Рис. 12.22. Октодерево, содержащее четыре цвета

Теория цвета

Каждый узел на глубине 8 представляет точный цвет (с точностью до 24 бит), в то время как внутренние узлы представляют подблоки цветов. Например, узел на уровне 3 представляет все цвета, имеющие определенный набор трех самых старших бит R, G, В, однако следующие биты могут быть любыми.

Когда в октодереве оказывается более к цветов, оно подвергается отсечению. «Отсекаемый» узел (имеющий как минимум двух потомков) ищется на возможно более низком уровне. (На рис. 12.22 удаляемый узел обозначен буквой а.) Для отсечения октодерева потомки отсекаемого узла удаляются (что освобождает место для будущих узлов), после чего данный узел помечается как лист. Этот узел уже содержит краткую информацию об уже встречавшихся цветах, которыми обладали его потомки. При каждом отсечении число различных цветов октодерева уменьшается на величину, на единицу меньшую, чем количество удаленных потомков. (Почему?) Теперь в октодерево можно добавлять новые цвета.

Как подробно описано в тематическом задании 12.7, каждый узел отслеживает определенную информацию, которая в закодированном виде включает в себя следующее"opengl1_865.html">⇐ Предыдущая| |Следующая ⇒