Jump to content
  • Advertisement
Sign in to follow this  
ChristOwnsMe

Minecraft planet using Level of Detail?

This topic is 2331 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey. So I am a noobie with graphics programming, but I was wondering if LoD can handle billions of objects? If i had a planet generated out of minecraft style boxes, and viewed it from space, would it even render? The other option is to just take the average color over a section and create a texture for the planet surface until you get close enough, thereby making a fake LoD. Thanks for the input.

Share this post


Link to post
Share on other sites
Advertisement
The best answer would probably come from mister Minecraft himself, but I guess rendering millions of cubes is crazy, even when batched, using instancing, or whatsoever.

The particular shape lends itself for all kinds of tricks though. For example, maybe they combine blocks to bigger ones from a distance? Let's say 1 cubic meter is the smallest cube you encounter. After 20 meters or so, you could start combining 8 blocks to one 2M3 cube, if all 8 are present.

Another trick is culling whatever is not visible. Culling can be pretty difficult, but in this case, all you need to know if there are neighbour blocks. A cube surrounded by 6 others can never be visible, unless the neighbor blocks are transparent maybe. So, the majority of underground blocks don't have to be rendered at all, until they get revealed by removing the cube above or asides it.

Maybe they aren't rendering cubes at all for distant stuff. How about voxels? I have no experience with them, but drawing colored squares instead of cubes on a buffer may be a boost as well. Only the foreground cubes would be actual 3D shapes then.


Just some thoughts...

Share this post


Link to post
Share on other sites
If you stored your landscape as a sparse voxel octree, maybe you could use marching cubes or simply raycasting.

Share this post


Link to post
Share on other sites

If you stored your landscape as a sparse voxel octree, maybe you could use marching cubes or simply raycasting.

Indeed and since SVO's are hierarchical structures they only have a O(logn) cost, which means assuming infinite memory, you can render any amount of voxels very quickly. Of course, my assumption of infinite memory is invalid, but considering how efficiently voxels can be encoded, you could potentially get a draw distance of at least 8-10x times the current distance supported in Minecraft (which is limited by the efficiency of the hardware rasterizer).

Rendering any number of polygons/voxels is pretty much a solved problem with octrees, kd-trees, BVH's, etc... the real challenge nowadays is how to store all that data.

I don't believe Minecraft uses any sort of advanced LOD (blocks do not get combined at a distance, although they should which would allow for a much greater draw distance), but I do believe some tricks are being used to reduce the number of polygons pushed on screen (such as occlusion culling, etc...).

Remember that the fastest polygons are those that aren't drawn.

Share this post


Link to post
Share on other sites
But doesn't the tree invalidate itself if the tree changes? Players would be able to change the landscape like in MC, so does this change things?

Share this post


Link to post
Share on other sites
[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

But doesn't the tree invalidate itself if the tree changes? Players would be able to change the landscape like in MC, so does this change things?

[/font][/quote]

Yes, but this isn't like a BSP tree where adding one thing shifts the balance and invalidates everything. An octree is more like a mipmap. The area immediately near the player/camera should be 'expanded' out to the most detailed leaf nodes of the tree. Turning individual cells on/off only affects these nodes, plus their immediate parents all the way up to the top of the tree.

Share this post


Link to post
Share on other sites
Great, thanks a lot for the replies. I did some calculations about the size of a planet that takes 1 hour to run across, and this is what I got.


1 hour to run acors(assuming they run 37 km an hour):

37 km circumferance
radius of planet = 6 km
diameter = 12 km
Formula for the surface area of a sphere = 4 x pi x R² = 452 km

1 mc block = 1m
1 kilometer = 1000 meters

cover area of 452,000,000 meters.

at 1 byte per "voxel" block

452,000,000 blocks = 3.36766242980957 GB's

This could be lowered by creating a smaller planet, or using less data for a voxel of course.

So the idea was to create the surface of a planet so the player could see it from space, and then only generate new blocks as they explore underground. It seems that it is indeed possible to do this then.

Share this post


Link to post
Share on other sites
Hey Shadowman, the idea is that of course the game only generates terrain which is in range of the player. That way the amount of data grows pretty slowly unless you're a crazed explorer. Generating everything in one shot is not usually practical. Consider that a 6km radius planet is extremely small - a player can run a full revolution in a couple hours and the planet's curvature will be obvious from the surface (you will not be able to see the base of a mountain 2 km ahead).

That said what you can do is generate high-resolution voxels (1m^3/voxel) for blocks near the player, and generate the rest of the planet with lower-resolution voxels (which would allow it to be seen from space with good enough detail). Then as the player moves, the low-resolution voxels are updated to high-resolution. But it is quite a bit harder to implement.

It is, in fact, possible to render an infinitely big landscape with zero memory, using implicit voxel data (via procedural means, using scalar fields), but that's not worth much outside of tech demos since it's impossible to interact with the voxels and it's significantly more computationally intensive to render it (still O(logn) complexity, though).

With simple RLE (run length encoding, i.e. 11111111 -> (8)1) compression people have achieved rates of around 1.5 bits per voxel, and better schemes can attain even better compression rates. Of course this is dependent on the underlying voxel distribution, natural landscape is very redundant but not everything is (alien-like terrain is significantly more random).

Share this post


Link to post
Share on other sites

at 1 byte per "voxel" block

452,000,000 blocks = 3.36766242980957 GB's

Totally wrong. Most of minecraft content is procedurally generated. A whole world, before interactions, can be stored in like 200 bytes if memory serves. I think Notch noted this multiple times.
No need to compress anything.
Personally, I'd build LODs as impostors of original geometry.

Share this post


Link to post
Share on other sites

Totally wrong. Most of minecraft content is procedurally generated. A whole world, before interactions, can be stored in like 200 bytes if memory serves. I think Notch noted this multiple times.
No need to compress anything.

8 bytes for seed. However, pretty much every single chunk generated from it has inherent "interactions" in the form of liquid flows and hence - every chunk must be saved. So, compressing that chunk data to preserve it is essentially mandatory due of the amount of data involved.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!