Author Topic:   Lithium Engine
posted December 29, 2000 05:06 PM         

You know, I'm going to give this project a name and call it the
Lithium Engine.

From a previous thread:


[1] What's the size of your terrain, and how many quad-levels do you use?

[2] Do you use strips, fans, or indexed lists to render the leaves?

[3] How many triangles are visible per frame, and what's the average frame rate?

[4] What hardware do you use?

I'm really quite curious, because I never did full-resolution terrain. I always
used some kind of CLOD, and I'd like to know how your full-resolution terrain

Well, I don't know if you can call it full resolution. If it was, then
I should be able to scale my xz coordinates by 1:1, and have it run at
a steady 60fps. Instead, I scale my xz coords. by 8:8, which places them
further apart, so there are less vertices drawn on the screen. This reduces
detail somewhat. Slopes are more jagged then curved.

Your questions:
[1] I can load a 1025x1025 heightmap and go down all 10 levels.

[2] I'm currently using fans. Each fan node can have up to 10 vertices.

[3] Which is better? Vertex count, or primitive count? I only count
vertices, and I try to limit it to about 8k-10k per frame.

[4] I have a P3 Celeron with a bland OEM 3D card that came with the computer.
I would like to replace it with something better in the future.

Some numbers:

Running at 640x480x16 full-screen (1025x1025 heightmap):
Total vertices: 2,621,440

vertices drawn: 2k, clipping distance: 250, fps:70-85 (maxxed at refresh rate)
vertices drawn: 8k, clipping distance: 500, fps:45-50
vertices drawn: 16k, clipping distance: 750, fps:35
vertices drawn: 28k, clipping distance: 1000, fps:20

Btw, the camera always stays low to the surface of the terrain, and it is
usually pointing into the horizon. I don't plan to have the camera fly high
above the terrain like an airplane, but instead it will stay low like a tank.
This helps keep the vertex count down. If I was doing LOD, I could probably
place my camera anywhere.

For all of this, I am only using AABB frustum culling and I am doing
simple tile texturing with a single 128x128 texure.

What kind of numbers do your get using CLOD?


Klaus Hartmann
posted December 30, 2000 04:09 AM            
Thanks for the input It's not really possible to compare your numbers with the numbers of my LOD engine, but here are a few figures:
The size of my terrain is 1025x1025, and I'm using a 1 meter grid-spacing (1:1). On a P3-450 with a GeForce256 and a display resolution of 1152x864x32 I get about 20K triangles at approx. 40 fps. This is not exactly fast, because:

[1] I use triangle fans without vertex buffers.

[2] I don't have separate AABB information. Instead I use the minimum/maximum heights of the whole terrain. In addition, my AABBs are 3 times as large as necessary (this has to do with the LOD algorithm).

[3] As with most CLOD algorithms, the performance is limited by the execution time of the LOD algorithm.

