# Terrain generation

This topic is 1817 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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".

##### Share on other sites

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.

Perlin noise itself isn't very interesting.

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.:

FBM:  https://sites.google.com/site/jicenospam/hill_fbm.png (this is what libnoise samples usually show, note that it is NOT perlin noise, but a derivative of such)

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.

##### Share on other sites

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.

Thank you.

##### Share on other sites

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.

##### Share on other sites

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?

##### Share on other sites
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.)

##### Share on other sites
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.

##### Share on other sites

Here is what I have done before:

-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.

##### Share on other sites

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.

##### Share on other sites

That makes sense. I think I understand how to make the quad-tree....

Basically, I create several planes of varying complexity and adjust the Y-values of the vertices according to the elevation of the spot it is on. I would need to make a routine to render only the ones in view (this will be first person).

BTW, do you have a good quad-tree tutorial?

Edited by Hawkblood

##### Share on other sites
I kind of second FLeBlanc's recommendation against a quad-tree here. You can get it to work, and it's not really as hard as he makes it out to be, but I'm not sure it's really the right abstraction to use for this. In my experiments in the past, I ended up with a lot more overhead and complexity for the tree management and visibility determination than I felt was really necessary.

If you use a spatial hash, you could even go with something as simple as:
std::map<std::pair<int,int>, TerrainBlock> blocks;

for your map structure. Then if your camera view is centered upon some location, (X,Y) it is a simple matter to find which TerrainBlock (X,Y) resides within, construct a std::pair<int,int>(BlockX,BlockY) from the block coordinates to index into the map and obtain the TerrainBlock, then compute a rectangle of blocks surrounding this central block as the visible area, size of the rectangle decided by your maximum view distance. As the center viewpoint moves, you simply re-calculate this visible area, load TerrainBlocks that need to be loaded for the new area, and discard TerrainBlocks that are no longer within the visible area. I have implemented infinitely sized outdoor areas this way before, and it does work well; plus the coding was far less complex than quad-tree management.

##### Share on other sites

I kind of second FLeBlanc's recommendation against a quad-tree here. You can get it to work, and it's not really as hard as he makes it out to be, but I'm not sure it's really the right abstraction to use for this. In my experiments in the past, I ended up with a lot more overhead and complexity for the tree management and visibility determination than I felt was really necessary.

The only problem I see with this is that in order to have large viewing distances the number of blocks you'll need to draw will grow quite fast (much faster than a quad tree). From stuff I tested, the limiting factor then becomes not the actual polygon drawing time, but the number of blocks you need to iterate over, plus the number of view frustum tests you need to run on single blocks.

True, for a small enough viewing distance this won't be an issue (small enough being again, determined by how large you make your blocks, since the larger your blocks the less of them you'll have for a given view distance), but overall, a quadtree will be able to handle larger viewing distances much better than a block map/array.

I definitely agree with you on the complexity of the code though - quad trees can become a slight pain to manage correctly. In my eyes its a tradeoff between simplicity of code and having a really large viewing distance - so if you don't need to have large viewing distances, don't bother with quad trees. If you do want large viewing distance and you don't mind more complex code, quad trees :)

##### Share on other sites

Isn't it better to use Simplex noise instead of Perlin noise? That is, Simplex noise is faster? I have only used Simplex, so I don't know for sure.

I organize blocks into chunks of 32x32x32 blocks. The chunks are then organized in a map<>, just as JTippetts suggested above. The chunks are transformed into a structure better suited for drawing. That is, all faces that may be visible are identified and ordered together with other faces of the same material.

I use 3D simplex to create caves and overhang.

Sure, there certainly will be quite a lot of data. Even with advanced culling, you may end up with quite a lot of vertices per frame. This is a disadvantage of a voxel based worlds.

I am not sure how a quadtree would help you. It is very efficient when you want to find what other objects are near, as the cost doesn't grow quadratically. But if you just need to know what objects are inside the view frustum, the map<> should suffice?

##### Share on other sites

I feel I need to give everyone a better idea of what I have and what I want.....

My current project is a multi-aspect simulator, if that makes sense.... It has space flight, landing sequences for planets, classic first person, and driving a rover. All views are first person/cockpit view. I am trying to make this game with absolutely NO transitions-- that is to say, the player can fly through a solar system, orbit a planet and then land on it, get out of the ship and walk around. All of this without load screens, pauses, or any other type of transition. The way I would do this is to take the "generation" parts and call them in small chunks instead of all at once. This way, the frame rate suffers as little as possible while still generating what's next.

I currently have a large star cluster for the player to explore. Each system will generate as the player is in FTL enroute-- I know. This sounds like a transition, but I want the player to feel as if he is actually on a starship, so it works here. Each planet of the system has a unique texture (hopefuly) and atmosphere generated by perlin noise. Once in a system, the player can go to any planet and orbit it. Once in orbit, the player can select a landing site and begin the landing sequence.

This is what I need to accomplish:

Generate the landing area in a progressive maner.

Split it up in some way to make it managable.

Have high detail up close and low detail far away.

I would like to make it possible for the player to completely traverse the planet and look at every rock and tree without transition...... I have ideas on how to do this, but I don't want to re-invent the wheel.

