On average-case complexity of ray tracing algorithms
G. Marton, László Szirmay‐Kalos · Digital Library (University of West Bohemia) · 1995
A theoretical framework for analyzing average-case time and storage complexity of ray tracing acceleration techniques is introduced by means of homogeneous spatial Poisson point processes. Then, as a demonstrative example of its application, the expected query time of the widely known technique based on a regular spatial grid is analyzed. Finally, an interpretation of the results is presented within the context of probability theory.