Dynamic voxels

In the past couple of weeks, I've learned that there are different methods to efficiently store voxels for GPU raycasting:

- Octrees

- Geometry images (Hoppe 2002, Carr et al., 2006)

- Spatial hashes

- Hybrid aceleration structures such as an octree with bricks (Crassin et al., 2008)


Jules Urbach said in an article on TechCrunch (http://www.techcrunch.com/2008/08/20/the-truth-behind-liveplaces-photo-realistic-3d-world-and-otoys-rendering-engine/):

We store voxel data in several ways, including geometry maps (see our Siggraph or Iceland presentations, where we show this method applied to the Ligthstage 5 structured light data, courtesy Andrew Jones ICT/Graphics lab)

Lightstage 5 is being used to capture performances of real actors in polygon based animations, which are then converted to voxels and stored in geometry maps (or geometry images, see A Brief Overview of Geometry Maps). So there is at least one way to render characters and dynamic objects through voxel raycasting, without the need for hybrid techniques. The paper from Carr et al. (Fast GPU Ray Tracing of Dynamic Meshes using Geometry Images) shows that "interactive" raycasting of dynamic objects is possible "at no extra cost". They use geometry maps to store triangles however instead of voxels. With this method, it's feasible to have extremely detailed characters raycasted in realtime.
Spatial hash maps could possibly be used as for dynamics as well.


In the TechCrunch article Jules Urbach gives some more info on the rendering methods behind OTOY and the Ruby voxel demo:

- The datasets from the BCN and Ruby city scenes contain up to 64 data layers per voxel, including diffuse albedo, fresnel reflectance values, irradiance data, UV coordinates (up to 8 sets), normals, and, for static scenes, look up vectors for 1-20 bounces of light from up to 252 evenly distributed viewpoints (it is important to note that this data is always 100% optional, as the raycaster can do this procedurally when the voxels are close and reflection precision is more important than speed; however, with cached reflectance data, you might see the scene rendering at 100s-1000s of fps when the scene isn’t changing).

- A note on raytracing vs. rasterization: amplifying the tree trunk in Fincher’s Bug Snuff demo to 28 million polys using the GPU tessellator turned out to be faster than rendering a 28 million voxel point cloud for this object. So there is a threshold where voxels become faster than rasterziation at about 100 million polys. At least in our engine, on R7xx GPUs, using full precision raycasting at 1280×720. Below that point, traditional rasterization using the GPU tessellator seems to be faster for a single viewport.

- The engine can convert a 1 million poly mesh into voxel data in about 1/200th second on R770 (60 fps on R600 and 8800 GTX). This is useful for baking dense static scenes that are procedurally generated once, or infrequently, on the GPU. That is why some of the OTOY demos require the GPU tessellator to look right.

- Hard shadows in OTOY were done using rasterization until we got R770 in May. Now hard shadows, like reflections, can be calculated using raycasting, although shadow masks are still very useful, and raycasting with voxel data can still give you aliasing.

- We can use the raycaster with procedurally generated data (perlin generated terrain or clouds, spline based objects etc.). At Jon Peddie’s Siggraph event, we showed a deformation applied in real time to the Ruby street scene. It was resolution independent, like a Flash vector object, so you could get infinitely close to it with no stair stepping effects, and likewise, the shadow casting would work the same way.

- The voxel data is grouped into the rough equivalent of ‘triangle batches’ (which can be indexed into per object or per material groups as well). This allows us to work with subsets of the voxel data in the much the same way we do with traditional polygonal meshes.

- The reflections in the march 2007 ‘Treo’ video are about 1/1000th as precise/fast as the raycasting we now use for the Ruby demo on R770/R700.

- One R770 GPU can render about 100+ viewports at the quality and size shown in the ‘Treo’ video. When scenes are entirely voxel based, the number of simultaneous viewports is less important than the total rendered area of all the viewports combined.

- The server side rendering system is currently comprised of systems using 8x R770 GPUs ( 8 Gb VRAM, 1.5 Kw power per box).

The full Ruby demo: http://www.youtube.com/watch?v=sWgQp_LL-Cg

High quality download: http://blip.tv/file/get/Ubergizmo-AMDR700RubyDemo193.mov

Voxel ray tracing vs polygon ray tracing

Carmack's thoughts about ray tracing:

I think that ray tracing in the classical sense, of analytically intersecting rays with conventionally defined geometry, whether they be triangle meshes or higher order primitives, I’m not really bullish on that taking over for primary rendering tasks which is essentially what Intel is pushing. But, I do think that there is a very strong possibility as we move towards next generation technologies for a ray tracing architecture that uses a specific data structure, rather than just taking triangles like everybody uses and tracing rays against them and being really, really expensive. It
involves ray tracing into a sparse voxel octree which is essentially a geometric evolution of the mega-texture technologies that we’re doing today for uniquely texturing entire worlds. It’s clear that what we want to do in the following generation is have unique geometry down to the equivalent of the texel across everything.

There are some interesting things to note in there:

- ray tracing in the classical sense, in which rays intersect with triangles, is far too expensive for use in games, even with next generation hardware

- the sparse voxel octree format permits unique geometry


Octrees can be used to accelerate ray tracing and store geometry in a compressed format at the same time.

Quote from a game developer (Rare) on the voxel octree:

Storing data in an octree is far more efficient than storing it using textures and polygons (it's basically free compression for both geometry and texture data). It's primarily cool because you stop traversing when the size of the pixel is larger than the projected cell, so you don't even need to have all your data in memory, but can stream it in on demand. This means that the amount of data truly is unlimited, or at least the limits are with the artists producing it. You only need a fixed amount of voxels loaded to view a scene, and that doesn't change regardless of how big the scene is. The number of voxels required is proportional to the number of pixels on the screen. This is true regardless of how much data you're rendering! This is not true for rasterization unless you have some magical per-pixel visibility and LOD scheme to cut down the number of pixels and vertices to process, which is impossible to achieve in practice. Plus ray casting automatically gives you exact information on what geometry needs to be loaded in from disk, so it's a "perfect" streaming system,
wheras with rasterization it would be very difficult to incrementally load a scene depending on what's visible (because you need to load the scene before you know what's visible!)
If you want to model micrometer detail, go ahead, it won't be loaded into memory until someone zooms in close enough to see it. Voxels that are not intersected can be thrown out of memory. Of course you would keep some sort of cache and throw things out on a least recently used basis, but since it's hierarchical you can just load in new levels in the hierarchy only when you hit them.

Voxels have some very interesting benefits compared to polygons:

- It's a volumetric representation, so you can model very fine details and bumps, without the need for bump mapping. Particle effects like smoke, fire and foam can be efficiently rendered without using hacks. Voxels are also being used by some big Hollywood special effects studio's to render hair, fur and grass.

- id wants to use voxels to render everything static with real geometry without using normal maps.

- Voxels can store a color and a normal. For the renderer, textures and geometry are essentially the same.

- The position of the voxel is defined implicitely by the structure that is holding it (the octree). Here's the good part: this structure represents both the primitives that need to be intersected and the spatial division of these primitives. So, in contrast to triangle ray tracing which needs a separate spatial division structure (kd-tree, BVH, ...), voxels are right away structured in a grid or an octree (this does not mean that other structures can't be used as well). So for voxel ray tracing, octrees are perfect.