As larspensjo said, perlin noise is slow. So far, it's the only thing I have been able to get to work. If someone has simplex in C++ with no frills and a simple implimentation example, I would love to look at it. I have looked at some simplex code and each time I got a bunch of junk!

By the way, is this a good place to post "work in progress" or is there another forum for that?

##### Share on other sites

The site from where the video of the first post comes from is called http://sea-of-memes.com

That guy uses a quadtree for dynamic lod., here is the post related to the video http://sea-of-memes.com/LetsCode28/LetsCode28.html

You can check the sources (C++) for his implementation.

Edited by TheChubu

##### Share on other sites

If someone has simplex in C++ with no frills and a simple implimentation example, I would love to look at it. I have looked at some simplex code and each time I got a bunch of junk!

I am using simplexnoise1234.h and simplexnoise1234.cpp. I haven't analyzed it much, but I think it is rather efficient.

I would like to make it possible for the player to completely traverse the planet and look at every rock and tree without transition...... I have ideas on how to do this, but I don't want to re-invent the wheel.

It i possible, I am doing it, based on voxel data. The world is infinite (kind of). Instead of planets, though, I have "flying islands". But it would be easy to increase the distances between the islands.

But I have split it up into a server and a client, to allow many players to explore the same universe at the same time.

What I am not using yet, is a LOD functionality. The block resolution is 0.5m, but special objects can have higher resolutions. Edited by larspensjo

##### Share on other sites

I haven't analyzed it much, but I think it is rather efficient.

So, you've used it? How do I generate 3D noise so that it can wrap around a sphere?
Edited by Hawkblood

##### Share on other sites

I haven't analyzed it much, but I think it is rather efficient.

So, you've used it? How do I generate 3D noise so that it can wrap around a sphere?

There you got me, sorry! I use it, but only on a flat world (though with infinite height).

I admit I don't know how to apply the simplex/perlin noise function to spherical objects. I wonder if it would be possible to make transformation from polar coordinates to rectangular, without have singularities at the poles or non constant resolution.

One common way to do this is to use a "cube map", which is really just 6 rectangles stitched together into a cube. The height map from these would need to be adjusted by the average radius of the sphere, which should not be hard. There are some disadvantages with this is that there will be a discontinuity between any of the 6 adjacent rectangles. The resolution will also be slightly different at the edges and corners of the cube map (with a factor of sqrt(3)=1.73 in the corners). This non linear resolution should be possible to compensate for, I think?

##### Share on other sites

I've been trying to upload an image to this post with no luck. Here is a link for it:

As you can see, the top has less quality than the bottom. The top is done with simplex, while the bottom is done with perlin. How do I get better quality with simples?

It is notable that simples is about 2x faster than perlin.....

##### Share on other sites

Looks like your top only has a single octave of noise, while the bottom has multiple octaves. You can stack octaves of simplex noise just like you do with Perlin gradient noise to get more detail.

To wrap Perlin noise around a sphere, you can generate a sphere then use the 3D (x,y,z) coordinates of each face to evaluate a 3D noise function. Here is an example:

Create a cube and subdivide it using Catmull Rom subdivision. This has the effect of A) Rounding the cube toward a spherical shape and B) Providing you with regular quad faces, though there is some distortion at the places where the cube corners were subdivided.

Use the geometry of the sphere to evaluate a 3D noise function:

You can see that the noise is distributed smoothly across the surface of the sphere.

Now, use the generated noise to displace the surface of the sphere:

To do a progressive LoD scheme from orbit to landing, I would probably go with something like this:

1) Use sub-divided cubes of progressively denser tesselation:

2) At some point during de-orbit, when the planet is near enough that the mesh will be pretty dense, switch from a subdivided cube to a subdivided plane whose verts are mapped according to the section of the cube it is derived from. When this switch takes place is subject to experimentation. This process, again, could use multiple levels of subdivision as the lander draws nearer the ground.

During this process, the noise function can be adjusted based on distance, as well as adjusting the tesselation of the mesh. From a long way away, the number of octaves can be adjusted downward so that the function evaluates more quickly, since the majority of the smaller detail won't be noticeable and, in fact, can cause aliasing artifacts. As the planet draws nearer, more and more detail is revealed so at the same time that the visible area becomes restricted to a smaller and smaller piece of the globe, the detail of the noise function generating it becomes greater.

Now, this is not really a trivial thing you are doing here. If you are worried about performance from your noise fractal now, wait until you see how slow it becomes when you try to do things such as add terrain variations, as well as constructing it so that it can provide the detail needed for the final ground-level surface. You are going to need to build a decent background thread process that can generate the LoD levels in the background, and it's going to have to be pretty optimized. It can be done (look at Outerra ) but it is not a simple task at all. I think you would be well served to gain some solid experience with simpler terrain projects first, to learn the basic techniques you will need in order to complete the larger project.

Note that I still don't think a quadtree is appropriate; even more-so now, since if you want the player to be able to explore the entire planet (and not just some abstract, flat, infinite plane of terrain) then your terrain chunks will have to accept some level of distortion to preserve the curvature of the sphere, and this just wouldn't play well with the neat, tidy subdivision of a quadtree. Look at the faces in those subdivided cubes; some are relatively neat and square, while others are distorted. Since there is no way to tesselate a sphere with quads that are non-distorted, then I just don't think a quadtree would be appropriate.