Oh no, another terrain rendering paper!
My paper, Continuous Distance-Dependent Level of Detail for Rendering Heightmaps, was recently published in the journal of graphics, gpu and game tools - it took a while but it's finally done.
Slightly updated version can be downloaded from here - demo, code and data download links are in the paper.
Abstract:
This paper presents a technique for GPU-based rendering of heightmap terrains, which is a refinement of several existing methods with some new ideas. It is similar to the terrain clipmap approaches [Tanner et al. 98, Losasso 04], as it draws the terrain directly from the source heightmap data. However, instead of using a set of regular nested grids, it is structured around a quadtree of regular grids, more similar to [Ulrich 02], which provides it with better level-of-detail distribution. The algorithm's main improvement over previous techniques is that the LOD function is the same across the whole rendered mesh and is based on the precise three-dimensional distance between the observer and the terrain. To accomplish this, a novel technique for handling transition between LOD levels is used, which gives smooth and accurate results. For these reasons the system is more predictable and reliable, with better screen-triangle distribution, cleaner transitions between levels, and no need for stitching meshes. This also simplifies integration with other LOD systems that are common in games and simulation applications. With regard to the performance, it remains favourable compared to similar GPU-based approaches and works on all graphics hardware supporting Shader Model 3.0 and above. Demo and complete source code is available online under a free software license.
I'm currently working on a DirectX11 CDLOD demo, and when that's done I'll try out what I wanted to play with for a while now - the hardware tessellation. We'll see how it goes; I'll post the results here.
Let me know if you find this paper (and code) useful and if you have any questions or suggestions!
[edit] Adding the download links here... [\edit]
Binaries and a small example dataset
http://www.vertexasylum.com/downloads/cdlod/binaries_tools_testdata.exe
Complete source code
http://www.vertexasylum.com/downloads/cdlod/source.zip
Example datasets
http://www.vertexasylum.com/downloads/cdlod/dataset_califmtns.exe,
http://www.vertexasylum.com/downloads/cdlod/dataset_hawaii.exe,
http://www.vertexasylum.com/downloads/cdlod/dataset_puget.exe
Example animations
http://www.vertexasylum.com/downloads/cdlod/cdlod_calif.wmv,
http://www.vertexasylum.com/downloads/cdlod/cdlod_hawaii.wmv,
http://www.vertexasylum.com/downloads/cdlod/cdlod_params.wmv
July 15th, 2010 - 15:34
Hi, Filip. You’ve done the great job. I’m enjoying your paper and results. Thanks for nice things.
July 15th, 2010 - 16:03
Thanks! If you create something interesting using it please let me know (post some screenshots, etc)!
July 28th, 2010 - 16:13
Two weeks later and I finally get to check this out. It looks great and I’m really getting a lot out of this paper.
August 15th, 2011 - 04:51
Couldn’t you partially solve the granularity issue by using a restricted quad tree, where neighbors are restricted to a single level difference?
August 15th, 2011 - 09:53
Hi George, thanks for the comment!
The quadtree selection _is_ restricted so that each node can only have neighbours of a single level difference (+1 or -1) – that’s what is causing granularity issues! Because of this there is a minimum valid difference ratio between LOD distances, and minimum valid starting LOD distance, below which more than 2 LOD level transitions can occur over the are of one quadtree node, which isn’t supported and would result in morphing artifacts!
August 23rd, 2011 - 13:20
Hello, I saw your library and it was awesome!
But I have a question. you presented California map as splatting example, but the demo already has splatting map as tbmp file. I want to know how the splatting image built, but your tbmpconv utility only support one-way conversion. I cannot see the structure of splatting map!
Can you upload source splatting map?
August 23rd, 2011 - 14:28
Heightmap can be converted back to tiff, but splatting image cannot! Saying
[Error: TIFF image pixel format is not supported].
August 23rd, 2011 - 15:59
Hi homelander,
I used a custom quickly-assembled tool to generate the splatmap based on terrain elevation / slope / roughness / etc; nothing fancy, used heightmap and normalmap as inputs. I don’t have the code with me at the moment unfortunately and will be away from my PC for a while
tbmpconv probably doesn’t work for A4R4G4B4 (the format of the splatmap) tbmp, but you should be able to load it in code and do the conversion yourself – the source code for tbmp loader is included in the demo!
September 7th, 2011 - 15:55
Hi,
I am currently implementing this paper.
I am trying to get rid of the “m_visDistTooSmall” case, were the morphing doesn’t work correctly.
From what I understand, there is a relation between a terrain cell size (let’s say the size of one cell at LOD0), the m_morphStartRatio value, and the visibility distance used for nodes selections (LODSelection::m_visibilityDistance).
Actually, if “m_visibilityDistance” is big enough, no morphing issue will happen.
I am trying to compute the minimal value for “m_visibilityDistance” which would get rid of this morphing issue, according to the given LOD0 cell size and “m_morphStartRatio”.
I am sure there is a way to compute this, however, I haven’t found it
Any idea how I could do that ?
September 7th, 2011 - 16:39
Hi Greg,
That’s a good question! I actually gave up trying to calculate it because it also depends on the heightmap itself. It should be possible (easy?) to come up with the visibility distance formula based on the LOD0 cell size and ratio as you say, but only for flat terrain. Hilliness will increase the minimum visibility distance in a less predictable way, so, so far, I’ve simply relied on ‘increase the distance until there’s no morphing errors anywhere, and then add 20% for good measure’. Might not be the cleanest approach, but it’s good enough for games
September 8th, 2011 - 06:48
Hi Filip,
thanks for your answer!
So, do you mean you do that manually (trial and error) ?
I think I will consider the case of a flat terrain (I compute the camera-vertex distance required for morphing using null-heights anyway).
I am pretty sure there is a way to compute it mathematically, independently of the data…
September 8th, 2011 - 07:09
by “independently of the data”, I mean, considering a flat terrain (height=0)
September 8th, 2011 - 14:15
“I am pretty sure there is a way to compute it mathematically, independently of the data…”
definitely, as long as the data is 0
if not, you’ll have to analyse data as well or assume that it’s always under some height range; that’s because the morphing happens in 3D (takes the height difference into account) which depends on data.
September 8th, 2011 - 09:24
I found out how the avoid any potential morphing problems
I proceed as follow:
- compute the minimal max distance (LODFar) which won’t cause any issue
- this is the minimal LODFar value, if used as it is the morphing length is null, so multiply by a new “morph factor” > 1.0
- compute each LOD visiblity distances according to this new LODFar
- compute each LOD morph start & end according to the visibility limites computed during previous step
Below the math :
// this is the length (side) of a terrain node at LOD 0 / TODO: get from data
float fLOD0CellWidth = 1024.0f;
// compute the theorical minimal value of the global visibility range that can be used without having any potential morph issue
// that is been computed as follow:
//
// MorphStart(n+1) = VisLimit(n) + sqrt(2) * CellWidth(n)
// MorphEnd(n+1) = VisLimit(n+1)
//
// MorphEnd(n+1) > MorphStart(n+1)
// MorphEnd(n+1) – MorphStart(n+1) > 0
// VisLimit(n+1) – (VisLimit(n) + sqrt(2) * CellWidth(n)) > 0
// VisLimit(n+1) – VisLimit(n) > sqrt(2) * CellWidth(n)
//
// LODLevelDistanceRatio * VisLimit(n) – VisLimit(n) > sqrt(2) * CellWidth(n)
// VisLimit(n) * (LODLevelDistanceRatio – 1.0) > sqrt(2) * CellWidth(n)
// GlobalVisibility * (2^n / (2^(LODCount-1))) * (LODLevelDistanceRatio – 1.0) > sqrt(2) * CellWidth(n)
// GlobalVisibility * (2^n / (2^(LODCount-1))) * (LODLevelDistanceRatio – 1.0) > sqrt(2) * (LOD0CellWidth * 2^n)
// GlobalVisibility * (LODLevelDistanceRatio – 1.0) > (sqrt(2) * LOD0CellWidth * 2^n) / (2^n / (2^(LODCount-1)))
// GlobalVisibility * (LODLevelDistanceRatio – 1.0)> (sqrt(2) * LOD0CellWidth * 2^n) * (2^(LODCount-1)) / (2^n)
// GlobalVisibility > ((sqrt(2) * LOD0CellWidth) * (2^(LODCount-1))) / (LODLevelDistanceRatio – 1.0)
float fGlobalVisibility = (sqrt(2.0f) * fLOD0CellWidth * (float)(1 <m_fLODLevelDistanceRatio – 1.0f);
// now multiply this value by a factor > 1.0. Using 1.0 means no morphing. The higher the value is, the bigger the morphing transition will be.
// this ratio also have an impact on how detailled the terrain will be (higher value => further LOD transition)
// we use 2x here:
fGlobalVisibility *= 2.0f;
// compute the new visibility ranges for each LOD
for( int i = 0; i m_fVisibilityRanges[i] = m_fLODVisRangeDistRatios[i] * fGlobalVisibility;
// compute the morphing start/end distances
for (int i = 0; i m_fMorphStart[i] = (i == 0) ? 0.0f : _pSelectionObj->m_fVisibilityRanges[i-1] + sqrt(2.0f) * fLOD0CellWidth * (float)(1<m_fMorphEnd[i] = _pSelectionObj->m_fVisibilityRanges[i];
}
I have tested the code above, and no morph problem are triggered.
Time for a brain break
September 8th, 2011 - 14:18
I’ll have to trust you on this for now, my brain hurts even trying to understand it now – haven’t touched CDLOD code for a while
November 10th, 2011 - 11:43
What’s the MorphStart(n+1)
Equal:
MorphEnd(n+1) = MorphStart(n+1) > 1 ? 1 : 0;
?
November 11th, 2011 - 11:42
Well the encoding got that all messed up. I mean the creative use of greater than/smaller than symbols. Coming from a C# background I can’t see how they work without a ternary operator somewhere.
September 9th, 2011 - 06:57
Basically, I tried to find out what is the potentially furthest “morph start” and the closest “morph end” for a specific level.
Then resolve the equation so that “morph start” > “morph end”.
This lets you find the minimal LODFar value that works.
But I agree, even I don’t understand this anymore this morning
September 14th, 2011 - 15:07
Hi Filip,
I stumbled upon your paper when I was looking for a state of the art terrain rendering algorithm that is heightmap based and could do the LOD morphing on the GPU. Your idea looked brilliant and I decided to reimplement it in C in my own OpenGL/GLSL based 3D framework without just copying your code. Although this turned out to be a lot more work than I initially expected, I managed to get it working over the last few months. Even though there is still a lot to be done, the whole thing is functional and I can confirm that you claim in the paper is correct and that results in it can be reproduced.
As Gregory Jaegy, I ran into the same morphing problems as him and analyzed it formally. I found that if you adjust the forumlae for the start and end points of a morph region just slightly from what can be found in your code, there is actually a very simple inequality that must hold for these problems to disappear. As this so far is just scribbled onto a piece of paper on my desk and as I am using different variable names than you are, I won’t go into more detail until I’ve written it down in a clean manner, which I’m planning to do soon.
If you’re interested in my results and/or my code (available under an open source license), check out the following links:
http://kalisko.org/browser/kalisko/src/modules/lodmap/ (code)
http://www.youtube.com/watch?v=JLnkRdiB-9w (proof of concept video)
http://www.youtube.com/watch?v=3Ey9Ga589pk (video with lighting)
http://www.youtube.com/watch?v=TwCzb69lfS0 (video with texturing)
Thanks a lot for this great paper and I’m looking forward to seeing more of your projects.
– Fabian
September 15th, 2011 - 19:42
Hi Fabian,
Amazing work, thanks for letting me know! I can’t try anything out at the moment (my main PC died) but I will definitely go through it at some point. I’ll also be glad to see the math for determining the minimum safe view distance when you get it cleaned up.
All the best!
Filip
November 9th, 2011 - 09:19
I would be interested in the math as well
I am about to work on this again, as I am not satisfied with the way the LODs are selected.
With current LOD scheme, I either get to coarse details at distance, or too many tiles if I decrease LODLevelDistanceRatio (to 1.8 for instance)…
January 5th, 2012 - 05:20
I am interested in reading your code but the source code link provided by you is dead.
January 5th, 2012 - 10:03
Hi Jaytirth,
The links seem to work fine now (for example, http://www.vertexasylum.com/downloads/cdlod/source.zip ) – maybe it was a temporary problem with the web server?
January 9th, 2012 - 05:06
Actually, I meant Fabian Hahn’s link of C code. It is not working.
December 19th, 2011 - 11:55
Hi,
After reading streaming LOD code, the first impression i got is, LODs are generated for overlay maps in addition to heightmaps. Are we using morphing technique for overlay maps in pixel shader? (refering to albedoColor = lerp( albedoColor, parentAlbedoColor, LODMorphValue ) )
January 5th, 2012 - 10:05
Hi Mihir,
Yes, a same/similar morphing technique is used to blend overlay maps in the pixel shader!
January 9th, 2012 - 06:04
Normal Map Texture is computed in basiccdlod approach before the vertices are morphed. Hence normal fecthed during rendering will be based on unmorphed terrain vertices. Hence normals fetched in the morphed region will not be accurate. Is it correct? If yes, any remedy for the same?
February 2nd, 2012 - 11:58
I’d be interested in that too. Mihir did you look into this? Any findings?
January 9th, 2012 - 09:45
The paper says ‘While a detailed discussion of the topic of streaming is outside the scope of this article, some basics will be covered.’
Since I am a novice I wish to understand the details about streaming. Can you suggest any resources for it? I will be grateful.
January 18th, 2012 - 03:38
http://silverspaceship.com/src/svt/
January 18th, 2012 - 03:36
Hi, thanks for an interesting new take on terrain/LOD.
Perhaps a minor point: in your pseudo code for LODSelect(), isn’t it worth performing the FrustumIntersect() first?
That is, once a cell is out of view, is there any reason to consider it for LOD selection at all? In trying to implement the pseudo-code, it appeared as if some out-of-frustum cells were being added to the selection list, and performing the frustum test first seemed to fix this.