14 replies to this topic

[ekba89]

Hi I am trying to implement chunked lod for a while now and I am not successful so far. I read the paper about chunked lod and understood the main system but it doesn't have anything about implementation. And I looked the code he published but it was missing how he ensures every child chunk has half of maximum geometric deviation of its parent. He is reading that value from terrain files. So should I read/know other things before understanding chunked lod or am I missing something? Also there aren't any implementations of chunked lod other then his. Is it because there are better ways for large terrains now or it is implemented by commercial products so they don't want to share their code publicly? Thanks.

[Krohm]

What paper are you reading in particular? Nothing of your message makes sense without pointing out the exact paper. The code he published... who is he?
My opinion on terrain algorithms, condensed to be as simple as possible

• Small organic patches: brute force
• Generic terrains: hierarchical geomipmapping
• Large/streaming/infinite terrain: geometry clipmaps

In GeoMipmapping the deviation is simply a function of the distance between the interpolated value and the missed sample.
Geometry clipmaps don't care about the deviation, they exploit Nyquist Theorem so nobody really cares.

[ekba89]

Thanks for the reply and sorry I forgot to mention it. Here is the page for it and here is the paper T.Ulrich wrote. Also you can download his code here. And as I mentioned before I don't think there are any resources other than this one for chunked lod technique. People say chunked lod is easy to implement but I don't know if they are saying this just by reading the article and without actually implementing it. Because as I mentioned he is loading one of the most critical value from his terrain files or maybe it is really easy and I am missing something.

[Krohm]

As a start, when you read stuff about chunked LOD, it's probably about stuff that fits in RAM. Most people just assumes terrain data will fit. I have myself tried an algorithm which blew 150+ MiB of RAM with no remorse.
The algorithm you pulled out is quite old but still good at its core. I think you might be missing part of the picture, it appears the deviation is a result of a preprocessing step. I'm not going to look at the code, but I suspect he's doing something like:

That is, the error is probably the length of either the blue lines or the yellow lines. I general Discrete LOD starts from finding an error we want to allow for each mesh level and removes every vertex which contribute to correctness less than we want. That is something like
[source lang="java"]foreach vertex if(abs(value - LinearNeightbours()) < EPS) discard;[/source](that would evaluate the length of blue lines, this code is just food for thought). The biggest error is stored in the .CHU file (I'm guessing that's the "terrain files" you're referring to). If you think at it, you might see this is not really as easy as it seems. For this reason, I suggest to look at either more modern approaches OR easier approaches. In particular, I suggest to look at geomipmapping, which works in reverse: instead of selecting vertices to drop based on a error metric, it drops vertices using a simple logic (every odd vertex) and obtains a deviation from there. For densely tessellated height fields that works rather well. The various chunks can still page to disk or assembled in hierarchical fashion (albeit most people using geomipmapping does not seem to be aware of that. Geomipmapping is older than your paper but I think it provides better value as it probably takes less to implement and avoids dealing with not-quite-regular grids. Think at it.

[ekba89]

Thanks again for the reply, I didn't see that slides page so I'll look it now if it has any different information than the paper. Also I looked geomipmapping but as you said it can still be used but a little outdated. And as far as I know chunked lod allows you to create bigger terrains than geomipmapping and I really like games with large terrains. Currently I don't have any purpose I am just trying to learn some populer techniques about game programming and I have never worked on terrains before thats why I started to learn chunked lod. What I don't understand about his error metric is he says every successive lod level has half of its parent error. Meaning Error(L+1) = Error(L)/2. How does he ensure that or does he just assume that it is like that for simplicity? At first I thought he is trying to find the first child which has smaller-equal error to Error(L)/2 and assign it as L's child and discard other children between L and the child he found. But with this technique it is virtually impossible to get exact error value of Error(L)/2, you can only get close to it. And I really appreciate if you have any suggestions about other modern approaches.

Edited by ekba89, 21 July 2012 - 06:08 AM.

[Frenetic Pony]

If you want something BIG and modern I'd suggest taking a look at this: http://www.slideshare.net/DICEStudio/terrain-in-battlefield-3-a-modern-complete-and-scalable-system

[Krohm]

For first I figured out I've written something really wrong in my previous message. Meshes are progressively refined from coarsest to finest and not vice versa (I wrote this hoping it would help you understand the process but I guess it's not valueble).

• I looked geomipmapping but as you said it can still be used but a little outdated.
• And as far as I know chunked lod allows you to create bigger terrains than geomipmapping
• What I don't understand about his error metric is he says every successive lod level has half of its parent error. Meaning Error(L+1) = Error(L)/2. How does he ensure that or does he just assume that it is like that for simplicity?
• And I really appreciate if you have any suggestions about other modern approaches.

