Virtual worlds and games increasingly deliver 3D meshes over the Internet using instanced file formats, such as COLLADA. However, existing simplification algorithms do not account for instancing in their inputs, operating instead on triangle soups or indexed triangle meshes. This makes them unsuitable for highly instanced meshes, since expanding an instanced mesh to an indexed triangle mesh and then simplifying it can result in a larger output file size. The high cost of delivering these larger files over the Internet results in long network latencies and low performance. This paper presents instance-aware simplification (IAS), an algorithm designed to efficiently simplify instanced 3D meshes. To ensure smaller output file sizes, IAS incorporates the existing compression of mesh instancing into its cost metrics. Unlike existing algorithms, IAS strictly reduces file size as it simplifies, so that IAS-simplified meshes of a given file size have higher visual quality than meshes simplified using existing algorithms. On highly instanced models, IAS results in simplified versions that are orders of magnitude smaller than existing algorithms for a given triangle count.

Unlike most graphics systems, a shared, user-generated virtual world is created on-the-fly by end users rather than professional artists. Objects in the world can come and go, and the world can be composed of so many models and textures that it cannot be stored locally on disk. The content must be stored in a shared, networked resource such as the cloud and delivered to clients dynamically.

A virtual-world environment becomes a truly engaging platform when users have the ability to insert 3D content into the world. However, arbitrary 3D content is often not optimized for real-time rendering, limiting the ability of clients to display large scenes consisting of hundreds or thousands of objects. We present the design and implementation of an automatic, unsupervised conversion process that transforms 3D content into a format suitable for real-time rendering while minimizing loss of quality. The resulting progressive format includes a base mesh, allowing clients to quickly display the model, and a progressive portion for streaming additional detail as desired. Sirikata, an open virtual world platform, has processed over 700 models using this method.

We present an efficient computational algorithm for functions represented by a nonlinear piecewise constant approximation called cuts. Our main contribution is a single traversal algorithm for merging cuts that allows for arbitrary pointwise computation, such as addition, multiplication, linear interpolation, and multi-product integration. A theoretical error bound of this approach can be proved using a statistical interpretation of cuts. Our algorithm extends naturally to computation with many cuts and maps easily to modern GPUs, leading to significant advantages over existing methods based on wavelet approximation. We apply this technique to the problem of realistic lighting and material design under complex illumination with arbitrary BRDFs. Our system smoothly integrates all-frequency relighting of shadows and reflections with dynamic per-pixel shading effects, such as bump mapping and spatially varying BRDFs. This combination of capabilities is typically missing in current systems. We represent illumination and precomputed visibility as nonlinear sparse vectors; we then use our cut merging algorithm to simultaneously interpolate visibility cuts at each pixel, and compute the triple product integral of the illumination, interpolated visibility, and dynamic BRDF samples. Finally, we present a two-pass, data-driven approach that exploits pilot visibility samples to optimize the construction of the light tree, leading to more efficient cuts and reduced datasets.

This paper presents a method for efficient compression and relighting with high-resolution, precomputed light transport matrices. We accomplish this using a 4D wavelet transform, transforming the columns of the transport matrix, in addition to the 2D row transform used in previous work. We show that a standard 4D wavelet transform can actually inflate portions of the matrix, because high-frequency lights lead to high-frequency images that cannot easily be compressed. Therefore, we present an adaptive 4D wavelet transform that terminates at a level that avoids inflation and maximizes sparsity in the matrix data. Finally, we present an algorithm for fast relighting from adaptively compressed transport matrices. Combined with a GPU-based precomputation pipeline, this results in an image and geometry relighting system that performs significantly better than 2D compression techniques, on average 2x-3x better in terms of storage cost and rendering speed for equal quality matrices.