Como otimizar um mundo voxel no estilo Minecraft?

Eu achei os maravilhosos mundos grandes do Minecraft extremamente lentos para navegar, mesmo com um quad core e uma placa de vídeo carnuda.

Presumo que a lentidão do Minecraft venha de:

• Java, pois o particionamento espacial e o gerenciamento de memória são mais rápidos no C ++ nativo.
• Particionamento mundial fraco.

Eu poderia estar errado em ambas as suposições. No entanto, isso me fez pensar sobre a melhor maneira de gerenciar grandes mundos de voxel. Como é um verdadeiro mundo 3D, onde um bloco pode existir em qualquer parte do mundo, que é basicamente uma grande matriz 3D [x][y][z], onde cada bloco no mundo tem um tipo (isto é BlockType.Empty = 0, BlockType.Dirt = 1, etc.)

Presumo que, para que esse tipo de mundo funcione bem, você precisará:

• Use uma árvore de alguma variedade ( oct / kd / bsp ) para dividir todos os cubos; parece que um oct / kd seria a melhor opção, pois é possível particionar em um nível por cubo e não por triângulo.
• Use algum algoritmo para descobrir quais blocos podem ser vistos no momento, pois os blocos mais próximos do usuário podem ofuscar os blocos, tornando inútil renderizá-los.
• Mantenha o objeto do bloco leve, para que seja rápido adicioná-lo e removê-lo das árvores.

Eu acho que não há resposta certa para isso, mas eu estaria interessado em ver as opiniões das pessoas sobre o assunto. Como você melhoraria o desempenho em um grande mundo baseado em voxel?

Com relação ao Java vs C ++, escrevi um mecanismo voxel em ambos (versão C ++ mostrada acima). Também escrevo motores voxel desde 2004 (quando não estavam em voga). :) Posso dizer com pouca hesitação que o desempenho do C ++ é muito superior (mas também é mais difícil de codificar). É menos sobre a velocidade computacional e mais sobre gerenciamento de memória. Sem dúvida, quando você está alocando / desalocando tantos dados quanto os que estão no mundo dos voxel, C (++) é o idioma a ser batido. Contudo, você deve pensar em seu objetivo. Se o desempenho é sua maior prioridade, vá com C ++. Se você quer apenas escrever um jogo sem desempenho de ponta, o Java é definitivamente aceitável (como evidenciado pelo Minecraft). Existem muitos casos triviais / de borda, mas em geral você pode esperar que o Java execute cerca de 1,75-2,0 vezes mais lento que o C ++ (bem escrito). Você pode ver uma versão mais antiga e mal otimizada do meu mecanismo em ação aqui (EDIT: versão mais recente aqui ). Embora a geração de chunk possa parecer lenta, lembre-se de que está gerando diagramas de voronoi 3D volumetricamente, calculando normais de superfície, iluminação, AO e sombras na CPU com métodos de força bruta. Eu experimentei várias técnicas e posso obter uma geração de chunk 100x mais rápida usando várias técnicas de armazenamento em cache e instanciação.

Para responder ao restante da sua pergunta, há muitas coisas que você pode fazer para melhorar o desempenho.

1. Armazenamento em cache. Sempre que possível, você deve calcular os dados uma vez. Por exemplo, asso a iluminação na cena. Poderia usar iluminação dinâmica (no espaço da tela, como um pós-processo), mas assar a iluminação significa que não preciso passar nas normais pelos triângulos, o que significa ...

2. Passe o mínimo de dados possível para a placa de vídeo. Uma coisa que as pessoas tendem a esquecer é que, quanto mais dados você passa para a GPU, mais tempo leva. Eu passo em uma única cor e uma posição de vértice. Se eu quiser fazer ciclos de dia / noite, posso apenas fazer a classificação das cores ou recalcular a cena à medida que o sol muda gradualmente.

3. Como a transmissão de dados para a GPU é muito cara, é possível escrever um mecanismo em um software que é mais rápido em alguns aspectos. A vantagem do software é que ele pode fazer todos os tipos de manipulação de dados / acesso à memória que simplesmente não são possíveis em uma GPU.

