- Explique como ordenar os polígonos no algoritmo do pintor.
Passo 1
O enunciado pede para explicarmos como, no algoritmo do pintor, ordenamos uma coleção de polígonos para desenhá-los do mais distante ao mais próximo em relação à câmera, de modo a sobrepor corretamente as faces visíveis. O conteúdo aqui é renderização gráfica e precisamos saber: coordenadas dos vértices em espaço de câmera (ou eye space), como extrair um valor de profundidade para cada polígono e como usar essa informação para fazer uma ordenação.
Passo 2
Para cada polígono, calculamos um escalar que represente sua “profundidade média” ou “profundidade de referência”. A forma mais simples é usar a coordenada
de cada vértice (já em espaço de câmera) e definir:
onde
é o número de vértices do polígono e
é a coordenada
do
-ésimo vértice. Esse valor diz quão “longe” em média o polígono está da câmera.
Passo 3
Com todos os
calculados, ordenamos a lista de polígonos de modo decrescente de profundidade média: o polígono com maior
(mais distante) vem primeiro, e o polígono com menor
(mais próximo) vem por último. Podemos usar qualquer algoritmo de ordenação estável, por exemplo QuickSort, MergeSort ou até um simples InsertionSort se o número de polígonos for pequeno.
Passo 4
Desenhamos os polígonos nesta ordem: começamos pelo primeiro da lista (o mais longe) e “pintamos” na tela, depois vamos sobrepondo com cada próximo (que está mais perto). Assim, polígonos próximos cobrem corretamente os mais distantes.
Passo 5
Em alguns casos há interseção ou ciclo de sobreposição entre polígonos (A sobre B, B sobre C, C sobre A) e a ordenação por profundidade média não resolve. A solução clássica é usar um BSP tree (Binary Space Partitioning):
- Escolho um polígono como plano de separação.
- Divido todos os outros em três conjuntos: in front, behind e intersectando.
- Para os que intersectam, faço split em dois pedaços, um para cada lado do plano.
- Recorro à mesma rotina nos dois subespaços, garantindo que sempre posso ordenar sem ciclos.
Resposta
Para ordenar polígonos no algoritmo do pintor:
(a) Calculo para cada polígono um valor de profundidade, tipicamente a média das coordenadas de seus vértices.
(b) Ordeno os polígonos de forma decrescente nesse valor (mais distante primeiro).
(c) Desenho-os nesta ordem, garantindo que faces próximas sobreponham faces distantes.
(d) Se houver interseções cíclicas, uso particionamento BSP para dividir polígonos e eliminar ciclos de sobreposição.
(a) Calculo para cada polígono um valor de profundidade, tipicamente a média das coordenadas
(b) Ordeno os polígonos de forma decrescente nesse valor (mais distante primeiro).
(c) Desenho-os nesta ordem, garantindo que faces próximas sobreponham faces distantes.
(d) Se houver interseções cíclicas, uso particionamento BSP para dividir polígonos e eliminar ciclos de sobreposição.