JoeJ said: To form a river crossing many tiles, we can do this because the parent tiles, being larger at less detail, already carved in the coarse shape of the river.
This is true to an extent, but there is a problem which I guess you mentioned in your earlier post:
JoeJ said: In nature, events on higher frequencies can affect lower frequencies, but we can't do that since our method only works for the other way around. For example, we may have a problem to form fine rivers…
What this means is that in practice we can only produce features with hierarchical erosion which follow a kind of “fractal” structure, where things are similar at all scales and the size of details added at each LOD follow a power law 2^(-x). Parameters such as erosion rate, precipitation, and time step duration must be tuned so that they scale with the same 2^(-x) power law, or else the terrain diverges (changes shape unnaturally) as you zoom in to smaller tiles. When we zoom in with the erosion we are effectively looking forward in time by progressively modifying the elevation with more time steps at smaller scale. If the erosion effect does not follow the power law, the time (and therefore simulation state) does not converge to a specific value. (It's a similar situation to Zeno's Dichotomy Paradox vs. someone moving at a constant linear rate: one person's position asymptotically converges to close to 1, while the other diverges to larger values). This places constraints on what we can do with the hierarchical erosion approach I am using.
Since narrow rivers are an inherently high-frequency phenomenon, they cannot be produced by the larger tiles due to the Nyquist limit. The smallest feature that can be formed at any LOD scale is 1 pixel in size. One of the biggest issues I've seen with my system is that the “rivers” in many cases are much too wide (typically 100-1000m) once you get to surface level, which is a direct result of this limitation. It is still possible to have narrow streams, but these emerge at finer LOD levels in preexisting depressions from coarser LOD, and do not carve themselves. I doubt there is a workaround aside from significantly increasing the tile resolution, which I am not likely to do due to performance constraints.
@Aressera with regard to rivers - this is why I eventually abandoned the “entirely in RAM” route. River routing has to have access to the most detailed level of landscape heights and slopes in order to be formed naturally - and I ‘spring’ the rivers from the erosion particle termination point.
So to produce rivers, I do the following sequence;
Generate coarse land heights and store them.
Apply erosion at coarse level, storing the termination points.
Generate detailed land heights suitable for river route calculation (about 10m resolution)
Select some erosion termination points as springs
Generate a river set of vertexes which follow the natural landscape route (rivers dont flow uphill) by consulting my previously stored land heights, I store the speed of water plus the volume of water at each vertex. I also join rivers where they intersect.
Store the river route as a set of vertexes (which I later load as a Triangle Strip at runtime). I also store a set of indexes to tiles which the river intersects, and update the tile metadata to record which River crosses it,.
This set of offline processes are unbounded in scope - a river may be very short (and therefore theoretically calculable at runtime) but it also might be very long and require an extended time to generate it.
At runtime when I load the tile.
Load the height map
If this tile has one or more Rivers recorded in its metadata, I load the river vertexes
Generate a river Triangle Strip
Use VS/PS pair to draw the triangle strip, and for every pixel hit, I modify the loaded heightmap to generate the river trough, and also modify the vegetation map to prevent trees growing in the middle of rivers.
I also generate various river artefacts such as the river water surface mesh.
I could do these runtime steps at generation time (offline) but I'd then be completely abandoning runtime generation in favour of “baking” a world. I'm intellectually stuck in between runtime generation and offline generation - I don't see a way to do runtime generation for anything other than purely fractal landscapes; oddly although these fractal landscapes are called ‘procedural’ landscapes, the generation at runtime prevents non-trivial processes to be run over them ; they are probably better called “algorithmic landscapes" :-)
For rivers I'm actually working on some functions that generate them naturally. They use a kind of recusive voronoi system, further modified by noise. In my case I don't want to store anything other than player modifications to terrain, since I'm dealing with planetary scales and the storage requirements would be far too high. For erosion I'm playing with 4D noise to modify high slope areas. All this is pretty experimental at this point however.
@gnollrunner With regard to Voronoi - I've also gone down this route, but only now use Voronoi cells to describe Fields, Woodlands and other human managed areas of my landscape. It works pretty well, and where there are non-human areas of the landscape “the wilds” these are just handled algorithmically.
I have found some benefit in defining roads as a series of Voronoi cell edges, because in a human managed landscape, roads often simply traverse field and woodland boundaries - but in the unmanaged “the wilds” they tend to take a optimum route based on the slope value (i.e. they typically follow contour lines).
In my experimentation I found that river routes are not based on Voronoi cells - they look really odd if you try to force them to obey Voronoi boundaries unless your heighmap already is based on Voronoi cells. That can be true - but it also means that heights would not longer be able to be determined as the result of a single algortihm with inputs of X and Y - the heightmap would need to repeat the Delaunay triangulation that provides the Voronoi cell - and probably not be able to be determined at runtime in a given set of operations.
When I say “look really odd” they tend to carve into the landscape excessively - in order to obey the rule “all rivers run downhill” they simply carve a trench between one Voronoi vertex point and another - the two Voronoi vertexes are definitely downhill with respect to one another, but the intervening landscape heights might easily be uphill - and the river just carves through them. Its technically correct but the river ends up looking like it was a laser cutting through the landscape.
I've ended up treating Rivers as a procedural task than can only be satisfied offline - but I'd be really interested in hearing if you've found a way to do this at runtime without arbitrarily truncating a river course to fit the time budget neccessary,
Aressera said: Since narrow rivers are an inherently high-frequency phenomenon, they cannot be produced by the larger tiles due to the Nyquist limit. The smallest feature that can be formed at any LOD scale is 1 pixel in size. One of the biggest issues I've seen with my system is that the “rivers” in many cases are much too wide (typically 100-1000m) once you get to surface level, which is a direct result of this limitation. It is still possible to have narrow streams, but these emerge at finer LOD levels in preexisting depressions from coarser LOD, and do not carve themselves. I doubt there is a workaround aside from significantly increasing the tile resolution, which I am not likely to do due to performance constraints.
Agree on the limitations. In my layman terms, i would describe them with ‘as we add higher frequencies, we need to half max. amplitudes each time, so the changes we do are guaranteed to be smaller than what the lower frequency already represents’.
Btw, one problem that could be maybe avoided is about the scaling of simulation parameters, so we get the same erosion behavior at every scale (or frequency band). My parameters are relative to global space, so i have to scale them. And this was not easy to figure out. I need to multiply with either x, x^2, or x^3, and i had to use trial and error and lots of testing to get this right. If i had my parameters relative to tiles or cells, no parameter scaling would be needed, saving some tedious work. But i guess anyone who works with hightmaps should arrive at that without thinking anyway.
About the rivers, they are too fine to show up in lower frequencies, yes. But the lower frequencies do already represent the valleys guiding the water, and rivers form by carving the valleys deeper, so it might work regardless eventually? I have no rivers yet. I feel like my 3D particle simulation is just too noisy to generate them, but not sure. But i was thinking to make this valleys idea work, i might need to guide the rain density, so more rain falls where water has concentrated in the simulation of the lower frequency tile. But i have not tried this, and i'm not really optimistic this gives good results. I'll rather handle rivers with a hack. My world is big but finite, so i will just create rivers globally with some custom data structure and carve them out. Something like that. But first i need to switch from 3D simulation to hightmap tiles on the quadrangulated surface. 3D is way too slow to use it for finer frequencies, and i could not really reach the quality of simple 2D simulation either.
Another interesting problem i've had was about the blending across tiles. Using 3D particles i can not blend results as easy as with heightmaps. So i did stochastic culling of the particles, and afterwards i have displaced them slightly to enforce a poission disk distance between them, which i do during simulation as well. This should be correct and ideal, but it did not work. The cell boundaries were visible, showing a global grid over the blended landscapes. So after having done all that work, i have tried to do no blending at all, just cutting away all particles outside the cell bounds. And surprisingly this works. But i'm still baffled, and would not wonder if at some point this shows problems.
PhillipHamlyn01 said: So to produce rivers, I do the following sequence;
Interesting, that's similar to what i have in mind. But i think we want to model the effect of meandering rivers somehow eventually. You know, those curls and loops that rivers form. They don't want to be straight. It might work to detect curvature along our river path, then trying to make the path longer, by amplifying the curvature.
Though, i'm uncertain about mixing procedural modelling and simulation. I'd prefer to simulate everything if possible, but we may also want manual control for level design too, so not sure what's better.
Btw, i found it very difficult to make erosion simulation work in 3D. It's much harder than in 2D for unknown reasons. So i always had doubts to understand the concept of the process. It seems both simple and complex. Later i found this video which is really telling and inspiring. I wish i would have found it earlier:
In case you're curious about 3D vs. 2D results, here's what i get so far (uses tiled processing):
It shows some overhangs heightmaps could not do, but i need to work on caves to show a real advantage. Currently i would not recommend anybody to go that 3D route. It's much more work, and much slower. I think it took me a year, not really knowing anything about fluid sim before.
I did 2D simualtion first to learn about it. 2 weeks of work, and results are pretty good (no tiling here):
In my experimentation I found that river routes are not based on Voronoi cells - they look really odd if you try to force them to obey Voronoi boundaries unless your heighmap already is based on Voronoi cells.
I'm not really using Voronoi “directly” for rivers. As an example, if you take two points and use Voronoi, you get a straight line. Now you consider those two points as peaks, and you have a small mountain range with a dip between them. Again, it's still a straight line, but on either side of the center point directly between them, they slope downhill based on the distance from the points. You have to use some smoothing functions and randomness to make it reasonable. The river(s) should never start at the top so there is some distance away from the center point they begin. Now you have to warp the whole thing so the rivers wind. Finally, you introduce new peaks to the two sides to start generating tributaries and do the same sorts of operations as before. You do this recursively. That's the basic idea but there are a lot of details.
You can also now use noise in the normal way to vary your terrain, but you have to tail off your noise as you approach the rivers to keep them flowing downhill. So basically, you first define rough terrain with downhill flowing rivers and then build the more detailed terrain around them.
Keep in mind, I'm not going for ultimate realism. My goal is to have a playable game on large scale planets with a very small disk footprint. This approach is targeted at that. Yet I still want basic stuff, like downhill flowing rivers, and I want to support caves and underground areas, hence the use of voxels.
@gnollrunner - I think I understand but want to check - you generate the river system prior to (or at least partly affecting) your noise based heightmap by the distance-from-river of a given point ?
I tried this but found that the checking of “how far is this point from the nearest river segment” algorithm needed so much optimisation (theoretically every point could be near every possible river segment - impossible to calculate) that I started chunking up my rivers to be bounded by tiles, and to make that point-nearest check that boundary had to be as small as it could be, and I was back where I started - to have natural river courses that are unbounded by a tile seems to be requiring offline processing and storage. Every time I try to think my way thorough this I get to this point.
My problem (of many) is that clearly No Mans Sky and other titles have solved this - but I'm hoping to find that simple hint that will tell me how to combine algorithmic based noise heights (easy to make a plant out of) with non-algorithmic, procedural features; such as rivers, roads and other items unbounded by any given size of tile.
@JoeJ - I did come across an interesting way of doing heightmaps that allowed for overhangs, tunnels etc, - but I didn't try it myself. In the example I saw, heightmaps were described as 3d displacement maps. I've applied part of this concept in my heightmap generation - but still only store the offset height coordinate as a height. In the example the full 3D displacement was stored so that overhangs could be created, and caves etc were possible.
In the example, the author stored a datum height based on a fractal algorithm to provide the basic surface, but then applied a Displacement value to combine horizontal as well as vertical offsets. This is very similar to most of the examples I've seen of ocean wave rendering. Maybe useful to try it out sometime.
PhillipHamlyn01 said: clearly No Mans Sky […] have solved this [river problem]
Absolutely not, at least for NMS. NMS procedural generation is child's play compared to what we are discussing in this thread, having spent a few hundred hours playing that disaster of a game. Their generation is just warped perlin noise in voxels with the same biome/textures everywhere. It took me about 2-3 weeks to get something like that up an running (see my first blog post). You can watch their GDC talks here and here to see how they do it. In fact that game was a big motivator for my project, because I was so disappointed with how simplistic their generation is. I want to make something that is much more realistic than that cartoon, with proper geology, erosion, plate tectonics, and realistic solar system scale. The biggest planet in NMS is <100km in diameter. The worst part is that they've had 7 years to make the core generation better but have instead focused on fluff.
PhillipHamlyn01 said: @JoeJ - I did come across an interesting way of doing heightmaps that allowed for overhangs, tunnels etc, - but I didn't try it myself. In the example I saw, heightmaps were described as 3d displacement maps. I've applied part of this concept in my heightmap generation - but still only store the offset height coordinate as a height. In the example the full 3D displacement was stored so that overhangs could be created, and caves etc were possible.
You mean somebody uses standard heightmaps, but deforms the surface with vector displacement to get overhangs and caves? This sounds quite limited. In general vector over scalar displacement is rarely worth it, because vectors give more deformation headroom, but do not address the main limitations of displacement mapping: The resolution depends on parametrization, which for a hightmap model is usually a regular UV grid at the ground plane. So if we have steep cliff, parametrization is stretched along height and we don't have enough displacement texels to add the detail we would need. If we deform this so much to get a cave, the resolution of final geometry would decrease dramatically the further we go into the cave.
In practice, displacement mapping can only slightly modulate the surface of our base mesh. But if we want consistent resolution independent of slopes, we need a better basemesh or at least a better parameterization than hightmap models can give. Using vector displacements does not really help with this.
If we use a traditional mesh for our terrain to have a better basemesh, our UV parametrization requires multiple UV charts (islands of connected triangles for a patch of surface). A steep cliff or the interior of a cave require their own charts. That's what we do for traditional meshes, but unfortunately there is a problem preventing this to be useful for displacement mapping. The problem is UV seams. If we look at the UV chart boundaries on our mesh, we notice texels are cut along the boundary. That's acceptable for texturing, but if we use it for displacement we get cracks in the final geometry, because texels along UV seams do not precisely match. That's why displacement mapping is rarely used and mostly restricted to flat heightmap models. The parametrization here is not ideal for slopes, but it has no charts and so no cracks. Again, vector displacement adds nothing to improve this limitations.
If you ask me for the simplest way to make terrain with caves and overhangs, plus high detail from displacement maps, i would propose a basemesh made from voxels. Just like Minecraft. But instead keeping the voxels blocky, we project vertices to the surface as given from our initial scalar density volume we got our binary voxels from. This smooths the terrain and removes the blockyness. (That's exactly what you see in my purple 3D screenshot btw.) It's important our mesh is still a quadmesh. No triangles, just quads. And with quads it's easy to avoid texture seams. We just give each quad a block of texture. It's like Disneys PTex. The parametrization is implicit and semless, so we can do displacement mapping everywhere. So at this point we have support for high genus models and we have seamless parametrization too, at low effort. However, our parametrization is of low quality:
That's a smoothed voxel Armadillo, and you see some quads are stretched. If we can't counteract this stretch by compensating it within the content of our textures, it might look bad and like artifacts. But i do think this might work well for terrains. If i would try, i think i would get something similar to Gnollrunners work, just using cubes instead prisms to form some spherical, planetary domain. This could also easily support runtime editing of terrain. The potential advantage here is we can do 2D texturing, and we do not need to use limited volumetric texturing (volume textures or procedural 3D noise).
But for me personally that's not an option, since my primary goal is not terrain but global parametrization for realtime GI. I need higher quality for both performance and image quality reasons. So i use the above method only as a starting point for curvature aligned, quaddominant remeshing, which looks like this:
There are some triangles, so i need to apply one level of Catmull Clark subdivision to get all quads. But then stretching is minimized, each quad has roughly the same size, and i can finally do high quality UV-less texturing including displacement. Because those initial conditions are ideal, i would see zero benefit from using vector over scalar displacement.
It's nice, but at this point the meshing as a much harder problem than terrain generation. That's really difficult to do, and you loose all advantages simple height maps give, including fast collision detection, minimum storage costs, etc. From my perspective i can say improvements over standard methods are always possible, but complexity, effort, and other costs tend to increase exponentially pretty quickly.
