Classificar polígonos em ordem - não está funcionando?

Eu sou bastante novo em programação em um mundo 3D.

Estou tentando criar uma tela em que todos os objetos são desenhados na ordem do mais longe ao mais próximo e de baixo para cima - para que não se sobreponham, mas há problemas.

insira a descrição da imagem aqui

Como você pode ver, alguns dos objetos se sobrepõem. Nenhum dos objetos na tela estará se movendo, então eu queria saber: existe um algoritmo disponível para classificar os objetos na ordem correta? No momento, eu os ordeno no eixo Z ascendente, depois X desce e Y desce.

c# 3d isometric Pedro
fonte

só vou perguntar arbitrariamente, já que você disse que é novo na programação 3D, o mecanismo que você está usando suporta testes de profundidade? a classificação em profundidade só o levará até agora. mesmo se você resolver este problema que você está tendo, L ou T em forma de blocos, por exemplo, fará com que artifacting

dreta

+1 porque este é um tópico de grande interesse para o 3d em geral e sua ilustração é ótima.

Patrick Hughes

Respostas:

Como o @dreta mencionado nos comentários, a maneira típica de os mecanismos 3D resolverem isso é com um buffer de profundidade e usando o teste de profundidade do hardware, que permite desenhar objetos de forma arbitrária em qualquer ordem e acompanhar a superfície mais próxima de cada pixel . A classificação manual de objetos também é possível, mas não necessariamente manipula objetos não-convexos ou sobrepostos corretamente.

No entanto, se você quiser classificar objetos, será necessário calcular um valor de profundidade para cada objeto e classificar por profundidade descendente. Para obter profundidade, se você estiver usando uma configuração típica de mecanismo 3D, será necessário transformar o ponto central de cada objeto através da sua matriz de vistas (que vai do espaço do mundo para o espaço da vista), e então tomar o negativo da coordenada Z de o resultado. (Negativo porque nas coordenadas destras com X e Y alinhados com a tela, Z estará apontando para fora da tela.)

Se for sempre uma vista isométrica como essa, você provavelmente poderá calcular a profundidade = ± X ± Y - Z, onde o ± significa: escolha o sinal que aumenta a profundidade à medida que você se afasta da câmera. Isso dependerá da orientação dos seus eixos X e Y.

Nathan Reed
fonte

Mesmo com uma vista isométrica, não é possível classificar formas usando um valor de profundidade. A única coisa que você pode fazer, desde que as formas e a organização da cena não sejam muito complicadas (e geralmente são), é criar uma ordem parcial ( ou seja, dadas duas formas, diga qual deve ser desenhado primeiro). A partir disso, você precisaria classificar as formas (usando, por exemplo, classificação topológica) e, por si só, geralmente é uma operação O (n²) quando você tiver sorte, mas estou apostando em O (n²logn).

sam hocevar

@SamHocevar Sim, como observei na minha resposta, a classificação de objetos por profundidade não lidará com todos os casos corretamente, especialmente (mas não se limitando a) objetos não-convexos ou sobrepostos. É uma aproximação na melhor das hipóteses. BTW, acredito que a classificação topológica de um gráfico sempre pode ser feita em O (V + E) (é basicamente apenas DFS). A contagem de arestas pode ser O (V ^ 2), mas suspeito que não seja tão ruim assim.

Nathan Reed

@SamHocevar Em uma vista isométrica com todos os objetos retângulos alinhados ao eixo sem interseção, no entanto - como mostra o exemplo -, é provável que você possa ordenar formas? Você conhece alguma construção de uma figura que não possa ser classificada (por exemplo, algo que tenha uma sobreposição cíclica) sob essas restrições?

Steven Stadnicki

@StevenStadnicki Aqui está um caso em que a classificação ingênua por profundidade não funcionaria. A ordem correta do desenho nesse diagrama seria vermelho, verde, azul, mas a classificação de profundidade com base no centro de cada retângulo (pontos pretos) forneceria azul, verde e vermelho. (A linha pontilhada é perpendicular à vista, para que você possa ver claramente a relação entre as profundezas dos centros.) A classificação topológica de Sam funcionaria aqui, fornecendo uma maneira de determinar as relações "atrasadas" entre os retângulos.

Nathan Reed

Aqui está um exemplo de objetos alinhado ao eixo que você não pode tipo: i.stack.imgur.com/jey1e.png

Sam Hocevar

Confira o algoritmo do pintor e suas desvantagens.

Valmond
fonte

Em geral, a resposta para sua pergunta ('existe um algoritmo disponível para classificar os objetos na ordem correta?') Em configurações arbitrárias em 3D não existe - nenhum algoritmo pode existir, mesmo quando os objetos são tão simples quanto triângulos. É fácil construir três triângulos com uma sobreposição cíclica; por exemplo, imagine olhar para o eixo Z em três triângulos longos e finos:

A: (2.1, 1.9, 1), (1.9, 2.1, 1), (-1, -1, 0)
B: (-2,1, 1,9, 0), (-1,9, 2,1, 0), (1, -1, 1)
C: (2.1, 1, 0), (1.9, 1, 0), (-2, 1, 1)

Então, onde A e B se sobrepõem na tela (próximo ao ponto XY (0,0)), B estará no topo (tem o valor Z mais alto): seu valor Z será aproximadamente 0,66 enquanto A será aproximadamente 0,33. Da mesma forma, onde A e C se sobrepõem (próximo ao ponto XY (1, 1)), A estará no topo; e onde B e C se sobrepõem (próximo ao ponto XY (1, -1)), C estará no topo. Não há como ordenar esses três triângulos, de modo que desenhá-los na tela na ordem especificada dará o resultado correto.

Como sugere Nathan Reed, o fato de você estar em uma visão isométrica significa que provavelmente seria capaz de evitar esse problema em particular; a questão é se vale a pena evitar ou não, e isso depende mais do seu ambiente e da funcionalidade específica que você tem disponível. A maioria das plataformas em que você pode estar desenvolvendo tem pelo menos alguma forma de renderização em 3D prontamente disponível, e minha primeira inclinação seria apenas pegar carona nessa tarefa para seus propósitos.

Steven Stadnicki
fonte