Thursday, October 11, 2018

Thinking about voxels

Very often people ask me what a voxel is. I struggle to explain this in simple terms, even to savvy professionals from other fields of IT. In most occasions, I just say a voxel is like a pixel, but in 3D, and move on to refresh my drink or hide in a lavatory. I can't help the feeling I have avoided the question.

To help understand why voxels matter today, we need a different analogy. If I had enough time, I would say voxels are like triangles.

A triangle defines a closed 2D space. Imagine we want to do something to this closed space, for instance, paint it red. We could do this by drawing one long line and making the right turns until we have our triangle:


This is how most triangle rasterization worked in the early days. Even after many clever optimizations, it remained awfully slow. It was an inherently serial solution. The value we paint for one point depends on computations we made for earlier points. This would never scale up to hundreds of millions of triangles per second, even with the transistor densities we have today.

GPUs changed that. They render triangles faster only because the problem is solved in parallel. Remember how a triangle is a closed 2D space? That means there is "inside" versus "outside". The GPU, with a simple test, will know this. If a point is inside it will be painted red. It does not matter whether previous points were inside. Since there are no dependencies between points, the GPU is free to look at many points at the same time.

This amazing property of triangles, where they can tell inside from outside without any additional context, enabled the GPU age.

Just like a triangle defines a closed 2D space, a voxel defines a closed 3D space. And just like a triangle, a voxel can have any properties you want. It could have a color, or a material, or even surface parametrization. Voxels can use UV maps and textures in the same way triangles do. In this next image, you can see this voxel rock that looks indistinguishable from your typical low-poly textured mesh:


We tend to think of voxels as cubes, and most of the time this is correct. A voxel cube is equivalent to a surface quad. Just like the quad can be split into two triangles, a voxel cube can be split into five tetrahedron voxels.

And just like triangles did for 2D problems, voxels enable massively parallel processing for problems in 3D. I think this is a big deal.

But what are these problems that you need to solve in 3D?

Rendering is not one of them, contrary to what intuition may tell you. Rendering is about projecting the data into 2D so humans can understand it. It will always be solved more efficiently using 2D elements like triangles and surface processors like GPUs. While "seeing" is very important for humans, it does not really mean anything to a computer. They have no problem working in higher dimensions.

Pretty much everything else is a problem in 3D. Here is a basic one: Imagine you needed to compute the volume of a very random 3D object that has the size of a small town. If you are using voxel data, you can have hundreds of nodes in a network compute a small section of the object's volume and then add the results to get the final volume. You would get the results in a fraction of the time. This is only possible because voxels, like triangles did it for GPUs, allow you to answer the inside/outside question locally. That's the voxel Eureka moment.

This enables many Holy Grail solutions which for brevity reasons I won't enumerate, but that I will be happy to discuss if you drop me a comment below.

Today, most of the entertainment and geospatial industries still use serial, on-core, approaches to solving their 3D content problems.

As the data grows and more entities are required to produce it and consume it, the shift to parallel computing will necessarily happen. And we can be certain voxels will be at the heart of this next age, just like triangles were at the center of the GPU revolution.

7 comments:

  1. You express how GPUs made triangles work WAY better, do you imagine a similar new type of hardware for voxels? Or is that not necessary because voxels won't be visible until processed through triangles etc?

    Also, please, do feel free to enumerate the various Holy Grail solutions =D.

    ReplyDelete
    Replies
    1. Yes, a programmable voxel hardware pipeline would be fantastic.

      The GPU, when working with triangles, does two main things for you: it maps your triangle primitives to your final pixel output, and it interpolates the different vertex attributes you have defined inside your triangle.

      Working with voxels is very similar to this. The GPU would need to convert your voxel into a bunch of fragments/pixels. The hardware would take care of producing the contour surface and from the surface the fragments. It would also interpolate any attributes you have defined inside the voxel.

      For some weird reason, when it comes to rendering, most people identify voxels with raytracing, while in fact, voxels are very amenable to rasterization as well. Adding GPU support for voxel rasterization is not as hard as hardware raytracing support. Rasterization even for voxels remains a very coherent operation.

      The new pipeline architecture unveiled by NVidia with Turin gets us much closer to this, but the contouring and attribute interpolation still happens in the shaders, the hardware does not provide it.

      As for killer applications, if you are in the geospatial industry:

      - Produce data as the real-time mashup of multiple datasets
      - Compute complex volumetric operations between datasets
      - Track changes over time
      - Use implicit modeling to have complex algorithms produce data in real time

      If you are in the entertainment industry:

      - Ease production by placing content in multiple layers
      - Source control (see who has done what, approve or revert changes)
      - Create procedural layers that take a fraction of the data
      - Allow your players to modify the game world in real time

      Delete
  2. How about "voxel is a small piece of 3D space"? I feel like most people won't care about its shape.

    Are modern GPUs well suited for voxel processing or would it help for them to be redesigned? People are using them to calculate physics, neural networks and much more I'm sure, but there was a push to make it possible in the past. Will such push happen for voxels?

    ReplyDelete
    Replies
    1. The new architecture NVidia announced along with Turin makes working with voxels a breeze. NVidia acknowledges that in the second slide of their official presentation. It is pretty clear they have designed it with this in mind. Making the pipeline voxel friendly is not the same as having the hardware perform the critical operations, as the tensor cores do for AI.
      It only you will have a better time writing your voxel shaders and that you will get decent performance.

      I'm not sure everyone needs voxel hardware. As I see it, it is more a problem anyone producing or managing the content will have, not end users necessarily. If you are making an MMO world or operating a mine site, you should definitively adopt voxels at a large scale.

      Delete
  3. This comment has been removed by the author.

    ReplyDelete
  4. Thanks for the article.
    A thing I don't understand with voxels is how you represent more detailed geometry or meshes within one voxel. I do get one voxel cube is divided up into 5 tetrahedrons, but if I'm not mistaken I've seen you represent way more complex geometry within one voxel cube than what 5 tetrahedrons would allow. Or have you just subdivided the voxel cube into smaller cubes to allow the higher resolution?
    Maybe you could use the image in the article and add visible voxel cube outlines as to illustrate this.
    Please enlighten me if you have the time :)

    ReplyDelete
    Replies
    1. It is a good question. A voxel is just a region of space. You could put anything you wanted inside. For instance a 100MB SQL database could be used to describe the contents of a single voxel. That of course is an exaggeration, but helps illustrate the point. In practice, we try to make voxels as simple as possible. When designing a voxel system, you would like to find the smallest and hardware friendliest representation that can carry your content. In our engine Voxel Farm, you need 8 voxels to make a single cube. A single voxel won't do much for you, there is no way to produce anything visual with just one voxel, let alone any complex geometry.

      Delete