Graphics Projects

The Graphics group at Microsoft Research is exploring new graphics representations and algorithms that take advantage of existing and upcoming hardware features to heighten the quality of real-time computer graphics.

Real-Time Soft Global Illumination

Traditional graphics renders “hard” shadows from a point light source like a candle, but neglects “soft” effects including shadows from a large area light source like a cloudy sky or a picture window. These effects add realism and provide cues that enhance our perception of shape. Until now, capturing soft effects has involved sampling rays originating from every surface point in all directions towards the light sources to determine whether intervening objects block or reflect the light. This is tremendously expensive. Can we exploit their smoothness to make these effects easier to compute? Our current work factors rendering into a pre-processing and a run-time phase, called precomputed radiance transfer (PRT). The spherical harmonic basis is used to capture how an object shadows and reflects low-frequency lighting onto itself. Small vectors (e.g. 16D) capture soft effects well and are handled efficiently on GPUs. Though the original PRT work was restricted to static geometry, we have recently been extending it to dynamic geometry too.

Precomputed Radiance Transfer (PRT) captures soft shadows and other global illumination effects from environmental lighting that are critical for realism. The lighting and the object’s response to it, called its self-transfer, are both represented using spherical harmonics. Without shadows, the image on the left glows unnaturally making it harder to recognize the face (in this case, Max Planck). See [prt][shbrdf][cpca].

PRT for Textural Details captures precomputed shading effects from fine-scale features like bumps or wrinkles that respond in real-time to changes in lighting. We have also explored techniques for mapping such precomputed details onto deformable geometry as well as static models like this bunny. See [biscale][ldprt].

Soft Shadows on Dynamic Geometry: can be computed in real-time by approximating each moving character as a small set of animated spheres and accumulating each blocker sphere’s effect at every receiver point in every frame. We make this computation practical using a technique called spherical harmonic exponentiation, which accumulates blocker visibility in a low-frequency log space to replace expensive products of spherical harmonic vectors by simple additions. See [shexp][imacc].

Back to top

Procedural Geometric Representations and Rendering

Traditional graphics represents an object as a triangle mesh. This represents a huge expansion relative to the object’s original CAD description which must be sent from network server or local disk to system memory, and then from CPU to GPU. Moreover, a polygonal tessellation is appropriate only for a limited range of viewing distances. Our research looks at rendering and processing procedural representations directly.

For parametric objects (described as the result of evaluating a function over a simple domain like the unit square), we can tessellate on the GPU so that data is amplified close to where it’s consumed for rendering. By tessellating adaptively given the current view, polygonal artifacts are avoided no matter how close the camera gets to an object. Our work also enables new forms of shape analysis, such as symbolic derivatives and robust CSG (Boolean operations on solid objects).

Shapes: Rendering and CSG using Parametric Descriptions. Each of these objects was created through CSG operations on procedural parametric surfaces. The largest object requires less than 12 kbytes of storage. Only the surface description is required; the normal function is computed automatically using a new efficient symbolic differentiation algorithm (see [symbol]). The parametric functions describing the surfaces are compiled to HLSL code. The GPU evaluates this code to compute position and normal values when the surface is tessellated dynamically. See [shapes].

For implicit objects (described as the solution to a system of equations, often low-order polynomials), we can compute ray intersections directly with the geometry without any polygonal approximation at all. We have developed efficient and robust GPU methods to compute these intersections. The implicit description also lends itself to antialiased rendering, since a display sample’s distance to the shape can be computed analytically.

Back to top

The Polynomial Catalog

Computer graphicists model shapes with polynomials. Simple linear polynomials generate flat polygons; higher order polynomials generate curved lines and surfaces. In order to develop algorithms for modeling and rendering such shapes we must have an intimate understanding of how the coefficients of the polynomials relate to the geometric shapes they generate. The answers to various geometric questions are expressed in terms of new polynomials built out of the coefficients of the original polynomial. The problem is that, for fairly simple shapes, these new polynomials can get incredibly complicated. For example, the condition that a cubic curve has a double point results in a test expression that is a 12^th order polynomial in the cubic’s coefficients, and this test expression has over 10000 terms! Fortunately there is a better way to deal with this problem. The research we are doing here builds on a graphical notation technique that was originally proposed by Sylvester and Clifford over 100 years ago. We are now translating many of the results of classical invariant theory into this notation. This has led to a much better visualization of the relation between a polynomial’s shape and its coefficients and has produced new algorithms for solving and factoring polynomials. Our ultimate goal is a new catalog of all the interesting algebraic relations between polynomial coefficients and their shape, describing curves and surfaces of orders up to 4 or 5 in a way that their processing can be accurately computed by parallel processors such as modern GPU’s.

Back to top

GPU Vector Art Rendering

Vector art is represented by collections of strokes and paths containing quadratic and cubic Bézier curves. Unlike conventional bitmaps, vector representations are resolution-independent and can be transformed arbitrarily without pixilation artifacts.

