BoundingVolumes(包围盒）·Bounding Volumesbounding- Besides acceleration forsphereray tracing. Boundingvolumes could be used forother motivations, such asnon-alignedHidden Surface Removalbounding boxCollision(碰撞)Detectionaxis-alignedboundingbox
Bounding Volumes(包围盒) • Bounding Volumes – Besides acceleration for ray tracing. Bounding volumes could be used for other motivations, such as Hidden Surface Removal, Collision(碰撞) Detection
BoundingVolumes(包围盒）· Ray Intersection with Bounding Volumes- Including Ray/Box intersection and Ray/SphereIntersection. Both have been discussed in chapter 4 “RayTracing"maxmintomax1RR.min0min
Bounding Volumes(包围盒) • Ray Intersection with Bounding Volumes – Including Ray/Box intersection and Ray/Sphere Intersection. Both have been discussed in chapter 4 “Ray Tracing”. Ro Pc Rd d tP r min 0 t min 1 t max 0 t max 1 t min 0 t min 1 t max 0 t max 1 t
Hierarchical Bounding Volume·HierarchicalBoundingVolume(HBV:层次包围盒）- Limitation of bounding volume: Still need to test ray against every object, O(n) timecomplexity, where n is the number of objects. A natural extension to bounding volumes is ahierarchical bounding volume (HBV)
Hierarchical Bounding Volume • Hierarchical Bounding Volume (HBV:层次包围盒) – Limitation of bounding volume • Still need to test ray against every object, O(n) time complexity, where n is the number of objects. – A natural extension to bounding volumes is a hierarchical bounding volume (HBV)
- Given the bounding volumes of the objects in thescene, a tree data structure of bounding volumes iscreated with the bounding volumes of the objects atthe leaves.-Each interior nodev of HBV corresponds to thebounding volumes that completely encloses thebounding volumes of all the children nodes of y
– Given the bounding volumes of the objects in the scene, a tree data structure of bounding volumes is created with the bounding volumes of the objects at the leaves. – Each interior node v of HBV corresponds to the bounding volumes that completely encloses the bounding volumes of all the children nodes of v
Hierarchical Bounding Volume: Hierarchical Bounding Volume (HBV)- The method for testing a ray with the objects in thescene using HBV:: First test whether the ray intersect with the boundingvolume at the root node. If not intersected, the raycannot intersect any object.: Otherwise, recursively test the hierarchy for thosenodes of HBV whose bounding volumes areintersected by the ray
Hierarchical Bounding Volume • Hierarchical Bounding Volume (HBV) – The method for testing a ray with the objects in the scene using HBV: • First test whether the ray intersect with the bounding volume at the root node. If not intersected, the ray cannot intersect any object. • Otherwise, recursively test the hierarchy for those nodes of HBV whose bounding volumes are intersected by the ray