Lecture 9: Intro to Ray-Tracing & Accelerating Ray-Scene Intersection (32)
Spectato54
How would we determine optimal volume bounds?
ncastaneda02
@Spectato54 The most important factor when determining volume bounds is how easy it is to determine if a ray intersects with it - in that sense a cube/rectangular prism would likely be the best bounding shape for an object as an intersection is as easy as calculating a plane intersection. As for determining the box, you could likely just take the furthest point of the object in each direction and then create planes connecting them
rishiarjun
In response to the question asking about finding optimal volume bounds, I searched up about it and found this interesting paper (https://www.sciencedirect.com/science/article/pii/S0885064X08000745) that talks about finding optimal volumes subintervals as a NP-Hard problem. The article here talks about forming volume boundaries using a n-dimensional unit cube, and how to calculate using different point sets. The overarching problem being solved is finding a subinterval of either minimum or maximum volume that contains k of n points.
StaffDanCubed
3 slides later they also mentioned that there might exist a computational advantage for making all the planes axis aligned, which is definitely an interesting thing to think about: since performance is all we care about here, it would make sense to go with an axis aligned bounding box; but if there’s an object that has a really bad approximation by the axis aligned bounding box, then it could force us to subdivide many times before we are confident enough that it is a hit, which will cost extra computation. Perhaps this conflicting trade off is what makes this problem so difficult.
adham-elarabawy
It seems as though the optimal bounding box would be defined by the minimal area needed to cover the entire object, which being easily represented and tested for intersections. I can see how circles and rectangles are much easier to test for intersections, but at the same time, it is not immediately intuitive to me why they balance the tradeoff better than other shape primitives. I wonder if there is a slightly more complex shape that is (1) easy to represent mathematically, (2) relatively simple to test for intersections, (3) easy to optimize to fit the underlying object, and (4) of minimal enough area to easily exclude rays that aren't intersecting.
omaryu17
Something I wondered while reading this slide was how collision detection between objects can be determined. Calculating the distance between bounding volumes seems to be a good start, but how might it differ between different bounding volume shapes, i.e. a circle to a rectangle or if an object is constantly moving/resizing? I found this documentation: https://developer.mozilla.org/en-US/docs/Games/Techniques/3D_collision_detection, which talks about implementing collision detection for 3D objects and some different ways to go about testing for overlaps. I found it really interesting to see how they optimized some of the checks. They included this simulation if anyone is interested in playing around with it: https://mozdevs.github.io/gamedev-js-3d-aabb/physics.html.
lwg0320
Optimal volume bounds reminds me of collision detection in games. Most video games's collision detection is either a boxes or spheres. It is reflected in Unity with rigidbody and collision detection as box colliders and sphere colliders are two of the most common colliders used!
How would we determine optimal volume bounds?
@Spectato54 The most important factor when determining volume bounds is how easy it is to determine if a ray intersects with it - in that sense a cube/rectangular prism would likely be the best bounding shape for an object as an intersection is as easy as calculating a plane intersection. As for determining the box, you could likely just take the furthest point of the object in each direction and then create planes connecting them
In response to the question asking about finding optimal volume bounds, I searched up about it and found this interesting paper (https://www.sciencedirect.com/science/article/pii/S0885064X08000745) that talks about finding optimal volumes subintervals as a NP-Hard problem. The article here talks about forming volume boundaries using a n-dimensional unit cube, and how to calculate using different point sets. The overarching problem being solved is finding a subinterval of either minimum or maximum volume that contains k of n points.
3 slides later they also mentioned that there might exist a computational advantage for making all the planes axis aligned, which is definitely an interesting thing to think about: since performance is all we care about here, it would make sense to go with an axis aligned bounding box; but if there’s an object that has a really bad approximation by the axis aligned bounding box, then it could force us to subdivide many times before we are confident enough that it is a hit, which will cost extra computation. Perhaps this conflicting trade off is what makes this problem so difficult.
It seems as though the optimal bounding box would be defined by the minimal area needed to cover the entire object, which being easily represented and tested for intersections. I can see how circles and rectangles are much easier to test for intersections, but at the same time, it is not immediately intuitive to me why they balance the tradeoff better than other shape primitives. I wonder if there is a slightly more complex shape that is (1) easy to represent mathematically, (2) relatively simple to test for intersections, (3) easy to optimize to fit the underlying object, and (4) of minimal enough area to easily exclude rays that aren't intersecting.
Something I wondered while reading this slide was how collision detection between objects can be determined. Calculating the distance between bounding volumes seems to be a good start, but how might it differ between different bounding volume shapes, i.e. a circle to a rectangle or if an object is constantly moving/resizing? I found this documentation: https://developer.mozilla.org/en-US/docs/Games/Techniques/3D_collision_detection, which talks about implementing collision detection for 3D objects and some different ways to go about testing for overlaps. I found it really interesting to see how they optimized some of the checks. They included this simulation if anyone is interested in playing around with it: https://mozdevs.github.io/gamedev-js-3d-aabb/physics.html.
Optimal volume bounds reminds me of collision detection in games. Most video games's collision detection is either a boxes or spheres. It is reflected in Unity with rigidbody and collision detection as box colliders and sphere colliders are two of the most common colliders used!