Ray tracing of box spline surfaces

Ray tracing is a computationally expensive computer graphics algorithm for rendering three-dimensional scenes based on a camera model. This thesis develops tools for ray tracing a certain class of multivariate spline surfaces generated from box splines. The tools include interactive programs for designing such surfaces and for including them into a ray tracing program. The surfaces are approximated by triangular facets. A comparison of several ray-triangle intersection methods leads to a new, hybrid method which is shown to be superior to the others. A new three-dimensional data structure, the 2:1 octree, is developed to speed up the ray tracing calculations. This structure differs from the standard octree construct in that leaves on the octree corresponding to adjacent locations in space are constrained to differ in size by no more than a factor of two. This makes it feasible to employ points to help locate directly the sequence of leaves traversed by a ray, without having to travel to the root of the tree every time the ray moves from one leaf to another. Finally, parallel implementations of ray tracing are constructed and compared on a Sequent Balance, a machine with 20 processors and shared main memory. The schemes implemented include image space subdivision and several scheduling algorithms. The latter result from dividing the ray tracing computations into independent subtasks and assigning processors to these subtasks according to several schemes. In static scheduling, the assignment is done beforehand and not changed. Two types of dynamic scheduling were tried, in which the work load is monitored and redistributed when an imbalance is sensed. While image space subdivision results in almost perfect linear speed-up, the performance of the more sophisticated load-balancing algorithms is disappointing.