4. Brinque com o tamanho do lote. Se você estiver usando uma GPU, o desempenho pode variar drasticamente com base no tamanho de cada matriz de vértices que você passa. Assim, brinque com o tamanho dos pedaços (se você usar pedaços). Descobri que os pedaços de 64x64x64 funcionam muito bem. Não importa o que aconteça, mantenha seus pedaços cúbicos (sem prismas retangulares). Isso tornará a codificação e várias operações (como transformações) mais fáceis e, em alguns casos, mais eficientes. Se você armazenar apenas um valor para o comprimento de cada dimensão, lembre-se de que existem dois registros a menos que são trocados durante a computação.

5. Considere as listas de exibição (para OpenGL). Mesmo sendo o caminho "antigo", eles podem ser mais rápidos. Você deve criar uma lista de exibição em uma variável ... se você chamar as operações de criação de lista de exibição em tempo real, será incrivelmente lento. Como uma lista de exibição é mais rápida? Ele atualiza apenas o estado, versus atributos por vértice. Isso significa que posso passar até seis faces e depois uma cor (vs uma cor para cada vértice do voxel). Se você estiver usando GL_QUADS e voxels cúbicos, isso poderá economizar até 20 bytes (160 bits) por voxel! (15 bytes sem alfa, embora geralmente você queira manter as coisas alinhadas em 4 bytes).

6. Eu uso um método de força bruta para renderizar "pedaços", ou páginas de dados, que é uma técnica comum. Ao contrário das octrees, é muito mais fácil / rápido ler / processar os dados, embora seja muito menos amigável à memória (no entanto, hoje em dia você pode obter 64 gigabytes de memória por US $ 200 a US $ 300) ... não que o usuário médio tenha isso. Obviamente, você não pode alocar uma matriz enorme para o mundo inteiro (um conjunto de 1024x1024x1024 de voxels tem 4 gigabytes de memória, assumindo que um int de 32 bits seja usado por voxel). Assim, você aloca / desaloca muitas pequenas matrizes, com base na proximidade delas com o visualizador. Você também pode alocar os dados, obter a lista de exibição necessária e despejar os dados para economizar memória. Eu acho que a combinação ideal pode ser usar uma abordagem híbrida de octrees e matrizes - armazene os dados em uma matriz ao fazer a geração procedural do mundo, iluminação, etc,

7. Renderizar próximo ao longe ... um pixel recortado economiza tempo. A gpu lançará um pixel se não passar no teste do buffer de profundidade.

8. Renderize apenas pedaços / páginas na janela de exibição (auto-explicativa). Mesmo que a gpu saiba cortar os polígonos fora da janela de exibição, a transmissão desses dados ainda leva tempo. Não sei qual seria a estrutura mais eficiente para isso ("vergonhosamente", nunca escrevi uma árvore BSP), mas mesmo um simples raycast em uma base por pedaço pode melhorar o desempenho e, obviamente, testar contra o frustum visual economizar tempo.

9. Informações óbvias, mas para os novatos: remova todos os polígonos que não estão na superfície - ou seja, se um voxel consiste em seis faces, remova as faces que nunca são renderizadas (estão tocando em outro voxel).

