Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Aleksandar Dimitrijevic]

Hi all,

A long time has passed since my last post on this forum, and in a meantime I have finished my own planet-size terrain engine, so I have some question to ask in order to correctly classify the Outerra engine and make a valid comparison. 

In order to avoid overwhelming with questions, let's start with the organization of data. As I read from this forum posts, Outerra uses some form of quadrilateralized spherical cube (QLSC). The topic became interesting again few years ago when Chan claimed that his version ('75) was precise and exact equal-area projection, and that Laubscher desecrated his work one year later ('76). Brano said Outerra uses some modification, but can we say it is still QLSC?

If each side of the QLSC uses its own quadtree, does it mean there is always 6 quadtrees in the memory (of even 12, if the elevation data is decoupled from the texture)? I guess the data is cached in those quadtree structures.

How do you create a grid for the chunks upon which the terrain is elevated? Does Outerra still uses a sphere or you have started to use ellipsoid?

If the coordinate system changes at certain altitude, how do you address data using local coordinate system?

I'm sorry for the overwhelming with the questions! 
Everything I asked was just related to data organization, which I would like to compare with mine. I'm planning to use Outerra as an example of QLSC data organization (probably the most popular approach along with classical geographic grid).

Thank you in advance!

[cameni]

I have finished my own planet-size terrain engine

Links! Pics! Or it did not happen

In order to avoid overwhelming with questions, let's start with the organization of data. As I read from this forum posts, Outerra uses some form of quadrilateralized spherical cube (QLSC). The topic became interesting again few years ago when Chan claimed that his version ('75) was precise and exact equal-area projection, and that Laubscher desecrated his work one year later ('76). Brano said Outerra uses some modification, but can we say it is still QLSC?

Honestly, I don't know. I usually find only later what name(s) exist there for something I did, and I normally do not invest too much energy into a detailed comparison. Looking at it now, all resources I'm able to find quickly only mention that QLSC attempts to make an equal-area projection (for Chan: center of every face is expanded in order to make an approximately equal-area map), but I'm unable to find any better description of Chan's or Laubscher's algorithm.

In OT the individual cube face coordinates u,v (in range -1..1) are mapped to the sphere by normalization of vectors made from <u, v, ±k> set (order depends on the face), where k is:

k = 1 + 0.2071067812 (1 - u²)(1 - v²)

With 0.2071067812 ~= 0.5/(sqrt(2) - 1) - 1, which is creating most regularly sized tiles.
Technically it's kind of "expanded center" too, but I hope you'll be able to clarify how that compares to QLSC.

If each side of the QLSC uses its own quadtree, does it mean there is always 6 quadtrees in the memory (of even 12, if the elevation data is decoupled from the texture)? I guess the data is cached in those quadtree structures.

Quadtrees are dynamic so they exist only into a depth that's necessary or cached until the limiter disassembles the finer levels again.

How do you create a grid for the chunks upon which the terrain is elevated? Does Outerra still uses a sphere or you have started to use ellipsoid?

By employing the above mentioned mapping function. Ellipsoid is not yet used, but it should be relatively straightforward, once there's a real need for it.

If the coordinate system changes at certain altitude, how do you address data using local coordinate system?

Not at certain altitude, but at certain quadtree level, where the reference coordinates change to local center.

[Aleksandar Dimitrijevic]

Thank you very much for the answers, Brano!

Links! Pics! Or it did not happen

I'll soon publish the whole algorithm as well as screen shots and videos.
But it wouldn't be as spectacular as Outerra, probably.

Since I'm not very familiar with the quadtree implementation of terrain data, I need some clarification. I'm sorry if I'm asking something trivial, but I have totally different perspective, hence the problem of misunderstanding.

Quadtrees are dynamic so they exist only into a depth that's necessary or cached until the limiter disassembles the finer levels again.

How do you cache data (both geometry and texture) in quadtree nodes? Does a node contain just hight-field of a full 3D mesh?
I guess nodes are not resident. It would be very inefficient (or even impossible) to store a whole quadtree in the memory. So you need some algorithm to page-in/page-out nodes. How do you actually cache date? I'm using clipmaps, where caching and data fetching is quite obvious and "natural", hence the questions.

Thank you again! The previous post already corrected one of mine false assumption about data organization. Something that is inherent for the clipmaps, but not for the chunked LODs. Although, I still think clipmaps are more efficient and easier to deal with.

[cameni]

Our quad tree nodes are mainly represented in GPU memory, but there are some data stored on the CPU side - the data unpacked from wavelet compressed source of external terrain data, and data used for collisions etc.
But most of it is kept on the GPU as heightmaps, color and bio maps and meshes. Live nodes keep at least texture and mesh, sometimes heightmap if it's necessary for lower level chunks to generate from. It's dynamic - a very important component of the system is the limiter that manages tiles. Tiles can be in various states - ready to be rendered, ready to be generated, loaded/created etc. Limiter keeps just a subset of nodes to be in each of the states that consume some limited resources.

What tile levels are rendered depends on the quality metrics that accounts for the amount of stretching on the textures. It can easily get into a bit irregular shapes because of that, but that's no problem for the algo:



I'd say that caching and data fetching is straightforward in quadtree driven rendering too, or I fail to see where the problem is. Quadtrees are traversed from top down, tiles checked for visibility, quality metrics decides if refinement is necessary, requests to load/generate/render etc.

[Aleksandar Dimitrijevic]

Thanks again, Brano!

Live nodes keep at least texture and mesh, sometimes heightmap if it's necessary for lower level chunks to generate from.

Isn't height maps necessary for all nodes, except the topmost levels where elevation of the terrain can be neglected?

Tiles can be in various states - ready to be rendered, ready to be generated, loaded/created etc.

If I understand correctly, each quadtree node contains instances of one or more tiles. Does a tile contains all relevant data for the proper spatial extent, or there is a tile for each data type. In my approach, the texture overlay is decoupled from the geometry and separately updated. This enables different metrics for geometry and overlay.

What tile levels are rendered depends on the quality metrics that accounts for the amount of stretching on the textures.

Does it imply strong coupling height fields and texture overlay? Using a texture stretching as a metric is a little bit odd. It is chosen probably because of vertical cliffs. But equally spaced hight fields is not sufficient in that case for the terrain rendering.

I'd say that caching and data fetching is straightforward in quadtree driven rendering too, or I fail to see where the problem is. Quadtrees are traversed from top down, tiles checked for visibility, quality metrics decides if refinement is necessary, requests to load/generate/render etc.

No doubt quadtrees are good for the terrain rendering. They wouldn't be used in such number of engines otherwise. What I see as a problem, since I'm not involved in quadtree based rendering, is data organization on a GPU side. You probably need some way to combine multiple textures/overlays into a single resource (a.i. texture). Otherwise, each node would have its own resource (texture). Clipmaps inherently use a single resource (or almost a single) for the whole dataset. That could be possible for the quadtrees too, to have just a single texture array, but in that case accompanying texture will be a clipmap actually. 

[cameni]

I see our perspectives are indeed quite different.

Isn't height maps necessary for all nodes, except the topmost levels where elevation of the terrain can be neglected?

Wavelet decompression uses data from upper layers, so we have to keep these even when the nodes are not rendered (just traversed). If the limiter throws them away, they have to be reloaded.
 

Tiles can be in various states - ready to be rendered, ready to be generated, loaded/created etc.

If I understand correctly, each quadtree node contains instances of one or more tiles. Does a tile contains all relevant data for the proper spatial extent, or there is a tile for each data type. In my approach, the texture overlay is decoupled from the geometry and separately updated. This enables different metrics for geometry and overlay.

tiles == nodes
A renderable node contains mesh (sometimes in the form of heightfield+displacement info) and a texture. These are connected in OT, generator produces both at once.

Does it imply strong coupling height fields and texture overlay? Using a texture stretching as a metric is a little bit odd. It is chosen probably because of vertical cliffs. But equally spaced hight fields is not sufficient in that case for the terrain rendering.

Basically yes, though not quite. The metric is not quite as simple, because just a small steep step in the mesh would force the terrain to refine too much, so it's probably comparable to measuring screen space size of the tile. Though not quite that, because that would not capture some peaks on the tile that from some views do not enlarge the screen size much, but make the texture stretched and blurry just in some parts.

As long as the tile would have parts of it blurry because of stretching beyond a threshold, a refinement is requested. Generator loads or produces refined data, and when it's ready, it gets rendered instead of the parent node.

You probably need some way to combine multiple textures/overlays into a single resource (a.i. texture). Otherwise, each node would have its own resource (texture). Clipmaps inherently use a single resource (or almost a single) for the whole dataset. That could be possible for the quadtrees too, to have just a single texture array, but in that case accompanying texture will be a clipmap actually. 

I'm not sure I understand this part. A single resource for the whole dataset? Since we are augmenting the world elevation data (which would be ~80GB unpacked by itself) with procedurally generated levels, that makes 1E17 vertices for the whole world. Quadtrees+some tricks allow us to expand the resolution almost indefinitely.

We certainly aren't using a single resource. Technically though, the limiter keeps a fixed array of textures and buffers and controls the population of slices there as requested by the metric and current view, and constrained by the resource limits.

[Aleksandar Dimitrijevic]

I see our perspectives are indeed quite different.

Yes, our approaches are diametrically opposite. That's why I started this thread. I need to understand your implementation in order to be able to compare with mine. And I hope we will both learn something from each other.

A renderable node contains mesh (sometimes in the form of heightfield+displacement info) and a texture. These are connected in OT, generator produces both at once.

The main problem to understand your implementation is my poor knowledge of the chunked LOD implementation and different terminology we are using. In the meantime I have read about Chunked LOD, and I hope the conversation will be much easier now. I've read original Ulrich's paper from 2002 and Kevin's chapter from 3D Engines for Virtual Globes.

I thought you were referring to additional assets on the terrain when you use term mesh, but it seems you actually refer to a terrain geometry. Does chunked LOD still need full mesh for the chunk (if you are using TIN, all three coordinates for each vertex are required). I think this is the first point of misunderstanding. Do you understand correctly the structure of the chunk (precomputed 3D mesh as a basis, additional height field for some additional displacement, index buffer)? I don't need the mesh. Actually I don't even need a grid. Everything is procedurally generated in the vertex shader. My approach does not require even a single attribute for the terrain to be generated. Everything is set by uniforms and textures. Quite different approach.

I suppose your implementation differs from Ulrich's/Kevin's models. Can you procedurally generate a chunk without need to have a full 3D mesh? How the textures are stored and referenced by the chunks?

I'm not sure I understand this part. A single resource for the whole dataset? Since we are augmenting the world elevation data (which would be ~80GB unpacked by itself) with procedurally generated levels, that makes 1E17 vertices for the whole world. Quadtrees+some tricks allow us to expand the resolution almost indefinitely.

We certainly aren't using a single resource. Technically though, the limiter keeps a fixed array of textures and buffers and controls the population of slices there as requested by the metric and current view, and constrained by the resource limits.

Yes, this is the second point where out paths diverge.
According to the previous sentence, you have texture arrays and buffers (filled with chunks' data and indices). The Limiter manages those resources by replacing unneeded data with newly fetched/generated. Probably textures for the same LOD are single layer in the texture array. Is it a correct assumption? Also, probably several chunks share the same VBO. Otherwise there would be a huge number of buffers.

When I was speaking about a single resource, I meant I could have a single texture array for a single partition. In fact I have two, because I'm separating elevations from the coverage (different data-types with different packing), but generally the number of resources is very small. And, oh, yes, I don't have even i single VBO since I don't have any attributes. In clipmaps' approach there is no meshes, just pure textures. And I don't even have a grid to extrude the heights from it. Everything is procedurally generated.

Today I have tried to make some movies to demonstrate my solution, but I failed.
Camtasia significantly disturb the frame rate and display on my built-in profiler. FRAPS is a little bit better, but it is also unusable to reliably reflect what's going on on the screen. What are you using from capturing the screen?

Thank you very much for your time and patience to reply to my questions! 
I'm very grateful!

[cameni]

I thought you were referring to additional assets on the terrain when you use term mesh, but it seems you actually refer to a terrain geometry. Does chunked LOD still need full mesh for the chunk (if you are using TIN, all three coordinates for each vertex are required). I think this is the first point of misunderstanding. Do you understand correctly the structure of the chunk (precomputed 3D mesh as a basis, additional height field for some additional displacement, index buffer)? I don't need the mesh. Actually I don't even need a grid. Everything is procedurally generated in the vertex shader. My approach does not require even a single attribute for the terrain to be generated. Everything is set by uniforms and textures. Quite different approach.

You mean techniques like implicit grid computed from gl_VertexID? Looking up height in textures based on computed coordinates. Yeah that's pretty common.
I do not know how chunked LOD does it, we certainly do not have a separate base mesh. But we do not have all the terrain vertex shaders computing positions algorithmically in all classes of detail levels - for performance reasons and for reasons outlined below. There are actually 3 classes/approaches used depending on the quadtree level.

I suppose your implementation differs from Ulrich's/Kevin's models. Can you procedurally generate a chunk without need to have a full 3D mesh?

Full 3D mesh of what? If you mean whether there is some base spherical patch mesh on top of which we'd modulate heights, then not at all. OT never used TINs, vertex shader can generate everything from a heightfield texture and positional info of the tile/node on the sphere. However, we currently create some intermediate gridded representations that are cached, because heightfield lookups aren't the only thing that make up the terrain in OT. Heightfields come from several sources (elevation dataset, procedurally refined heights, generated heights), and they can be also modified by dynamic vector overlays (things like craters are modifiers).

How the textures are stored and referenced by the chunks?
...
... you have texture arrays and buffers (filled with chunks' data and indices). The Limiter manages those resources by replacing unneeded data with newly fetched/generated. Probably textures for the same LOD are single layer in the texture array. Is it a correct assumption? Also, probably several chunks share the same VBO. Otherwise there would be a huge number of buffers.

All chunks can be in a single VBO, and all textures can be in a single texture array (all LODs in the quadtree have the same sizes). It's not exactly that way because there are ~3 separate ranges of quadtree levels, and data storage is optimized for each. VBOs sometimes contain just heights, at lower levels also things like horizontal displacements and some other attributes.
However, it can be also split into separate buffers and textures, and we support that too. Interestingly, there's practically no difference in performance between the two currently, but we expect we will be able to optimize the former mode better, once we get rid of some constraints of GL3.3 cards that we still support.

When I was speaking about a single resource, I meant I could have a single texture array for a single partition. In fact I have two, because I'm separating elevations from the coverage (different data-types with different packing), but generally the number of resources is very small. And, oh, yes, I don't have even i single VBO since I don't have any attributes. In clipmaps' approach there is no meshes, just pure textures. And I don't even have a grid to extrude the heights from it. Everything is procedurally generated.

Yeah, that's only logical nowadays. Although we refer to that not as procedural but algorithmic, because we are using procedural for stuff that generates extra detail from existing data using fractal-based algorithms. Just in case the "procedural" expression I used above made some confusion

If I understand it correctly, when you have to lookup into distant parts of the texture where samples are apart - it's not going to be very cache friendly if there wasn't also a "mipmapped" representation. I wonder how much more memory clipmaps have to keep, compared to a LOD-fitting quadtree representation of the same thing for a single view on the ground level. But that will largely depend on the reachable quadtree depth and the world size ...

Today I have tried to make some movies to demonstrate my solution, but I failed.
Camtasia significantly disturb the frame rate and display on my built-in profiler. FRAPS is a little bit better, but it is also unusable to reliably reflect what's going on on the screen. What are you using from capturing the screen?

We have our own built-in video recorder there, but recently we also successfully tested Nvidia ShadowPlay.

[Aleksandar Dimitrijevic]

If I understand it correctly, when you have to lookup into distant parts of the texture where samples are apart - it's not going to be very cache friendly if there wasn't also a "mipmapped" representation. I wonder how much more memory clipmaps have to keep, compared to a LOD-fitting quadtree representation of the same thing for a single view on the ground level. But that will largely depend on the reachable quadtree depth and the world size ...

I really don't understand the problem. 
There is no undersampling in clipmaps. Each level in a texture array is a LOD level. Chosen screen space error metric selects appropriate level. The clipmap stacks is implemetet as a texture array (without mipmaping, since levels are actually mip-levels in a global virtual mipmap) while the clipmap pyramid is separate texture with mipmaps.

Unfortunately, I still don't have a clear vision of you implementation, so I'll confine description to clipmaps.

We have our own built-in video recorder there, but recently we also successfully tested Nvidia ShadowPlay.

I'm still using Fermi, so NV ShowPlay doesn't work. It requires (GTX) Kepler.
I also made my grabber, but don't have time to optimize it. The problem is all grabbers (I have't tried ShowPlay) affect utilization of the GPU, so HW counters drastically drop their values. Timers are OK since I'm controlling them, but HW counters are different story. Some colleagues of mine suggest to use a camera and literally record the screen.

Thank you once again for the help!

[cameni]

There is no undersampling in clipmaps. Each level in a texture array is a LOD level. Chosen screen space error metric selects appropriate level. The clipmap stacks is implemetet as a texture array (without mipmaping, since levels are actually mip-levels in a global virtual mipmap) while the clipmap pyramid is separate texture with mipmaps.

I see I have no idea how clipmaps work
Looking at the paper ... "Given a filtered terrain pyramid of L levels, the geometry clipmap caches a square window at each resolution level.".
You mention a global virtual mipmap. Does it mean there's a global texture for the whole dataset, with mipmaps computed so that they can be easily fetched into the clipmap pyramid?

I'm still using Fermi, so NV ShowPlay doesn't work. It requires (GTX) Kepler.
I also made my grabber, but don't have time to optimize it. The problem is all grabbers (I have't tried ShowPlay) affect utilization of the GPU, so HW counters drastically drop their values. Timers are OK since I'm controlling them, but HW counters are different story. Some colleagues of mine suggest to use a camera and literally record the screen.

Our system (or an earlier version of it) is described in the OpenGL Insights book (In-Game Video Capture with Real-Time Texture Compression), I know you have it, being a co-author there too
It was designed to minimize the impact, but of course there's always some unless you have got a hw framegrabber.

[Aleksandar Dimitrijevic]

You mention a global virtual mipmap. Does it mean there's a global texture for the whole dataset, with mipmaps computed so that they can be easily fetched into the clipmap pyramid?

Yes, there's a texture resampled at different resolutions and tiled into manageable blocks (chunks). GPU memory representation is something that is incrementally updated (because of DXT compression usage, minimal width of the strip is 4 pixels in my implementation), while CPU memory cache is tile-oriented (each tile is 1024x1024 pix, 2048x2048 pix, or so), but resembles clipmap representation. Only a subset (centered at the viewer's position, or other focal point) is read from the disk (or downloaded from the net), and cached, first in RAM then in graphics card's memory.

"Virtually" there is a full mipmap, but actually only a fraction of it (green slices) are cached in the GPU.

Our system (or an earlier version of it) is described in the OpenGL Insights book (In-Game Video Capture with Real-Time Texture Compression), I know you have it, being a co-author there too
It was designed to minimize the impact, but of course there's always some unless you have got a hw framegrabber.

Yes, thank you! I have completely forgotten what's in the book. I'll read your chapter this afternoon.
The HW framegrabber I've got cannot be used for the purpose. Never mind, I'll make movies on the regular way, and explain (and illustrate with pictures) what really happens.

I'll send you links to movies later as a personal message. It wouldn't be correct to advertise my engine on your site. 
Let it be for your personal usage only.