Thread: Terrain algos

  1. #1
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001

    Terrain algos

    Ok, all of you have seen my its time for you guys to help me get this sucker to fly...if ya want that is.

    Ok here is the basis of roam based on my reading. The terrain uses more tris in the area that need it. Essentially if the y transformed coordinate difference between two vertexes is greater than some pre-determined divide that quad into two tris and so on until it passes the test. This is great for areas with lots of flat land...but not so great with very mountainous terrain.

    I have another idea based on distance from the viewer. Since all terrain in real life gains detail the close you are to it..why not split the quads that are closer to the viewer and not even worry about the distant ones? This would allow me to texture way off into the distance - perhaps even as far as the sky plane and yet still retain detail at close range and still stay under the max primitive count.

    Problem is...I don't want to transform every vertex...test it's y component...and compute the terrain on every frame. Also I don't want to render the whole mesh because most of it is not in view.

    The ideal method would be to find which vertexes will actually lie in screen space and which one's won't. But I don't know how to get the final screen x,y positions of vertexes in D3D. If I could then I would only create a mesh out of the vertexes that were visible. If a vertex was not visible but the one near it would be part of the mesh too or the quad would not be complete and the render would be a mess.

    Any more ideas? The whole problem is finding what lies in the frustrum and what does not. This has not been an easy thing to compute on the fly.

    Some of you gurus out there must have other ideas.

    EDIT: Found some nifty articles/books on frustrum culling and terrain optimizations. First step is to render triangle strips instead of a triangle list - next would be to cull the geometry that lies outside of the frustrum. Also I'm starting to implement the quadtree renderer. It is so much different from the original renderer, I basically have to re-code the whole terrain loader and vertex buffer/index buffer creation functions.

    The idea is that each part of the map is divided into 4 quads. Each parent has 4 children. If the parent is not visible, none of its children, none of their children, and none of their children, etc., etc. are visible. If parent is visible then check child1. If child1 not visible - move to child2, else do similar check on child1's children. Store the vertexes that are indeed visible and then create a mesh out of them. This will be extremely fast if I can get it to work. Another optimization is to fire a ray across the map towards the vertex. If we hit a hill, the vertex is not rendered. However using triangle strips also presents another problem with this method - the top of the closest hill will share a vertex with the next hill that is higher. Not what I want. So I might not be able to cull geometry that lies behind hills. Anyways the quadtree and frustrum culling should give enough results for the time being.

    Also I will pre-compute weights in a weight map. Basically I will place the differences in hill heights in an array the same size as the heightmap. If the distance is rather large, then this quad will be split into smaller ones until the number of tris matches the weight in the map. It's sort of like ROAM but it's pre-calculated.

    ..anyone wanna help...this stuff is fun but it's not exactly easy.

    Last edited by VirtualAce; 04-08-2004 at 03:00 AM.

  2. #2
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    try calculating the middle of the view frustum in world coordinates

    pos = camera.pos + (0.5*FarClipPlaneDist)camera.dir;

    then you can calculate a bounding box around the view frustum with the distance to the far clip plane as the distance of one side of the box and the centre of the box at 'pos'. (the view frustum is virtually projected onto the xz plane because its essentially a 2d mesh of verticies with heights)

    Then you can then use simple plane tests against the view frustum planes for the verticies within the bounding box. this method is no where near as elegant as oct/quad trees but is relatively simple to implement and works quite well.

    NOTE: this also assumes the distance to the far clipping plane is greater than the width of the view frustum at the far clipping plane. If this isnt the case you'd have to use the greatest width distance (at the far clip plane) instead.
    Last edited by Perspective; 04-10-2004 at 02:52 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Continous LOD Terrain Source... Released!
    By Perspective in forum Game Programming
    Replies: 13
    Last Post: 04-17-2006, 11:21 PM
  2. New terrain engine
    By VirtualAce in forum Game Programming
    Replies: 16
    Last Post: 03-16-2006, 02:47 AM
  3. Drawing only what you can see (terrain)
    By Eber Kain in forum Game Programming
    Replies: 8
    Last Post: 07-05-2004, 12:19 AM
  4. Terrain engine idea
    By VirtualAce in forum Game Programming
    Replies: 15
    Last Post: 04-03-2004, 01:30 AM
  5. OpenGL terrain demo (EDITOR)
    By Jeremy G in forum Game Programming
    Replies: 2
    Last Post: 03-30-2003, 08:11 PM