1Computer Graphics (Fall 2008)Computer Graphics (Fall 2008)COMS 4160, Lecture 15: Ray Tracinghttp://www.cs.columbia.edu/~cs4160Effects needed for RealismEffects needed for Realism (Soft) Shadows Reflections (Mirrors and Glossy) Transparency (Water, Glass) Interreflections (Color Bleeding) Complex Illumination (Natural, Area Light) Realistic Materials (Velvet, Paints, Glass) And many moreImage courtesy Paul Heckbert 1983Ray TracingRay Tracing Different Approach to Image Synthesis as compared to Hardware pipeline (OpenGL) Pixel by Pixel instead of Object by Object Easy to compute shadows/transparency/etcOutlineOutline History Basic Ray Casting (instead of rasterization) Comparison to hardware scan conversion Shadows / Reflections (core algorithm) Ray-Surface Intersection Optimizations Current ResearchSection 10 in textRay Tracing: HistoryRay Tracing: History Appel 68 Whitted 80 [recursive ray tracing]  Landmark in computer graphics Lots of work on various geometric primitives Lots of work on accelerations Current Research Real-Time raytracing (historically, slow technique) Ray tracing architecture2OutlineOutline History Basic Ray Casting (instead of rasterization) Comparison to hardware scan conversion Shadows / Reflections (core algorithm) Ray-Surface Intersection Optimizations Current ResearchRay CastingRay CastingProduce same images as with OpenGL Visibility per pixel instead of Z-buffer Find nearest object by shooting rays into scene Shade it as in standard OpenGLSection 10.1-10.2 in text (we show visually, omitting math)Ray CastingVirtual ViewpointVirtual Screen ObjectsRay misses all objects: Pixel colored blackRay intersects object: shade using color, lights, materialsMultiple intersections: Use closest one (as does OpenGL)Comparison to hardware scanComparison to hardware scan--lineline Per-pixel evaluation, per-pixel rays (not scan-convert each object). On face of it, costly But good for walkthroughs of extremely large models (amortize preprocessing, low complexity) More complex shading, lighting effects possibleOutlineOutline History Basic Ray Casting (instead of rasterization) Comparison to hardware scan conversion Shadows / Reflections (core algorithm) Ray-Surface Intersection Optimizations Current ResearchShadowsVirtual ViewpointVirtual Screen Objects10.5 in textbookLight SourceShadow ray to light is unblocked: object visibleShadow ray to light is blocked: object in shadow3Shadows: Numerical Issues• Numerical inaccuracy may cause intersection to be below surface (effect exaggerated in figure)• Causing surface to incorrectly shadow itself• Move a little towards light before shooting shadow rayMirror Reflections/RefractionsVirtual ViewpointVirtual Screen Objects10.6 in textbookGenerate reflected ray in mirror direction, Get reflections and refractions of objectsRecursive Ray TracingRecursive Ray TracingFor each pixel Trace Primary Eye Ray, find intersection Trace Secondary Shadow Ray(s) to all light(s) Color = Visible ? Illumination Model : 0 ; Trace Reflected Ray Color += reflectivity * Color of reflected rayAlso see section 10.4 in textProblems with RecursionProblems with Recursion Reflection rays may be traced forever Generally, set maximum recursion depth Same for transmitted rays (take refraction into account)Turner Whitted 1980Effects needed for Realism•(Soft)Shadows• Reflections (Mirrors and Glossy)• Transparency (Water, Glass)• Interreflections (Color Bleeding)• Complex Illumination (Natural, Area Light)• Realistic Materials (Velvet, Paints, Glass)Discussed in this lectureNot discussed but possible with distribution ray tracing (10.11)Hard (but not impossible) with ray tracing; radiosity methods4OutlineOutline History Basic Ray Casting (instead of rasterization) Comparison to hardware scan conversion Shadows / Reflections (core algorithm) Ray-Surface Intersection Optimizations Current ResearchRay/Object IntersectionsRay/Object Intersections Heart of Ray Tracer One of the main initial research areas Optimized routines for wide variety of primitives Various types of info Shadow rays: Intersection/No Intersection Primary rays: Point of intersection, material, normals Texture coordinates Work out examples Triangle, sphere, polygon, general implicit surfaceSection 10.3RayRay--Tracing Transformed ObjectsTracing Transformed ObjectsWe have an optimized ray-sphere test But we want to ray trace an ellipsoid…Solution: Ellipsoid transforms sphere Apply inverse transform to ray, use ray-sphere Allows for instancing (traffic jam of cars)Mathematical details worked out in classSection 10.8 of textOutlineOutline History Basic Ray Casting (instead of rasterization) Comparison to hardware scan conversion Shadows / Reflections (core algorithm) Ray-Surface Intersection Optimizations Current ResearchAccelerationAccelerationTesting each object for each ray is slow Fewer RaysAdaptive sampling, depth control Generalized RaysBeam tracing, cone tracing, pencil tracing etc. Faster Intersections Optimized Ray-Object Intersections Fewer IntersectionsSection 10.9 goes into more detail, we just discuss some approaches at high levelAcceleration StructuresAcceleration StructuresBounding boxes (possibly hierarchical)If no intersection bounding box, needn’t check objectsBounding BoxRaySpatial Hierarchies (Oct-trees, kd trees, BSP trees)5Acceleration Structures: GridsAcceleration Structures: GridsOutlineOutline History Basic Ray Casting (instead of rasterization) Comparison to hardware scan conversion Shadows / Reflections (core algorithm) Ray-Surface Intersection Optimizations Current ResearchInteractive Interactive RaytracingRaytracing Ray tracing historically slow Now viable alternative for complex scenes  Key is sublinear complexity with acceleration; need not process all triangles in scene Allows many effects hard in hardware OpenRT project real-time ray tracing (http://www.openrt.de)RaytracingRaytracingon Graphics Hardwareon Graphics Hardware Modern Programmable Hardware general streaming architecture Can map various elements of ray tracing Kernels like eye rays, intersect etc.  In vertex or fragment programs Convergence between hardware, ray tracing[Purcell et al. 2002,