T1 DE COMPUTAÇÃO GRÁFICA
Implementação de Octrees
Thoran Rodrigues
O QUE É UMA OCTREE
• É uma representação de subdivisões
no espaço
– Cada nó representa um cubo no espaço
– Cada filho é uma das oito subdivisões
COMO REPRESENTAR O ESPAÇO RGB
• A raiz da árvore representa um cubo
que contém todas as cores da figura
– Cada nível abaixo representa uma subdivisão
deste cubo
– Cada vez que descemos um nível, estamos
estreitando os cubos (representando cada
vez menos cores)
REPRESENTAÇÃO DO ESPAÇO
DETALHES DE IMPLEMENTAÇÃO
• Para encontrar o índice do filho para
onde queremos ir, olhamos para uma
tripla de bits (os bits dos canais R, G e
B)
– Assim, no nível um, o índice é dado pela
combinação dos bits 7 de cada canal, no
dois, o índice é dado pela combinação dos
bits 6…
DETALHES DE IMPLEMENTAÇÃO
DETALHES DE IMPLEMENTAÇÃO
• Para inserir uma cor na árvore, vamos
pegando os bits, calculando o índice e
descendo na árvore até alcançar uma
folha
• Quando o número de folhas excede o
número máximo de cores desejados,
reduzimos a árvore.
DETALHES DE IMPLEMENTAÇÃO
• Para reduzir a árvore, selecionamos o
nó com menor frequência no nível mais
profundo que conseguirmos
– Este nó passa a conter a soma dos valores
RGB e de frequência de todos os seus filhos,
e passa a ser uma folha, não podendo mais
ser reduzido
DETALHES DE IMPLEMENTAÇÃO
DETALHES DE IMPLEMENTAÇÃO
• No final, temos uma árvore que
representa a nova paleta de cores
– Para substituir as cores na imagem,
utilizamos um processo similar ao de
inserção, descendo na árvore até chegar em
uma folha
BIBLIOGRAFIA
As figuras foram retiradas de:
CLARK, D. Color Quantization Using Octrees, Dr. Dobbs
Journal, Janeiro, 1996
PROSISE, J. Wicked Code, Microsoft Systems Journal, Agosto,
1996