<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.)</p>

CC BY-SA 3.0
2015-12-10T07:29:19.003Z
Thanks @NathanReed. 1 more question. Say I want to traverse the tree breadth first, I am at level 0 (i.e at the root of the tree, I haven't divided the tree yet, I have a bounding box including all the scene primitives). I divide the bounding box along an axis such that the left child node is the one closer to the camera. Then I find that a certain ray R intersects the left node. R should be early terminated with regard to the right child node and to all of its future children nodes. But I still have to test the intersection of R with the future children nodes of this left node, am I?
S.E.K.
CC BY-SA 3.0
2015-12-10T20:01:27.557Z
@user2651062 Normally you would have built the whole tree before you start traversing it. Your comment makes it sound like you're trying to build and traverse at the same time? Or else what do you mean by "future child nodes"? In any case, you have to traverse all child nodes that intersect the ray or segment. If it intersects the left child, you descend into the left child and repeat the process for its children. You might need to descend into both children if they both intersect the ray/segment.
Nathan Reed
CC BY-SA 3.0
2015-12-10T05:20:02.120Z
2015-12-10T05:20:02.120Z
Nathan Reed
<p>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?<br/>
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) ?</p>

<raytracing><c++><optimisation><data-structure>
The meaning of early ray termination and front-to-back traversal in ray tracing
S.E.K.
# The meaning of early ray termination and front-to-back traversal in ray tracing

(Asked by: username_0 on 2015-12-09)

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) ?

**Tags:** raytracing, c++, optimisation, data-structure


---

## 1 answers

### Answer by username_1 on 2015-12-10. Score: 5

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.)

> **Comments:**
> **username_0**: Thanks @username_1. 1 more question. Say I want to traverse the tree breadth first, I am at level 0 (i.e at the root of the tree, I haven't divided the tree yet, I have a bounding box including all the scene primitives). I divide the bounding box along an axis such that the left child node is the one closer to the camera. Then I find that a certain ray R intersects the left node. R should be early terminated with regard to the right child node and to all of its future children nodes. But I still have to test the intersection of R with the future children nodes of this left node, am I?  
> **username_1**: @user2651062 Normally you would have built the whole tree before you start traversing it. Your comment makes it sound like you're trying to build and traverse at the same time? Or else what do you mean by "future child nodes"? In any case, you have to traverse all child nodes that intersect the ray or segment. If it intersects the left child, you descend into the left child and repeat the process for its children. You might need to descend into both children if they both intersect the ray/segment.  

---