- Voxels are very cheap primitives to intersect, much cheaper than triangles. This is probably their biggest benefit when choosing between voxel and polygon ray tracing.

- A voxel octree permits a very natural multiresolution. There's no need to go deeper into the octree when the size of a pixel is larger than the underlying cell, so you don't have to display detail if it's not necessary and you don't streal in data that isn't visible either way.

- Voxels are extremely well suited for local effects (voxel ray casting). In contrast to triangle rasterization, there are no problems with transparency, refraction, ... There are also major benefits artwise: because voxels are volumetric, you can achieve effects like erosion, aging materials, wear and tear by simply changing the iso value.

- Ray casting voxels is much less sensitive to scene complexity than triangles

(partly translated from http://forum.canardplus.com/showpost.php?p=1257790&postcount=96)


Disadvantages of voxel ray tracing vs polygon ray tracing:

- Memory. Voxel data sets are huge relative to polygon data. But this doesn't have to be a problem, since all data can be streamed in. This does however create new challenges when the point of view changes rapidly and a lot of new data bricks have to be streamed in at once. Voxels sets have the benefit over polygons that voxel subsets can be loaded in, which permits some sort of progressive refinement. Other possible solutions are: using faster hard disks or solid state drives to accelerate the streaming, limiting depth traversal during fast camera movement or masking the streaming with motion blur or depth of field postprocessing.

- Animation of voxels requires specialized tools

- Disadvantages of ray tracing in general: dynamic objects require the octree to be updated in realtime. However, there are solutions for dynamic objects which don't require updating of the octree (such as building a deformation lattice around dynamic objects so that when you raycast into it bend the rays as it hits the deformation lattice). id Tech 6 plans to tackle the problem of having many dynamic objects with hybrid rendering.

More on dynamic raytracing:

Dynamic Acceleration Structures for Interactive Ray Tracing, Reinhard, E., Smits, B., and Hansen, C., in Proc. Eurographics Workshop on Rendering, pp. 299-306, June 2000. Summary: This system uses a grid data structure, allowing dynamic objects to be easily inserted or removed. The grid is tiled in space (i.e. it wraps around) to avoid problems with fixed boundaries. They also implement a hiearchical grid with data in both internal and leaf nodes; objects are inserted into the optimal level.

Towards Rapid Reconstruction for Animated Ray Tracing, Lext and Akenine-Moller, Eurographics 2001. Summary: Each rigid dynamic object gets its own grid acceleration structure, and rays are transformed into this local coordinate system. Surprisingly, they show that this scheme is not a big win for simple scenes, because in simple scenes it is possible to completely rebuild the grid each frame using only about a quarter of the runtime. But, this would probably not be true for a k-d or BSP tree.

Distributed Interactive Ray Tracing of Dynamic Scenes, Wald, Benthin, and Slusallek, Proc. IEEE Symp. on Parallel and Large-Data Visualization and Graphics (PVG), 2003. Summary: This system uses ray transformation (into object coordinate system) for rigid movement, and BSP rebuild for unstructured movement. A top-level BSP tree is rebuilt every frame to hold bounding volumes for the moving objects. Performance is still an issue for unstructured movement.

Interactive Space Deformation with Hardware Assisted Rendering, IEEE Computer Graphics and Applications, Vol 17, no 6, 1997, pp. 66-77. Summary: Instead of deforming objects directly, this system deforms the space in which they reside (using 1-to-1 deformations). During raytracing, the rays are deformed into the object space instead of deforming the objects into the ray space. However, the resulting deformed rays are no longer straight, so they must be discretized into short line segments to perform the actual ray-object intersection tests.

Ray casting free-form deformed-volume objects, Haixin Chen, Jürgen Hesser, Reinhard Männer A collection of techniques is developed in this paper for ray casting free-form deformed-volume objects with high quality and efficiency. The known inverse ray deformation approach is combined with free-form deformation to bend the rays to the opposite direction of the deformation, producing an image of the deformed volume without generating a really deformed intermediate volume. The local curvature is estimated and used for the adaptive selection of the length of polyline segments, which approximate the inversely deformed ray trajectories; thus longer polyline segments can be automatically selected in regions with small curvature, reducing deformation calculation without losing the spatial continuity of the simulated deformation. We developed an efficient method for the estimation of the local deformation function. The Jacobian of the local deformation function is used for adjustments of the opacity values and normal vectors computed from the original volume, guaranteeing that the deformed spatial structures are correctly rendered. The popular ray casting acceleration techniques, like early ray termination and space leaping, are incorporated into the deformation procedure, providing a speed-up factor of 2.34-6.56 compared to the non-optimized case.

More info on id Tech 6 and voxel ray casting in the ompf thread