Rapid Hierarquichal Radiosity Algorithm
Pat Hanrahan
David Salzman
Larry Aupperle
Siggraph ´91 Las Vegas
Introdução
Para a criação de imagens por computador a
aproximação com mais sucesso foi a radiosidade
Assume que todas as superfícies são difusas e reflectoras
Permite uma computação directa do equilíbrio distribuição da
luz em cenas com geometrias complexas
Rapid Hierarquichal Radiosity Algorithm
Introdução
Rapid Hierarquichal Radiosity Algorithm
Objectivo – Acelerar o criação matriz de form factors
A partir dos
estudos de:
Appel 1985, Barnes e Hunt 1986, Greengard 1988
Algoritmos numéricos para resolução de problemas com N-Corpos
Trabalho anterior
Em estudos anteriores concluiu-se que a matriz
de form factors pode sempre ser aproximada a um
valor dentro de uma tolerância para uma matriz O(n)
elementos
Rapid Hierarquichal Radiosity Algorithm
Objectivos
Rapid Hierarquichal Radiosity Algorithm
Subdividir a geometria em patches antes da execução da radiosidade
Reordenar a forma como a radiosidade é calculada
Sabendo que no calculo de cada form factor todos os elementos interagem entre si
reduzir o numero de interacções a
apenas os elementos visíveis
Técnica de detecção
baseada em ray tracing
Tirar vantagem dos níveis de detalhe
Visibilidade para o calculo – total ou não total
Radiosidade
Rapid Hierarquichal Radiosity Algorithm
B i  B ei   d  B j Fij
j
form-factor indica a fracção de radiosidade emitida por uma Patch j que incide noutra Patch i
Não é considerada a oclusão
Uma primeira aproximação para resolver este problema foi apresentado por
Cohen e Greenberg em 1985 em que propunham integrar a visibilidade
no calculo de form factors a partir de um algoritmo Hemi-cubo.
Este algoritmo era simples e rápido sendo baseado no calculo de ray trace
proposto por Malley, Ward, Wallece sillion e Puech
Radiosidade
Rapid Hierarquichal Radiosity Algorithm
form factor
Fij 
1
Ai
 
Ai
Aj
V ( x i , y j ) cos(  i ) cos(  j )
r
2
 Aj  Ai
