Ray Tracing on the GPU

Introduction

Ray tracing is used to render photorealistic images in computer graphics. We work on real time ray tracing of static, dynamic and deformable scenes composed of polygons as well as higher order surfaces. This has been made possible with the recent advances in GPU hardware and computing resources. We have developed various algorithms that perform real time ray tracing of various kinds of scenes by constructing efficient acceleration structures on the GPU as well as algorithms that work without constructing any explicit structure.

Projects involving Ray Tracing using CUDA

1. Parallel Divide and Conquer Ray Tracing

Divide and Conquer Ray Tracing is a recent technique in which ray tracing is performed without constructing any explicit acceleration structure. We have developed a parallel version of the algorithm that runs entirely on the GPU using efficient parallel primitives like sort and reduce. Our approach suits the GPU well, with a low memory footprint. Our implementation outperforms the serial CPU algorithm for both primary and secondary ray passes.

2. Hybrid Ray Tracing and Path Tracing of Bezier Surfaces Using A Mixed Hierarchy

We present a scheme for interactive ray tracing of Bezier bicubic patches using Newton iteration. We use a mixed hierarchy representation as the acceleration structure. This has a bounding volume hierarchy above the patches and a fixed depth subpatch tree below it. This helps reduce the number of ray-patch intersections that needs to be evaluated and provides good initialization for the iterative step, keeping the memory requirements low. We use Newton iteration on the generated list of ray patch intersections in parallel. Our method can exploit the cores of the CPU and the GPU with OpenMP on the CPU and CUDA on the GPU by sharing work between them according to their relative speeds. A data parallel framework is used with a list of rays, which is transformed to a list of ray-patch intersections by traversal and then to intersections and a list of secondary rays by root finding. Shadow and reflection rays can be handled exactly in the same manner as a result. We also show how our method extends easily to generate soft shadows using area light sources and path tracing by tracing a large number of rays per pixel.

3. Ray Tracing Dynamic Scenes on the GPU

We present fast ray tracing of dynamic scenes with primary and shadow rays. We present a GPU- friendly strategy to bring coherency to shadow rays, based on previous work on grids as acceleration structures. We introduce indirect mapping of threads to rays to improve the performan ce of ray tracing on the GPU for the traversal and intersection steps. We also construct a light frustum in a sph erical space for shadow rays. A grid structure is constructed each frame for the light frustum and traversed coh erently. This involves careful mapping of the primary ray information to the light space and balancing the work load of th e threads. Using the finegrained parallelism of GPU, we reorder the shadow rays to make them coherent a nd process multiple thread blocks to each cell to balance the work load. Spherical mapping is key to handling ligh t sources placed anywhere in the scene by reducing the triangle count and improving performance in shad ow checking. In addition it also allows us to introduce spotlights in raytracing. In practice, we attain interactive perform ance for moderately large models which change dynamically in the scene.

4. Ray Tracing Implicit Surfaces in Real-Time

We present a ray-tracing procedure to render general implicit surfaces efficiently on the GPU. Though only the fourth or lower order surfaces can be rendered using analytical roots, our adaptive marching points algorithm can ray trace arbitrary implicit surfaces without multiple roots, by sampling the ray at selected points till a root is found. Adapting the sampling step size based on a proximity measure and a horizon measure delivers high speed. The sign test can handle any surface without multiple roots. The Taylor test that uses ideas from interval analysis can ray trace many surfaces with complex roots. Overall, a simple algorithm that fits the SIMD architecture of the GPU results in high performance.

5. Ray Casting Deformable Models on CUDA

We explore the problem of real time ray casting of large deformable models (over a million triangles) on large displays (a million pixels) on an off-the-shelf GPU. We build a GPU-efficient three-dimensional data structure for this purpose and a corresponding algorithm that uses it for fast ray casting. We also present fast methods to build the data structure on the SIMD GPUs, including a fast multi-split operation. We achieve real-time ray-casting of a million triangle model onto a million pixels on current generation hardware.

Related Publications

• Srinath Ravichandran and P. J. Narayanan - Parallel Divide and Conquer Ray Tracing In SIGGRAPH ASIA 2013 Technical Briefs, 19-22nd Nov. 2013, Hong Kong. [PDF]

• Rohit Nigam, P J Narayanan - Hybrid Ray Tracing and Path Tracing of Bezier Surfaces Using A Mixed Hierarchy Proceedings of the 8th Indian Conference on Vision, Graphics and Image Processing, 16-19 Dec. 2012, Bombay, India. [PDF]
  

• Sashidhar Guntury and P.J. Narayanan - Raytracing Dynamic Scenes on the GPU Using Grids IEEE Transactions on Visualization and Computer Graphics, Vol.18, No.1 pp. 5-16, 2012. [PDF]

• Sashidhar Guntury and P. J. Narayanan - Ray Tracing Dynamic Scenes with Shadows on the GPU Proceedings of Eurographics Symposium on Parallel Graphics and Visualization (EGPGV'10), pp.27-34, 2-3 May, 2010, Norrkoping, Sweden. [PDF]

• Jag Mohan Singh and P. J. Narayanan - Real-Time Ray Tracing of Implicit Surfaces on the GPU IEEE Transactions Visualization and Computer Graphics, Vol. 16(2), pp. 261-272 (2010). [PDF]

• Suryakant Patidar and P. J. Narayanan - Ray Casting Deformable Models In: ACM ICVGIP 2008. [PDF]

Associated People

• Srinath Ravichandran
• Sashidhar Guntury
• Suryakant Patidar
• Rohit Nigam
• Jag Mohan Singh
• Prof. P.J. Narayanan

Scene Text Understanding

Motivation

Recognizing scene text is a challenging problem, even more so than the recognition of scanned documents. Given the rapid growth of camera-based applications readily available on mobile phones, understanding scene text is more important than ever. One could, for instance, foresee an application to answer questions such as, “What does this sign say?”. This is related to the problem of Optical Character Recognition (OCR), which has a long history in the computer vision community. However, the success of OCR systems is largely restricted to text from scanned documents. Scene text exhibits a large variability in appearances, and can prove to be challenging even for the state-of-the-art OCR methods. Many scene understanding methods recognize objects and regions like roads, trees, sky in the image successfully, but tend to ignore the text on the sign board. Our goal is to fill this gap in understanding the scene.

Highlights

• Binarization as a labelling problem (see our ICDAR'11 paper)
• Both open and closed vocabulary word recognition (see our CVPR'12 paper and BMVC'12 paper)
• Use of both top-down (lexicons) and bottom-up cues (character detection)
• Holistic recognition approach of lexicon-driven scene text recognition (see our ICDAR'13 paper)
• Applications in image retrieval (see our ICCV'13 paper)
• Word recognition for large lexicions and cropped word image retrieval (see our ACCV'14 paper)

Code

Generating exemplars (based on our ICDAR'13 paper) README

Coming Soon:

• Scene Text Binarization
• Scene Character Recognition

Datasets

Lexicons (ACCV '14)

IIIT 5K-word

SVT-CHAR (9.9MB)  README

IIIT Scene Text Retrieval (IIIT STR)

Video Scene Text Retrieval Datasets (Sports-10K and TV series-1M)

Related Publications

• Anand Mishra, Karteek Alahari and C. V. Jawahar - Enhancing energy minimization framework for scene text recognition with top-down cues - Computer Vision and Image Understanding (CVIU 2016), volume 145, pages 30–42, 2016. [PDF]

• Udit Roy, Anand Mishra, Karteek Alahari, C.V. Jawahar - Scene Text Recognition and Retrieval for Large Lexicons Proceedings of the 12th Asian Conference on Computer Vision,01-05 Nov 2014, Singapore. [PDF] [Abstract] [Poster] [Lexicons] [bibtex]
  

• Anand Mishra, Karteek Alahari and C V Jawahar - Image Retrieval using Textual Cues Proceedings of International Conference on Computer Vision, 1-8th Dec.2013, Sydney, Australia. [Pdf] [Abstract] [Project page][bibtex]

• Vibhor Goel, Anand Mishra, Karteek Alahari, C V Jawahar - Whole is Greater than Sum of Parts: Recognizing Scene Text Words Proceedings of the 12th International Conference on Document Analysis and Recognition, 25-28 Aug. 2013, Washington DC, USA. [PDF] [Abstract] [bibtex]

• Anand Mishra, Karteek Alahari and C V Jawahar - Scene Text Recognition using Higher Order Language Priors Proceedings of British Machine Vision Conference, 3-7 Sep. 2012, Guildford, UK. [PDF] [Abstract] [Slides] [bibtex]

• Anand Mishra, Karteek Alahari and C V Jawahar - Top-down and Bottom-up Cues for Scene Text Recognition Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 16-21 June 2012, pp. 2287-2294, Providence RI, USA. [PDF] [Abstract] [Poster] [bibtex]

• Anand Mishra, Karteek Alahari and C.V. Jawahar - An MRF Model for Binarization of Natural Scene Text Proceedings of 11th International Conference on Document Analysis and Recognition (ICDAR 2011),18-21 September, 2011, Beijing, China. [PDF] [Abstract] [Slides] [bibtex]

People

• Udit Roy
• Anand Mishra
• Karteek Alahari
• C. V. Jawahar

Acknowledgements

Anand Mishra is partly supported by MSR India PhD Fellowship 2012. 

Copyright Notice

The documents contained in these directories are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright.

Computational Displays

Introduction

Displays have seen many improvements over the years. With advancements in pixel resolution, color gamut, vertical refresh rates and power consumption, displays today have become more personal and accessible devices for sharing and feeding information. Advancements in computer human interaction have provided novel interactions with current displays. Touch panels are now common and provide better interaction with the cyberworld shown on a device. Displays today have many shortcomings still. These include rectangular shape, low color gamut, low dynamic range, lack of focus and context in a scene, lack of 3D viewing, etc. Efforts are being made to create better and more natural displays than 2D flat rectangular screens we see today. Much research has gone into designing better displays including 3D displays, focus and context displays, HDR displays, etc. Such displays work at the device level and use physical (mechanical, metallurgical, chemical, etc) means to create better displays. Such approaches prove expensive and are hard to scale to acceptable standards of color, refresh rate, etc. of current displays. An alternate to this is to use computation to enhance displays. We propose Computational Displays, which employ computation to economically alleviate some of the shortcomings of availabe displays. Specifically we give solutions to the walk-around 3D viewing, focus+context and color resolution problems The systems work on top of existing display methodologies and are independent of any specific display technology. This makes our systems scalable to any display method and enhances the same using computation. In conclusion, we argue that such computation/algorithms should be built into the displays themselves to enhance the visual experience.

View Dependent, Multi-Planar, Walkaround 3D Displays

Displays have remained flat for most part since their inception. In this work we focus on non-planar displays made out of planar facets. We focus on displaying 3D scenes in perspective correct manner to such displays. We propose an accurate rendering mechanism using GPU shaders that produces correct color and depth map on each facet, ensuring consistency across facet boundaries. We compare our results with various previous methods such as CAVE and Projective Texture Mapping and conclude that our method is artifact free and superior in terms of visual quality - a requirement for visualization applications. We also provide a scalable GPU culling algorithm to scale our rendering scheme to any display shape, consisting of over a thousand facets. The pipeline proposed uses commodity GPUs to implement the system and can handle any type of scene, even mesh deformations as shown in the video.

Distributed Massive Model Rendering

Graphics models are getting increasingly bulkier with detailed geometry, textures, normal maps, etc. There is a lot of interest to model and navigate through detailed models of large monuments. Many monuments of interest have both rich detail and large spatial extent. Rendering them for navigation on a single workstation is practically impossible, even given the power of today's CPUs and GPUs. Many models may not fit in the GPU memory, the CPU memory, or even the secondary storage of the CPU. Distributed rendering using a cluster of workstations is the only way to navigate through such models. We present a design of a Distributed rendering system intended for massive models. Our design has a server that holds the skeleton of the whole model, namely, its scenegraph with actual geometry replaced by bounding boxes at all levels. The server divides the screen space among a number of clients and sends them a list of objects they need to render using a frustum culling step. The clients use 2 GPUs with one devoted to visibility culling and the other to rendering. Frustum culling at the server, visibility culling on one GPU, and rendering on the second GPU form the stages of our distributed rendering pipeline. We describe the design and implementation of our system and demonstrated the results of rendering relatively large models using different clusters of clients in this work. The demonstration video shows the interactive rendering of huge scenes of Coal Powerplant (approx. ~96M triangles) and Fatehpur Sikri (~172M triangles) models on a 4-client setup.

Increasing Intensity Resolution on Single Displays

Displays have seen many improvements in spatial resolutions and vertical refresh, to provide a smoother visual experience. Color intensity resolution, however, has not changed much. Most displays are still limited to 8-bits per channel. Simultaneously, much work has gone into capturing high dynamic range images. Mapping these directly to current displays loses information that may be critical to many applications. We present a way to enhance intensity resolution of a given display by mixing intensities over spatial or temporal domains. Our system sacrifices high vertical refresh and spatial resolution in order to gain intensity resolution. We present three ways to mix intensities: spatially, temporally and spatio-temporally. The systems produce in-between-intensities not present on the base display, which are clearly distinguishable by the naked eye. We evaluate our systems using both a camera and human subjects, evaluating if our system scales the intensity resolution and also ensuring the newly generated intensities follow the display model.

View Dependent Parametric/Implicit Displays

This work extends the view dependent displays to non-planar parametric shapes. In this the display surface is not defined using planar facets, but by a set of parametric or implicit equations. To render perspective correct 3D on to such a display requires non-linear rasterization. No graphics pipeline at the moment supports this. We approximate it using the tessellation hardware provided by the new Shader Model 5.0 / DirectX 11 GPUs. We break large triangles on the fly to a user defined error threshold using the tessellation hardware. The resulting vertices are then moved using per-vertex raycasting to correct their positions in the observer's eye. This results in correct perspective view in the eye of a user whose head is tracked. The method is an approximate rendering scheme to any parametric display, however does not interpolate pixels as opposed to Projective Texture Mapping. The rendering speed is orders faster than approximating the surface using planes because of single pass rendering and the use of tessellation hardware. 

Garuda: A Scalable, Tiled Display Wall using Commodity PCs

Garuda is a client-server based display wall system employing distributed rendering to render massive 3D environments at interactive framerates to a tiled display. The system is designed and built using commodity hardware. Features such as client caching and use of server-push philosophy in conjunction with UDP multicast help the system scale to very large tiled configurations. The system uses a novel culling algorithm to find what part of the scene is in which of the tiles. This is a scalable algorithm both in terms of scene complexity and number of tiles. The system is built as a library intercept mechanism over the Open Scene Graph (OSG) API. This ensures that any OSG application can be ported to Garuda without the need of modifying, recompiling or relinking the code. The OSG executable directly runs on the tiled display using this. Rendering capabilities increase with number of tiles as distributed rendering is employed. No machine in Garuda, server or clients, renders the entire environment. Culling is performed at the server and part of the scene graph are sent to clients over standard Ethernet. Clients cache the geometry and evict it based on LRU, this exploits the temporal coherence in the scene. Rendering happens at client end with the server used to to synchronize the buffer swap.

Related Publications

• Pawan Harish, Parikshit Sakurikar, P J Narayanan - Increasing Instensity Resolution on a Single Display using Spatio-Temporal Mixing Proceedings of the 8th Indian Conference on Vision, Graphics and Image Processing, 16-19 Dec. 2012, Bombay, India. [PDF]

• Revanth N R, P J Narayanan - Distributed Massive Model Rendering Proceedings of the 8th Indian Conference on Vision, Graphics and Image Processing, 16-19 Dec. 2012, Bombay, India. [PDF]

• Pawan Harish and P. J. Narayanan - Designing Perspectively-Correct Multiplanar Display IEEE Transactions on Visualization and Computer Graphics, Vol.99, 2012. [PDF]

• Nirnimesh, Pawan Harish and P. J. Narayanan - Culling an Object Hierarchy to a Frustum Hierarchy, 5th Indian Conference on Computer Vision, Graphics and Image Processing, Madurai, India, LNCL 4338 pp.252-263,2006. [PDF]
  

• Pawan Harish, Parikshit Sakurikar, P. J. Narayanan - Spatio-Temporal Mixing to Increase Intensity Resolution on a Single Display (Poster) In CVPR Workshop on Computational Cameras and Displays 2012. [PDF]
• Pawan Harish, P. J. Narayanan - View Dependent Rendering to Simple Parametric Display Surfaces (Short Paper)" In JVRC of EuroVR-EGVE, 2011. [PDF]
• Pawan Harish, P. J. Narayanan - A View Dependent, Polyhedral 3D Display, in ACM SIGGRAPH Virtual Reality Continuum and its Applications in Industry 2009. [PDF]
• Nirnimesh, Pawan Harish, P. J. Narayanan - Garuda: A Scalable Tiled Display Wall using Commodity PCs, In IEEE TVCG, 2007. [PDF]

 Related Videos

Multiplanar Displays.

Parametric Displays.

Polyhedral Displays.

Garuda Display Wall.

Associated People

• Revanth N R
• Parikshit Sakurikar
• Pawan Harish
• Nirnimesh
• Prof. P. J. Narayanan

Image Annotation

 Motivation

In many real-life scenarios, an object can be categorized into multiple categories. E.g., a newspaper column can be tagged as "political", "election", "democracy"; an image may contain "tiger", "grass", "river"; and so on. These are instances of multi-label classification, which deals with the task of associating multiple labels with single data. It is a difficult problem becauses one needs to consider the intricate correlations that exist amont different labels.

Automatic image annotation is a multi-label classification problem that aims at associating a set of textual with an image that describe its semantics. It has potential applications in image retrieval, image description, etc. Recent outburst of multimedia content on the Internet and as personal collections has raised the demand for auto-annotation methods; due to which this has become an active area of research.

A Modified KNN for Image Annotation [1]

• For a given image, the labels are usually predicted from an annotation vocabulary of few hundred labels. Because of the large vocabulary, there is high variance in label frequency ("class-imbalance"). Moreover, due to limitations of manual annotation, a significant number of available images are not annotated with all the relevant labels ("weak-labelling"). These two issues affect the performance of many existing image annotation models.
• In this work, we proposed 2PKNN, a two-step variant of the classical K-nearest neighbour algorithm, that triest to address these two issues. We also proposed a metric learning framework over 2PKNN for learning better distances.

Generating Image Description [2]

Problem

Results

* A black ferrari is parked in front of a green tree.	* An adult hound is laying on an orange couch.	* A blond woman is posing with an elvis impersonator.	* A small sailboat is passing near a yellow buoy.
* A sporty car is parked on a concrete driveway.	* A sweet cat is curling on a pink blanket.	* An orange fixture is hanging in a messy kitchen.	* An ocean boat is travelling in a narrow water.

• In this work, we proposed a method to describe an image in a sentence.
• It is based on annotating an image with linguistically motivated phrases.
• These phrases are combined to generate image description.

Related Publications

• Yashaswi Varma and C V Jawahar - Image Annotation using Metric Learning in Semantic Neighbourhoods Proceedings of 12th European Conference on Computer Vision, 7-13 Oct. 2012, Print ISBN 978-3-642-33711--6, Vol. ECCV 2012, Part-III, LNCS 7574, pp. 114-128, Firenze, Italy. [PDF]
  

• Ankush Gupta, Yashaswi Verma and C. V. Jawahar - Choosing Linguistics Over Vision to Describe Images, In AAAI, 2012. [paper] [presentation] [poster]

People

Yashaswi Verma
C. V. Jawahar