7 ms·

Rendering large terrains

175 points by pheelicks 13y ago

eliah-lakhin 13y ago
Thank you for such detailed and well written material, pheelicks! I had been looking it for a long time. Bookmarked.
- pheelicks 13y ago
  Glad you like it! I'm planning on doing a follow-up, where I look at doing more detailed things with the fragment shader, to give the terrain a different look. E.g. using some textures for the ground, like grass, rock, snow etc
platinum1 13y ago
This reminds me of: http://www.zephyrosanemos.com/ http://www.zephyrosanemos.com/ - another very impressive webGL terrain demo. One thing I particularly like about the zephyrosanemos is the realtime rendering of the procedural terrain generation. I'd love to hear a comparison of the two by someone knowledgeable about the subject.
deletes 13y ago
If you look carefully you will see the very tops of the mountains "grow and sharpen" or "shrink and smoothen" when they pass a certain distance. I saw that same behavior in an old game Starsiege Tribes( from 1998 ). Now I know why it happens.
- zamalek 13y ago
  This could be caused by two issues: Popping: it "naturally" happens with all dynamic LOD systems (back in '98 it would have been Real-time Adaptive Optimized Meshes). It happens when something changes from one detail level to another (and hence more details "pops" into view). If you spend more time on your renderer you will generally morph those vertices between the lower detail position and the higher over a very small amount of time. This means that the pop happens over a longer duration and humans are bad at noticing stuff like that. Incorrect Heuristics: a heuristic is used to determine how far away from the camera you need to be in order to not see the difference between four triangles and two (this has a lot to do with Nyquist-associated theorems) because "the difference is less than a pixel." If you get it wrong you could present too little detail for a pixel and change the apparent shape of the terrain (obviously intentionally presenting too little detail increases framerate).
soup10 13y ago
Cool demo and writeup. Why's is it so sparkly though?
- ginko 13y ago
  Probably aliasing due to undersampling. Terrain rendering is probably one of the things where GPU-based raymarching really is an option nowadays. http://iquilezles.org/www/articles/terrainmarching/terrainmarching.htm http://iquilezles.org/www/articles/terrainmarching/terrainma...
  - ttctciyf 13y ago
    Probably is - I was astonished when I first saw this raymarched procedural terrain at shadertoy: https://www.shadertoy.com/view/4slGD4 https://www.shadertoy.com/view/4slGD4
    - deletes 13y ago
      ::rant:: Crashed firefox( latest version ); tried chrome, loads forever and then doesn't work. For whom is this made, if it doesn't work on my i5 with a decent gpu?
      - ttctciyf 13y ago
        Mac users? :) Sorry! Runs ok (well, 12fps!) here on firefox on an iMac. Just black on my centOS laptop with intel graphics, I admit, but loads of gl things don't run on that.
- pheelicks 13y ago
  There's a specular light positioned above the terrain, which adds the sparkle (light3 in https://github.com/felixpalmer/lod-terrain/blob/master/js/shaders/terrain.frag https://github.com/felixpalmer/lod-terrain/blob/master/js/sh...). If you want to play around with changing the light etc, you can use Mozilla's awesome in-browser GLSL editor (currently in FF beta): https://hacks.mozilla.org/2013/11/live-editing-webgl-shaders-with-firefox-developer-tools/ https://hacks.mozilla.org/2013/11/live-editing-webgl-shaders...
blackdivine 13y ago
Ah game programming and terrains, the nostalgia :)
zurn 13y ago
Looks superficially similar to the WebGL terrain 3-parter at http://www.gamasutra.com/blogs/JasmineKent/20130904/199521/ http://www.gamasutra.com/blogs/JasmineKent/20130904/199521/ - are there differences?
- exDM69 13y ago
  This is a common technique so no surprise they are similar. However, there seem to be slight differences in the way the chunk edges are made seamless. In Trigger Rally, there are additional vertices being added to the lower LOD chunk side of the seam to avoid T-junctions in the mesh topology. In the OP demo, the vertices on the higher LOD side of the seam are morphed so that they will be flat with the lower LOD side of the seam. This should also help reduce "snapping" when moving to higher LOD levels.
