Archived

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

Subotron

Best way to program a high-detailed, huge (infinite) world

Recommended Posts

Subotron    182
I''ve been programming for a few years now with OpenGL/DirectX, and most of the time I''m trying to create a graphics engine that is capable of producing a world that can be as big as I want it to be (read: infinite) so I can create an enormous world. This has always been my goal. In the last few years, I tried different methods of creating virtual worlds. I tried making data files with coords and more info for each polygon/vertex, and load those data files in and display the polies. I tried making heightmaps, and stretching textures on them. I''ve tried some more stuff. What I''ve been working on for the last 6 months was a method which worked this way: I create a heightmap image of 1024x1024 pixels. I create a texture of 2048x2048 pixels. I use the heightmap image to create a map (each pixel of the heightmap image resembles the height of one vertex on the map) and I stretch the texture over the map. Then, using multi-texturing, I add a detail texture over it to get the detail I want. The problems I''ve encountered: 1. The heightmap image cannot be much bigger than 1024x1024, because else there will be too much polygons. I''ve tried solving this using frustum culling & octrees, but the speed gain is not enough to create a heightmap image with nearly-infinite size. Possible solution: Create different heightmap images and load only a few at once. Problem: how do I know which ones to load, and when do I switch (don''t want the landscape to popup suddenly, the change should go unnoticed) 2. The stretched texture should be quite small. It''s 2048x2048 atm, which is already too big, and even bigger is impossible. (Mayor speed loss) I can''t think of a good solution here 3. When I add the detail texture, I don''t know how often to repeat that texture. Say if I put the whole texture on 1 poly, the detail will be quite small. It the poly is close, this looks great, but once the poly is not really close to the camera you don''t see the detail anymore (mipmapping effects) If I stretch the detail texture more, it gives detail in the distance too, but now the ground close to the camera is not detailed enough anymore I don''t really know a solution. I have to figure out a way to make the detail texture stretch more if it''s far away but I don''t know how to do this. 4. Can''t make overhangs (like caves) with heightmaps 5. I want to insert some buildings/trees/friemel/other objects on the heightmap (a heightmap is not a complete world yet) but I don''t know how to implement this without hard-coding all the poly''s... If you have any thoughts on this, any solutions for the problems, or if you have a way to make the landscapes like I want them to be, please respond. I appreciate any thoughts about the subject. Thanks in advance!

Share this post


Link to post
Share on other sites
Korvan    178
I''ve been putting some thought into a method of dealing with an arbitrarily sized and detailed world.

The world is stored as a height map at a very rough scale, say one sq. km per pixel. The area around the player is then expanded into main memory using procedural methods (such as perlin noise) to a detail level of one metre. At this point, overlays may be applied to the map. These overlays deform the map to show such things as roads, rivers, etc.

A trianglular mesh is created that is just larger than the camera''s view frustum. It is set up so that there is less detail the further you get from the camera. The vertices of this mesh are transformed by the camera''s position and orientation and the x,z (assuming y is up) values are used to look-up the height from the expanded map in main memory.

As the camera moves about, you will have to expand new map areas, so your procedures to do this will have to run fast enough in real time.

The frustum shaped mesh is used to minimize overdraw, but it will fail if the camera is positioned too far above the ground, or if it rotates too far off being paralell to the ground.

If anyone know of any serious flaws with the above approach, I''d love to hear them, as I''m pretty much just a beginner in terrain rendering.

Share this post


Link to post
Share on other sites
Karg    133
I''ll take a wack at this.

1. The heightmap image cannot be much bigger than 1024x1024, because else there will be too much polygons. I''ve tried solving this using frustum culling & octrees, but the speed gain is not enough to create a heightmap image with nearly-infinite size.

---With frustum culling, an implicit quadtree (the heightmap''s a regular grid) a nice LOD algo. and possibly an occlusion algo, there shouldn''t be a problem with too many polygons. That leaves the actual storage and retrieval of a very large number (near-infinite) of heights. If you break the height map into blocks that are just larger than the visible range (far clipping plane) then you can load up the surrounding blocks around where the player is:
XXX
XOX
XXX
and once they move into another block, slowly load in the new set of nine (at least four will already be loaded). Try a thread that just loops and makes sure that the current block is fully loaded, else loads part of an ajacent block that is visible, else loads part of an ajacent block that isn''t visible, else sleeps. I have no idea how fast this is, though.


