The meaning of early ray termination and front-to-back traversal in ray tracing

Question

I'm new to computer graphics. These days I've been trying to understand how ray tracing using an acceleration data structure works. I came across the term "early ray termination" several times, I looked it over the internet several times too, but I haven't been able to find a satisfactory explanation of it. What does it mean to terminate a ray early, and why do we have to do it?
Besides, I noticed that the term "front-to-back traversal" is mentioned almost every time there's a mention of "early ray termination". Concretely how does front-to-back traversal work (in the case of a kd-tree for example) ?

Answer 1

Front-to-back traversal is the idea that when traversing a ray through the acceleration structure, we want to examine nodes that are in front, i.e. closer to the camera, before other nodes. If you only want the first intersection with a surface (as usual in ray tracing), then if you get an intersection in the front node you don't need to traverse any nodes behind it; as any possible intersection there would be later than the one you already found. This saves time.

For example, in a kd-tree, at each node you have a splitting plane dividing space into two child nodes. You would first descend to the child closer to the camera, and only if no intersections are found there do you descend to the other child.

Early ray termination seems to be a term used in the context of volume rendering. When you're traversing a ray through a medium that attenuates light, such as fog, smoke, cloudy liquids, etc., then beyond a certain distance there is no possibility of the ray having any more effect on the image. If you have thick fog with a visibility of 10 meters, then an object 11 meters away cannot be seen.

You can precalculate the distance at which the attenuation reaches 99% or so (it never quite reaches 100%, but approaches it exponentially). There is no reason to intersect the ray against objects farther than that, so when using the acceleration structure, you can simply discard any nodes beyond that distance. In effect, the ray becomes a line segment terminated at a fixed length. If it doesn't hit anything within that length, there's no point checking further. (Another case where limited-length rays are handy is for shadow rays. You only want to trace them back to the originating light source; any intersections beyond that are irrelevant for the shadow.)