1.7. 5D Octree

In the previous, simple algorithm, we still walk along a ray every time we shoot it into the scene. However, rays are essentially static objects, just like the geometry of the scene! This is the basic observation behind the following algorithm [Arvo and Kirk 87, Arvo and Kirk 89]. Again, it makes use of octrees to adaptively decompose the problem.

The underlying technique is a discretization of rays, which are 5D objects. Consider a cube enclosing the unit sphere of all directions. We can identify any rays direction with a point on that cube; hence, it is called a direction cube (see Figure 1.17). The nice thing about it is that we can now perform any hierarchical partitioning scheme that works in the plane, such as an octree: we just apply the scheme individually on each side.

Figure 1.17: With the direction cube, we can discretize directions and organize them with any hierarchical partitioning scheme.

Using the direction cube, we can establish a one-to-one mapping between direction vectors and points on all six sides of the cube, i.e.:

We will denote the coordinates on the cubes side by u and v . Here, {+ x, ˆ x, } are just some kind of IDs that are used to identify the side of the cube, on which a point ( u, v ) lives (we could have used {1 , , 6} just as well).

Within a given universe B = [0 , 1] ³ (we assume it is a box), we can represent all possibly occurring rays by points in

(1.3)

which can be implemented conveniently by six copies of 5D boxes.

Returning to our goal, we now build six 5D octrees as follows . Associate (conceptually) all objects with the root. Partition a node in the octree if there are too many objects associated with it and the nodes cell is too large. If a node is partitioned, we must also partition its set of objects and assign each subset to one of the children.

Observe that each node in the 5D octree defines a beam in 3-space: the xyz -interval of the first three coordinates of the cell define a box in 3-space, and the remaining two uv -intervals define a cone in 3-space. Together (more precisely, taking their Minkowski sum), they define a beam in 3-space that starts at the cells box and extends in the general direction of the cone (see Figure 1.18).

Figure 1.18: A uv interval on the direction cube plus a xyz interval in 3-space yield a beam.

Since we have now defined what a 5D cell of the octree represents, it is almost trivial to define how objects are assigned to sub-cells: we just compare the bounding volume of each object against the sub-cells 3D beam. Note that an object can be assigned to several sub- cells (just like in regular 3D octrees). The test whether or not an object intersects a beam could be simplified further by enclosing a beam with a cone and then checking the objects bounding sphere against that cone. This just increases the number of false positives a bit.

Having computed the six 5D octrees for a given scene, ray tracing through that octree is almost trivial: map the ray onto a 5D point via the direction cube; start with the root of the octree that is associated with the side of the direction cube onto which the ray was mapped; find the leaf in that octree that contains the 5D point (i.e., the ray); and check the ray against all objects associated with that leaf.

By locating a leaf in one of the six 5D octrees, we have discarded all objects that do not lie in the general direction of the ray. But we can optimize the algorithm even further.

First of all, we sort all objects associated with a leaf along the dominant axis of the beam by their minimum (see Figure 1.19). If the minimum coordinate of an object along the dominant axis is greater than the current intersection point, then we can stopall other possible intersection points are farther away.

Figure 1.19: By sorting objects within each 5D leaf, we can often stop checking ray intersection quite early.

Second, we can utilize ray coherence as follows. We maintain a cache for each level in the ray tree that stores the leaves of the 5D octrees that were visited last time. When following a new ray, we first look into the octree leaf in the cache to see whether it is contained therein before we start searching for it from the root.

Another trick (which works with other ray acceleration schemes as well) is to exploit the fact that we do not need to know the first occluder between a point on a surface and a light source. Any occluder suffices to assert that the point is in shadow. So, we also keep a cache with each light source, which stores the object (or a small set) that was an occluder last time.

Finally, we would like to mention a memory optimization technique for 5D octrees, because they can occupy a lot of memory. It is based on the observation that within a beam defined by a leaf of the octree, the objects at the back (almost) never intersect with a ray emanating from that cell (see Figure 1.20). So, we store objects with a cell only if they are within a certain distance. Should a ray not hit any object, we start a new intersection query with another ray that has the same direction and a starting point just behind that maximum distance. Obviously, we have to make a trade-off between space and speed here, but when chosen properly, the cutoff distance should not reduce performance too much, while still saving a significant amount of memory.

Figure 1.20: By truncating the beam (or rather, the list of objects), we can save a lot of memory usage of a 5D octree, while reducing performance only insignificantly.