Ma, Vincent C. H.McCool, Michael D.Thomas Ertl and Wolfgang Heidrich and Michael Doggett2013-10-282013-10-2820021-58113-580-11727-3471https://doi.org/10.2312/EGGH/EGGH02/089-098For hardware accelerated rendering, photon mapping is especially useful for simulating caustic lighting effects on non-Lambertian surfaces. However, an efficient hardware algorithm for the computation of the k nearest neighbours to a sample point is required. Existing algorithms are often based on recursive spatial subdivision techniques, such as kd-trees. However, hardware implementation of a tree-based algorithm would have a high latency, or would require a large cache to avoid this latency on average. We present a neighbourhood-preserving hashing algorithm that is low-latency and has sub-linear access time. This algorithm is more amenable to fine-scale parallelism than tree-based recursive spatial subdivision, and maps well onto coherent block-oriented pipelined memory access. These properties make the algorithm suitable for implementation using future programmable fragment shaders with only one stage of dependent texturing.I.3.7 [Computer Graphics]Three Dimensional Graphics and RealismColorShadingShadowingTexture.