10. Como regra geral de tudo o que você faz na programação: LOCALIDADE DO CACHE! Se você pode manter as coisas em cache local (mesmo que por um curto período de tempo, isso fará uma enorme diferença. Isso significa manter seus dados congruentes (na mesma região de memória) e não mudar áreas da memória para processar com muita frequência. , idealmente, trabalhe em um pedaço por thread e mantenha essa memória exclusiva para o thread. Isso não se aplica apenas ao cache da CPU. Pense na hierarquia de cache assim (mais lenta para mais rápida): network (cloud / database / etc) -> disco rígido (obtenha um SSD se você ainda não tiver um), ram (obtenha um canal tripple ou mais RAM, se ainda não o tiver), cache (s) da CPU, registre-se. o fim final, e não trocá-lo mais do que você precisa.

11. Rosqueamento. Faça. Os mundos da Voxel são adequados para o encadeamento, pois cada parte pode ser calculada (principalmente) independentemente das outras ... Eu vi literalmente uma melhoria quase 4x (em um Core i7 de 4 núcleos e 8 threads) na geração processual do mundo quando escrevi rotinas para rosqueamento.

12. Não use tipos de dados de caracteres / bytes. Ou shorts. Seu consumidor médio terá um processador AMD ou Intel moderno (como você provavelmente). Esses processadores não possuem registradores de 8 bits. Eles calculam os bytes colocando-os em um slot de 32 bits e os convertendo de volta (talvez) na memória. Seu compilador pode fazer todo tipo de vodu, mas usar um número de 32 ou 64 bits fornecerá os resultados mais previsíveis (e mais rápidos). Da mesma forma, um valor "bool" não leva 1 bit; o compilador geralmente usa 32 bits completos para um bool. Pode ser tentador fazer certos tipos de compactação nos seus dados. Por exemplo, você pode armazenar 8 voxels como um número único (2 ^ 8 = 256 combinações) se todos forem do mesmo tipo / cor. No entanto, você precisa pensar nas ramificações disso - isso pode economizar bastante memória, mas também pode prejudicar o desempenho, mesmo com um pequeno tempo de descompressão, porque mesmo essa pequena quantidade de tempo extra varia de acordo com o tamanho do seu mundo. Imagine calcular um raycast; para cada etapa do raycast, você teria que executar o algoritmo de descompressão (a menos que tenha uma maneira inteligente de generalizar o cálculo para 8 voxels em uma etapa de raio).

13. Como José Chávez menciona, o padrão de design do peso mosca pode ser útil. Assim como você usaria um bitmap para representar um bloco em um jogo 2D, você pode criar seu mundo com vários tipos de blocos (ou blocos) em 3D. A desvantagem disso é a repetição de texturas, mas você pode melhorar isso usando texturas de variação que se encaixam. Como regra geral, você deseja utilizar instâncias sempre que puder.

14. Evite o processamento de vértices e pixels no sombreador ao gerar a geometria. Em um mecanismo voxel, você inevitavelmente terá muitos triângulos, portanto, mesmo um simples sombreador de pixel pode reduzir bastante o tempo de renderização. É melhor renderizar em um buffer, e você usa pixel shader como um pós-processo. Se você não puder fazer isso, tente fazer cálculos no seu shader de vértice. Outros cálculos devem ser detalhados nos dados do vértice sempre que possível. Passagens adicionais ficam muito caras se você precisar renderizar novamente toda a geometria (como mapeamento de sombra ou mapeamento de ambiente). Às vezes, é melhor desistir de uma cena dinâmica em favor de detalhes mais ricos. Se o seu jogo tiver cenas modificáveis ​​(ou seja, terrenos destrutíveis), você sempre poderá recalcular a cena à medida que as coisas forem destruídas. A recompilação não é cara e deve levar menos de um segundo.

15. Descontraia seus loops e mantenha as matrizes planas! Não faça isso:

    for (i = 0; i < chunkLength; i++) {
     for (j = 0; j < chunkLength; j++) {
      for (k = 0; k < chunkLength; k++) {
       MyData[i][j][k] = newVal;
      }
     }
    }
    //Instead, do this:
    for (i = 0; i < chunkLengthCubed; i++) {
     //figure out x, y, z index of chunk using modulus and div operators on i
     //myData should have chunkLengthCubed number of indices, obviously
     myData[i] = newVal;
    }
    

    EDIT: Através de testes mais extensos, descobri que isso pode estar errado. Use o caso que funciona melhor para o seu cenário. Geralmente, as matrizes devem ser planas, mas o uso de loops com vários índices pode ser mais rápido, dependendo do caso

EDIT 2: ao usar loops com vários índices, é melhor fazer um loop na ordem z, y, x, e não o contrário. Seu compilador pode otimizar isso, mas eu ficaria surpreso se isso acontecesse. Isso maximiza a eficiência no acesso à memória e na localidade.

for (k < 0; k < volumePitch; k++) {
    for (j = 0; j < volumePitch; j++) {
        for (i = 0; i < volumePitch; i++) {
            myIndex = k*volumePitch*volumePitch + j*volumePitch + i;
        }
    }
}

16. Às vezes você tem que fazer suposições, generalizações e sacrifícios. O melhor que você pode fazer é assumir que a maior parte do seu mundo é completamente estática e muda apenas a cada dois mil quadros. Para as partes animadas do mundo, elas podem ser feitas em um passe separado. Também assuma que a maior parte do seu mundo é completamente opaca. Objetos transparentes podem ser renderizados em um passe separado. Suponha que as texturas variem apenas a cada x unidades ou que os objetos possam ser colocados apenas em incrementos de x. Suponha um tamanho de mundo fixo ... Por mais tentador que seja um mundo infinito, ele pode levar a requisitos de sistema imprevisíveis. Por exemplo, para simplificar a geração do padrão de voronoi nas rochas acima, eu assumi que todos os pontos centrais dos voronoi estavam em uma grade uniforme, com um pequeno deslocamento (em outras palavras, o hash geométrico implícito). Suponha que um mundo não envolva (tenha arestas). Isso pode simplificar muitas complexidades introduzidas por um sistema de coordenadas de empacotamento, a um custo mínimo para a experiência do usuário.

Você pode ler mais sobre minhas implementações no meu site

Há muitas coisas que o Minecraft poderia estar fazendo com mais eficiência. Por exemplo, o Minecraft carrega pilares verticais inteiros com cerca de 16x16 blocos e os renderiza. Eu sinto que é muito ineficiente enviar e renderizar tantas peças desnecessariamente. Mas não acho que a escolha do idioma seja importante.

O Java pode ser bastante rápido, mas, para algo orientado a dados, o C ++ possui uma grande vantagem com uma sobrecarga significativamente menor para acessar matrizes e trabalhar em bytes. Por outro lado, é muito mais fácil executar threading em todas as plataformas em Java. A menos que você planeje utilizar o OpenMP ou o OpenCL, não encontrará essa conveniência no C ++.

Meu sistema ideal seria uma hierarquia um pouco mais complexa.

O bloco é uma unidade única, provavelmente em torno de 4 bytes, para manter informações como tipo de material e iluminação.

O segmento seria um bloco de blocos de 32 x 32 x 32.

1. Bandeiras seriam definidas para cada um dos seis lados, se esse lado inteiro for um bloco sólido. Isso permitiria ao renderizador ocultar segmentos atrás desse segmento. Atualmente, o Minecraft não parece executar testes de oclusão. Mas houve menção de ter disponível a seleção por oclusão de hardware, o que pode ser caro, mas melhor do que a renderização de grandes quantidades de polígonos em cartões de baixo custo.
2. Os segmentos só seriam carregados na memória durante a atividade (jogadores, NPCs, física da água, crescimento de árvores, etc.). Caso contrário, eles seriam enviados diretamente ainda compactados do disco para os clientes.

Os setores seriam um bloco de segmentos 16x16x8.

1. Os setores rastreiam o segmento mais alto de cada coluna vertical, para que segmentos mais altos que isso possam ser rapidamente determinados vazios.
2. Ele também rastreia o segmento ocluído inferior, para que todos os segmentos que precisam ser renderizados da superfície possam ser rapidamente agarrados.
3. Os setores também acompanhariam a próxima vez que cada segmento precisar ser atualizado (física da água, crescimento de árvores, etc.). Dessa forma, carregar em cada setor seria suficiente para manter o mundo vivo e carregar apenas segmentos por tempo suficiente para concluir suas tarefas.
4. Todas as posições da entidade seriam rastreadas em relação ao setor. Isso impediria os erros de ponto flutuante presentes no Minecraft ao viajar muito longe do centro do mapa.

O mundo seria um mapa infinito de setores.

1. O mundo seria responsável por gerenciar setores e suas próximas atualizações.
2. O mundo enviaria preventivamente segmentos aos jogadores em seus caminhos potenciais. O Minecraft envia reativamente os segmentos solicitados pelo cliente, causando um atraso.

O Minecraft é bem rápido, mesmo no meu 2-core. Java não parece ser um fator limitante aqui, embora exista um pouco de atraso no servidor. Os jogos locais parecem se sair melhor, então vou assumir algumas ineficiências lá.

Quanto à sua pergunta, Notch (autor do Minecraft) já escreveu em algum blog sobre a tecnologia. Em particular, o mundo é armazenado em "pedaços" (às vezes você os vê, especialmente quando um está faltando porque o mundo ainda não foi preenchido). Portanto, a primeira otimização é decidir se um pedaço pode ser visto ou não. .

Dentro de um pedaço, como você adivinhou, o aplicativo precisa decidir se um bloco pode ser visto ou não, com base em se é ou não obscurecido por outros blocos.

Observe também que há o bloco FACES, que pode ser considerado não visto, devido ao fato de ser obscurecido (ou seja, outro bloco cobre o rosto) ou por qual direção a câmera está apontando (se a câmera estiver voltada para o norte, você pode veja a face norte de QUALQUER bloco!)

As técnicas comuns também incluem não manter objetos de bloco separados, mas, em vez disso, um "bloco" de tipos de bloco, com um único bloco de protótipo para cada um, juntamente com um conjunto mínimo de dados para descrever como esse bloco pode ser personalizado. Por exemplo, não existem blocos de granito personalizados (que eu saiba), mas a água possui dados para determinar a profundidade em cada face lateral, a partir da qual é possível calcular sua direção do fluxo.

Sua pergunta não está clara se você deseja otimizar a velocidade de renderização, tamanho dos dados ou o quê. Esclarecimento seria útil.

Aqui estão apenas algumas palavras de informações e conselhos gerais, que posso dar como um modder Minecraft muito experiente (que pode, pelo menos em parte, fornecer algumas orientações).

O motivo pelo qual o Minecraft é lento tem muito a ver com algumas decisões questionáveis ​​e de baixo nível de design - por exemplo, toda vez que um bloco é referenciado por posicionamento, o jogo valida as coordenadas com cerca de 7 se instruções para garantir que não esteja fora dos limites. . Além disso, não há como pegar um 'pedaço' (uma unidade de blocos de 16x16x256 com a qual o jogo trabalha) e, em seguida, referenciar blocos nele diretamente, a fim de ignorar pesquisas de cache e, erm, problemas de validação boba (ou seja, cada referência de bloco também envolve uma pesquisa de partes, entre outras coisas.) No meu mod, criei uma maneira de capturar e alterar diretamente a matriz de blocos, o que impulsionou a geração massiva de masmorras, de inegavelmente atrasada a inegavelmente rápida.

EDIT: Removida a alegação de que declarar variáveis ​​em um escopo diferente resultou em ganhos de desempenho, na verdade, esse não parece ser o caso. Acredito que na época em que confluí esse resultado com outra coisa com a qual eu estava experimentando (especificamente, removendo elencos entre duplos e flutuadores em códigos relacionados a explosões, consolidando-os em duplos ... compreensivelmente, isso teve um enorme impacto!)

Além disso, embora não seja a área em que passo muito tempo, a maior parte do estrangulamento de desempenho no Minecraft é um problema com a renderização (cerca de 75% do tempo do jogo é dedicado a ela no meu sistema). Obviamente, você não se importa tanto se a preocupação for apoiar mais jogadores no modo multiplayer (o servidor não renderiza nada), mas isso importa na medida em que as máquinas de todos possam jogar.

Portanto, qualquer que seja o idioma que você escolher, tente ficar muito íntimo com os detalhes de implementação / baixo nível, porque mesmo um pequeno detalhe em um projeto como esse pode fazer toda a diferença (um exemplo para mim em C ++ foi "O compilador pode estaticamente inline funcionar?" ponteiros? "Sim, pode! Fez uma diferença incrível em um dos projetos em que eu estava trabalhando, pois tinha menos código e a vantagem de inlining.)

Eu realmente não gosto dessa resposta porque dificulta o design de alto nível, mas é a dolorosa verdade se o desempenho é uma preocupação. Espero que você tenha achado isso útil!

Além disso, a resposta de Gavin cobre alguns detalhes que eu não queria reiterar (e muito mais! Ele é claramente mais conhecedor do assunto do que eu), e eu concordo com ele em sua maior parte. Vou ter que experimentar o comentário dele sobre processadores e tamanhos variáveis ​​mais curtos, nunca ouvi falar disso - gostaria de provar para mim mesmo que é verdade!

O importante é pensar em como você primeiro carregaria os dados. Se você transmitir os dados do mapa para a memória quando necessário, existe um limite natural para o que você pode renderizar, isso já é uma atualização de desempenho da renderização.

O que você faz com esses dados depende de você. Para o desempenho do GFX, você pode usar o Recorte para recortar objetos ocultos, objetos pequenos demais para serem visíveis etc.

Se você está procurando apenas técnicas de desempenho gráfico, tenho certeza de que pode encontrar montanhas de coisas na rede.

Algo para se olhar é o padrão de design Flyweight . Acredito que a maioria das respostas aqui faça referência a esse padrão de design de uma maneira ou de outra.

Embora eu não conheça o método exato que o Minecraft está usando para minimizar a memória de cada tipo de bloco, esse é um caminho possível para o seu jogo. A idéia é ter apenas um objeto, como um objeto de protótipo, que contém informações sobre todos os blocos. A única diferença seria a localização de cada bloco.

Mas mesmo a localização pode ser minimizada: se você sabe que um bloco de terra é de um tipo, por que não armazenar as dimensões dessa terra como um bloco gigante, com um conjunto de dados de localização?

Obviamente, a única maneira de saber é começar a implementar o seu próprio e fazer alguns testes de memória para obter desempenho. Deixe-nos saber como vai!