Voxel Face Crawling (simplificação de malha, possivelmente usando ganancioso)

9

Edit: Isso é apenas para minha própria experiência de aprendizado, NÃO é por razões de desempenho que eu faço essa pergunta.

Isso se refere a um mecanismo de terreno semelhante ao Minecraft. Eu armazeno blocos em blocos (blocos de 16x256x16 em um bloco). Ao gerar um pedaço, uso várias técnicas de procedimento para definir o terreno e colocar objetos. Durante a geração, mantenho uma matriz 1D para todo o bloco (sólido ou não) e uma matriz 1D separada de blocos sólidos.

Após a geração, eu percorro os blocos sólidos verificando seus vizinhos para gerar apenas faces de bloco que não têm vizinhos sólidos. Eu armazeno quais faces gerar em sua própria lista (ou seja, 6 listas, uma por possível face / normal). Ao renderizar um pedaço, renderizo todas as listas no pedaço atual da câmera e apenas as listas voltadas para a câmera em todos os outros pedaços. Eu faço isso armazenando todas as 6 listas em um buffer e simplesmente altero os intervalos que eu desenho.

Usando um atlas 2D com esse pequeno truque de shader sugerido por Andrew Russell, quero mesclar completamente rostos semelhantes. Ou seja, se eles estão na mesma lista (o mesmo normal), são adjacentes um ao outro, têm o mesmo nível de luz etc. Eu sei que ainda vou acabar com retângulos, mas isso deve reduzir facilmente minha contagem de vértices em 50% ou melhor, se minhas estimativas estiverem corretas.

Minha suposição seria ter cada uma das 6 listas classificadas pelo eixo em que repousam e depois pelos outros dois eixos (a lista para o topo de um bloco seria classificada pelo seu valor Y, depois X e Z).

Com isso, eu poderia facilmente mesclar tiras de rostos, mas estou procurando mesclar mais do que apenas tiras juntas, quando possível. Eu li esse algoritmo de malha ganancioso, mas estou tendo muitos problemas para entendê-lo.

Então, minha pergunta: para realizar a mesclagem de faces como descrito (ignorando se é uma má idéia para terreno / iluminação dinâmicos), existe talvez um algoritmo mais simples de implementar? Eu também aceitaria com satisfação uma resposta que me orienta pelo algoritmo ganancioso de uma maneira muito mais simples (um link ou explicação).

Não me importo com uma ligeira diminuição no desempenho se for mais fácil de implementar ou mesmo se for apenas um pouco melhor do que apenas fazer tiras. Eu me preocupo que a maioria dos algoritmos se concentre em triângulos em vez de quads e, usando um atlas 2D do jeito que sou, não sei se poderia implementar algo triângulo com base em minhas habilidades atuais.

PS: Eu já seleciono frustum por bloco e, como descrito, também seleciono faces entre blocos sólidos. Eu não abro a oclusão ainda e talvez nunca.

* Edit: Eu implementei minha própria técnica pequena, que provavelmente tem um nome, mas eu simplesmente passo minhas 6 listas, que são classificadas pelos eixos em que repousam, seguidas pelo tipo de bloco e depois pelo nível de iluminação. Eu itero através deles, criando novos retângulos à medida que os passo e os desenvolvo simultaneamente (com um forte viés em direção a um determinado eixo). Definitivamente, não é o ideal, mas é realmente muito rápido e reduz minha contagem de vértices em cerca de 50%, em média. O comentário de Byte56 é o armário que penso em uma resposta real, mas não posso selecioná-lo para a resposta / recompensa.

Aqui está a minha maneira rápida e simplista de lidar com esse problema APÓS gerar o terreno inicial completo sem muita otimização. Supondo que todos os quadrados dados sejam a mesma imagem, nível de luz, normal, etc. cada cor é um quad diferente que eu renderizaria. Com minhas listas ordenadas do jeito que estão, essa é uma abordagem muito fácil / rápida.

Mythics
fonte
Depois de todas as suas otimizações, você ainda está tendo problemas de desempenho? Você já tentou criar um perfil do código para ver onde estão os problemas?
MichaelHouse
@ Byte56 Oh, definitivamente não é um problema de desempenho no momento. Pode ser um no futuro quando tento colocar o que estou aprendendo a usar em um jogo real. Por enquanto, estou simplesmente querendo aprender. Não afirmei nada disso, porque pareço receber menos ajuda se estou apenas querendo aprender coisas simplesmente para aprendê-las.
Mitos
Eu também acho que devo dizer que, se eu realmente tentar um jogo adequado com isso, quero que o mundo visível seja ENORME. Eu não gostaria que o personagem tivesse 2 blocos de altura e 1 de largura como Minecraft e muitos outros, mas mais como 3 blocos de largura / comprimento e 6-9 de altura. Provavelmente terreno estático.
Mitos
11
Ah, tudo bem, Tim. Obrigada pelo esclarecimento. Eu fiz algumas pesquisas sobre isso quando eu estava produzindo o motor para o meu jogo. Como meu cenário é dinâmico, não achei que valeria o custo de desempenho toda vez que algo fosse alterado. No entanto, você pode encontrar alguma utilidade neste artigo sobre o problema do retângulo máximo. Essencialmente, é o algoritmo que você está falando para mesclar rostos semelhantes (talvez não gananciosos, mas o ideal). Boa sorte!
MichaelHouse
@ Byte56 Obrigado, eu aprecio muito. Isso certamente parece mais próximo do tipo de algoritmo que eu estou procurando, se não no local. Vou ter que mexer um pouco para ver se consigo obter todos os retângulos máximos com uma única execução. Posso dar uma recompensa por isso também daqui a pouco, pois acho que a pergunta e uma resposta detalhada podem ajudar muitos outros no futuro.
Mitos

