Terrain Rendering

Engines, Libraries and Tools Xith3D Forums
#1

Howdy again … guess it’s time to contibute something useful again ( looks at his last posts )

in this thread i’d like to discuss some terrain rendering specific topics
the last two or three weeks i was reading some articles and now the org.xith3d.terrain packages gets orphaned … so i’d like to start some talking

i’ll post two posts first:

  • a small overview about common technics with pros and cons
  • some thoughts that i’ve developed during the last weeks and like to have some comments on

ok … enough talking … i’ll start writing the first post now

#2

ok … back again :wink:

this post is about common technics of terrain rendering. Some of them became obsolete when those high powered graphic cards came out … and some won’t get listed here … but i’ll do my best to give you a small overview about this topic

In the beginning …
… there was the developer … he was able to talk software and he thought it was good as long as he wrote the best alghorithms.
The developer thought it would be cool if he’d be able to show large terrains on the computer screen and developed voxel terrain engines. The results looked beautiful and the developer was happy.
( have a look at http://www.outcast-thegame.com/ fro some examples )

Voxel Engines
Actually i don’t know nothing about voxel terrain rendering … and list them here just for completion :wink: … but voxel terrain is calculated entirely in software, stressing the cpu on large terrains … i read somewhere that there may be a voxel comeback due to the large calculation power of current cpus … but i don’t really believe in this cause nvidia’n’co will build larger gpus too and all terrain rendering will be based on polygons … but … who knows …

Introducing Polygons
… the developer was greedy … and he thought of new ways of rendering larger and better terrains … one of this ways was polygon rendering … but soon the developer found out that it was necessary to decrease the number of rendered polygons in order to render large terrains … and again he sat down and thought about better algorithms … he came up with an approach that would be called ROAM which could decrease the resolution of the rendered terrain where necessary …

ROAMing Terrain
ROAM … short for Real-time Optimally Adapting Meshes … is a way to render large terrains with the minimum number of polygons necessary …
there are two major implementations of this: split and split/merge roaming
they both have in common that they rely on splitting a isoscele triangle in two new isoscele triangles:

     *
    / \
   /   \
  /     \
 /       \
*---------*
parent triangle

     *
    /|\
   / | \
  /  |  \
 /   |   \
*----*----*
two new triangles ( children )

(hopefully this is understandable)

the difference between the two implementations ( split; split/merge ) is that with just splitting the whole splittree is recalculated each frame whilst with split/merge the tree is kept in memory and there are checks for each triangle wether it is necessary to have the higher resolution … else the triangle is not splitted if it has no children … or the children are merged into the parent triangle

the decision wether to split or not varies from implemtation to implementation … but i think a screen pixel error based solution will work best here … ( more on screen pixel error further down )

if a triangle won’t be splitted it will be send to the graphics pipeline to be rendered

the pros:

  • very dynamic resolution just depending on the decision algorithm
  • as the terrain is recalculated each frame dynamic terrain is easy to implement
  • very low memory usage cause no per vertex data is kept
  • allows for frame coherence ( just split until the frame time is up )

the cons:

  • gaps: actually gaps are found in every terrain implementation at places where a higher and a lower resolution piece of terrain hit each other … in roam this is avoided by an easy algorithm based on splitting the base neighbour if necessary
  • time: the terrain is recalculated every frame, there are ways to avoid this but they would require dynamic triangle counts which are as far as i know not avaible in xith
  • doesn’t use any hardware optimisations

references:

Introducing Hardware
… but the developer was restless … he found that there were graphic cards with high memory on them and he decided to transfer as much load from the cpu to the gpu as possible … he found that there was the possibility of using some technics of imaging in his work and came up with geomipmaps

Geomipmaps
in mipmapping there are several copies of a texture stored in memory each at a half the resolution of its parent
as modern graphic cards have huge memory banks on them these copies can be stored on the cards freeing ram and allowing for fast transfer to the graphic processor
geomipmap terrains consist of several evenly spaced blocks which i like to call patches
these are layed out in a binary or quadtree allowing for fast culling as a first optimisation
for each patch there exists precalculated data representing the terrain of this patch at different resolutions
level 0 means full resolution, each higher level means half the resolution of the last level


*---*---*---*---*
| \ | \ | \ | \ |
*---*---*---*---*
| \ | \ | \ | \ |
*---*---*---*---*
| \ | \ | \ | \ |
*---*---*---*---*
| \ | \ | \ | \ |
*---*---*---*---*
level 0 resolution

*-------*-------*
| \     | \     |
|   \   |   \   |
|     \ |     \ |
*-------*-------*
| \     | \     |
|   \   |   \   |
|     \ |     \ |
*-------*-------*
level 1 resolution

the decision which level to choose is again implementation dependend … i’d recommend screen space pixel error calculations:
it’s not that hard to understand: for each patch the maximal change in height per level is precalculated than it’s checked if this change results in a user seeable popping. This is done using the viewport and some easy calculations ( ok … i confess that i write this somehow unprepared and have the papers not at hand :wink:

the pros:

  • uses the benefits of current hardware to free the cpu from calculations
  • allows free detail levels
  • very fast

the cons:

  • more memory requirement than other approaches ( but graphic card memory is used )
  • terrain changes require recalculation of patches
  • gaps: as above need some tweaking to avoid these

references:

Beauty
the developer was happy with his work … however he was annoyed with the popping of terrain that happend sometimes …
he thought that if he could find some way to slowly morph between two states of detail he would be pleased …

Geomorphing
this is essentially easy: take the to detail levels and define a function that gives level a if you put 0 in it and level b if you put 1 in … than calculate this over several frames … the result is a smooth ‘morph’ between two detail levels
( ok … it’s not that easy … but i think it’s easy to understand that way )

as you remember correct the vertex data of the geomipmap approach is stored on the graphic card … this is where newest features of graphic cards kick in: vertex programs are able to modify vertex data before it is rendered on the screen.
geomorphing can be implemented as a vertex program which reduces cpu load alot

( actually i can’t say more on this topic cause i’m waiting for my new graphic card since one week now … and so wasn’t able to work with vertex programs etc )

Rest
the developer was happy with his work … and set down to rest
i’m not that happy about my article as it just covers two technics … but i decided that these are the easiest ways to render terrain … and i believe they are the ones most suitable for xith … there are of course other interesting ways, terrain rendering got some sort of academic disciplin … but …
let’s Keep It Simple, Stupid

any questions on this first post can be posted here … i’ll take some time and continue with the second post …

#3

ok … i’m back …

in this second part of my writing i’ll try to explain what kind of terrain implementation i’m aiming at
if you have any questions please feel free to ask

Representation of the Heightdata
although the usual way to handle height data is a heightmap, represented by a grayscale bitmap, i’d like to show that there are other ways without giving up compability to the old method

Normalized Heightspace
under this definition i’d like to define an area in 3d space which is exactly 1x1x1 units
if you’d look at this area you’d see a representation of an terrain with evenly spaced points acting as it’s heightdata
no matter how large the terrain resulting from this data is every coordinate is inbetween 0.0f and 1.0f

http://the-hellboard.de/attachment.php?attachmentid=1846

this is a graphical representation of what i tried to explain above

HeightSpace Interface
to implement this in java i provide an interface which has these features:

float getHeight( float x, float y ):
gives you an normalized heightvalue for this point … x and y have to be between 0 and 1
the result is also between 0 and 1 ( except for a some times i’ll explain below )

float getMinResStep():
gives you the number that a value has to be increased to get the next height value
Example:
you have an 10x10 field heightmap. getMinResStep would give you 0.1f cause you’d have to increase for example 0.0f by 0.1f to get the next heightvalue

ok … now i said before that there are exceptions, that the returned height sometimes is not between 0 and 1 …
i’d like to have the functionality that parts of the terrain aren’t rendered so if getHeight() returns a value < 0 a flag is set
if a triangle has this flag for all of it’s 3 vertices it isn’t drawn … easy huh?

Implementations of HeightSpace
ok … now you may shake your had and think ‘that boy’s crazy or stuff’ … but i’d like to show you the benefit of this way
the old approach of representing heightdata is to get a greyscale image and make a terrain from that, but there are numerous ways to represent height data … for example you could ( and i’ll try to implement that one ) use a quadtree which nodes are bezier patches … this would provide almost unlimited detail heightdata … and thats the reason HeightSpace does have a getMinResStep and no getNumOfHeightValuesPerSide

Terrain Mechanism
i think the system should use a geomipmapped approach just like the one in org.xith.terrain … a heightspace object is loaded and then scaled to fit the users wishes … although i’d like to add the optimisations mentioned in the above post. geomorphing is implemented as a vertex program but if this isn’t avaible old fashioned software calculations should be used

Interoperability with level geometry
there are two things i’d like to say about this:

a: detail geometry and stuff
quadtree based frustumculling speeds up terrainrendering alot … but it can do more. My implementation ( which honestly is far from complete ) uses the xith scenegraph and culling for it’s culling … now if i would add level data ( for example trees buildings etc ) directly in this quadtree alot culling calculations could be omitted when for example one topnode of the quadtree is out of bounds
this of course would work just for static or static animated stuff or would need some coding that objects can change it’s parent quadtree part

b: indoor levels
remember when i said i’d like holes in my terrain?
in this holes i’d like to add indoor geometry … if the terrain would be rendered at these places it wouldn’t be possible to go deeper than the heightmap

Textures
actually i was very dissapointed by the Terrain demo cause it was plain greyscale
the texture should feature a 2 texture surface
the one texture defines the overall look and should be created from several images and the heightdata ( for example everything above 0.8f uses the snow image ) … this texture is scaled all above the landscape and should fit with mountains and valleys
the other texture is a detail texture which is scaled at a much lower rate so that it repeates all over the terrain

Conclusion
I think that should be it … it’s much … but it’s just enough for xith :wink:
as i mentioned i have some parts of this already implemented … but nothing is yet presentable
nevertheless i’d like to see some nice comments and stuff … :wink:

Florian

#4

Wow, wow, wow nice job explaining all this !!! :slight_smile: I actually like the idea of bezier patches very much. Oh yes! a function for the terrain, where you simply can say getHeight(x,y) that returns you a height value for any x,y value would be a nice idea to start with. Then you can also have dynamic positions for the vertices.

About coloring the Terrain:
For that I have in my terrainloader a alphamap, that specifies the visibility of a texture, and then I layer different textures above each other:

snowsnow_alpha
+
grasgras_alpha
+
sand*sand_alpha

the alpha textures are not wrapped, they span over the entire terrain, but the can contain a pretty low resolution
the other textures are wrapped, so allow a pretty detailed ground.

Pros:
Terrain is easy to paint (you’ll only need some pictures)
Nice slow fades are possible

Cons:
Lot’s of layers are needed (some graphic cards got only a low number of TextureUnitStates e.g. 2)
For this the Geometry would have to be created several times and then put above each other with some distance (which is visible)

There’s also a fix for the duplicate creating of the Geometry, simply to split the terrain into several chunks and then to don’t create the terrain that never is possible to be seen (either because the alpha-texture is there completely transparent, or because there is an totally opaque layer above).

Arne

#5

What about:

You can also do this with fragment-shaders.

#6

actually i don’t think this is a good idea …

i prefer the implementation that is used in the jme terrain system
there you have a texture constructor which first takes a heightmap
than you register several textures and specify at which heights this texture is used
then you tell the constructor to create the terrain texture and you get a new texture with smooth blended transitions

have a look at the jme system to see this in action …
not much time … Florian

#7

TextureBombing technique demo (Delphi sourcecode but rather easy to port Java) and terraingtexture demo.
http://www.delphi3d.net/download/texturebombing.zip
http://www.delphi3d.net/shotpop.php?image=download/texturebombing.zip_b.jpg
http://www.delphi3d.net/articles/viewarticle.php?article=terraintex.htm

#8

Take a look at the “More fun with texture” tut on xith.org, it shows alpha mapped textures (animated) in a decalgroup

http://xith.org/tutes/GettingStarted/html/more_fun_with_textures.html#SECTION00073000000000000000

#9

so … .back

i must confess that i’m not that conviced by whome’s article cause it uses too many texture unit states and i think that an open library should sacrifice performance where compability is needed

in my opinion 2 texture states should be enough to give a nice looking terrain which is usable even on older graphic cards ( think gforce 4 downwards i guess )

if i got it right the splashshape thing uses multipass rendering does it? guess that would affect performance alot altough i don’t know how far …

on the other hand we have an advantage cause we have seperate patches which could get different detail textures
with, say, 5 different detail textures the ‘repeat-effect’ wouldn’t be that strong … if these textures would be freely rotatable ( with each edge fitting to each other edge from any texture ) this would result in a large amount of combinations …
but that would restrict the user alot cause it’s not that easy to get those edgefitting textures …

actually i’m no expert with textures … but i think a better solution should be found … and if there aren’t any good i guess we should fall back on the ‘overall+detail-map’ scheme cause it is ( in my eyes ) the most commen used

Florian

#10

2 texture unit states are a must, or I’m not in the team (I’ve only got 2 :confused: )

We could write a simple tool that makes any texture freely rotatable, so this should actually be not a restriction.

Arne

#11

yep … i’ve 2 unit too :slight_smile: …

i had a look at the demeter terrain engine and now i think it’s a good idea to use the splat shape approach cause it allows ( of course almost ) unlimited textures on the terrain …
i’d give the user a ‘splat texture at point on terrain’ function too … this way he’d be able to easily add trails, roads, and stuff to his landscape without having to deal with creating additional geometry and fitting it exactly to the terrain ( z buffer problems )

Florian

links:
Demeter Engine - > www.terrainengine.com

#12

That would be sweet!

Will.

#13

howdy again …

the good news
i think i found the ultimate heigthmap representation 8)

the bad news
i’d like to give you a full description here … but i’d like to accompany it with at least a simple techdemo
unfortunatly my new job grants me much less time than i originally thought, leaving me with about half an hour free time a day …

the deal
i’ll give you a little feature overview and’ll try to implement it over the weekend which actually shouldn’t be that hard cause it is really simple … ( an other thing i’ll do is to search the web cause it is really that simple that i don’t think nobody have done this before )

the name
i like to call it “Ultimate Height Data” … ::slight_smile:

features

  • can use both bezier ( “unlimited resolution data”) and ordinary ( “heightmapping” ) mode ( maybe even in the same height data )
  • when using ordinary mode almost no overhead exists ( actually i have no proof for this right now … but as ordinary mode uses very simple math this may be true )
  • provides full interpolation even in ordinary mode
  • provides normals that should be exacter and faster to create than NWA or NWE ( another guess … but as it doesn’t work on a x times per vertex level and is simple math again … i might be right again )

last words
i like bold char settings … :wink:
Florian

#14

nice :slight_smile:

But I think the most processing time will be needed anyways for setting the vertices to their positions, when changing LODs, and specially if we have smooth LODs, which would then be possible :slight_smile:

Even if this is like I think it is:
good+bad is still better then bad+bad :wink:

Arne

#15

can i use tthat demiter engine in my game for terrains?

really looking for an esay to use terrain creator/loader for my xith3d thing

#16

On the multitexture unit front.

Radeon 9000 and above have at least 6 TUs.
Geforce 3 and above have at least 4 TUs.

Only when you fall below to Radeon 7500 (3 TU) and Geforce 2 (2 TU) do you see such low multitexture unit counts. Your decision concerning how many TUs to require certainly depends on your target audience, but I personally wouldn’t lose any sleep over getting terrain to render in 2 TUs.

#17

yeah, but if the developers only got 2 …

#18

on terrain rendering… has anyone used a combination of perlin noise (infinite terrain) and local heightfields as a means to soften the noises locally ?

That way, one could have a very large terrain (a planet ?) with locally defined zones (e.g. hand made towns / grounds)

Lilian

#19

If you want to soften the heightfields at certain locations, just blend it with another layer of very-very-low-frequency perlinnoise:


float hiFreqNoise = hiNoise.get(x, y);
float loFreqNoise = loNoise.get(x, y);

float noise = hiFreqNoise * lowFreqNoise;

But before it suits your needs, you’re doing the funkiest math with lots of noise-layers. Been there, done that, still recovering from the headache. :-\

#20

What about having an interface like

public interface TerrainData {
  getHeight(float x, float y);
}

and another class that set’s vertices according to TerrainData’s height-values like

public class Terrain {
  public void setHeightMap(TerrainData d);
  public Shape3D getShape();
}

Then it would be possible to simply implement TerrainData, to use your very own data-structure.

maybe Terrain could also simply extend Leaf (then the scenegraph wouldn’t have to get updated (e.g. when you want to change the LOD), because it’s then a direct part of the scenegraph)

Arne