Armazenando voxels para um mecanismo voxel em C ++

9

Estou tentando escrever um pequeno mecanismo voxel porque é divertido, mas luto para encontrar a melhor maneira de armazenar os voxels reais. Estou ciente de que precisarei de algum tipo de pedaço para não precisar ter o mundo inteiro na memória e estou ciente de que preciso renderizá-lo com desempenho razoável.

Eu li sobre octrees e, pelo que entendi, começa com 1 cubo, e nesse cubo pode haver mais 8 cubos, e em todos esses 8 cubos podem haver outros 8 cubos etc. Mas não acho que isso se encaixe no meu motor voxel porque meus cubos / itens de voxel terão exatamente o mesmo tamanho.

Portanto, outra opção é apenas criar uma matriz de tamanho 16 * 16 * 16 e ter um pedaço, e você a preencherá com itens. E partes onde não existem itens terão 0 como valor (0 = ar). Mas receio que isso desperdice muita memória e não seja muito rápido.

Outra opção é um vetor para cada pedaço e preencha-o com cubos. E o cubo mantém sua posição no bloco. Isso economiza memória (sem bloqueios de ar), mas torna a procura de um cubo em um local específico muito mais lenta.

Portanto, não consigo realmente encontrar uma boa solução, e espero que alguém possa me ajudar com isso. Então, o que você usaria e por quê?

Mas outro problema está sendo processado. Basta ler cada pedaço e enviá-lo para a GPU usando o OpenGL é fácil, mas muito lento. Gerar uma malha por pedaço seria melhor, mas isso significa que toda vez que eu quebro um bloco, tenho que reconstruir o pedaço inteiro, o que pode demorar um pouco, causando um soluço menor, mas perceptível, o que obviamente eu também não quero. Então isso seria mais difícil. Então, como eu renderizaria os cubos? Basta criar todos os cubos em um buffer de vértice por bloco e renderizar isso e talvez tentar colocar isso em outro thread, ou existe outra maneira?

Obrigado!

Clonkex
fonte
11
Você deve usar o instanciamento para renderizar seus cubos. Você pode encontrar um tutorial aqui learnopengl.com/Advanced-OpenGL/Instancing . Para armazenar os cubos: você tem fortes restrições de memória no hardware? 16 ^ 3 cubos não parecem muita memória.
Turms
Obrigado pelo seu comentário! Não tenho fortes restrições de memória, é apenas um PC comum. Mas pensei: se todo pedaço mais alto é de 50% de ar e o mundo é muito grande, então deve haver um pouco de memória desperdiçada. Mas provavelmente não é muito como você diz. Então, devo apenas escolher pedaços de 16 * 16 * 16 com uma quantidade estática de blocos? E também, você diz que eu deveria usar instanciamento, isso é realmente necessário? Minha idéia era gerar uma malha para cada pedaço, porque dessa maneira eu posso deixar de fora todos os triângulos invisíveis.
6
Não recomendo o uso de instanciamento para os cubos, como Turms descreve. Isso reduzirá suas chamadas de empate, mas não fará nada para rostos extraviados e ocultos - na verdade, ele amarra suas mãos para resolver esse problema, pois para instanciar todos os cubos deve ser o mesmo - você não pode excluir faces ocultas de alguns cubos ou mesclar faces coplanares em polígonos únicos maiores.
DMGregory
Escolher o melhor mecanismo de voxel pode ser um desafio. A grande pergunta a ser feita é "que operações eu preciso fazer nos meus voxels?" Isso orienta as operações. Por exemplo, você está preocupado com a dificuldade de descobrir qual é o voxel em uma árvore de outubro. Os algoritmos de out-tree são ótimos para problemas que podem gerar essas informações conforme necessário, à medida que caminha na árvore (geralmente de maneira recursiva). Se você tiver problemas específicos onde isso é muito caro, poderá procurar outras opções.
Cort Ammon
Outra grande questão é a frequência com que os voxels são atualizados. Alguns algoritmos são grandes de dados se eles podem pré-processar para armazená-lo de forma eficiente, mas menos eficiente se os dados são contstantly sendo atualizado (como força de dados em uma partícula com base simulação de fluidos)
Cort Ammon

Respostas:

23

Armazenar os blocos como as posições e os valores é realmente muito ineficiente. Mesmo sem sobrecarga causada pela estrutura ou objeto usado, você precisa armazenar 4 valores distintos por bloco. Só faria sentido usá-lo sobre o método "armazenar blocos em matrizes fixas" (o que você descreveu anteriormente) é quando apenas um quarto dos blocos é sólido e, dessa forma, você nem usa outros métodos de otimização conta.

Octrees são ótimos para jogos baseados em voxel, pois são especializados em armazenar dados com recursos maiores (por exemplo, patches do mesmo bloco). Para ilustrar isso, usei um quadtree (basicamente octrees em 2d):

Este é o meu conjunto inicial contendo blocos de 32 x 32, o que equivale a 1024 valores: insira a descrição da imagem aqui

Armazenar isso como 1024 valores separados não parece ineficiente, mas quando você alcança tamanhos de mapa semelhantes aos jogos, como Terraria , as telas de carregamento levam vários segundos. E se você aumentar para a terceira dimensão, ele começará a consumir todo o espaço do sistema.

Quadríceps (ou octrees em 3d) podem ajudar a situação. Para criar um, você pode ir dos ladrilhos e agrupá-los, ou ir de uma célula enorme e dividi-la até chegar aos ladrilhos. Vou usar a primeira abordagem, porque é mais fácil de visualizar.

Portanto, na primeira iteração, você agrupa tudo em células 2x2 e, se uma célula contém apenas blocos do mesmo tipo, você os solta e armazena o tipo. Após uma iteração, nosso mapa ficará assim:

insira a descrição da imagem aqui

As linhas vermelhas marcam o que armazenamos. Cada quadrado é apenas 1 valor. Isso reduziu o tamanho de 1024 para 439, o que representa uma redução de 57%.

Mas você conhece o mantra . Vamos dar um passo adiante e agrupá-los em células:

insira a descrição da imagem aqui

Isso reduziu a quantidade de valores armazenados para 367. Isso é apenas 36% do tamanho original.

Obviamente, você precisa fazer essa divisão até que cada 4 células adjacentes (8 blocos adjacentes em 3d) dentro de um pedaço seja armazenada dentro de uma célula, convertendo essencialmente um pedaço em uma célula grande.

Isso também tem outros benefícios, principalmente ao fazer colisões, mas convém criar uma octree separada para isso, que só se preocupa se um único bloco é sólido ou não. Dessa forma, em vez de verificar se há colisão em todos os blocos de um bloco, você pode fazer isso contra as células.

Bálint
fonte
Obrigado pela sua resposta! Parece que os octree são o caminho a seguir. (Como meu mecanismo voxel será 3D) Eu tenho algumas perguntas que gostaria de fazer: sua última foto mostra as partes pretas com quadrados maiores, pois pretendo ter um minecraft como motor em que você pode modificar o terreno voxel, eu preferiria manter tudo o que tem um bloco do mesmo tamanho, porque, caso contrário, isso tornaria as coisas muito complicadas, isso é possível, certo? , existe algum tipo de tutorial sobre como programar um octree? Obrigado!
7
@ appmaker1358 isso não é problema. Se o jogador tentar modificar um bloco grande, você o dividirá em blocos menores naquele momento . Não é necessário armazenar valores 16x16x16 de "rock" quando você pode dizer "todo esse pedaço é um rock sólido" até que isso não seja mais verdade.
DMGregory
11
@ appmaker1358 Como o DMGregory disse, atualizar os dados armazenados em um octree é relativamente fácil. Tudo o que você precisa fazer é dividir a célula na qual a alteração ocorreu até que cada subcélula contenha apenas um único tipo de bloco. Aqui está um exemplo interativo com um quadtree . Gerar um também é simples. Você cria uma célula grande, que contém completamente o pedaço, depois percorre recursivamente todas as células foliares (células que não têm filhos), verifica se a parte do terreno que representa contém vários tipos de blocos; se sim, subdivide o cell
Bálint
@ appmaker1358 O problema maior é o inverso - garantir que o octree não fique cheio de folhas com apenas um bloco, o que pode acontecer facilmente em um jogo no estilo Minecraft. No entanto, existem muitas soluções para o problema - trata-se de escolher o que você achar apropriado. E isso só se torna um problema real quando há muita construção acontecendo.
Luaan 21/05/19
Octrees não são necessariamente a melhor escolha. Aqui está uma leitura interessante: 0fps.net/2012/01/14/an-analysis-of-minecraft-like-engines
Polygnome
7

Octrees existem para resolver exatamente o problema que você descreve, permitindo armazenamento denso de dados esparsos sem grandes tempos de pesquisa.

O fato de seus voxels terem o mesmo tamanho significa que a octree tem uma profundidade fixa. por exemplo. para um pedaço de 16x16x16, você precisa de no máximo 5 níveis de árvore:

  • raiz de bloco (16x16x16)
    • octante de primeira camada (8x8x8)
      • octante de segunda camada (4x4x4)
        • octante de terceira camada (2x2x2)
          • voxel único (1x1x1)

Isso significa que você tem no máximo 5 etapas para descobrir se existe um voxel em uma posição específica no bloco:

  • raiz do pedaço: o pedaço inteiro tem o mesmo valor (por exemplo, todo o ar)? Se sim, terminamos. Se não...
    • primeira camada: o octante que contém essa posição tem o mesmo valor? Se não...
      • segundo nível...
        • terceira camada ...
          • agora estamos abordando um único voxel e podemos retornar seu valor.

Muito mais curto do que digitalizar até 1% em uma matriz de até 4096 voxels!

Observe que isso nos permite compactar os dados sempre que houver um octante completo do mesmo valor - seja esse valor todo ar, rocha ou qualquer outra coisa. É apenas onde os octantes contêm valores mistos que precisamos subdividir ainda mais, até o limite dos nós das folhas de voxel único.


Para abordar os filhos de um pedaço, normalmente procederemos na ordem de Morton , algo como isto:

  1. X- Y- Z-
  2. X- Y- Z +
  3. X- Y + Z-
  4. X- Y + Z +
  5. X + Y- Z-
  6. X + Y- Z +
  7. X + Y + Z-
  8. X + Y + Z +

Portanto, nossa navegação no nó Octree pode ser algo como isto:

GetOctreeValue(OctreeNode node, int depth, int3 nodeOrigin, int3 queryPoint) {
    if(node.IsAllOneValue)
        return node.Value;

    int childIndex =  0;
    childIndex += (queryPoint.x > nodeOrigin.x) ? 4 : 0;
    childIndex += (queryPoint.y > nodeOrigin.y) ? 2 : 0;
    childIndex += (queryPoint.z > nodeOrigin.z) ? 1 : 0;

    OctreeNode child = node.GetChild(childIndex);

    return GetOctreeValue(
                child, 
                depth + 1,
                nodeOrigin + childOffset[depth, childIndex],
                queryPoint
    );
}
DMGregory
fonte
Obrigado pela sua resposta! Parece que os octree são o caminho a percorrer. Mas eu tenho duas perguntas, porém, você diz que os octree são mais rápidos do que varrer através de uma matriz, o que é correto. Mas eu não precisaria fazer isso, pois a matriz poderia ser estática, o que significa que posso calcular onde está o cubo. Então, por que eu precisaria digitalizar? Segunda pergunta, na última camada do octree (o 1x1x1), como sei qual cubo é onde, pois se o entendi corretamente e o nó octree possui mais 8 nós, como você sabe qual nó pertence a qual posição 3d ? (Ou eu devo lembrar que eu?)
Sim, você já abordou o caso de uma matriz exaustiva de voxels de 16x16x16 em sua pergunta e pareceu rejeitar o espaço ocupado por memória de 4K por pedaço (assumindo que cada ID de voxel é um byte) como excessivo. A pesquisa que você mencionou ocorre ao armazenar uma lista de voxels com uma posição, forçando-o a percorrer a lista para encontrar o voxel na sua posição de destino. 4096 aqui é o limite superior do comprimento dessa lista - normalmente será menor que isso, mas geralmente ainda mais profundo que uma pesquisa octree correspondente.
DMGregory