bitL 13y ago
Very nice! An interesting approach! Did you also consider using some more advanced geometry representation of terrain other than heightfields, such as triangulated irregular networks? That would allow you to choose an error threshold for each LOD and seamlessly join neighboring patches together without the need to use vertex shaders for it. I did my own "Google Earth"-alike using a modified BDAM algorithm a couple of years ago. It required Hadoop preprocessing of detailed input data (resolution in meters), parallel terrain simplification using quadric error metrics and edge collapses and produced a set of layers at different LODs. The cool thing about it was that you could have chosen the desired screen-space error and fetch only those LODs that were fitting - usually these had far smaller size than regular heightfields of the same resoultion/error. You could have also incorporated roads, rivers, buildings, bridges, tunnels straight into your terrain geometry, as well as different textures for each sub-part of it. The tessellation was a bit funky (BDAM uses triangular patches instead of tiles) however there are also variants that utilize rectangular tiles. Vertex shader was then used to simulate 64-bit precision, giving uniform rendering detail in centimeters for the whole Solar system. Geometry shader could add more detail into it and overall it was very snappy online as the size of downloaded data was smaller than with regular meshes.
- pheelicks 13y ago
  I was keen on keeping as much of the complexity on the GPU, so I wanted to avoid having to update the geometry. Not to say I'm against exploring different approaches. Did your "Google Earth"-alike, ever see the light of day?
  - bitL 13y ago
    Completely understood, it's better to focus on interesting 3D stuff and easier to do it this way in JavaScript than to handle tile caching using WebWorkers/WebSockets and local storage in a language that doesn't support proper multithreading. Yes, the project was completed and working fine though it ended up buried deep within my former employer's R&D lab and I have no update if they are using parts of it anywhere. They got acquired and another office was aggressively taking over, getting rid of internal competing technologies. I also had a prior experience in adding dynamic 3D cities and vector maps into NASA's World Wind, and therefore writing a completely own globe from the scratch was a joy ;-) I am thinking about doing similar apps in WebGL and Qt and writing some tutorials on how to do it as I progress, so perhaps we can inspire each other then. First I need to finish some tutorials for advanced 2D geometry and Bezier curves though (Illustrator-class algorithms with JavaScript + HTML5 live examples). Thanks for writing this inspiring piece! :)
zamalek 13y ago
CLOD is the underlying mesh/LOD technology used in Frostbite (BF3/4). There is a formal paper for it [1]. My coworker is currently making a toy CLOD renderer in C++ and the technology speaks for itself - he's rendering 8K x 8K worth of height-map data at some 200 FPS on some laptop NVidia chip (he will be open-sourcing it in a few months time, so watch this space). Frostbite goes a bit further (they stream in the height-map etc.) but the bare method used is this. His reaction to me sharing this was quite funny: > Cool! But… Javascript??! It’s like writing the bible (or your religious equivalent) in glitter and kids crayons… Loses something. You just can't get oldschool developers away from their beloved languages :). [1]: http://dice.se/wp-content/uploads/GDC12_Terrain_in_Battlefield3.pdf http://dice.se/wp-content/uploads/GDC12_Terrain_in_Battlefie...
- theandrewbailey 13y ago
  It's 2014 and Javascript is awesome. If I ever do anything 3D, it will probably be WebGL. Some industry veterans have reservations against it, but so long as it doesn't look like poop smeared origami, it's OK.
  - valarauca1 13y ago
    >2014 and javascript is awesome sort(1,10,5,3) 1, 10, 3, 5 Then there is this. null == false //false !null //true
    - Cthulhu_ 13y ago
      https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe... > The default sort order is lexicographic (not numeric). Works as documented.
      - CmonDev 13y ago
        Ok, pick any other embarrassing design flaw: http://wtfjs.com/ http://wtfjs.com/
elktea 13y ago
Fantastic, I have been looking for good example in modern opengl for a while. Thank you!
xedarius 13y ago
The main reason for LODing is to increase the draw distance. The demo seems to have implementing a LODing system, and then fogged the draw distance anyhow ... which is odd.
- dualogy 13y ago
  No matter how far your draw-distance is, you totally DO want to "fog anyhow" in any event: you want distant scenery to smoothly fade-out rather than abruptly pop-out (regardless of your actual far-plane distance), plus fogging is a primary spatial-distance cue to the viewer in 3D, and is cheap/free nowadays. Even the real-world does "fogging-out" over distance depending on atmospheric scattering, haze, rain/storm or actual fog conditions. So fogging-out-smoothly, while beneficial as per above, also looks beautifully "realistic" as an added benefit, at least provides a great realism/cost ratio
  - lutorm 13y ago
    This has always impacted the realism of flight simulators, in my mind - due to performance reasons, you're always flying around in some pea-soup like fog. At altitude, you can easily see hundreds of miles in clear weather, but I haven't seen any flight simulator that comes even near to being able to render out to those distances.
    - bitL 13y ago
      I believe there are two problems in flight simulators: - insufficient precision of OpenGL 32-bit floats in Earth-scale computations. If you want to render the whole Earth, you'll find that at the ground level your precision is only 16m resulting in jittering as you move. This was usually solved by "zoning" and local coordinate systems, hence it was easier to deal with a smaller set of ground "tiles" and haze out the distant ones. Having said all that, nowadays you can use vertex shaders to simulate 64-bit (or rather 56-bit) precision and get around 1cm resolution at any distance - the need to have various LODs that include curvature of the Earth with significantly increased error tolerances, which in turn increases memory consumption. Again, nowadays should be no longer an issue given entry-level GPUs having 1GB of RAM and geometry shaders
frik 13y ago
Three years ago, someone had the same idea: http://sea-of-memes.com/LetsCode28/LetsCode28.html http://sea-of-memes.com/LetsCode28/LetsCode28.html Edit: just for some additional information, the idea is of course a lot older
- shultays 13y ago
  This is far older that 3 years old, I don't think OP says he invented it
twp 13y ago
There are some great open source WebGL terrain renderers out there, on a planetary scale, for example: http://doarama.com/view/2171 http://doarama.com/view/2171 This is built on the Cesium open source virtual globe http://cesiumjs.org/ http://cesiumjs.org/
grimmdude 13y ago
This is amazing
merpnderp 13y ago
If the inner level is 1x1 and the other level is 5x5 and the inner level moves by 1 unit, then the outer level will have to move by 1/5 of its 5x5 units (1). Thus the outer level will not move by its proper grid snapping amount. Or am I missing something?
- pheelicks 13y ago
  The grid snap happens after the movement. You are correct that the higher level grid may not move. To fix this, the higher resolution tiles (1x1 in your example) are morphed near their edges so that gaps do not appear. I cover this in the blog post, see the 'Morphing between regions' section
  - merpnderp 13y ago
    I still don't think I understand. If the 1x1 level moves, and didn't overlap the 2x2 outer ring, and the 2x2 outer ring doesn't move (the camera hasn't triggered a 2x2 move yet, just the 1x1), then there is now a gap in the opposite direction of the 1x1 move. That's why trigger rally uses the overlapping geometries, so that a 1x1 level can move and in the direction of the move the overlapping geometries double up and in the opposite direction, they no longer overlap at all (it uses morphing also so that the overlapping geometries have vertices in the exact same spots).
    - pheelicks 13y ago
      Imagine instead that each ring is joined by a set of springs, which can be compressed down to zero and extended to the difference in the grid snapping between the 2 rings. As the rings snap to different grids the springs extend and contract to fill the gaps. Now place some vertices on these springs and you have a terrain mesh, where the majority of vertices are snapped to locations depending on the LOD, except those joining the rings, which such that the transitions between the layers are seamless
      - merpnderp 13y ago
        You are a genius :)
