The third time is the...
So, I decided to implement the algorithm in the paper pretty much literally, without paying much attention to what actually its doing (besides a major issue I did notice).
In short, my implementation doesn't works, height points get generated but the midpoint displacement pass fails to create anything useable.
I did notice that the algorithm as it stands on the paper, uses an awful amount of memory. It has to store the "parent" points (usually 2 to 4) for each of the height values of the map (I'll explain what a parent point is in another journal entry). For a 512x512 is no problem, but for a 4k heightmap you can get 100 million (or more) objects jumping around, which isn't nice at all.
You could use plain arrays and do some index calculations instead but it still is an awful amount of height points to store.
Not everything is lost
Turns out I didn't paid attention at all to the other version of the paper I had (or maybe I just didn't knew what it was doing at the time) but it has the pseudocode of a much nicer way to go about the midpoint displacement inverse process. It is recursive, so it might produce a stack overflow but an iterative approach should be doable if I can wrap my head around the algorithm (which means, wish me luck :P ).
And that's it for now. See you next time! :D