terrain generation fractal terrain midpoint displacement
Back in Time
I'll try to reconstruct this paragraph since I deleted it by mistake (closed the browser without saving the changes )
In the last entry I commented about the massive data ammounts that the Midpoint Displacement's Inverse process needed as it was on the paper, so I decided to try the recursive approach I found on another version of the paper. I was going to discuss why the previous method needed so much data but I forgot exactly what I was going to say (had a draft of only one paragraph) and I'm not looking forward to delve into that code again so I'll just jump over the issue completely.
Forever a Point
So, Midpoint Displacement's Inverse. This process comes from the idea that a Midpoint Displacement algorithm (which isn't the same as a Diamond-Square algorithm) result depends on the height data generated by the previous iterations of the same algorithm. Thus, each set of new points depend (more or less) on the points that preceded them.
With that in mind there could exist a MD algorithm that is aware of already existing data. The paper achieves this by having two arrays: One with the height data and the other with the state of each height value. There are various states that each point can have (river, ridge, done, null) but the most important part is differentiating between those already computed (river, ridge, done) and those that need to be computed (null).
I don't know exactly how the paper achieves this "awareness" but its probably with a check before calculating each point. If the state at (x,y) is NULL, then calculate the point normally, if it isn't null, then leave it as it is.
For simplicity I used a map with only ridge lines traced on it to begin the process:
The state checks alone won't give you good results:
You can see that the MD algorithm sort-of adapts to the ridge lines in some places but rapidly loses track and it gets ugly.
Inverse or Reverse?
To solve these issues, the paper introduces the Midpoint Displacement's Inverse process. It is an algorithm that steps through the data and places height values where the MD algorithm expects them and that make sense in the context of the present pre-computed data. That way the MD algorithm has more data to work with and can adapt better to the main features of the terrain. You can check it out on the alternate version of the paper that I found.
There are a few parts of the paper algorithm that I don't understand, for example:
if nns>0 then; • a ←for each corner of square in DEM: the altitude average of all non-NUL cordinates; • for each corner (l, m)of square with a NULL coordinate: –altitude(CDEM[l][m])←a + s * ur() –state(CDEM[l][m])←DONE;nns is the counter of non null states. That means, if we have at least one corner pre calculated in our square, make a rough assumption about the heights of the other corners. DEM is digital elevation model, your run off the mill heightmap. And ur() is an uniform random value between -1.0f and 1.0f. s is the current stepping of the MDI iteration and the square represents the subarea where we're working on.
Now, that "for each corner of square in DEM: the altitude average of all non-NULL cordinates" is kinda weird. I *think* it means that I have to average all the height values of the known corners. (ie, (corner1+corner2)/2 ) but I'm not sure.
Then, the next part I just don't have any idea what it means. "For each corner (1,m) of square" ? Where the "m" comes from? Why the constant 1? I guessed that it means that for each corner that has a null state, calculate it with the average of the non-null corners like it says in "a + s * ur()". Then set the state of that coordinate as DONE. But its just a guess based on what I'd expect it to do, I honestly have no idea what that "corner (1,m)" means.
Artifacts in my soup!
I half expected it to burst into flames, but alas it kinda worked. Not only it wasn't awfully slow like my last attempt (70ms against like whole seconds for a 513^2 map), but it worked better, still ugly, but better:
You can see that the algorithm adapts way more to the ridge lines than before, misses a lot of terrain and has weird points around. I'm thinking I have issues with the sub-square sizes. This result is actually after arbitrarily creating each subsquare with square.width = stepping + 1. This is what happens if I leave it as square.width = stepping (like the paper suggests), albeit with a different base ridge network:
And this is what happens when I leave it as square.width = stepping - 1
I know the artifacts on the first image since I had them while implementing a regular MD algorithm, I was sizing my subsquares with a width off by 1. That's why the white points are spaced by long black lines. Now for the second image I have no idea what is going on. Probably missing all the corners or most of them, so barely any new point gets generated.
And the moral of the story is...
I'll try to find out what's happening with the squares. I'm pretty sure its some width/height/range issue. Maybe I'll attach some code next time (though I hope to have it complete and "readable" someday). Until then, have a good night!