lootsauce 13y ago
This has been a transformational technique in graphics and mapping and I think its worthwhile to recognize where the technique came from. As far as I can tell the origin of the technique described here can be traced back to SGI prior to Keyhole as published in 2002. [1] This "Clip Map" technique is a key enabler of applications like Google Earth because of how efficiently it pages data. Recall that Google Earth was the product of an acquisition of a company called Keyhole. Named after the spy satellite, a reference to the recently declassified satellite imagery they were using. Its also interesting to note Al Gore played an important role in declassifying this data. [2] But to make use of all of this imagery a new efficient algorithm was needed for loading and rendering the data. This is what the Clip Map paper describes and enabled the iconic zoom from space to the surface of the earth with real time rendering of satellite imagery. According to Michael T. Jones. "Keyhole started by accident. The earliest possible origin of Keyhole actually lies with me. I worked with a company called Silicon Graphics (SGI). One of the companies I worked with had created a program to view satellite imagery where you could zoom in and see the imagery in great detail. It was used in the Bosnia peace talks to draw the border." [3] "Before its acquisition by Google, Michael was CTO of Keyhole Corporation, the company that developed the technology used today in Google Earth. He was also CEO of Intrinsic Graphics, and earlier, was Director of Advanced Graphics at Silicon Graphics." [4] It is interesting to note that a German company is now suing Google over Google earth and possibly this very technique. [5] Are ART+COM and Terravison the company and software Michael Jones was speaking of? The real power of this technique is that it allows you to pre-page the data in tiles that can be easily loaded over the web and are sized specifically to live graphics memory. It optimizes both the IO this way and off-loads the mesh creation process from CPU to the GPU. In 2004 Microsoft research published an expansion of the of the Clip Map technique that does just that. [6] A basic demo and source in C++ available [7] and I have also found SpiderGL uses this technique [8] One thing I have not found yet is a good discussion of implementing collision detection in conjunction with this technique if anyone has found any resources on this I would be grateful. [1]: http://www.cs.virginia.edu/~gfx/courses/2002/BigData/papers/Texturing/Clipmap.pdf http://www.cs.virginia.edu/~gfx/courses/2002/BigData/papers/... [2]: http://www.realityprime.com/blog/2006/07/notes-on-the-origin-of-google-earth http://www.realityprime.com/blog/2006/07/notes-on-the-origin... [3]: http://geospatialworld.net/FirstPerson/ArticleView.aspx?aid=18979 http://geospatialworld.net/FirstPerson/ArticleView.aspx?aid=... [4]: http://www.uoc.edu/portal/en/sala-de-premsa/actualitat/noticies/2010/noticia_109.html http://www.uoc.edu/portal/en/sala-de-premsa/actualitat/notic... [5]: http://www.eweek.com/cloud/google-sued-for-alleged-google-earth-patent-infringement.html http://www.eweek.com/cloud/google-sued-for-alleged-google-ea... [6]: http://research.microsoft.com/en-us/um/people/hoppe/gpugcm.pdf http://research.microsoft.com/en-us/um/people/hoppe/gpugcm.p... [7]: http://filougk.blogspot.com/2007/03/gpu-geometry-clipmaps-source.html http://filougk.blogspot.com/2007/03/gpu-geometry-clipmaps-so... [8]: http://spidergl.org/example.php?id=8 http://spidergl.org/example.php?id=8
SunboX 13y ago
Waiting for the time someone comes across VRML ;)
nilkn 13y ago
Writing terrain renderers like this pretty much consumed my junior year of high school. This is the stuff that made me a programmer. I'm glad to see it get some attention here on HN.
arh68 13y ago
Is there a name for this approach? The recursive-tile-morph-factor shader?
peapicker 13y ago
Hate to be a dissenter, but none of the pics in the linked article look good to me. ???
gavanwoolery 13y ago
I did some stuff with terrain LOD by using tessellation, but that is a DX 11 feature and not supported in WebGL yet. Basically I rendered Bezier patches that were turned into triangles on the GPU, and then used screen-space displacement mapping for the finer details. The bezier patches were designed to be seamless but still add/remove triangles as the distance grew. Unfortunately I no longer have the code, but here is an image: http://www.gavanw.com/uploads/9/5/4/0/9540564/8069858_orig.png
sytelus 13y ago
Is this the same algorithm used in games like Dying Light? These new breed of games allows free movements from rooftops to ground with very realistic graphics. http://www.youtube.com/watch?feature=player_detailpage&v=J2TSCZqcjR0#t=36 http://www.youtube.com/watch?feature=player_detailpage&v=J2T...

175 points by pheelicks 13y ago

eliah-lakhin 13y ago

Thank you for such detailed and well written material, pheelicks! I had been looking it for a long time. Bookmarked.

pheelicks 13y ago
Glad you like it! I'm planning on doing a follow-up, where I look at doing more detailed things with the fragment shader, to give the terrain a different look. E.g. using some textures for the ground, like grass, rock, snow etc

platinum1 13y ago

This reminds me of: http://www.zephyrosanemos.com/ http://www.zephyrosanemos.com/ - another very impressive webGL terrain demo. One thing I particularly like about the zephyrosanemos is the realtime rendering of the procedural terrain generation. I'd love to hear a comparison of the two by someone knowledgeable about the subject.

deletes 13y ago

If you look carefully you will see the very tops of the mountains "grow and sharpen" or "shrink and smoothen" when they pass a certain distance. I saw that same behavior in an old game Starsiege Tribes( from 1998 ). Now I know why it happens.

zamalek 13y ago
This could be caused by two issues: Popping: it "naturally" happens with all dynamic LOD systems (back in '98 it would have been Real-time Adaptive Optimized Meshes). It happens when something changes from one detail level to another (and hence more details "pops" into view). If you spend more time on your renderer you will generally morph those vertices between the lower detail position and the higher over a very small amount of time. This means that the pop happens over a longer duration and humans are bad at noticing stuff like that. Incorrect Heuristics: a heuristic is used to determine how far away from the camera you need to be in order to not see the difference between four triangles and two (this has a lot to do with Nyquist-associated theorems) because "the difference is less than a pixel." If you get it wrong you could present too little detail for a pixel and change the apparent shape of the terrain (obviously intentionally presenting too little detail increases framerate).

soup10 13y ago

Cool demo and writeup. Why's is it so sparkly though?

ginko 13y ago
Probably aliasing due to undersampling. Terrain rendering is probably one of the things where GPU-based raymarching really is an option nowadays. http://iquilezles.org/www/articles/terrainmarching/terrainmarching.htm http://iquilezles.org/www/articles/terrainmarching/terrainma...
- ttctciyf 13y ago
  Probably is - I was astonished when I first saw this raymarched procedural terrain at shadertoy: https://www.shadertoy.com/view/4slGD4 https://www.shadertoy.com/view/4slGD4
  - deletes 13y ago
    ::rant:: Crashed firefox( latest version ); tried chrome, loads forever and then doesn't work. For whom is this made, if it doesn't work on my i5 with a decent gpu?
    - ttctciyf 13y ago
      Mac users? :) Sorry! Runs ok (well, 12fps!) here on firefox on an iMac. Just black on my centOS laptop with intel graphics, I admit, but loads of gl things don't run on that.
pheelicks 13y ago
There's a specular light positioned above the terrain, which adds the sparkle (light3 in https://github.com/felixpalmer/lod-terrain/blob/master/js/shaders/terrain.frag https://github.com/felixpalmer/lod-terrain/blob/master/js/sh...). If you want to play around with changing the light etc, you can use Mozilla's awesome in-browser GLSL editor (currently in FF beta): https://hacks.mozilla.org/2013/11/live-editing-webgl-shaders-with-firefox-developer-tools/ https://hacks.mozilla.org/2013/11/live-editing-webgl-shaders...

blackdivine 13y ago

Ah game programming and terrains, the nostalgia :)

zurn 13y ago

Looks superficially similar to the WebGL terrain 3-parter at http://www.gamasutra.com/blogs/JasmineKent/20130904/199521/ http://www.gamasutra.com/blogs/JasmineKent/20130904/199521/ - are there differences?

exDM69 13y ago
This is a common technique so no surprise they are similar. However, there seem to be slight differences in the way the chunk edges are made seamless. In Trigger Rally, there are additional vertices being added to the lower LOD chunk side of the seam to avoid T-junctions in the mesh topology. In the OP demo, the vertices on the higher LOD side of the seam are morphed so that they will be flat with the lower LOD side of the seam. This should also help reduce "snapping" when moving to higher LOD levels.

bitL 13y ago

Very nice! An interesting approach! Did you also consider using some more advanced geometry representation of terrain other than heightfields, such as triangulated irregular networks? That would allow you to choose an error threshold for each LOD and seamlessly join neighboring patches together without the need to use vertex shaders for it. I did my own "Google Earth"-alike using a modified BDAM algorithm a couple of years ago. It required Hadoop preprocessing of detailed input data (resolution in meters), parallel terrain simplification using quadric error metrics and edge collapses and produced a set of layers at different LODs. The cool thing about it was that you could have chosen the desired screen-space error and fetch only those LODs that were fitting - usually these had far smaller size than regular heightfields of the same resoultion/error. You could have also incorporated roads, rivers, buildings, bridges, tunnels straight into your terrain geometry, as well as different textures for each sub-part of it. The tessellation was a bit funky (BDAM uses triangular patches instead of tiles) however there are also variants that utilize rectangular tiles. Vertex shader was then used to simulate 64-bit precision, giving uniform rendering detail in centimeters for the whole Solar system. Geometry shader could add more detail into it and overall it was very snappy online as the size of downloaded data was smaller than with regular meshes.

pheelicks 13y ago
I was keen on keeping as much of the complexity on the GPU, so I wanted to avoid having to update the geometry. Not to say I'm against exploring different approaches. Did your "Google Earth"-alike, ever see the light of day?
- bitL 13y ago
  Completely understood, it's better to focus on interesting 3D stuff and easier to do it this way in JavaScript than to handle tile caching using WebWorkers/WebSockets and local storage in a language that doesn't support proper multithreading. Yes, the project was completed and working fine though it ended up buried deep within my former employer's R&D lab and I have no update if they are using parts of it anywhere. They got acquired and another office was aggressively taking over, getting rid of internal competing technologies. I also had a prior experience in adding dynamic 3D cities and vector maps into NASA's World Wind, and therefore writing a completely own globe from the scratch was a joy ;-) I am thinking about doing similar apps in WebGL and Qt and writing some tutorials on how to do it as I progress, so perhaps we can inspire each other then. First I need to finish some tutorials for advanced 2D geometry and Bezier curves though (Illustrator-class algorithms with JavaScript + HTML5 live examples). Thanks for writing this inspiring piece! :)

zamalek 13y ago

CLOD is the underlying mesh/LOD technology used in Frostbite (BF3/4). There is a formal paper for it [1]. My coworker is currently making a toy CLOD renderer in C++ and the technology speaks for itself - he's rendering 8K x 8K worth of height-map data at some 200 FPS on some laptop NVidia chip (he will be open-sourcing it in a few months time, so watch this space). Frostbite goes a bit further (they stream in the height-map etc.) but the bare method used is this. His reaction to me sharing this was quite funny: > Cool! But… Javascript??! It’s like writing the bible (or your religious equivalent) in glitter and kids crayons… Loses something. You just can't get oldschool developers away from their beloved languages :). [1]: http://dice.se/wp-content/uploads/GDC12_Terrain_in_Battlefield3.pdf http://dice.se/wp-content/uploads/GDC12_Terrain_in_Battlefie...

theandrewbailey 13y ago
It's 2014 and Javascript is awesome. If I ever do anything 3D, it will probably be WebGL. Some industry veterans have reservations against it, but so long as it doesn't look like poop smeared origami, it's OK.
- valarauca1 13y ago
  >2014 and javascript is awesome sort(1,10,5,3) 1, 10, 3, 5 Then there is this. null == false //false !null //true
  - Cthulhu_ 13y ago
    https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe... > The default sort order is lexicographic (not numeric). Works as documented.
    - CmonDev 13y ago
      Ok, pick any other embarrassing design flaw: http://wtfjs.com/ http://wtfjs.com/

elktea 13y ago

Fantastic, I have been looking for good example in modern opengl for a while. Thank you!

xedarius 13y ago

The main reason for LODing is to increase the draw distance. The demo seems to have implementing a LODing system, and then fogged the draw distance anyhow ... which is odd.