We have a developed a technique for rendering Bézier curves directly in terms of their mathematical equations using the Graphics Processing Unit. The idea is to render the triangles of each Bézier convex hull and apply a special pixel shader program to determine if a pixel is inside or outside a bounding curve. We then shade the pixel accordingly, including anti-aliasing if a pixel is near a boundary. Our approach is highly efficient allowing real-time translation, scaling, rotation, or arbitrary perspective transformation. These curves can also be animated in real-time with very little CPU intervention.

Rendering TrueType Fonts. We begin with a TrueType Font outline (left) consisting of a series of ordered control points. As a preprocess, we triangulate the control points preserving triangles that contain Bézier curves. These triangles are sent to the GPU and rendered using a special pixel shader program determines if a pixel is inside or outside the boundary. See [vector].

Applying an Arbitrary Projective Transform to our representation can be done in real-time without the sampling artifacts that would be apparent in a texture or bitmap representation.

Texture Mapping effects can be created by embedding the vector geometry in the tessellation of surface. This approach preserves the resolution-independent properties of our representation.

Back to top

GPU Rendering of Piecewise Algebraic Surfaces

An Algebraic Surfaces is the solution to a polynomial equation f(x,y,z)=0. By restricting such an equation to the volume within a bounding tetrahedra we get Bézier tetrahedra, a volumetric analog of Bézier curves and surfaces. We can put collections of these primitives together and obtain smooth piecewise objects. We render these surfaces directly in terms of their mathematical representations on the GPU by rendering the triangular faces of each tetrahedra and applying a special purpose pixel shader. At each pixel, our shader determines the pixel ray/surface intersection (if one exists), calculates the surface normal, and evaluates the lighting. This process is highly efficient and can achieve real-time frame rates without the faceting artifacts that appear in conventional polygonal object rendering.

Basic Curved Primitives can be represented as collections of Bézier tetrahedra and rendered directly on the GPU using our approach. See [tetra].

Dynamic Topological Change is easily achieved by varying the underlying algebraic equations over time. Such effects are incredibly difficult to achieve with traditional mesh based modeling.

Back to top

Approximating Subdivision Surfaces for Hardware Tessellation

Subdivision surfaces have become a standard tool for modeling objects in film and video games. One of the reasons for the success of subdivisions surfaces is their ability to represented irregular shapes. In order to accelerate the rendering of high order surfaces on the GPU, a new programmable tessellator unit has been proposed for future graphics chips – an early form of this functionality has already shipped on Xbox 360. The tessellator unit is ideally suited for rendering polynomial patches such as a bicubic tensor product Bézier patch.

Due to the irregular nature of a subdivision control mesh, the limit surface contains an infinite number of bicubic patches. In order allow for the efficient rendering of this popular modeling primitive on tessellator hardware, we have devised an approximation to the “extraordinary patches” that is visually nearly identical to the corresponding subdivision surface. Our approximation uses a bicubic geometry patch, and a pair of lower order tangent patches that define a continuous normal field. The advantage of this representation is that it can easily take advantage of tessellation hardware to accelerate the rendering of objects modeled as subdivision surfaces.

Approximate Subdivision Surfaces are compared to the ‘true’ subdivision surface in this figure. In the first column, we show the connectivity of the patches defined by the control mesh; blue patches have two or more extraordinary vertices, green have one extraordinary vertex, and grey are regular (bicubic) patches. In the second column, only the approximating geometry patches are shown – note the visible discontinuities between extraordinary patches. In the third column, we show the geometry patches combined with the normal field defined by the pair of tangent patches. Finally in the fourth column, we show he original subdivision surface. See [acc].

Back to top

Efficient Processing of Sampled Geometric Surfaces and Signals

Not all content can be described procedurally – it’s often useful to sample and tabulate data. Regular grids are especially attractive because they exploit the texture mapping capability of graphics hardware and because signal processing on this simple structure is well understood. Texture maps also decouple sampling of the object’s shape from the associated signal, such as how its color or normal varies. The graphics group is exploring parameterization techniques to represent surface signals as texture maps that are as small as possible. We have investigated a diverse set of signals allowing many shading effects, including fur, hatching, and geometric detail with precomputed shading effects. We can even represent the geometry itself as a 2D image, called a geometry image.

Lapped Textures use a Poisson-like surface parameterization metric to align a user-specified surface direction field with the axes of the texture domain. See [lapped].

Texture Mapping Progressive Meshes shows that all meshes in a progressive mesh sequence can be made to share a common texture parameterization, and introduces a texture-stretch metric to minimize undersampling in the resulting parameterization. See [tmpm].

Signal-Specialization Parameterization extends the parameterization stretch metric and optimization algorithm to create a texture atlas optimized to a particular signal, thereby allowing a more faithful resampled approximation for the same texture map size. See [ssp][ssplinear].

