# OpenGL Implementing LOD based Terrain

This topic is 2915 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hey folks! Im currently trying to implement a satisfying terrain with LOD. My requirements are:
1. Tremendous height map => streaming
3. More might appear while I progress, but right now its just those 2...

I would like some advanced people to guide me through this... I have already implemented (2^n + 1) x (2^n + 1) height map convertion into the simple quad tree of chunks, which contain their own VB, IB and AABB. The incoming information for this convertion is:

1. Height Map size: (2^n + 1) x (2^n + 1);
2. Vertex number per quad: vertexNumberPerQuad = 2^i + 1, i = 0...n =>
=> Number of LODs (quad tree depth): numberOfLODs = (n + 1) - log2(vertexNumberPerQuad - 1), so 1 <= numberOfLODs <= (n + 1);
3. Root deviation;

I compute deviation for each chunk as:

Deviation(L + 1) = Deviation(L) / 2

On rendering stage all I do is traversing top-bottom this tree and cheking a simple equation:

p = K * (d / D), K = viewport_width / [2 * tan(horizontal_fov / 2)];

p - maximum screen-space vertex error;
d - deviation of current chunk;
D - distance from camera to the center of AABB of current chunk;

As you can notice on the picture I use triangle strips "snake" approach to render a chunk.

For now thats it (quite simple right? :])... I can't go further due to the lack of experience and poor knowledge of recent trends in this subject, moreover its a little bit hard for me to understand algorithms, while reading papers, since papers are very short and provide little information...

So first of all, tell me if I am heading the right way by making a kind of "Chunked LOD"?

And, secondly, if I am on a right way, then it seems like the next step is crack elimination: which approach would you recommend? Personally I dont like skirts, since they might look ugly when textured. But avoiding skirts leads to 2 different approaches that have problems, which I dunno how to solve:

1. If adjacent chunks differ in 2 or more LODs, I have to omit more than 1 vertex in a T-junction;

2. If I stick stricktly with a rule "adjacent chunks may differ only in 1 LOD", consequently I get another headache - make some restricktions to quad tree;

