Abstract:
This paper presents an efficient algorithm for tracing particles in large, arbitrary geometries containing nonparticipating media, drawing on techniques from computer graphics' ray tracing field. It details an efficient intersection algorithm for triangles and convex planar quadrilaterals, and discusses various ray tracing techniques to limit surface tests, implementing Uniform Spatial Division (USD) and covering the "mailbox" technique. Timing results are provided to demonstrate the efficiency of the intersection algorithm and USD across geometries with thousands of surfaces, observing speedups in tracing time exceeding eighty-fold with USD.
