Mad Vertex's hideout

11Jul/1043

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

Comments (43) Trackbacks (1)
  1. Hi, Filip. You’ve done the great job. I’m enjoying your paper and results. Thanks for nice things.

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

  3. Couldn’t you partially solve the granularity issue by using a restricted quad tree, where neighbors are restricted to a single level difference?

  4. 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!

  5. 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?

  6. Heightmap can be converted back to tiff, but splatting image cannot! Saying
    [Error: TIFF image pixel format is not supported].

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

  8. 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 ?

    • 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 πŸ˜€

  9. 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…

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

      • “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.

  10. 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 πŸ˜‰

    • 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 πŸ™‚

      • What’s the MorphStart(n+1)

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

        ?

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

  11. 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 πŸ™‚

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

  13. 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 ) )

  14. 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?

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

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

  17. 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?

  18. 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 ?

    • 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!

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

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

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

  20. 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?

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

  22. 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 ?

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

  24. 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?

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


Leave a comment