¿Cómo puedo generar campos de distancia con signo (2D) en tiempo real, rápido?

En una pregunta anterior , se sugirió que los campos de distancia firmados pueden calcularse previamente, cargarse en tiempo de ejecución y luego usarse desde allí.

Por razones que explicaré al final de esta pregunta (para las personas interesadas), necesito crear los campos de distancia en tiempo real.

Hay algunos documentos disponibles para diferentes métodos que se supone que son viables en entornos en tiempo real, como los métodos para transformaciones de distancia de Chamfer y transformaciones basadas en aproximación de diagrama de Voronoi (como se sugiere en esta presentación por el desarrollador de Pixeljunk Shooter ), pero A mí (y, por lo tanto, se puede suponer que muchas otras personas) me cuesta mucho ponerlos en práctica, ya que generalmente son largos, en gran parte hinchados con las matemáticas y no son muy algorítmicos en su explicación.

¿Qué algoritmo sugeriría para crear los campos de distancia en tiempo real (favorablemente en la GPU) especialmente teniendo en cuenta la calidad resultante de los campos de distancia?

Como estoy buscando una explicación / tutorial real en lugar de un enlace a otro documento o diapositiva, esta pregunta recibirá una recompensa una vez que sea elegible para uno :-).

He aquí por qué necesito hacerlo en tiempo real:

Si tiene que calcular previamente estas SDF para entornos 2D grandes (piense en un mapa grande similar a Terraria), esto significaría que está aceptando una sobrecarga bastante grande en el espacio de almacenamiento (y el tiempo de generación del mapa) a favor de implementar un algoritmo complicado que es lo suficientemente rápido para la generación de SDF en tiempo real.

Por ejemplo, un mapa relativamente pequeño con 1000 * 256 (ancho * alto) con un tamaño de mosaico de 10 * 10 píxeles y, por lo tanto, dimensiones totales de 10000 * 2560 píxeles ya le costaría alrededor de 2 megabytes de tamaño, si elige un tamaño relativamente pequeño Resolución SDF de 128x128, suponiendo que está almacenando solo los valores de distancia de 0 a 255.

Obviamente, esto puede convertirse rápidamente en demasiado y es una sobrecarga que no quiero tener.

Hay algo mas:

Las SDF se pueden usar para muchas cosas (como la detección de colisiones), y algunas aplicaciones útiles aún no se han descubierto. Creo que mucha gente buscará estas cosas en el futuro, y si obtenemos una respuesta integral aquí, creo que ayudaremos a mucha gente.

Catalin Zima explica cómo lograr sombras dinámicas en 2D en su artículo , y usa un campo de distancia con signo (por lo que puedo decir, es solo un nombre elegante para un búfer de sombra en este contexto). Su método necesita una GPU, y su implementación tal cual no es la mejor (cayó por debajo de 60Hz a aproximadamente 20 luces en mi máquina, la mía obtuvo aproximadamente 500 luces); lo cual es de esperarse ya que ha favorecido la claridad del código sobre la velocidad.

Implementación

Exactamente como lo implementó él:

1. Renderiza todas las ruedas de sombra en una textura.
2. Calcule la distancia al centro de la luz para cada píxel y asigne ese valor al RGB de píxeles opacos.
3. Distorsiona la imagen para que represente cómo una cámara 3D habría visto esos píxeles.
4. Comprima la imagen en una imagen de tamaño 2xN usando el cambio de tamaño inusual descrito en su artículo (un cambio de tamaño simple no funcionará).
5. La imagen de 2xN es ahora su campo de distancia firmado para los cuatro cuadrantes de la luz (recuerde que un cuadrante es básicamente un tronco de cámara única a 90 grados).
6. Renderiza el mapa de luz.
7. Desenfoque el mapa de luz (basado en la distancia desde la luz) para obtener sombras suaves.

Mi implementación final fue (cada paso es un solo sombreador):

1. Hacer (1).
2. Haz (2) y (3) .
3. Hacer (4). Su implementación es realmente lenta: si puede intentar usar GPGPU para esto. No pude usar GPGPU (XNA), así que lo que hice fue:
   • Establezca una malla donde las primeras columnas N / 2 fueron representadas por N / 2 quads con la misma posición EXACT (cubriendo la primera columna del buffer final) pero con diferentes coordenadas de textura (lo mismo para las segundas columnas N / 2)
   • Desactiva las pruebas de profundidad en la GPU.
   • Use la función de combinación de píxeles MIN.
4. Haz (6) y (7).

Es bastante ingenioso: es básicamente una traducción directa de cómo se manejan las sombras en 3D a 2D.

Trampas

El principal inconveniente es que algunos objetos no deberían sombrearse: en mi ejemplo, estaba escribiendo un clon de Liero (gusanos en tiempo real) y, por lo tanto, no quería que, por ejemplo, los gusanos de los jugadores fueran sombreados (al menos el en la pantalla de cada jugador). Todo lo que hice por estos objetos 'especiales' fue volver a dibujarlos como último paso. La ironía era que la mayoría de los objetos no estaban sombreados (gusanos, primer plano del paisaje), por lo que aquí hay un problema de sobregiro.