All-frequency relighting of glossy objects
We present a technique for interactive rendering of glossy objects in complex and dynamic lighting environments that captures interreflections and all-frequency shadows. Our system is based on precomputed radiance transfer and separable BRDF approximation. We factor glossy BRDFs using a separable decomposition and keep only a few low-order approximation terms, each consisting of a purely view-dependent and a purely light-dependent component. In the precomputation step, for every vertex, we sample its visibility and compute a direct illumination transport vector corresponding to each BRDF term. We use modern graphics hardware to accelerate this step and further compress the data using a nonlinear wavelet approximation. The direct illumination pass is followed by one or more interreflection passes, each of which gathers compressed transport vectors from the previous pass to produce global illumination transport vectors. To render at run time, we dynamically sample the lighting to produce a light vector, also represented in a wavelet basis. We compute the inner product of the light vector with the precomputed transport vectors, and the results are further combined with the BRDF view-dependent components to produce vertex colors. We describe acceleration of the rendering algorithm using programmable graphics hardware and discuss the limitations and trade-offs imposed by the hardware.

title: All-Frequency Relighting of Non-Diffuse Objects using Separable BRDF Approximation
abstract: This paper presents a technique, based on pre-computed light transport and separable BRDF approximation, for interactive rendering of non-diffuse objects under all-frequency environment illumination. Existing techniques using spherical harmonics to represent environment maps and transport functions are limited to low-frequency light transport effects. Non-linear wavelet lighting approximation is able to capture all-frequency illumination and shadows for geometry relighting, but interactive rendering is currently limited to diffuse objects. Our work extends the wavelet-based approach to relighting of non-diffuse objects. We factorize the BRDF using separable decomposition and keep only a few low-order approximation terms, each consisting of a 2D light map paired with a 2D view map. We then pre-compute light transport matrices corresponding to each BRDF light map, and compress the data with a non-linear wavelet approximation. We use modern graphics hardware to accelerate precomputation. At run-time, a sparse light vector is multiplied by the sparse transport matrix at each vertex, and the results are further combined with texture lookups of the view direction into the BRDF view maps to produce view-dependent color. Using our technique, we demonstrate rendering of objects with several non-diffuse BRDFs under all-frequency, dynamic environment lighting at interactive rates.

title: Efficient reconstruction of indoor scenes with color
abstract: We present an efficient and general approach to computing and integrating 3D distance fields directly from multiple range images. We compute normal and confidence values directly from a 2D range image. We then approximate 3D Euclidean distance by correcting the line-of-sight distance. To integrate multiple scans, we efficiently transform voxels of the target distance field to each scan's local coordinate system, then update voxels with computed distance and confidence values. Finally, we extract an iso-surface from the weighted distance field using the marching cubes algorithm. We extend the same idea to the assignment of weighted colors or texture coordinates to the reconstructed model. Experiments show that our approach is fast, has reasonable storage requirements, and can produce high-quality surfaces from multiple range scans.

title: All-frequency interactive relighting of translucent objects with single and multiple scattering
abstract: We present a technique, based on precomputed light transport, for interactive rendering of translucent objects under all-frequency environment maps. We consider the complete BSSRDF model proposed by Jensen et al. [2001]. which includes both single and diffuse multiple scattering components. The challenge is how to efficiently precompute all-frequency light transport functions due to subsurface scattering. We apply the two-pass hierarchical technique by Jensen et al. [2002] in the space of non-linearly approximated transport vectors, which allows us to efficiently evaluate transport vectors due to diffuse multiple scattering. We then include an approximated single scattering term in the precomputation, which previous interactive systems have ignored. For an isotropic phase function, this approximation produces a diffuse transport vector per vertex, and is combined with the multiple scattering component. For a general phase function, we introduce a technique from BRDF rendering to factor the phase function using a separable decomposition to allow for view-dependent rendering. We show that our rendering results qualitatively match the appearance of translucent objects, achieving a high level of realism at interactive rates.

title: Real-time editing and relighting of homogeneous translucent materials
abstract: Existing techniques for fast, high-quality rendering of translucent materials often fix BSSRDF parameters at precomputation time. We present a novel method for accurate rendering and relighting of translucent materials that also enables real-time editing and manipulation of homogeneous diffuse BSSRDFs. We first apply PCA analysis on diffuse multiple scattering to derive a compact basis set, consisting of only twelve 1D functions. We discovered that this small basis set is accurate enough to approximate a general diffuse scattering profile. For each basis, we then precompute light transport data representing the translucent transfer from a set of local illumination samples to each rendered vertex. This local transfer model allows our system to integrate a variety of lighting models in a single framework, including environment lighting, local area lights, and point lights. To reduce the PRT data size, we compress both the illumination and spatial dimensions using efficient nonlinear wavelets. To edit material properties in real-time, a user-defined diffuse BSSRDF is dynamically projected onto our precomputed basis set, and is then multiplied with the translucent transfer information on the fly. Using our system, we demonstrate realistic, real-time translucent material editing and relighting effects under a variety of complex, dynamic lighting scenarios.

