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. The mipmapping capabilities of octrees are what make it such an incredibly powerful tool for large volumes such as that you describe. Given the amount of space required, though, alternatives are few and far between (see below). But provided you do things right, you will only ever need to traverse a few levels at a time. 24 octree levels to traverse would amount to a gargantuan amount of branching - very costly for GPUs and CPUs alike. Mipmapping is a necessity: 12.8 million meters diameter at the nearest higher power of 2 is 2^24=16.8 million. 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).Ĭonsidering 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. Any tree structure may contain n children. 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. 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. This would exclude the need to use an algorithm to fill gaps in the Earth topography. I believe that this information could be used to generate a very precise heightmap of the Earth. The ESA GOCE has already mapped the Earth geoid with a 1cm-2cm precision. This is a theoretical question, I have no intentions of writing a voxel earth EDIT The entropy of this voxel map is probably very low, so I guess that a very high level of compression can be achieved. I think that a voxel octree could compress the map, but I am not sure by how much. 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. Just like in Minecraft, the map is not static, it can be modified in-game.Ī '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 underground blocks will be chosen based on geological studies e.g.: if depth is greater than 3000km render a 'magma' voxel. Human building, plants or caves are excluded. Only the Earth topography and bathymetry will be used to generate the map. The earth volume is 1 * 10ˆ21 cubic meters.īy "current technology" I include anything that is commercially available, but not super computers. Will be used to store the identify the "type" of the voxel (earth, 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?Įach voxel has a resolution of 1 cubic meter.Įach voxel requires only 1 byte of metadata information.
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |