Complexity of practical algorithms for Volume Rendering and Computer Graphics

Lead Research Organisation: Swansea University
Department Name: Computer Science

Abstract

3D Computer Graphics is a quite new research area when compared to traditional disciplines, and has a wide scope of application, ranging from games and movie effects to scientific visualisation. A crucial issue in computer graphics is that it is tremendously computation intensive, especially at the rendering stage. Once the 3D scene has been modelled in an appropriate way (i.e., voxels, triangular mesh, implicit surfaces, etc...), rendering must then be performed. Rendering involves the crucial operation of being able to determine the visibility between any pair of point within the scene, and the current best computer graphics algorithms can only solve this by performing Log(n) steps on average, where n is the number of elements within the scene (can be as large as a billion).The new algorithm to be developed in this project aims to make the number of required steps independent (i.e., constant) from the number of elements of the 3D world. This will allow, for example, to generate movie pictures quicker than what is currently possible. A speed-up factor between 5 and 10 is expected.

Publications

10 25 50
publication icon
B Mora (2008) On the Lower Complexity of Coherent Renderings

publication icon
Kammaje R (2007) A Study of Restricted BSP Trees for Ray Tracing

publication icon
Lu A (2007) Volume illustration using wang cubes in ACM Transactions on Graphics

publication icon
Mora B (2011) Naive ray-tracing A divide-and-conquer approach in ACM Transactions on Graphics

publication icon
Mora B (2009) Visualization and Computer Graphics on Isotropically Emissive Volumetric Displays in IEEE Transactions on Visualization and Computer Graphics

 
Title DIRECT RAY TRACING OF 3D SCENES 
Description Determining intersections between rays and triangles is at the heart of most Computer Generated 3D images. The present disclosure describes a new method for determining the intersections between a set of rays and a set of triangles. The method is unique as it processes arbitrary rays and arbitrary primitives, and provides the lower complexity typical to ray- tracing algorithms without making use of a spatial subdivision data structure which would require additional memory storage. Such low memory usage is particularly beneficial to all computer systems creating 3D images where the available on-board memory is limited and critical, and must be minimized. Also, a pivot-based streaming novelty allows minimizing conditional branching inherent to normal ray- tracing techniques by handling large streams of rays. In most cases, our method displays much faster times for solving similar intersection problems than preceding state of the art methods on similar systems. 
IP Reference WO2011035800 
Protection Patent granted
Year Protection Granted 2011
Licensed No
Impact At this stage, we can fairly say that this technique can be extended to solve many more problems. We believe that, provided funding is made available, application to critical areas having a huge impact on daily life will be demonstrated.
 
Title DirectTrace driver 
Description A driver and API to accelerate ray-tracing without spatial subdivision data structures 
Type Of Technology Software 
Year Produced 2011 
Impact So far it has been more of a proof of concepts than a commercial software. Researchers have used it to compare they results to our own work and develop their own improvements. This has motivated further work in the area. Many students have also used it to implement realistic images without having to code ray tracing themselves. 
URL http://directtrace.org/