Outerra forum

Outerra Engine => Technology => Topic started by: Aleksandar Dimitrijevic on January 05, 2010, 11:24:11 am

Title: Planetary Engine in detail
Post by: Aleksandar Dimitrijevic on January 05, 2010, 11:24:11 am
Hello Brano, and thank you for the invitation for this forum!

I'm also involved in the development of a large terrain rendering algorithm, so I hope we have a lot of topics to discuss about. :)

First of all, I have to congratulate you on your effort to build extraordinary engine!

Let's continue the discussion from the Intro (http://outerra.blogspot.com/2008/07/intro.html) page...
Quote from: Brano Kemen
Yes, using a geocentric coordinate system for the planet directly would allow only for limited precision, and thus it can be used only up to a certain level of detail (i.e. for some maximum distance from the surface). So what I do is that the geometry for the more detailed terrain tiles is generated in its "local space", what is a coordinate system centered in the middle of the terrain tile that starts to use it. All subsequent subdivisions of this tile use the same coordinate system.
Finally, for the rendering of these tiles the camera is expressed in the local space too. This way you get rid of large static numbers in coordinates that ruin the precision.
Yes, that is exactly what must be done, but there is a problem when switching from one "local" tile to the other.

Many applications I am involved now does not require planet-sized terrain, so I've discarded all calculation involving Earth's diameter on certain geographic latitude and geoid's correction. But rendering the whole Earth will always be a hot topic. ;)

During the reading your posts, I have found some interesting ideas that are just mentioned and not explained, and I'm very curious if you can give just a bit of explanation on them.

One of them is using wavelet compressed terrain data. Which algorithm are you using? Ecw, MrSID, JPEG200, or some custom built? Five years ago I had carried out some experiments with ECW compression and found out that it cannot be used, because of very high level of degradation. That degradation is suitable for the image, because our eye cannot find the distinction in the variations of colors, but using it on the terrain heights is not acceptable.  Lossless compressions can be used, but the compression-rate is moderate or poor (except on the large water surfaces with zero-elevation).

The idea of using torrent protocol for the data retrieval is excellent!

Can you give us a clue on what algorithm is based Outerra for managing terrain LOD? Quadtrees, Octrees, Clipmaps, Ray casting or something quite different?

Thank you in advance!
Title: Planetary Engine in detail
Post by: cameni on January 05, 2010, 12:53:01 pm
Welcome, and thanks for the kind words.

There is no problem with switching between separate local spaces that I'm aware of, can you explain what you mean?

We are using custom wavelet compression, that does not smoothen the terrain when producing coarser levels. You are right, what is good for images is not at all good for the height maps. Initially we used Haar wavelet but due to the smoothing it was unusable. Currently we are using one (don't know if it's got a name) that reduces a (2n+1)*(2n+1) map to a (n+1)*(n+1) one by picking every other row and column, and encoding the remaining points as differences to the interpolated values. It's lossless compression, and the final dataset for Earth with resolution ~76m is somewhere around 13 gigs.

But just a small part of it is needed, I think it was 20Mb when landing perpendicularly on Earth surface, and more data was needed only after moving several kilometers away. Also, thanks to the wavelet and separation of LOD layers, less data is needed when flying in higher altitudes. So it can be all downloaded progressively.

Terrain LOD is managed using quad-trees, with error metric that considers the amount of texture stretching on terrain tile to decide when to subdivide.
Title: Planetary Engine in detail
Post by: Aleksandar Dimitrijevic on January 06, 2010, 06:27:14 am
Quote from: cameni
There is no problem with switching between separate local spaces that I'm aware of, can you explain what you mean?
The problem is in the fact that I'm trying to minimize terrain reorganization and keep all coordinates of the vertices in the block. Moving from one coordinate system to the other requires blocks reorganization, which is an expensive operation for me. I didn't think much about that, but I'll post my solution when I consider all possibilities and carry out some experiments and measure the speed of execution.

Quote from: cameni
Initially we used Haar wavelet but due to the smoothing it was unusable. Currently we are using one (don't know if it's got a name) that reduces a (2n+1)*(2n+1) map to a (n+1)*(n+1) one by picking every other row and column, and encoding the remaining points as differences to the interpolated values.

That is exactly what I'm doing, but currently do not use compression. Textures are much greater than DEM and so far I didn't need to compress it, but I will for sure. Thank you for the suggestion!

