Estoy usando C # y XNA. Mi algoritmo actual para la iluminación es un método recursivo. Sin embargo, es costoso , hasta el punto en que se calcula un fragmento de 8x128x8 cada 5 segundos.
- ¿Existen otros métodos de iluminación que harán sombras de oscuridad variable?
- ¿O es bueno el método recursivo, y tal vez lo estoy haciendo mal?
Parece que las cosas recursivas son fundamentalmente caras (forzadas a atravesar alrededor de 25k bloques por trozo). Estaba pensando en usar un método similar al trazado de rayos, pero no tengo idea de cómo funcionaría. Otra cosa que intenté fue almacenar las fuentes de luz en una Lista, y para cada bloque obtener la distancia a cada fuente de luz, y usarla para iluminarla al nivel correcto, pero luego la iluminación atravesaba las paredes.
Mi código de recursión actual está debajo. Esto se llama desde cualquier lugar en el trozo que no tenga un nivel de luz de cero, después de limpiar y volver a agregar la luz solar y la luz de las antorchas.
world.get___ates una función que puede obtener bloques fuera de este fragmento (está dentro de la clase de fragmento). Locationes mi propia estructura que es como a Vector3, pero usa números enteros en lugar de valores de coma flotante. light[,,]es el mapa de luz para el fragmento.
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);
}
Respuestas:
LR.|VP - LP| < LR, donde VP es el vector de posición del vóxel en relación con el origen yLPes el vector de posición de la luz en relación con el origen. Para cada luz cuyo radio del voxel actual se encuentra para ser en, incrementar su factor de la luz por la distancia desde el centro de la luz,|VP - LP|. Si normaliza ese vector y luego obtiene su magnitud, esto estará en el rango 0.0-> 1.0. El nivel de luz máximo que puede alcanzar un vóxel es 1.0.El tiempo de ejecución es
O(s^3 * n), dondesestá la longitud del lado (128) de su región de vóxel ynes la cantidad de fuentes de luz. Si sus fuentes de luz son estáticas, no hay problema. Si sus fuentes de luz se mueven en tiempo real, puede trabajar únicamente en deltas en lugar de volver a calcular todo el shebang en cada actualización.Incluso podría almacenar los vóxeles que afecta cada luz, como referencias dentro de esa luz. De esta manera, cuando la luz se mueve o se destruye, puede pasar por esa lista, ajustando los valores de la luz en consecuencia, en lugar de tener que atravesar toda la rejilla cúbica nuevamente.
fuente
Minecraft en sí no hace la luz del sol de esta manera.
Simplemente llene la luz solar de arriba hacia abajo, cada capa está recogiendo la luz de los vóxeles vecinos en la capa anterior con atenuación. Muy rápido: paso único, sin listas, sin estructuras de datos, sin recursividad.
Debe agregar antorchas y otras luces que no se inundan en un pase posterior.
Hay muchas otras formas de hacer esto, incluida la elegante propagación de luz direccional, etc., pero obviamente son más lentas y tienes que averiguar si quieres invertir en el realismo adicional dadas esas sanciones.
fuente
Alguien dijo que respondiera a su propia pregunta si lo resolvía, así que sí. Descubrí un método.
Lo que estoy haciendo es esto: Primero, cree una matriz booleana 3d de "bloques ya cambiados" superpuestos sobre el fragmento. Luego, complete la luz del sol, la luz de la antorcha, etc. (solo encienda el bloque que está encendido, todavía no se ha llenado la inundación). Si cambiaste algo, presiona los "bloques cambiados" en esa ubicación como verdadero. También vaya y cambie cada bloque sólido (y, por lo tanto, no es necesario calcular la iluminación) a "ya cambiado".
Ahora para las cosas pesadas: ve a través de todo el trozo con 16 pases (para cada nivel de luz), y si 'ya ha cambiado' simplemente continúa. Luego, obtenga el nivel de luz para los bloques a su alrededor. Obtén el nivel de luz más alto de ellos. Si ese nivel de luz es igual al nivel de luz de los pases actuales, configure el bloque en el que se encuentra al nivel actual y establezca "ya cambiado" para esa ubicación en verdadero. Seguir.
Sé que es un poco complicado, traté de explicar lo mejor. Pero el hecho importante es que funciona y es rápido.
fuente
Sugeriría un algoritmo que combina su solución de múltiples pasadas con el método recursivo original, y probablemente sea bastante más rápido que cualquiera de ellos.
Necesitarás 16 listas (o cualquier tipo de colecciones) de bloques, una para cada nivel de luz. (En realidad, hay formas de optimizar este algoritmo para usar menos listas, pero esta es la forma más fácil de describir).
Primero, borre las listas y establezca el nivel de luz de todos los bloques en cero, y luego inicialice las fuentes de luz como lo hace en su solución actual. Después (o durante) eso, agregue cualquier bloque con un nivel de luz distinto de cero a la lista correspondiente.
Ahora, revise la lista de bloques con nivel de luz 16. Si alguno de los bloques adyacentes tiene un nivel de luz inferior a 15, establezca su nivel de luz en 15 y agréguelo a la lista correspondiente. (Si ya estaban en otra lista, puede eliminarlos de ella, pero no hace ningún daño incluso si no lo hace).
Luego repita lo mismo para todas las otras listas, en orden decreciente de brillo. Si encuentra que un bloque en la lista ya tiene un nivel de luz más alto de lo que debería por estar en esa lista, puede suponer que ya se procesó y ni siquiera se molesta en verificar a sus vecinos. (Por otra parte, podría ser más rápido verificar a los vecinos; depende de la frecuencia con que eso suceda. Probablemente debería intentarlo en ambos sentidos y ver qué camino es más rápido).
Puede notar que no he especificado cómo deben almacenarse las listas; En realidad, casi cualquier implementación razonable debería hacerlo, siempre que insertar un bloque determinado y extraer un bloque arbitrario sean operaciones rápidas. Una lista vinculada debería funcionar, pero también lo haría cualquier implementación a medias decente de matrices de longitud variable. Solo usa lo que funcione mejor para ti.
Anexo: Si la mayoría de sus luces no se mueven muy a menudo (y tampoco lo hacen las paredes), podría ser aún más rápido almacenar, para cada bloque iluminado, un puntero a la fuente de luz que determina su nivel de luz (o a uno de ellos, si varios están atados). De esa manera, puede evitar las actualizaciones de iluminación global casi por completo: si se agrega una nueva fuente de luz (o una existente se iluminó), solo necesita hacer una sola pasada de iluminación recursiva para los bloques a su alrededor, mientras que si se elimina una (o atenuado), solo necesita actualizar los bloques que apuntan a él.
Incluso puede manejar los cambios de pared de esta manera: cuando se retira una pared, simplemente comience un nuevo pase de iluminación recursiva en ese bloque; cuando se agrega uno, realice un recálculo de iluminación para todos los bloques que apuntan a la misma fuente de luz que el bloque recién amurallado.
(Si ocurren varios cambios de iluminación a la vez, por ejemplo, si se mueve una luz, lo que cuenta como una eliminación y una adición, debe combinar las actualizaciones en una sola, utilizando el algoritmo anterior. Básicamente, pone a cero el nivel de luz de todos bloques que apuntan a fuentes de luz eliminadas, agregue los bloques iluminados que los rodean, así como cualquier fuente de luz nueva (o fuentes de luz existentes en las áreas cerradas) a las listas apropiadas y ejecute las actualizaciones como se indica arriba).
fuente