¿Algoritmo de iluminación 2D rápido?

Question

Tenemos un área rectangular con paredes translúcidas y unos pocos sources.We luz están considerando sólo la vista superior, por lo que es un problema 2D. Necesitamos encontrar la iluminación aproximada (intensidad de la señal) en cada punto del área.

Tenemos que hacer que el algoritmo muy rápido. El método de la fuerza bruta fue demasiado lento para nuestros propósitos. Puede suponer que todas las paredes se atenúan en la misma cantidad, incluso una cantidad constante de atenuación es aceptable.

la zona sería en la mayoría de 1000x1000, y no sería de más de 100 fuentes de luz. Las fuentes de luz pueden tener un rango de aprox. 50-100 unidades (no son infinitas). Los algoritmos más rápidos pero aproximados son bienvenidos.

¡Gracias de antemano!

Lo que intenté fue básicamente el método de fuerza bruta: comparando cada punto de muestra con cada pared y fuente de luz para determinar su luminosidad. Obviamente, es O (n^3) e inaceptablemente lento.

Por tiempo no quise decir ningún límite específico: pero sería bueno hacer toda la imagen dentro de 100ms o más rápido. Recuerde, no requiero precisión tanto como la velocidad.

Answer 1

Solo una puñalada en la oscuridad: ¿has mirado en el mapeo de fotones (acelerado por GPU)?

Answer 2

Puede reducir el tiempo de ejecución de un algoritmo similar de forma cuadrática (por ejemplo, omitir cada 2º x e y) perdiendo calidad linealmente (la imagen obtiene medio diámetro y vuelve a muestrear al mismo tamaño).

Utilice un mapa de bits para almacenar la luminosidad, y rinde en un mapa de bits menor tamaño (divide por el factor de aproximación) todos los puntos de las líneas atc (pero dividir todos los puntos por el factor de aproximación también) a continuación, utilizar el desenfoque gaussiano y volver a muestrear de nuevo a tamaño deseado . Luego extrae la luminosidad de los píxeles.

Cargué un video en youtube que muestra la ejecución de una prueba que hice para probar si eso pudiera funcionar. Parece omething similar a lo que necesite (hacerlo con 'casi a tiempo real' en un único subproceso):

Link to Video

Por supuesto aquí paredes son líneas con propiedades de transparencia, y la luz no se difunde como lo haría espere pero linealmente, pero la "aproximación" debería ser utilizable por su algoritmo, o puede adaptarla si la velocidad es suficiente. Y cuidado, el código está escrito muy mal porque simplemente estaba experimentando.

Aquí luminosidad se normaliza, es probable que vaya con la incorporación de luminosidad en una escala logarítmica en píxeles, por lo que puede adaptarse a una gama más amplia, para preservar los valores originales.

es que se puede utilizar para algo: Aquí está el proyecto:

Link to project

Si optimiza y el hilo que, probablemente, 100ms una imagen de 1000x1000 con 100 luces con diámetro 300 para y como 20 paredes de longitud 200, con una aproximación de 5 es alcanzable.