Did you publish any paper on this topic? I would like to try floating point Z-buffer extensions and logarithmic Z-buffer in my algorithm (although currently I don't have problems with z-fighting because of dynamically changing near and far clipping planes), and it will be useful to have a reference.
Title: Planetary Engine in detail
Post by: cameni on January 06, 2010, 07:16:20 am
Quote from: Aleksandar
The problem is in the fact that I'm trying to minimize terrain reorganization and keep all coordinates of the vertices in the block. Moving from one coordinate system to the other requires blocks reorganization, which is an expensive operation for me. I didn't think much about that, but I'll post my solution when I consider all possibilities and carry out some experiments and measure the speed of execution.
What method do you use for LOD? Because it sounds you re doing something very differently. With the quadtrees I'm simply generating tiles up to a specific quadtree level in the global (geocentric) coordinate system, and tiles from that level and deeper are generated in their local coordinate spaces. Once the VBOs are generated, they are never reorganized or anything, just rendered with appropriately shifted camera.

Quote
Did you publish any paper on this topic? I would like to try floating point Z-buffer extensions and logarithmic Z-buffer in my algorithm (although currently I don't have problems with z-fighting because of dynamically changing near and far clipping planes), and it will be useful to have a reference.
No I didn't write any paper on it, I'm not skilled in writing academic papers (I never tried ;)).
But of course I'll gladly help you if you find any problems with it or if there's something unclear.
Title: Planetary Engine in detail
Post by: Aleksandar Dimitrijevic on January 06, 2010, 07:51:22 am
Quote from: cameni
What method do you use for LOD? Because it sounds you re doing something very differently.
Yes, indeed. My algorithm is similar to clipmaps, but the whole terrain is organized into blocks of equal spatial size, but the LOD depends on the distance from the viewer (using nested rings). Each block is a mini-world for itself and does not change its structure as long as it says in the bounding box of certain LOD level (i.e. ring). In 2006. I published two papers on this topic, but then the algorithm was at its beginning with many things unsolved. In that time I have to develop an algorithm that uses fixed functionality (because of equipment it had to be executed on) and to achieve highest possible frame rate with minimal CPU utilization. Now the time has come to change it a bit. :)

Quote
No I didn't write any paper on it, I'm not skilled in writing academic papers (I never tried ;)).
But you should try! ;)
Practical approach, skills and ideas you have should be published as an academic paper.
Title: Planetary Engine in detail
Post by: cameni on January 06, 2010, 04:25:14 pm
Quote from: Aleksandar
Quote
No I didn't write any paper on it, I'm not skilled in writing academic papers (I never tried ;)).
But you should try! ;)
Practical approach, skills and ideas you have should be published as an academic paper.
Well, I might write one about the approaches and results after it's done. But I have yet many things planned to do there, and the blog format suits me better now. But I should probably put more technical details into it, since there are still more people asking for it.
Do you work in academic field?
Title: Planetary Engine in detail
Post by: Aleksandar Dimitrijevic on January 07, 2010, 11:36:46 am
Fortunately, or unfortunately, I do work in academic field. :)
I'm also involved in many scientific and non-scientific projects. Those programming and fulfilling customers' requests dragged me out from the computer graphics and finishing my own terrain rendering algorithm. But, slowly I'm coming back...

I'm glad that you have started your blog and this forum. It is always very useful to exchange ideas with people doing the same thing. Especially, when someone is alone in his effort to do something, like I am.

Thank you for the previous answer about tile's coordinate system! I was blind as a mole, thinking that all tiles in the matrix must be in the same coordinate system, or I'll have problems with bounding areas. I'll try to change drawing "philosophy", by I first have to test the implications of translation of tens of thousands of tiles on the drawing speed. I hope that impact is not significant.

Another very interesting question about rendering the whole globe is In which coordinate system your DEM and raster data are? Having LatLon coordinates dramatically alleviate gathering data, but there are singularities at poles. Even a mighty GoogleEarth have problems with poles. Fortunately, only a small number of people (only those who knows about the problem of rendering the whole Earth) can notice that. :)
Title: Planetary Engine in detail
Post by: cameni on January 07, 2010, 12:28:22 pm
Quote from: Aleksandar
Another very interesting question about rendering the whole globe is In which coordinate system your DEM and raster data are? Having LatLon coordinates dramatically alleviate gathering data, but there are singularities at poles. Even a mighty GoogleEarth have problems with poles. Fortunately, only a small number of people (only those who knows about the problem of rendering the whole Earth) can notice that. :)
We used LatLon coordinate system initially but because of the problems with poles or rather because of problems with the mapping in general we abandoned it.
Currently we are using something called "quadcube" (http://acko.net/blog/making-worlds-part-1-of-spheres-and-cubes) -  cube projected to a sphere, with quadtree for each cube face. Quadtree vertices can be simply projected to the surface of the sphere, although we ended up using a slightly more complicated projection that tries to compensate the distortion appearing there.

As the result we have to remap all raster data to this system while simultaneously compressing and generating LOD layers. It is a relatively slow process, but the resulting data organization is extremely LOD streaming-friendly and rending is then fast and straightforward. Likewise, continuing with fractal noise refinement from the tile level where the elevation data end is natural too.
Title: Planetary Engine in detail
Post by: Aleksandar Dimitrijevic on January 07, 2010, 03:07:49 pm
I had the same idea, but instead of remapping the whole world, I had used LatLon mapping from -45 to 45 degrees (Latitude), which is used for the four sides of the cube, and remap the rest in two plates (top and bottom side of the cube). Of course you did it better. :)

Thank you for the explanation! Currently I am implementing texturing in the new limited area application and Earth-Cube will have to wait some other time for the implementation. ;)

Something related to the previous post...
I have just tried to express each tile (block) in its local coordinates and translate it to the original position on the globe, and ... IT DOESN'T WORK. :(
There are gaps between tiles, as I had assumed, and drawing is significantly slower (PushMatrix/Translate/PopMatrix). So, I'll try to find some other solution. At one moment it seems like it could work, but...