What kind of hardware would be required to render an Earth sized minecraft like map?

Question

I have been thinking about this problem. Is it possible with current technology to create a 1:1 replica of the earth in voxel based game? What's the best data structure to store this giant map? Which algorithm should be used to render this data structure in real-time?

These questions make these assumptions:

• Each voxel has a resolution of 1 cubic meter.

• For simplicity sake, each voxel requires only 1 byte of metadata information. This information will be used to store the identify the "type" of the voxel (earth, water, rock, etc).

• The earth volume is 1 * 10ˆ21 cubic meters.

• By "current technology" I include anything that is commercially available, but not super computers.

• Only the Earth topography and bathymetry will be used to generate the map. Human building, plants or caves are excluded. The underground blocks will be chosen based on geological studies e.g.: if depth is greater than 3000km render a 'magma' voxel.

• Just like in Minecraft, the map is not static, it can be modified in-game.

• A 'infinite' draw distance is a big plus, what's the point of having the whole earth in a map if you can't fly up and watch the whole planet?

The first conclusion that I came when I thought about this problem is that storing the Earth data in a linear way is infeasible, assuming that each voxel occupies only 1 byte of memory this would still require 1 zettabyte to store the map. So some kind of compression is required.

I think that a voxel octree could compress the map, but I am not sure by how much. The entropy of this voxel map is probably very low, so I guess that a very high level of compression can be achieved.

Disclaimer

This is a theoretical question, I have no intentions of writing a voxel earth

EDIT

The ESA GOCE has already mapped the Earth geoid with a 1cm-2cm precision. I believe that this information could be used to generate a very precise heightmap of the Earth. This would exclude the need to use an algorithm to fill gaps in the Earth topography.

Answer 1

That depends on the spatial subdivision method you use, although all subdivision methods (like any compression method) eventually pan out where no further compression can take place, due to data structure overheads and other logical/mathematical factors. An example can be found in octrees. For each node in the octree, a pointer must be kept to it's parent and/or children (depending on how you go about your data sructure architecture), to enable meaningful traversal. Any tree structure may contain n children. The lower the ratio 1:n, the more efficient use of space you gain, and consequently the larger the overheads in tree-traversal since you must have more ancestor nodes to contain the same number of leaf voxels (in your case, roughly 510 trillion of these representing the surface area).

Considering that in your instance the primary issues are storage cost and rendering the whole planet (or parts thereof) from a fair distance, there is no data structure I would recommend over an octree. Mipmapping is a necessity: 12.8 million meters diameter at the nearest higher power of 2 is 2^24=16.8 million. 24 octree levels to traverse would amount to a gargantuan amount of branching -- very costly for GPUs and CPUs alike. But provided you do things right, you will only ever need to traverse a few levels at a time. Given the amount of space required, though, alternatives are few and far between (see below).

The mipmapping capabilities of octrees are what make it such an incredibly powerful tool for large volumes such as that you describe. Unlike all other known subdivision methods (with the exception of KD-trees), the octree keeps subdivision per level minimal, meaning that the visual and physical differences between mipmap levels are also kept minimal, meaning much finer deltas in granularity as you walk up and down the tree.

If, on the other hand, you want to generate a world where hierarchical grid traversal is kept to a minimum, then you will need to trade off space for increase speed.

Speaking of the ideal 1:n ratio, there is no finer structure than the kd-tree in this respect. Where the octree divides in 2 for each axis, resulting in 2^3=8 individual child cells, the kd tree splits exactly once per subdivision level. The problem with this is that you must choose a hyperplane to split by, and this hyperplane could be chosen around any of the 3 axes. While it is optimal in terms of space, it makes 3D traversals (such as during raymarches, a fundamental op when using octrees for physics or rendering) much more difficult than in an octree, since a dynamic portal-type structure must be kept to record interfaces between individual kd-tree nodes.

RLE is another approach to compression, but is in many ways harder to apply to a problem like this (where the base of operations is spherical), since RLE compression is one dimensional, and you must pick the axis that it operates in. For a planet, one might choose the polar axis, but any single-axis choice would introduce certain issues with traversals for rendering and physics when acting from certain non-optimal angles. Of course, you could also run RLE in 3 axes simultaneously, tripling the storage cost, or in 6 axes (-x, +x, -y, +y, -z, +z) as a further optimisation.

So to answer your question (or not!)

