Source: Voxel Sphere (CPU)
A previous post described an efficient CPU voxel ray tracer with octree compression for an 8192x512x8192 sandbox. One limitation of that engine is the fact that the world is not infinite. Thinking about that, one could wonder: do we want a voxel world to be infinite? Would Minecraft be more fun on a planet, where a world can actually be ‘done’ and ‘explored’? I don’t know, but rendering a voxel sphere certainly is an interesting challenge.
A naive solution to rendering spheres using voxels is to simply rasterize a sphere to a 3D grid. Although this works, on a large sphere, with a player walking on the surface of the ‘planet’, this does not allow for intuitive editing. An alternative is to construct the sphere using six faces:
We now have two new problems: voxels are not equally sized, more or less deformed. The problem is more elaborately discussed in a 2016 paper by A. Dimitrijević et al. titled Comparison of Spherical Cube Map Projections used in Planet-sized Terrain Rendering. Figure 2.1 from that paper nicely illustrates the cause of the deformation:
The paper then evaluates various improvements. Several are suitable for our purposes; among them is the Adjusted Spherical Cube (ASC) approach in Section 4.2, which reduces area distortion by sampling the map directly in spherical coordinates.
With a decent mapping in place we can now populate the sphere using six voxel slabs of, say, 2048x256x2048, for a total amount of 6G voxels, so 24GB of raw data. We’ll obviously need some compression for that. For efficient traversal we will subdivide each slab in chunks of 64^3 voxels. We thus have 32x4x32 chunks for each cube face, divided in four shells.
The traversal is a challenge. Ray tracing a grid of octree chunks is relatively straightforward, but one does not simply intersect a ray with a voxel sphere. It turns out that things get simpler when we bent the rays.
To intersect a ray with the planet, we start with a simple ray-sphere intersection, which yields a point on the surface of the sphere (actually, the outer atmosphere layer), for which we then determine the cube face. The ASC mapping provides us with u/v coordinates within this face, which can then be quantized to a chunk ID and a position within the chunk. With the starting point established, we start a modified 3DDDA traversal of the chunks.
The first part of this is the traversal of the chunks themselves. Given enough chunks, a regular 3DDDA turns out to be sufficient.
The second part is the chunk-to-chunk transition. At each transition we can leave the current chunk through six faces. The chunk is bound by four planes perpendicular to the sphere surface, and the two shell spheres. We find the nearest intersection of the ray with these planes to advance to the next chunk, or to terminate in case we leave the four shells
This leaves us with one issue: due to the concavity of the chunk volume, it is possible for a ray to leave the same chunk twice. It turns out that this problem cannot be completely eliminated. We can approximate the ‘top’ and ‘bottom’ of a chunk with a plane, but the four vertices on a shell sphere do not always lie in the same plane. More on this in a subsequent post, in which a GPU implementation will be discussed.
Source code for Windows / Visual Studio 64.