Há duas fontes de erro no calculo dos integrais dos form factors
•
O integral é avaliado por amostragem das patchs. Uma vez que a amostragem
uniforme está sujeita ao aliasing, o erro de aliasing condicionará o resultado do
integral
•
o form factor entre duas superfícies pode ser aproximado para o form factor
diferencial apenas se a distancia que separa as duas superfícies for maior que o
seu tamanho
Problema de N-Corpos
Rapid Hierarquichal Radiosity Algorithm
O algoritmo de subdivisão hierárquica é inspirado na resolução de problemas de n-corpos,
em que:
cada partícula exerce uma força sobre todas as outras n-1 partículas, implicando uma
interacção de n(n-1)/2 partículas
Este algoritmo é rápido mas baseia-se em dois pressupostos:
1- O calculo numérico está sujeito a erro (a força que actua na partícula tem de ser
calculada dentro de uma margem de precisão )
2- A força proveniente de um cluster de partículas pode ser aproximada (dentro de uma
margem de precisão) reduzindo o numero de interacções
N-Corpos vs Radiosidade
Rapid Hierarquichal Radiosity Algorithm
Uma das grandes diferenças entre os dois problemas (n-corpos vs. radiosidade) é a forma
como a estrutura hierárquica de dados se forma.
Os algoritmo dos n-corpos começa com as partículas transformando-as em grupos e grupos
de grupos.
O algoritmo de radiosidade proposto começa com alguns grandes polígonos e subdivide-os
em elementos cada vez mais pequenos
Outra diferença é que algoritmo dos n-corpos tira vantagem da superposição linear em que o
potencial de um grupo de partículas é a soma do potencial da partículas individuais.
Isto nem sempre se aplica à radiosidade uma vez que temos que contar com problemas de
oclusão, o que torna este sistema não linear.
O algoritmo dos n-corpos é baseado em equações diferenciais
enquanto a radiosidade é baseada em equações de integrais
Matriz de form factor
Rapid Hierarquichal Radiosity Algorithm
Este processo descreve o refinamento progressivo que decompõe um polígono numa
hierarquia de patches e elementos.
Construindo uma representação hierárquica de uma matriz de form factors pelo registo de
interacções a níveis diferentes de detalhe.
1º - estima-se o form factor (Fe) entre as duas patchs
2º - Subdividir as patchs ou registar a interacção
Se o form factor for > que Fe, então o form factor estimado não esta
correcto e a patch com maior form factor é subdividida
Se o form factor for < que Fe, então o form factor pode ser aproximado
pela estimativa e as patchs interagem a este nível de detalhe
Matriz de form factor
Rapid Hierarquichal Radiosity Algorithm
A subdivisão é registada numa quadtree
Nesta implementação as patchs são quadriláteros e a subdivisão é feita em
4 quadriláteros iguais
Matriz de form factor
Rapid Hierarquichal Radiosity Algorithm
O critério de erro diz que duas patches de tamanho r podem interagir directamente apenas
se o seu afastamento R for maior que r/sqr(Fe) assim fixamos o valor Fe para que duas
patches no mesmo nível de uma arvore binária podem interagir se pelo menos uma outra
patch estiver entre elas.
Caso contrario forma-se um ângulo demasiado grande e a patch subdivide-se empurrando
a interacção para uma nível mais baixo da arvore
Resumo
Este método estima a matriz de form factors entre patchs visíveis, dentro de uma
margem de erro fixando automaticamente uma tolerância.
Neste processo reorganiza a matriz de form factors em O(n) blocos ou menos.
O form factor estimado associado a cada bloco tem o mesmo valor e erro que todos
os outros blocos.
Visibilidade
Rapid Hierarquichal Radiosity Algorithm
A interacção entre superfícies ocultas resulta no decréscimo do transporte de luz entre duas
patchs, embora o verdadeiro form factor perante uma situação de oclusão nunca será
um valor nulo
O efeito da oclusão pode ser simulado pela multiplicação de um valor de correcção de
visibilidade (estimando a percentagem de visibilidade entre patch) ao form factor.
F = Ve Fe
No algoritmo proposto são executados dois tipos de testes:
1º determina se os polígonos estão virados para si ou não, ou se o
polígono é intersectado por outro.
Este teste considera apenas dois polígonos de cada vez.
2º verifica qual a percentagem de visibilidade entre cada polígono a
partir de um conjunto de raios disparados entre patchs.
Soluções Tecnicas
Rapid Hierarquichal Radiosity Algorithm
Uma vez calculados os form factors o próximo passo será resolver as radiosidades
Shooting e Gathering
A equação de radiosidade pode ser resolvida com um processo de Shooting em vez
de um processo de Gathering.
Todas as patchs na hierarquia estão organizadas por prioridades baseadas na sua
luminosidade.
Uma patch é retirada da hierarquia e a sua energia é disparada para todas as
outras que interagem com ela
Com esta proposta resulta menor granularidade devido a que uma patch não
dispara energia para toda a cena mas apenas para um numero constante de
patchs.
Soluções Tecnicas
Rapid Hierarquichal Radiosity Algorithm
Multigrid e BF Refinement
Multigrid não tem vantagens sobre o processo de Gathring.
Uma vez que todas as interacções levam aproximadamente a mesma quantidade
de energia e não há vantagem em organiza-las por luminosidade.
Resumo e Conclusão
Rapid Hierarquichal Radiosity Algorithm
.Este algoritmo reduz drasticamente o numero de interacções que são
necessárias para manter a precisão dos form factors calculados.
Resulta uma maior qualidade e menor tempo de trabalho computacional.
Este algoritmo funciona melhor em ambientes com poucos e grandes polígonos
e com elevados níveis de brilho que obrigam à subdivisão de polígonos
Refinar sucessivamente o ambiente usando um processo de erro de
luminosidade leva a um algoritmo onde a granularidade em cada passo é menor
que o algoritmo standard.
Rapid Hierarquichal Radiosity Algorithm
Luis Albino de Castro Baptista
Francisco Gaitto Gonçalves Pereira