## 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

starlikeJuly 15th, 2010 - 15:34

Hi, Filip. You’ve done the great job. I’m enjoying your paper and results. Thanks for nice things.

Filip StrugarJuly 15th, 2010 - 16:03

Thanks! If you create something interesting using it please let me know (post some screenshots, etc)!

MikeJuly 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.

GeorgeRAugust 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?

Filip StrugarAugust 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!

homelanderAugust 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?

homelanderAugust 23rd, 2011 - 14:28

Heightmap can be converted back to tiff, but splatting image cannot! Saying

[Error: TIFF image pixel format is not supported].

Filip StrugarAugust 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!

GregSeptember 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 ?

Filip StrugarSeptember 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 π

GregSeptember 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…

GregSeptember 8th, 2011 - 07:09

by “independently of the data”, I mean, considering a flat terrain (height=0)

Filip StrugarSeptember 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.

Gregory JaegySeptember 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 π

Filip StrugarSeptember 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 π

George RNovember 10th, 2011 - 11:43

What’s the MorphStart(n+1)

Equal:

MorphEnd(n+1) = MorphStart(n+1) > 1 ? 1 : 0;

?

George RNovember 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.

Gregory JaegySeptember 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 π

Fabian HahnSeptember 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

Filip StrugarSeptember 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

Gregory JaegyNovember 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)…

JaytirthJanuary 5th, 2012 - 05:20

I am interested in reading your code but the source code link provided by you is dead.

Filip StrugarJanuary 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?

JaytirthJanuary 9th, 2012 - 05:06

Actually, I meant Fabian Hahn’s link of C code. It is not working.

MihirDecember 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 ) )

Filip StrugarJanuary 5th, 2012 - 10:05

Hi Mihir,

Yes, a same/similar morphing technique is used to blend overlay maps in the pixel shader!

MihirJanuary 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?

PhilFebruary 2nd, 2012 - 11:58

I’d be interested in that too. Mihir did you look into this? Any findings?

JaytirthJanuary 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.

kenbotJanuary 18th, 2012 - 03:38

http://silverspaceship.com/src/svt/

kenbotJanuary 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.

PGTFebruary 7th, 2012 - 14:11

Hi,

The CDLOD algorithm first selects the height nodes and then renders the overlay textures associated with the node. Hence it cannot render the portion of the overaly (raster/ vector layers) map where there is no height data. Any remdey for this problem?

PGTFebruary 7th, 2012 - 14:24

Hi,

The CDLOD algorithm first selects the height nodes and then renders the overlay textures associated with the node. Hence it cannot render the portion of the overaly (raster/ vector layers) map where there is no height data.

Even if we have a top view where we should see only 2D view rendered for overaly maps, still this is not possible for areas where no elevation data is provided. Any remedy for this problem ?

Filip StrugarFebruary 7th, 2012 - 18:28

Hi,

You simply need to calculate your other data layers min/max heights and merge it with the existing quadtree min/max heights that are generated from the heightmap!

PGTFebruary 8th, 2012 - 05:03

Hi,

Thanks for the suggestion. However what if we don’t have min/max heights data for other data layers?

e.g. say we have overlay data for entire Europe, but we have height data only for UK. How do we render overlay data of portion other than UK as there will be no height nodes for the portion?

Filip StrugarFebruary 8th, 2012 - 19:19

I’m not sure I understand correctly, but if your vector/other data layers lay outside of the area covered by the heightmap but you want to use CDLOD’s QuadTree then you have to expand the area it covers to outside of the original heightmap in one way or the other. Otherwise, you can create your own QuadTree or a similar culling system.

JaytirthFebruary 13th, 2012 - 11:20

Hello,

There are some questions raised about CDLOD in the forum

http://www.gamedev.net/topic/620084-a-good-heightmap-lod-technique-no-vtf-please/page__view__findpost__p__4911965

I would like to know the author’s views on it.

JazzFebruary 26th, 2012 - 00:53

Hey Filip,

I’ve been trying to implement CDLOD, but I’ve been having popping with partial nodes morphing to next lod levels. I’ve gone through your source to see if anything thing special was done for morphing partial node and couldn’t find anything. It seems view position comes in a partial node’s lower lod viewing distance before the morphing completes. I know this seems like a more implementation specific problem, but am I missing something? Are partial node morphing handled exactly the same as regular nodes?

JaytirthMarch 7th, 2012 - 05:50

What if I create child nodes dynamically, only those child nodes whose parent node are in range of a more detailed LOD level? Will it affect the performance? What can be the other problems in this approach? I would be grateful for the help.

RobertMarch 21st, 2012 - 22:15

A morph vertex is defined as a grid vertex

having one or both of its grid indices (i, j) as an odd number, and its corresponding no-morph

neighbour is the one with coordinates (i β i/2, j β j/2).

But how do you find which vertex has to be morphed, i don’t see code in vertex shader for that ?

JKApril 24th, 2012 - 03:23

What are the issues that I may have to tackle if I decide not to give the user the option of choosing LODCount?

DennisMay 5th, 2012 - 13:22

Hey,

I was just wandering what this “normalmap” is I mean I get that you need the heightmap for the extrusion and the overlaymap as an optional overlay BUT what is the “normalmap”? how do you create it? Is it a normal “vector” map but still how did you create it?

chrisAugust 24th, 2012 - 09:03

Hi, Filip

Youβve done the great and a hard Project really…

Filip i found a things like a bug and i don’t understand how to solve it

when my

heightmap.tif resolution is 527 X 484 (10m resolution)

and

overlaymap.jpg resolution is 4028 X 3864 (about 26cm resolution)

hetch.scdlod make by StreamingCDLOD.exe good and no error receive

but when i try to open my created hetch.scdlod i recive errror messeage and application will crach…

it seams overlaymap buffer size is not enough or ratio of heightmap by overlaymap is not true or any things like this..

can you please try it:) make heightmap and overlaymap by that resulotion and you’v see crash.

can you please guide me to fix it π

waiting for replay.. :p

thank’s