Archived

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

Alternatives to heightmapping

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

I''m kind of sleepy right now, but I''ve been thinking about this for a while, so bare with me. Right now most landscapes in games are represented with heightmaps, or a grid of heights with a fixed distance between each vertex, and some kind of LOD is used to remove unneeded vertices. But there is still memory being used, and you may need a LOT of detail in part and not much at all in another. The only way to get the LOT of detail for the one spot is to have the entire map have the same LOT of detail. Even though all those verticies may not be sent through the graphics pipeline (due to LOD) they''re still having to be stored. What if the heightmap was stored in a different format? Each vertex has an X and Z (with Y being height) coordinate anyway, so why not just make the X and Z coords whatever you need? And since LOD was basically built in you wouldn''t really need to worry about it. I''ll probably need to clarify what I mean later, but what about this idea so far? Is it already being used anywhere?

Share this post


Link to post
Share on other sites
let me see if i understand you correctly...
are you talking about storing a buntch of height values and ignoring x and z, then just moving the x and z points around in real time as your rendering the heights

hmm, actually now that i think about it, a heightmap is just a buntch of height values, even if you specified a list of height values, its the same thing

maybe i dont understand you yet..

Share this post


Link to post
Share on other sites
You can divide your terrain into blocks of 128x128 metres. When using an 8-bit heightmap those would be 16Kbyte chunks of memory each.

You keep an array of 9 pointers, specifying the block you are in right now and those next to you. Those point to 9 memory blocks of 16 Kbyte. When you move into another block you load 3 new heightmap files into the 3 memory blocks you don''t need anymore and adjust the 9 pointer array again. You can also have 9 vertex buffers, or one large vertex buffer with an array of 9 offsets in which you compute and store the vertex data.
Assuming x,y,z and 2 texture coordinates that''s 28 bytes per vertex. a 128x128 map is 32768 triangles.
When using a triangle list that''s 28*3*32768 bytes per vertex buffer, 5.5 MB per vertex buffer.
Because of the view frustrum you will always draw only 5 of the max, only 27 MB of vertex data. Any modern card can easily do this.

For speed considerations you can compute only one vertex buffer or vertex buffer part per frame, if you need to generate 3 new ones that''s only 2 frames where they are not yet available.

Fog at 128 metres distance makes sure ensures you never see beyond what can be rendered, yet keeps new terrain appearing smoothly. If you go to 64x64 patches everything will be 4x smaller and faster.

Share this post


Link to post
Share on other sites
Do you mean something like:

Use x and z values for, say, tu and tv, and sort it out in a vertex shader?

So you could have a vertex format of:

float tu, tv, y;

= 12 bytes

Instead of

float x, y, z;
float tu, tv;

= 20 bytes

Then your vertex shader could decide where each vertice''s x and z coordinates are.

---------------------------------------

