The most time consuming calculation of any ray tracer. Given a collection of various objects (the world), a ray starting location (origin) and direction, this operation seeks to obtain the closest object the ray intersects, and the 3D point (and usually surface normal) of the intersection.

The reason this is so time consuming is because the computer has to use a collection of tests, called ray-object intersection tests, for each object the ray has the potential of intersecting. There exist well-documented methods to test a ray against many simple objects such as:

Ray-Plane intersection
Ray-Triangle intersection
Ray-Polygon intersection
Ray-Box intersection
Ray-Cylinder intersection

A couple of examples have already been noded:

How to test if a ray intersects with a sphere
Ray Tracing: intersections with cones

The main problem is that the ray tracer isn't like a human, it can't just look at the ray and the set of objects and say "Yep, the ray hits object X". Instead, the ray tracer does something like this:


for(all objects){
    data = TestRayAgainstObject();
    if(data->distance_to_hit < current_distance){
        hitdata = data;
        continue;
        }
    }

One thing that's immediately obvious about this operation is that the ray has to be tested against every object in the scene, as the nearest intersection has to be returned. If your scene has thousands of different objects, it could take all day to calculate the intersection for one ray!

This method as described is better known as stupid ray tracing.

ray tracing acceleration techniques are usually employed to make this above operation a lot smarter. One of these techniques is known as heirarchical bounding volumes. It happens that the CPU time required to compute a ray-box intersection is a lot less than most other tests. Some ray tracers use a clever algorithm of enclosing nearby sets of objects in bounding boxes, and then testing the ray against each bounding box. If the ray doesn't pierce the box, then the ray is not tested against any object in that box. This can save you a lot of time if it's well-implemented. This method is often integrated together with a Binary Space Partition algorithm. Using a BSP helps you arrange the objects in a set of heirarchical bounding boxes, and provides a very fast method of determining which of these boxes the ray intersects and in which order along the ray path.


For additional information, Graphics Gems are an excellent set of books dealing with topics in computer graphics and ray tracing, complete with very useful source code.

http://www.acm.org/pubs/tog/GraphicsGems/

Also the book "Introduction to Ray Tracing" by Andrew Glasner is an excellent reference on the subject of ray-object intersections.

Log in or register to write something here or to contact authors.