Como posso implementar iluminação baseada em voxel com oclusão em um jogo no estilo Minecraft?

13

Estou usando C # e XNA. Meu algoritmo atual para iluminação é um método recursivo. No entanto, é caro , a ponto de um pedaço de 8x128x8 ser calculado a cada 5 segundos.

  • Existem outros métodos de iluminação que produzem sombras de escuridão variável?
  • Ou o método recursivo é bom e talvez eu esteja fazendo errado?

Parece que o material recursivo é fundamentalmente caro (forçado a percorrer cerca de 25 mil blocos por bloco). Eu estava pensando em usar um método semelhante ao traçado de raios, mas não tenho idéia de como isso funcionaria. Outra coisa que tentei foi armazenar fontes de luz em uma lista e, para cada bloco, obter a distância de cada fonte de luz e usá-la para iluminá-la no nível correto, mas a iluminação atravessaria as paredes.

Meu código de recursão atual está abaixo. Isso é chamado de qualquer lugar no pedaço que não tenha um nível de luz zero, depois de limpar e adicionar novamente a luz solar e a lanterna.

world.get___até uma função que pode obter blocos fora desse bloco (isso é dentro da classe de bloco). Locationé minha própria estrutura que é como a Vector3, mas usa números inteiros em vez de valores de ponto flutuante. light[,,]é o mapa de luz do pedaço.

    private void recursiveLight(int x, int y, int z, byte lightLevel)
    {
        Location loc = new Location(x + chunkx * 8, y, z + chunky * 8);
        if (world.getBlockAt(loc).BlockData.isSolid)
            return;
        lightLevel--;
        if (world.getLightAt(loc) >= lightLevel || lightLevel <= 0)
            return;
        if (y < 0 || y > 127 || x < -8 || x > 16 || z < -8 || z > 16)
            return;
        if (x >= 0 && x < 8 && z >= 0 && z < 8)
            light[x, y, z] = lightLevel;

        recursiveLight(x + 1, y, z, lightLevel);
        recursiveLight(x - 1, y, z, lightLevel);
        recursiveLight(x, y + 1, z, lightLevel);
        recursiveLight(x, y - 1, z, lightLevel);
        recursiveLight(x, y, z + 1, lightLevel);
        recursiveLight(x, y, z - 1, lightLevel);
    }

fonte
1
Algo está terrivelmente errado se você estiver fazendo 2 milhões de blocos por bloco - especialmente porque existem apenas 8.192 blocos em um bloco 8 * 128 * 8. O que você poderia estar fazendo para passar por cada bloco ~ 244 vezes? (que poderia ser 255?)
doppelgreener
1
Eu fiz minhas contas erradas. Desculpe: P. Mudando. Mas a razão pela qual você precisa ir embora é que você precisa sair de cada bloco até atingir um nível de luz maior que o seu. Isso significa que cada bloco pode ser substituído de 5 a 10 vezes antes de atingir o nível de luz real. 8x8x128x5 = muito
2
Como você está armazenando seus Voxels? Isso é importante para reduzir os tempos de travessia.
Samaursa 31/10/11
1
Você pode postar seu algoritmo de iluminação? (você perguntar se você está fazendo isso mal, não temos idéia)
doppelgreener
Estou armazenando-os em uma matriz de "Blocos", e um Bloco consiste em uma enumeração para material, além de um byte de metadados para uso futuro.

Respostas:

6
  1. Toda luz possui uma posição precisa (ponto flutuante) e uma esfera delimitadora definida por um valor de raio de luz escalar LR,.
  2. Todo voxel tem uma posição precisa (ponto flutuante) no centro, que você pode calcular facilmente a partir da sua posição na grade.
  3. Execute cada um dos 8192 voxels apenas uma vez e, para cada um, veja se ele cai dentro de cada um dos volumes esféricos das luzes N |VP - LP| < LR, verificando onde VP é o vetor de posição do voxel em relação à origem e LPo vetor de posição da luz em relação à origem. Para cada luz em que raio se encontra o voxel atual, aumente seu fator de luz pela distância do centro de luz |VP - LP|,. Se você normalizar esse vetor e, em seguida, obtiver sua magnitude, isso estará no intervalo 0,0-> 1,0. O nível máximo de luz que um voxel pode atingir é 1,0.