Let''''s struggle for our dream of Game!

http://andrewporritt.4t.com

Share this post


Link to post
Share on other sites
f8k8: No, I never even thought of that! But I personally don't have a vertex shader so that wouldn't do me any good.

Fidelio66: That's sort of what I'm doing now, except without the loading and unloading of blocks on the fly. Right now I have my 256 X 256 (verticies, not meters) divided into blocks of 16 X 16 verticies, each with it's own index array.

That's kind of a neat idea, but that's not really what I'm talking about. I drew pictures to help visualize what I mean:



The first image is the way it is now with LOD. Vertecies are stored but never even sent to the graphics card due to LOD. The second image is where only the verticies you need are stored and the rest are completely thrown away, not stored in memory at all. The second image has 22 verticies, and the first has 81. If each vertex has 3 floats for it's coordinate and 2 more for the texture coords, that's a difference of 60 KB. Over a large landscape that could easily add up to many MB.

The reason I'm interested in doing this is because I want my landscape engine to have HUGE landscapes of several square km. I would also like the far clipper set at about 1500 meters so that you can see really far away. Right now, the only way that I can do that and get any kind of speed is to have about 20 meters between each vertex, which is pretty bad granularity. In some places I need a lot more (mountains) and in some places I need a lot less (plains).

Another benefit I see is that you could use special formats to store the heightmap so that it'd only store the verticies you needed. Smaller filesize and quicker load time!

The only disadvantage I can see is it'd be hard to calculate the height of a specific point on the landscape.

Anyways, does all this clear up what I mean?

[edited by - BradDaBug on November 11, 2003 10:59:16 AM]

Share this post


Link to post
Share on other sites
There is already a technique like the one you describe, it''s called Geomipmapping.
Except that it divides the terrain into eg. 32x32 patches.
For each patch it calculates a 32x32 mesh/vertexbuffer, but also a 16x16, 8x8, 4x4 and 2x2. The 2x2 vertices is only 4 vertices and 2 triangles.
You can then draw the detailed ones, the 32x32 ones for the area the player is in and the ones surrounding him, and the further they are from the camera, the lower the detail.
To improve on it you could calculate the error margin (if x and y are between 0 and 31, in a 16x16 grid point (1,1) is the average of (0,0) and (2,2) heightwise. Then you can base going to a lower miplevel based on its error weight.
This means you go to lower mipmap levels quickly on almost flat areas but slowly on rough terrain.

Share this post


Link to post
Share on other sites
I know about geomipmapping, but that''s not really what I mean either.

Imagine you''ve got a road with a ditch on each side. This ditch may be 0.5 m across and 0.5 meters deep, forming a "V". That means the verticies would have to be 0.25 meters apart to represent it! Using geomipmapping the WHOLE block that the ditch is in would have to have each vertex 0.25 m from the next one, just to represent a simple "V"! If the terrain is otherwise flat, that''s a LOT of waste.

What I''m talking about is arbitrarily placing verticies, independent of any kind of grid, where you need them, so that there may be nearly no verticies where it''s flat, then in the middle of that there''s a whole bunch right where the ditch is. Only the verticies that are needed.

Share this post


Link to post
Share on other sites
you''re basically talking about storing a polygon soup type of thing, aren''t you? like, when you load the landscape from a file, you read in x, y, and z, instead of just the y? this would mean larger data files probably, but since you end up store the x and z in memory anyways, it would mean less memory usage when the program is running... sounds like a good idea. don''t know much about landscape rendering, but I think it would work pretty good.

Share this post


Link to post
Share on other sites
Polygon soup would surely give you more control on the "sampling" of the height values. Furthermore it solves some common terrain representation problems sush as caves, cliffs,...

However I don''t understand how you would achieve dynamic LOD. Because you have to deal with x,y,z components instead of height only), traditional LOD algorithms can''t be used (at least, not those I know).

Another alternative was discussed a month ago : using NURBS patches for the terrain. These patches are tesselated depending on the LOD you need (with a cache to prevent unnecessary tesselations) and high frequency details are added with fractal noise.
See http://gamedev.net/community/forums/topic.asp?topic_id=185716 for more details.

Share this post


Link to post
Share on other sites
Your idea of arbitrarily moving the verticies (and not just changing their y) is one way to improve terrain. Another would be to use a real mesh made in something like gmax instead of a custom format.
A third, and I think possibly better thing to do would be simmilar to dungeon siege where you have 3d tiles with ''anchor points'' and you can attach any 3d tile to any other 3d tile by connecting their anchor points. Also, since you use anchor points instead of just a grid of tiles, you can easily have really complex constructs and different sized tiles.
The only problem with that method is the editor. Forcing users to manage tiles themselves is IMO a bad idea. Instead, you have the traditional RTS controls (things like ''change terrain height'', ''change terrain type'', ''add cliff face'', etc) and make the editor pick which tile to use where. You could of course also have a manual edit mode, but it would be for advanced users that need to lay a specific tile in a few specific locations and not for general use. It is a lot more work to make the editor and tiles, but it also allows for many kinds of easy optimizations and allows for a more freeform world without the work of making a full blown 3d editor (or having to process polysoup)

Share this post


Link to post
Share on other sites
the thing about "better methods than heightmapping" is that it makes the algo for finding the height at a point *really* complex.

also, if you store x and z for a vertex as well as the y, you''re increasing the thing by another 8 bytes. with my heightmap structures, that *triples* the data size in the worst case (no LOD optimizations). you''d have to have a good optimizing routine to get that below 1........3 is bad.

i like the sound of the anchor points thing

Share this post


Link to post
Share on other sites