Figure 4: Cena 3D a) Imagem colorida. b) Mapa de profundidade da imagem a.
O algoritmo de Z-Buffer, desenvolvido por Catmull (Catmull, A subdivision algorithm for computer display of curved surfaces. 1974) é um algoritmo para determinação de superfícies visíveis centrado na resolução da janela de visualização.
Na implementação do algoritmo, cria-se dois espaços de memória: o frame buffer (F), onde esta armazenada as cores computadas a partir da cena, e o buffer de profundidade (Z-Buffer, Z), da mesma resolução que o frame buffer, contendo a profundidade (valor de Z) para cada pixel.
O Z-Buffer (que trabalha nas coordenadas da janela do dispositivo) é inicializado com o valor de 1 (sua variação é de zero até um), o qual representa o valor de Z no plano atrás do volume de visão, enquanto que, o Frame Buffer será inicializado com a cor do fundo da cena. A figura 4 apresenta uma cena e seu correspondente mapa de profundidade.
Figure 4: Cena 3D a) Imagem colorida. b) Mapa de profundidade da imagem a.
Na versão mais simples do algoritmo, os objetos são processados sobre o frame buffer em qualquer ordem, um a um. Durante este processo de conversão de um ponto do polígono para a coordenada (x,y), se o valor de sua profundidade é mais próxima para o observador, então a cor daquele ponto e sua profundidade substituirão o último valor do frame buffer e buffer de profundidade, respectivamente.
O pseudocódigo do algoritmo de z-buffer apresenta-se na figura 5.
Figure 5: Pseudocódigo do algoritmo de z-buffer
Algumas das características básicas do algoritmo são:
Figure 6: O Z-Buffer. A cor do pixel é apresentada em cores e seu valor Z é representado pelo número. a) Adição ao z-buffer de um polígono com valor constante de profundidade. b) Adicionando outro polígono que intersecta o primeiro.
O algoritmo de Z-Buffer não exige que os objetos sejam polígonos, seu maior atrativo é que pode ser utilizado para renderizar qualquer objeto se sua cor e valor z podem ser determinados para cada ponto na sua projeção. Nenhum algoritmo de interseção é necessário.
Baseado na coerência de profundidade, o cálculo da profundidade z para cada ponto pode ser simplificado numa linha de varredura aproveitando o fato de que o polígono é planar. Normalmente, calcular o valor z equivale a resolver a equação do plano: Ax + By + Cz + D=0 para z:
Se, avaliamos a equação anterior para z i , então para (x+dx) o novo valor de z é:
É necessária somente uma subtração para calcular z(x+1,y), dado o valor de z(x,y), o cociente A/C for constante e dx = 1. Da mesa forma pode ser realizado o cálculo do z na próxima linha de varredura, decrementando B/C para cada dy. Se o polígono não for planar, o valor de z(x,y) pode ser calculado interpolando os valores z dos vértices do polígono ao longo de um par de arestas, e depois ao longo de cada linha de varredura, como se apresenta na figura 7.
6: Interpolação de z ao longo das arestas de um polígono e uma linha de varredura. z_a é interpolado entre z_1 e z_2; z_b, entre z_1 e z_3, z_p entre z_a e z_b.
Embora o algoritmo de Z-Buffer requeira grandes quantidades de memória, sua simplicidade e carência de estruturas de dados adicionais, facilitam sua implementação em software e hardware (firmware).
Entretanto, devido a sua natureza centrada na imagem, ele pode sofrer o fenômeno de a aliasing, no caso em que o Z-Buffer possuir precisão limitada. O Z-Buffer é frequentemente implementado em hardware com inteiros de 16 ou 32 bits; em software, se utiliza valores de ponto flutuante.
Depois que a imagem foi renderizada, o z-buffer ainda não perdeu sua utilidade. Seus valores podem ser salvos e posteriormente utilizados. Um exemplo é o cursor 3D que se movimenta ao redor de uma imagem em x, y e z para selecionar um objeto o região da cena (o clássico "picking").
Os algoritmos baseados em listas de prioridades determinam a visibilidade ordenando os objetos de uma cena, garantindo que uma imagem correta será gerada se os objetos forem renderizados em tal ordem. Por exemplo, para objetos não sobreposicionados bastará somente ordenar seus valores de z de forma decrescente e renderizar os objetos em tal ordem. Objetos afastados serão obscurecidos pelos objetos mais próximos, os pixels dos objetos próximos sobrescrevem os pixels dos objetos afastados.
Se os objetos estão sobreposicionados em z, ainda é possível ordená-los, como no caso da figura 8-a. Se os objetos estão sobreposicionados ciclicamente um sobre outro, figuras 8b e 8c, ou penetram um deles, então não há forma de determinar a ordem certa. Nesse casso, será necessário partir um ou mais objetos para fazer um ordenamento linear de ser possível.
Figure 8: Alguns casos onde o valor de z se estende nos polígonos sobrepostos.
Os algoritmos baseados em lista de prioridades são algoritmos híbridos que combinam operações de precisão de objetos e precisão de imagem. A comparação da profundidade z é feita sobre os objetos, entretanto, a varredura de conversão realizada pelo dispositivo gráfico para sobrescrever os pixels dos objetos anteriores é feita com precisão de imagem. Como o ordenamento é realizado com precisão de objeto, a renderização pode ser feita com qualquer resolução de imagem. Temos dois algoritmos de lista de prioridades: o Algoritmo de Ordenamento de Profundidade (Newell, Newell and Sancha 1972) e os Arvore de partição binária do espaço (Fuchs, Kedem and Naylor 1980). A principal diferencia nestes algoritmos está na forma determinar a lista de prioridade, como são divididos os objetos e quando acontece tal divisão.
Em seguida, será apresentado brevemente o Algoritmo do Pintor, o qual é a versão mais simples do Algoritmo de Ordenamento de Profundidade.
O Algoritmo do Pintor é uma versão simplificada do Algoritmo de Ordenamento de Profundidade, desenvolvido por Newell (Newell, Newell and Sancha 1972).
A ideia fundamental neste algoritmo é pintar os polígonos no frame buffer em ordem decrescente, o seja, do objeto mais afastado terminando no objeto mais próximo.
Dois passos conceituais são realizados:
Entretanto, realizando estes passos não se garante que o uma cena seja a desejada, pois nem sempre o algoritmo produz um ordenamento correto.
A figura 9 apresenta uma sequencia de objetos renderizados segundo o Algoritmo do Pintor.
Figure 9: Algoritmo do Pintor. a) Primeiro se pinta as montanhas distantes. b) Depois, pinta-se o prado. c) Finalmente, pintam-se as árvores, as quais são os objetos mais próximos.
Os algoritmos de subdivisão de área utilizam a estratégia "divide e vencerás" realizando uma divisão espacial do plano de projeção. Como a região da imagem é examinada, se fosse possível conhecer quais polígonos são visíveis na área, então eles simplesmente seriam visualizados. Caso contrário, a área é novamente dividida recursivamente em pequenas subáreas, sobre as quais continuamos aplicando a decisão de visualização. Esta abordagem explora a coerência de área, o seja, pequenas áreas da projeção tendem a ser cobertas por apenas um polígono visível.
Dentro da bibliografia, se mencionam três algoritmos representativos desta categoria: o Algoritmo de Warnock (Warnock 1969), o Algoritmo de Weiler-Athernton (Weiler and Atherton 1977) e o Algoritmo de subdivisão de sub-pixels (Catmull, A hidden-surface algorithm with anti-aliasing 1978) (Carpenter 1984). A seguir, fazemos uma exposição do Algoritmo de Warnock.
O Algoritmo desenvolvido por Warnock (Warnock 1969) subdivide cada área de projeção em quatro quadrados iguais. Em cada etapa do processo de subdivisão recursiva, a projeção de cada polígono tem um de quatro tipos de relacionamento como a área de interesse.
Figure 10: Quatro tipos de relacionamento da projeção de um polígono com uma área de interesse. a) Envolvente. b) Intersecção. c) Contido. d) Disjunto.
Da figura anterior, deduzimos que os polígonos disjuntos não tem nenhuma influencia sobre a área de interesse. Igualmente, a parte de um polígono de interseção que esta fora da área é irrelevante. Para o algoritmo somente são importantes à parte interior do polígono de intersecção que recaiu sobre a área de interesse, os polígonos contidos e os polígonos envolventes.
Existem quatro casos triviais para determinar o que esta na frente de uma área, assim que a área não precisa dividir ainda mais para ser conquistada:
O pseudocódigo do Algoritmo de Warnock apresenta-se na figura 11.
Figure 11: Pseudocódigo do algoritmo de Warnock.
Para uma resolução de 1024x1024, são necessários, pelo menos, 10 níveis de subdivisão. Se ao alcançar o número máximo de subdivisões nenhumas dos quatro casos acontecer, então se calcula a profundidade dos polígonos no centro de pixel indivisível, pintando aquele pixel com a cor de polígono mais próximo.
A figura 12 apresenta uma cena simples com as subdivisões necessárias para exibição. O número em cada área corresponde aos casos acima indicados. Nas áreas sem nenhum rótulo, nenhuns dos enunciados são verdadeiros.
Figure 12: Algoritmo de Warnock. Subdivisão de área em quadrados iguais.
O principal inconveniente do Algoritmo de Warnock é que seus testes são muito complexos e lentos. As cenas complexas têm muitos polígonos pequenos e complicada distribuição de profundidade (z), assim varias regiões da tela terminam sobre um simples pixel.
A execução deste algoritmo pode ser vista no seguinte vídeo: http://www.youtube.com/watch?v=e3mmFnDO670
De acordo com a classificação feita no início do trabalho, o algoritmo de ray-tracing faz parte do grupo que aborda a visibilidade orientada a imagem, pois este método determina as superficies visíveis traçando raios de luz imaginários do observador até os objetos da cena, testando se há intersecção entre eles.
A idéia básica deste algoritmo consiste em traçar, para cada pixel na janela de visualização, um raio a partir do centro de projecão até o centro do pixel da cena. Assim, a cor do pixel sera definida como a cor do ponto de intersecção mais próximo encontrado, como pode ser visto na figura 13.
13: Raio projetado saindo do centro de projeção em direção aos objetos da cena.
Assim, este algoritmo, além da determinação de superficies visíveis, pode englobar em sua implementação, a tonalização de cada pixel visível. Entretanto, neste trabalho, será abordado apenas o primeiro caso, o qual se resume em encontrar a intersecção entre os raios traçados e os objetos da cena.
Para solucionar este problema, utiliza-se a representação paramétrica de um vetor. Assim, cada ponto P(x,y,z) que pertença a um raio que parte do ponto P0(x0,y0,z0) até o ponto P1(x1,y1,z1) pode ser definido por uma variável t, de tal forma que: