Eu estive pensando sobre este problema. É possível com a tecnologia atual criar uma réplica 1: 1 da Terra no jogo baseado em voxel? Qual é a melhor estrutura de dados para armazenar este mapa gigante? Qual algoritmo deve ser usado para renderizar essa estrutura de dados em tempo real?
Essas perguntas fazem as seguintes suposições:
Cada voxel tem uma resolução de 1 metro cúbico.
Por uma questão de simplicidade, cada voxel requer apenas 1 byte de informações de metadados. Esta informação será usada para armazenar a identificação do "tipo" do voxel (terra, água, rocha, etc).
O volume terrestre é de 1 * 10ˆ21 metros cúbicos.
Por "tecnologia atual", incluo qualquer coisa que esteja comercialmente disponível, mas não supercomputadores.
Somente a topografia da Terra e a batimetria serão usadas para gerar o mapa. Construção humana, plantas ou cavernas são excluídas. Os blocos subterrâneos serão escolhidos com base em estudos geológicos, por exemplo: se a profundidade for maior que 3000 km, render um voxel de 'magma'.
Assim como no Minecraft, o mapa não é estático, pode ser modificado no jogo.
Uma distância de desenho 'infinita' é uma grande vantagem, qual é o sentido de ter toda a Terra em um mapa se você não pode voar e observar o planeta inteiro?
A primeira conclusão que cheguei quando pensei sobre esse problema é que armazenar os dados da Terra de maneira linear é inviável, supondo que cada voxel ocupe apenas 1 byte de memória, isso ainda exigiria 1 zettabyte para armazenar o mapa. Portanto, é necessário algum tipo de compactação.
Penso que um voxel octree poderia comprimir o mapa, mas não tenho a certeza quanto. A entropia deste mapa de voxel é provavelmente muito baixa, então acho que pode ser alcançado um nível muito alto de compressão.
aviso Legal
Esta é uma questão teórica, não tenho intenções de escrever uma terra voxel
EDITAR
O ESA GOCE já mapeou o geóide da Terra com uma precisão de 1 cm a 2 cm. Acredito que esta informação possa ser usada para gerar um mapa de altura muito preciso da Terra. Isso excluiria a necessidade de usar um algoritmo para preencher lacunas na topografia da Terra.
fonte
Respostas:
Isso depende do método de subdivisão espacial que você usa, embora todos os métodos de subdivisão (como qualquer método de compactação) acabem se desenvolvendo onde nenhuma compactação adicional pode ocorrer, devido às despesas gerais da estrutura de dados e outros fatores lógicos / matemáticos. Um exemplo pode ser encontrado em octrees. Para cada nó na octree, um ponteiro deve ser mantido para seu pai e / ou filhos (dependendo de como você executa a arquitetura da estrutura de dados), para permitir uma travessia significativa. Qualquer estrutura de árvore pode conter n filhos. Quanto menor a proporção 1: n, o uso mais eficiente do espaço que você ganha e, consequentemente, maiores as despesas gerais no deslocamento de árvores, pois você deve ter mais nós ancestrais para conter o mesmo número de voxels de folhas (no seu caso, aproximadamente 510 trilhões) destes representando a área da superfície).
Considerando que, no seu caso, os principais problemas são o custo de armazenamento e a renderização de todo o planeta (ou partes dele) a uma distância justa, não há uma estrutura de dados que eu recomendaria em uma octree. O mipmapping é uma necessidade: 12,8 milhões de metros de diâmetro na potência mais alta mais próxima de 2 é 2 ^ 24 = 16,8 milhões. O deslocamento de 24 níveis de octree equivaleria a uma quantidade enorme de ramificações - muito caro para GPUs e CPUs. Mas desde que você faça as coisas certas, você só precisará atravessar alguns níveis de cada vez. Dada a quantidade de espaço necessária, porém, as alternativas são poucas e distantes (veja abaixo).
Os recursos de mipmapping dos octrees são o que o torna uma ferramenta incrivelmente poderosa para grandes volumes, como você descreve. Diferente de todos os outros métodos de subdivisão conhecidos (com exceção das árvores KD), a octree mantém a subdivisão por nível mínima, o que significa que as diferenças visuais e físicas entre os níveis do mipmap também são mínimas, o que significa deltas muito mais finos na granularidade à medida que você caminha e sobe. abaixo da árvore.
Se, por outro lado, você deseja gerar um mundo em que a passagem hierárquica da grade é mantida no mínimo, precisará trocar espaço para aumentar a velocidade.
Falando da proporção ideal de 1: n, não existe uma estrutura mais refinada do que a árvore kd a esse respeito. Onde a octree se divide em 2 para cada eixo, resultando em 2 ^ 3 = 8 células filho individuais, a árvore kd se divide exatamente uma vez por nível de subdivisão. O problema é que você deve escolher um hiperplano para dividir, e esse hiperplano pode ser escolhido em qualquer um dos três eixos. Embora seja ideal em termos de espaço, torna as travessias 3D (como durante raymarches, uma operação fundamental ao usar octrees para física ou renderização) muito mais difíceis do que em uma octree, uma vez que uma estrutura dinâmica de portal deve ser mantida para registrar interfaces entre nós individuais da árvore kd.
O RLE é outra abordagem da compactação, mas é, de muitas maneiras, mais difícil de aplicar a um problema como este (onde a base de operações é esférica), pois a compactação do RLE é unidimensional e você deve escolher o eixo em que opera. planeta, pode-se escolher o eixo polar, mas qualquer opção de eixo único introduziria certos problemas nas travessias para renderização e física ao atuar a partir de determinados ângulos não ideais. Obviamente, você também pode executar o RLE em 3 eixos simultaneamente, triplicando o custo de armazenamento ou em 6 eixos (-x, + x, -y, + y, -z, + z) como uma otimização adicional.
Então, para responder à sua pergunta (ou não!)
Não vou responder diretamente a que tipo de hardware, mas acho que olhar de uma perspectiva octree começa a dar uma idéia do que é de fato possível em que tipo de hardware. Gostaria de encorajá-lo a seguir esse caminho. Se você realmente quiser saber, talvez seja mais fácil implementar uma simples octree esparsa(veja o artigo de Laine nas referências) e coloque uma casca esférica de voxels de superfície nele e veja como é o uso resultante do espaço. Intensifique a partir daí. Veja até onde você pode chegar antes que a memória do sistema comece a se esgotar. Isso não exige que você escreva um renderizador, a menos que deseje visualização. Lembre-se também de que isso é melhor feito na CPU - as GPUs, em geral, não têm capacidade de memória para lidar com problemas dessa escala. Essa é uma das razões pelas quais a Intel está buscando avançar para processadores massivamente paralelos: os benefícios da GPGPU, que é melhor nesse tipo de coisa, podem ser aplicados a um espaço de memória muito mais vasto, sem gargalos no barramento do sistema. Provavelmente existem outros aqui, ou em mathematics.stackexchange.com,
Em termos de seu requisito de distância de visualização infinita, claro, mas a questão sempre se resume a "quantos detalhes a que distância". A renderização de detalhes infinitos exigiria recursos infinitos. É aí que entra em cena o mipmap de variável por cena. Também tenha em mente que todas as estruturas de dados incorporam alguma troca de velocidade por espaço ou vice-versa. Isso significa renderização menos / mais lenta, se você deseja um mundo maior para a mesma quantidade de esforço de engenharia.
fonte
Como é provável que você nunca descubra as propriedades de cada metro cúbico do mundo real, precisará de alguma maneira de gerar dados incertos com base em suposições. Portanto, se você já descobriu isso, não há necessidade de calcular e armazenar todos esses dados, mas é possível gerá-los em tempo real.
Primeiro e acima de tudo, você pode descartar todos os voxels da Terra, porque eles só precisam ser calculados se alguém realmente cavar um buraco, por exemplo. os voxels se tornam visíveis.
Para a superfície da Terra, eu provavelmente tiraria uma imagem como ponto de partida para meus cálculos. Talvez algum tipo de mapa de temperatura e umidade permita calcular o tipo de bloco a ser aplicado. Por exemplo. Água, areia (deserto), grama, neve etc. Como a imagem provavelmente não terá um pixel de informação para cada metro quadrado da superfície terrestre, você precisará misturar isso com algum ruído para gerar um pouco de variação a superfície. Se você sempre usa as mesmas sementes aleatórias, seu resultado deve ser determinístico.
Além disso, um mapa de elevação seria útil, para que você possa determinar a altura dos recursos da superfície. Dessa forma, você pode adicionar montanhas, etc.
Portanto, isso se resume a um volume de dados de algumas imagens 2D que contêm informações sobre a superfície da Terra. Para tudo o que está por dentro, você reverteria para uma abordagem processual pura, onde renderizar diferentes tipos de blocos, dependendo da distância do centro da terra. Mas, como dito acima, estes devem ser calculados apenas quando alguém cavar um buraco.
Para tornar as alterações persistentes, eu salvaria apenas as modificações no mundo. Portanto, se alguém cavar um buraco, eu armazenaria informações sobre quais voxels foram removidos, pois eu seria capaz de processar os voxels ao redor processualmente.
Quanto à renderização: você precisará de algoritmos sofisticados de nível de detalhe e seleção para fazer isso funcionar. É bobagem renderizar todos os voxels de superfície, quando a câmera está no nível de zoom que mostra o mundo inteiro. Nesse nível, os voxels devem ser muito maiores, talvez até uma simples esfera texturizada seja suficiente.
Eu acho que o mais complicado seria ter um gerador sólido que permita calcular as propriedades do voxel, mesmo para diferentes "resoluções", para que você possa usá-lo para gerar diferentes níveis de detalhes.
fonte
Você pode basicamente fazer a mesma coisa que o Minecraft. Em vez de criar essa quantidade de dados, você pode definir um mundo como uma fórmula matemática, sempre que um dado é necessário para exibição, você o gera usando a fórmula.
Essa fórmula geralmente é construída usando o conceito de ruído Perlin ; isso permite detalhes em todos os níveis, você pode ter montanhas tão grandes quanto as do mundo real, mas optar por gerar apenas uma pequena parte delas. Você pode gerar a quantidade de detalhes que desejar, para que seja possível fazer detalhes muito finos para coisas próximas, mas também gerar cenários distantes no nível de detalhe necessário.
O Minecraft salva todos os blocos que você visitou, com todas as alterações feitas, pode-se simplesmente salvar apenas a diferença entre o mundo gerado e o mundo atualizado, mas acho que salvar blocos grandes foi mais fácil e eles se compactam relativamente bem.
Eu não acho que exista algum jogo que realmente leve isso ao limite, mas é muito comum usar a geração de fórmula de todos os detalhes "sem importância" dos grandes mundos de jogos. Não tenho certeza de quão comum é a abordagem de gerar quando necessário, em vez de simplesmente gerar o lote e colocá-lo no disco.
fonte
Você pode procurar dados vetoriais das massas terrestres da Terra, pois os dados vetoriais têm a vantagem de escalar para qualquer escala desejada. Combine-o com um mapa de altura da Terra para gerar a altura do terreno. O último passo é algumas imagens de satélite detalhadas, de onde você pode escolher o tipo do bloco superior com base na imagem, para obter rochas onde há rochas, areia onde há areia etc. O interior real do planeta provavelmente deve ser gerado como o Minecraft, a menos que você possa encontrar dados geográficos detalhados para trabalhar. Basicamente, o que você deseja fazer é encontrar dados geográficos e extrapolar a partir deles, considerando apenas a entrada de coordenadas XYZ. Isso significa que você tem dados limitados e extrapola o restante da maneira mais precisa possível.
fonte