# Optimization

## 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.]