Have no idea about both :[
I also appreciate any suggestions about mixing different algorithms!

Using OpenGL + Java btw. Thanks!

[Edited by - Haroogan on October 21, 2010 3:45:15 PM]

##### Share on other sites
If you're going stick with geometry based terrain, you can use RobMaddison's Terrain LOD stitching on the GPU. It's very easy to implement (4 lines of shader code). BTW Rob, if you read this, please check your PM's lol.

Quote:
 Original post by spaceratWhy using triangles ? Its easier to raycast the terrain - you dont need to worry about geometry in this case.http://msdn.microsoft.com/en-us/library/ee416425%28VS.85%29.aspx

niiiiiiice!

##### Share on other sites
First of all I dont really understand whats the essence of raycasting and why is it good for terrain? Does it simplify terrain assembling? Does it simplify texturing and lighting? Does it bring decent FPS rates...? And is it useful in making planet-like terrain, since, for instance, chuncked LOD is!

Well about Rob Maddison... ummmhh, u know his algorithm is described too shallowly, isnt it? Again the lack of direct and structured information :[

##### Share on other sites
Quote:
 Original post by HarooganFirst of all I dont really understand whats the essence of raycasting and why is it good for terrain? Does it simplify terrain assembling? Does it simplify texturing and lighting? Does it bring decent FPS rates...? And is it useful in making planet-like terrain, since, for instance, chuncked LOD is!Well about Rob Maddison... ummmhh, u know his algorithm is described too shallowly, isnt it? Again the lack of direct and structured information :[

There's an executable of the raycasting sample in the dx sdk.

I could actually extract enough information out of Rob Maddison's post to write a well working implementation. After being stitched with his algorithm (which is basically a modulo operation on the patch edges) the grid looks like this:

##### Share on other sites
Before you start with raycasting on such a scale, you should consider a few things:
- Raycasting does not (cannot) make use of MSAA (other than triangles)
- Cone step mapping as proposed in this article, requires non-trivial preprocessing. We are talking about several minutes to hours for a large texture. Editing in or close to real time is out of the question.
- Most other raycasting algorithms are either very slow or inaccurate (or both).
- Raycasting requires the pixel shader to output depth for proper results, which means you have no Z-Cull

##### Share on other sites
>> why is it good for terrain?

you can do terrain with displacementmapping in one pass

>> Does it simplify terrain assembling?

yes - you have unlimited geometry details and no trouble with triangle count

>>Does it simplify texturing and lighting?

no - thats the same

>>Does it bring decent FPS rates...?

yes. my volume terrain raycaster gets about 100fps just for the terrain without SSAO&SSDM (
>
)

>>And is it useful in making planet-like terrain, since, for instance, chuncked LOD is!

if you need a complex distance or angle function to calc the texture coord on a sphere it might slow down...

##### Share on other sites
So u've dropped down ur FPS to 100 just by adding terrain on GTX 285? lawl... How about additional geometry and high polygonal animated models then? And as I understand raycasting is able only on very recent graphic cards right?

"During this stage, fill in a matrix of LOD levels - for a 4096x4096 terrain with a 32x32 high-LOD patch size, this involves filling a matrix of [128][128] - but only those elements that fall within the viewing frustum and only the outer edges of each of those elements need to be set."

What matrix? Does he mean just to create a 2-dimensional array of 128x128 and fill it with pointers to chuncks that are going to rendered, and those who shouldnt be rendered must have null pointers in the appropriate position of this 2-dimensional array? He wants to do it every frame?

"and only the outer edges of each of those elements need to be set."

What are outer edges of those elements?

"I believe this is standard practise for pre-determining the LODs of neighbouring patches."

After filling this matrix he learns about neighbours of each chunk? How?

"front-to-back-sorted"

WTF?

BTW, ur screenshot looks like GeoClipMapping, I mean nested LOD layers?

[Edited by - Haroogan on October 23, 2010 5:10:54 AM]

##### Share on other sites
Quote:
 Original post by HarooganWhat matrix? Does he mean just to create a 2-dimensional array of 128x128 and fill it with pointers to chuncks that are going to rendered, and those who shouldnt be rendered must have null pointers in the appropriate position of this 2-dimensional array?

Yes i think you got it. You first figure out which nodes are going to be rendered and write their LOD's (or pointer to the node) into the matrix. If a node isn't visible, you don't have to write it into the matrix because invisible nodes don't cause cracks :)

This is blazingly fast since you only do the outer edges. You could bake the LOD-Matrix on the GPU but it's not even worth it. Here's my code for this step:

void CeTerrain::buildRenderQueue(node& n){	if(!Ce::cam->InFrustumAABB(&n.aabb)) return;		n.lod = max(n.depth / 2, computeLOD(n));	if(n.lod <= n.depth)	{		UINT nodeSize	= lodMatrixSize / n.depth;		UINT coord	= n.pos.y * lodMatrixSize + n.pos.x;		node** lodPtr	= &LODMATRIX[coord];		for(UINT i = 0; i < nodeSize; ++i)		{			*(lodPtr + i * lodMatrixSize)				= &n;			*(lodPtr + i * lodMatrixSize + (nodeSize - 1))		= &n;			*(lodPtr + i)						= &n;			*(lodPtr + i + lodMatrixSize * (nodeSize - 1))		= &n;		}		renderQueue.push(&n);		return;	}	for(UINT i = 0; i < 4; ++i) buildRenderQueue(*n.child);}

Quote:
 He wants to do it every frame?

Only when the camera moves, unless you have some kind of animated terrain.

Quote:
 What are outer edges of those elements?

I can best explain it with an image. The colored borders are the edges of the nodes.

Quote:
 After filling this matrix he learns about neighbours of each chunk? How?

You look it up in the LOD matrix or you store pointers in the nodes to the neighbours in the LOD matrix and just dereference them before you render the node.

Quote:
 "front-to-back-sorted"

This would just require to push the nodes into a priority queue with the distance as comparison key. Or use a vector and sort it after the LOD step. It's not required but prevents some overdraw on the GPU for better performance.

Quote:
 BTW, ur screenshot looks like GeoClipMapping, I mean nested LOD layers?

Hugues Hoppe's geometry clipmaps are a little different as far as i can tell.

[Edited by - Daniel E on October 23, 2010 11:23:55 AM]

##### Share on other sites
For completeness, here's the shader code for stitching patches on the GPU:

with conditions:
VS_output vs_terr(VS_input input){        VS_output output;	float4	pos = { input.pos.x, 0, input.pos.y, 1 };	if	(pos.x < 0.5f)			pos.z -= pos.z % nLODs.x;	else if	(pos.x > NUMVERTS - 0.5f)	pos.z -= pos.z % nLODs.z;	if	(pos.z < 0.5f)			pos.x -= pos.x % nLODs.y;	else if	(pos.z > NUMVERTS - 0.5f)	pos.x -= pos.x % nLODs.w;}

no conditions:

VS_output vs_terr(VS_input input){        VS_output output;	float4	pos = { input.pos.x, 0, input.pos.y, 1 };	pos.z -= input.isEdge.x	* (pos.z % nLODs.x);	pos.z -= input.isEdge.z	* (pos.z % nLODs.z);	pos.x -= input.isEdge.y	* (pos.x % nLODs.y);	pos.x -= input.isEdge.w	* (pos.x % nLODs.w);}

1. 1
Rutin
29
2. 2
3. 3
4. 4
5. 5

• 13
• 13
• 11
• 10
• 13
• ### Forum Statistics

• Total Topics
632959
• Total Posts
3009464
• ### Who's Online (See full list)

There are no registered users currently online

×

## Important Information

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!