c++ – Consulta Octree – Pesquisa Frustum e Inserções de Vetor Recursivo

Apresentação

Passei provavelmente o último ano pensando em implementar uma estrutura de dados Octree no meu projeto de mecanismo de jogo C++ para gerenciamento de cena e seleção de frustum de luzes e malhas. No momento, meu objetivo é superar o desempenho da minha atual abordagem iterativa de força bruta para testes de frustum de cada luz e malha na cena.

Finalmente decidi atacar isso de frente e, na semana passada, implementei uma classe Octree com modelo que me permite armazenar dados dentro da minha octree, como UUID (uint32_t no meu caso). Também planejo poder redirecionar essa estrutura para outros recursos no mecanismo de jogo, mas, por enquanto, o frustum culling é meu objetivo principal para este sistema.

Agora, vamos ao que interessa: tenho um problema de desempenho com std::vector::insert() e a natureza recursiva do meu design atual.

Estrutura

1. Octreeesta é a classe base que gerencia todas as chamadas de API do usuário, como inserir, remover, atualizar, consultar (AABB, Sphere ou Frustum), and so on. Quando crio o Octree, o construtor pega uma estrutura OctreeConfig que contém informações básicas sobre quais propriedades o Octree deve pegar, por exemplo, MinNodeSize, PreferredMaxDataSourcesPerNode, and so on.
2. OctreeDataSourceesta é uma estrutura simples que contém uma caixa delimitadora AABB que representa os dados no espaço 3D, e o valor do DataType, por exemplo, um UUID. Eu planejo estender isso também para que eu possa ter esferas delimitadoras ou pontos para os tipos de dados também.
3. OctreeNodeesta é uma estrutura privada dentro da classe Octree, pois não quero que o usuário acesse os nós diretamente; no entanto, cada nó tem um std::array, 8> para seus filhos, e também detém um std::vector<:shared_ptr>>> que contém um vetor de ponteiros inteligentes para a fonte de dados.

Problema

Meu problema atual é o impacto no desempenho de std::vector::insert() que é chamado recursivamente através do OctreeNode quando eu chamo meu método Octree::Question(CameraFrustum).

Conforme visto acima na minha estrutura, cada OctreeNode contém um std::vector de fontes de dados e quando eu consulto o Octree, ele insere todos esses vetores em um único vetor pré-alocado que é passado para o Octree por referência.

Quando consulto o Octree, ele executa as seguintes etapas básicas:

Método de consulta

1. Octree::Consulta
   1. Crie um estático std::vector e garantir que na criação ele tenha reservado espaço para a consulta (atualmente estou apenas codificando isso para 1024, pois isso contém suficientemente todos os objetos de malha em minha cena de teste octree atual, então não há realocações ao executar uma std::vector inserção de intervalo).
   2. Limpe o vetor estático.
   3. Chamar OctreeNode::Question e passar o vetor como referência.
2. OctreeNode::Consulta
   1. Verifique a contagem de fontes de dados no nó atual e seus filhos. Se não tivermos fontes de dados neste nó e seus filhos, retornaremos – simples
   2. Notice uma verificação de frustum nos limites AABB do nó atual. O resultado é Comprises, Intersects ou DoesNotContain.
      • Contém: (IMPACTO NO DESEMPENHO AQUI) Se o nó atual estiver totalmente contido dentro do frustum, simplesmente incluiremos todos os DataSources na consulta do nó atual e de todos os nós filhos recursivamente. Chamamos OctreeNode::GatherAllDataSourcese passe o vetor estático criado em Octree::Question() por referência.
      • Intersecções: Nós verificamos individualmente cada frustum OctreeDataSource::AABB dentro do vetor de fonte de dados deste nó, então chamamos recursivamente OctreeNode::Question em cada uma das crianças para executar esta função recursivamente.

OctreeNode::GatherAllDataSources (o filho problemático)

Eu usei macros de criação de perfil para medir a quantidade acumulada de tempo que essa função leva em cada quadro. Se eu chamar Question uma vez no meu loop de jogo do mecanismo principal, o GatherAllDataSources() leva aproximadamente 60%, se não mais, do tempo inteiro do método Question.

Você também pode ver nesses resultados de perfil que a Consulta Octree está levando o dobro do tempo que “Ahead Plus – Frustum Culling (MESHES)”, que é a abordagem de força bruta para verificação de frustum em cada malha dentro da cena (a cena tem 948 malhas com AABBs).

Reduzi o problema à linha de código com o comentário abaixo:

void GatherAllDataSources(std::vector& out_data) {
    
    L_PROFILE_SCOPE_ACCUMULATIVE_TIMER("Octree Question - GatherAllDataSources"); // Accumulates a profile timer outcomes every time this technique known as. Profiler begins time on development and stops timer and accumulates consequence inside a ProfilerResults class.
    if (Rely() == 0) {
        CheckShouldDeleteNode();
        return;
    }

    if (!m_DataSources.empty()) {
        // That is the road of code which is taking a lot of the queries search time
        // As you'll be able to see under aswell, the time complexity will increase as a result of 
        // I'm calling this perform recursively for all kids, virtually, 
        // gathering all information sources inside this node and all kids
        out_data.insert(out_data.finish(), m_DataSources.start(), m_DataSources.finish()); 
    }               

    if (!IsNodeSplit()) 
        return;
        
    // Recursively collect information from little one nodes
    for (const auto& little one : m_ChildrenNodes) {
        if (little one) {
            child->GatherAllDataSources(out_data); // Go the identical vector to keep away from reminiscence allocations
        }
    }       
}

Hora das perguntas

Como posso melhorar significativamente a eficiência da coleta recursiva de fontes de dados dos meus nós filhos?

Estou aberto a mudar completamente a abordagem de como as fontes de dados são armazenadas no Octree e como a estrutura geral do Octree é projetada, mas é aqui que fico preso.

Sou muito inexperiente quando se trata de otimização de algoritmos ou otimização de C++ e, como esse é um novo algoritmo que tentei implementar, estou achando muito difícil encontrar uma solução para esse problema.

Qualquer dica/truque é bem-vindo!

Você pode encontrar a versão completa do meu código de implementação atual do Octree aqui (observe que ainda não terminei com outras funcionalidades e provavelmente retornarei se não encontrar soluções para a otimização de Inserir e Remover!).

Aqui estão alguns recursos que analisei:

Se você também estiver interessado no restante da minha base de código, ela pode ser encontrada no GitHub através de este hyperlink. Eu opero principalmente no ramo de Desenvolvimento. Essas mudanças ainda não foram enviadas, mas enfrentei muitos desafios durante a jornada deste projeto, então se você tiver mais insights sobre meu código ou tiver alguma dúvida sobre como implementei diferentes recursos, por favor, me avise!