|COMP1011 Assignment 2 - 05s2|
|Computing 1A 05s2||
Thu 13 Oct 2005 11:25
Despite the simplicity of the algorithm, ray tracing is a computationally intensive process. Depending on the complexity of the scene it can take hours to create a single image. One of the things that slows down the algorithm, especially in scenes containing many objects is that, for each ray, intersection is tested against every single object. Clearly, this can lead to much redundant computation. Imagine a row of non-overlapping spheres parallel with the x-y plane. Each ray from the eye only intersects one of these spheres. Now imagine there are thousands of them.
The solution to this conundrum is to split up three dimensional space into smaller chunks, each of which is guaranteed to contain at most a small number of objects. One particularly elegant way of doing this is using OctTrees: a structure that recursively sub-divides voxels (which are cubes) in eight smaller voxels. But before we can talk about how to create an OctTree we must first talk about what it means for an object to be contained within a voxel.
An object is considered to be contained within a voxel if any
portion of its surface is inside. For example a voxel could completely
contain a sphere, or only part of its surface could intersect with the
front face. Yet, if a voxel happens to be completely contain
within a sphere then we do not say that the voxel contains
the sphere. We have provided a function in the
contains which checks whether an object is
contained within a voxel or not.
With that explained we can now explain the subdivision process. We
start with one large voxel containing the scene and a maximum
number of objects that we wish each voxel to contain. We shall call
maxObjects. If the voxel contains at most
maxObjects objects then we are done; no further
subdivision is required. This voxel becomes a leaf of the
OctTree and contains all the objects. If, on the other hand, there are
more we divide the voxel into eight smaller and equally sized voxels
as per Figure 1. Each one of these is known as an octant of
the original voxel. We create a node in the OctTree that will
hold eight smaller OctTrees, which will be created from the octants.
Figure 1. The hidden voxel is voxel 4.
We then repeat the process. For each of the eight voxels we check
whether they have more than
maxObjects contained within
them. For those that do, we sub-divide and repeat the process
again. For those that don't, we stop. The process terminates when no
voxel contains more than
Thus, we can see that OctTrees break up three dimensional space is a non-uniform way. The greatest number of leaves of the OctTree will be clustered around the part of the scene where the most objects are.
Figure 2 shows a pictorial example of an OctTree:
Figure 2. One possible OctTree
The advantage of using OctTrees is that now there are a lot less objects to check intersections against. The process of ray tracing also changes in a subtle way. When we fire a ray from the eye we must first find what leaf of the OctTree we are in. We then check for intersections in that voxel. However, if we don't find an intersection this does not mean that there are no more. There could be more in other leaves of the OctTree that the ray passes through. What is needed is some way in which to find the next leaf we should be checking.
We provide a function called
WorldBase which returns a point that is guaranteed
to be in the next leaf of the OctTree that contains the ray. It
requires, as one of its arguments, the minimum size of all the leaves
in the OctTree. You will have to write a function
findMinSize to calculate this value.
pointNextVoxel is not enough to find the next leaf;
one also needs a function
getLeafContaining which finds
the leaf containing the point. You will also be writing this
This process of checking for intersections and moving on to the next leaf of the OctTree is repeated until an intersection is found or the ray passes out of the bounding voxel of the scene. This is easily checked for.
A good question is, for a given voxel what are the points that are contained within it? The answer is obvious for points well inside the voxel, but what about points on the faces? Are they included? Sometimes and sometimes not. The voxel contains all those points that are on the bottom, left and front faces but not those on the top, right and back faces.
Check the code of
for more details.