I''m at school atm and shouldn''t b here so here goes a quick answer, but there''s lots more about it really...

First of all, before I forget, let me mention some techniques you should master to build a big terrain:

1. Make a x-z grid with the sizes of your map. Most of the time the delta x (so how much the x changes, this is also the size of your polygons) is 32. It''s fast (the smaller the polygons the slower) but it allows great detail. (So it looks smooth)
2. Read in the y (height) values from a file. This could be a file you made with some sort of map editor, but if you don''t have one you could use the heightmap loading technique too (loading height values out of a RAW data file, technique #1 look it up)
3. Make the octree. (technique #2 An octree is basically just a division of the landscape. See it as this: First, you draw a cube around the whole map. Then, you make 1 subdivision. So you split the x-axis into 2 parts, and the z and y-axis too. That''d leave you with 8 different cubes now, each 1/8th the size of the original cube. Now, if you''d check which of the cubes are in your viewing frustum (check if they collide with the shape that''s your view, this technique is called frustum culling (technique #3 enters)) you can only draw the cubes that are visible. This might leave A LOT out if your landscape is big (and your view is optimal). BTW, if you DRAW one of the cubes, you draw the polygons inside that cube. I think www.gametutorials.com has one of the best octree tutorials.
So now you have your octree. There''s a lot more to it than this, but you''ll see.
4. Use LOD. (Technique 4) LOD means level of detail, and it basically just merges polygons where the detail level (so the size of the polygon) is higher than required. If, for example, the polygons are far far away from you, or if the height delta between some polygons is (almost) the same, you could decrease the amount of polygons a lot by merging the small polygons together in less, bigger polygons (thereby decreasing the detail level, but this goes (almost) unnoticed) This saves polygons, which saves speed.

If you use all these methods, you get a quite fast terrain engine. I believe there''s another technique for checking which polygons are hidden behind others, to skip those too. I haven''t looked into that though. It''s called ray tracing I believe, or DirectX calls it culling I think. Look that up as well. If you''ve done this, I think you got one of the most speedy terrains possible. It''s a really big job though, so start out working on the techniques one by one, and make sure the previous technique is implemented perfectly before you move on to the next. To help you out starting, the best way in technique #1 is to store the vertices in a vertex buffer or make some sort of vertex description and save the data into an array of these vertices. Like this:

class CVERTEX{   float x, y, z;   float u, v; // texture coords   // Add what else you need}; 

You could also make more classes like one for polygons

class CPOLY{   CVERTEX a, b, c;   texturefile texture;};Then just draw all the vertices (or polygons) and find out how to texture them. There are many of these texturing techniques as well: none is ''best'', it depends on what you want (I always stretch a texture over the landscape, and add a detail texture with multitexturing that''s repeated for higher texture detail)Oh one last note www.gametutorials.com does not only have octree tutorials, but also heightmap tutorials. The way of loading heightmaps is used in the octree code too, so it''s wise to use both if you want to use one of the 2...    

Hey there. I differ slightly from the last poster''s thoughts but only in detail.
Here are some thoughts...
1)A basic landscape is easy to render - just a 2d array of vertices at different heights, where you store the heights as a bitmap or some other way.
2)The sizes of the polygons are NOT normally 32 - in fact the spacing between vertices makes no difference as you can scale them to whatever you want - I use the distance as a value in metres and have points at 1m spacing.
3)Both quadtrees and Octrees are popular. A quadtree divides the map into 4, then each part divides into 4 and so on until you get to a region of the map which is some size e.g 16x16, 32x32, called a leaf - the leaf stores a small section of the map. This means when you render you quickly find out which sections need drawing. An octree is the same idea but you divide a cube into 8 so you divide the map by volume rather than area. I assume which is best depends on how flat your maps are.
4)Typically the quadtree sections (I''d recommend this not octreee personally) are static size but they don''t have to be. For instance you don''t have to have each section having 4 children - if there''s nothing in one section (ie your terrain is not square) you can leave it empty. You can also keep subdividing different sections to different levels so not all leaves are equally big, if you can think of a good reason to (I''d avoid this initially though but maybe leave the design open to this possibility)
5)LOD is typically used to decide for each leaf in view, what detail to draw it at. This choice can be done in different ways, the main problem is where two leaves join it must be at the same detail or you get nasty gaps, so you need to make the rendering code more complex.

I''d advise initially making a quadtree but drawing everything, then do quadtree culling, then lastly implement LOD.
Other occlusion techniques exist but they are a lot more complicated and you''ll probably find you don''t need them. You can also stop drawing leaves which are far enough away - it''s noticeable but not if you introduce a bit of fog.

Helpful?


Read about my game, project #1
NEW (18th December)2 new screenshots, one from the engine and one from the level editor

John 3:16

Well It depends. If your map is always going to be small enough to fit all of it in memory, then keeping your heightmap as one big 2D array makes access potentially easier (checking the height at (x,y) is much easier this way). However if you want really big terrains then you''ll need to keep loading different sections of the map. Now it makes much more sense to store each leaf (or maybe a small quadtree which is a sub-level of the map but still contains 4 children each with 4 leaves for example - so you don''t have too many sections to keep loading) somehow with it''s own minature heightmap so that you can load one part of the map without having to check which other bits are loaded. You''d have to make sure not to call GetHeight() for somewhere not loaded, but since you only load the sections you need that shouldn''t be a problem.

Well, I''ve not implemented collisions yet so on accuracy I''m not sure. Also, do you mean linear interpolation (drawing a plane between the 3 points of a triangle) or higher order (finding a curved surface that fits well over the points and smooths out the boundaries)?

The latter is more taxing but certainly possible, it''s much more computationally expensive too. For the linear version you just find the plane eqn for the 3 points of the triangle and stuff in the x/z coord to get the height.

Feel free to email me if you have any further questions.


Read about my game, project #1
NEW (18th December)2 new screenshots, one from the engine and one from the level editor

John 3:16