O tempo de execução é O(s^3 * n): onde sestá o comprimento lateral (128) da região do voxel e o nnúmero de fontes de luz. Se suas fontes de luz são estáticas, isso não é problema. Se suas fontes de luz se moverem em tempo real, você poderá trabalhar apenas em deltas, em vez de recalcular todo o conteúdo de cada atualização.

Você pode até armazenar os voxels que cada luz afeta, como referências dentro dessa luz. Dessa forma, quando a luz se move ou é destruída, você pode percorrer apenas essa lista, ajustando os valores da luz de acordo com as especificações, em vez de precisar percorrer toda a grade cúbica novamente.

Engenheiro
fonte
Se eu entendi seu algoritmo corretamente, ele tenta fazer algum tipo de pseudo-radiosidade, permitindo que a luz alcance lugares distantes, mesmo que isso signifique que ela precisa "contornar" alguns cantos. Ou, em outras palavras, um algoritmo de preenchimento de inundação dos espaços "vazios" (não sólidos) com uma distância máxima limitada da origem (a fonte de luz) e a distância (e dela, a atenuação da luz) sendo calculada de acordo com o caminho mais curto para a origem. Então - não exatamente o que você propõe atualmente.
Martin Sojka
Obrigado pelo detalhe @MartinSojka. Sim, parece mais um preenchimento inteligente. Com qualquer tentativa de iluminação global, os custos tendem a ser altos, mesmo com otimizações inteligentes. Portanto, é bom tentar primeiro esses problemas em 2D e, se eles forem remotamente caros, saiba que você terá um desafio definido em suas mãos em 3D.
Engenheiro de
4

O próprio Minecraft não faz a luz do sol dessa maneira.

Você simplesmente preenche a luz do sol de cima para baixo, cada camada está captando a luz dos voxels vizinhos na camada anterior com atenuação. Muito rápido - passe único, sem listas, sem estruturas de dados, sem recursão.

Você precisa adicionar tochas e outras luzes que não inundam em um passe posterior.

Existem muitas outras maneiras de fazer isso, incluindo a sofisticada propagação de luz direcional etc., mas elas são obviamente mais lentas e você precisa descobrir se deseja investir no realismo adicional, considerando essas penalidades.

Bjorn Wesen
fonte
Espere, então como exatamente o Minecraft faz isso? Não consegui entender exatamente o que você estava dizendo ... O que significa "cada camada está captando luz dos voxels vizinhos na camada anterior com atenuação" significa?
2
Comece com a camada superior (fatia de altura constante). Encha com luz solar. Em seguida, vá para a camada abaixo, e todo voxel lá obtém sua iluminação dos voxels mais próximos da camada anterior (acima dela). Coloque zero luz em voxels sólidos. Você tem algumas maneiras de decidir o "kernel", o peso das contribuições dos voxels acima, o Minecraft usa o valor máximo encontrado, mas o diminui em 1 se a propagação não for direta. Essa é a atenuação lateral, para que colunas verticais desbloqueadas de voxels obtenham a propagação total da luz do sol e a luz se incline nos cantos.
Bjorn Wesen
1
Observe que esse método não se baseia em nenhuma física real :) O principal problema é que você está basicamente tentando aproximar uma luz não direcional (a dispersão atmosférica) E a radiosidade refletida com uma heurística simples. Parece muito bom.
Bjorn Wesen
3
Que tal um "lábio" que paira sobre como a luz chega lá em cima? Como a luz viaja para cima? Quando você apenas desce, não pode voltar para cima para preencher as saliências. Também tochas / outras fontes de luz. Como você faria isso? (eles só poderia ir para baixo!)
1
@ Coração: foi um tempo agora que eu olhei para isso, mas em essência há um nível de luz ambiente mínimo que geralmente é suficiente para a parte de baixo das saliências, para que elas não fiquem completamente pretas. Quando eu implementei isso, adicionei uma segunda passagem de baixo para cima, mas realmente não vi grandes melhorias estéticas em comparação com o método ambiental. Tochas / luzes pontuais devem ser manuseadas separadamente - acho que você pode ver o padrão de propagação usado no MC se colocar uma tocha no meio de uma parede e experimentar um pouco. Nos meus testes, eu os propago em um campo de luz separado e depois adiciono.
Bjorn Wesen
3

