1. 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 z de cada vértice (já em espaço de câmera) e definir:
z_{\text{médio}} \;=\; \frac{1}{n}\sum_{i=1}^{n} z_ié
onde n é o número de vértices do polígono e z_i é a coordenada z do i-ésimo vértice. Esse valor diz quão “longe” em média o polígono está da câmera.

Passo 3

Com todos os z_{\text{médio}}é calculados, ordenamos a lista de polígonos de modo decrescente de profundidade média: o polígono com maior z_{\text{médio}}é (mais distante) vem primeiro, e o polígono com menor z_{\text{médio}}é (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):
  1. Escolho um polígono como plano de separação.
  2. Divido todos os outros em três conjuntos: in front, behind e intersectando.
  3. Para os que intersectam, faço split em dois pedaços, um para cada lado do plano.
  4. 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 z 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.

Exercícios relacionados