CMSC 635Basic ideaIntersection approachesMaking it easierHow many intersections?SpeedupsFewer intersectionsObject: bounding hierarchyBounding spheresAABBOBBSlabsSpace: partitioningImageAlgorithmic improvementsFaster intersectionsParallel intersectionsSlide 18CMSC 635CMSC 635Ray TracingRay TracingBasic ideaBasic ideaIntersection approachesIntersection approachesPlug parametric ray into implicit shapePlug parametric shape into implicit raySolve implicit ray = implicit shapePlug parametric ray into implicit shapePlug parametric shape into implicit raySolve implicit ray = implicit shapeMaking it easierMaking it easierTransform to cannonical ray (0,0,0)–(0,0,1)Transform to cannonical objectEllipsoid to unit sphere at (0,0,0)Compute in stagesPolygon plane, then polygon edgesNumerical iterationTransform to cannonical ray (0,0,0)–(0,0,1)Transform to cannonical objectEllipsoid to unit sphere at (0,0,0)Compute in stagesPolygon plane, then polygon edgesNumerical iterationHow many intersections?How many intersections?Pixels~103 to ~107Rays per Pixel1 to ~10Primitives~10 to ~107Every ray vs. every primitive~104 to ~1015Pixels~103 to ~107Rays per Pixel1 to ~10Primitives~10 to ~107Every ray vs. every primitive~104 to ~1015SpeedupsSpeedupsFaster intersectionsFewer intersectionsFaster intersectionsFewer intersectionsFewer intersectionsFewer intersectionsObject-basedSpace-basedImage-basedObject-basedSpace-basedImage-basedObject: bounding hierarchyObject: bounding hierarchyBounding spheresAABBOBBSlabsBounding spheresAABBOBBSlabsBounding spheresBounding spheresVery fast to intersectHard to fitPoor fitVery fast to intersectHard to fitPoor fitAABBAABBFast to intersectEasy to fitReasonable fitFast to intersectEasy to fitReasonable fitOBBOBBPretty fast to intersectHarder to fitEigenvectors of covariance matrixIterative minimizationGood fitPretty fast to intersectHarder to fitEigenvectors of covariance matrixIterative minimizationGood fitSlabsSlabsFamilies of planesFast intersectionFamilies of planesFast intersectionSpace: partitioningSpace: partitioningSlabsUniform gridOcttreeBSPSlabsUniform gridOcttreeBSPImageImageCoherenceLight buffer (avoid shadow rays)Pencil tracing/cone tracingImage approximationTruncate ray treeSuccessive refinementContrast-driven antialiasingCoherenceLight buffer (avoid shadow rays)Pencil tracing/cone tracingImage approximationTruncate ray treeSuccessive refinementContrast-driven antialiasingAlgorithmic improvementsAlgorithmic improvementsObject-basedDecide ray doesn’t intersect earlySpace-basedPartial order of intersection testsImage-basedRay-to-ray coherenceObject-basedDecide ray doesn’t intersect earlySpace-basedPartial order of intersection testsImage-basedRay-to-ray coherenceFaster intersectionsFaster intersectionsPrecompute and store with objectCache results from previous testsStop early for rejectPostpone expensive operationsReject then normalizeIf a cheap approximate test exists, do it firstSphere / box / separating axes / …Project to fewer dimensionsPrecompute and store with objectCache results from previous testsStop early for rejectPostpone expensive operationsReject then normalizeIf a cheap approximate test exists, do it firstSphere / box / separating axes / …Project to fewer dimensionsParallel intersectionsParallel intersectionsDistribute pixelsDistribute raysDistribute objectsDistribute pixelsDistribute raysDistribute objectsParallel intersectionsParallel intersectionsLoad balancingScattered rays, blocks, lines, ray queuesCullingCommunication costsDatabaseRay requestsRay resultsLoad balancingScattered rays, blocks, lines, ray queuesCullingCommunication costsDatabaseRay requestsRay