ray tracing ,
The Design of Acceleration Algorithm for Real-time Ray TracingJeong-soo Park
2011/05/31Media System Lab.Yonsei Univ.1 An effective depth data memory system using anescape count buffer for 3D rendering processorsIEICE express, Vol. 8, No. 4A Latency-efficient Stencil/depth Buffer System forMobile 3D Rendering ProcessorsIEICE express (reviewer selected) Ordered Depth-First Layouts for Ray TracingSIGGRAPH Asia 2010, sketches 3 (80%)*2IntroductionBenefit of Ray TracingWhy todays issue?ContributionsBackground & Related WorkBasics of Ray TracingTechnical CategorizationRT execution platformAcceleration technique Ray Differentials for Adaptive Level-of-DetailDerivation of ray differentialRay-diff for texture filteringRay-diff for adaptive antialiasingProbability Heuristics for Ray Tracing AccelerationSimulation Environment for Graphics Acceleration HardwareConclusion & Future Work*3Introduction4Benefit of Ray TracingHigh degree of realistic imageSupport reflection, refraction, caustics naturallyCalculate physically-correct lighting effectSimulate interference between primitives in the scene
5Ray tracing is one of global illumination algorithm to synthesize high degree realistic images as well as to process 3D scene more efficiently than Z-buffer algorithm
Image of nVidia. :Optix : INTERACTIVE RAY TRACING ON NVIDIA QUADRO PROFESSIONAL GRAPHICS SOLUTIONS, developer.nvidia.com, 2009 *5Barrier of Ray TracingComputation All operations are based on real numbers High amount of computationsFor example:Image resolution : 1280 x 720, Scene size : 100K primitives, 10 propagations1280 x 720 x 100K x 10 = 858G times intersection test and shading
6However ray tracing has several barriers to achieve in real-time performance, which are its types and amount of computations.
O(#pixel * #obj * #propagation)*6Why Todays IssueHardware performance growthRaw performance of CPU/GPU increasedGPU as massive parallel architectureMore parallelism exploitedEven CPU starts to expand parallelism Ray tracing algorithm is highly parallel
7Even so, there are several trends that realizes real-time performance of ray tracing.
*Nvidia developer centerParallel architect`ure in commodity PC**Larrabee architecture*Intel, Larrabee: A Many-Core x86 Architecture for Visual Computing, SIGGRAPH 2008*7Why Todays issueIndustrial demands for advanced, realistic graphicsIn addition to be getting complex, it becomes more real-time
8Even so, there are several trends that realizes real-time performance of ray tracing.
Half-Life 2(2004)Real-time Rendering (Game)
A Bugs Life(1998)Toy Story(1995)Car(2006)Finding Nemo(2003)TextureMappingBumpMappingHDRIRayTracingHigh Quality Rendering (Movie)
*8Background & Related Work9Basics of Ray TracingRay tracing processes RAYS to SEARCH corresponding primitivesBasically searching algorithm Z-buffered algorithm processes primitives to sort its projective positionRay tracing algorithm is essentially searching algorithm that finds the primitive that contributes to the screenProcessing PRIMITIVES to SORT onto image plane Processing RAYS to SEARCH contributing objectsZ-buffered rasterizationRay tracing10*10Acceleration AlgorithmsThere are several works for accelerating ray tracing to real-time performance. 11Ray tracing Acceleration worksAcceleration structure : pre-indexing primitives with auxiliary data structureCore acceleration : optimize efficiency of RT core algorithm (traversal & intersection test)Execution platform : exploiting hardware resources efficiently Search AlgorithmRay tracingAcceleration StructureGrid[Kalojanov11], BVH[Lauterbach09], KD-tree, Fast build/update[Kalojanov09, Pantaleoni10]Core AccelerationMLRTA[Reshtov05], Packet[Boulos08] Fast IST[Havel09]PlatformCPU/GPUGPU[Parker10, Aila09], Multi-core[Wald10, Seiler08]GPU build [Lauterbach09]*11Ray Differentials for Adaptive LOD12IntroductionRegular sampling of ray tracing aliasing problemSolutionStochastic samplingMore rays per pixel, EXPENSIVEEg.) Distribution ray tracing, Path tracingTexture filtering (like rasterization)Filtering texels in a pixel, or choose from prefiltered texture map (MIPMAP)Filtering kernel is rays footprint on texture spaceHow to know rays footprint along ray traversalLike other rendering algorithm, ray tracing is another regular sampling technique. It also suffers from aliasing problem.
13*13Related worksBMRT[Gritz96]Estimating difference based on ray traversal distanceOnly valid for primary rayCould not support convergence/divergence of ray ( lens effect )Tracing ray differential[Igehy99]Derivatives of world coordinate positionUsed for geometry subdivision in offline renderer [Christensen03, Christensen06]
Several works has been announced to eliminate aliasing problem in texture mapping
14*14Tracing Ray DifferentialEssentially tracing derivatives of rays starting point (P) and its direction (D)Keep track of whether ray is expanding or shrinking15*15Derivation of Ray DifferentialRay generationRay differentialPrimary rayReflection RayRefraction RayBarycentric CoordinateRay differential is partial derivatives of ray parameters of x, y. Hence ray differentials for each types of ray could be found by differentiating ray generation equation.
16*16Ray differentials for texture filteringLonger edge (R1 or R2) is selected for filtering kernel size
For Mipmapping, appropriate level of mipmap is calculated as: 17
*17Ray differential pipeline designRay differential unit needs 3 DOT3, 17 MUL, 10 ADD, 1 DIV, 1 SQRT18At ray generation stage, differential unit calculates ray differential according to type of ray. Primary rayDOT3 (1)DIV (1)DOT3(2)SQRT (1)MUL (3)MUL (12)ADD (6)MUL (1)MUL (1)P1P2P3P4P5P6P7P8P9P10P11P12P13P14P15Reflection rayDOT3 (1)MUL (1)MUL (3)MUL (1)MUL (3)ADD (6)DOT3(1)Refraction rayDIV (1)MUL (1)MUL (1)ADD (1) MUL (2)MUL (12)ADD (6)DOT3 (1)DOT3(1)*18Result19Scene comparison (no filtering distance based ray differential )
BaseDistance baseRay differential baseBaseDistance baseRay differential base*19
Result20Scene comparison (no filtering distance based ray differential )
BaseDistance baseRay differential base*20Conclusion & Future work21Conclusion & Future worksRay differential could estimated size of ray footprint as the ray propagatesBy differentiating function of world-to-texture space transformation, it is possible to calculate footprint on the textureTexture space footprint could be used to compute:Filtering kernel sizeLevel of mipmapAdaptive supersampling by differential schemeTransform ray differential barycentric differential
22*22Backup23Edge detection using ray differentialFor each sub-pixel, check conditions:Barycentric coordinate differential could be used to estimate hit-point of neighbor rays
3412*24Result25Scene comparison (no filtering distance based ray differential )
*25Why todays issueHardware performance growthRaw performance of CPU/GPU increasedGPU as massive parallel architectureMore parallelism exploitedEven CPU starts to expand parallelism Ray tracing algorithm is highly parallel
Even so, there are several trends that realizes real-time performance of ray tracing.*26IntroductionBenefit of Ray TracingWhy todays issue?ContributionsBackground & Related WorkBasics of Ray TracingTechnical CategorizationRT execution platformAcceleration technique Ray Differentials for Adaptive LODDerivation of ray differentialRay-diff for texture filteringRay-diff for adaptive antialiasingNew Heuristics for Accelerating RTSimulation Environment for Advanced Computer GraphicsConclusion & Future Work*27Benefit of Ray TracingBenefit High Image QualitySupport reflection, refraction, caustics naturallyCalculate lighting effect globally
Efficient processingLogarithmic behavior to scene complexityOnly process the primitive that contributes to final image
28Ray tracing is one of global illumination algorithm to synthesize high degree realistic images as well as to process 3D scene more efficiently than Z-buffer algorithm
*Daniel Pohl, Ray Tracing and Gaming, PC perspective articles from Intel, Jan. 2008
Z-buffer algorithmRay TracingComputationBehavior of graphics algorithm**28
29 Eg. 1 3 Eg. 4 1 Eg. 3 2 Eg. 5 1 (N) (Linear complexity: O(N) ) application
321Graphics Pipeline213N54*291Global Illumination 30
, , (simulation)Eg. 1 ray , 4 1 ray Eg. 3 1 tree (N) Log(N)
231Shadow rayEye rayReflection rayRefraction ray4*30IntroductionBackground & Related WorkRay Differentials for Adaptive LODNew Heuristics for Accelerating RTSimulation Environment for Advanced Computer GraphicsConclusion & Future Work*31