Use of polymorphism with objects and changing h files

[MstrPikachu]

When splitting objects with the AABB tree, we need to decide which objects go on the left or right. We can do this easily by checking the object center. However, this is no such method in Object.h. Are we expected to use if statements and casts for this and other similar situations?

Additionally, the bfs algorithm described in the assignment doesn't prune the tree until a leaf node is reached, instead of pruning the tree early with max distance estimates. Because we only submit source files I don't think we can change h files. Is there any solution to implement this or will I have to follow the assignment exactly?

[Zhecheng-Wang]

On object centers: Object struct in Object.h has BoundingBox box, which provides BoundingBox::center(). I think you are wondering when did bounding box for triangles are computed -- see here.

On pruning: we do prune the tree early with minimum (was "max" typo?) distance estimates, but note that a valid minimum distance estimate is the distance between a query point to a leaf object and we only update our guess when a leaf node is reached.

[MstrPikachu]

About pruning with distances, the idea is that you don't consider a box at all if its minimum distance is larger than our min distance estimate. We can make our min distance estimate an upper bound by finding the farthest distance from the box, and then we can update our guess sooner instead of updating when we hit a leaf.

[Zhecheng-Wang]

You can't modify .h files, so you need to make good use of what's provided in .cpp. Following the pseudocode provided is definitely the safe solution.

If I am understanding correctly, you would like to use point-box distance as an upper bound for the minimum distance estimate? But point-box distance will be >> point-leaf object distance.

Would you mind elaborating more on "estimate an upper bound by finding the farthest distance from the box" (farthest distance between query point and which box)? Maybe post some pseudocode (based on README) so I can see the branches?

[MstrPikachu]

// initialize a queue prioritized by minimum distance
d_r ← distance to farthest point root's box
Q.insert(d_r, root)
// initialize minimum distance seen so far
d ← ∞
while Q not empty 
  // d_s: distance from query to subtree's bounding box
  (d_s, subtree) ← Q.pop
  if d_s < d
    if subtree is a leaf
      d ← min[ d , distance from query to leaf object ]
    else

    // Everything is the same up to here

      d_l ← closest distance to left's box
        if d_l <= d // ignore boxes that are farther than our upper bound on the min guess so far
          Q.insert(d_l ,subtree.left)
          d = min(d, distance from query point to farthest point in the box) // update our min guess
      // same thing for right child

[MstrPikachu]

If I am understanding correctly, you would like to use point-box distance as an upper bound for the minimum distance estimate? But point-box distance will be >> point-leaf object distance.

You are correct, the point-box (farthest) distance should be > point-leaf distance. The idea is that if we use this as an estimate, then if we see another box with a closest distance > our estimate, we can reject it immediately (because all of its leaves will be strictly farther away than the leaves in our current best estimate).

[Zhecheng-Wang]

I see what you mean. I think this will work. If a point-box A maximum distance is > point-box B minimum distance, then box A is already a better candidate compared to box B no matter what -- so we can safely skip box B.

But yeah it does require some functions like point_box_maximum_distance which are not declared in .h.

I did not personally implement and test this, so I wouldn't recommend you implement it this way unless you do some testing with the baseline before submission. I think it is ok to declare and use some helper function in .cpp, but please double-check with the professor to be sure.

Interesting discussion btw.

[MstrPikachu]

Thank you. There is no class on Monday so I will email the professor.

[MstrPikachu]

After thinking about it again I realized that my method is redundant. Because we are using a priority queue, a leaf will have set the min distance so far before getting to any far boxes, which will get pruned afterwards .