Slide 1OverviewLast lectureAcceleration structuresAcceleration structuresSpatial hierarchies: gridsSpatial hierarchies: kd-treesSpatial hierarchies: kd-treesRT with the kd-tree (2)RT with the kd-tree (3)RT with the kd-tree (4)Kd-tree traversalObject hierarchies: BVHsBounding volumesBVH traversalChoosing a structureChoosing a structureChoosing a structureOverviewRay PacketsRay coherenceBVH traversalBVH packet traversalRay packet advantagesData parallelismData parallelismSIMD ray processingOptimized hierarchy constructionRay Tracing, Part 2Christian LauterbachCOMP 770, 2/16/2009OverviewAcceleration structuresSpatial hierarchiesObject hierarchiesInteractive Ray Tracing techniquesRay packetsOptimized hierarchy constructionLast lectureRay TracingFor each pixel: generate rayFor each primitive:Does ray hit primitive?Yes: Test depth / write colorThat means linear time complexity in number of primitives!Acceleration structuresGoal: fast search operation for ray that returns all intersecting primitives Then test only against thoseOperation should take sub-linear timeIn practice: conservative supersetAcceleration structuresBroad classification:Spatial hierarchiesGridsOctreesKd-trees, BSP treesObject hierarchiesBounding volume hierarchiesSpatial kd-treesSpatial hierarchies: gridsRegular subdivision of space into cellsCells almost always cubesEach object is referenced in each cell it overlapsNested grids also possibleRay tracing with the grid:Find entry cell of rayFor each cell:Intersect with all objects in cell. If hit, terminate.Otherwise, walk to next cell ray can hitSpatial hierarchies: kd-treesBinary tree of space subdivisionsEach is axis-aligned plane xy ySpatial hierarchies: kd-treesTraversing a kd-tree: recursiveStart at root nodeFor current node:If inner node:Find intersection of ray with planeIf ray intersects both children, recurse onnear side, then far sideOtherwise, recurse on side it intersectsIf leaf node:Intersect with all object. If hit, terminate.RT with the kd-tree (2)ray 1ray 2ray 3split plane'near' node 'far' nodewhat can the ray possibly hit?RT with the kd-tree (3)three cases:hitpoint above split: far node onlyhitpoint below split: near node onlyotherwise: near, then far'above' and 'below' rather vagueuse distance t along ray ray = origin + t *directionRT with the kd-tree (4)when does the ray intersect?split planesplit plane'near' node 'far' node'near' node 'far' nodet_mint_mint_maxt_maxt_splitt_splitKd-tree traversalSimple and fast implementationIn practice: using stack, not recursionVery quick intersection test (couple FLOPS + tests)Overall: logarithmic complexity for each rayObject hierarchies: BVHsDifferent approach: subdivide objects, not spaceHierarchical clustering of objectsEach cluster represented by bounding volumeBinary treeEach parent node fully contains childrenBounding volumesPractically anything can be bounding volumeJust need ray intersection methodTypical choices:SpheresAxis-aligned bounding boxes (AABBs)Oriented bounding boxes (OBBs)k-DOPsTrade-off between intersection speed and how closely the BV encloses the geometryBVH traversalRecursive algorithm:Start with root nodeFor current node:Does ray intersect node’s BV? If no, returnIs inner node?Yes, recurse on childrenIs leaf node?Intersect with object(s) in node, store intersection resultsNote: can’t return after first intersection!Choosing a structureThere is no ‘best’ acceleration structureAll have pros and consGrid:+ fast construction- bad for high local detail (teapot/stadium)Choosing a structureThere is no ‘best’ acceleration structureAll have pros and conskd-tree:+ fast traversal- expensive build, only static scenesChoosing a structureThere is no ‘best’ acceleration structureAll have pros and consBVH:+ can be updated for dynamic scenes- traversal more expensive than kd-treeOverviewAcceleration structuresSpatial hierarchiesObject hierarchiesInteractive Ray Tracing techniquesRay packetsOptimized hierarchy constructionRay PacketsOften have large set of rays close togetherIdea:trace rays in coherent groups (ray packets)ViewerScreenRay coherenceHow does this change tracing?Traversal and object intersectionwork on group of rays at a timeAlso generate secondary (shadow, …) rays in packetsGeneral idea:If one ray intersects, all are intersectedBVH traversalRecursive algorithm:Start with root nodeFor current node:Does ray intersect node’s BV? If no, returnIs inner node?Yes, recurse on childrenIs leaf node?Intersect ray with all object(s) in node, store intersection resultsBVH packet traversalRecursive algorithm:Start with root nodeFor current node:Does any ray intersect node’s BV? If no, returnIs inner node?Yes, recurse on childrenIs leaf node?Intersect all rays with all object(s) in node, store intersection resultsRay packet advantagesWhy does this make things faster?Less memory bandwidth: nodes/objects only loaded once for rays in packetAllows data parallel processing!Current CPUs: e.g. Intel SSEAll GPUsDisadvantage:Rays can be intersected with objects/nodes they would never hit!Data parallelismEssentially vector operations (SIMD)Operations work on all elements in parallelv1 v2 v3 v4 v5 v6 v7 v8v1 v2 v3 v4 v5 v6 v7 v8w1 w2 w3 w4 w5 w6 w7 w8+=v1+w1 v2+w2 v3+w3 v4+w4 v5+w5 v6+w6 v7+w7 v8+w8Data parallelismVector operations usually as fast as a single scalar operationIntel SSE: 4-wide vectorsGPUs: 8-32 wide Cell: 4-wideVector processors: up to 64,000!SIMD ray processingCan use SIMD units to parallelize for raysEach vector has one component from one rayThus, can process small group at same speed as one ray!ray1ray2ray3ray4ray5ray6ray7ray8triitriitriitriitriitriitriitriitriiOptimized hierarchy constructionThe way the hierarchy is constructed has high impact on traversal