search

alecjacobson / computer-graphics-bounding-volume-hierarchy

Computer Graphics Assignment about Bounding Volume Hierarchies
124 stars 46 forks source link

About pseudo-code for distance queries #60

Open ericxu233 opened 2 years ago

ericxu233 commented 2 years ago

I read the pseudo-code for distance queries and was wondering why do we have the if statement "if d_s < d". Wouldn't the first leaf to be dequeued by the priority queue be the closest object to the query point? We could just do a break statement when we encounter the first leaf and record it. Wouldn't this aslo be more efficient since I wouldn't have to pop all the content in the priority queue. I have tested out both implementations and they work the same. Is there a particular reason that the pseudo-code is written that way with the if statement "if d_s < d"?

abhimadan commented 2 years ago

I think you're right here - great catch! I think it's written that way for simplicity, since the early return is a bit unintuitive. In terms of performance, I don't expect a huge difference since the queue should only have O(tree depth) elements in it, and since that check basically flushes out the queue, it only needs to remove a few elements.