2. The stretched texture should be quite small. It''s 2048x2048 atm, which is already too big, and even bigger is impossible. (Mayor speed loss)

---You need''nt have a texture that large. Just get a few smaller textures and find a way to blend them (highest point is 100% texture A, lowest point is 100% texture B, interpolate the rest). That, together with a good detail texture can look quite good.

I can''t think of a good solution here
3. When I add the detail texture, I don''t know how often to repeat that texture. Say if I put the whole texture on 1 poly, the detail will be quite small. It the poly is close, this looks great, but once the poly is not really close to the camera you don''t see the detail anymore (mipmapping effects)
If I stretch the detail texture more, it gives detail in the distance too, but now the ground close to the camera is not detailed enough anymore

---I haven''t tried it myself, but I''ve seen people with both a near and far detail texture, again just interpolate between the two. The near is as a good setting for close polys, the far for far polys.

4. Can''t make overhangs (like caves) with heightmaps

---Nope. The hack is to treat the heightmap as the lowest elevation and everything else as a separate polygon with a special case collision, LOD, etc. Kinda messy. Might be better dealing with a more free form mesh than heightmaps if this is something you really want to do. Can''t help you out much here.

5. I want to insert some buildings/trees/friemel/other objects on the heightmap (a heightmap is not a complete world yet) but I don''t know how to implement this without hard-coding all the poly''s...

Either create them in a modeling program and export them out, or hard code em into your own format and save em. Then you can add stuff like occlusion geometry to objects and all kinds of fun stuff (Do you really want to draw all of that landscape hidden behind that house?).

There are some great posts on most of this stuff in the forums, if you can find it... Just check out google for most of it, and for anything specific, there are many people here than can help a lot more than me.

karg

Share this post


Link to post
Share on other sites
mrbastard    1577
some resources on paging large terrain datasets:

chunklod
demeter

both page terrain from disk as needed. demeter is more accessable but the chunklod method looks more powerful and could probably be used on things other than heightmaps - eg modelled caves, building etc

Share this post


Link to post
Share on other sites
The only method that allows for infinite worlds is one in which you tile together heightmaps (or whatever data set you use). When you add a new one into the scene, initially make it completely flat and have the vertices expand upwards as the user gets closer. Also, use fog or haze so the user doesn''t see the flat ground itself popping into view. This should work. The heightmaps would be loaded from disk.

~CGameProgrammer( );

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
I''m sorry, but I can''t see the resemblance between infinite and all the ideas put forward here, as they are all *limited* in some way. They mere fact that your PC has a *limited* amount of storage space should be enough of clue for you not to use the word infinite. My 2c.

Share this post


Link to post
Share on other sites
Yann L    1802
The only thing you can do to get a really infinite terrain, is to generate it on the fly. For example using realtime fractal systems, basically creating new heightmap values as they are needed, instead of pre-storing this information.

Share this post


Link to post
Share on other sites
Subotron    182
First of all, thanks for the help. I see some pretty usefull ideas here, and I will study them closer after I''ve posted this message

Of course, infinite world is not possible (unless created on the fly, like Yann said) because you can never make enough heightmaps to have an infinite world. My idea is to use the shape of a planet (round) so the edges of the map are connected again

Like this

ABCD(A starts again here)
ABCD(A starts again here)
ABCD(A starts again here)
ABCD(A starts again here)

but still I need a really big amount of heightmaps. As for the blending method (interpolating textures based on height) this is possible, but you don''t get very varied landscapes that way. Using one texture, you can make it exactly the way you like (you can also do things like including a path of stones to walk on and stuff) this gives you much more flexibility. I''ll have to find a solution for that problem too...

As for the terrain loading, loading the 9 chunks in the

XXX
X0X
XXX

way was something I thought about too, and it seems really good. A lot of poly''s, but with octree/frustrum culling it shouldn''t be a problem. I''ll use fog for the popup, yes.