I'm not going to go directly into answering what kind of hardware, but I think looking at it from an octree perspective begins to give you an idea of what is in fact possible on what kind of hardware. I would encourage you to go down this route, if you really want to know, it might be easiest to actually implement a simple sparse octree (see Laine's paper in the refs) and place a spherical shell of surface voxels into it, and see what the resultant space usage is like. Step up from there. See just how far you can get before your system memory starts to give out. This doesn't require you to write a renderer unless you want visualisation. Also bear in mind this is best done on the CPU -- GPUs by and large do not have the memory capacity to deal with problems of this scale. This is one of the reasons Intel is looking at moving towards massively parallel processors: the benefits of GPGPU, which is better at this sort of thing, can be applied to a far vaster memory space without system bus bottlenecks to contend with. There are probably others here, or on mathematics.stackexchange.com, who could answer this space-requirement question directly using mathematical means given just the size of the shell and depth of the octree.

In terms of your infinite view distance requirement, sure, but the question always comes down to, "how much detail at what distance". Rendering infinite detail would require infinite resources. That's where variable-per-scene mipmapping comes into play. Also bear in mind that all data structures embody some tradeoff of speed for space or vice versa. That means less/slower rendering, if you want a larger world for the same amount of engineering effort.

Answer 2

The first conclusion that I came when I thought about this problem is that storing the Earth data in a linear way is infeasible, assuming that each voxel occupies only 1 byte of memory this would still require 1 zettabyte to store the map. So some kind of compression is required.

Since you're most likely never going to find out the properties of each cubic-meter of the real world, you'll need some way to generate that data that is uncertain based on assumptions. So if you have that figured out, there's no need to calculate and store all that data, but you can rather generate it on the fly.

First and foremost you can discard all the voxels within the earth, because these will only have to be calculated if somebody actually digs a hole, eg. the voxels become visible.

For the surface of the earth, I'd probably take an image as starting-point for my calculations. Maybe some sort of temperature- and humidity-map will allow you to calculate the type of blocks to apply. Eg. Water, sand (desert), grass, snow etc. Since the image probably won't have one pixel of information for every square-meter of the earths surface, you would have to mix this with some noise to generate a bit of variation on the surface. If you always use the same random-seeds, your result should be deterministic nevertheless.

In addition, an elevation-map would be useful, so that you can determine the height of the surface features. That way you can add mountains etc.

So this boils down to a data-volume of some 2D images that contain information about the earth surface. For everything on the inside, you would revert to a pure procedural approach, where you render different types of blocks, depending on the distance from the earth-center. But as said above, these have to be calculated only, when somebody digs a hole.

To make changes persistent, I would only save modifications to the world. So if somebody digs a hole, I would store information about which voxels have been removed, as I should be able to render the surrounding voxels procedurally.

As for the rendering: You will need some sophisticated level-of-detail and culling algorithms to make this work. It's silly to render all the surface voxels, when the camera is at a zoom level that shows the whole world. At this level, the voxels should be much bigger, maybe even a simple textured sphere would be enough.

I guess the most tricky thing would be to have a solid generator that allows you to calculate voxel properties, even for different "resolutions", so that you can use it to generate different levels of detail.

Answer 3

You can basically do the same thing that Minecraft does. Rather than making such an amount of data you can define a world as a mathematical formula, whenever a piece of data is required for display you generate it using the formula.

Such a formula is usually constructed using the concept of Perlin noise, this allows for details at all levels, you can have mountain ranges as big as those in the real world, yet choose to only generate a small part of them. You can generate the amount of detail you like, so it's possible to make very fine details for close stuff, yet also generate far off scenery in the required level of detail.

Minecraft saves all those blocks you have visited, complete with whatever changes has been made, one could simply save only the difference between the generated world and the updated world, but I guess saving big blocks was easier, and they do compress relatively well.

I don't think there is any game that really takes this to the limit, but it is very common to use formulaic generation of all the "unimportant" details of large game worlds. I'm not sure how common the generate when needed approach is though, as opposed to simply generating the lot and putting it on the disc.

Answer 4

You could look for vector data of the landmasses of Earth, as vector data has the advantage of scaling to any scale you want. Combine it with a height map of Earth to generate the height of the terrain. Last step is some detailed satellite imagery, from where you can pick the type of the top block based on the image, so you get rock where there's rock, sand where there is sand, etc. The actual insides of the planet should probably be generated like Minecraft does it, unless you can find detailed geographic data to work from. Basically, what you want to do is find geographic data, and extrapolate from it, given only the XYZ coordinate input. This means you have limited data, and you extrapolate the rest as precise as you can.