ITR: Geometric Algorithms and Analytical Models: the Case of Ray Shooting

Polytechnic University Of New York, Brooklyn NY

Investigators

Abstract

The purpose of Computational Geometry is to provide provably efficient algorithms and data structures for applications of a geometric nature. Unfortunately, the commonly adopted attitude of studying worst-case behavior has disserved the field by building a gap between the theoretical research and the growing community that implements and uses geometric algorithms. This project will develop frameworks that model more closely the behavior of algorithms of practical importance on actual data. To do this, it will concentrate on ray shooting, which is the bottleneck operation in the fundamental ray tracing technique for producing photo-realistic images in graphics. Ray shooting also has numerous other applications. Technically, the project will develop a new framework for predicting the "average" (rather than worst-case) performance of ray shooting on any decomposition- or hierarchy-based data structure on a given input. This would allow one to compare the expected performance of different approaches on a given data, with the eventual aim of being able to predict the cost of an operation, such as rendering a scene at a certain resolution, or optimizing the choice of a data structure to store a scene, prior to actual ray-shooting computation. It will also devise novel ray shooting/ray tracing algorithms that reduce the I/O-complexity for datasets too large to fit in main. In addition, It will attempt to extend the proposed performance-predicting framework to incorporate I/O-complexity as well, to cover the entire spectrum of the input sizes. Finally, the project will implement its algorithms, address the corresponding robustness issues, and investigate the accuracy of the predictive framework on practical data.