Korvan, your method is new to me, I''ll try to dig some articles up about this subject so I can try.

Thanx all for the help!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
I use a basic technique:

- a generated ocean which is infinite
- some heightmaps to make islands where the player is.

Share this post


Link to post
Share on other sites
Domini    126
A seeded random number generator can be used to create predictable psuedo random results. You can use this to develop an algorithm that can take a seed value to generate different parts of the world as you approach them. Since you''re using a seed, you''ll be able to generate the same world every time.

Miracle Man Studios Inc

Share this post


Link to post
Share on other sites
NeverSayDie    122
The first two articles in the triology "A Real-Time Procedural Universe" published on Gamasutra a while back might be useful. Look under Programming in the Features section.

Far as I recall, the articles deal with generating arbitrary planetary bodies/surfaces in realtime. Some kind of procedural trick involving simulating Brownian motion I think? Might be of use to you.

[Edit: Damn links!]

[edited by - NeverSayDie on October 22, 2002 11:11:14 AM]

Share this post


Link to post
Share on other sites
BrianH    145
There is also a book:

Infinite Game Universe: Mathematical Techniques
by: Guy W. Lecky-Thompson

Domini and Yann are correct. If you can figure out a method to generate your terrain on the fly from a psuedo-random number generator, then you can store your entire world by simply storing the seed values. Its analogous to storing the frequency value of a sin wave instead of storing thousands of points along its curve.

-BH

Share this post


Link to post
Share on other sites
Yann L    1802
Here some more ideas:

If you want to pre generate your huge world, then why not compressing the heightmaps on disk, and decompressing the data when swapping them in. Most terrain heightmaps are a more or less simple multiresolution 2D waveform. This kind of data compresses extremely well using Fourrier transforms (ala JPEG). Take your heightmap data, run a DCT over it, quantize it and compress using zigzag scanning, RLE and an optional Huffman encoding. You will easily be able to compress a 1024² heightmap into just a few kilobytes, without noticeable loss of quality. The decompression can be highly optimized by using MMX, 3DNow or SSE. You could even use the hardware to decompress it, most modern 3D cards feature a hardware IDCT/dequantizer as part of the onboard MPEG decoder.

But you can reduce memory consumption even more. The parts you''d like to control (ie. prebuild) on your terrain are most likely large features: this mountain must be exactly here, and not over there, this lake here, and that river there. You don''t really care about the exact positioning of small details such as little rocks. So create a very small resolution version of your heightmap, only encoding the large features (a 64*64 map would be enough). Store it on disk, together with a seed value. When decompressing, simply scale the 64² map up to 1024² using a good interpolation algorithm (bicubic, spline, or similar). Now, use a seeded fractal system (eg. Perlin Noise) to add the details onto your map.

Especially with the second method allows for controllable (ie. not entirely random) huge worlds. Store just what is needed (the large scale visual appearance of the terrain), and generate everything else on the fly.

/ Yann

Share this post


Link to post
Share on other sites
I don''t see the need to create literally infinite worlds, even MMORPGs don''t have that. Well obviously - you can''t have a persistent world if it keeps being randomly calculated on the fly

But definitely a method that combines manually-determined information with randomly calculated (procedural) information is very good for representing large worlds. The engine I''m doing will just have nothing random but will load sections on the fly from disk, but I''m not doing a heightmap engine or even a terrain engine per se -- it''s more geared towards structures, like large cities.

And although one way of implementing a partly random terrain, as has been said, involves each pixel representing the average height of a 1km^2 area, what might be preferable is to have the pixel values represent the type of terrain instead of the height. So having the red color be 0 would indicate totally flat terrain, having it be 64 indicates low rolling hills, and having it be 255 indicates a very mountainous region.

The green component can represent the amount of vegetation and the blue color can represent the height of sea level, flooding the region with water up to it.

~CGameProgrammer( );

Share this post


Link to post
Share on other sites
Scheermesje    169
But would it be possible to save an heightmap whit different colors so you can see what the height value is and what kind of terrain?

How brighter the collor how higher and the color gives the texture?

Share this post