Respostas:

4

Você só quer fazer tiras ou, na melhor das hipóteses, retângulos. Não há outras formas que possam ser solucionadas ou úteis para você.

Gostaria também de salientar que, mantendo 6 listas por bloco, a qualquer momento você usará 5 listas dos blocos nas direções cardeais e pelo menos 3 em todas as outras. Você está perdendo tempo aqui, quando não apenas a placa de vídeo pode fazer essa otimização para você, mas, mesmo que você tenha feito isso, seria melhor manter todos os rostos em um só lugar e comparar o normal com a direção com o camera (produto de pesquisa DOT de vetores).

Os links do CaptainRedMuff na tela Greedy que você já viu é a resposta para o seu problema. Também deve ficar claro que você terminará com malhas "Stripy", mas elas são perfeitamente eficazes, e vir com algo mais ideal será mais complicado, e você expressou que a malha gananciosa já é muito complicada.

Se você está tendo problemas de desempenho com um único pedaço, isso me faz pensar que outra coisa está muito errada.

Meu primeiro palpite seria que você está chamando uma operação de desenho com muita frequência. Você pode apenas dizer à placa gráfica que desenhe entre 50 e 400 ~ vezes por segundo, dependendo do hardware. Quantas chamadas para .setData ou .draw ____ Primitivas você está fazendo?

Phil
fonte
Retângulos são o que eu quero. O Byte56 vinculou um algoritmo muito mais simples de seguir do que ganancioso, mas não posso aceitar um comentário como resposta. Eu assumi que ele comentou, porque ele apenas vinculou a um algoritmo em vez de explicá-lo. Não sei o que você quer dizer com relação a minhas listas. Normalmente, eu tenho de 1 a 2 chamadas por bloco. Minhas listas são armazenadas em um buffer por bloco. Eu mudo os intervalos para desenhar por quadro. Eu posso estar errado, mas enviar dados desnecessários para a GPU parece contraproducente. Um empate extra ou dois por pedaço parece melhor do que enviar mais dados para a gpu e forçá-la a selecionar.
Mitos
Não estou tendo problemas de desempenho. Eu simplesmente gosto de aprender essas coisas. Vou editar minha pergunta para dizer isso, mas, como também contei ao Byte56, recebo menos ajuda se o que estou tentando fazer não estiver realmente resolvendo um problema. Para responder à sua pergunta, processo no máximo 200-260 pedaços por quadro atualmente. É um DrawIndexedPrimitives 500ish bastante comum por quadro. Eu recebo regularmente de 100 a 130 FPS sem vsync, fazendo 65.000 chamadas por segundo. Não estou tentando ser rude, mas pouco que você disse faz sentido para mim. Eu posso não entender, então por favor explique se eu entendi errado. Talvez isso tenha a ver com XNA?
Mitos
Ah, desculpe, eu quis dizer por quadro, não por segundo. Você está chegando perto de um limite superior e, se estiver apenas no terreno, estará praticamente acabando.
6133 Phil
Marquei sua resposta com +1, pois ela me fez pensar em algumas melhorias que eu poderia fazer, mas nada a ver com a pergunta. Além disso, eu pensei que deveria compartilhar uma resposta de Nathan Reed no limite possível chamada de desenho ligação
Mythics
Vou ter que encontrar o artigo que li que citou 400-500 como limite. Um google rápido não me ajudou.
19413 Phil
0

O artigo ao qual você vincula não fornece realmente um algoritmo para gerar a malha; indica uma maneira de avaliar possíveis soluções.

Geralmente, no entanto, o artigo fornece um bom resumo: 1) a solução ingênua é ruim, 2) existe uma solução ideal, mas será demorado escrever e executar, 3) uma seleção rápida fornece resultados muito melhores ( e isso é tudo o que o próprio Minecraft faz) e, finalmente, 4) pode haver uma solução mais inteligente (o algoritmo ganancioso).

A "solução" que você implica na imagem da sua pergunta é o algoritmo ganancioso. Parece que sua pergunta é "eu implementei a solução dele corretamente?" ao qual devo responder "ele não deu uma solução; você acabou de resolver isso sozinho".

Sua solução pode ser melhor? Meh. Certo. Provavelmente não vale a pena. Acho que a seleção por oclusão ou LOD seriam melhores próximos passos. O Minecraft desperdiça um bom número de ciclos desenhando a superfície mesmo quando você está no subsolo, bem como desenhando vastas redes de cavernas e sistemas de minas quando está na superfície. Uma vez que você tenha uma boa quebra de malha, sim, livrar-se de superfícies obscurecidas pode ser uma coisa boa - mas (por exemplo) geralmente é mais rápido permitir que sua placa de vídeo faça a seleção de backface do que na CPU.

AndrewS
fonte