Search

Heuristics that exploit bouning boxes are common in algorithms for rendering, modeling, and animation. While experience has shown that bounding boxes improve the performance of these algorithms in practice, the previous theoretical analysis has concluded that bounding boxes perform poorly in the worst case. This paper reconciles this discrepancy by analyzing intersections amongngeometric objects in terms of two parameters: α an upper bound on theaspect ratioor elongatedness of each object; and σ an upper bound on thescale factoror size disparity between the largest and smallest objects. LettingKoandKbbe the number of intersecting object pairs and bounding box pairs, respectively, we analyze a ratio measure of the bounding boxes' efficiency, ρ =Kb/ (n + K0). The analysis proves thatρ = O(α√σlog2σ)andρ = Ω(α√σ).One important consequence is that if α and σ are small constants (as is often the case in practice), thenKb=O(Ko)+O(n, so an algorithm that uses bounding boxes has time complexity proportional to the number of actual object intersections. This theoretical result validates the efficiency that bounding boxes have demonstrated in practice. Another consequence of our analysis is a proof of the output-sensitivity of an algorithm for reporting all intersecting pairs in a set ofnconvex polyhedra with constant α and σ. The algorithm takes timeO(nlogd-1n+Kologd-1n) for dimensiond= 2, 3. This running time improves on the performance of previous algorithms, which make no assumptions about α and σ.

This article presents the density estimation framework for generating view-independent global illumination solutions. It works by probabilistically simulating the light flow in an environment with light particles that trace random walks origination at luminaires and then using statistical density estimation techniques to reconstruct the lighting on each surface. By splitting the computation into separate transport and reconstruction stages, we gain many advantages including reduced memory usage, the ability to simulate nondiffuse transport, and natural parallelism. Solutions to several theoretical and practical difficulties in implementing this framework are also described. Light sources that vary spectrally and directionally are integrated into a spectral particle tracer using nonuniform rejection. A new local linear density estimation technique eliminates boundary bias and extends to arbitrary polygons. A mesh decimation algorithm with perceptual calibration is introduced to simplify the Gouraud-shaded representation of the solution for interactive display.