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);
}
Respostas:
LR,.|VP - LP| < LR, verificando onde VP é o vetor de posição do voxel em relação à origem eLPo 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): ondesestá o comprimento lateral (128) da região do voxel e onnú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.
fonte
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.
fonte
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
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.)
fonte