Szirmay-Kalos László, Márton Gábor
Department of Control Engineering and Information Technology, Technical University of Budapest,
Budapest, Muegyetem rkp. 11, H-1111, HUNGARY
szirmay@fsz.bme.hu
Abstract:
This paper examines worst-case and average-case complexity measures of ray-shooting algorithms in order to find the answer to the question why computer graphics practitioners prefer heuristic methods to extensively studied worst-case optimal algorithms. It demonstrates that ray-shooting requires at least logarithmic time in the worst-case and discusses the strategies how to design such worst-case optimal algorithms. It also examines the lower-bounds of storage complexity of logarithmic-time algorithms and concludes that logarithmic time has very high price in terms of required storage. In order to find average-case measures, a probabilistic model of the scene is established. We conclude that algorithms optimized for the average-case are not only much simpler to implement, but have moderate storage requirement and can even run faster for the majority of problems.
Keywords:
Ray-shooting, complexity analysis, data-stuctures.