| dc.description.abstract | The computational requirements of high-quality, real-time rendering exceeds the limits of generally available computing power. However illumination effects, except shadows, are less noticeable on moving pictures. Shadows can be produced with the same techniques used for visibility computations, therefore the basic requirements of real-time rendering are transformations, pre-selection of the part of the scene to be displayed and visibility computations. Transformations scale well, ie, their time requirement grows linearly with the input size. Pre-selection, if implemented by the traditional way of polygon clipping, has a growing rate of N logN in the worst case, where N is the total number of edges in the scene. Visibility computations, exhibiting a quadratic growing rate, are the bottleneck from a theoretical point of view. Three approaches are discussed to speed up visibility computations: (i) reducing the expected running time to O(NlogN) (ii) using approximation algorithms with O(NK) worst-case time, where K is the linear resolution of the image, and (iii) applying parallel techniques leading to logarithmic time in the worst-case. Though the growing rate of the time requirement of pre-selection is significantly slower than that of visibility, it is demonstrated that pre-selection has to deal with a significantly higher amount of data than visibility computations, as the average clipping volume is 1/27 of the volume of the model. | en_US |
