BVH is slowing down Python raytracer instead of speeding it up

[sturdy tapir]

My Python raytracer before I added BVH (aabb.py and bvh.py): https://github.com/RW-77/python-raytracer

After adding aabb.py and bvh.py and slightly refactoring hittable_list.py, my code is much slower.

The BVH tree constructor operates on a HittableList, a list of scene objects, sorting by a random axis and then splitting in half to a left node and right node. This approach is taken from https://raytracing.github.io/books/RayTracingTheNextWeek.html#boundingvolumehierarchies.

I don't know exactly where the problem is. I've tried debugging by creating a BVH.print_tree() method which does a BFS traversal and prints each BVH_Node's bounding box and the type of it's left and right children. Based on this, my tree appears to be constructed correctly. So it may have something to do with how the hit() function is being called.

[flint bolt]

I can't imagine the memory layout is going to be very nice here in Python. How many objects are you testing where you're still seeing a reduction in perf with the BVH?

it will slow things down with only a few objects

You can check how many nodes you're hitting while tracing a ray through the BVH to see how good (or bad) it has divided the scene nodes, in case you have a bug there. (it's hard to see just from glancing through it)

https://jacco.ompf2.com/2022/04/13/how-to-build-a-bvh-part-1-basics/

[sturdy tapir]

Actually something I didn't mention before is that the BVH also causes most of the objects not to render properly

[sturdy tapir]

For 120 objects, BVH takes 27 seconds while no BVH is 12 seconds

For ~5000 objects, no BVH takes 101 seconds, BVH just didn't render at all

[hallow pebble]

Can you show your hit() function?

[sturdy tapir]

Which one? BVH_Node.hit() is in bvh.py, and the AABB.hit() is in aabb.py.

Are you asking for Sphere.hit()?

[hallow pebble]

BVH_Node.hit()

[sturdy tapir]

It's in the bvh.py file I sent

[hallow pebble]

Ah, sorry, didn't notice

I think the BVH_Node.hit() is not implemented correctly.

the objects in the left child could intersects the ray before the objects in the right child. But when the left child is tested against the ray, it's unaware of the intersecting distance of the right child. This becomes a problem since rec_left is short-circuitly returned

[sturdy tapir]

I think so too, thanks for pointing this out

I changed it to this:

# return rec_left or rec_right if the other is None
        if rec_left is not None and rec_right is None:
            return rec_left
        elif rec_right is not None and rec_left is None:
            return rec_right
        # for collisions in both rec_left and rec_right, return the closest hit object (smallest t)
        elif rec_left is not None and rec_right is not None:
            return rec_left if rec_left.t < rec_right.t else rec_right
        # if nothing is hit, return None
        else:
            return None

[sturdy tapir]

How many object until BVH is faster than linear search?

For 445 objects my raytracer takes:

• 58.81017208099365 seconds with BVH.
• 29.7018039226532 seconds without "BVH (linear search).

Is that normal?

This is for rendering a basic scene containing spheres only:

width: 300px
height: 168 px
samples per pixel: 50
max recursion depth: 25

If I increase the width to 600 px maintaining a 16:9 aspect ratio, increase samples per pixel to 250, the BVH takes incredibly long. (Linear does it ~3 minutes)

[hallow pebble]

It isn't. I would say 40 well-spaced(not heavily overlapped) objects will be enough for BVH to do a better job.

[hallow pebble]

You tested the right child up to the distance returned by rec_left, so if rec_right is not None, you can confidently return it, without comparing the diatance to rec_left again.

In my BVH, the child that is "closer"(e.g. sorted by center) is tested first, I'm not sure if not doing this breaks things. Maybe you should double check your implementation against the reference one?

Also, print has some overhead

[sturdy tapir]

maybe my BVH implementation just sucks?

• I'm using Python?

[sturdy tapir]

wdym by this?

they're sorted by either x, y, or z axis at random, not all three

so the first element isn't even necessarily the closest

[hallow pebble]

I mean the two children are sorted on-the-fly when tested inside BVH_Node.hit(). The child that is closer(so more likely to produce a closer intersection) according to some metric is tested first

[hallow pebble]

If the sorting axis is x, and the children are sorted from low x to high x, and the x component of ray direction is positive, then the first child should be tested first. If the ray direction is negative on x axis, then the second child should be tested first

[sturdy tapir]

I will still have to test the second child, no?

I will need to render the closest object 100% of the time, so why does it matter that one child is more likely to produce a closer intersection?

Btw I have an update: I've discovered that my BVH does in fact work. Although I am still open to suggestions on how to optimize because it clearly has an insane constant factor.

[sturdy tapir]

BVH On vs Off

BVH Off (Linear Search)

density = 1
n = 40,000
time = 5589 seconds (vs 43 seconds for BVH)
calls = a lot (didn't count)

BVH On

density = 1
n = 40,000
time = 43 seconds
calls = 251,000,000

4 Million Spheres Render

density = 20
n = 4,000,000
time = 394 seconds
calls = 2125696153

[hallow pebble]

If an intersection does get found in the "closer" node, then we can skip testing the other node since even if it intersects, the intersection will be farther away than the intersection in the closer node. If we had tested the node in the wrong order, we will always have to test both nodes.

This is the ideal case for non-overlapping BVH. If the left and right children do overlap a bit then the result would be less ideal, but the strategy still helps.

[hallow pebble]

I think it will be a premature optimization since you are using Python. What improves performance in other programming language like C++ or Rust might slowdown a Python program. After you have switched to a lower level language you can take a look at some of those optimization:

1. more optimized AABB hit test(some information can be computed per ray, instead of per ray-AABB test)
2. manual stack-based BVH_Node.hit() (so that no function recursion is used)
3. Surface area heuristics

You should take a look at https://github.com/madmann91/bvh
His BVH tree traversal function is well-tuned and much faster than the naive one