Abstract
An efficient algorithm for tracing particles in large, arbitrary geometries containing nonparticipating media is presented. For arbitrary triangles and/or convex planar quadrilaterals, an efficient intersection algorithm is discussed in detail. Several techniques used in ray tracing to limit the number of surfaces tested are discussed and the method of Uniform Spatial Division (USD) is implemented. The ''mailbox'' technique is also discussed. The efficiency of the intersection algorithm and USD are demonstrated by timing results. For USD, speedups exceeding a factor of eighty are observed.