1
$\begingroup$

While studying Peter Shirley's Ray Tracing:The Next Week, I came across an issue that I cannot quite figure out:

Stepping through the random_scene() case of the code, found out that once a leaf of the BVH tree is reached, the aabb of the object is checked for a hit; even when the object is a sphere.

The check for a hit against the bounding_box of a sphere (aabb) is necessary but not sufficient; there are parts of the bounding_box which is not a part of a sphere.

Shouldn't it invoke the specific hit() function of the object when the leaf is reached?

Yet the code works somehow.

$\endgroup$
1
$\begingroup$

It does indeed do exactly what you described. Have a close look at how the bvh is constructed, it is a passed a list of concrete shapes that implement hittable, e.g. xy_rect, sphere, etc. The base cases for the recursive bvh construction create leaf nodes that directly reference the concrete shapes that make up the scene.

bvh_node::bvh_node(
    const std::vector<shared_ptr<hittable>>& src_objects,
    size_t start, size_t end, double time0, double time1
) {
    auto objects = src_objects; // Create a modifiable array of the source scene objects
    ...
    size_t object_span = end - start;

    // **create leaf nodes, concrete shapes referenced here**
    if (object_span == 1) {
        left = right = objects[start]; 
    } else if (object_span == 2) {
        if (comparator(objects[start], objects[start+1])) {
            left = objects[start];
            right = objects[start+1];
        } else {
            left = objects[start+1];
            right = objects[start];
        }
    } else {
       // create internal bvh_node
       ...
}

When bvh_node::hit is called and the ray/aabb test passes, the left and right child nodes have their hit functions called recursively. Eventually when this recursion bottoms out the concrete shapes referenced by the leaf nodes will have their hit functions called as you would expect.

bool bvh_node::hit(const ray& r, double t_min, double t_max, hit_record& rec) const {
    if (!box.hit(r, t_min, t_max))
        return false;

    bool hit_left = left->hit(r, t_min, t_max, rec);
    bool hit_right = right->hit(r, t_min, hit_left ? rec.t : t_max, rec);

    return hit_left || hit_right;
}
$\endgroup$
1
$\begingroup$

I agree with @xasp's answer, but to understand why you would do it like that:

Checking for ray-circle intersections is not the most expensive in terms of cpu-time required, but a ray-aabb intersection is frighteningly faster. Apparently Shirley found that in his scenes, checking the leaf's AABB first led to better results, because in a "sparse bounding volume tree", you might recurse down to a leaf node, but still not hit it.

So why is the AABB faster than a sphere intersection? Well for spheres in 3d you need to square 3 numbers (will be compiled to a single vector instruction most likely) and you need to then take the square root, which is a traditionally expensive operation. See this answer: https://stackoverflow.com/a/12304868/11359454

In AABB intersection you just need to do some larger/smaller than checks and divide your rays x y and z components to get the inverse (single vector divide instruction).

Infamously in quake, to get faster lighting, an approximation hack was used to get a fast root-ish. Nowadays that hack is actually slower than a call to sqrtf, because the floating point parts of processors have gotten faster and more advanced.

$\endgroup$
3
  • $\begingroup$ "and you need to then take the square root," Why do you need to take the sqrt? If you are comparing the perpendicular distance from centre to ray against the radius, surely one just compares against the square of both values? $\endgroup$ – Simon F Nov 16 '20 at 13:26
  • $\begingroup$ @SimonF because of the math to work out an intersection between a line and a sphere, you need to solve a quadratic equation which involves a root. We're not just checking distance, we're generating intersection points. There is also another method but even that requires taking a root. I recommend reading this: scratchapixel.com/lessons/3d-basic-rendering/… You'll see there's even more math than I mentioned. Here is the math for a ray-AABB intersection: tavianator.com/2011/ray_box.html $\endgroup$ – AnnoyinC Nov 16 '20 at 20:02
  • $\begingroup$ Perhaps I wasn't clear enough. Most of the scene testing is rejecting potential hits against geometry. You don't need the sqrt for that part. The OP was asking why use the AABB of the sphere for a reject test, rather than the sphere itself, and the reject test for a sphere, to my knowledge, doesn't need a sqrt. (For example, see "An Introduction to Ray Tracing, 1989, Ed: Andrew Glassner). $\endgroup$ – Simon F Nov 19 '20 at 9:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.