PDA

View Full Version : Terrain alogrithm



tcs
02-12-2000, 08:36 AM
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

DJSnow
02-12-2000, 05:46 PM
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).]

paolom
02-14-2000, 03:09 AM
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.

MikeC
02-14-2000, 05:24 AM
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.

Bob
02-15-2000, 07:14 AM
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...




------------------
| |
| 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)



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...



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

Mike The Spike
02-15-2000, 01:42 PM
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 http://www.opengl.org/discussion_boards/ubb/smile.gif
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 http://www.opengl.org/discussion_boards/ubb/smile.gif


Mike The Spike


PS. Crap this was a long message!


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

malkia
02-15-2000, 02:05 PM
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

Daedalus
02-15-2000, 03:20 PM
MikeC: To my knowledge, 3d texture acceleration isn't supported on any consumer level hardware.

-Daedalus

tcs
02-16-2000, 02:04 PM
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....

Mike The Spike
02-17-2000, 05:52 AM
Guess we are on the same wavelength tcs http://www.opengl.org/discussion_boards/ubb/smile.gif


Mike The Spike

nickels
02-22-2000, 01:54 PM
For some very cool terrain, check out the USGS web site. You can download digital Elevation data for the entire US. Next, you might use a TIN algorithm to create polygons from this data.
Next Next, look for some DOQQ's (satellite photos) to texture over the polygons.

Cheersarino.

tcs
02-23-2000, 04:54 AM
What site should I check out, I'm German - maybe that's the reason why I don't understand your acronym. Please give me the url to the image data and the alogrith.

Thanks !

Bob
02-23-2000, 05:09 AM
I suggest you have a look at http://vterrain.org . There you can find alot of cool stuff about realtime landscaperendering.
http://www.usgs.gov is the link to the archive with LOADS of maps.

At http://www.cs.arizona.edu/topovista/ you find a really nice landscapeengine. It imports DEM-files (found at usgs.gov). The source is included, and it's not too hard to understand.

Bob

nickels
02-24-2000, 03:49 PM
vterrain.org is a great site! The exact site with (U(S)G(eological) S(urvey) elevation data is: http://edcwww.cr.usgs.gov/doc/edchome/ndcdb/ndcdb.html

Download the DEM's (Digitial Elevation Models). The format is not too horrible to understand. Another good viewer to start is dlgv32, found at: http://mcmcweb.er.usgs.gov/viewers/dlg_view.html

It will display the elevation data and get you started.
The photos are harder to find. DOQQ's are in 3.5x3.5 minute squares. I have been working with a bunch of Wyoming photos found at: http://webhost8.sdvc.uwyo.edu/node/data/bdyDoqqQuadJPG.html

Other sites exist, but the coverage is not as great as with the elevation data.
The TIN (Triangulated Irregular Network) program creates polygons from the elevation data. Triangulating the entire grid would never be displayable, but this algorithm uses only the elevation heights most deviant and creates an approximation of the real thing that works very well. I have used one from:
http://www.ecse.rpi.edu/Homepages/wrf/

Good Luck!