dualogy 13y ago
No matter how far your draw-distance is, you totally DO want to "fog anyhow" in any event: you want distant scenery to smoothly fade-out rather than abruptly pop-out (regardless of your actual far-plane distance), plus fogging is a primary spatial-distance cue to the viewer in 3D, and is cheap/free nowadays. Even the real-world does "fogging-out" over distance depending on atmospheric scattering, haze, rain/storm or actual fog conditions. So fogging-out-smoothly, while beneficial as per above, also looks beautifully "realistic" as an added benefit, at least provides a great realism/cost ratio
- lutorm 13y ago
  This has always impacted the realism of flight simulators, in my mind - due to performance reasons, you're always flying around in some pea-soup like fog. At altitude, you can easily see hundreds of miles in clear weather, but I haven't seen any flight simulator that comes even near to being able to render out to those distances.
  - bitL 13y ago
    I believe there are two problems in flight simulators: - insufficient precision of OpenGL 32-bit floats in Earth-scale computations. If you want to render the whole Earth, you'll find that at the ground level your precision is only 16m resulting in jittering as you move. This was usually solved by "zoning" and local coordinate systems, hence it was easier to deal with a smaller set of ground "tiles" and haze out the distant ones. Having said all that, nowadays you can use vertex shaders to simulate 64-bit (or rather 56-bit) precision and get around 1cm resolution at any distance - the need to have various LODs that include curvature of the Earth with significantly increased error tolerances, which in turn increases memory consumption. Again, nowadays should be no longer an issue given entry-level GPUs having 1GB of RAM and geometry shaders

frik 13y ago

Three years ago, someone had the same idea: http://sea-of-memes.com/LetsCode28/LetsCode28.html http://sea-of-memes.com/LetsCode28/LetsCode28.html Edit: just for some additional information, the idea is of course a lot older

shultays 13y ago
This is far older that 3 years old, I don't think OP says he invented it

twp 13y ago

There are some great open source WebGL terrain renderers out there, on a planetary scale, for example: http://doarama.com/view/2171 http://doarama.com/view/2171 This is built on the Cesium open source virtual globe http://cesiumjs.org/ http://cesiumjs.org/

grimmdude 13y ago

This is amazing

merpnderp 13y ago

If the inner level is 1x1 and the other level is 5x5 and the inner level moves by 1 unit, then the outer level will have to move by 1/5 of its 5x5 units (1). Thus the outer level will not move by its proper grid snapping amount. Or am I missing something?

pheelicks 13y ago
The grid snap happens after the movement. You are correct that the higher level grid may not move. To fix this, the higher resolution tiles (1x1 in your example) are morphed near their edges so that gaps do not appear. I cover this in the blog post, see the 'Morphing between regions' section
- merpnderp 13y ago
  I still don't think I understand. If the 1x1 level moves, and didn't overlap the 2x2 outer ring, and the 2x2 outer ring doesn't move (the camera hasn't triggered a 2x2 move yet, just the 1x1), then there is now a gap in the opposite direction of the 1x1 move. That's why trigger rally uses the overlapping geometries, so that a 1x1 level can move and in the direction of the move the overlapping geometries double up and in the opposite direction, they no longer overlap at all (it uses morphing also so that the overlapping geometries have vertices in the exact same spots).
  - pheelicks 13y ago
    Imagine instead that each ring is joined by a set of springs, which can be compressed down to zero and extended to the difference in the grid snapping between the 2 rings. As the rings snap to different grids the springs extend and contract to fill the gaps. Now place some vertices on these springs and you have a terrain mesh, where the majority of vertices are snapped to locations depending on the LOD, except those joining the rings, which such that the transitions between the layers are seamless
    - merpnderp 13y ago
      You are a genius :)

lootsauce 13y ago

This has been a transformational technique in graphics and mapping and I think its worthwhile to recognize where the technique came from. As far as I can tell the origin of the technique described here can be traced back to SGI prior to Keyhole as published in 2002. [1] This "Clip Map" technique is a key enabler of applications like Google Earth because of how efficiently it pages data. Recall that Google Earth was the product of an acquisition of a company called Keyhole. Named after the spy satellite, a reference to the recently declassified satellite imagery they were using. Its also interesting to note Al Gore played an important role in declassifying this data. [2] But to make use of all of this imagery a new efficient algorithm was needed for loading and rendering the data. This is what the Clip Map paper describes and enabled the iconic zoom from space to the surface of the earth with real time rendering of satellite imagery. According to Michael T. Jones. "Keyhole started by accident. The earliest possible origin of Keyhole actually lies with me. I worked with a company called Silicon Graphics (SGI). One of the companies I worked with had created a program to view satellite imagery where you could zoom in and see the imagery in great detail. It was used in the Bosnia peace talks to draw the border." [3] "Before its acquisition by Google, Michael was CTO of Keyhole Corporation, the company that developed the technology used today in Google Earth. He was also CEO of Intrinsic Graphics, and earlier, was Director of Advanced Graphics at Silicon Graphics." [4] It is interesting to note that a German company is now suing Google over Google earth and possibly this very technique. [5] Are ART+COM and Terravison the company and software Michael Jones was speaking of? The real power of this technique is that it allows you to pre-page the data in tiles that can be easily loaded over the web and are sized specifically to live graphics memory. It optimizes both the IO this way and off-loads the mesh creation process from CPU to the GPU. In 2004 Microsoft research published an expansion of the of the Clip Map technique that does just that. [6] A basic demo and source in C++ available [7] and I have also found SpiderGL uses this technique [8] One thing I have not found yet is a good discussion of implementing collision detection in conjunction with this technique if anyone has found any resources on this I would be grateful. [1]: http://www.cs.virginia.edu/~gfx/courses/2002/BigData/papers/Texturing/Clipmap.pdf http://www.cs.virginia.edu/~gfx/courses/2002/BigData/papers/... [2]: http://www.realityprime.com/blog/2006/07/notes-on-the-origin-of-google-earth http://www.realityprime.com/blog/2006/07/notes-on-the-origin... [3]: http://geospatialworld.net/FirstPerson/ArticleView.aspx?aid=18979 http://geospatialworld.net/FirstPerson/ArticleView.aspx?aid=... [4]: http://www.uoc.edu/portal/en/sala-de-premsa/actualitat/noticies/2010/noticia_109.html http://www.uoc.edu/portal/en/sala-de-premsa/actualitat/notic... [5]: http://www.eweek.com/cloud/google-sued-for-alleged-google-earth-patent-infringement.html http://www.eweek.com/cloud/google-sued-for-alleged-google-ea... [6]: http://research.microsoft.com/en-us/um/people/hoppe/gpugcm.pdf http://research.microsoft.com/en-us/um/people/hoppe/gpugcm.p... [7]: http://filougk.blogspot.com/2007/03/gpu-geometry-clipmaps-source.html http://filougk.blogspot.com/2007/03/gpu-geometry-clipmaps-so... [8]: http://spidergl.org/example.php?id=8 http://spidergl.org/example.php?id=8

SunboX 13y ago

Waiting for the time someone comes across VRML ;)

nilkn 13y ago

Writing terrain renderers like this pretty much consumed my junior year of high school. This is the stuff that made me a programmer. I'm glad to see it get some attention here on HN.

arh68 13y ago

Is there a name for this approach? The recursive-tile-morph-factor shader?

peapicker 13y ago

Hate to be a dissenter, but none of the pics in the linked article look good to me. ???

gavanwoolery 13y ago

I did some stuff with terrain LOD by using tessellation, but that is a DX 11 feature and not supported in WebGL yet. Basically I rendered Bezier patches that were turned into triangles on the GPU, and then used screen-space displacement mapping for the finer details. The bezier patches were designed to be seamless but still add/remove triangles as the distance grew. Unfortunately I no longer have the code, but here is an image: http://www.gavanw.com/uploads/9/5/4/0/9540564/8069858_orig.png

sytelus 13y ago

Is this the same algorithm used in games like Dying Light? These new breed of games allows free movements from rooftops to ground with very realistic graphics. http://www.youtube.com/watch?feature=player_detailpage&v=J2TSCZqcjR0#t=36 http://www.youtube.com/watch?feature=player_detailpage&v=J2T...