GPU que fluye computa el agua

Tengo experiencia en ingeniería civil y realizo análisis hidráulicos e hidrológicos regularmente. Venden títulos para ese tipo de cosas, pero en realidad no es ciencia espacial. Hace poco pensé en implementar todo el proceso hidrológico e hidráulico para un terreno en la GPU. Aprendí sombreadores informáticos solo recientemente, así que actualmente estoy atascado siendo mejor en ingeniería que diseñando flujos de trabajo de GPU paralelos.

Puede calcular la cantidad de agua generada durante un evento de lluvia usando la fórmula:
Q (CF/S) = c * I (in/hr) * A (acres)

Tengo dificultades para avanzar más allá del cálculo de la "superficie" de incluso la primera área.

Resumen de la implementación actual:

1. El terreno es una grilla regular de vértices a intervalos de 1 unidad.
2. Un mapa de altura contiene un valor de altura R32 para cada vértice
3. Actualmente, solo estoy permitiendo el flujo en las 4 direcciones cardinales (sin diagonales)
4. Estoy usando un Texture2D [int] como plantilla para vértices que ya he analizado

Algoritmo actual:

1. Cuando la herramienta de terreno ha estado activa y ahora no ...
2. Borrar la "plantilla".
3. Escanee todo el terreno para la elevación más baja.
4. Ese único punto es la entrada inicial a CS_Flood.
5. CS_Flood realiza un pase del eje X.
6. Cada vértice de entrada se proyecta en las direcciones X y X + hasta 2048 veces.
7. Encontrar un vértice adyacente con una coordenada OOB indica el borde del terreno en esta dirección. CurrentPoint se agrega al búfer BoundaryPoints y se termina el bucle de proyección para esa dirección. Esto fue fácil y funciona muy bien cada vez.
8. Los vértices adyacentes con alturas> = la altura del vértice actual se marcan en la plantilla y se agregan al búfer NextPass.
9. Vértices adyacentes con alturas <la altura del vértice actual indica el pico de una cresta y termina el bucle de proyección. Una iteración futura del relleno de inundación podría fluir alrededor de la base de la cresta, hasta el lado "posterior" y detectar la misma cresta por segunda vez.
10. Cualquier punto de cresta / cresta que se detecte más de una vez no será un BoundaryPoint, para este propósito.
11. Cualquier punto de cresta / cresta detectado exactamente una vez se agrega a BoundaryPoints y se termina el bucle de proyección en esa dirección.
12. CS_Flood realiza una pasada del eje Z con el mismo código, utilizando los puntos generados por la pasada del eje X como entrada.
13. En este momento, CS_Flood continúa alternando entre las dos direcciones indefinidamente. Eventualmente, terminaré el ciclo general cada vez que CS_Flood se complete y el búfer NextPass esté vacío.

Idealmente, en ese punto, BoundaryPoints contendría cada vértice que ocurre en la división de drenaje natural. Las gotas de agua que caen dentro del límite finalmente fluyen al mismo punto bajo. Las gotas de agua que caen fuera del límite van "a otro lugar".

Luego:

1. Sin despejar la plantilla, vuelva a escanear el terreno para encontrar el vértice más bajo, no estarcido.
2. Iterar CS_Flood.
3. Repita hasta que la plantilla esté llena (o algo similar).

3D es difícil de percibir con estos colores; esto muestra líneas de contorno en elevaciones integrales:
(un agujero rodeado por una berma cerca del borde)

Hay alrededor de 10 formas únicas de drenar a través de un vértice; dar a cada uno un color único se ve así:
(las marcas de herramientas circulares visibles, "crestas" se muestran muy bien)

Esto muestra cada punto generado por CS_Flood, límite o de otro modo, como POINTLIST:

El algoritmo casi siempre funciona . A veces, incluso funciona correctamente. Otras veces, el algoritmo está claramente contenido en la forma correcta, pero continuará emitiendo puntos indefinidamente. Como se ve en la tercera captura de pantalla, a veces se confunde. Debe haber otra situación / factor que he pasado por alto. Agradecería cualquier ayuda para encontrar mi supervisión o sugerencias de formas más simples y / o más elegantes para atacar el problema.

MissingPoint! puede incluirse ayudando al algoritmo para agregar cada nuevo BoundaryPoint detectado al búfer NextPass. Durante la próxima pasada, el 99% de los puntos generados por esa curita desperdiciarán una pequeña cantidad de tiempo de GPU determinando que no pueden ir a ningún lado y no hacer nada. Durante la primera pasada, el envío de LowestPoint junto con los otros puntos NextPass también manejaría este escenario específico.

Sé que es plausible y, con el tiempo suficiente, podré usar la curita lo suficiente como para hacer lo que quiero. Me gustaría hacerlo de una manera mejor, más inteligente y más rápida, si es posible, y todavía no tengo suficiente experiencia para saberlo mejor.

Cuando una gota "tratado" para visitar un vértice, la plantilla estaba marcado con InterlockedExchangeel uso del "valor original" para determinar si ha sido ya estarcido (a pesar de que solo se sobreescribí).

El mejor algoritmo que se me ocurrió le dio a la inundación un "bloc de notas" y una sola regla: "no fluya cuesta abajo" (alturas iguales o mayores). Eso eliminó casi todas las pruebas complicadas. Si bien generalmente es bueno para no fluir sobre picos / crestas, fluye a lo largo de ellos porque los vértices adyacentes son "planos". Esto ocasionalmente permite que las gotas se escapen más allá de las crestas.

Cada uno de los puntos "demasiado lejanos" es, entonces, "fluido" y fluirá "hacia" el área de drenaje (se detiene en un 1) o no (se detiene en un 0). Los "nots" se descartan y el bloc de notas corregido se copia en el "final". Si el final ya está estampado, se descarta el bloc de notas. (Futuro: esas colisiones deben representar colectivamente el límite exterior del área de drenaje actual).

A 10 fps:

Los "nots" se muestran en rojo, una vez que el área grande se copia en el final y se vuelve verde, el algoritmo se repite para las áreas restantes sin grabar.