Optimization
Table of Contents
The Need for Optimizations
Raytracing can be an extremely computationally intensive process. The recent
feature length film Toy Story, with 110,000 frames, took about 46 days to render
on 117 Sun Sparc 20's. (87 100Mhz dual processors, and 30 100Mhz quad
processors). For more details of the rendering system used to render all the
frames in toy story, click here.
Because of the immense computational time required to render images, it is
necessary to optimize ray tracing as highly as possible.
Techniques
Backwards Ray Tracing
As mentioned above, one of the moste effective and easiest to implement
performance optimizations is to trace rays backwards from the eye, rather than
from the light sources. In this way, computing power is not wasted tracing rays
that never hit the model or camera.
Bounding Volumes
Onoptimized raytracing involves calculating intersection points for every
primitive in the scene. As the number of primitives increase, this calculation
scales in constant O(N) time. In order to solve this problem, ray tracers
implement Bounding Volumes. These objects enclose other, more complicated
objects in the scene. If a ray intersects a bounding volume, than all the
primitives that the bounding volume encloses must be checked for intersection,
and no speed gain is noticed. On the other hand, if a ray is tested to see if it
intersects a bounding volume and it does not, then there is no need to test any
of the enclosed objects for intersection. {The buddha in the following image is re-produced, with permission, from the
Stanford Computer Graphics Lab Web Site @ http://graphics.stanford.edu. Reproduction is prohibited.]
Space Subdivision
Another technique similar to Bounding Volumes uses a similar concept of enclosing
complicated shapes inside of simpler, larger primitives. This technique, called
Space Subdivision, divides up the entire world into regular shapes. These
shapes are further subdivided until each one contains no more than a given number
of subdivions. This process can be further subdivided if multiprocessing or
vector math capabilities are available. The maximum number of primitives in any
given subdivision can be determined by the size of the vector registers and the
number of processors. In this technique, the world is first uniformly
subdivided, say into a given number of cubes, and then adaptively subdivided (as
necessary) to lowere the number of primitives per cube. The values for number of
subdivisions and primitives per subdivision trade off with one another. The
implementer of a raytracer must be careful not to set the number of primitives
per subdivision too low, for the number of subdivions will be too high and the
majority of calculation time will be spent calculating ray-subdivision
intersection. [The buddha in the following image is re-produced, with permission, from the
Stanford Computer Graphics Lab Web Site @ http://graphics.stanford.edu. Reproduction is prohibited.]
Table of Contents