🔒 Recursive Constructor Correct Implementation | Python | Page 1

little shoal Feb 21, 2024, 5:10 PM

#

Intended Behavior:
The class BVH_Node is supposed to be a binary tree of AABBs. This implementation is a one-class approach which only stores the root.

class BVH_Node:
  def __init__(self, list: HittableList):
        """Constructs a BVH node from a `HittableList`."""
        self.bbox: AABB # (ROOT)
        self.left: 'BVH_Node'
        self.right: 'BVH_Node'

        # list.objects is passed by mutable and passed by reference
        self.construct_bvh_tree(list.objects, 0, len(list.objects))
  
  ...

  def construct_bvh_tree(self, _src_objects: list[Hittable], start: int, end: int) :
        """
        Constructs a BVH node from a subarray of a list of objects. Creates AABBs from subarrays of Hittables.
        """

        objects = _src_objects[:]
        axis = random.randint(0, 2)
                
        axis_key = self.x_axis_key if axis == 0 else self.x_axis_key if axis == 1 else self.z_axis_key

        object_span = end - start
        
        if object_span == 1:
            self.left = self.right = objects[start]
        elif object_span == 2:
            if self.box_compare(objects[start], objects[start+1], axis):
                self.left = objects[start];
                self.right = objects[start+1];
            else:
                self.left = objects[start+1];
                self.right = objects[start];
        else:
            sys.stderr.write(f"start: {type(start)}\n")
            sys.stderr.write(f"objects span: {type(object_span)}\n")
            sys.stderr.write(f"end: {type(end)}\n")
            objects[start:end] = sorted(objects[start:end], key=axis_key)
 
            mid: int = (start + object_span) // 2
            # BUG (POTENTIAL): Assignment may be incorrect
            self.left = self.construct_bvh_tree(objects, start, mid)
            self.right = self.construct_bvh_tree(objects, mid, end)
        
        self.bbox = AABB.merge(self.left.bounding_box, self.right.bounding_box)

limpid roseBOT Feb 21, 2024, 5:10 PM

#

little shoal **Intended Behavior:** The class `BVH_Node` is supposed to be a binary tree of `...

#

@little shoal

Python help channel opened

Remember to:

Ask your Python question, not if you can ask or if there's an expert who can help.
Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

little shoal Feb 21, 2024, 5:13 PM

#

                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  [Previous line repeated 4 more times]
  File "/Users/caleb/Documents/Projects/raytracer/src/bvh.py", line 69, in construct_bvh_tree
    self.bbox = AABB.merge(self.left.bounding_box, self.right.bounding_box)
                                                   ^^^^^^^^^^^^^^^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'bounding_box'```

#

My main concern is the last line:
self.bbox = AABB.merge(self.left.bounding_box, self.right.bounding_box)

#

This line is supposed to construct an AABB (AABB.merge is @classmethod alternative constructor) by recursively calling the constructor on it.
I am newer to python and am not entirely sure if python is reassigning the instance attributes self.bbox and overwriting the root self.bbox.

steep prairie Feb 21, 2024, 5:17 PM

#

I think the issue is simply that you do self.left = self.construct_bvh_tree(objects, start, mid) and similarly for self.right... but construct_bvh_tree never returns a value, so this just sets them both to None.

#

It's strange to me that construct_bvh_tree modifies self - I'd expect it to have a signature like

@classmethod
def construct_bvh_tree(cls, _src_objects: list[Hittable], start: int, end: int) -> "BVH_Node":

so that it can recusively call itself and use the child nodes as left and right of the node under construction.

little shoal Feb 21, 2024, 5:42 PM

#

steep prairie It's strange to me that `construct_bvh_tree` modifies `self` - I'd expect it to ...