[4] The code is not optimized and it uses OpenGL (I'm not too familiar with OpenGL, because I normally use Direct3D).

Anyway, I'm currently playing with the thought to write a new engine (for fun). The features would be:

[1] Disk-paging for large terrain. I never tried this and I'm curious about the performance.

[2] In the beginning it will be full-resolution. If everything works then I'll perhaps switch to some LOD algorithm, like P. Lindstrom's algorithm for phototextured terrain.

[3] I will not traverse the quadtree to its full depth, because that only costs performance. The full-resolution leaves will probably be 33x33 vertices, rendered as an indexed triangle list (or indexed strip).

[4] Some time ago, I implemented an algorithm for ray/terrain intersection. I intend to use this for occlusion culling (cull whole blocks of 33x33 vertices).

[5] I also intend to port my texture synthesizer, which uses ecosystems. These ecosystems will also allow me to place trees etc. on the terrain (so that the trees are naturally distributed over the terrain).

[6] Front-to-back rendering of the quadtree.

*IF* I'm going to write that engine, then I'll also make the source publicly available. Of course, it'll take a while to implement it.

Anyway, I think I'll end up using LOD again, because:

[1] Distance-based LOD causes distant triangles to be coarser than closer triangles. This greatly reduces z-buffer artifacts.

[2] 3D accelerator can only render a limited number of triangles per second. If the terrain has too many triangles, then there's no resources left for other things, like tree, houses, sky domes et cetera. Think about this: You terrain is 1025x1025, and you look down on it so that you can see the whole terrain. If I display this with full-resolution then we are talking about 2M triangles. If I write really fast and hardware-friendly code, then I could perhaps (unlikely) achieve 18M triangles per second on a *GeForce2*. The result would be about 9 fps... terrible!



posted December 30, 2000 01:19 PM         
i'm enjoying your discussion, guys!
what a great name "Lithium Engine" - cool!

you guys play TreadMarks?

we need a map editor - it would be nice to have one with a preview, so if you want to add a little more functionality to you terrain engines, would you make us a map previewer? LDA could give you the TM specs... i dunno - i just thought it might help you (and us) you know - more practice & feedback for you & a previewer for us!

just a thought...

Black Widow Lance all the way, baby!


posted December 30, 2000 08:24 PM         

Rendering 20k trigs at 40fps seems about right with my card too,
LOD or no LOD. But, I have no idea what will happen with my program
at 1152x864x32. It will most likely be extremely slow.

I understand what you are saying about rendering limitations. Along
similar lines, I don't want to create just a pretty terrain renderer
that looks good from a single viewpoint. I want something along the
lines of Treadmarks, with real-time interaction and terrain collision.
If I can't drive a tank over it and obliterate it with a nuke, then it
is no good.

Right now, I'm pretty much statisfied with my quadtree structure, so
I will start doing texturing. I consider this to be the fun part.

I've never done this before, but I got some good ideas from the LDA
archives. What I would like to do is synthesize a single 1025x1025
texture, from 4 pixel colors (dirt brown, grass green, rock gray, snow
white) based on elevation. This will probably give me a flat, blotchy,
colorful texture.

Then I'll tile a single grayscale detail texture across the entire
1025x1025 texture and cut it up into 256 64x64 blocks. Probably
have to do something special with that 1 pixel border. Maybe it is
better to create a 1024x1024 texture instead. Not sure yet how to
choose which blocks I need when drawing my vertices.

I want it to be simple, so there will be no lighting calculations.
Just the blending of the 4 pixel colors based on elevation and the
final detail texture. Hopefully, this should look good enough.

And I would really like to add texturing that does not relate to
to terrain itself, like paths and roads. Perhaps I can do this
as a post-processing step, and add some dirt paths by hand in
Photoshop. That would mean my program wouldn't create the terrain
texture during run-time. I would have it already prepared for the
program to cut it up into smaller blocks.

But I doubt I will be at that point any time soon.


posted December 30, 2000 08:25 PM         

Hmmm... I just use the .VED files for heightmap data, but looking
over it again with my hex editor, it looks like there's a:

FORM header = 4 bytes + 34 byte data (format?)
HMAP header = 4 bytes + 1024*1024 heightmap data (0-255)
TXID header = 4 bytes + ? (texture ID?)
ECOS header = 4 bytes + ? (ecosystems)
ENTS header = 4 bytes + ? (entity systems?)
SCFG header = 4 bytes + ? (system config?)

All 3 of my .VED files have different file sizes, so there must
be variable-size data structures within the file. I really can't
make much of anything else.

Let me know if you have better specs, but perhaps you should
just wait for the official spec to be released.

As for the map previewer, if it was in real-time, it would be a
very time-consuming task. Someone should probably separate it from
the map editor if they wanted to do this. A map editor could only
take a couple days to complete, while a map previewer would probably
take a couple months.

However, the name "previewer" suggests that it doesn't have to
look exactly like it does in the game, so the previewer could display
a small windowed low-resolution grayscale image of the heightmap in 3D.
No ecosystems or detailed textures required. This could be easily
integrated into the map editor.

Besides, why have a previewer anyway, when you can just use the
TM engine to display it for you? Just set the no. of enemy AI tanks
to zero and you should be able to roam around it freely.

And also, there are special things like trees, tower structures,
and water. Do .VED files even specify these types of objects? If
not, then it would be difficult to create custom maps in the first
place. Maybe these are listed under the ENTS header, I don't know.


posted December 30, 2000 09:20 PM         
Just one more thing on the map editor/previewer:

You might have compatibility issues doing a previewer.

With a map editor, you're only editing a 2D heightmap image,
so I see no problems.

With a map previewer, unless you are doing the rendering all
in software, you're going to have to use some kind of 3D hardware.
And you need to decide how you are going to access that hardware,
using OpenGL or perhaps DirectX.

So depending on which programming API and what features you
want, you might have a lot people complaining they can't get
the previewer to run on their machines. I would probably pick
OpenGL, but then I know absolutely nothing about it.


Klaus Hartmann
posted January 02, 2001 05:32 AM            

Yes, texturing terrain can be a lot of fun Only problem is that is takes an enormous amount of time to make it look good.

If you are using a 1025x1025 height map, then a 1024x1024 texture will be way too small. This is especially the case if you intend to stay with that grid-spacing of 8. It would be better to split the terrain into smaller blocks, and then generate a 256x256 texture for each block.
The 1-pixel border is no problem. In a height field, each cell has four corner vertices. Each of these corner vertices has a material assigned to it. All you need to do now is to use a bilinear interpolation to interpolate between those four corner materials. The results of the interpolation belong to the texels that represent this cell (e.g. a cell could be represented by 4x4 texels in a 256x256 texture map). Now, if you think a bit further then you realize the following:
[1] A 1025x1025 height field has 1024x1024 cells, and therefore the 1-pixel border problem does not exist.
[2] Thanks to the bilinear interpolation you can easily make a texture of any size (scaling is easy).

Making the colors depend on elevation only won't look good, because this approach will give you very hard and unnatural transitions between the materials. So before you start to hardcode this stuff, you should make sure that you use an approach that can easily be enhanced. That means:
Make an eco-map. This eco-map is a 2D array that has exactly the same size as the height field, and it contains indices into an array of ecosystems. Each ecosystem has a material assigned to it, and therefore you have direct access to the four corner materials of each cell (via the eco-map). You can now have a separate function that precomputes the eco-map. If you need new features (like slope-based ecosystems), then you just add them to this function. The "render-to-texture" code, however, stays the same. An ecomap has more uses than this, so don't throw it away after you've generated the textures. It will make sense to have run-time access to the ecomap.

Lighting is something you don't want? Well, lighting (except shadows) is rather easy, and it only takes a few lines of code to support it. The visual difference is too important to just dismiss the lighting Terrain without lighting looks totally boring.

As for the roads... How about adding a new feature to the ecomap generation???



posted January 02, 2001 03:25 PM         
I am beginning to see if I can control the color of every pixel on the
texture using ecosystems, then anything on the surface, like roads,
dirt paths, tracks, and even water, would be possible. I would probably
have to create an eco-editor with special brushes to get the desired

But, let's just say for simplicity sake that I'm using a 1025x1025
heightmap and I'm not doing any scaling, so there would be exactly
1 heightmap cell for every texture pixel, so the final texture would
have a size of 1024x1024.

For each heightmap cell, there are 4 corners with colors assigned to
them. I would blend them all together to get the final pixel color for
that heightmap cell. This would be my basic rendering function.

But, you say that I shouldn't assign the colors of these 4 corners
based on elevation? Where is elevation used then?

To get good results, I think I have to use a combination of slope
and elevation. Slope could be the determining factor between the
current material based on elevation(dirt,grass,snow) and rock.
So rock can be at the lowest point of the terrain, or at the highest
point depending on the slope. But dirt, grass, and snow would
follow elevation. Dirt and grass would only be at the bottom, while
snow would only be at the top.


Klaus Hartmann
posted January 03, 2001 05:39 AM            
You wrote:
"But, you say that I shouldn't assign the colors of these 4 corners
based on elevation? Where is elevation used then?"

What I wanted to say is that pure height-based ecosystems are not enough. For example, height-based means: grass exists below 400 meters, and everything above 400 meters is rock. You should use rules that are a bit more complex (i.e. add other factors, like slope and azimuth). This'll make the texture look much more organic.

Some time ago, I wrote an unfinished paper about this (1.7 MB): http://www.thecore.de/TheCore/synthesis.zip
Note, that I'm not going to finish that paper, but it should help you to generate good eco-maps.


PS: Lithium, could you please send me an e-mail? I'd like to know your e-mail address, if possible. Don't worry, I don't want to take this discussion off the board... it's just that I have a few comments to add, and these comments are not ready for the public, yet (not yet, but soon


posted January 04, 2001 06:25 PM         
I've finally got my heightmap-based texture synthesizer working.
I have read your synthesis paper, and found it useful. But at
the moment, I'm still using simple factors like elevation and
slope to assign materials to my texture.

I think the way I scale my terrain may limit the color range in
some way. I scale the 0-255 heightmap values by 1/8, so it leaves
me with only 32 possible heights. This reduces detail a lot.
But I have to scale it this way to keep it in proportion with the
way I scale the xz coordinates.


New Member
posted January 08, 2001 09:17 PM         
To Lithium,
This is a really simple solution for your terrain texturing needs. Just use the slope.

I've been programming a game engine that uses ROAM. This is basically what I use (I believe Treadmarks does the same). I generate a 2048x2048 texture and break it into 256x256 chunks.

Anyways it looks good enough for my uses.

ps. Klaus, I read your eco paper last year. Cool stuff. If you did finish writing it, would the section dealing with "Lighting and Shading" just deal with calculating the innerproduct of the vertex normals with the light vector or would it be some raytracing deal?


posted January 09, 2001 02:23 AM         

I've seen that page before, but it doesn't quite explain how
it is applying its texture to the terrain. It shows how to blend
two textures by themselves together:

for(v = 0; v < 256; v++) {
for(u = 0; u < 256; u++) {
// etc..

But how is this texture being applied in relation to the terrain?

Ok, I think I might know, but let me try to describe it:

Given a 1024x01024 terrain texture, The terrain is divided up into
16 256x256 blocks. So let's say we have 4 pure material textures
(grass,dirt,rock,snow) that are themselves 256x256 in size. For
each 256x256 terrain block, all 4 material textures are blended
together, depending on factors like slope and elevation. This
continues, block by block, until the entire terrain is textured.
Does this sound correct?

Hmmm...if this is right, then I am doing it all wrong. At the
moment, I'm not even using whole material textures. I'm using
pure colors instead as my material. After I blend the 4 colors
together, I tile a detail texture across the entire terrain
in small blocks.

Perhaps using textures instead of pure colors is better?


Just to let you know, I've added simple lighting to my texture
synthesizer. I'm using the lighting formula described here:

It was easier than I expected.

btw, I also have a question about your eco paper. In the paper,
you describe a function to get the normal at a heightmap vertex,
using delta height distances. Is it possible to modify this,
to get the normal of plane, instead of a vertex? I suppose I
have to call this function for each vertex of the plane I want?


New Member
posted January 11, 2001 02:56 PM         
Your first statement is essentially correct.
The objective of this is to CREATE a large texture by tilling smaller textures. TM uses 2 64x64 texture "blocks". The creation of the large texture map would go like (before runtime):

calc blend value
newTexture[u][v]=t1[u%(TILESIZE+1)][v%(TILESIZE+1)]*blend + t2[u%(TILESIZE+1)][v%(TILESIZE+1)]*(1.0f-blend);

This is your terrain texture, your material textures aren't needed anymore. I divide the terrain texture into 256x256 chunks just for 3dfx cards, otherwise you can store the terrain texture all in texture memory and apply it like:

textureScale = 1.0f/ heightMapSize;
glTexCoord2f(textureScale * tri->vertex1[0],....);

As for the surface normal algorithm, I think that you should just pluck out 3 verticies and take the cross product of 2 vectors. I think you can also use the delta slopes of the two diagonals of a quad like you would to find the normal of a vertex, but this would be a normal of a quad, not a triangle. Quads usually do not have a single definite normal.

[This message has been edited by Kgen (edited January 11, 2001).]


posted January 11, 2001 03:13 PM            
This is a side note on the Normals.

Wouldn't it be better to get the normals of all 3 vertices, then seeing how they're shared vertices, also calculate their normals relative to other triangles that might be formed from them. Then take the average of these 6-8 normals and use that?

The reason I say this is if you do this, your terrain will have proper lighting.

I haven't even attempted this myself, but it just seemed to make sense...


Klaus Hartmann
posted January 11, 2001 04:43 PM            
I'm sorry for being so silent, but I'm buried with work

Lithium -- I believe it is possible to use the delta-height-distances to compute the normal of a triangle's plane in a regular grid, but why would you want to? If it's for the lighting, then you can better calculate the normals at the four corner of each cell, and then use bilinear interpolation to generate normals inside the cell. (Do NOT use this approach for collision detection, because it is NOT mesh-exact). If you need true face normals then use the standard cross-product approach.

Lithium -- You should definitely use material textures when you synthesize your surface texture. Those material textures should be seamlessly tilable, because you'll need to repeat them over the surface texture. And by all means... make your surface texture larger than the height field. This isn't really difficult.

Kgen -- The section about "Lighting and Shading" would have dealt with Phong-shading (using the dot product). I am a bit familiar with ray-tracing terrain, though, so I might be able to answer specific questions.

binaryz -- You described the standard approach for calculating vertex normals: "average the face normals of all faces that share the vertex". For regular grids (e.g. height fields), however, there's a better approach, namely the one presented in my paper.



posted January 11, 2001 06:52 PM            
Is your paper on terrains available to others? If so could I possibly get a copy? I'm fairly new at this and any help would be appreciated.

I've read 2 articles so far and one was on ROAM and the second was on BSP (which didn't have anything to do with terrain)

Thanks for the help.


posted January 11, 2001 08:11 PM         

Thanks, you're right, collision detection was my intention. I have no
peformance issues with using the standard CrossProduct, I was just wondering
if I could generate faster plane normals using your function.


A link to the eco paper was posted above: http://www.thecore.de/TheCore/synthesis.zip


New Member
posted January 13, 2001 09:59 PM            
Hey guys, have you seen Willem H. de Boer's paper on Fast Terrain Rendering Using Geometrical MipMapping? Go here: http://www.flipcode.com/tutorials/tut_geomipmaps.shtml
I am not expert enough to know if there is anything interesting there, but it is fairly recent and not well known yet.
Let me know your thoughts.