20 replies to this topic

[Hawkblood]

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

[Milcho]

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:

http://www.youtube.com/watch?v=-K8QNpzgKUY

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

The article I used when I was starting this was this: http://http.developer.nvidia.com/GPUGems3/gpugems3_ch01.html

An example: 

 

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.

[SeraphLance]

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.

 

http://upload.wikimedia.org/wikipedia/commons/d/da/Perlin_noise.jpg

 

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)

 

Hybrid Multifractal:  http://www.dragonheadstudio.com/htc/tutorial9.jpg

 

Ridged Multifractal:  http://www.neilblevins.com/cg_education/procedural_noise/musgrave_ridged_turbulent3.jpg

 

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.

[Hawkblood]

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.

[FLeBlanc]

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.

[Hawkblood]

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?

[FLeBlanc]

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

[Waterlimon]

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.

[Hawkblood]

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.

[Milcho]

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.

[Hawkblood]

@Milcho

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, 25 January 2013 - 08:02 AM.

[JTippetts]

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.

[Milcho]

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.

[snipped for ease of reading]

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

[larspensjo]

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?

[Hawkblood]

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?

[TheChubu]

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, 26 January 2013 - 01:14 AM.

[larspensjo]

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, 26 January 2013 - 02:50 AM.

[Hawkblood]

 

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, 26 January 2013 - 04:51 AM.

[larspensjo]

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?

[Hawkblood]

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

https://docs.google.com/file/d/0BySKIgkx3OcbQUNsZkNLSlljcXc/edit

 

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