Zelimir Fedoran
email zelimir.fedoran@gmail.com

Rendering Voxels

Posted on
April 21st, 2010
Tags
, ,

I have decided that orion will have similar gameplay mechanics to Minecraft, Love, and Miner Dig Deep. I really enjoy the ability to poke holes into a mountain to create vast underground caves and hideouts. Another aspect of all three games is their size. They’re all huge! Minecraft actually claims to have infinite level sizes. While I don’t think infinity is necessary, large sandboxes are more fun than little ones.

With large destructible voxel based environments in mind, I have started development on orion.

16x16x16 RegionA Single VoxelA Single Voxel

Memory Representation

Voxel data is stored in two byte arrays. These arrays are subdivided into 16x16x16 or 32x32x32 regions of voxels. One of the byte arrays contains the id of the block type. Since a byte can store 256 different numbers, there are 256 possible block types. The second byte array stores information about the block. For now I am using it to store which faces are visible for each voxel. Since a cube has 6 sides and a byte has 8 bits I have 2 extra bits which will probably be used for declaring a block as transparent or non-destructible.

Rendering

Drawing each voxel, one per draw call, is a horrible idea for even small worlds of 16x16x16. If the world is 256x256x256 voxels and we assume 5% coverage then there are 419,439 potentially visible voxels. Even with fog and frustum culling, that’s about 50,000 to 150,000 voxels that need to be drawn each frame. I considered using mesh instancing to draw each of the voxels in a similar way to how Fez renders its “trixels“. However, the Xbox 360 lacks hardware instancing support so I went with a different route (note: while hardware instancing is not supported shader instancing is).

I decided to draw groups of voxels or regions per draw call. Each one of the regions can be drawn with a vertex and index buffer corresponding to that region. By increasing the size of the regions I can reduce the draw calls. However, larger regions lead to more inefficient frustum culling. Also, if I get around to implementing an occlusion query system, large regions may be undesirable since there would be a greater chance of some pixel in the region being visible and making the occlusion culling pointless.

Creating the Mesh

Currently I am filling 10% of the byte array with voxels at random locations. Once it is filled I iterate through it to find which surfaces are visible and store that data in my second byte array. To create the surfaces I simply iterate trough my visible surface array and create each face using code similar to the code below (note: surfaces are visible if they are next to an empty or transparent voxel). These surfaces are then added to the index and vertex buffer for the current region.

                            Vector3 a, b, c, d, normal, side1, side2;

                            // Create a face in the "Backward" direction
                            normal = Vector3.Backward;
                            side1.X = normal.Y;
                            side1.Y = normal.Z;
                            side1.Z = normal.X;
                            side2 = Vector3.Cross(normal, side1);

                            // Quad vertices for the face in the "normal" direction
                            a = (normal + side1 + side2) * 0.5f;
                            b = (normal + side1 - side2) * 0.5f;
                            c = (normal - side1 - side2) * 0.5f;
                            d = (normal - side1 + side2) * 0.5f;