Source:Department of Computer Science, University of Calgary, Volume MSc, Calgary (2018)
The literature on path tracing has rarely explored distributing workload using distinct spatial partitions. This thesis corrects that by describing seven algorithms which use Voronoi cells to partition scene data. They were tested by simulating their performance with real-world data, and fitting the results to a model of how such partitions should behave. Analysis shows that image-centric partitioning outperforms other algorithms, with a few exceptions, and restricting Voronoi centroid movement leads to more efficient algorithms. The restricted algorithms also demonstrate excellent scaling properties. Potential refinements are discussed, such as voxelization and locality, but the tested algorithms are worth further exploration. The details of an implementation are outlined, as well.