Core S2 Software Solutions

Cubism

A while ago I worked on a small experimental project to try and figure out how the Minecraft game rendered such a complex world without having any major frame-rate hit. Most end-users might think it’s a simple world to render: after all it’s just cubes, right? Turns out it’s extremely complex for three reasons:

1. The world has true depth. In most 3D games, when you go up or down terrain, all you are really doing is just walking along a plane that has had it’s depth changed in certain areas. Complex scenery, such as a building, is just hollow and has plenty of open space. If you were to take a camera and bring it below the game’s surface, you would see nothing. Minecraft has a fully editable world so if the user chooses to, they can mine all the way straight down, and thus the world is required to not only render the surface but also render under-ground elements. Also, user’s have the ability to build in the air, so if they had enough time, they could fill the entire world volume with cubes and have absolutely no empty space.

2. The world is editable. A quick solution to the Mincraft rendering problem would be to batch-render everything: put all of the required polygones and textures directly on the graphic card’s memory, and that’s that! The problem with this is that the world can change over time, and thus any content on the graphics card will have to come back and forth between main memory to be manipulated (i.e. when blocks are removed or added) and the hardware again.

3. The world grows exponentially fast in scene complexity. The world is a 3D volume, and the “bigger” the world is, the exponentially more  polygons we have. A 32 by 32 by 32 world, assuming six faces per cube, has at most ~20 thousand faces. A world that is twice as long, wide, and tall (64^3) has ~1.6 million faces! It is unreasonable to retain straight-forward data simply because any reasonably sized world would have too much data to handle at once

Our solution, since this experiment was to figure out how the original scene rendering system works from Minecraft, was to find an optimization technique for these massive amounts of polygons. I explain our general approach through a video on YouTube:

The basic approach was to group up indivual cubes as “chunks”, where contained a volume of 8x8x8 cubes. Within this chunk, we applied a “filter” algorithm that removed all faces that could not be seen by the user (i.e. faces that did not touch an “air” block) and completely removed cubes that were surrounded. If the user build a thick wall that was 8x8x8 cube elements, only the outermost surfaces had to be rendered, since the user could never see “inside” the wall.

To deal with fast changes such as when the user destroys or adds a block, we only reapply this “chunks” algorithm onto the single chunk that was updated. Thus, the world could be left alone on the hardware, and only small amounts of memory had to be changed at a time. Email me if you want access to the source code!

This entry was posted in Programming. Bookmark the permalink.

2 Responses to Cubism

  1. Erich S says:

    Hey, I remember this.

  2. Samuel says:

    Interesting! I want to learn about this too! Despite being a little late…!

    Emailing you!

    Congrats!

Leave a Reply

Your email address will not be published. Required fields are marked *


*

Sites map