ok ... back again

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
[size=12pt]
In the beginning ... [/size]
... 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 )
[size=12pt]
Voxel Engines[/size]
Actually i don't know nothing about voxel terrain rendering ... and list them here just for completion

... 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 ...
[size=12pt]
Introducing Polygons[/size]
... 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 ...
[size=12pt]
ROAMing Terrain[/size]
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| * / \ / \ / \ / \ *---------* 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:
- an article with the title "ROAMing Terrain: Real-time Optimally Adapting Meshes" by ... hmm... someone with the name Turner i guess ... the article can be found on gamasutra.com here:
www.gamasutra.com/features/20000403/turner_01.htm[size=12pt]
Introducing Hardware[/size]
... 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
[size=12pt]
Geomipmaps[/size]
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| *---*---*---*---* | \ | \ | \ | \ | *---*---*---*---* | \ | \ | \ | \ | *---*---*---*---* | \ | \ | \ | \ | *---*---*---*---* | \ | \ | \ | \ | *---*---*---*---* 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

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:
- some articles at
http://vterrain.org[size=12pt]
Beauty[/size]
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 ...
[size=12pt]
Geomorphing[/size]
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 )
[size=12pt]
Rest[/size]
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 ...