title: Interactive Time-Dependent Tone Mapping Using Programmable Graphics Hardware

title: Privacy-preserving genomic computation through program specialization
abstract: In this paper, we present a new approach to performing important classes of genomic computations (e.g., search for homologous genes) that makes a significant step towards privacy protection in this domain. Our approach leverages a key property of the human genome, namely that the vast majority of it is shared across humans (and hence public), and consequently relatively little of it is sensitive. Based on this observation, we propose a privacy-protection framework that partitions a genomic computation, distributing the part on sensitive data to the data provider and the part on the pubic data to the user of the data. Such a partition is achieved through program specialization that enables a biocomputing program to perform a concrete execution on public data and a symbolic execution on sensitive data. As a result, the program is simplified into an efficient query program that takes only sensitive genetic data as inputs. We prove the effectiveness of our techniques on a set of dynamic programming algorithms common in genomic computing. We develop a program transformation tool that automatically instruments a legacy program for specialization operations. We also demonstrate that our techniques can greatly facilitate secure multi-party computations on large biocomputing problems.

title: NP-Completeness Results for All-Shortest-Path Interval Routing
abstract: k-Interval Routing Scheme (k-IRS) is a compact routing method that allows up to k interval labels to be assigned to an arc. A fundamental problem is to characterize the networks that admit k-IRS. Many of the problems related to single-shortest-path k-IRS have already been shown to be NP-complete. For all-shortest-path k-IRS, the characterization problem remains open for k≥ 1. We investigate the time complexity of devising minimal-space all-shortest-path k-IRS and prove that it is NP-complete to decide whether a graph admits an all-shortest-path k-IRS, for every integer k≥ 3, as well as whether a graph admits an all-shortest-path k-strict IRS, for every integer k≥ 4. These are the first NP-completeness results for all-shortest-path k-IRS where k is a constant and the graph is unweighted. Moreover, the NP-completeness holds also for the linear case.

title: Real-time KD-tree construction on graphics hardware
abstract: We present an algorithm for constructing kd-trees on GPUs. This algorithm achieves real-time performance by exploiting the GPU's streaming architecture at all stages of kd-tree construction. Unlike previous parallel kd-tree algorithms, our method builds tree nodes completely in BFS (breadth-first search) order. We also develop a special strategy for large nodes at upper tree levels so as to further exploit the fine-grained parallelism of GPUs. For these nodes, we parallelize the computation over all geometric primitives instead of nodes at each level. Finally, in order to maintain kd-tree quality, we introduce novel schemes for fast evaluation of node split costs.
 As far as we know, ours is the first real-time kd-tree algorithm on the GPU. The kd-trees built by our algorithm are of comparable quality as those constructed by off-line CPU algorithms. In terms of speed, our algorithm is significantly faster than well-optimized single-core CPU algorithms and competitive with multi-core CPU algorithms. Our algorithm provides a general way for handling dynamic scenes on the GPU. We demonstrate the potential of our algorithm in applications involving dynamic scenes, including GPU ray tracing, interactive photon mapping, and point cloud modeling.

title: Recognizing Textual Relatedness with Predicate-Argument Structures
abstract: In this paper, we first compare several strategies to handle the newly proposed three-way Recognizing Textual Entailment (RTE) task. Then we define a new measurement for a pair of texts, called Textual Relatedness, which is a weaker concept than semantic similarity or paraphrase. We show that an alignment model based on the predicate-argument structures using this measurement can help an RTE system to recognize the Unknown cases at the first stage, and contribute to the improvement of the overall performance in the RTE task. In addition, several heterogeneous lexical resources are tested, and different contributions from them are observed.

title: On the Performance of Three Kinds of Channel Code Used in Turbo-BLAST
abstract: A MIMO system named Turbo-BLAST was introduced recently. We investigate the structure of Turbo- BLAST, and study its three kinds structures using different channel codes. Some necessary deductions and new structures are proposed: the decoding algorithm of trellis coded modulation (TCM) is modified to provide the detector with extrinsic information, and a new decoder structure for Turbo code is also given. Simulation results show that the structure using Turbo code can achieve better performance and faster convergence rate for high-order modulation. And the performance improvement of the structure using TCM is also obvious. Since TCM can bring high spectral efficiency, it would be useful to apply TCM in Turbo-BLAST.