Abstract

General purpose programming on the graphics processing units (GPGPU) has received a lot of attention in the parallel computing community as it promises to offer the highest performance per dollar. The GPUs have been used extensively on regular problems that can be easily parallelized. In this paper, we describe two implementations of List Ranking, a traditional irregular algorithm that is difficult to parallelize on such massively multi-threaded hardware. We first present an implementation of Wyllie's algorithm based on pointer jumping. This technique does not scale well to large lists due to the suboptimal work done. We then present a GPU-optimized, Recursive Helman-JaJa (RHJ) algorithm. Our RHJ implementation can rank a random list of 32 million elements in about a second and achieves a speedup of about 8-9 over a CPU implementation as well as a speedup of 3-4 over the best reported implementation on the Cell Broadband engine. We also discuss the practical issues relating to the implementation of irregular algorithms on massively multi-threaded architectures like that of the GPU. Regular or coalesced memory accesses pattern and balanced load are critical to achieve good performance on the GPU.

Abstract

The significant growth in computational power of modern Graphics Processing Units (GPUs) coupled with the advent of general purpose programming environments like NVIDIA's CUDA, has seen GPUs emerging as a very popular parallel computing platform. Till recently, there has not been a performance model for GPGPUs. The absence of such a model makes it difficult to definitively assess the suitability of the GPU for solving a particular problem and is a significant impediment to the mainstream adoption of GPUs as a massively parallel (super)computing platform. In this paper we present a performance prediction model for the CUDA GPGPU platform. This model encompasses the various facets of the GPU architecture like scheduling, memory hierarchy, and pipelining among others. We also perform experiments that demonstrate the effects of various memory access strategies. The proposed model can be used to analyze pseudo code for a CUDA kernel to obtain a performance estimate, in a way that is similar to performing asymptotic analysis. We illustrate the usage of our model and its accuracy with three case studies: matrix multiplication, list ranking, and histogram generation.

Abstract

Depth movies provide 2-D representations of a time-varying 3D scene. Multistream depth movies arise in many structure-capturing setups and have been used for image based rendering. They are bulky and carry redundant information. We propose a proxy-based compression scheme for multistream depth movies of a scene involving dynamic human actors. The input to our system is depth movies from different viewpoints and the calibration parameters to relate depths to 3D points. We use an articulated human model as a proxy to represent the common structure of the scene. The proxy is parametrized by various bone angles.

Abstract

Graph cuts has become a powerful and popular opti-mization tool for energies defined over an MRF and havefound applications in image segmentation, stereo vision,image restoration, etc. The maxflow/mincut algorithm tocompute graph-cuts is computationally heavy. The best-reported implementation of graph cuts takes over 100 mil-liseconds even on images of size640×480and cannot beused for real-time applications or when iterated applica-tions are needed. The commodity Graphics Processor Unit(GPU) has emerged as an economical and fast computationco-processor recently. In this paper, we present an imple-mentation of the push-relabel algorithm for graph cuts onthe GPU. We can perform over 60 graph cuts per secondon1024×1024images and over 150 graph cuts per secondon640×480images on an Nvidia 8800 GTX. The time foreach complete graph-cut is about 1 millisecond when only afew weights change from the previous graph, as on dynamicgraphs resulting from videos. The CUDA code with a well-defined interface can be downloaded for anyone’s use

Abstract

Capturing dynamic scenes in 3D using a suitable depth or structure recovery mechanism has become popular today for image based modelling, 3D telelconferencing, etc. The 2 1 2 D geometric structure and the aligned texture – together called a depth image – are captured by such setups. Time varying sequences of depth images are called depth movies. Depth movies of humans performing interesting actions are being captured using specialized setups today in different research labs. The data so captured is often streamed to another location for immersive viewing using standard depth-image rendering techniques. The depth maps are bulky and need innovative algorithms for efficient representation and compression. In this paper, we present a compression scheme that uses parametric proxy models for the underlying action. We use a generic articulated human model as the proxy and the various joint angles as its parameters for each time instant. The proxy model represents common prediction of the scene structure for that time instant. It can be projected to each view and the difference or residue between the depth due to the proxy and the original depth can be used to represent the scene. The residues compress better and can exploit temporal and spatial relationship between multiple depth movies. We show results on several synthetic actions to demonstrate the usefulness of the scheme

Abstract

Augmenting virtual objects between real objectsof a video poses a challenging problem, primarily because itnecessitates accurate knowledge of the scene’s depth. In thispaper, we propose an approach that generates an approximatedepth for every pixel in the vicinity of the virtual object, which weshow is enough to decide the ordering of objects in every image.We also draw a similarity between layered segmentation andaugmentation. We argue that augmentation only needs to knowwhich layers are in front of the object and which are behind it.Our algorithm makes effective use of object boundaries detectedin an image using image segmentation. The assumption thatthese boundaries correspond to depth discontinuities provides auseful simplification of the problem, sufficient to produce realisticresults. We use a combination of segmentation and featuredetection for sparse depth assignment. Results on challengingdata sets show the effectiveness of our approach

Abstract

Capture of dynamic events is an active research area to-day. Capturingthe212D geometric structure and photomet-ric appearance of dynamic scenesnds applications in 3Dtele-conferencing systems,3DTVetc.The captured ìn depth movies îcontain aligned sequences of depth maps and tex-tures and are often streamed to a distant location for immer-siveviewing. The depth maps are heavy and needed acient compression schemes.In this paper, we present a scheme to compress depth movies of human actors using a parametric proxy model for the under lying action.We use a generic articulated human model as the proxy and the various joint angles a sits parameters for reach time in stant to represent a common prediction of the scene structure. The difference or residue between the captured depth and the depth of the proxy represents the scene to exploits patial coherence. Dif-ferences in residues across time are used to exploit temporal coherence. In tra-frame code frames and difference-coded frames provider and om access and high compression.We show results on several synthetic and real actions to demon-strate the compression ratio and resulting quality using a depth-based rendering of the decoded scene

Abstract

Terrains can be rendered efficiently with rectangular 2D grid of heights. Terrain on spheres, on the other hand, can be rendered using Hierarchical Triangular Mesh (HTM) but the representation does not fit directly with 2D grid of heights. We present a unified representation of HTM and clip mapping using Hexagonal Geome-try Clipmaps. This provides one to one correspondence of vertices and heights, low and constant memory usage, less storage space requirements, no pole singularity, fast vertex look-ups, and large range of view distances. Hexagonal clip maps fit equilateral trian-gles of HTM and achieve uniform triangle count on the screen. We keep the clipmaps on the GPU for fast access from shaders and usevertex buffer objects for fast triangle rendering.

Abstract

Terrains are challenging geometric objects for real-timerendering and interactive manipulation. State-of-the-artterrain rendering systems use custom, multiresolution, rep-resentations like geometry clipmaps for fast rendering onthe GPU. In this paper, we present a system that exploitsthe power and flexibility of the modern GPUs to store, ren-der, and manipulate terrains with minimal CPU involve-ment. The central idea is to use a regular-grid represen-tation and fixed size blocks/tiles that change in resolution.The potentially visible portion of the terrain is cached atthe highest necessary resolution and is rendered from theGPU. The CPU sends a light geometry template which isexpanded by the Geometry Shader to the triangles, usingthe heights stored in the GPU Cache. The CPU performsa coarse culling of the tiles with the GPU performing fineculling. The GPU cache is updated continuously as theviewpoint changes. Our system enables the terrain to bemodified procedurally or edited interactively on the GPUwith no CPU involvement. The terrain can also interactwith a large number of external objects in real-time entirelywithin the GPU. We achieve a consistent rendering rate of100 frames per second with terrain modification and inter-actions as well as a triangle rate of upto 350 million persecond on an Nvidia 8800 GTX GPU for large terrains, witha CPU load below 10%.

Abstract

The GPUs pack high computation power and a restricted architecture into easily available hardware today. They are now used as computation co-processors and come with programming models that treat them as standard paral-lel architectures. We explore the problem of real time raycasting of large deformable models (over a million trian-gles) on large displays (a million pixels) on an off-the-shelf GPU in this paper. Ray casting is an inherently parallel and highly compute intensive operation. We build a GPU-efficient three-dimensional data structure for this purpose and a corresponding algorithm that uses it for fast ray cast-ing. We also present fast methods to build the data struc-ture on the SIMD GPUs, including a fast multi-split opera-tion. We achieve real-time ray-casting of a million triangle model onto a million pixels on current Nvidia GPUs using the CUDA model. Results are presented on the data struc-ture building and ray casting on a number of models. The ideas presented here are likely to extend to later models and architectures of the GPU as well as to other multi core ar-chitectures.