• No. I said it is old. Not outdated. No discrete LOD system producing static geometry is truly outdated. By contrast, most continuous LOD schemes are outdated in my opinion. Let me be clear: Geomipmapping is NOT better, it's just easier to deal with IMHO.
• This is a common misconception. Again, most people will never have to deal with the paging problem. Nothing prevents geomipmapping from being paged to disk. Terrain clipmaps suffers from a common misconception: the algorithm itself is based on "fitting a grid on the terrain signal", while the paging is a basically orthogonal problem but if you ask around everyone will say terrain clipmaps are natively paged. They are not completely wrong either as this is what the term "clipmap" is typically used for.
• (I assume you're talking about Geomipmapping) It's a direct consequence of doubling the sampling frequency. Draw it on paper on 1D.
• I already listed three methods in my 1st message. But I'd add one. The possibility of traversing the heightmap with raycasting.

[ekba89]

If you want something BIG and modern I'd suggest taking a look at this: http://www.slideshar...scalable-system

Thanks I added it to my favorites, I'll look it later.

For first I figured out I've written something really wrong in my previous message. Meshes are progressively refined from coarsest to finest and not vice versa (I wrote this hoping it would help you understand the process but I guess it's not valueble).

• I looked geomipmapping but as you said it can still be used but a little outdated.
• And as far as I know chunked lod allows you to create bigger terrains than geomipmapping
• What I don't understand about his error metric is he says every successive lod level has half of its parent error. Meaning Error(L+1) = Error(L)/2. How does he ensure that or does he just assume that it is like that for simplicity?
• And I really appreciate if you have any suggestions about other modern approaches.

• No. I said it is old. Not outdated. No discrete LOD system producing static geometry is truly outdated. By contrast, most continuous LOD schemes are outdated in my opinion. Let me be clear: Geomipmapping is NOT better, it's just easier to deal with IMHO.
• This is a common misconception. Again, most people will never have to deal with the paging problem. Nothing prevents geomipmapping from being paged to disk. Terrain clipmaps suffers from a common misconception: the algorithm itself is based on "fitting a grid on the terrain signal", while the paging is a basically orthogonal problem but if you ask around everyone will say terrain clipmaps are natively paged. They are not completely wrong either as this is what the term "clipmap" is typically used for.
• (I assume you're talking about Geomipmapping) It's a direct consequence of doubling the sampling frequency. Draw it on paper on 1D.
• I already listed three methods in my 1st message. But I'd add one. The possibility of traversing the heightmap with raycasting.

Thanks for the reply. And for 3th question I was talking about chunked lod. Anyways I gave up chunked lot and started cdlod, what do you think about cdlod? You said most continuous LODs are outdated but this seemed good after running the code and seeing the results. And here is the paper about it if you have never seen it before.

[Krohm]

My experience with CDLOD was terrible. The algorithm takes more preprocessing time than anything else I know about as well as more runtime resources. At that cost, the benefit over well-estabilished algorithms is not clear to me. The paper is written in such a way one wonders how much of it is true, how much is snake oil, how much I couldn't understand and how much is written with no clear understanding of the notions involved. Last time I moved those objections I experienced consistent fanboyism (mainly by a single user, who clearly didn't read my messages, let alone explain anything). In my opinion, its usefulness is unproven. You can use the search functionality to find what I have written (keyword VTF) I must admit however that it had quite some sarcasm in it, in retrospect, that was an error by my side.

Edited by Krohm, 24 July 2012 - 01:00 AM.

[ekba89]

As I said I am very new to terrain rendering stuff so it is hard for me to compare a lot of techniques because I don't know most of them yet but I think the best advantage of this over chunked lod is you don't have to worry about cracks. Also it seems fast, I tried the demo terrain that is included with 1920*1280 resolution, near 180k triangles and I got ~550fps and I tried chunked lod it was nearly the same. I've added screenshots. First one is from cdlod and the other two are from chunked lod.

Attached Thumbnails

• 

[Krohm]

I think the best advantage of this over chunked lod is you don't have to worry about cracks.

That is an over-approximation. Crack fixing is implemented in the algorithm via morphing. Again, this is a rather orthogonal problem. No terrain algorithm in wide use has demostrated to be incompatible with crack-fixing so far. Therefore, take any possible algorithm and put in crack-fixing: no cracks will occur as well!
The statistics you got mean nothing: I know nothing about your hardware, but it's worth noticing you have said performance is similar. Perhaps it's just me but I think there are some similarities between your original chunked LOD paper and CDLOD.

Additional considerations:

Page 14.
In the case of older graphics cards (Shader Model 2 or lower), the heightmap sampling in the vertex shader can be too costly or even impossible due to the lack of hardware capabilities.

It should read: In the case of older graphics cards (Shader Model 2 or lower), texture sampling functionality in the vertex shader is not supported. Therefore the algorithm cannot run.

But of course I am still open to check it again. Did you use the default settings or did you made your own configs? In the latter case, could you please send them to me for testing?
By the way, I still don't understand from where the "Continuous" in "CDLOD" comes from. Interpolating discretized signals don't make them continuous, although it might appear so.

