This is not a paper. Papers tend to be full of proofs and references and structured according to some ancient tradition, and I couldn't be bothered emulating that right now. I might get a bit mathsy towards the end, but this is still just a description of my voxel rendering algorithm for anyone who might be interested.

My voxel renderer is, loosely speaking, raytracing (raycasting?) based. It has a couple of interesting properties. It scales very well as the size of the rendered dataset increases. It also scales reasonably well with increased resolution - I expect it's better than a raytracer and worse than a rasterizer in that respect, but I can't back that up. The main thing that cripples the algorithm is memory usage. Data is required not just for the surface but the entire volume of empty space. Generating a usable dataset involves some fairly hefty processing too.

Tracing

At each point in space, the radius of empty space around the point is stored. This is used to trace rays. Say you query the radius of empty space around the origin of some ray. Regardless of the direction of the ray, you can trace it at least that distance without it intersecting anything. Then, having traced that far, you can look up another radius and trace it further. This technique makes use of the coherency of the environment to skip over large volumes of empty space. Assuming the radius lookups are perfect the ray will never enter the surface, so I simply loop until the radius could be covered by the size of the pixel. This algorithm is not new - I think I saw this in some parallax/displacement mapping paper a few years ago, but I have no idea where. If anyone can point me to a likely candidate, I'd appreciate it.

Data structure

I've simply been using a regular 3 dimensional grid to store the radii, and interpolating between the grid points. This gives an approximation of the actual surface you'd like to represent. I've tried trilinear and tetrahedral interpolation, but any interpolation scheme should work (with varying quality). Note that some interpolation is required; if nearest neighbour is used a ray could step forward and backward repeatedly and never reach a small enough radius to terminate. A regular grid is not optimal. For a start, the (negative) radii inside an object should never be queried, because the rays stop at the surface. Of the negative radii, only those interpolated with positive radii should be needed. In practice the interpolation doesn't result in perfect radii, so radii inside objects are occasionally queried. Also, storing all the radii allows you to grow the world out or shrink it in by a certain radius, simply by adding or subtracting a constant each time you query a radius. Why anyone would want to do that, I don't know. The performance loss of more approximate radii large distances from a surface would not be significant, so a more sparse grid could theoretically be used in those places. That might reduce the currently hefty memory requirements a little.

Recursive rendering

Storing the radius of empty space at each point allows tracing of more than just rays. You could trace anything your heart desires, you just have to find the first time of intersection between your ray and the sphere of space given by the radius. Most interesting to me was tracing frustums. I'll go into the maths of that later. But it allowed me to reduce the number of radius queries needed to generate the same image. I would start by tracing out the entire view frustum, using the radii at the centre of the frustum, until those radii became too small to trace the frustum a significant distance. I would then subdivide the view into 4 smaller frustums, and trace them out from where the larger one stopped. This recursive subdivision means that on average only 2 or 3 iterations need to be performed at the pixel level, resulting in much better performance. This optimisation also relies on relatively coherent world geometry. If the world is noisy, the radii will be small, so the frustums will be subdivided earlier and the performance gains will be less significant.

Tracing frustums

Finding the exact time of intersection between a frustum and a sphere would require a square root, which would seriously degrade performance. Fortunately, you don't actually need to calculate the intersection time of the frustum with the sphere. You only need a conservative estimate of the distance to step forward, although poor estimates will result in lower performance due to the increased number of radius queries and early subdivision.

Last Updated Saturday, January 19 2008 @ 07:26 PM NZDT|171 Hits