Jump to content
  • Advertisement

Archived

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

Structural

Outdoor level rendering/management

This topic is 5776 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''ve got this neat idea for a game in the back of my head, but it requires me to render a big outdoor level. I have never written a landscape generator or heightmap loader or anything like that, so I''d like to inform what techniques are often used in rendering and managing outdoor levels. I''d like to know what I''m getting myself into before I start cursing and hitting my computer screen if it doesn''t work I''ve just read the "is BSP dead?" thread and the term quadtree caught my eye. I have a basic idea what it is, but is it used a lot in outdoor levels? If so what for? For rendering or actor-management? Are the quadtree sections a static size? What techniques are used for occluded terrain culling? Or do you render everything up to a certain distance and have the API handle the culling? Any tips/linkage/answers are very appreciated Thank you!

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
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...

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Thanks, I got quite a few answers here...
A bit of a technical question:
How do you split up the leaves of the quadtree? Do still keep your 2D array, and do you determine each leaf by the index of the array (leaf 1 starting at [0][0], leaf two at [0][10], etc) of do you sort them in a particular way? each leaf in it''s own array for example.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Thanks d000gh...
I shall continue my questioning
I have also been looking at collision detection with terrain.
I have read on OpenGL.org that a common way of detecting an objects collision with the terrain is checking a point of the object against the y-value of the array entry that the point is over. Now, to smoothen this detection I read about interpolating the points around the collision point, and checking it then. How accurate is this?
More over, how do I interpolate? I do know what it is, but do not know a formula.

Another thing, is it common to smoothen the terrain amongst points between the array entries? Or does is each entry exactly one vertex?

To summarize:

1) Is interpolating for collision detection accurate?
2) what is the formula for interpolating four (or three) points?
3) Is it common a terrain is smoothed between the array entries?

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!