I don't know if you are familiar with C++, but this was the code I was trying to emulate:

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

        int axis = random_int(0,2);
        auto comparator = (axis == 0) ? box_x_compare
                        : (axis == 1) ? box_y_compare
                                      : box_z_compare;

        size_t object_span = end - start;

        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 {
            std::sort(objects.begin() + start, objects.begin() + end, comparator);

            auto mid = start + object_span/2;
            left = make_shared<bvh_node>(objects, start, mid);
            right = make_shared<bvh_node>(objects, mid, end);
        }

        bbox = aabb(left->bounding_box(), right->bounding_box());
    }
    ...
};```

#

I do see what you're saying though

steep prairie Feb 21, 2024, 5:43 PM

#

make_shared is something like calling the constructor and wrapping it into a shared pointer, right? Whereas yours doesn't make a new node, it calls a method on the current one.

little shoal Feb 21, 2024, 5:45 PM

#

yeah

#

how does my code not stack overflow though

steep prairie Feb 21, 2024, 5:47 PM

#

you mean, from the recursion? I think the recursion is finite here, since you halve the interval each call

little shoal Feb 21, 2024, 5:48 PM

#

oh right

steep prairie Feb 21, 2024, 5:48 PM

#

(and unreletadly, since 3.11 you can't get a stack overflow from recursing - I believe the reason why is that the function frames are now always stored on the heap, but however it works, you can recurse all the way to the (adjustable) recursion limit)

little shoal Feb 21, 2024, 5:49 PM

#

so if I turned my function into a classmethod constructor, I wouldn't need to return a value right?

#

@classmethod
def construct_bvh_tree(cls, _src_objects: list[Hittable], start: int, end: int) -> "BVH_Node":```

steep prairie Feb 21, 2024, 5:50 PM

#

You do

little shoal Feb 21, 2024, 5:51 PM

#

what if I used __init__ as my recursive constructor (hypothetically)?

#

btw I have no problem returning a value, but if I understand correctly, only __init__ directly constructs the objects without having to return anything just like the C++ constructor

steep prairie Feb 21, 2024, 5:53 PM

#

steep prairie You do

my advice is to make the constructor trivial:

def __init__(self, bbox: AABB, left: BVH_Node|None, right: BVH_Node|None):
    self.bbox = bbox
    self.left = left
    self.right = right

and then have construct_bvh_tree be an alternative constructor:

@classmethod
def construct_bvh_tree(cls, _src_objects: list[Hittable], start: int, end: int) -> "BVH_Node":
    # do stuff and eventually construct and return a node
    # e.g. the last case would end up doing
    left = cls.construct_bvh_tree(objects, start, mid)
    right = cls.construct_bvh_tree(objects, mid, end)
    return cls(AABB.merge(left.bounding_box, right.bounding_box), left, right)

little shoal Feb 21, 2024, 5:54 PM

#

steep prairie my advice is to make the constructor trivial: ```py def __init__(self, bbox: AAB...

Yeah this is mine:

def __init__(self, list: HittableList) -> None:
        """Constructs a BVH node from a `HittableList`."""
        self.bbox: AABB
        self.left: 'BVH_Node'
        self.right: 'BVH_Node'

        # list.objects is passed by mutable and passed by reference
        self.construct_bvh_tree(list.objects, 0, len(list.objects))

little shoal Feb 21, 2024, 5:55 PM

#

steep prairie my advice is to make the constructor trivial: ```py def __init__(self, bbox: AAB...

ok I will use this

#

thank you

steep prairie Feb 21, 2024, 5:56 PM

#

little shoal what if I used `__init__` as my recursive constructor (hypothetically)?

You could, I guess - in that case you'd want to recursively call not self.left = self.construct_bvh_tree(objects, start, mid), but self.left = BVH_Node(objects, start, mid), and modify the init to have that signature

#

Generally in python, though, one sees the pattern I mentioned - simple main constructors (which can even be turned into a dataclass, in this case) and fancy alternative ones.

little shoal Feb 21, 2024, 6:00 PM

#

steep prairie You could, I guess - in that case you'd want to recursively call not `self.left ...

i don't actually want to use __init__ as my recursive constructor, was just trying to understand how stuff works

limpid roseBOT Feb 21, 2024, 7:00 PM

#

Python help channel closed

This help channel has been closed and it's no longer possible to send messages here. If your question wasn't answered, feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.

#🔒 Recursive Constructor Correct Implementation