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

计算几何的目的是为几何性质的应用提供可证明的有效算法和数据结构。不幸的是，通常采用的研究最坏情况行为的态度，通过在理论研究和日益增长的实现和使用几何算法的社区之间建立差距，使该领域受到了损害。该项目将开发框架，更密切地模拟对实际数据具有实际重要性的算法的行为。要做到这一点，它将集中在光线拍摄，这是瓶颈操作的基本光线追踪技术，以产生逼真的图像在图形。射线射击还有许多其他的应用。从技术上讲，该项目将开发一个新的框架，用于在给定输入的任何基于分解或层次结构的数据结构上预测光线拍摄的“平均”（而不是最坏情况）性能。这将允许人们在给定数据上比较不同方法的预期性能，最终目标是能够预测操作的成本，例如以特定分辨率渲染场景，或优化数据结构的选择来存储场景，在实际的射线射击计算之前。它还将设计新颖的光线拍摄/光线跟踪算法，以减少数据集太大而无法适应main的I/ o复杂性。此外，它还将尝试扩展所提出的性能预测框架，以纳入I/ o复杂度，以覆盖输入大小的整个范围。最后，该项目将实现其算法，解决相应的鲁棒性问题，并研究预测框架在实际数据上的准确性。

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.