Realistic Image Synthesis Using Photon Mapping
A practical guide to photon mapping, this book provides both the theory and the insight necessary to implement photon mapping and simulate all types of direct and indirect illumination efficiently.
TABLE OF CONTENTS Realistic Image Synthesis Using Photon Mapping
Chapter 6: The Photon Map Data Structure
The photon map is a representation (a map) of all the stored photons in the model. A fundamental aspect of the photon map is that it is decoupled from the geometry in the model. This means that we do not associate photons with certain geometry, but instead keep them in a separate structure. This chapter describes the actual data structure used and efficient techniques for representing and using it.
6.1 The Data Structure
Photons are only generated during the photon tracing pass. When the image is rendered, the photon map is a static data structure that is used to compute statistics of the illumination in the model. The statistics are based on the nearest photons at any given point, and can be computed at all locations in the model. In order for the photon-mapping algorithm to be practical, the data structure has to be fast when it comes to locating nearest neighbors in a three-dimensional point set. At the same time it should be compact since we intend to use millions of photons.
We can immediately discard simple structures such as multi-dimensional arrays and lists, since searching through these for the nearest neighbors is far too costly.
A simple data structure for maintaining proximity within a set of points is the three-dimensional grid in which a cube containing the photons is divided uniformly along x, y, and z into a number of sub-cubes, each containing a number of photons. A search for the nearest neighbors is simply a...
Copyright A K Peters, Ltd. 2001 under license agreement with Books24x7