I want to make clear. I am open on that. If I'm wrong, I will have no problem in admitting it. One of the reasons I write there is to check what I know. If somebody helps me understand and considers my points good. Until that happens, I'm sorry but I'll remain on my position. This algorithm usefulness is unproven for me. What does it buys over other methods? I don't know in theory and I cannot observe consistent advantages in practice. So I have no real reason to support this.

[ekba89]

That is an over-approximation. Crack fixing is implemented in the algorithm via morphing. Again, this is a rather orthogonal problem. No terrain algorithm in wide use has demostrated to be incompatible with crack-fixing so far. Therefore, take any possible algorithm and put in crack-fixing: no cracks will occur as well!

Chunked lod uses morphing too and it uses skirts to fix cracks. But with cdlod you don't need to create skirts.

I know nothing about your hardware

My specs are: geforce gtx 580, i7-2600k and 8gb ram

Did you use the default settings or did you made your own configs?

Yes I used codes that are provided by the owner of papers and used the default settings on both(With one difference that I mention below). And I should mention this too. There are two cdlod projects one is using paging and one is not(which are both belong to Filip Strugar). I am using the one without paging and his tests in the paper are from the one that uses paging. He mentions that he is using more compressed node structure for paging one so its performance might be different.

And one last thing to add. I used binaries for chunked lod but I used debug build from the visual studio for cdlod so before posting this I compiled a release build for cdlod and its performance was a lot better. I got 630fps for the same scene.

Again, I am not an expert so I am not defending either one. I started implementing cdlod just because I had problems implementing chunked lod and I just want to know if I am making a mistake .

[Krohm]

Chunked lod uses morphing too and it uses skirts to fix cracks. But with cdlod you don't need to create skirts.

I don't care about how the cracks are fixed. Use a morphing scheme, use skirts, it's no problem for me and saving a batch does not save much until profiling proves so. I don't see any added in not using skirts. And again, who says you have to use the original morphing scheme for chunked?

As a side note, the chunk LOD paper you originally noted uses morphing as a way to reduce popping from a node changing into its children, not to deal with adjacent chunks. It's called the same but it involves fairly different concepts. CDLOD many years later can afford to do per-vertex operations and uses them to deal with adjacent chunks. It then basically designates a set of vertices (odd) to be "movable" and uses a vertex attribute to move those vertices{1}, relying on texture fetch to perform the interpolation halving sampling frequency at bounduary{2}. I had some quite bad experience with this method in the past (way before CDLOD surfaced) due to variable-frequency sampling issues. I am thus reluctant to recommend this algorithm and again, I have some yellow lights about possible overhype.

My specs are: geforce gtx 580, i7-2600k and 8gb ram ... its performance was a lot better. I got 630fps for the same scene.

Awesome. We can now safely assert CDLOD reaches high performance on high-end hardware.
630 fps --> 1.58ms (87.2%)
550 fps --> 1.81ms
I don't see anything being "much higher" (the algorithm is GPU-driven). Any measurements above 200fps is to be taken with extra care. As a side note, on your hardware simple bruteforce will likely exceed 400fps as well (my geforce4 on an Athlon 1800+ used to churn along 64*1024 unique vertices at over 80 fps even in debug mode).

I'm afraid you might be focusing too much on those. I want to warn you because I spent close to a year on this, and it has been wasted effort for me.

John Carmack on Quake Wars
John Carmack: Level of detail wise, the terrain does not render with any sophisticated geometry morphing situation. That's one of those things that for years I think most of the research that's gone into has been wasted. Geometry level of detail on terrain.. there have been thousands of papers written about it, and I honestly don't think it's all that important. The way the hardware works, you're so much better off setting down a static mesh that's all in vertex and index buffers, and just letting the hardware plow through it, rather than going through and having the CPU attempt to do some really clever cross blended interpolation of vertices.

So don't spend too much effort on it. Optimize your life. For another metric of how interesting terrain algorithms are, see the number of third-party opinions we collected. To say it again: I am willing to (re)consider any algorithm as long as I can have an articulated discussion of the pros and cons.
As a side note, the only project in which I have been requested terrain has been shut down prematurely. As it stands now, my current system still has no integrated terrain system, so my effort has been completely wasted.

{1} to be completely honest, I think having the morph function work in world space is not the best option. But I guess that's personal preference.
{2} sounds like interpolated geomipmapping? so much for your previous doubt about sampling frequency!

Edited by Krohm, 25 July 2012 - 01:04 PM.

[ekba89]

When I mentioned skirts I meant it is good for me that cdlod is not using skirts so I don't need to work on another thing . Also from now on it is too late for me back down, today I worked on it all day so hopefully it will be good when it is finished. But what I understand from my little performance experiment is that cdlod is faster than chunked lod as long as you have good gpu to support it. Also cdlod example is in DirectX 9 and I am implementing it in DirectX 11 so I expect a little bit more performance if I manage to implement it well. I'll share my results as soon as I finish implementation if I manage to finish it of course .

[Krohm]

Ok, thank you very much.