search

dilevin / computer-graphics-bounding-volume-hierarchy

Computer Graphics Assignment about Bounding Volume Hierarchies
6 stars 5 forks source link

AABB Ray Intersect Approach #84

Open hugoksp opened 11 months ago

hugoksp commented 11 months ago

According to the handouts and class, we are advised against using any type of depth first search (even with some peeking) as we would eventually have to search through the majority of the nodes since there are lots of overlaps. We are given a pseudocode algorithm for using bfs for searching for closest distance (presumably for point AABB squared distance), is this the same idea that we should modify in order to fit our needs for this file? I am a bit confused on the direction to implement this as I implemented the dfs algorithm by accident when trying different methods and can clearly see the time is same/worse than brute force.

Zhecheng-Wang commented 11 months ago

See #75 for discussions on BFS vs. DFS for ray-AABB. TL;DR: Yes, ray-AABB intersection is basically the same as point-AABB distance, but due to how ray-AABB is implemented, you might want to do DFS for ray-AABB.

However, even with DFS, ray-AABB should be faster than brute force.