First, I'm new to this forum, but not new to C++ or DirectX9. I've tried searching the topic of how to generate terrain, but didn't find anything I thought was useful for these specific parameters:
-fast generation
-contenuous (moves with the player so there is no spacial limit)
-detailed up close, low-poly at distance, and smooth transition between.
I've come up with some ideas, but I would like to know if there is anyone here that knows how the experts do it.....
I think my ideas would be slower than methods used by "the industry".
The answer depends on the kind of terrain features you want.
Either case, my first thought was to use Perlin noise, but that may be because that's what I used on my previous project which was essentially a procedural terrain generator.
If you don't need to have overhangs or caves generated, you can use a 2D perlin noise function over a flat grid. Perlin noise usually returns a [-1, 1] value, which you can then scale and transform to your needs to determine how you set mountains, plains, lakes, etc. There's a noise library and corresponding tutorial here: http://libnoise.sourceforge.net/tutorials/tutorial4.html - but that's just one of the many, just google "perlin noise terrain", you'll get a lot of results.
A standard method to make continuous terrain as your move around is to use a quad-tree. There's a nice visual representation of quad trees in action here:
">
- but again, it's far from the only tutorial/demo online, you should be able to find dozens of these online.
Advantages of heightmap
- Fast (samples only grow quadratically as you increase visible terrain)
- Easier to make smooth transitions - there's not so hard to learn and well described known ways to have different Level Of Detail quadtrees blend together without holes in them
Disadvantages:
- No Caves or Overhangs possible
Another way, which I used for my old project, is to take 3D perlin noise, and generate terrain from that. This involves sampling a perlin noise function over a 3d space (not just a flat 2d grid as with heightmaps). It gives you a bit more control, and also a lot more variation too, since you can have bumps, overhangs, caves and the likes easily. The samples from the 3d noise function can be used to construct a mesh using the Marching Cubes algorithm.
This describes terrain on the GPU, which has advantages, but it's also doable entirely on the CPU as well, though slower. Using libnoise and smart construction of the marching cubes, I had some fairly good results (look at my journal here on gamedev for some of them). The problems with using 3d noise is speed and the difficulty in producing meshes at multiple levels of detail that go together without holes inbetween them. The GPU Gems site suggests a way to overcome this, however I think their method is inefficient as it draws the same terrain multiple times at different LOD.
Advantages:
- Caves, Overhangs, more detail
Disadvantages:
- Slower, number of samples grows cubically in worst case, unless you impose artificial limits to height.
- Harder to produce smooth transitions between different LOD terrain meshes - there's a lot of approaches I've read, none solve this perfectly for me.
Both of the above methods can give you incredibly fine detail up-close, if set up correctly.
This is just terrain generation using perlin noise, which is what I'm familiar with. There are other methods to do this, which involve more numeric approach (as opposed to analytical functions), where you generate simple terrain and iterate over it, deforming it with each pass, to produce the desired features. This is again done through automated functions, and it can give some more control in what you want to generate and where, however it won't be able to generate extreme closeup details by itself. I'm also not sure how this approach would work with different LOD since it usually requires a full-resolution terrain to work properly. I only have a passing familiarity with these methods, I'm sure someone else will describe this better.
perlin Noise (and associated fractals) is the canonical way of doing this. Basially, it generates a continous (i.e. smooth) surface at whatever coordinate you give the algorithm. Zooming in and out is just a matter of giving it more accurate coordinates, say... 1.25 between 1.0 and 1.5. The point will be exactly between the neighbors on the contour of the surface.
As you can see, it kinda looks like the noise you get off a TV, but blurry. More interesting is when you use the output of Perlin Noise as a basis function for various fractals, e.g.:
Once you have these constituent fractals, you can mix and match them with basic math functions as you please. There's a wealth of other things you can do too, but this is just a topical overview.
Thank you both for replying. The method for generating the "heights" for the mesh/meshes is one issue. I think I'll use perlin noise, but I have tried to use it without success. I have a method for generating the height values already, but it's slow. The quad-tree method is what is more pressing at the moment. I don't even know how it's done.... I understand the concept, but how to impliment it eludes me. Is it a single mesh or is it multiple meshes that are placed together? I'll look at the libnoise article, but I need to know how the quad-tree is done.
You will probably want to use multiple meshes placed adjacent to one another. For lower LOD chunks, you can use a lower res block of samples plus a skirt to hide the cracks between seams.
Perlin noise fractals are ideally suited for this kind of on-the-fly generation, because in order to get a lower detail terrain (and incidentally one that will generate more quickly) you simply reduce the octave count of the fractal. So for example, if the largest block size is MxM, and the next LOD level down is a block M/2xMx2, then you can generate the first one using, say, 8 octaves and the second LOD level using 4 octaves.
If you are going with a large or practically infinite terrain, then I would recommend against using a quadtree. The basic quadtree takes a finite, bounded volume and splits it recursively into 2x2 sections, which doesn't extend well to an infinite sized volume. Instead, I would use something like a spatial hash where blocks are indexed using a BlockX, BlockY pair that is hashed to find the "bucket" in which that terrain block lives. Block coordinates can be negative and practically infinite (if a large enough precision type is used for the coordinate pair) and you can easily draw a "chunk" of blocks centered at some given coordinate to implement your moving window into the world. You can also easily implement streaming and discarding of blocks as they come into or go out of a larger "active" window on the world.
Thank you FLeBlanc. I've used that method before, but I thought a better method was out there. Are you sure the quad-tree method has those limitations you described?
Thank you FLeBlanc. I've used that method before, but I thought a better method was out there. Are you sure the quad-tree method has those limitations you described?
Yes. In order to represent an infinite terrain your quadtree needs to be infinitely sized; that means, the top-level node has to be infinite. Let's say you go with just "really large" For example, say your standard terrain chunk is 16x16 meters, and you want to represent an area 1km x 1km in size. That equates to a tree 7 levels deep; ie, the root node would be a node 1024x1024 meters in size, the next level down would be 4 nodes each sized 512x512 meters, next would be 16 nodes sized 256x256, and so on until the leaf level would comprise 4096 nodes each sized 16x16. That is for a mere square kilometer.
To represent an area the size of, say, Nebraska you would be looking at an area that is 512km on a side, or 524288 meters to a side on the root node, and the tree would be 16 levels deep. That's getting into crazy territory if you are doing recursive culling and such.
Additionally, this assumes that you do bound the player to some finite area, that area being the size of the root node. If you are not bounding the player, then you have no way of calculating the size of the root node, so your only recourse is to hack some sort of collection of quadtrees. You can always grow a tree downward from the root, but growing upward from the root is trickier. And if you do manage to figure out a scheme for growing your quadtree infinitely upward, you then face the problem that any search of the tree (for culling or other purposes) is going to increase in overall complexity the further the player explores. If the player stays close to spawn, searches will be fast since the tree won't have grown very deep. But if he hops on a horse and tears ass across the country to the other side, your tree is going to grow quickly and search complexity will correspondingly grow as well.
On the other hand, if you use a spatial hash then it doesn't matter how large the area is. There is no requirement for setting bounds, and search complexity will not grow with explored area size. Complexity will be exactly the same for a small world as for a huge one (minus some basically trivial bookkeeping depending on the spatial hash implementation.)
You can use a quadtree by:
-Add a new root node when you need more area (or just make it 32 layers to start with to match integer positions range)
-Never traverse the whole tree (well youll need to do that sometimes but not for every access). You should know what branch(es) you are currently working in.
-You could use a tree with a higher branching rate. lets say 4*4 children per node. That would make it not so deep.
-had a HUGE, low-poly, scaled mesh of the entire terrain (the absolute maximum the player could explore).
-had 25x25 "blocks" of 100mX100m each placed over the huge terrain.
-as the player moved from one block to another, the blocks would shift in the opposite direction. The blocks at the far edge opposite the direction of travel would be repositioned to the front and reused as the new terrain blocks.
Of course I will have an absolute max distance of where the player can go, but I don't want it to be practical or desirable for the player to go there. So, I want the area to be huge.
Of course I will have an absolute max distance of where the player can go, but I don't want it to be practical or desirable for the player to go there. So, I want the area to be huge.
Why do you limit your area like that?
Infinite terrain doesn't have to be displayed all at once - see how the video I posted originally handles it.
You can have a 3x3 grid of big blocks (you can make the grid 5x5 or 7x7 etc). Each time the player changes which one of these 'big blocks' he's in, the blocks are re-organized such that the new block the player is in, is the center one again. I thought this was pretty well illustrated from the video, so I can't really give a better illustration.
Then, for getting more fine detail, you basically subdivide each big block depending on how close the player is to it. Once you subdivide, you no longer draw the low-res terrain, but instead draw the resulting 4 smaller blocks.
After that you run the same sub-division on the resulting smaller blocks, until:
a) either the player is too far away from the block so it doesn't need to be subdivided (this 'too far' should be a function of the block size - i.e. if the block is 32x32m, then 'too far' could be more than 32m away from the block's side, but if the block is 8x8m, then 'too far' is going to be 8m away from the block's side),
b) or your block's resolution is small enough that you don't need to subdivide anymore. By that I mean that if your block size becomes 8x8m and you're doing 8x8 samples, your resolution will be 1m. If that's good enough for you, then stop there. if it isn't, then subdivide the 8x8 block again, so now you have a 4x4m block that has 8x8 sampls, so your resolution will be 0.5m, giving you even more fine terrain.
Of course, your terrain function must be specifying fine enough details for smaller resolutions, because if its not, your 0.5m resolution block will look exactly the same as your 1m resolution block, only use up more triangles. If using perlin noise, you just have to make sure you add noise with small enough frequency to give some definition at 0.5m.
