Archived

This topic is now archived and is closed to further replies.

marijnh

on-the-fly procedural terrain

Recommended Posts

I have been trying to create a heightmap-like terrain rendering system that uses a procedural approach without caching the heights. This has the advantage that it does not require any memory and that you can take any floating-point coordinates you want and get the exact height. This makes lod-reduction for faraway terrain much more straightforward. I use a basic grid aligned to the camera, nearby i use a lot of triangles and far-off i use little. I do run into a bunch of problems though: - Performance of generating the heights. I am using a perlin-noise at the moment, and it is way too slow. I optimized it pretty well i think, but i have to use a ridiculously low-resolution (big triangles) to get decent performance. Can anyone recommend a faster, but still realistic-looking method? I''ve been messing around with combined sinuses but that didn''t produce satisfactory results. - Popping. This probably has something to do with the fact that i use big triangles, but when the camera moves the landscape seems to deform slightly. Ugly. - Texturing. I haven''t even started on this, but any hints on coherently texturing the geometry created would be very welcome. Has anyone implemented such a system? Any source code available? Marijn

Share this post


Link to post
Share on other sites
I''m working on a planet engine at the moment, and i''ve been implementing pretty much all you''ve described a few weeks ago. You can have a look at the procedural planet thread, on this same board, which is quite recent. Should be on the bottom of this page, or on the second page.

- Performance: i''m using 12 octaves of ridged Perlin noise, and i found it runs at around 60k samples per second on a P4-2 Ghz. If you have a high amount of vertices/triangles (i have up to 64k for my terrain), this can quickly become tricky. I found that, at low speeds, performance was ok, because the LOD system only evaluates the height for a small number of new vertices; but at high camera speeds the number of new vertices increases too much. I solved that issue by using a priority queue. Each terrain patch is given a priority, mostly depending on the distance to the camera. Each frame, a max amount of time is allowed to regenerate new vertices (10 ms in my current implementation). That way, your framerate goes down, but never too low, and the whole heights generation is spreaded over many frames. This obviously makes popping even worse than what it was before, so you need a good way to reduce popping.

- Popping: was very tricky. Not sure if i can help, it depends on the LOD system you''re using. Basically you have no choice rather than making your hands dirty, and code the whole thing. I have a queue for vertices currently morphed, and for each vertex i keep the original position, the final position, and a time parameter which is used as the linear interpolation parameter. This makes my morphing only dependant on time, however the time parameter is updated depending on the camera speed (at high speeds, morphing is done faster) so it''s not too noticeable.

- Texturing: i''m using per-vertex blending; i''ve got different layers (grass, rock..) and for each vertex i calculate the % of grass, % of rock, etc.. It doesn''t mix well with high altitudes, because the number of triangles becomes too low to have good details. I''m working on a mix, with unique, photo-realistic textures for high altitudes, blended with the per-vertex blending for lower altitudes. I''ll also implement a form of detail texturing for very low (ground-level) altitudes.

- Other considerations: lighting; or more generally, finding the normal to a vertex. The brute approach would be, instead of using perlin-noise to generate one height per vertex, to generate 3 or 5, but it quickly kills your performance. I improved it by reusing the heights of neighbooring terrain patches, but this was a nightmare to code. I have to improve that as well, because i still get some artifacts, from the fact that, when splitting a terrain patch, i reuse as much as possible the vertices from the parent patch for its children. One consequence is that vertices from the root patch of the tree are being reused in the leaves, and the normal is no longer correct (neighboors vertices have changed).

Y.

Share this post


Link to post
Share on other sites
I see. I haven''t properly read that whole thread but i plan to. Could you maybe give the code or a description of the code you use to generate the perlin noise? (I don''t think it is in the planet rendering thread) Since my plan was to not cache *any* heights between frames i''ll need to generate huge amounts of heights, so any ideas for speedy noise are welcome.
I might go back to a buffered approach if i don''t find a fast enough way, but i think this on-the-fly thing would be nice if i got it working.

Marijn

Share this post


