Construindo um Octree para geração de terrenos

9

Eu já implementei cubos de marchas / tetraedros para renderizar um IsoSurface. Funcionou ( YouTube ), mas o desempenho foi péssimo, pois nunca consegui implementar o Nível de detalhe variável com base na distância da visualização (ou mesmo remover pedaços antigos e distantes).

Decidi tentar outra vez e fazê-lo corretamente desta vez. Comecei criando um OctreeNode que funciona da seguinte maneira quando Build()é chamado.

  • Se o pedaço for muito pequeno para ser construído, retorne imediatamente.
  • Calcule se a superfície passa pelo volume desse pedaço.
  • Nesse caso, decida se queremos aumentar o LOD (porque a câmera está próxima)
  • Nesse caso, crie 8 filhos e chame o mesmo processo para eles
  • Caso contrário, construa a malha usando as dimensões do nó atual

Algum PseudoCode:

OctNode Build() {
    if(this.ChunkSize < minChunkSize) {
        return null;
    }
    densityRange = densitySource¹.GetDensityRange(this.bounds);
    if(densityRange.min < surface < densityRange.max) {
        if(loDProvider.DesiredLod(bounds > currentLoD) {
            for(i 1 to 8) {
                if(children[i] == null) {
                    children[i] = new OctNode(...)
                }
                children[i] = children[i].Build();
            }
        } else {
            BuildMesh();
        }
        return this;
    }
}

¹ Além de retornar a densidade em um ponto, a fonte de densidade pode determinar a faixa de densidade possível para um determinado volume.

² O provedor LoD pega uma caixa delimitadora e retorna o LoD máximo desejado com base na posição da câmera / perfil, configurações do usuário, etc.

Então ... Tudo isso funciona muito bem. Usando uma esfera simples como fonte de densidade e mostrando todos os nós:

Octree completo

E apenas as folhas:

Octree mostrando apenas folhas

No entanto, existem alguns problemas:

  • Eu tenho que definir o volume inicial delimitador (e quanto maior, mais processamento eu preciso fazer)
  • Na raiz da árvore, não tenho idéia de quão profundas serão as folhas, então minha numeração LoD começa na menor qualidade (raiz) e aumenta à medida que os pedaços ficam menores. Como o LoD agora é relativo ao volume inicial, não é muito útil quando quero fazer coisas em tamanhos / qualidades específicos.

Pensei em algumas opções, mas ambas parecem falhas:

  • Mantenha uma coleção de Octrees e adicione / remova dependendo da distância. Não consigo ver como eu faria a malha bem¹, além de precisar de uma lista de nós vazios conhecidos, especialmente se eu quiser superfícies 3D arbitrárias (para evitar recalcular volumes vazios repetidamente)
  • Adicione um nó pai à raiz atual e adicione sete irmãos para o nó original. Isso funcionaria e seria sob demanda, mas parece complexo recuar sensivelmente à medida que o jogador se move pela paisagem. Isso também tornaria os números LoD ainda menos significativos.

In [Para esclarecer Q abaixo] No momento, se 2 nós fisicamente adjacentes na árvore estiverem em LODs diferentes, eu tenho algum código para coagir os verts de modo que não haja costura quando as malhas são geradas. Sou capaz de fazer isso conhecendo a densidade de vários nós circundantes. Em um cenário em que eu tenho 2 octrees independentes lado a lado, eu não teria uma maneira fácil de recuperar essas informações, resultando em costuras.

Qual é a melhor maneira de abordar isso?

Basic
fonte

Respostas:

1

Não tenho certeza se estou respondendo à pergunta exata, por isso vou responder em segmentos e fique à vontade para responder nos comentários se houver um mal-entendido sobre os detalhes de uma pergunta específica.

Eu tenho que definir o volume inicial delimitador (e quanto maior, mais processamento eu preciso fazer)

Isso não parece ser o caso. Como o octree aumenta exponencialmente a granularidade, adicionar alguns níveis no topo deve ser um aumento líquido muito pequeno no impacto no desempenho.

Na raiz da árvore, não tenho idéia de quão profundas serão as folhas, então minha numeração LoD começa na menor qualidade (raiz) e aumenta à medida que os pedaços ficam menores. Como o LoD agora é relativo ao volume inicial, não é muito útil quando quero fazer coisas em tamanhos / qualidades específicos.

Se você corrigir o octree raiz com algum "valor suficientemente grande", "LoD em relação ao volume inicial" não deve ser um problema. E, como mencionado acima, não acho que ter um nível extra no topo tenha impacto no desempenho geral.

Mantenha uma coleção de Octrees e adicione / remova dependendo da distância. Não consigo ver como seria a malha entre mim, além de precisar de uma lista de nós vazios conhecidos, especialmente se eu quiser superfícies 3D arbitrárias (para evitar recalcular os volumes vazios repetidamente)

Pelo que entendi, esta solução proposta é reduzir o LoD ao se afastar de uma área anteriormente detalhada. Eu acho que deve parecer muito semelhante ao caminho do código "crescente LoD":

if (loDProvider.DesiredLod(bounds) <(is a lot less than)< currentLoD) { 
    for(i = 1 to 8) { 
        children[i].Destroy();
    }
    BuildMesh();
}

Então, você não está gastando muito mais tempo verificando nós distantes porque você pode contar com o fato de que enquanto longe, não há também muitos nós "activos", uma vez que todos os nós de alta resolução terá sido removido.


Supondo que os pequenos nós sejam em escala de rocha, isso significaria potencialmente dezenas, senão centenas, de níveis, enquanto viajo por um continente

Penso que a escala logarítmica do octree ainda o torna viável. Se o seu nível superior tiver 1.000.000.000.000 de largura (isso seria 25 vezes maior que a Terra real e com 625x a área da superfície) e os bits de nível mais baixo terão 10 cm de diâmetro, são 32 níveis no octree, o que é provavelmente gerenciável o suficiente. Se você queria um planeta 100 vezes mais largo que a Terra (e com 10.000 vezes mais área de superfície), isso representa apenas 3-4 níveis adicionais em sua octree. Nesse ponto, um jogador levaria centenas de anos para percorrer o mundo e, se você usar matemática ingênua de ponto flutuante, o mundo estará acumulando erros de precisão.

Mantenha uma coleção de Octrees e adicione / remova dependendo da distância. Não consigo ver como eu faria a malha bem¹, além de precisar de uma lista de nós vazios conhecidos, especialmente se eu quiser superfícies 3D arbitrárias (para evitar recalcular volumes vazios repetidamente)

Isso não é fundamentalmente equivalente a ter o octree de bilhões de quilômetros de largura, mas manter uma lista de indicadores para cada bloco, digamos, de 1 km? Então, "meshing across" seria simplesmente contar com os nós do tamanho de 2 km. Manter uma referência local para cada "bloco grande" de nível médio também impede que você precise percorrer os nós de nível superior, se você estiver preocupado com as "possivelmente dezenas de níveis adicionais de octree"

Jimmy
fonte
Obrigado por responder. Não posso simplesmente escolher um volume inicial massivo, pois meu terreno é infinito (esse é meu objetivo). Assista ao vídeo para ter uma ideia. Como tal, minha árvore de nós ficaria cada vez mais alta. Supondo que os pequenos nós tenham uma escala de rocha, isso significaria potencialmente dezenas, senão centenas, de níveis, enquanto viajo por um continente. Re: Meshing across, deixe-me adicionar mais alguns detalhes à pergunta [Concluído]
Básico
no que diz respeito ao jogador, "um bilhão de milhas" é bem próximo de "infinito". Mais argumentos para um volume inicial fixo adicionado à resposta.
7137 Jimmy
Ainda não estou convencido. Por que ter mais de 30 camadas de processamento inútil conhecido? Não é elegante, muito menos eficiente. Entendo o seu ponto de tempo para atravessar, mas estamos simplesmente falando sobre a geração de terrenos. Nada que diga que eu tenho que me centrar na origem, nem que voar em alta velocidade seja impossível (embora eu não estivesse fazendo mal a essa velocidade!). FWIW Estou usando dobros internamente para evitar esse problema de precisão.
Básico