PDA

View Full Version : Rivers using Heirarchical Poisson Disc and Delaunay Triangulation

Hai-Etlik
04-26-2014, 01:53 AM
Here's what happens when you take a hierarchical Poisson disc stipple field, assign a rainfall level of 0 or 1 based on rank in the field and a precipitation surface (in this case (sin x*cos y)^1.5), assign the nodes around the edge to a starting set (effectively the ocean) and then randomly add nodes adjacent to the connected set in the Delaunay triangulation of the whole set to the connected set until you've connected them all, and then display the graph with edges weighted by the sum of upstream rainfall.

63501

Hai-Etlik
04-26-2014, 07:28 PM
Now with a weighted selection for flow direction that reduces the likelyhood of sharp bends and constrained hydrological divides.

63536

Here's the weighting function, where theta is the angle between the new segment and the downstream one. All the available downstream nodes are weighted and then one is selected randomly based on that weighting. This is designed to encourage some squiggle but avoid really sharp bends.

ToDoubleFunction<Optional<Double>> weight = theta->{
return Math.pow((Math.cos(theta.orElse(0.0))+1)/2, 100) - Math.pow((Math.cos(theta.orElse(0.0))+1)/2, 300)/4;
};

Hai-Etlik
04-26-2014, 07:45 PM
I think I may need to add a weighting to the selection of the next node to add, perhaps based on proximity to break lines. If nodes near the break line were selected later it would reduce the occurrence of rivers along the sides of break lines.

Hai-Etlik
04-26-2014, 08:06 PM
Weighting the selection with proximity to the break line helped immensely.

63538

ravells
04-26-2014, 08:07 PM
Holy moley! This looks fantastic!!!

Allow me to give you some reputation!

Hai-Etlik
05-13-2015, 10:26 PM
I've noodled around with this a bit more recently

73328

Hai-Etlik
05-15-2015, 03:02 AM

73352

Lakes start as a point on a river and then expand up stream (including along streams that were made 'dry' during the precipitation and flow calculation).

Redrobes
05-15-2015, 06:09 AM
Very cool stuff going on here. Keep posting - I am following what your doing with some interest. Tho I calculate my rivers using a different technique I can see why this way might be really super fast compared to mine. Presumably you can determine the height map from the initial stipple field. Id like to see how this looks in 3D or with shaded relief.

Hai-Etlik
05-18-2015, 10:55 PM
Very cool stuff going on here. Keep posting - I am following what your doing with some interest. Tho I calculate my rivers using a different technique I can see why this way might be really super fast compared to mine. Presumably you can determine the height map from the initial stipple field. Id like to see how this looks in 3D or with shaded relief.

The speed is hampered by the weighted random selection it has to make at each step of computing the paths. Once that is done though, it can be saved and re-used so that the river network can be recomputed for different precipitation surfaces. At some point I'd like to do an animation of the river network shifting with varying weather. Tying the lakes into that too would be particularly cool. Overall the images above took a few minutes to generate. Being a bit more clever about it ought to speed it up, especially if created some specialized data structures.

3D isn't that practical given the way this works. It essentially only knows about aspect, not slope or elevation. Artificial DEMs that don't look horribly fake are really hard to do which is why I tried to come up with a way of generating decent looking rivers without a DEM.

Hai-Etlik
05-24-2015, 05:48 PM
Weighted random selection now uses parallel prefix sum and binary search which has improved performance. I've also switched to loading shapefiles instead of generating the coastline and divides internally.

Input
73585

Output
73586

gilgamec
05-25-2015, 10:20 AM
I've given this a try and I'm curious how you're handling the triangulation near the coastline. Not creating points outside the landmass gives triangulations like this:
73597
This in turn gives rivers that reach the coastline at very oblique angles. Are you continuing the triangulation beyond the coasts but truncating the triangles? If so, how do you handle altitudes of these triangles? Is there some other solution I've missed?

Hai-Etlik
05-25-2015, 12:16 PM
I've given this a try and I'm curious how you're handling the triangulation near the coastline. Not creating points outside the landmass gives triangulations like this:
73597
This in turn gives rivers that reach the coastline at very oblique angles. Are you continuing the triangulation beyond the coasts but truncating the triangles? If so, how do you handle altitudes of these triangles? Is there some other solution I've missed?

Yes I'm continuing outside the coastline. At the start, any nodes inside the land are unconnected and anything outside is connected, then I find the set of unconnected nodes adjacent to connected ones, select one at random, find the set of connected nodes adjacent to it, and select one at random, then join the two and move the newly joined node to the the connected set, and all of its adjacent nodes (that aren't connected) to the set of potential selections for the next iteration. There's no concept of elevation involved, just weight functions applied to the random selections. The final output has the rivers sticking out past the coastline. I currently fix this by applying the coastline as a clipping path in Inkscape although it shouldn't be hard to do the clipping operation in my generator, and I'll probably add that when I add a raw data output capability (shapefile, etc)

RedKettle
05-26-2015, 12:23 AM
Very interesting! For just (semi-)randomly picking directions, this generates some nice results. I am also watching this thread to see how far you can take this!

There's no concept of elevation involved...

I would hesitantly disagree, and say that your hydrological divides could be an abstraction of elevation data (ridge lines?). I am now wondering if there is some way of processing elevation data so that this can read it as just a set of ridge lines/break lines/divides.

Hai-Etlik
05-26-2015, 01:13 AM
Very interesting! For just (semi-)randomly picking directions, this generates some nice results. I am also watching this thread to see how far you can take this!

I would hesitantly disagree, and say that your hydrological divides could be an abstraction of elevation data (ridge lines?). I am now wondering if there is some way of processing elevation data so that this can read it as just a set of ridge lines/break lines/divides.

The ridgelines are certainly meant to represent topography in a highly abstract way, as are some of the selection weightings. I'd hesitate to use the term "elevation" though. In geography "elevation" is specifically the distance between the ground surface and the datum (essentially "sea level" in non-geography speak). There's no vertical distance quantity anywhere in my algorithm which is why I say it has no concept of elevation.

Hai-Etlik
05-31-2015, 10:27 PM
The precipitation is now a raster file rather than a perlin noise generator. So the collecive inputs to the algorithm look like this
73787

And the output looks like this
73786

Azelor
06-01-2015, 11:03 AM
What are the colours for, blue is wet and red is drier ?

Hai-Etlik
06-01-2015, 06:35 PM
What are the colours for, blue is wet and red is drier ?

Yep, it's a pseudocolour ramp for easier visualization. The underlaying data is a greyscale 8 bit PNG with a world file for georeferencing.

TK.
09-28-2015, 08:53 AM
uhhh... for the really stupid people like me...what software is this?

Redrobes
09-28-2015, 09:19 AM
I believe this is his own software that he has written. I have written something like it too as have several others. Its an interesting little problem to try to automatically calculate the probable river paths, which is hard to map, based on some simple inputs like rough height maps, which is a lot easier to manually do. It makes making a map much easier and more realistic than if you arbitrarily draw on the rivers where you think they might be. The physics of where water should be is generally pretty well known although its complicated by the infinitely detailed and complex terrain of real world ground and weather. But you can do a pretty good job of it. Another harder problem that we have had a go at and nobody has really had great results yet is that of automatically placing buildings for a town that look right. To get it to look right you need to grow the town much like you need to grow the rivers. Just plonking them down in some random way doesnt cut it. People tend to build where it needed, and sometimes knock buildings down and put up new ones based on what has grown there so far. But for now, rivers is something we can have a crack at and get some plausible results from and this particular technique is something Hai Etlik is exploring.

TK.
09-28-2015, 11:00 AM
@Redrobes Thanks for the reply! I see... yeah, I encountered that problem with city buildings when I tried my first city map. Saw that would take a huge amount of time to get buildings individually and manually, so tried an automated approach without much success.

Redrobes
04-14-2016, 05:46 AM
I just saw this link below posted on ycombinator about calculating voroni patches and wondered if this would be useful for this process. What I particularly liked was that you can rapidly get the distance from the points. Surely that has great implications for calculating the river flow. I can see that this could be useful for other things too like city mapping where the probability of putting stuff down depends on its closeness to a resource. I was doing something similar to this when trying to find the closest route from person to resource in my mapping with economics thing and I used a similar but not nearly as effective way of doing it.

http://rykap.com/graphics/skew/2016/02/25/voronoi-diagrams/

Hai-Etlik
04-18-2016, 09:04 PM
I just saw this link below posted on ycombinator about calculating voroni patches and wondered if this would be useful for this process. What I particularly liked was that you can rapidly get the distance from the points. Surely that has great implications for calculating the river flow. I can see that this could be useful for other things too like city mapping where the probability of putting stuff down depends on its closeness to a resource. I was doing something similar to this when trying to find the closest route from person to resource in my mapping with economics thing and I used a similar but not nearly as effective way of doing it.

http://rykap.com/graphics/skew/2016/02/25/voronoi-diagrams/

The voronoi/delaunay calculation I'm currently using JTS for really isn't a significant part of the time it takes. I do it just once. Initial generation of the points, and the weighted random selection are what slow it down. Once I get the tile based stippling working again (doing proper, stable, non-hacked together implementation was the original point of this project) the point generation should be plenty fast. That leaves weighted random selection which I've done a bit of thinking about, but for now it's good enough for the kind of use cases I have in mind for this software.