Alguém disse para responder sua própria pergunta, se você entendeu, então sim. Descobri um método.

O que estou fazendo é o seguinte: primeiro, crie uma matriz booleana 3d de "blocos já alterados" sobrepostos sobre o bloco. Em seguida, preencha a luz do sol, a luz de tochas, etc. (apenas acenda o bloco em que está ligado, sem enchente ainda). Se você mudou alguma coisa, pressione os "blocos alterados" nesse local como true. Além disso, vá e altere todos os blocos sólidos (e, portanto, não é necessário calcular a iluminação) para "já alterados".

Agora, para as coisas pesadas: passe por todo o pedaço com 16 passes (para cada nível de luz) e, se o 'já mudou', continue. Em seguida, obtenha o nível de luz dos blocos ao seu redor. Obtenha o nível mais alto de luz deles. Se esse nível de luz for igual ao nível de luz dos passes atuais, defina o bloco em que você está no nível atual e defina "já alterado" para esse local como verdadeiro. Continuar.

Eu sei que é meio complicado, tentei explicar o meu melhor. Mas o fato importante é que funciona e é rápido.


fonte
2

Eu sugeriria um algoritmo que meio que combina sua solução de múltiplas passagens com o método recursivo original e é provavelmente um pouco mais rápido do que qualquer um deles.

Você precisará de 16 listas (ou qualquer tipo de coleção) de blocos, um para cada nível de luz. (Na verdade, existem maneiras de otimizar esse algoritmo para usar menos listas, mas é mais fácil descrevê-lo.)

Primeiro, limpe as listas e defina o nível de luz de todos os blocos como zero e, em seguida, inicialize as fontes de luz como na sua solução atual. Depois (ou durante) disso, adicione todos os blocos com um nível de luz diferente de zero à lista correspondente.

Agora, percorra a lista de blocos com nível de luz 16. Se algum dos blocos adjacentes a eles tiver um nível de luz menor que 15, defina seu nível de luz como 15 e adicione-os à lista apropriada. (Se eles já estavam em outra lista, você pode removê-los, mas não faz mal, mesmo que não o faça.)

Repita o mesmo para todas as outras listas, em ordem decrescente de brilho. Se você achar que um bloco na lista já tem um nível de luz mais alto do que deveria por estar nessa lista, você pode assumir que ele já foi processado e nem se deu ao trabalho de verificar seus vizinhos. (Por outro lado, pode ser mais rápido verificar os vizinhos - depende da frequência com que isso acontece. Você provavelmente deve tentar os dois lados e ver qual é o caminho mais rápido.)

Você pode observar que não especifiquei como as listas devem ser armazenadas; realmente qualquer implementação razoável deveria fazer isso, desde que inserir um determinado bloco e extrair um bloco arbitrário sejam operações rápidas. Uma lista vinculada deve funcionar, mas também qualquer implementação decente de matrizes de comprimento variável. Basta usar o que for melhor para você.


Termo aditivo: se a maioria das luzes não se mover com muita frequência (e nem as paredes), pode ser ainda mais rápido armazenar, para cada bloco aceso, um ponteiro para a fonte de luz que determina seu nível de luz (ou para um dos eles, se vários estiverem ligados). Dessa forma, você pode evitar atualizações quase inteiramente da iluminação global: se uma nova fonte de luz for adicionada (ou uma já existente iluminada), você precisará fazer apenas uma única passagem de iluminação recursiva para os blocos ao redor, enquanto se uma for removida (ou esmaecido), você só precisa atualizar os blocos que apontam para ele.

Você pode até lidar com mudanças de parede desta maneira: quando uma parede for removida, basta iniciar um novo passe de iluminação recursiva nesse bloco; quando um for adicionado, faça um recálculo da iluminação para todos os blocos que apontam para a mesma fonte de luz que o bloco com paredes novas.

(Se várias mudanças de iluminação acontecerem de uma só vez - por exemplo, se uma luz for movida, o que conta como uma remoção e uma adição - você deve combinar as atualizações em uma única, usando o algoritmo acima. Basicamente, você zera o nível de luz de todas blocos apontando para fontes de luz removidas, adicione os blocos acesos ao seu redor, bem como novas fontes de luz (ou fontes de luz existentes nas áreas zeradas) às listas apropriadas e execute as atualizações como acima.)

Ilmari Karonen
fonte