Basically, every raytracer looks like this code:

for (each pixel) {The performance is clearly going to be O(pixels*bounces*geometry). The number of pixels is in the millions, the amount of geometry is in the thousands, although luckily we can get away with only a few bounces (on average). Searching thousands of chunks of geometry for each of the millions of pixels per frame is not going to be efficient.

for (each ray bounce) {

for (each chunk of geometry) {

if (ray from pixel hits geometry)

shade pixel with geometry

}

}

}

One simple way to improve performance above is to reduce the number of pixels--that is, reduce the screen resolution. Another simple trick is to reduce the geometric complexity of the scene.

But one surprising way to reduce the average geometric complexity per ray without changing the final image is to use a "bounding volume hierarchy". The basic idea behind bounding volumes is before digging into a complicated block of geometry, we first intersect our ray with a simple bounding volume like a sphere. If the ray misses the sphere, then we can skip the entire block of geometry. Because misses are common (a ray can only hit one object in the end!), this can be a huge savings in complex scenes. You can even have a nested tree of bounding volumes, and raytracing then boils down to something like a binary search: does the ray hit anything on the left? No, how about the right? Yes! Then is it the left-right, or the right-right? And so on.

Common bounding volumes include:

- Planes. Intersecting a ray with a plane only takes one dot
product, but you need to load the plane normal and offset, which is
four floats. Planes aren't closed, so you need several planes to
bound small objects.

- Bounding boxes. Intersecting a ray with an axis-aligned bounding box takes three dot products, and six floats.
- Spheres. Intersecting a ray with a sphere takes three dot products, and four floats.

ray_intersection intersect(ray r,geometry_tree_node g) {Of course, "intersect" is a recursive function, and recursion isn't supported on the GPU yet (no hardware stack). Instead of recursing, you can:

ray_intersection ret=miss;

for (c in child geometry of g) {

if (r hits c's bounding volume)

add_intersection(ret,intersect(r,c));

}

return ret;

}

- Ignore bounding volumes, and just traverse all the geometry
linearly. The bounding volumes give you a log-factor speedup,
like binary search, so this is quite expensive for scenes with any
complexity.

- Expand the functions out to a fixed recursion depth. The code grows exponentially as you do this, though!

- Convert the recursion to some form of iteration. For example, you can add links to "thread" a binary tree, which allows you to traverse the tree without using any stack space.

You can read much more about iterated function systems online, for example the Wikipedia Sierpinksi page.

I wrote a little 2D IFS manipulation program back in 2003.