Exact and Approximate Surface Geodesics are an important component for improving the quality of parameterized surface charts, both in terms of their boundaries and their interior distortion. See [geodesics].

Isocharts combine ideas from signal-specialized stretch with recent techniques in nonlinear dimension reduction (isomap) to automatically produce compact texture atlases for arbitrary meshes. See [isocharts].

Spherical Parameterization applies many of these parameterization ideas to the special but important case of spheres and meshes of spherical topology. See [sphereparam][csp][shapecompr][spheremap].

Geometry Images replace irregular triangle meshes with a completely regular structure -- a simple 2D array of quantized points. Surface signals like normals and colors are stored in similar 2D arrays using the same implicit surface parameterization — texture coordinates are absent. Geometry images can be encoded using traditional image compression algorithms, such as wavelet-based coders. See [gim][mcgim][sgim].

Geometry Clipmaps cache the terrain in a set of nested regular grids centered about the viewer. This simple framework provides visual continuity, uniform frame rate, complexity throttling, and graceful degradation. Moreover it allows two new exciting real-time functionalities: decompression and synthesis. Our main dataset is a 40GB height map of the United States. A compressed image pyramid reduces the size by a remarkable factor of 100, so that it fits entirely in memory. This compressed data also contributes normal maps for shading. As the viewer approaches the surface, we synthesize grid levels finer than the stored terrain using fractal noise displacement. Decompression, synthesis, and normal-map computations are incremental, thereby allowing interactive flight at 60 frames/sec. See [geomclipmap][gpugcm].

Random-Access GPU Data Structures

Perfect Spatial Hashing packs sparse data into a compact table while retaining efficient random access. Because our hash function makes a single reference to a small offset table, queries always involve exactly two memory accesses and are thus ideally suited for parallel SIMD evaluation on graphics hardware. Applications include vector images, texture sprites, alpha channel compression, 3D-parameterized textures, 3D painting, simulation, and collision detection. See [perfecthash].

Back to top

Texture Synthesis

The idea of procedural and sampled representations can also be combined; texture synthesis is an example. The idea is to record how the signal varies locally via a small 2D example and automatically synthesize a similar version over a larger 2D area or a 3D surface. Previous approaches grow the texture by successively inserting small patches: an inherently slow and serial process. Our work has developed fast, parallel solutions.

Parallel controllable texture synthesis operates in real-time on a GPU. Texture variation is achieved by multiresolution jittering of exemplar coordinates. Combined with the local support of parallel synthesis, the jitter enables intuitive user controls including multiscale randomness, spatial modulation over both exemplar and output, feature drag-and-drop, and periodicity constraints. We also introduce synthesis magnification, a fast method for amplifying coarse synthesis results to higher resolution. See [paratexsyn].

Appearance-space texture synthesis shows that texture synthesis quality is greatly improved if pointwise colors are replaced by appearance vectors that incorporate nonlocal information such as feature and radiance-transfer data. We perform dimensionality reduction on these vectors prior to synthesis, to create a new appearance-space exemplar. Synthesis in this information-rich space lets us reduce runtime neighborhood vectors from 5x5 grids to just 4 locations. We introduce novel techniques for coherent anisometric synthesis, surface texture synthesis directly in an ordinary atlas, and texture advection. Remarkably, we achieve all these functionalities in real-time, or 3 to 4 orders of magnitude faster than prior work. See [apptexsyn].

Surface tangent vector fields are an essential ingredient in controlling surface appearance for applications ranging from anisotropic shading to texture synthesis and non-photorealistic rendering. We present a simple framework to efficiently create smooth tangent vector fields that follow constraints interactively sketched by a user. See [vfdesign].

Back to top

Surface Reconstruction

Often, detailed models are best acquired by scanning physical objects, for instance using laser range scanners. Converting the 3D points into useful surface geometry is referred to as surface reconstruction. See [thesis][recon][psrecon].

Poisson surface reconstruction considers all the oriented points at once, without resorting to heuristic spatial partitioning or blending, and is therefore highly resilient to data noise. Our Poisson approach allows a hierarchy of locally supported basis functions, and therefore the solution reduces to a well conditioned sparse linear system. See [poissonrecon].

Multilevel streaming for out-of-core surface reconstruction allows the reconstruction of huge datasets, far too large to fit into memory. We realize a cascading multigrid algorithm as a single sweep across the data, by simultaneously advancing through the multiple data streams associated with different levels of a sparse octree. See [mlstream].

Displaced Subdivision Surfaces represent a detailed surface model as a scalar-valued displacement over a smooth domain surface. The representation defines both the domain surface and the displacement function using a unified subdivision framework, allowing for simple and efficient evaluation of analytic surface properties. The encoding of fine detail as a scalar function makes the representation extremely compact. See [dss].

Back to top