Link to post
Share on other sites
Not to cache any heights between frames ? I''d say you''re crazy, but that''s just me Tom Nuydens, from delphi3d.net, has made a small perlin noise class in Delphi (easily portable to C/C++) that is quite optimized. You can get it here:

http://www.delphi3d.net/download/perlin.zip

Then i''m using that for my base function:


  
///

/// Ridged perlin noise

///

TFloat CProcedural::ridgedPerlinNoise(SVec3D a_pos)
{
TFloat r = perlinNoise(a_pos);
if (r < 0)
r = -r;
return(1 - r);
}


That''s a small modification, but it gives better results for mountains.

Y.

Share this post


Link to post
Share on other sites
The reason i did not want to cache is that that way i can sample the terrain at any point i want during the rendering phase. The idea was to have the (x, z) grid of sample points decided by the camera position, and then go through those points adding an y-coordinate based on the noise. I am getting more and more convinced this wont be fast enough though... unless i find some brilliantly fast noise method.

Marijn

Share this post


Link to post
Share on other sites
A brilliant idea technically - lose the huge memory usage! Replace it with on-the-fly generation! Do it on the GPU if possible.

Unfortunately, this is completely useless outside of the "cute tech demo" target application. The reason? Zero level design. Of course, you can pile layer upon layer of "guided random generators" and "procedural noise" etc., but this rapidly approaches the complexity of the traditional draw-it-offline-into-a-heightfield method.

On our last project, we spent a lot of time (read: several months) attempting to create a "decent" random map generator. We did multiple perlins. We recombined them with almost arbitrary operations. We introduced noise-augmented templates ("a mountain ridge approximately here, and a squarish lake next to it"). We fiddled with the coefficients for weeks.

The results, while not too bad when viewed in isolation, were completely blown away by what the level designers did with a few simple tools in the editor.

Share this post


Link to post
Share on other sites
I got your idea Marijn, actually i used this technic a while ago when doing ocean rendering. It was basically a circular grid surrounding the viewer (kindda like a skybox) displaced by animated perlin noise, to simulate animated waves. You get LOD & morphing for free. The drawback is, you have to regenerate all the heights values for each frame. Might be acceptable if you go for a small amount of octaves (3 or 4), and a low number of vertices (like 2000). For more complex terrains, the performance would dramatically drop i think.

Assen: you''re right, designers can always do better than computer-generated scenes. However, it''s not always possible, if you''ve got a terrain the size of a country (or planet)..

Y.

Share this post


Link to post
Share on other sites
quote:
Original post by Ysaneya
Assen: you''re right, designers can always do better than computer-generated scenes. However, it''s not always possible, if you''ve got a terrain the size of a country (or planet)..



Terrain the size of a country (or planet) with meter-resolution is again within the "nice tech demo" realm, not a game.

You can''t do without the level designer data - you''ll need a mountain here, and lakes there, and some rolling hills around.

So I think the procedural generation (or rather, augmentation with noise of the crude, large-scale painting by the artists) should be done offline, and the memory problem should be solved by some kind of compression/streaming scheme.

Maybe get the lowest octaves from an artist-drawn large scale map, in a compressed form; higher octaves are either generated on the fly, from a stored seed, or overriden with local artist-drawn patches - for e.g. cities where even the most detailed level of the terrain relief needs to be exactly specified.

But again, from a game design point of view, one can argue that the game should happen only in places touched by the hand of a designer. You have city A, designed by a human, you have city B, designed by a human, and you want to insert between them 1 hour of mindless bashing of hordes of random-generated monsters on boring random-generated rolling hills with random-planted trees. Isn''t that a fault in your design? Aren''t you telling the player "now please spend 1 hour without much effort on my part while I go get a nap"?

Share this post


Link to post
Share on other sites
I think computer generated terrain is fine for a flight sim or something similar. Although I prefer to use a user defined list of functions that mould the general shape of the terrain followed by some Perlin noise over the top. Using the user defined functions the Perlin noise can be controlled, eg flattened. It''s all a case of getting the right functions in the right order. I''ve never got round to fully implementing it. The functions I''ve used have always been hardcoded in and the terrain rendered using brute force, which is not suitable for the application of the terrain I wanted.

