@Enzio599
What Joel posted is very nice. actually. It's on the GPU which makes it fast. One possible downside to GPU stuff is you might have to send data back from the GPU to do physics and/or collision.
Here I'm doing terrain on the CPU. This is not technically terrain since it's just a sphere but it does have LOD and chunking as you can see. The algorithm actually accepts heights. I simply didn't need them here because it's a sun. I'm using equilateral (ish) triangles since it gives more even triangles on a sphere, and a bit less directional bias to meshes. This is at to the cost of a bit more complexity to the algorithm. For flat land it's probably not worth it
https://www.youtube.com/watch?v=oRO1IGcWIwg
Here I'm doing voxel terrain again on the CPU. This is using marching prisms which is akin the marching cubes. This version is somewhat more advanced as it supports LOD, octrees, chunking, threading and so forth. Again this is working on a sphere since I'm doing planets. At this point I'm only feeding it height data but this supports fully 3D data with caves and the like. It's not as fast as the GUP stuff you often see, but it's pretty versatile and it leaves the GPU free for graphics (which may or may not mean much). It depends on how fast you want to travel. At walking or even driving speeds it's still plenty fast. If you want to zoom by you terrain at high speed and have it do LOD super fast, a GPU solution might be better.
https://www.youtube.com/watch?v=G7LzzBcO8mQ
Something like what Joel posted might be a good solution for you. Before going forward, I would think about how you want to do physics. Traditionally that's been done on the CPU but I've seen a lot of GPU solutions. If you are going to do physics on the CPU you will have to have mesh data available there also.
Also keep in mind when you talk about “very large” terrain there is a limit to floating point accuracy that's available. Beyond like 12 km from the origin you will start to lose millimeter accuracy and it gets progressively worse from there. To make this work with single precision floating point you will need to do some sort of coordinate rebasing. I'm doing things in double precision on the CPU side and then keeping the origin near the camera on the GPU, but most game engines don't support that so it can be an issue.
As for “holes” in terrain, a lot depends on the rest of your code. I'm generating terrain directly from functions but if you are generating meshes ahead of time you have the option of hand editing your terrain the way you want it. With something doing runtime procedural height mapped terrain, adding holes is probably more tricky.
Bottom line is I don't think their is a “best” way to do any of this stuff. It really depends on the end product you are targeting. A walking sim is not the same as a flight simulator.