Link to post
Share on other sites
Nypyren    12063
Or use 32 bit (ARGB), and use A for the height?? j/k. 256 heights would probably not be smooth enough.


For your "heightmap can't have overhangs"...

have you considered storing partial heightmaps that describe "ceiling" and further "ground" levels? You could technically do this for as many levels as you wanted, but they are tougher to render, since they stop/start at strange places and don't always lend themselves to tri-strips. And are harder to manage in memory if you care about size.

[edited by - Nypyren on October 24, 2002 3:25:49 AM]

Share this post


Link to post
Share on other sites
Ysaneya    1383
Another idea is to mix the heightmaps and the procedural approaches.. use heightmaps for the low frequencies (say: 1 texel every 100m ), and generate the high frequencies with some kind of noise, to add local variety.

Y.

Share this post


Link to post
Share on other sites
Heightmaps map onto the Y axis. If you add X- and Z-maps then you can have overhangs and vertical walls. What I mean is, instead of each heightmap pixel being used for the Y, you use it for the X,Y, and Z. You can have red be X, green be Y, and blue be Z, or you can ditch bitmaps altogether and use a level editor. I wrote code to display XYZ heightmaps. But ideally you'd make the regular Y-heightmap and then edit it in some sort of editor and manually tweak the vertices, it's much easier than trying to edit the X/Z values on a bitmap.

~CGameProgrammer( );

EDIT: By the way, when I say X and Z I really mean delta-X and delta-Z. In other words you take the X and Z positions of each vertex that you already have, and you add the heightmap's X and Z values to them. So if the X and Z maps are zero then the heightmap is just a regular heightmap.

[edited by - CGameProgrammer on October 24, 2002 9:02:44 PM]

Share this post


Link to post
Share on other sites
Truckhunter    122
I just saw this thred and couldn''t resist contributing.... I''ve actually been tackling this problem for the past month or so. After a considerable amount of work, I have yet to come up with a great solution, but have tried some variations on the things posted so far.
Basically, what I was doing wasn''t infinite, but large enough that storing a heightmap isn''t feasible. Here is the approach that I am currently using:
1. Generate the height data on the fly. Guy Lecky-Thompson (who has already been mentioned on this thread) has written several things on this subject - all that I''ve read of his was his article in Game Programming Gems, but that was a good start. The basic idea (read the article, or some of the others already mentioned for a full treatment) is that you randomly generate the terrain every time, but you use the same seed for the generation. The result is, you can have an truly infinite universe that is the same every time without storing anything more than a 4 byte seed.

Well, that''s fine and dandy for something simple, but it has the huge problem of persistence as CGameProgrammer mentioned. The solution that I am using is something similar to what Korvan mentioned - storing deformations. Thus we get to parts 2 and 3 of my approach:

2. Store any ''actors'' separately. Actors would be anything that moves around frequently (not a normal part of the terrain.) I am actually using a separate random generation technique to generate actors (such as trees.) The difference is, I only run this one the first time I generate an area, and then I store them separately. This does require a bit of extra storage - basically, I do a grid-like approach to store what has already been generated, where this grid has a pretty large resolution, and all I need to store is a single bit telling me if I have generated the actors for that area.

3. Store deformations to the terrain. The way I am doing this right now (it could certainly use some improvement) is to store a list of points that have been deformed (by being dug or something like that.) When I generate an area of terrain, I check to see if any of the points I have generated are deformed in any way. (this list gets quite large, so I am using a sort of hashing approach so I don''t have to go through the entire list to see any that are in this area.) All I need to do then is adjust the specified points by the height they are deformed by.

This approach is the best I have found so far to maintain a persistent universe of an arbitrary size. The problem you can probably see is that its space requirments could grow indefinitely. My current solution is to ''forget'' old deformations once a certain number have been made. That way I can cap my storage requirements to whatever I want.

If anyone can think of any great improvements on this, let me know.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Would u be willing to use a new hardware ?

I had designed a graphics sub-system just for this case.
(real time , randomly-or not generated worlds, with full collisions, properties, no polygones used, rendering in 2-6 seconds)

Share this post


Link to post
Share on other sites
Xai    1838
I don''t know anything about the 3D and mapping aspect of this questions, but i have some input on the infinite aspect ...

First, you can can use random generation of terrain and new areas, but not in the simple way described here .. because first of all, it wouldn''t let the player return to the areas they had been before ... So

IF you get any random generation engine created, it should A) be predictable, in that given the same input / seed, it generated the same data (this way you can store only the seed for each quadrant that has already been visited but is not in view) B) you need some way of making the 9 neigboring sqaures blend together smothly, and this algorithm must be deterministic as well ...

Second ... this is the internet age, and there are many amazing ways you can use this fact ... for one, let every client have the option of connecting to a central server, just to get map information, and possible even to SEND map information back to the server ... and THINK HARD about the doors this opens up ... first of all, it means a human being (you) can carefully create the terrain as needed, and make it available on your server ... and if you combine this with the random generator, then you get this amazing synergy ...

the human create an area, if a player exceeds its scope, he is invisibly feed randomly generated terrains, the terrain seeds are stored locally, until he next communicates with the server (which can be often while playing), then he sends the seeds he generated, and so on ... so the server generates this data, and makes it available to all ... so EVERYONE is in the same world, MM style, but anyone can upload data, an artist who renders it by hand, or the program, when it generates it algorithmically ...

Share this post


Link to post
Share on other sites
kylecrass    163
I have 2 cents of info that may be of interest. When saving a "section" of a map, store its width and height in 4 bytes each. Then using that info, you can calculate where to begin displaying "Strips" using this info and a given position of camera.
To find the square''s index for any given position, use an equation like this:
column + (row * max_columns)

For example, a grid has 32767 columns * 32767 rows, and you want to get to start drawing at row 3, column 2) you''d first find the index like so:
2 + (3 * 32767)

If you''re using triangle strips or the like, you should be able to see how to modify it to accomodate. Right now I have a 1024*1024 grid (using triangle strips) that renders at about 90 fps on a Geforce2 @ 1280*1024 at 32bpp. Email me if you want more help :D

Share this post


Link to post
Share on other sites
Andos    124
You could use the same algoryth Soldier of Fortune 2 uses. You can write a seed and Sof2 generates a level out from the seed. The level is EXACTLY the same if you write the same thing even on different computers. A seed for sof 2 is only 6 characters long for a huge area. That could be used...

Share this post


Link to post
Share on other sites
TerranFury    142
To everyone unfamiliar with random number generators and seeds:

A "random number generator" works something like this: It takes the previous random number, and does "something" to it. This becomes the new random number. When rand() (or whatever the function is) is again called, it does the same "something" to this new number, and so on.

As you can tell, your series depends on previous numbers. So what determines the first one? You do. This number is called the seed. Given the same seed, a random number generator will output the same series of numbers. That''s why they''re more accurately called pseudorandom number generators.

Very often, the seed used comes from the system clock. This makes the random number sequences more unpredictable, since the same seed won''t be used more than once unless the user sets the clock back (and even then it''s highly unlikely of seeding the generator when the clock reads the EXACT SAME time).

Seeds, however, don''t need to come from the clock. You could have a user enter a seed. That''s how this part of Soldier of Fortune''s random level generator works.

In the standard C library, the function srand(...) seeds the random number generator. I would guess that most professional games use their own random number generators, with seperate random number generator objects, so that re-seeding the generator doesn''t cause global changes.

There are many types of random number generators. IIRC, rand() is a linear congruential generator. Another well-respected generator is called the Mersenne(sp?) Twister. All simply use mathematical techniques, generally dependant on previous results, to create new numbers. The resulting sequence appears random, but isn''t.

There are a few ways to generate numbers that are, according to science''s current understanding of the way things work, truly random, using special hardware. Usually it outputs noise generated across a resistor. A TV antenna tuned to a station not used for broadcasting would also give a "truly random" signal. Whether or not it really is random (and if there is such a thing as randomness) gets into scientific philosophical questions to which there are currently no answers.

Anyway, now that I''ve rambled on about random number generators, I hope I''ve give you at least SOMETHING useful. Enjoy.

Share this post


Link to post
Share on other sites