A function based terrain editor could easily be produced and could allow a lot shapes and patterns. The only thing it falls down on is sharp edges. But for a flight sim this is not important.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Original post by assen

Terrain the size of a country (or planet) with meter-resolution is again within the "nice tech demo" realm, not a game.

Unless you''re making some sort of a simulator and use actual DEM data to have your earth resemble the real thing...

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
Unless you''re making some sort of a simulator and use actual DEM data to have your earth resemble the real thing...


Using actual DEM data is as far as it gets from procedural generation.

Share this post


Link to post
Share on other sites
In my current project, I use Bezier patches to define the general shape of the terrain over a 32m x 32m patch in only 16 floats. To give it a rougher shape I then overlay a few octaves of Perlin noise.

By manipulating bezier patch points you can get almost any shape terrain you want, and you can tessellate it to whatever detail you desire.

Performance wise it''s not too bad: the Bezier patch evaluation can be simplified to 4x4 matrix-vector multiplication with a couple of additional mults. With general shape defined by the bezier, you don''t need that many octaves of noise: I currently use 3 iirc, so thats not much of an issue either.

The problem is, as somebody mentioned, that a fast moving viewpoint causes bucketloads of new verts to be generated. This drives the framerate down, which in turn means the camera moves further between frames, leading to *even more* vert calculations next frame: It''s a horrible negative feedback loop. I''ll have look into the priority idea mentioned above.

Share this post


Link to post
Share on other sites
quote:

Terrain the size of a country (or planet) with meter-resolution is again within the "nice tech demo" realm, not a game.



It''s not common, but i wouldn''t go as far as saying it''s not possible in a game. Granted, DEM data is not procedural generation, but nothing prevents you from mixing DEM data for high-level data (kilometer data) and procedural data for smaller details.

Elite 2: Frontier and First Encounters had a procedural universe, with complete planets on which you can land, back in 1993. Ten years have elapsed since, why isn''t there more games with such a scale ? Games like Freelancer, or Earth & Beyond, just look so ridiculous with their sphere-like planets !

Y.

Share this post


Link to post
Share on other sites
assen: Never say never
The adequacy of random terrain varies for different types of game. I admit that at the moment my project is in the ''funny demo'' state, but i have a vague idea of a game in a more or less completely randomized world. I''ll experiment with tweaking the generator, and when i have something i like i''ll place a few settlements and other entities on top of the random world. The hugeness of the world will be an important aspect of the game. There will an area that i have inspected and slightly modified where most of the game takes place, but it will be situated in an effectively infinite world, and this huge ''wilderness'' will be used in the game.
Does anyone have any information on how the terrain for Delta Force I was generated? That was infinite, and i think they used the method i descrbed above (although i plan to make trees part of the randomness, while their trees were all hand-placed).

Marijn

Share this post


Link to post
Share on other sites
Assen, I think you need to be careful when making such sweeping statements. Obviously, whether an entirely computer generated terrain is useful or not will depend on the type of game you''re making. Even if you didn''t need huge (and by huge I mean virtually infinite) terrains, for example in a standard large-scale online FPS like Battlefield 1942, I''d still consider computer generated maps a valuable feature.

With computer generated terrain, you''ll lose direct control over the details, of course, and time and energy spent on creating and configuring the terrain generator, but you''ll gain so much more, in my opinion, not least of which the *freedom* of *not* having direct control over the details. That *should* appeal to hobbyists. Personally, I''m glad to be rid of another burden that threatens the completion of my game. If I need a "mountain here, and lakes there, and some rollings hills around," I''ll simply go find them. They''re bound to be somewhere this side of infinity.

Personally, I have found my own computer generated terrains perfectly adequate. What I lose in quality in the details I gain in quantity, and quantity can be quality if your game needs it. Besides, real world terrain tends to be quantity rather than quality. Pick a random spot on Earth; it''ll probably be pretty dull.

oo

Share this post


Link to post
Share on other sites