The ray tracer you're provided with is a modified (aka "hacked") version of the one used this year in COMPSCI 372. So if you did 372 this year, you should find the general structure pretty much the same. The major addition is the BSP stuff, which is included in the files SceneDescription.h/cpp. See later for details.
For those who didn't do 372 this year, the code is based on that in F.S.Hill's 372 text. The principal change in the structure is that whereas Hill computes all the hit details whenever a ray hits an object, I compute only the t value. The program sorts the hits into t order and then "calls back" to the hit object to get the position of the hit and the normal at the hit point. I give some quite detailed discussion of how the code is structured in my lecture notes:
http://www.cs.auckland.ac.nz/compsci372s1c/richardLectures/31RayTracing.complete.4up.pdf
Look at slides 13 and beyond.
This is a teaching ray tracer, not a production ray tracer. So I've tried to compromise on the side of readability rather than performance (though you may not agree!). So there are lots of places where relatively inefficient code is written. For example, I use Burkhard's geometry classes throughout rather than float arrays, and I sometimes use generalized algorithms where faster special purpose ones exist e.g. when clipping a ray to an axis-aligned bounding box. Because of this the execution speed is likely to be significantly slower than that of a production ray tracer, perhaps by a factor of two or more.
Another apologetic warning: I'm a bit embarrassed at the way bits of executable code are scattered around between ".h" files and ".cpp" files. In my defence, I'll point out that that's perfectly normal in C++! You may find it helpful to navigate in the code using the "class view" panel in your IDE (.NET or Dev-C++ Version 2) -- this hides the problem somewhat.
A final caveat: the code has been rather frantically hacked at over the last couple of days. It really needs to undergo a refactoring effort to remove some of the debugging code, clean up the comments, etc. But I don't have time. So please think of it this way: I was going to give you the 372 program and tell you to implement BSP-tree space subdivision. What I've done instead (I hope) is make your job a lot easier. Please don't grumble too much about the odd inelegance in what you're being given (though please do tell me about any bugs you find).
The provided RayTracer should compile and run under either .NET or Dev-C++. It displays a scene consisting of a 3D array of spheres on a regular grid, interconnected by axial cylinders. The program takes 3 parameters:
For example, the command
RayTracer 4 1000 0
displays a 4 x 4 x 4 grid of spheres using a brute-force approach, since the maximum BSP depth of 0 results in the BSP tree being a single leaf node containing all scene objects, which are all checked by every ray. Note that when the program runs it prints out various run-time statistics, such as how many rays of various sorts were traced and how many ray-object intersections were performed. These should be helpful to you in answering the exercise sheet question.
When the BSP tree traversal has been implemented (see the section "Your Job") you should be able to get an IDENTICAL image (only much faster) with the command
RayTracer 4 10 10
The BSP tree is implemented by three classes: CBSPNode and its two subclasses CBSPTree and CBSPLeaf. The superclass represents any node in a BSP tree; the other two are internal and leaf nodes respectively. A separate function (not a method of those classes) makeBSPTree builds a BSP tree from a list of scene objects and a bounding volume.
The tree is built by a simple process of recursively subdividing the scene volume by an axis-aligned plane orthogonal to the volume's longest axis. Unlike in the polygon-rendering case, scene objects are NOT split by the partitioning plane -- any object that straddles a partitioning plane is placed in both the two subtrees. Since the tree traversal stops when it hits the first object, this doesn't cause any problems except that you do have to check that when a ray hits an object it hits it in the current leaf volume -- see the lecture notes. [And if you were implementing transparent objects, you'd need to avoid passing through the same object twice, but that's not a problem in this ray tracer.]
The "only" thing you have to do to get the ray tracer working with BSP tree subdivision is to write the 20 - 30 lines of code for the method CBSPTree::getFirstHit().When (if?) you eventually succeed, I promise you it'll feel great!
It turns out that this method isn't as simple as I thought. In class I gave you a very simplistic algorithm: "at each internal node just intersect the ray with the objects on the near side of the partitioning plane and if you don't hit anything then do the objects on the far side". This is a correct algorithm but a woefully inefficient one. A little bit of thought reveals that a ray that misses all scene objects will finish up doing an intersection test with every object in the scene -- scarcely the goal of the exercise!
A correct algorithm is based around the following observation. If you push a ray (a set of colinear points with a defined start and end) down into a BSP tree, clipping it in two at each partitioning plane, you'll land up with bits of the ray in a small subset of the leaves. Only the scene objects in those leaves need to be tested for intersection with the ray. And of course the tests should be carried out in sequence along the ray.
Those observations lead to the following relatively simple algorithm, which is taken from an article "Ray Tracing with the BSP Tree" by Kelvin Sung and Peter Shirley, in "Graphics Gems III", P271. The input parameters are the ray (defined by a start and a direction), the BSP tree node, and the minimum and maximum "t" values along the ray (which define the sub-ray of relevance).
RayTreeIntersect(Ray, Node, min, max)
if (Node is NIL) then return ["no intersect"]
if (Node is a leaf) then begin
intersect Ray with each primitive in the node
discarding those farther away than "max"
return closest object
end
dist := signed distance along ray to the cutting plane of the node
near := child of Node for half-space containing ray start
far := the "other" child of Node (i.e. not the near one)
if ((dist > max) or (dist < 0) then // Whole interval is on near side
return RayTreeIntersect(Ray, near, min, max)
else if (dist < min) then // Whole interval is on far side
return RayTreeIntersect(Ray, far, min, max)
else begin
hit_data := RayTreeIntersect(Ray, near, min, dist) // test near side
if hit something then return hit_data
return RayTreeIntersect(Ray, near, dist, max)
end
I suggest you implement that algorithm (except the first bit, which is handled
in the separate CBSPLeaf::getFirstHit method). Then, when you've got it working, try moving the eye point,
defined in RayTracerMain.cpp, to (0,0,5). See if it still works. If it
doesn't (as mine didn't), figuring out why will be an interesting exercise for
you :-)