Part of the Khronos Group
OpenGL.org

The Industry's Foundation for High Performance Graphics

from games to virtual reality, mobile phones to supercomputers

Page 1 of 2 12 LastLast
Results 1 to 10 of 14

Thread: Terrain alogrithm

  1. #1
    Intern Contributor
    Join Date
    Feb 2000
    Location
    Bremen, Bremen, Germany
    Posts
    58

    Terrain alogrithm

    Hi,

    Could one of you gl gurus please verify my terrain alogrithm ?
    I haven't programmed it fully yet, but I think it should work well.

    The alogrithm:

    I have a triangle based terrain. It is represented as an 2D array
    with height values in it. All this data is rendered into one big
    display list.

    To speed up redering, I tried to minimize state changes. So I sort the
    polys by texture. When I have three textures, I only need three glBegin()
    statements and three changes to the texture state. This gave an performance boost.

    Now I want greater terrain. Reducing the view depth (the far clipping plane)
    doesn't bring much. I think I have to manually decide which polys are
    in my viewing range. My solution to this:

    I divide my terrain into smaler square areas. These areas are rendered into their
    own display lists. Then I do a quick check which of these areas are into my
    view (shouldn't be that problem). But now I can't benefit from sorting the textures.
    When I have 10 textures, I have 10 glBegin()/glEnd statements and 10 texture state
    changes for EACH of my square areas. A solution would be to create for each texture
    in each square area a own display list, but is this a good solution ?

    Any ideas for optimizing this alogrithm or a better one would be great...

    I hope my English was good enough to make myself clear.

    Tcs

  2. #2
    Junior Member Regular Contributor
    Join Date
    Feb 2000
    Posts
    211

    Re: Terrain alogrithm

    Yes, i have the same problem with my terrain-genrator. But no solution on the other hand !
    If anyone, has a good solution, please send it to me to !

    [This message has been edited by DJSnow (edited 02-12-2000).]
    DJSnow

  3. #3
    Intern Contributor
    Join Date
    Feb 2000
    Location
    Italy
    Posts
    77

    Re: Terrain alogrithm

    I think the big drop in performance comes from vertex transformation. You should focus on optimizing this, maybe clipping out vertices before transformation. I think the direction of expensive state-change optimizations won't pay much in performance gain. The best to do with state-changes is to group them; minimizing is about grouping code to call in the same state of OGL.
    --
    Paolo M.

  4. #4
    Advanced Member Frequent Contributor
    Join Date
    Feb 2000
    Location
    London
    Posts
    503

    Re: Terrain alogrithm

    Hmmm... anybody know what kind of performance hit you take for using 3D textures on current hardware? It just struck me that if you have 4 textures in your lanscape, you could make them layers of the same 3D texture and pick the one you want using the r texcoord. So you avoid texture state changes, and get terrain texture blending thrown in for free.

    Alternatively, you could pack all your terrain textures in a single texture object, and avoid state changes that way. Wouldn't get the blending though.

  5. #5
    Senior Member OpenGL Guru
    Join Date
    Feb 2000
    Location
    Sweden
    Posts
    2,982

    Re: Terrain alogrithm

    Hello...

    I have, like everyone I guess, a 2D array
    (256x256) with height values. I also have
    arrays for precalculated texture coordinates,
    normals (for backface removing) and color.

    I will try to explain the way I render my
    scene. It's easy when you understand how it
    works, and that shouldn't be to hard.

    First of all I want too show you a picture.
    It's supposed to be the entire landscape from
    above...

    Code :
    ------------------
    |                |
    |     a----b     |
    |     |    |     |
    |     |    |     |
    |     *    |     |
    |     |    |     |
    |     |    |     |
    |     c----d     |
    ------------------
    *=viewingpoint

    Outer square is landscape.

    First, we need to know where the camera is
    pointing. In the above example, the camera
    is pointing to the left (0<y<45 or 315<y<360
    where y is angle around the y-axis and 0
    degree is left).

    Then, I use two for-loops to loop through all
    points inside the inner square. Something
    like this...

    (This is just pseudo-code)
    Code :
    for(x=a; x<b; x++)
    {
       for(z=a; z<c; z++)
       {
          glBegin();
          glVertex(x,   height(x,   z  ), z  );
          glVertex(x+1, height(x+1, z  ), z  );
          glVertex(x+1, height(x+1, z+1), z+1);
          glVertex(x,   height(x,   z+1), z+1);
          glEnd();
       }
    }
    The distance from a to b and from camera to
    a or c is up to you to set, the longer the
    distance, the further you see, and the more
    polygons to draw (slower).
    height() is a function/macro to get the
    height for the current point. You can do the
    same way for colors, normals and texmapping.

    The reason I do these squares is because I
    don't want to draw elements behind the
    camera or elements too far away.

    If your camera is pointing another direction,
    just setup some new values for a, b, c and d,
    if the camera is pointing upwards (45<y<135),
    then you do the following...
    Code :
    a----------b
    |          |
    |          |
    c----*-----d
    ... and render this box instead.

    Some good things:
    Most important: you don't draw elements you
    dont see, you don't even process them.

    If someone drops a bomb in the middle of the
    world, just modify the heightmap, the colors
    and normals, and you have a dark hole in the
    ground (no need to rebuild displaylists,
    you do have to rebuild them, right?).

    High framefare, I can reach 120 fps on
    my celeron 300mhz with TNT, and it still
    looks good.

    Some not so good things:
    Using quite a lot of gl-calls, I'm calling
    gl-functions more that 1.000.000 times per
    second (@50 fps) (you can use vertexarrays
    to get away from gl-calls, but I tried, and
    there was no big speedimprovement because you have to build them).

    1.000.000 gl-calls/sec might seems to be
    a few too many, and I agree. I'm trying
    to come up with a way of reducing this
    number...

    You can also have a array for texture index.
    You just assign each element a number
    (generated when you create a texture) and
    activate the specific texture when drawing
    each element in the "square".

    Bob

  6. #6
    Junior Member Newbie
    Join Date
    Feb 2000
    Location
    SubVobWee, near Rigel
    Posts
    22

    Re: Terrain alogrithm

    Yes Bob I would have said something like that asswell,yet using other features with the 2D representation of the world. I would say that you should create a square picture (A bitmap for instance) of height values represented by colors. The brighter the color,the higher the hill, the darker the color, the lower the hill. Simply read that color map straight into an array, after extracting the bits that make up the image's color value. Now most image formats represent the images they contain in a left-to right reading order where the left most and outer most color value of a single line is 0 and width respectively. Simply use this algorithm to render the data inside the array of pixels to a 3D terrain:

    int ix;
    int ip;
    int detail = 0; /* Detail level of hills. */
    /* The higher the value, */
    /* the crappier you're */
    /* terrain looks like. */

    // The color vals of the bitmap
    int * image = (int*)malloc(sizeof(int)*
    (imagewidth*imageheight)-detail);

    // The vertices of the landscape
    float vertecis[(imagewidth*imageheight)-detail][3];

    // Position of you're landscape
    float landscapepos[3] = {0,0,0};

    // Indices into vertex array
    const int X = 0,Y = 1,Z = 2;

    // Let's do it!
    for(ix = 0; ix < imageheight-detail;ix++)
    {
    /* For the entire image, turn the */
    /* colors in the image into 3D vertecis*/
    for(ip = 0;ip < imagewidth-detail;ip++)
    {
    /* simply store the value of the color as the Y value of the current vertex, scale these heights later
    if required. */
    vertecis[ip][Y] = image[ip];
    vertecis[ip][X] = landscapepos[X]+ip;
    vertecis[ip][Z] = landscapepos[Z]+ix;
    }
    }

    /* Now you're "vertecis" array is filled with
    the 3D height points of you're landscape,
    simply connect all of the with a spline,
    and there you go! You've got a 3D height map!
    */


    Hehe.
    I don't know about any certified terrain rendering algorithm, this is just what I would have done if I had to create a 3D map out of an image. Be carefull though, because this algorithm produces *very* realistic terrains,and the polygon count could exceed ten thousand! What you should do to limit the details of the map is simply setting the "detail" variable to a higher value, yetthe value should be smaller then imagewidth*imageheight. With this algorithm, you could use the actual colors in the "image" array and apply them to the vertecis with just one line of code, so you're terrain would look like the picture, yet in 3D (!!).
    I could also show you how to connect these height values with lines and draw the actual terrain on the screen in OpenGL, but I don't know that much about GL yet
    What you can also do to make the camera (player) walk ontop of the landscape and follow the contours of the hill, is to keep the position of the player in a variable,and then matching it to the vertex array, so that he actualy moves *into* the array.
    How to fill the "image" array with colors from a bitmap is another thing,but is easy asswell, simply do the following:

    Call "LoadBitmap()" from the Win32 API and supply the path to the image you want to use.
    Now use "getDIBBits()" to retrieve the color bits in the bitmap, and then multiply each R,G and B value with eachother,and store them into the "image" array.
    Like this:

    HBITMAP myTerrain = LoadBitmap("MyTerrain.bmp");

    DWORD* bits;
    GetDIBits(&bits,myTerrain);

    for(int ix = 0;ix < sizeof(bits)*sizeof(DWORD)/3;ix++)
    {
    image[ix] = bits[ix]*bits[ix+1]*bits[ix+2];
    }


    /* That's it! */


    That simple, huh?
    Well if this doesn't work because the parameters to GetDIBits() are wrong (My documentation is currently out of order : ),
    then please let me know


    Mike The Spike


    PS. Crap this was a long message!


    [This message has been edited by Mike The Spike (edited 02-15-2000).]

  7. #7
    Junior Member Newbie
    Join Date
    Feb 2000
    Location
    Woodland Hills, CA, USA
    Posts
    10

    Re: Terrain alogrithm

    blaaah, my terrain engines (4DOF crap)
    http://EasternAnalog.hypermart.net

    Now I'm researching a fast terrain ray-caster using inverted cones for raycast acceleration. I'll make a static 2D mesh of 128x128x2 equally sized triangles and will shot rays through the vertices and will just change the U, V in this vertices - though it will be limited to the MAX texture size, but i can split terrain on parts, or something like that - So.... Soon.... may be I'll be ready, But have little problems with fast normal & XY-bend angle calculations

    that's all for now, doodies!
    Keep the faith

    BTW: There is a lot of discussion on 3dgamedev.com mailing list about terrains

    malkia/eastern.analog
    malkia@mindless.com http://EasternAnalog.hypermart.net
    malkia/eastern.analog
    malkia@mindless.com
    http://EasternAnalog.hypermart.net (vox4 & glvox8)

  8. #8
    Junior Member Newbie
    Join Date
    Feb 2000
    Location
    Rochester, NY, USA
    Posts
    9

    Re: Terrain alogrithm

    MikeC: To my knowledge, 3d texture acceleration isn't supported on any consumer level hardware.

    -Daedalus

  9. #9
    Intern Contributor
    Join Date
    Feb 2000
    Location
    Bremen, Bremen, Germany
    Posts
    58

    Re: Terrain alogrithm

    Hi mike!

    The way you described it is exactly the way I do it, works pretty cool.

    BTW: 20K fully textured triangles are no problem for a GeForce....

  10. #10
    Junior Member Newbie
    Join Date
    Feb 2000
    Location
    SubVobWee, near Rigel
    Posts
    22

    Re: Terrain alogrithm

    Guess we are on the same wavelength tcs


    Mike The Spike

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •